Accession Number : ADA135105

Title :   On Acyclic Database Decompositions.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Beeri,C ; Vardi,M

PDF Url : ADA135105

Report Date : Jul 1983

Pagination or Media Count : 13

Abstract : Given a universal relation scheme, presented as a set of attributes and a set of dependencies, it may be advantageous ot decompose it into a collection of schemes, each with its own sets of attributes and dependencies, which has some desired properties. A basic requirement for such a decomposition to be useful is that the corresponding decomposition map on universal relations be injective. A central problem in database theory is to find the reconstruction map, i.e., the inverse map of an injective decomposition map. We prove here that when the decomposition, viewed as a hypergraph, is acrylic and the given dependencies are full implicational dependencies, then the reconstruction map is the natural join. Based on this, we show that there is a polynomial time algorithm to test for injectiveness of decompositions.

Descriptors :   *Data bases, *Set theory, Mapping, Decomposition, Functions(Mathematics), Joining, Logic, Polynomials, Algorithms, Finite element analysis, Quadratic equations, Permutations, Theorems, Normality, Injection

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE