Seminar Ly Thuyet Chuan Hoa V1.2

17 %
83 %
Information about Seminar Ly Thuyet Chuan Hoa V1.2

Published on June 14, 2008

Author: hcdung18

Source: slideshare.net

Lý thuyết chuẩn hoá Huế, 09 2006. Đại Học Huế Trường Đại học Khoa học

Các dạng chuẩn của một 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 1NF

Dạng chuẩn 2NF

Dạng chuẩn 3NF

Dạng chuẩn BCNF

Dạng chuẩn 1NF Định nghĩa: Một lược đồ quan hệ R được gọi là thuộc dạng chuẩn 1NF (ký hiệu: R  1NF) nếu mọi thuộc tính của lược đồ là nguyên tố. Ví dụ: Quy ước: Tất cả các lược đồ quan hệ được xét đều thuộc 1NF. z y x A z v u B Tinh Huyen Xa DIACHI Hoten

Định nghĩa:

Một lược đồ quan hệ R được gọi là thuộc dạng chuẩn 1NF (ký hiệu: R  1NF) nếu mọi thuộc tính của lược đồ là nguyên tố.

Ví dụ:

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

Dạng chuẩn 2NF Định nghĩa: R  2NF Lược đồ quan hệ R được gọi là 2NF nếu  X  A trên R (A  X) thì: - Hoặc: A là thuộc tính khóa - Hoặc: X không là tập con thực sự của khóa Ví dụ: Cho R = <U, F>, U = {A, B, C, D} F = {AB  C, C  D}  R là 2NF F = {AB  C, C  A}  R là 2NF F = {AB  C, A  D}  R không là 2NF

Định nghĩa: R  2NF

Lược đồ quan hệ R được gọi là 2NF nếu  X  A trên R (A  X) thì:

- Hoặc: A là thuộc tính khóa

- Hoặc: X không là tập con thực sự của khóa

Ví dụ:

Cho R = <U, F>, U = {A, B, C, D}

F = {AB  C, C  D}  R là 2NF

F = {AB  C, C  A}  R là 2NF

F = {AB  C, A  D}  R không là 2NF

Dạng chuẩn 2NF Nhận xét: 1) Nếu mọi khoá của lược đồ quan hệ R chỉ có 1 thuộc tính thì R  2NF. 2) R  2NF   X  A  F + , với X  K (K là khóa 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:

1) Nếu mọi khoá của lược đồ quan hệ R chỉ có 1 thuộc tính thì R  2NF.

2) R  2NF   X  A  F + , với X  K (K là khóa 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 Một lược đồ quan hệ R được gọi là ở dạng chuẩn 3NF nếu:  X  A trên R (A  X) thì: - Hoặc: A là thuộc tính khoá. - Hoặc: X là siêu khoá. Ví dụ: Cho R = <U, F>, với U = {A, B, C, D}, F = {AB  C, C  D}  R không là 3NF. F = {AB  C, C  A}  R là 3NF.

Định nghĩa: R  3NF

Một lược đồ quan hệ R được gọi là ở dạng chuẩn 3NF nếu:  X  A trên R (A  X) thì:

- Hoặc: A là thuộc tính khoá.

- Hoặc: X là siêu khoá.

Ví dụ: Cho R = <U, F>, với U = {A, B, C, D},

F = {AB  C, C  D}  R không là 3NF.

F = {AB  C, C  A}  R là 3NF.

Dạng chuẩn 3NF Nhận xét: 1) Nếu R  3NF thì R  2NF 2) R  3NF  không  phụ thuộc bắc cầu: X  Y  F + và Y  A  F + với: + X là 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, Y  -  X, mà Y  A_không khoá 

Nhận xét:

1) Nếu R  3NF thì R  2NF

2) R  3NF  không  phụ thuộc bắc cầu:

X  Y  F + và Y  A  F + với:

+ X là 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, Y  -  X, mà Y  A_không khoá 

