A->H >> A->B 이고 B->H 이므로 transitive 속성으로 A->H 인 것을 추가적으로 알 수 있다.
AG->I >> A->C 이므로 augmentation 속성으로 AG->CG 이고 따라서 CG->I 이므로 transitivity속성으로 AG->I인 것도 알 수 있다.
CG->HI >> CG->I 의 augmentation 속성으로 CG->CGI 인것을 알 수 있고 CG->H 는 augmentation 속성으로 CGI->HI 인 것도 알 수 있다. 따라서 CG->CGI , CGI->HI 이므로 transitivity 속성을 이용해 CG->Hi 인것까지 구해낼 수 있다.
F+를 구하는 알고리즘을 간략하게 말하면 우선 reflexivity 와 augmentation의 속성들을 다 찾아서 더한 후에
transitivity의 속성을 원래 F와 추가된 속성에서 찾아내서 더이상의 f+에 덜할 것이 없을때까지 반복문을 돌리는 것이다.
attribute가 n개 라면 2^2n의 개수가 나올수 있어 알고리즘 수행시간은 O(2^n)이다.
이때까지 했던 것은 "Closure of Functional Dependency" 였다. 이제 "Closure of Attribute Sets"에 대해서 알아보자.
attribute set이 a 라고 한다면 a로 부터 도달할 수 있는 모든 것들을 a+라고 한다.
예) R = { A,B,C} // F = {A->B, B->C}라고 한다면 A+는 {A,B,C} 인 것이다.
이때 a+가 R가 똑같다면 a 는 그 relation의 key 라고 한다!
이것에 대한 알고리즘은 간략하게 말하자면 a 로 부터 도달 가능한 것들을 result라고 하고 a를 먼저 result 에 넣어준다. 반복문을 돌 때 b가 현재 result에 있고 b->r의 관계를 발견한다면 result에 r도 추가시키는 것이다. 이것의 수행시간은 n+n-1+,,+1 = O(n^2) 이다.
ex) R = ( A,B,C,G,H,I ), F = { A->B, A->C, CG->H, CG->I, B->H }
(AG)+ 는
1. result = AG
2. result = ABCG ( A->C and A->B )
3. result = ABCGH ( CG->H and CG는 AGBC 에 속한다. )
4. result = ABCGHI ( CG->I and CG는 AGBCH 에 속한다.)
AG는 candidate key 인가 >> super key 는 맞으나 A와 G 각각이 key 가 아니라면 candidate key 의 조건 까지 만족한다.
Attribute Closure 를 사용하는 것은 슈퍼 키인지 판단하거나 Functional dependencies를 만족하는지 판단 할 때 사용한다.
Lossless-join Decomposition
Lossless-join을 만족시키려면 위의 사진처럼 둘 중 하나의 조건은 만족해야한다.
만약 r( A, B, C, D) 라면 (A,B)//(C,D) 이렇게 는 분해 할 수 없다.
(A,B)//(A,C,D) -->> 이렇게 decomposition을 하고 A 가 R1 가 R2에서 key의 역할을 하고 있어야한다ㅏ.
첫 번째 분해 시에 (A,B) 와 (B,C) 로 하면 R1과 R2의 교집합인 B이고 B는 R2에 속하기 때문에 Lossless를 보장하고 있다.
추가적으로 FD를 각각의 relation을 join 하지 않고 각각으로 검사가 가능하기 때문에 Dependency preserving 또한 보장된다.
하지만 B->R 이 아닌 상태에서 키의 역할을 하고 있기 때문에 BCNF는 아니다.
두 번째 분해는 (A,B) (A,C)로 하면 두 테이블의 교집합인 A가 R1에 속하기 때문에 lossless는 보장한다.
추가적으로 각각의 릴레이션을 조인하지 않고 FD를 검사하는 것은 불가능하기 때문에 Dependency preserving은 보장하지 않는다.
마지막으로 두 relation의 key인 A가 A->R이기 때문에 BCNF는 만족한다.
Dependency Preservation
Ri 의 FD 를 Fi 라고 할 때, DP가 보장된다는 것은
위 사진의 조건을 만족한다는 것이다. 즉 각각의 릴레이션에 대한 functional dependency를 모으면 F+가 만들어진다는 것.
만약 DP가 보장이 안된다면 = 이 아닌 ⊆ 의 형태일 것이다.
위의 사진을 설명하자면 JK->L 이므로 JK->JKL 따라서 JK->R 이다. 즉 JK 는 이 릴레이션의 KEY이다.
또한 L->K, JL->JK, JL->JKL의 과정을 거쳐서 JL->R인 것을 확인할 수 있어 JL도 이 릴레이션의 KEY이다.
KEY = [J,K] 로 L->K의 조건때문에 L 은 KEY가 아닌데 왼쪽에 위치하여 이 릴레이션은 BCNF가 아닌 것을 알 수 있다.
Decomposition을 해야하므로 L->K의 조건으로 a->b 일때 a교집합b 와 R-(b-a)로 분해하면
R1=(J,L) R2=(L,K)로 분해된다. 이때 key 들이 fd의 왼쪽에 위치하고 있기에 BCNF 이지만 조인을 하지 않고서는 FD를 검사할 수 없기 때문에 DP를 만족한다고 볼 수 없다.
따라서 분해 전의 상황을 보면 r(J,K,L) 일때 JK->L L->K 일때 JK->K transitivity 속성을 이용한 것이 아니기때문에 3NF는 만족한다고 볼 수 있다.
📌BCNF : lossless 만족, key들은 FD의 왼쪽에 있어야함, DP는 보장되지 못할 수도 있다
이전에 배웠었던 instructor 와 department 스키마를 combine한 schema가 있다고 가정해보자.
우리는 이전에 배웠던 스키마가 더 좋은 스키마라고 알고있다. 그러면 지금 이 big_instructor 스키마를 어떨때 decomposition 하는 것이 맞는지 그리고 어떻게 decompositon 하는 것이 맞는지에 대해 알아보려고한다.
그전에 잠시 functional dependency에 이야기해보자.
💡Functional Dependency
관계형 데이터베이스의 설계에서 중복된 데이터가 최소화되도록 데이터베이스의 구조를 결정하는 것을 정규화 (normalization)라고 한다. 정규화된 데이터베이스가 그렇지 않은 데이터베이스에 비하여 더욱 효율적으로 데이터에 대한 연산을 수행할 수 있는 것은 매우 당연한 것이다. 이러한 데이터베이스의 정규화 과정에서 'Functional Dependency'이라는 개념은 매우 중요하게 이용된다.
Functional Dependency은 수학에서의 함수와 같이 두 필드의 집합이 many-to-one 관계로 사상되는 것을 말한다. 즉, 함수와 같이 어떠한 값을 통해 종속 관계에 있는 다른 값을 유일하게 결정할 수 있다는 것이다. 데이터베이스에서의 함수 종속성을 더욱 명확하게 정의하면 다음과 같다.
어떤 테이블 RR에 존재하는 필드들의 부분집합을 각각XX와YY라고 할 때,XX의 한 값이YY에 속한 오직 하나의 값에만 사상될 경우에 "YY는XX에 함수 종속 (YYis functionally dependent onXX)"이라고 하며,XX→YY라고 표기한다.
예를 들어, 테이블에 [생일]과 [나이]라는 필드가 존재할 경우에 [나이] 필드는 [생일] 필드에 함수 종속이다. 즉, 생일을 알고 있다면, 나이에 대한 필드를 참조하지 않거나, 아예 필드를 유지하지 않아도 나이를 결정할 수 있다. 데이터베이스 설계 단계에서 함수 종속 관계에 있는 필드를 찾는다면, 그 만큼 중복된 데이터를 줄일 수 있다. 그러므로, 데이터베이스 설계 단계에서 각 정보들 간의 함수 종속 관계를 찾는 것은 매우 중요하다.
중복이 일어난 현상 자체를 금지하는 것이 아닌 어떤 relation이 적법한 지 정의하는 constraint를 Functional Dependencies이라고 하는 것이다. 즉 현상에 집중하는 것이 아니라 Rule에 집중한다고 보면 된다.
- Functional Dependencies require that the value for a certain set of attributes determines uniquely the value for another set of attributes. ( 어떤 attributes set은 다른 attributes set을 uniquely 하게 결정한다. )- A functional dependency is a generalization of the notion of a key. (f-d 는 일종의 key 의 개념의 일반적인 형태 == key 는 일종의 functional dependecy 이다. ) >> key에 속하는 attribute가 relation 에 있는 모든 다른 값을 결정하기 때문에 functional dependency의 일종이라고 할 수 있다.
+ Use of Functional Dependencies
: 모든 functional dependencies의 set을 "F" 라고 가정할 때, F는 두 가지로 사용될 수 있습니다.
(1) 어떤 relation 을 검사하기 위해 F 사용
(2) 사전에 relation을 정의시에 모든 F를 만족해야 생성이 가능하게 하기 위해 F 사용
Functional Dependency의 특징
Trivial : 만약 b가 a 에 속하는 속성일 때, a->b 는 trivial하게 만족한다고 볼 수 있다.
Closure : 주어진 FD 속성에서 Trivial 한 속성을 제외하고 추론을 통해 얻을 수 있는것을 closure한다고 한다.
>> 주어진 FD에서 유도할 수 있는 모든 FD를 closure 라고 하는 것.
>> closure한 속성과 trivial한 속성을 모두 합쳐놓은 집합을 F+ 라고 하고 F+ 는 F 의 superset이다.
+ F+를 구하는 과정은 O(2^n)time
Armstrong's Axioms
reflexivity: 만약 Y가 X의 부분집합이면, X→Y이다. ( Trivail 속성 )
augmentation: 만약 X→Y이면, XZ→YZ이다.
transitivity: 만약 X→Y이고 Y→Z이면, X→Z이다.
three rules are sound and complete
( 위의 규칙 세 개를 통해 나온 것은 언제나 true 이고, 3개의 규칙만 있으면 closure에 포함되어야하는 모든 FD 찾을 수 있다.)
union: 만약 X→Y이고 X→Z이면, X→YZ이다.
decomposition: 만약 X→YZ이면, X→Y이고 X→Z이다.
pseudotransitivity: X->Y 이고, YZ->A 이면 XZ -> A 이다.
잠시 functional dependency 에 대한 설명을 적었다. 다시 big_instructor의 내용으로 돌아와보자.
이 스키마에는 dept_name 이 정해지면 building 과 buget이 무엇인지 결정된다.
따라서 "Functional Dependency" 는
dept_name ---> building, budget 이라고 선언할 수 있다.
이때 dept_name 은 candidate key 가 아니기 때문에 key 가 가지고 있는 unique한 속성을 지킬 필요가 없어져서
building과 budget이 중복될 수 있음을 시사한다. 이럴때 decomposition은 필요한 것이다.
Lossy Decomposition
decomposition 시에 가장 조심해야할 부분은 원래 스키마에서 decomposition한 스키마들을 다시 조인할 시에 원래 테이블에 있던 정보와 동일해야한다. 만약 동일하지 않고 쓸데 없는 정보가 추가되는 현상을 "Lossy Decompositon" 이라고 한다.
즉 위의 사진처럼 decomposition 한 테이블을 조인한다면 name attribute 를 통해 조인을 하게되고, name은 key 의 역할을 할 수 없어서 원래 테이블과 동일한 테이블을 만들어내지 못합니다. 즉, "lossy decomposition" 이 일어났다고 보면 됩니다.
💡Lossless-join Decomposition
위에서 설명했던 lossy decomposition 과 반대되는 개념의 용어가 바로 "Lossless-join Decomposition" 이다.
다시 말해 decomposed 된 relationdmf 다시 join 했을 때 원래 relation이 나오는 것을 뜻한다.
💡1NF = First Normal Form
1NF는 각 로우마다 컬럼의 값이 1개씩만 있어야 합니다. 이를 컬럼이원자값(Atomic Value)를 갖는다고 합니다. 예를 들어, 아래와 같은 경우 Adam의 Subject가 Biology와 Maths 두 개 이기 때문에 1NF를 만족하지 못합니다.
즉, 추가적으로 이전에 배웠던 E-R Diagram에서 multi valued는 1NF를 만족하지 못함을 알 수 있습니다.
위의 정보를 표현하고 싶은 경우 이렇게 한 개의 로우를 더 만들게 됩니다. 결과적으로 1NF를 함으로써 데이터 redundancy는 더 증가하였습니다. 데이터의 논리적 구성을 위해 이 부분을 희생하는 것으로 볼 수 있습니다.
하지만 이렇게 atomic 하게 바꾸면 student age의 중복 값이 생긴 것을 확인할 수 있습니다. 즉 만약 student가 key 의 역할을 하고 있었다면 key 역할을 상실하게 되는 것을 확인할 수 있습니다.
즉 1NF는 Domain의 값이 atomic 해야하고 그
의미는 모든 테이블의 각각의 key를 가지고 있다는 의미와도 같음을 확인할 수 있습니다.
앞으로 우리가 배우는 모든 relation(=table) 들은 1NF는 무조건 만족해야한다고 가정하면서 나가겠습니다.!
추가적으로
Atomicity는 우리가 도메인의 요소들을 어떻게 사용하느냐에 달려있습니다.
예를 들어 주민번호를 주민번호 그 자체로만 사용한다면 atomicity를 만족하지만 생년월일의 정보만 사용하게된다면 divide를 해야하므로 non-atomicity 의 속성임을 확인할 수 있습니다.
따라서 주어진 정보를 application 입장에서는 그대로 이용하는 것이 좋습니다. 정보를 쪼개려고 한다면 Database 측면에서는 multivalue라고 인식하고 non atomicity이기 때문입니다.
>> Doing so is a bad idea : leads to encoding of information in application program rather than in the database.
💡BCNF ( Boyce-Codd Normal Form )
앞서 1NF : all domains are atomic == every relation should have a key 의 조건을 만족하는 것이었다.
BCNF는 1NF의 속성을 다 만족해야함과 동시에 " key를 제외한 다른 attribute는 FD를 통해 또 다른 attribute를 결정하면 안된다 " 라는 조건도 만족해야한다. 즉 FD 에. a->b 가 만족한다는 Rule 이 있다면 "a" 는 반드시 relation의 superkey 여야하는 것이다.
따라서 위에서 봤던 예제인 big_instructor에서 dept_name -> building, budget 의 rule은 big_instructor의 테이블이 BCNF를 만족하지 못하게 하는 것이다. ( dept_name이 super key 가 아니기 때문에..)
정리하면 BCNF가 되기 위해선
1. a-> b is trivial ( b는 a 에 포함)
2. a is super key for R
💡Decomposing a Schema into BCNF
스키마가 위에 언급했던 조건들을 위배한다면 조건들을 만족하여 BCNF를 만족하는 테이블을 만들기위해 decomposition을 해야합니다.
decompose 방법은 다음과 같습니다.
BCNF을 만족하지 않는 조건이 F 에서 a->b 라고 할 때
( a union b ) ( R - ( b - a ) )
위의 두 개의 테이블로 decomposition 하면 됩니다.
앞에서 계속 언급했던 예제로 한번 decomposition을 해본다면
dept_name -> building, budget 때문에 big_instructor가 BCNF 가 아니었다 따라서
a = dept_name, b = building, budget
R1 : ( a union b ) = ( dept_name, building, budget )
각각은 BCNF를 만족하고 Lossless join decomposition 인지만 확인한다면 제대로 된 분배였을 것입니다.
lossless 인지는 뒤에서 설명하도록 하겠습니다. 그전에
💡 BCNF and Dependency Preservation
어떤 attribute 관계에 대해 FD 를 사용자가 정의하고, table 을 decomposition 한 상태일 때,
각각의 relation만 가지고 (join을 하지 않은 상태 ) 모든 FD를 검사할 수 있는 상황을 " Dependency Preservation " 이라고 한다.
BCNF는 항상 Dependency Preservation을 만족하지는 않는다. 왜냐하면 조건들이 너무 까다로워서 decomposition 이 많이 일어나고, 따라서 FD를 검사하기 위해서는 테이블간의 join이 불가피한 상황이 일어날 수 있기 때문이다.
따라서 BCNF를 만족할 것이냐 Dependency Preservation을 만족할 것이냐 기로에 서있을때,
Dependency Preservation을 만족하는 것을 "3NF " 라고 한다.
💡3NF
trivial 하고 dependency preservation 을 만족하는 것
또 다른 말로
Transitivity Dependecy 가 없는 것이라고도 할 수 있다.
Transitivity Dependecy 는 a->b 이고 b->c 일때 a->b->c 의 관계가 성립하고 그때 a->c 를 알 수 있다.
즉 가운데에 있는 b를 통해 a->c 의 관계가 성립되는 것을 말한다. 만약 b 가 없이 a->c 의 관계가 성립한다면
transitivity dependency 가 성립하지 않고 3NF를 만족한다고 보면된다.
ex1
F = { ID -> dept_name, dept_name -> building, budget }
ID -> dept_name -> building, budget 으로 id -> building budget
즉, dept_name 이 없다면 관계가 성립하지 않기때문에 transitivity dependency를 만족한다.
다른 말로는 3NF는 만족하지 않는 것.
ex2
F = { dept_name, s_id -> i_id, i_id-> dept_name}
dept_name, s_id ->. i_id -> dept_name 이지만 i_id 가 없다고 하더라도 dept_name, s_id -> dept_name 은 trivial 관계로 설명 가능하다. 즉 transitivity dependency 는 성립하지 않고, 3NF 는 성립한다고 볼 수 있는 것.
Goals of Normalization
each relation scheme is in good form
the decomposition is a lossless-join decomposition
preferably, the decomposition should be dependency preserving.
