Decomposition

관계형 데이터베이스를 설계하는 과정에서 관계형 스키마Relation Schema를 생성하는 과정에 초점을 맞춰보자. 이 과정에서 고려해야 할 것은 관계형 스키마를 "좋은 형태"로 빚어내는 것이다. 그렇다면 이 "좋은 형태"란 도대체 무엇인가? 바로 연산 과정에서, 특히 데이터베이스에 정보를 추가하거나 검색할 때 중복하지 않는 형태다. 이러한 "좋은 형태"에는 여러 유형이 있는데, 이들을 정규형Normal Form라고 한다. 만약 관계형 스키마가 "좋은 형태"가 아니라면 그때는 "좋은 형태"의 관계형 스키마만 남도록 기존의 관계형 스키마를 분할해야 하는데, 이 과정을 분해Decomposition라 부른다.

분해의 핵심은 정규형이 아닌 관계형 스키마를 정규형으로 만드는 것이다. 아래 그림은 이를 제대로 수행하지 못한 나쁜 분해의 예시다.

$employee$라는 관계형 스키마를 둘로 분해한 다음 내추럴 조인(Natural Join) 연산을 통해 다시 원래대로 합치려 하니 정보를 잘못 섞는 바람에 이름이 $Kim$으로 같은 두 직원의 정보가 불분명해졌다. 이렇듯 정보의 손실을 야기하는 나쁜 분해를 손실 분해Lossy Decomposition이라 부르며, 이와 반대로 정보의 손실 없이 이루어진 분해를 무손실 분해Lossless Decomposition이라 부른다.

Lossless Decomposition

조금 더 엄밀하게 정의해보자. $R = R_1 \cup R_2$ 를 만족하는 관계형 스키마 $R$, $R_1$, $R_2$에 대하여 $R$을 $R_1$과 $R_2$로 대체했을 때 정보의 손실이 일어나지 않는다면, $R$을 $R_1$과 $R_2$로 나누는 그 분해는 무손실 분해이다. 이 정의 다음의 SQL 명령을 실행했을 때 원본인 $R$ 전체를 쿼리했을 때와 같은 결과가 나와야 한다는 것을 의미한다.

select *
from (select R_1 from r)
	natural join
	(select R_2 from r)

관계 대수Relational Algebra의 측면에서 무손실 분할은 곧 아래와 같은 식이 성립한다는 것과 같다. 이 식은 관계형 스키마가 $R$인 관계 $r$에서 에서 $R_1$과 $R_2$에 해당하는 속성만 드러나도록 프로젝트(project)¹ 연산을 수행한 뒤 그 결과끼리 Join 연산을 수행하면 그 결과가 $r$이 된다는 의미다.

$$\prod\nolimits_{R_1}(r) \bowtie \prod\nolimits_{R_2}(r) = r$$

Lossy Decomposition

$R = R_1 \cup R_2$ 를 만족하는 관계형 스키마 $R$, $R_1$, $R_2$에 대하여 만약 정보의 손실이 일어나는 손실 분해가 이루어졌다면 SQL과 관계 대수의 결과 모두 원본을 포함한다. 즉, $\prod\nolimits_{R_1}(r) \bowtie \prod\nolimits_{R_2}(r) \supset r$이다. 더 큰 집합임에도 불구하고 정보의 손실이 일어났다고 정의하는 이유는 위에서 살펴본 사례처럼 일부 속성의 값이 같은 서로 다른 두 데이터를 구분하기 위해 사용했던 정보를 더이상 활용할 수 없게 되었기 때문이다.

Decomposition & Functional Dependency

함수 의존성Functional Dependency를 통해 분해의 손실 여부를 보여줄 수도 있다. Relation Schema $R, R_1, R_2$ 와 $R$의 함수 의존성 집합 $F$에 대하여 함수 의존성 $R_1 \cap R_2 \to R_1$ 혹은 $R_1 \cap R_2 \to R_2$ 중 최소 하나가 $F^+$에 존재한다면, $R$을 $R_1$과 $R_2$로 나누는 분해는 손실이 없다. 그리고 이는 곧 $R_1 \cap R_2$가 $R_1$이나 $R_2$의 슈퍼키가 된다는 것을 의미하기도 한다. 다만 이를 위해서는 데이터베이스의 모든 제약 조건이 함수 의존성으로 표현 가능해야만 한다. 또한 관계형 스키마가 각각 $R_1, R_2$인 관계 $r_1, r_2$에 대하여 $R_1 \cap R_2 \to R_1$이 유지될 때, $R_1 \cap R_2$가 $r_1$의 주요 키Primary Key가 되어야 함수 의존성이 강제되고, $R_1 \cap R_2$가 $r_2$에서 $r_1$을 참조하는 외래 키Foreign Key가 되어야 $r_1$이 $r_2$를 대상으로 내추러 조인 연산을 수행했을 때 서로 대응하는 튜플이 나타나지 않는다. 이러한 제약 조건은 원본 스키마 $R$의 특성이 분해된 $R_1, R_2$에서도 유지됨을 보장한다. $r_1, r_2$가 더 세분화되더라도, $R_1 \cap R_2$의 모든 속성이 하나의 관계에 존재하는 한 $r_1$이나 $r_2$에 존재하는 주요 키 제약Primary Key Constraint나 외래 키 제약Foreign Key Constraint는 그 관계에 상속될 것이다.

그래서 분해는 어떻게 해요?

그렇다면 분해는 어떻게 해야 할까? 분해는 정규형으로 해야 한다는 것을 다시금 생각해보자. 정규형에는 다음과 같이 여러가지 유형이 있다.

• Boyce-Codd Normal Form(예정)
• Third Normal Form(예정)
• Fourth Normal Form(예정)
• Project-Join Normal Form(예정)
• Domain-Key Normal Form(예정)

정규형에 따라 분해하는 방법이 다르고 지켜야 할 조건도 다르다. 일부 정규형을 분해하는 과정은 함수 의존성 외에도 다변수 의존성Multivalue Dependency을 활용하기도 한다. 이런 이유로 인해 모든 정규형의 분해 과정을 이 글에서 일일이 추적하기보다는 우선 각각 별도의 글로 다룰 예정이다.

---

출처

• Silberschatz, A., Korth, H.F. and Sudarshan, S. (2020) Database system concepts. Seventh edition. New York, NY: McGraw-Hill

Footnotes

1. 어떤 수열에 대하여 곱셈을 반복하는 연산을 의미한다. 수열의 각 항을 더하는 과정이 시그마($\Sigma$)로 표현되듯 수열의 각 항을 곱하는 연산은 프로젝트로 표현된다. 기호는 그리스 대문자 파이($\Pi$)를 사용한다. ↩