함수적 종속과 정규화

• 이상(Anomaly)
  • 테이블에서 일부 속성들의 종속으로 인해 데이터의 중복이 발생하고, 이 중복으로 인해 테이블 조작 시 문제가 발생하는 현상
  • 이상 발생의 원인 : 여러 종류의 정보들을 하나의 릴레이션으로 표현함으로써 속성들간에 존재하는 여러 가지 종속 관계에 대해 정규화가 제대로 실행되지 않았기 때문
  • 이상의 종류
    • 삽입 이상
      • 릴레이션에서 어떤 데이터를 삽입할 경우, 원하지 않는 불필요한 정보까지도 삽입해야 하는 현상
      • 테이블에 데이터를 삽입할 경우, 의도와는 상관없이 원하지 않은 값들로 인해 삽입할 수 없게 되는 현상
    • 삭제 이상
      • 릴레이션에서 특정 튜플을 삭제할 경우, 원하지 않은 정보나 유지되어야 할 정보까지도 삭제되는 연쇄 삭제 현상
      • 정보의 손실이 발생
    • 갱신 이상
      릴레이션에서 특정 속성값 갱신 시, 중복 저장되어 있는 속성값 중 하나만 갱신하고, 나머지는 갱신되지 않아서 발생하는 데이터의 불일치 현상
       
• 함수적 종속(Functional Dependency)
  • 정의
    • R이 릴레이션 스키마이고, α ⊆ R, β ⊆ R 일 때, 함수적 종속 α → β가 R에 존재 ⇔ r(R)의 임의의 튜플t1과 t2에 대해서 t[α] = t2[α] ⇒ t1[β] = t2[β]
    • 릴레이션 r(R)에서 α의 각 값에 대해 대응되는 속성 β의 값이 정확하게 하나만 존재할 경우, β는 α에 대하여 함수적으로 종속된다고 하고, α → β로 표현됨
    • 1개의 속성은 2개 이상의 속성에 함수적으로 종속될 수 있으며, 이러한 경우에는 [A, B] → C로 표현
    • A→B일 경우 A는 결정자(Determinant), B는 종속자(Dependent)라고 부름
    • 함수적 동등
      • 두 속성(또는 속성들의 집합)이 서로 함수적으로 종속될 경우 이들을 함수적으로 동등하다고 함
      • 학번, 주민번호, 소속학과에서 주민등록번호는 학번에 함수적으로 종속되고, 학번은 주민등록번호에 함수적으로 종속될 때 주민등록번호와 학번은 함수적으로 동등하다고 함
  • 함수적 종속의 규치
    • 암스트롱의 공리(Armstrong's Axioms)
      • 재귀(Reflexivity) 규칙 : Y가 X의 부분 집합(즉, Y ⊆ X)이면, X → Y
        • 모든 속성들은 자신에 대하여 함수적으로 종속됨
        • 모든 속성은 자신을 포함하는 다른 속성들에 대해 함수적으로 종속됨
      • 부가(Augmentation) 규칙 : X → Y 이면, XZ → YZ(표기 : XZ는 X ∪ Z를 의미)
        부가적 종속에 다른 속성들을 추가하여도 함수적 종속이 성립하는 데에는 아무런 영향을 미치지 않음
      • 이행(Transitivity) 규칙 : X → Y 이고, Y → Z 이면, X → Z
        임의의 릴레이션 R에서 속성(또는 속성들의 집합) Y가 X에 함수적으로 종속되며, 속성(또는 속성들의 집합) Z가 Y에 함수적으로 종속될 경우, Z는 Y를 매개로 하여 X에 함수적으로 종속되며, 이를 이행적 함수적 종속이라 함
      • 예) {과목번호, 교수, 연구실}에서 과목번호 → 교수, 교수 → 연구실 이면 과목번호 → 연구실이 성립
    • 추가 규칙
      • 합집합(Union) 규칙 : X → Y이고 X → Z이면, X → YZ
      • 분해(Decomposition) 규칙 : X → YZ 이면, X → Y이고, X → Z
      • 의사 이행성(Pseudo=transitivity) 규칙 : X → Y이고 WY → Z이면, WX → Z

