Bài giảng Cơ sở dữ liệu - Chương 4: Lý thuyết thiết kế cơ sở dữ liệu quan hệ - Hoàng Thị Hà

giá trị lặp. Chú ý, đặt khóa chính vào cả hai quan hệ mới. Hoang Thi Ha Tóm tắt- 2  2NF  Một quan hệ ở 2NF nếu nó ở 1NF và mọi thuộc tính không khóa của nó đều PTH đầy đủ vào khóa chính.  Chú ý: Nếu một quan hệ chỉ có một thuộc tính thì ở 2NF.  Để chuyển một quan hệ chưa ở 2NF thành 2NF thì ta tạo một tập quan hệ mới:  Một quan hệ với các thuộc tính là những PTH đầy đủ vào khóa chính, và những quan hệ còn lại cho các PTH bị vi phạm 2NF. Hoang Thi Ha Tóm tắt- 3  3NF  Một quan hệ ở 3NF nếu nó ở 2NF và các thuộc tính không khóa đều PTH trực tiếp vào khóa chính  Để chuyển một quan hệ vi phạm 3NF thành 3NF ta loại bỏ các thuộc tính liên quan đến những PTH bị vi phạm và đặt chúng trong một quan hệ mới  Rule: Một quan hệ ở 2NF nếu không có hoặc chỉ có 1 thuộc tính không khóa đều ở 3NF.  Các quan hệ ở dạng chuẩn 3NF rất tốt cho hầu hết các bài toán thiết kế CSDL thực tế. Mặc dù vậy, 3NF không dảm bảo rằng tất cả các dị thường đều bị xóa hết. Hoang Thi Ha Quá trình tách một lược đồ quan hệ dạng chưa chuẩn về dạng chuẩn 1NF, 2NF, 3NF Hoang Thi Ha DẠNG CHUẨN Boye-Codd(BCNF)  Định nghĩa: Một 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. Hoang Thi Ha 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 Hoang Thi Ha 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 Hoang Thi Ha Đị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, Hoang Thi Ha 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 Hoang Thi Ha Thuật toán kiểm tra một phép tách không làm mất thông tin  Bước 1: Tạo một bảng Tm n gồm m hàng và n cột. Cột thứ j tương ứng với thuộc tính Aj , hàng thứ i tương ứng với lược đồ quan hệ con Ri . Ở vị trí hàng i, cột j , ta đặt ký hiệu aj nếu Aj  Ri , ngược lại ta đặt ký hiệu bij vào vị trí đó.  Bước 2: Lần lượt xét các phụ thuộc hàm trong F và áp dụng các phụ thuộc hàm này cho bảng vừa xây dựng được. Giả sử xét phụ thuộc hàm X→ Y∈ F. Nếu tồn tại hai hàng mà tất cả các cột tương ứng với các thuộc tính của X có giá trị như nhau thì ta làm cho các cột ứng với các thuộc tính của Y cũng có giá trị như nhau trong hai hàng này theo nguyên tắc sau: nếu có một ký hiệu aj trong các cột ứng với các thuộc tính Y thì đồng nhất các ký hiệu aj , nếu không thì đồng nhất bằng bij.  Tiếp tục áp dụng các phụ thuộc hàm cho bảng trên (kể cả việc lặp lại các phụ thuộc hàm đã được áp dụng) cho tới khi không có sự thay đổi trong bảng.  Bước 3: Kiểm tra bảng trên, nếu có tồn tại một hàng gồm các ký hiệu a1, a2,..., an (chứa toàn a) thì phép tách không tổn thất thông tin (còn gọi là bảo toàn thông tin). Ngược lại, thì phép tách làm tổn thất thoongg tin (hay còn gọi là không bảo toàn thông tin) . Hoang Thi Ha Hoang Thi Ha  Cho lược đồ R(U,F), U=ABCDE F= {A  C, B C, C  D, DE  C, CE A}  Phép tách  tách lược đồ quan hệ trên thành: R1=AD, R2=AB, R3=BE, R4 =CDE, R5=AE  Hỏi phép tách  trên có làm mất thông tin hay không?. Hoang Thi Ha 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ơ đồ đó. Hoang Thi Ha 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). Hoang Thi Ha 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 Hoang Thi Ha 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 Hoang Thi Ha 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 Hoang Thi Ha 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 Hoang Thi Ha  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 Hoang Thi Ha 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. Hoang Thi Ha Phép tách một lược đồ về dạng chuẩn BCNF không mất thông tin  Bước 1: Tìm tập tất cả các khóa của R(U,F) Bước 2: Tìm phụ thuộc hàm X →Y F có X không là siêu khóa. Có hai trường hợp xảy ra: - Trường hợp 1: Nếu tìm thấy thì tách R thành R1 và R2 theo nguyên tắc sau: R1(U1, F1) với U1 =XY, F1= X →Y; R2(U2, F2) với U2 =U\Y, F2=  F(U2). Sau bước này ta được lược đồ R1(U1, F1) đã tồn tại ở dạng BCNF. - Trường hợp 2: Nếu không tìm thấy thì lược đồ đang xét đã tồn tại ở dạng BCNF.  Bước 3: Lặp lại bước 1 và bước 2 cho lược đồ R2(U2, F2). Tiếp tục quá trình trên cho đến khi mọi sơ đồ con đều ở dạng chuẩn BCNF. Kết quả cuối cùng ta được một phép tách không mất thông tin về dạng chuẩn BCNF. Hoang Thi Ha Ví dụ 5.21. Xét lược đồ quan hệ R(U,F) với U= CTHRSG  Trong đó: C = course (khóa học), T=teacher (thầy giáo), H = hour(giờ học), R=room (phòng học), S=Student (sinh viên), G=grade (điểm số).  Các phụ thuộc hàm F tối thiểu tồn tại là: Ftt = { C→T,HR → C , HT → R, CS→ G, HS → R}  Hãy xác định một phép tách  tách lược đồ trên về BCNF không mất thông tin. Hoang Thi Ha Bài làm U= CTHRSG F= Ftt = { C→T, HR → C, HT → R, CS→ G, HS → R } U1=CSG F1= CS→ G U2=CTHRS F2= { C→T, HR → C, HT → R, HS → R } U21=CT F21= { C→T} U22=CHRS F22= { HR → C, HS → R } U221=HRC F221= { HR→C} U222=HRS F222= { HS→ R} Hình: Hoang Thi Ha Câu hỏi và bài tập chương 4  (Xem trong cuối chương 4, bài giảng word đầy đủ) Hoang Thi Ha 112