정규화

1. 릴레이션 스키마 설계 지침

 

① 릴레리션 애트리뷰트들의 의미

∘릴레이션 스키마를 형성하기 위해 애트리뷰트를 집단화 할 때는 각각의 애트리뷰트들이 실세계에서 어떤 의미를 가져야 하며, 그에 합당하는 적절한 해석을 가져야 함 ∘즉 설계자는 데이터베이스에 포함될 전체 애트리뷰트들을 대상으로 실세계에서 어떤 연관성이 있는 애트리뷰트들을 묶어서 하나의 릴레이션 스키마를 만들어 나감 ∘여러 엔티티(예를 들면 EMPLOYEE, DEPARTMENT, PROJECT 등)의 애트리뷰트들이 하나의 릴레이션에 혼합되면 안됨 ∘다른 엔티티를 참조하기 위해서는 외래키 만을 사용해야 함 [그림 1] 단순화된 COMPANY 관계 데이터베이스 예 ∘지침) 의미가 쉽게 전달되도록 릴레이션 스키마를 설계한다. 여러 개의 엔티티 타입과 관계 타입의 애트리뷰트를 섞어서 하나의 릴레이션을 구성하면 안 된다. 직관적으로, 하나의 릴레이션 스키마가 하나의 엔티니 타입이나 하나의 관계 타입에 대응된다면, 그 의미를 설명하기사 쉽다. 그렇지않고, 여러 개의 엔티티 타입과 관계 타입이 한 릴레이션에 섞이게 되면, 의미가 모호하게 되고 릴레리션을 쉽게 설명할 수 없다.

 

② 투플에서 중복된 정보와 갱신 이상

∘하나의 릴레이션에 하나 이상의 엔티티의 애트리뷰트들을 혼합하는 것은 여러 가지 문제를 일으킬 수 있는데, 우선 정보가 중복 저장되며, 저장 공간을 낭비하게 되고, 또한 갱신 이상이 발생하게 되는데, 이것은 동일한 정보를 한 릴레이션에는 변경하고, 나머지 릴레이션에서는 변경하지 않은 경우 어느 것이 정확한지 알 수 없게 됨을 말함 ∘갱신 이상(update anomaly)의 종류에는 삽입 이상, 삭제 이상, 변경 이상이 있음 - 삽입 이상 (insertion anomalies)이란 예를 들어 EMP_DEPT에 객체를 삽입할 때 부서가 정해지지 않은 직원이나 직원이 없는 부서를 insert 하는데 문제가 발생함 - 삭제 이상 (deletion anomalies)이란 예를 들어 부서의 마지막 직원을 삭제하면 부서 정보도 없어짐 - 변경 이상 (modification anomalies)이란 예를 들어 부서 정보를 변경하면 부서의 모든 직원 투플에서 동일하게 변경해야 함 [그림 2] 갱신 이상이 발생하는 두 릴레이션 스키마 ∘위의 EMP_DEPT 릴레이션에서는 특정부서를 표현하는 애트리뷰트 값(DNUMBER, DNAME, DMGRSSN) 들이 그 부서에서 일하는 모든 사원 정보에 중복되어 저장됨 ∘위의 EMP_PROJ 릴레이션에서는 SSN에 따른 ENAME이 중복되고, PNUMBER에 따른 PNAME, PLOCATIONS의 정보가 중복되어 저장됨 ∘지침) 릴레이션에서 삽입, 삭제, 또는 수정 이상이 생기지 않도록 기본 릴레이션 스키마를 설계한다. 만약 어떤 이상이 존재하면, 그것을 잘 이해하여 데이터베이스를 수정하는 프로그램들이 올바르게 동작할 수 있도록 작성한다.

 

③ 투플의 널값

∘릴레이션의 투플들이 널 값을 가지지 않도록 설계해야 함 - 널 값은 저장 단계에서 공간을 낭비하게 됨 - 논리적 차원에서는 조인 연산들을 지정하기 어려움 - 애트리뷰트들의 의미를 이해하기 어려움 - COUNT나 AVG와 같은 집단 함수들이 적용되었을 때 널 값의 해석이 모호함 ∘모든 널 값을 동일하게 표현하면 널 값이 갖는 여러 의미를 훼손하게 됨 ∘널값의 방지 기법은 널 값이 많이 나타나는 애트리뷰트들은 별개의 릴레이션으로 분리함 ∘예를 들어, 사원들 중에 10%만이 개인 사무실을 가지고 있는 경우에 office_no라는 애트리뷰트를 Employee에 추가하지 말고, Emp_office라는 새로운 릴레이션을 만드는 것이 office_no의 널값을 가지지 않도록 설계하는 기법임 [그림 3] 널값 방지를 위해 Emplyee 릴레이션의 분리 ∘지침) 널값을 자주 가질 수 있는 애트리뷰트를 가능한 한 기본 릴레이션의 애트리뷰트로 포함하지 않는다. 만약 널값을 포함할 수밖에 없다면 예외적인 경우에만 포함하고 대다수 투플들에 대해서는 널값이 없도록 한다.

