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

Elimination of Intersection Anomalies from Database Schemes.

Catriel Beeri, Michael Kifer: Elimination of Intersection Anomalies from Database Schemes. PODS 1983: 340-351
@inproceedings{DBLP:conf/pods/BeeriK83,
  author    = {Catriel Beeri and
               Michael Kifer},
  title     = {Elimination of Intersection Anomalies from Database Schemes},
  booktitle = {Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, March 21-23, 1983, Colony Square Hotel,
               Atlanta, Georgia},
  publisher = {ACM},
  year      = {1983},
  isbn      = {0-89791-097-4},
  pages     = {340-351},
  ee        = {http://doi.acm.org/10.1145/588058.588099, db/conf/pods/BeeriK83.html},
  crossref  = {DBLP:conf/pods/83},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The desirability of acyclic database scheme is well argued in [L,BFMY]. When a scheme is described by multivalued dependencies, acycliclty means that the dependencies do not split each other's left-hand side and do not form intersection anomalies. We show that if the second condition fails to hold, the scheme can be amended so that it holds. The basic step is to add one attribute and some dependencies to resolve one intersection anomaly. This step generates an extension of the given scheme in which the anomaly does not exists. We also analyze the repetitive use of the basic step and prove that the transformation so defined removes all intersection anomalies. Finally, we characterize a class of attributes that can be removed from the final scheme, leaving it acyclic.

Copyright © 1983 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 Second ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 21-23, 1983, Colony Square Hotel, Atlanta, Georgia. ACM 1983, ISBN 0-89791-097-4
Contents BibTeX

Online Edition: ACM Digital Library

Journal Version

Catriel Beeri, Michael Kifer: Elimination of intersection anomalies from database schemes. J. ACM 33(3): 423-450(1986) BibTeX

References

[ABU]
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
[B]
Catriel Beeri: On the Membership Problem for Functional and Multivalued Dependencies in Relational Databases. ACM Trans. Database Syst. 5(3): 241-259(1980) BibTeX
[Ber]
Philip A. Bernstein: Synthesizing Third Normal Form Relations from Functional Dependencies. ACM Trans. Database Syst. 1(4): 277-298(1976) BibTeX
[BB]
Catriel Beeri, Philip A. Bernstein: Computational Problems Related to the Design of Normal Form Relational Schemas. ACM Trans. Database Syst. 4(1): 30-59(1979) BibTeX
[BBG]
Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Database Normalization Theory. VLDB 1978: 113-124 BibTeX
[BFH]
Catriel Beeri, Ronald Fagin, John H. Howard: A Complete Axiomatization for Functional and Multivalued Dependencies in Database Relations. SIGMOD Conference 1977: 47-61 BibTeX
[BFMY]
Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis: On the Desirability of Acyclic Database Schemes. J. ACM 30(3): 479-513(1983) BibTeX
[BeKi]
...
[Fag1]
Ronald Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Trans. Database Syst. 2(3): 262-278(1977) BibTeX
[Fag2]
Ronald Fagin: Degrees of Acyclicity for Hypergraphs and Relational Database Schemes. J. ACM 30(3): 514-550(1983) BibTeX
[FMU]
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
[GS]
Nathan Goodman, Oded Shmueli: The Tree Property is Fundamental for Query Processing. PODS 1982: 40-48 BibTeX
[L]
Y. Edmund Lien: On the Equivalence of Database Models. J. ACM 29(2): 333-362(1982) BibTeX
[MU]
David Maier, Jeffrey D. Ullman: Connections in Acyclic Hypergraphs. PODS 1982: 34-39 BibTeX
[Sc]
Edward Sciore: Real-World MVD's. SIGMOD Conference 1981: 121-132 BibTeX
[SDPF]
Yehoshua Sagiv, Claude Delobel, Douglas Stott Parker Jr., Ronald Fagin: An Equivalence Between Relational Database Dependencies and a Fragment of Propositional Logic. J. ACM 28(3): 435-453(1981) BibTeX
[Ull]
...
[Yan]
Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94 BibTeX

Referenced by

  1. Z. Meral Özsoyoglu, Li-Yan Yuan: A New Normal Form for Nested Relations. ACM Trans. Database Syst. 12(1): 111-136(1987)
  2. Mark A. Roth, Henry F. Korth: The Design of ¬1NF Relational Databases into Nested Normal Form. SIGMOD Conference 1987: 143-159
  3. Dirk Van Gucht: Interaction-Free Multivalued Dependency Sets. ICDT 1986: 409-420
  4. Z. Meral Özsoyoglu, Li-Yan Yuan: A Normal Form for Nested Relations. PODS 1985: 251-260
  5. Catriel Beeri, Michael Kifer: Comprehensive Approach to the Design of Relational Database Schemes. VLDB 1984: 196-207
  6. Gösta Grahne, Kari-Jouko Räihä: Dependency Characterizations for Acyclic Database Schemes. PODS 1984: 9-18
  7. Alessandro D'Atri, Marina Moscarini: On the Recognition and Design of Acyclic Databases. PODS 1984: 1-8
  8. Gösta Grahne, Kari-Jouko Räihä: Database Decomposition into Fourth Normal Form. VLDB 1983: 186-196
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:43 2009