On the decidability of containment of recursive datalog queries - preliminary report

ABSTRACT

The problem of deciding query containment has important applications in classical query optimization and heterogeneous database systems. Query containment is undecidable for unrestricted recursive queries, and decidable for recursive monadic queries and conjunctive queries over regular path expressions. In this paper, we identify a new class of recursive queries with decidable containment. Our framework extends the aforementioned query classes by supporting recursive predicates with more than two arguments and nonlinear recursion.

REFERENCES

• 1: P. A. Bonatti. Undecidability results for description logics with recursion and counting. In Proc. of IJCAI'03, pp., 2003.
• 2: Piero A. Bonatti, Towards Service Description Logics, Proceedings of the European Conference on Logics in Artificial Intelligence, p.74-85, September 23-26, 2002
• 3: 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]
• 4: Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini, Reasoning in Expressive Description Logics with Fixpoints based on Automata on Infinite Trees, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.84-89, July 31-August 06, 1999
• 5: Diego Calvanese , Giuseppe De Giacomo , Moshe Y. Vardi, Decidable Containment of Recursive Queries, Proceedings of the 9th International Conference on Database Theory, p.330-345, January 08-10, 2003
• 6: 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]
• 7: Stavros Cosmadakis , Haim Gaifman , Paris Kanellakis , Moshe Vardi, Decidable optimization problems for database logic programs, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.477-490, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62259]
• 8: Brouno Courcelle, Graph rewriting: an algebraic and logic approach, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 9: Ulrike Sattler , Moshe Y. Vardi, The Hybrid µ-Calculus, Proceedings of the First International Joint Conference on Automated Reasoning, p.76-91, June 18-23, 2001
• 10: Oded Shmueli, Equivalence of datalog queries is undecidable, Journal of Logic Programming, v.15 n.3, p.231-241, Feb. 1993 [doi>10.1016/0743-1066(93)90040-N]
• 11: Jeffrey D. Ullman, Information Integration Using Logical Views, Proceedings of the 6th International Conference on Database Theory, p.19-40, January 08-10, 1997