릴레이션 정규화

1. 개요

- ER 스키마를 릴레이션 스키마로 곧바로 매핑한 결과물 안에는 여러 엔티티가 실제 필요한 수보다 적은 릴레이션 안에 중복하여 존재하는 경우가 있을 수 있으며, 이 경우 데이터의 삽입/수정/삭제 때, 예를 들어 한 튜플에서는 적절히 수정되었으나 다른 튜플에서는 제대로 수정사항이 반영되지 않는 것 같은 여러 문제가 발생할 수 있다. 이러한 문제를 갱신 이상(update anomaly)이라 하며, 이러한 갱신 이상이 나타나지 않도록 릴레이션 스키마를 적절히 분해하는 작업을 릴레이션 정규화(relation normalization)라 한다.

- 정규화의 최우선순위는 갱신 이상이 나타나지 않도록 하는 것이며, 그 다음으로 효율성 등 요소를 고려한다.

- 기본적으로 릴레이션 정규화는 릴레이션을 분해하는 작업이지만, 무조건 릴레이션을 분해한다고 해서 모든 문제가 다 해결되는 것은 아니며 잘못 분해할 경우 분해 전 릴레이션에 있던 엔티티나 엔티티 사이 관계에 관한 정보가 분해 후 사라질 수 있다. 이 경우 분해된 릴레이션을 다시 결합하면 분해 전 릴레이션에 있던 실제 정보가 사라지고 실제 정보와 전혀 무관한 허구의 튜플(이를 ‘가짜 튜플’이라 한다)이 나타나기도 한다. 이런 일을 방지하려면 릴레이션 정규화 시 분해 후 릴레이션들을 다시 결합했을 때 분해 전 릴레이션과 같은 릴레이션을 다시 얻을 수 있도록 분해(loseless decompostion)를 해야 한다.

2. 갱신 이상(update anomaly)

• 수정 이상(modification anomaly): 한 튜플에서는 적절히 수정되었지만 다른 튜플에서는 제대로 수정사항이 반영되지 않는 문제

• 삽입 이상(insertion anomaly): 릴레이션이 적절히 생성되지 않아, 새 엔티티를 DB에 추가하려 해도 아예 할 수 없거나 튜플에 불필요한 정보를 함께 담아아먄 추가할 수 있는 문제. 예를 들면, 부서에 관한 릴레이션이 없는 경우에는 부서를 신설해도 그 부서에 소속된 사원이 아직 없기 때문에 DB에 신설 부서에 관한 정보를 추가할 수 없다.

• 삭제 이상(deletion anomaly): 릴레이션이 적절히 생성되지 않아, 한 튜플을 DB에서 삭제하면 여전히 DB에 필요한 엔티티 정보까지 함께 삭제되는 문제. 예를 들면, 부서에 관한 릴레이션이 없는 경우에 직원이 1명뿐인 부서에서 그 직원이 퇴사를 했다면 그 부서는 아직 존재함에도 그 부서에 관한 정보를 담은 튜플이 더 이상 DB에 없어 그 부서가 아직 존재한다는 정보가 사라진다.

3. 정규화 단계

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

- 릴레이션 내 모든 필드값이 집합을 값으로 갖지 않도록(=atomic하도록) 분해된 릴레이션을 제1정규형이라 한다.

- RDB 모델의 모든 릴레이션 내 모든 필드값은 atomic하므로, 기본적으로 RDB 모델의 모든 릴레이션들은 제1정규형이다. (한편, 릴레이션 내 필드값이 집합을 갖는 것을 허용하는 것은 RDB 모델은 아니지만 그 나름의 여러 장점이 있다. 이러한 데이터베이스 모델을 object-oriented DB라 하며 나름의 영역에서 활용되고 있다.)

- 제1정규화는 다음 과정을 거쳐 할 수 있다.

(1) 필드값으로 집합을 갖는 필드를 기존 릴레이션의 모든 레코드에서 삭제한다.

(2) 그 필드의 값들을 atomic하게 쪼개 기존 릴레이션의 기본키와 함께 새 릴레이션에 추가한다.

- 제1정규형 상태여도 릴레이션 내 갱신 이상 문제가 있을 때에는 추가로 릴레이션 분해를 수행한다.

2) 부분 함수 종속과 제2정규화(Second Normal Form, 2NF)

