Datalog±: a unified approach to ontologies and integrity constraints

ABSTRACT

We report on a recently introduced family of expressive extensions of Datalog, called Datalog^±, which is a new framework for representing ontological axioms in form of integrity constraints, and for query answering under such constraints. Datalog± is derived from Datalog by allowing existentially quantified variables in rule heads, and by enforcing suitable properties in rule bodies, to ensure decidable and efficient query answering. We first present different languages in the Datalog± family, providing tight complexity bounds for all cases but one (where we have a low complexity AC₀ upper bound). We then show that such languages are general enough to capture the most common tractable ontology languages. In particular, we show that the DL-Lite family of description logics and F-Logic Lite are expressible in Datalog±. We finally show how stratified negation can be added to Datalog± while keeping ontology querying tractable in the data complexity. Datalog± is a natural and very general framework that can be successfully employed in different contexts such as data integration and exchange. This survey mainly summarizes two recent papers.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: H. Andréka, I. Németi, and J. van Benthem. Modal languages and bounded fragments of predicate logic. J. Philos. Logic, 27(3):217--274, 1998.
• 3: 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
• 4: Catriel Beeri , Ronald Fagin , David Maier , Alberto Mendelzon , Jeffrey Ullman , Mihalis Yannakakis, Properties of acyclic database schemes, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.355-362, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802489]
• 5: 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
• 6: 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]
• 7: T. Berners-Lee, J. Hendler, and O. Lassila. The Semantic Web. Scientific American, 284:34--43, 2001.
• 8: D. Brickley and R. V. Guha. RDF vocabulary description language 1.0: RDF Schema, 2004. W3C Recommendation.
• 9: A. Calì, G. Gottlob, and M. Kifer. Taming the infinite chase: Query answering under expressive relational constraints. Unpublished technical report, 2008. Available from the authors or at http://benner.dbai.tuwien.ac.at/staff/gottlob/CGK.pdf. This is the full and revised version of a preliminary short version which has appeared in Proc. of KR 2008, pages 70--80. AAAI Press, 2008.
• 10: A. Calì, G. Gottlob, and T. Lukasiewicz. A general Datalog-based framework for tractable query answering over ontologies, 2008. Manuscript, available from the authors.
• 11: Andrea Cali , Michael Kifer, Containment of conjunctive object meta-queries, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 12: 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]
• 13: 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]
• 14: M. A. Casanova, R. Fagin, and C. H. Papadimitriou. Inclusion dependencies and their interaction with functional dependencies. Journal of Computer and System Sciences, 28:29--59, 1984.
• 15: Stefano Ceri , Georg Gottlob , Letizia Tanca, Logic programming and databases, Springer-Verlag New York, Inc., New York, NY, 1990
• 16: Ashok K. Chandra , Harry R. Lewis , Johann A. Makowsky, Embedded implicational dependencies and their inference problem, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.342-354, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802488]
• 17: 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]
• 18: A. K. Chandra and M. Y. Vardi. The implication problem for functional and inclusion dependencies is undecidable. SIAM J. Comput., 14:671--677, 1985.
• 19: Bruno Courcelle, The monadic second-order logic of graphs. I. recognizable sets of finite graphs, Information and Computation, v.85 n.1, p.12-75, March 1990 [doi>10.1016/0890-5401(90)90043-H]
• 20: J. de Bruijn and S. Heymans. Logical foundations of (e)RDF(S): Complexity and reasoning. In Proc. of ISWC 2007, volume 4825 of LNCS, pages 86--99. Springer, 2007.
• 21: 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]
• 22: Alin Deutsch , Val Tannen, Reformulation of XML Queries and Constraints, Proceedings of the 9th International Conference on Database Theory, p.225-241, January 08-10, 2003
• 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: M. E. Goncalves and E. Grädel. Decidability issues for action guarded logics. In Proc. of DL 2000, pages 123--132, 2000.
• 25: Georg Gottlob , Christoph Koch , Robert Baumgartner , Marcus Herzog , Sergio Flesca, The Lixto data extraction project: back and forth between theory and practice, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055560]
• 26: Georg Gottlob , Christos Papadimitriou, On the complexity of single-rule datalog queries, Information and Computation, v.183 n.1, p.104-122, May 25, 2003 [doi>10.1016/S0890-5401(03)00012-9]
• 27: E. Grädel. On the restraining power of guards. J. Symb. Log., 64(4):1719--1742, 1999.
• 28: 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.
• 29: D. S. Johnson and A. C. Klug. Testing containment of conjunctive queries under functional and inclusion dependencies. J. Comput. Syst. Sci., 28(1):167--189, 1984.
• 30: Michael Kifer , Georg Lausen , James Wu, Logical foundations of object-oriented and frame-based languages, Journal of the ACM (JACM), v.42 n.4, p.741-843, July 1995 [doi>10.1145/210332.210335]
• 31: 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]
• 32: 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]
• 33: John C. Mitchell, The implication problem for functional and inclusion dependencies, Information and Control, v.56 n.3, p.154-173, March 1983 [doi>10.1016/S0019-9958(83)80002-3]
• 34: 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]
• 35: 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.
• 36: Xiaolei Qian, Query Folding, Proceedings of the Twelfth International Conference on Data Engineering, p.48-55, February 26-March 01, 1996
• 37: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 38: M. Y. Vardi, 1984. Personal communication reported in {29}.
• 39: Moshe Y. Vardi, On the complexity of bounded-variable queries (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.266-276, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.212474]

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, Theory

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