ER Modeling, Keys, Functional Dependencies and Normalization

entity relationship model

An entity-relationship model describes entity types, attributes, identifiers, relationships.

entity and attribute

An entity is a distinguishable real-world object or concept; an attribute records one property of that entity.

relationship cardinality

Cardinality states how many instances of one entity may be associated with each instance of another entity.

candidate primary and foreign keys

Candidate keys uniquely identify rows, one candidate becomes the primary key and a foreign key references a key in another relation.

functional dependency

A functional dependency X → Y states that any two valid rows equal on determinant X must also be equal on Y.

normalization

Normalization decomposes relations according to dependencies to reduce update anomalies while aiming to preserve information and necessary constraints.

first second and third normal form

First normal form uses atomic fields, second removes partial dependency on a composite key and third removes transitive dependency of nonkey attributes on.

BCNF

A relation is in Boyce-Codd normal form when every nontrivial functional dependency has a determinant that is a superkey.

lossless decomposition

A decomposition is lossless when joining its projections under the stated dependencies reconstructs exactly the original relation without spurious rows.

dependency preservation

A decomposition preserves dependencies when the original functional dependencies can be enforced without joining decomposed tables.

A decomposition preserves dependencies when all original dependencies can be enforced by checking constraints within individual decomposed relations, without joining them.

Lossless join protects information, while dependency preservation protects practical enforceability. They are separate properties. A decomposition may be lossless but require an expensive join to verify an original rule.

3NF synthesis can provide both losslessness and dependency preservation. A BCNF decomposition is lossless but may sacrifice dependency preservation in some schemas.

Boyce-Codd Normal Form

A relation is in BCNF when, for every nontrivial functional dependency X → Y, X is a superkey.

BCNF is stricter than 3NF because it does not include the prime-attribute exception. Every determinant of a meaningful functional dependency must identify the whole tuple.

A relation can be in 3NF but not BCNF when a non-superkey determines a prime attribute. Such cases often involve overlapping candidate keys. BCNF removes more dependency-based redundancy, but a lossless BCNF decomposition may not preserve every dependency locally.

Second Normal Form

A relation is in 2NF when it is in 1NF and every non-prime attribute is fully functionally dependent on every candidate key. No non-prime attribute may depend on only a proper subset of a candidate key.

In ENROLLMENT with key (student_id, course_id):

student_id → student_name course_id → course_title (student_id, course_id) → grade

student_name and course_title are partial dependencies. Splitting STUDENT and COURSE removes them, while grade remains with the full enrollment key.

A relation whose candidate keys each contain one attribute cannot have a partial-key violation because such a key has no nonempty proper subset.

A Reliable Normalization Method

Begin with one relation and a complete set of business dependencies. Identify candidate keys through closure. Check 1NF structure, then partial dependencies for 2NF, transitive and formal dependency conditions for 3NF and all determinants for BCNF.

For each decomposition, prove lossless join and evaluate dependency preservation. Add primary, unique, foreign-key, not-null and check constraints that implement the resulting rules.

Normalization is a reasoning process about facts. The objective is not the largest possible number of tables; it is a schema in which each fact is stored with the key that determines it, updates preserve one consistent truth and joins reconstruct the required information correctly.

First Normal Form

A relation is in first normal form when each attribute value is atomic for the relational design and repeating groups are absent.

This table is problematic:

CUSTOMER(customer_id, name, phone1, phone2, phone3)

It imposes a fixed number of phones and repeats one logical attribute. A separate relation is clearer:

CUSTOMER(customer_id, name) CUSTOMER_PHONE(customer_id, phone_number, phone_type)

Atomicity depends on intended operations. A postal address may be stored as one value if never queried by components, though structured columns are needed when city or postal code has independent meaning.

Third Normal Form

A relation is in 3NF when it is in 2NF and does not store non-key facts through other non-key facts. Informally, non-key attributes should depend on keys, the whole keys and not on non-key intermediates.

Consider:

EMPLOYEE(employee_id, department_id, department_name)

with:

employee_id → department_id department_id → department_name

