Chapter 4

Database Constraints and Normalization

6 hours9 marks24 past questionsBack to chapters Open filtered PYQs Previous: Ch 3 Next: Ch 5

Chapter Notes

Block-based notes with markdown, diagrams, code, and math.

Chapter 4 — Database Constraints and Normalization

4.1 Integrity Constraints

Constraint	Scope	Purpose	SQL Example
NOT NULL	Column	Prevent missing values	`name VARCHAR(100) NOT NULL`
UNIQUE	Column / group	No duplicate values	`UNIQUE(email)`
PRIMARY KEY	Column / group	Unique + not null identifier	`sid INT PRIMARY KEY`
FOREIGN KEY	Column	Referential integrity	`REFERENCES Student(sid)`
CHECK	Column / row	Custom business rule	`CHECK (gpa BETWEEN 0 AND 4)`
DEFAULT	Column	Value when none supplied	`dept VARCHAR(50) DEFAULT 'CS'`
ASSERTION	Table / DB	Multi-table constraint	`CREATE ASSERTION ...`

CREATE TABLE Student (
  sid    INT          PRIMARY KEY,
  name   VARCHAR(100) NOT NULL,
  email  VARCHAR(200) UNIQUE,
  dept   VARCHAR(50)  DEFAULT 'Undeclared',
  gpa    DECIMAL(3,2) CHECK (gpa >= 0 AND gpa <= 4.0),
  mentor INT          REFERENCES Student(sid) ON DELETE SET NULL -- self-ref FK
);

-- Table-level constraint (composite)
CREATE TABLE Enrollment (
  sid   INT REFERENCES Student(sid),
  cid   INT REFERENCES Course(cid),
  grade CHAR(2),
  CONSTRAINT pk_enroll PRIMARY KEY (sid, cid),
  CONSTRAINT valid_grade CHECK (grade IN ('A','B','C','D','F','IP','W'))
);

-- Assertion (SQL standard, limited DBMS support)
CREATE ASSERTION max_salary
CHECK (NOT EXISTS (
  SELECT 1 FROM Employee WHERE salary > 1000000
));

4.2 Functional Dependencies (FD)

A functional dependency A → B means: for any two tuples with the same A value, they must have the same B value. "A functionally determines B."

Armstrong's Axioms (sound and complete)

Axiom	Rule	Example
Reflexivity	If B ⊆ A, then A → B	{sid, name} → {name}
Augmentation	If A → B, then AC → BC	sid → name ⟹ {sid,dept} → {name,dept}
Transitivity	If A → B and B → C, then A → C	sid → dept, dept → dean ⟹ sid → dean

Derived rules (from the axioms):

Union: A → B, A → C ⟹ A → BC
Decomposition: A → BC ⟹ A → B and A → C
Pseudotransitivity: A → B, CB → D ⟹ CA → D

Attribute Closure Algorithm

To find A⁺ (closure of attribute set A under FD set F):

Algorithm: AttributeClosure(A, F)
  result ← A
  repeat
    for each FD (X → Y) in F:
      if X ⊆ result:
        result ← result ∪ Y
  until result does not change
  return result

Example:
  Relation: R(A, B, C, D, E)
  FDs: F = { A→BC, B→D, CD→E }

  Closure of {A}:
    Start: {A}
    A→BC:  {A, B, C}
    B→D:   {A, B, C, D}
    CD→E:  {A, B, C, D, E}  ← all attributes!
  So {A} is a superkey (and candidate key since no proper subset of {A} gives full closure).

Canonical Cover (Minimal Cover)

A canonical cover F_c has no extraneous attributes and no redundant FDs. Steps:

Use Union rule to combine FDs with same LHS.
Remove extraneous attributes from each LHS and RHS.
Remove FDs that are derivable from the rest.

4.3 Normalization

Goal: eliminate update, insert, and delete anomalies by decomposing relations.

1NF — First Normal Form

Condition: every attribute is atomic (no repeating groups, no sets, no arrays).

Fix: move multivalued attributes into separate rows or a separate relation.

2NF — Second Normal Form

Condition: in 1NF AND no non-prime attribute is partially dependent on any candidate key. (A partial dependency: non-key attribute depends on part of a composite key.)

Fix: move the partially dependent attribute + the partial key into a new relation.

Example violation:
OrderItem(order_id, product_id, product_name, quantity)
product_name depends only on product_id (part of composite PK).

Fix: split into OrderItem(order_id, product_id, quantity) and Product(product_id, product_name).

