1NF to BCNF - Step-by-Step Normalization

▶

Steps

setup

Initialize Relation Schema

We start with the original relation R having attributes A, B, C, D and functional dependencies A->B, B->C, C->D. This is represented as a single node in the B-tree.

💡 Initialization sets the base schema before any normalization. Understanding the starting point is crucial to follow subsequent decompositions.

Line:

relation = Relation(['A','B','C','D'], fds=[('A','B'), ('B','C'), ('C','D')])

💡 The entire schema is initially one node containing all attributes and dependencies.

compare

Check for BCNF Violations at Root

We examine the functional dependencies to find any that violate BCNF. A->B is checked first; since A is not a superkey, this FD violates BCNF.

💡 Identifying violating FDs is the key to deciding where to decompose the schema.

Line:

for fd in fds:
    if not is_superkey(fd.left):
        violation = fd

💡 BCNF requires every determinant to be a superkey; here A is not, so decomposition is needed.

split

Decompose Relation on Violation A->B

We split the relation into two: R1 with attributes {A,B} and R2 with attributes {A,C,D}. This removes the violation by isolating the dependency.

💡 Decomposition removes redundancy caused by violating FDs by creating smaller relations.

Line:

R1 = Relation(['A','B'])
R2 = Relation(['A','C','D'])

💡 Splitting isolates the violating FD into a separate relation where it is BCNF compliant.

compare

Check BCNF Violations in Subrelation R2

We now check relation R2(A,C,D) for violations. The FD B->C is not applicable here, but C->D is checked and found violating since C is not a superkey in R2.

💡 Each decomposed relation must be checked independently for BCNF compliance.

Line:

for fd in R2.fds:
    if not is_superkey(fd.left):
        violation = fd

💡 Decomposition is iterative; new relations may still violate BCNF and require further splitting.

split

Decompose Relation R2 on Violation C->D

We split R2 into R3 with attributes {C,D} and R4 with attributes {A,C}. This isolates the violating FD C->D.

💡 Further decomposition refines the schema to satisfy BCNF in all subrelations.

Line:

R3 = Relation(['C','D'])
R4 = Relation(['A','C'])

💡 Splitting on violating FD reduces redundancy and enforces BCNF locally.

compare

Check BCNF Violations in Relation R4

We check R4(A,C) for violations. The FD B->C is not applicable here. No FD violates BCNF in R4, so no decomposition needed.

💡 Confirming no further decomposition is needed prevents unnecessary splits.

Line:

for fd in R4.fds:
    if not is_superkey(fd.left):
        violation = fd

💡 Some subrelations are already BCNF compliant and remain unchanged.

compare

Check BCNF Violations in Relation R2 (Node 3) After Decomposition

We verify if node 3 (now with key C) violates BCNF. Since it only contains the key C, it is trivially BCNF compliant.

💡 After decomposition, parent nodes may become simple keys ensuring BCNF compliance.

Line:

if len(node.keys) == 1:
    node_is_bcnf = True

💡 Decomposition simplifies parent nodes to keys that satisfy BCNF.

compare

Check BCNF Violations in Relation R1

We check R1(A,B) for violations. The FD B->C is not applicable here. No violations found, so R1 is BCNF compliant.

💡 Verifying all leaf relations ensures the entire schema is BCNF compliant.

Line:

for fd in R1.fds:
    if not is_superkey(fd.left):
        violation = fd

💡 Initial decomposed relations may already satisfy BCNF.

traverse

Final BCNF Schema Achieved

All relations are BCNF compliant. The final schema consists of R1(A,B), R3(C,D), and R4(A,C) with root node linking them by keys A and C.

💡 The final step confirms the normalization process is complete and the schema is free of BCNF violations.

Line:

return [R1, R3, R4]

💡 Normalization decomposes the original schema into smaller BCNF relations connected in a tree structure.

traverse

Read Final Answer from BCNF Schema

We extract the final normalized relations from the B-tree structure: R1(A,B), R4(A,C), and R3(C,D). This is the BCNF decomposition result.

💡 Reading the final answer confirms the normalization output matches expectations.

Line:

answer = [R1.keys, R4.keys, R3.keys]

💡 The final relations represent a lossless, dependency-preserving BCNF decomposition.

class Relation:
    def __init__(self, keys, fds=None):
        self.keys = keys
        self.fds = fds or []

# STEP 1
relation = Relation(['A','B','C','D'], fds=[('A','B'), ('B','C'), ('C','D')])

