Bài giảng Cơ sở dữ liệu - Chương 5: Phụ thuộc hàm - Trường Cao đẳng Tài Chính Hải Quân

Nội dung text: Bài giảng Cơ sở dữ liệu - Chương 5: Phụ thuộc hàm - Trường Cao đẳng Tài Chính Hải Quân

1. Choose Learn Succeed Trường Cao Đẳng Tài Chính – Hải Quan CHƯƠNG 5: PHỤ THUỘC HÀM (FUNCTIONAL DEPENDENCY) I. PHỤ THUỘC HÀM 1. Khái niệm  Cho lược đồ quan hệ Q với tâp thuộc tính Q+=(A1, A2, , An ), X và Y là 2 tập thuộc tính con của Q+ (X, Y  U).  Y được gọi là phụ thuộc hàm vào X hoặc X xác định hàm Y nếu:  t1.X = t2.X t1.Y = t2.Y  Ký hiệu: X Y This document was created with the trial version of Print2PDF! Once Print2PDF is registered, this message will disappear! 1 Purchase Print2PDF at
2. Choose Learn Succeed Trường Cao Đẳng Tài Chính – Hải Quan 2. Ví dụ Xét lược đồ quan hệ NHAN_VIEN (MSNV, HOTEN, GIOITINH, NƠISINH, ĐIACHI, ĐINHMUCLĐ) MSNV HOTEN GIOITINH NOISINH ĐINHMUCSP NV01 Nguyễn Ngọc Anh Nữ Hà Nội 50 NV02 Lê Hồng Hải Nam Long An 70 NV03 Trần Mạnh Linh Nam Trà Vinh 70 NV04 Nguyễn Ngọc Huệ Nữ Lâm Đồng 50 NV05 Nguyễn Đỗ Quyên Nữ Long An 50 Giả sử cĩ các phụ thuộc hàm sau : •GIOITINH ĐINHMUCSP (1) •NOISINH ĐINHMUCSP (2) This document was created with the trial version of Print2PDF! Once Print2PDF is registered, this message will disappear! Purchase Print2PDF at
3. Choose Learn Succeed Trường Cao Đẳng Tài Chính – Hải Quan II. BIỂU DIỄN PHỤ THUỘC HÀM BẰNG ÁNH XẠ Cho tập hợp A là tập các thuộc tính nguồn, tập hợp B là tập các thuộc tính đích. f được gọi là ánh xạ (phụ thuộc hàm) từ tập A -> B nếu với tập thuộc tính X A xác định tập thuộc tính Y B thơng qua phép biến đổi f. Ký hiệu f:A B This document was created with the trial version of Print2PDF! Once Print2PDF is registered, this message will disappear! Purchase Print2PDF at
4. Choose Learn Succeed Trường Cao Đẳng Tài Chính – Hải Quan III. HỆ LUẬN DẪN ARMSTRONG 1. Luật phản hồi:  Y  X, X Y. 2. Luật cộng  Nếu X Y  thì XZ YZ. 3. Luật bắc cầu  Nếu X Y và Y Z  thì X Z. This document was created with the trial version of Print2PDF! Once Print2PDF is registered, this message will disappear! Purchase Print2PDF at
5. Choose Learn Succeed Trường Cao Đẳng Tài Chính – Hải Quan 4. HỆ QUẢ Từ 3 luật dẫn trên ta cĩ thể suy dẫn ra một số luật dẫn khác. Sau đây là 3 luật dẫn khác thường hay cần đến.  Luật bắc cầu giả:  Nếu X Y và YW Z  thì XW Z  Luật hội:  Nếu X Y và X Z  thì X YZ  Luật phân rã :  Nếu X YZ  thì X Y và X Z This document was created with the trial version of Print2PDF! Once Print2PDF is registered, this message will disappear! Purchase Print2PDF at
6. Choose Learn Succeed Trường Cao Đẳng Tài Chính – Hải Quan IV. BAO ĐĨNG CỦA TẬP PHỤ THUỘC HÀM 1. Khái niệm Tập tất cả phụ thuộc hàm hệ quả của F được gọi là bao đĩng của F, ký hiệu F + = {X Y / F |= X Y } 2. Cách xác định  Ta xác định tập F + dựa vào bộ luật dẫn cĩ thể dẫn đến tâp F + rất lớn. Do đĩ, trong thực tế người ta thường khơng đi tính F + mà chỉ sử dụng bộ luật dẫn để trả lời cho các câu hỏi thuộc dạng:  F |= X Y This document was created with the trial version of Print2PDF! Once Print2PDF is registered, this message will disappear! Purchase Print2PDF at
7. Choose Learn Succeed Trường Cao Đẳng Tài Chính – Hải Quan Ví dụ: Cho U = ABEGIH F = { AB E, AG I, E G} Chứng minh rằng F |= AB G Giải : Ta cĩ: AB E E G Theo luật bắc cầu ta cĩ: AB G Vậy F |= AB G This document was created with the trial version of Print2PDF! Once Print2PDF is registered, this message will disappear! Purchase Print2PDF at
8.  Choose Learn Succeed Trường Cao Đẳng Tài Chính – Hải Quan V. CÁC LOẠI PHỤ THUỘC HÀM 1. Phụ thuộc hàm hiển nhiên X Y là một phụ thuộc hàm hiển nhiên nếu Y  X. 2. Phụ thuộc hàm đầy đủ  Cho tập phụ thuộc hàm F và 1 phụ thuộc hàm X Y F.  X Y là 1 phụ thuộc hàm đầy đủ trong F nếu:   X’ X sao cho:  F  (F – (X Y)  (X’ Y))  Y được gọi là phụ thuộc đầy đủ vào X. This document was created with the trial version of Print2PDF! Once Print2PDF is registered, this message will disappear! Purchase Print2PDF at
9. Choose Learn Succeed Trường Cao Đẳng Tài Chính – Hải Quan 3. Phụ thuộc hàm bắc cầu  A phụ thuộc bắc cầu vào X nếu cĩ 4 điều kiện sau:  X Y F + (i)  Y A F +(ii)  Y X F + (iii)  A (XY) (iv)  Ví dụ: Cho F = { MN OPRX ; NO M ; P RY } Thuộc tính P khơng phụ thuộc bắc cầu vào NO vì: Cĩ NO M NO MN :(i) thỏa MN O MN ON :(iii) khơng thỏa và MN P :(ii) thỏa Thuộc tính R phụ thuộc bắc cầu vào NO vì: Cĩ NO MN và MN P nên cĩ NO P :(i) thỏa Cĩ P R :(ii) thỏa Khơng cĩ P NO :(iii) thỏa ThisC documentĩ was created with the trialR version(NOP) of Print2PDF!:(iv) thỏa Once Print2PDF is registered, this message will disappear! Purchase Print2PDF at
10. Choose Learn Succeed Trường Cao Đẳng Tài Chính – Hải Quan VI. BAO ĐĨNG CỦA TẬP THUỘC TÍNH 1. Khái niệm  Cho một lược đồ quan hệ R tập thuộc tính U=(ABCDEGH) và các phụ thuộc hàm F{f1,f2,f3, fn} Giả sử X là một tập hợp con của U +  Bao đĩng của X dựa trên F được ký hiệu là : X F là tập hợp các thuộc tính phụ thuộc vào X dựa trên F: + +  X F = {Y Q / X Y F}  Khái niệm bao đĩng của X dùng để xét xem một phụ thuộc hàm f cĩ được suy dẫn từ F hay khơng. This document was created with the trial version of Print2PDF! Once Print2PDF is registered, this message will disappear! Purchase Print2PDF at
11. Choose Learn Succeed Trường Cao Đẳng Tài Chính – Hải Quan 2. Cách xác định +  Thuật tốn tính X F +  X F được tính theo quy nạp:  X(0) = X (X = {Ai / Ai X })  X(i+1) = X  {Bj / X Y với X  X(j) và Bj Y })  Cho đến bước thứ k mà X(k+1) = X(k) This document was created with the trial version of Print2PDF! Once Print2PDF is registered, this message will disappear! Purchase Print2PDF at
12. Choose Learn Succeed Trường Cao Đẳng Tài Chính – Hải Quan  Bước 1: X0 = X  Bước 2: lần lượt xét các phụ thuộc hàm của F  Nếu Y→Z có Y ⊆ Xi thì Xi+1 = Xi ∪ Z  Loại phụ thuộc hàm Y → Z khỏi F  Bước 3: Nếu ở bước 2 ta tính được Xi+1 = Xi thì Xi chính là bao đóng của X. Ngược lại lặp lại bước 2 This document was created with the trial version of Print2PDF! Once Print2PDF is registered, this message will disappear! Purchase Print2PDF at
13. Choose Learn Succeed Trường Cao Đẳng Tài Chính – Hải Quan  Ví dụ 1: Cho U =ABEGIH F = { AB E, E G, BE->I, GI->H} Chứng minh rằng F |= AB GH  Giải : + Bài tốn trên trở thành GH  (AB) F X(0) := (AB) X(1) := (AB)  (E, với AB E) = (ABE) X(2) := (ABE)  (I, với BE I) = (ABEI) X(3) := (ABEI)  (G, với E G) = (ABEIG) X(4) := (ABEIG)  (H, với GI H) = (ABEIGH) X(5) := X(4) Vậy (AB)+ F = (ABEIGH) = Q+ GH  (AB)+ F F = AB GH This document was created with the trial version of Print2PDF! Once Print2PDF is registered, this message will disappear! Purchase Print2PDF at
14. Choose Learn Succeed Trường Cao Đẳng Tài Chính – Hải Quan  Ví dụ 2:  Cho U = ABCDEG  F = { AB C,  D EG,  C A,  BE C,  BC D,  CG BD,  ACD B,  CE AG } This document was created with the trial version of Print2PDF! Once Print2PDF is registered, this message will disappear! Purchase Print2PDF at
15.  Choose Learn Succeed Trường Cao Đẳng Tài Chính – Hải Quan VII. THUẬT TỐN XÁC ĐỊNH KHĨA CỦA MỘT LƯỢC ĐỒ QUAN HỆ 1. Định nghĩa :  Cho R(U) và F là 1 tập phụ thuộc hàm định nghĩa trên. Cho K  U  K là một khố của R nếu: +  (i) K F = U.  (ii) K’  K, K U F. This document was created with the trial version of Print2PDF! Once Print2PDF is registered, this message will disappear! Purchase Print2PDF at
16. Choose Learn Succeed Trường Cao Đẳng Tài Chính – Hải Quan 2. Thuật tốn xác định khĩa 1. Xây dựng các tổ hợp cĩ thể của U 2.Với mỗi tổ hợp K  U Nếu K thỏa điều kiện (i) thì K là 1 siêu khố cuả R Cuối Nếu Cuối  Gọi K = { tập tất cả siêu khố của R} 3.Min (K) ( kiểm tra điều kiện (ii)):  k K : Nếu  k’ sao cho k’ k Thì loại k khỏi K. Cuối Nếu Cuối  This document was created with the trial version of Print2PDF! Once Print2PDF is registered, this message will disappear! Purchase Print2PDF at
17. Choose Learn Succeed Trường Cao Đẳng Tài Chính – Hải Quan Bước 1: Tìm các tập sau: Tập nguồn : bao gồm các thuộc tính chỉ xuất hiện ở vế trái của tập phụ thuộc hàm F Tập đích: bao gồm các thuộc tính chỉ xuất hiện ở vế phải của tập phụ thuộc hàm F Tập trung gian : bao gồm các thuộc tính xuất hiện ở cả vế phải và vế trái của tập phụ thuộc hàm F Tập thuộc tính khơng xuất hiện trong tập phụ thuộc hàm F Bước 2: - Tập các thuộc tính khố K ban đầu bao gồm: các thuộc tính thuộc tập nguồn và tập thuộc tính khơng xuất hiện trong tập phụ thuộc hàm. + - Tính bao đĩng của K trên F (K F ) - Nếu K+F = U (tập thuộc tính) thì kết luận K là khố duy nhất của quan hệ. Kết thúc thuật tốn. - Ngược lại, chuyển sang bước 3 Bước 3: Lặp: - - Xây dựng tổ hợp của K với tập thuộc tính trung gian. - Tính bao đĩng của tổ hợp đĩ. Nếu bao đĩng = U thì kết luận tổ hợp đĩ là khố của quan hệ - Nếu tổ hợp xây dựng K1 cĩ bao đĩng = U thì khơng xét các tổ hợp K2 mà K2  K1 This document was created with the trial version of Print2PDF! Once Print2PDF is registered, this message will disappear! Purchase Print2PDF at
18. Choose Learn Succeed Trường Cao Đẳng Tài Chính – Hải Quan  Ví dụ 1:  Cho R (ABCDEFGHIJKLMN)  F = { f1: AB CDEF,  f2: G HIJ,  f3: AC KL,  f4: K M} This document was created with the trial version of Print2PDF! Once Print2PDF is registered, this message will disappear! Purchase Print2PDF at
19. Choose Learn Succeed Trường Cao Đẳng Tài Chính – Hải Quan  Giải:  - Tập các thuộc tính U = ABCDEFGHIJKLMN  - Tập nguồn = ABG  - Tập đích = DEFHIJLM  - Tập trung gian = CK  - Tập thuộc tính khơng xuất hiện trong tập phụ thuộc hàm = N  - Xét: (ABGN)+F = ABGNCDEFKLMHIJ = U  Vậy ABGN là khĩa duy nhất của R This document was created with the trial version of Print2PDF! Once Print2PDF is registered, this message will disappear! Purchase Print2PDF at
20. Choose Learn Succeed Trường Cao Đẳng Tài Chính – Hải Quan Ví dụ 2:  C= Q(ABCDEGHI),  F = f1: AC B; f2: BI ACD; f3: ABC D; f4:H I f5: ACE BCG; f6: CG AE This document was created with the trial version of Print2PDF! Once Print2PDF is registered, this message will disappear! Purchase Print2PDF at
21. Choose Learn Succeed Trường Cao Đẳng Tài Chính – Hải Quan This document was created with the trial version of Print2PDF! Once Print2PDF is registered, this message will disappear! Purchase Print2PDF at