Dạng chuẩn Boyce-Codd (BCNF) Định nghĩa: R  BCNF Lược đồ quan hệ R được gọi là BCNF nếu  X  A trên R (A  X) thì: - X là siêu khoá. Ví dụ: Cho R = <U,F>, với U = {A, B, C, D}, F = {AB  C, AB  D}  R là BCNF Nhận xét: R  BCNF  R  3NF 1NF 2NF 3NF BCNF

Định nghĩa: R  BCNF

Lược đồ quan hệ R được gọi là BCNF nếu  X  A trên R (A  X) thì:

- X là siêu khoá.

Ví dụ: Cho R = <U,F>, với U = {A, B, C, D},

F = {AB  C, AB  D}  R là BCNF

Nhận xét: R  BCNF  R  3NF

Phân tách bảo toàn thông tin thành BCNF Cho lược đồ quan hệ R = <U, F>,  = (R 1 , R 2 , …, R k ) là phép tách bảo toàn thông tin của R theo F.  ’ = (R 11 , R 12 ) là phép tách bảo toàn thông tin của R 1 theo  R 1 (F).   ’’ = (R 11 , R 12 , R 2 , …, R k ) là phép tách bảo toàn thông tin của R theo F. Định lý: a./ Mọi lược đồ quan hệ chỉ có hai thuộc tính luôn là BCNF. b./ Nếu R không là BCNF thì  A, B  U (A  U) sao cho: U{AB}  A.

Cho lược đồ quan hệ R = <U, F>,  = (R 1 , R 2 , …, R k ) là phép tách bảo toàn thông tin của R theo F.

 ’ = (R 11 , R 12 ) là phép tách bảo toàn thông tin của R 1 theo  R 1 (F).

  ’’ = (R 11 , R 12 , R 2 , …, R k ) là phép tách bảo toàn thông tin của R theo F.

Định lý:

a./ Mọi lược đồ quan hệ chỉ có hai thuộc tính luôn là BCNF.

b./ Nếu R không là BCNF thì  A, B  U (A  U) sao cho:

U{AB}  A.

Phân tách bảo toàn thông tin thành BCNF Nhận xét: - Nếu  A, B  U (A  U) sao cho UAB  A thì R vẫn có thể là BCNF. Ví dụ: Cho R = <U, F>, U = {A, B, C, D} F = {AB  C, AB  D}  R là BCNF Vẫn tồn tại U{CD}  C - Nếu không tìm được cặp A, B  U: U{AB}  A thì R là BCNF.

Nhận xét:

- Nếu  A, B  U (A  U) sao cho UAB  A thì R vẫn có thể là BCNF.

Ví dụ: Cho R = <U, F>, U = {A, B, C, D}

F = {AB  C, AB  D}  R là BCNF

Vẫn tồn tại U{CD}  C

- Nếu không tìm được cặp A, B  U: U{AB}  A thì R là BCNF.

Phân tách bảo toàn thông tin thành BCNF Thuật toán: Input : R = <U, F> Output:  = (R 1 , R 2 , …, R k ) sao cho R i là BCNF,  là BTTT Method:  :=  ; While  A,B  U | A  (U{AB}) + do begin Chọn 1 cặp A, B | A  (U{AB}) + ; Y:=U B; While  A,B  Y | A  (Y{AB}) + do Y:=Y B;  :=   Y; U:= U A; end ;  :=   U; Return  ;

Thuật toán:

Input : R = <U, F>

Output:  = (R 1 , R 2 , …, R k ) sao cho R i là BCNF,  là BTTT

Method:

 :=  ;

While  A,B  U | A  (U{AB}) + do

begin

Chọn 1 cặp A, B | A  (U{AB}) + ;

Y:=U B;

While  A,B  Y | A  (Y{AB}) + do

Y:=Y B;

 :=   Y;

U:= U A;

end ;

 :=   U;

Return  ;

Phân tách bảo toàn thông tin thành BCNF Ví dụ: Cho R = <U, F>, U = {A, B, C, D, E, H, G} F = {AB  D, CD  E, E  B, EH  G}, bảo đảm F là cực tiểu.

Ví dụ: Cho R = <U, F>, U = {A, B, C, D, E, H, G}

F = {AB  D, CD  E, E  B, EH  G}, bảo đảm F là cực tiểu.

