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

Synthesizing Independent Database Schemas.

Joachim Biskup, Umeshwar Dayal, Philip A. Bernstein: Synthesizing Independent Database Schemas. SIGMOD Conference 1979: 143-151
@inproceedings{DBLP:conf/sigmod/BiskupDB79,
  author    = {Joachim Biskup and
               Umeshwar Dayal and
               Philip A. Bernstein},
  editor    = {Philip A. Bernstein},
  title     = {Synthesizing Independent Database Schemas},
  booktitle = {Proceedings of the 1979 ACM SIGMOD International Conference on
               Management of Data, Boston, Massachusetts, May 30 - June 1},
  publisher = {ACM},
  year      = {1979},
  isbn      = {0-89791-001-X},
  pages     = {143-151},
  ee        = {http://doi.acm.org/10.1145/582095.582118, db/conf/sigmod/BiskupDB79.html},
  crossref  = {DBLP:conf/sigmod/79},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We study the following database design problem. Given a universal relation scheme <U,F> where F is a set of functional dependencies, find an in some way normalized database schema D= {<X1, Fl>, ..., <Xn, Fn>} where Xi < U and Fi is inherited from F, such that D is an independent representation of the universal scheme <U, F>. This means thatD has both the lossless join property and the faithful closure property, (Union i=1n F)+, where + denotes the closure of a set of functional dependencies. We show that this goal can easily be achieved by an extension of the well-known synthetic approach of Bernstein and others to database design. We merely have to check whether the usual synthesis procedure has produced a key component <Xi, Fi> such that Xi = U in F=; in case this is true the output of the synthesis procedure is actually an independent (and not only faithful) representation, otherwise we only have to add one further component, namely just a key. These claims are proved by a careful inspection of the Aho/ Beeri/Ullman algorithm to test for losslessness. Finally, we show how to use our method to synthesize minimal independent third normal form schemas.

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


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Philip A. Bernstein (Ed.): Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, Boston, Massachusetts, May 30 - June 1. ACM 1979, ISBN 0-89791-001-X CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
Contents

Online Edition: ACM Digital Library


References

[1]
Alfred V. Aho, Catriel Beeri, Jeffrey D. Ullman: The Theory of Joins in Relational Data Bases (Extended Abstract). FOCS 1977: 107-113 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Database Normalization Theory. VLDB 1978: 113-124 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
Catriel Beeri, Ronald Fagin, John H. Howard: A Complete Axiomatization for Functional and Multivalued Dependencies in Database Relations. SIGMOD Conference 1977: 47-61 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
Philip A. Bernstein: Synthesizing Third Normal Form Relations from Functional Dependencies. ACM Trans. Database Syst. 1(4): 277-298(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
E. F. Codd: Further Normalization of the Data Base Relational Model. IBM Research Report, San Jose, California RJ909: (1971) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
...
[9]
...
[10]
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
[11]
Jorma Rissanen: Independent Components of Relations. ACM Trans. Database Syst. 2(4): 317-325(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
Jorma Rissanen: Theory of Relations for Databases - A Tutorial Survey. MFCS 1978: 536-551 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
...
[14]
...

Copyright © Fri Mar 12 17:21:24 2010 by Michael Ley (ley@uni-trier.de)