DBScholar

Back to papers

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.8865476e-05
Overall Rank
6,051 | 59.44%
DOI
10.1145/1559795.1559804

Incoming Non-self Citations Over Time

Authors

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
397 Worst-case Optimal Join Algorithms 2012 PODS 0.0001911958
4,473 Bounded Conjunctive Queries 2014 VLDB 6.570529e-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
24 Data Integration: A Theoretical Perspective 2002 PODS 0.00055201845
41 Testing Implications Of Data Dependencies 1979 SIGMOD 0.00045733094
72 Answering Queries Using Views (Extended Abstract) 1995 PODS 0.00037421163
259 An Overview of Query Optimization in Relational Systems 1998 PODS 0.00022881075
524 Schema Mappings, Data Exchange, and Metadata Management 2005 PODS 0.00016888746
Previous Page 1 / 1 Next

Semantically Similar Papers