※ 널(null) 값의 의미

∘널 값은 다음과 같이 여러 가지로 해석이 가능함 - 애트리뷰트가 해당 투플에는 적용되지 않음 (존재 여부를 모름) - 투플에서 애트리뷰트의 값이 아직 알려져 있지 않음 (존재하지만 모름). - 애트리뷰트 값이 알려져 있지만 DB에 기록되지는 않았음

③ 가짜 투플의 생성

∘관계 데이터베이스 설계를 잘못하게 되면, 조인 연산들이 틀린 결과를 생성할 수 있음 ∘조인 연산의 결과가 올바르기 위해서는, 릴레이션들이 “무손실 조인(lossless join)” 조건을 만족하도록 설계되어야 함 [그림 4] EMP_PROJ에 대한 나쁜 설계 : (a) [그림 2]의 EMP_PROJ를 두 개의 릴레이션 스키마 (EMP_LOCS와 EMP_PROJ1)로 표현 (b) [그림 2] EMP_PROJ 릴레이션을 EMP_LOCS 와 EMP_PROJ1 릴레이션의 애트리뷰트들 상에 프로젝트 한 결과 [그림 5] EMP_PROJ1, EMP_LOCS의 실선 윗부분 자연조인 적용 결과 (*는 가짜 투플) ∘지침) 가짜 투플들이 생성되지 않도록 하기 위해서, 기본키나 외래키 애트리뷰트를 가지고 동등 조건으로 조인할 수 있는 릴레이션 스키마를 설계한다. (외래키, 기본키) 조합을 제외하고 릴레이션들이 대응하는 애트리뷰트(match attributes)들을 가지지 않도록 한다. 왜냐하면 그러한 애트리뷰트에 대한 조인은 가짜 투플을 생성하기 때문이다.

---

2. 함수적 종속성

 

① 함수 종속성의 정의

∘X와 Y를 임의의 애트리뷰트들의 집합이라고 할 때, X의 값이 Y의 값을 유일하게(unique) 결정한다면 “X는 Y를 함수적으로 결정한다(functionally determines)”라고 함 ∘X → Y로 표기하고, “Y는 X에 함수적으로 종속된다” 라고 함 ∘함수적 종속성은 모든 릴레이션 인스턴스 r(R)에 대하여 성립해야 함 ∘함수적 종속성의 검사 방법은 릴레이션 인스턴스 r(R)에 속하는 어떠한 임의의 두 투플에 대해서도 속성들의 집합 X에 대해 동일한 값을 가질 때마다 Y에 대해서도 동일한 값을 가진다면 X → Y라는 함수적 종속성이 성립함 ∘즉, r(R)에서의 임의의 두 투플 t1과 t2에 대해 t1[X] = t2[X]이면, t1[Y] = t2[Y] 임 ∘함수 종속성는 특정 릴레이션 인스턴스보다는 실세계에서 존재하는 애트리뷰트들 사이의 제약조건으로부터 유도됨 ∘함수 종속성 제약조건의 예제 - 주민등록번호는 사원의 이름을 결정함 SSN → ENAME - 프로젝트 번호는 프로젝트 이름과 위치를 결정함 PNUMBER → {PNAME, PLOCATION} - 사원의 주민등록번호와 프로젝트 번호는 그 사원이 일주일동안 그 프로젝트을 위해서 일하는 시간을 결정함 {SSN, PNUMBER} → HOURS ∘함수 종속성은 릴레이션 스키마(내연) R의 특성이지, R의 어떤 특정 적법한 릴레이션 상태(외연)r의 특성은 아님 ∘따라서 함수 종속성은 주어진 릴레이션 r로부터 자동적으로 추측할 수 있는 것이 아니라 R의 애트리뷰트들의 의미를 아는 사람이 명시적으로 정의해야 함 ∘한 릴레이션 투플 t1, t2가 있다면, t1[K] = t2[K]인 서로 다른 두개의 투플이 존재하지 않기 때문에, K가 R의 키이면 K는 R의 모든 애트리뷰트들을 함수적으로 결정함 ∘앞의 [그림 2]이 EMP_DEPT 및 EMP_PROJ의 화살표그림은 함수적 종속성을 그림으로 표현한 것임

 