함수 종속 관련 추론 규칙
이행 규칙(Transitive rule)	α → β가 보존되고 β→ γ가 보존되면, α → γ는 보존된다
증가 규칙(Augmentation rule)	α → β가 보존되고 γ가 속성들의 집합이면, γα → γβ는 보존된다
분해 규칙(Decomposition rule)	α → βγ가 보존되고 α → β가 보존되면, α → γ가 보존된다
결합 규칙(Union rule)	α → β가 보존되고 α → γ가 보존된다면, α → β γ가 보존된다
재귀 규칙(Reflexivity rule)	α 가 속성들의 집합이고 β ⊆ α이면, α → β가 보존된다

• 함수적 종속 집합의 폐쇄(Closure)
  • 주어진 함수적 종속 집합 F가 다른 특정 함수적 종속을 보존하고 있을 경우, 이러한 함수적 종속을 F에 의해 논리적으로 함축되었다(Logically Implied)라고 함
  • F를 함수적 종속 집합이라고 할 때, F의 폐쇄는 F*라고 표현하는데, 이는 F에 의해 논리적으로 함축되어 있는 모든 함수적 종속의 집합을 의미
  • F* 계산 절차

F* = F REPEAT FOR EACH F*의 함수적 종속 f f에 대해 재귀 규칙과 부가 규칙을 적용 결과 함수적 종속 집합을 F*에 추가 FOR EACH F*의 함수적 종속의 쌍 f1과 f2 IF f1과 f2가 이행 규칙을 만족할 경우 결과 함수적 종속 집합을 F*에 추가 UNTIL F*에 변화가 없을 때까지

• 릴레이션의 키와 함수적 종속
  • 키의 특성으로 부터 다음과 같은 함수적 종속에 대한 정의가 가능
    키 → {키가 아닌 속성들}
  • 릴레이션의 키 값만 알면 유일하게 하나의 튜플을 추출할 수 있으며, 추출된 튜플에는 모든 속성에 대하여 하나의 값만 존재
  • 릴레이션을 구성하는 모든 속성들은 키에 대하여 함수적으로 종속되므로, 릴레이션의 키값을 알면 다른 모든 속성들의 값을 알 수 있음
  • 집합 X가 슈퍼키 인지를 검사하기 위해서는 F*를 이용해서 X가 모든 속성과 함수적 종속을 갖는지(즉,
    X → R ∈ F*) 확인이 필요하지만, 이는 F*가 커지는 경우로 비용이 매우 커짐
• 속성 집합의 폐쇄(Closure)
  • α를 속성의 집합이라고 할 경우, 함수적 종속 관계의 집합 F에서 α가 함수적으로 결정하는 속성들의 집합을 F 하에서는 α에 대한 폐쇄(Closure)라고 부르며, α*라고 표시
  • α* 계산 절차

result := α* WHILE ( result의 변화) DO FOR EACH F의 함수적 종속 β → γ BEGIN IF β ⊆ result THEN result := result U γ END

예) 릴레이션 스키마 R=(A, B, C, G, H, I)과 함수적 종속 집합 F = { A→B, A→C, CG→H, CG→I, B→H } 가 주어질 때 (AG)* 를 구하시오.

A→B에서 B가 result에 포함 : F가 A→B를 포함하고 A ⊆ result(현재 AG)이므로 result :=result U B A→C에서 result는 ABCG CG→H에서 result는 ABCGH CG→I에서 result는 ABCGHI ∴ result = (AG)* = ABCGHI

