On the Correctness of Representing Extended Entity-Relationship Structures in the Relational Model.

@inproceedings{DBLP:conf/sigmod/MarkowitzS89,
  author    = {Victor M. Markowitz and
               Arie Shoshani},
  editor    = {James Clifford and
               Bruce G. Lindsay and
               David Maier},
  title     = {On the Correctness of Representing Extended Entity-Relationship
               Structures in the Relational Model},
  booktitle = {Proceedings of the 1989 ACM SIGMOD International Conference on
               Management of Data, Portland, Oregon, May 31 - June 2, 1989},
  publisher = {ACM Press},
  year      = {1989},
  pages     = {430-439},
  ee        = {http://doi.acm.org/10.1145/67544.66967, db/conf/sigmod/MarkowitzS89.html},
  crossref  = {DBLP:conf/sigmod/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Although the relational representation of Entity-Relationship (ER) structures gained extensive coverage, scarce attention has been paid to the issue of correctness for such representations. Several mappings have been proposed for the representation of both ER and extended ER (EER) structures by relational schemas. The informal nature of most of these proposals, however, does not allow a precise evaluation of their correctness, nor a comparison of the various mappings. We propose a canonical relational representation for EER structures and prove its correctness. We claim that a relational schema represents correctly an EER structure if it has equivalent information-capacity with the corresponding canonical representation.

The second problem addressed by this paper is the normalization of relational schemas that represent EER structures. We examine the conditions required by this process and show that ignoring these conditions leads to erroneous analyses and inappropriate design decisions. We show that, under these conditions, the canonical relational representation of any (unrestricted) EER structure has an (information-capacity) equivalent Boyce-Codd Normal Form schema.

Copyright © 1989 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

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

• 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

Online Edition: ACM Digital Library

References

[1]

Paolo Atzeni, Douglas Stott Parker Jr.: Assumptions in Relational Database Theory. PODS 1982: 1-9 BibTeX

[2]

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

[3]

Lynette I. Brady: A Universal Relation Assumption Based on Entities and Relationships. ER 1985: 208-215 BibTeX

[4]

Marco A. Casanova, Ronald Fagin, Christos H. Papadimitriou: Inclusion Dependencies and Their Interaction with Functional Dependencies. J. Comput. Syst. Sci. 28(1): 29-59(1984) BibTeX

[5]

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

[6]

E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX

[7]

Stavros S. Cosmadakis, Paris C. Kanellakis: Equational Theories and Database Constraints. STOC 1985: 273-284 BibTeX

[8]

...

[9]

Richard Hull: Relative Information Capacity of Simple Relational Database Schemata. PODS 1984: 97-109 BibTeX

[10]

Richard Hull, Roger King: Semantic Database Modeling: Survey, Applications, and Research Issues. ACM Comput. Surv. 19(3): 201-260(1987) BibTeX

[11]

Sushil Jajodia, Peter A. Ng, Frederick N. Springsteel: The Problem of Equivalence for Entity-Relationship Diagrams. IEEE Trans. Software Eng. 9(5): 617-630(1983) BibTeX

[12]

...

[13]

...

[14]

...

[15]

David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX

[16]

David Maier, David Rozenshtein, David Scott Warren: Window Functions. Advances in Computing Research 3: 213-246(1986) BibTeX

[17]

David Maier, Jeffrey D. Ullman, Moshe Y. Vardi: On the Foundations of the Universal Relation Model. ACM Trans. Database Syst. 9(2): 283-308(1984) BibTeX

[18]

...

[19]

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

[20]

Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX

Referenced by

1. Zahir Tari, John Stokes, Stefano Spaccapietra: Object Normal Forms and Dependency Constraints for Object-Oriented Schemata. ACM Trans. Database Syst. 22(4): 513-569(1997)
2. Il-Yeol Song, Trevor H. Jones: Ternary Relationship Decomposition Strategies Based on Binary Imposition Rules. ICDE 1995: 485-492
3. Arnon Rosenthal, David S. Reiner: Tools and Transformations - Rigorous and Otherwise - for Practical Database Design. ACM Trans. Database Syst. 19(2): 167-211(1994)
4. William J. Premerlani, Michael R. Blaha: An Approach for Reverse Engineering of Relational Databases. Commun. ACM 37(5): 42-49, 134(1994)
5. Alice H. Muntz, Christian T. Ramiller: A Requirement-Based Approach to Data Modeling and Re-Engineering. VLDB 1994: 643-654
6. Il-Yeol Song, Trevor H. Jones: Analysis of Binary Relationships within Ternary Relationships in ER Modeling. ER 1993: 271-282
7. Alberto H. F. Laender, Donal J. Flynn: A Semantic Comparison of the Modelling Capabilities of the ER and NIAM Models. ER 1993: 242-256
8. Norbert Kehrer, Gustaf Neumann: An EER Prototyping Environment and its Implemetation in a Datalog Language. ER 1992: 243-261
9. Vram Kouramajian, Ramez Elmasri: Mapping of 2-D Temporal Extended ER Models into Temporal Nested Relational Models. ER 1991: 671-691
10. Marco A. Casanova, A. P. de Carvalho, L. F. G. G. M. Ridolfi, Alberto H. F. Laender: An Analysis of Table Constraints in SQL2 Based on the Entity-Relationship Model. ER 1991: 623-641
11. Y. Richard Wang, Stuart E. Madnick: A Polygen Model for Heterogeneous Database Systems: The Source Tagging Perspective. VLDB 1990: 519-538
12. Victor M. Markowitz: Referential Integrity Revisited: An Object-Oriented Perspective. VLDB 1990: 578-589
13. Victor M. Markowitz: Representing Processes in the Extended Entity-Relationship Model. ICDE 1990: 103-110
14. Jean Philippe Lagrange: A Knowledge-Based System and an ER Query Language for Accessing Relational Databases. ER 1990: 157-170
15. Marco A. Casanova, Luiz Tucherman, Alberto H. F. Laender: Algorithms for Designing and Maintaining Optimized Relational Representations of Entity-Relationship Schemas. ER 1990: 361-374
16. Arnon Rosenthal, David S. Reiner: Database Design Tools: Combining Theory, Guesswork, and User Interaction. ER 1989: 187-201
17. Victor M. Markowitz, Arie Shoshani: Abbreviated Query Interpretation in Extended Entity-Relationship Oriented Databases. ER 1989: 325-343
18. Victor M. Markowitz, Arie Shoshani: Name Assignment Techniques for Relational Schemas Representing Extended Entity-Relationship Schemas. ER 1989: 75-93