×

Tractable approximate deduction for OWL. (English) Zbl 1352.68233

Summary: Today’s ontology applications require efficient and reliable description logic (DL) reasoning services. Expressive DLs usually have high worst case complexity while tractable DLs are restricted in terms of expressive power. This brings a new challenge: can users use expressive DLs to build their ontologies and still enjoy the efficient services as in tractable languages? Approximation has been considered as a solution to this challenge; however, traditional approximation approaches have limitations in terms of performance and usability. In this paper, we present a tractable approximate reasoning framework for OWL 2 that improves efficiency and guarantees soundness. Evaluation on ontologies from benchmarks and real-world use cases shows that our approach can do reasoning on complex ontologies efficiently with a high recall.

MSC:

68T30 Knowledge representation
68T27 Logic in artificial intelligence

Software:

DLog; TrOWL
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Baader, F.; Brandt, S.; Lutz, C., Pushing the \(EL\) envelope, (Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 (2005), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers Edinburgh, UK)
[3] (Baader, F.; Calvanese, D.; McGuinness, D. L.; Nardi, D.; Patel-Schneider, P. F., The Description Logic Handbook: Theory, Implementation, and Applications (2003), Cambridge University Press) · Zbl 1058.68107
[5] Boddy, M.; Dean, T., Solving time-dependent planning problems, (Proceedings of the 11th International Joint Conference on Artificial Intelligence, vol. 2. Proceedings of the 11th International Joint Conference on Artificial Intelligence, vol. 2, IJCAI’89 (1989), Morgan Kaufmann Publishers Inc.: Morgan Kaufmann Publishers Inc. San Francisco, CA, USA), 979-984
[6] Botoeva, E.; Calvanese, D.; Rodriguez-Muro, M., Expressive approximations in DL-Lite ontologies, (Proc. of the 14th Int. Conf. on Artificial Intelligence: Methodology, Systems, Applications. Proc. of the 14th Int. Conf. on Artificial Intelligence: Methodology, Systems, Applications, AIMSA 2010. Proc. of the 14th Int. Conf. on Artificial Intelligence: Methodology, Systems, Applications. Proc. of the 14th Int. Conf. on Artificial Intelligence: Methodology, Systems, Applications, AIMSA 2010, Lecture Notes in Computer Science, vol. 6304 (2010), Springer), 21-31
[7] Cadoli, M.; Donini, F. M., A survey on knowledge compilation, AI Commun., 10, 137-150 (1997)
[8] Cadoli, M.; Schaerf, M., Approximation in concept description languages, (Nebel, B.; Rich, C.; Swartout, W. R., Proceedings of the Third International Conference on Principles of Knowledge Representation and Reasoning. Proceedings of the Third International Conference on Principles of Knowledge Representation and Reasoning, KR92 (1992), Morgan Kaufmann), 330-341
[9] Cadoli, M.; Schaerf, M., On the complexity of entailment in propositional multivalued logics, Ann. Math. Artif. Intell., 18, 29-50 (1996) · Zbl 0890.03010
[10] Calvanese, D.; De Giacomo, G.; Lembo, D.; Lenzerini, M.; Rosati, R., Tractable reasoning and efficient query answering in description logics: the dl-lite family, J. Autom. Reason., 39, 385-429 (2007) · Zbl 1132.68725
[11] Calvanese, D.; Giacomo, G. D.; Lembo, D.; Lenzerini, M.; Rosati, R., Data complexity of query answering in description logics, Artif. Intell., 195, 335-360 (2013) · Zbl 1270.68294
[16] Dolby, J.; Fokoue, A.; Kalyanpur, A.; Kershenbaum, A.; Schonberg, E.; Srinivas, K.; Ma, L., Scalable semantic retrieval through summarization and refinement, (Proceedings of the 22nd National Conference on Artificial intelligence, vol. 1. Proceedings of the 22nd National Conference on Artificial intelligence, vol. 1, AAAI’07 (2007), AAAI Press), 299-304
[17] Donini, F. M.; Massacci, F., EXPTIME tableaux for ALC, Artif. Intell., 124, 87-138 (2000) · Zbl 0952.68136
[18] Du, J.; Qi, G.; Pan, J. Z.; Shen, Y. D., A decomposition-based approach to optimizing conjunctive query answering in OWL DL, (Bernstein, A.; Karger, D. R.; Heath, T.; Feigenbaum, L.; Maynard, D.; Motta, E.; Thirunarayan, K., International Semantic Web Conference. International Semantic Web Conference, Lecture Notes in Computer Science, vol. 5823 (2009), Springer), 146-162
[20] Finger, M.; Wasserman, R., Approximate and limited reasoning: semantics, proof theory, expressivity and control, J. Log. Comput., 14, 179-204 (2004) · Zbl 1101.68086
[21] Finger, M.; Wassermann, R., Logics for approximate reasoning: approximating classical logic “from above”, (Advances in Artificial Intelligence (2002), Springer), 21-30 · Zbl 1031.68115
[23] Frisch, A. M., Inference without chaining, (Proceedings of the 10th International Joint Conference on Artificial Intelligence, vol. 1. Proceedings of the 10th International Joint Conference on Artificial Intelligence, vol. 1, IJCAI’87 (1987), Morgan Kaufmann Publishers Inc.: Morgan Kaufmann Publishers Inc. San Francisco, CA, USA), 515-519
[25] Groot, P.; Stuckenschmidt, H.; Wache, H., Approximating description logic classification for semantic web reasoning, (Proceedings of the Second European Conference on the Semantic Web: Research and Applications. Proceedings of the Second European Conference on the Semantic Web: Research and Applications, ESWC’05 (2005), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 318-332
[26] Grosof, B. N.; Horrocks, I.; Volz, R.; Decker, S., Description logic programs: combining logic programs with description logic, (Proceedings of the 12th International Conference on World Wide Web. Proceedings of the 12th International Conference on World Wide Web, WWW ’03 (2003), ACM: ACM New York, NY, USA), 48-57
[28] Hitzler, P.; Vrandecic, D., Resolution-based approximate reasoning for OWL DL, (Gil, Y.; etal., Proceedings of the 4th International Semantic Web Conference. Proceedings of the 4th International Semantic Web Conference, Galway, Ireland, November 2005. Proceedings of the 4th International Semantic Web Conference. Proceedings of the 4th International Semantic Web Conference, Galway, Ireland, November 2005, Lecture Notes in Computer Science, vol. 3729 (2005), Springer: Springer Berlin), 383-397
[30] Horrocks, I.; Kutz, O.; Sattler, U., The even more irresistible \(SROIQ\), (Proc. of the 10th Int. Conf. on Principles of Knowledge Representation and Reasoning. Proc. of the 10th Int. Conf. on Principles of Knowledge Representation and Reasoning, KR 2006 (2006), AAAI Press), 57-67
[31] Horrocks, I.; Sattler, U., Decidability of \(SHIQ\) with complex role inclusion axioms, Artif. Intell., 160, 79-104 (2004) · Zbl 1086.68129
[32] Horrocks, I.; Sattler, U.; Tobies, S., Practical reasoning for very expressive description logics, Log. J. IGPL, 8, 239-264 (2000) · Zbl 0967.03026
[33] Horrocks, I.; Sattler, U.; Tobies, S., Reasoning with individuals for the description logic \(SHIQ\), (McAllester, D., Proc. of the 17th Int. Conf. on Automated Deduction. Proc. of the 17th Int. Conf. on Automated Deduction, CADE 2000. Proc. of the 17th Int. Conf. on Automated Deduction. Proc. of the 17th Int. Conf. on Automated Deduction, CADE 2000, Lecture Notes in Computer Science, vol. 1831 (2000), Springer), 482-496 · Zbl 0963.68197
[35] Horvitz, E. J., Reasoning under varying and uncertain resource constraints, (Proceedings of the Seventh National Conference on Artificial Intelligence. Proceedings of the Seventh National Conference on Artificial Intelligence, AAAI 1988 (1988)), 111-116
[36] Hudek, A. K.; Weddell, G., Binary absorption in tableaux-based reasoning for description logics, (Proc. of the 2006 Int. Workshop on Description Logics. Proc. of the 2006 Int. Workshop on Description Logics, DL 2006, vol. 189 (2006))
[37] Hustadt, U.; Motik, B.; Sattler, U., Reducing \(SHIQ^-\) description logic to disjunctive datalog programs, (Dubois, D.; Welty, C. A.; Williams, M. A., Proc. of the 9th Int. Conference on Principles of Knowledge Representation and Reasoning. Proc. of the 9th Int. Conference on Principles of Knowledge Representation and Reasoning, KR 2004 (2004), AAAI Press: AAAI Press Whistler, Canada), 152-162
[38] Kautz, H.; Selman, B., A general framework for knowledge compilation, (Processing Declarative Knowledge (1991), Springer), 287-300
[39] Kautz, H.; Selman, B., Forming concepts for fast inference, (Foundations of Knowledge Representation and Reasoning (1994), Springer), 200-215
[40] Kazakov, Y., RIQ and SROIQ are harder than SHOIQ, (Brewka, G.; Lang, J., KR 2008 (2008), AAAI Press), 274-284
[42] Kazakov, Y.; Krötzsch, M.; Simančík, F., Concurrent classification of \(EL\) ontologies, (Aroyo, L.; Welty, C.; Alani, H.; Taylor, J.; Bernstein, A.; Kagal, L.; Noy, N.; Blomqvist, E., Proceedings of the 10th International Semantic Web Conference. Proceedings of the 10th International Semantic Web Conference, ISWC’11. Proceedings of the 10th International Semantic Web Conference. Proceedings of the 10th International Semantic Web Conference, ISWC’11, LNCS, vol. 7032 (2011), Springer)
[43] Kazakov, Y.; Krötzsch, M.; Simančík, F., Practical reasoning with nominals in the \(EL\) family of description logics, (Brewka, G.; Eiter, T.; McIlraith, S. A., Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning. Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning, KR’12 (2012), AAAI Press), 264-274
[44] Krötzsch, M., Efficient rule-based inferencing for OWL EL, (Walsh, T., Proceedings of the 22nd International Joint Conference on Artificial Intelligence. Proceedings of the 22nd International Joint Conference on Artificial Intelligence, IJCAI’11 (2011), AAAI Press/IJCAI), 2668-2673
[45] Krötzsch, M., The not-so-easy task of computing class subsumptions in owl rl, (The Semantic Web-ISWC 2012 (2012), Springer), 279-294
[46] Krötzsch, M.; Rudolph, S.; Hitzler, P., Complexity boundaries for Horn description logics, (Proceedings of the 22nd AAAI Conference on Artificial Intelligence. Proceedings of the 22nd AAAI Conference on Artificial Intelligence, AAAI’07 (2007), AAAI Press), 452-457
[48] Levesque, H. J., Logic and the complexity of reasoning, J. Philos. Log., 17, 355-389 (1988)
[50] Levesque, H. J.; Brachman, R. J., A Fundamental Tradeoff in Knowledge Representation and Reasoning (1984), Laboratory for Artificial Intelligence Research, Fairchild, Schlumberger
[51] LukÁcsy, G.; Szeredi, P., Efficient description logic reasoning in Prolog: the DLog system, Theory Pract. Log. Program., 9, 343-414 (2009) · Zbl 1179.68024
[52] Lutz, C.; Walther, D.; Wolter, F., Conservative extensions in expressive description logics, (Veloso, M., Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI’07 (2007), AAAI Press), 453-458
[53] Massacci, F., Efficient approximate deduction and an application to computer security (1998), Universitá di Roma I “La Sapienza”, Dipartimento di Informatica e Sistemistica, Ph.D. thesis
[54] Miñarro-Giménez, J. A.; Blagec, K.; Boyce, R. D.; Adlassnig, K. P.; Samwald, M., An ontology-based, mobile-optimized system for pharmacogenomic decision support at the point-of-care, PLoS ONE, 9, Article e93769 pp. (2014)
[55] Motik, B., Reasoning in description logics using resolution and deductive databases (2006), Univesität Karlsruhe (TH): Univesität Karlsruhe (TH) Karlsruhe, Germany, Ph.D. thesis
[58] Motik, B.; Sattler, U., A comparison of reasoning techniques for querying large description logic aboxes, (Hermann, M.; Voronkov, A., Proc. of the 13th Int. Conference on Logic for Programming Artificial Intelligence and Reasoning. Proc. of the 13th Int. Conference on Logic for Programming Artificial Intelligence and Reasoning, LPAR 2006. Proc. of the 13th Int. Conference on Logic for Programming Artificial Intelligence and Reasoning. Proc. of the 13th Int. Conference on Logic for Programming Artificial Intelligence and Reasoning, LPAR 2006, LNCS, vol. 4246 (2006), Springer: Springer Phnom Penh, Cambodia), 227-241 · Zbl 1165.68506
[59] Motik, B.; Shearer, R.; Horrocks, I., Hypertableau reasoning for description logics, J. Artif. Intell. Res., 36, 165-228 (2009) · Zbl 1192.68664
[61] Pan, J. Z.; Thomas, E., Approximating OWL-DL ontologies, (Proceedings of the 22nd National Conference on Artificial Intelligence, vol. 2. Proceedings of the 22nd National Conference on Artificial Intelligence, vol. 2, AAAI’07 (2007), AAAI Press), 1434-1439
[62] Pan, J. Z.; Thomas, E.; Ren, Y.; Taylor, S., Exploiting tractable fuzzy and crisp reasoning in ontology applications, IEEE Comput. Intell. Mag., 7, 2, 45-53 (2012)
[63] Parreiras, F. S.; Staab, S., Using ontologies with UML class-based modeling: the TwoUse approach, Data Knowl. Eng., 69, 1194-1207 (2010), special issue on contribution of ontologies in designing advanced information systems
[64] Patel-Schneider, P. F., A four-valued semantics for terminological logics, Artif. Intell., 38, 319-351 (1989) · Zbl 0664.03024
[67] Romero, A. A.; Grau, B. C.; Horrocks MORe, I., Modular combination of OWL reasoners for ontology classification, (Proceedings of the 11th International Semantic Web Conference. Proceedings of the 11th International Semantic Web Conference, ISWC 2012. Proceedings of the 11th International Semantic Web Conference. Proceedings of the 11th International Semantic Web Conference, ISWC 2012, LNCS (2012), Springer)
[68] Rudolph, S.; Tserendorj, T.; Hitzler, P., What is approximate reasoning?, (Calvanese, D.; Lausen, G., Proceedings of the 2nd International Conference on Web Reasoning and Rule Systems. Proceedings of the 2nd International Conference on Web Reasoning and Rule Systems, RR2008. Proceedings of the 2nd International Conference on Web Reasoning and Rule Systems. Proceedings of the 2nd International Conference on Web Reasoning and Rule Systems, RR2008, LNCS, vol. 5341 (2008), Springer), 150-164
[69] Schaerf, A., Reasoning with individuals in concept languages, Data Knowl. Eng., 13, 141-176 (1994)
[70] Schaerf, M.; Cadoli, M., Tractable reasoning via approximation, Artif. Intell., 74, 249-310 (1995) · Zbl 1014.03512
[71] Selman, B.; Kautz, H., Knowledge compilation using Horn approximations, (Proceedings of the Ninth National Conference on Artificial Intelligence, vol. 2. Proceedings of the Ninth National Conference on Artificial Intelligence, vol. 2, AAAI’91 (1991), AAAI Press), 904-909
[72] Selman, B.; Kautz, H., Knowledge compilation and theory approximation, J. ACM, 43, 193-224 (1996) · Zbl 0882.68137
[74] Sirin, E.; Cuenca Grau, B.; Parsia, B., From wine to water: optimizing description logic reasoning for nominals, (Proceedings of KR-2006, Tenth International Conference on Principles of Knowledge Representation and Reasoning. Proceedings of KR-2006, Tenth International Conference on Principles of Knowledge Representation and Reasoning, Lake District of the United Kingdom, June 2-5, 2006 (2006), AAAI Press), 90-99
[76] Stuckenschmidt, H.; van Harmelen, F., Approximating terminological queries, (Larsen, H.; etal., Proceedings of the 4th International Conference on Flexible Query Answering Systems. Proceedings of the 4th International Conference on Flexible Query Answering Systems, FQAS’02. Proceedings of the 4th International Conference on Flexible Query Answering Systems. Proceedings of the 4th International Conference on Flexible Query Answering Systems, FQAS’02, Advances in Soft Computing, vol. 2522 (2002), Springer-Verlag), 329-343
[77] Suntisrivaraporn, B., Module extraction and incremental classification: a pragmatic approach for \(EL^+\) ontologies, (Bechhofer, S.; Hauswirth, M.; Hoffmann, J.; Koubarakis, M., Proceedings of the 5th European Semantic Web Conference. Proceedings of the 5th European Semantic Web Conference, ESWC’08. Proceedings of the 5th European Semantic Web Conference. Proceedings of the 5th European Semantic Web Conference, ESWC’08, Lecture Notes in Computer Science, vol. 5021 (2008), Springer-Verlag), 230-244
[80] Tsarkov, D.; Horrocks, I.; Patel-Schneider, P. F., Optimizing terminological reasoning for expressive description logics, J. Autom. Reason., 39, 277-316 (2007) · Zbl 1132.68742
[81] Tserendorj, T.; Rudolph, S.; Krötzsch, M.; Hitzler, P., Approximate OWL-reasoning with screech, (Calvanese, D.; Lausen, G., Proceedings of the Web Reasoning and Rule Systems, Second International Conference. Proceedings of the Web Reasoning and Rule Systems, Second International Conference, RR 2008, Karlsruhe, Germany, October 31-November 1, 2008. Proceedings of the Web Reasoning and Rule Systems, Second International Conference. Proceedings of the Web Reasoning and Rule Systems, Second International Conference, RR 2008, Karlsruhe, Germany, October 31-November 1, 2008, LNCS, vol. 5341 (2008), Springer), 165-180
[82] Urquhart, A., Hard examples for resolution, J. ACM, 34, 209-219 (1987) · Zbl 0639.68093
[83] Wache, H.; Groot, P.; Stuckenschmidt, H., Scalable instance retrieval for the semantic web by approximation, (Proceedings of the 2005 International Conference on Web Information Systems Engineering. Proceedings of the 2005 International Conference on Web Information Systems Engineering, WISE’05 (2005), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 245-254
[84] Walter, T.; Silva Parreiras, F.; Staab, S., OntoDSL: an ontology-based framework for domain-specific languages, (Proceedings of the 12th International Conference on Model Driven Engineering Languages and Systems. Proceedings of the 12th International Conference on Model Driven Engineering Languages and Systems, MODELS ’09 (2009), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 408-422
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.