A B C D E H G A B D E H G A B D H G A B D G A B D D C D E D H D G A B D A B C E H G A B C E G A B C E B C E B E E H E G B A B C B E A C E H G C E H G E H G G A G C E H G A C E H  = { ABD, BE, EHG, ACEH } F = {AB  D, CD  E, E  B, EH  G} Ví dụ:

Phân tách bảo toàn thông tin thành 3NF Thuật toán: Input : R = <U, F> Output:  = (R 1 , R 2 , …, R k ) sao cho R i là 3NF,  là bảo toàn thông tin. Method: B1: Kiểm tra R  3NF? (không  X  Y  A?) - Nếu R  3NF thì dừng - Nếu R  3NF (  X  Y  A) thì phân tách R thành 2 lược đồ con:  := (YA, UA) B2: Kiểm tra lần lượt các lược đồ con có thuộc 3NF không? - Nếu lược đồ con nào không thuộc 3NF thì ta phân tách tiếp (theo quy tắc được chỉ ra trong B1) Cuối cùng chúng ta sẽ có một 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. ------------------------------------------- Nhận xét: Phân tách thu được dựa vào thuật toán trên là bảo toàn thông tin và các lược đồ là thuộc 3NF.

Thuật toán:

Input : R = <U, F>

Output:  = (R 1 , R 2 , …, R k ) sao cho R i là 3NF,  là bảo toàn thông tin.

Method:

B1: Kiểm tra R  3NF? (không  X  Y  A?)

- Nếu R  3NF thì dừng

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

 := (YA, UA)

B2: Kiểm tra lần lượt các lược đồ con có thuộc 3NF không?

- Nếu lược đồ con nào không thuộc 3NF thì ta phân tách tiếp (theo quy tắc được chỉ ra trong B1)

Cuối cùng chúng ta sẽ có một 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.

-------------------------------------------

Nhận xét: Phân tách thu được dựa vào thuật toán trên là bảo toàn thông tin và các lược đồ là thuộc 3NF.

Phân tách bảo toàn thông tin thành 3NF Ví dụ: Cho NKBH = <U, F>, U = {STT, NGAY, MH, TH, ĐG, SL}, F = {STT  U, MH  TH, MH  ĐG} Ta có: STT là khóa duy nhất của lược đồ NKBH Ta thấy  {STT}  {MH, TH}  ĐG = ({MH, TH, ĐG}, {STT, NGAY, MH, TH, SL})  3NF  3NF {MH, TH} {STT, NGAY, MH, SL}  = ({MH, TH, ĐG}, {STT, NGAY, MH, SL})

Ví dụ: Cho NKBH = <U, F>,

U = {STT, NGAY, MH, TH, ĐG, SL},

F = {STT  U, MH  TH, MH  ĐG}

Ta có: STT là khóa duy nhất của lược đồ NKBH

Ta thấy  {STT}  {MH, TH}  ĐG

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

 3NF  3NF

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

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

Phân tách bảo toàn TT & PTH thành 3NF Thuật toán: Input : R = <U, F> Output:  = (R 1 , R 2 , …, R k ) sao cho R i là 3NF,  là bảo toàn PTH. Method: B1: - Tìm phủ cực tiểu G của F -  :=  ; B2: -Tìm một khoá K bất kỳ của R,  :=   {<K,  K (F)>} B3: - Với mỗi các phụ thuộc hàm có dạng X  A 1 , X  A 2 , …, X  A k , thì tạo thành một lược đồ R’ có U’ = XA 1 A 2 …A k :  :=   {R’} B4: - Nếu  R i , R j   mà U i  U j thì loại R i ra khỏi  .

Thuật toán:

Input : R = <U, F>

Output:  = (R 1 , R 2 , …, R k ) sao cho R i là 3NF,  là bảo toàn PTH.

Method:

B1: - Tìm phủ cực tiểu G của F

-  :=  ;

B2: -Tìm một khoá K bất kỳ của R,  :=   {<K,  K (F)>}

