BCNF로 무손실 조인 분해하는 방식은, 3NF로 무손실 조인 분해하는 방식에 역시 그대로 적용될 수 있다(알고리즘의 수행 단계에서 3NF 릴레이션들을 모두 얻게 되면 수행을 종료하면 된다). 그러나, 이 방법은 항상 종속성 유지를 보장하지 않는다.
3NF 릴레이션들로 분해하는 알고리즘을 설명하기 전에, 최소 커버라는 개념이 필요하다. FD들의 집합 F에 대한 최소 커버는 다음 조건을 만족하는 FD들의 집합 G로 정의된다.
1. G에 속하는 모든 종속성들은 X → A의 형태이고, 이때 A는 단일 애트리뷰트이다.
2. 폐쇄 F+는 폐쇄 G+와 동등하다.
3. 만약 G의 종속성들을 몇 개 삭제하거나, 혹은 G의 어떤 종속성에 있는 애트리뷰트들을 몇 개 삭제한 후, G로부터 얻게 되는 종속성들의 집합 H에 대해서, F+ ≠ H+이다.
즉, 어떤 FD들의 집합 F에 대한 최소 커버를 얻는 다음과 같은 일반적인 알고리즘을 얻을 수 있다.
1. FD들을 표준 형태로 전환한다. 우측에 반드시 단일 애트리뷰트만 있는 FD들로만 되도록 표준 형태 G를 구한다(이를 위해 분해 규칙을 이용한다).
2. 각 FD의 좌측을 최소화환다. G에 속하는 각 FD에 대해서, 촤측의 각 애트리뷰트를 검사한다. 만약 이 애트리뷰트를 삭제해도, F+와 동등한지 검사한다. 만약 동등성이 유지되면, 이 애트리뷰트를 삭제한다.
3. 중복되는 FD들을 식별하여 이들을 삭제한다. G에 남아있는 FD들을 일일이 검사한다. 만약 이 FD를 삭제해도, F+와 동등한지 검사한다. 만약 동등성이 유지되면, 이 FD를 삭제한다.
이 과정을 수행해가면서 FD들을 어떠한 순서로 선택하는가에 따라서, 서로 다른 최소 커버들이 생성될 수 있다. 즉, 주어진 FD들의 집합에 대해 여러 개의 최소 커버들이 존재할 수 있다.
여기서, 중복되는 FD들을 식별하여 이들을 삭제하기 이전에 반드시 FD의 좌변을 먼저 최소화해야 한다. 만약 이 두 순서가 역으로 수행되면, 최종적으로 생성되는 FD들의 집합에 일부 중복된 FD들이 여전히 남아 있게 된다.
그렇다면, 결국 무손실 조인과 종속성 유지를 만족하면서 3NF 릴레이션들로 분해하는 방법은 무엇인가? R을 최소 커버인 FD들의 집합 F를 갖는 릴레이션들이라 하고, R1, R2, R3.. Rn을 R의 무손실 조인 분해라고 하자. 1 ≤ i ≤ n인 모든 i에 대해, 각 Ri를 3NF에 속하는 릴레이션이라고 하고, Fi는 F를 각 Ri의 애트리뷰트들에 대해 프로젝션한 결과라고 하자. 이제 다음 과정을 차례로 거친다.
1. F에 속하면서 종속성이 유지가 되지 않는 종속성들의 집합 N을 식별한다. 즉 이들은 Fi의 합집합의 폐포에 포함되지 못하는 종속성들이다.
2. N에 속한 각 FD X → A에 대하여, 릴레이션 스키마 XA를 생성하고, 이 스키마를 R의 분해에 추가한다.
여기서 분명한 점은, 만약 원래의 스키마 R을 스키마 Ri들과 이 과정에서 추가적으로 생성되는 XA 형태의 스키마들로 대체하면, F에 속하는 종속성이 모두 유지된다는 점이다.
3NF 릴레이션들로 분해하는 알고리즘을 설명하기 전에, 최소 커버라는 개념이 필요하다. FD들의 집합 F에 대한 최소 커버는 다음 조건을 만족하는 FD들의 집합 G로 정의된다.
1. G에 속하는 모든 종속성들은 X → A의 형태이고, 이때 A는 단일 애트리뷰트이다.
2. 폐쇄 F+는 폐쇄 G+와 동등하다.
3. 만약 G의 종속성들을 몇 개 삭제하거나, 혹은 G의 어떤 종속성에 있는 애트리뷰트들을 몇 개 삭제한 후, G로부터 얻게 되는 종속성들의 집합 H에 대해서, F+ ≠ H+이다.
즉, 어떤 FD들의 집합 F에 대한 최소 커버를 얻는 다음과 같은 일반적인 알고리즘을 얻을 수 있다.
1. FD들을 표준 형태로 전환한다. 우측에 반드시 단일 애트리뷰트만 있는 FD들로만 되도록 표준 형태 G를 구한다(이를 위해 분해 규칙을 이용한다).
2. 각 FD의 좌측을 최소화환다. G에 속하는 각 FD에 대해서, 촤측의 각 애트리뷰트를 검사한다. 만약 이 애트리뷰트를 삭제해도, F+와 동등한지 검사한다. 만약 동등성이 유지되면, 이 애트리뷰트를 삭제한다.
3. 중복되는 FD들을 식별하여 이들을 삭제한다. G에 남아있는 FD들을 일일이 검사한다. 만약 이 FD를 삭제해도, F+와 동등한지 검사한다. 만약 동등성이 유지되면, 이 FD를 삭제한다.
이 과정을 수행해가면서 FD들을 어떠한 순서로 선택하는가에 따라서, 서로 다른 최소 커버들이 생성될 수 있다. 즉, 주어진 FD들의 집합에 대해 여러 개의 최소 커버들이 존재할 수 있다.
여기서, 중복되는 FD들을 식별하여 이들을 삭제하기 이전에 반드시 FD의 좌변을 먼저 최소화해야 한다. 만약 이 두 순서가 역으로 수행되면, 최종적으로 생성되는 FD들의 집합에 일부 중복된 FD들이 여전히 남아 있게 된다.
그렇다면, 결국 무손실 조인과 종속성 유지를 만족하면서 3NF 릴레이션들로 분해하는 방법은 무엇인가? R을 최소 커버인 FD들의 집합 F를 갖는 릴레이션들이라 하고, R1, R2, R3.. Rn을 R의 무손실 조인 분해라고 하자. 1 ≤ i ≤ n인 모든 i에 대해, 각 Ri를 3NF에 속하는 릴레이션이라고 하고, Fi는 F를 각 Ri의 애트리뷰트들에 대해 프로젝션한 결과라고 하자. 이제 다음 과정을 차례로 거친다.
1. F에 속하면서 종속성이 유지가 되지 않는 종속성들의 집합 N을 식별한다. 즉 이들은 Fi의 합집합의 폐포에 포함되지 못하는 종속성들이다.
2. N에 속한 각 FD X → A에 대하여, 릴레이션 스키마 XA를 생성하고, 이 스키마를 R의 분해에 추가한다.
여기서 분명한 점은, 만약 원래의 스키마 R을 스키마 Ri들과 이 과정에서 추가적으로 생성되는 XA 형태의 스키마들로 대체하면, F에 속하는 종속성이 모두 유지된다는 점이다.