Bài giảng môn Cơ sở dữ liệu - Bài 9: Phụ thuộc hàm và dạng chuẩn (ĐH Công nghệ thông tin)

Bài giảng môn "Cơ sở dữ liệu - Bài 9: Phụ thuộc hàm và dạng chuẩn" cung cấp cho người học các kiến thức: Phụ thuộc hàm (hệ luật dẫn Amstrong, bao đóng, phủ tối thiểu,...), các dạng chuẩn. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng môn Cơ sở dữ liệu - Bài 9: Phụ thuộc hàm và dạng chuẩn (ĐH Công nghệ thông tin)Bài 9: Phụ thuộc hàm và dạng chuẩn Khoa HTTT - Đại học CNTT 1 Nội dung Phụ thuộc hàm  Hệ luật dẫn Amstrong  Bao đóng  Phủ tối thiểu  Khóa  Thuật toán tìm khóa Các dạng chuẩn  Dạng chuẩn 1  Dạng chuẩn 2  Dạng chuẩn 3  Dạng chuẩn Boyce Codd Khoa HTTT - Đại học CNTT 2 1. Phụ thuộc hàm (1)X,Y là hai tập thuộc tính trên quan hệ Rr1, r2 là 2 bộ bất kỳ trên RTa nói X xác định Y, ký hiệu X → Y, nếu và chỉ nếu r1[X] = r2[X] thì r1[Y] = r2[Y]X → Y là một phụ thuộc hàm, hay Y phụ thuộc X.X là vế trái của phụ thuộc hàm, Y là vế phải của phụ thuộc hàm.Ví dụ: cho quan hệ sinh viên như sau:SINHVIEN(Tên, Mônhọc, SốĐT, ChuyênNgành, GiảngViên, Điểm) Khoa HTTT - Đại học CNTT 3 1. Phụ thuộc hàm (2)Tên Mônhọc SốĐT ChuyênNgành GiảngViên ĐiểmHuy CSDL 0913157875 HTTT Hưng 5Hoàng CSDL 0913154521 HTTT Hưng 10Huy AV 0913157875 HTTT Thủy 5Hải Toán SXTK 0166397547 MạngMT Lan 10Tính HQTCSDL 012145475 CNPM Sang 7Tính LậpTrình 012145475 CNPM Việt 8Hoàng LậpTrình 0913154521 HTTT Việt 10Tên SốĐT ChuyênNgành? Tên Mônhọc Điểm?Mônhọc GiảngViên? Khoa HTTT - Đại học CNTT 4 1. Phụ thuộc hàm (3)Một số tính chất sau:Với mỗi Tên có duy nhất một SốĐT và ChuyênNgànhVới mỗi Mônhọc có duy nhất một GiảngViênVới mỗi Tên, Mônhọc có duy nhất một ĐiểmKý hiêu:{Tên} → {SốĐT, ChuyênNgành}{Mônhọc} → {GiảngViên}{Tên, Mônhọc} → {Điểm} Khoa HTTT - Đại học CNTT 5 1. Phụ thuộc hàm (4)Tên Mônhọc SốĐT ChuyênNgành GiảngViên Điểm Các phụ thuộc hàm kéo theo: {Tên} → {ChuyênNgành} {Mônhọc, Điểm} → {GiảngViên, Điểm} Khoa HTTT - Đại học CNTT 6 2. Hệ luật dẫn Amstrong (1)Gọi F là tập các phụ thuộc hàmĐịnh nghĩa: X → Y được suy ra từ F, hay F suy ra X →Y, ký hiệu: F ╞ X → Y nếu bất kỳ bộ của quan hệ thỏa Fthì cũng thỏa X → YHệ luật dẫn Amstrong:Với X, Y, Z, W ⊆ U. Phụ thuộc hàm có các tính chất sau:F1) Tính phản xạ: Nếu Y ⊆ X thì X → YF2) Tính tăng trưởng: {X → Y} ╞ XZ → YZF3) Tính bắc cầu: {X → Y, Y → Z} ╞ X → Z Khoa HTTT - Đại học CNTT 7 2. Hệ luật dẫn Amstrong (2)Từ hệ luật dẫn Amstrong ta suy ra một số tính chất sau:F4) Tính kết hợp: {X → Y, X → Z} ╞ X → YZF5) Tính phân rã: {X → YZ, X → Y} ╞ X → ZF6) Tính tựa bắt cầu: {X → Y, YZ → W} ╞ XZ → WVí dụ: F = {A → B, A → C, BC → D}, chứng minh A → D?1) A → B2) A → C3) A → BC (tính kết hợp F4)4) BC → D5) A → D (tính bắc cầu F3) Khoa HTTT - Đại học CNTT 8 3. Bao đóng (1)Bao đóng của tập phụ thuộc hàmBao đóng của tập phụ thuộc hàm F, ký hiệu F+ là tập tấtcả các phụ thuộc hàm được suy ra từ F.Nếu F = F+ thì F là họ đầy đủ của các phụ thuộc hàm.Thuật toán tìm bao đóng của tập thuộc tínhBao đóng của tập thuộc tính X đối với tập phụ thuộc hàmF, ký hiệu là X+F là tập tất cả các thuộc tính A có thể suydẫn từ X nhờ tập bao đóng của các phụ thuộc hàm F+ X+F = { A ∈ Q+ | X → A ∈ F+ } Khoa HTTT - Đại học CNTT 9 3. Bao đóng (2)Input: (Q,F),X ⊆ Q+Output: X+FBước 1: Tính dãy X(0) , X(1) ,…, X(i): - X(0) = X - X(i+1) = X(i) ∪ Z, ∃(Y → Z ) ∈ F(Y ⊆ X(i)), loại (Y→ Z) ra khỏi F - Dừng khi X(i+1) = X(i) hoặc khi X(i)=Q+Bước 2: Kết luận X+F = X(i) Khoa HTTT - Đại học CNTT 10 3. Bao đóng (3)Ví dụ:Cho lược đồ quan hệ R(A, B, C, D, E, G, H) và tập phụthuộc hàmF={ f1: B → A , f2: DA → CE, f3: D → H, f4: GH →C, f5: AC → D}Tìm AC+F ? Khoa HTTT - Đại học CNTT 11 3. Bao đóng (4)Bước 1: X0 = ACBước 2: Từ f1 đến f4 không thoả, f5 thoả nên X1 = AC ∪ D =ACDLặp lại bước 2: f1 không thoả, f2 thỏa nên X2=ACD ∪ CE = ACDE f3 thỏa nên X3=ACDE ∪ H =ACDEH f4 không thỏa, f5 đã thỏaLặp lại bước 2: f2, f3 và f5 đã thỏa, f1 và f4 không thỏa. NênX4=X3=ACDEHVậy AC+F=ACDEH Khoa HTTT - Đại học CNTT 12 3. Bao đóng (5)Bài toán thành viênCho tập thuộc tính Q, tập phụ thuộc hàm F trên Q vàmột phụ thuộc hàm X → Y trên Q. Câu hỏi đặt ra rằngX → Y ∈ F+ hay không? X → Y ∈ F+ ⇔ Y ⊆ X+Ví dụ:Từ ví dụ tìm bao đóng của tập thuộc tính AC. Cho biếtAC → E có thuộc F+ ?Ta có AC+F=ACDEHVì E ∈ AC+F nên AC → E ∈ F+ Khoa HTTT - Đại học CN ...