![](images/graphics/blank.gif)
Bài giảng Lý thuyết cơ sở dữ liệu - Chương 4: Phụ thuộc hàm
lượt xem 4
download
![](https://tailieu.vn/static/b2013az/templates/version1/default/images/down16x21.png)
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!
Bình luận(0) Đăng nhập để gửi bình luận!
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
![](images/graphics/blank.gif)
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Lý thuyết thông tin: Chương 1 - Bùi Văn Thành
68 p |
224 |
21
-
Bài giảng Lý thuyết độ phức tạp: Lý thuyết NP - Đầy đủ - PGS. TSKH Vũ Đình Hòa
23 p |
177 |
16
-
Bài giảng Lý thuyết tính toán: Chương 1 - PGS.TS. Phan Huy Khánh
10 p |
160 |
8
-
Bài giảng Lý thuyết cơ sở dữ liệu: Chương 4 - Đỗ Thị Mai Hường
89 p |
26 |
5
-
Bài giảng Lý thuyết cơ sở dữ liệu: Chương 5 - Đỗ Thị Mai Hường
136 p |
33 |
5
-
Bài giảng Lý thuyết cơ sở dữ liệu: Chương 6 - Đỗ Thị Mai Hường
114 p |
34 |
5
-
Bài giảng Lý thuyết nhận dạng - Một số kỹ thuật trong lý thuyết nhận dạng
61 p |
80 |
5
-
Bài giảng Cơ sở dữ liệu: Chương 1 - ThS. Hồ Đắc Quán
11 p |
119 |
5
-
Bài giảng Lý thuyết cơ sở dữ liệu - Chương 5: Chuẩn hóa cơ sở dữ liệu (Data normalization)
52 p |
85 |
5
-
Bài giảng Lý thuyết cơ sở dữ liệu: Chương 2 - Đỗ Thị Mai Hường
50 p |
32 |
4
-
Bài giảng Lý thuyết cơ sở dữ liệu: Chương 1 - Đỗ Thị Mai Hường
55 p |
48 |
4
-
Bài giảng Lý thuyết cơ sở dữ liệu - Chương 2: Mô hình thực thể liên kết
28 p |
57 |
4
-
Bài giảng Lý thuyết cơ sở dữ liệu: Chương 3 - Đỗ Thị Mai Hường
94 p |
28 |
4
-
Bài giảng Lý thuyết cơ sở dữ liệu - Chương 4: Đại số quan hệ
43 p |
87 |
3
-
Bài giảng Lý thuyết cơ sở dữ liệu - Chương 1: Các khái niệm cơ bản
18 p |
79 |
3
-
Bài giảng Lý thuyết cơ sở dữ liệu - Chương 3: Mô hình cơ sở dữ liệu quan hệ
35 p |
78 |
2
-
Bài giảng môn học Cơ sở dữ liệu - Chu Thị Minh Hải
75 p |
4 |
1
![](images/icons/closefanbox.gif)
![](images/icons/closefanbox.gif)
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn
![](https://tailieu.vn/static/b2013az/templates/version1/default/js/fancybox2/source/ajax_loader.gif)