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= {<X₁, F_l>, ..., <X_n, F_n>} where X_i < U and F_i 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=₁ⁿ 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 <X_i, F_i> such that X_i = 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 ...

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
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/smod7592 or /cdrom

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

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
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

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

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