Tractable Database Design through Bounded Treewidth

Summary: Restricting FD sets to bounded-treewidth hypergraphs (via primal or incidence graph views) yields a tractable database-design regime. Provides polynomial-time, highly parallel algorithms and novel key/primality characterizations for attribute primality, 3NF and BCNF tests. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1384
Venue: PODS
Year: 2006
Pagerank: 4.2936538e-05
Overall Rank: 9,740 | 32.25%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
376	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00025097452
5,705	Datalog Unchained	2021	PODS	5.3621239e-05
13,585	Monadic Datalog over Finite Structures with Bounded Treewidth	2007	PODS	-

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,973	Logical Design of Relational Database Schemes	1987	PODS	4.1945683e-05
5,781	Practical algorithms for finding prime attributes and testing normal forms	1989	PODS	5.3298267e-05
6,180	The Design of non-1NF Relational Databases into Nested Normal Form	1987	SIGMOD	5.1686632e-05
11,132	A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition	2024	VLDB	4.1945683e-05
7,473	The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability	2010	PODS	4.7198203e-05
10,508	Synthesizing Third Normal Form Schemata that Minimize Integrity Maintenance and Update Overheads: Parameterizing 3NF by the Numbers of Minimal Keys and Functional Dependencies	2025	SIGMOD	4.1945683e-05
12,925	Polynomial Time Designs toward Both BCNF and Efficient Data Manipulation	1990	SIGMOD	4.1945683e-05
6,997	Tractable Lineages on Treelike Instances: Limits and Extensions	2016	PODS	4.8676446e-05
6,949	Tree-Width and Functional Dependencies in Databases	2008	PODS	4.8898337e-05
1,038	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	0.00014492414