Proceedings

EQL-Lite: Effective First-Order Query Processing in Description Logics

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 274-278.

© 2007 International Joint Conferences on Artificial Intelligence

Abstract

Querying Description Logic knowledge bases has received great attention in the last years. In such a problem, the need of coping with incomplete information is the distinguishing feature with respect to querying databases. Due to this feature, we have to deal with two conflicting needs: on the one hand, we would like to query the knowledge base with sophisticated mechanisms provided by full first-order logic (FOL); on the other hand, the presence of incomplete information makes query answering a much more difficult task than in databases. In this paper we advocate the use of a nonmonotonic epistemic FOL query language as a means for expressing sophisticated queries over Description Logic knowledge bases. We show that through a controlled use of the epistemic operator, resulting in the language called EQL-Lite, we are able to formulate full FOL queries over Description Logic knowledge bases, while keeping computational complexity of query answering under control. In particular, we show that EQL-Lite queries over DL-Lite knowledge bases are FOL reducible (i.e., compilable into SQL) and hence can be answered in LOGSPACE through standard database technologies.

  1. S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison Wesley Publ. Co., 1995.
  2. A. Acciarri, D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, M. Palmieri, and R. Rosati. QUONTO: QUerying ONTOlogies. In Proc. of AAAI 2005, pages 1670-1671, 2005.
  3. F. Baader, S. Brandt, and C. Lutz. Pushing the EL en- velope. In Proc. of IJCAI 2005, pages 364-369, 2005.
  4. F. Baader, D. Calvanese, D. McGuinness, D. Nardi, and P. F. Patel-Schneider, editors. The Description Logic Handbook: Theory, Implementation and Applications. Cambridge University Press, 2003.
  5. D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. DL-Lite: Tractable description logics for ontologies. In Proc. of AAAI 2005, pages 602-607, 2005.
  6. D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. Data complexity of query answering in description logics. In Proc. of KR 2006, pages 260-270, 2006.
  7. D. Calvanese, G. De Giacomo, and M. Lenzerini. On the decidability of query containment under constraints. In Proc. of PODS'98, pages 149-158, 1998.
  8. F. M. Donini, M. Lenzerini, D. Nardi, W. Nutt, and A. Schaerf. An epistemic operator for description log- ics. Artificial Intelligence, 100(1-2):225-274, 1998.
  9. R. Fikes, P. Hayes, and I. Horrocks. OWL-QL: A lan- guage for deductive query answering on the semantic web. J. of Web Semantics, 2(1), 2005.
  10. V. Haarslev, R. Möller, and M. Wessel. A high perfor- mance semantic web query answering engine. In Proc. of DL 2005, 2005.
  11. I. Horrocks and U. Sattler. A description logic with tran- sitive and inverse roles and role hierarchies. J. of Log. and Comp., 9(3):385-410, 1999.
  12. G. E. Hughes and M. J. Cresswell. A Companion to Modal Logic. Methuen, London, 1984.
  13. U. Hustadt, B. Motik, and U. Sattler. Data complexity of reasoning in very expressive description logics. In Proc. of IJCAI 2005, pages 466-471, 2005. IJCAI
  14. H. J. Levesque. Foundations of a functional approach to knowledge representation. Artificial Intelligence, 23:155-212, 1984.
  15. H. J. Levesque and G. Lakemeyer. The Logic of Knowl- edge Bases. The MIT Press, 2001.
  16. M. M. Ortiz, D. Calvanese, and T. Eiter. Data com- plexity of answering unions of conjunctive queries in SHIQ. In Proc. of DL 2006, 2006.
  17. R. Reiter. What should a database know? J. of Logic Programming, 14:127-153, 1990.
  18. E. Sirin and B. Parsia. Pellet system description. In Proc. of DL 2006, 2006.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards