(edX stanfordOnline Databases: Modeling and Theory) Boyce-Codd Normal Form

https://www.edx.org/learn/databases/stanford-university-databases-modeling-and-theory

StanfordOnline: Databases: Modeling and Theory | edX

 

R(A1,A2,...An): relatioin R with a set of attributes A-1 through A-N

We can decompose R into two relations.

 

파이 있는 곳 => R1 = projection on the B attributes of R

projection을 할 때 중복은 제거된다.

릴레이션은 집합 개념이라서 기본적으로 중복이 제거된다.

 

What Boyce Codd Normal Form really does is separate the relations so that we capture each piece of information exactly once.

Boyce-Codd 정규화(BCNF)이 실제로 하는 일은,

각 정보를 정확히 한 번만 표현할 수 있도록 릴레이션을 분리하는 것이다.

 

중복을 제거하고,

하나의 정보가 하나의 테이블에만 있도록

릴레이션을 쪼개는 것이 BCNF의 본질

 

BCNF는 모든 함수적 종속 X → Y에 대해
X가 슈퍼키여야 한다는 조건을 만족해야 한다

 

(1) good decomposition을 해야 한다

(2) 분해된 릴레이션들 자체도 좋은 릴레이션이어야 한다.

그리고 그 "좋은 릴레이션"이라는 것은 BCNF를 만족하는 릴레이션이다.

 

따라서 BCNF가 무엇인지 형식적으로 설명하고,

그 다음에 자동으로 BCNF 분해를 수행하는 알고리즘을 살펴볼 것이다.

 

set of attributes A가 키가 아니라면, BCNF violation이다.

BCNF violation은 릴레이션에 redundancy가 있음을 의미하고,

업데이트 이상과 삭제 이상을 경험하게 한다.

 

여기서 key란 primary key가 아니다.

다른 속성들을 결정하는 속성이다.

또한, 릴레이션에서 튜플들 사이에 key 속성에 대한 중복이 없어야 한다.

 

다른 속성을 결정하는 속성들의 superset도 key다.

따라서 "A"가 키라면, AC, ACD도 키다.

 

 

Question. Does every functional dependency have a key on its left-hand side?

Answer. NO.

이 경우 최소키는 SSN과 HScode다.

So no functional dependency has the key on the left hand side.

따라서 BCNF 정규화된 상태를 만들려면, 릴레이션을 쪼개야 한다.

더 이상 분해할 필요 없음

Q. For the relation Apply(SSN,cName,state,date,major), suppose college names are unique and students may apply to each college only once, so we have two FDs: cName  state and SSN,cName  date,major. Is Apply in BCNF?

Answer: NO

Explanation

{SSN,cName} is a key so only cName  state is a BCNF violation. Based on this violation we decompose into A1(cName,state), A2(SSN,cName,date,major). Now both FDs have keys on their left-hand-side so we're done.

 

Input: relation R, functional dependencies for that relation

schema design that is produced automatically by the BCNF decomposition algorithm, using functional dependencies

Pick any R prime with A -> B : 어떤 functional dependencies를 pick했는지에 따라 다른 스키마를 도출할 수 있다.

하지만 다른 순서로 FD를 골라도 모두 BCNF를 만족할 것이다.

 

Compute FDs for R1 and R2: 각 분해된 릴레이션에 대해 어떤 FD가 유효한지 새로 유도해서 계산해야 한다.

implied functional dependencies

• Implied functional dependencies (함의된 함수적 종속성들)
  → 명시적으로 주어진 FD(예: A → B)만이 아니라, 그로부터 추론할 수 있는 모든 FD
  예: {A → B, B → C} 가 주어졌다면, A → C 역시 implied FD이다
• Closure (클로저)
  → 어떤 속성 집합 X에 대해, X로부터 도달 가능한(함의되는) 모든 속성들의 집합
  보통 X⁺ 라고 쓰며, 주어진 FD 집합을 기반으로 계산합니다.

 

BCNF는 이상(anomalies)을 제거한다.

같은 정보를 여러 번 저장하게 되는 경우(when we have multiple instances of the same piece of information being captured)

그런 중복된 정보가 BCNF로 분해하는 과정에서 제거된다(that's what squeezed out by the decomposition into BCNF)

 

BCNF라면 다시 조인했을 때, 원래 프로퍼티를 얻을 수 있어야 한다.

위의 판서 예시에서 B에 대한 functional dependencies가 없는데 B를 중심으로 분해하여 조인했을 때 원래 릴레이션이 나오지 않는다.

따라서 잘못된 분해다.