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: Serge Abiteboul , Victor Vianu, Datalog extensions for database queries and updates, Journal of Computer and System Sciences, v.43 n.1, p.62-124, Aug. 1991 [doi>10.1016/0022-0000(91)90032-Z]
• 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. R. Apt , H. A. Blair , A. Walker, Towards a theory of declarative knowledge, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 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: Catriel Beeri , Moshe Y. Vardi, The Implication Problem for Data Dependencies, Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.73-85, July 13-17, 1981
• 7: Catriel Beeri , Moshe Y. Vardi, A Proof Procedure for Data Dependencies, Journal of the ACM (JACM), v.31 n.4, p.718-741, Oct. 1984 [doi>10.1145/1634.1636]
• 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: Luca Cabibbo, The expressive power of stratified logic programs with value invention, Information and Computation, v.147 n.1, p.22-56, Nov. 25, 1998 [doi>10.1006/inco.1998.2734]
• 11: Marco Cadoli , Luigi Palopoli , Maurizio Lenzerini, Datalog and Description Logics: Expressive Power, Proceedings of the 6th International Workshop on Database Programming Languages, p.281-298, August 18-20, 1997
• 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: Andrea Calì , Domenico Lembo , Riccardo Rosati, On the decidability and complexity of query answering over inconsistent and incomplete databases, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.260-271, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773179]
• 14: Francesco Calimeri , Susanna Cozza , Giovambattista Ianni, External sources of knowledge and value invention in logic programming, Annals of Mathematics and Artificial Intelligence, v.50 n.3-4, p.333-361, August 2007 [doi>10.1007/s10472-007-9076-z]
• 15: Diego Calvanese , Giuseppe Giacomo , Domenico Lembo , Maurizio Lenzerini , Riccardo Rosati, Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family, Journal of Automated Reasoning, v.39 n.3, p.385-429, October 2007 [doi>10.1007/s10817-007-9078-x]
• 16: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 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: Evgeny Dantsin , Thomas Eiter , Georg Gottlob , Andrei Voronkov, Complexity and expressive power of logic programming, ACM Computing Surveys (CSUR), v.33 n.3, p.374-425, September 2001 [doi>10.1145/502807.502810]
• 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: Alin Deutsch , Alan Nash , Jeff Remmel, The chase revisited, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376916.1376938]
• 21: Francesco M. Donini , Maurizio Lenzerini , Daniele Nardi , Andrea Schaerf, $\{\backslash cal\; A\}\{\backslash cal\; L\}$-log: Integrating Datalog and Description Logics, Journal of Intelligent Information Systems, v.10 n.3, p.227-252, June 1, 1998 [doi>10.1023/A:1008687430626]
• 22: Ronald Fagin, A normal form for relational databases that is based on domains and keys, ACM Transactions on Database Systems (TODS), v.6 n.3, p.387-415, Sept. 1981 [doi>10.1145/319587.319592]
• 23: Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data exchange: semantics and query answering, Theoretical Computer Science, v.336 n.1, p.89-124, 25 May 2005 [doi>10.1O16/j.tcs.2004.10.033]
• 24: Boi Faltings , Santiago Macho-Gonzalez, Open constraint programming, Artificial Intelligence, v.161 n.1-2, p.181-208, January 2005 [doi>10.1016/j.artint.2004.10.005]
• 25: D. Johnson and A. Klug. Testing containment of conjunctive queries under functional and inclusion dependencies. JCSS, 28:167--189, 1984.
• 26: Maurizio Lenzerini, Data integration: a theoretical perspective, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543644]
• 27: David Maier , Alberto O. Mendelzon , Yehoshua Sagiv, Testing implications of data dependencies, ACM Transactions on Database Systems (TODS), v.4 n.4, p.455-469, Dec. 1979 [doi>10.1145/320107.320115]
• 28: Daniel Mailharro, A classification and constraint-based framework for configuration, Artificial Intelligence for Engineering Design, Analysis and Manufacturing, v.12 n.4, p.383-397, September 1998 [doi>10.1017/S0890060498124101]
• 29: Peter F. Patel-Schneider , Ian Horrocks, Position paper: a comparison of two modelling paradigms in the Semantic Web, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135784]
• 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, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 32: Riccardo Rosati, On Combining Description Logic Ontologies and Nonrecursive Datalog Rules, Proceedings of the 2nd International Conference on Web Reasoning and Rule Systems, October 31-November 01, 2008, Karlsruhe, Germany [doi>10.1007/978-3-540-88737-9_3]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing; Rule-based databases; Relational databases

General Terms:
Algorithms, Languages, Theory

Keywords:
chase, complexity, conjunctive queries, constraints, datalog, dependencies, ontologies, query evaluation, semantic web, tractability