ER Model and Normalization

7 pages · ~5 min✓ Reviewed

Start here. Next up: Indexing and Storage.

DBMSPage 1

ER Model Mental Model

1. Entities and Attributes

Entity = thing you store facts about (Student)
Entity set = all such things; rectangle in ER, rows in a table

Attribute	Example
Simple vs composite	`name` → first, last
Multivalued	`phones`
Derived	`age` from `dob`
Stored	`dob`

2. Weak Entities and Relationships

Weak entity: no key of its own
Depends on an owner via the identifying relationship
Key = owner key + partial key (Dependent of Employee)
Relationship links entities (Student enrolls in Course)
Relationships can carry attributes: grade on enrolls

3. ER to Tables

Entity→ table
Multivalued attr→ separate table
M:N relationship→ junction table

sql

CREATE TABLE enrolls (
  student_id INT REFERENCES student,
  course_id INT REFERENCES course,
  grade CHAR(1),
  PRIMARY KEY (student_id, course_id));

junction: both FKs, plus the relationship attribute

4. Interview Point

Why can't Dependent stand alone? No own key; needs Employee key + partial key
How is M:N stored? Junction table with both FKs; grade lives there

DBMSPage 2

Cardinality and Participation

1. Cardinality Ratios

Ratio	Maps to	Example
1:N	FK on the N side	`Order.customer_id`
M:N	Junction table	PK `(student_id, course_id)`
1:1	FK + `UNIQUE`	either side

Junction PK is usually the pair of FKs, so a pair cannot repeat

sql

CREATE TABLE enrolls (
  student_id INT REFERENCES student,
  course_id INT REFERENCES course,
  PRIMARY KEY (student_id, course_id)
);

2. Participation

Total (double line): every instance takes part, FK NOT NULL
Partial: taking part is optional, FK nullable
In 1:1, put the FK on the side with total participation

3. Common Mistakes

M:N stored as a comma-separated list column
FK placed on the 1 side of a 1:N

Remember

The FK goes on the many side; many-to-many always gets its own table.

DBMSPage 3

Keys: Super, Candidate, Primary, Foreign

1. The key ladder

Super key: any set that uniquely identifies a row
Supersets of a key also qualify: {id}, {id, name}
Candidate key: minimal super key; a table may have several
Prime attribute: part of some candidate key

Super keysall unique sets
Candidate keysminimal
Primary keyone chosen

2. Primary, alternate, foreign

	Primary	Alternate	Foreign
Is	chosen candidate	other candidates	refers to another table's key
Unique	yes	yes, UNIQUE	no, duplicates OK
NULL	never	per column	allowed
Per table	at most 1	many	many

ON DELETE CASCADE: child rows deleted too
SET NULL: child FK becomes NULL
RESTRICT: parent delete is blocked

3. Composite and surrogate

Composite key: 2+ attributes, e.g. (student_id, course_id)
Surrogate key: generated id, no business meaning

Remember

Every primary key is a candidate key, but not every super key is one.

DBMSPage 4

Functional Dependencies and Closure

1. Meaning of an FD

X → Y: equal X ⇒ equal Y in any two rows
A rule about the schema, not the current data

2. Armstrong's axioms and derived rules

Rule	Statement
Reflexivity	Y ⊆ X ⇒ X → Y
Augmentation	X → Y ⇒ XZ → YZ
Transitivity	X → Y, Y → Z ⇒ X → Z
Union	X→Y, X→Z ⇒ X→YZ
Decomposition	X→YZ ⇒ X→Y, X→Z

3. Closure and keys

StartX⁺ = X
Growadd RHS of FDs whose LHS ⊆ set
Repeatuntil nothing changes
Super keyX⁺ = all attributes

Attributes never on any RHS are in every key
Test them by closure, then add attributes only as needed

4. Partial vs transitive

Kind	Shape
Partial	non-prime depends on part of a composite key
Transitive	non-prime → non-prime via X → Y → Z

Remember

FDs come from the meaning of the schema, not from sample rows.

DBMSPage 5

Normal Forms and Anomalies

1. Anomalies in One Wide Table

Insert: can't add a course without a student
Update: change many rows, miss some
Delete: removing the last student loses the course

2. The Normal Forms

Form	Rule
1NF	Atomic cells, row identified by a key
2NF	1NF + no partial dependency
3NF	2NF + no transitive; X super key or Y prime
BCNF	Every nontrivial X→Y: X is a super key

2NF only matters for composite keys
BCNF is stricter; can lose dependency preservation

3. Decompose

Offending FDdept_id→dept_name
New table(X, Y)
Keep Xin original
Checklossless join

Trade-off

Too much normalizing costs joins; denormalize on purpose for reads.

4. Interview Point

Why can BCNF lose dependency preservation? Splitting may separate an FD's attributes across tables
2NF vs 3NF? Partial versus transitive dependency

DBMSPage 6

Normalization Cheat Sheet

1. Keys and Cardinality

Super key ⊇ candidate key ⊇ primary key
FK points at a key; may be NULL and duplicated

Cardinality	Tables
1:N	FK on the N side
M:N	Junction table, PK (fk1, fk2)
1:1	FK plus UNIQUE

M:N stored as a comma-separated list column
FK placed on the 1 side of a 1:N

2. Closure and Normal Form Tests

X is a super key iff X⁺ contains every attribute
X⁺: add the RHS of any FD whose LHS is inside the set

Form	Test
1NF	Values are atomic
2NF	No partial dependency
3NF	No transitive dependency
BCNF	Every determinant is a super key

Memory line

Every non-key attribute depends on the key (1NF), the whole key (2NF), and nothing but the key (3NF/BCNF).

DBMSPage 7

Check yourself

R(A,B,C) has A→B and B→C. Find A⁺. Is R in 3NF?

A⁺ = {A,B,C}, so A is the key
B→C: B is not a super key and C is non-prime
Transitive dependency, so not 3NF

Enroll(student_id, course_id, course_name) has key (student_id, course_id) and course_id→course_name. Highest normal form?

1NF only
course_name depends on part of the key (partial dependency)
Fix: move (course_id, course_name) to a Course table

R(A,B,C) has AB→C and C→B. In 3NF? In BCNF?

Keys are AB and AC, so A, B, C are all prime
3NF: yes, B in C→B is prime
BCNF: no, C is not a super key

Student–Course is M:N. Why is a course_id column in Student wrong?

A student row can hold only one course
Use a junction table with PK (student_id, course_id)