ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Embedded Join Dependencies as a Tool for Decomposing Full Join Dependencies.

Marc Gyssens: Embedded Join Dependencies as a Tool for Decomposing Full Join Dependencies. PODS 1985: 205-214
@inproceedings{DBLP:conf/pods/Gyssens85,
  author    = {Marc Gyssens},
  title     = {Embedded Join Dependencies as a Tool for Decomposing Full Join
               Dependencies},
  booktitle = {Proceedings of the Fourth ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, March 25-27, 1985, Portland, Oregon},
  publisher = {ACM},
  year      = {1985},
  isbn      = {0-89791-153-9},
  pages     = {205-214},
  ee        = {http://doi.acm.org/10.1145/325405.325441, db/conf/pods/Gyssens85.html},
  crossref  = {DBLP:conf/pods/85},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In [10] a method is proposed for decomposing join dependencies (jds) in a relational database, using the notion of a hinge. Decompositions of jds can be used to make integrity-checking more efficient. Therefore it is important for a given jd to find the "best possible" decomposition. In [12] it is shown that decompositions obtained by the method mentioned above minimize the number of components of their "largest" element. However it is still possible to further "simplify" out decompositions. Thusfar, we always restricted our attention to full jds: indeed, the decomposition methodology introduced in [10] and subsequently studied in [11] and [12] generates only full jds. This restriction however seems unnatural. In this paper we slightly modify the decomposition methodology of [10] in order to remove this restriction. It turns out that in doing so, and hence allowing embedded jds in our decompositions, a certain redundancy is eliminated. This leads to a minimality criterion of which we show that it is satisfied by the decompositions obtained using the modified methodology. We also generalize the notion of hinge, introduced in [10]. Surprisingly, generalised hinges turn out to be a very natural tool for characterizing when an arbitrary (possibly embedded) jd is logically implied by a given jd. This result generalizes the well known characterization for a full jd to be a consequence of a given full jd.

Copyright © 1985 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 ... BibTeX

Printed Edition

Proceedings of the Fourth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 25-27, 1985, Portland, Oregon. ACM 1985, ISBN 0-89791-153-9
Contents BibTeX

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) BibTeX
[2]
Catriel Beeri, Ronald Fagin, David Maier, Alberto O. Mendelzon, Jeffrey D. Ullman, Mihalis Yannakakis: Properties of Acyclic Database Schemes. STOC 1981: 355-362 BibTeX
[3]
Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis: On the Desirability of Acyclic Database Schemes. J. ACM 30(3): 479-513(1983) BibTeX
[4]
...
[5]
...
[6]
Ronald Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Trans. Database Syst. 2(3): 262-278(1977) BibTeX
[7]
Ronald Fagin: Acyclic Database Schemes (of Various Degrees): A Painless Introduction. CAAP 1983: 65-89 BibTeX
[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) BibTeX
[9]
Yuri Gurevich, Harry R. Lewis: The Inference Problem for Template Dependencies. PODS 1982: 221-229 BibTeX
[10]
...
[11]
Marc Gyssens, Jan Paredaens: On the Decomposition of Join Dependencies. PODS 1984: 143-152 BibTeX
[12]
...
[13]
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX
[14]
David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) BibTeX
[15]
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 BibTeX
[16]
...
[17]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
[18]
Moshe Y. Vardi: The Implication and Finite Implication Problems for Typed Template Dependencies. PODS 1982: 230-238 BibTeX
[19]
...

Referenced by

  1. Francesco M. Malvestuto: Statistical versus Relational Join Dependencies. SSDBM 1994: 64-73
  2. John H. Leuchner, Les Miller, Giora Slutzki: A Polynomial Time Algorithm for Testing Implications of a Join Dependency and Embodied Functional Dependencies. SIGMOD Conference 1988: 218-224
  3. Marc Gyssens: On the Complexity of Join Dependencies. ACM Trans. Database Syst. 11(1): 81-108(1986)
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:33:47 2009