A Formal Approach to the Definition and the Design of Conceptual Schemata for Database Systems.

@article{DBLP:journals/tods/ZanioloM82,
  author    = {Carlo Zaniolo and
               Michel A. Melkanoff},
  title     = {A Formal Approach to the Definition and the Design of Conceptual
               Schemata for Database Systems},
  journal   = {ACM Trans. Database Syst.},
  volume    = {7},
  number    = {1},
  year      = {1982},
  pages     = {24-59},
  ee        = {http://doi.acm.org/10.1145/319682.319695, db/journals/tods/ZanioloM82.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A formal approach is proposed to the definition and the design of conceptual database diagrams to be used as conceptual schemata in a system featuring a multilevel schema architecture, and as an aid for the design of other forms of schemata. We consider E-R (entity-relationship) diagrams, and we introduce a new representation called CAZ-graphs. A rigorous connection is established between these diagrams and some formal constraints used to describe relationships in the framework of the relational data model. These include functional and multivalued dependencies of database relations. The basis for our schemata is a combined representation for two fundamental structures underlying every relation: the first defined by its minimal atomic decompositions, the second by its elementary functional dependencies.

The interaction between these two structures is explored, and we show that, jointly, they can represent a wide spectrum of database relationships, of which the well-known one-to-one, one-to-many, and many-to-many associations constitute only a small subset. It is suggested that a main objective in conceptual schema design is to ensure a complete representation of these two structures. A procedure is presented to design schemata which obtain this objective while eliminating redundancy. A simple correspondence between the topological properties of these schemata and the structure of multivalued dependencies of the original relation is established. Various applications are discussed and a number of illustrative examples are given.

Copyright © 1982 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]

Alfred V. Aho, Catriel Beeri, Jeffrey D. Ullman: The Theory of Joins in Relational Data Bases (Extended Abstract). FOCS 1977: 107-113 BibTeX

[2]

Adarsh K. Arora, C. Robert Carlson: The Information Preserving Properties of Relational Database Transformations. VLDB 1978: 352-359 BibTeX

[3]

Catriel Beeri: On the Membership Problem for Functional and Multivalued Dependencies in Relational Databases. ACM Trans. Database Syst. 5(3): 241-259(1980) BibTeX

[4]

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

[5]

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

[6]

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

[7]

...

[8]

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

[9]

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

[10]

...

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

Eckhard D. Falkenberg: Concepts for Modelling Information. IFIP Working Conference on Modelling in Data Base Management Systems 1976: 95-109 BibTeX

[17]

André Flory, Jacques Kouloumdjian: A Model and a Method for Logical Data Base Design. VLDB 1978: 333-341 BibTeX

[18]

Patrick A. V. Hall, J. Owlett, Stephen Todd: Relations and Entities. IFIP Working Conference on Modelling in Data Base Management Systems 1976: 201-220 BibTeX

[19]

...

[20]

...

[21]

Y. Edmund Lien: On the Semantics of the Entity-Relationship Data Model. ER 1979: 155-168 BibTeX

[22]

Michel A. Melkanoff, Carlo Zaniolo: Decomposition of Relations and Synthesis of Entity-Relationship Diagrams. ER 1979: 277-294 BibTeX

[23]

Jean-Marie Nicolas: Mutual Dependencies and Some Results on Undecomposable Relations. VLDB 1978: 360-367 BibTeX

[24]

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

[25]

Nick Roussopoulos, John Mylopoulos: Using Semantic Networks for Database Management. VLDB 1975: 144-172 BibTeX

[26]

...

[27]

Hans Albrecht Schmid, J. Richard Swenson: On the Semantics of the Relational Data Model. SIGMOD Conference 1975: 211-223 BibTeX

[28]

...

[29]

John Miles Smith, Diane C. P. Smith: Database Abstractions: Aggregation. Commun. ACM 20(6): 405-413(1977) BibTeX

[30]

Nicolas Spyratos, François Bancilhon: Name Independence and Database Abstraction in the Relational Model. MFCS 1978: 497-505 BibTeX

[31]

Dennis Tsichritzis, Anthony C. Klug: The ANSI/X3/SPARC DBMS Framework Report of the Study Group on Dabatase Management Systems. Inf. Syst. 3(3): 173-191(1978) BibTeX

[32]

...

[33]

Carlo Zaniolo, Michel A. Melkanoff: On the Design of Relational Database Schemata. ACM Trans. Database Syst. 6(1): 1-47(1981) BibTeX

Referenced by

1. Sudha Ram: Deriving Functional Dependencies from the Entity-Relationship Model. Commun. ACM 38(9): 95-107(1995)
2. Laura M. Haas, Johann Christoph Freytag, Guy M. Lohman, Hamid Pirahesh: Extensible Query Processing in Starburst. SIGMOD Conference 1989: 377-388
3. Margareta Dina Draghici: An Extended View on Data Base Conceptual Design. MFDBS 1989: 148-171
4. André Flory, Salvatore T. March: SCRABBLE: A Local Database Management System. ER 1986: 271-286
5. Doris E. Altenkrueger: FAIM, the Formal Association Inference Model, a Means for the Formal definition of Coceptual Meta Schemas. ER 1985: 10-17
6. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
   Contents
7. Carlo Zaniolo, Michel A. Melkanoff: On the Design of Relational Database Schemata. ACM Trans. Database Syst. 6(1): 1-47(1981)
8. E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979)
9. Michel A. Melkanoff, Carlo Zaniolo: Decomposition of Relations and Synthesis of Entity-Relationship Diagrams. ER 1979: 277-294