Move Fast

  릴레이션 정규화

• 부주의한 데이터베이스 설계는 제어할 수 없는 데이터 중복을 야기하여 여러 가지 갱신 이상(update anomaly)을 유발한다.
• 정규화(Normalization)는 주어진 릴레이션 스키마를 함수적 종속성과 기본 키를 기반으로 분석하여, 원래의 릴레이션을 분해함으로써 중복과 세 가지 갱신(삽입/삭제/수정) 이상을 최소화한다.
• 어떻게 좋은 데이터베이스 설계를 할 것인가, 데이터베이스에 어떤 릴레이션들을 생성할 것인가, 각 릴레이션에 어떤 애트리뷰트들을 둘 것인가는 정규화의 핵심이다.
•  좋은 관계 데이터베이스 스키마를 설계하는 목적

- 정보의 중복과 갱신 이상이 생기지 않도록 하고, 정보의 손실을 막으며, 실세계를 훌륭하게 나타내고, 애트리뷰트들 간의 관계가 잘 표현되는 것을 보장하며, 어떤 무결성 제약조건의 시행을 간단하게 하며, 아울러 효율성 측면도 고려하는 것

- 먼저 갱신 이상이 발생하지 않도록 노력하고 그 다음에 효율성을 고려한다. 효율성을 고려하는 부분에서 부분적 역정규화가 필요할 수 있다.

  갱신 이상(Update Anomaly)

• 수정 이상(Modification Anomaly) : 반복된 데이터 중에 일부만 수정하면 데이터의 불일치가 발생
• 삽입 이상(Insertion Anomaly) : 불필요한 정보를 함께 저장하지 않고는 어떤 정보를 저장하는 것이 불가능

(b, c) 데이터만 삽입하고 싶으나 (a, b)가 함께 삽입되지 않으면 (b, c)를 삽입할 수 없는 경우

• 삭제 이상(Deletion Anomaly) : 유용한 정보를 함께 삭제하지 않고는 어떤 정보를 삭제하는 것이 불가능

(b, c)만 삭제하고 싶으나 (a, b)가 함께 삭제되지 않으면 삭제할 수 없는 경우

위와 같은 구조와 내용을 갖는 사원 릴레이션으로부터 설계를 시작한다고 가정하자. 

이 회사에서는 각 사원이 두 개까지의 부서에 속할 수 있다. 

즉, 각 사원마다 부서 수를 제한하게 된다.

예시 1에서 봤던 릴레이션을 위의 구조로 바꾼다면, 각 사원마다 부서 수를 제한하게 되는 문제점을 해결할 수 있다.

그러나 아래와 같은 문제점이 발생하게 된다.

- 정보의 중복 : 각 사원이 속한 부서 수만큼 동일한 사원의 투플들이 존재하므로 사원번호, 사원이름, 주소, 전화번호 등이 중복되어 저장 공간이 낭비된다.

- 수정 이상 : 만일 어떤 부서의 이름이 바뀔 때 이 부서에 근무하는 일부 사원 투플에서만 부서이름을 변경하면 (부서이름을 한 레코드에서만 변경하면) 다른 사원들과는 부서번호는 동일하나 부서이름이 다른, 데이터베이스 불일치 상태가 된다.

- 삽입 이상 : 만일 어떤 부서를 신설했는데 아직 사원을 한 명도 배정하지 않았다면, 사원번호가 기본 키인데 널 값이 들어가기 때문에 이 부서에 관한 정보를 입력할 수 없다.

- 삭제 이상 : 만일 어떤 부서에 속한 사원이 단 한 명 있는데, 이 사원에 관한 투플을 삭제하면 이 사원이 속한 부서에 관한 정보도 릴레이션에서 삭제된다.

결론적으로, 서로 독립적인 개체를 하나의 릴레이션에 두면 안된다.

  릴레이션 분해

• 하나의 릴레이션을 두 개 이상의 릴레이션으로 나누는 것
• 릴레이션의 분해는 필요한 경우에는 분해된 릴레이션들로부터 원래의 릴레이션을 다시 구할 수 있음(Ex. 조인 연산)을 보장해야 한다.
• 분해를 잘못하면 두 릴레이션들로부터 얻을 수 있는 정보가 원래의 릴레이션이 나타내던 정보보다 적을 수도 있고 많을 수도 있다. (많은 경우: 가짜 투플이 생긴 경우)
• 릴레이션의 분해는 릴레이션에 존재하는 함수적 종속성에 관한 지식을 기반으로 한다.
• Ex. 위의 나쁜 설계의 예시를 분해해보자.

