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

Chia sẻ: Tần Mộc Phong | Ngày: | Loại File: PDF | Số trang:42

Thêm vào BST

Báo xấu

84
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ới hai 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ác phụ 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, NgaySinh 2. Luật bổ sung - gia tăng: Nếu X®Y thì XZ®YZ VD: Nếu MaNV ® HoTen thì MaNV, NgaySinh ® HoTen, NgaySinh 3. 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, DiaChi 4. 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 ® HSL 5. Luật hợp: Nếu X®Y và X®Z thì X®YZ VD: MaSV ® HoTen, MaSV ® NgaySinh thì MaSV ® HoTen, NgaySinh 6. 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®ABC Thự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 - Closure 1. 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í dụ: ¡ Ví dụ: Cho R = { A, B, C, D, E} Và F = {AàC, BàC,CàD,DEàC,CEàA } - Tính bao đóng X+ với X = (AE) 8/9/21 8:06 AM 23
Ví dụ: ¡ Cho Q+ = ABCDEG ¡ F = {AB->C; D->EG; C->A; BE->C; BC->D; CG->BD; ACD->B; CE->AG } Cho X = BD. Tính (BD)+ 8/9/21 8:06 AM 24
Ví dụ: ¡ Cho Q+ = ABCDEG F = {AB->C; D->EG; C->A; BE->C; BC->D; CG->BD; ACD->B; CE->AG } Cho X = AD Tính bao đóng (AD)+ 8/9/21 8:06 AM 25
3. Bài toán thành viên ¡ Dùng để xác định một phụ thuộc hàm bất kỳ nào đó có là thành viên của tập phụ thuộc hàm F đã cho hay không ó phụ thuộc hàm được suy dẫn từ F ¡ Thuật toán kiểm tra X®Y là thành viên của F: - Cách 1: Áp dụng các quy tắc biến đổi của Hệ tiên đề Amstrong - Cách 2: Tính X+. So sánh X+ với Y nếu YÍX+ thì khẳng định X®Y là thành viên của tập phụ thuộc hàm F, ngược lại không phải là thành viên 8/9/21 8:06 AM 26
¡ Ví dụ: Cho U = (ABCDEI) và F = { AB ® E, BE ® I, E ® C, CI ® D } - Chứng minh: AB ® CD ¡ Ví dụ: Cho R = { A, B, C, D, E, G, H } và F= { AB à C, Bà D, CDàE, CE à GH, Gà A} - Chứng minh rằng: AB à G 8/9/21 8:06 AM 27
IV. Tập phụ thuộc hàm tương đương ¡ Hai tập pth F và G được gọi là tương đương nếu: - mọi pth của F đều có thể suy được từ G - mọi pth của G đều có thể suy được từ F có nghĩa là F+ = G+ ¡ Khi đó ta nói F phủ G (và G phủ F). ¡ Kí hiệu: F º G 8/9/21 8:06 AM 30
Thuật toán ¡ Kiểm tra mọi PTH của F suy từ G: "X ® YÎF, tính X+ từ G, sau đó kiểm tra xem YÎ X+ ó Tính bao đóng của tất cả vế trái của F dựa trên tập PTH của G và kết luận dựa vào vế phải ¡ Kiểm tra mọi PTH của G suy từ F: "X ® YÎG, tính X+ từ F, sau đó kiểm tra xem YÎ X+ ó Tính bao đóng của tất cả vế trái của G dựa trên tập PTH của F và kết luận dựa vào vế phải 8/9/21 8:06 AM 31
¡ Ví dụ: Xét hai tập phụ thuộc hàm F = { A ® C, AC ® D, E® AD, E ® H } và G = { A ® CD, E ® AH } CMR: F và G là tương đương với nhau 8/9/21 8:06 AM 32