Converting Instance Checking to Subsumption: A Rethink for Object Queries over Practical Ontologies

Jia Xu¹, Patrick Shironoshita¹, Ubbo Visser², Nigel John¹, Mansur Kabuka¹

¹Department of Electrical and Computer Engineering, University of Miami, Coral Gables, USA.
²Department of Computer Science, University of Miami, Coral Gables, USA.

DOI: 10.4236/ijis.2015.51005                

Abstract

Efficiently querying Description Logic (DL) ontologies is becoming a vital task in various data-intensive DL applications. Considered as a basic service for answering object queries over DL ontologies, instance checking can be realized by using the most specific concept (MSC) method, which converts instance checking into subsumption problems. This method, however, loses its simplicity and efficiency when applied to large and complex ontologies, as it tends to generate very large MSCs that could lead to intractable reasoning. In this paper, we propose a revision to this MSC method for DL SHI , allowing it to generate much simpler and smaller concepts that are specific enough to answer a given query. With independence between computed MSCs, scalability for query answering can also be achieved by distributing and parallelizing the computations. An empirical evaluation shows the efficacy of our revised MSC method and the significant efficiency achieved when using it for answering object queries.

Keywords

Description Logic, Ontology, Object Query, SHI , Most Specific Concept

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Horrocks, I. (2008) Ontologies and the Semantic Web. Communications of the ACM, 51, 58-67. http://dx.doi.org/10.1145/1409360.1409377
[2]	Horrocks, I.R. (1997) Optimising Tableaux Decision Procedures for Description Logics. Ph.D. Dissertation, University of Manchester, Manchester.
[3]	Haarslev, V. and Möller, R. (2008) On the Scalability of Description Logic Instance Retrieval. Journal of Automated Reasoning, 41, 99-142. http://dx.doi.org/10.1007/s10817-008-9104-7
[4]	Motik, B., Shearer, R. and Horrocks, I. (2007) Optimized Reasoning in Description Logics using Hypertableaux. Proceedings of Conference on Automated Deduction (CADE), 4603, 67-83.
[5]	Motik, B., Shearer, R. and Horrocks, I. (2009) Hypertableau Reasoning for Description Logics. Journal of Artificial Intelligence Research, 36, 165-228.
[6]	Sirin, E., Parsia, B., Grau, B.C., Kalyanpur, A. and Katz, Y. (2007) Pellet: A Practical Owl-Dl Reasoned. Journal of Web Semantics, 5, 51-53. http://dx.doi.org/10.1016/j.websem.2007.03.004
[7]	Haarslev, V. and Möller, R. (2001) RACER System Description. Proceedings of the First International Joint Conference on Automated Reasoning, Siena, June 2001, 701-705.
[8]	Horrocks, I. (1998) Using an Expressive Description Logic: Fact or Fiction? Proceedings of Knowledge Representation and Reasoning, 98, 636-645.
[9]	Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M. and Rosati, R. (2007) Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family. Journal of Automated Reasoning, 39, 385-429.http://dx.doi.org/10.1007/s10817-007-9078-x
[10]	Donini, F. (2007) The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press, Cambridge.
[11]	Glimm, B., Horrocks, I., Lutz, C. and Sattler, U. (2008) Conjunctive Query Answering for the Description Logic. Journal of Artificial Intelligence Research, 31, 157-204.
[12]	Ortiz, M., Calvanese, D. and Eiter, T. (2008) Data Complexity of Query Answering in Expressive Description Logics via Tableaux. Journal of Automated Reasoning, 41, 61-98. http://dx.doi.org/10.1007/s10817-008-9102-9
[13]	Tobies, S. (2001) Complexity Results and Practical Algorithms for Logics in Knowledge Representation. Ph.D. Dissertation, RWTH Aachen, Aachen.
[14]	Guo, Y. and Heflin, J. (2006) A Scalable Approach for Partitioning OWL Knowledge Bases. International Workshop on Scalable Semantic Web Knowledge Base Systems (SSWS), Geogia, November 2006, 636-641.
[15]	Wandelt, S. and Möller, R. (2012) Towards ABox Modularization of Semi-Expressive Description Logics. Applied Ontology, 7, 133-167.
[16]	Xu, J., Shironoshita, P., Visser, U., John, N. and Kabuka, M. (2013) Extract ABox Modules for Efficient Ontology Querying. ArXiv e-Prints. arXiv: 1305.4859
[17]	Donini, F., Lenzerini, M., Nardi, D. and Schaerf, A. (1994) Deduction in Concept Languages: From Subsumption to Instance Checking. Journal of Logic and Computation, 4, 423-452. http://dx.doi.org/10.1093/logcom/4.4.423
[18]	Nebel, B. (1990) Reasoning and Revision in Hybrid Representation Systems. Vol. 422, Springer-Verlag, Germany.
[19]	Schaerf, A. (1994) Reasoning with Individuals in Concept Languages. Data and Knowledge Engineering, 13, 141-176. http://dx.doi.org/10.1016/0169-023X(94)90002-7
[20]	Donini, F. and Era, A. (1992) Most Specific Concepts for Knowledge Bases with Incomplete Information. Proceedings of CIKM, Baltimore, November 1992, 545-551.
[21]	Tsarkov, D. and Horrocks, I. (2006) FaCT++ Description Logic Reasoner: System Description. Proceedings of 3rd International Joint Conference on Automated Reasoning, Seattle, 17-20 August 2006.
[22]	Horrocks, I. and Sattler, U. (2007) A Tableau Decision Procedure for Mathcal SHOIQ. Journal of Automated Reasoning, 39, 249-276. http://dx.doi.org/10.1007/s10817-007-9079-9
[23]	Horrocks, I. and Tessaris, S. (2000) A Conjunctive Query Language for Description Logic Aboxes. Proceedings of AAAI, Austin, August 2000, 399-404.
[24]	Baader, F. and Küsters, R. (1998) Computing the Least Common Subsumer and the Most Specific Concept in the Presence of Cyclic ALN-Concept Descriptions. In: Herzog, O. and Gunter, A., Eds., KI-98: Advances in Artificial Intelligence, Springer, Bremen, 129-140.
[25]	Krötzsch, M., Rudolph, S. and Hitzler, P. (2008) Description Logic Rules. European Conference on AI, 178, 80-84.
[26]	Horrocks, I., Sattler, U. and Tobies, S. (2000) Reasoning with Individuals for the Description Logic SHIQ. Proceedings of Automated Deduction (CADE), Pittsburgh, June 2000, 482-496.
[27]	Küsters, R. and Molitor, R. (2001) Approximating Most Specific Concepts in Description Logics with Existential Restrictions. In: Baader, Franz, Brewka, Gerhard, Eiter and Thomas, Eds., KI 2001: Advances in Artificial Intelligence, Springer, Vienna, 33-47.
[28]	Baader, F. (2003) Least Common Subsumers and Most Specific Concepts in a Description Logic with Existential Restrictions and Terminological Cycles. International Joint Conference on Artificial Intelligence, 3, 319-324.
[29]	Baader, F., Küsters, R. and Molitor, R. (1999) Computing Least Common Subsumers in Description Logics with Existential Restrictions. International Joint Conference on Artificial Intelligence, 99, 96-101.
[30]	Haarslev, V., Möller, R. and Turhan, A.Y. (2001) Exploiting Pseudo Models for TBox and ABox Reasoning in Expressive Description Logics. International Joint Conference, IJCAR 2001, Siena.
[31]	Hudek, A.K. and Weddell, G. (2006) Binary Absorption in Tableaux-Based Reasoning for Description Logics. Proceedings of the International Workshop on Description Logics (DL 2006), 189, 86-96.
[32]	Tsarkov, D. and Horrocks, I. (2004) Efficient Reasoning with Range and Domain Constraints. Proceedings of the 2004 Description Logic Workshop (DL 2004), 104, 41-50.
[33]	Wu, J., Hudek, A.K., Toman, D. and Weddell, G.E. (2012) Assertion Absorption in Object Queries over Knowledge Bases. International Conference on the Principles of Knowledge Representation and Reasoning, Rome, June 2012.
[34]	Grosof, B., Horrocks, I., Volz, R. and Decker, S. (2003) Description Logic Programs: Combining Logic Programs with Description Logic. Proceedings of WWW, Budapest, May 2003, 48-57.
[35]	Baader, F., Brand, S. and Lutz, C. (2005) Pushing the EL Envelope. Proceedings of IJCAI, Edinburgh, August 2005, 364-369.
[36]	Baader, F., Brandt, S. and Lutz, C. (2008) Pushing the EL Envelope Further. Proceedings of the OWLED 2008 DC Workshop on OWL: Experiences and Directions, Karlsruhe, October 2008.
[37]	Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M. and Rosati, R. (2005) DL-Lite: Tractable Description Logics for Ontologies. Proceedings of AAAI, 5, 602-607.
[38]	Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M. and Rosati, R. (2006) Data Complexity of Query Answering in Description Logics. Proceedings of Knowledge Representation and Reasoning (KR), 6, 260-270.
[39]	Bishop, B., Kiryakov, A., Ognyanoff, D., Peikov, I., Tashev, Z. and Velkov, R. (2011) OWLIM: A Family of Scalable Semantic Repositories. Journal of Semantic Web, 2, 33-42.
[40]	Kazakov, Y., Krötzsch, M. and Simancík, F. (2011) Concurrent Classification of EL Ontologies. International Semantic Web Conference, Bonn, October 2011, 305-320.
[41]	Wu, Z., Eadon, G., Das, S., Chong, E.I., Kolovski, V., Annamalai, M. and Srinivasan, J. (2008) Implementing an Inference Engine for RDFS/OWL Constructs and User-Defined Rules in Oracle. Proceedings of IEEE 24th International Conference on Data Engineering (ICDE), Cancun, April 2008, 1239-1248.
[42]	Zhou, Y., Cuenca Grau, B., Horrocks, I., Wu, Z. and Banerjee, J. (2013) Making the Most of Your Triple Store: Query Answering in OWL 2 Using an RL Reasoner. Proceedings of the 22nd International Conference on World Wide Web, Rio, May 2013, 1569-1580.
[43]	Guo, Y., Pan, Z. and Heflin, J. (2005) LUBM: A Benchmark for OWL Knowledge Base Systems. Journal of Web Semantics, 3, 158-182. http://dx.doi.org/10.1016/j.websem.2005.06.005
[44]	Auer, S., Bizer, C., Kobilarov, G., Lehmann, J., Cyganiak, R. and Ives, Z. (2007) DBpedia: A Nucleus for a Web of Open Data. Proceedings of ISWC, Busan, November 2007, 722-735.
[45]	Dean, J. and Ghemawat, S. (2008) MapReduce: Simplified Data Processing on Large Clusters. Communications of the ACM, 51, 107-113. http://dx.doi.org/10.1145/1327452.1327492