Relational Database Design by ER- and EER-to-Relational Mapping

Chapter 9
← Main Page
  1. Mapping ER to Relational
    1. The Example
    2. The Algorithm
    3. In Detail
    4. Summary
  2. Mapping EER to Relational
    1. Specialization/Generalization
      1. Example
    2. Shared Subclasses (Multiple Inheritance)
    3. Union Types (Categories)
Having designed a database using an ER or EER model, let's automatically convert it to relational form as a first draft implementation model. How? ­

Mapping ER to Relational

­

The Example

­

The Algorithm

  1. Regular entity types
  2. Weak entity types
  3. Binary 1:1 relationship types
  4. Binary 1:N relationship types
  5. Binary M:N relationship types
  6. Multivalued attributes
  7. Higher-arity relationship types
­

In Detail

Step 1: Regular Entity Types
Create an entity relation for each strong entity type. Include all single-valued attributes. Flatten composite attributes. Keys become secondary keys, except for the one chosen to be the primary key.
Step 2: Weak Entity Types
Also create an entity relation for each weak entity type, similarly including its (flattened) single-valued attributes. In addition, add the primary key of each owner entity type as a foreign key attribute here. Possibly make this foreign key CASCADE.
Step 3: Binary 1:1 Relationship Types
Let the relationship be of the form [S]——<R>——[T].
  1. Foreign key approach: The primary key of T is added as a foreign key in S. Attributes of R are moved to S (possibly renaming them for clarity). If only one of the entities has total participation it's better to call it S, to avoid null attributes. If neither entity has total participation nulls may be unavoidable. This is the preferred approach in typical cases.
  2. Merged relation approach: Both entity types are stored in the same relational table, “pre-joined”. If the relationship is not total both ways, there will be null padding on tuples that represent just one entity type. Any attributes of R are also moved to this table.
  3. Cross-reference approach: A separate relation represents R; each tuple is a foreign key from S and a foreign key from T. Any attributes of R are also added to this relation. Here foreign keys should CASCADE.
ApproachJoin cost Null-storage cost
Foreign key1low to moderate
Merged relation0very high, unless both are total
Cross-reference2none
Step 4: Binary 1:N Relationship Types
Let the relationship be of the form [S]——N<R>1——[T]. The primary key of T is added as a foreign key in S. Attributes of R are moved to S. This is the foreign key approach. The merged relation approach is not possible for 1:N relationships. (Why?) The cross-reference approach might be used if the join cost is worth avoid null storage.
Step 5: Binary M:N Relationship Types
Here the cross-reference approach (also called a relationship relation) is the only possible way.
Step 6: Multivalued Attributes
Let an entity S have multivalued attribute A. Create a new relation R representing the attribute, with a foreign key into S added. The primary key of R is the combination of the foreign key and A. Once again this relation is dependent on an “owner relation” so its foreign key should CASCADE.
Step 7: Higher-Arity Relationship Types
Here again, use the cross-reference approach. For each n-ary relationship create a relation to represent it. Add a foreign key into each participating entity type. Also add any attributes of the relationship. The primary key of this relation is the combination of all foreign keys into participating entity types that do not have a max cardinality of 1.
­
­

Summary

ER ModelRelational Model
Entity typeEntity relation
1:1 and 1:N relationship typeForeign key or relationship relation
M:N relationship typeRelationship relation and two foreign keys
n-ary relationship typeRelationship relation and n foreign keys
Simple attributeAttribute
Composite attributeSet of component attributes
Multivalued attributeRelation and foreign key
Value setDomain
Key attributePrimary key or secondary key

Once More With Feeling! ­

Mapping EER to Relational

Adds three new complications to consider: how to represent a specialization group (generalization group), how to handle shared subclasses, and how to represent union types. ­

Specialization/Generalization



Step 8: Specialization/Generalization
Use Attrs(R) to mean the attributes of relation R, and PK(R) to mean the primary key of R. Let the subclasses be {S₁,S₂,…,Sm} and the superclass be C, and let Attr(C) = {k,a₁,…,an} and PK(C) = k.
  1. Multiple relations—superclass and subclasses Create a relation to represent C, having its attributes and primary key. Also create relations for each Si, having attributes Attr(Si) ∪ {k}. In these relations k is both the primary key and a foreign key into C.
  2. Multiple relations—subclass relations only Only create relations for each Si. The attributes of each of these relations will be Attr(Si) ∪ {k} ∪ Attr(C). The primary key will be k.
  3. Single relation with one type attribute Create one relation representing the entire specialization set. Its attributes are Attr(C) ∪ {t} ∪ i=0m Attr(Si). Attribute t is a type attribute (discriminator) that identifies which entity subtype an entity belongs to. If the specialization is already attribute-defined it uses that as t, otherwise t is a new attribute.
  4. Single relation with multiple type attributes Proceed as in the previous approach, except instead of one t create m ts, each one a Boolean indicating whether a tuple is a member of its associated subtype. Together the ts form a bitmap of the entity's type.
ApproachPreconditionsConsiderationsTradeoffs
A (super and sub relations) None   Most flexible but incurs a join cost
B (sub relations) Specialization must be total Specialization should be disjoint In order to query all entities of the supertype one must OUTER UNION the subtype relations (and project to Attr(C), technically)
C (one relation, one t) Specialization must be disjoint If one table is desirable Potential for a large NULL cost
D (one relation, multiple t's) None One table is desired but specialization is overlapping Also very flexible but incurs a NULL cost
Note this step is applied to each specialization group independently. In a hierarchy or lattice, each application of the step is free to be any of the four approaches. ­

Example

Person/{Employee,Alumnus,Student}8A
Employee/{Staff,Faculty,Student_Assistant}8C
Student_Assistant/{Research_Assistant,Teaching_Assistant}8D
Student/Student_Assistant8D
Student/{Graduate_Student,Undergraduate_Student}8D
­
­

Shared Subclasses (Multiple Inheritance)

All classes must have the same key. Then, any of the four approaches can work, but an approach must be performed for each superclass of the shared subclass (one for each specialization group). They can be different. In the previous example, Employee → Student_Assistant used approach 8C, adding attribute Employee_type to the Employee relation. But Student → Student-Assistant used approach 8D, adding Boolean attribute Student_assist_flag to the Student relation. (The attribute of Student_Assistant, Percent_time, could have gone to either one of the relations, so long as it went to only one of them.) ­

Union Types (Categories)

Step 9: Union Types
Let C₁,C₂,…,Cm be the entity types participating in the union and S be the union type. Create a relation for S. If the primary keys of the Ci relations differ, create a surrogate key ks so that PK(S)=ks, and also add ks to each Attr(Ci) as a foreign key into S. If all the Cis have the same primary key type, use that as PK(S) instead.
By the way, the book mentions it may be a good idea to add a type discriminator to S, to indicate which entity type a tuple in the union type belongs to. Why?
­

Your Questions

Questions

ER Practice

  1. Regular entity types
  2. Weak entity types
  3. Binary 1:1 relationship types
  4. Binary 1:N relationship types
  5. Binary M:N relationship types
  6. Multivalued attributes
  7. Higher-arity relationship types

EER Practice

  1. Regular entity types
  2. Weak entity types
  3. Binary 1:1 relationship types
  4. Binary 1:N relationship types
  5. Binary M:N relationship types
  6. Multivalued attributes
  7. Higher-arity relationship types
  8. Specialization/Generalization
  9. Union types

 
 
 
 
 
 

Weather Example


 
 
 
 
 
 
← Main Page