B3: - Với mỗi các phụ thuộc hàm có dạng X  A 1 , X  A 2 , …, X  A k , thì tạo thành một lược đồ R’ có U’ = XA 1 A 2 …A k :

 :=   {R’}

B4: - Nếu  R i , R j   mà U i  U j thì loại R i ra khỏi  .

Phân tách bảo toàn TT & PTH thành 3NF Nhận xét: - Thuật toán trên là không duy nhất do cách xác định phủ cực tiểu là không duy nhất. Ví dụ: Cho R = <U, F>, U = {A, B, C, D, E, G, H} F = {AB  C, AB  D, C  B, CD  E} là cực tiểu. - ABGH là một khoá của R.  = (ABGH) - Bổ sung các lược đồ thông qua các phụ thuộc hàm:  = (ABCD, CB, CDE, ABGH) - Loại CB ra khỏi  .  = (ABCD, CDE, ABGH)

Nhận xét:

- Thuật toán trên là không duy nhất do cách xác định phủ cực tiểu là không duy nhất.

Ví dụ: Cho R = <U, F>, U = {A, B, C, D, E, G, H}

F = {AB  C, AB  D, C  B, CD  E} là cực tiểu.

- ABGH là một khoá của R.

 = (ABGH)

- Bổ sung các lược đồ thông qua các phụ thuộc hàm:

 = (ABCD, CB, CDE, ABGH)

- Loại CB ra khỏi  .

 = (ABCD, CDE, ABGH)

Nhóm thực hiện Lê Quang Chiến Trần Tấn Từ Võ Hoài Trung Trương Khắc Tùng Quách Xuân Hưng Chân thành cảm ơn cả lớp! Hẹn gặp lại lần sau! ^_^ V

Lê Quang Chiến

Trần Tấn Từ

Võ Hoài Trung

Trương Khắc Tùng

Quách Xuân Hưng

Chân thành cảm ơn cả lớp!

Hẹn gặp lại lần sau!

^_^ V

Add a comment

Related presentations

Related pages

Interview Luu Tuyet Hoa & Tan Han - YouTube

Interview Luu Tuyet Hoa & Tan Han ... Standard YouTube License; Loading ... Dong song ly biet - Tap 44 ...
Read more

xay dung he thong, ly thuyet va bai tap, dung cho hoc sinh ...

14 tieu chuan nganh , ve thiet ke, ... san xuat dich vu, thuong mai duc hoa,truong tuan nghia. cac giai phap truyen thong ... ly thuyet, va thuc tien ...
Read more

download giao trinh,dinh muc,tieu chuan,xay dung,dong kim ...

Khoá luận tốt nghiệp: Trích chọn các điểm ảnh đặc trưng trên ảnh hộp sọ...Không giống như con người, khả năng nhìn ...
Read more

Tu hoc dan organ :thuc hanh chu am va hop am - YouTube

LY THUYET VA THUC HANH HOP AM ORGAN 1 - Duration: 12:58. ... Minh nguyen hoa 169,749 views. 13:57 DAY DEM SLOWROCK - Duration: 3:25.
Read more

Phật Học - Tu Viện Phật Giáo Việt Nam - TUVIEN.com

categories: phat phap, phật pháp, thuyet phap ... mp3 thuyết pháp Hé Mở Cửa Giải Thoát, mp3 thuyet phap Tinh Hoa Tinh Do, mp3 thuyet ...
Read more

Home | ÁNH ĐẠO VÀNG

Tâm sự người cài hoa trắng: 3550: 2502: 6: Kinh Ngũ Bách Danh 1: 3216: ... Nam Mô Dược Sư Lưu Ly Quang Vương Phật 2: 2001: 1668: 27 ...
Read more

-> Thông báo

Trang web http://hocvienketoan.edu.vn hiện đã hết hạn sử dụng hoặc bị đình chỉ hoạt động, vui lòng liên hệ nhân viên kinh ...
Read more

Đào Tạo Lái Xe Ô Tô Tại TPHCM - Học Lái Xe Ô Tô Đậu 99%

Điểm đưa đón học viên học lái xe ô tô (học thực hành): Điểm học lái xe ô tô tại Quận 10: Số 63 Đường ...
Read more