Nhập môn Cơ Sở Dữ Liệu - Chương 4 ( tiếp theo )

Thuật toán thiết kế CSDL và dạng chuẩn cao hơnNội dung chi tiếtCác thuật toán thiết kế lược đồ CSDL quan hệ Các phụ thuộc hàm đa trị và dạng chuẩn 4 Các phụ thuộc nối và dạng chuẩn 5
Nội dung trích xuất từ tài liệu:
Nhập môn Cơ Sở Dữ Liệu - Chương 4 ( tiếp theo ) Chương 4 Chương4.2. Thuật toán thiết kế CSDL4.2. Thu CSDL và dạng chuẩn cao hơnNội dung chi tiết Các thuật toán thiết kế lược đồ CSDL quan hệ Các phụ thuộc hàm đa trị và dạng chuẩn 4 Các phụ thuộc nối và dạng chuẩn 5Nhập môn Cơ sở dữ liệu - Khoa CNTT 2Phép tách bảo toàn phụ thuộc Một số định nghĩa - Quan hệ vũ trụ đơn R={A1, …An} chứa tất cả các thuộc tính của CSDL - Tập hợp F các phụ thuộc hàm phải được thỏa mãn trên R - Thuật toán tách sẽ phân chia R thành 1 tập các quan hệ D= {R1, …Rm} gọi là lược đồ CSDL quan hệ và D gọi là một phép tách - Điều kiện bảo toàn thuộc tính R i =R - Tính không đầy đủ của các dạng chuẩn: không đảm bảo thiết kế CSDL tốtNhập môn Cơ sở dữ liệu - Khoa CNTT 3Phép tách bảo toàn FD… (tt) ĐN (đk bảo toàn phụ thuộc) Một phụ thuộc hàm XY phải xuất hiện trong F hoặc suy diễn ra được từ các DF thông qua các phép biến đổi trong F ĐN(phép chiếu của F trên Ri- ký hiệu là Ri(F)): Cho trước một tập hợp các phụ thuộc F trên R,trong đó Ri là một tập con của R, là một tập hợp các phụ thuộc hàm XY trong F+ sao cho các thuộc tính trong X  Y đều được chứa trong RiNhập môn Cơ sở dữ liệu - Khoa CNTT 4Phép tách bảo toàn FD… (tt) Ta nói rằng phép tách D = {R1, R2, …, Rm} của R bảo toàn phụ thuộc đối với F nếu hợp của các phép chiếu của F trên mỗi Ri trong D là tương đương với F. Điều đó có nghĩa là: ( (R1(F))  (R2(F))  …  (Rm(F)))+ = F+Nhập môn Cơ sở dữ liệu - Khoa CNTT 5Phép tách bảo toàn FD… (tt) Để kiểm tra xem một phụ thuộc hàm X B, trong đó X là tập thuộc tính thuộc về Ri, B là một thuộc tính thuộc Ri có thỏa mãn trong Ri hay không ta làm như sau: Tính X+ , Với mỗi thuộc tính B, kiểm tra 1. B là một thuộc tính của Ri 2. B là ở trong X+: 3. B không ở trong X Khi đó phụ thuộc hàm X  B thỏa mãn trong Ri.Nhập môn Cơ sở dữ liệu - Khoa CNTT 6Phép tách bảo toàn FD… (tt) Ví dụ Xét lược đồ quan hệ: R = { A,B,C,D} với các phụ thuộc hàm: A  BCD; BC  DA; D B Lược đồ này có hai khóa dự tuyển là A và BC. Lược đồ này vi phạm BCNF. Nó được tách thành: - R1 = {D,B}, lược đồ này chứa phụ thuộc hàm D  B - R2 = {A,C,D}, lược đồ này chứa phụ thuộc hàm A  CD Rõ ràng sau khi tách, phụ thuộc hàm BC  DA bị mất.Nhập môn Cơ sở dữ liệu - Khoa CNTT 7Phép tách bảo toàn FD… (tt) Thuật toán 5.1: Tạo một phép tách bảo toàn phụ thuộc D = {R1, R2, …, Rn} của một quan hệ vũ trụ R dựa trên một tập phụ thuộc hàm F sao cho mỗi Ri trong D là ở 3NF. Thuật toán này chỉ đảm bảo tính chất bảo toàn phụ thuộc, không đảm bảo tính chất nối không mất mát.Nhập môn Cơ sở dữ liệu - Khoa CNTT 8Phép tách bảo toàn FD… (tt) Input: Một quan hệ vũ trụ R và một tập phụ thuộc hàm F trên các thuộc tính của R.1. Tìm phủ tối thiểu G của F.2. Với mỗi vế trái X của một phụ thuộc hàm xuất hiện trong G, hãy tạo một lược đồ trong D với các thuộc tính {X  {A1}  {A2} … {Ak}} trong đó XA1, XA2,…, XAk chỉ là các phụ thuộc hàm trong G với X là vế trái (X là khóa của quan hệ này).3. Đặt các thuộc tính còn lại (những thuộc tính chưa được đặt vào quan hệ nào) vào một quan hệ đơn để đảm bảo tính chất bảo toàn thuộc tính.Nhập môn Cơ sở dữ liệu - Khoa CNTT 9Phép tách bảo toàn FD… (tt) Ví dụ: Xét lược đồ quan hệ: R = { A,B,C,D} với các phụ thuộc hàm: A  BCD; BC  DA; D B Yêu cầu tách lược đồ R thành tập các lược đồ sao cho bảo toàn các phụ thuộc hàm trong RNhập môn Cơ sở dữ liệu - Khoa CNTT 10Phép tách bảo toàn FD… (tt) Ta thực hiện thuật toán như sau: - B1: Tìm G là phủ tối thiểu của F.  Theo thuật toán tìm phủ tối thiểu, đầu tiên ta làm cho các vế phải trong G chỉ chứa một thuộc tính, ta có:  G = {A  B; A  C; A D; BC  D; BC  A; D  B}  Sau đó ta bỏ đi các phụ thuộc hàm thừa (A B)  G = {A  C; A D; BC  D; BC  A; D  B}. - B2: Lược đồ R sẽ được tách thành:  R1( A,C,D)  R2(B,C,D,A)  R3(D,B)Nhập môn Cơ sở dữ liệu - Khoa CNTT 11Phép tách không mất mát Phép tách D phải có một tính chất nữa là nối không mất mát (hoặc tính chất nối không phụ thêm), nó đảm bảo rằng không có các bộ giả được tạo ra khi áp dụng một phép nối tự nhiên vào các quan hệ trong phép táchNhập môn Cơ sở dữ liệu - Khoa CNTT 12Phép tách không mất mát (tt) Thuật toán 5.2: kiểm tra nối không mất mátInput: Một quan hệ vũ trụ R(A1,A2,…An), một phép tách D = {R1, R2, …, Rm} của R và một tập F các phụ thuộc hàm. 1. Tạo một ma trận S có m hàng, n cột. Mỗi cột của ma trận ứng với một thuộc tính, mỗi hàng ứng với mỗi quan hệ Ri 2. Đặt S(i,j) = 1 nếu thuộc tính Aj thuộc về quan hệ Ri và bằng 0 trong trường hợp ngược lại. 3. Lặp lại vòng lặp sau đây cho đến khi nào việc thực hiện vòng lặp không làm thay đổi S: Với mỗi phụ thuộc hàm X  Y trong F, xác định các hàng trong S có các ký hiệu 1 như nhau trong các cột ứng với các thuộc tính trong X. Nếu có một hàng trong số đó chứa 1 trong các cột ứng với thuộc tính Y thì hãy làm cho các làm cho các cột tương ứng của các hàng khác cũng chứa 1. 4. Nếu có một hàng chứa toàn ký hiệu “1” thì phép tách có tính chất nối không mất mát, ngược lại, phép tách không có tính chất đó.Nhập môn Cơ sở dữ liệu - Khoa CNTT 13Ví dụ R = (MaNV, TenNV, MaDA, TenDA, DDiem, Sốgiờ) F= {MaNV TenNV, MaDA  {TenDA, DDiem}, {MaNV, MaDA}  Sốgiờ} R1= (Ma ...