跳至主要内容

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

Read full paper at:
http://www.scirp.org/journal/PaperInformation.aspx?PaperID=52931#.VKyljcnQrzE

Author(s)   
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.
 
Cite this paper
Xu, J. , Shironoshita, P. , Visser, U. , John, N. and Kabuka, M. (2015) Converting Instance Checking to Subsumption: A Rethink for Object Queries over Practical Ontologies. International Journal of Intelligence Science, 5, 44-62. doi: 10.4236/ijis.2015.51005.
 
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                          eww150107lx
标签：

评论

发表评论

此博客中的热门博文

Does Immigration Promote the Investment of the Monopolistic Firm?

In the present paper, we examine the effect of increasing uncertainty of immigrants’ growth on the optimal timing of investment of a firm that has a monopolistic power over the labor market. It is revealed that when the uncertainty of immigrants’ growth is more than a threshold level, increasing uncertainty of immigrants’ growth accelerates the optimal timing of firms’ investment and enhances the economic growth, even if the uncertainty of immigrants’ growth is formulated by the geometric Brownian motion, which is in sharp contrast to the standard result that an increase in the uncertainty postpones the optimal timing. With an increase in the immigrants over the past ten years, workforces in the host countries have been growing significantly to the extent that the immigrants represent 70% of the increase in the workforce in Europe, and 47% in the United States as OECD indicates. In the present paper, we attempted to investigate the effect of increased uncertainty caused by the growi...
发表评论
阅读全文

Education Policy Implementation: A Mechanism for Enhancing Primary Education Development in Zanzibar

Education is one of the fundamental rights of individuals; therefore, the government of a country needs to develop and strengthen educational policy and quality as well as to ensure that everyone has equal access to basic education. The improvement of access and quality of education in the world is becoming as an essential factor in development, whereas the basic education (primary school), is acknowledged as a foundation of the higher educational development for every country. To fulfill this goal, governments introduce several policies and procedures; however, it requires some reforms and participation from the politician, policymakers, and other stakeholders to re-examine educational policy so that it can lead to multiplication and betterment of the reforms. Educational reforms actually focus on accountability. A positive educational development and reform is very challenging and needs more effort and strategy on how to use and utilize the resources effectively as such it can achie...
发表评论
阅读全文