- 릴레이션 내 각 레코드의 속성별 값의 중복 양상을 보고 릴레이션 스키마의 각 속성 사이 종속관계를 알 수 있다. 예를 들어 어떤 학교 학생들의 신상 정보와 그 학생이 수강 중인 과목이 각 레코드에 담겨 각 학생이 수강 중인 과목 개수만큼 있는 릴레이션이 있을 때, 설사 몇몇 레코드 사이에 일부 값의 중복이 있더라도 일단 하나의 학번에는 오직 하나의 학년만 대응되는 양상이 나타나는 것을 볼 수 있다. 이처럼 그 값에 대응되는 다른 속성의 값이 오직 하나뿐인 속성(또는 여러 속성으로 이루어진 집합)을 그 다른 속성에 대한 결정자(determinant set)라 하며, 그 결정자의 각 값에 대응되는 값을 오로지 하나만 갖는 그 속성을 종속자(dependent attribute)라 한다. 그리고 이 관계를 ‘종속자가 결정자에 함수 종속(functional dependency)한다’라고 표현하기도 한다. (이는 수학의 함수가 정의역의 한 원소에 대해 오로지 공역 내 한 원소만을 가리키도록 정의된 것에서 따온 표현이다.)

• 결정자 A와 종속자 B 사이 관계를 수식으로 A \(\rightarrow\)B로 표현한다.

- 결정자 A가 원소가 둘 이상인 집합(복합 애트리뷰트)일 때, 종속자 B가 A에는 함수 종속 해도 A의 진부분집합들에는 함수 종속 하지 않는다면(=A의 진부분집합들이 결정자일 때에는 한 속성값에 대응되는 속성값이 여럿이라면) ‘B는 A에 완전 함수 종속(full functional dependency)한다’라고 한다. 반대로 B가 A의 진부분집합 중 어느 하나에 함수 종속 하는 경우(=A의 어느 한 진부분집합이 결정자일 때에도 한 속성값에 대응되는 속성값이 하나뿐인 경우)를 두고 ‘B는 A에 부분 함수 종속(partial functional dependency)한다’라고 한다.

• 예를 들어 학생들의 신상 정보와 그 학생이 수강 중인 과목이 담긴 릴레이션의 경우 ‘출석 횟수’ 속성은 결정자 (학번, 수강과목명)에 함수 종속하나 학번이나 수강과목명이 결정자일 때에는 함수 종속 하지 않는다. (따라서 이 경우 출석 횟수 속성은 결정자 (학번, 수강과목명)에 완전 함수 종속한다.) 그러나 ‘학생의 학년’ 속성은 결정자가 (학번, 수강과목명)일 때뿐 아니라 학번일 때에도 함수 종속한다. (즉 학생의 학년 속성은 결정자 (학번, 수강과목명)에 부분 함수 종속한다.)

- 어떤 릴레이션의 기본키가 둘 이상 속성으로 구성돼 있고, 이 릴레이션에 기본키에 부분 함수 종속인 속성이 있다면, 이 릴레이션은 갱신 이상 문제가 발생할 수 있다. 예를 들어, 학생들의 신상 정보와 그 학생이 수강 중인 과목이 담긴 릴레이션의 경우 기본키는 학번과 수강과목명 두 속성으로 구성되는데, 이때 ‘학생의 학년’ 속성은 결정자가 기본키인 (학번, 수강과목명)이 아니라 학번일 때에도 함수 종속한다(각 학번에 대해 오직 하나의 학년만 대응된다). 이때 학년 부분의 필드값에 수정/삽입/삭제 연산 수행 시, 그 레코드에 해당하는 학생의 수강과목이 여럿이기 때문에 릴레이션에 그 학생의 정보를 담고 있으면서 수강과목만 다른 레코드가 또 있을 수 있으며, 이로 인해 갱신 이상 문제가 발생할 수 있다. 이러한 갱신 이상 문제를 해결하기 위해, 그 릴레이션에서 기본키 아닌 속성들이 모두 그 릴레이션의 기본키에 완전 함수 종속하도록 분해된 릴레이션(부분 함수 종속하는 속성을 모두 분리해낸 릴레이션)을 제2정규형이라 한다.

• 제1정규형을 만족하면서 기본키를 구성하는 속성이 하나뿐인 릴레이션은 항상 제2정규형을 만족한다고 본다.

- 제2정규형 상태도 릴레이션 내 갱신 이상 문제가 있을 때에는 추가로 릴레이션 분해를 수행한다.

3) 이행적 함수 종속과 제3정규화(Third Normal Form, 3NF)

