[데이터베이스] Ch11 RDB design

11.1 Good Schema and Bad Schema

나쁜 테이블의 기준은 무엇일까?

나쁜 테이블은 갱신 이상(update anomaly), 삭제 이상(delete anomaly), 입력 이상(insert anomaly)를 가지고 있다.

우선 위의 mybadtable1 테이블을 보자.

 

chairman, building, budget 속성 값이 deptName 속성에 의존하고 있는 것을 볼 수 있다.

즉, deptName이 변경되면 나머지 속성들도 같이 바뀌게 되는 것이다.

 

예를 들어서 설명을 해보면

CS학과의 경우, Databases 과목 및 Java 과목이 삭제되는 경우에는 삭제 이상이 발생하지 않는다.

그러나, 남아있는 마지막 과목인 Data Structure가 삭제되면 CS학과에 대한 정보도 영원히 삭제되기 때문에 삭제 이상이 발생한 것이다.

 

입력 이상에 대해서도 언급을 하자면

새로운 학과가 창설되었을 때 학과에 대한 정보를 입력하고자 했다고 가정하자.

그러나 mybadtable1의 주 키는 cID이기 때문에 새로운 학과가 개설하는 과목이 없으면 삽입할 수 없는 것이다.

 

함수 종속성 (Functional Dependencies)

함수 종속성이란, 유효한 관계 인스턴스에 대한 제약으로 키 개념의 일반화라고도 볼 수 있다.

α, β가 R 속성의 일부분이라고 가정하자.

α 속성 값이 동일한 임의의 터플 두 개에서 β 속성 값이 항상 동일하다면 α는 β를 함수적으로 의존한다고 한다.

위의 예시에서 A 속성 값이 같은 터플은 첫 번째와 두 번째 터플이다. 이때 첫 번째와 두 번째 터플 모두 B 속성 값이 동일하다.

그래서 A는 B를 함수적으로 결정한다고 본다. (A → B) (= B는 A에 함수적으로 의존한다.)

 

두 번째와 세 번째 터플의 B 속성 값은 같지만 A 속성 값은 다르므로, B는 A를 함수적으로 결정하지 않는 것이다.

 

함수 종속성과 키와의 관계에 대해서도 알아보자.

- 슈퍼 키는 관계 속성의 일 부분으로서 전체 속성을 함수적으로 결정하는 속성을 의미한다.

- 후보 키는 슈퍼키의 성질을 만족하면서 동시에 슈퍼 키의 서브셋이 없으면 이를 후보키라고 한다.

 

Professor(pID, name, deptName, salary)

위와 같은 Professor 관계가 있다고 할 때 pID는 교수 개개인을 식별할 수 있으므로 슈퍼 키이다.

(pID, name)도 터플을 식별할 수 있기 때문에 슈퍼키이다.

 

후보 키의 경우 pID는 가능하지만 (pID, name)은 불가능하다.

왜냐하면 pID만으로도 고유 식별이 가능하기 때문이다.

 

그렇다면 아래와 같은 관계를 파악할 수 있다.

• pID→name: 교수 ID가 이름을 고유하게 결정
• pID→deptName: 교수 ID가 학과명을 고유하게 결정.
• pID→salary: 교수 ID가 급여를 고유하게 결정.
• pID→name,deptName,salary: 교수 ID가 테이블의 모든 속성을 고유하게 결정.

11.2 Functional Dependency Theory

이제 함수 종속성 이론에 대해 알아볼 것이다.

 

Trivial

함수 종속성이 테이블의 모든 인스턴스에 대해 만족이 되는 경우, 무의미(trivial)하다고 한다.

즉, 함수 종속 α→β에서, β⊆α (즉, β가 α의 부분집합)인 경우, 이 함수 종속성은 무의미한 것이다.

 

이에 대해 더 자세히 설명하자면 

α→β는 α가 β를 결정한다는 의미이다.

그런데 β가 이미 α 속성에 포함되어 있다면 β의 값은 α에 포함된 정보로 인해 자동으로 "결정"되는 것이다.

따라서 무의미하다고 보는 것이다.

• ID name → ID
• name → name

지금까지 이해가 됐다면 위의 두 예제는 당연한 결과임을 알 수 있을 것이다.

 

Closure

함수 종속성은 다른 함수 종속성으로부터 유추할 수 있다.

 

A → B

B → C

로 부터 A → C를 유추할 수 있다.

 

이처럼 주어진 함수 종속성 집합으로부터 유추할 수 있는 모든 함수 종속성을 가진 집합을 함수 종속성 폐포(closure)라고 한다.

 

Armstrong’s Axioms

암스트롱 공리는 새로운 함수 종속성을 유추할 수 있는 추론 규칙이며, 세 가지 추론 규칙으로 구성되어 있다.

• 재귀성(reflexivity): β⊆α라면, α→β
• 부가성(augmentation): α→β라면, α∪γ → β∪γ
• 이행성(transivity) 규칙: α→β이고 β→γ라면, α→γ

이와 관련한 간단한 문제를 풀어보자.

R = (A, B, C, G, H, I)
F = {A → B,  A → C, CG → H, CG → I, B → H}