• 속성 집합의 폐쇄(Closure) 활용
  • 슈퍼키 확인
    • α가 수퍼키인지를 검사하기 위해, α*를 구하고, α*가 R의 모든 속성을 포함하는지 확인(즉, α* = R)
    • 위 예에서 (AG)* = ABCGHI = R 이므로 AG는 슈퍼키
  • 후보키 확인
    • α가 후보키인지를 검사하기 위해, α* = R이나 α의 어떠한 부분 집합의 폐쇄도 R이 되지 않는지 확인
    • 위 예에서 (AG)* = ABCGHI = R이나 A* = ABCH ≠ R이고, G* = G ≠ R이므로 AG는 후보키
  • 함수적 종속 확인
    • 함수적 종속 α → β 가 존재한다는 것은 β ⊆ α* 인지를 알아봄으로써 확인
    • 위 예에서 R이 함수적 종속 A → CH를 만족하는가?
      A* = ABCH(즉, CH ⊆ A*)이므로 A → CH가 R에 존재
  • F* 계산
    각각의 γ ⊆ R에 대해 γ*을 계산하고, 각각의 S ⊆ γ*에 대해서 함수적 종속 γ → S를 구함
• 함수적 종속 종류
  • 완전 함수적 종류
    • 함수적 종속 X →Y 에서 X가 Y의 속성값을 유일하게 결정하기 위한 최소한의 속성들만을 포함할 경우, Y는 X에 대하여 완전 함수적 종속된다고 함
    • 임의의 릴레이션 R에서 속성 또는 속성들의 집합 X에 대해 Y가 함수적으로 종속되나, X의 어떠한 부분 집합 Z(즉, Z ⊂ X)에 대해서도 함수적으로 종속되지 않는 경우, Y는 X에 대하여 완전 함수적 종속이라고 함
      예) { 이름, 학과명 } → 주소이나, 이름 ↛ 주소, 학과명 ↛ 주소 라면 {이름, 학과명} → 주소는 완전 함수적 종속
  • 부분 함수적 종류
    함수적 종속 X → Y 에서 만약 Y가 X의 임의의 부분 집합Z(즉, Z ⊂ X)에 대해서도 함수적으로 종속일 경우, Y는 X에 대하여 부분 함수적 종속이라고 함    
  • 예) 공급자번호 → 주소, {공급자번호, 부품번호} → 주소, {공급자번호, 공급량} → 주소 이라면 {공급자번호, 부품번호} → 주소, {공급자번호, 공급량} → 주소는 부분 함수적 종속

• 분해(Decomposition)
  • 무손실 조인(Lossless-join) 분해
    • 릴레이션 R의 프로젝션인 R1, R2가 자연 조인(NATURAL JOIN)을 통해 원래의 테이블 R로 정보 손실없이 복귀되는 경우, R은 R1과 R2로 무손실 분해되었다고 함
    • R을 릴레이션 스키마라 하고 R1 ∩ R2 → R1 또는 R1 ∩ R2 → R2 중에 하나라도 F*에 포함된다면, 이 분해는 무손실 조인 분해
    • 즉, R1 ∩ R2가 R1 또는 R2의 슈퍼키를 구성한다면 R의 R1과 R2로의 분해는 무손실 조인 분해
  • 종속 보존(Dependency Preservation) 분해
    • 릴레이션 R이 R1, R2, … Rn으로 분해 되었을 경우, 함수적 종속 집합 F도 각 릴레이션에 속한 속성만을 포함한 함수적 종속 집합 F1, F2, …, Fn으로 분해
    • 이때, F' = F1 U F2 U … U Fn이라고 하면, 일반적으로 F' ≠ F
    • 그러나 F' ≠ F이지만 F'* = F*가 될 수 있으며, 이러한 경우에 종속성 보존 분해라고 함
  • 예) R(A, B, C)과 F = { A → B, B → C } 이 주어졌을 때,
    • R1 = ( A, B), R2 = (B,C)
      • 무손실 조인 분해 : R1 ∩ R2 = {B} 이고, B → BC ∈ F*
      • 종속 보존 분해 : ( F1 U F2)* = F*
    • R1 = (A, B), R2 = (A, C)
      • 무손실 조인 분해 : R1 ∩ R2 = {A} 이고, A → AB ∈ F*
      • 종속 보존 분해 : ( F1 U F2)* ≠ F*
           