employee_id determines department_name transitively through department_id. Repeating department_name for every employee creates anomalies. Decompose into EMPLOYEE(employee_id, department_id) and DEPARTMENT(department_id, department_name).

Formally, for every nontrivial dependency X → A in 3NF, X must be a superkey or A must be prime.

Join Dependencies and 5NF

Fifth normal form addresses join dependencies that require decomposition into three or more projections. A relation satisfies 5NF when every nontrivial join dependency follows from candidate keys.

A classic Supplier-Part-Project relation may contain facts reconstructable from several pairwise relations under a specific business rule. Decomposition avoids storing redundant combinations, but incorrect assumptions can create combinations that were never valid.

5NF situations are less common in ordinary application schemas and require precise semantic evidence. Do not decompose merely because three foreign keys appear together; the ternary fact may be irreducible.

Finding Candidate Keys

A candidate key is a minimal attribute set whose closure contains every relation attribute.

A practical method is:

1. place attributes that never appear on any dependency's right side into every candidate-key starting set;
2. compute closure;
3. add combinations of remaining attributes until closure covers the relation;
4. remove any unnecessary attribute to verify minimality;
5. search for other minimal combinations.

Minimal means minimal by set inclusion, not the fewest characters or smallest stored number.

All candidate keys matter when evaluating 2NF and 3NF. Looking only at the chosen primary key can miss violations involving another candidate key.

BCNF Decomposition

If R violates BCNF through X → Y, decompose it into:

R1 = X ∪ Y R2 = R − (Y − X)

The decomposition is lossless because the intersection contains X, which determines R1. Continue until every resulting relation satisfies BCNF.

At each step, project dependencies onto the new relations and re-evaluate keys. Do not assume that keys and dependencies transfer unchanged.

Candidate and Primary Keys

A candidate key is a minimal superkey. No proper subset remains unique. A table can have several candidate keys, such as employee_id and an officially unique tax identifier.

One candidate key is designated the primary key. The others are alternate keys and should normally receive UNIQUE constraints. The primary key is a design choice; candidate status comes from business semantics.

Primary-key columns cannot be NULL. A composite primary key requires every component to be present.

From ER Model to Reliable Relations

Map strong entities to relations with constrained candidate keys. Place foreign keys on the many side of one-to-many relationships. Add uniqueness for one-to-one mappings. Turn many-to-many relationships into associative relations, including attributes of the relationship.

Do not stop after drawing boxes and lines. Verify that each table represents one kind of fact, keys express stable identity, optionality matches nullability and referential actions match lifecycle.

This logical foundation prepares the schema for dependency analysis and normalization. Correct keys and relationships are essential because later SQL constraints, joins and transactions can enforce only the model that the design actually expresses.

A 3NF but Not BCNF Pattern

Let R(Student, Course, Instructor) have rules:

(Student, Course) → Instructor Instructor → Course

Candidate keys include (Student, Course) and (Student, Instructor). Every attribute is prime. Instructor → Course satisfies 3NF because Course is prime, but it violates BCNF because Instructor is not a superkey.

Decomposing to INSTRUCTOR_COURSE(Instructor, Course) and STUDENT_INSTRUCTOR(Student, Instructor) removes the BCNF violation and is lossless under Instructor → Course. Whether all intended dependencies remain directly enforceable must be checked separately.

Prime Attributes

A prime attribute belongs to at least one candidate key. A non-prime attribute belongs to no candidate key.

Prime does not mean “part of the primary key.” If a relation has candidate keys {email} and {employee_id}, both attributes are prime even if employee_id is selected as primary.

This distinction matters in the formal 3NF condition, which permits a dependency with a non-superkey determinant when every dependent attribute is prime.

Lossless Join

A decomposition is lossless when natural joining the decomposed relations reconstructs exactly the original valid relation, without losing tuples or producing spurious combinations.

For a binary decomposition of R into R1 and R2, it is lossless under dependency set F when the common attributes functionally determine all of R1 or all of R2:

(R1 ∩ R2) → R1

or:

(R1 ∩ R2) → R2

