Representing extended entity-relationship structures in relational databases: a modular approach

ABSTRACT

A common approach to database design is to describe the structures and constraints of the database application in terms of a semantic data model, and then represent the resulting schema using the data model of a commercial database management system. Often, in practice, Extended Entity-Relationship (EER) schemas are translated into equivalent relational schemas. This translation involves different aspects: representing the EER schema using relational constructs, assigning names to relational attributes, normalization, and merging relations. Considering these aspects together, as is usually done in the design methodologies proposed in the literature, is confusing and leads to inaccurate results. We propose to treat separately these aspects and split the translation into four stages (modules) corresponding to the four aspects mentioned above. We define criteria for both evaluating the correctness of and characterizing the relationship between alternative relational representations of EER schemas.

REFERENCES

• 1: Paolo Atzeni , Edward P. F. Chan, Independent Database Schemes under Functional and Inclusion Dependencies, Proceedings of the 13th International Conference on Very Large Data Bases, p.159-166, September 01-04, 1987
• 2: Paolo Atzeni , D. Stott Parker, Jr., Assumptions in relational database theory, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588113]
• 3: Paolo Atzeni , Douglas Stott Parker, Jr., Formal Properties of Net-Based Knowledge Representation Schemes, Proceedings of the Second International Conference on Data Engineering, p.700-706, February 05-07, 1986
• 4: Lynette I. Brady, A Universal Relation Assumption Based on Entities and Relationships, Proceedings of the Fourth International Conference on Entity-Relationship Approach, p.208-215, October 29-30, 1985
• 5: CASANOVA, M. A., FAGIN, R., AND PAPADIMITRIOU, C. H. Inclusion dependencies and their interactmn with functional dependencies. J. Comput. Syst. Scl. 28, i (Feb. 1984), 29-59.
• 6: Peter Pin-Shan Chen, The entity-relationship model—toward a unified view of data, ACM Transactions on Database Systems (TODS), v.1 n.1, p.9-36, March 1976 [doi>10.1145/320434.320440]
• 7: E. F. Codd, Extending the database relational model to capture more meaning, ACM Transactions on Database Systems (TODS), v.4 n.4, p.397-434, Dec. 1979 [doi>10.1145/320107.320109]
• 8: Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
• 9: Richard Hull, Relative information capacity of simple relational database schemata, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588027]
• 10: Richard Hull , Roger King, Semantic database modeling: survey, applications, and research issues, ACM Computing Surveys (CSUR), v.19 n.3, p.201-260, Sept. 1987 [doi>10.1145/45072.45073]
• 11: JAJODIA, S., N6, P. A., AND SPRINGSTEEL, F.N. The problem of equivalence for entity-relationship diagrams. IEEE Trans. Softw Eng. SE 9, 5 (Sept. 1983), 617-630.
• 12: Sushil Jajodia , Peter A. Ng , Frederick N. Springsteel, Entity-relationship diagrams which are in BCNF, International Journal of Parallel Programming, v.12 n.4, p.269-283, Aug. 1983
• 13: Y. Edmund Lien, On the Semantics of the Entity-Relationship Data Model, Proceedings of the 1st International Conference on the Entity-Relationship Approach to Systems Analysis and Design, p.155-168, January 1980
• 14: Y. Edmund Lien, On the Equivalence of Database Models, Journal of the ACM (JACM), v.29 n.2, p.333-362, April 1982 [doi>10.1145/322307.322311]
• 15: David Maier, Theory of Relational Databases, Computer Science Pr, 1983
• 16: MAIER, D., ROZENSHTEIN, D., AND STEIN, J. Representing roles in universal scheme interfaces. IEEE Trans. Softw. Eng. SE-11, 7 (July 1985), 644-652.
• 17: MAIER, D., ROZENSHTEIN, D., AND WARREN, D.S. Window functions. In Advances in Computing Research, vol. 3, JAI Press, 1986, pp. 213-246.
• 18: David Maier , Jeffrey D. Ullman , Moshe Y. Vardi, On the foundations of the universal relation model, ACM Transactions on Database Systems (TODS), v.9 n.2, p.283-308, June 1984 [doi>10.1145/329.318580]
• 19: V. M. Markowitz , J. A. Makowsky, Identifying Extended Entity-Relationship Object Structures in Relational Schemas, IEEE Transactions on Software Engineering, v.16 n.8, p.777-790, August 1990 [doi>10.1109/32.57618]
• 20: Victor M. Markowitz, A Relation Merging Technique for Relational Databases, Proceedings of the Eighth International Conference on Data Engineering, p.428-437, February 03-07, 1992
• 21: MARKOWITZ, V. M. Problems underlying the use of referential integrity mechanisms in relational database management systems. In Proceedings Supplement of the 7th IEEE International Conference on Data Eng~neemng (Kobe, Japan, Apr. 8 12, 1991), pp. 41-49.
• 22: MARKOWITZ, V. M., AND FANG, W SDT 4.1. Reference Manual. Tech. Rep. LBL-27843, Lawrence Berkeley Laboratory, May 1991.
• 23: Victor M. Markowitz , Arie Shoshani, Name Assignment Techniques for Relational Schemas Representing Extended Entity-Relationship Schemas, Proceedings of the Eight International Conference on Enity-Relationship Approach to Database Design and Querying, p.75-93, October 18-20, 1989
• 24: Toby J. Teorey , Dongqing Yang , James P. Fry, A logical design methodology for relational databases using the extended entity-relationship model, ACM Computing Surveys (CSUR), v.18 n.2, p.197-222, June 1986 [doi>10.1145/7474.7475]
• 25: Toby J. Teorey, Database modeling and design: the entity-relationship approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 26: SZETO, E., AND MARKOWlTZ, V.M. ERDRAW 2.2. Reference Manual. Tech. Rep. LBL-PUB- 3084, Lawrence Berkeley Laboratory, May 1991.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Normal forms
      H.2.3 Languages
          Subjects: Data description languages (DDL)

General Terms:
Algorithms, Design

Keywords:
database design, extended entity-relationship model, relational data model, schema translation, semantic data model