TAILIEUCHUNG - Thiết kế cơ sở dữ liệu quan hệ - Phần 5: Phủ cover của tập phụ thuộc hàm
CSDL là tập tất cả các dữ liệu tác nghiệp của một doanh nghiệp. Các dữ liệu này được tổ chức theo một cấu trúc nhất định và có một phần mềm dùng để quản lí nó (Hệ quản trị CSDL). | THIẾT KẾ CƠ SỞ DỮ LIỆU QUAN HỆ (Relational Database Designing) Phần V – PHỦ (Cover) CỦA TẬP PHỤ THUỘC HÀM Một số định nghĩa Cho F, G là 2 tập phụ thuộc hàm, F và G gọi là tương đương nếu và chỉ nếu F+=G+ Ký hiệu : F G F gọi là phủ G nếu và chỉ nếu F+ G+ 2 tập Phụ thuộc hàm tương đương Thuật toán kiểm tra F G Bước 1 : Tính F+, G+ Bước 2 : Nếu F+ = G+, => F G Thuật toán kiểm tra F G Phủ tối thiểu (minimal cover) –Tập Phụ thuộc hàm không đầy đủ Cho lược đồ Q, tập PTH F, Z Y F. Z Y gọi là có vế trái dư thừa hay Y phụ thuộc không đầy đủ vào Z hay Z Y là phụ thuộc hàm không đầy đủ nếu và chỉ nếu : A Z: F (F \ {Z Y}) {(Z-A) Y} Ngược lại, Z Y gọi là phụ thuộc hàm đầy đủ hay không có vế trái dư thừa. F được gọi (tắt) là có vế trái không dư thừa, nếu F không chứa PTH có vế trái dư thừa. Phủ tối thiểu của 1 tập phụ thuộc hàm () Phụ thuộc hàm không đầy đủ - Ví dụ Cho Q(ABC), F={AB C, B C} Xét AB C : F’ = F – {AB C} = {B C} (AB-A) C = {B C} => F’ = (F – {AB C}) {(AB-A) C} = {B C} Tính (F’)+ , ta có (F’)+ = {AB C,B C} Tính F+ = F = {AB C, B C} => F+ = (F’)+ => AB C là phụ thuộc hàm có vế trái dư thừa Phủ tối thiểu của 1 tập phụ thuộc hàm () Thuật toán loại khỏi F các PTH không đầy đủ Bước 1 : Tính F+ Bước 2 : Duyệt tập F, với mọi d = X Y F : Bước : Duyệt các tập con X’ của X : Nếu X’ Y F+ : thay X = X’, lặp lại Phủ tối thiểu của 1 tập phụ thuộc hàm () Tập phụ thuộc hàm có vế phải 1 thuộc tính Định nghĩa : F được gọi là tập phụ thuộc hàm có vế phải 1 thuộc tính nếu và chỉ nếu mọi phụ thuộc hàm trong F đều có vế phải chỉ 1 thuộc tính. Ví dụ : F = {A BC,B C,AB D}, ta tách các phụ thuộc hàm trong F để F thỏa tiêu chuẩn là tập phụ thuộc hàm có vế phải 1 thuộc tính : F = {A B, A C, B C, AB D} Phủ tối thiểu của 1 tập phụ thuộc hàm () Tập phụ thuộc hàm không dư thừa Định nghĩa : F được gọi là tập phụ thuộc hàm không dư thừa Không F’ F, F’ F Ngược lại, F được gọi là tập phụ thuộc hàm dư thừa. Ví dụ : F = {A BC, B D, AB D} F dư thừa vì
đang nạp các trang xem trước
