함수종속, NF

릴레이션 스키마의 설계

설계

릴레이션 스키마를 설계하는것에 있어서 제1의 목표는 좋은 스키마를 많드는것이다. 좋은 스키마란, 엔티티(개체)와 릴레이션쉽을 잘 도출해서 만들어낸 스키마이다. 즉, 데이터의 종속성을 고려해서 서로 연관있는 애트리뷰트끼리 하나의 릴레이션(관계성)에 묶어야한다.

1. 애트리뷰트, 엔티티, 관계성을 파악
2. 관련된 애트리뷰트들을 릴레이션으로 묶음
   고려사항
   애트리뷰트들간의 관계성(relationship): 데이터 종속성
   효율적인 데이타 처리
   데이타의 일관성
3. 변칙적 성질의 예방
   데이터 변경 시의 이상현상

예시

학생이름, 학번은 학생에 대한 애트리뷰트이다. 하지만 과목이름은 학생은 관계가 없다.따라서 이를 관계에 따라 나눠야한다.

이상 (Anomaly)

이상에는 총 3가지 이상이 있다.

다음과 같은 스키마가 있다.

1. 삭제 이상
   200번학생의 C123의 등록을 취소한다고 할 때, 3학년이라는 학년정보역시 같이 사라져 버린다. 즉, 연쇄 삭제에 의한 정보손실이 발생한다.

2. 삽입 이상
   600번 학생이 2학년이라는 사실을 넣을 때, 어떤 과목이 등록되지 않는 이상 삽입이 안된다(과목번호가 기본 키). 즉, 원하지 않는 정보의 강제삽입이 이루어진다

3. 갱신 이상
   400번 학생의 학년은 4에서 3으로 변경 할 때, 400에대한 4개의 튜플을 전부 변경해야한다.
   중복 데이터의 일부 갱신으로 정보의 모순성(inconsistency)이 발생

이상의 원인

하나의 개체에 속한 애트리뷰트간에 존재하는 여러 개의 종속관계를 하나의 릴레이션으로 표현해서

이상의 해결

애트리뷰트들 간의 여러 종속관계를 분해하여 각각 하나의
릴레이션으로 표현 -> 하나의 종속성은 하나의 릴레이션으로 표현 -> 정규화

스키마 설계와 변환

스키마 설계

1. 애트리뷰트들과 이들의 제약조건(종속성)을 수집
2. 수집된 결과를 명시된 제약조건에 따라 여러 개의 릴레이션으로 분할 -> 스키마변환

어떠한 집단에서 사용되는 데이터들의 제약조건, 종속성은 해당 집단의 전문가에게 문의하여야 한다.

스키마 변환의 원리

1. 정보표현의 무손실

• 분해 전 릴레이션에서 표현한 정보가 누락없이 하위 릴레이션 들어가야함.
  • R을 나눈 R1 R2 R3가 있을 때, R1 Join R2 Join R3 하면 원래 릴레이션 R이 나옴

2. 최소의 데이터 중복

3. 분리의 원칙 -> 독립된 관계성은 별도의 릴레이션으로 분리시켜 표현

함수종속의 정의

함수종속은 만고불변의 진리가 아니라, DB사용자들이 결정하는것이다.

정의
애트리뷰트X에 대해서 Y의 값이 연관관계일떄
Y는 X의 함수 종속이다
X->Y

이때 X는 결정자, Y는 종속자
X Y는 두 개 이상의 에트리뷰트 집합이 될 수 있다

X가 키이면 Y1 Y2 Y3 모든 애트리뷰트 Y에 대해 X->Y 성립한다.

함수종속 X → Y의 경우

애트리뷰트 X가 반드시 키(유일 값)라는 것을 요건으로 하지 않는다. 즉, X의 어느 한 값에 대응되는 Y 값을 갖는 투플이 둘 이상 존재 가능.

함수종속의 다이어그램

위 다이어그램에서
X = {학번, 과목번호}
X’ = X의 부분집합
X’로 Y가 결정되는 경우가 있다면 부분함수종속
없다면 완전 함수 종속

예시

예: 수강 릴레이션의 함수 종속
학번 -> 학년
{학번,과목번호} -> 성적

