Acyclic join dependency and data base projections (Q800103)

In the presence of a join dependency \(*[R_ 1,R_ 2,...,R_ k]\) over relation scheme U, a relation I(U) can be faithfully represented by the database of projected relations \(d=\{r_ 1,r_ 2,...,r_ n\},\) where \(r_ i=\pi_{R_ i}(I).\) The question addressed in this paper is how to compute efficiently a projection \(\pi_ X(I)\) directly from the relations in d. The computations considered are joins of projections of relations in d, and ''efficiency'' means minimizing the number of joins. Permitting projections of relations in d, rather than simply the relations themselves, sets this work apart from that of \textit{M. Yannakakis}, who independently obtained similar results [Proc. 7th int. Conf. Very Large Databases, Cannes, 82-94 (1981)]. The paper gives a sufficient condition on a set of projections of relations in d for computing \(\pi_ X(I)\). Using an alternative definition of acyclic database scheme based on structured edge-trees the author shows the sufficient condition is also necessary if \(\{R_ 1,R_ 2,...,R_ n\}\) is an acyclic database scheme. The alternative definition of acyclic database scheme is also used to derive a modified Graham reduction procedure that will determine which projections of relations in d are needed to compute \(\pi_ X(I)\), given X.