Mapping ER to Relations

The ER-to-relational mapping is a constructive translation: a deterministic procedure that consumes an ER diagram — entity sets with attributes and keys, relationship sets with cardinality ratios and participation constraints — and produces a relational schema consisting of table definitions, primary keys, and foreign keys. The procedure is deterministic in the sense that, given the same ER diagram and the same design choices for optional cases (like 1:1 relationships), it always produces the same schema shape. It is not, however, unique: several valid mappings can exist for a single diagram, and part of the designer's job is choosing among them based on expected query patterns. The central object of translation is the entity set, which becomes a relation schema (a table) with one column per descriptive attribute and the entity set's key attribute(s) as the table's primary key. The second central object is the relationship set, which is handled differently depending on its cardinality ratio (one-to-one, one-to-many, many-to-one, many-to-many) and its participation constraint (total or partial). A many-to-many relationship set fundamentally cannot be captured by adding a column to either entity's table — it needs its own table with a composite key — while a many-to-one relationship set can always be absorbed as a foreign-key column on the "many" side, avoiding an unnecessary extra table. Two attribute categories require special handling because relational tables only support single-valued, atomic columns. A multivalued attribute (e.g., a student's set of phone numbers) violates atomicity and must be pulled out into its own table keyed by the owning entity's key plus the value itself. A composite attribute (e.g., an address made of street, city, and zip) is not atomic either, but the fix is the opposite: it is flattened, replaced by one column per component, directly in the owning table. A derived attribute (e.g., age computed from birth date) is typically omitted from the schema entirely and recomputed by a query or a stored generated column.

The mapping proceeds construct by construct. Below is the complete rule set, followed by pseudocode that mechanizes it.

Rule 1 — Strong entity set. For a strong entity set `E` with attributes `a1, ..., an` and key `K ⊆ {a1,...,an}`, create a table `E(a1, ..., an)` with `PRIMARY KEY (K)`. Every simple, single-valued attribute becomes a column directly.

Rule 2 — Composite attribute. If an attribute `c` is composite with components `c1, ..., ck`, replace the single column `c` with columns `c1, ..., ck` in whatever table `c` belongs to. There is no separate table for a composite attribute unless it is also multivalued.

Rule 3 — Multivalued attribute. For a multivalued attribute `m` belonging to entity set `E` with key `K`, create a new table `EM(K, m)` with `PRIMARY KEY (K, m)` and a foreign key `K → E`. This table has one row per (entity, value) pair, correctly modeling a set of values without repeating groups.

Rule 4 — Weak entity set. A weak entity set `W` has no key of its own; it depends on an identifying (owner) strong entity set `O` via an identifying relationship, and has a partial key (discriminator) `d` that distinguishes `W`-entities that share the same owner. Create a table `W(K_O, b1, ..., bn)` where `K_O` is the owner's primary key attributes, `b1,...,bn` are `W`'s own attributes including `d`, with ``` PRIMARY KEY (K_O, d) FOREIGN KEY (K_O) REFERENCES O(K_O) ON DELETE CASCADE ``` The `ON DELETE CASCADE` reflects existence dependency: a weak entity cannot exist without its owner.

Rule 5 — Many-to-many binary relationship set. For relationship set `R` between entity sets `A` (key `K_A`) and `B` (key `K_B`), with `R`'s own descriptive attributes `r1,...,rm`, create a table ``` R(K_A, K_B, r1, ..., rm) PRIMARY KEY (K_A, K_B) FOREIGN KEY (K_A) REFERENCES A(K_A) FOREIGN KEY (K_B) REFERENCES B(K_B) ``` A separate table is unavoidable here: neither `A` nor `B`'s table has room for a set of partners, since a column can hold only one value per row.

Rule 6 — One-to-many / many-to-one binary relationship set. Say `R` relates `A` and `B` where each `B`-entity relates to at most one `A`-entity (many-to-one from `B` to `A`). Instead of a new table, add `K_A` (plus `R`'s own attributes) as columns to `B`'s table: ``` B(K_B, ..., K_A, r1, ..., rm) FOREIGN KEY (K_A) REFERENCES A(K_A) ``` If participation of `B` in `R` is total, mark the foreign-key columns `NOT NULL`; if partial, allow `NULL` (an unrelated `B`-entity has no `A`-partner).

Rule 7 — One-to-one relationship set. Either side may absorb the foreign key. Add `K_A` to `B`'s table (or symmetrically `K_B` to `A`'s table) with a `UNIQUE` constraint on the foreign-key column, reflecting that each `A` matches at most one `B`. Prefer adding it to whichever side has total participation, so the column can be `NOT NULL` rather than nullable.

Rule 8 — n-ary relationship set (n ≥ 3). Generalize Rule 5: create a table containing the primary key of every participating entity set plus `R`'s own attributes, with the combined foreign keys as the primary key (or a subset thereof, if the cardinality constraints of the diagram identify a smaller determining set).

Rule 9 — Specialization / generalization (ISA hierarchies). For a superclass `S` with subclasses `C1, ..., Ck`, two common strategies:

• Strategy A (multiple tables): create a table for `S` with shared attributes, and a table for each `Ci` containing only `Ci`'s own attributes plus `K_S` as both primary key and foreign key referencing `S`. Good when subclasses are disjoint and queries often target one subclass.
• Strategy B (single table with nulls): create one table with all attributes of `S` and every `Ci`, using a "type" discriminator column; attributes not applicable to a row's type are `NULL`. Good when subclasses overlap heavily in attributes or overlap in membership.

```pseudocode function MAP_ER_TO_RELATIONS(entities, relationships): schema = {} // table_name -> (columns, primary_key, foreign_keys) // Step 1: strong entities for E in entities where E.is_strong: cols = flatten_composites(E.attributes) minus E.multivalued_attributes schema[E.name] = Table(cols, primary_key = E.key) // Step 2: weak entities (owner must already exist) for W in entities where W.is_weak: owner = W.identifying_owner cols = flatten_composites(W.attributes) + owner.key schema[W.name] = Table(cols, primary_key = owner.key + W.partial_key, foreign_keys = {owner.key -> owner.name (ON DELETE CASCADE)}) // Step 3: multivalued attributes, for every entity (strong or weak) for E in entities: for m in E.multivalued_attributes: name = E.name + "_" + m schema[name] = Table(E.key + [m], primary_key = E.key + [m], foreign_keys = {E.key -> E.name}) // Step 4: relationship sets for R in relationships: participants = R.entity_sets // list of (entity_set, role) n = len(participants) if n == 2 and R.cardinality == MANY_TO_MANY: A, B = participants schema[R.name] = Table(A.key + B.key + R.attributes, primary_key = A.key + B.key, foreign_keys = {A.key -> A.name, B.key -> B.name}) else if n == 2 and R.cardinality in {ONE_TO_MANY, MANY_TO_ONE}: one_side, many_side = classify_by_cardinality(R) // fold R into the "many" side's table add_columns(schema[many_side.name], one_side.key + R.attributes) add_foreign_key(schema[many_side.name], one_side.key -> one_side.name) if R.participation[many_side] == TOTAL: mark_not_null(schema[many_side.name], one_side.key) else if n == 2 and R.cardinality == ONE_TO_ONE: preferred = pick_side_with_total_participation(R) or participants[0] other = the_other_side(preferred) add_columns(schema[preferred.name], other.key + R.attributes) add_foreign_key(schema[preferred.name], other.key -> other.name, unique = true) else: // n-ary, n >= 3, or a binary relationship we choose to keep explicit all_keys = union of entity.key for (entity, role) in participants schema[R.name] = Table(all_keys + R.attributes, primary_key = all_keys, foreign_keys = {entity.key -> entity.name for (entity, role) in participants}) return schema ``` The order matters only weakly: entities must be mapped before relationships that reference them (so their keys are known), and owners must be mapped before their weak entities. A topological sort over the "owner-of" and "participates-in" edges guarantees a valid processing order; since ER diagrams are finite and (in well-formed diagrams) acyclic in identifying dependencies, this order always exists.

Time and space complexity of the mapping itself. Let the ER diagram have `e` entity sets, `r` relationship sets, and a total of `p` attributes (including multivalued and composite ones). Rule 1 processes each entity set once, examining its attribute list, giving `O(p)` total work across all entities (each attribute touched a constant number of times). Rules 3, 4, and 9 similarly touch each multivalued attribute, weak entity, and specialization edge once. Rules 5–8 process each relationship set once, doing `O(k)` work where `k` is the number of participating entity sets in that relationship (2 for binary, more for n-ary); summed over all relationships this is bounded by the total number of (relationship, participant) edges in the diagram, call it `q`. The overall algorithm therefore runs in ``` O(p + q) ``` time — linear in the size of the diagram — and uses `O(p + q)` space to store the resulting table definitions, foreign keys, and constraints. This is optimal: any correct translation must at minimum read every attribute and every relationship-participant edge once, so `Ω(p + q)` is a lower bound, and the algorithm matches it.

Correctness argument. "Correctness" here means: the relational schema can represent exactly the set of database states the ER diagram permits, and no others — i.e., every key constraint, participation constraint, and structural constraint (existence dependency of weak entities, disjointness of specializations) expressed in the ER diagram has a corresponding, enforced constraint in the relational schema. The argument proceeds construct by construct, each an invariant preserved by its rule: Entity identity is preserved (Rule 1). Since `K` was declared a key in the ER model — no two entities in `E` agree on all of `K` — declaring `PRIMARY KEY(K)` in the table enforces exactly that uniqueness constraint at the database level, and nothing more or less. Multivalued sets are preserved without loss (Rule 3). A single row `(k, m)` per (entity, value) pair means the set of `m`-values for entity `k` is recoverable exactly as `{ m : (k, m) ∈ EM }`. No 1NF violation is possible because each column now holds a single atomic value. This is precisely the motivation that Normalization Motivation and Anomalies revisits later: repeating groups are exactly what Rule 3 eliminates by construction. Weak entity existence-dependency is preserved (Rule 4). Because `K_O` is a foreign key with `ON DELETE CASCADE`, no `W`-row can exist referencing a nonexistent owner (referential integrity), and deleting the owner removes its dependents automatically — precisely modeling "a weak entity cannot outlive its owner." The partial key `d` combined with `K_O` forming the primary key exactly captures "distinguishable only relative to an owner": two `W`-rows can share `d` as long as they have different owners, but not the same owner. Many-to-many cardinality is preserved, and could not be captured otherwise (Rule 5). Suppose, for contradiction, we tried to fold an M:N relationship into `A`'s table by adding a `K_B` column. Since a `B`-column can hold only one value, this would restrict `A`-entities to at most one partner — contradicting the "many" side of M:N. Hence a separate junction table is necessary, not just conventional; `PRIMARY KEY (K_A, K_B)` correctly permits any number of pairs while forbidding an exact duplicate pair. Functional dependency correctly encoded for many-to-one (Rule 6). If each `B` relates to at most one `A`, then functionally `K_B → K_A` (the ER cardinality constraint is a functional dependency). Storing `K_A` as an ordinary column in `B`'s table, one value per row, is exactly the tabular representation of that functional dependency — no information is lost, and no table is wasted, since a separate relationship table would only ever have one `A`-partner per `B`-row anyway (making the extra join redundant). Total participation correctly forces `NOT NULL` (Rule 6, 7). If participation is total, every `B`-entity must appear in some `R`-tuple, i.e., the `K_A` column can never be legitimately absent, so `NOT NULL` is exactly the right constraint; conversely, partial participation genuinely permits a `B` with no partner, which SQL models as `NULL` in that column. Declaring `NOT NULL` where participation is partial would forbid valid states, and omitting it where participation is total would allow invalid ones — so the mapping is tight in both directions. Specialization strategies trade off completeness against redundancy (Rule 9). Strategy A enforces disjointness naturally (an entity is a row in at most one subclass table) but requires a join to reconstruct a full subclass entity's attributes. Strategy B avoids joins but cannot, by itself, enforce disjointness or completeness constraints without an additional `CHECK` constraint on the discriminator column — a real, honestly-stated tradeoff rather than a defect hidden by the mapping.

Tradeoffs worth stating plainly. The mapping is not unique for M:1 and 1:1 cases (which side absorbs the foreign key is a design choice, ideally driven by which side has total participation, to avoid nullable foreign keys). It is also not "lossless" in a naive sense for 1:1 relationships if participation is partial on both sides — the chosen side's foreign-key column will contain `NULL`s, which is correct but requires care in queries (`OUTER JOIN` rather than `INNER JOIN` to see all entities). Finally, choosing to keep a relationship set as its own table even when Rule 6 would allow folding it in (e.g., to store relationship attributes with independent temporal history) is a legitimate, common deviation — the algorithm gives the default, not a legal mandate.

Consider this ER fragment for a company database:

• Strong entity set `Employee(ssn, name, {phone})` — `phone` is multivalued; key is `ssn`.
• Strong entity set `Department(dno, dname)` — key is `dno`.
• Weak entity set `Dependent(dname_partial, birthdate)`, identified by `Employee` via relationship `DependentOf`; partial key `dname_partial`.
• Relationship set `WorksIn` between `Employee` and `Department`, many-to-one from `Employee` to `Department` (each employee works in exactly one department — total participation on the `Employee` side), with attribute `since`.
• Relationship set `Manages` between `Employee` and `Department`, one-to-one (a department has exactly one manager — total participation on the `Department` side; not every employee manages a department — partial on the `Employee` side), with attribute `start_date`.

Trace the algorithm:

Final schema, rendered as SQL: ```sql CREATE TABLE Employee ( ssn CHAR(9) PRIMARY KEY, name VARCHAR(50) NOT NULL, dno INT NOT NULL, since DATE, FOREIGN KEY (dno) REFERENCES Department(dno) ); CREATE TABLE Employee_phone ( ssn CHAR(9), phone VARCHAR(15), PRIMARY KEY (ssn, phone), FOREIGN KEY (ssn) REFERENCES Employee(ssn) ON DELETE CASCADE ); CREATE TABLE Department ( dno INT PRIMARY KEY, dname VARCHAR(50) NOT NULL, manager_ssn CHAR(9) NOT NULL UNIQUE, start_date DATE, FOREIGN KEY (manager_ssn) REFERENCES Employee(ssn) ); CREATE TABLE Dependent ( ssn CHAR(9), dname_partial VARCHAR(50), birthdate DATE, PRIMARY KEY (ssn, dname_partial), FOREIGN KEY (ssn) REFERENCES Employee(ssn) ON DELETE CASCADE ); ``` Notice the subtlety: `Employee.dno` references `Department.dno`, and `Department.manager_ssn` references `Employee.ssn` — a mutual foreign-key cycle between the two tables. This is legal in SQL (both can be `NOT NULL` since neither table is empty in a valid database instance, and the DBMS defers constraint checking within a transaction), but it means the two `CREATE TABLE` statements cannot both be issued with their foreign keys active on first creation — one foreign key must be added afterward via `ALTER TABLE`, or both created with `DEFERRABLE INITIALLY DEFERRED` constraints. This kind of cycle is a direct, honest consequence of a 1:1 relationship between two entity sets that both have other relationships to each other; the mapping algorithm exposes it rather than hiding it.

Every relational database design workflow — from a whiteboard ER diagram in a systems-design interview to enterprise data-modeling tools like ERwin, Oracle SQL Developer Data Modeler, or open-source tools like dbdiagram.io — implements some variant of this mapping, often semi-automatically generating `CREATE TABLE` statements from a drawn diagram. Object-relational mapping (ORM) frameworks such as Hibernate, Django's ORM, and Prisma effectively perform a version of this same translation at a different altitude: they map object-oriented class relationships (one-to-many associations, many-to-many associations) into relational foreign keys and junction tables using exactly the cardinality-based rules described here. Database administrators reviewing a schema migration script for a new feature — say, adding a "favorite courses" list for students — are implicitly checking whether the migration correctly applied Rule 3 (a junction table) rather than an anti-pattern like a comma-separated column. Data warehouse design, while it uses dimensional modeling rather than pure ER modeling, still relies on the same foreign-key-folding logic when building fact and dimension tables. Understanding this mapping deeply is also the natural on-ramp to recognizing why some schemas — even ones produced by a mechanically correct mapping — can still suffer from update, insertion, and deletion anomalies, which is precisely the motivating question behind Normalization Motivation and Anomalies.

Ask the tutor: How would this mapping change if the university's `Takes` relationship also needed to record a history of grade changes over time, not just the current grade?