위와 같은 테이블과 함수 종속성이 주어졌을 때 새로 만들 수 있는 함수 종속성을 추론해 보는 것이다.

 

답은 아래와 같다.

A → H, AG→ I, CG → HI, A → BC

 

마지막 두 개가 이해하기 어려웠기 때문에 짚고 넘어가자면

- CG → I는 CG → CGI로 변환 가능하고, CG → H는 CGI → HI로 변환 가능하다. 즉, 이행성 규칙에 의해 CG → HI가 되는 것이다.

- A → B, A → C이므로 병합규칙에 의해 A → BC가 된다.

 

Closure of Attribute Sets

주어진 속성이 함수적으로 결정할 수 있는 모든 것을 속성 폐포(closure of attributes)라고 한다.

* 앞서 알아본 함수 종속성 폐포와는 다른 개념이니 주의하자.

 

속성 폐포를 구하는 알고리즘은 아래와 같다.

Algorithm to compute α+:
closure := α;
while (changes to closure) do
    for each β → γ in F do
    begin
    	if β ⊆ closure then closure := closure ∪ γ
    end
/* After while loop, variable closure has α+  */

어려워 보이지만 생각보다 간단하다.

closure의 초기값은 α로 잡고 closure가 더 이상 변경되지 않을 때까지 while문을 반복한다.

F에 있는 β → γ를 보고  β가 현재 closure에 포함되어 있다면 γ도 closure에 추가한다.

 

정규 커버(Canonical Cover)

주어진 함수 종속성과 동일한 표현력을 가지면서, 가장 최소한의 속성 및 가장 적은 수의 함수 종속성을 가지는 집합을 정규 커버라고 한다.

 

1. 중복된 함수 종속성

어떤 함수 종속성이 다른 종속성에 의해 유추 가능하다면 이는 중복으로 간주하는 것이다.

F = {A → B, B → C, A → C}

여기서 A → C는 A → B와 B → C를 통해 유추가능하므로 중복이다.

따라서 정규 커버에서는 제거된다.

 

2. 불필요한 속성

어떤 함수 종속성의 일부 속성이 없어도 동일한 유추를 제공할 수 있다면 이는 불필요한 속성으로 간주한다.

F = { A → B, B → C, AC → D}

여기서 AC → D는 불필요하다.

왜냐하면 A → B, B → C로 A → C를 유추할 수 있고,

A → C를 통해 A → D도 유추 가능하다.

따라서 AC → D는 A → D로 간소화된다.

 

11.3 Normal Forms

관계 정규화에는 총 6개의 정규화형이 있다. 그 중 4가지에 대해 알아보자.

 

(1) First Normal Form (1NF)

: 모든 속성은 원자값을 가져야 한다. 즉, 속성값은 더 이상 나눌 수 없는 값이어야 한다.

학생	과목
홍길동	수학
홍길동	과학
이몽룡	영어

위처럼 각 각 속성은 단일 값만 가지고, 각 열은 동일한 데이터 유형이어야 한다.

(원자 값이 아닌 경우로는 집합, 리스트, 백, 복합 속성 등이 있다.)

 

➕완전 함수 종속성 (Full functional dependency)

: 함수 종속성  α→β에서  α의 부분집합 γ에 대하여 γ→β이 성립하지 않으면, α→β는 완전 함수 종속이라고 한다.

 

(2) Second Normal Form (2NF)

: 1NF를 만족하고, 비주요 속성이 모든 후보 키에 완전 의존적이어야 한다.

R(SSN, pNumber, hours, eName, pName, pLocation)

SSN pNumber → hours
SSN → eName
pNumber → pName pLocation

 

위 예제에서 테이블 R의 후보 키는 SSN과 pNumber이다.

그런데, 비주요 속성인 eName이 후보 키에 부분적으로 의존하고 있으므로 테이블 R은 제 2정규형이 아니다.

 

이를 제 2정규형에 부합하도록 분해하면 다음과 같다.

R1(SSN, pNumber, hours)
R2(SSN, eName)
R3(pNumber, pName, pLocation)

테이블 R1, R2, R3에 대하여 모든 비주요 속성이 후보 키에 의존하고 있음을 볼 수 있다.

 

(3) Third Normal Form (3NF)

: 2NF를 만족하고, 비주요 속성이 모든 후보 키에 이행적으로 의존적이면 안된다. (= 이행 종속성이 제거됨)

(이행 종속성은 비주요 속성이 다른 비주요 속성을 통해 종속되는 경우를 의미한다.)

 

의미적으로 제 2정규형과 동일하나 또 다른 제 3정규형의 정의는 

"모든 함수 종속성 α→β에서 α가 슈퍼 키이거나 β가 주요 속성이어야 한다."이다.

 

(4) Boyce/Codd Normal Form (BCNF)

: 관계형 스키마가 모든 의미 있는 함수 종속성 α→β에서 α가 슈퍼 키인 것이다.

 

바로 위에서 정의한 제 3정규형의 또 다른 정의를 제거한 것이 BCNF이다.

지금까지 설명한 정규형 간의 관계를 나타낸 그림이다.

실세계에서는 제 3정규형과 BCFN 정규형을 사용하는 것을 권장하고 있다.