상위 문서: 데이터베이스 시스템
개요
해당 문서와 그 하위 문서에서는 relational 데이터베이스(database)를 위한 스키마(schema)를 설계하는 방법에 대해 다룬다. 일반적으로 relational 데이터베이스를 설계할 때 중요한 것은 불필요한 중복(redundancy)없이 정보를 저장하면서도, 정보를쉽게 검색할 수 있도록 하는 어떤 relation 스키마를 생성하는 것이다. 이는 적절한 정규형(normal form)에 해당하는 스키마를 설계하여 달성할 수 있다. 해당 문서와 그 하위 문서에서 사용하는 대학교의 데이터베이스의 스키마들은 figure 1과 같다.
Features of Good Relational Designs
E-R 모델 설계로 부터 직접 relation 스키마 집합을 생성하는 것이 가능하며, 생성된 relation 스키마 집합의 좋고 나쁨은 기반이 된 E-R 모델의 설계가 얼마나 잘 되었는지에 의해 결정된다. 예를 들어 대학교 엔터프라이즈를 설계할 때, 다음과 같은 스키마로 시작했다고 가정하자.
in_dep (ID, name, salary, dept_name, building, budget)
해당 스키마는 instructor(교수)와 department(학과)에 해당하는 릴레이션 간의 natural join의 결과이다. 이 스키마는 어떤 쿼리에 대해 더 간단히 표현할 수 있기 때문에 좋은 스키마처럼 보일 수 있다. 하지만 이는 문제를 가지고 있다. 이는 figure 2에 제시된 인스턴스에서, 각 학과에 속한 교수마다 학과 정보를 반복해서 저장해야 한다는 것이다. 즉, 불필요한 중복이 스키마 인스턴스에 나타난다. 이는 해당하는 모든 중복되는 튜플의 속성들의 값이 모두 일치해야 하며, 그렇지 않다면 일관성(cinsistency)를 잃게 된다.
또한 in_dep 스키마에는 여전히 다른 문제가 존재한다. 새로운 학과(department)를 생성할 경우, 위의 스키마를 이용한다면 해당 학과에 속한 교수(ID, name, salary)가 적어도 한 명 있어야만 학과에 해당하는 정보(dept_name, building, budget)를 비로소 담을 수 있다.
Decomposition
위의 in_dep 스키마에서 정보 반복 문제(repetition-of-information problem) 를 피할 수 있는 유일한 방법은, 이를 두 개의 스키마로 분해(decompose) 하는 것이다. 이 경우에는 instructor 스키마와 department 스키마로 분해한다. 일반적으로 정보가 반복되는 스키마는 여러 개의 더 작은 스키마로 분해해야 한다.
하지만 모든 분해가 바람직한 것은 아니다. 예를 들어,
employee (ID, name, street, city, salary)
와 같은 스키마를 다음과 같이 분해한다고 가정하자:
employee1 (ID, name) employee2 (name, street, city, salary)
해당 분해가 좋지 않은 이유는, 어떤 기업(enterprise) 내에 이름이 같지만 서로 다른 두 명의 직원이 동명이인으로 존재할 수 있기 때문이다. 예를 들어, 대학에 이름이 Kim인 두 명의 직원이 있다고 가정하면 원래의 employee 스키마에 대해 이 두 직원은 다음과 같은 튜플을 가진다:
(57766, Kim, Main, Perryridge, 75000) (98776, Kim, North, Hampton, 67000)
Figure 3는 위의 원래 튜플과, 원래의 스키마를 분해하여 생성한 스키마를 이용한 튜플들, 해당 스키마들로부터 natural join를 통해 원래의 튜플을 복구하기 위해 시도한 결과를 보여준다. Figure 3에서 알 수 있듯이, 원래의 두 튜플은 물론 이름이 Kim인 두 직원의 데이터를 잘못 조합한 두개의 새로운 튜플도 나타난다. 이는 사실상 정보가 손실된 것이다. 그 이유는 어느 Kim이 어떤 거리(street), 도시(city), 급여(salary) 속성 값을 가지는지 구별할 수 없기 때문이다. 이렇게 분해할 경우 정보가 손실되는 분해를 손실 분해(lossy decomposition) 라고 부르고, 반대로 정보 손실 없이 분해할 수 있는 경우를 손실 없는 분해(lossless decomposition)라고 한다.
Lossless Decomposition
R이 하나의 relation 스키마이고, R1과 R2가 R을 분해하여 형성된 스키마라고 할 때, R, R1, R2를 속성들의 집합이라고 하면 [math]\displaystyle{ R = R1 \cup R2 }[/math]와 같이 나타낼 수 있다. 이때 R을 두 개의 릴레이션 스키마 R1과 R2로 대체했을 때 정보 손실이 없다면, 이 분해를 손실 없는 분해(lossless decomposition)라고 한다. 정보 손실(loss of information) 은, 어떤 경우에 r(R)의 인스턴스(instance)를 가지고 있을 때, r(R)의 인스턴스 대신 r1(R1)과 r2(R2)의 인스턴스를 사용하면 표현할 수 없는 정보가 생기는 경우 발생한다.
조금 더 정확하게는 R에 대한 인스턴스 r이 다음 SQL 쿼리의 결과와 같은 튜플 집합을 가진다면 손실 없는 분해이다:
select *
from (select R1 from r) natural join (select R2 from r)
이를 relational algebra로 표현하면 다음과 같다:
[math]\displaystyle{ \prod_{R1}^{(r)} ⋈ \prod_{R2}^{(r)} = r }[/math]
즉, 인스턴스 r을 각각 R1, R2에 대해 projection를 수행한 결과에 대해 natural join을 수행하면, 정확히 r을 다시 얻을 수 있어야 한다. 반대로, 손실 분해(lossy decomposition)의 경우는, projection를 수행한 결과에 대해 natural join을 수행하면 원래 릴레이션보다 더 큰 집합(proper superset)이 나오는 경우이다. 이를 relational algebra로 표현하면 다음과 같다:
[math]\displaystyle{ r \subset \prod_{R1}^{(r)} ⋈ \prod_{R2} ^{(r)} }[/math]