DBMS - (18) BCNF(Boyce-Codd Normal Form)

DBMS - (18) BCNF(Boyce-Codd Normal Form)

Relational design by decomposition
- 'mega' relations + properties of the data
- system decomposes based on properties.
- final set of relations satisfies normal form.
- functional dependencies => BCNF
- multivalued dependences => 4NF

Decomposition of a relational schema.
R(A1,A2,...,An) = R(A*)
R1(B1,B2,...,Bn) = R(B*)
R2(C1,C2,...,Cn) = R(C*)

- B* U C* = A*
- R1 ⋈ R2 = R
- R1 = π(B*)(R)
- R2 = π(C*)(R)

 

Decomposition Example #1
Student(SSN, sName, address, HScode, HSname, HScity, GPA, property)

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

- B* U C* = A* 만족
- 즉, S1 ⋈ S2 = Student 이므로 decomposition으로 인한 정보의 손실이 발생하지 않았음
(* lossless decomposition)

Decomposition Example #2
Student(SSN, sName, address, HScode, HSname, HScity, GPA, property)

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

- B* U C* = A* 만족
- 즉, S1 ⋈ S2 = Student 이므로 decomposition으로 인한 정보의 손실이 발생하지 않았음
(* lossless decomposition)

Example #1, #2와 같이 Student schema를 서로 다른 형태의 relation으로 decomposition할 수 있다. 두 개의 예제 모두 lossless decompositon이다. 그러나, S1, S2이 서로 다른 attr를 갖게 되었는 데 무엇이 더 좋은 relation일까?

GOOD decompositon only want "reassembly" that produces original(=lossless join property)
GOOD relations is a BCNF.

 

BCNF(Boyce-Codd Normal Form)
- Relation R with FDs is in BCNF if: For each A*->B, A* is a key.
- 즉, attribute의 결정자는 반드시 key인 경우 BCNF라 한다.

BCNF Example #1
- BCNF로 decomposition할 때는 FD(Functional Dependency)를 이용한다.

Student(SSN, sName, address, HScode, HSname, HScity, GPA, property)
SSN -> sName, address, GPA
GPA -> priority
HScode -> HSname, HScity

(1) Student schema의 key를 찾는다. key는 key -> all attributes 정의를 만족하는 set of attribute 이므로 {SSN, HScode}가 위 조건을 만족한다. 즉, {SSN, HScode} functionally determines all of attributes.

(2) Student shcema에 존재하는 모든 FDs의 left-hand side가 key인지 체크한다. => NO, BCNF가 아님

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

(1) Apply schema의 key를 찾는다. {SSN, cName, state}

(2) Apply schema에 존재하는 모든 모든 FDs의 left-hand side가 key인지 체크한다. => YES, BCNF 만족

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. ( Key -> all of attributes )
- Repeat until all relations are in BCNF :
(1) Pick any R' with A*->B* that violates BCNF
(2) Decompose R' into R1(A*, B*) and R2(A*, rest)
(3) Compute FDs for R1 and R2
(4) Compute keys for R1 and R2

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

Compute keys for R using FDs. ( Key -> all of attributes )
key : {SSN, HScode}

Pick any R' with A*->B* that violates BCNF
S1(HScode, HSname, HScity)
- S1은 HScode->HSname, HScity 단 하나의 FD를 갖고 LHS가 key이므로 BCNF를 만족한다.

S2(SSN, sName, address, HScode, GPA, priority)
SSN -> sName, address, GPA
GPA -> priority
- S2가 가진 FDs 중 GPA -> priority의 LHS가 key가 아니므로 BCNF가 아니다.

S2에 대해 (1) ~ (4) 반복
Pick any R' with A*->B* that violates BCNF
S3(GPA, priority)
- GPA -> priority FD를 가지므로 LHS가 key이다. BCNF 만족
S4(SSN, sName, address, HScode, GPA)
- S4 have a violating FD(HScode -> HSname, HScity), BCNF가 아니다
- SSN, HScode -> sName, address, GPA 이지만
- SSN -> sName, address, GPA로써 key의 부분집합인 SSN이 attribute를 결정짓는 부분함수 종속성을 지닌다.

S4에 대해 (1) ~ (4) 반복
S5(SSN, sName, address, GPA)
- SSN-> sName, addres,GPA FD를 가짐. BCNF 만족
S6(SSN, HScode)
- FD가 존재하지 않음. BCNF 만족

BCNF Decomposition 결과

Student(SSN, sName, address, HScode, HSname, HScity, GPA, property) 

BCNF
S1(HScode, HSname, HScity)
S3(GPA, priority)
S5(SSN, sName, address, GPA)
S6(SSN, HScode)

Does BCNF guarantee a good decomposition?
- removes anomalies? YES
- Can logically reconsturct original relation? YES

(주의)
BCNF Decomposition을 하려면 반드시 original relation에 functional dependency가 존재해야 함.

Reference
https://www.youtube.com/watch?v=mfVCesoMaGA&list=PL6hGtHedy2Z4EkgY76QOcueU8lAC4o6c3&index=21