Weighted Hypertree Decompositions and Optimal Query Plans

Summary: Weighted hypertree decompositions: hypertree decompositions annotated with cost functions to combine structural and quantitative information (cardinalities/selectivities); minimal-weight decompositions are generally intractable but become polynomial-time (and sometimes parallel) under mild cost/target-tree restrictions. Use a query-cost function to derive optimal logical query plans and show experiments where this hybrid optimizer outperforms a commercial DBMS on large multi-join queries. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hefed49b8534c3de5
Venue: PODS
Year: 2004
Pagerank: 8.0895728e-05
Overall Rank: 2,728 | 81.66%
DOI: 10.1145/1055558.1055587

Incoming Non-self Citations Over Time

Authors

1. Francesco Scarcello (University of Calabria)
2. Gianluigi Greco (University of Calabria)
3. Nicola Leone (University of Calabria)

BibTeX Citation

@inproceedings{scarcello_pods04,
        address = {New York, NY, USA},
        series = {{PODS} '04},
        title = {{Weighted Hypertree Decompositions and Optimal Query Plans}},
        url = {https://dl.acm.org/doi/10.1145/1055558.1055587},
        doi = {10.1145/1055558.1055587},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Scarcello, Francesco and Greco, Gianluigi and Leone, Nicola},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
684	Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants	2007	PODS	0.00014798237
2,481	Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability	2014	PODS	8.403072e-05
2,594	Computing Cores for Data Exchange: New Algorithms and Practical Solutions	2005	PODS	8.2426092e-05
6,044	Topology Dependent Bounds For FAQs	2019	PODS	5.9055665e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
238	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00023591683
255	The History of Histograms (abridged)	2003	VLDB	0.00022981861
390	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00019248147
421	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00018516535
6,404	Constraint Satisfaction and Database Theory: a Tutorial	2000	PODS	5.796156e-05
7,608	On the Complexity of Join Predicates	2001	PODS	5.4849468e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,922	The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability	2010	PODS
2	7,141	Tree-Width and Functional Dependencies in Databases	2008	PODS
3	8,091	Ranked Enumeration of Minimal Triangulations	2019	PODS
4	10,054	Tractable Database Design through Bounded Treewidth	2006	PODS
5	11,185	Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized	2025	SIGMOD
6	2,365	Hypertree Decompositions and Tractable Queries	1999	PODS
7	11,656	A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition	2024	VLDB
8	10,508	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
9	11,096	Soft and Constrained Hypertree Width	2025	PODS
10	818	Hypertree Decompositions: Questions and Answers	2016	PODS