ER Model & Relational Model

Database design begins with a description of the world and ends with a set of tables, and the two are not the same kind of thing.

The organising fact is that the ER model can express constraints the relational model cannot. An ER diagram says every loan must have a customer, that a dependant cannot exist without an employee, that a manager manages exactly one department. A relational schema knows only tables, columns, keys and foreign keys.

Design is therefore about which constraints survive the translation and which must be enforced somewhere else, by an assertion, a trigger, or application code.

The second organising fact is that the number of tables is decided by the relationship's cardinality, not by the number of boxes in the diagram. A many-to-many relationship needs its own table; a one-to-many does not.

The third is that a key is a statement about all possible instances, not about the data currently present. A column that happens to be unique today is not a key unless the world guarantees it always will be.

1. Entities and Attributes

An entity is a thing distinguishable from other things; an entity set is a collection of entities of the same type, drawn as a rectangle.

Attributes are properties of entities, drawn as ellipses, and five distinctions matter.

Simple attributes are atomic; composite attributes decompose, as an address decomposes into street, city and postal code.

Single-valued attributes hold one value; multi-valued attributes hold several, as a person may have several phone numbers, drawn with a double ellipse.

Derived attributes are computed from others, as age is computed from date of birth, drawn with a dashed ellipse. They are stored nowhere.

A key attribute uniquely identifies an entity and is underlined.

A null value means one of three quite different things: the value is unknown, the value does not exist, or the value is not applicable. The relational model does not distinguish them, which is a well-known weakness.

2. Relationships, Cardinality and Participation

A relationship associates two or more entities, drawn as a diamond, and its degree is the number of participating entity sets.

The cardinality ratio bounds how many entities of one set may relate to one entity of another. Four cases exist: one-to-one, one-to-many, many-to-one and many-to-many.

Participation says whether every entity must take part. Total participation, drawn with a double line, requires every entity of the set to appear in at least one relationship instance. Partial participation does not.

These two are independent and are frequently confused. Cardinality limits how many; participation requires at least one.

Relationships may have their own attributes. A works-on relationship between employee and project carries hours, which belongs to neither entity alone.

A recursive relationship relates an entity set to itself, and then each side needs a role name, as an employee supervises other employees.

Ternary Relationships

A relationship of degree three relates three entity sets at once, and it is not generally replaceable by three binary relationships.

Consider a supplies relationship among Supplier, Part and Project, recording that a particular supplier supplies a particular part to a particular project.

Three binary relationships would record that a supplier supplies a part, that a supplier serves a project, and that a project uses a part. All three can be true without the ternary fact holding, because the supplier might supply that part only to a different project.

Information is lost in the decomposition, which is why the ternary diamond is kept.

The cardinality notation also changes meaning. Writing "one" on the Project side of a ternary relationship means that a given supplier and part combination relates to at most one project, not that a project relates to at most one of anything.

A ternary relationship always maps to its own table, holding all three primary keys, with the combination determined by the cardinality constraints as the key.

3. Weak Entity Sets

A weak entity set has no key of its own and depends on another entity for identification, drawn with a double rectangle.

The identifying or owner entity set supplies the missing identification through an identifying relationship, drawn with a double diamond.

The discriminator, or partial key, distinguishes weak entities belonging to the same owner and is underlined with a dashed line.

A weak entity always has total participation in its identifying relationship, because it cannot exist without an owner. That is what weak means.

The primary key of a weak entity set is the owner's primary key together with the discriminator.

The standard example is a dependant identified by an employee's number plus the dependant's name, since two employees may each have a dependant called Rahul.

4. Extended Features

Specialisation forms subgroups within an entity set, moving top-down from a general entity to more specific ones. Generalisation is the same relationship viewed bottom-up.

Two constraints apply to each such hierarchy.

Disjoint versus overlapping says whether an entity may belong to more than one subclass.

Total versus partial says whether every superclass entity must belong to some subclass.

Attribute inheritance flows downward: a subclass has all the superclass attributes plus its own, and participates in all the superclass relationships.

Aggregation treats a whole relationship as a single higher-level entity, so that another relationship can relate to it. It is needed when a relationship must itself participate in a relationship, which the basic model forbids.

The standard example has an employee working on a project at a branch, and a manager evaluating that whole assignment. The evaluation relates a manager to a works-on instance, not to any single entity, so works-on is aggregated into a box and the evaluation diamond attaches to that box.

A category, or union type, is the reverse of specialisation. It is a subclass whose members come from any of several superclasses, as an account owner may be either a person or a company. Its members inherit only from whichever superclass each belongs to, which is why it is drawn with a circle marked with a set union symbol.

