Các thuật toán phân rã

Thuật toán:

INPUT: Lược đồ quan hệ R, tập phụ thuộc hàm F.

OUTPUT: Một phân rã bảo toàn thông tin của R sao cho mỗi lược đồ quan hệ đều có dạng 3NF.

Phương pháp:

BC1: Tìm phủ cức tiểu của tập phụ thuộc hàm F.

BC2: Loại bỏ tất cả các thuộc tính của R nếu các thuộc tính đó không liên quan tới một phụ thuộc hàm nào trong F, hoặc vế trái hoặc vế phải.

BC3: Nếu có phụ thuộc hàm nào của F mà liên quan tới tất cả các thuộc tính của R thì kết quả ra chính là R.

BC4: Ngoài ra, phép tách R đưa ra các lược đồ con gồm các thuộc tính XA cho phụ thuộc hàm ( X -> A) Î F, tuy nhiên nếu X -> A₁, X -> A_2,…, X -> A_n thì thay thế tập thuôc tính XA₁A₂…A_n cho XA_i (i = 1…n).

Chú ý:

Tại mỗi bước kiểm tra lược đồ R, nếu mỗi thuộc tính không khoá không phụ thuộc gián tiếp vào khoá chính, khi đó R sẽ ở 3NF, ngược lại cần áp dụng BC3.

Ví dụ:

Cho lược đồ quan hệ R(CTHRSC) với tập phụ thuộc hàm tối thiểu F = {C -> T, HR -> C, CS -> G, HS -> R,HT ->R}.

Áp dụng thuật toán:

BC1: Ta đã có phủ cực tiểu là F (giả thiết)

BC2: Giữ nguyên.

BC3: Giữ nguyên.

BC4: R₁(CT), R₂(HRC), R₃(CSG), R₄(HSR), R₅(HTR)

Thuật toán:

INPUT: Lược đồ quan hệ R, tập phụ thuộc hàm F.

OUTPUT: Một phân rã của R có nối không mất, sao cho mỗi lược đồ quan hệ trong phân rã có dạng BCNF.

Phương pháp: Phân rã lược đồ R thành hai lược đồ.

Lược đồ 1: Có tập các thuộc tính XA, có dang BCNF và phụ thuộc X -> A đúng.

Lược đồ 2: R – A.

Lặp lại phân rã trên với R – A ở vị trí ủa R cho đến khi không thể phân rã được nữa hoặc lược đồ chỉ còn 2 thuộc tính.

Bổ đề:

Mỗi lược đồ có 2 thuộc tính đều có dạng BCNF.

Nếu R không có dạng BCNF thì ta có thể tìm được các thuộc tính A và B trong R sao cho (R – AB) -> A.( có thể (R – AB) -> B cũng đúng). Điều ngược lại có thể không đúng.

Chương trình :

Chương trinh chính:

BEGIN :

Z := R;

REPEAT

Phân rã Z thành Z – A và XA /* gọi thủ tục con */

Thêm XA và phân rã;

Z := Z –A ;

UNTIL Không thể phân rã Z

Thêm Z vào phân rã.

END.

Thủ tục phân rã:

BEGIN

IF Z không chứa AB sao cho A Î (Z – AB)⁺ THEN

RETURN Z có dạng BCNF và không phân rã được

ELSE

BEGIN

Tìm một căp A và B; Y:=Z;

WHILE Y chứa A và B sao cho (Y – AB) -> A DO

Y := Y – B;

RETURN phân rã Z –A và Y /* Y là XA trong CT chính*/

END;

END;

Ví dụ:

Cho lược đồ quan hệ R(U) = CTHRSG và tập phụ thuộc hàm F = {C -> T, HR -> C, CS-> G, HS -> R}

Áp dụng thuật toán:

• Y = CTHRSG, A = C, B =T, C Î (HRSG)⁺ => Y = CHRSG
• Y = CHRSG, A = R, B = C, R Î (HSG)⁺ => Y = HRSG
• Y = HRSG ,A = R, B = G, R Î (HS)⁺ => Y = HRS
• Không phân rã được nữa, HRS là một lược đồ trong phân rã.
• Z = CTHRSG – R = CTHSG
• Tiếp tục với Y = CTHSG
• Y = CTHSG, A = T, B = H, T Î (CSG)⁺ => Y = CTSG
• Y = CTSG, A = T, B = S, T Î (CS)⁺ => Y = CTG
• Y = CTG, A = T, B = G, T Î (C)⁺ => Y = CT
• CT là một lược đồ trong phân rã.
• Z = CSHG
• Tiếp tục với Y = CSHG
• …..
• Cuối cùng được phân rã (HRS, CT, CSG, CHS)

