An optimization for query answering on ALC database

ABSTRACT

Query answering over OWLs and RDFs on the Semantic Web is, in general, a deductive process. To this end, OWL, a family of web ontology languages based on description logic, has been proposed as the language for the Semantic Web. However, reasoning even on ALC, a description logic weaker than OWL, faces efficiency problem. To obviate this problem, at least for ALC, we propose a partition approach that improves the efficiency by splitting the search space into independent Aboxes. Each partition class, i.e., an Abox, can be queried independently. The answer to a query is the simple combination of the answers from each Abox. We prove the correctness of this approach and we outline how to represent compactly the content of each independent Abox. This work can be seen as an optimization for querying a deductive semi-structured database.

REFERENCES

• 1: Akahani, J., Hiramatsu, K. & Kogure, K. (2002), Coordinating heterogeneous information services based on approximate ontology translation, in 'Proceedings of AAMAS-2002 Workshop on Agentcities: Challenges in Open Agent Systems', pp. 10-14.
• 2: Arens, Y., Hsu, C. & Knoblock, C. A. (1996), 'Query processing in the sims information mediator', Advanced Planning Technology.
• 3: Franz Baader , Diego Calvanese , Deborah L. McGuinness , Daniele Nardi , Peter F. Patel-Schneider, The description logic handbook: theory, implementation, and applications, Cambridge University Press, New York, NY, 2003
• 4: Franz Baader , Bernhard Hollunder, A Terminological Knowledge Representation System with Complete Inference Algorithms, Proceedings of the International Workshop on Processing Declarative Knowledge, p.67-86, July 01-03, 1991
• 5: Tim Berners-Lee , Mark Fischetti, Weaving the Web; The Original Design and Ultimate Destiny of the World Wide Web by Its Inventor (2 Cassettes), Harper Audio, 1999
• 6: Donini, F. M., Lenzerini, M., Nardi, D. & Nutt, W. (1991), The complexity of concept languages, in J. Allen, R. Fikes & E. Sandewall, eds, 'Proceedings of the Second International Conference on Principles of Knowledge Representation and Reasoning (KR-91)', Massachusetts, pp. 151-162.
• 7: Francesco M. Donini , Maurizio lenzerini , Daniele Nardi , Andrea Schaerf, Reasoning in description logics, Principles of knowledge representation, Center for the Study of Language and Information, Stanford, CA, 1997
• 8: Francesco M. Donini , Fabio Massacci, EXPTIME tableaux for ALC, Artificial Intelligence, v.124 n.1, p.87-138, Nov 2000 [doi>10.1016/S0004-3702(00)00070-9 ]
• 9: Jon Doyle , Ramesh S. Patil, Two theses of knowledge representation: language restrictions, taxonomic classification, and the utility of representation services, Artificial Intelligence, v.48 n.3, p.261-297, April 1991 [doi>10.1016/0004-3702(91)90029-J ]
• 10: Cheng Hian Goh , Stuart E. Madnick, Representing and reasoning about semantic conflicts in heterogeneous information systems, 1997
• 11: Goodchild, A. (1998), Database Discovery in the Organizational Environment, PhD thesis, University of Queensland.
• 12: Haarslev, V. & Mööller, R. (2002), Optimization strategies for instance retrieval, in 'Proceedings of the International Workshop on Description Logics (DL 2002)'.
• 13: Horrocks, I. (1997), Optimising Tableaux Decision Procedures for Description Logics, PhD thesis, University of Manchester.
• 14: Horrocks, I., Li, L., Turi, D. & Bechhofer, S. (2004), The instance store: Description logic reasoning with large numbers of individuals, in 'International Workshop on Description Logics (DL 2004)', pp. 31-40.
• 15: McGuinness, D. L., Fikes, R., Stein, L. A. & Hendler, J. (2003), Daml-ont: An ontology language for the semantic web, in D. Fensel, J. Hendler, H. Lieberman & W. Wahlster, eds, 'Spinning the Semantic Web: Bringing the World Wide Web to its Full Potential', MIT Press.
• 16: E. Mena , V. Kashyap , A. Sheth , A. Illarramendi, OBSERVER: An Approach for Query Processing in Global Information Systems based on Interoperation across Pre-existing Ontologies, Proceedings of the First IFCIS International Conference on Cooperative Information Systems, p.14, June 19-21, 1996
• 17: Pan, J. Z. & Horrocks, I. (2003), Rdfs(fa): A dlised sub-language of rdfs, in 'Proceedings of the 2003 International Workshop on Description Logics (DL2003)'.
• 18: Manfred Schmidt-Schaubß , Gert Smolka, Attributive concept descriptions with complements, Artificial Intelligence, v.48 n.1, p.1-26, Feb. 1991 [doi>10.1016/0004-3702(91)90078-X ]
• 19: Stuckenschmidt, H. (2003), 'Query processing on the semantic web', Künstliche Intelligenz 17.
• 20: Tessaris, S. (2001), Questions and Answers: Reasoning and Querying in Description Logic, PhD thesis, University of Manchester.
• 21: Wache, H., Vögele, T., Visser, U., Stuckenschmidt, H., Schuster, G., Neumann, H. & Hüübner, S. (2001), Ontology-based integration of information - a survey of existing approaches, in 'Proceedings of the IJCAI- 01 Workshop: Ontologies and Information Sharing', pp. 108-117.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models; Query formulation
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Answer/reason extraction

General Terms:
Algorithms, Design, Performance

Keywords:
description logic, query optimization, web database