If STUDENT and ENROLLMENT share student_id and student_id is a key of STUDENT, their join is lossless under the rule.

Joining tables merely because they share a similarly named non-key attribute can create spurious tuples.

Foreign Keys

A foreign key is a set of child columns whose non-NULL values must match a candidate key in the referenced parent table. It establishes referential integrity.

Foreign-key values commonly repeat because many child rows can refer to one parent. A foreign key is not automatically unique and need not be the child's primary key.

Types and meanings should align. Referencing a product identifier from a column labeled customer_id may be technically possible with matching types but conceptually wrong.

Functional Dependencies

A functional dependency X → Y states that in every valid instance of a relation, any two tuples equal on attribute set X must also be equal on attribute set Y. X is the determinant and Y is functionally dependent on X.

Examples:

student_id → student_name, date_of_birth course_id → course_title, credits (student_id, course_id) → grade

Dependencies express business rules, not accidental patterns in current data. Ten rows with different names do not prove name → student_id. Future people can share a name.

Composite Keys

A composite key contains more than one attribute. It is appropriate when identity naturally depends on a combination, such as (order_id, line_number).

Composite foreign keys must reference the complete candidate key with compatible column order and types. Using only one component does not identify a parent row.

Wide composite keys increase the size of referencing rows and indexes. A surrogate identifier can simplify references, but the original combination still needs a UNIQUE constraint if it represents business identity.

Mapping a Many-to-Many Relationship

A many-to-many relationship becomes an associative table:

STUDENT(student_id, ...) COURSE(course_id, ...) ENROLLMENT(student_id, course_id, term, grade)

ENROLLMENT contains foreign keys to both participants and stores attributes of the relationship. Its key must follow the business rule. If a student can repeat the same course in a later term, (student_id, course_id) is too restrictive; term or an offering identifier must participate.

An associative table is a full relation. It may have its own surrogate key, status, timestamps or relationships, but business uniqueness should still be constrained.

Decomposition

Decomposition replaces one relation schema with two or more smaller schemas. For example:

ENROLLMENT(student_id, student_name, course_id, course_title, grade)

can become:

STUDENT(student_id, student_name) COURSE(course_id, course_title) ENROLLMENT(student_id, course_id, grade)

The goal is not merely smaller tables. A useful decomposition should be lossless, should ideally preserve dependencies and should place each important fact where its determinant is a key.

NULL in Foreign Keys

If any permitted foreign-key representation is NULL, the relationship may be absent according to the DBMS rules and constraint definition. Use NOT NULL when every child must have a parent.

NULL should represent missing or inapplicable information, not a magic identifier. A special parent row such as “Unknown” has different semantics: it is an actual referenced row and can collect children deliberately.

Composite foreign keys require careful NULL rules. Prefer all components present for a relationship or all absent when optional, enforced with checks if needed.

Relationships and Degree

A relationship expresses an association among entity types. Employee works for Department is binary because it connects two entity types. A recursive relationship connects occurrences of one type, such as Employee supervises Employee.

A ternary relationship connects three types at once. Suppose a Supplier supplies a Part to a Project. Splitting this fact into unrelated binary relationships may lose which supplier supplied which part to which project.

Relationship attributes describe the association itself. Enrollment.grade belongs to the link between Student and Course offering; it is not a permanent property of either one alone.

Entity-Relationship Modeling

Entity-relationship modeling describes a domain before it is reduced to tables. It identifies the kinds of things the organization records, their properties and the rules connecting them.

An entity type is a category such as Student, Department or Course. An entity occurrence is one particular student or course. An entity must be distinguishable from other occurrences, usually through one or more identifying attributes.

ER modeling uses business concepts rather than interface screens or existing file layouts. A screen may combine several entities for convenience, while a sound model keeps their independently changing facts separate.

Mapping a One-to-One Relationship

A one-to-one relationship uses a foreign key plus uniqueness. Suppose each Person has at most one Passport and each Passport belongs to exactly one Person:

PASSPORT( passport_number PRIMARY KEY, person_id UNIQUE NOT NULL, ... )

