Bài giảng Lý thuyết cơ sở dữ liệu - Chương 4: Phụ thuộc hàm

Bài giảng Lý thuyết cơ sở dữ liệu - Chương 4: Phụ thuộc hàm cung cấp cho học viên những kiến thức về định nghĩa phụ thuộc hàm; biểu diễn phụ thuộc hàm; hệ tiên đề Amstrong; bao đóng - closure; tập phụ thuộc hàm tương đương;... Mời các bạn cùng tham khảo chi tiết nội dung bài giảng!

Nội dung trích xuất từ tài liệu:
Bài giảng Lý thuyết cơ sở dữ liệu - Chương 4: Phụ thuộc hàm CHƯƠNG IV:PHỤ THUỘC HÀM I. Giới thiệu¡ Functional Dependency¡ Phụ thuộc hàm là khái niệm được xây dựng để mô tả các ràng buộc logic trong CSDL - là công cụ để biểu diễn các ràng buộc logic giữa các thuộc tính của quan hệ 8/9/21 8:06 AM 2 *Định nghĩa PTH¡Cho quan hệ R(U), trong đó U = {A1, A2,…An} là tập thuộc tính.Cho X,Y là tập thuộc tính con thuộc U¡Nói rằng X xác định hàm Y hay Y phụ thuộc hàm vào X, kýhiệu X®Y, nếu với mọi quan hệ (bộ) r xác định trên R(U) và vớihai bộ t1 và t2 bất kỳ mà t1[X] = t2[X] thì t1[Y] = t2[Y]¡Cách đọc khác: X xác định duy nhất Y (hay X kéo theo Y) -X gọi là vế trái của PTH, Y là vế phải acủa PTH¡Ký hiệu: F:= { f : Lj → Rj | Lj, Rj ⊆ Ω } là tập cácphụ thuộc hàm trên các thuộc tính Ω 8/9/21 8:06 AM 3¡ Ví dụ:HOADON (soHD, NgayLap, TongGiaTri)CHITIET_HOADON (SoHD, MaHang, SoLuong, DonGia, ThanhTien) - SoHD ® NgayLap - SoHD ® TongGiaTri - SoHD, MaHang ® SoLuong - SoHD, MaHang ® DonGia - SoHD, MaHang ® ThanhTien 8/9/21 8:06 AM 4¡ Biểu diễn phụ thuộc hàm: - Liệt kê các thuộc tính, dùng đường nối mũi tên từ các thuộc tính vế trái đến các thuộc tính vế phải của tất cả các phụ thuộc hàm¡ Ví dụ:MƯỢN( Sốthẻ, Mãsốsách, Tênngườimượn, Tênsách, Ngàymượn ) - Với các phụ thuộc hàm: FD1: Sốthẻ ® Tênngườimượn FD2: Mãsốsách ® Tênsách FD3: Sốthẻ, Mãsốsách ® Ngàymượn¡ Có sơ đồ phụ thuộc hàm như sau: Mã số Tên người Tên sách Ngàymượn Sốthẻ sách mượn FD2 FD1 FD3 8/9/21 8:06 AM 9 II. Hệ tiên đề Amstrong¡ Năm 1974, Amstrong đưa ra hệ luật dẫn hay các tính chất của phụ thuộc hàm, gọi là hệ tiên đề Amstrong¡ Hệ tiên đề Amstrong gồm các nguyên tắc biến đổi của PTH 8/9/21 8:06 AM 13 * Hệ tiên đề Amstrong:¡ Cho X, Y, Z, W Í U. Ký hiệu: XY = XÈY. Ta có các luật sau :1. Luật phản xạ: Nếu Y Í X thì X® Y VD: MaNV, HoTen, NgaySinh ® HoTen, NgaySinh2. Luật bổ sung - gia tăng: Nếu X®Y thì XZ®YZ VD: Nếu MaNV ® HoTen thì MaNV, NgaySinh ® HoTen, NgaySinh3. Luật bắc cầu: Nếu X®Y và Y®Z thì X® Z VD: Nếu có MaNV, Hoten ® MaP và MaP ® TenPhong,DiaChi thì MaNV, Hoten ® TenPhong, DiaChi4. Luật tựa bắc cầu: Nếu X®Y và WY®Z thì XW®Z VD: MaNV ® HoTen và HoTen, NgaySinh ® HSL thì MaNV, NgaySinh ® HSL5. Luật hợp: Nếu X®Y và X®Z thì X®YZ VD: MaSV ® HoTen, MaSV ® NgaySinh thì MaSV ® HoTen, NgaySinh6. Luật tách: Nếu X®Y và Z Í Y thì X®Z VD: MaSV ® HoTen, NgaySinh thì MaSV ® HoTen, MaSV ® NgaySinh 8/9/21 8:06 AM 14¡ Ví dụ: Cho R = {ABC} và tập F = { AB®C, C®A }.Áp dụng hệ tiên đề Amstrong CMR: BC®ABCThực hiện: 1. Từ C ® A 2. Có: BC ® AB (luật tăng cường thêm B) 3. Từ AB ® C 4. Có: AB ® ABC (luật tăng cường thêm AB) 5. Có BC ® ABC (bắc cầu từ (2) và (4)) Vậy tồn tại BC®ABC 8/9/21 8:06 AM 17¡ Ví dụ: Cho R = { A, B, C, E, F }và F= { AB à C, C à B , ABC à E, F à A }.Áp dụng hệ tiên đề Amstrong. CMR: FB à E 8/9/21 8:06 AM 18 III. Bao đóng - Closure1. Các khái niệm cơ bản¡ Gọi F là tập các pth trên tập thuộc tính U, X Í U¡ Bao đóng của tập thuộc tính X: là tất cả các thuộc tính A mà phụ thuộc hàm X ® A có thể được suy diễn logic từ F nhờ hệ tiên đề Amstrong. Kí hiệu: X+ X+ = { AÎU | X ® A Î F+ }ó Là tập tất cả các thuộc tính A mà được suy ra từ X¡ Bao đóng của phụ thuộc hàm: là tập tất cả các PTH được suy diễn logic từ tập pth F - F+ := {X→Y | X,Y ⊆U và X→Y được suy dẫn logic từ F} - Nếu F+ = F thì F là họ đầy đủ của các pth 8/9/21 8:06 AM 20 2. Thuật toán tìm bao đóng của tập thuộc tính¡Closure of a set attributes¡Các bước: - Bước 0: Đặt G = F và Gán X0 = X (i=0) - Bước i (i =1): Chọn phụ thuộc hàm A®B Î G Ÿ Nếu A Í Xi-1 * Nếu B Ë Xi-1 khi đó Xi = Xi-1 È B với i = 2, 3, … * G=G–{A®B} Ÿ Lặp lại bước i Ÿ Thuật toán dừng kiểm tra nếu G = ᴓ - Bước n: Tập Xi cuối cùng là kết quả Xi = Xi+1 = Xi+2 = X+ 8/9/21 8:06 AM 21¡ Ví dụ: U = (ABCDEGH) và tập pth F = {A à D, AB à DE, CE àG, EàH } - Tính bao đóng X+ với X = (AB) 8/9/21 8:06 AM 22 V ...