skip to main content
10.1145/1055558.1055600acmconferencesArticle/Chapter ViewAbstractPublication PagespodsConference Proceedingsconference-collections
Article

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

Published: 14 June 2004 Publication History

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]
P. A. Bonatti. Towards Service Description Logics. In Proc. of JELIA'02, LNAI 2424, pages 74--85, 2002. Springer.
[3]
D. Calvanese, G. De Giacomo, M. Lenzerini. On the Decidability of Query Containment under Constraints. In Proc. of Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS'98), pages 149--158, ACM Press, 1998.
[4]
D. Calvanese, G. De Giacomo, M. Lenzerini. Reasoning in expressive description logics with fixpoints based on automata on infinite trees. In Proc. of IJCAI'99, pages 84--89, 1999.
[5]
D. Calvanese, G. De Giacomo, Moshe Y. Vardi. Decidable Containment of Recursive Queries. Proc. of ICDT'03, LNCS 2572, pp. 330--345, 2003. Springer.
[6]
A. K. Chandra, P. M. Merlin. Optimal Implementation of Conjunctive Queries in Relational Data Bases., Proc. of ACM STOC'77, pp. 77--90, 1977.
[7]
S. S. Cosmadakis, H. Gaifman, P. C. Kanellakis, M. Y. Vardi. Decidable Optimization Problems for Database Logic Programs. Proc. of ACM STOC'88, pp. 477--490, 1988.
[8]
Courcelle. Graph rewriting: An algebraic and logic approach. Handbook of Theoretical Computer Science Vol. B: Formal models and semantics. MIT Press/Elsevier, 1990.
[9]
U. Sattler, M. Y. Vardi. The hybrid μ-calculus. In Proc. of IJCAR'01, LNCS 2392, pages 27--30, 2001. Springer.
[10]
O. Shmueli. Equivalence of DATALOG Queries is Undecidable. JLP, 15(3): 231--241, 1993.
[11]
J. D. Ullman. Information Integration Using Logical Views. Proc. of ICDT'97, LNCS 1186, pp. 19--40, 1997. Springer.

Cited By

View all
  • (2016)Monadic Datalog and Regular Tree Pattern QueriesACM Transactions on Database Systems10.1145/292598641:3(1-43)Online publication date: 30-Jun-2016
  • (2015)Eliminating Recursion from Monadic Datalog Programs on TreesMathematical Foundations of Computer Science 201510.1007/978-3-662-48057-1_31(394-406)Online publication date: 11-Aug-2015
  • (2014)Monadic Datalog and Regular Tree Pattern QueriesMathematical Foundations of Computer Science 201410.1007/978-3-662-44522-8_36(426-437)Online publication date: 2014
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODS '04: Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
June 2004
350 pages
ISBN:158113858X
DOI:10.1145/1055558
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2004

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

SIGMOD/PODS04

Acceptance Rates

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)0
Reflects downloads up to 30 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2016)Monadic Datalog and Regular Tree Pattern QueriesACM Transactions on Database Systems10.1145/292598641:3(1-43)Online publication date: 30-Jun-2016
  • (2015)Eliminating Recursion from Monadic Datalog Programs on TreesMathematical Foundations of Computer Science 201510.1007/978-3-662-48057-1_31(394-406)Online publication date: 11-Aug-2015
  • (2014)Monadic Datalog and Regular Tree Pattern QueriesMathematical Foundations of Computer Science 201410.1007/978-3-662-44522-8_36(426-437)Online publication date: 2014
  • (2012)Monadic datalog containmentProceedings of the 39th international colloquium conference on Automata, Languages, and Programming - Volume Part II10.1007/978-3-642-31585-5_11(79-91)Online publication date: 9-Jul-2012
  • (2010)The impact of virtual views on containmentProceedings of the VLDB Endowment10.14778/1920841.19208823:1-2(297-308)Online publication date: 1-Sep-2010
  • (2010)Datalog for security, privacy and trustProceedings of the First international conference on Datalog Reloaded10.1007/978-3-642-24206-9_2(21-36)Online publication date: 16-Mar-2010
  • (2008)Type inference for datalog and its application to query optimisationProceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems10.1145/1376916.1376957(291-300)Online publication date: 9-Jun-2008
  • (2008)Conjunctive query containment and answering under description logic constraintsACM Transactions on Computational Logic10.1145/1352582.13525909:3(1-31)Online publication date: 12-Jun-2008
  • (2008)Comparing Rule-Based PoliciesProceedings of the 2008 IEEE Workshop on Policies for Distributed Systems and Networks10.1109/POLICY.2008.16(11-18)Online publication date: 2-Jun-2008
  • (2006)On Simplification of Database Integrity ConstraintsFundamenta Informaticae10.5555/2369336.236933871:4(371-417)Online publication date: 1-Dec-2006
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media