② 함수적 종속성(FD)의 추론 규칙

∘설계자는 주어진(알려진) FD의 집합 F로서, 추가로 성립하는 FD들을 추론할 수 있음 ∘암스트롱의 추론 규칙 - IR1. (재귀성 규칙) Y ⊆ X이면, X → Y - IR2. (부가성 규칙) X → Y이면, XZ → YZ - IR3. (이행성 규칙) X → Y이고 Y → Z이면, X → Z ∘IR1을 각 애트리뷰트 집합이 항상 자신이나 자신의 임의의 부분집합을 결정한다는 것으로 이것은 명백하며, IR2는 동일한 애트리뷰트 집합을 함수적 종속성의 왼편과 오른편에 붙이는 것인데, 이것도 역시 명백히 성립하고, IR3에 따르면 합수적 종속성을 이행적임 ∘추가적으로 유용한 추론 규칙 - IR4. (분해 규칙) X → YZ이면, X → Y이고 X → Z - IR5. (합집합 규칙) X → Y이고 X → Z이면, X → YZ - IR6. (의사이행성 규칙) X → Y이고 WY → Z이면, WX → Z ∘IR4는 함수적 종속성의 오른쪽에서 애트리뷰트를 제거할 수 있다는 것이며, IR5는 분해규칙의 역인 합집합 규칙도 성립함 ∘FD의 집합 F의 폐포(closure) : F+ - F로부터 추론할 수 있는 모든 가능한 함수적 종속성들의 집합 ∘F하에서 속성 집합 X의 폐포(closure of X under F) : X+ - 함수적 종속성 집합 F를 사용하여 X에 의해 함수적으로 결정되는 모든 애트리뷰트들의 집합 - 예) F = SSN→ENAME, PNUMBER→PNAME, PLOCATION, SSN, PNUMBER→HOURS 알고리즘을 사용하여 F하에서 다음과 같은 폐포 집합들을 구할 수 있음 SSN+=SSN, ENAME PNUMBER+ = PNUMBER, PNAME, PLOCATION SSN, PNUMBER+ = SSN, PNUMBER, ENAME, PNAME, PLOCATION, HOURS - F하의 X의 폐포 X+를 구하는 알고리즘 X+ := X; repeat oldX + := X+; for each functional dependency Y → Z in F do if Y ⊆ X+ then X+ := X+ ∪ Z; until (oldX+ = X +);

③ 함수적 종속성 집합의 동등성과 종속성의 최소집합