• 정규화(Normalization)
  • 정규화의 정의
    • 데이터의 손실이나 불필요한 정보 없이 데이터의 일관성을 확보하고 최소한의 데이터 중복을 꾀하며, 또한 최대한 데이터의 안정성을 확보하기 위하여 보다 바람직한 릴레이션 스키마로 전환하는 과정
    • 주어진 하나의 릴레이션을 이상(Anomaly)이 적게 발생하는 좋은 형태의 릴레이션들로 분해(Decomposition)하는 방법을 설명
    • 정규화 수준이 낮을수록 데이터 중복성과 디스크 용량 사용이 높아짐
    • 정규화는 함수의 종속성을 제거하는 것은 아님
  • 정규화의 원칙
    • 무손실 조인 분해
    • 함수적 종속 보존
    • 데이터의 중복성 감소
  • 정규화의 필요성
    • 중복에 따른 이상 현상의 제거로 데이터의 일관성 유지 가능
    • 보다 간단한 관계 연산에 기초하여 검색 알고리즘을 효과적으로 만듬
    • 중복의 제거로 인한 저장 공간의 최소화 달성
    • 새로운 형태의 데이터가 삽입될 때 릴레이션을 재구성할 필요성이 줄어듬
  • 정규화의 장.단점
    • 장점
      • 데이터의 중복을 최소화함으로써 최소의 데이터로 최적의 데이터베이스를 구축할 수 있고, 데이터 관리의 효율성을 높일 수 있음
      • 데이터에 대한 삭제, 삽입, 갱신 시에 릴레이션에서 발생 가능한 이상을 제거할 수 있음
      • 데이터 중복이 제거됨으로써 갱신 처리가 적어져 데이터의 일관성과 무결성을 확보할 수 있음
      • 중복의 최소화로 저장 공간을 효율적으로 운용할 수 있음
    • 단점
      • 분할이 다양하게 이루어져, 빈번한 조인(JOIN) 연산의 증가로 시스템의 실행 시간이 오래 소요되어 검색 시간이 비효율적일 수 있음
      • 복잡한 검색 조건으로, 데이터베이스 질의문의 의미가 부자연스러울 수 있음
  • 정규화 동향
    • 최근에는 디스크나 메모리의 고밀도화와 가격의 저렴화 등으로 장치의 유연성이 높아졌으며, 데이터 접근 속도가 시스템 성능에 중요한 요소로 작용하고 있어 정규화의 필요성이 점차 줄어들고 있는 실정
    • 프로젝트 현장에서는 2~3차 정규화 정도까지를 진행한 후 설계 단계에서 원활한 업무 수행 조건을 반영하여 성능 향상을 위해 객체 통합이나 속성의 중복 관리 등을 통한 반정규화도 수행하고 있음
  • 정규화의 종류