The UNIQUE constraint prevents two passports from referencing the same person. The choice of which table receives the foreign key depends on optionality, lifecycle and access patterns. If two entities always share identity and lifecycle, merging them may be reasonable; if they are independently meaningful, separate tables preserve that distinction.

Trivial and Nontrivial Dependencies

A dependency X → Y is trivial when Y is a subset of X. For example:

(student_id, course_id) → student_id

It holds from the structure of attribute sets and reveals no additional business rule.

A nontrivial dependency has at least one right-side attribute not already in the determinant. Normal-form definitions focus on nontrivial dependencies because they reveal how distinct facts are determined.

Multivalued Dependencies and 4NF

A multivalued dependency X ↠ Y means that, for a fixed X, the set of Y values is independent of the remaining attributes.

Suppose an Instructor has independent Skills and Languages:

INSTRUCTOR_DETAIL(instructor, skill, language)

If every skill combines with every language, the table stores their cross-product. Decompose into INSTRUCTOR_SKILL and INSTRUCTOR_LANGUAGE.

A relation is in 4NF when every nontrivial multivalued dependency has a superkey determinant. Functional dependencies are special cases within this broader concern.

Attributes

An attribute describes an entity or relationship. Attributes can be:

• simple, such as salary;
• composite, such as an address divided into street, city and postal code;
• single-valued, such as date of birth;
• multivalued, such as several phone numbers;
• stored, such as quantity and unit price;
• derived, such as an order total calculated from lines.

Relational implementation normally decomposes composite attributes into useful columns and represents multivalued attributes in a related table. Repeating columns such as phone1, phone2 and phone3 impose an arbitrary limit and complicate searching.

Derived data may be calculated when requested or stored for performance and historical requirements. Stored derivations need controls that keep them synchronized with their source facts.

Mapping a One-to-Many Relationship

A one-to-many relationship is normally implemented by placing the primary key of the one side as a foreign key in the many-side table:

DEPARTMENT(department_id, department_name) EMPLOYEE(employee_id, employee_name, department_id)

EMPLOYEE.department_id references DEPARTMENT.department_id. Several employee rows may repeat the same department identifier, which correctly represents many employees belonging to one department.

If participation is mandatory, the foreign key should also be NOT NULL. A foreign key alone may permit NULL and therefore an employee with no referenced department.

Attribute Closure

The closure X+ under a dependency set is the set of attributes functionally determined by X. Begin with X, repeatedly add the right side of every dependency whose left side is already contained and stop when nothing changes.

For R(A, B, C, D) with:

A → B B → C AC → D

Start A+ = {A}. A → B adds B. B → C adds C. AC → D then adds D. Therefore A+ contains all attributes, so A is a superkey.

Closure also tests whether a dependency is implied: X → Y follows when Y is contained in X+.

Minimal Covers

A minimal or canonical cover is an equivalent dependency set with a simple form:

1. each dependency has one attribute on the right;
2. no left-side attribute is extraneous;
3. no dependency is redundant.

To test whether an attribute in X is extraneous in X → A, compute closure after removing that attribute under the appropriate dependency set. To test whether a dependency is redundant, remove it and see whether its right side remains in the determinant's closure.

Minimal covers are useful in 3NF synthesis because they isolate essential rules.

Strong and Weak Entities

A strong entity has an identifier independent of another entity. A weak entity depends on an owner for identification and existence.

An OrderLine might be identified by (order_id, line_number). line_number is unique only within one Order, so the Order's key participates in the weak entity's key.

Not every child with a foreign key is conceptually weak. A registered Employee has its own identity even when assigned to a Department. Dependence should reflect the domain, not merely the presence of a relationship.

Natural and Surrogate Keys

A natural key has meaning in the domain, such as an ISBN edition identifier or an assigned employee number. A surrogate key is introduced primarily for database identity, such as an auto-increment integer.

A good natural key is unique, stable, compact and always known. Many apparent natural keys change, contain sensitive data or are assigned by another system whose rules are outside local control.

