Back to papers
Conjunctive-Query Containment and Constraint Satisfaction
Summary: Shows that conjunctive-query containment and constraint satisfaction coincide as homomorphism problems A→B, unifying CQ containment with the CSP perspective. Proves three families of non‑uniform tractable CSPs uniformize—Boolean (via binarization), Datalog with bounded distinct variables, and bounded-treewidth queries—yielding PTIME cases for CQ containment.
(summarized by gpt-5-mini on Feb 09 2026)
- Paper ID
- 1147
- Venue
- PODS
- Year
- 1998
- Pagerank
- 0.00024004562
- Overall Rank
- 407 | 97.18%
- DOI
-
-
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 28 of 28 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 31 |
Provenance Semirings |
2007 |
PODS |
0.0007857786 |
| 1,038 |
Weighted Hypertree Decompositions and Optimal Query Plans |
2004 |
PODS |
0.00014492414 |
| 1,328 |
Hypertree Decompositions: Questions and Answers |
2016 |
PODS |
0.00012565612 |
| 2,296 |
Joins via Geometric Resolutions: Worst-case and Beyond |
2015 |
PODS |
9.0776226e-05 |
| 2,365 |
The Analytical Bootstrap: a New Method for Fast Error Estimation in Approximate Query Processing |
2014 |
SIGMOD |
8.9551432e-05 |
| 2,764 |
The Semiring Framework for Database Provenance |
2017 |
PODS |
8.1574444e-05 |
| 2,796 |
Hypertree Decompositions and Tractable Queries |
1999 |
PODS |
8.1112658e-05 |
| 2,829 |
Computing Cores for Data Exchange: New Algorithms and Practical Solutions |
2005 |
PODS |
8.0546963e-05 |
| 3,084 |
On the minimization of Xpath queries |
2003 |
VLDB |
7.6011919e-05 |
| 3,117 |
Processing Queries on Tree-Structured Data Efficiently |
2006 |
PODS |
7.5407318e-05 |
| 3,715 |
Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries |
2020 |
VLDB |
6.8220943e-05 |
| 3,901 |
Automated Verification of Query Equivalence Using Satisfiability Modulo Theories |
2019 |
VLDB |
6.6499845e-05 |
| 4,010 |
A Web Odyssey: from Codd to XML |
2001 |
PODS |
6.5351699e-05 |
| 4,405 |
On Preservation under Homomorphisms and Unions of Conjunctive Queries |
2004 |
PODS |
6.2156238e-05 |
| 4,553 |
View-Based Query Containment |
2003 |
PODS |
6.091702e-05 |
| 4,570 |
On the Efficiency of Checking Perfect Privacy |
2006 |
PODS |
6.0780779e-05 |
| 4,977 |
Constraint Satisfaction and Database Theory: a Tutorial |
2000 |
PODS |
5.7881576e-05 |
| 6,239 |
The Parameterized Complexity of Database Queries |
2001 |
PODS |
5.1417208e-05 |
| 6,948 |
Semantic Acyclicity on Graph Databases |
2013 |
PODS |
4.8898337e-05 |
| 7,162 |
Computing the Difference of Conjunctive Queries Efficiently |
2023 |
SIGMOD |
4.8132423e-05 |
| 7,163 |
Probabilistic Query Evaluation: The Combined FPRAS Landscape |
2023 |
PODS |
4.8132033e-05 |
| 7,501 |
Ranked Enumeration of Minimal Triangulations |
2019 |
PODS |
4.7180617e-05 |
| 8,851 |
Efficient Approximations of Conjunctive Queries |
2012 |
PODS |
4.4363908e-05 |
| 9,091 |
Efficiently Enumerating Minimal Triangulations |
2017 |
PODS |
4.39823e-05 |
| 10,649 |
STsCache: An Efficient Semantic Caching Scheme for Time-series Data Workloads Based on Hybrid Storage |
2025 |
VLDB |
4.1945683e-05 |
| 10,919 |
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity |
2024 |
PODS |
4.1945683e-05 |
| 11,232 |
Collective Grounding: Applying Database Techniques to Grounding Templated Models |
2023 |
VLDB |
4.1945683e-05 |
| 12,031 |
The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity |
2013 |
PODS |
4.1945683e-05 |
Outgoing Citations (Sorted by Pagerank)
Showing 3 of 3 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 11,967 |
Does Query Evaluation Tractability Help Query Containment? |
2014 |
PODS |
4.1945683e-05 |
| 2,398 |
Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract) |
1992 |
PODS |
8.8973978e-05 |
| 3,307 |
Attacking Diophantus: Solving a Special Case of Bag Containment |
2019 |
PODS |
7.2431594e-05 |
| 7,598 |
Polynomial-time program transformations in deductive databases |
1990 |
PODS |
4.7004867e-05 |
| 5,709 |
On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract) |
1997 |
PODS |
5.3602702e-05 |
| 9,791 |
Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability. |
2024 |
PODS |
4.2818172e-05 |
| 4,048 |
On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates |
1998 |
PODS |
6.4968603e-05 |
| 3,168 |
Query Containment for Data Integration Systems |
2000 |
PODS |
7.4508875e-05 |
| 1,522 |
The Containment Problem for Real Conjunctive Queries with Inequalities |
2006 |
PODS |
0.0001153051 |
| 1,490 |
On the Decidability of Query Containment under Constraints |
1998 |
PODS |
0.00011699154 |