Algorithm for Decomposition 문서 원본 보기

상위 문서: [[Relational Database Design]]

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

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

===Testing for BCNF===
릴레이션 스키마 R이 BCNF에 속하는지 테스트하는 것은, 특정 경우에 단순화될 수 있다:
* 비자명한(Non-trivial) 함수 종속성 <code>α → β</code>가 BCNF를 위반하는지를 확인하기 위해서는, α<sup>+</sup><ref>함수 종속성 집합 F 하에서 α에 의해 함수적으로 결정되는 모든 속성들의 집합, 즉 α의 폐포(closure)이다.</ref>를 계산하고, <code>α<sup>+</sup> = R</code>를 만족하는지 확인하면 된다. 즉, 즉, α가 R의 수퍼키인지 확인한다.
* 릴레이션 스키마 R이 BCNF에 속하는지 확인하기 위해, F<sup>+</sup>에 있는 모든 함수 종속성을 확인할 필요 없이, 주어진 종속성 집합 F에 있는 종속성만 검사해도 충분하다.
F에 있는 함수 종속성 중 어떤 것도 BCNF를 위반하지 않는다면, F<sup>+</sup>에 있는 함수 종속성들 중 어떤 것도 BCNF를 위반하지 않는다. 하지만 이는 릴레이션 스키마가 분해된 경우에는 동작하지 않는다. 즉, 릴레이션 R에서 분해되어 생긴 Ri가 BCNF에 속하는지 테스트할 때 함수 종속성 F만을 사용하는 것은 충분하지 않다.<br>
예를 들어, (A, B, C, D, E)라는 릴레이션 스키마에 함수 종속성 집합 <code>F = {A → B, BC → D}</code>가 존재한다고 하자. 해당 릴레이션을 (A, B)와 (A, C, D, E)로 분해하였을 때, (A, C, D, E) 릴레이션 스키마는 속성 집합 B를 가지지 않고, 이에 따라 F에 존재하는 함수 종속성 집합은 해당 스키마와 무관하므로, BCNF에 속하는 것처럼 보일 수 있다. 하지만 실제로는 F에서 함수 종속성 <code>AC → D</code>가 유도될 수 있으며, 이는 릴레이션 스키마 (A, C, D, E)가 BCNF에 속하지 않음을 보여준다. 왜냐하면, <code>AC<sup>+</sup> = {A, C, D}</code>이므로 AC는 슈퍼키가 아니기 때문이다. 따라서 분해된 릴레이션이 BCNF를 만족하지 않음을 보이기 위해, F에는 없고 F⁺에만 있는 종속성이 필요할 수 있다.

이에 따라 F<sup>+</sup>의 모든 종속성을 계산하지 않고, R을 분해한 Ri가 BCNF에 속하는지 확인하려면 다음 방식을 사용한다:
* Ri의 속성 부분집합 α에 대해, α<sup>+</sup>가 {Ri − α}의 어떤 속성도 포함하지 않거나,<ref>아예 무관한 함수 종속성이라는 뜻이다.</ref> 또는 Ri의 모든 속성을 포함해야 한다.<ref>α가 슈퍼키라는 뜻이다.</ref> 
* 이 조건이 어떤 α에 의해 위반된다면, <code> α → (α<sup>+</sup> − α) ∩ Ri</code>이 F<sup>+</sup>에 존재함을 보일 수 있다. 이는 Ri가 BCNF를 위반함을 보여준다.

===BCNF Decomposition Algorithm===
BCNF를 만족하도록 릴레이션을 분해하는 알고리즘은 아래와 같다:
<syntaxhighlight lang="go">
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;
</syntaxhighlight>
이 알고리즘은 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
이 스키마의 후보키는 <code>{course_id, sec_id, semester, year}</code>이며, 아래와 같이 알고리즘을 적용할 수 있다:
# 함수 종속성 <code>course_id → title, dept_name, credits</code>에서, course_id가 슈퍼키가 아니므로 BCNF 위반이다. 따라서 class를 아래와 같이 분리한다.
#* <code>course(course_id, title, dept_name, credits)</code>
#* <code>class-1(course_id, sec_id, semester, year, building, room_number, capacity, time_slot_id)</code>
#* course 릴레이션에 대해, 모든 비자명한 함수 종속성은 좌변에 course_id를 포함하며, 이는 course의 수퍼키이므로 course는 BCNF이다.
# class-1에 대해, 후보 키는 여전히 <code>{course_id, sec_id, semester, year}</code>이다. 이때, 함수 종속성 <code>building, room_number → capacity</code>는 유지되지만, <code>{building, room_number}</code>는 수퍼키가 아니므로 BCNF 위반이다. 이에 따라 class-1을 다음 두 릴레이션으로 분해한다.
#* <code>classroom(building, room_number, capacity)</code>
#* <code>section(course_id, sec_id, semester, building, room_number, time_slot_id)</code>
이에 따라 class 릴레이션의 분해는 course, classroom, section의 세 릴레이션으로 구성된다. 이들은 모두 BCNF를 만족한다.

==각주==
[[분류:데이터베이스 시스템]]