Xem mẫu
- 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
nguon tai.lieu . vn
