On Acyclic Database Decompositions.

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1983
Accession Number
ADA135105

Entities

People

  • C. Beeri
  • M. Vardi

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Classification
  • Computations
  • Computer Science
  • Computers
  • Databases
  • Decomposition
  • Information Science
  • Permutations
  • Polynomials
  • Relational Databases
  • Security
  • Universities

Readers

  • Database Systems and Applications
  • Graph Algorithms and Convex Optimization.