Phụ thuộc hàm và Chuẩn hóa cơ sở dữ liệu

Phụ thuộc hàm và Chuẩn hóa CSDL Functional Dependency and Normal Forms Giảng viên: Ths. Nguyễn Thị Khiêm Hòa NỘI DUNG • Phụ thuộc hàm. • Nguyên tắc thiết kế các lƣợc đồ quan hệ. • Chuẩn hóa lƣợc đồ CSDL • Các dạng chuẩn. • Một số thuật toán chuẩn hóa. 2Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng PHỤ THUỘC HÀM Ví dụ Bạn có nhận xét gì về mối liên hệ giữa các thuộc tính? 3Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng PHỤ THUỘC HÀM Ví dụ 4Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng PHỤ THUỘC HÀM • Tồn tại hai mối liên hệ giữa các thuộc tính trong quan hệ DU_AN • TenDA -> Diadiem_DA • TenDA-> TenPB • Mối liên hệ nhƣ thế này đƣợc gọi là phụ thuộc hàm Ví dụ 5Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng PHỤ THUỘC HÀM Định nghĩa (1) Ký hiệu Khái niệm phụ thuộc hàm f trên quan hệ R giữa hai tập hợp các thuộc tính A1, A2, ..., An và B1, B2, ..., Bm được phát biểu như sau: Nếu hai bộ của quan hệ R có giá trị giống nhau tại các thuộc tính A1, A2, ..., An, thì chúng cũng phải có giá trị giống nhau tại các thuộc tính B1, B2, ..., Bm. A1, A2, ..., An → B1, B2, ..., Bm 6Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng PHỤ THUỘC HÀM Minh họa bằng hình ảnh Hình 8.1. Ảnh hưởng của phụ thuộc hàm A->B đối với hai bộ t, u bất kỳ. 7Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng PHỤ THUỘC HÀM Định nghĩa (2) Cho R là quan hệ trên tập thuộc tính Ω, với X và Y là hai tập con (khác rỗng) bất kỳ của Ω. Nói rằng X xác định Y, hay Y phụ thuộc hàm vào X, ký hiệu X → Y, khi và chỉ khi :  r, s  R, nếu r[X] = s[X], thì r[Y] = s[Y]. 8Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng PHỤ THUỘC HÀM Ví dụ TenDA  Diadiem_DA, TenPB TenDA, TenNV  Thoigian 9Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng PHỤ THUỘC HÀM Nhận xét Phụ thuộc hàm là phương tiện biểu diễn hình thức và phát hiện ràng buộc dữ liệu. Đây là cơ sở xác định khóa và chuẩn hóa lược đồ cơ sở dữ liệu. 10Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng HỆ TIÊN ĐỀ AMSTRONG • Giả sử quan hệ R thỏa mãn tập các phụ thuộc hàm  • Chứng minh ràng R cũng phải thỏa mãn phụ thuộc hàm f Mục tiêu • Giả sử R thỏa mãn hai phụ thuộc hàm A B, và BC • Chứng minh rằng R cũng thỏa mãn phụ thuộc hàm AC • Chứng minh rằng R không thỏa mãn phụ thuộc hàm CA Ví dụ 11Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng HỆ TIÊN ĐỀ AMSTRONG • Nếu Y ⊆ X, thì X Y • Ví dụ: ABC  BC Luật 1: Luật phản xạ • Nếu X  Y thì XZ  YZ • Ví dụ: nếu C  D thì ABC  ABD Luật 2: Luật tăng trƣởng • Nếu X  Y và Y  Z thì X  Z • Nếu AB  CD và CD  EF thì AB  EF Luật 3: Luật bắc cầu 12Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng HỆ QUẢ CỦA TIÊN ĐỀ AMSTRONG • Nếu X  Y và X  Z thì X  YZ • Ví dụ: AB  CD, AB  EF, AB  CDEF Luật hợp • Nếu X  YZ thì X  Y và X  Z • Ví dụ: nếu AB  CDEF thì AB  CD, AB  EF, AB  C, AB  D, AB  E và AB  F Luật tách hay còn gọi là luật phân rã • Nếu X  Y và WY  Z thì WX  Z • Ví dụ: Nếu AB  EF và DEF  G thì ABD  G Luật bắc cầu giả 13Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng HỆ TIÊN ĐỀ AMSTRONG Ví dụ TenDA  Diadiem_DA TenDA  TenPB TenDA  Diadiem_DA, TenPB 14Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng HỆ TIÊN ĐỀ AMSTRONG Ví dụ TenDA  Thoigian TenNV  Thoigian TenDA, Ten NV  Thoigian? 15Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng BAO ĐÓNG CÁC THUỘC TÍNH • Bao đóng của X trên  (đƣợc ký hiệu là X+) là tập con của tập thuộc tính đƣợc xác định duy nhất bởi X qua các phụ thuộc hàm trong  Định nghĩa • Phụ thuộc hàm X  B đƣợc dẫn xuất từ  • Bao đóng của X luôn chứa X Chú ý 16Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng BAO ĐÓNG CÁC THUỘC TÍNH • Phân tách các phụ thuộc hàm trong , sao cho mỗi phụ thuộc hàm trong  chỉ có một thuộc tính ở vế phải • Gọi X là tập hợp bao đóng các thuộc tính. Tại thời điểm khởi tạo X = {A1, A2, ..., An}. • Tìm một phụ thuộc hàm B1B2...Bm→C, sao cho tất cả B1, B2, ..., Bm đều nằm trong X, nhƣng C thì không. Thêm C vào tập X, và lặp lại bƣớc 3 Thuật toán tìm bao đóng 17Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng BAO ĐÓNG CÁC THUỘC TÍNH • Quan hệ R với các phụ thuộc hàm AB → C(1), BC → AD(2), D → E(3), và CF → B(4). Tìm {A, B}+ Ví dụ 1 2 3 4 Tách (2) thành BC → A(5), BC → D(6) Bắt đầu với X={A,B} Chọn (1), thêm C vào X X = {A,B,C} Chọn (2), thêm D vào X X = {A,B,C,D} Chọn (3), thêm E vào X X = {A,B,C,D,E} X+ = {A,B,C,D,E} 18Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng BAO ĐÓNG CÁC THUỘC TÍNH • Kiểm tra sự tồn tại của phụ thuộc hàm A B Ứng dụng 1 • Tìm khóa (siêu khóa) X của quan hệ R Ứng dụng 2 Tính bao đóng của A Nếu B  {A}+, thì kết luận tồn tại A  B Ngược lại, kết luận không tồn tại A  B Tính bao đóng của X Nếu {X}+ chứa tất cả thuộc tính của R, thì X là siêu khóa. Ngược lại, kết luận X không phải là siêu khóa 19Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng BAO ĐÓNG CÁC THUỘC TÍNH • Quan hệ R với các phụ thuộc hàm AB → C(1), BC → AD(2), D → E(3), và CF → B(4). • Kiểm tra sự tồn tại của phụ thuộc hàm AB → D • Kiểm tra sự tồn tại của phụ thuộc hàm D → A Ví dụ Tính {AB}+ = {A,B,C,D,E} Do {D}  {AB}+, nên tồn tại AB → D Tính {D}+ = {D,E} Do {A}  {D}+, nên không tồn tại D → A 20Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng KHÓA CỦA QUAN HỆ Định nghĩa Tập hợp của một (hoặc nhiều) thuộc tính {A1, A2, ..., An} là khóa của quan hệ R nếu thỏa mãn đồng thời hai điều kiện sau đây: 1. Các thuộc tính đó xác định tất cả các thuộc tính khác của quan hệ. 2. {A1, A2, ..., An} không có bất kỳ tập con khác rỗng nào có thể xác định tất cả các thuộc tính khác của quan hệ. Khóa phải là nhỏ nhất. 21Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng KHÓA CỦA QUAN HỆ Ví dụ 22Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng KHÓA CỦA QUAN HỆ Ví dụ (tt) Khóa của quan hệ là {TenDA, TenNV} vì: 1. {TenDA, TenNV} xác định hàm Thoigian 2. {TenDA} xác định hàm Diadiem_DA, TenPB, 3. {TenDA}, {TenNV} không xác định hàm các thuộc tính còn lại của quan hệ 23Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng KHÓA CỦA QUAN HỆ Bài tập Xác định tất cả khóa của quan hệ 24Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng SIÊU KHÓA • Siêu khóa là tập hợp các thuộc tính chứa khóa • Mọi khóa đều là siêu khóa, siêu khóa không phải là khóa Định nghĩa • Khóa là {TenDA, TenNV} • Siêu khóa là {TenDA, TenNV}, {TenDA, TenNV, TenPB} Ví dụ 25Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng THUẬT TOÁN TÌM KHÓA • Input : Lƣợc đồ quan hệ R với các thuộc tính {A1, A2, ..., An} và tập phụ thuộc hàm định nghĩa trên R • Output: Khóa của R • Thuật toán: • Khóa: = R • Với i:= 1 to n (số thuộc tính) Nếu Khóa – {Ai } là một siêu khóa của R Khóa: = Khóa - {Ai } 26Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng THUẬT TOÁN TÌM KHÓA • Ví dụ: cho R(ABCDE); F = {AB  C, C  DE} • Tìm khóa: i = 1: Xét (BCDE)+ ≠ R i = 2: Xét (ACDE)+ ≠ R i = 3: Xét (ABDE)+ = R => loại C i = 4: Xét (ABE)+ = R => loại D i = 5: Xét (AB)+ = R => loại E Vậy khóa là AB 27Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng THUẬT TOÁN TÌM NHIỀU KHÓA • Cho lƣợc đồ quan hệ R(A1, A2, ..., An) và F là tập phụ thuộc hàm định nghĩa trên R • Thuộc tính chia làm 3 loại: • Tập gốc: chỉ xuất hiện trong vế trái của phụ thuộc hàm hoặc không xuất hiện trong bất kỳ phụ thuộc hàm • Tập ngọn: chỉ xuất hiện trong vế phải của phụ thuộc hàm • Tập trung gian: các thuộc tính còn lại. 28Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng THUẬT TOÁN TÌM NHIỀU KHÓA Nhận xét: • Các thuộc tính ở nút ngọn không có trong khóa. • Các thuộc tính ở nút gốc chắc chắn phải xuất hiện trong khóa Thuật toán: • Xác định các tập thuộc tính: gốc, ngọn, trung gian • Xây dựng tổ hợp giữa tập gốc và trung gian, xét bao đóng để xác định khóa 29Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng THUẬT TOÁN TÌM KHÓA • Ví dụ: cho R(ABCDE); F = {AB  C, C  BD} • Tìm khóa: Tập gốc: A, E Tập ngọn: D Tập trung gian: B, C Tính bao đóng: (AE)+ = AE (AEB)+ = AEBCD = R+ (AEC)+ = AEBCD = R+ Vậy khóa là AEB và AEC A B C D 1 2 (1) (2) 30Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng BÀI TẬP 1 • Cho quan hệ R với các thuộc tính A,B,C,D,E,F • Các phụ thuộc hàm AC, A D, D E, E F • Tìm bao đóng của {A}+ • Tìm bao đóng của {A,B}+ Tìm bao đóng 31Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng BÀI TẬP 2 • Cho quan hệ R với các thuộc tính A,B,C,D,E,F • Các phụ thuộc hàm ABC, BCAD, DE, CFB • Tìm bao đóng của {A,B}+ • Tìm bao đóng của {BC}+ • Tìm khóa của quan hệ R Tìm bao đóng 32Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng BÀI TẬP 3 • Cho quan hệ R với các thuộc tính A,B,C,D • Các phụ thuộc hàm BC  D, D  A, A  B • Tìm tất cả các khóa của quan hệ R • Tìm tất cả các siêu khóa không phải là khóa của quan hệ R Xác định khóa, siêu khóa 33Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng BÀI TẬP 4 • Cho quan hệ R với các thuộc tính A,B,C,D • Các phụ thuộc hàm A→B, A→C, C→D • Tìm tất cả các khóa của quan hệ R • Tìm tất cả các siêu khóa không phải là khóa của quan hệ R Xác định khóa, siêu khóa 34Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng TƢƠNG ĐƢƠNG GIỮA CÁC PHỤ THUỘC HÀM • Mọi phụ thuộc hàm của F đều có thể suy đƣợc từ G và mọi phụ thuộc hàm của G đều có thể suy đƣợc từ F • Do vậy F và G là tƣơng đƣơng nếu F+ = G+ Hai tập phụ thuộc hàm F và G là tƣơng đƣơng nếu: • F và G là tương đương nếu F phủ G và G phủ F F phủ G nếu mọi phụ thuộc hàm của G đều suy được từ F ( G + ⊆ F +) 35Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng PHỤ THUỘC HÀM ĐẦY ĐỦ • Cho phụ thuộc hàm F định nghĩa trên lƣợc đồ quan hệ R. Phụ thuộc hàm X  Y là phụ thuộc hàm trên R • X  Y là phụ thuộc hàm đầy đủ nếu vế phải Y không phụ thuộc hàm vào bất kỳ tập con nào khác rỗng Z của X. •  Z  X, Z ≠ , Z Y • Y là phụ thuộc hàm đầy đủ vào X • Ví dụ: cho F = {AB→C, A→C}. Ta nói AB→C không phải là phụ thuộc hàm đầy đủ vì A→C Định nghĩa: 36Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng PHỦ TỐI THIỂU • F và G tƣơng đƣơng • G chỉ có những phụ thuộc hàm có vế phải có một thuộc tính • Các phụ thuộc hàm trong G là phụ thuộc hàm đầy đủ. Cho phụ thuộc hàm F định nghĩa trên lƣợc đồ quan hệ R. Phủ tối thiểu của F là tập phụ thuộc hàm G nếu: • Mọi tập phụ thuộc hàm đều tƣơng đƣơng với một phủ tối thiểu hoặc nhiều phủ tối thiểu Nhận xét: 37Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng THUẬT TOÁN TÌM PHỦ TỐI THIỂU • G: = F • Phân rã vế phải của các phụ thuộc hàm trong G để có tập phụ thuộc hàm chỉ có vế phải là một thuộc tính • Kiểm tra các phụ thuộc hàm đầy đủ với các phụ thuộc hàm có vế trái từ hai thuộc tính trở lên? • Loại bỏ các phụ thuộc hàm thừa. Input: tập phụ thuộc hàm F Output: tập phủ tối thiểu G 38Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng PHÉP CHIẾU PHỤ THUỘC HÀM • Cho trƣớc quan hệ R(A,B,C,D) và tập phụ thuộc hàm  = {A→B, B→C, C→D} • R1=A,C,D(R) • Xác định các phụ thuộc tồn tại trong R1 Đặt vấn đề Phải đƣợc dẫn xuất từ  Chỉ chứa các thuộc tính của R1 39Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng PHÉP CHIẾU PHỤ THUỘC HÀM • Input: Quan hệ R, tập phụ thuộc hàm S, quan hệ R1 • Output: Tập phụ thuộc hàm trên R1 • T =  • XR1, tính X +. Thêm vào T tất cả phụ thuộc hàm không hiển nhiên X  A, với A  {X}+ R1 • Tìm phủ tối thiểu của T Thuật toán 40Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng PHÉP CHIẾU PHỤ THUỘC HÀM • Bao đóng của tập rỗng và tập tất cả các thuộc tính không thể phát sinh phụ thuộc hàm không hiển nhiên. • Nếu bao đóng của một tập X nào đó là tập tất cả các thuộc tính, thì bao đóng của mọi tập chứa X đều không thể phát sinh phụ thuộc hàm mới Chú ý 41Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng PHÉP CHIẾU PHỤ THUỘC HÀM • Tìm bao đóng của tập chứa một thuộc tính • {A}+= {A, B, C, D}, T = {A→C, A→D} • {C}+= {C, D}, T = {A→C, A→D, C→D} • {D}+= {D}, T = {A→C, A→D, C→D} • Tìm bao đóng của tập chứa hai thuộc tính • {C, D}+= {C, D}, T = {A→C, A→D, C→D} • T = {A→C, A→D, C→D} Ví dụ: Cho trƣớc quan hệ R(A,B,C,D) và tập phụ thuộc hàm ={A→B, B→C, C→D}. R1=A,C,D(R). Xác định các phụ thuộc tồn tại trong R1 Không xét các tập hợp chứa thuộc tính A 42Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng PHÉP CHIẾU PHỤ THUỘC HÀM • Tìm phủ tối thiểu của T = {A→C, A→D, C→D} • Vì A→D là kết quả của phép bắc cầu của A→C và C→D, nên loại bỏ A→D không làm thay đổi tính phủ của T • T = {A→C, C→D} là phủ tối thiểu Ví dụ (tiếp) 43Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng MỘT SỐ VẤN ĐỀ KHI THIẾT KẾ CƠ SỞ DỮ LIỆU • Dữ liệu lặp đi lặp lại nhiều lần không cần thiết Dƣ thừa dữ liệu • Cập nhật dữ liệu một cách riêng rẽ, dẫn đến sự không đồng nhất về dữ liệu Xung đột dữ liệu • Thực thể vẫn tồn tại trong thực tế, nhƣng không đƣợc phản ánh trong cơ sở dữ liệu Mất mát dữ liệu 44Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng MỘT SỐ VẤN ĐỀ KHI THIẾT KẾ CƠ SỞ DỮ LIỆU Sự dƣ thừa dữ liệu 45Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng MỘT SỐ VẤN ĐỀ KHI THIẾT KẾ CƠ SỞ DỮ LIỆU Sự xung đột dữ liệu 46Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng MỘT SỐ VẤN ĐỀ KHI THIẾT KẾ CƠ SỞ DỮ LIỆU Sự mất mát dữ liệu Nhân viên Vũ Thụy Hồng Anh không được thể hiện trong CSDL 47Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng MỘT SỐ VẤN ĐỀ KHI THIẾT KẾ CƠ SỞ DỮ LIỆU Phân tách quan hệ Dƣ thừa dữ liệu Xung đột dữ liệu Mất mát dữ liệu 48Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng PHÂN TÁCH QUAN HỆ • Sự phân hoạch  = [S1, S2, …, Sk] là một phép phân tách của quan hệ R(A1, A2, …, An) nếu thỏa mãn hai điều kiện • Si  {A1, A2, …, An} • {A1, A2, …, An} = S1  S2  …  Sk Định nghĩa 49Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng PHÂN TÁCH QUAN HỆ • R1=A,B(R), R2=B,C,D(R) là một phép phân tách quan hệ R(A,B,C,D) • R1=A,B(R), R2=B,C(R), R3=C,D(R) là một phép phân tách khác của quan hệ R(A,B,C,D) Ví dụ 50Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng PHÂN TÁCH QUAN HỆ • Sự phân tách  = [S1, S2, …, Sk] của quan hệ R(A1, A2, …, An) gọi là kết nối tự nhiên nếu: Phép phân tách – kết nối tự nhiên S1(R)⋈ S2(R)⋈... ⋈Sk(R)  R 51Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng PHÂN TÁCH QUAN HỆ • Sự phân tách  = [S1, S2, …, Sk] của quan hệ R(A1, A2, …, An) gọi là không mất thông tin nếu: Phép phân tách không mất thông tin S1(R)⋈ S2(R)⋈... ⋈Sk(R) = R 52Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng PHÂN TÁCH QUAN HỆ Ví dụ R = A B C 1 2 3 4 2 5 R1=A,B(R)= A B 1 2 4 2 R2=B,C(R)= B C 2 3 2 5 Sự phân hoạch  = [(A,B), (B,C)] là: Phép phân tách quan hệ? Phép phân tách – kết nối tự nhiên? Phép phân tách không mất thông tin? 53Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng PHÂN TÁCH QUAN HỆ • Phép kết tự nhiên có tính giao hoán và kết hợp • Nếu tR, thì t[Si] Si(R) • Nếu tR, thì tS1(R)⋈ S2(R)⋈... ⋈Sk(R) • S1(R)⋈ S2(R)⋈... ⋈Sk(R) = R khi và chỉ khi mọi bộ trong phép kết tự nhiên đều nằm trong R Phân tách không mất thông tin 54Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng PHÂN TÁCH QUAN HỆ • Bước 1: Xây dựng ma trận S: n dòng và m cột (Dòng i tương ứng với Ri; Cột j tương ứng Ai) • Bƣớc 2: Gán giá trị a tại thuộc tính có trong Ri • Bƣớc 3: Với mỗi phụ thuộc hàm X  Y thuộc F: • Thay đổi giá trị tại Y bằng a nếu thỏa phụ thuộc hàm, ngƣợc lại đặt giá trị b. • Bƣớc 4: Lặp lại bƣớc 3 cho đến khi có một dòng toàn giá trị a hoặc ma trận S không thay đổi đƣợc nữa • Bƣớc 5: Kết luận Thuật toán kiểm tra bảo toàn thông tin của một phân tách 55Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng PHÂN TÁCH QUAN HỆ • R(A,B,C,D), R1=A,D(R),R2=A,C(R),R3=B,C,D(R) • Tập phụ thuộc hàm  ={A→B, B→ C, CD→A} • Kiểm tra phép phân tách không mất thông tin Ví dụ A B C D a b1 c1 d a b2 c d2 a3 b c d Lập bảng kiểm tra A B C D a b1 c1 d a b1 c d2 a3 b c d Áp dụng A→B Áp dụng B→C A B C D a b1 c d a b1 c d2 a3 b c d Áp dụng CD→A A B C D a b1 c d a b1 c d2 a b c d 56Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng CÁC DẠNG CHUẨN CỦA MÔ HÌNH DỮ LIỆU QUAN HỆ BCNF 3NF 2NF 1NF 57Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng DẠNG CHUẨN THỨ NHẤT • Một quan hệ R đƣợc gọi là ở dạng chuẩn thứ nhất (1NF) khi và chỉ khi các thuộc tính chỉ chứa các giá trị nguyên tố. Định nghĩa Ví dụ NUMBER NAME LOCATION 1 ABC TP. Cần Thơ TP. Đà Nẵng TP. Hà Nội TP. Hồ Chí Minh 2 XYZ TP. Đà Nẵng TP. Hà Nội TP. Hải Phòng NUMBER NAME LOCATION 1 ABC TP. Cần Thơ 1 ABC TP. Đà Nẵng 1 ABC TP. Hà Nội 1 ABC TP. Hồ Chí Minh 2 XYZ TP. Đà Nẵng 2 XYZ TP. Hà Nội 2 XYZ TP. Hải Phòng 58Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng DẠNG CHUẨN THỨ HAI • Một quan hệ R đƣợc gọi là ở dạng chuẩn thứ hai (2NF) khi và chỉ khi nó ở dạng chuẩn thứ nhất và mọi thuộc tính không khóa của R phụ thuộc hàm đầy đủ vào khóa chính của nó. Định nghĩa 59Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng DẠNG CHUẨN THỨ HAI • Quan hệ Phan_cong(MaNV, MaDA, Thoigian, TenNV, TenDA, Diadiem_DA) với các phụ thuộc hàm: • MaNV, MaDA  Thoigian • MaNV  TenNV • MaDA  TenDA, Diadiem_DA • Phụ thuộc hàm nào trên đây vi phạm điều kiện chuẩn thứ hai? Ví dụ 60Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng DẠNG CHUẨN THỨ BA • Quan hệ R đƣợc gọi là ở dạng chuẩn thứ ba (3NF) khi và chỉ khi nó ở dạng chuẩn thứ hai và mọi thuộc tính không khóa của nó đều không phụ thuộc bắc cầu vào khóa chính Định nghĩa 1 61Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng DẠNG CHUẨN THỨ BA • Quan hệ R đƣợc gọi là ở dạng chuẩn thứ ba (3NF) khi và chỉ khi mọi phụ thuộc hàm không hiển nhiên X →Y trong quan hệ R phải thỏa mãn một trong hai điều kiện sau đây: • X là siêu khóa,hoặc • Các thuộc tính Y không nằm trong X đều là thành viên của một khóa nào đó (không nhất thiết phải cùng một khóa). Định nghĩa 2 62Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng DẠNG CHUẨN THỨ BA • Quan hệ Phan_cong(MaNV, MaDA, Thoigian, TenNV, TenDA, Diadiem_DA) với các phụ thuộc hàm: • MaNV, MaDA  Thoigian • MaNV  TenNV • MaDA  TenDA, Diadiem_DA Ví dụ 63Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng DẠNG CHUẨN THỨ BA Ví dụ Không đạt chuẩn 3NF 64Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng DẠNG CHUẨN BCNF • Quan hệ R đƣợc gọi là ở dạng chuẩn Boyce – Codd (BCNF) khi và chỉ khi với mọi phụ thuộc hàm không hiển nhiên X → Y trên R, X là siêu khóa của R Định nghĩa 65Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng DẠNG CHUẨN BCNF Ví dụ 66Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng DẠNG CHUẨN BCNF Ví dụ TenDA Diadiem_DA TenPB Project A TP.Hà Nội Phòng giải pháp mạng truyền thông Project B TP.Hà Nội Phòng phần mềm nước ngoài 67Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng DẠNG CHUẨN BCNF • Mọi lƣợc đồ quan hệ R(A,B) đều thuộc dạng chuẩn BCNF Trƣờng hợp đặc biệt • R không có phụ thuộc hàm hiển nhiên • A B và không có B  A • B  A và không có A B • A B và B  A Chứng minh 68Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng CÁC PHƢƠNG PHÁP CHUẨN HÓA CƠ SỞ DỮ LIỆU QUAN HỆ • Hạn chế dƣ thừa dữ liệu • Không tổn thất thông tin • Không bảo toàn phụ thuộc hàm Phân tách quan hệ về dạng chuẩn BCNF • Có thể dƣ thừa dữ liệu • Không tổn thất thông tin • Bảo toàn phụ thuộc hàm Phân tách quan hệ về dạng chuẩn 3NF 69Khoa Công nghệ Thông tin - Trƣờng Đại học Ngân hàng PHÂN TÁCH QUAN HỆ VỀ DẠNG CHUẨN BCNF • Khởi tạo R = R0, S=S0 • Kiểm tra R có vi phạm BCNF hay không, nếu không trả về kết quả là R • Nếu R vi phạm, chọn X  Y là phụ thuộc hàm vi phạm. Tính X+, R1=X +(R), R2= XR \ X +(R) • Tính tập phụ thuộc hàm S1, S2 trên R1, R2 • Gọi đệ quy thuật toán này với (S1,R1) và (S2,R2) Input: Quan hệ R0 với tập phụ thuộc hàm S0 Output: Tập quan hệ Ri là kết quả c