A general datalog-based framework for tractable query answering over ontologies

ABSTRACT

In this paper, we introduce a family of expressive extensions of Datalog, called Datalog+/-, as a new paradigm for query answering over ontologies. The Datalog+/- family admits existentially quantified variables in rule heads, and has suitable restrictions to ensure highly efficient ontology querying. We show in particular that Datalog+/- generalizes the DL-Lite family of tractable description logics, which are the most common tractable ontology languages in the context of the Semantic Web and databases. We also show how stratified negation can be added to Datalog+/- while keeping ontology querying tractable. Furthermore, the Datalog+/- family is of interest in its own right and can, moreover, be used in various contexts such as data integration and data exchange.

References

1. ]]S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995.
2. ]]S. Abiteboul and V. Vianu. Datalog extensions for database queries and updates. JCSS, 43(1):62--124, 1991.
3. ]]H. Andréka, I. Németi, and J. van Benthem. Modal languages and bounded fragments of predicate logic. J. Phil. Log., 27(3):217--274, 1998.
4. ]]K. Apt, H. Blair, and A. Walker. Towards a theory of declarative knowledge. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pp. 89--148. Morgan Kaufmann, 1988.
5. ]]A. Artale, D. Calvanese, R. Kontchakov, M. Zakharyaschev. DL-Lite in the light of first-order logic. In Proc. AAAI-2007, pp. 361-366. AAAI Press, 2007. Extended report: The DL-Lite family and relations. School of Computer Science and Information Systems, Birkbeck College, 2009.
6. ]]C. Beeri and M.Y. Vardi. The implication problem for data dependencies. In Proc. ICALP-1981, LNCS 115, pp. 73--85. Springer, 1981.
7. ]]C. Beeri and M.Y. Vardi. A proof procedure for data dependencies. J. ACM, 31(4):718--741, 1984.
8. ]]T. Berners-Lee, J. Hendler, and O. Lassila. The Semantic Web. Sci. Am., 284:34--43, 2001.
9. ]]D. Brickley and R. Guha. RDF vocabulary description language 1.0: RDF Schema, 2004. W3C Recommendation.
10. ]]L. Cabibbo. The expressive power of stratified logic programs with value invention. Inf. Comput., 147(1):22--56, 1998.
11. ]]M. Cadoli, L. Palopoli, and M. Lenzerini. Datalog and description logics: Expressive power. In Proc. DBPL-1997, LNCS 1369, pp. 281--298. Springer, 1998.
12. ]]A. Calì, G. Gottlob, and M. Kifer. Taming the infinite chase: Query answering under expressive relational constraints. In Proc. KR-2008, pp. 70--80. AAAI Press, 2008. Revised version: http://benner.dbai.tuwien.ac.at/staff/gottlob/CGK.pdf.
13. ]]A. Calì, D. Lembo, and R. Rosati. On the decidability and complexity of query answering over inconsistent and incomplete databases. In Proc. PODS-2003, pp. 260--271. ACM Press, 2003.
14. ]]F. Calimeri, S. Cozza, and G. Ianni. External sources of knowledge and value invention in logic programming. Ann. Math. Artif. Intell., 50(3/4):333--361, 2007.
15. ]]D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. Tractable reasoning and efficient query answering in description logics: The DL-Lite family. J. Autom. Reasoning, 39(3):385--429, 2007.
16. ]]A.K. Chandra and P.M. Merlin. Optimal implementation of conjunctive queries in relational data bases. In Proc. STOC-1977, pp. 77--90. ACM Press, 1977.
17. ]]A.K. Chandra and M.Y. Vardi. The implication problem for functional and inclusion dependencies is undecidable. SIAM J. Comput., 14:671--677, 1985.
18. ]]E. Dantsin, T. Eiter, G. Gottlob, and A. Voronkov. Complexity and expressive power of logic programming. ACM Comput. Surv., 33(3):374--425, 2001.
19. ]]J. de Bruijn and S. Heymans. Logical foundations of (e)RDF(S): Complexity and reasoning. In Proc. ISWC-2007, LNCS 4825, pp. 86--99. Springer, 2007.
20. ]]A. Deutsch, A. Nash, and J.B. Remmel. The chase revisited. In Proc. PODS-2008, pp. 149--158. ACM Press, 2008.
21. ]]F.M. Donini, M. Lenzerini, D. Nardi, and A. Schaerf. AL-log: Integrating Datalog and description logics. J. Intell. Inf. Syst., 10(3):227--252, 1998.
22. ]]R. Fagin. A normal form for relational databases that is based on domians and keys. ACM TODS, 6(3):387--415, 1981.
23. ]]R. Fagin, P.G. Kolaitis, R.J. Miller, and L. Popa. Data exchange: Semantics and query answering. Theor. Comput. Sci., 336(1):89--124, 2005.
24. ]]B. Faltings and S. Macho-Gonzalez. Open constraint programming. Artif. Intell., 161(1-2):181--208, 2005.
25. ]]D. Johnson and A. Klug. Testing containment of conjunctive queries under functional and inclusion dependencies. JCSS, 28:167--189, 1984.
26. ]]M. Lenzerini. Data integration: A theoretical perspective. In Proc. PODS-2002, pp. 233--246. ACM Press, 2002.
27. ]]D. Maier, A.O. Mendelzon, and Y. Sagiv. Testing implications of data dependencies. ACM TODS, 4(4):455--469, 1979.
28. ]]D. Mailharrow. A classification and constraint-based framework for configuration. Artif. Intell. for Engineering Design, Analysis and Manufacturing, 12(4):383--397, 1998.
29. ]]P.F. Patel-Schneider and I. Horrocks. Position paper: A comparison of two modelling paradigms in the Semantic Web. In Proc. WWW-2006, pp. 3--12. ACM Press, 2006.
30. ]]A. Poggi, D. Lembo, D. Calvanese, G. De Giacomo, M. Lenzerini, and R. Rosati. Linking data to ontologies. J. Data Semantics, 10:133--173, 2008.
31. ]]T.C. Przymusinski. On the declarative semantics of deductive databases and logic programs. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pp. 193--216. Morgan Kaufmann, 1988.
32. ]]R. Rosati. On combining description logic ontologies and nonrecursive Datalog rules. In Proc. RR-2008, LNCS 5341, pp. 13--27. Springer, 2008.

Index Terms

• Information systems

  • Data management systems

    • Database design and models

      • Relational database model

    • Database management system engines

      • Database query processing

      • Triggers and rules

    • Query languages

      • Relational database query languages

• Theory of computation

  • Randomness, geometry and discrete structures

  • Theory and algorithms for application domains

    • Database theory

      • Database query processing and optimization (theory)