Size and Treewidth Bounds for Conjunctive Queries

Summary: Introduce a novel query-variable “coloring number” C(Q) giving tight worst-case bounds on result size |Q(D)| for conjunctive queries both without and with simple (one-attribute) keys, generalizing Atserias–Grohe–Marx AGM-style bounds. Extend the coloring to obtain lower bounds under arbitrary functional dependencies and exactly characterize which queries preserve output treewidth and input sparsity (with or without keys). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h79487d28d13b6c97
Venue: PODS
Year: 2009
Pagerank: 5.9060629e-05
Overall Rank: 6,043 | 59.38%
DOI: 10.1145/1559795.1559804

Incoming Non-self Citations Over Time

Authors

1. Georg Gottlob (Oxford Man Institute of Quantitative Finance; University of Oxford)
2. Stephanie Tien Lee (University of Oxford)
3. Gregory J. Valiant (University of California Berkeley)

BibTeX Citation

@inproceedings{gottlob_pods09,
        address = {New York, NY, USA},
        series = {{PODS} '09},
        title = {{Size and Treewidth Bounds for Conjunctive Queries}},
        url = {https://dl.acm.org/doi/10.1145/1559795.1559804},
        doi = {10.1145/1559795.1559804},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Gottlob, Georg and Lee, Stephanie Tien and Valiant, Gregory J.},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
402	Worst-case Optimal Join Algorithms	2012	PODS	0.00019104625
4,452	Bounded Conjunctive Queries	2014	VLDB	6.5938977e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
24	Data Integration: A Theoretical Perspective	2002	PODS	0.00055043581
41	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00045899672
72	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00037549176
272	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022509573
517	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.00016948466

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,918	Join Size Bounds using l_p-Norms on Degree Sequences	2024	PODS
2	6,739	Computing Join Queries with Functional Dependencies	2016	PODS
3	11,469	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS
4	10,387	Towards Parameterized Hardness on Maintaining Conjunctive Queries	2026	PODS
5	12,520	The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity	2013	PODS
6	5,489	Compressed Representations of Conjunctive Query Results	2018	PODS
7	4,452	Bounded Conjunctive Queries	2014	VLDB
8	7,141	Tree-Width and Functional Dependencies in Databases	2008	PODS
9	9,169	Efficient Approximations of Conjunctive Queries	2012	PODS
10	6,467	Output-sensitive Conjunctive Query Evaluation	2024	PODS