CSE 414: Section 6

BCNF

October 31st, 2019

​

Mid-Quarter Section Survey!!

tinyurl.com/y23u4q8c

Outline

BCNF decomposition

• Check whether chosen FD violates BCNF
• Use any FD that violates BCNF to decompose.

​

​

Keys

We call a set of attributes that determines all other attributes in a relation to be a superkey.

​

If no proper subset of a superkey is a superkey, �we call that set a minimal superkey or just key

e.g. a & b, c

Closure Algorithm

Goal:

We want everything that an attribute/set of attributes determines

Observation:

• If we have A -> B and B -> C, then A -> C
• So really, A -> B and C
• Formal notation is {A}⁺ = {A, B, C}
• Since the closure of A is all attributes, A is a key

​

Conceptual Design

SSN Name, City

Conceptual Design

Anomalies:

• Redundancy = repeat data

• Update anomalies = what if Fred moves to “Bellevue”?

• Deletion anomalies = what if Joe deletes his phone number?

​

Conceptual Design

The BCNF (Boyce-Codd Normal Form) ---- A relation R is in BCNF if every set of attributes is either a superkey or its closure is the same set (itself)

BCNF Decomposition Algorithm

Normalize(R)

find X s.t.: X ≠ X⁺ and X⁺ ≠ [all attributes]

if (not found) then R is in BCNF

let Y = X⁺ - X; Z = [all attributes] - X⁺

decompose R into R1(X ∪ Y) and R2(X ∪ Z)

Normalize(R1); Normalize(R2);

​

X +

Example

The relation is R (A, B, C, D, E)

FDs : A → E, BC → A, and DE → B

Question : Decompose R into BCNF.

Solution

Notice that {A}⁺ = {A,E}, which violates the BCNF condition.

We split R to R1(A,E) and R2(A,B,C,D).

R1 satisfies BCNF now, but R2 does not because: {B,C}⁺ = {B,C,A}.

Notice that there is no E in R2 table so we don't need to consider the FD

DE → B!

Split R2 to: R21(B,C,A) and R22(B,C,D)

Solution

Final Result:

R1(A,E), R21(B,C,A) and R22(B,C,D)