Phụ thuộc hàm

Chia sẻ: Nguyen Ha | Ngày: | Loại File: PDF | Số trang:81

Thêm vào BST

Báo xấu

174
lượt xem 11
download

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

Đọc : X xác định Y Tập các thuộc tính Y phụ thuộc vào tập các thuộc tính X hoặc được suy ra từ tập các thuộc tính X. X là vế trái, Y là vế phải của phụ thuộc hàm Phụ thuộc hàm X → Y là tầm thường (trivial) khi và chỉ khi Y = X. .4.2. Định nghĩa về phụ thuộc hàm

Chủ đề:

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

Lưu

Nội dung Text: Phụ thuộc hàm

Chương 4: PHỤ THUỘC HÀM
4.1 Các bất thường về dữ liệu  Bất thường khi cập nhật  Bất thường xóa bỏ
4.2. Định nghĩa về phụ thuộc hàm  Xét lược đồ quan hệ gồm n thuộc tính:  R(U), U = {A1, A1…. An }  Phụ thuộc hàm giữa hai tập thuộc tính X,Y U  Ký hiệu: X  Y  rR, t1, t2r nếu t1[X] = t2[X] thì t1[Y] = t2[Y]  Quan hệ r thỏa phụ thuộc hàm X  Y
4.2. Định nghĩa về phụ thuộc hàm  Đọc : X xác định Y  Tập các thuộc tính Y phụ thuộc vào tập các thuộc tính X hoặc được suy ra từ tập các thuộc tính X.  X là vế trái, Y là vế phải của phụ thuộc hàm  Phụ thuộc hàm X → Y là tầm thường (trivial) khi và chỉ khi Y = X.
4.2. Định nghĩa về phụ thuộc hàm  Ví dụ r (R) A B 1 4 1 5 3 7  r không thỏa AB nhưng thỏa B A
4.2. Định nghĩa về phụ thuộc hàm NHANVIEN TenNV MaNV Ngsinh Diachi MaPB TenPB TrPhong MaNVTenNV MaNVMaPB MaPB{TenPB,TrPhong} rR thỏa các phụ thuộc hàm
4.2. Định nghĩa về phụ thuộc hàm
4.2. Định nghĩa về phụ thuộc hàm  Lược đồ GV (Magv, Tengv);Magv → Tengv  Lược đồ SV (Masv, Tensv);Masv → Tensv  Lược đồ Mon(Mamon,Tenmon); Mamon → Tenmon
4.2. Định nghĩa về phụ thuộc hàm  Lược đồ Hoc (Masv, Mamon, Diem) Masv Mamon Diem A01 M01 9 A01 M02 6 A04 M01 8 Masv, Mamon → Diem
4.2. Định nghĩa về phụ thuộc hàm Nhận xét:  Các PTH xuất phát từ thế giới thực  rR, tr nếu t[X] là duy nhất thì X là một khóa của R.  Nếu K là một khóa của R thì K xác định tất cả các thuộc tính của R.  PTH dùng để đánh giá một thiết kế cơ sở dữ liệu.
4.2.1 Bao đóng của tập PTH  F là tập PTH trên R  F= { MaNVTenNV, MaPB {TenPb, TrPhong}, MaNV MaPB}  r  R thỏa F và MaNV{TenPB,TrPhong} cũng đúng với r thì MaNV{TenPB,TrPhong} được gọi là suy diễn từ F
4.2.1 Bao đóng của tập PTH Bao đóng của F ký hiệu F+ gồm:  F và  Tất cả các phụ thuộc hàm suy diễn từ F F được gọi là đầy đủ nếu F = F+
4.2.2.Hệ tiên đề Amstrong  A1: Tính phản xạ (Reflexivity) Nếu Y ⊆ X ⊆ U thì F ⊨ X → Y  A2: Tính tăng trưởng (Augmentation) Nếu X → Y đúng và Z ⊆ U thì XZ → YZ  A3: Tính bắc cầu (Transivity) Nếu X → Y và Y → Z thì X → Z đúng
4.2.3. Các luật suy diễn bổ sung  Qui tắc hợp (The union rule) {X → Y, X → Z} ⊨ X → YZ  Qui tắc giả bắc cầu(The pseudotransivity rule) {X → Y, WY → Z} ⊨ WX → Z  Qui tắc phân rã (The decomposition rule) Nếu X → Y và Z ⊆ Y thì X → Z đúng
Vấn đề  Làm thế nào để biết một PTH XY được suy diễn từ tập PTH F cho trước?  Bao đóng của tập thuộc tính X đối với F, ký hiệu X+ là:  Tập các thuộc tính PTH vào X  X+= {A  U| XA F+}  Nhận xét: XYF+ Y X+ Nếu K là khóa của R thì K+= U Nếu K là một khóa của R thì K xác định tất cả các thuộc tính của R.
Thuật toán tìm X+  Vào: U, F và X  U  Ra: X+  Bước 1: X+ = X  Bước 2: nếu tồn tại YZ  F và Y  X+ thì: X += X +  Z Tiếp tục bước 2. Ngược lại qua bước 3  Bước 3: cho X+
Ví dụ tìm X+  Cho F = {ABC, BCD, DEG}  X=BD tìm X+ = ?  X+ = BD  Tìm các PTH có vế trái là tập con của X+=BD DEG, thêm EG vào X+ ta được X+=BDEG Tìm các phụ thuộc hàm có vế trái là tập con của BDEG. Không có phụ thuộc hàm nào. Suy ra X+ = BDEG
Ví dụ tìm X+ 1. AB → C 2. C → A 3. BC → D 4. ACD →B 5. D → EG 6. BE → C 7. CG → BD 8. CE → AG TÍNH (BD)+ X+ = BDEGC
4.2.4. Kiểm tra phụ thuộc hàm suy diễn  Cho F= {ABC,AD,DE,ACB}  Hai phụ thuộc hàm: ABE và DC có được suy diễn từ F hay không?  X = AB suy ra: X+ = ABCDE có chứa E  X = D suy ra X+= DE không chứa C
Phụ thuộc hàm tương đương  Tập PTH F được nói là phủ tập PTH G nếu: G  F+. Hai tập phụ thuộc hàm được gọi là tương đương nếu G phủ F và F phủ G. Nhận xét: XYG, nếu YX+(F) thì F phủ G F và G tương đương nếu và chỉ nếu F+ = G+