Algorithms for acyclic database schemes
Mihalis Yannakakis · Very Large Data Bases · 1981
Many real-world situations can be captured by a set of functional dependencies and a single join dependency of a particular form called acyclic [B..]. The join dependency corresponds to a natural decomposition into meaningfull objects (an acyclic database scheme). Our purpose in this paper is to describe efficient algorithms in this setting for various problems, such as computing projections, minimizing joins, inferring dependencies, and testing for dependency satisfaction.