Acyclic join dependency and data base projections

摘要

Suppose that the contents of a data base can be viewed as a (universal) instance I which satisfies a given join dependency, and that the corresponding components (i.e., projections), rather than I itself, are stored in the data base. A condition on projections of a subset of these components of I, sufficient to imply that they can be used to compute the projection of I onto some fixed set of attributes, is obtained. This condition is shown to be necessary in case the original join dependency is acyclic. To obtain these results, a new characterization of acyclic join dependency, based on “structured edge-trees,” is given. The characterization is used to obtain a variety of results on acyclic join dependency and a modification of the Graham reduction process.