Bài giảng Cơ sở dữ liệu nâng cao - Nguyễn Trần Minh Thư

12/24/2010 1 GV. Ths . NGUYỄN TRẦN MINH THƯ KHOA CÔNG NGHỆ THÔNG TIN ĐẠI HỌC KHOA HỌC TỰ NHIÊN , TPHCM 12/2010 CƠ SỞ DỮ LIỆU NÂNG CAO 2 Chương 3 – PHỤ THUỘC DỮ LIỆU  Phụ thuộc hàm (PTH)  Hệ quả từ tập PHT  Luật dẫn Armstrong  Suy dẫn từ tập PTH  Bao đóng của tập PTH  Bao đóng của tập thuộc tính X  Phủ và Phủ tối tiểu  PTH và Khóa Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 2 3 Chương 3 – PHỤ THUỘC DỮ LIỆU  Phụ thuộc hàm (PTH)  Hệ quả từ tập PHT  Luật dẫn Armstrong  Suy dẫn từ tập PTH  Bao đóng của tập PTH  Bao đóng của tập thuộc tính X  Phủ và Phủ tối tiểu  PTH và Khóa ©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM Cơ sở dữ liệu nâng cao 4 Phụ thuộc hàm  PTH (Functional dependencies) là một loại RBTV rất quan trọng để phát hiện các thiết kế CSDL tốt.  Có thể biểu diễn RBTV bằng PTH  Phụ thuộc hàm (PTH) thể hiện sự phụ thuộc của một tập thuộc tính (Y) đối với một tập thuộc tính khác(X) trong cùng một quan hệ  Định nghĩa dựa trên những ngữ nghĩa, qui tắc tìm hiểu được từ môi trường ứng dụng ©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM Cơ sở dữ liệu nâng cao 12/24/2010 3 5 Phụ thuộc hàm  Định nghĩa: Nếu X, Y là hai tập thuộc tính của Q (X, Y  Q+), Y phụ thuộc hàm trên X (ký hiệu X → Y), nếu mỗi giá trị tại X trong Q xác định duy nhất một giá trị của Y trong R.  Cho quan hệ Q(X, Y, Z), với X, Y, Z là các tập thuộc tính, X  , Y  , Z có thể .  Một thể hiện TQ của Q thỏa PTH XY nếu: q,q’TQ, q.X = q’.X =>q.Y = q’.Y  TQ vi phạm PTH XY nếu: q,q’ TQ: q.X = q’.X và q.Y  q’.Y  PTH XY được gọi là định nghĩa trên Q nếu TQ là thể hiện của Q, TQ thỏa PTH này  PTH XY gọi là phụ thuộc hàm hiển nhiên nếu Y X ©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM Cơ sở dữ liệu nâng cao 6 Đặc trưng của PTH  Biểu diễn bằng đồ thị:  PTH có hiệu lực về ngữ nghĩa (về nghĩa) của các thuộc tính trong một quan hệ.  Yếu tố quyết định cho một PTH liên quan đến một thuộc tính hoặc một tập các thuộc tính ở bên trái mũi tên. Thiết kế cơ sở dữ liệu quan hệ X Y ©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 4 7 Ví dụ Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 8 Ví dụ A B C 1 1 2 1 1 3 2 1 3 2 1 2 PTH Yes/No AA yes AB yes AC No AAB yes AAC No ABC No AABC No AB  C No ... ...  Tìm tổng số PTH có thể là bao nhiêu? Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 5 9 Nhận diện PTH  Việc nhận diện PTH dựa vào ý nghĩa của thuộc tính và mối quan hệ của chúng trong quan hệ.  Dựa vào dữ liệu trên Staff:  staffNo → sName  sName → staffNo  Tuy nhiên, chỉ có pth:  staffNo → sName Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 10 Ví dụ  Xét lược đồ quan hệ  Và thể hiện Phim(Tênphim, Nămsx, Thờilượng, Loạiphim, Xưởngsx, Diễnviên) Tênphim Nămsx Thờilượng Loạiphim Xưởngsx Diễnviên Star Wars 1977 124 color Fox Carrie Fisher Star Wars 1977 124 color Fox Mark Hamill Star Wars 1977 124 color Fox Harrison Ford Mighty Ducks 1991 104 color Disney Emilio Esteves Wayne’s World 1992 95 color Paramount Dana Carvey Wayne’s World 1992 95 color Paramount Mike Meyers Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 6 11 Ví dụ (tt)  Tìm được nhiều PTH Tênphim Nămsx  Thờilượng Tênphim Nămsx  Loại Tênphim Nămsx  Xưởngsx Tênphim Nămsx  Diễnviên Không là phụ thuộc hàm Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12 Chú ý  Xét thể hiện r1 Tênphim Nămsx Thờilượng Loạiphim Xưởngsx Diễnviên Star Wars 1977 124 color Fox Carrie Fisher Star Wars 1977 124 color Fox Mark Hamill Star Wars 1977 124 color Fox Harrison Ford Mighty Ducks 1991 104 color Disney Emilio Esteves Wayne’s World 1992 95 color Paramount Dana Carvey Wayne’s World 1992 95 color Paramount Mike Meyers Tênphim  Loại Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 7 13 Chú ý (tt)  Xét thể hiện r2 Tênphim Nămsx Thờilượng Loạiphim Xưởngsx Diễnviên Star Wars 1977 124 color Fox Carrie Fisher Star Wars 1977 124 color Fox Mark Hamill Star Wars 1977 124 color Fox Harrison Ford Mighty Ducks 1991 104 color Disney Emilio Esteves Kingkong 1993 120 color Paramount Fay Wray Kingkong 1993 120 Black/white Paramount Robert Amstrong Tênphim  Loại PTH phải được định nghĩa trên lược đồ quan hệ Thỏa với mọi thể hiện của quan hệ Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 14 Chương 3 – PHỤ THUỘC DỮ LIỆU  Phụ thuộc hàm (PTH)  Hệ quả từ tập PTH  Luật dẫn Armstrong  Suy dẫn từ tập PTH  Bao đóng của tập PTH  Bao đóng của tập thuộc tính X  Phủ và Phủ tối tiểu  PTH và Khóa Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 8 15 Hệ quả từ tập PTH  Cho F là tập các PTH định nghĩa trên Q  PTH f là hệ quả của F, ký hiệu F ╞ f nếu f được thỏa trong tất cả các thể hiện TQ của Q  Ví dụ:  Xét lược đồ R(A, B, C, G, H, I) và PTH F định nghĩa trên R  Ta có f6: : A  H là phụ thuộc hàm hệ quả từ F F = { f1: A  B f2: A  C f3: CG  H f4: CG  I f5: B  H } Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM Ví dụ  Xét lịch xếp lớp của một cơ sở giảng dạy trong một ngày, ta có các phụ thuộc hàm sau:  f1: GV, Giờ  Lớp ( nếu biết giảng viên và giờ dạy, ta sẽ biết được lớp mà giảng viên dạy vào giờ đó)  f2: Giờ, Lớp  Phòng (Cho một giờ học và lớp học cụ thể, ta sẽ biết được lớp đang học phòng nào vào giờ đó)  Nếu biết giảng viên và giờ dạy, ta sẽ biết Phòng mà giảng viên dạy vào giờ đó  f3 GV,Giờ  Phòng (f3) là hệ quả của (f1) và (f2) Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 9 17 Chương 3 – PHỤ THUỘC DỮ LIỆU  Phụ thuộc hàm (PTH)  Hệ quả từ tập PTH  Luật dẫn Armstrong  Suy dẫn từ tập PTH  Bao đóng của tập PTH  Bao đóng của tập thuộc tính X  Phủ và Phủ tối tiểu  PTH và Khóa Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 18 Luật dẫn Armstrong  Luật phản hồi/phản xạ/hiển nhiên  Luật cộng  Luật bắc cầu  Hệ tiên đề Amstrong là một tập luật dẫn hợp lệ và đầy đủ (FD1) Y  X, X Y (FD2) Nếu X  Y và Z  W Thì X, W  Y, Z (FD3) Nếu X  Y và Y  Z Thì X  Z Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 10 19 Một số luật dẫn khác  Luật bắc cầu giả  Luật hội  Luật phân rã  Ghi chú: X,Y hay XY có nghĩa là X Y (FD4) (FD5) (FD6) Nếu X  Y và Y, W  Z Thì X, W  Z Nếu X  Y và X  Z Thì X  Y, Z Nếu X  Y và Z  Y Thì X  Z Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 20 Chương 3 – PHỤ THUỘC DỮ LIỆU  Phụ thuộc hàm (PTH)  Hệ quả từ tập PTH  Luật dẫn Armstrong  Suy dẫn từ tập PTH  Bao đóng của tập PTH  Bao đóng của tập thuộc tính X  Phủ và Phủ tối tiểu  PTH và Khóa Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 11 21 Suy dẫn từ tập PTH  Cho trước một tập PTH trên 1 quan hệ  Có thể suy luận “quan hệ phải thỏa một tập PTH khác nào đó”  Khả năng suy dẫn nhằm khám phá thêm tập PTH là rất cần thiết để thiết kế các lược đồ quan hệ đạt chất lượng tốt  f là một PTH được suy dẫn từ F, ký hiệu F├ f, nếu:  Tồn tại một chuỗi phụ thuộc hàm f1, f2,…fn, với:  fn= f  fi  F hoặc được suy từ những phụ thuộc hàm fj, j=1..i-1 nhờ vào luật dẫn  F’ là tập các PTH suy dẫn từ F nhờ vào tập luật dẫn R (F  F’ ) Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 22 Ví dụ  Xét lược đồ R(A,B,C) thỏa tập PTH  Ta có thể suy diễn R còn thỏa PTH F = { f1: A  B f2: B  C } f3: A  C Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 12 23 Chương 3 – PHỤ THUỘC DỮ LIỆU  Phụ thuộc hàm (PTH)  Hệ quả từ tập PTH  Luật dẫn Armstrong  Suy dẫn từ tập PTH  Bao đóng của tập PTH  Bao đóng của tập thuộc tính X  Phủ và Phủ tối tiểu  PTH và Khóa ©2009 Khoa CNTT - ĐH KHTN TPHCM Cơ sở dữ liệu nâng cao 24 BAO ĐÓNG CỦA TẬP PTH (Closure of a Set of Functional Dependencies)  Cho F là tập các PTH định nghĩa trên R  Tập hợp các PTH của F và hệ quả từ F được gọi là bao đóng (closure) của F  Ký hiệu F+ F  F+ Làm sao xác định F+? Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 13 25 Tìm bao đóng của F  Từ tập F ban đầu ta sử dụng định nghĩa hình thức của PTH để tìm bao đóng F+  Nếu F quá lớn, tìm F+ sẽ khó khăn và tốn thời gian Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 26 Bao đóng của F (tt)  Cho F là tập các PTH định nghĩa trên R  Gọi f là một PTH được suy dẫn từ F  Áp dụng luật dẫn cho các PTH trong F để có được f  Tập hợp các PTH suy dẫn từ F ký hiệu F’  Ta muốn F’ = F+ Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 14 27 Tìm bao đóng của F (tt)  Từ tập F ban đầu ta sử dụng các luật dẫn để tìm bao đóng F+  Áp dụng luật dẫn vào F cho đến khi không không thể áp dụng được nữa Tập F+ rất lớn Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 28 Thuật toán tính F+ Để tính F+ dựa trên F ta làm như sau: Bước 1: F+ = F Bước 2: LẶP - Với mỗi pth f trong F+: Áp dụng tính phản xạ và tính tăng trưởng trên f và thêm các PTH kết quả vào F+ - Với mỗi cặp PTH f1và f2 trong F + Nếu f1 và f2 có thể kết nối lại bằng cách sử dụng luật bắt cầu thì thêm PTH kết quả vào F+ CHO ĐẾN KHI F+ không thể thay đổi được nữa Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 15 29 Ví dụ  Xét lược đồ R(A, B, C, G, H, I)  Và PTH F định nghĩa trên R  Tìm được nhiều PTH trong F+ F = { f1: A  B f2: A  C f3: CG  H f4: CG  I f5: B  H } Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 30 Ví dụ  A  B, B  H: A  H  CG  H, CG  I: CG  HI  A  C, CG  I: AG  I Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 16 31 Nhận xét  Bài toán thực tế  Cho một PTH f: X  Y  Xác định f có thuộc bao đóng F+ hay không  Giải quyết  Tìm bao đóng F+  Kiểm tra f có nằm trong F+ không  Tìm bao đóng F+ có hiệu quả ???  Chuyển sang bài toán thành viên:  Ta chỉ cần tìm bao đóng của tập thuộc tính X dựa trên F  Kiểm tra Y có thuộc bao đóng của X hay không Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 32 Chương 3 – PHỤ THUỘC DỮ LIỆU  Phụ thuộc hàm (PTH)  Hệ quả từ tập PTH  Luật dẫn Armstrong  Suy dẫn từ tập PTH  Bao đóng của tập PTH  Bao đóng của tập thuộc tính X  Phủ và Phủ tối tiểu  PTH và Khoa Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 17 33 Bao đóng của tập thuộc tính X  Ký hiệu X+F  Định nghĩa:  Ta thấy: X+F  { Y | X  Y được suy dẫn từ F } Là tập hợp những VP của các PTH có VT là X nằm trong F X  X+F X  R+ Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 34 Thuật toán tìm bao đóng của X Bước 1: Bước 2: X+F  X Lặp { Nếu (có f : U  V thuộc F) và (U  X+F) Thì X+F = X + F  V } cho đến khi (X+F = R +) hoặc (không còn thay đổi được nữa) Tìm các PTH trong F có VT là các thuộc tính nằm trong X+F có VP không nằm trong X+F Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 18 35 Ví dụ  R(A, B, C, D, E, F)  F = { ABC, BCAD, DE, CFB }  Tìm AB+F  AB+F = AB  ABC: ABC  BCAD: ABCD  DE: ABCDE  Ngừng AB+F = {A, B, C, D, E} Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 36 Ví dụ (tt)  R(A, B, C, D, E, F)  F = { ABC, BCAD, DE, CFB }  Kiểm tra PTH ABD có suy dẫn từ F không?  AB+F = {A, B, C, D, E}  Có D trong bao đóng  Kết luận ABD suy dẫn từ F Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 19 37 Ví dụ (tt)  R(A, B, C, D, E, F)  F = { ABC, BCAD, DE, CFB }  Kiểm tra PTH DA có suy dẫn từ F không?  D+F = {D, E}  Không có A trong bao đóng  Kết luận DA không suy dẫn từ F Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 38 Một số tính chất  Tương đương  Hai tập PTH F1 và F2 gọi là tương đương  Bổ đề F1  F2  F1+  F2+ F1  F2  F1 là hệ quả của F2 và F2 là hệ quả của F1 Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 20 39 Ví dụ  R(A, B, C, D, E)  F1 = { ABC, AD, CDE }  F2 = { ABCE, AABD, CDE }  F1  F2 ?  Chứng minh  F1 là hệ quả của F2  F1 được suy dẫn từ F2  F2 là hệ quả của F1  F2 được suy dẫn từ F1 Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 40 Ví dụ (tt)  {ABCE, AABD, CDE }  {ABC, AD, CDE }  Ta thấy F1  F2, hiển nhiên F1 là hệ quả của F2  {ABC, AD, CDE }  {ABCE, AABD, CDE }  Xét F2 có AE, tìm xem F1 có AE ? Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 21 41 Ví dụ  R(A, B, C, D, E)  F1 = { ABC, AD, CDE }  F2 = { ABCDE }  F1  F2 ?  Chứng minh  F1 là hệ quả của F2  F1 được suy dẫn từ F2  F2 là hệ quả của F1  F2 được suy dẫn từ F1 Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 42 Ví dụ  {ABCDE}  {ABC, AD, CDE}  Xét CDE không thuộc trong F2  F1 không được suy dẫn từ F2  F1 không là hệ quả của F2  {ABC, AD, CDE}  {ABCDE}  Xét F2 có AE Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 22 43 Chương 3 – PHỤ THUỘC DỮ LIỆU  Phụ thuộc hàm (PTH)  Hệ quả từ tập PTH  Luật dẫn Armstrong  Suy dẫn từ tập PTH  Bao đóng của tập PTH  Bao đóng của tập thuộc tính X  Phủ và Phủ tối tiểu  PTH và Khóa Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 44 PHỦ  Cho F là tập các PTH định nghĩa trên R  Xét một tập PTH G định nghĩa trên R G là phủ nếu G  F tương đương Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 23 45 Một số khái niệm  PTH đầy đủ Xét X  Y Thì Y phụ thuộc đầy đủ vào X F  F – {XY}  {X’Y} Nếu X’  X sao cho Y phụ thuộc hàm vào X và không phụ thuộc hàm vào tập con nào của X Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 46 Ví dụ  R(A, B, C, D, E, I)  F = { ABCD, BCDE, CDEI }  BCDE là phụ thuộc hàm đầy đủ không? Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 24 47 Một số khái niệm (tt)  PTH thừa  Ví dụ: Xét X  Y là thừa nếu F  F – {XY} F = { f1: A  B f2: B  C f3: A  C } f3 là PTH thừa Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 48 PHỦ TỐI TIỂU  Cho F là tập các PTH định nghĩa trên R  Mà VP chỉ chứa 1 thuộc tính  PTH G gọi là PTT  Nếu G là một phủ  G chỉ chứa những PTH đầy đủ  G không chứa những PTH thừa  Ký hiệu: G=PTT(F) Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 25 49 Ví dụ  R(A, B, C, D)  F = { AB, BA, BC, AC, CA }  PTT(F) ?  Mọi VP đều có 1 thuộc tính  Các PTH đều đầy đủ  Có thể bỏ phụ thuộc hàm thừa nào? Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 50 Ví dụ (tt)  Xét AB  A+F – {AB} = AC  AB không là phụ thuộc hàm thừa  Xét BA  B+F-{BA} = BCA  BA là phụ hàm thừa Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 26 51 Ví dụ (tt)  Nếu bỏ đi BA và AC thì  F’ = { AB, BC, CA }  F’  F nên F’=PTT(F)  Chỉ cần xét F được suy dẫn từ F’  Nếu bỏ đi BC  F” = { AB, BA, AC, CA}  F”  F nên F”=PTT(F) F’  F” Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 52 Thuật toán tìm tập PTH nhỏ nhất G dựa trên F 1. G  F 2. Thay mỗi PTH X → { A1, A2, ......., An} trong G thành n FDs X → A1, X → A2,…, X → An. 3. Với mỗi PTH X → A trong G Với mỗi thuộc tính B mà là một phần tử của X Nếu ( (G – {X → A })  {(X – {B})→ A} ) là tương đương với G, thì thay thế X → A bằng (X – {B}) → A trong G. 4. Với mỗi PTH còn lại X → A trong G Nếu (G – {X → A }) là tương đương với G, thì xóa X → A từ G. Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 27 53 Ví dụ  R(A, B, C)  F = { ABC, AB, BC }  PTT(F) ?  Mọi VP đều có 1 thuộc tính  Có ABC không là PTH đầy đủ  Thay thế bằng các PTH đầy đủ  Có thể bỏ phụ thuộc hàm thừa nào? Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 54 Ví dụ (tt)  F = { AC, AB, BC }  Có thể bỏ phụ thuộc hàm thừa nào? Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 28 55 Chương 3 – PHỤ THUỘC DỮ LIỆU  Phụ thuộc hàm (PTH)  Hệ quả từ tập PTH  Luật dẫn Armstrong  Suy dẫn từ tập PTH  Bao đóng của tập PTH  Bao đóng của tập thuộc tính X  Phủ và Phủ tối tiểu  PTH và Khóa Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 56 NHẮC LẠI  Khóa  Là một tập các thuộc tính dùng để xác định tính duy nhất của mỗi bộ trong quan hệ  Các bộ trong quan hệ khác nhau từng đôi một  Gồm  Siêu khóa  Khóa  Khóa chính Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 29 57 Ví dụ A B CR x 1 10 D a x 2 20 a 1 1 1 40 40 50 b c d y y z  Tập hợp các thuộc tính  ABCD  ABC, ABD, ACD, BCD  AB, AC, AD, BC, BD, CD  A, B, C, D  Siêu khóa  ABCD, ABD, ACD, BCD, BD, CD  Khóa  BD, CD Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 58 PTH và Khóa  Phụ thuộc hàm cho phép ta diễn tả các RBTV không thể diễn tả bằng siêu khóa. Vd., lược đồ Muon(tenkh, magdmuon, tencn, sotien) Ta muốn có tập các pth sau: magdmuon  sotien magdmuon  tencn nhưng không muốn có pth (vì một giao dịch mượn có thể của nhiều khách hàng): magdmuon  tenkh Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 30 59 Đồ thị phụ thuộc hàm  Đồ thị phụ thuộc hàm là một đồ thị vô hướng, với :  Một tập nút tượng trưng cho tập PTH, ký hiệu O với tên PTH bên cạnh.  Một tập nút tượng trưng cho các thuộc tính, ký hiệu ● với tên thuộc tính bên cạnh.  Một tập cung có hướng nối một nút PTH(thuộc tính) đến một nút thuộc tính (PTH).  Một cung xuất phát từ nút thuộc tính A đến một nút PTH f, cùng với một cung từ nút PTH f đến nút thuộc tính B, biểu diễn cho PTH AB  Khi F có nhiều PTT, đồ thị của F có chứa chu trình. Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM Ví dụ Cho F = {f1:ABC; f2: B A; f3: AD E; f4:BD E } Đồ thị của F: A C E B D f1 f2 f3 f4 Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 31 61 Ứng dụng phụ thuộc hàm vào khóa  Thuật toán xác định khóa của quan hệ: 1. Xây dựng các tổ hợp có thể có từ Q+ 2. Với mỗi tổ hợp K  Q+ thỏa điều kiện K Q+ thì K là một siêu khóa của Q. Gọi K = {các siêu khóa của Q} 3. Kiểm tra Min (K) Nếu K’ | K’  K , K’  Q+ thì loại K ra khỏi K  Thực tế, kết hợp bước 2 và bước 3: bắt đầu xét từ những tổ hợp có ít phần tử nhất, nếu tìm được một tổ hợp Ki thỏa điều kiện (i) thì loại bỏ ngay các tổ hợp có chứa Ki.  Vấn đề: Số tổ hợp có thể có từ Q+ sẽ rất lớn nếu Q+ lớn  Cần giới hạn số tổ hợp cần khảo sát Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM Ứng dụng phụ thuộc hàm vào khóa  Giới hạn số lượng tổ hợp:  Thuộc tính nguồn:  A là một thuộc tính nguồn nếu f: XY  F |AY  Trên đồ thị PTH, thuộc tính nguồn không có cung vào  Nhận xét: mọi thuộc tính nguồn phải xuất hiện trong mọi khóa của Q  Thuộc tính đích:  B là một thuộc tính đích nếu f: XY  F| BX  Trên đồ thị PTH, thuộc tính đích chỉ có cung vào, không có cung ra.  Nhận xét: thuộc tính đích không xuất hiện trong bất kỳ khóa nào của Q Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM 12/24/2010 32 63 Ví dụ  Cho Q(ABCDEG) với F = {f1: ADB; f2:EG A; f3: BC G} Xác định các khóa của Q? Cơ sở dữ liệu nâng cao©2010 BM HTTT - Khoa CNTT - ĐH KHTN TPHCM Ví dụ Đồ thị của F: E C B