Decomposing An N-Ary Relation Into A Tree Of Binary Relations

Summary: Efficient algorithm to decompose an n-ary relation into a tree of binary relations plus an efficient test to verify that the tree exactly represents the relation. Novelty: derives dependencies from the bare instance (no assumed FDs/schemas) and is complete—finds a decomposition iff one exists, otherwise the test reports failure. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 792
Venue: PODS
Year: 1987
Pagerank: 0.00012436377
Overall Rank: 1,348 | 90.63%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Rina Dechter

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
25	Dependency Inference (Extended Abstract)	1987	VLDB	0.00083101742

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
25	Dependency Inference (Extended Abstract)	1987	VLDB	0.00083101742
12,998	Alpha-Acyclic Decompositions of Relational Database Schemes	1986	PODS	4.1945683e-05
6,180	The Design of non-1NF Relational Databases into Nested Normal Form	1987	SIGMOD	5.1686632e-05
12,959	A Polynomial Time Algorithm for Testing Implications of a Join Dependency and Embodied Functional Dependencies	1988	SIGMOD	4.1945683e-05
7,501	Ranked Enumeration of Minimal Triangulations	2019	PODS	4.7180617e-05
13,051	Algebraic Aspects of Relational Database Decomposition (Extended Abstract)	1983	PODS	4.1945683e-05
3,090	Database Decomposition Into Fourth Normal Form	1983	VLDB	7.582872e-05
3,999	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS	6.5469939e-05
1,052	A Normal Form for Nested Relations	1985	PODS	0.00014436103
12,950	Decomposition of Relational Schemata into Components Defined by Both Projection and Restriction	1988	PODS	4.1945683e-05