Bài giảng Hệ cơ sở dữ liệu: Chương 5.2 - TS. Lê Thị Tú Kiên

Bài giảng Hệ cơ sở dữ liệu: Chương 5.2 cung cấp cho người học những kiến thức như: Các phép tách lược đồ quan hệ; Chuyển đổi mô hình thực thể liên kết sang mô hình quan hệ; Định nghĩa phép tách lược đồ quan hệ; Phép tách kết nối không tổn thất về BCNF; Phép tách bảo toàn phụ thuộc về 3NF. 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 Hệ cơ sở dữ liệu: Chương 5.2 - TS. Lê Thị Tú Kiên CHƢƠN V. THIẾT KẾ CƠ SỞ DỮ LIỆU QUAN HỆ Ở MỨC KHÁI NIỆM TS. Nguyễn Thị Kim Ngân Nội dung  Dư thừa và dị thường dữ liệu  Phụ thuộc hàm  Hệ tiên đề Armstrong  Bao đóng của tập thuộc tính  Phủ của một tập PTH  Xác định khóa của lược đồ quan hệ  Chuẩn hóa lược đồ quan hệ  Các phép tách lược đồ quan hệ  Chuyển đổi mô hình thực thể liên kết sang mô hình quan hệ Các phép tách lược đồ quan hệ  Định nghĩa phép tách lược đồ quan hệ  Phép tách kết nối không tổn thất về BCNF  Phép tách bảo toàn phụ thuộc về 3NF Các phép tách lược đồ quan hệ  Định nghĩa phép tách lược đồ quan hệ  Phép tách kết nối không tổn thất về chuẩn BCNF  Phép tách bảo toàn phụ thuộc về chuẩn 3NF Định nghĩa phép tách lược đồ quan hệ Cho lược đồ quan hệ R= U1, U2, …, Uk là các tập con của U sao cho U1  U2 …  Uk=U Fi= Ui(F)={{XY| XY F+, XYUi}, i=1,..,k Phép tách lược đồ R là việc thay thế R= bằng các lược đồ con R1 =, R2 =, …, Rk= Kí hiệu phép tách: =(R1, R2, …, Rk) hoặc =(U1, U2, …, Uk) Phép tách kết nối không tổn thất Cho lược đồ quan hệ R= r là một quan hệ bất kỳ trên R thỏa mãn F U1, U2, …, Uk là các tập con của U sao cho U=U1  U2 …  Uk Fi= Ui(F)={XY| XY F+, XYUi}, i=1,..,k Ri=, i=1,..,k ri=Ui(r), i=1,..,k Phép tách R thành {R1, R2, …, Rk} được gọi là tách kết nối không tổn thất (Lossless Join Decomposition) đối với tập phụ thuộc hàm F nếu r=r1 * r2 *…* rk Phép tách kết nối không tổn thất Bổ đề Cho, R= là một lược đồ quan hệ, r là một quan hệ trên R thỏa F U1, U2, …, Uk là các tập con của U sao cho U=U1  U2 …  Uk Fi= Ui(F)={XY| XY F+, XYUi}, i=1,..,k Ri=, i=1,..,k =(R1, R2, …, Rk) là một phép tách của R ri=Ui(r), i=1,..,k m(r)=r1 * r2 *…* rk Khi đó i) r m(r) ii) Nếu s=m(r) thì Ui(s)=ri, i=1,..,k iii) m(m(r))=m(r) Kiểm tra tính kết nối không tổn thất của một phép tách Bài toán Cho lược đồ R , trong đó, U={A1, A2, …, An} là tập các thuộc tính, F là tập các phụ thuộc hàm, U1, U2, …, Uk là các tập con của U sao cho U1  U2 …  Uk=U Kiểm tra phép tách =(U1, U2, …, Uk) có phải là phép tách kết nối không tổn thất hay không? Kiểm tra tính kết nối không tổn thất của một phép tách Thuật toán Vào: U={A1, A2, …, An}, F, =(U1, U2, …, Uk) Ra: Kết luận  có phải là phép tách kết nối không tổn thất hay không? Phƣơng pháp: Bước 1: Lập bảng kxn, Tại dòng i, cột j ta kí hiệu là aj nếu AjUi, ngược lại, ta kí hiệu là bij Bước 2: Với mỗi XY  F, xét các dòng có kí hiệu bằng nhau trên tập X. Các dòng này sẽ được thay đổi kí hiệu để chúng mang giá trị bằng nhau trên tập Y, theo quy tắc: - Nếu tồn tại một kí hiệu có dạng aj thì các kí hiệu còn lại được đổi thành aj - Nếu không có giá trị nào có dạng aj thì lấy tùy ý một ký hiệu bij để làm bằng Bước 2 được lặp lại cho đến khi không có thay đổi nào trên bảng nữa Nếu tại bước kết thúc, bảng có một dòng gồm toàn ký hiệu dạng aj thì  là phép tách kết nối không tổn thất, ngược lại  là phép tách kết nối tổn thất Kiểm tra tính kết nối không tổn thất của một phép tách Ví dụ Cho R=, trong đó U={S, A, I, P} và F={SA, SI  P} Kiểm tra =(SA, SIP) có là phép tách không tổn thất hay không? Bảng khởi tạo S A I P SA a1 a2 b13 b14 SIP a1 b22 a3 a4 Kiểm tra tính kết nối không tổn thất của một phép tách Ví dụ 1: Cho U={S, A, I, P} và F={SA, SI  P} Kiểm tra =(SA, SIP) có là phép tách không tổn thất hay không? Xét SA S A I P S A I P SA a1 a2 b13 b14  SA a1 a2 b13 b14 SIP a1 b22 a3 a4 SIP a1 a2 a3 a4 Kiểm tra tính kết nối không tổn thất của một phép tách Ví dụ 1: Cho U={S, A, I, P} và F={SA, SI  P} Kiểm tra =(SA, SIP) có là phép tách không tổn thất hay không? Xét SI  P S A I P S A I P S A I P SA a1 a2 b13 b14  SA a1 a2 b13 b14  SA a1 a2 b13 b14 SIP a1 b22 a3 a4 SIP a1 a2 a3 a4 SIP a1 a2 a3 a4 Kiểm tra tính kết nối không tổn thất của một phép tách Ví dụ 1: Cho U={S, A, I, P} và F={SA, SI  P} Kiểm tra =(SA, SIP) có là phép tách không tổn thất hay không? Xét SI  P S A I P S A I P S A I P SA a1 a2 b13 b14  SA a1 a2 b13 b14  SA a1 a2 b13 b14 SIP a1 b22 a3 a4 SIP a1 a2 a3 a4 SIP a1 a2 a3 a4 =(SA, SIP) là phép tách kết nối không tổn thất Kiểm tra tính kết nối không tổn thất của một phép tách Định lý Giả sử =(U1, U2) là một phép tách của lược đồ quan hệ R=. Khi đó,  là phép tách kết nối không tổn thất U1  U 2   U1 \ U 2   F    U1  U 2   U 2 \ U1  F  Kiểm tra tính kết nối không tổn thất của một phép tách Chứng minh định lý Giả sử U={A1, A2, …, Ai-1, Ai …, Aj, Aj+1…, An} U1={A1, A2, …, Ai-1, Ai …, Aj} U2={Ai , …, Aj,Aj+1 …, An} Bảng khởi tạo A1 A2 … Ai-1 Ai … Aj Aj+1 … An U 1 a1 a2 … ai-1 ai … aj b1j+1 … b1n U2 b21 b22 … bi-1 ai … aj aj+1 … an Kiểm tra tính kết nối không tổn thất của một phép tách Chứng minh định lý Giả sử U={A1, A2, …, Ai-1, Ai …, Aj, Aj+1…, An} U1={A1, A2, …, Ai-1, Ai …, Aj} U2={Ai , …, Aj,Aj+1 …, An} Nếu U1U2 U1\U2 F+ => Ai, Ai+1 …, Aj A1, A2, …, Ai-1 F+ A1 A2 … Ai-1 Ai … Aj Aj+1 … An A1 A2 … Ai-1 Ai … Aj Aj+1 … An U 1 a1 a2 … ai-1 ai … aj b1j+1 … b1n  U1 a1 a2 … ai-1 ai … aj b1j+1 … b1n U2 b21 b22 … bi-1 ai … aj aj+1 … an U 2 a1 a2 … ai-1 ai … aj aj+1 … an Kiểm tra tính kết nối không tổn thất của một p ...