Baocao Chuanhoa

20 %
80 %
Information about Baocao Chuanhoa

Published on June 14, 2008

Author: hcdung18

Source: slideshare.net

LÝ THUYẾT CHUẨN HOÁ Nhóm 4 Trần Tấn Từ Lê Quang Chiến Trương Khắc Tùng Quách Xuân Hưng Võ Hoài Trung

Chuẩn hoá là gì ? Cho lược đồ quan hệ R = <U, F>, 1 phân tách  còn được xem là có ý nghĩa nếu nó giảm được dư thừa dữ liệu. Lý thuyết chuẩn hoá sẽ xác định các dạng chuẩn của 1 lược đồ quan hệ. Quá trình phân tách 1 lược đồ thành các lược đồ con sao cho các lược đồ con đều thuộc 1 dạng chuẩn nào đó được gọi là quá trình chuẩn hoá.

Cho lược đồ quan hệ R = <U, F>, 1 phân tách  còn được xem là có ý nghĩa nếu nó giảm được dư thừa dữ liệu. Lý thuyết chuẩn hoá sẽ xác định các dạng chuẩn của 1 lược đồ quan hệ.

Quá trình phân tách 1 lược đồ thành các lược đồ con sao cho các lược đồ con đều thuộc 1 dạng chuẩn nào đó được gọi là quá trình chuẩn hoá.

Các dạng chuẩn lược đồ quan hệ Dạng chuẩn 1NF Dạng chuẩn 2NF Dạng chuẩn 3NF Dạng chuẩn BCNF Dạng chuẩn 4NF Dạng chuẩn 5NF Phụ thuộc đa trị Phụ thuộc kết nối

Dạng chuẩn 1NF

Dạng chuẩn 2NF

Dạng chuẩn 3NF

Dạng chuẩn BCNF

Dạng chuẩn 4NF

Dạng chuẩn 5NF

Dạng chuẩn 1NF Định nghĩa: Một lược đồ R được gọi là thuộc dạng chuẩn 1NF (ký hiệu: R  1NF) nếu miền giá trị của các thuộc tính trong R chỉ chứa những giá trị nguyên tố (không thể phân chia được nữa) Quy ước: Tất cả các lược đồ quan hệ được xét đều thuộc 1NF.

Định nghĩa: Một lược đồ R được gọi là thuộc dạng chuẩn 1NF (ký hiệu: R  1NF) nếu miền giá trị của các thuộc tính trong R chỉ chứa những giá trị nguyên tố (không thể phân chia được nữa)

Quy ước: Tất cả các lược đồ quan hệ được xét đều thuộc 1NF.

Dạng chuẩn 2NF Các khái niệm - Định nghĩa 1 (thuộc tính khoá) : Cho R= <U, F>. Khi đó, thuộc tính A được gọi là thuộc tính khoá nếu A thuộc khoá K nào đó của R. - Ví dụ R = <U, F>, với U = ABCD F = {AB  C, C  D}  K = {AB}  R có 2 thuộc tính khoá: A và B và R có thuộc tính không khoá : C và D

Các khái niệm

- Định nghĩa 1 (thuộc tính khoá) :

Cho R= <U, F>. Khi đó, thuộc tính A được gọi là thuộc tính khoá nếu A thuộc khoá K nào đó của R.

Dạng chuẩn 2NF (tiếp) - Định nghĩa 2 (Phụ thuộc hàm đầy đủ) : Cho R = <U, F>. Khi đó, X  Y  F được gọi là 1 phụ thuộc hàm đầy đủ nếu : Z  X sao cho Z  Y  F+ Nhận xét: Nếu X  U  F+ là 1 phụ thuộc hàm đầy đủ khi X là khoá của R. Ví dụ : NKBH = <U,F> với U = {NG, SP, MH, ĐG, SL} F = {SP, MH  U, MH  ĐG}  {SP, MH}  ĐG  F+ không là phụ thuộc hàm đầy đủ (vì  MH  {MH, SP}: MH  ĐG  F+)

- Định nghĩa 2 (Phụ thuộc hàm đầy đủ) : Cho R = <U, F>. Khi đó, X  Y  F được gọi là 1 phụ thuộc hàm đầy đủ nếu : Z  X sao cho Z  Y  F+

Dạng chuẩn 2NF (tiếp) - Định nghĩa 2NF : Cho R = <U, F>. Khi đó, R được gọi là thuộc 2NF (ký hiệu: R  2NF) nếu với mọi thuộc tính không khoá A là phụ thuộc hàm đầy đủ vào mọi khoá của R. (  A - không khoá,  X  K: X  A  F+ là phụ thuộc hàm đầy đủ) Ví dụ: Xét lược đồ quan hệ nêu trên NKBH có 2 thuộc tính khoá: SP và MH. Suy ra các thuộc tính không khoá: NG, ĐG, SL. Theo trên ta có : {SP, MH}  ĐG  F+ không là phụ thuộc hàm đầy đủ.  NKBH  2NF

