Algorithms for Decomposition
Decomposition is the process of breaking down a relation schema into smaller schemas to achieve
desirable properties like Boyce–Codd Normal Form (BCNF) and Third Normal Form (3NF) while
ensuring lossless decomposition and dependency preservation.
8.5.1 BCNF Decomposition
Testing for BCNF
To check if a relation R is in BCNF:
1. Find a functional dependency (FD) X → Y such that:
X is not a superkey for R.
2. If such a dependency exists, R is not in BCNF.
Simplifications:
o Instead of computing the full closure F+, check if X+ (closure of X) contains all
attributes of R.
o If X+ does not cover all attributes, R violates BCNF.
BCNF Decomposition Algorithm
1. Check if R is in BCNF:
o If R is in BCNF, return R.
o If not, find a nontrivial functional dependency X → Y such that X is not a superkey.
2. Decompose R into two relations:
o R1 = (X ∪ Y)
o R2 = (R - (Y - X)) (remaining attributes of R)
3. Recursively apply BCNF decomposition to R1 and R2.
Guarantees:
o The decomposition is lossless.
o It eliminates all redundancies due to functional dependencies.
Example:
Given Class(course_id, title, dept_name, credits, sec_id, semester, year, building, room_number,
capacity, time_slot_id) with functional dependencies:
1. course_id → title, dept_name, credits
2. building, room_number → capacity
3. (course_id, sec_id, semester, year) → building, room_number, time_slot_id
Steps:
A candidate key for this schema is{course id, sec id, semester, year}.
We can apply the algorithm of Figure 8.11 to the class example as follows:
• The functional dependency: course id→ title, dept name, credits holds, but course id is not a
superkey. Thus, class is not in BCNF. We replace class by:
course(course id, title, dept name, credits)
class-1 (course id, sec id, semester, year, building, room number capacity, time slot id)
The only non trivial functional dependencies that hold on course include course id on the left side of
the arrow. Since course id is a key for course, the relation course is in BCNF. • A candidate key for
class-1 is{course id, sec id, semester, year}.
The functional dependency:
building, room number→capacity holds on class-1, but{building, room number} is not a superkey for
class-1. We replace class-1 by:
classroom (building, room number, capacity)
section (course id, sec id, semester, year, building, room number, time slot id)
classroom and section are in BCNF.
Thus, the decomposition of class results in the three relation schemas course, classroom, and
section, each of which is in BCNF
Final Decomposition:
Course(course_id, title, dept_name, credits)
Classroom(building, room_number, capacity)
Section(course_id, sec_id, semester, year, building, room_number, time_slot_id)
8.5.2 3NF Decomposition
Why 3NF?
BCNF decomposition is not always dependency-preserving.
3NF allows for dependency preservation while minimizing redundancy.
3NF Decomposition Algorithm
1. Compute the canonical cover (Fc) of functional dependencies (F).
2. Create a relation for each functional dependency X → Y in Fc.
3. If no created relation contains a candidate key, add a relation containing a candidate key.
4. Resulting decomposition is guaranteed to be lossless and dependency-preserving.
Example of 3NF Decomposition Algorithm
We will apply the 3NF decomposition algorithm step by step using the same example from
the notes:
Given Relation Schema:
Class(course_id, title, dept_name, credits, sec_id, semester, year, building, room_number,
capacity, time_slot_id)
Given Functional Dependencies (F):
1. course_id → title, dept_name, credits
2. building, room_number → capacity
3. (course_id, sec_id, semester, year) → building, room_number, time_slot_id
Step 1: Compute the Canonical Cover (Fᴄ)
The canonical cover is found by removing extraneous attributes and redundant
dependencies. In this case, the functional dependencies are already minimal, so we keep
them as they are.
Step 2: Create a Relation for Each Functional Dependency
We create one relation for each FD in Fᴄ:
1. From course_id → title, dept_name, credits, create:
Course(course_id, title, dept_name, credits)
2. From building, room_number → capacity, create:
Classroom(building, room_number, capacity)
3. From (course_id, sec_id, semester, year) → building, room_number, time_slot_id,
create:
Section(course_id, sec_id, semester, year, building, room_number, time_slot_id)
Step 3: Ensure a Candidate Key is Present
The original relation Class has (course_id, sec_id, semester, year) as a candidate key.
The relations created so far do not contain all attributes from the original schema.
To ensure a candidate key is included, we add one more relation containing a superkey:
KeyRelation(course_id, sec_id, semester, year)
Final 3NF Decomposition
1. Course(course_id, title, dept_name, credits)
2. Classroom(building, room_number, capacity)
3. Section(course_id, sec_id, semester, year, building, room_number, time_slot_id)
4. KeyRelation(course_id, sec_id, semester, year) (to ensure a superkey is retained)
Comparison of BCNF and 3NF
Property BCNF 3NF
Stronger (Eliminates all Weaker (Allows some redundancy for
Redundancy Removal
redundancy due to FDs) dependency preservation)
Dependency
Not always preserved Always preserved
Preservation
Lossless
Yes Yes
Decomposition
Computation
Higher Lower
Complexity
