Lossless-join Decomposition
For the case of R = (R1, R2), we require that for all possible relations r on schema R
r = R1 (r ) R2 (r )
i.e., R1 R2 should be a superkey of either R1 or R2.
-> R1과 R2의 교집합이 둘중 하나를 결정할 때, R1 교 R2가 슈퍼키가 된다?
A decomposition of R into R1 and R2 is lossless join if at least one of the following dependencies is in F+:
R1 R2 R1
R1 R2 R2
i.e., R1 R2 should be a superkey of either R1 or R2.
The above functional dependencies are a sufficient condition for lossless join decomposition; the dependencies are a necessary condition only if all constraints are functional dependencies
Dependency Preservation
종속성 보존
Let Fi be the set of dependencies F + that include only attributes in Ri.
A decomposition is dependency preserving, if
(F1 F2 … Fn )+ = F +
If it is not, then checking updates for violation of functional dependencies may require computing joins, which is expensive.
Example
R = (A, B, C )
F = {A B, B C}
Key = {A}
R is not in BCNF
Decomposition R1 = (A, B), R2 = (B, C)
R1 and R2 in BCNF
Lossless-join decomposition
Dependency preserving
종속성이 보존될 수 있게 lossless-join을 해야한다.
Testing for BCNF
To check if a non-trivial dependency causes a violation of BCNF
1. compute + (the attribute closure of ), and
2. verify that it includes all attributes of R, that is, it is a superkey of R.
Simplified test: To check if a relation schema R is in BCNF, it suffices to check only the dependencies in the given set F for violation of BCNF, rather than checking all dependencies in F+.
If none of the dependencies in F causes a violation of BCNF, then none of the dependencies in F+ will cause a violation of BCNF either.
However, simplified test using only F is incorrect when testing a relation in a decomposition of R
Consider R = (A, B, C, D, E), with F = { A B, BC D}
Decompose R into R1 = (A,B) and R2 = (A,C,D, E)
Neither of the dependencies in F contain only attributes from
(A,C,D,E) so we might be mislead into thinking R2 satisfies BCNF.
In fact, dependency AC D in F+ shows R2 is not in BCNF.
attribute closure을 찾는 것이, functional dependency를 찾는 것보다 효과적임.
canonical cover시 a, c, d, e는 bcnf이다. canonical cover로만 체크하면 안됨
원본에서는 canonical만 하고 closure 체크는 안해도 된다. 하지만, decomposition시에는 closure도 체크를 해줘야 한다.
Testing Decomposition for BCNF
To check if a relation Ri in a decomposition of R is in BCNF,
Either test Ri for BCNF with respect to the restriction of F to Ri (that is, all FDs in F+ that contain only attributes from Ri)
or use the original set of dependencies F that hold on R, but with the following test:
for every set of attributes Ri, check that + (the attribute closure of ) either includes no attribute of Ri- , or includes all attributes of Ri.
If the condition is violated by some in F, the dependency
(+ - ) Ri
can be shown to hold on Ri, and Ri violates BCNF.
We use above dependency to decompose Ri
Example of BCNF Decomposition
class (course_id, title, dept_name, credits, sec_id, semester, year, building, room_number, capacity, time_slot_id)
Functional dependencies:
course_id→ title, dept_name, credits
building, room_number→capacity
course_id, sec_id, semester, year→building, room_number, time_slot_id
A candidate key {course_id, sec_id, semester, year}.
BCNF Decomposition:
course_id→ title, dept_name, credits holds
but course_id is not a superkey.
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)
course is in BCNF
How do we know this?
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.
BCNF and Dependency Preservation
It is not always possible to get a BCNF decomposition that is dependency preserving
R = (J, K, L )
F = {JK L, L K }
Two candidate keys = JK and JL
R is not in BCNF
Any decomposition of R will fail to preserve
JK L
This implies that testing for JK L requires a join
JK -> L 함수 종속의 preserving이 되지 않음.
JK, LK로 나눌 시, 프로그램에 JK -> L라는 종속을 프로그램에서 만들어 줘야 한다.
DB에서는 막을 수가 없음.
JKL, (L, K)
foreign key 제약의 관계를 하나 더만들면 됨.
근데 이건 BCNF가 아니다. BCNF를 안해도 된다는 거임...
Third Normal Form: Motivation
There are some situations where
BCNF is not dependency preserving, and
efficient checking for FD violation on updates is important
Solution: define a weaker normal form, called Third Normal Form (3NF)
Allows some redundancy (with resultant problems; we will see examples later)
But functional dependencies can be checked on individual relations without computing a join.
There is always a lossless-join, dependency-preserving decomposition into 3NF.
BCNF로 dependency preserving을 만족하지 못할 경우, 3정규형으로 정규화 하라.
대부분의 경우 제3정규형으로 anomally 배제 가능함.
Redundancy in 3NF
There is some redundancy in this schema
Example of problems due to redundancy in 3NF
R = (J, K, L)
F = {JK L, L K }
repetition of information (e.g., the relationship l1, k1)
(i_ID, dept_name)
need to use null values (e.g., to represent the relationship l2, k2 where there is no corresponding value for J => Insertion Anomaly).
(i_ID, dept_name) if there is no separate relation mapping instructors to departments
BCNF가 아니기 때문에 Redundancy가 존재.
L, K을 따로 빼서 foreign key 제약등으로 문제 해결가능.
Comparison of BCNF and 3NF
It is always possible to decompose a relation into a set of relations that are in 3NF such that:
the decomposition is lossless
the dependencies are preserved
It is always possible to decompose a relation into a set of relations that are in BCNF such that:
the decomposition is lossless
it may not be possible to preserve dependencies.
Design Goals
Goal for a relational database design is:
BCNF.
Lossless join.
Dependency preservation.
If we cannot achieve this, we accept one of
Lack of dependency preservation
Redundancy due to use of 3NF
Interestingly, SQL does not provide a direct way of specifying functional dependencies other than superkeys.
-> 예외적으로, SQL이 슈퍼키를 제외하고는 직접적으로 functional dependency를 제공해주지 않는다.
슈퍼키를 제외하고는 표현해 줄 수 없기 때문에 테이블을 나눠서라도 funtional dependency를 보존해줘야 함.
일반적으로는 Redundancy를 감수하고 3NF를 사용하는 것이 더 낫다.