Trong phần 5.2 chúng ta đã xem xét qúa chình chuẩn hoá một lược đồ quan hệ thành 3NF nhờ phép tách không mất mát thông tin đối với tập các phụ thuộc hàm. Trong phần này sẽ chình bầy quá trình chuẩn hoá nhờ phép tách tổng hợp. Điều khác nhau cơ bản ở phép tách tổng hợp so với phép tách bảo toàn thông tin là thông tin ban đầu gồm tập các thuộc tính và tập các phụ thuộc hàm, còn trong phương pháp tách bảo toàn thông tin, thông tin ban đầu là một lược đồ rẩt cụ thể. Qua phép tổng hợp kết quả cũng cho một tập các lược đồ ở dạng chuẩn 3NF. Để là rõ chúng ta sẽ nói đển một số khai niêm.

Phụ thuộc hàm dư thừa: Cho lược đồ quan hệ R và tập phụ thuộc hàm F. Một phụ thuộc hàm

f : X -> Y Î F gọi là dư thừa nếu F⁺ = (F - {X -> Y})⁺

Phủ không dư thừa: Cho lược đồ quan hệ R và tập phụ thuộc hàm F. G là phủ không dư thừa

của F nếu G⁺ = F⁺ và G không chứa phụ thuộc hàm nào dư thừa.

Thuộc tính dư thừa: Một thuộc tính thuộc vế trái một phụ thuộc hàm được gọi là dư thừa nếu loại bỏ nó không làm thay đổi bao đóng của tập các phụ thuộc hàm, tức là:

Nếu X -> Y Î F, A Î X, A là dư thừa nếu { X - A} -> Y Î F.}

Thuật toán

INPUT: Tập thuộc tính U = {A_1, A_2,…,A_n }, tập phụ thuộc hàm F.

OUTPUT: Tập các lược đồ quan hệ ở 3NF.

Phương pháp

BC1: Tìm phủ không dư thừa G của F (loại bỏ các phụ thuộc hàm không dư thừa của F)

BC2: Phân chia tập phụ thuộc hàm G thành các nhóm sao cho các phụ thuộc hàm trong một nhóm có cùng vế phải.

BC3: Mỗi cặp nhóm, ví dụ G_1, G₂ có vế trái là X và Y mà tồn tại song ánh (X « Y) Î G⁺ (tức là X -> Yvà Y -> X) thì hoà hai nhóm lai với nhau. Với A Î Y (nếu X -> A) Î H thì loại nó khoi H. Tương tự đối với các phụ thuộc hàm còn lại.

BC4: Ở mỗi nhóm đạt được cấu trúc thoả mãn ba bước trên thì ta gộp lại là một lược đồ quan hệ, trong đó mỗi tập thuộc tính xuất hiện ở vế trái của phụ thuộc hàm thì là một khoá của lược đồ quan hệ. Các khoá tìm được gọi là khoá được tổng hợp.

Ví dụ:

Cho tập các thuộc tính (A, B₁, B_2, C_1, C_2, D_, E_, I_1, I_2, I_3, J), tập các phụ thuộc hàm F = {

A -> B₁B₂C₁C₂DEI₁I₂I₃J

B₁B₂C₁ -> AC₂DEI₁I₂I₃J

B₁B₂C₂ -> AC₁DEI₁I₂I₃J

E -> I₁I₂I_3, C₁D -> J, C₂D -> J

I₁I₂ -> I_3, I₂I₃ -> I_1, I₁I₃ -> I₂

BC1: Rõ ràng F là tối thiểu nhưng dư thừa. Áp dụng thuật toán loại bỏ các thuộc tính dư thừa ta thu được tập phụ thuộc hàm G là phủ không dư thừa của F, G = {

A -> B₁B₂C₁C₂DEC₁D -> J

B₁B₂C₁ -> A C₂D -> J

B₁B₂C₂ -> A I₁I₂ -> I₃

E -> I₁I₂ I₂I₃ -> I₁

I₁I₃ -> I₂ }

BC2 + BC3: Sau khi hoà các nhóm phụ thuộc hàm ta được H= {

(A,B₁B₂C_1,B₁B₂C₂) -> DE

(E) -> I₁I₂

C₁D -> J

C₂D -> J

(I₁I_2, I₂I_3, I₁I₃)}

BC4: Thiết lập các lược đồ

R₁ = AB₁B₂C₁C₂DE với khoá K₁ = {A,B₁B₂C_1,B₁B₂C₂}

R₂ = EI₁I₂ K₂ = {E}

R₃ = C₁DJ K₂ = {C₁D}

R₄ = C₂DJ K₂ = {C₂D}

R₅ = I₁I₂I₃ K₂ = {I₁I_2, I₂I_3, I₁I₃}