Acyclic join dependency and data base projections
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.
- A simplied universal relation assumption and its properties
- Connections in acyclic hypergraphs
- Equivalence of Relational Database Schemes
- Equivalences among Relational Expressions
- Graph theory
- scientific article; zbMATH DE number 3648167 (Why is no real title available?)
- On Determining Tree Query Membership Of A Distributed Query
- On the Desirability of Acyclic Database Schemes
- Tree queries
- NP-complete problems simplified on tree schemas
- The tree projection theorem and relational query processing
- Losslessness and project-join constructibility in relational databases
- Synthesis of projections in relational data bases
- Join dependencies in relational-database design
- A characterization of finite fd-acyclicity
- On acyclic database decompositions
- On the complexity of join dependencies
- Joins and solutions of the projection synthesis problem in relational databases. II
- I/O-efficient join dependency testing, Loomis-Whitney join, and triangle enumeration
- GYO reductions, canonical connections, tree and cyclic schemas, and tree projections
This page was built for publication: Acyclic join dependency and data base projections
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q800103)