Surrogate keys offer compact stable references, but they do not eliminate business uniqueness. If duplicate email addresses are forbidden, UNIQUE(email) remains necessary even when customer_id is the primary key.

3NF Synthesis

A common dependency-preserving 3NF construction is:

1. find a minimal cover;
2. create a relation containing X ∪ {A} for each dependency X → A, combining compatible determinants;
3. remove relation schemas contained entirely in another;
4. if no created relation contains a candidate key of the original relation, add one relation containing a candidate key.

The result is in 3NF, preserves dependencies and has a lossless join under the standard construction.

Design still requires meaningful names, correct types and constraints; an algorithm does not replace domain understanding.

Cardinality

Cardinality states the maximum number of occurrences that may participate:

• one-to-one: each side associates with at most one occurrence on the other;
• one-to-many: one parent associates with many children, while each child associates with one parent;
• many-to-many: occurrences on both sides may associate with many on the other side.

Cardinality must come from business rules. A Department may employ many Employees, but each Employee may currently belong to one Department. A later requirement for simultaneous assignments would change the model to many-to-many.

Reading an ER Diagram

For each entity, identify its key and attributes. For every relationship, read minimum and maximum participation in both directions. Ask whether the relationship has its own attributes and whether its identity depends on the participating entities.

Then test the diagram with concrete scenarios: zero children, several children, repeated events over time, changed identifiers, deleted parents and optional information. Many modeling errors appear only when time and lifecycle are considered.

An ER diagram is useful only when its symbols are backed by written business rules. “Customer places Order” is incomplete until optionality, maximums, identity and deletion behavior are known.

Superkeys

A superkey is any attribute set that uniquely identifies a tuple. If student_id is unique, then {student_id} is a superkey, but so are {student_id, name} and {student_id, date_of_birth}.

The extra attributes in larger superkeys are unnecessary for identification. Superkeys describe uniqueness, while candidate keys add the requirement of minimality.

Uniqueness must hold for all valid future states, not merely the current sample. A column whose values happen to differ today is not necessarily a key.

Armstrong's Axioms

Functional dependencies can imply other dependencies. Armstrong's axioms provide sound and complete inference rules:

• reflexivity: if Y is a subset of X, then X → Y;
• augmentation: if X → Y, then XZ → YZ;
• transitivity: if X → Y and Y → Z, then X → Z.

Useful derived rules include:

• union: if X → Y and X → Z, then X → YZ;
• decomposition: if X → YZ, then X → Y and X → Z;
• pseudotransitivity: if X → Y and WY → Z, then WX → Z.

These rules support key discovery and decomposition analysis.

Entity, Referential and Domain Integrity

Entity integrity requires every relation to have distinguishable rows and primary-key components to be non-NULL.

Referential integrity prevents child references to nonexistent parent keys. It preserves relationship validity during inserts, updates and deletes.

Domain integrity restricts individual values through types, nullability, defaults and checks. Business rules spanning several rows may require more advanced constraints, controlled transactions or carefully designed triggers.

Why Relations Need Careful Structure

A table can be syntactically valid and still represent facts poorly. Consider one table containing:

ENROLLMENT( student_id, student_name, course_id, course_title, instructor_id, instructor_name, grade )

The likely key is a combination such as (student_id, course_id). Student names repeat for every course and course information repeats for every student. Repetition consumes space, but the larger concern is that the same fact is stored in several places and can become inconsistent.

Normalization analyzes dependencies among attributes and decomposes relations so that each fact has an appropriate home.

Participation and Optionality

Participation states whether a relationship is mandatory. Minimum cardinality zero means optional participation; minimum one means mandatory participation.

For example, a new Department may temporarily have no employees, giving Department participation a minimum of zero. If every Employee must belong to a Department, Employee participation has a minimum of one.

Maximum cardinality and optionality answer different questions. “Zero or many” combines optional participation with a many maximum. “Exactly one” combines mandatory participation with a one maximum.

Referential Actions

When a referenced parent key changes or a parent row is deleted, the foreign key defines an action:

