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)

Paper ID: 1581
Venue: PODS
Year: 2012
Pagerank: 5.3335287e-05
Overall Rank: 9,009 | 38.20%
DOI: 10.1145/2213556.2213591

Incoming Non-self Citations Over Time

Authors

1. Pablo Barceló (University of Chile)
2. Leonid Libkin (University of Edinburgh)
3. Miguel Romero (University of Chile)

BibTeX Citation

@inproceedings{barcelo_pods12,
        address = {New York, NY, USA},
        series = {{PODS} '12},
        title = {{Efficient Approximations of Conjunctive Queries}},
        url = {https://dl.acm.org/doi/10.1145/2213556.2213591},
        doi = {10.1145/2213556.2213591},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Barceló, Pablo and Libkin, Leonid and Romero, Miguel},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
747	Querying Graph Databases	2013	PODS	0.00014400452
3,463	Efficient Evaluation and Approximation of Well-designed Pattern Trees	2015	PODS	7.3921264e-05
5,245	Certain Answers Meet Zero-One Laws	2018	PODS	6.3012734e-05
6,841	Querying Big Data by Accessing Small Data	2015	PODS	5.7574257e-05
7,028	Semantic Acyclicity on Graph Databases	2013	PODS	5.7228058e-05
9,933	Semantic Acyclicity Under Constraints	2016	PODS	5.1955087e-05
11,084	Exploring Exploratory Querying	2025	VLDB	5.093636e-05

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
22	Data Integration: A Theoretical Perspective	2002	PODS	0.00056204792
225	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00024101949
363	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.0002005475
377	Data Exchange: Getting to the Core	2003	PODS	0.00019643793
382	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00019546431
673	Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants	2007	PODS	0.00015095061
763	On the Complexity of Bounded-Variable Queries	1995	PODS	0.00014230134
1,128	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.0001206219
1,673	Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width	2001	PODS	0.00010040854
6,558	Queries are easier than you thought (probably)	1992	PODS	5.8396421e-05
7,462	Incomplete Information and Certain Answers in General Data Models	2011	PODS	5.61159e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,468	On the Enumeration Complexity of Unions of Conjunctive Queries	2019	PODS
2	50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB
3	6,690	Can Datalog be approximated?	1994	PODS
4	12,229	The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity	2013	PODS
5	8,007	Complete Approximations of Incomplete Queries	2013	VLDB
6	3,553	On the Complexity of Approximate Query Optimization	2002	PODS
7	9,036	Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations	2022	PODS
8	9,921	Combined Approximations for Uniform Operational Consistent Query Answering	2024	PODS
9	4,136	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS
10	4,393	Bounded Conjunctive Queries	2014	VLDB