- 부서 이름의 수정 : 어떤 부서에 근무하는 사원이 여러 명 있더라도 사원 릴레이션에는 부서 이름이 포함되어 있지 않으므로 수정 이상이 나타나지 않는다.

- 새로운 부서를 삽입 : 만일 어떤 신설 부서에 사원이 한 명도 배정되지 않았더라도, 부서 릴레이션의 기본 키가 부서번호이므로 이 부서에 관한 정보를 부서 릴레이션에 삽입할 수 있다.

- 마지막 사원 투플을 삭제 : 만일 어느 부서에 속한 유일한 사원에 관한 투플을 삭제하더라도 이 부서에 관한 정보는 부서 릴레이션에 남아 있다.

  정규형(Normal Form)의 종류

• 제 1정규형(First Normal Form)
• 제 2정규형(Second Normal Form)
• 제 3정규형(Third Normal Form)
• BCNF(Boyce-Codd Normal Form)
• 제 4정규형(Fourth Normal Form)
• 제 5정규형(Fifth Normal Form)
• 일반적으로 산업계의 데이터베이스 응용에서 데이터베이스를 설계할 때 BCNF 까지 고려한다.

  관계 데이터베이스 설계의 비공식적인 지침

• 이해하기 쉽고 명확한 스키마 만들기 : 여러 엔티티 타입이나 관계 타입에 속한 애트리뷰트들을 하나의 릴레이션에 포함시키지 않는다.

• 널값 피하기
• 가짜 투플 생기지 않게 하기 (릴레이션 분해[정규화] 전의 릴레이션(기존)의 투플보다 많은 경우)
• 스키마 정제하기

  함수적 종속성의 개요

• 함수적 종속성은 정규화 이론의 핵심
• 릴레이션의 애트리뷰트들의 의미로부터 결정된다.
• 릴레이션 스키마에 대한 적용이지, 릴레이션의 특정 인스턴스에 대한 적용이 아니다.
• 릴레이션의 가능한 모든 인스턴스들이 (어떤 레코드가 삽입되어도) 만족해야 한다.
• 실세계에 대한 지식과 응용의 의미를 기반으로 어떤 함수적 종속성들이 존재하는가를 파악해야 한다.
• 함수적 종속성은 제 2정규형부터 BCNF까지 적용된다.
• 결정자(Determinant)

- 어떤 애트리뷰트의 값은 다른 애트리뷰트의 값을 고유하게 결정할 수 있다.

- 결정자 : 주어진 릴레이션에서 다른 애트리뷰트(또는 애트리뷰트들의 집합)를 고유하게 결정하는 하나 이상의 애트리뷰트

- 기본 키 애트리뷰트는 결정자이다.

- 레코드를 고유하게 식별하지 못하는 애트리뷰트(Ex. 주소)는 다른 애트리뷰트(Ex. 사원이름)를 고유하게 결정하지 못한다.

- 결정자 표기법 : A → B (A가 B를 결정한다. 또는 A는 B의 결정자이다.)

- Ex. 결정자 찾기 예제

위 릴레이션에서는 아래와 같은 결정자들을 발견할 수 있다.

사원번호 → 사원이름

사원번호 → 주소

사원번호 → 전화번호

부서번호 → 부서이름

(사원번호, 부서번호) → 직책

• 함수적 종속성

- 애트리뷰트 A가 애트리뷰트 B의 결정자(A → B)이면, B가 A에 함수적으로 종속한다고 말한다.

- 주어진 릴레이션 R에서 애트리뷰트 B가 애트리뷰트 A에 함수적으로 종속하는 필요 충분 조건은 각 A 값에 대해 반드시 한 개의 B 값이 대응된다.

- Ex. 사원번호가 사원이름, 주소, 전화번호의 결정자이므로 사원이름, 주소, 전화번호는 사원번호에 종속한다. 그러나, 직책은 (사원번호, 부서번호)에 함수적으로 종속하지, 사원번호에 함수적으로 종속하지는 않는다.

