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)
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 |
|---|---|---|---|---|
| 411 | Worst-case Optimal Join Algorithms | 2012 | PODS | 0.00018902089 |
| 4,393 | Bounded Conjunctive Queries | 2014 | VLDB | 6.7280426e-05 |
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 22 | Data Integration: A Theoretical Perspective | 2002 | PODS | 0.00056204792 |
| 40 | Testing Implications Of Data Dependencies | 1979 | SIGMOD | 0.00046918506 |
| 69 | Answering Queries Using Views (Extended Abstract) | 1995 | PODS | 0.00038090878 |
| 290 | An Overview of Query Optimization in Relational Systems | 1998 | PODS | 0.0002227038 |
| 506 | Schema Mappings, Data Exchange, and Metadata Management | 2005 | PODS | 0.0001728171 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 6,257 | Join Size Bounds using l_p-Norms on Degree Sequences | 2024 | PODS |
| 2 | 6,672 | Computing Join Queries with Functional Dependencies | 2016 | PODS |
| 3 | 11,121 | Consistent Query Answering for Primary Keys on Rooted Tree Queries | 2024 | PODS |
| 4 | 10,170 | Towards Parameterized Hardness on Maintaining Conjunctive Queries | 2026 | PODS |
| 5 | 4,393 | Bounded Conjunctive Queries | 2014 | VLDB |
| 6 | 12,229 | The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity | 2013 | PODS |
| 7 | 5,383 | Compressed Representations of Conjunctive Query Results | 2018 | PODS |
| 8 | 7,029 | Tree-Width and Functional Dependencies in Databases | 2008 | PODS |
| 9 | 9,009 | Efficient Approximations of Conjunctive Queries | 2012 | PODS |
| 10 | 6,678 | Output-sensitive Conjunctive Query Evaluation | 2024 | PODS |