Algorithm for Decomposition

상위 문서: Relational Database Design

개요

실제의 데이터베이스 스키마는 매우 복잡하고 거대하므로, 적절한 정규형(normal forms)을 만족하는 디자인을 생성하기 위한 알고리즘을 필요로 한다.

BCNF Decomposition

BCNF의 정의는 어떤 릴레이션이 BCNF를 만족하는지 테스트하는 데 직접적으로 사용할 수 있다. 하지만 이를 위해서는 F⁺을 계산하여 해당 함수 종속성의 왼쪽 항이 슈퍼키에 해당하는지 살펴보아야 하며, 이는 매우 지루한 작업이다. 따라서 어떤 릴레이션이 BCNF인지 아닌지를 확인하는 작업은 단순화될 필요가 있다. 또한, 이를 바탕으로 어떤 릴레이션을 BCNF에 속하도록 분해하면서 lossless decomposition을 만드는 알고리즘 또한 매우 중요하다.

Testing for BCNF

릴레이션 스키마 R이 BCNF에 속하는지 테스트하는 것은, 특정 경우에 단순화될 수 있다:

• 비자명한(Non-trivial) 함수 종속성 α → β가 BCNF를 위반하는지를 확인하기 위해서는, α⁺를 계산하고, α+ = R를 만족하는지 확인하면 된다. 즉, 즉, α가 R의 수퍼키인지 확인한다.
• 릴레이션 스키마 R이 BCNF에 속하는지 확인하기 위해, F⁺에 있는 모든 함수 종속성을 확인할 필요 없이, 주어진 종속성 집합 F에 있는 종속성만 검사해도 충분하다.

F에 있는 함수 종속성 중 어떤 것도 BCNF를 위반하지 않는다면, F⁺에 있는 함수 종속성들 중 어떤 것도 BCNF를 위반하지 않는다. 하지만 이는 릴레이션 스키마가 분해된 경우에는 동작하지 않는다. 즉, 릴레이션 R에서 분해되어 생긴 Ri가 BCNF에 속하는지 테스트할 때 함수 종속성 F만을 사용하는 것은 충분하지 않다.
예를 들어, (A, B, C, D, E)라는 릴레이션 스키마에 함수 종속성 집합 F = {A → B, BC → D}가 존재한다고 하자. 해당 릴레이션을 (A, B)와 (A, C, D, E)로 분해하였을 때, (A, C, D, E) 릴레이션 스키마는 속성 집합 B를 가지지 않고, 이에 따라 F에 존재하는 함수 종속성 집합은 해당 스키마와 무관하므로, BCNF에 속하는 것처럼 보일 수 있다. 하지만 실제로는 F에서 함수 종속성 AC → D가 유도될 수 있으며, 이는 릴레이션 스키마 (A, C, D, E)가 BCNF에 속하지 않음을 보여준다. 왜냐하면, AC+ = {A, C, D}이므로 AC는 슈퍼키가 아니기 때문이다. 따라서 분해된 릴레이션이 BCNF를 만족하지 않음을 보이기 위해, F에는 없고 F⁺에만 있는 종속성이 필요할 수 있다.

이에 따라 F⁺의 모든 종속성을 계산하지 않고, R을 분해한 Ri가 BCNF에 속하는지 확인하려면 다음 방식을 사용한다:

• Ri의 속성 부분집합 α에 대해, α⁺가 {Ri − α}의 어떤 속성도 포함하지 않거나, 또는 Ri의 모든 속성을 포함해야 한다.
• 이 조건이 어떤 α에 의해 위반된다면, α → (α+ − α) ∩ Ri이 F⁺에 존재함을 보일 수 있다. 이는 Ri가 BCNF를 위반함을 보여준다.

BCNF Decomposition Algorithm

BCNF를 만족하도록 릴레이션을 분해하는 알고리즘은 아래와 같다:

result := {R}; //시작은 전체 릴레이션으로 시작
done := false;
while (not done) do //더 이상 분해할 필요가 없을 때까지
    if (there is a schema Ri in result that is not in BCNF) //result 집합 안에 BCNF에 속하지 않는 스키마 Ri가 있는지 확인
    then begin
        //스키마 Ri에서 비자명한 함수 종속성 α → β 선택
        //α는 슈퍼키가 아니고, α ∩ β = ∅를 만족
        let α → β be a nontrivial functional dependency that holds 
        on Ri such that α⁺ does not contain Ri and α ∩ β = ∅;
        //Ri를 {Ri − β}, {α ∪ β}로 분해 후, result에서 Ri를 제거하고 두 릴레이션을 추가
        result := (result − Ri) ∪ (Ri − β) ∪ (α, β);
    end
    else done := true;

이 알고리즘은 BCNF를 위반하는 종속성을 사용하여 분해를 수행한다. 이 알고리즘이 생성하는 분해는 BCNF를 만족할 뿐만 아니라 손실 없는 분해(lossless decomposition)이기도 하다.