∘커버(cover)라는 용어의 정의 - E의 모든 FD가 F로부터 추론될 수 있다면(E+⊆F+), "F가 E를 커버(cover)한다" 표현함 ∘두 FD 집합의 동등성 정의 - FD의 집합 E와 F에 대하여, F의 모든 FD가 E로부터 추론될 수 있고, E의 모든 FD가 F로 부터 추론될 수 있으면 “E와 F는 동등하다(equivalent)” 라고 표현함 - F와 E가 다르더라도 F+ = E+이면 F와 E는 동등함 - F가 E를 커버하고 E가 F를 커버하면 F와 E는 동등함 ∘다음 세 조건을 만족하는 함수적 종속성들의 집합 F의 최소(minimal)라고 정의함 - F의 모든 함수적 종속성들의 오른쪽편 애트리뷰트가 하나임 - F로부터 어떤 함수적 종속성을 제거했을 때, F와 동등한 함수적 종속성들의 집합이 될 수 없음 - F에서 X→A를 X의 진부분집합 Y에 대하여 Y→A로 교체했을 때, F와 동등한 함수적 종속성들의 집합이 될 수 없음 ∘함수적 종속성의 최소집합은 중복이 없는 표준형(standard form) 도는 규준형(canonical form)이라고 생각할 수 있음 ∘함수적 종속성들의 집합 F의 최소 덮개(minimal cover)는 F와 동등한 함수적 종속성들의 최소 집합 Fmin을 의미함 ∘함수적 종속성들의 최소 덮개는 여러 개 존재할 수 있음 ∘또한, 임의의 함수적 종속성들의 집합 F에 대해 알고리즘을 사용하여 적어도 하나의 최소 덮개를 구할 수 있다 ∘함수적 종속성 집합 E에 대한 최소 커버 F를 구하는 알고리즘 ① Set F := E. ② Replace each functional dependency X→{A1,A2,...,An} in F by the n functional dependencies X→A1,X →A2,...,X→An. ③ For each functional dependency X→A in F for each attribute B that is an element of X if {{F-{X→A}} U {(X-{B})→A}} is equivalent to F, then replace X→A with {X-{B}}→A in F. ④ For each remaining dependency X→A in F if {{F-{X→A}} is equivalent to F, then remove X→A from F.

---

3. 기본 정규형

 

① 정규화의 의미

∘정규화(normalization)란 불만족스러운 “나쁜” 릴레이션의 애트리뷰트들을 나누어서 더 작은 “좋은” 릴레이션으로 분해하는 과정을 말함 ∘Codd(1972)가 처음 제안한 정규화 과정은 어떤 릴레이션 스키마가 어떤 정규형을 만족하는지 확인하는 일련의 테스트였음 ∘정규형(normal form)는 특정 조건을 만족하는 릴레이션 스키마의 형태를 말함 ∘정규형에서 제2 정규형, 제3 정규형, BCNF은 한 릴레이션 스키마의 애트리뷰트 사이에 함수 종속성(FD)을 기반으로 정의되었으며, 제 4정규형은 키와 다치 종속성(MVD) 개념을 기반으로 정의되었고, 제5 정규형은 조인 종속성(JD) 개념을 기반으로 정의되었음 ∘정규화(Normalization)의 원칙 - 정규화 ＝ 스키마 변환 (S→S') ① 정보의 무손실 표현(nonloss representation of information) - 같은 의미의 정보 유지해야 하며 구조상으로는 더 바람직한 형태가 되어야 함 ② 최소의 데이터 중복성(minimal data redundancy) 허용 - 중복으로 인한 이상을 제거할 수 있기 때문임 ③ 분리의 원칙(principle of separation) - 하나의 독립된 관계성은 하나의 릴레이션으로 분리시켜 표현한다는 것

 

※ 정규화의 필요성과 좋은 데이터베이스 설계의 추가적인 조건

∘정규화는 다음과 같은 이유로 그 필요성의 의미를 찾을 수 있음 - 설계된 모든 릴레이션은 동등(평등)하지 않음 - 잘못 설계된 릴레이션은 관계 연산시에 발생하는 이상(anomaly) 현상을 제거하기 위해 제약조건을 릴레이션 설계시에 반영해야 함 ∘좋은 데이터베이스 설계를 보장하기 위해서는 정규화 외에 추가적인 조건들이 필요함 - 종속성 보존 특성(dependency preservation property) - 무손실 조인 특성(lossless join property)

② 제1 정규형 (1NF, First Normal Form)

∘복합 애트리뷰트(composite attribute), 다치 애트리뷰트(multivalue attribute), 그리고 중첩 릴레이션(nested relation) 등 비원자적(non-atomic) 애트리뷰트들을 허용하지 않은 릴레이션의 형태 - 애트리뷰트의 도메인이 오직 원자값(atomaic value)들만 포함하고, 투플의 모든 애트리뷰트 값은 그 애트리뷰트 도메인에 속하는 하나의 값이어야 함 - '릴레이션 안의 릴레이션‘, ’애트리뷰트 값들로서의 릴레이션‘은 허용치 않음 ∘제1 정규형이 아닌 릴레이션 스키마 및 릴레이션 인스턴스의 예는 다음 그림과 같음 - 즉 릴레이션 DEPARTMENT의 DLOCATIONS 애트리뷰트에는 원자값이 아닌 세 개의 값{Bellaire, Sugarland, Houston}을 볼 수 있음 - 릴레이션의 각 애트리뷰트는 기본키 DNUMBER에 함수적으로 종속되어 있음 [그림 6] 제1 정규형이 아닌 릴레이션 스키마 및 그 인스턴스의 예 ∘릴레이션 DEPARTMENT에서 비원자적 요소를 단순하게 원자값으로 변형하여 제1 정규형 버전으로 변형할 경우 다음과 같이 기본키 DNUMBER의 중복현상을 초래함 - 이 경우 기본키를 {DNUMBER, DLOCATIONS}로 할 경우 중복데이터가 발생하기 때문에 DLOCATIONS 애트리뷰트를 제거하여 별도의 릴레이션 {DNUMBER, DLOCATIONS} 을 구성하는 것이 바람직함 [그림 7] 중복이 포함된 제1 정규형 릴레이션

 

③ 제2 정규형(2NF, Second Normal Form)

∘제2 정규형은 함수 종속성(FD)과 기본 키 개념을 기반에 둠 ∘제2 정규형의 정의 - 릴레이션이 제1 정규형을 만족하고, 키에 속하지 않는 애트리뷰트들은 모두 기본키에 완전 함수 종속이 될 경우에 제2 정규형에 속함 - 완전 함수적 종속성(full functional dependency): FD Y → Z에서 Y의 어떤 애트리뷰트라도 제거하면 더 이상 성립하지 않는 경우를 말함 ∘제2 정규형 예제 - {SSN, PNUMBER} → HOURS는 SSN → HOURS와 PNUMBER → HOURS가 성립하지 않기 때문에 완전 함수적 종속성임 - {SSN, PNUMBER} → ENAME은 SSN → ENAME이 성립하기 때문에 완전 함수적 종속성이 아님, 이것은 부분 함수 종속성(partial function dependency)이라고 칭함 - 릴레이션 스키마 R의 모든 비 기본(non-prime) 애트리뷰트들이 기본키에 대해서 완전 함수적 종속이면, R은 제2 정규형(2NF)에 속함 [그림 8] EMP_PROJ를 제 2 정규형으로 정규화

 

※ 제2 정규형의 무손실 분해

∘무손실 분해(nonloss decomposition) - 프로젝션하여 분해된 릴레이션들은 자연 조인을 통해 원래의 릴레이션으로 복귀 가능 - 원래의 릴레이션에서 얻을 수 있는 정보는 분해된 릴레이션들로부터도 얻을 수 있음. 그러나 그 역은 성립하지 않음 ∘Heath의 무손실 분해 - R(A,B,C)에서 함수 종속 A→B가 성립하면 ⇒ R1(A,B), R2(A,C) 로 무손실 분해 가능

④ 제3 정규형(3NF, Third Normal Form)

∘제3 정규형은 이행적 종속성의 개념에 그 기반을 두고 있음 ∘제3 정규형의 정의 - 릴레이션 스키마 R이 제2 정규형을 갖고 R의 어떤 비 기본 애트리뷰트도 기본키에 대해서 이행적으로 종속되지 않으면 릴레이션 R은 제 3 정규형을 갖는다고 함 . 이행적 함수적 종속성(transitive functional dependency): 두 FD Y → X와 X → Z에 의해서 추론될 수 있는 FD Y → Z . 예) SSN → DMGRSSN은 SSN → DNUMBER과 DNUMBER → DMGRSSN이 성립하기 때문에 이행적 함수적 종속성임 SSN → ENAME는 SSN → X이고 X → ENAME인 애트리뷰트 집합 X가 존재하지 않기 때문에 이행적 종속성이 아님 - 릴레이션 R은 정규화 과정에 의해서 항상 제3 정규형 릴레이션으로 분해될 수 있음 [그림 9] EMP_DEPT를 제3 정규형으로 정규화 ∘제2, 제3 정규형 일반적 정리 - 여러개의 후보 키를 가진 릴레이션들을 고려함 -릴레이션 스키마 R의 모든 비기본 애트리뷰트 A가 R의 모든 후보키에 완전 함수적 종속이면 R은 제2 정규형(2NF)을 갖는다고 함 - 릴레이션 스키마 R의 수퍼키(superkey): R의 후보키를 포함한 R의 애트리뷰트들의 집합 S릴레이션 스키마 R의 FD X → A가 성립할 때마다 (a) X 가 R의 수퍼키이거나 (b) A가 R의 기본 애트리뷰트이면 R은 제3 정규형(3NF)을 갖는다고 하며, 다음 절에 언급할 보이스 코드(Boyce-Codd) 정규형은 위의 조건중 (b)의 경우를 허락치 않는 정규형을 의미함 * 기본 애트리뷰트(prime attribute): 임의의 후보키 K의 멤버인 애트리뷰트

※ 제3 정규형의 약점

∘복수의 후보키를 가지고 있고, 후보키들이 복합 애트리뷰트들로 구성되고, 후보키들이 서로 중첩되는 경우에는 적용 불가능함⇒ 보다 일반적인 BCNF 형태를 제안함

⑤ 보이스-코드 정규형 (BCNF, Boyce-Codd Normal Form)

∘릴레이션 스키마 R에서 성립하는 임의의 FD X → A에서 X가 R의 수퍼키이면 R은 Boyce-Codd 정규형(BCNF)을 갖는다고 함 ∘각 정규형은 그의 선행 정규형보다 더 엄격한 조건을 갖는다. 즉, 모든 제2 정규형 릴레이션은 제1 정규형을 갖는다. 모든 제3 정규형 릴레이션은 제2 정규형을 갖는다. 모든 보이스-코드 정규형 릴레이션은 제3 정규형을 갖임 - 강력한 제3 정규형 ∘릴레이션의 모든 결정자가 후보키이면 보이스-코드 정규형이 됨 ∘제3 정규형이지만, 보이스-코드 정규형이 아닌 릴레이션의 예 - FD1: {STUDENT, COURSE} → INSTRUCTOR - FD2: INSTRUCTOR → COURSE ; 각 강사는 하나의 과목만 가르친다는 전제조건 - {STUDENT, COURSE}가 이 릴레이션의 기본 키이고, 다음과 같은 함수종속 다이어그램으로 표시할 수 있음 [그림 10] 제3 정규형이지만, BCNF가 아닌 함수종속 관계 ∘이것을 분해할 수 있는 세 가지 방법은 다음과 같음 - {STUDENT, INSTRUCTOR}와 {STUDENT, COURSE} - {COURSE, INSTRUCTOR}와 {COURSE, STUDENT, } - {INSTRUCTOR, COURSE}와 {INSTRUCTOR, STUDENT} ∘이 세 가지 분해는 모두 함수적 종속성 FD1을 잃어 버림 ∘가장 바람직한 분해는 가짜 투플이 생성치 않는 세 번째 방법임 - {INSTRUCTOR, COURSE}와 {INSTRUCTOR, STUDENT}

 

※ 기본키에 기반을 둔 정규형과 대응되는 정규화의 요약

정유형	검사	방법(정규화)
제 1 정규형	릴레이션은 비원자 애트리뷰트나 중첩 릴레이션을 가지지 않아야 함	각 비원자 애트리뷰트나 중첩 릴레이션에 대해 새로운 릴레이션을 만듬
제 2 정규형	복합키로 구성된 릴레이션에서 키가 아닌 애트리뷰트들은 기본키의 일부분에 함수 종속해서는 안됨	각 부분키와 이에 종속하는 애트리뷰트들에 대한 새로운 릴레이션으로 분해함
제 3 정규형	릴레이션에서 키가 아닌 애트리뷰트들이 키가 아닌 다른 애트리뷰트레 함수적으로 종속해서는 안됨. 키가 아닌 애트리뷰트들이 기본키에 이행적으로 종속해서는 안됨	키가 아닌 다른 애트리뷰트들을 함수적으로 결정하는 키가 아닌 애트리뷰트들을 포함하는 새로운 릴레이션으로 분해함

---

4. 진보된 정규형

 

① 제4 정규형(4NF) - 1

∘함수적 종속성은 하나의 공통된 형태의 제약조건을 명시하기 위해서 사용되며, 함수적 종속성 만에 의해서 명시될 수 없는 다른 형태의 제약조건들이 존재하는데, 이에 추가적인 종속성에는 다치 종속성(multi-valued dependency)이 있으며, 이 다치 종속성에 기반을 둔 정규형이 제4정규형(4NF)임 ∘정형적 정의 - 릴레이션 스키마 R에 대해, X와 Y는 R의 애트리뷰트들의 부분집합이다. 그리고 Z = R－(X ∪ Y) (남은 애트리뷰트들)이다. 릴레이션 스키마 R에서 성립하는 다치 종속성 X ↠ Y는 R의 임의의 인스턴스 r(R)에 대해, 만약 t1[X] = t2[Y]를 만족하는 r(R)의 두 투플 t1, t2가 존재한다면, 다음의 성질을 만족하는 두 개의 투플 t3와 t4도 반드시 존재해야 함 . t3[X] = t4[X] = t1[X] = t2[X] . t3[Y] = t1[Y]이고 t4[Y] = t2[Y] . t3[Z] = t2[Z]이고 t4[Z] = t1[Z] ∘MVD 제약조건은 Z의 값에 관계없이 X의 값이 Y의 값들의 집합을 결정한다는 것을 암시함 ∘MVD의 특성: X ↠ Y가 성립하면, X ↠ Z도 성립함 ∘애트리뷰트들의 집합 X의 값이 애트리뷰트들의 집합 Y의 값을 결정한다면, X는 Y를 다중결정한다(multidetermine)고 함 ∘MVD X ↠ Y가 “Y⊆X” 혹은 “(X∪Y) = R” 이면 단순 다치 종속성(trivial MVD)이라고 함 ∘단순 다치 종속성은 다치 종속성의 정의에 따라 항상 성립함 [그림 11] 다치 종속성과 제4 정규형 ∘EMP는 두 개의 다치 종속성을 가짐 : ENAME ↠ PNAME, ENAME ↠ DNAME ∘EMP 릴레이션을 제4정규형인 EMP_PROJECTS, EMP_DEPENDENTS 릴레이션으로 분해함

 

② 제4 정규형(4NF) - 2

∎함수적 종속성 및 다치 종속성의 추론 규칙 ∘함수적 종속성과 다치 종속성을 위한 건전(sound)하고 완전(complete)한 추론 규칙들의 집합 IR1. (FD의 재귀성 규칙): X⊇Y이면, X→Y 이다 IR2. (FD의 부가성 규칙): {X→Y} |= XZ→YZ IR3. (FD의 이행성 규칙): {X→Y, Y→Z} |= X→Z IR4. (MVD의 보완성 규칙): {X ↠ Y} |= {X ↠ (R－(X∪Y))} IR5. (MVD의 부가성 규칙): X ↠ Y이고 W⊇Z이면, WX ↠ YZ이다 IR6. (MVD의 이행성 규칙): {X ↠ Y, Y ↠ Z} |= X ↠ (Z－Y) IR7. (FD에서 MVD로의 모사 규칙): {X→Y} |= X ↠ Y IR8. (FD와 MVD의 합동 규칙): X ↠ Y이고, (a)W∩Y가 공집합,            (b) W→Z, (c) Y⊇Z인 W가 존재하면, X→Z이다 주의 - 규칙 IR7에 의해, 모든 FD는 MVD임 - 규칙 IR1에서 IR8를 적용하면 함수적 종속성들의 집합에 대한 폐쇄 F+를 유도 가능 ∎제 4 정규형의 특성: ∘3NF와 BCNF는 다치 종속성을 다루지 않음 ∘비 단순 다치 종속성을 가지는 릴레이션 스키마는 좋은 디자인이 아닐 수 있음 ∘제 4 정규형은 위와 같은 문제를 다루며, BCNF 정규형이 됨 (제 4 정규형에 속하는 모든 릴레이션은 BCNF 정규형에 속함) ∘제 4 정규형의 정형적 정의: - 종속성들의 집합 F에 대한 F+의 모든 비단순 다치 종속성 X ->> Y 에 대하여, X가 R의 수퍼키이면 릴레이션 스키마 R은 F에 대한 제 4 정규형임 ∎제4정규형 릴레이션으로의 무손실 조인 분해 ∘모든 MVD는 FD이므로, 제 4 정규형은 BCNF를 포함함 ∘F의 모든 종속성이 함수적 종속성이면, 4NF의 정의는 자동적으로 BCNF 정의가 됨 ∘릴레이션 R 상의 종속성의 집합 F에 대해 R을 제 4 정규형 릴레이션으로 무손실 조인 분해하는 알고리즘이 존재함 ∘특성 LJ1’: R의 분해집합 D = {R1, R2}가 종속성의 집합 F에 대해 무손실 조인 특성을 가질 필요충분조건은 다음의 둘 중 하나를 만족하는 것임 - 종속성 ((R1∩R2) ↠ (R1－R2))가 F+에 속함 - 종속성 ((R1∩R2) ↠ (R2－R1))가 F+에 속함

③ 제5 정규형(5NF, Project-Join NF: PJNF)

∘조인 종속성은 R에 지정된 조인 종속성은 JD(R1, R2, …, Rn)으로 표기하며, R의 상태 r에 대하여 “R의 모든 합법적 상태 r이 R1, R2, …, Rn으로의 무손실 조인 분해를 가져야 한다”는 점임 ∘다치 종속성은 n이 2인 특별한 경우로서 JD(R1, R2)로 표기하는 조인 종속성은 다치 종속성 (R1∩R2) ↠ (R1-R2) (또는 대칭성에 (R1∩R2) ↠ (R2-R1))를 의미한다. JD(R1, R2, …, Rn)에 있는 릴레이션 스키마 Ri중에 하나가 R과 동일할 경우, 릴레이션 스키마 R에 명시된 조인종속성 JD(R1, R2, …, Rn)은 무의미 조인 종속성이라 부름 ∘R이 함수적 종속성, 다치 종속성, 그리고 조인 종속성들의 집합인 F에 대해 모든 비 단순 조인 종속성 FD(R1, R2, …, Rn)가 F+에 속하고, Ri가 R의 수퍼키라면, R은 제5정규형에 속함 ∘프로젝트-조인 정규형(Project-Join NF: PJNF)이라고도 함 ∘조인 종속성을 발견하는 것은 매우 어려운 일로, 실제로 제5 정규형은 거의 쓰이지 않음 [그림 12] 프로젝션과 조인 (점선은 프로젝션, 실선은 조인) ∘만일 <S1,P1,C2>, <S2,P1,C1>, <S1,P2,C1>이 SPC에 포함되어 있으면, <S1,P1,C1>도 SPC에 포한되어야 한다는 제약 조건이 합법적으로 적용된다면, 이것은 시간에 독립적인 SPC의 제약 조건이며, 순환적 특징을 가지고 있는 제약 조건임 ∘3-분해 릴레이션 SPC가 어떤 프로젝션들을 조인한 결과와 EHr 같아야 한다고 할떄 이 제약 조건을 조인 종속(JD, Join Dependency)하고 함 ∘위의 SPC는 조인종속을 만족하고, SP, PC, CS의 3-분해 릴레이션이며, 만약 분해하지 않을 경우에 다음 예와 같이 갱신이상이 발생됨 -예1) <S2,P1,C1>을 삽입하려 한다면, 본의 아니게 <S1,P1,C1>도 함께 삽입해야 함 -예2) <S1,P1,C1>을 삭제하려면, 적어도 다른 나머지 투플 중에 하나를 함께 삭제해야 함