5. The Relational Model

A relation is a set of tuples over a fixed set of attributes, each attribute drawn from a domain.

Being a set has two consequences that examiners test. There are no duplicate tuples, and there is no order among tuples or, formally, among attributes.

Actual SQL tables are multisets, not sets, permitting duplicates unless a key forbids them, which is one of the places practice departs from theory.

A schema is the description and an instance is the contents. The schema names the attributes and their domains and changes rarely; the instance is the set of tuples present at a moment and changes constantly.

Degree, or arity, is the number of attributes, and cardinality here means the number of tuples, which is an unfortunate clash with the ER sense of the word.

The key definitions form a hierarchy.

A superkey is any set of attributes that uniquely identifies a tuple.

A candidate key is a minimal superkey, meaning no proper subset of it is a superkey.

The primary key is the candidate key chosen by the designer, and the others become alternate keys.

A foreign key is a set of attributes referencing the primary key of some relation, possibly the same one.

Three integrity constraints are built into the model. Domain integrity requires each value to belong to its attribute's domain. Entity integrity forbids a null in any part of a primary key. Referential integrity requires every foreign key value either to be null or to match an existing primary key value.

Referential integrity also specifies what happens when the referenced row is deleted or updated. Cascade propagates the change to the referencing rows. Set null replaces the foreign key with a null, which is impossible if it is part of a primary key. Restrict, the default, refuses the operation outright.

A weak entity's foreign key must cascade, since the dependent row has no meaning without its owner and cannot be set to null.

6. Mapping ER to Relations

Seven rules cover the translation, and knowing them in order is worth several marks.

A strong entity set becomes a table with its attributes, and its key becomes the primary key.

A weak entity set becomes a table containing its own attributes plus the owner's primary key as a foreign key, with the combination of that foreign key and the discriminator as the primary key.

A many-to-many relationship becomes its own table, holding the primary keys of both participants plus any relationship attributes. The pair of foreign keys is the primary key.

A one-to-many relationship needs no table. The primary key of the one side is added to the table on the many side as a foreign key, along with any relationship attributes.

A one-to-one relationship can be merged into either side, and the better choice is the side with total participation, because that avoids nulls.

A multi-valued attribute becomes its own table, holding the owning entity's primary key plus the attribute, with both together as the primary key.

Specialisation has three options: one table per subclass plus one for the superclass; one table per subclass carrying inherited attributes, which works only for total and disjoint hierarchies; or one wide table with nulls and a type discriminator.

Composite attributes are simply flattened into their component columns, and derived attributes are not stored at all.

7. Worked Examples

Example 1. An ER diagram has entity sets Student, Course and Instructor. Student enrols in Course as many-to-many with an attribute grade. Instructor teaches Course as one-to-many. What is the minimum number of tables?

Apply the rules one at a time.

Student is a strong entity set, so it becomes a table. Course becomes a table. Instructor becomes a table. That is three.

The enrols relationship is many-to-many, so it needs its own table holding the student key, the course key and grade, with the pair of keys as the primary key. That is four.

The teaches relationship is one-to-many from Instructor to Course, so it needs no table. The instructor's key is added to Course as a foreign key.

The answer is four tables.

The general principle worth extracting: entity sets always cost a table, many-to-many relationships always cost a table, and one-to-many and one-to-one relationships never do.

Example 2. Classify each of the following and give the ER notation: a customer must have at least one account; an account belongs to exactly one branch; an employee may supervise many employees.

"A customer must have at least one account" is a participation constraint, not a cardinality one. It says total participation of Customer in the has relationship, drawn with a double line.

It does not limit how many accounts, so the cardinality on that side is many.

"An account belongs to exactly one branch" is both. The cardinality is many-to-one from Account to Branch, and the word "exactly" adds total participation of Account.

"An employee may supervise many employees" is a recursive relationship on Employee with two roles, supervisor and supervisee.

The word "may" signals partial participation, since some employees supervise nobody, and every employee except the top one has exactly one supervisor, making it one-to-many.

The lesson is that phrases like must and at least give participation, while exactly one and at most give cardinality.

Example 3. Map a weak entity set Dependant, with discriminator name and attribute relationship, owned by Employee with primary key empId, through an identifying relationship.

Dependant becomes a table.

It carries its own attributes, name and relationship, plus the owner's primary key empId as a foreign key.

The primary key is the pair (empId, name), because name alone cannot identify a dependant across the whole company but is enough within one employee's family.