# STEP 2
for fd in relation.fds:
    if not is_superkey(fd[0], relation.keys):
        violation = fd
        break

# STEP 3
R1 = Relation(['A','B'], fds=[('A','B')])
R2 = Relation(['A','C','D'], fds=[('B','C'), ('C','D')])

# STEP 4
for fd in R2.fds:
    if not is_superkey(fd[0], R2.keys):
        violation = fd
        break

# STEP 5
R3 = Relation(['C','D'], fds=[('C','D')])
R4 = Relation(['A','C'], fds=[])

# STEP 6
for fd in R4.fds:
    if not is_superkey(fd[0], R4.keys):
        violation = fd
        break

# STEP 7
# Node 3 simplified to key C, BCNF compliant

# STEP 8
for fd in R1.fds:
    if not is_superkey(fd[0], R1.keys):
        violation = fd
        break

# STEP 9
final_schema = [R1, R4, R3]

# STEP 10
answer = [r.keys for r in final_schema]

📊

1NF to BCNF - Step-by-Step Normalization - Watch the Algorithm Execute, Step by Step

Watching this step-by-step visualization reveals how normalization systematically removes redundancy and anomalies by decomposing relations based on functional dependencies, which is hard to grasp from code or text alone.

traverse

ABCD

leaf

Starting with full relation R(A,B,C,D) and its functional dependencies.

compareKey: A->B

ABCD

leaf

Checking FD A->B for BCNF violation; A is not a superkey.

splitKey: A->B↑ promoted: A

A

AB

leaf

ACD

leaf

Decomposed relation on FD A->B; promoted A to parent node.

compareKey: C->D

A

AB

leaf

ACD

leaf

Checking FD C->D in subrelation R2 for BCNF violation.

splitKey: C->D↑ promoted: C

A

AB

leaf

C

CD

leaf

AC

leaf

Decomposed R2 on FD C->D; promoted C to parent node.

compare

A

AB

leaf

C

CD

leaf

AC

leaf

Checked R4 for BCNF violations; none found.

compare

A

AB

leaf

C

CD

leaf

AC

leaf

Node 3 with key C is BCNF compliant after decomposition.

compare

A

AB

leaf

C

CD

leaf

AC

leaf

Checked R1 for BCNF violations; none found.

traverse

AC

AB

leaf

C

CD

leaf

Final BCNF schema with relations R1(A,B), R4(A,C), and R3(C,D).

Key Takeaways

✓ Normalization decomposes relations by isolating violating functional dependencies into separate relations.

This insight is hard to see from code alone because the iterative splitting and promotion of keys is abstract without visualization.

✓ Each decomposed relation must be checked independently for BCNF compliance, leading to recursive decomposition.

Understanding the recursive nature of normalization is easier when watching how each node is processed and split.

✓ The final BCNF schema is a tree of relations connected by keys, ensuring lossless join and dependency preservation.

Visualizing the final tree structure clarifies how normalization maintains data integrity across decomposed relations.

Practice

1. You need to optimize a database query that frequently performs exact-match lookups on a large, unordered dataset. Which index type is most appropriate to use?

easy

A. B+ tree index, because it supports efficient range queries.

B. Hash index, because it provides O(1) average-time equality lookups.

C. B+ tree index, because it provides faster equality lookups than hash indexes.

D. Hash index, because it supports ordered traversal for range queries.

Solution

1. Step 1: Identify the query type

   The query performs exact-match lookups, which hash indexes optimize efficiently.

2. Step 2: Understand hash index strengths

   Hash indexes provide average O(1) time for equality lookups but do not support ordered traversal.

3. Step 3: Understand B+ tree strengths

   B+ trees support ordered traversal and range queries but equality lookups are O(log n), slower than hash indexes.

4. Step 4: Evaluate distractors

   B+ tree index, because it supports efficient range queries. is incorrect because range queries are not the focus here. B+ tree index, because it provides faster equality lookups than hash indexes. wrongly claims B+ trees are faster for equality lookups. Hash index, because it supports ordered traversal for range queries. incorrectly states hash indexes support ordered traversal.

5. Final Answer:

   Option B -> Option B

6. Quick Check:

   Exact-match queries -> hash index [OK]

Hint: Exact-match -> hash index; range -> B+ tree

Common Mistakes:

• Confusing hash indexes as supporting range queries
• Assuming B+ trees are always faster for equality lookups
• Believing hash indexes maintain order

2. You have a sales dataset with multiple products across categories. You need to compute total sales per product, rank products within each category by sales, and filter categories based on total sales exceeding a threshold. Which approach guarantees an efficient and correct solution?

