On the Decidability of Containment of Recursive Datalog Queries - Preliminary report

Summary: Identifies a new class of recursive Datalog queries with decidable query containment. Extends prior decidable fragments by allowing recursive predicates of arity >2 and nonlinear recursion, generalizing monadic and regular-path-based cases. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hfd21825a57e5c160
Venue: PODS
Year: 2004
Pagerank: 5.6068861e-05
Overall Rank: 7,066 | 52.51%
DOI: 10.1145/1055558.1055600

Incoming Non-self Citations Over Time

Authors

1. Piero A. Bonatti (University of Naples)

BibTeX Citation

@inproceedings{bonatti_pods04,
        address = {New York, NY, USA},
        series = {{PODS} '04},
        title = {{On the Decidability of Containment of Recursive Datalog Queries - Preliminary report}},
        url = {https://dl.acm.org/doi/10.1145/1055558.1055600},
        doi = {10.1145/1055558.1055600},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Bonatti, Piero A.},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,233	The Impact of Virtual Views on Containment	2010	VLDB	5.8412765e-05
6,439	Type Inference for Datalog and its Application to Query Optimisation	2008	PODS	5.7826139e-05
9,989	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD	5.0989764e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1,661	On the Decidability of Query Containment under Constraints	1998	PODS	9.9545204e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,230	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS
2	9,618	A Theory of Regular Queries	2016	PODS
3	13,412	Semigroup techniques in recursive query optimization	1990	PODS
4	2,100	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD
5	13,454	Classification Of Recursive Formulas In Deductive Databases	1988	SIGMOD
6	6,746	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS
7	3,097	Query Containment for Data Integration Systems	2000	PODS
8	1,201	Data Independent Recursion in Deductive Databases	1986	PODS
9	2,064	A Decidable Class of Bounded Recursions	1987	PODS
10	1,661	On the Decidability of Query Containment under Constraints	1998	PODS