Megan Taylor

front-end dev, volunteacher, news & data junkie, bibliophile, Flyers fan, sci-fi geek and kitteh servant

Intro to Databases: Relational Design Theory, Boyce-Codd Normal Form

Decomposition of a relational schema
R(a1, … ,an) -> R1(b1, …, bk) R2(c1, …, cm)
set of attributes B union set of attributes C = set of attributes A
R1 naturally joined with R2 = R

Example #1
Student (SSN, sName, address, HScode, HSname, HScity, GPA, priority)
S1 (SSN, sName, Address, HScode, GPA, priority)
S2(HScode, HSname, HScity)

Good decompositions – lossless join property
into good relations in Boyce-Codd Normal Form

BCNF
Relation R with functional dependencies is in BCNF if for each set of attributes A -> B, A is a key

Example #1
Student(SSN, sName, address, HScode, HSname, HScity, GPA, priority)
SSN -> sName, address, GPA
GPA -> priority
HScode -> HSname, HScity

Find Keys: Closure
{SSN, HScode}

Does every functional dependency have a key on the left side? NO.

Example #2
Apply(SSN, cName, state, date, major)
SSN, cName, state -> date, major

Keys {SSN, cName, state}

Does every functional dependency have a key on the left side? YES.

BCNF decomposition algorithm
Input: relation R + FDs for R
Output: decomposition of R into BCNF relations with “lossless join”

Compute keys for R using FDs
Repeat until all relations are in BCNF:
Pick any R with A -> B that violates BCNF
Decompose R into R1(A,B) and R2(A, rest)
Compute FDs for R1 and R2
Compute keys for R1 and R2

Example #3
Student(SSN, sName, address, HScode, HSname, HScity, GPA, priority)
SSN -> sName, address, GPA
GPA -> priority
HScode -> HSname, HScity
Key:{SSN, HScode}

S1 (HScode, HSname, HScity) -> BCNF
S2 (SSN, sName, address, HScode, GPA, priority)

S3 (GPA, priority) -> BCNF
S4 (SSN, sName, address, HScode, GPA)

S5 (SSN, sName, address, GPA) -> BCNF
S6 (SSN, HScode) -> BCNF

November 10, 2011 | Comments Off on Intro to Databases: Relational Design Theory, Boyce-Codd Normal Form | Categories: Posts | Permalink

Comments are closed.

%d bloggers like this: