Bài giảng Cơ sở dữ liệu - Chương 5: Lý thuyết thiết kế CSDL quan hệ

 sơ đồ quan hệ R(U) với tập PTH F được gọi là ở dạng chuẩn Boye – Codd nếu với mọi X→A thuộc F+ và A X thì X chứa một khóa của R. Xét ví dụ: Cho sơ đồ quan hệ R(C,S,Z), giả sử trên sơ đồ này có các PTH 	CS→Z, Z→C. Ta đã biết sơ đồ này có hai khóa tối thiểu là CS và SZ, như vậy sơ đồ này không có thuộc tính không khóa và ở dạng 3NF, tuy nhiên nó không ở BCNF do Z→C thuộc F nhưng Z không chứa khóa của R. BCNF(cont) Mục đích của BCNF: Loại bỏ sự dư thừa dữ liệu và tránh các dị thường cập nhật do thao tác thêm và thao tác xóa. Tuy nhiên, dạng chuẩn BCNF còn có thể loại bỏ được một số dị thường mà dạng chuẩn 3NF không loại bỏ được. Ví dụ: Định lý: Một quan hệ ở BCNF thì ở 3NF PHÉP TÁCH CÁC SƠ ĐỒ QUAN HỆ Giới thiệu: Phép tách một sơ đồ quan hệ R với R={A1, A2,…,An} là thay thế nó bởi một tập các sơ đồ con  = {R1(u1), R2(u2),…,Rk(uk)}, ở đây, Ri (i=1,2,…,k) là các tập con của R và R1 R2…Rk =R và Ri=ui(R). Phép tách sơ đồ có thể cho phép loại bỏ được những vấn đề đã đề cập ở phần đầu chương. Phép tách không mất thông tin (lossless join) Giả sử sơ đồ quan hệ R được phân tách thành các sơ đồ con R1, R2,…,Rk và F là các PTH trên R, ta nói phép tách này là không mất mát thông tin nếu R1*R2*…*Rk R Định lý tách Cho R(U),  = {R1(u1), R2(u2)} là phép tách 2 không làm mất thông tin nếu u1u2 u1\u2 hoặc u1u2 u2\u1 Hệ quả tách: Cho R(U) , XY, = {R1(u1), R2(u2)}, u1=XY, U2=XZ (Z=U\XY) thì  không làm mất mát thông tin, Thuật toán kiểm tra phép tách  có làm mất mát thông tin hay không?. Input: R(A1,A2,…,An), 	 = {R1(u1), R2(u2),…,Rm(um)} 	F={LiRi}, i=1,k Output:  có làm mất thông tin hay không?. Thuật toán: Xác định bảng kiểm tra Tmxn gồm n cột, m dòng Tmxn =(tij) Mọi j=1m với Ai Uj thì tij=ai, ngược lại tij=bij Mọi i=1k, xét LiRi , nếu mọi t1,t2  T mà t1[Li] =t2[Li] thì gán t1[Ri]=t2[Ri], ưu tiên các biến ai THUẬT TOÁN TÁCH BẢO TOÀN TẬP PHỤ THUỘC HÀM VỀ DẠNG CHUẨN 3NF. Vào: - R(U); Tập phụ thuộc hàm F. Không mất tính tổng quát giả sử F là phủ tối thiểu. Ra:  - một phép tách bảo toàn tập phụ thuộc hàm bao gồm 1 tập các sơ đồ con, trong đó mỗi sơ đồ con đều ở dạng chuẩn 3NF với các phụ thuộc hàm là hình chiếu của F lên sơ đồ đó. PHƯƠNG PHÁP TÁCH 1. Nếu có những thuộc tính nào đó thuộc R nhưng không xuất hiện trong bất kỳ một phụ thuộc hàm nào kể cả vế trái lẫn vế phải của 1 phụ thuộc hàm trong F thì về nguyên tắc có thể hình thành một sơ đồ quan hệ riêng xác định trên những thuộc tính này và loại nó ra khỏi R. 2. Nếu có 1 phụ thuộc hà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. 3. Ngược lại, kết quả ra bao gồm các sơ đồ XA ứng với 1 phụ thuộc hàm X->A trong F. Tuy nhiên, nếu chúng ta có các phụ thuộc hàm X->A1,...X->An, thì chúng ta có thể sử dụng XA1A2....An thay cho XAi (i=1,n). VÍ DỤ Cho sơ đồ quan hệ: R(ABCDEG) và tập phụ thuộc hàm F=AB->C, C->A, BC->D, ACD->B, D->EG, BE->C, CG->BD, CE->AG. Hãy tách sơ đồ quan hệ trên về dạng chuẩn 3NF bảo toàn tập PTH . 	Bài làm - Bước 1: Kiểm tra F có phải là phủ tối thiểu?. 	Vì F không phải là phủ tối thiểu nên ta phải chuyển F về phủ tối thiểu: 	+ Tách các vế phải với nhiều hơn 1 thuộc tính với vế trái giữ nguyên thu được F1= AB->C, C->A, BC->D, ACD->B, D->E,D->G, BE->C, CG->B, CG->D, CE->A, CE->G TiÕp 	+ Xét mỗi phụ thuộc hàm trong F1 với vế trái nhiều hơn 1 thuộc tính theo thứ tự như trên để loại bỏ các thuộc tính dư thừa. Ta có F2= AB->C, C->A, BC->D, CD->B, D->E, D->G, BE->C, CG->B, CG->D, CE->A, CE->G 	+ Loại bỏ các PTH dư thừa: Đặt F0=F2. Để tính F1ta phải kiểm tra phụ thuộc hàm thứ nhất AB->C có được suy diễn từ các PTH còn lại không, cụ thể tính bao đóng AB đối với các PTH F0 \ AB->C. Nếu (AB)+ không chứa C thì không bỏ được PTH AB-> C. Tương tự cho các PTH còn lại. Cuối cùng ta có: 	F’= Ftt=AB->C, C->A, BC->D, D->E, D->G, BE->C, CG->B, CE->G Tiếp Bước 2: áp dụng thuật toán trên ta có: 	=ABC, CA, BCD, DEG, BEC, CGB, CEG Vì AC ABC nên ta loại AC khỏi . Kết quả là =ABC, BCD, DEG, BEC, CGB, CEGlà phép tách về dạng chuẩn 3NF THUẬT TOÁN TÁCH BẢO TOÀN TẬP PHỤ THUỘC HÀM VÊ DẠNG CHUẨN 3NF VÀ KHÔNG MẤT THÔNG TIN BẢO TOÀN TẬP PTH Vào: - R(U,Ftt); Ra:  - một phép tách không mất thông tin và bảo toàn tập phụ thuộc hàm,  bao gồm 1 tập các sơ đồ con, trong đó mỗi sơ đồ con đều ở dạng chuẩn 3NF Giả sử  là phép tách của thuật toán trên(TToán 8) và K là 1 khoá của R thì  =   {K} là một phép tách bảo toàn F và không mất thông tin. Vậy các bước: - Bước 1: Tìm  - Bước 2: Tìm khoá tối thiểu K - Bước 3: Tồn tại Ri(ui) thuộc  mà K ui   = , ngược lại  =   Ri(K) Thuật toán Ví dụ Cho R(U), U=A,B,C,D,E,F,G,H,I,K 	F={AB->CDE, DE->C, F->GH, AF->I} Hãy tách R(U) thành các lược đồ con ở 3NF không mất thông tin và bảo toàn tập phụ thuộc hàm. PHỤ THUỘC ĐA TRỊ (mulivaluated dependency) Giới thiệu: Trong thực tế phụ thuộc hàm không phải là loại phụ thuộc duy nhất xuất hiện trong các sơ đồ quan hệ mà còn có những phụ thuộc khác nữa cũng thường xuất hiện đó là phụ thuộc đa trị. Khái niệm Cho 1 lược đồ quan hệ R(U), X,Y R. Ta nói rằng X ->->Y đọc là X đa xác định Y hoặc “có 1 phụ thuộc đa trị của Y vào X”. Nếu với những giá trị đã biết cho các thuộc tính của X tồn tại một tập gồm Zero hoặc nhiều giá trị cho các thuộc tính của Y, và tập giá trị này không liên hệ với những giá trị của các thuộc tính trong U-X-Y. Định nghĩa Cho R(U) là 1 sơ đồ quan hệ, X,Y U. Ta nói rằng X->>Y nếu với mọi quan hệ r xác định trên R(U) và với 2 bộ t1,t2 bất kỳ mà t1[X] = t2[X] thì tồn tại t3 sao cho t3[X] = t1[X], t3[Y]= t1[Y] và t3[Z] = t2[Z], Z=U\XY. Do tính đối xứng của t1,t2   r4 sao cho 	t4[X] = t2[X], t4[Y]= t2[Y] và t4[Z] = t1[Z]. VÍ DỤ DAY(MON, GIAOVIEN, GTRINH) Nhận thấy: MON 	 GIAOVIEN 	 MON 	 GTRINH CÁC TIÊN ĐỀ CHO PHỤ THUỘC HÀM VÀ PHỤ THUỘC ĐA TRỊ A1: Tính phản xạ cho phụ thuộc hàm: Nếu YXU thì X->Y. A2: Tính tăng trưởng của phụ thuộc hàm: Nếu X->Y, ZU thì XZ->YZ A3: Tính bắc cầu của phụ thuộc hàm: { X->Y, Y->Z}thì X->Z. A4: Tình bù của phụ thuộc đa trị: X->>Y thì X->>U\XY A5: Tính tăng trưởng của phụ thuộc đa trị: Nếu X->>Y, VW thì WX->YV A6: Tính bắc cầu của phụ thuộc đa trị: 	{ X->>Y, Y->>Z}thì X->>Z\Y A7: X->Y thì X->>Y A8: Nếu X->>Y, W-> Z víi ZY và tập W Y= thì có X->Z NHỮNG QUY TẮC SUY DIỄN BỔ SUNG CHO PHỤ THUỘC ĐA TRỊ 1. Quy tắc hợp của phụ thuộc đa trị 	{X->>Y, X->>Z}  X->>YZ 2. Quy tắc giả bắc cầu của phụ thuộc đa trị 	{X->>Y,WY->>Z}  WX->>(Z\WY) 3. Quy tắc giả bắc cầu pha trộn: 	{X->>Y, XY->Z}  X->>(Z\Y) 4. Quy tắc phân rã của phụ thuộc đa trị: 	 	Nếu X->>Y và X->>Z đúng thì X->>(YZ), X->>(Y\Z), và X->>(Z\Y) đúng. BAO ĐÓNG CỦA PHỤ THUỘC HÀM VÀ PHỤ THUỘC ĐA TRỊ ĐVĐ: Cho trước tập các PTH và phụ thuộc đa trị D, chúng ta muốn tìm tập D+ chứa tất cả các PTH và phụ thuộc đa trị được suy ra từ D. Cách tính D+: Chúng ta tính D+ bằng cách khởi đầu với D và áp dụng các tiên đề từ A1,...,A8 đến khi không còn suy ra được một phụ thuộc hàm nào nữa. Tuy nhiên quá trình này chiếm thời gian hàm mũ theo kích thước cuả D. Thông thường chúng ta chỉ muốn biết xem một phụ thuộc X->Y hoặc X->>Y nào đó có suy ra được từ D hay không?. 	Để kiểm tra X->>Y đúng hay sai chúng ta chỉ cần xác định cơ sở phụ thuộc của X đối với D và xem Y\X có phải là hợp của 1 số tập trong cơ sở đó hay không?. Nếu thoả mãn thì X->>Y suy ra được từ D, ngược lại thì X->>Y kh«ng suy ra được từ D. CÁCH TÍNH CƠ SỞ PHỤ THUỘC CỦA X ĐỐI VỚI Y Để tính toán cơ sở phụ thuộc hàm của X đối với D, một định lý Beeri(1980) cho biết chỉ cần tính toán cơ sở này đối với tập phụ thuộc đa trị M, trong đó M bao gồm: Tất cả các phụ thuộc đa trị trong D và tập các phụ thuộc đa trị X->>A1,..., X->>An với mỗi phụ thuộc hàm X->Y trong D với Y=A1A2...An Hơn nữa 1980 Beeri còn đưa ra 1 thuật toán với độ phức tạp thời gian đa thức để tính toán cơ sở phụ thuộc của X đối với M. Thuật toán như sau; Thuật toán tính cơ sở phụ thuộc Vào: tập các phụ thuộc đa trị M trên tập thuộc tính U và tập thuộc tính XU Ra: Cơ sở phụ thuộc của X đối với M Phương pháp Khởi đầu với 1 tập S mà cuối cùng sẽ trở thành cơ sở phụ thuộc. 	Bước 1: S=U\X 	Bước 2: Lặp đi lặp lại phụ thuộc V->>W và 1 tập Y trong S sao cho Y có giao với W nhưng không giao với V cho đến khi không còn thay đổi nào nữa trong S. Với mỗi quá trình trên thay Y bằng Y W và Y-W trong S. D¹ng chuÈn 4NF ĐN1: Cho R(U), X,Y U 	X->>Y được gọi là phụ thuộc đa trị sơ cấp nếu thoả mãn điều kiện: 	 X’ X thì X’ Y và XY  U	 ĐN2: R(U) được gọi là ở dạng chuẩn 4NF nếu với  phụ thuộc đa trị X ->>Y( Y, Y không là tập con của X và XY không chứa tất cả các thuộc tính của R) thì X chứa khoá của R. Xét CSDL DAY, quan hệ DAY không có 1 PTH nào ngoài các PTH tầm thường. Do đó, khoá tối thiểu của quan hệ là tập tất cả các thuộc tính trên quan hệ. Và quan hệ này đã ở dạng Boye-Codd. Tuy nhiên chúng ta thấy trên quan hệ này có hai PTH đa trị là 	Mônhọc->>Giảngviên, và 	Mônhọc->>GTrinh. 	 Chính các MVD này đã dẫn đến 1 số dữ liệu lặp lại nhiều lần, và sự dư thừa này dẫn đến nguyên nhân của 1 số vấn đề bất lợi. Ta thấy quan hệ DAY cú K=U vậy quan hệ DAY ở dạng chuẩn 3NF nhưng chưa ở dạng 4NF (vì MON ->>GIAOVIEN & 	MON ->>GTRINH mà MON không chứa khoá ) vậy, ta tách quan hệ DAY thành 2 quan hệ: DAY1(MON, GIAOVIEN)	 K1= U1 DAY2(MON, GTRINH) K2= U1 Vậy DAY1 &DAY2 đều ở 4NF Ví dụ 2 Cho CSDL của 1 công ty hoạt động đầu tư với các thuộc tính sau: B(người môi giới), O(văn phòng), I (nhà đầu tư), S (cổ phần), Q( số lượng cổ phần nhà đầu tư), D(lãi của mỗi cổ phần) với các phụ thuộc hàm và phụ thuộc đa trị : S->> D( biểu thị cho các phần lãi đã nhận từ 1 cổ phần), I->B, IS->Q , B->O. Tìm cơ sở phụ thuộc của I Tìm cơ sở phụ thuộc của BS Tìm 1 phân rã dạng chuẩn cấp 4NF