On the Decidability of Query Containment under Constraints

Summary: Decidability of containment for nonrecursive Datalog under inclusion constraints using set operations, restricted quantifiers, regular path expressions, and cardinality (models relational/ER/O-O schemas). Provides decision procedures/complexity: decidable when q omits regexes or when no number restrictions (first decidability for CQs with regex); undecidable if q' may use inequalities. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1139
Venue: PODS
Year: 1998
Pagerank: 0.00010180625
Overall Rank: 1,630 | 88.82%
DOI: 10.1145/275487.275504

Incoming Non-self Citations Over Time

Authors

1. Diego Calvanese (University of Rome 'La Sapienza')
2. Giuseppe De Giacomo (University of Rome 'La Sapienza')
3. Maurizio Lenzerini (University of Rome 'La Sapienza')

BibTeX Citation

@inproceedings{calvanese_pods98,
        address = {New York, NY, USA},
        series = {{PODS} '98},
        title = {{On the Decidability of Query Containment under Constraints}},
        url = {https://dl.acm.org/doi/10.1145/275487.275504},
        doi = {10.1145/275487.275504},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Calvanese, Diego and De Giacomo, Giuseppe and Lenzerini, Maurizio},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
22	Data Integration: A Theoretical Perspective	2002	PODS	0.00056204792
686	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014948634
2,066	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.2348082e-05
2,680	Efficient Algorithms for Minimizing Tree Pattern Queries	2002	SIGMOD	8.267202e-05
3,327	Automated Verification of Query Equivalence Using Satisfiability Modulo Theories	2019	VLDB	7.518491e-05
5,347	Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP	2013	PODS	6.2571376e-05
6,358	On Provenance Minimization	2011	PODS	5.9020113e-05
6,926	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS	5.7382018e-05
7,205	Containment of Graph Queries Modulo Schema	2024	PODS	5.6731473e-05
8,663	Scalable Delivery of Stream Query Result	2009	VLDB	5.3887668e-05
9,811	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD	5.214913e-05
9,865	Containment of Conjunctive Object Meta-Queries	2006	VLDB	5.2045536e-05
11,969	Dichotomies in Ontology-Mediated Querying with the Guarded Fragment	2017	PODS	5.093636e-05
12,599	Ontologies and Databases: myths and challenges	2008	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
97	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00034574497
134	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS	0.00030343737
953	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012997935
1,489	Constraint Checking with Partial Information	1994	PODS	0.00010612225
1,609	Managing Semantic Heterogeneity in Databases : A Theoretical Perspective	1997	PODS	0.00010225236
1,777	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.7849758e-05
2,296	Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract)	1992	PODS	8.7908999e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,933	Semantic Acyclicity Under Constraints	2016	PODS
2	5,736	On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract)	1997	PODS
3	686	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS
4	5,146	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS
5	12,165	Does Query Evaluation Tractability Help Query Containment?	2014	PODS
6	174	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS
7	1,269	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS
8	382	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS
9	6,926	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS
10	3,039	Query Containment for Data Integration Systems	2000	PODS