dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

On the Decomposition of Join Dependencies.

Marc Gyssens, Jan Paredaens: On the Decomposition of Join Dependencies. PODS 1984: 143-152
@inproceedings{DBLP:conf/pods/GyssensP84,
  author    = {Marc Gyssens and
               Jan Paredaens},
  editor    = {Daniel J. Rosenkrantz and
               Ronald Fagin},
  title     = {On the Decomposition of Join Dependencies},
  booktitle = {Proceedings of the Third ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, April 2-4, 1984, Waterloo, Ontario, Canada},
  publisher = {ACM},
  year      = {1984},
  isbn      = {0-89791-128-8},
  pages     = {143-152},
  ee        = {http://doi.acm.org/10.1145/588011.588032, db/conf/pods/GyssensP84.html},
  crossref  = {DBLP:conf/pods/84},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In [9] we proposed a method for decomposing join dependencies (jd's) in a relational database. Decomposing a jd can be useful for separating cyclic and acyclic parts of jd's, obtaining more insight in the structure of a jd or making integrity-checking more efficient. The decomposition methodology of [9] has many desirable properties. However, in general it cannot generate all the decompositions of a given jd. In this paper, we first recall this decomposition methodology and its most important properties. We then introduce a subclass of jd's, the unambiguous jd's. We show that this class represents exactly those jd's that have a unique decomposition (which can be obtained by our method). We also give a characterization of this decomposition in terms of the structure of the original jd. To prove our results, we make extensive use of hypergraph theory.

Copyright © 1984 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

Printed Edition

Daniel J. Rosenkrantz, Ronald Fagin (Eds.): Proceedings of the Third ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, April 2-4, 1984, Waterloo, Ontario, Canada. ACM 1984, ISBN 0-89791-128-8
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Online Edition: ACM Digital Library


References

[1]
Alfred V. Aho, Catriel Beeri, Jeffrey D. Ullman: The Theory of Joins in Relational Databases. ACM Trans. Database Syst. 4(3): 297-314(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Catriel Beeri, Ronald Fagin, David Maier, Alberto O. Mendelzon, Jeffrey D. Ullman, Mihalis Yannakakis: Properties of Acyclic Database Schemes. STOC 1981: 355-362 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis: On the Desirability of Acyclic Database Schemes. J. ACM 30(3): 479-513(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
...
[5]
...
[6]
Ronald Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Trans. Database Syst. 2(3): 262-278(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
Ronald Fagin: Acyclic Database Schemes (of Various Degrees): A Painless Introduction. CAAP 1983: 65-89 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Ronald Fagin, Alberto O. Mendelzon, Jeffrey D. Ullman: A Simplified Universal Relation Assumption and Its Properties. ACM Trans. Database Syst. 7(3): 343-360(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
...
[10]
...
[11]
David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
Jan Paredaens, Dirk Van Gucht: An Application of the Theory of Graphs and Hypergraphs to the Decomposition of Relational Database Schemes. CAAP 1983: 350-366 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
...
[14]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
...

Last update Fri Sep 14 17:28:24 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page