easy

A. Use a greedy algorithm to pick top-selling products without grouping or ranking.

B. Manually iterate over sales records in application code, aggregate totals, then sort and rank products.

C. Use SQL GROUP BY to aggregate sales, HAVING to filter categories, and window functions like RANK() to rank products within categories.

D. Use dynamic programming to compute cumulative sales and ranks iteratively.

Solution

1. Step 1: Identify aggregation and filtering needs

   The problem requires grouping sales by product and category, filtering categories by total sales, and ranking products within categories.

2. Step 2: Recognize SQL features that fit

   GROUP BY aggregates sales per product-category, HAVING filters aggregated categories, and window functions like RANK() rank products within partitions.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Window functions combined with GROUP BY and HAVING handle all requirements efficiently [OK]

Hint: Window functions + GROUP BY + HAVING solve aggregation and ranking [OK]

Common Mistakes:

• Confusing greedy or DP approaches for aggregation tasks

3. What is the time complexity of the optimal SQL approach that uses DISTINCT salaries ordered descending with LIMIT and OFFSET to find the second highest salary, assuming n rows in the Employee table?

medium

A. O(n log n) due to sorting distinct salaries before applying LIMIT and OFFSET.

B. O(n^2) because DISTINCT requires comparing each salary with every other salary.

C. O(n) because we only scan the table once to find the max salary.

D. O(log n) because indexing on Salary allows binary search for the second highest.

Solution

1. Step 1: Identify operations involved

   The query selects DISTINCT salaries and orders them descending, which requires sorting.

2. Step 2: Analyze complexity of sorting distinct salaries

   Sorting distinct salaries takes O(m log m), where m ≤ n. In worst case, m = n, so O(n log n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting dominates complexity, scanning alone is not enough [OK]

Hint: Sorting distinct salaries dominates time complexity [OK]

Common Mistakes:

• Assuming O(n) because of single scan
• Assuming DISTINCT is O(n^2) due to pairwise comparisons

4. What is the time complexity of performing a nested loop join between two tables with sizes n and m respectively, assuming no indexes and a simple equality join condition?

medium

A. O(n + m), since each table is scanned once

B. O(n * m), because each row in the first table is compared to every row in the second

C. O(n log m), assuming the second table is sorted

D. O(n), if a hash map is used for lookups

Solution

1. Step 1: Analyze nested loops

   The outer loop runs n times, and for each iteration, the inner loop runs m times, leading to n * m comparisons.

2. Step 2: Confirm no indexing or hashing

   Since no hash map or index is used, no faster lookup is possible, so complexity remains O(n * m).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Nested loops multiply iteration counts [OK]

Hint: Nested loops multiply table sizes for complexity [OK]

Common Mistakes:

• Assuming linear time due to scanning once
• Confusing sorting with hashing benefits

5. If a database system needs to support very high-frequency insertions and deletions along with range queries, how does the B+ Tree structure help maintain performance, and what challenges might arise?

hard

A. B+ Tree stores data in internal nodes to reduce tree height, minimizing disk I/O during updates.

B. B+ Tree's linked leaf nodes allow efficient range queries, but frequent splits and merges can cause fragmentation and increased disk I/O.

C. B+ Tree avoids node splitting by always merging nodes during insertions and deletions, ensuring stable performance.

D. B+ Tree uses a fixed node size that prevents fragmentation, so performance remains constant regardless of update frequency.

Solution

1. Step 1: Understand B+ Tree leaf linkage benefits

   Linked leaf nodes enable efficient sequential access for range queries.

2. Step 2: Consider update overhead

   High-frequency insertions/deletions cause node splits and merges, which can fragment data and increase disk I/O.

3. Step 3: Analyze incorrect options

   B+ Tree stores data in internal nodes to reduce tree height, minimizing disk I/O during updates. is false; B+ Tree stores data only in leaves. B+ Tree avoids node splitting by always merging nodes during insertions and deletions, ensuring stable performance. is incorrect because merges alone cannot avoid splits. B+ Tree uses a fixed node size that prevents fragmentation, so performance remains constant regardless of update frequency. is wrong; fixed node size does not prevent fragmentation from splits/merges.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   B+ Tree balances efficient range queries with update overhead due to structural changes.

Hint: Linked leaves -> fast range queries; splits/merges -> update overhead

Common Mistakes:

• Assuming B+ Tree stores data in internal nodes
• Believing merges prevent splits entirely
• Thinking fixed node size eliminates fragmentation