Tree-Width and Functional Dependencies in Databases

Summary: Define closure tree-width and hyperclosure tree-width via a homomorphism reformulation of conjunctive query evaluation under functional dependencies; bounded (hyper)closure tree-width makes HOM/CQ tractable. Prove separations from (hyper)tree-width, NP-completeness of recognition for fixed k≥3, and a polynomial-time approximation for k-bounded closure tree-width. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h8e6296142aa16641
Venue: PODS
Year: 2008
Pagerank: 5.6005794e-05
Overall Rank: 7,141 | 51.99%
DOI: 10.1145/1376916.1376959

Incoming Non-self Citations Over Time

Authors

1. Isolde Adler (Humboldt University of Berlin)

BibTeX Citation

@inproceedings{adler_pods08,
        address = {New York, NY, USA},
        series = {{PODS} '08},
        title = {{Tree-Width and Functional Dependencies in Databases}},
        url = {https://dl.acm.org/doi/10.1145/1376916.1376959},
        doi = {10.1145/1376916.1376959},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Adler, Isolde},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
818	Hypertree Decompositions: Questions and Answers	2016	PODS	0.0001366708

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
684	Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants	2007	PODS	0.00014798237

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,053	Polynomial-time program transformations in deductive databases	1990	PODS
2	11,096	Soft and Constrained Hypertree Width	2025	PODS
3	8,195	On Tree-Based Techniques for Query Evaluation	1992	PODS
4	9,169	Efficient Approximations of Conjunctive Queries	2012	PODS
5	3,870	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS
6	2,728	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS
7	136	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS
8	10,054	Tractable Database Design through Bounded Treewidth	2006	PODS
9	1,503	The Complexity of Evaluating Relational Queries	1983	PODS
10	2,365	Hypertree Decompositions and Tractable Queries	1999	PODS