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.00024281448
- Overall Rank
- 401 | 97.22%
- DOI
-
-
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 29 of 29 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 31 |
Provenance Semirings |
2007 |
PODS |
0.00078516827 |
| 1,039 |
Weighted Hypertree Decompositions and Optimal Query Plans |
2004 |
PODS |
0.00014488271 |
| 1,322 |
Hypertree Decompositions: Questions and Answers |
2016 |
PODS |
0.00012595941 |
| 2,298 |
Joins via Geometric Resolutions: Worst-case and Beyond |
2015 |
PODS |
9.0746479e-05 |
| 2,424 |
The Analytical Bootstrap: a New Method for Fast Error Estimation in Approximate Query Processing |
2014 |
SIGMOD |
8.8415494e-05 |
| 2,770 |
The Semiring Framework for Database Provenance |
2017 |
PODS |
8.1495762e-05 |
| 2,804 |
Hypertree Decompositions and Tractable Queries |
1999 |
PODS |
8.1039107e-05 |
| 2,835 |
Computing Cores for Data Exchange: New Algorithms and Practical Solutions |
2005 |
PODS |
8.0468415e-05 |
| 3,089 |
On the minimization of Xpath queries |
2003 |
VLDB |
7.5938563e-05 |
| 3,115 |
Processing Queries on Tree-Structured Data Efficiently |
2006 |
PODS |
7.5414053e-05 |
| 3,702 |
Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries |
2020 |
VLDB |
6.8251643e-05 |
| 3,903 |
Automated Verification of Query Equivalence Using Satisfiability Modulo Theories |
2019 |
VLDB |
6.6439695e-05 |
| 4,014 |
A Web Odyssey: from Codd to XML |
2001 |
PODS |
6.5300582e-05 |
| 4,401 |
On Preservation under Homomorphisms and Unions of Conjunctive Queries |
2004 |
PODS |
6.2096576e-05 |
| 4,552 |
View-Based Query Containment |
2003 |
PODS |
6.0856349e-05 |
| 4,569 |
On the Efficiency of Checking Perfect Privacy |
2006 |
PODS |
6.0721066e-05 |
| 4,978 |
Constraint Satisfaction and Database Theory: a Tutorial |
2000 |
PODS |
5.7833452e-05 |
| 6,238 |
The Parameterized Complexity of Database Queries |
2001 |
PODS |
5.1369162e-05 |
| 6,945 |
Semantic Acyclicity on Graph Databases |
2013 |
PODS |
4.8874695e-05 |
| 7,161 |
Computing the Difference of Conjunctive Queries Efficiently |
2023 |
SIGMOD |
4.8086254e-05 |
| 7,162 |
Probabilistic Query Evaluation: The Combined FPRAS Landscape |
2023 |
PODS |
4.8085863e-05 |
| 7,500 |
Ranked Enumeration of Minimal Triangulations |
2019 |
PODS |
4.7135369e-05 |
| 8,850 |
Efficient Approximations of Conjunctive Queries |
2012 |
PODS |
4.4324268e-05 |
| 9,088 |
Efficiently Enumerating Minimal Triangulations |
2017 |
PODS |
4.3940132e-05 |
| 10,007 |
Query Answering Under Volume-Based Diversity Functions |
2026 |
PODS |
4.1905499e-05 |
| 10,657 |
STsCache: An Efficient Semantic Caching Scheme for Time-series Data Workloads Based on Hybrid Storage |
2025 |
VLDB |
4.1905499e-05 |
| 10,923 |
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity |
2024 |
PODS |
4.1905499e-05 |
| 11,234 |
Collective Grounding: Applying Database Techniques to Grounding Templated Models |
2023 |
VLDB |
4.1905499e-05 |
| 12,039 |
The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity |
2013 |
PODS |
4.1905499e-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,975 |
Does Query Evaluation Tractability Help Query Containment? |
2014 |
PODS |
4.1905499e-05 |
| 2,396 |
Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract) |
1992 |
PODS |
8.8892825e-05 |
| 3,311 |
Attacking Diophantus: Solving a Special Case of Bag Containment |
2019 |
PODS |
7.2361776e-05 |
| 7,603 |
Polynomial-time program transformations in deductive databases |
1990 |
PODS |
4.6959912e-05 |
| 9,794 |
Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability. |
2024 |
PODS |
4.2777144e-05 |
| 5,719 |
On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract) |
1997 |
PODS |
5.3551435e-05 |
| 4,055 |
On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates |
1998 |
PODS |
6.4906839e-05 |
| 3,174 |
Query Containment for Data Integration Systems |
2000 |
PODS |
7.444226e-05 |
| 1,520 |
The Containment Problem for Real Conjunctive Queries with Inequalities |
2006 |
PODS |
0.00011524911 |
| 1,489 |
On the Decidability of Query Containment under Constraints |
1998 |
PODS |
0.00011687823 |