- 한 릴레이션에 속하는 속성 A, B, C에 대해 만약 A \(\rightarrow\)B이고 B\(\rightarrow\)C라면 A \(\rightarrow\)C가 성립하며, 이를 ‘C는 A에 이행적으로 함수 종속(transitive functional dependency)한다’라고 한다.

- 어떤 릴레이션이 제1, 제2정규형을 만족한다 하더라도 이행적 함수 종속이 있다면 이 릴레이션은 갱신 이상 문제가 발생할 수 있다. 예를 들어, 릴레이션 스키마를 구성하는 속성들이 학번, 수강 과목명, 그 과목을 가르치는 교수명 세 가지뿐이고 기본키는 학번으로 지정돼 있는 릴레이션이 있다면, 과목명은 학번에 함수 종속하고 교수명은 과목명에 함수 종속하므로 결과적으로 교수명은 학번에 함수 종속한다. 이때 교수명 부분의 필드값에 수정/삽입/삭제 연산 수행 시, 그 교수에게 수업을 듣는 다른 학생들이 여럿 있기 때문에 이로 인해 갱신 이상 문제가 발생할 수 있다. 이러한 갱신 이상 문제를 해결하기 위해, 그 릴레이션의 기본키가 아닌 모든 속성들이 모두 그 릴레이션의 기본키에 이행 함수 종속 하지 않도록 분해된 릴레이션을 제3정규형이라 한다.

- 제3정규형 상태도 릴레이션 내 갱신 이상 문제가 있을 때에는 추가로 릴레이션 분해를 수행한다.

4) BCNF(Boyce-Codd Normal Form)

- 어떤 릴레이션이 제1, 제2, 제3정규형을 만족한다 하더라도 기본키의 어느 한 속성이 그 자체로 후보키가 아닌 속성에 함수 종속하면 이 릴레이션은 갱신 이상 문제가 발생할 수 있다. 예를 들어, 릴레이션 스키마를 구성하는 속성들이 학번, 수강 과목명, 그 과목을 가르치는 교수명 세 가지뿐이고 기본키는 (학번, 과목)으로 지정돼 있는 릴레이션(=과목이 같아도 학생이 다르면 가르치는 교수가 다른 릴레이션)이 있다면, 교수명은 그 자체로 후보키가 아님에도 과목명이 교수명에 함수 종속 한다. 이때 교수명 부분의 필드값에 수정/삽입/삭제 연산 수행 시, 그 교수에게 수업을 듣는 다른 학생들이 여럿 있기 때문에 이로 인해 갱신 이상 문제가 발생할 수 있다. 이러한 갱신 이상 문제를 해결하기 위해, 그 릴레이션의 기본키가 그 자체로 후보키가 아닌 모든 속성들에 함수 종속 하지 않도록 분해된 릴레이션을 BCNF라 한다.

- BCNF로의 릴레이션 분해는 다음 방식으로 한다.

(1) 기본키의 속성 중 함수 종속 하는 속성을 기존 릴레이션에서 제거한 후, 그 속성을 그 속성의 결정자와 결합해 담은 새로운 릴레이션을 만든다.

(2) 기존 릴레이션에서는 그 결정자가 기본키 집합에 포함되며, 새 릴레이션에서는 그 결정자가 유일하게 기본키가 된다. (그리고 그 결정자는 기존 릴레이션에서 새 릴레이션을 참조하는 외래키도 된다.)

4. 역정규화(denormalization)

- 정규화 단계를 진행할수록 릴레이션 내 중복 및 갱신 이상이 감소하며 무결성 제약 조건을 충족하기 위한 코드의 양도 감소하나, 한편으로 이 DB에서 필요한 정보를 추출할 때 필요한 join 연산의 횟수가 정규화 이전보다 훨씬 늘어나 이 DB에서 필요한 정보를 추출하는 효율은 크게 떨어지게 된다.

- 만약 join 연산을 사용해 정보를 추출해야 하는 쿼리는 적게 들어오는 반면 데이터 삽입/수정/삭제는 빈번하게 일어나는 릴레이션들이라면 정규화를 함으로써 이득이 더 크겠지만 반대로 join 연산을 사용해 정보를 추출해야 하는 쿼리는 많이 들어오는 반면 데이터 삽입/수정/삭제는 극히 드물게 일어나는 릴레이션들이라면 정규화의 이득이 크게 떨어진다. 따라서 후자의 경우에는 정규화가 되어 있을 땐 오히려 역정규화를 통해 join되어 있는 릴레이션을 가지고 있는 게 전체 DB의 성능을 크게 높일 수 있다.