The foreign key empId references Employee, and it must be declared with cascading delete, since a dependant cannot outlive its owner.

No separate table is created for the identifying relationship. A weak entity's identifying relationship is always many-to-one from the weak side, so it is absorbed exactly as any one-to-many relationship is.

Contrast with a strong entity holding the same data. If Dependant had its own dependantId, it would still be one table, but the primary key would be dependantId alone, and deleting an employee would leave orphans unless referential integrity forbade it.

Example 4. A relation $R$ has attributes $A,B,C,D,E$ and $AB$ is the only candidate key. How many superkeys does $R$ have?

A superkey is any set containing a candidate key, since adding attributes to a key preserves uniqueness.

Every superkey must therefore contain both $A$ and $B$.

The remaining attributes $C$, $D$ and $E$ may be included or not, freely.

That gives $2^3=8$ superkeys: $AB$, $ABC$, $ABD$, $ABE$, $ABCD$, $ABCE$, $ABDE$, $ABCDE$.

The general formula is $2^{n-k}$ where $n$ is the number of attributes and $k$ is the size of the single candidate key.

The formula breaks when there are several candidate keys, because sets containing both keys would be counted twice, and inclusion-exclusion is needed.

For instance, if $AB$ and $CD$ were both candidate keys on the same five attributes, the count is those containing $AB$, plus those containing $CD$, minus those containing both: $2^3+2^3-2^1=8+8-2=14$.

Example 5. A one-to-one relationship connects Employee and Department through manages, with Department having total participation and Employee partial. Where should the foreign key go, and why?

Either side is legal, since a one-to-one relationship can be merged into either table.

Put the foreign key on Department, the side with total participation.

The reason is nulls. Every department has a manager, so every row of Department will have a value in that column, and the column can be declared not null.

If instead the foreign key sat on Employee, then every employee who is not a manager would carry a null, and since most employees manage nothing, the column would be overwhelmingly null.

A unique constraint is required either way, because without it the schema would permit one employee to manage several departments, which the one-to-one cardinality forbids.

The general rule: merge a one-to-one relationship into the side with total participation, and always add a uniqueness constraint on the foreign key.

Example 6. Which ER constraints cannot be expressed in a pure relational schema, and how are they enforced?

Cardinality on the many side of a many-to-many relationship cannot be expressed. A schema cannot say a student enrols in at most six courses; the relationship table accepts any number of rows.

Total participation of the referenced side cannot be expressed by a foreign key. A foreign key on Account referencing Branch guarantees every account has a branch, but nothing guarantees every branch has an account.

The asymmetry is worth stating clearly. A foreign key enforces total participation on the side holding the key, and says nothing about the side referenced.

Disjointness in a specialisation cannot be expressed if the mapping uses one table per subclass, since nothing prevents the same key appearing in two of them.

Three enforcement mechanisms exist beyond the schema. An SQL assertion states a condition over the whole database and is checked on every change, though few systems implement it. A trigger runs procedural code on insert, update or delete and is what real systems use. Application-level checks are the weakest, since another program can bypass them.

The design consequence is that a schema alone is not a specification. The ER diagram remains the authoritative statement of what the world requires, and the schema is a partial implementation of it.

Summary

The ER model expresses constraints the relational model cannot, so design is about deciding which survive translation and which must be enforced by assertions, triggers or application code.

Attributes are simple or composite, single or multi-valued, and derived attributes are never stored. A null conflates unknown, non-existent and inapplicable.

Cardinality bounds how many; participation requires at least one. They are independent, and words like must and at least signal participation while exactly one signals cardinality.

A weak entity has no key of its own, always participates totally in its identifying relationship, and takes the owner's primary key plus its discriminator as its key.

Specialisation carries disjoint-or-overlapping and total-or-partial constraints, and attributes and relationships inherit downward. Aggregation exists so a relationship can itself participate in a relationship.

A relation is a set, so it has no duplicates and no order, though SQL tables are multisets. A superkey identifies uniquely, a candidate key is a minimal superkey, and the primary key is the chosen candidate. Domain, entity and referential integrity are built in.

In mapping, entity sets always cost a table and many-to-many relationships always cost a table, while one-to-many and one-to-one relationships never do. A multi-valued attribute costs a table. A one-to-one relationship should merge into the side with total participation, with a uniqueness constraint added.

With a single candidate key of size $k$ among $n$ attributes there are $2^{n-k}$ superkeys, and several candidate keys require inclusion-exclusion.

A foreign key enforces total participation only on the side holding it, which is why triggers exist.