Description logic programs: combining logic programs with description logic

ABSTRACT

We show how to interoperate, semantically and inferentially, between the leading Semantic Web approaches to rules (RuleML Logic Programs) and ontologies (OWL/DAML+OIL Description Logic) via analyzing their expressive intersection. To do so, we define a new intermediate knowledge representation (KR) contained within this intersection: Description Logic Programs (DLP), and the closely related Description Horn Logic (DHL) which is an expressive fragment of first-order logic (FOL). DLP provides a significant degree of expressiveness, substantially greater than the RDF-Schema fragment of Description Logic. We show how to perform DLP-fusion: the bidirectional translation of premises and inferences (including typical kinds of queries) from the DLP fragment of DL to LP, and vice versa from the DLP fragment of LP to DL. In particular, this translation enables one to "build rules on top of ontologies": it enables the rule KR to have access to DL ontological definitions for vocabulary primitives (e.g., predicates and individual constants) used by the rules. Conversely, the DLP-fusion technique likewise enables one to "build ontologies on top of rules": it enables ontological definitions to be supplemented by rules, or imported into DL from rules. It also enables available efficient LP inferencing algorithms/implementations to be exploited for reasoning over large-scale DL ontologies.

REFERENCES

• 1: F. Baader, D. Calvanese, D. McGuinness, D. Nardi, and P. Patel-Schneider, editors. The Description Logic Handbook. Cambridge University Press, 2002.
• 2: C. Baral and M. Gelfond. Logic programming and knowledge representation. Journal of Logic Programming, 19/20:73--148, 1994.
• 3: H. Boley, B. Grosof, M. Sintek, S. Tabet, and G. Wagner. RuleML Design , September 2002. http://www.dfki.uni-kl.de/ruleml/indesign.html.
• 4: Alex Borgida, On the relative expressiveness of description logics and predicate logics, Artificial Intelligence, v.82 n.1-2, p.353-367, April 1996 [doi>10.1016/0004-3702(96)00004-5]
• 5: Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini, On the decidability of query containment under constraints, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.149-158, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275504]
• 6: D. Connolly, F. van Harmelen, I. Horrocks, D. L. McGuinness, P. F. Patel-Schneider, and L. A. Stein. DAML+ OIL (March 2001) Reference Description, December 2001. http://www.w3.org/TR/daml+oil-reference/.
• 7: F. M. Donini, M. Lenzerini, D. Nardi, and W. Nutt. The complexity of concept languages. In Proc. of KR'91, pages 151--162, 1991.
• 8: W. Dowling and J. Gallier. Linear time algorithms for testing the satisfiability of propositional horn formulae. Journal of Logic Programming, 3:267--284, 1984.
• 9: E. Grädel. On the restraining power of guards. J. of Symbolic Logic, 64:1719--1742, 1999.
• 10: V. Haarslev and R. Moller. Description of the RACER system and its applications. In DL2001 Workshop on Description Logics, Stanford, CA, 2001.
• 11: I. Horrocks and U. Sattler. Ontology reasoning in the SHOQ(D) description logic. In Proc. of IJCAI 2001, pages 199--204, 2001.
• 12: I. Horrocks, U. Sattler, S. Tessaris, and S. Tobies. How to decide query containment under constraints using a description logic. In Proc. of LPAR'2000, 2000.
• 13: Ian Horrocks , Ulrike Sattler , Stephan Tobies, Practical Reasoning for Expressive Description Logics, Proceedings of the 6th International Conference on Logic Programming and Automated Reasoning, p.161-180, September 06-10, 1999
• 14: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 15: Raghu Ramakrishnan, Magic templates: a spellbinding approach to logic programs, Journal of Logic Programming, v.11 n.3-4, p.189-216, Oct./Nov. 1991 [doi>10.1016/0743-1066(91)90026-L]
• 16: Konstantinos Sagonas , Terrance Swift , David S. Warren, XSB as an efficient deductive database engine, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.442-453, May 24-27, 1994, Minneapolis, Minnesota, United States
• 17: K. Schild. A correspondence theory for terminological logics: Preliminary report. In Proc. of IJCAI'91, pages 466--471, 1991.
• 18: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 19: M. Y. Vardi. Why is modal logic so robustly decidable? In N. Immerman and P. Kolaitis, editors, Descriptive Complexity and Finite Models. American Mathematical Society, 1997.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Representation languages

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.m Miscellaneous

General Terms:
Languages, Standardization, Theory

Keywords:
RDF, XML, description logic, inferencing, information integration, interoperability, knowledge representation, logic programs, model-theoretic semantics, ontologies, rules, semantic web, translation