---

5. 정규형간의 관계

 

① 포함 종속성과 템플리트 종속성

∎포함 종속성 ∘포함 종속성은 릴레이션들 사이의 제한조건 표시함; 외래키 조건, 클래스-서브클래스 조건 ∘정의: 릴레이션 R의 애트리뷰트 집합 X와 릴레이션 S의 애트리뷰트 집합 Y사이의 포함 종속성 R.X < S.Y는 R의 릴레이션 상태 r과 S의 릴레이션 상태 s에 대해 다음과 같은 조건을 만족해야 함 * (ΠX(r(R)) ⊆ ΠY (s(S)) ∘포함 종속성에 대한 세 가지 추론 규칙: - IDIR1(재귀성 규칙): R.X < R.X - IDIR2(애트리뷰트 대응 규칙): X={A1, A2,…, An}이고 Y={B1, B2,…, Bn}일 때, R.X < S.Y이고 Ai가 Bi에 대응한다면 R.Ai < S.Bi 이다 - IDIR3(이행성 규칙): R.X < S.Y이고 S.Y < T.Z이면, R.X < T.Z이다 ∎템플리트 종속성 ∘템플리트 종속성: 각 제약조건과 함수적 종속성을 템플리트 혹은 예제를 사용하여 지정하는 방법을 말함 ∘템플리트의 종류: 투플-생성 템플리트, 제약조건-생성 템플리트 ∘템플리트는 많은 수의 가설 투플(hypothesis tuple)로 구성되며, 템플리트의 나머지 부분은 템플리트 결론(templete conclusion)이라 함 - 투플-생성 템플리트 결론: 가상 투플에 있다면 릴레이션에 반드시 나타나야 하는 투플들의 집합 - 제약조건-생성 템플리트 결론: 가상 투플들에 대해서 반드시 지켜져야 하는 조건 ∘고용자의 월급이 직속 상급자의 월급보다 많을 수 없다는 제약조건에 대한 템플리트의 예는 다음 그림과 같음 EMPLOYEE = {NAME, SSN, …, SALARY, SUPERVISORSSN } a b c dHypothesis e d f g ---------------------Conclusion c < f [그림 13] 템플리트 종속성의 예

② 정규형간의 포함 관계

∘정규형의 차수가 높을수록 보다 강한 제약조건이 적용됨 ∘모든 릴레이션을 반드시 제5 정규형에 속하도록 분해하면 좋다는 것은 아님 ∘데이터베이스 설계자가 효율적인 데이터베이스 구축을 위해 응용에 결부시키면 됨 [그림 14] 정규형 간의 포함 관계 ∘릴레이션의 정규화는 실제 데이터 값이 아니라 개념적인 측면에서 다루어져야 함 ∘ 실제 정규화 과정은 정규형의 순서와 다를 수 있음