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.08577e-05
Overall Rank: 2,728 | 81.67%
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.00014791388
2,482	Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability	2014	PODS	8.3992826e-05
2,596	Computing Cores for Data Exchange: New Algorithms and Practical Solutions	2005	PODS	8.2387266e-05
6,046	Topology Dependent Bounds For FAQs	2019	PODS	5.9027709e-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.00023580688
255	The History of Histograms (abridged)	2003	VLDB	0.00022974524
391	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00019245666
421	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00018507815
6,406	Constraint Satisfaction and Database Theory: a Tutorial	2000	PODS	5.7934139e-05
7,615	On the Complexity of Join Predicates	2001	PODS	5.4823519e-05

Semantically Similar Papers

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