종류	방법
제 1차 정규화 (1NF :First Normal Form)	릴레이션의 모든 속성의 도메인이 원자값만으로 구성된 상태 다중값 속성 및 복합 속성을 제거함으로써 !NF로 정규화
제 2차 정규화 (2NF :Second Normal Form)	릴레이션 1NF이고 키에 속하지 않은 속성 모두가 기본키에 완전 함수적 종속인 상태 부분 함수적 종속을 제거함으로써 2NF로 정규화
제 3차 정규화 (3NF :Third Normal Form)	릴레이션이 2NF이고 키에 속하지 않은 속성 모두가 기본키에 대해 이행적 함수적 종속을 만족하지 않는 상태 이행적 함수적 종속을 제거함으로써 3NF로 정규화
보이스/코드 정규형 (BCNF : Boyce/Codd Normal Form)	릴레이션의 모든 결정자(Determinant)가 후보키인 상태 릴레이션이 BCNF에 속하면 R은 제1, 제2, 제3차 정규형에 속함 후보키가 아닌 모든 결정자를 분해함으로써 BCNF로 정규화
제 4차 정규화 (4NF : Fourth Normal Form)	릴레이션에서 다중값 종속(Multi Valued Dependency) A ↛ B가 존재할 때 릴레이션의 모든 속성이 A에 함수적 종속을 만족하는 상태 다중값 종속 : 릴레이션 R(A, B, C)에서 속성 A와 C값에 대응하는 B값의 집합이 A값에만 종속되고 C값에는 독립되는 관계 함수적 종속이 아닌 다중값 종속을 제거함으로써 4NF로 정규화
제 5차 정규화 (5NF : Fifth Normal Form)	릴레이션에 존재하는 모든 조인 종속(Join Dependency)이 후보키를 통해서만 성립되는 상태 조인 종속 : 어떤 릴레이션 R에서 R의 프로젝션들인 X, Y, …, Z 릴레이션을 자연 조인한것이 R과 동일해지는 종속 후보키를 통하지 않은 조인 종속을 제거함으로써 5NF로 정규화

• 3NF와 BCNF의 비교
  • 릴레이션은 3NF로 무손실 조인 분해와 종속 보존 분해 가능
  • 릴레이션은 BCNF로 무손실 조인 분해는 가능하나, 종속 보존 분해는 항상 가능하지 않음
• 정규화 정리
  • 1차 정규화
    
  • 2차 정규화
    
  • 3차 정규화
    
  • 최종 정규화 결과
    

