Dependency Characterizations for Acyclic Database Schemes.

@inproceedings{DBLP:conf/pods/GrahneR84,
  author    = {G{\"o}sta Grahne and
               Kari-Jouko R{\"a}ih{\"a}},
  title     = {Dependency Characterizations for Acyclic Database Schemes},
  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     = {9-18},
  ee        = {http://doi.acm.org/10.1145/588011.588014, db/conf/pods/GrahneR84.html},
  crossref  = {DBLP:conf/pods/84},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Acyclic database schemes have attracted a lot of interest because of the nice properties enjoyed by such schemes. Recently some new acyclicity conditions that are strictly stronger than the normal alpha-acyclicity have been introduced by Fagin. Because of increased requirements, the database schemes in the new classes have some further useful properties that are not shared by alpha-acyclic schemes. Therefore the new classes have practical relevance.

A database designer may work in terms of attribute sets and data dependencies, and not only in terms of database schemes. Thus it is important to have a characterization for the acyclic schemes of various degree in terms of data dependencies. For alpha-acyclic schemes such a characterization exists, but for the new classes the question has been open. In this paper we provide characterizations for beta-, gamma- and Berge-acyclic database schemes. The characterizations can be stated in a simple form: thus they should be useful for the database designer.

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.

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[BBG78]

Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Database Normalization Theory. VLDB 1978: 113-124 BibTeX

[BFMY83]

Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis: On the Desirability of Acyclic Database Schemes. J. ACM 30(3): 479-513(1983) BibTeX

[BeK83]

Catriel Beeri, Michael Kifer: Elimination of Intersection Anomalies from Database Schemes. PODS 1983: 340-351 BibTeX

[Fag83a]

Ronald Fagin: Degrees of Acyclicity for Hypergraphs and Relational Database Schemes. J. ACM 30(3): 514-550(1983) BibTeX

[Fag83b]

Ronald Fagin: Acyclic Database Schemes (of Various Degrees): A Painless Introduction. CAAP 1983: 65-89 BibTeX

[FMU82]

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

[GrR83]

Gösta Grahne, Kari-Jouko Räihä: Database Decomposition into Fourth Normal Form. VLDB 1983: 186-196 BibTeX

[Lie82]

Y. Edmund Lien: On the Equivalence of Database Models. J. ACM 29(2): 333-362(1982) BibTeX

[Sci81]

Edward Sciore: Real-World MVD's. SIGMOD Conference 1981: 121-132 BibTeX

[Sci83]

Edward Sciore: Improving Database Schemes by Adding Attributes. PODS 1983: 379-383 BibTeX

[Ull82a]

Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX

[Ull82b]

Jeffrey D. Ullman: The U. R. Strikes Back. PODS 1982: 10-22 BibTeX

Referenced by

1. Dirk Van Gucht: Interaction-Free Multivalued Dependency Sets. ICDT 1986: 409-420