Giáo trình

Giáo trình Cơ Sở Dữ Liệu

Science and Technology

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

Tác giả: unknown

Phân rã nối không mất thành 3NF

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 -> A1, X -> A2,…, X -> An thì thay thế tập thuôc tính XA1A2…An cho XAi (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: R1(CT), R2(HRC), R3(CSG), R4(HSR), R5(HTR)

Phân rã nối không mất thành BCNF.

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)

Chuẩn hoá nhờ phép tổng hợp

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:XYF size 12{f:X - >Y in 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à:

f:XYF,AX size 12{f:X - >Y in F,A in X} {}, A là dư thừa nếu {XA}YF size 12{ left lbrace X - A left none right rbrace right none - >Y in F} {}

Thuật toán

INPUT: Tập thuộc tính U = {A1, A2,…,An }, 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ụ G1, G2 có vế trái là X và Y mà tồn tại song ánh (XY)G+ size 12{ \( X↔Y \) in G rSup { size 8{+{}} } } {}(tức là X -> Yvà Y -> X) thì hoà hai nhóm lai với nhau. Với AY size 12{A in Y} {} (nếu XAH) size 12{X - >A in H \) } {}thì loại nó khỏi 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, B1, B2, C1, C2, D, E, I1, I2, I3, J), tập các phụ thuộc hàm

F = {

A -> B1B2C1C2DE I1I2I3J

B1B2C1 -> AC2DE I1I2I3J

B1B2C2 -> AC1DE I1I2I3J

E -> I1I2I3, C1D -> J, C2D -> J

I1I2 -> I3, I2I3 -> I1, I1I3 -> I2

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 -> B1B2C1C2DE   C1D -> J

B1B2C1 -> A   C2D -> J

B1B2C2 -> A   I1I2 -> I3 

E -> I1I2   I2I3 -> I1 

     I1I3 -> I2 }

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

H= {
    (A,B1B2C1,B1B2C2) -> DE
    (E) -> I1I2
    C1D -> J
    C2D -> J
    (I1I2, I2I3, I1I3)}
    

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

R1 = AB1B2C1C2DE với khoá K1 = {A,B1B2C1,B1B2C2}

R2 = EI1I2 với khoá K2 = {E}

R3 = C1DJ với khoá K2 = {C1D}

R4 = C2DJ với khoá K2 = {C2D}

R5 = I1I2I3 với khoá K2 = {I1I2, I2I3, I1I3}