3NF — Third Normal Form

Condition: in 2NF AND no non-prime attribute transitively depends on any candidate key.

Fix: remove transitive dependency chain into a new relation.

Example violation:
Student(sid, dept, dept_head)
sid → dept → dept_head (transitive).

Fix: Student(sid, dept) and Department(dept, dept_head).

BCNF — Boyce-Codd Normal Form

Condition: for every non-trivial FD X → Y, X must be a superkey. Stricter than 3NF — BCNF removes anomalies 3NF can miss.

Trade-off: BCNF decomposition may not preserve all FDs; 3NF decomposition always does.

	3NF	BCNF
Lossless decomposition	✓ always possible	✓ always possible
Dependency preservation	✓ always possible	✗ not always
Anomaly elimination	Partial	Complete

BCNF Decomposition Algorithm:
  result ← {R}
  while some relation Ri in result is not in BCNF:
    find a non-trivial FD X → Y in Ri that violates BCNF (X is not superkey of Ri)
    replace Ri with:
      Ri1 = X ∪ Y          (contains the violating FD)
      Ri2 = Ri − Y + X     (retains X as a join key)
  return result

3NF Synthesis Algorithm:
  1. Compute canonical cover Fc of F
  2. For each FD X → Y in Fc, create relation (X ∪ Y)
  3. If no relation contains a candidate key of R, add one
  4. Remove redundant relations (subsets of another)

4.4 Lossless Decomposition

Decomposing R into R1 and R2 is lossless if:

R1 ∩ R2 → R1 (the common attributes are a key for R1), OR
R1 ∩ R2 → R2 (the common attributes are a key for R2).

Test: natural joining R1 and R2 should reproduce exactly R — no spurious tuples.

Dependency preservation: a decomposition preserves dependencies if every FD in F can be checked within a single relation of the decomposition (no cross-relation FD checking needed).

Exam Quick-Reference

Armstrong axioms: Reflexivity · Augmentation · Transitivity (RAT).
Closure test: if the closure of an attribute set includes all attributes, it's a superkey.
2NF removes partial deps on composite PK; 3NF removes transitive deps.
BCNF: every determinant is a candidate key — stricter than 3NF.
BCNF may lose dependency preservation; 3NF always preserves dependencies.

Full Syllabus Outline

Every topic from the syllabus data is preserved here.

4.1
Integrity constraints and domain constraints
DE
NOT NULL, UNIQUE, PRIMARY KEY, FOREIGN KEY, and CHECK constraints with SQL syntax. Relational integrity and key constraints. Domain constraints.
4.2
Assertions
DE
CREATE ASSERTION syntax. Using assertions to enforce complex multi-table integrity constraints. Examples.
4.3
Functional dependencies
DEPS
Formal definition of functional dependency. Armstrong's axioms: reflexivity, augmentation, transitivity. Derived rules: union, decomposition, pseudotransitivity. Attribute closure algorithm ({A}+). Canonical cover. Examples and problems.
4.4
Different normal forms (1NF, 2NF, 3NF, BCNF)
DEPS
Definition and significance of database normalization. Update, insertion, and deletion anomalies. 1NF: atomicity of attributes. 2NF: no partial dependencies. 3NF: no transitive dependencies; 3NF decomposition algorithm. BCNF: every determinant is a candidate key; BCNF decomposition algorithm. Lossless-join decomposition. Dependency preservation. Properties and comparison of 3NF and BCNF.

Solved PYQs

A few past questions with short answers.

Chapter 45 marksasked 1x2082 Kartik B

How do you compute an attribute closure? Explain with a suitable example. Define 3NF along with a suitable example schema. Compare 3NF with BCNF.

Solution

Attribute Closure (A⁺):

The attribute closure of a set of attributes A under a set of functional dependencies F is the set of all attributes that can be functionally determined by A using the FDs in F.

Algorithm:

Initialize: closure := A
Repeat until no change:
- For each FD X → Y in F: if X ⊆ closure, then closure := closure ∪ Y
Return closure

Uses:

If closure = all attributes → A is a superkey.
If additionally no proper subset of A has a closure = all attributes → A is a candidate key.
To test if FD A → B holds under F: check if B ⊆ A⁺.

Example: R(A, B, C, D, E), F = {A → BC, B → D, CD → E}

Compute {A}⁺:
  Start:   {A}
  A → BC:  {A, B, C}       (A ⊆ {A}, so add B, C)
  B → D:   {A, B, C, D}    (B ⊆ {A,B,C}, so add D)
  CD → E:  {A, B, C, D, E} (CD ⊆ {A,B,C,D}, so add E)