• 완전 함수적 종속성(Full Functional Dependency, FFD)

- 주어진 릴레이션 R에서 애트리뷰트 B가 애트리뷰트 A에 함수적으로 종속하면서 애트리뷰트 A의 어떠한 진부분 집합에도 함수적으로 종속하지 않으면, 애트리뷰트 B가 애트리뷰트 A에 완전하게 함수적으로 종속한다고 말한다.

- 여기서 애트리뷰트 A는 복합 애트리뷰트

- Ex. A가 (C, D)로 이루어진 복합 애트리뷰트일 때, A → B = (C, D) → B 이다. 여기서 C → B 또는 D → B 가 아니라면, A → B는 완전 함수적 종속성이다.

• 이행적 함수적 종속성(Transitive Functional Dependency, TFD)

- 한 릴레이션의 애트리뷰트 A, B, C가 주어졌을 때 애트리뷰트 C가 이행적으로 A에 종속한다는 것의 필요 충분 조건

- A가 릴레이션의 기본 키라면 키의 정의에 따라 A→B와 A→C가 성립한다. 만일 C가 A외에 B에도 함수적으로 종속(B→C)한다면 C는 A에 직접 함수적으로 종속하면서 B를 거쳐서 A에 이행적으로 종속한다고 표현한다.

  릴레이션 분해의 특징

• 릴레이션을 분해하면 중복이 감소되고 갱신 이상이 줄어드는 장점이 있다.
• 바람직하지 않은 문제들을 포함하여 몇 가지 잠재적인 문제들을 야기할 수 있다.

- 릴레이션이 분해되기 전에는 조인이 필요 없는 질의가 분해 후에는 조인을 필요로 하는 질의로 바뀔 수 있다.

- 분해된 릴레이션들을 사용하여 원래 릴레이션을 재구성하지 못할 수 있다.

• 릴레이션 분해 시, 기본 키와 외래 키의 관계를 잘 알고 분해해야 한다.
• 분해 후 릴레이션들이 조인을 많이 요구한다면, 이는 분해할 필요가 없는 릴레이션을 분해한 경우(불필요한 분해)이다.
• 완전 함수적 종속성을 만족하는 경우, 두 애트리뷰트(결정자)가 각각 기본 키가 되는 릴레이션으로 분해하는 것은 나쁜 분해이다. (조인하면, 가짜 투플이 생성됨)

  무손실 분해(Lossless Decomposition)

• 분해된 두 릴레이션을 조인했을 때, 원래의 릴레이션에 들어 있는 정보를 완전하게 얻을 수 있는 분해
• 여기서 손실이란 정보의 손실을 의미한다.
• 정보의 손실은 원래의 릴레이션을 분해한 후에 생성된 릴레이션을 조인한 결과에 들어 있는 정보가 원래의 릴레이션에 들어 있는 정보보다 적거나 많은 경우(불일치)를 모두 포함한다.
• 정보의 손실이 발생한 경우 어떤 정보가 줄어들었는지, 늘어났는지 알 수 없다.

  제 1정규형(First Normal Form)

• 한 릴레이션 R이 제 1정규형을 만족할 필요 충분 조건은 릴레이션 R의 모든 애트리뷰트가 단일값을 갖는 것이다.
• 릴레이션의 모든 애트리뷰트에 반복 그룹(Repeating Group), 즉 다치 애트리뷰트가 없으면 제 1정규형을 만족한다.
• 제 1정규형으로 변환하는 방법

- 다치 애트리뷰트에 나타나는 집합에 속한 각 값마다 하나의 투플로 표현한다. (중복 발생)

- 다치 애트리뷰트에 나타나는 값들을 분리해서 새로운 릴레이션에 삽입한다. 원래 릴레이션의 기본 키를 새로운 릴레이션에 애트리뷰트로 추가한다. (두 애트리뷰트는 기본 키의 구성요소)

• 제 1정규형에 존재하는 갱신 이상

- 아래의 릴레이션은 모든 애트리뷰트가 단일값을 가지므로 제 1정규형을 만족한다. 이 릴레이션의 기본 키는 (학번, 과목번호)이다. 그러나 세 가지 갱신 이상이 존재한다.

