Chương 4: Phụ thuộc hàm

Chương 4: PHỤ THUỘC HÀM 4.1 Các bất thường về dữ liệu  Bất thường khi cập nhật  Bất thường xóa bỏ 4.2. Định nghĩa về phụ thuộc hàm  Xét lược đồ quan hệ gồm n thuộc tính:  R(U), U = {A1, A1…. An }  Phụ thuộc hàm giữa hai tập thuộc tính X,Y U  Ký hiệu: X  Y  rR, t1, t2r nếu t1[X] = t2[X] thì t1[Y] = t2[Y]  Quan hệ r thỏa phụ thuộc hàm X  Y 4.2. Định nghĩa về phụ thuộc hàm  Đọc : X xác định Y  Tập các thuộc tính Y phụ thuộc vào tập các thuộc tính X hoặc được suy ra từ tập các thuộc tính X.  X là vế trái, Y là vế phải của phụ thuộc hàm  Phụ thuộc hàm X → Y là tầm thường (trivial) khi và chỉ khi Y = X. 4.2. Định nghĩa về phụ thuộc hàm r (R) A B 1 4 1 5 3 7  Ví dụ  r không thỏa AB nhưng thỏa B A 4.2. Định nghĩa về phụ thuộc hàm MaNVTenNV Ngsinh Diachi MaPB TenPB TrPhong MaNVTenNV MaNVMaPB MaPB{TenPB,TrPhong} NHANVIEN rR thỏa các phụ thuộc hàm 4.2. Định nghĩa về phụ thuộc hàm 4.2. Định nghĩa về phụ thuộc hàm  Lược đồ GV (Magv, Tengv);  Lược đồ SV (Masv, Tensv);  Lược đồ Mon(Mamon,Tenmon); Magv → Tengv Masv → Tensv Mamon → Tenmon 4.2. Định nghĩa về phụ thuộc hàm  Lược đồ Hoc (Masv, Mamon, Diem) Masv Mamon Diem A01 M01 9 A01 M02 6 A04 M01 8 Masv, Mamon → Diem 4.2. Định nghĩa về phụ thuộc hàm Nhận xét:  Các PTH xuất phát từ thế giới thực  rR, tr nếu t[X] là duy nhất thì X là một khóa của R.  Nếu K là một khóa của R thì K xác định tất cả các thuộc tính của R.  PTH dùng để đánh giá một thiết kế cơ sở dữ liệu. 4.2.1 Bao đóng của tập PTH  F là tập PTH trên R  F= { MaNVTenNV, MaPB {TenPb, TrPhong}, MaNV MaPB}  r  R thỏa F và MaNV{TenPB,TrPhong} cũng đúng với r thì MaNV{TenPB,TrPhong} được gọi là suy diễn từ F 4.2.1 Bao đóng của tập PTH Bao đóng của F ký hiệu F+ gồm:  F và  Tất cả các phụ thuộc hàm suy diễn từ F F được gọi là đầy đủ nếu F = F+ 4.2.2.Hệ tiên đề Amstrong  A1: Tính phản xạ (Reflexivity) Nếu Y ⊆ X ⊆ U thì F ⊨ X → Y  A2: Tính tăng trưởng (Augmentation) Nếu X → Y đúng và Z ⊆ U thì XZ → YZ  A3: Tính bắc cầu (Transivity) Nếu X → Y và Y → Z thì X → Z đúng 4.2.3. Các luật suy diễn bổ sung  Qui tắc hợp (The union rule) {X → Y, X → Z} ⊨ X → YZ  Qui tắc giả bắc cầu(The pseudotransivity rule) {X → Y, WY → Z} ⊨ WX → Z  Qui tắc phân rã (The decomposition rule) Nếu X → Y và Z ⊆ Y thì X → Z đúng Vấn đề  Làm thế nào để biết một PTH XY được suy diễn từ tập PTH F cho trước?  Bao đóng của tập thuộc tính X đối với F, ký hiệu X+ là:  Tập các thuộc tính PTH vào X  X+= {A  U| XA F+}  Nhận xét: XYF+ Y X+ Nếu K là khóa của R thì K+= U Nếu K là một khóa của R thì K xác định tất cả các thuộc tính của R. Thuật toán tìm X+  Vào: U, F và X  U  Ra: X+  Bước 1: X+ = X  Bước 2: nếu tồn tại YZ  F và Y  X+ thì: X+= X+  Z Tiếp tục bước 2. Ngược lại qua bước 3  Bước 3: cho X+ Ví dụ tìm X+  Cho F = {ABC, BCD, DEG}  X=BD tìm X+ = ?  X+ = BD  Tìm các PTH có vế trái là tập con của X+=BD DEG, thêm EG vào X+ ta được X+=BDEG Tìm các phụ thuộc hàm có vế trái là tập con của BDEG. Không có phụ thuộc hàm nào. Suy ra X+ = BDEG Ví dụ tìm X+ 1. AB → C 2. C → A 3. BC → D 4. ACD →B 5. D → EG 6. BE → C 7. CG → BD 8. CE → AG TÍNH (BD)+ X+ = BDEGC 4.2.4. Kiểm tra phụ thuộc hàm suy diễn  Cho F= {ABC,AD,DE,ACB}  Hai phụ thuộc hàm: ABE và DC có được suy diễn từ F hay không?  X = AB suy ra: X+ = ABCDE có chứa E  X = D suy ra X+= DE không chứa C Phụ thuộc hàm tương đương  Tập PTH F được nói là phủ tập PTH G nếu: G  F+. Hai tập phụ thuộc hàm được gọi là tương đương nếu G phủ F và F phủ G. Nhận xét: XYG, nếu YX+(F) thì F phủ G F và G tương đương nếu và chỉ nếu F+ = G+ Tập phụ thuộc hàm tối thiểu  Thừa phụ thuộc hàm: {AB,BC,AC}  Thừa thuộc tính:  {AB,BC,ACD} Vì ACD được suy diễn từ: {AB,BC,AD}  AB, BC  AC (Luật bắc cầu)  AC, AD  ACD (Luật hợp) Tập phụ thuộc hàm tối thiểu  {AB,BC,ACD} Thừa… vì ACD được suy diễn từ {AB,BC,AD}  AB,AD  ABD (Luật hợp)  ABD  ACBDC (Luật tăng trưởng)  ACBDC  ACD (Luật phân rã) Tập phụ thuộc hàm tối thiểu  Một tập PTH F được gọi là tối thiểu nếu thỏa các điều kiện sau:  Mọi PTH chỉ có một thuộc tính ở vế phải  Không thể thay XA  F bằng YA với YX mà tập mới tương đương với F  Nếu bỏ đi một PTH bất kỳ trong F thì tập PTH còn lại không tương đương với F.  Phủ tối thiểu của tập PTH E là tập PTH tối thiểu F tương đương với E  Nhận xét: mọi tập PTH có ít nhất một phủ tối thiểu Thuật toán tìm phủ tối thiểu 1. Tách các phụ thuộc hàm sao cho vế phải chỉ còn một thuộc tính. (ví dụ: A->BC thành A->B và A->C) 2. Bỏ các thuộc tính dư thừa ở vế trái. (ví dụ: cho F = {A → B, B → C, AB → D} các phụ thuộc hàm có vế trái 1 thuộc tính là đầy đủ nên ta không xét, xét AB → D có B dư thừa(bỏ B) vì bao đóng của A có chứa B. A+=ABC) (bỏ thuộc tính bên vế trái, khi và chỉ khi bao đóng của các thuộc tính còn lại có chứa thuộc tính đó) 3. Loại khỏi F các phụ thuộc hàm dư thừa. (Các thuộc tính ở vế phải của PTH chỉ xuất hiện duy nhất 1 lần thì không thể loại bỏ. Còn lại tính bao đóng của tập thuộc tính vế trái nếu có xuất hiện thuộc tính vế phải thì có thể loại bỏ thuộc tính đó vì đó là PTH dư thừa.) Ví dụ tìm phủ tối thiểu  Tìm phủ tối thiểu của E = {ABC,AB,BC,ABC}  B1: F={AB,AC,BC,ABC}  B2: Xét ABC  BF+= C  F = {AB,AC,BC}  B3: AC THỪA  Suy ra : F = {AB,BC} Ví dụ: Cho lược đồ quan hệ Q(A,B,C,D) và tập pth F={AB->CD, B- >C, C->D} Tìm phủ tối thiểu? 1. Tách các phụ thuộc hàm sao cho vế phải chỉ còn một thuộc tính. + ta có F={AB->C, AB->D, B->C, C->D} 2. Bỏ các thuộc tính dư thừa ở vế trái. + B->C, C->D Không xét vì vế trái chỉ có một thuộc tính. + xét AB->C : Nếu Bỏ A thì B+=BCD không chứa A nên không thể Bỏ A. Nếu Bỏ B thì A+=A. không bỏ được thuộc tính nào. + xét AB->D : Nếu Bỏ A thì B+=BCD không chứa A nên không thể Bỏ A. Nếu Bỏ B thì A+=A. không bỏ được thuộc tính nào. 3. Loại khỏi F các phụ thuộc hàm dư thừa. + xét AB->C : Tính AB+=ABCD = Q nên loại bỏ AB->C + xét AB->D : tính AB+=ABCD = Q nên loại bỏ AB->D + B->C : tính B+=B không thể bỏ. + C->D : tính C+=C không thể bỏ. Phủ tối thiểu là Ftt = {B->C, C->D} Ví dụ  Cho F= {ABC,AD,DE,ACB}  Một số bài tập ví dụ Siêu khóa và khóa  Cho R(U)  S  U là siêu khóa nếu rR,t1,t2r,t1t2 thì t1[S], t2[S]  K  U là khóa nếu K là siêu khóa nhỏ nhất  AK được gọi là thuộc tính khóa  Nhận xét:  S xác định tất cả các thuộc tính của R  R có thể có nhiều khóa. Xác định khóa của lược đồ  Nhập: tập PTH F xác định trên lược đồ R(U)  Xuất: khóa K của R Bước 1: K = U = {A1,…,An} i= 1; Bước 2: Nếu U(K-{Ai})F+ thì K= K - {Ai} i= i+1; Bước 3: Xuất K Ví dụ tìm khóa của lược đồ  Cho R(U), U = {A,B,C,D,E,F,G}  Cho F = {BA,DC,DBE,DFG} Tìm khóa của R: Bước 1: K=ABCDEFG Bước 2: Lặp 1 (BCDEFG)+=ABCDEFGK= BCDEFG (CDEFG)+=CDEFGBAK= CDEFG (DEFG)+= DEFGCBAK= DEFG (EFG)+= EFG (khóa K ?) (DFG)+= DFGCBEAK= DFG (DG)+= DGCBEA (khóa K ?) (DF)+=DFCBEAGK = DF Bước 3: Khóa là K= DF Ví dụ tìm khóa của lược đồ  Tìm khóa của lược đồ quan hệ:  U={A,B,C,D,E}  Cho F= {ABC,AD,DE,ACB} Xác định tất cả các khóa của lược đồ  Nhập tập PTH F xác định trên lược đồ quan hệ R(U)  Xuất tất cả các khóa của R Bước 1: Xây dựng 2n tập con của U={A1,…,An} S={}; Bước 2: Với mỗi tập con XU Nếu U XF+ thì S=S  {X} Bước 3: X,YS, nếu XY thì S=S - {X} Bước 4: S là tập các khóa của R Ví dụ tìm tất cả các khóa của R  Cho R(U), U = {A,B,C,D,E,F}. F={AEC,CFA,BDF,AFE}. Tìm tất cả các khóa của R. Tập siêu khóa: S={ABD,BCD,ABCD,ABDE,BCDE,ABCDE,A BDF,BCDF,ABCDF,ABDEF,BCDEF,ABCDEF} Xác định tất cả các khóa của lược đồ ABDF ABDE ABCD ABD BCD BCDE BCDF BCDEF ABDEF ABCDE ABCDF ABCDEF Thuật toán cơ bản tìm all các khóa Bước 1: Xác định tất cả các tập con khác rỗng của R+. Giả sử X1,X2,..,X2n-1 Bước 2: Tìm bao đóng của Xi Bước 3: Siêu khóa là các Xi có bao đóng đúng bằng R+. Giả sử ta có các siêu khóa S= {S1, S2,..,Sm } Bước 4: Xây dựng tập chứa tất cả các khóa của R từ tập S bằng cách xét mọi Si, Sj con của S(ij), nếu SiSj thì ta loại Sj(i,j=1..n), kết quả còn lại của S chính là tập các khóa cần tìm. Ví dụ tìm khóa  Tìm tất cả các khóa của lược đồ quan hệ:  R (C,S,Z) F={CSZ, ZC} Xi Xi+ Siêu khóa Khóa C C CS CSZ CS CS Z ZC CZ CZ SZ SZC SZ SZ CSZ CSZ CSZ Tập các khóa K=CS và K=SZ Thuật toán tìm tất cả các khóa cải tiến  TN: chứa các thuộc tính vế trái(kh xuất hiện vế phải) + các thuộc tính không xuất hiện ở hai vế.  TD: chứa các thuộc tính vế phải  TG: tập chứa các thuộc tính xuất hiện ở cả VT và VP.  Hệ quả: nếu K là khóa của Q thì TNK và TDK=  Thuật toán tìm tất cả các khóa  Dữ liệu vào: lược đồ quan hệ R và tập F  Dữ liệu ra: tất cả các khóa của R Thuật toán tìm khóa được mô tả như sau: Bước 1: xác định tập TN và TD Bước 2: nếu TG= thì lược đồ quan hệ chỉ có một khóa K. K=TN ngược lại, qua bước 3 Bước 3: tìm tất cả các tập con Xi của tập TG Thuật toán tìm tất cả các khóa Bước 4: tìm các siêu khóa Si bằng cách Xi Nếu (TNXi)+= R+ thì Si = TNXi Bước 5: tìm khóa bằng cách loại bỏ các siêu khóa không tối thiểu Si,SjS Nếu SiSj thì loại Sj ra khỏi tập siêu khóa S còn lại chính là tập khóa cần tìm Áp dụng thuật toán cải tiến  R (C,S,Z), F={CSZ, ZC} Ta có: TN = {S}, TG ={CZ} Gọi Xi là các tập con của tập TG: Xi (TNXi) (TNXi)+ Siêu khóa Khóa  S S C CS CSZ CS CS Z SZ SZC SZ SZ CZ SCZ SCZ SCZ Tập các khóa K=CS và K=SZ Chương 4: Chuẩn hóa dữ liệu  Chuẩn hóa là gì?  Các dạng chuẩn - Normal Form  Dạng chuẩn 1NF  Dạng chuẩn 2NF  Dạng chuẩn 3NF  Dạng chuẩn BCNF 4.1 Chuẩn hóa là gì? Mục đích: Tăng cường tính tổ chức cho cơ sở dữ liệu Loại bỏ những dữ liệu dư thừa  Duy trì tính toàn vẹn dữ liệu cho CSDL  Quản lý và bảo mật dễ dàng hơn 4.4 Dạng chuẩn 1NF  Định nghĩa: Một lược đồ quan hệ được gọi là thuộc 1NF, nếu miền giá trị của các thuộc tính trong R chỉ chứa những giá trị nguyên tố.  Qui ước: tất cả các lược đồ quan hệ đều thuộc 1NF. 4.4 Dạng chuẩn 1NF TENPB MAPB TRPH TRUSO Nghiên cứu 5 334455 TÂN BÌNH, THỦ ĐỨC Hành chính 4 945857 GÒ VẤP TENPB MAPB TRPH TRUSO Nghiên cứu 5 334455 TÂN BÌNH Hành chính 4 945857 GÒ VẤP Nghiên cứu 5 334455 THỦ ĐỨC Không 1NF 1NF 4.4 Dạng chuẩn 2NF  Định nghĩa 1: (thuộc tính khóa) Cho R=. Khi đó, thuộc tính A được gọi là thuộc tính khóa nếu A thuộc một khóa K nào đó của R. Ví dụ: R=, với U=ABCD F={ABC,CD} K={AB}R có hai thuộc tính khóa: A và B Và R có hai thuộc tính không khóa C và D. 4.4 Dạng chuẩn 2NF  Định nghĩa 2: (phụ thuộc hàm đầy đủ) Cho R=. Khi đó XYF được gọi là một phụ thuộc hàm đầy đủ (đọc Y phụ thuộc hàm đầy đủ vào X) nếu: !Z  X sao cho ZY F+ Nhận xét: nếu XUF+ là một phụ thuộc hàm đầy đủ khi X là khóa của R. 4.4 Dạng chuẩn 2NF  Định nghĩa: Cho R=. Khi đó, R được gọi là thuộc 2NF (ký hiệu: R2NF) nếu với mọi thuộc tính không khóa A là phụ thuộc hàm đầy đủ vào mọi khóa của R. 4.4 Dạng chuẩn 2NF Nhận xét:  Nếu mọi khóa của lược đồ quan hệ R chỉ có một thuộc tính thì R thuộc 2NF.  Ta có thể chứng minh rằng: 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 khóa  Hoặc AX (XA là phụ thuộc hàm tầm thường) 4.4. Thuật toán kiểm tra 2NF  Vào: lược đồ R, phụ thuộc hàm F  Ra: khẳng định có phải là 2NF hay không?  Bước 1: Tìm tất cả các khóa của R  Bước 2: Với mỗi khóa K, tìm bao đóng của tất cả tập con thật sự S của K  Bước 3: Nếu có bao đóng S+ chứa thuộc tính không khóa thì R không đạt chuẩn 2 ngược lại thì R đạt chuẩn 2. 4.4. Ví dụ  Cho lược đồ quan hệ: R(A,B,C,D)  F={ABC;BD;BCA} Hỏi R có đạt chuẩn 2 hay không?  Áp dụng thuật toán tìm khóa nâng cao (trang 58)  Được 2 khóa: K1=AB, K2=BC.  BK1, BD, D là thuộc tính không khóa thuộc tính không khóa không phụ thuộc đầy đủ vào khóa  R không đạt chuẩn 2. Ví dụ  Cho lược đồ quan hệ Q(A,B,C,D,E,H) F={A → E; C → D; E → DH}. 2NF?  TN={ACB} TG={E}  Tìm khoá, có K={ACB}  C⊂K, C→D, D là thuộc tính không khoá⇒ D phụ thuộc không đầy đủ vào khoá nên Q không đạt chuẩn 2. 4.4. Dạng chuẩn 3NF  Định nghĩa: Cho R=. Khi đó R được gọi là thuộc 3NF (ký hiệu: R3NF) nếu XAF với AX thì: + Hoặc X là siêu khóa + Hoặc A là thuộc tính khóa Từ định nghĩa : R3NF XAF với AX sao cho: + X không là siêu khóa + A là thuộc tính không khóa 4.4. Dạng chuẩn 3NF  NKBH =, với U= {STT,NGAY,MH,TH,ĐG,SL} F={STTU, MHTH, MHĐG} NKBH 2NF (do lược đồ có một khóa duy nhất là STT chỉ có một thuộc tính) Vẫn còn tồn tại dư thừa dữ liệu. Phân tách thành 2 lược đồ con: HANG= với U1={MH,TH,ĐG}, F1={MHU1} NK= với U2={STT,NGAY,MH,SL} và F2={STTU2} 4.4. Dạng chuẩn 3NF  Ta chứng minh:  NKBH3NF  HANG,NK  3NF Ta thấy rằng: NKBH có K = {STT} Và có MH  TH  F nhưng: + MH không là siêu khóa + TH không là thuộc tính khóa Ngoài ra ta có thể thấy được: HANG,NK3NF 4.4. Thuật toán kiểm tra dạng chuẩn 3NF  Vào: lược đồ quan hệ, tập phụ thuộc hàm  Ra: Khẳng định R đạt chuẩn 3 hay không?  Bước 1: Tìm tất cả các khóa của R  Bước 2: Từ F tạo ra tập phụ thuộc hàm tương đương F1tt có vế phải 1 thuộc tính.  Bước 3: nếu mọi phụ thuộc hàm XAF1tt với AX đều có X là siêu khóa hoặc A là thuộc tính khóa thì R đạt chuẩn 3 và ngược lại là R không đạt chuẩn 3. Ví dụ xác định chuẩn 3  Cho R(A,B,C,D), F={ABC;DB;CABD};  Hỏi R có đạt chuẩn 3 hay không? TÌM KHÓA LÀ KHÂU CHỦ YẾU ĐỂ XÁC ĐỊNH THUỘC DẠNG CHUẨN NÀO ĐÓ HAY KHÔNG? SAU ĐÓ DỰA VÀO ĐỊNH NGHĨA CỦA CÁC DẠNG CHUẨN ĐỂ XÁC ĐỊNH, VIỆC NÀY ĐƯỢC THỰC HIỆN CHỦ YẾU LIÊN QUAN ĐẾN CÁC KHÓA. R(A,B,C,D), F={ABC;DB;CABD}; Xi (TNXi) (TNXi)+ Siêu khóa Khóa TN=, TG={ABCD} A A A B B B AB AB ABCD AB AB C C ABCD C C AC AC ABCD AC BC BC ABCD BC ABC ABC ABCD ABC R(A,B,C,D), F={ABC;DB;CABD} D D BD AD AD ABCD AD AD BD BD BD ABD ABD ABCD ABD Xi (TNXi) (TNXi)+ Siêu khóa Khóa CD CD ABCD CD ACD ACD ABCD ACD BCD BCD ABCD BCD ABCD ABCD ABCD ABCD Tìm tất cả các khóa  Như vậy ta được 3 khóa: K1={AB}, K2={C}, K3={AD} Mà các phụ thuộc hàm XA (={ABC;DB;CABD})trong F đều có A là thuộc tính khóa. Vậy R đạt chuẩn 3. 4.4. Dạng chuẩn BCNF (Boyce-Codd-NF)  Định nghĩa: (BCNF) Cho R=. Khi đó: RBCNFXA F+ với AX thì: X là siêu khóa. 4.4. Thuật toán kiểm tra BCNF  Vào : R và tập phụ thuộc hàm  Ra: khẳng định có phải BCNF hay không?  Bước 1: Tìm tất cả các khóa của R  Bước 2: Từ F tạo ra tập phụ thuộc hàm tương đương F1tt có vế phải 1 thuộc tính.  Bước 3: Nếu mọi phụ thuộc hàm XA F1tt với AX đều có X là siêu khóa thì R đạt chuẩn BC ngược lại R không đạt chuẩn BC. Ví dụ kiểm tra thuộc BCNF  R(A,B,C,D,E,I) F={ACDBEI,CEAD} R có thuộc dạng chuẩn BCNF hay không? TN={C},TG={ADE} Xi (TNXi) (TNXi)+ Siêu khóa Khóa  C C A AC AC D CD CD AD ACD ABCDEI ACD ACD E CE ABCDEI CE CE Kiểm tra thuộc chuẩn BCNF Xi (TNXi) (TNXi)+ Siêu khóa Khóa AE ACE ACBDEI ACE DE CDE ACBDEI CDE ADE CADE ACBDEI ACDE F={ACDBEI,CEAD} F={ACDB, ACDE, ACDI, CEA, CED} Mọi phụ thuộc hàm đều có vế trái là siêu khóa nên đạt chuẩn BC. Các ví dụ bổ sung  Q(SV,MH,THAY), F={SV,MHTHAY;THAYMH}  chuẩn 3  Q(ABCD),F={ABC,DB,CABD}3 4.4. Thuật toán kiểm tra dạng chuẩn của lược đồ quan hệ Vào: lược đồ quan hệ R và tập phụ thuộc hàm Ra: Khẳng định R đạt chuẩn gì? Bước 1: Tìm tất cả các khóa của R Bước 2:Kiểm tra chuẩn BC nếu đúng thì đạt chuẩn BC nếu không thì chuyển sang bước 3 Bước 3: Kiểm tra chuẩn 3 nếu đúng thì R đạt chuẩn 3 nếu không thì chuyển sang bước 4 Bước 4: Kiểm tra chuẩn 2 nếu không đạt thì R đạt chuẩn 1. XIN CHÂN THÀNH CẢM ƠN Lý thuyết phân tách  Kiểm tra phép tách thành 2 lược đồ bảo toàn thông tin.  Kiểm tra một phép tách bảo toàn thông tin.  Phân tách lược đồ quan hệ để thuộc một chuẩn nào đó.  Ngoài ra, trong một số trường hợp, người ta yêu cầu phép tách phải bảo toàn phụ thuộc hàm. Phép tách Định nghĩa: Cho lược đồ quan hệ R=, các lược đồ con R1=, R2=,...,Rn= là các lược đồ con. Phép tách bảo toàn thông tin Phép tách kết nối bảo toàn thông tin:  Cho lược đồ quan hệ R: R(TENNCC, DIACHI, SANPHAM, DONGIA).  R1 là một quan hệ có được bằng cách chiếu lên quan hệ R. R1(TENNCC, SANPHAM, DONGIA)  R2 là một quan hệ có được bằng cách chiếu lên quan hệ R. R2(TENNCC, DIACHI)  R’ là một quan hệ có được bằng phép nối tự nhiên giữa hai quan hệ R1 và R2 qua TENNCC. Lý thuyết phân tách TENNCC DIACHI Hùng 12 Nguyễn Kiệm Hùng 40 Nguyễn Oanh TENNCC DIACHI SANPHAM DONGIA Hùng 12 Nguyễn Kiệm Gạch ống 200 Hùng 12 Nguyễn Kiệm Gạch thẻ 250 Hùng 40 Nguyễn Oanh Gạch ống 200 R1 Lý thuyết phân tách TENNCC SANPHAM DONGIA Hùng Gạch ống 200 Hùng Gạch thẻ 250 Thực hiện phép nối tự nhiên giữa hai bảng R’= R1 nối R2 R2 TENNCC DIACHI SANPHAM Hùng 12 Nguyễn Kiệm Gạch ống Hùng 12 Nguyễn Kiệm Gạch thẻ Hùng 40 Nguyễn Oanh Gạch ống Hùng 40 Nguyễn Oanh Gạch thẻ Lý thuyết phân tách  Ta thấy R  R’ với kết quả trên ta nói phép tách R thành 2 lược đồ con R1 và R2 không bảo toàn thông tin.  Vậy với điều kiện nào thì phép tách không mất thông tin? Định nghĩa  R được gọi là lược đồ quan hệ, R1,R2 là lược đồ con có:  R1R2 = X  R1R2 = R Ta nói rằng lược đồ quan hệ R được tách thành 2 lược đồ con theo phép tách (R1,R2) là phép tách bảo toàn thông tin nếu r là quan hệ bất kỳ của R ta đều có: r = r.R1 |><| r.R2 Tính chất  Nếu R là một lược đồ quan hệ, R1,R2 là 2 lược đồ con có:  R1R2 = X  R1R2 = R XR2 Thì R= R.R1 nối R.R2 (bảo toàn thông tin) Ví dụ  Cho R(SAIP), R1=SA, R2=SIP, F={SA, SIP}. Việc tách R thành R1 và R2 có gây mất mát thông tin hay không?  Áp dụng tính chất trên ta có:  R1R2 = S  R1R2 = R SSA ( phép tách là bảo toàn thông tin) Phép tách R thành n lược đồ con  R là một lược đồ quan hệ, F là tập phụ thuộc hàm, R được tách thành n lược đồ con R1,R2,..,Rn theo từng bước mà ở mỗi bước là một lược đồ được tách thành 2 lược đồ con và thỏa điều kiện của tính chất bảo toàn thông tin. Thuật toán kiểm tra phép tách bảo toàn thông tin hay không? Thuật toán: Vào: R= với U= và =(U1,U2,..,Uk) Ra: Yes/No Bước 1: Phần tử cột i dòng j là nếu AiUj Phần tử cột i dòng j là bij nếu ngược lại Thuật toán kiểm tra phép tách bảo toàn thông tin hay không?  Bước 2: biến đổi bảng. Với mỗi phụ thuộc hàm XY F ta thực hiện việc biến đổi.  Ứng với hai dòng (bộ) nào đó của bảng mà giá trị bằng nhau trên X thì thực hiện quá trình làm bằng trên Y.  Lặp lại bước 2: cho đến khi không có sự thay đổi nào trên bảng.  Bước 3: Nếu tồn tại 1 dòng chỉ toàn các giá trị ai bảo toàn thông tin. Ngược lại không bảo toàn thông tin. Thí dụ: Cho R=, với U=ABCDE F={AC,BC,CD,DEC,CEA} và =(AD,AB,BE,CDE,AE) Bước 1: lập bảng Bước 2: biến đổi bảng Bước 3: kết luận Phân rã lược đồ quan hệ  Phân rã lược đồ quan hệ thành chuẩn BCNF hay chuẩn 3 bảo toàn thông tin? Phân tách thành các lược đồ con 3NF bảo toàn thông tin  Vào: R=  Ra:  =(R1,R2,...,Rk) và  bảo toàn thông tin.  Bước 1: Kiểm tra R có thuộc 3NF hay không?  Nếu thuộc thì dừng  Nếu không thì phân tách thành 2 lược đồ con  Bước 2: kiểm tra lần lượt các lược đồ con. Cho đến khi nào tất cả đều thuộc 3NF lúc đó ta sẽ có một cây nhị phân.  Kết luận: 