Entity-Relation Mapping Algorithm

Written by @andrewlalis. Adapted from Fundamentals of Database Systems, 7th Edition.

1. Mapping of Regular Entity Types

For each regular (strong) entity type E in the ER schema, create a relation R that includes all the simple attributes of E. Include only the simple component attributes of a composite attribute. Choose one of the key attributes of E as the primary key for R. If the chosen key is a composite, then the set of simple attributes that form it will together form the primary key of R.

If multiple keys were identified for E during the design of the schema, then the information describing the attributes that form each additional key should be kept in order to specify additional (unique) keys of the relation R. Knowledge about keys is also kept for indexing purposes and other types of analyses.

2. Mapping of Weak Entity Types

For each weak entity type W in the ER schema with owner entity type E, create a relation R and include all simple attributes (or simple components of composite attributes) of W as attributes of R. In addition, include as foreign key attributes of R, the primary key attribute(s) of the relation(s) that correspond to the owner entity type(s); this takes care of mapping the identifying relationship type of W. The primary key of R is the combination of the primary key(s) of the owner(s) and the partial key of the weak entity type W, if any. If there is a weak entity type E₂ whose owner is also a weak entity type E₁, then E₁ should be mapped first, to determine the primary key(s) that will be required by E₂.

3. Mapping of Binary 1:1 Relationship Types

For each binary 1:1 relationship type R in the ER schema, identify the relations S and T that correspond to the entity types participating in R. There are three possible approaches, the first of which is the most useful and should be followed unless special conditions exist:

• Foreign Key Approach: Choose one of the relations, for example S (preferably one with total participation in the relationship), and include a foreign key in S which references the primary key of T. Include all simple attributes of the relationship type R as attributes of S.
• Merged Relation Approach: Merge the two entity types and the relationship into a single relation. This is only possible when both participations are total, as ths would indicate that the two tables will have the exact same number of tuples at all times.
• Cross-Reference or Relationship Relation Approach: Set up a third relation for the purpose of cross-referencing the primary keys of the two relations S and T representing the entity types. As we will see, this approach is required for binary M:N relationships. The resulting relation is called a relationship relation (or lookup table/join table), because each tuple in the relation represents an instance of the relationship that connects one tuple from S with one tuple from T. The relation will therefore include the primary key attributes of S and T as foreign keys to their respective relations. The drawback of this approach is the added complexity of an additional relation, and requiring extra join operations when combining related tuples from the tables.

4. Mapping of Binary 1:N Relationship Types

There are two possible approaches, the first of which is generally preferred as it reduces the number of tables.

• Foreign Key Approach: For each regular binary 1:N (or N:1, depending on your perspective), identify the relation which represents the entity that's on the N side of the relationship, and include in that entity's relation a foreign key to the entity on the 1 side. Include any simple attributes (or simple components of composite attributes) of the 1:N relationship as attributes of the N-side entity.
• Relationship Relation Approach: An alternative approach is to use a relationship relation, where we create a separate relation R whose attributes are the primary keys of the two related entities, S and T. Those attributes will also be foreign keys to their respective entity relation. The primary key of R is the same as the primary key of the N-side entity.

5. Mapping of Binary M:N Relationship Types

The only option for M:N relationships in the traditional relational model is the relationship relation. For each binary M:N relationship type R, create a new relation S to represent R. Include foreign key attributes in S for the primary keys of both participating entities. The combination of both foreign keys forms the primary key of S. Also include any simple attributes of R as attributes of S.

6. Mapping of Multivalued Attributes

For each multivalued attribute A from an entity E, create a new relation that contains a foreign key to E, and an attribute representing a single instance of A. The primary key of the new relation is the combination of the foreign key and the single attribute.

7. Mapping of N-ary Relationship Types

For each N-ary relationship type R, where n > 2, create a new relationship relation S to represent R. Include as foreign key attributes in S the primary keys of the relations that represent the participating entity types. Also include any simple attributes of the n-ary relationship type (or simple components of the composite attributes) as attributes of S. The primary key of S is usually a combination of all the foreign keys that reference the participating entities (except the foreign keys to entities that participate in the relationship with a cardinality constraint of 1).

8. Options for Mapping Specialization or Generalization

There are a few different options for mapping specializations and generalizations. The four most common are given here:

• Multiple Relations - Super and Subclasses: Create a relation for the superclass just as you would for a normal entity. Create a relation for each subclass (specialization) of the superclass, which contains a foreign key to the super class, as well as all attributes of the subclass. The foreign key to the superclass will also be the subclass' primary key. This option works for any specialization (total or partial, disjoint or overlapping).
• Multiple Relations - Subclasses Only: Create a relation for each subclass, which contains all attributes of the subclass, alongside all attributes of the superclass, and use the superclass' primary key as the primary key for each relation. This option only works for specializations where the superclass has total participation (every entity in the superclass must belong to at least one subclass). This option is also only recommended for disjointed specializations, because an overlapping specialization would lead to duplicate superclass entity information in possibly many of the subclass relations.
• Single Relation with One Type Attribute: Create a single relation with the attributes of the superclass, combined with the attributes of every subclass, and a discriminating type attribute whose value indicates the subclass to which each tuple belongs. This option works only for a specialization whose subclasses are disjoint, and has the potential for generating a huge number of NULL values if there are many separate subclass-specific attributes.
• Single Relation with Multiple Attribute Types: Create a single relation with the attributes of the superclass and all subclasses, just as with the previous option, but instead of a single discriminating type attribute, create one boolean type attribute for each subclass, to indicate whether or not the entity belongs to a given subclass. This option is a variant of the previous, which has been designed to work with overlapping (but will also work with disjoint).

9. Mapping of Union Types (Categories)

For mapping a union type, we create a surrogate key attribute which should be appended to the relation of any entity that participates in the union. A relation is made for the union type itself, and that relation uses the surrogate key as its primary key. We then also declare the surrogate key in each participating entity relation as a foreign key to the union type's primary key.