- 수정 이상 : 한 학과에 소속한 학생 수만큼 그 학과의 전화번호가 중복되어 저장되므로 여러 학생이 소속된 학과의 전화번호가 변경되었을 때 그 학과에 속한 모든 학생들의 투플에서 전화번호를 수정하지 않으면 데이터베이스의 일관성이 유지되지 않는다.

- 삽입 이상 : 한 명의 학생이라도 어떤 학과에 소속되지 않으면(새로 신설된 학과 등의 경우) 이 학과에 관한 투플을 삽입할 수 없다. 학번이 기본 키의 구성요소인데 엔티티 무결성 제약조건에 따라 기본 키에 널값을 입력할 수 없기 때문이다.

- 삭제 이상 : 어떤 학과에 소속된 마지막 학생 투플을 삭제하면 이 학생이 소속된 학과에 관한 정보도 삭제된다.

• 제 1정규형에서 갱신 이상이 생기는 이유 : 기본 키에 대한 부분 함수적 종속성이 존재하므로 분해 시 부분 함수적 종속성을 제거해야 한다.
  

  제 2정규형(Second Normal Form)

• 한 릴레이션 R이 제 2정규형을 만족할 필요 충분 조건은 릴레이션 R이 제 1정규형을 만족하면서, 어떤 후보 키에도 속하지 않는 모든 애트리뷰트들이 R의 기본키에 완전하게 함수적으로 종속하는 것
• 기본 키가 두 개 이상의 애트리뷰트로 구성되었을 경우에만 제 1정규형이 제 2정규형을 만족하는가를 고려할 필요가 있다.
• 제 2 정규형에 존재하는 갱신 이상

- 아래의 릴레이션의 기본 키는 한 애트리뷰트인 학번이므로 제 2정규형을 만족한다. 그러나, 세 가지 갱신 이상이 존재한다.

- 수정 이상 : 여러 학생이 소속된 학과의 전화번호가 변경되었을 때 그 학과에 속한 모든 학생들의 투플에서 전화번호를 수정하지 않으면 데이터베이스의 일관성이 유지되지 않는다.

- 삽입 이상 : 어떤 학과를 신설해서 아직 소속 학생이 없으면(새로 신설된 학과 등의 경우) 그 학과의 정보를 입력할 수 없다. 학번이 기본 키의 구성요소인데 엔티티 무결성 제약조건에 따라 기본 키에 널값을 입력할 수 없기 때문이다.

- 삭제 이상 : 어떤 학과에서 마지막 학생의 투플이 삭제되면 그 학과의 정보도 함께 삭제된다.

• 제 2정규형에서 갱신 이상이 생기는 이유 : 학번 → 학과이름, 학번 → 학과전화번호인 상태에서 학과이름이 학과전화번호를 결정하기 때문에(학과이름 → 학과전화번호) 이행적 함수적 종속성이 존재한다. 따라서 릴레이션 분해 시 이행적 함수적 종속성을 제거해야 한다.

  제 3정규형(Third Normal Form)

• 한 릴레이션 R이 제 3정규형을 만족할 필요 충분 조건은 릴레이션 R이 제 2정규형을 만족하면서, 키가 아닌 모든 애트리뷰트가 릴레이션 R의 기본키에 이행적으로 종속하지 않는 것(직접 종속)
• 제 3정규형에 존재하는 갱신 이상

- 아래의 릴레이션에서 각 학생은 여러 과목을 수강할 수 있고, 각 강사는 한 과목만 가르친다. 이 릴레이션의 기본 키는 (학번, 과목)이다.

* 학번이나 과목 하나로는 강사 애트리뷰트를 결정하지 못한다. (직접 종속) *

- 키가 아닌 강사 애트리뷰트가 기본 키에 완전하게 함수적으로 종속하므로 제 2정규형을 만족하고, 키가 아닌 강사 애트리뷰트가 기본 키에 직접 종속하므로 제 3정규형도 만족한다.

- 단, 또 다른 함수적 종속성(강사 → 과목)이 존재한다.

- 수정 이상 : 여러 학생이 수강 중인 어떤 과목의 강사가 변경되었을 때 그 과목을 수강하는 모든 학생들의 투플에서 강사를 수정하지 않으면 데이터베이스의 일관성이 유지되지 않는다.