{A}⁺ = {A,B,C,D,E} = all attributes → A is a superkey.
No proper subset of {A} has this property → A is a CANDIDATE KEY.

Compute {B}⁺:
  Start:   {B}
  B → D:   {B, D}
  (No other FD fires)
{B}⁺ = {B, D} ≠ all attributes → B is NOT a superkey.

Chapter 43 marksasked 1xModel Q

Formally define a functional dependency. Explain the Armstrong's axioms for functional dependencies.

Solution

Armstrong's Axioms for Functional Dependencies:

Armstrong's axioms are a set of inference rules that are sound (only derive valid FDs) and complete (can derive all FDs that logically follow from a set F). They are used to compute F⁺ (the closure of F).

Three Primary Axioms:

Axiom	Statement	Example
Reflexivity	If Y ⊆ X, then X → Y	{A,B} → {A} (trivial FD; always holds)
Augmentation	If X → Y, then XZ → YZ (for any Z)	A → B implies AC → BC
Transitivity	If X → Y and Y → Z, then X → Z	A → B and B → C implies A → C

Three Derived Rules (proved from the primary three):

Rule	Statement	Proof
Union	X → Y and X → Z ⟹ X → YZ	Augment X→Y with Z: XZ→YZ; augment X→Z with X: X→XZ; transitivity: X→YZ
Decomposition	X → YZ ⟹ X → Y and X → Z	YZ⊇Y by reflexivity: YZ→Y; transitivity with X→YZ
Pseudotransitivity	X → Y and WY → Z ⟹ WX → Z	Augment X→Y with W: WX→WY; transitivity with WY→Z

Chapter 46 marksasked 1xModel Q

Explain the conditions for BCNF and 3NF. Compare them and explain which normal form you would use in which condition along with proper justification.

Solution

Canonical Cover (Minimal Cover, F_c):

The canonical cover of a set of FDs F is a minimal equivalent set F_c such that:

F_c logically implies all FDs in F (and vice versa — they are equivalent).
Every FD in F_c has a single attribute on the right-hand side.
No FD in F_c is redundant — removing any one FD changes the closure.
No LHS attribute in any FD is extraneous — removing it still allows deriving the same set of FDs.

Algorithm to Compute Canonical Cover:

Step 1: Apply the Union rule — combine FDs with identical LHS: e.g., A → B and A → C become A → BC.

Step 2: Remove extraneous LHS attributes. Attribute X is extraneous in XY → Z if removing X still allows deriving XY → Z from the remaining FDs. Test: compute {Y}⁺ under F — if Z ∈ {Y}⁺, then X is extraneous.

Step 3: Remove extraneous RHS attributes (decompose). Split A → BC into A → B and A → C, then check if either is derivable from the rest.

Step 4: Remove redundant FDs. An FD X → Y is redundant if Y ∈ {X}⁺ computed using the remaining FDs in F_c.

Use of Canonical Cover: The 3NF synthesis algorithm uses F_c as input — one relation is created for each FD in F_c.

More PYQs

Additional practice from this chapter.

Define integrity constraints in DBMS. Give examples of domain constraints with its SQL syntax.
4 marksasked 1x2082 Kartik B
How do you compute an attribute closure? Explain with a suitable example. Define 3NF along with a suitable example schema. Compare 3NF with BCNF.
5 marksasked 1x2082 Kartik B
Formally define a functional dependency. Explain the Armstrong's axioms for functional dependencies.
3 marksasked 1xModel Q
Explain the conditions for BCNF and 3NF. Compare them and explain which normal form you would use in which condition along with proper justification.
6 marksasked 1xModel Q
What is database normalization and why is it needed? Explain 1NF, 2NF, 3NF and BCNF along with examples.
10 marksasked 2x2081 Chaitra R

Database Constraints and Normalization

Chapter 4 — Database Constraints and Normalization

4.1 Integrity Constraints

4.2 Functional Dependencies (FD)

Armstrong's Axioms (sound and complete)

Attribute Closure Algorithm

Canonical Cover (Minimal Cover)

4.3 Normalization

1NF — First Normal Form

2NF — Second Normal Form

3NF — Third Normal Form

BCNF — Boyce-Codd Normal Form

4.4 Lossless Decomposition

Exam Quick-Reference

Integrity constraints and domain constraints

Assertions

Functional dependencies

Different normal forms (1NF, 2NF, 3NF, BCNF)