• RESTRICT or NO ACTION prevents the change when matching children exist, subject to product timing;
• CASCADE propagates the update or deletion;
• SET NULL removes the reference while preserving nullable child rows;
• SET DEFAULT uses a declared default where supported.

Choose the action from lifecycle meaning. Deleting an Order can reasonably cascade to its OrderLines because lines have no independent purpose. Deleting a Department should rarely delete all Employees; reassignment or restriction is safer.

Cascades can cross several relationships, so their full effect must be understood before use.

Integrity Independence and Non-Subversion

Integrity independence means rules should be represented in the database language and catalog rather than existing only in application source code. This allows every access path to receive the same enforcement.

The non-subversion principle says that a lower-level interface must not bypass relational integrity and security rules. A system is not meaningfully relational if constraints apply through SQL but can be silently ignored through routine record-level access.

Administrative recovery facilities may operate below normal interfaces, but they require controlled privileges and procedures.

Relational Principles

The relational model presents information through values in relations rather than navigation through physical addresses. Users express the required result declaratively and the DBMS chooses access paths.

Relations should be addressable through keys, missing information should receive systematic treatment and integrity rules should be expressed in the relational language rather than hidden in file-level procedures.

Physical organization remains necessary internally, but it should not become part of the logical meaning that every application must follow.

Information and Guaranteed Access

The information principle says that facts should be represented logically as values in relations. Application-visible pointer chains should not be required to interpret the database.

Guaranteed access means a scalar value can be identified conceptually by relation name, a key identifying its row and a column name. This relies on proper keys; physical row position is not durable identity.

Queries may use indexes internally, but an index address is an access mechanism, not the logical identity of a business fact.

Deletion Anomalies

A deletion anomaly occurs when deleting one fact unintentionally removes the only stored copy of another fact. If the last enrollment in a course is deleted from the combined table, the database may also lose the course title and instructor information.

Separate relations let deletion follow meaning: deleting an ENROLLMENT removes that association, while the COURSE remains until an explicit course deletion is performed.

Insertion Anomalies

An insertion anomaly occurs when one fact cannot be recorded without another unrelated fact. In the combined table, a new course may not be stored until at least one student enrolls because student_id participates in the key.

Using dummy student values hides the design error and pollutes the data. A separate COURSE relation allows a course to exist independently of enrollment, matching its real lifecycle.

Denormalization

Denormalization deliberately stores redundant or derived data for a measured performance or availability reason. Examples include cached totals, reporting snapshots or prejoined analytical structures.

It reintroduces consistency work. The design must define:

• which copy is authoritative;
• when and how derived copies update;
• what happens on partial failure;
• how inconsistencies are detected and repaired;
• which workload measurement justifies the tradeoff.

Denormalization is not a substitute for indexes, query analysis or correct relational design.

Update Anomalies

An update anomaly occurs when a repeated fact must be changed in several rows. If course_title appears in every enrollment for a course, renaming the course requires updating all matching rows. A missed row leaves contradictory titles for the same course.

The anomaly is structural. A transaction can make one multirow update atomic, but it does not explain why the fact was duplicated or stop a later program from updating only one copy.

Separating COURSE(course_id, course_title) stores the title once and lets enrollments reference it.

Set-Level Operations and Data Independence

A relational language operates on sets or multisets of rows. One UPDATE can modify every row matching a predicate without an application navigating record by record.

Physical data independence permits indexes and storage organization to change without changing relational queries. Logical data independence seeks to preserve external views when the conceptual schema evolves.

These properties reduce coupling between applications and storage, allowing database administrators to tune access without redefining what the facts mean.

Codd's Relational Rules

Codd described a foundation rule and twelve rules for a fully relational system. They include:

• representing information as values in tables;
• guaranteed logical access using table, key and column;
• systematic treatment of NULL;
• an online relational catalog;
• a comprehensive relational data language;
• support for theoretically updatable views;
• set-level insert, update and delete;
• physical and logical data independence;
• independence of integrity constraints and distribution;
• protection against bypassing relational rules through lower-level access.

Commercial systems meet these ideals to different degrees. The rules are best understood as principles for relational completeness rather than a product checklist reduced to marketing labels.