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

Decomposition
Hinges

Cite this

Gyssens, M., & Paredaens, J. (1986). On the decomposition of join dependencies. In P. C. Kanellakis (Ed.), The Theory of Databases (pp. 69-106). (Advances in Computing Research; Vol. 3). Greenwich CT: JAI Press.
Gyssens, M. ; Paredaens, J. / On the decomposition of join dependencies. The Theory of Databases. editor / P.C. Kanellakis. Greenwich CT : JAI Press, 1986. pp. 69-106 (Advances in Computing Research).
@inbook{d2fc619b89ca438586a4f82d72abed07,
title = "On the decomposition of join dependencies",
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.",
author = "M. Gyssens and J. Paredaens",
year = "1986",
language = "English",
isbn = "0-89232-611-5",
series = "Advances in Computing Research",
publisher = "JAI Press",
pages = "69--106",
editor = "P.C. Kanellakis",
booktitle = "The Theory of Databases",
address = "United States",

}

Gyssens, M & Paredaens, J 1986, On the decomposition of join dependencies. in PC Kanellakis (ed.), The Theory of Databases. Advances in Computing Research, vol. 3, JAI Press, Greenwich CT, pp. 69-106.

On the decomposition of join dependencies. / Gyssens, M.; Paredaens, J.

The Theory of Databases. ed. / P.C. Kanellakis. Greenwich CT : JAI Press, 1986. p. 69-106 (Advances in Computing Research; Vol. 3).

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

TY - CHAP

T1 - On the decomposition of join dependencies

AU - Gyssens, M.

AU - Paredaens, J.

PY - 1986

Y1 - 1986

N2 - 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.

AB - 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.

M3 - Chapter

SN - 0-89232-611-5

T3 - Advances in Computing Research

SP - 69

EP - 106

BT - The Theory of Databases

A2 - Kanellakis, P.C.

PB - JAI Press

CY - Greenwich CT

ER -

Gyssens M, Paredaens J. On the decomposition of join dependencies. In Kanellakis PC, editor, The Theory of Databases. Greenwich CT: JAI Press. 1986. p. 69-106. (Advances in Computing Research).