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: 1471
Venue: PODS
Year: 2008
Pagerank: 4.8898337e-05
Overall Rank: 6,949 | 51.66%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Isolde Adler

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,328	Hypertree Decompositions: Questions and Answers	2016	PODS	0.00012565612

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
626	Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants	2007	PODS	0.00018973823

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,598	Polynomial-time program transformations in deductive databases	1990	PODS	4.7004867e-05
7,293	On Tree-Based Techniques for Query Evaluation	1992	PODS	4.7740089e-05
10,360	Soft and Constrained Hypertree Width	2025	PODS	4.1945683e-05
8,851	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4363908e-05
4,048	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS	6.4968603e-05
1,038	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	0.00014492414
144	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS	0.00041462501
9,740	Tractable Database Design through Bounded Treewidth	2006	PODS	4.2936538e-05
915	The Complexity of Evaluating Relational Queries	1983	PODS	0.0001538509
2,796	Hypertree Decompositions and Tractable Queries	1999	PODS	8.1112658e-05