1. “학년”은 “학번”에 완전 함수 종속,
2. “학년”은 “{학번,과목번호}에 부분 함수 종속,
3. “성적”은 {학번,과목번호}에 완전 함수 종속

함수 종속에 따른 추론 규칙

정규형

정규형어떤 일련의 제약조건을 만족하는 릴레이션
정규화 즉, 스키마 변환 (S -> S')으로 정규형을 만듦

정규화의 원칙

① 정보 표현의 무손실

• 같은 의미의 정보 유지
• 효율적인 구조

② 최소의 데이터 중복

③ 분리의 원칙

• 독립적인 관계는 별개의 릴레이션으로 표현
• 릴레이션 각각에 대해 독립적 처리가 가능

제 1 정규형 1NF

모든 애트리뷰트가 원자값으로 구성

예시

수강지도 릴레이션

• 수강지도 (학번, 지도교수, 학과, 과목번호, 성적)
• 기본키 : {학과, 과목번호}
• 함수 종속 :
  {학번, 과목번호} -> 성적
  학번 -> 지도교수
  학번 - > 학과
  지도교수 - > 학과
  

이상

1. 삽입 이상
   500번 학생의 지도교수가 P4라는 사실을 삽입하려 할 때 어떤 과목을 등록하지 않는 한 삽입은 불가능 (기본키 과목번호가 없음)

2. 삭제 이상
   200번 학생이 C123의 등록을 취소하여 이 투플이 삭제되는 경우에 지도교수가 P2라는 정보까지 손실됨 (유일한 데이터)

3. 갱신 이상
   400번 학생의 지도교수를 P1에서 P3로 변경하는 경우에 학번이 400인 4개의 투플에 대한 지도교수를 모두 P3로 변경해야 함

이상의 원인화 해결

• 이상의 원인

  • 기본 키에 부분 함수 종속된 이 행적 존재
  • 두 가지 독립적인(상이한) 정보가 하나의 릴레이션으로
    표현

• 이상의 해결

  • 부분함수종속을 제거하면 2NF로 변하면서 해결 가능함

제 2 정규형 2NF

1NF이고, 키에 속하지 않는 애트리뷰트들은 모두 기본 키에 완전 함수종속

무손실 분해

1NF를 프로젝션하면 2NF
2NF를 조인하면 1NF

• 이 과정에서 손실되는 데이터가 없어야한다. 즉, 조인을 하면 원래 릴레이션이 나와야한다.
• 원래 릴레이션에서 얻을 수 있던 정보는 분해된 릴레이션들로부터도 얻을 수 있어야한다. 다만 반대는 해당하지 않는다.

무손실 분해 정리

R(A,B,C)에서 함수 종속 A -> B가 성립하면
⇒ R1(A,B), R2(A,C) 로 무손실 분해가 가능

제 2 정규형으로 분해

수강지도 > 지도, 수강 릴레이션으로 분해

• 지도 (학번, 지도교수, 학과)
  • 기본 키 : {학번}

• 수강 (학번, 과목번호, 성적)
  • 기본 키 : {학번, 과목번호}
  • 외래 키 : {학번} 참조 : 지도

2NF에서의 이상

1. 삽입 이상
   어떤 지도교수가 특정 학과에 속한다는 사실의 삽입이 불가능 (학번이 기본키)

2. 삭제 이상
   300번 학생의 투플을 삭제하면 지도교수 P3가 컴퓨터공학과에 속한다는 정보를 상실

3. 갱신 이상
   지도교수 P1의 소속을 컴퓨터공학과에서 전자과로
   변경한다면 학번이 100과 400인 두 개의 투플을 모두
   변경해야 함

발생원인 - 이행적 함수 종속이 존재하기 떄문

해결 - 프로젝션으로 2NF 릴레이션을 분해 (이행적 함수 종속을 제거) ⇒ 3NF

이행적 함수 종속 (TD, Transitive Dependency)

릴레이션 R에 함수 종속 A > C가 존재하고 함수 종속 A > B와 B > C가 성립할 때 애트리뷰트 C는 애트리뷰트 A에 이행적 함수 종속이라고 한다.

제 3 정규형 (3NF)

2NF이고, 키가 아닌 모든 애트리뷰트들은 기본 키에 이행적
함수 종속이 되지 않음

이행적 함수 종속 제거

지도 > 학생지도와 지도교수학과로 분해

• 학생지도 (학번, 지도교수)

  • 기본 키 : {학번}
  • 외래 키 : {지도교수} 참조 : 지도교수확과

• 지도교수학과 (지도교수, 학과)

  • 기본 키 : {지도교수}

제 3정규형의 특징

1. 키가 아닌 애트리뷰트 값 갱신 시, 이상은 발생하지 않음
2. 모든 이원 릴레이션은 3NF에 속함
3. 3NF를 적용 할 수 없는 경우

I. 복수의 후보 키를 가지고 있고
II. 후보 키들이 두 개 이상의 애트리뷰트들로 구성되고
III. 후보 키들의 애트리뷰트가 서로 중첩되는 경우
⇒ 보다 일반적인 Boyce/Codd Normal Form(BCNF)을 제안

수강과목 릴레이션을 이용한 문제점의 예

• 예(3NF) : 수강과목(학번,과목,교수) 릴레이션
  • 제약조건
    한 학생은 각 과목에 대해 오직 한 교수의 강의만 수강
    각 교수는 한 과목만 담당
    같은 과목을 여러 교수가 담당할 수 있음
    수강과목 (학번,과목,교수)
    후보 키 : {학번,과목}, {학번,교수}
    기본 키 : {학번,과목}
    함수종속 :
    {학번,과목} > 교수 , 교수 > 과목

1. 삽입 이상
   교수 P5가 자료 구조 과목을 담당한다는 사실의 삽입은 학번(수강 학생)이 있어야 가능

2. 삭제 이상
   100번 학생이 자료 구조를 취소하여 투플을 삭제하게 되면 P2가 담당교수라는 정보도 삭제됨

3. 갱신 이상
   P1이 프로그래밍 과목 대신 자료 구조를 담당하게 되면 P1이 나타난 모든 투플을 변경하여야 함

⇒ 원인 : 교수가 결정자이지만 후보 키가 아님

보이스/코드 정규형 BCNF

릴레이션 R의 결정자(determinant)가 모두 후보 키이면 릴레이션 R은 BCNF에 속한다.

• Strong 3NF 라고도 한다.
• R이 BCNF이면, R은 제 1 2 3 정규형이다.
• 예(BCNF) : 수강과목 ⇒ 수강교수, 과목교수
• 3가지 이상상태를 모두 해결 하였음
  

반복 그룹의 표현과 제한

• BCNF인 CPT 릴레이션의 제약조건
  • 만일 이 CPT에 튜플 <c1, p1, t1>과 <c1, p2, t2 가 포함되어 있으면, 두 개의 투플 <c1, p1, t2>와 <c1, p2, t1>도 포함되어 있어야 한다. (왜냐하면 2개의 교재, t1과 t2가 있기 때문)

CPT에서의 변경이상

P4가 데이터 베이스를 담당한다는 정보를 입력하려면 데이터베이스 교제 (T3, T3, T5)에 대한 튜플을 삽입해야함

원인

• 과목은 교수나 교재의 값 하나를 정하는게 아니라 값의 집합을 결정한다.

이런것을 다치종속이라 부른다

다치종속

A, B, C가 릴레이션 R의 애트리뷰트의 부분 집합이라 할 때
애트리뷰트 쌍 (A, C)-값에 대응되는 B-값의 집합이
A-값에만 종속되고 C-값에는 독립적이면
B는 A에 다치 종속이라 하고 A↠ B로 표기한다

• Fagin: A ↠ B이면 A ↠ C도 성립 즉, A ↠ B|C A > B 는 A ↠ B 안에 포함되어 있다.

  이상현상의 해결

  CPT를 CP와 CT로 나눈다.
  

제 4정규형 4NF

릴레이션 R에서 A ↠ B를 만족하는 애트리뷰트 집합 A, B가 존재할 때 R의 모든 애트리뷰트들이 A에 함수 종속이면 R은 4NF(즉 R의 모든 애트리뷰트 X에 대해 A > X 이고 A가 후보 키)

• 보통 정규화를 한다고 하면 4NF까지 정규화를 한다