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}
}
BibTeX

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 ... BibTeX

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

Referenced by

  1. Mark Levene, George Loizou: Database Design for Incomplete Relations. ACM Trans. Database Syst. 24(1): 80-125(1999)
  2. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  3. Ke Wang, Marc H. Graham: Constant-Time Maintainability: A Generalization of Independence. ACM Trans. Database Syst. 17(2): 201-246(1992)
  4. Jürgen Diet, Frederick H. Lochovsky: Interactive Specification and Integration of User Views Using Forms. ER 1989: 171-185
  5. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  6. Volkert Brosda, Gottfried Vossen: Update and Retrieval in a Relational Database Through a Universal Schema Interface. ACM Trans. Database Syst. 13(4): 449-485(1988)
  7. Detlev Ruland, Dietmar Seipel: Designing Alpha-Acyclic BCNF-Database Schemes. MFDBS 1987: 197-209
  8. Catriel Beeri, Michael Kifer: An Integrated Approach to Logical Design of Relational Database Schemes. ACM Trans. Database Syst. 11(2): 134-158(1986)
  9. Carlo Batini, Maurizio Lenzerini, Shamkant B. Navathe: A Comparative Analysis of Methodologies for Database Schema Integration. ACM Comput. Surv. 18(4): 323-364(1986)
  10. Joachim Biskup, Bernhard Convent: A Formal View Integration Method. SIGMOD Conference 1986: 398-407
  11. Detlev Ruland, Dietmar Seipel: Alpha-Acyclic Decompositions of Relational Database Schemes. PODS 1986: 191-201
  12. Edward P. F. Chan, Héctor J. Hernández: On the Desirability of gamma-Acyclic BCNF Database Schemes. ICDT 1986: 105-122
  13. Gottfried Vossen, Volkert Brosda: A High-Level User Interface for Update and Retrieval in Relational Databases - Language Aspects. SIGMOD Conference 1985: 343-353
  14. Jacob Stein, David Maier: Relaxing the Universal Relation Scheme Assumption. PODS 1985: 76-84
  15. Volkert Brosda, Gottfried Vossen: Updating a Relational Database through a Universal Schema Interface. PODS 1985: 66-75
  16. François Bancilhon, Nicolas Spyratos: Algebraic Versus Probabilistic Independence in Data Bases. PODS 1985: 149-153
  17. Hirofumi Katsuno: An Extension of Conflict-Free Multivalued Dependency Sets. ACM Trans. Database Syst. 9(2): 309-326(1984)
  18. Catriel Beeri, Michael Kifer: Comprehensive Approach to the Design of Relational Database Schemes. VLDB 1984: 196-207
  19. Yehoshua Sagiv: A Characterization of Globally Consistent Databases and Their Correct Access Paths. ACM Trans. Database Syst. 8(2): 266-286(1983)
  20. Marc H. Graham: Functions in Databases. ACM Trans. Database Syst. 8(1): 81-109(1983)
  21. Gösta Grahne, Kari-Jouko Räihä: Database Decomposition into Fourth Normal Form. VLDB 1983: 186-196
  22. David Maier, David Rozenshtein, David Scott Warren: Windows on the World. SIGMOD Conference 1983: 68-78
  23. Sharon McCure Kuck, Yehoshua Sagiv: Designing Globally Consistent Network Schemas. SIGMOD Conference 1983: 185-195
  24. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
    Contents
  25. Carlo Zaniolo: A New Normal Form for the Design of Relational Database Schemata. ACM Trans. Database Syst. 7(3): 489-499(1982)
  26. Carol Helfgott LeDoux, Douglas Stott Parker Jr.: Reflections on Boyce-Codd Normal Form. VLDB 1982: 131-141
  27. Sharon McCure Kuck, Yehoshua Sagiv: A Universal Relation Database System Implemented via the Network Model. PODS 1982: 147-157
  28. Tok Wang Ling, Frank Wm. Tompa, Tiko Kameda: An Improved Third Normal Form for Relational Databases. ACM Trans. Database Syst. 6(2): 329-346(1981)
  29. François Bancilhon, Nicolas Spyratos: Independent Components of Databases. VLDB 1981: 398-408
  30. Yehoshua Sagiv: Can We Use the Universal Instance Assumption Without Using Nulls? SIGMOD Conference 1981: 108-120
  31. Peter Honeyman: Extension Joins. VLDB 1980: 239-244
  32. Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Optimization of a Class of Relational Expressions. ACM Trans. Database Syst. 4(4): 435-454(1979)
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:39:21 2009