[Database] 10 함수적 종속과 정규화 기초

REF: fundamentals of database systems 7th edition

1. 개론

• 여기서는 디자인 퀄리티를 평가하는 이론에 대해 논한다.
• relation schema들의 좋고나쁨을 평가하는 것은 2가지 레벨에서 이뤄진다.
  1. logical level
     • user가 어떻게 relation 스키마와 속성을 해석하는지
     • 유저가 명확하게 relation의 data를 파악하는게 목적이다.
     • base relation(physically stored as files)와 view들에 모두 적용
  2. implementation(physical storage level)
     • base relation의 tuple이 어떻게 저장되고 수정되는가.
     • base relation에만 적용.

디자인 접근방법

• bottom-up design methodology(design by synthesis)
  • 1개 relation에 모든 속성을 넣고 이를 decomposition간다.
  • decomposition의 기준은 함수적 종속성들이고,
  • normalization을 통해 relational DB schema를 작성해나간다.
  • 개별 속성을 가진 relationship들, 더 정확하게는 함수적 종속성들을 파악해 relation schema를 작성한다.
• top-down design methodology(design by analysis)
  • 개념적 스키마를 ER모델링을 통해 그린다.
  • 이를 relation schema mapping을 통해 ER을 작성하고,
  • 이를 실제 relation DB schema로 작성한다.
• 대부분의 경우, top-down방식으로 그리고, 성능상 issue(join)으로 인해 비정규화를 하는데, 다시 bottom-up을 통해 정규화를 하는
• hybrid방법을 사용한다.
• 이 장에서는 top-down design된 스키마를 평가하는 방법에 대해 공부한다.

디자인 목표

1. information preservation
2. minimum redundancy

Informal Design Guidelines

Guideline 1

• 1개의 엔티티는 1개 릴레이션으로, 1개 릴레이션타입은 1개 릴레이션으로 할 것.
  • 의미를 확실히해라

Guideline 2

• 튜플에서 중복된 정보를 줄일 것.
  • 저장공간을 최소화해라
  • base relation이 natural join된 상태로 존재하면, update anomalies가 발생한다.

update anomalies

• insertion
  • SSN이없는 부서의 정보를 입력할 수 없다.
• deletion
  • 유일한 부서에 속한 직원 삭제하면 부서정보도 삭제된다.

• modification
  • 부서 5의 부서장을 바꾼다고 했을 때, 모든 부서5 튜플의 부서장 번호를 바꿔야한다.

Guideline 3

• 널값을 줄일 것.
  • 저장공간을 최소화하기위해서.
  • null값은 다양한 의미로 해석될 수 있음.(missing, not known, not applicable)

Guideline 4

• spurious tuple의 발생 가능을 허용하지 않을 것.
  • DB를 잘못 설계하면 spurious tuple, 즉 가짜 튜플을 만들어낸다.
  • lossless(non-additive) join, 즉 손실도 없어야하고, 추가되는 튜플도 없어야한다.
  • PK또는 FK인 속성으로만 JOIN연산을 해야한다.

함수적 종속

용어정의

• Universal Schema R
  • DB스키마가 A₁부터 A₂… A𝑛까지 N개의 속성을 가지고 있을 때
  • 전체 DB 스키마를 1개로 나타낸 것을 의미한다.

• Functional Dependency X ➡ Ỵ
  • universal schema R의 state r에서
  • t1[X] = t2[X]이고, t1[Y] = t2[Y]일때를 의미한다.

• 어떤 relation instance r에서 주어진 X-value를 가진 튜플이 한개보다 많을 수 없다는 조건(unique)이 있을 경우,
  • 이 X가 R의 Candidate Key(CK)가 된다.
  • 후보키의 조건이 relation에서 이 속성값이 unique해야한다는 것이므로, 당연하다.

• legal extensions
  • 모든 함수적 종속성을 만족하는 relation schema instance(extensions) r(R)을 부르는 말.

Inference Rules

• Bottom-up design, design by synthesis에서는 스키마 설계자가 의미적으로 명확한 함수적 종속성을 먼저 파악한다.
• 하지만, legal extensions에서는 수없이 많은 함수적 종속성들을 inferring, 추론해낼 수 있다.
• 이런 추론된 함수적 종속성들을 inferred or implied functional dependencies라고 부른다.
• 이를 closure of F, F⁺라고 한다.

Armstrong’s axioms

• 암스트롱이 제시한 F의 closure를 찾는 rule들을 의미한다.

• IR1 : reflexive rule
  • X ⊇ Y이면 X -> Y
  • 또는, X -> X
  • 속성집합은 항상 스스로나, 부분집합을 결정(진부분집합을 결정)한다는 것을 의미한다.
• IR2 : augmentation rule
  • {X -> Y} |= XZ -> YZ
  • 양변의 Z를 생략할 수 있기 때문.
• IR3 : transitive rule
  • {X -> Y, Y - >Z} |= X -> Z
  • X->Y->Z의 종속성을 이용해 추론해낸 것.

