On the decomposition of join dependencies

M. Gyssens, J. Paredaens

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

Abstract

In an earlier paper we proposed an algorithm for decomposing join dependencies (jds) in a relational database, using "hinges." Decomposing a jd can be useful for separating cyclic and acyclic parts of jds, obtaining more insight into the structure of a jd or making integrity checking more efficient. The Hinge Decomposition Algorithm has many desirable properties. However, in general it cannot generate all the decompositions of a given jd. Hence we cannot be sure that the Hinge Decomposition Algorithm generates the decomposition that is most suitable for the purposes it has to serve. Therefore, after reviewing the Hinge Decomposition Algorithm and its most important properties, we introduce unambiguous jds. We show that decomposable unambiguous jds are characterized by the property that they have exactly one decomposition satisfying some elementary desirable properties (union and intersection properties). Furthermore, this decomposition can be obtained with the Hinge Decomposition Algorithm. Finally, we characterize this decomposition in terms of the structure of the original jd. To prove our results, we make extensive use of hypergraph theory.
Original languageEnglish
Title of host publicationThe Theory of Databases
EditorsP.C. Kanellakis
Place of PublicationGreenwich CT
PublisherJAI Press
Pages69-106
ISBN (Print)0-89232-611-5
Publication statusPublished - 1986

Publication series

NameAdvances in Computing Research
Volume3
ISSN (Print)0741-9341

Fingerprint

Dive into the research topics of 'On the decomposition of join dependencies'. Together they form a unique fingerprint.

Cite this