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: 791
Venue: PODS
Year: 1987
Pagerank: 6.906603e-05
Overall Rank: 4,093 | 71.92%
DOI: 10.1145/28659.28679

Incoming Non-self Citations Over Time

Authors

1. Rina Dechter (Hughes Aircraft Company; University of California Los Angeles)

BibTeX Citation

@inproceedings{dechter_pods87,
        address = {New York, NY, USA},
        series = {{PODS} '87},
        title = {{DECOMPOSING AN N-ARY RELATION INTO A TREE OF BINARY RELATIONS}},
        url = {https://dl.acm.org/doi/10.1145/28659.28679},
        doi = {10.1145/28659.28679},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Dechter, Rina},
        year = {1987}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
203	Dependency Inference	1987	VLDB	0.00025381538

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
1	203	Dependency Inference	1987	VLDB
2	13,196	Alpha-Acyclic Decompositions of Relational Database Schemes	1986	PODS
3	6,516	The Design of non-1NF Relational Databases into Nested Normal Form	1987	SIGMOD
4	13,155	A Polynomial Time Algorithm for Testing Implications of a Join Dependency and Embodied Functional Dependencies	1988	SIGMOD
5	13,250	Algebraic Aspects of Relational Database Decomposition (Extended Abstract)	1983	PODS
6	7,923	Ranked Enumeration of Minimal Triangulations	2019	PODS
7	4,259	Database Decomposition into Fourth Normal Form	1983	VLDB
8	4,425	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS
9	1,056	A Normal Form for Nested Relations	1985	PODS
10	13,145	Decomposition of Relational Schemata into Components Defined by Both Projection and Restriction	1988	PODS