Decomposing a relation into a tree of binary relations

摘要

We present an efficient algorithm for decomposing an n-ary relation into a tree of binary relations and provide a simple test for checking whether or not the tree formed by the algorithm represents the relation precisely. If a tree decomposition exists, the algorithm is guaranteed to find one. Otherwise, the tree generated by the algorithm can be used as an approximation of the relation. The method can be extended to decomposing a relation into an acyclic database of bounded relation arity. The unique feature of the algorithm presented in this paper is that it does not a priori assume any dependencies in the initial relation, but rather derives such dependencies from the bare relation instance.