- 삽입 이상 : 어떤 과목을 신설하여 아직 수강하는 학생이 없으면 어떤 강사가 그 과목을 가르친다는 정보를 입력할 수 없다. 학번이 기본 키를 구성하는 애트리뷰트인데 엔티티 무결성 제약조건에 따라 기본 키를 구성하는 애트리뷰트에 널값을 입력할 수 없기 때문이다.

- 삭제 이상 : 어떤 과목을 이수하는 학생이 한 명밖에 없을 경우 이 학생의 투플을 삭제하면 그 과목을 가르치는 강사에 관한 정보도 함께 삭제된다. (실제 상황에서는 몇 명 이상일 경우 강의를 개설한다는 조건이 붙으나, 여기서는 그 조건이 없다고 가정한다.)

• 제 3정규형에서 갱신 이상이 생기는 이유 : 릴레이션에서 키가 아닌 애트리뷰트가 다른 애트리뷰트를 결정하기 때문이다. 위의 릴레이션의 후보키는 (학번, 과목)과 (학번, 강사)인데 강사 애트리뷰트가 과목 애트리뷰트를 결정하고 있다.
  

  BCNF

• 한 릴레이션 R이 BCNF를 만족할 필요 충분 조건은 릴레이션 R이 제 3정규형을 만족하고, 모든 결정자가 후보 키이어야 한다.
• 위의 예시처럼 수강 릴레이션에서 강사 애트리뷰트는 후보 키가 아님에도 불구하고 과목 애트리뷰트를 결정하기 때문에 BCNF가 아니다.
• 제 3정규형을 만족하는 대부분의 릴레이션들은 BCNF도 만족한다.
• 하나의 후보 키만을 가진 릴레이션이 제 3정규형을 만족하면 동시에 BCNF도 만족한다.
• 제 3정규형을 만족하는 릴레이션을 BCNF로 정규화하려면 키가 아니면서 결정자 역할을 하는 애트리뷰트와 그 결정자에 함수적으로 종속하는 애트리뷰트가 포함된 릴레이션을 하나 생성한다. 이 릴레이션에서 결정자는 기본 키가 된다.
• 이후 기존 릴레이션에 결정자를 남겨서 외래 키 역할과 동시에 기본 키의 구성요소가 되도록 한다.

[ 제 3 정규형의 릴레이션을 분해한 결과 ]

  정리

• 정규화 단계가 진행될수록 중복이 감소하고 갱신 이상도 감소된다.
• 정규화가 진전될수록 무결성 제약조건을 시행하기 위해 필요한 코드의 양도 감소된다.
• 정규화가 데이터베이스 설계의 중요한 요소이지만 성능상의 관점에서만 보면 높은 정규형을 만족하는 릴레이션 스키마가 항상 최적인 것은 아니다.
• 한 정규형에서 다음 정규형으로 진행될 때마다 하나의 릴레이션이 최소한 두 개의 릴레이션으로 분해된다.
• 분해되기 전의 릴레이션을 대상으로 질의를 할 때는 조인이 필요 없지만, 분해된 릴레이션을 대상으로 질의를 할 때는 같은 정보를 얻기 위해서 보다 많은 릴레이션들을 접근해야 하므로 조인의 필요성이 증가한다.

  역정규화(Denormalization)

• 데이터베이스 설계자는 응용의 요구 사항에 따라 데이터베이스 설계의 일부분을 역정규화함으로써, 데이터 중복 및 갱신 이상을 대가로 치르면서라도 성능상의 요구를 만족시킬 필요가 있다.
• 역정규화 : 주어진 응용에서 빈번하게 수행되는 검색 질의들의 수행 속도를 높이기 위해서 이미 분해된 두 개 이상의 릴레이션들을 합쳐서 하나의 릴레이션으로 만드는 작업
• 많은 데이터베이스 응용에서 검색 질의의 비율이 갱신 질의의 비율보다 훨씬 높다.
• 역정규화는 쉽게 말해 보다 낮은 정규형으로 되돌아가는 것이다.
• Ex. 제 3정규형을 만족하지 않더라도 발생하는 문제가 빈도 수가 적은 등의 감수할만한 상황인 경우 역정규화를 통해 제 2정규형만 만족하도록 한다.