- Định nghĩa 2NF : Cho R = <U, F>. Khi đó, R được gọi là thuộc 2NF (ký hiệu: R  2NF) nếu với mọi thuộc tính không khoá A là phụ thuộc hàm đầy đủ vào mọi khoá của R.

Dạng chuẩn 2NF (tiếp) - Nhận xét : + Nếu mọi khoá của lược đồ quan hệ R chỉ có 1 thuộc tính thì R thuộc 2NF. + Ta có thể chứng minh rằng : R 2NF   X  A  F+, với X  K ( K là khoá của R thì: . hoặc A là thuộc tính khoá. . hoặc A  X (X  A là phụ thuộc hàm tầm thường)

- Nhận xét : + Nếu mọi khoá của lược đồ quan hệ R chỉ có 1 thuộc tính thì R thuộc 2NF. + Ta có thể chứng minh rằng : R 2NF   X  A  F+, với X  K ( K là khoá của R thì: . hoặc A là thuộc tính khoá. . hoặc A  X (X  A là phụ thuộc hàm tầm thường)

Dạng chuẩn 3NF - Định nghĩa: (R  3NF) Cho R = <U, F>. Khi đó R được gọi là thuộc 3NF (ký hiệu: R  3NF) nếu  X  A  F+ với A  X thì: + Hoặc X là siêu khoá + Hoặc A là thuộc tính khoá - Ví dụ: NKBH = <U, F>, với U = {STT, NGAY, MH, TH, ĐG, SL}, F = {STT  U, MH  TH, MH  ĐG}  NKBH  2NF (do lược đồ có 1 khoá duy nhất là STT chỉ có 1 thuộc tính) nhưng NKBH  3NF vì :

- Định nghĩa: (R  3NF) Cho R = <U, F>. Khi đó R được gọi là thuộc 3NF (ký hiệu: R  3NF) nếu  X  A  F+ với A  X thì: + Hoặc X là siêu khoá + Hoặc A là thuộc tính khoá

Dạng chuẩn 3NF (tiếp) NKBH có: K = {STT} Ta có MH  TH  F+ nhưng: + MH không là siêu khoá + TH không là thuộc tính khoá - Phân tách NKBH thành 2 lược đồ con: +HANG = <U1, F1>, với U1 = {MH, TH, ĐG} và F1 = {MH  U1} +NK = <U2, F2>, với U2 = {STT, NGAY, MH, SL} và F2 = {STT  U2} rõ ràng HANG và NK thuộc dạng chuẩn 3NF

NKBH có: K = {STT}

Ta có MH  TH  F+ nhưng: + MH không là siêu khoá

+ TH không là thuộc tính khoá

Dạng chuẩn 3NF (tiếp) - Nhận xét : + Nếu R  3NF thì R  2NF. + Ta có thể chứng minh rằng: . R  3NF  phụ thuộc bắc cầu: X  Y  F+ và Y  A  F+ với: + X là khoá (X_khoá) + Y không là siêu khoá + A là thuộc tính không khoá và A  XY Hay: . R  3NF   X_khoá Y, mà Y  A_không khoá

- Nhận xét :

+ Nếu R  3NF thì R  2NF.

+ Ta có thể chứng minh rằng: . R  3NF  phụ thuộc bắc cầu: X  Y  F+ và Y  A  F+

với: + X là khoá (X_khoá)

+ Y không là siêu khoá

+ A là thuộc tính không khoá và A  XY

Hay:

. R  3NF   X_khoá Y, mà Y  A_không khoá

Thuật toán 1 : Phân tách thành các lược đồ con 3NF bảo toàn thông tin Vào: R = <U, F> Ra:  = (R1, R2, …, Rk) với Ri  3NF (i = ) và  là bảo toàn thông tin. Phương pháp: Bước 1: Kiểm tra R  3NF? ( X  Y  A?) Nếu R  3NF: không phân tách và dừng Nếu R  3NF: (  X  Y  A) phân tách R thành 2 lược đồ con:  = (YA, UA) Bước 2: Kiểm tra lần lượt các lượt các lược đồ con có thuộc 3NF không, nếu không thuộc thì lại phân tách tiếp cho đến khi nào tất cả các lược đồ con đều thuộc dạng chuẩn 3NF. Bấy giờ chúng ta sẽ có 1 cây phân tách (cây nhị phân) mà các nút lá là các lược đồ con thuộc 3NF.

Vào: R = <U, F>

Ra:  = (R1, R2, …, Rk) với Ri  3NF (i = )

và  là bảo toàn thông tin.

Phương pháp:

Bước 1: Kiểm tra R  3NF? ( X  Y  A?)

Nếu R  3NF: không phân tách và dừng

Nếu R  3NF: (  X  Y  A) phân tách R thành 2 lược đồ con:  = (YA, UA)

Bước 2: Kiểm tra lần lượt các lượt các lược đồ con có thuộc 3NF không, nếu không thuộc thì lại phân tách tiếp cho đến khi nào tất cả các lược đồ con đều thuộc dạng chuẩn 3NF. Bấy giờ chúng ta sẽ có 1 cây phân tách (cây nhị phân) mà các nút lá là các lược đồ con thuộc 3NF.

Thuật toán 1 : Phân tách thành các lược đồ con 3NF bảo toàn thông tin (Tiếp) procedure Phantach(U, F); begin if (  X  Y  A (phụ thuộc bắc cầu)) then begin Phantach(YA,F1); Phantach(UA,F2); end; end; Lưu ý: Nếu phân tách  = (U1, …, Un) tồn tại Ui là tập con của Uj (i  j) thì ta loại bỏ lược đồ tương ứng với tập thuộc tính Ui.

procedure Phantach(U, F);

begin

if (  X  Y  A (phụ thuộc bắc cầu)) then

begin

Phantach(YA,F1);

Phantach(UA,F2);

end;

end;

Thuật toán 1 : Phân tách thành các lược đồ con 3NF bảo toàn thông tin (Tiếp) Ở ví dụ trên  {STT}  {MH, TH}  ĐG   = ({MH, TH, ĐG}, {STT, NGAY, MH, TH, SL})  3NF  3NF {MH,TH} {STT,NGAY,MH,SL}  3NF  3NF   = ({MH,TH, ĐG},{STT,NGAY,MH,SL}) Lưu ý: Thuật toán trên không duy nhất

Ở ví dụ trên  {STT}  {MH, TH}  ĐG

  = ({MH, TH, ĐG}, {STT, NGAY, MH, TH, SL})

 3NF  3NF

{MH,TH} {STT,NGAY,MH,SL}

 3NF  3NF

  = ({MH,TH, ĐG},{STT,NGAY,MH,SL})

Lưu ý: Thuật toán trên không duy nhất

Thuật toán 2 : Phân tách 3NF bảo toàn thông tin và bảo toàn phụ thuộc hàm Vào : R = <U, F> Ra:  = (R0, R1, R2, …, Rk) với Ri 3NF (i = )  là bảo toàn thông tin và bảo toàn phụ thuộc hàm. Phương pháp: Bước 1: Xác định phủ tối thiểu của F: F’ = {Xi  Ai | i = } Bước 2: Tìm 1 khoá X bất kì của R. Bước 3: Xác định lược đồ con R0 =<U0, F0> với U0 = X Bước 4: Lần lượt xác định các lượt đồ con Ri = <Ui, Fi> với Ui = XiAi (i = ) Bước 5: Nếu  i  j mà Ui  Uj (i, j = ) thì loại bỏ Ri. Quá trình này sẽ tiếp tục cho đến khi không thể loại bỏ được một Ri nào nữa.

Vào : R = <U, F>

Ra:  = (R0, R1, R2, …, Rk) với Ri 3NF (i = )

 là bảo toàn thông tin và bảo toàn phụ thuộc hàm.

Phương pháp:

Bước 1: Xác định phủ tối thiểu của F:

F’ = {Xi  Ai | i = }

Bước 2: Tìm 1 khoá X bất kì của R.

Bước 3: Xác định lược đồ con R0 =<U0, F0> với U0 = X

Bước 4: Lần lượt xác định các lượt đồ con Ri = <Ui, Fi> với Ui = XiAi (i = )

Bước 5: Nếu  i  j mà Ui  Uj (i, j = ) thì loại bỏ Ri.

Quá trình này sẽ tiếp tục cho đến khi không thể loại bỏ được một Ri nào nữa.

Thuật toán 2 : Phân tách 3NF bảo toàn thông tin và bảo toàn phụ thuộc hàm (tiếp) Ví dụ: Cho R = <U,F> với U = ABCD, F = {A  B, B  C, CD  A, AC  D} Bước 1: Ta có 1 phủ tối thiểu của F là: F = {A  B, B  C, CD  A, A  D} Bước 2: Ta có A là 1 khoá của R. Bước 3: R0 = <U0, F0> với U0 = A , F0 =  Bước 4: R1 = <AB, {A  B }> R2 = <BC, {B  C}> R3 = < ACD, {CD  A, A  D, A  C}> R4 = <AD, {A  D}> Bước 5: Loại R0 và R4 Kết luận:  = (AB, BC, ACD)

Ví dụ:

Cho R = <U,F>

với U = ABCD, F = {A  B, B  C, CD  A, AC  D}

Bước 1: Ta có 1 phủ tối thiểu của F là:

F = {A  B, B  C, CD  A, A  D}

Bước 2: Ta có A là 1 khoá của R.

Bước 3: R0 = <U0, F0> với U0 = A , F0 = 

Bước 4:

R1 = <AB, {A  B }>

R2 = <BC, {B  C}>

R3 = < ACD, {CD  A, A  D, A  C}>

R4 = <AD, {A  D}>

Bước 5: Loại R0 và R4

Kết luận:  = (AB, BC, ACD)

Dạng chuẩn BCNF Định nghĩa: (R  BCNF) Cho R = <U, F>. Khi đó: R  BCNF  X  A  F+ với A  X thì: X là siêu khoá. Ví dụ: Cho R = <U, F>, với U = CSZ và F = {CS  Z, Z  C} Xét r  R: => Dư thừa dữ liệu r = C VN VN Mỹ Mỹ Mỹ Mỹ X S Hue HN A B C D A Z 84 84 1 1 2 2 99

Định nghĩa: (R  BCNF)

Cho R = <U, F>. Khi đó: R  BCNF  X  A  F+ với A  X thì: X là siêu khoá.

Dạng chuẩn BCNF (tiếp) Rõ ràng R  3NF (vì R có 2 khoá: CS và SZ), nhưng R vẫn dư thừa. = r C VN Mỹ Mỹ X Z 84 1 2 99 S Hue HN A B C D A Z 84 84 1 1 2 2 99 Không dư thừa Không dư thừa

Ở ví dụ trên R  BCNF vì  Z  C  F+ với Z không là siêu khoá. Nhưng: R1 = <U1, F1> với U1 = CZ và F1 = {Z  C} R2 = <U2, F2> với U2 = SZ và F2 =  Ta có R1, R2  BCNF. Nhận xét: R  BCNF  R  3NF Ta có thuật toán để phân tách 1 lược đồ quan hệ thành các lược đồ con thuộc BCNF và phân tách này bảo toàn thông tin như sau: Dạng chuẩn BCNF (tiếp)

Nhận xét:

R  BCNF  R  3NF

Ta có thuật toán để phân tách 1 lược đồ quan hệ thành các lược đồ con thuộc BCNF và phân tách này bảo toàn thông tin như sau:

Vào: R = <U, F> Ra:  = (R1, R2, …, Rk) với Ri  BCNF (i = )  là bảo toàn thông tin Phương pháp: Dựa vào giải thuật sau: procedure PT(U,F) begin if (  X  A  F+ với A  X và X không là siêu khoá) then begin PT(XA,F1); PT(UA,F2); end; end; Thuật toán để phân tách 1 lược đồ quan hệ thành các lược đồ con thuộc BCNF bảo toàn thông tin

Vào: R = <U, F>

Ra:  = (R1, R2, …, Rk) với Ri  BCNF (i = )

 là bảo toàn thông tin

Phương pháp: Dựa vào giải thuật sau:

procedure PT(U,F)

begin

if (  X  A  F+ với A  X và X không là siêu khoá) then

begin

PT(XA,F1);

PT(UA,F2);

end;

end;

Người ta đã chứng minh: không tồn tai 1 giải thuật phân tách 1 lược đồ quan hệ thành các lược đồ con thuộc BCNF vừa bảo toàn thông tin vừa bảo toàn phụ thuộc hàm

XIN CHÂN THÀNH CÁM ƠN !

XIN CHÂN THÀNH CÁM ƠN !

Add a comment

Related presentations

Related pages

OraFAQ Forum: Performance Tuning » Latch:Library Cache

Latch:Library Cache Solaris 10, 10.2.0.1 DB ... = CCS_ADMIN.qltn_baocao.cuoingay_huy ... diachi_tt, select distinct qltn_tamthu.chuanhoa_string ...
Read more

Cach Trang Tri Nha Cua.web : 4590000 Résultats 1/20 Exit.ws

Cach Trang Tri Nha Cua.web : 4590000 Résultats - Page 1/20 - Exit.ws : Trouver la sortie de tous les sites web pour obtenir toutes vos informations sur ...
Read more

Hoàng Chí Dũng - HubSlide

HubSlide is the easiest way to upload & share PowerPoint & PDF presentations online; embed in Blogs, Slideshows, Transcript & more
Read more

Nha Tro Cho Thue.web : 360000 Résultats 1/20 Oui.im

Nha Tro Cho Thue.web : 360000 Résultats - Page 1/20 - Oui.im : eh bien, finalement on va dire OUI aux resultats de recherches qu'on va avoir sur une seule ...
Read more