Thiết kế cơ sở dữ liệu - Chương 3: Phương pháp chuẩn hóa lược đồ CSDL

ĐH CÔNG NGHỆ THÔNG TIN Số tiết lý thuyết: 45 tiết Số tiết thực hành: 30 tiết 1 GVHD: Dương Khai Phong – Email khaiphong@gmail.com 2  Chương 1: Giới thiệu tổng quan  Chương 2: Mô hình dữ liệu và các phụ thuộc dữ liệu  Chương 3: Phương pháp chuẩn hóa Lược đồ CSDL  Chương 4: Lý thuyết đồ thị quan hệ  Chương 5: Thiết kế CSDL ở mức vật lý  Nội dung môn học: 3  Chương 3: Phương pháp chuẩn hóa lược đồ CSDL 1. Giới thiệu dạng chuẩn 2. Phân loại dạng chuẩn 3. Phương pháp chuẩn hóa 4. Bài tập chuẩn hóa 4  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 1. Giới thiệu dạng chuẩn Xét bài toán 1: Cho thể hiện của một quan hệ sau MASV HO TEN KHOA TÊN_MH DIEM 9912 Nguyen Thu Cong nghe thong tin Tin hoc dai cuong 6 Co so du lieu 8 Toan roi rac 4 9903 Nguyen A Kinh te Xac suat thong ke 5 MASV HO TEN KHOA TÊN_MH DIEM 9912 Nguyen Thu Cong nghe thong tin Tin hoc dai cuong 6 9912 Nguyen Thu Cong nghe thong tin Co so du lieu 8 9912 Nguyen Thu Cong nghe thong tin Toan roi rac 4 9903 Nguyen A Kinh te Xac suat thong ke 5 MAMH TÊN_MH MAKHOA THDC Tin hoc dai cuong CNTT CSDL Co so du lieu CNTT TRR Toan roi rac CNTT XSTK Xac suat thong ke KT MAKHOA KHOA CNTT Cong nghe thong tin KT Kinh te MASV HO TEN 9912 Nguyen Thu 9903 Nguyen A MASV MAMH DIEM 9912 CNTT 6 9912 CNTT 8 9912 CNTT 4 9903 KT 5 Chọn lược đồ? 5  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 1. Giới thiệu dạng chuẩn Nhận xét bài toán 1:  Sự trùng lắp thông tin: tăng không gian lưu trữ  thông tin bị mâu thuẫn khi cập nhật CSDL.  Chi phí kiểm tra ràng buộc toàn vẹn.  Bảo toàn thông tin.  Bảo toàn qui tắc quản lý tức là bảo toàn các phụ thuộc hàm. 6  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 1. Giới thiệu dạng chuẩn Xét bài toán 2: Cho thể hiện của quan hệ quản lý học tập của sinh viên QLHT(MsSV, Ten, NS, Phai, ĐC, MsLop, TenLop, MsMH, TenMH, Diem) F = { f1:MsSV  Ten, NS, Phai, ĐC, MsLop; f2: MsLop  TenLop; f3: MsMH  TenMH; f4: TenMH  MsMH; f5: MsSV, MsMH  Diem } 7  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 1. Giới thiệu dạng chuẩn Xét bài toán 2: Cho thể hiện của quan hệ quản lý học tập của sinh viên QLHT(MsSV, Ten, NS, Phai, ĐC, MsLop, TenLop, MsMH, TenMH, Diem) F = { f1:MsSV  Ten, NS, Phai, ĐC, MsLop; f2: MsLop  TenLop; f3: MsMH  TenMH; f4: TenMH  MsMH; f5: MsSV, MsMH  Diem }  Sửa đổi: Giả sử có 1 sv thay đổi địa chỉ  duyệt toàn bộ quan hệ để tìm và sửa địa chỉ ở các bộ liên quan đến sv này  thông tin không nhất quán. 8  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 1. Giới thiệu dạng chuẩn Xét bài toán 2: Cho thể hiện của quan hệ quản lý học tập của sinh viên QLHT(MsSV, Ten, NS, Phai, ĐC, MsLop, TenLop, MsMH, TenMH, Diem) F = { f1:MsSV  Ten, NS, Phai, ĐC, MsLop; f2: MsLop  TenLop; f3: MsMH  TenMH; f4: TenMH  MsMH; f5: MsSV, MsMH  Diem }  Xóa: Giả sử sv có mã số 1108 hiện nay chỉ đăng ký học môn CSDL xóa kết quả điểm môn này  xóa thông tin của sv này. 9  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 1. Giới thiệu dạng chuẩn Xét bài toán 2: Cho thể hiện của quan hệ quản lý học tập của sinh viên QLHT(MsSV, Ten, NS, Phai, ĐC, MsLop, TenLop, MsMH, TenMH, Diem) F = { f1:MsSV  Ten, NS, Phai, ĐC, MsLop; f2: MsLop  TenLop; f3: MsMH  TenMH; f4: TenMH  MsMH; f5: MsSV, MsMH  Diem }  Thêm: vì khóa của quan hệ là {MsSV, MsMH} và {MsSV, TenMH}  không thể thêm 1 sv vào quan hệ nếu sv đó chưa đăng ký học môn nào. 10  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 2. Phân loại dạng chuẩn DC3 BCK DC4 DC2 Dạng chuẩn 1 (DC1)  Khái niệm: Một lược đồ Q đạt DC1 nếu toàn bộ các thuộc tính của mọi bộ đều mang giá trị đơn.  Nhận xét: khi xét DC, xem DC đang xét ít nhất đạt DC1. DC1 * Tips: Giá trị đơn là giá trị không phải kết hợp bởi nhiều thông tin có ý nghĩa khác nhau. Ví dụ: giá trị của thuộc tính Bằng cấp: {“Thạc sĩ”,”ĐH CNTT”}: thuộc tính mang giá trị kép. {“Thạc sĩ}: thuộc tính mang giá trị đơn. 11  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 2. Phân loại dạng chuẩn DC3 BCK DC4 DC1 Dạng chuẩn 2 (DC2)  Khái niệm: Một lược đồ Q đạt DC2 nếu  Q ở dạng DC1.  Mọi thuộc tính không khóa đều phụ thuộc đầy đủ vào các khóa của Q. DC2 * Tips: Thuộc tính A được gọi là phụ thuộc đầy đủ vào tập thuộc tính X nếu:  A  XF +  X  A là pth nguyên tố. Ví dụ: MsSV, MsMH  TenSV là pth không đầy đủ do: MsSV  TenSV 12  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 2. Phân loại dạng chuẩn DC3 BCK DC4 DC1 Dạng chuẩn 2 (DC2)  Thuật toán kiểm tra DC2:  Input: Q,F  Output: Q đạt DC2?  Thuật toán: B1: Tìm tập các khóa của Q B2: Với mỗi khóa, tính bao đóng của tất cả các tập con thật sự S của Q. B3: Nếu có bao đóng S+ chứa thuộc tính không khóa thì Q không đạt DC2 (ngược lại đạt). DC2 * Tips: Nếu mỗi khóa của quan hệ Q chỉ có một thuộc tính thì Q hiển nhiên đạt DC2. 13  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 2. Phân loại dạng chuẩn DC3 BCK DC4 DC1 Dạng chuẩn 2 (DC2) Ví dụ: Cho Q (A,B,C,D) và F=(ABC;BD;BC A). Hỏi Q đạt DC2? Giải: B1: tìm tập các khóa N = {B},M= {AC} DC2 AC Ki Ki = N  Ki K +I.F Siêu khóa Khóa 00  B BD 01 C BC BCAD = Q+ BC AB 10 A BA BACD = Q+ AB BC 11 AC BAC BACD = Q+ BAC 14  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 2. Phân loại dạng chuẩn DC3 BCK DC4 DC1 Dạng chuẩn 2 (DC2) Ví dụ: Cho Q (A,B,C,D) và F = (ABC ; B D ; BC  A). Hỏi Q đạt DC2? Giải: B1: tập các khóa {AB},{BC} B2,3: tính bao đóng các tập con của khóa {AB}, {BC} DC2 AB Si (Si) + Kết luận 00   01 B BD (BD)+ chứa thuộc tính không khóa D 10 A A 11 AB ABCD  Kết luận: Q không đạt DC2 15  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 2. Phân loại dạng chuẩn DC2 BCK DC4 DC1 Dạng chuẩn 3 (DC3)  Khái niệm 1: Một lược đồ Q đạt DC3 nếu  Q đạt dạng DC2.  Mọi thuộc tính không khóa của Q đều không phụ thuộc bắc cầu vào một khóa bất kỳ của Q. DC3 * Tips: Thuộc tính A được gọi là phụ thuộc bắc cầu vào tập thuộc tính X nếu tồn tại nhóm thuộc tính Y  Q+ thỏa các điều kiện sau:  X  Y  F+ và Y  A  F+  Y  X  A  (X  Y) 16  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 2. Phân loại dạng chuẩn DC2 BCK DC4 DC1 Dạng chuẩn 3 (DC3)  Khái niệm 2: Một lược đồ Q đạt DC3 nếu mọi pth X  A  F+ với A  X đều có  hoặc X là siêu khóa.  hoặc A là thuộc tính khóa. DC3 * Tips: thông thường dựa trên khái niệm 2 để giải quyết bài toán kiểm tra lược đồ Q có đạt dạng chuẩn DC3? 17  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 2. Phân loại dạng chuẩn DC2 BCK DC4 DC1 Dạng chuẩn 3 (DC3) DC3  Thuật toán kiểm tra DC2:  Input: Q,F  Output: Q đạt DC3?  Thuật toán: B1: Tìm tập các khóa của Q B2: Từ F tạo tập pth tương đương Ftt có vế phải 1 thuộc tính. B3: Nếu mọi pth XA Ftt với AX đều có  hoặc X là siêu khóa.  hoặc A là thuộc tính khóa.  Q đạt DC3 hoặc ngược lại. 18  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 2. Phân loại dạng chuẩn DC2 BCK DC1 DC4 Dạng chuẩn 3 (DC3) DC3 Ví dụ: Cho Q (A,B,C,D) và F = (ABC ; DB ; C  ABD). Hỏi Q đạt DC3? Giải: B1: tìm tập các khóa N = {},M= {ABCD} (Kẻ bảng xác định tập khóa)  Tập khóa: {AB}, {AD}, {C} 19  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 2. Phân loại dạng chuẩn DC2 DC4 BCK DC1 Dạng chuẩn 3 (DC3) DC3 Ví dụ: Cho Q (A,B,C,D) và F = (ABC ; DB ; C  ABD). Hỏi Q đạt DC3? Giải: B1: tập các khóa {AB}, {AD}, {C} B2,3: tập pth tương đương Ftt của F có VP một thuộc tính: F = (ABC ; DB ; C  ABD) Ftt = (ABC ; DB ; CA ; CB ; CD) Nhận xét: - pth ABC : có C là thuộc tính khóa - pth DB : có B là thuộc tính khóa - pth CA : có A là thuộc tính khóa - pth CB : có B là thuộc tính khóa - pth CD : có D là thuộc tính khóa Đạt DC3 20  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 2. Phân loại dạng chuẩn DC2 DC3 DC1 DC4 Dạng chuẩn BCK (Boyce-Codd-Kent)  Khái niệm: Một lược đồ Q đạt BCK (còn gọi BC) nếu mọi pth không hiển nhiên đều có vế trái chứa khóa. BCK  Thuật toán kiểm tra BC:  Input: Q,F  Output: Q đạt BC?  Thuật toán: B1: Tìm tập các khóa của Q B2: Nếu mọi pth XA Ftt với AX đều có X là siêu khóa  Q đạt DC3 hoặc ngược lại. 21  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 2. Phân loại dạng chuẩn DC2 DC4 DC3 DC1 Dạng chuẩn BCK (Boyce-Codd-Kent) BCK Ví dụ 1: Cho Q (SV,MH,Thay) và F = (SV,MHThay ; ThayMH). Hỏi Q đạt BC? Giải: B1: tìm tập các khóa N={SV},M={MH,Thay} (Kẻ bảng xác định tập khóa)  Tập khóa: {SV,Thay}, {SV,MH} B2: áp dụng thuật toán - Xét pth SV,MHThay: có VT chứa khóa - Xét pth Thay MH: có VT không chứa khóa  Q không đạt BC. * Thử xét Q đạt DC3? - Xét pth SV,MHThay: VP chứa Thay là thuộc tính khóa - Xét pth Thay MH: VP chứa MH là thuộc tính khóa  Q đạt DC3. 22  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 2. Phân loại dạng chuẩn DC2 DC3 DC4 DC1 Dạng chuẩn BCK (Boyce-Codd-Kent) BCK Ví dụ 2: Cho Q (A,B,C,D,E,I) và F = (ACDEBI ; CEAD). Hỏi Q đạt BC? Giải: B1: tìm tập các khóa N={C},M={ADE} (Kẻ bảng xác định tập khóa)  Tập khóa: {ACD}, {CE} B2: áp dụng thuật toán - Xét pth ACDEBI : có VT chứa khóa ACD - Xét pth CEAD : có VT chứa khóa CE  Q đạt BC. 23  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 2. Phân loại dạng chuẩn DC2 BCK DC3 DC1 Dạng chuẩn 4 (DC4) – tham khảo  Khái niệm: Một lược đồ Q đạt DC4 nếu:  Q đạt BCK.  Với mọi phụ thuộc đa trị không hiển X-->>Y được định nghĩa trên Q thì vế trái X phải chứa 1 khóa của Q, nghĩa là AQ+ thì XA  F+. DC4 • Tips: phụ thuộc hàm đa trị (ký hiệu X -->> Y) Cho một LĐQH Q(X,Y,Z) với XQ+, Y  Q+, XY=  và Z = Q+\ {X,Y} PTH đa trị là một định nghĩa trên Q nếu mỗi giá trị x của X xác định duy nhất một tập giá trị {y1, y2,...} của Y. Tập giá trị này không phụ thuộc vào các giá trị của Z trong các bộ có liên quan đến x, y1, y2,... Nghĩa là: bộ (x, z1), (x, z2)  Q[X,Z] thì (Q: X=x và Z = z1)[Y] = (Q:X=x và z = z2)[Y] 24  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 2. Phân loại dạng chuẩn DC2 BCK DC3 DC1 DC4 Dạng chuẩn của một LĐ CSDL: là dạng chuẩn thấp nhất trong các LĐQH của LĐCSDL. Giảm trùng lắp thông tin Kiểm tra PTH và PTH đa trị • Tips: Xác định dạng chuẩn cao nhất Q? B1: Tìm tập khóa của Q B2: Q đạt BC? Nếu không sang B3. B3: Q đạt DC3? Nếu không sang B4. B4: Q đạt DC2? Nếu không xem như Q đạt DC1. ĐH CÔNG NGHỆ THÔNG TIN 25 26  Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu Xác định dạng chuẩn cao nhất của Q? 1) Q(ABCD) và F = {BD ; AC ; CABD } Giải: B1: tìm tập các khóa N = {},M= {ABC} (Kẻ bảng xác định tập khóa)  Tập khóa: {A}, {C} B2: xác định Q đạt BC? (tức mọi pth có VT chứa khóa) - Xét pth BD: có VT không chứa khóa  Q không đạt BC. B3: xác định Q đạt DC3? (tức mọi pth hoặc có VT là siêu khóa hoặc VP có thuộc tính khóa) - Xét pth BD: có VT không là siêu khóa và VP không có thuộc tính khóa.  Q không đạt DC3. B4: xác định Q đạt DC2? (tức mọi thuộc tính không khóa phụ thuộc đầy đủ vào khóa) Do mỗi khóa của quan hệ Q chỉ có một thuộc tính thì Q hiển nhiên đạt DC2. Vậy dạng chuẩn cao nhất của Q là DC2. 27  Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu Xác định dạng chuẩn cao nhất của Q? 2) Q(ABCD) và F = {DB ; CA ; BACD } Giải: B1: tìm tập các khóa N = {},M= {BCD} (Kẻ bảng xác định tập khóa)  Tập khóa: {B}, {D} B2: xác định Q đạt BC? (tức mọi pth có VT chứa khóa) - Xét pth DB: có VT chứa khóa - Xét pth CA: có VT không chứa khóa  Q không đạt BC. B3: xác định Q đạt DC3? (tức mọi pth hoặc có VT là siêu khóa hoặc VP có thuộc tính khóa) - Xét pth DB: vừa có VT là khóa vừa có VP có thuộc tính khóa. - Xét pth CA: có VT không là siêu khóa và VP không có thuộc tính khóa.  Q không đạt DC3. B4: xác định Q đạt DC2? (tức mọi thuộc tính không khóa phụ thuộc đầy đủ vào khóa) Do mỗi khóa của quan hệ Q chỉ có một thuộc tính thì Q hiển nhiên đạt DC2. Vậy dạng chuẩn cao nhất của Q là DC2. 28  Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu Xác định dạng chuẩn cao nhất của Q? 3) Q(ABCD) và F = {CDB ; AC ; BACD } Giải: B1: tìm tập các khóa N = {},M= {ABCD} (Kẻ bảng xác định tập khóa)  Tập khóa: {B}, {A,D}, {C,D} B2: xác định Q đạt BC? (tức mọi pth có VT chứa khóa) - Xét pth CDB: có VT chứa khóa - Xét pth AC: có VT không chứa khóa  Q không đạt BC. B3: xác định Q đạt DC3? (tức mọi pth hoặc có VT là siêu khóa hoặc VP có thuộc tính khóa) - Xét pth CDB: vừa có VT là khóa vừa có VP có thuộc tính khóa. - Xét pth AC: VP có thuộc tính khóa. - Xét pth BACD: VT là khóa.  Q đạt DC3. Vậy dạng chuẩn cao nhất của Q là DC3. 29  Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu Xác định dạng chuẩn cao nhất của các câu sau: 4) Q(ABCD) và F = {AB ; BC ; AD ; DC} 5) Q(ABCD) và F = {AB ; BC ; DB} 6) GIANGDAY(MaGV,MaMH,TenMH,TenGV,Hocvi,Heso,Mucluong,Lop) và F = { MaGVTenGV ; TenGVHocvi,Heso,Mucluong ; Hocvi,HesoMucluong ; MaGV, MaMH  Lop ; Lop, MaMH  MaGV ; MaMH  TenMH} 7) Q(ABCDEGTVXYZ) và F = {ABCEGDX ; GECY ; BCETD ; DVCE} 8) Q(ABCDEGRTVXYZ) và F = {EDY ; BCGZD; CGB ; ABCDEGRX ; GRV ; DT} 9) Q(AIMNLTVXYZ) và F = {AVIXLN ; LIXT; NLI ; MNZA} 10) Q(ABCDEMNOPXYZVW) và F = {DYMNPE ; MNPYYABO; MNZO ; OV ; PABW ; ABP ; NEMP} 30  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 3. Phương pháp chuẩn hóa  Giới thiệu:  Xuất phát từ giai đoạn phân tích nhu cầu, ta có thể có 1 trong 2 kết quả sau: • Dựa trên kinh nghiệm, một cấu trúc CSDL ban đầu gồm các quan hệ con Qi cùng các phụ thuộc dữ liệu 𝐹𝑄𝑖 định nghĩa trên các quan hệ con. 𝐶 = 𝑖=1 𝑛 () • Hoặc chỉ có một quan hệ phổ quát duy nhất Q0 chứa tất cả các thuộc tính cần được lưu trữ và tập các phụ thuộc FQ tìm được. C0 = 31  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 3. Phương pháp chuẩn hóa  Các tiêu chuẩn của quá trình chuẩn hóa: CSDL kết quả cần đạt dạng chuẩn cao nhất CSDL kết quả phải tương đương với CSDL phân tích lúc ban đầu  Cập nhật: hạn chế tối đa sự trùng lắp thông tin trong CSDL,  giảm thông tin bị mâu thuẫn sau những lần cập nhật CSDL  Kiểm tra RBTV: tạo điều kiện thuận lợi cho việc kiểm tra RBTV ở dạng phụ thuộc dữ liệu dựa trên cơ chế khoá sẵn có bên trong các Hệ Quản trị CSDL. 32  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 3. Phương pháp chuẩn hóa  Tiêu chuẩn tương đương: CSDL kết quả phải tương đương với CSDL phân tích lúc ban đầu Bảo toàn phụ thuộc hàm Bảo toàn thông tin Biểu diễn trọn vẹn (Vừa bảo toàn PTH vừa Bảo toàn thông tin) 33  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 3. Phương pháp chuẩn hóa  Tiêu chuẩn tương đương: Bảo toàn phụ thuộc hàm  Quan điểm: các thông tin được lưu trong CSDL là những thông tin được thể hiện thông qua các phụ thuộc dữ liệu  bảo toàn phụ thuộc hàm trong khi biến đổi.  Tiêu chuẩn tương đương: - Giả sử, C1= và 𝐶2 = {}𝑖=1 𝑛 là một biến đổi từ C1 - C1  C2 nếu hai điều kiện sau được thỏa: 𝑖=1 𝑛 𝑄𝑖 = 𝑄 + Không được xót thuộc tính ( 𝑖=1 𝑛 𝐹𝑖) += 𝐹+ Bảo toàn PTH 34  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 3. Phương pháp chuẩn hóa  Tiêu chuẩn tương đương:  Phương pháp chứng minh bảo toàn PTH: Để Chứng minh ( Fi) + = F+ , ta đặt: F' = (Fi) Và chứng minh:  f’ (F’ \ F ) thì f’  F+ và  f (F \ F’ ) thì f  F’+ Bảo toàn phụ thuộc hàm 35  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 3. Phương pháp chuẩn hóa  Tiêu chuẩn tương đương:  Quan điểm: các thông tin lưu trữ trong CSDL ban đầu đều phải được tìm thấy đầy đủ trong CSDL kết quả.  Tiêu chuẩn tương đương: - Giả sử, C1= và 𝐶2 = {}𝑖=1 𝑛 là một biến đổi từ C1 - C1  C2 nếu hai điều kiện sau được thỏa: 𝑖=1 𝑛 𝑄𝑖 = 𝑄 + Không được xót thuộc tính (⊳⊲ 𝑄[𝑄𝑖 +]) = 𝑄 Bảo toàn thông tin lưu trữ Bảo toàn thông tin 36  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 3. Phương pháp chuẩn hóa  Tiêu chuẩn tương đương:  Phương pháp kiểm tra bảo toàn thông tin của một phân rã: Cho C = {Qi} là 1 phân rã của lđqh Q có tập pth FQ . B1: Xây dựng 1 bảng 2 chiều mà các cột là các thuộc tính của Q, mỗi dòng là một Qi trong phân rã nhận được. Mỗi ô ở dòng i cột j chứa ký hiệu: a) aj nếu Qi có chứa thuộc tính thứ j của Q b) bk nếu ngược lại (trong đó k là số thứ tự xuất hiện b) B2: Biến đổi bảng dựa trên các pth có trong FQ theo qui tắc: Xét một pth f: X  Y  FQ. Chọn 2 dòng Qi, Qj sao cho: Qị.x = Qj.x Nếu Qi.Y  Qj.Y thì thực hiện thay thế trên Qi và Qj ở từng cột Ak thuộc Y theo các trường hợp sau: - Nếu cả 2 ô(i,k) và ô(j,k) đều không chứa ak  không thay đổi - Ngược lại nếu có 1 ô chứa ak thì thay ô kia bằng ký hiệu ak. B3: Lặp lại B2 cho đến khi xuất hiện 1 dòng chứa toàn ký hiệu a hoặc không còn thay đổi giá trị ak nào trong bảng. B4: Nếu xuất hiện 1 dòng chứa toàn ký hiệu a thì phân rã bảo toàn thông tin. Ngược lại thì phân rã không bảo toàn thông tin. Bảo toàn thông tin 37  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 3. Phương pháp chuẩn hóa  Tiêu chuẩn tương đương: Xét phân rã C = { Q1(MSCD. CD) ; Q2(MSCD, HG); Q3(CD, HG, MSSV)} của quan hệ Q(MSCD, MSSV, CD, HG) FQ = { f1: MSCDCD; f2: CD MSCD; f3: CD, MSSV  HG; f4: MSCD,HG  MSSV; f5: CĐ,HG  MSSV; (2 sv không đồng hạng trong cùng 1 chuyên đề) f6:MSCD,MSSV  HG} Tân từ: Mỗi chuyên đề (CD) có 1 tên phân biệt và có một mã số phân biệt (MSCD). Một chuyên đề có thể được thực hiện bởi nhiều sinh viên và hạng (HG) của mỗi sinh viên trong cùng một chuyên đề là phân biệt. Bảo toàn thông tin  Ví dụ kiểm tra bảo toàn thông tin của một phân rã C: 38  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 3. Phương pháp chuẩn hóa  Tiêu chuẩn tương đương:  Ví dụ kiểm tra bảo toàn thông tin của một phân rã C:Bảo toàn thông tin B1: lập bảng T MSCD CD MSSV HG Q1 Q2 Q3 C = { Q1(MSCD. CD) ; Q2(MSCD, HG); Q3(CD, HG, MSSV)} a1 a2 b1 b2 a1 b3 b4 a4 b5 a2 a3 a4 B2: biến đổi theo pth Ta có pth: f2: CD MSCD; T MSCD CD MSSV HG Q1 Q2 Q3 a1 a2 b1 b2 a1 b3 b4 a4 b5 a2 a3 a4a1 T MSCD CD MSSV HG Q1 Q2 Q3 a1 39  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 3. Phương pháp chuẩn hóa  Tiêu chuẩn tương đương:  Ví dụ kiểm tra bảo toàn thông tin của một phân rã C:Bảo toàn thông tin B1: lập bảng T MSCD CD MSSV HG Q1 Q2 Q3 C = { Q1(MSCD. CD) ; Q2(MSCD, HG); Q3(CD, HG, MSSV)} a1 a2 b1 b2 a1 b3 b4 a4 b5 a2 a3 a4 B2: biến đổi theo pth Ta có pth: f2: CD MSCD; a1 a2 b1 b2 a1 b3 b4 a4 a2 a3 a4 Dòng Q3 chứa toàn giá trị a nên phân rã C là một phân rã bảo toàn thông tin. 40  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 3. Phương pháp chuẩn hóa  Hai phương pháp chuẩn hóa một LĐCSDL: A. Phương pháp phân rã B. Phương pháp tổng hợp 41  Chương 3: Phương pháp chuẩn hóa LĐ CSDL 3. Phương pháp chuẩn hóa  Hai phương pháp chuẩn hóa một LĐCSDL: A. Phương pháp phân rã: ĐH CÔNG NGHỆ THÔNG TIN 42