Bài giảng Cơ sở dữ liệu và quản trị cơ sở dữ liệu - Chương 5: Lý thuyết về phụ thuộc hàm - Nguyễn Vương Thịnh

TRƯỜNG ĐẠI HỌC HÀNG HẢI VIỆT NAMKHOA CÔNG NGHỆ THÔNG TINBÀI GIẢNG HỌC PHẦNCƠ SỞ DỮ LIỆU VÀ QUẢN TRỊ CƠ SỞ DỮ LIỆUGiảng viên: ThS. Nguyễn Vương ThịnhBộ môn: Hệ thống thông tinHải Phòng, 2016Chương 5LÝ THUYẾT VỀ PHỤ THUỘC HÀM2Thông tin về giảng viênHọ và tênNguyễn Vương ThịnhĐơn vị công tácBộ môn Hệ thống thông tin – Khoa Công nghệ thông tinHọc vịThạc sỹChuyên ngànhHệ thống thông tinCơ sở đào tạoTrường Đại học Công nghệ - Đại học Quốc Gia Hà NộiNăm tốt nghiệp2012Điện thoại0983283791Emailthinhnv@vimaru.edu.vnWebsiteông tin về học phầnTên học phầnCơ sở dữ liệu và quản trị cơ sở dữ liệuTên tiếng AnhDatabase and Database ManagementMã học phần17425Số tín chỉ04 tín chỉ (LT: 45 tiết, TH: 30 tiết)Bộ môn phụ tráchHệ thống thông tinPHƯƠNG PHÁP HỌC TẬP, NGHIÊN CỨUNghe giảng, thảo luận, trao đổi với giảng viên trên lớp.Tự nghiên cứu tài liệu và làm bài tập ở nhà.PHƯƠNG PHÁP ĐÁNH GIÁSV phải tham dự ít nhất 75% thời gian.Có 02 bài kiểm tra viết giữa học phần (X2 = (L1 + L2)/2), 01 bài kiểm tra thực hành (X3). Điểm quá trình X = (X2 + X3)/2.Thi kết thúc học phần bằng hình thức trắc nghiệm khách quan trên máy tính (Z = 0.5X + 0.5Y).4Tài liệu tham khảoElmasri, Navathe, Somayajulu, Gupta, Fundamentals of Database Systems (the 4th Edition), Pearson Education Inc, 2004.Nguyễn Tuệ, Giáo trình Nhập môn Hệ Cơ sở dữ liệu, Nhà xuất bản Giáo dục Việt Nam, 2007. Nguyễn Kim Anh, Nguyên lý của các hệ Cơ sở dữ liệu, Nhà xuất bản Đại học Quốc gia Hà Nội, 2004.5Tài liệu tham khảoLÝ THUYẾT VỀ PHỤ THUỘC HÀM 5.1. PHỤ THUỘC HÀM VÀ HỆ TIÊN ĐỀ ARMSTRONG5.2. BAO ĐÓNG CỦA TẬP PHỤ THUỘC HÀM5.3. BAO ĐÓNG CỦA TẬP THUỘC TÍNH5.4. PHỦ TỐI THIỂU CỦA TẬP PHỤ THUỘC HÀM5.6. KHÓA CỦA LƯỢC ĐỒ QUAN HỆ 67Giáo sư William Ward ArmstrongĐại học Montreal, Canada85.1. PHỤ THUỘC HÀM VÀ HỆ TIÊN ĐỀ ARMSTRONG5.1.1. ĐỊNH NGHĨA PHỤ THUỘC HÀMVí dụ: Xét quan hệ trên lược đồ quan hệ Đặt HàngMã KHTên KHSố CMNDĐiện ThoạiMã MHTên MHĐơn vị tínhĐơn GiáSố LượngNgày ĐặtKH01An0312755680988812322MH01USB 32GChiếc25$3011/6KH02Bình0312546780912345678MH02Ốp lưngChiếc10$10020/7KH01An0312755680988812322MH02Ốp lưngChiếc20$5028/7KH03Cường0312555660987654323MH01USB 32GChiếc25$2529/7KH02Bình0312546780912345678MH03Thẻ 16GChiếc15$2001/8KH03Cường0312555660987654323MH03Thẻ 16GChiếc15$5509/10Mã KH quyết định Tên KH, Số CMND, Điện Thoại Ký hiệu: Mã KH → Tên KH, Số CMND, Điện ThoạiSố CMND quyết định Mã KH, Tên KH, Điện ThoạiKý hiệu: Số CMND → Mã KH, Tên KH, Điện ThoạiMã MH quyết định Tên MH, Đơn Vị Tính, Đơn GiáKý hiệu: Mã MH → Tên MH, Đơn Vị Tính, Đơn GiáMã KH, Mã MH quyết định Số Lượng, Ngày ĐặtKý hiệu: Mã KH, Mã MH → Số Lượng, Ngày ĐặtPhụ thuộc hàm9Cho lược đồ quan hệ R(Ω) và các tập thuộc tính X, Y  Ω.Ta nói X quyết định Y hay Y phụ thuộc hàm vào X (ký hiệu: X→Y) khi và chỉ khi với mọi quan hệ r trên R(Ω) và với 02 bộ t1, t2 bất kỳ thuộc r ta luôn có: Nếu t1[X] = t2[X] thì t1[Y] = t2[Y]Lưu ý:+ Phụ thuộc hàm X →  đúng với mọi quan hệ r+ Phụ thuộc hàm  → Y đúng với quan hệ r có cùng giá trị trên YABCa2b2c2a1b1c1a2b2c2a1b1c1a2b2c2a1b1c1XYViết X → Y có nghĩa là:Cứ mang giá trị giống nhau trên X thì phải mang giá trị giống nhau trên Y105.1.2. HỆ TIÊN ĐỀ ARMSTRONGCho lược đồ quan hệ R(Ω) và các tập thuộc tính X, Y, Z, W  Ω5.1.2.1. LUẬT PHẢN XẠ: Nếu Y  X thì X → Y5.1.2.2. LUẬT TĂNG TRƯỞNG: Nếu X → Y thì XZ → YZ5.1.2.3. LUẬT BẮC CẦU: Nếu X → Y và Y → Z thì X → Z5.1.2.4. LUẬT KẾT HỢP: Nếu X → Y và X → Z thì X → YZ5.1.2.5. LUẬT PHÂN RÃ: Nếu X → YZ thì X → Y và X → Z5.1.2.6. LUẬT GIẢ BẮC CẦU: Nếu X → Y và YW → Z thì XW → Z Được công bố bởi William Ward Armstrong vào năm 1974115.2. BAO ĐÓNG CỦA TẬP PHỤ THUỘC HÀM  12  135.2.2.3. Tính chất của bao đóng của tập phụ thuộc hàmA. Tính phản xạ: F  F+B. Tính đơn điệu: Nếu F  G thì F+  G+ C. Tính bao phủ: Nếu F  G+ thì F+  G+ D. Tính lũy đẳng: (F+)+ = F+14 5.2.3. HỆ TIÊN ĐỀ ARMSTRONG LÀ ĐÚNG VÀ ĐẦY ĐỦA. Hệ tiên đề Armstrong là đúng: Từ tập phụ thuộc hàm F ban đầu, hệ tiên đề Armstrong chỉ có thể sinh ra các phụ thuộc hàm nằm trong F* B. Hệ tiên đề Armstrong là đầy đủ: Từ tập phụ thuộc hàm F ban đầu, hệ tiên đề Armstrong có thể sinh ra được tất cả các phụ thuộc hàm của F* Vậy nên:Kể từ giờ trở đi ta không phân biệt F* hay F+ nữa mà chỉ dùng một khái niệm bao đóng F+155.3. BAO ĐÓNG CỦA TẬP THUỘC TÍNH 16Ví dụ: Cho lược đồ quan hệ R(A,B,C,D,E,G,H) và tập phụ thuộc hàm: F = {B → A, DA → CE, D → H, GH → C, AC → D}Tìm bao đóng của X = AC.Giải:Bước 1: Xo = ACBước 2: Duyệt các phụ thuộc hàm trong F:- Có AC → D nên X1 = Xo  {D} = ACD và loại AC → D khỏi FLặp lại bước 2: Duyệt các phụ thuộc hàm còn lại trong F:- Có DA → CE nên X2 = X1  {CE} = ACDE và loại DA → CE ra khỏi F- Có D → H nên X3 = X2  {H} = ACDEH và loại D → H ra khỏi F.Lặp lại bước 2: Từ các phụ thuộc hàm còn lại F = {B → A, GH → C} không thể sinh thêm X4 từ X3 Bước 3: Thuật toán kết thúc. Bao đóng là X+ = X3 = ACDEH. 175.3.3. TÍNH CHẤT CỦA BAO ĐÓNG CỦA TẬP THUỘC TÍNHA. Tính phản xạ: X  X+B. Tính đơn điệu: Nếu X  Y thì X+  Y+C. Tính lũy đẳng: (X+)+ = X+ D. Các tính chất khác: X+Y+  (XY)+(X+Y)+ = (XY+)+ = (X+ Y+)+X → Y  Y+  X+X → X+ và X+ → XX+ = Y+  X → Y và Y → X 185.3.4. ĐỊNH LÝ BÀI TOÁN THÀNH VIÊN  19 205.3.5. TÌM BAO ĐÓNG CỦA TẬP PHỤ THUỘC HÀM DỰA TRÊN BAO ĐÓNG CỦA TẬP THUỘC TÍNHCho lược đồ quan hệ R(Ω) và tập phụ thuộc hàm FThuật toán tìm F+Bước 1: Tìm tất cả các tập thuộc tính là tập con thực sự của Ω.Bước 2: Tìm bao đóng của từng tập thuộc tính con của Ω tìm được ở bước 1.Bước 3: Dựa vào các bao đóng của các tập thuộc tính con tìm được ở bước 2 để suy ra các phụ thuộc hàm trong F+.21XX+Các tập con của X+ không thuộc XCác phụ thuộc hàm trong F+ (không kể các phụ thuộc hàm hiển nhiên)AABBCBCB, BCC → B, C → BCABABCC, AC, BC, ABCAB → C, AB → AC, AB → BC, AB → ABCACABCB, AB, BC, ABCAC → B, AC → AB, AC → BC, AC → ABCBCBCVí dụ 5.2: Cho lược đồ quan hệ R(A, B, C) và tập phụ thuộc hàm: F = {AB → C, C → B}Hãy tìm bao đóng F+ của tập phụ thuộc hàm F.Lưu ý: Các phụ thuộc hàm hiển nhiên là phụ thuộc hàm dạngX → X hoặc X → Y với Y ⊆ X225.4. PHỦ TỐI THIỂU CỦA TẬP PHỤ THUỘC HÀM5.4.1. TẬP PHỤ THUỘC HÀM TƯƠNG ĐƯƠNG5.4.1.1. Định nghĩaHai tập phụ thuộc hàm F và G được gọi là tương đương với nhau (ký hiệu F ≡ G) nếu như F+ = G+ 5.4.1.2. Cách chứng minh 2 tập phụ thuộc hàm F và G là tương đươngBước 1: Chứng minh mọi phụ thuộc hàm X → Y ∈ F là thành viên của G+ hay F  G+ và từ tính chất bao phủ suy ra F+  G+ (1)Bước 2: Chứng minh mọi phụ thuộc hàm X → Y ∈ G là thành viên của F+ hay G  F+ và từ tính chất bao phủ suy ra G+  F+ (2)Từ (1) và (2) suy ra F+ = G+ hay F ≡ G (đpcm)23Ví dụ 5.3: Cho lược đồ quan hệ R(A,B,C,D,E) và 2 tập phụ thuộc hàm:F = {A → BC, A → D, CD → E}G = {A → BCE, A → ABD, CD → E}Hai tập phụ thuộc hàm F và G có tương đương với nhau không?Giải:+ Chứng minh F  G+: Xét từng phụ thuộc hàm trong FA → BC: (A)+G = ABCDE mà BC  ABCDE nên A → BC ∈ G+ A → D: (A)+G = ABCDE mà D  ABCDE nên A → D ∈ G+ CD → E: (CD)+G = CDE mà E  CDE nên CD → E ∈ G+Vậy F  G+ hay theo tính chất bao phủ thì F+  G+ (1)+ Chứng minh G  F+: Xét từng phụ thuộc hàm trong GA → BCE: (A)+F = ABCDE mà BCE  ABCDE nên A → BCE ∈ F+ A → ABD: (A)+F = ABCDE mà ABD  ABCDE nên A → ABD ∈ F+ CD → E: (CD)+F = CDE mà E  CDE nên CD → E ∈ F+Vậy G  F+ hay theo tính chất bao phủ thì G+  F+ (2)Từ (1) và (2) suy ra F+ = G+ hay F ≡ G245.4.2. TẬP PHỤ THUỘC HÀM CÓ VẾ TRÁI KHÔNG DƯ THỪA5.4.2.1. Phụ thuộc hàm có vế trái dư thừaPhụ thuộc hàm X → Y trong F được gọi là có vế trái dư thừa (hay phụ thuộc hàm không đầy đủ) nếu như tồn tại X’ ⊂ X sao cho:F ≡ F\{X → Y} ∪ {X’ → Y}Ngược lại, X → Y được gọi là phụ thuộc hàm có vế trái không dư thừa (hay phụ thuộc hàm đầy đủ). Ví dụ: Cho tập phụ thuộc hàm F = {A → BC, B → C, AB → D}Phụ thuộc hàm AB → D có vế trái dư thừa (thừa thuộc tính B) vì:F\{AB → D} ∪ {A → D} = {A → BC, B → C, A → D} ≡ F (Bản chất là vì A → BC nên A → B và dẫn tới AB → D không cần có thuộc tính B mà chỉ cần A → D là đủ) 255.4.2.2. Tìm tập phụ thuộc hàm có vế trái không dư thừaA. Định nghĩa: Tập phụ thuộc hàm F được gọi là tập phụ thuộc hàm có vế trái không dư thừa nếu như trong F không chứa phụ thuộc hàm nào có vế trái dư thừa.B. Thuật toán loại khỏi F các thuộc tính vế trái dư thừaBước 1: Lần lượt thực hiện bước 2 cho các phụ thuộc hàm X → Y trong FBước 2: Nếu tìm được X’ ⊂ X và X’ ≠ ∅ sao cho X’ → Y ∈ F+ thì thay thế ngay phụ thuộc hàm X → Y trong F bằng X’ → Y và thực hiện lại bước 2 với phụ thuộc hàm X’ → Y vừa được thay thế. Nếu không, quay lại bước 1Ví dụ: Cho tập phụ thuộc hàm F = {A → BC, B → C, AB → D}Xét AB → D: Xét A có A+ = ABCD nên A → D ∈ F+ và ta thay AB → D trong F bằng A → D. Lúc này F = {A → BC, B → C, A → D} và là tập phụ thuộc hàm có vế trái không dư thừa.265.4.3. TẬP PHỤ THUỘC HÀM CÓ VẾ PHẢI MỘT THUỘC TÍNHBằng cách áp dụng luật phân rã, mọi tập phụ thuộc hàm F đều có thể đưa về tập phụ thuộc hàm G tương đương với nó mà vế phải mỗi phụ thuộc hàm trong G đều chỉ có 1 thuộc tính. Ví dụ 5.4:F = {A → BC, B → DE, DG → AE} ≡ G = {A → B, A → C, B → D, B → E, DG → A, DG → F}275.4.4. TẬP PHỤ THUỘC HÀM KHÔNG DƯ THỪA5.4.4.1. Phụ thuộc hàm dư thừaPhụ thuộc hàm X → Y trong F được gọi là phụ thuộc hàm dư thừa nếu: F\{X → Y} ≡ F5.4.4.2. Tập phụ thuộc hàm không dư thừaTập phụ thuộc hàm F được gọi là tập phụ thuộc hàm không dư thừa nếu như nó không chứa phụ thuộc hàm dư thừa hay nói cách khác không tồn tại F’ ⊂ F mà F’ ≡ F.5.4.4.3. Thuật toán loại bỏ các phụ thuộc hàm dư thừaBước 1: Lần lượt xét các phụ thuộc hàm X → Y ∈ F. Bước 2: Nếu X → Y ∈ (F\{X → Y})+ thì loại X → Y khỏi F.Bước 3: Thực hiện bước 2 cho các phụ thuộc hàm khác của F.28Ví dụ 5.5: Cho tập phụ thuộc hàm F = {X → YW, XW → Z, Z →Y, XY → Z}Hãy loại bỏ các phụ thuộc hàm dư thừa.Giải+ Xét X → YW: F\{X → YW} = {XW → Z, Z →Y, XY → Z}X+ = X ⊉ YW nên X → YW không dư thừa+ Xét XW → Z: F\{XW → Z} = {X → YW, Z →Y, XY → Z}(XW)+ = XYWZ ⊇ Z nên XW → Z là dư thừa và bị loại khỏi FLúc này F = {X → YW, Z →Y, XY → Z}+ Xét Z →Y: F\{Z →Y} = {X → YW, XY → Z}(Z)+ = Z ⊉ Y nên Z →Y không dư thừa+ Xét XY → Z: F\{XY → Z} = {X → YW, Z →Y}(XY)+ = XYW ⊉ Z nên XY → Z không dư thừaVậy sau khi loại các phụ thuộc hàm dư thừa thì ta có được tập phụ thuộc hàm không dư thừa F = {X → YW, Z →Y, XY → Z}295.4.5. PHỦ TỐI THIỂU5.4.5.1. Khái niệmMột tập phụ thuộc hàm được gọi là tập phụ thuộc hàm tối thiểu nếu thỏa mãn đồng thời 03 tính chất:1. Là tập phụ thuộc hàm có vế trái không dư thừa.2. Là tập phụ thuộc hàm có vế phải chỉ gồm 1 thuộc tính.3. Là tập phụ thuộc hàm không dư thừa.Với mỗi tập phụ thuộc hàm F bất kỳ, luôn tìm được ít nhất 1 tập phụ thuộc hàm tối thiểu tương đương với nó gọi là phủ tối thiểu.5.4.5.2. Thuật toán tìm phủ tối thiểu của tập phụ thuộc hàm FBước 1: Loại khỏi F các thuộc tính vế trái dư thừa.Bước 2: Đưa F về dạng có vế phải gồm 1 thuộc tính bằng cách sử dụng luật phân rã.Bước 3: Loại bỏ khỏi F các phụ thuộc hàm dư thừa.30Ví dụ 5.6: Cho lược đồ quan hệ R(A,B,C,D) và tập phụ thuộc hàm:F = {AB → CD, B → C, C → D}Tìm phủ tối thiểu của F.GiảiBước 1: Xét AB → CD: (B)+ = BCD ⊇ CD nên B → CD ∈ F+ Tức là có thể thay AB → CD bằng B → CD (A dư thừa)F = {B → CD, B → C, C → D}Bước 2: Đưa tập phụ thuộc hàm F về tập phụ thuộc hàm tương đương có vế phải chỉ gồm 1 thuộc tính:F = {B → D, B → C, C → D} 31Bước 3: F = {B → D, B → C, C → D}+ Xét B → D: G = F\{B → D} = {B → C, C → D} có (B)+G = BCD nên B → D ∈ G+ . Vậy B → D là dư thừa và ta loại nó khỏi F. Lúc này:F = {B → C, C → D}+ Xét B → C: G = F\{B → C} = {C → D} có (B)+G = B nên B → D ∉ G+ . Vậy B → C không dư thừa.+ Xét C → D: G = F\{C → D} = {B → C} có (C)+G = C nên C → D ∉ G+ . Vậy C → D không dư thừa.Vậy phủ tối thiểu cần tìm là: Ftt = {B → C, C → D}325.5. KHÓA CỦA LƯỢC ĐỒ QUAN HỆ5.5.1. ĐỊNH NGHĨACho lược đồ quan hệ R(Ω) với Ω là tập thuộc tính. Xét một tập thuộc tính K ⊆ Ω. Tập thuộc tính K được gọi là một khóa của lược đồ quan hệ R(Ω) khi và chỉ khi thỏa mãn đồng thời hai điều kiện sau đây:K+ = Ω (hay K → Ω ∈ F+).∄Ko ⊂ K sao cho Ko+ = Ω (hay Ko → Ω ∈ F+).Khóa là tập thuộc tính tối thiểu có bao đóng bằng Ω (không có tập con nào của nó có tính chất như vậy).33Khóa dự tuyển (candidate key): Trong một lược đồ quan hệ có thể tồn tại một hay nhiều khóa, ta gọi các khóa này là khóa dự tuyển (candidate key) hoặc đôi khi chỉ gọi tắt là khóa. Khóa chính (primary key): Người ta có thể chọn ra một trong số các khóa dự tuyển để sử dụng. Khi đó, khóa được chọn ra sử dụng sẽ được gọi là khóa chính (primary key).Siêu khóa (super key): Tập thuộc tính S được gọi là siêu khóa (super key) nếu nó chứa khóa hay K ⊆ S.Thuộc tính khóa và thuộc tính không khóa:Thuộc tính A được gọi là thuộc tính khóa (prime attribute) nếu như A ∈ K với K là một khóa bất kỳ của lược đồ quan hệ. Ngược lại, A được gọi là thuộc tính không khóa (nonprime attribute).34 L∩RΩ\RK35Tính chất 2: Các khóa của lược đồ quan hệ chỉ khác nhau trên các thuộc tính nằm trong tập L ∩ RTính chất 3: Nếu L ∩ R = ⍉ thì ta có Ω\R là khóa duy nhất của lược đồ quan hệ.Tính chất 4: Nếu R\L ≠ ⍉ thì tồn tại khoá K sao cho K ≠ Ω là khoá không tầm thường.5.5.3. THUẬT TOÁN TÌM MỘT KHÓA CỦA LƯỢC ĐỒ QUAN HỆÝ tưởng:Khóa của lược đồ quan hệ bị kẹp giữa hai tập thuộc tính là Ω\R và (Ω\R) ∪ (L∩R)Các khóa chỉ khác nhau trên các thuộc tính nằm trong tập L∩R. ⇒ Thuật toán tìm khóa: xuất phát từ tập siêu khóa (Ω\R)∪ (L∩R), loại bỏ dần các thuộc tính nằm trong tập L∩R cho đến khi thu được tập thuộc tính nhỏ nhất có bao đóng là Ω thì dừng lại. 36Input: Tập thuộc tính Ω và tập phụ thuộc hàm F.Output: Một khóa K của lược đồ quan hệ.beginX:= Ω\RIf (Ω\R)+ ⊂ Ω thenbeginX:= X ∪ (L∩R)for each Ai ∈ L∩R doif (X\{Ai})+ = Ω then X:= X\{Ai};end;K:=X;end.37Ví dụ 5.7: Cho lược đồ quan hệ R(A,B,C,D,E,G) với tập phụ thuộc hàm F = {B→C, C→B, A→GD}Hãy chỉ ra một khóa của lược đồ quan hệ này.GiảiΩ = ABCDEG, L = ABC, R = BCDGΩ\R = AE, L∩R = BCTa thấy (Ω\R)+ = (AE)+ = AEDG ⊂ Ω nên:X = Ω\R ∪ (L∩R) = ABCEXét (X\{B})+ = (ACE)+ = ABCEGD = Ω ⟹ X = ACEXét (X\{C})+ = (AE)+ = ADEG ≠ Ω ⟹ Không thể loại bỏ C khỏi X.Vậy K = X = ACE là một khóa của lược đồ quan hệ.38Ví dụ 5.8: Cho lược đồ quan hệ R(A,B,C,D,E,G,H,I) với tập phụ thuộc hàm F = {AB→E, AG→I, BE→I, E→G, GI→H}Hãy chỉ ra một khóa của lược đồ quan hệ này.GiảiΩ = ABCDEGHI, L = ABEGI, R = EGHIΩ\R = ABCD, L∩R = EGITa thấy (Ω\R)+ = (ABCD)+ = ABCDEGHI = Ω ⟹ K = ABCD là khóa duy nhất.39Bước 1: Đặt TN = Ω\R và TG = L∩RBước 2: if TG= ⍉ thenLược đồ quan hệ chỉ có một khóa K = TN;Kết thúc thuật toán;elseQua bước 3;Bước 3: Tìm tất cả các tập con Xi của tập TGBước 4: Gọi S là tập các khóa của lược đồ quan hệ; Đặt S = ⍉;Tìm các siêu khóa Si bằng cách: ∀Xiif (TN ∪ Xi)+ = Ω then beginSi = TN ∪ Xi;S = S ∪ {Si};end;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 ∈ Sif (Si ⊂ Sj) then S = S\{Sj};S còn lại chính là tập siêu khóa cần tìm;5.5.3. THUẬT TOÁN TÌM TẤT CẢ CÁC KHÓA CỦA LƯỢC ĐỒ QUAN HỆ40Ví dụ 5.9: Cho lược đồ quan hệ R(C,S,Z) với tập phụ thuộc hàm: F = {CS→Z, Z→C}Hãy tìm tất cả các khóa của lược đồ quan hệ này.GiảiTN = Ω\R = S, TG = L∩R = CZGọi Xi là các tập con của tập TG. Ta có bảng sau:Vậy ta tìm được tất cả là 2 khóa: SC, SZ. Siêu khóa SCZ bị loại vì nó không phải là siêu khóa tối thiểu.XiSi = TN ∪ Xi(TN ∪ Xi)+Siêu khóaKhóa⍉SS  CSCΩSCSCZSZΩSZSZCZSCZΩSCZ 41Ví dụ 5.10: Cho lược đồ quan hệ R(A,B,C,D,E,G) với tập phụ thuộc hàmF = {B→C, C→B, A→GD}Hãy tìm tất cả các khóa của lược đồ quan hệ này.GiảiΩ = ABCDEG, L = ABC, R = BCDGTN = Ω\R = AE, TG = L∩R = BCGọi Xi là các tập con của tập TG. Ta có bảng sau:Vậy ta tìm được tất cả là 2 khóa: ABE, ACE. Siêu khóa ABCE bị loại vì nó không phải là siêu khóa tối thiểu.XiSi = TN ∪ Xi(TN ∪ Xi)+Siêu khóaKhóa⍉AEAEDG  BABEΩABEABECACEΩACEACEBCABCEΩABCE 42Ví dụ 5.11: Cho lược đồ quan hệ R(A,B,C,D) với tập phụ thuộc hàm F = {AB→C, B→D, BC→A}Hãy tìm tất cả các khóa của lược đồ quan hệ này.GiảiΩ = ABCDL = ABC, R = ACDTN = Ω\R = BTG = L∩R = ACGọi Xi là các tập con của tập TG. Ta có bảng sau:Vậy ta tìm được tất cả là 2 khóa: AB, BC. Siêu khóa ABC bị loại vì nó không phải là siêu khóa tối thiểu.XiSi = TN ∪ Xi(TN ∪ Xi)+Siêu khóaKhóa⍉BBD  AABΩABABCBCΩBCBCACABCΩABC 43Ví dụ 5.12: Cho lược đồ quan hệ R(A,B,C,D,E,H) với tập phụ thuộc hàm F = {A→E, C→D, E→DH}Hãy tìm tất cả các khóa của lược đồ quan hệ này.GiảiΩ = ABCDEH, L = ACE, R = DEHTN = Ω\R = ABC, TG = L∩R = EGọi Xi là các tập con của tập TG. Ta có bảng sau:Vậy ta tìm được tất cả là 1 khóa: ABC. Siêu khóa ABCE bị loại vì nó không phải là siêu khóa tối thiểu.XiSi = TN ∪ Xi(TN ∪ Xi)+Siêu khóaKhóa⍉ABCΩABCABCEABCEΩABCE 44Ví dụ 5.13: Cho lược đồ quan hệ R(A,B,C,D,E,I) với tập phụ thuộc hàm F = {ACD→EBI, CE→AD}Hãy tìm tất cả các khóa của lược đồ quan hệ này.GiảiΩ = ABCDEI, L = ACDE, R = ABDEITN = Ω\R = C, TG = L∩R = ADEGọi Xi là các tập con của tập TG. Ta có bảng sau:Vậy ta tìm được tất cả là 2 khóa: CE, ACD. Các siêu khóa ACE, CDE, ACDE bị loại vì nó không phải là siêu khóa tối thiểu (có chứa siêu khóa CE).XiSi = TN ∪ Xi(TN ∪ Xi)+Siêu khóaKhóa⍉CC  AACAC  DCDAD  ECEΩCECEADACDΩACDACDAEACEΩACE DECDEΩCDE ADEACDEΩACDE Q & A45