Efficient Approximations of Conjunctive Queries
Summary: Defines sound approximations of conjunctive queries as queries from tractable classes (acyclic, bounded (hyper)treewidth) that minimize disagreement with the original Q, proving such approximations always exist and are polynomial (often linear) in |Q|. Relates closure properties to existence, gives combinatorial bounds and counts, and analyzes complexity of finding/recognizing approximations and of variants that return all correct answers. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Pablo Barceló
- 2. Leonid Libkin
- 3. Miguel Romero
Incoming Citations (Sorted by Pagerank)
Showing 6 of 6 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,037 | Querying Graph Databases | 2013 | PODS | 0.00014502493 |
| 4,058 | Efficient Evaluation and Approximation of Well-designed Pattern Trees | 2015 | PODS | 6.4866036e-05 |
| 6,948 | Semantic Acyclicity on Graph Databases | 2013 | PODS | 4.8898337e-05 |
| 7,085 | Querying Big Data by Accessing Small Data | 2015 | PODS | 4.8388174e-05 |
| 10,860 | Exploring Exploratory Querying | 2025 | VLDB | 4.1945683e-05 |
| 11,829 | Semantic Acyclicity Under Constraints | 2016 | PODS | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 11 of 11 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 48 | Data Integration: A Theoretical Perspective | 2002 | PODS | 0.00069720859 |
| 297 | Complexity of Answering Queries Using Materialized Views | 1998 | PODS | 0.00028596715 |
| 407 | Conjunctive-Query Containment and Constraint Satisfaction | 1998 | PODS | 0.00024004562 |
| 449 | Approximate Query Processing: Taming the TeraBytes! A Tutorial | 2001 | VLDB | 0.00022846068 |
| 494 | Data Exchange: Getting to the Core | 2003 | PODS | 0.00021805832 |
| 602 | On the Complexity of Bounded-Variable Queries | 1995 | PODS | 0.00019352415 |
| 626 | Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants | 2007 | PODS | 0.00018973823 |
| 1,414 | Graph Pattern Matching: From Intractable to Polynomial Time | 2010 | VLDB | 0.00012118275 |
| 2,015 | Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width | 2001 | PODS | 9.7901938e-05 |
| 6,255 | Queries are easier than you thought (probably) | 1992 | PODS | 5.1367617e-05 |
| 7,393 | Incomplete Information and Certain Answers in General Data Models | 2011 | PODS | 4.7428879e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,371 | On the Enumeration Complexity of Unions of Conjunctive Queries | 2019 | PODS | 7.1696145e-05 |
| 74 | Efficient Query Evaluation on Probabilistic Databases | 2004 | VLDB | 0.00057857292 |
| 6,748 | Can Datalog be approximated? | 1994 | PODS | 4.9401128e-05 |
| 12,031 | The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity | 2013 | PODS | 4.1945683e-05 |
| 7,560 | Complete Approximations of Incomplete Queries | 2013 | VLDB | 4.7102455e-05 |
| 4,194 | On the Complexity of Approximate Query Optimization | 2002 | PODS | 6.3697822e-05 |
| 8,992 | Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations | 2022 | PODS | 4.413099e-05 |
| 9,748 | Combined Approximations for Uniform Operational Consistent Query Answering | 2024 | PODS | 4.2897489e-05 |
| 4,442 | Approximating Predicates and Expressive Queries on Probabilistic Databases | 2008 | PODS | 6.186154e-05 |
| 4,546 | Bounded Conjunctive Queries | 2014 | VLDB | 6.0987778e-05 |