이렇게 위의 3가지 inference rule들로 F⁺를 만들어낼 수 있다.
위 3개 Armstrong’s axioms를 응용해 3가지 rule을 더 만들어낼 수 있다.

• IR4 : decomposition rule
  • {X -> YZ} |= X -> Y
  • 기본적으로, {}표현 안의 각 양변은 분해할 수 있다.
• IR5 : union rule
  • {X -> Y, X - >Z} |= X -> YZ
  • decomposition이 가능하듯, union도 가능하다.
• IR6 : pseudotransitive rule
  • {X -> Y, WY -> Z} |= WX -> Z
  • augmentation rule과 transitive rule을 응용한다.
    1. augmentation rule로 WX -> WY로 변환
    2. transitive rule로 WX->WY->Z을 추론

finding dependent attribute

• 주어진 F에 대해서 의존적인 속성을 분석한다.
• 즉, F의 왼쪽 속성이 표현가능한 모든 F를 찾는다.
• 주어진 F의 함수적 종속성 각각에 IR을 적용한다.

F =
{
	SSN -> {ENAME},
	PNUMBER -> {PNAME, PLOCATION},
	{SSN, PNUMBER} -> {HOURS}
}

• IR 적용

F⁺ = 
{
	SSN⁺ -> {SSN, ENAME},  
	PNUMBER⁺ -> {PNUMBER, PNAME, PLOCATION}, 
	{SSN, PNUMBER}⁺ -> {SSN, PNUMBER, ENAME, PNAME, PLOCATION, HOURS} 
}

함수적 종속성의 동등집합

• 함수적 종속성 파악은 여러명의 요구사항으로 이뤄져있기때문에, 설계자 각각에 의해 다른 결과가 나올 수 있따.

• 따라서 이에대해 판단하는 방법이 필요하다.

• 함수적 종속성을 파악하기 위해서, 각 함수적 종속성 집합의 closure을 찾아서 비교해야한다.

정의

• 함수적 종속성 집합 E와 F가 각각 다른 설계자에 의해 도출되었다고 가정한다.

• cover 확인

  • E의 closure E⁺를 찾는다.
  • 만약 F의 모든 FD가 E⁺에 속한다면, F는 E가 cover한다.

• quivalent 확인
  • E⁺, F⁺를 찾는다.
  • 만약 E⁺와 F⁺가 같다면, E와 F는 서로 cover하는 관계가되며, equivalent하다고 할 수 있다.

Minimal set 찾기

• 함수적 종속성 집합 F가 있다고 가정한다.
• minimal cover찾는 과정은 외부속성을 제거하는 과정을 의미한다.

minimal set 조건

1. 모든 함수적 종속성 집합의 Y가 단일 속성이다.
2. 함수적 종속성 집합에서 1개의 함수적 종속성 FD를 삭제했을때, 여전히 closure가 같다면 minimal이다.
3. Y가 X의 진부분집합일때, 즉, X ⊇ Y일때, X->A를 Y->A로 치환할 수 없을때 minimal이다.

Normalization

정의

• 정규화는 bottom-up design에서 중요한 이론이다.
• 정규화된 각 relation은 1차,2차,3차, BCNF 등으로 나뉘는데, 각 정규화된 relation의 차수가 높다고해서 좋은 디자인이 아니다.

특성

• 따라서, Normalization은 2가지의 특성을 가져야한다.

1. lossless join property(non-addititive)
   • spurious tuple이 없게하기위해
   • 분할은 1번에 2개로 나뉘어 PK, FK로 join이 되도록해야한다.
2. dependency preservation property
   • 원본 테이블의 함수적 종속성을 보존해야하며, closure로 추론될 수 있어야한다.

• 그리고 각 relation schema는 prime attribute와 non-prime attribute로 구분된다.
• prime attribute는 후보키인 속성을 의미한다.

1차 정규화

• 단순, 원자 속성으로만 이뤄진 스키마를 의미한다.
• single, atomic

예시 1

• a는 함수적 종속성을 의미한다.
• DLOCATION은 다중속성이다.
• b는 다중속성 DLOCATION으로 1차 정규형이 아니다.
• c는 1차 정규형을 만족한다.

예시 2

• nested relation을 확인하자.
• 각 직원이 여러 개의 Projs를 가진다고 가정하자.
• b를 확인해보면 Projs는 다중속성으로 1차 정규형을 만족하지 못한다.
• 이를 구분하기 위해서는 c로 바꿔야한다.

2차 정규형

완전종속

• 2차 정규형은 완전 종속의 개념을 기반으로 한다.
• X->Y의 종속성에서 X에서 원소를 하나라도 제거했을때
  • Y가 여전히 의존한다면 부분 종속이며
  • Y가 의존하지 않는다면 완전 종속이다.

2차 정규형 정의

• 모든 non-prime attribute가 relation schema R의 모든 key에 완전 종속할때를 의미한다.
• 모든 key라고 함은 primary key 뿐만 아니라, candidate key를 모두 고려해야한다는 의미이다.

• 위의 예시를 보자.

