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

Victor M. Markowitz, Arie Shoshani: On the Correctness of Representing Extended Entity-Relationship Structures in the Relational Model. SIGMOD Conference 1989: 430-439
  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        = {, db/conf/sigmod/MarkowitzS89.html},
  crossref  = {DBLP:conf/sigmod/89},
  bibsource = {DBLP,}


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

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

James Clifford, Bruce G. Lindsay, David Maier (Eds.): Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, Portland, Oregon, May 31 - June 2, 1989. ACM Press 1989 BibTeX , SIGMOD Record 18(2), June 1989

Online Edition: ACM Digital Library


Paolo Atzeni, Douglas Stott Parker Jr.: Assumptions in Relational Database Theory. PODS 1982: 1-9 BibTeX
Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Database Normalization Theory. VLDB 1978: 113-124 BibTeX
Lynette I. Brady: A Universal Relation Assumption Based on Entities and Relationships. ER 1985: 208-215 BibTeX
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
Peter P. Chen: The Entity-Relationship Model - Toward a Unified View of Data. ACM Trans. Database Syst. 1(1): 9-36(1976) BibTeX
E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX
Stavros S. Cosmadakis, Paris C. Kanellakis: Equational Theories and Database Constraints. STOC 1985: 273-284 BibTeX
Richard Hull: Relative Information Capacity of Simple Relational Database Schemata. PODS 1984: 97-109 BibTeX
Richard Hull, Roger King: Semantic Database Modeling: Survey, Applications, and Research Issues. ACM Comput. Surv. 19(3): 201-260(1987) BibTeX
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
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX
David Maier, David Rozenshtein, David Scott Warren: Window Functions. Advances in Computing Research 3: 213-246(1986) BibTeX
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
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
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6

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
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:39:59 2009