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: 1140
Venue: PODS
Year: 1998
Pagerank: 0.00011699154
Overall Rank: 1,490 | 89.64%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
48	Data Integration: A Theoretical Perspective	2002	PODS	0.00069720859
810	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00016428374
2,342	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.0015589e-05
2,956	Efficient Algorithms for Minimizing Tree Pattern Queries	2002	SIGMOD	7.821865e-05
3,901	Automated Verification of Query Equivalence Using Satisfiability Modulo Theories	2019	VLDB	6.6499845e-05
6,143	Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP	2013	PODS	5.1889914e-05
6,186	On Provenance Minimization	2011	PODS	5.166082e-05
6,896	Containment of Graph Queries Modulo Schema	2024	PODS	4.8925595e-05
7,070	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS	4.843579e-05
7,660	Scalable Delivery of Stream Query Result	2009	VLDB	4.6862657e-05
9,676	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD	4.3047774e-05
9,741	Containment of Conjunctive Object Meta-Queries	2006	VLDB	4.2936538e-05
11,763	Dichotomies in Ontology-Mediated Querying with the Guarded Fragment	2017	PODS	4.1945683e-05
12,405	Ontologies and Databases: myths and challenges	2008	VLDB	4.1945683e-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
58	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00064826446
144	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS	0.00041462501
909	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00015428222
1,384	Managing Semantic Heterogeneity in Databases : A Theoretical Perspective	1997	PODS	0.00012262892
1,578	Constraint Checking with Partial Information	1994	PODS	0.00011284233
1,952	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.9677831e-05
2,398	Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract)	1992	PODS	8.8973978e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,709	On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract)	1997	PODS	5.3602702e-05
11,829	Semantic Acyclicity Under Constraints	2016	PODS	4.1945683e-05
810	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00016428374
5,406	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS	5.5243825e-05
11,967	Does Query Evaluation Tractability Help Query Containment?	2014	PODS	4.1945683e-05
172	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00038808816
1,522	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS	0.0001153051
407	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00024004562
7,070	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS	4.843579e-05
3,168	Query Containment for Data Integration Systems	2000	PODS	7.4508875e-05