ACM SIGMOD Anthology TODS dblp.uni-trier.de

On the Complexity of Join Dependencies.

Marc Gyssens: On the Complexity of Join Dependencies. ACM Trans. Database Syst. 11(1): 81-108(1986)
@article{DBLP:journals/tods/Gyssens86,
  author    = {Marc Gyssens},
  title     = {On the Complexity of Join Dependencies},
  journal   = {ACM Trans. Database Syst.},
  volume    = {11},
  number    = {1},
  year      = {1986},
  pages     = {81-108},
  ee        = {http://doi.acm.org/10.1145/5236.5237, db/journals/tods/Gyssens86.html},
  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. This method was subsequently studied in [11] and [12]. We show how the technique of decomposition can be used to make integrity checking more efficient. It turns out that it is important to find a decomposition that minimizes the number of edges of its largest element. We show that the decompositions obtained with the method described in [10] are optimal in this respect. This minimality criterion leads to the definition of the degree of cyclicity, which allows us to classify jds and leads to the notion of n-cyclicity, of which acyclicity is a special case for n = 2. We then show that, for a fixed value of n (which may be greater than 2). integrity checking can be performed in polynomial time provided we restrict ourselves to n-cyclic jds. Finally, we generalize a well-known characterization for acyclic jds by proving that n-cyclicity is equivalent to "n-wise consistency implies global consistency." As a consequence, consistency checking can be performed in polynomial time if we restrict ourselves to n-cyclic jds, for a tired value of n, not necessarily equal to 2.

Copyright © 1986 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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

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]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[6]
E. F. Codd: Further Normalization of the Data Base Relational Model. IBM Research Report, San Jose, California RJ909: (1971) BibTeX
[7]
Ronald Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Trans. Database Syst. 2(3): 262-278(1977) BibTeX
[8]
Ronald Fagin: Acyclic Database Schemes (of Various Degrees): A Painless Introduction. CAAP 1983: 65-89 BibTeX
[9]
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
[10]
Marc Gyssens, Jan Paredaens: A Decomposition Methodology for Cyclic Databases. Advances in Data Base Theory 1982: 85-122 BibTeX
[11]
Marc Gyssens, Jan Paredaens: On the Decomposition of Join Dependencies. PODS 1984: 143-152 BibTeX
[12]
Marc Gyssens: Embedded Join Dependencies as a Tool for Decomposing Full Join Dependencies. PODS 1985: 205-214 BibTeX
[13]
...
[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]
Jorma Rissanen: Theory of Relations for Databases - A Tutorial Survey. MFCS 1978: 536-551 BibTeX
[17]
...
[18]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
[19]
...

Referenced by

  1. Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113(1992)
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:38:59 2008