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.00011687823
Overall Rank: 1,489 | 89.66%
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
47	Data Integration: A Theoretical Perspective	2002	PODS	0.00069691761
808	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.000164132
2,345	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	8.9933611e-05
2,957	Efficient Algorithms for Minimizing Tree Pattern Queries	2002	SIGMOD	7.8143379e-05
3,903	Automated Verification of Query Equivalence Using Satisfiability Modulo Theories	2019	VLDB	6.6439695e-05
6,147	Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP	2013	PODS	5.1840098e-05
6,187	On Provenance Minimization	2011	PODS	5.1611195e-05
6,899	Containment of Graph Queries Modulo Schema	2024	PODS	4.8878659e-05
7,066	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS	4.8389293e-05
7,658	Scalable Delivery of Stream Query Result	2009	VLDB	4.6817213e-05
9,676	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD	4.3006524e-05
9,740	Containment of Conjunctive Object Meta-Queries	2006	VLDB	4.2895392e-05
11,771	Dichotomies in Ontology-Mediated Querying with the Guarded Fragment	2017	PODS	4.1905499e-05
12,414	Ontologies and Databases: myths and challenges	2008	VLDB	4.1905499e-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.00064817807
142	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS	0.00041780711
907	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00015417107
1,386	Managing Semantic Heterogeneity in Databases : A Theoretical Perspective	1997	PODS	0.00012251453
1,579	Constraint Checking with Partial Information	1994	PODS	0.00011273105
1,959	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.958725e-05
2,396	Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract)	1992	PODS	8.8892825e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,837	Semantic Acyclicity Under Constraints	2016	PODS	4.1905499e-05
5,719	On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract)	1997	PODS	5.3551435e-05
808	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.000164132
5,415	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS	5.5188622e-05
11,975	Does Query Evaluation Tractability Help Query Containment?	2014	PODS	4.1905499e-05
173	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00038731283
1,520	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS	0.00011524911
401	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00024281448
7,066	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS	4.8389293e-05
3,174	Query Containment for Data Integration Systems	2000	PODS	7.444226e-05