On the Design of Relational Database Schemata.

@article{DBLP:journals/tods/ZanioloM81,
  author    = {Carlo Zaniolo and
               Michel A. Melkanoff},
  title     = {On the Design of Relational Database Schemata},
  journal   = {ACM Trans. Database Syst.},
  volume    = {6},
  number    = {1},
  year      = {1981},
  pages     = {1-47},
  ee        = {http://doi.acm.org/10.1145/319540.319542, db/journals/tods/ZanioloM81.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The purpose of this paper is to present a new approach to the conceptual design of relational databases based on the complete relatability conditions (CRCs).

It is shown that current database design methodology based upon the elimination of anomalies is not adequate. In contradistinction, the CRCs are shown to provide a powerful criticism for decomposition. A decomposition algorithm is presented which (1) permits decomposition of complex relations into simple, well-defined primitives, (2) preserves all the original information, and (3) minimizes redundancy.

The paper gives a complete derivation of the CRCs, beginning with a unified treatment of functional and multivalued dependencies, and introduces the concept of elementary functional dependencies and multiple elementary multivalued dependencies. Admissibility of covers and validation of results are also discussed, and it is shown how these concepts may be used to improve the design of 3NF schemata. Finally, a convenient graphical representation is proposed, and several examples are described in detail to illustrate the method.

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

Joint ACM SIGMOD / IEEE Computer Society Anthology

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

References

[1]

William Ward Armstrong: Dependency Structures of Data Base Relationships. IFIP Congress 1974: 580-583 BibTeX

[2]

Catriel Beeri, Ronald Fagin, John H. Howard: A Complete Axiomatization for Functional and Multivalued Dependencies in Database Relations. SIGMOD Conference 1977: 47-61 BibTeX

[3]

...

[4]

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

[5]

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

[6]

Philip A. Bernstein: Synthesizing Third Normal Form Relations from Functional Dependencies. ACM Trans. Database Syst. 1(4): 277-298(1976) BibTeX

[7]

Joachim Biskup: On the Complementation Rule for Multivalued Dependencies in Database Relations. Acta Inf. 10: 297-305(1978) BibTeX

[8]

Peter P. Chen: The Entity-Relationship Model - Toward a Unified View of Data. ACM Trans. Database Syst. 1(1): 9-36(1976) BibTeX

[9]

E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX

[10]

E. F. Codd: Further Normalization of the Data Base Relational Model. IBM Research Report, San Jose, California RJ909: (1971) BibTeX

[11]

E. F. Codd: Recent Investigations in Relational Data Base Systems. IFIP Congress 1974: 1017-1021 BibTeX

[12]

C. J. Date: An Introduction to Database Systems, 2nd Edition. Addison-Wesley 1977
BibTeX

[13]

...

[14]

...

[15]

Ronald Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Trans. Database Syst. 2(3): 262-278(1977) BibTeX

[16]

Ronald Fagin: The Decomposition Versus Synthetic Approach to Relational Database Design. VLDB 1977: 441-446 BibTeX

[17]

Zvi Galil: An Almost Linear-Time Algorithm for Computing a Dependency Basis in a Relational Database. J. ACM 29(1): 96-102(1982) BibTeX

[18]

...

[19]

Kenichi Hagihara, Minoru Ito, Kenichi Taniguchi, Tadao Kasami: Decision Problems for Multivalued Dependencies in Relational Databases. SIAM J. Comput. 8(2): 247-264(1979) BibTeX

[20]

Alberto O. Mendelzon: On Axiomatizing Multivalued Dependencies in Relational Databases. J. ACM 26(1): 37-44(1979) BibTeX

[21]

...

[22]

Jorma Rissanen: Independent Components of Relations. ACM Trans. Database Syst. 2(4): 317-325(1977) BibTeX

[23]

...

[24]

...

[25]

...

[26]

...

[27]

...

[28]

Carlo Zaniolo, Michel A. Melkanoff: A Formal Approach to the Definition and the Design of Conceptual Schemata for Database Systems. ACM Trans. Database Syst. 7(1): 24-59(1982) BibTeX

Referenced by

1. Sudha Ram: Deriving Functional Dependencies from the Entity-Relationship Model. Commun. ACM 38(9): 95-107(1995)
2. Bernhard Thalheim: The Higher-Order Entity-Relationship Model and (DB)2. MFDBS 1989: 382-397
3. Margareta Dina Draghici: An Extended View on Data Base Conceptual Design. MFDBS 1989: 148-171
4. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
   Contents
5. Z. Meral Özsoyoglu, Li-Yan Yuan: Reduced MVDs and Minimal Covers. ACM Trans. Database Syst. 12(3): 377-394(1987)
6. Z. Meral Özsoyoglu, Li-Yan Yuan: A New Normal Form for Nested Relations. ACM Trans. Database Syst. 12(1): 111-136(1987)
7. Z. Meral Özsoyoglu, Li-Yan Yuan: A Design Method for Nested Relational Databases. ICDE 1987: 599-608
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. Toby J. Teorey, Dongqing Yang, James P. Fry: A Logical Design Methodology for Relational Databases Using the Extended Entity-Relationship Model. ACM Comput. Surv. 18(2): 197-222(1986)
10. Dirk Van Gucht, Patrick C. Fischer: Some Classes of Multilevel Relational Structures. PODS 1986: 60-69
11. Mokrane Bouzeghoub, Georges Gardarin, Elisabeth Métais: Database Design Tools: An Expert System Approach. VLDB 1985: 82-95
12. Z. Meral Özsoyoglu, Li-Yan Yuan: A Normal Form for Nested Relations. PODS 1985: 251-260
13. Tim Connors: Equivalence of Views by Query Capacity. PODS 1985: 143-148
14. Catriel Beeri, Michael Kifer: Comprehensive Approach to the Design of Relational Database Schemes. VLDB 1984: 196-207
15. Allan Shepherd, Larry Kerschberg: PRISM: A Knowledge Based System for Semantic Integrity Specification and Enforcement in Database Systems. SIGMOD Conference 1984: 307-315
16. Hartmut Wedekind: Supporting the Design of Conceptual Schemata by Database Systems. ICDE 1984: 434-438
17. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
    Contents
18. Carlo Zaniolo, Michel A. Melkanoff: A Formal Approach to the Definition and the Design of Conceptual Schemata for Database Systems. ACM Trans. Database Syst. 7(1): 24-59(1982)
19. Carlo Zaniolo: A New Normal Form for the Design of Relational Database Schemata. ACM Trans. Database Syst. 7(3): 489-499(1982)
20. Kenneth C. Sevcik: Data Base System Performance Prediction Using an Analytical Model (Invited Paper). VLDB 1981: 182-198
21. William Ward Armstrong, Claude Delobel: Decomposition and Functional Dependencies in Relations. ACM Trans. Database Syst. 5(4): 404-430(1980)
22. Michel A. Melkanoff, Carlo Zaniolo: Decomposition of Relations and Synthesis of Entity-Relationship Diagrams. ER 1979: 277-294