• ENAME의 경우, 현재 relation의 Primary key SSN, PNUMBER 모두에 종속하지 않고, SSN에만 종속한다. 따라서 PNUBMER를 지워도 종속성이 사라지지 않을 수 있기때문에 부분종속한다.

• PNAME, PLOCATION도 현재 relation Primary key SSN, PNUMBER 모두에 종속하는게 아닌 PNUMBER에만 종속한다. 따라서 부분종속이다.

2차 정규화 예시

• 위 relation을 2차 정규형을 만족하도록 정규화하기 위해서는 현재 relation을 분리해 각 relation이 주키-비주키 종속만 하도록 해야한다.
• relation이 2차 정규형을 만족하는지 확인하는 빠른 방법은
  1. 비주키 속성의 종속관계를 확인한다.
  2. 비주키 속성이 현재 relation의 primary key의 일부분에만 종속한다면 2차 정규형이 아니다.

• 2차 정규화한 테이블

LOT 예시

• LOTS 테이블의 현재 상태를 보면 1차 정규화된 상태임을 알 수 있다.
• 이를 2차 정규화를 시키기 위해선 non-prime 속성들이 prime attribute에 완전 종속하는지 파악해야한다.
• 이 테이블에서 prime attribute들은 PROPERTY_ID#, OUNTY_NAME, LOT#이고, 나머지는 아니다.
• AREA, PRICE는 모두 PROPERTY_ID#, {COUNTY_NAME, LOT#}에 완전종속한다.
• TAX_RATE은 후보키 속성인 {COUNTY_NAME, LOT#} 중 COUNT_NAME에만 부분종속하므로 2차정규형이 아니다.

• 이를 2차정규형으로 만들기 위해서는 COUNTY_NAME->TAX_RATE을 따로 분리해야한다.

3차 정규형

이전종속

• 3차 정규형은 이전종속의 개념을 기반으로한다.
• transitive dependency라고 부른다.
• 이전 종속은 candidate key의 부분집합이 아닌 Z가 X->Z, Z->Y의 종속성을 만족하는 것을 의미한다.

3차 정규형 정의

• 3차 정규형은 2NF를 만족하면서 이전종속이 없는 relation을 의미한다.
• 즉, 2NF가 단일 속성을 만족하면서 부분종속이 없는 정규형이므로,
• 3NF는
  1. 단일 속성으로만 이뤄짐
  2. 부분 종속이 없음(candidate key의 일부분에만 종속하는 FD가 없음)
  3. 이전 종속이 없음(candidate key가 아닌 속성 부분집합 Z충, X->Z->Y를 만족하는 속성이 없음)
• 을 만족해야한다.

3차 정규형 예시

• 위의 예시를 보면, SSN이 유일한 candidate key임을 알 수 있다.
• DNUMBER의 경우, candidate key가 아닌데, DNUMBER를 통해
• SSN->DNUMBER->{DNAME, DMGRSSN}을 만족하므로, 이전종속이다.
• 따라서 위의 예시는 3차 정규형이 아니다.

• 3차 정규화를 시키면 아래와같이 된다.

3차 정규형의 일반적인 정의

1. 부분 종속이 없어야 한다.
   • candidate key들의 진부분집합(proper subset)이 nonprime attribute를 결정해서는 안된다.
2. 이전 종속이 없어야 한다.
   • nonprime attribute에 의해 다른 nonprime attribute가 결정되어서는 안된다.

LOTS 예시

• 위에서 2차 정규형을 만족한 테이에서 AREA->PRICE로 non-prime attribute간 함수적 종속을 이루고 있으므로, 이를 분리해야한다.

BCNF

BCNF정의

• BCNF는 3NF의 간소화된 형태로 주어진다.

• 따라서 BCNF의 모든 relation은 3NF에 속한다.

• 3NF가 2차정규형을 만족하면서 이전종속이 없는 relation이다.
• 단, 3NF는 non-prime attribute가 candidate key를 종속하는 것에는 제약이 없다.
• 따라서 3NF ⊇ BCNF가 성립한다.

• BCNF는 3차정규형이면서 relation의 FD X->Y의 모든 X가 super key여야한다.
• super key란 해당 key로 모든 relation의 속성이 결정되는 것을 의미한다.
  • R{A,B,C,D,E,F}
    • {A,B,C,D}->{E,F} : superkey
    • {A,B,D}->{C,E,F} : superkey
    • {A,B,C}->{E,F} : not superkey
    • {A,B,C,D}->{F} : not superkey

LOT예시

• 위의 예시에서 PROPERTY_ID, {COUNTY_NAME, LOT#}이 candidate key이다.
• PROPERTY_ID -> {COUNTY_NAME, LOT#, AREA}에서 PROPERTY_ID 는 superkey이고
• {COUNTY_NAME, LOT#} -> {PROPERTY_ID, AREA}에서 {COUNTY_NAME, LOT#}도 superkey이다.

• 하지만, AREA->COUNTY_NAME 에서 AREA는 super key가 아니므로 분리해야한다.