다음은 BCNF 분해 알고리즘을 사용한 긴 예시이다. 아래와 같은 스키마를 가진 class 릴레이션을 사용하는 데이터베이스를 고려하자:

class(course_id, title, dept_name, credits,
      sec_id, semester, year,
      building, room_number, capacity, time_slot_id)

이에 대해 아래의 함수 종속성 집합이 존재한다:

course_id → title, dept_name, credits
building, room_number → capacity
course_id, sec_id, semester, year → building, room_number, time_slot_id

이 스키마의 후보키는 {course_id, sec_id, semester, year}이다. 이때 함수 종속성 course_id → title, dept_name, credits에서, course_id가 슈퍼키가 아니므로 BCNF 위반이다. 따라서 class를 아래와 같이 분리한다:

course(course_id, title, dept_name, credits)
class-1(course_id, sec_id, semester, year, building, room_number, capacity, time_slot_id) 

course 릴레이션에 대해, 모든 비자명한 함수 종속성은 좌변에 course_id를 포함하며, 이는 course의 수퍼키이므로 course는 BCNF이다. 또한 class-1에 대해, 후보 키는 여전히 {course_id, sec_id, semester, year}이다. 이때, 함수 종속성 building, room_number → capacity는 유지되지만, {building, room_number}는 슈퍼키가 아니므로 BCNF 위반이다. 이에 따라 class-1을 다음 두 릴레이션으로 분해한다:

classroom(building, room_number, capacity)
section(course_id, sec_id, semester, building, room_number, time_slot_id)

이에 따라 class 릴레이션의 분해는 course, classroom, section의 세 릴레이션으로 구성된다. 이들은 모두 BCNF를 만족한다.

Third Normal Form Decomposition

BCNF는 항상 종속성 보존을 보존하지 않는다. 또한, 많은 경우 업데이트 시에 함수 종속성 위배 여부를 효율적으로 검증하는 것이 중요하다. 이에 따라 BCNF보다 더 약한 수준의 정규형인 3NF이 사용된다. 이는 어느 정도의 중복을 허용하지만, 개별 릴레이션에서 조인 연산 없이 함수 종속성을 검사할 수 있다는 장점을 가진다. 또한 항상 손실없는 분해와 종속성 보존을 만족하는 3NF 분해가 가능하다는 장점이 있다.

Testing for 3NF

어떤 릴레이션이 3NF에 속하는지 검사할 때에는 함수 종속성 집합 F⁺을 계산할 필요가 없다. 단지 F에 있는 각 종속성 α → β에 대해 다음과 같이 검사하면 된다.

• α가 슈퍼키에 속하는가? → α⁺를 활용하여 확인한다.
• β−α에 속하는 각 속성 A가 후보키에 속하는가?

3NF 만족 여부 판단은 NP-HARD 문제이므로 다항 시간에 풀 수 없어 비용이 큰 편이다.

3NF Decomposition Algorithm

3NF를 만족하도록 릴레이션을 분해하는 알고리즘은 아래와 같다:

Let Fc be a canonical cover for F; //Fc 설정
i := 0;
for each functional dependency α → β in Fc do //Fc의 각 함수 종속성에 대해
    begin
        i := i + 1; //함수 종속성의 개수를 카운트
        Ri := α ∪ β //1~i 번째 릴레이션 설정
    end

if none of the schemas Rj, 1 ≤ j ≤ i contains a candidate key for R then //생성된 릴레이션이 어떤 후보키도 포함하지 않으면
    begin
        i := i + 1; 
        Ri := any candidate key for R; //후보키로 이뤄진 릴레이션 설정
    end

repeat
    if any schema Rt is contained in another schema Rk then //중복되는 릴레이션 제거
        Rt := Ri;
        i := i - 1;

return (R1, R2, ..., Ri)

아래는 위 3NF 분해 알고리즘을 사용한 긴 예시이다. 아래와 같은 스키마를 가진 cust_banker_branch 릴레이션을 사용하는 데이터베이스를 고려하자:

cust_banker_branch (customer_id, employee_id, branch_name, type)

이에 대해 아래의 함수 종속성 집합이 존재한다:

customer_id, employee_id → branch_name, type
employee_id → branch_name
customer_id, branch_name → employee_id

Canonical cover F_c을 계산하면 아래와 같다:

customer_id, employee_id → type
employee_id → branch_name
customer_id, branch_name → employee_id

이때 위의 3NF 분해 알고리즘의 for문 부분을 적용하면, 아래와 같은 3개의 스키마가 생성된다.

(customer_id, employee_id, type)
(employee_id, branch_name)
(customer_id, branch_name, employee_id)

이때 첫 스키마 (customer_id, employee_id, type)가 후보키 (customer_id, employee_id)를 포함하므로, 추가적인 분해는 불필요하다. 이때 스키마 중에서, 포함관계가 존재하는 (employee_id, branch_name)는 제거할 수 있다. 따라서 최종적으로 분해된 스키마는 아래와 같다:

(customer_id, employee_id, type)
(customer_id, branch_name, employee_id)