• 반정규화(De-normalization, 비정규화)
  • 반정규화의 개념
    • 반정규화는 정규화된 개체, 속성, 관계를 성능 향상 및 개발의 단순화를 위해 일부의 데이터에 대해 중복을 허용하는 정규화의 역작업으로, 데이터베이스 튜닝에서 사용
    • 반정규화를 진행할 때는 데이터의 정합성/무결성을 중요시할 것인지, 아니면 성능 개선과 구조의 단순화로 편리성을 제고할 것인지 선택해야 함
    • 정규화의 단점을 보완하거나 해결하는 방안으로 적절한 수준의 반 정규화로 수행 속도를 빠르게 함
    • 반정규화의 내용을 DBA나 설계/개발자가 숙지하여 이상이 발생하지 않도록 해야 함
         
  • 반정규화의 특징
    • 정규화를 충분히 수행한 후에 반정규화를 실시해야 함
    • 갱신이 적고, 검색이 많은 테이블에 적용하는 것이 좋음
    • 반정규화된 테이블을 갱신하는 응용 프로그램이 복잡해 질 수도 있음
    • 비정규화 적용 부분에 대해서는 일관성 검증을 위한 추가적인 테스트가 필요
  • 테이블 반정규화 방법
    • 테이블 통합
      • 업무를 처리함에 있어 2개 이상의 테이블이 항상 조인이 발생하는 경우에 고려
      • 조인이 없어짐으로써 데이터베이스 접근 성능이 좋아짐
    • Parent 테이블과 Child 테이블의 통합
      • Parent 테이블에 Child 테이블의 속성을 삽입하고 Child 테이블을 삭제
      • Parent 테이블 내의 각 튜플에 대해 Child 튜플 수가 고정되어 있는 경우에 적용
      • 조인이 없어짐으로 데이터베이스 접근 성능은 좋아지나, SQL 문에 모든 중복 필드를 Hard 코딩해야 함
    • 코드(Code) 테이블 통합
      • 코드명을 속성으로 추가하여 조인을 제거
      • 테이블 통합보다는 코드 테이블을 메모리에 올리는 등의 프로그램적인 방법을 사용
      • 서버의 자원 활용을 줄이고, 데이터베이스 I/O 성능이 좋아지나, 기억 공간의 낭비가 발생하며, 데이터 불일치가 발생
    • 테이블 분할
      • 테이블의 일부 속성에 데이터가 집중하여 접근되는 경우(수직분할)이거나 특정 범위의 튜플만 집중적으로 접근되는 경우(수평분할)에 분산 전략에 따라 분할
        • 수직분할 : 매우 많은 수의 속성들로 구성된 테이블에서 빈번하게 접근되는 속성과 접근 횟수가 적은 속성을 분리하여 테이블을 구성하는 것으로, 디스크 I/O와 네트워크 트래픽을 줄일 수 있음
        • 수평분할 : 1개의 테이블을 특정 기준에 따라 2개 이상의 데이블(파티션)들로 분리하는 것을 말하며, 효율성 증대(수행시간 단축 및 I/O 부담 경감) 효과를 얻을 수 있음
      • 분할을 실시하면 스캔 범위가 축소되어 접근하는 양이 감소하여 Locking이나 Contention이 감소함으로써 단일 테이블 처리 시 속도 향상이 가능
      • SQL문장이 복잡해지며, 분할된 테이블을 모두 처리할 경우에는 느려질 수 있음
    • 테이블 추가
      • 통계, 이력 관리 등의 업무를 위해 추가적으로 테이블이 필요한 경우
      • 대량의 데이터를 처리해야 하는 경우 통계 테이블을 별도로 두어 시간이 많이 소요되는 작업은 배치로 실시하여 업무 성능을 개선
  • 필드 반정규화 방법
    • 중복(Redundant) 필드 추가
      • 조인이 자주 발생할 때 조인하여 읽어올 속성을 양쪽 테이블에 중복적으로 저장하거나 특정 정보를 가져오는데 많은 테이블을 검색해야 하는 경우, 하나의 필드를 추가하여 저장함으로써 성능을 개선할 수 있음
      • 조인을 피하여 데이터 접근 횟수를 줄이기 위하여 사용하며, 갱신 횟수에 비해 조회횟수가 매우 많거나 갱신보다 조회의 성능 향상이 더 중요할 때 적용해야 함
      • 조인 비용은 줄지만 갱신 비용은 증가되는 특성이 있음
      • 단점 : 데이터의 무결성 확보가 어려우며, 중복 데이터 저장을 위해 디스크를 사용해야 하고, 속성에 대한 소유권의 책임이 불명확해 질 수 있음
    • 계산(Computed) 필드 추가
      • 여러 숫자 필드를 조인하여 계산이 필요한 경우, 해당 테이블의 필드를 모두 읽어서 산정해야 하는 경우, 데이터 발생에 따라 누적되는 상황을 관리해야 하는 경우에 성능 향상을 위해 특정 테이블에 계산된 결과를 위한 별도의 필드를 두어 관리함
      • 단점 : 갱신 비용이 증가되며, 데이터 중복성이 존재하므로 데이터를 일치시키기 위해 많은 비용이 소요됨
    • 이력 필드 추가
      데이터의 변경이나 발생에 대한 이력, 최신의 변경정보,현재의 진행 상태를 필요로 하는 경우에는 다양한 업무를 해소하기 위해 별도의 필드를 두어 관리
    • 대체키 필드 추가
      기본키가 너무 복잡한 복합키로 구성되어 처리에 불편하거나, 특정 필드만을 대상으로 업무가 처리되는 경우에는 대체키를 지정하여 사용
    • 시스템의 오류를 방지하기 위한 필드 추가
      업무를 처리하면서 실수 등으로 데이터가 잘못 입력되는 경우, 계산에 의한 결과값이나 진행 상태 변경과 같은 최신 정보를 관리하여 오작동 시 회복을 위해 활용하는 방법