Bài giảng chương 4: Chuẩn hóa dữ liệu

2Cơ sở dữ liệu  1.1. Chuẩn hoá  Trong một số trường hợp quan hệ có thể chứa các thông tin trùng lặp (dư thừa), nên việc cập nhật dữ liệu (thêm, sửa, huỷ) gây ra những dị thường.  Các quan hệ trên cần thiết phải biến đổi thành các dạng phù hợp hơn được gọi là chuẩn hoá. 1. Giới thiệu chung 3Cơ sở dữ liệu  1.2. Quan hệ được chuẩn hoá  Là quan hệ trong đó mỗi miền của một thuộc tính chỉ chứa những giá trị nguyên tố tức là không phân nhỏ được nữa  1.3. Quan hệ không chuẩn hoá Quan hệ có chứa các miền giá trị là không nguyên tố 1. Giới thiệu chung 4Cơ sở dữ liệu Mỗi quan hệ thuộc một trong các dạng Không chuẩn hoá Chuẩn 1 Chuẩn 2 Chuẩn 3 Chuẩn Boyce codd 5Cơ sở dữ liệu  Định nghĩa Quan hệ R ở dạng chuẩn 1 (1NF - First Normal Form) nếu mọi thuộc tính của R đều chứa các giá trị nguyên tố (atomic value), giá trị này không là một danh sách các giá trị hoặc các giá trị phức hợp (composite value).  Các thuộc tính của quan hệ R  Không là thuộc tính đa trị (multivalued attribute).  Không là thuộc tính phức hợp (composite attribute). 2. Dạng chuẩn 1 6Cơ sở dữ liệu  Cho lược đồ quan hệ: CHUYEN_MON(MaGV,MonGD) MonGD là chuỗi gồm môn học mà giáo viên có khả năng giảng dạy Xét thể hiện sau: CHUYEN_MON(MaGV,MonGD)  GV1, CTDL,CSDL,C  GV2, Pascal, VB, C MonGD không phải là thuộc tính nguyên tố. Ví dụ: 7Cơ sở dữ liệu 2. Dạng chuẩn 1 R Mãsv Họtên Mãlớp Tênlớp Điểmthi S1 Tiến L1 MT01 M1 9 S1 Tiến L1 MT01 M2 7 S1 Tiến L1 MT01 M3 8 S2 Trúc L1 MT01 M1 9 S2 Trúc L1 MT01 M2 8 S3 Hiền L2 MT02 M1 5 Quan hệ R không ở dạng chuẩn 1 vì thuộc tính Điểmthi là thuộc tính phức hợp. 8Cơ sở dữ liệu 2. Dạng chuẩn 1 R Mãsv Họtên Mãlớp Tênlớp Mônhọc Điểm S1 Tiến L1 MT01 M1 9 S1 Tiến L1 MT01 M2 7 S1 Tiến L1 MT01 M3 8 S2 Trúc L1 MT01 M1 9 S2 Trúc L1 MT01 M2 8 S3 Hiền L2 MT02 M1 5 Quan hệ R ở 1NF vì các thuộc tính của R không là thuộc tính đa trị, không là thuộc tính phức hợp. 9Cơ sở dữ liệu  Các bất thường của quan hệ ở 1NF  Thêm vào  Không thể thêm thông tin của sinh viên mới có mã là S4, tên là Thành, thuộc lớp có mã là L1 nếu sinh viên này chưa đăng ký học môn học nào cả.  Cập nhật  Sửa tên của sinh viên có tên là Tiến với tên mới là Thành sẽ phải sửa tất cả các hàng của sinh viên này.  Xóa bỏ  Xóa thông tin sinh viên S3 đăng ký môn học M1 sẽ làm mất thông tin của sinh viên này.  Nguyên nhân  Tồn tại thuộc tính không khóa phụ thuộc hàm riêng phần vào khóa. 2. Dạng chuẩn 1 10Cơ sở dữ liệu  Định nghĩa Quan hệ R ở dạng chuẩn 2 (2NF - Second Normal Form) nếu R ở dạng chuẩn 1 và mọi thuộc tính không khóa đều phụ thuộc hàm đầy đủ vào mọi khóa của R. 3. Dạng chuẩn 2 11Cơ sở dữ liệu 3. Dạng chuẩn 2 R Mãsv Họtên Mãlớp Tênlớp Mônhọc Điểm S1 Tiến L1 MT01 M1 9 S1 Tiến L1 MT01 M2 7 S1 Tiến L1 MT01 M3 8 S2 Trúc L1 MT01 M1 9 S2 Trúc L1 MT01 M2 8 S3 Hiền L2 MT02 M1 5 Các phụ thuộc hàm: Khóa của R: {Mãsv, Mônhọc} Mãsv  {Họtên, Mãlớp} Mãlớp  Tênlớp {Mãsv, Mônhọc}  Điểm Lược đồ quan hệ R không ở 2NF vì thuộc tính không khóa Họtên phụ thuộc hàm riêng phần vào khóa {Mãsv, Mônhọc}. 12Cơ sở dữ liệu 3. Dạng chuẩn 2 R1 Mãsv Họtên Mãlớp Tênlớp S1 Tiến L1 MT01 S2 Trúc L1 MT01 S3 Hiền L2 MT02 Mãsv Mônhọc Điểm S1 M1 9 S1 M2 7 S1 M3 8 S2 M1 9 S2 M2 8 S3 M1 5 R2 Khóa của R1: Mãsv Lược đồ quan hệ R1 và R2 đều ở 2NF vì các thuộc tính không khóa đều phụ thuộc hàm đầy đủ vào khóa. Khóa của R2: {Mãsv, Mônhọc} 13Cơ sở dữ liệu  Các bất thường của quan hệ ở 2NF  Thêm vào  Không thể thêm thông tin của lớp L3 có tên là MT03 nếu chưa có sinh viên nào học lớp này.  Cập nhật  Sửa tên của lớp có mã L1 với tên mới là MT_1 sẽ phải sửa tất cả các hàng của lớp này.  Xóa bỏ  Xóa thông tin của sinh viên có mã S3 sẽ làm mất thông tin của lớp L2.  Nguyên nhân  Tồn tại thuộc tính không khóa phụ thuộc bắc cầu vào khóa. 3. Dạng chuẩn 2 14Cơ sở dữ liệu  Định nghĩa Quan hệ R ở dạng chuẩn 3 (3NF- Third Normal Form) nếu R ở dạng chuẩn 1 và mọi thuộc tính không khóa đều không phụ thuộc bắc cầu vào một khóa của R. 4. Dạng chuẩn 3 15Cơ sở dữ liệu 4. Dạng chuẩn 3 R1 Mãsv Họtên Mãlớp Tênlớp S1 Tiến L1 MT01 S2 Trúc L1 MT01 S3 Hiền L2 MT02 Lược đồ quan hệ R1 không ở 3NF vì thuộc tính không khóa Tênlớp phụ thuộc bắc cầu vào khóa Mãsv. Mãsv  Mãlớp Mãlớp  Tênlớp Mãlớp /Mãsv Tênlớp  {Mãsv, Mãlớp} 16Cơ sở dữ liệu 4. Dạng chuẩn 3 R11 Mãlớp Tênlớp L1 MT01 L2 MT02 Mãsv Họtên Mãlớp S1 Tiến L1 S2 Trúc L1 S3 Hiền L2 R12 Khóa của R11: Mãlớp Khóa của R12: Mãsv Lược đồ quan hệ R11 và R12 đều ở 3NF vì các thuộc tính không khóa đều không phụ thuộc bắc cầu vào khóa. Tóm tắt 3 dạng chuẩn 1-3 NF Nhận biết Cách chuẩn hóa 1 Quan hệ ko có thuộc tính đa trị và quan hệ lặp Chuyển tất cả quan hệ lặp hoặc đa trị thành 1 quan hệ mới 2 Phụ thuộc 1 phần vào thuộc tính khóa Tách thuộc tính phụ thuộc 1 phần thành lược đồ mới, đảm bảo quan hệ với lược đồ liên quan 3 Phụ thuộc ẩn, tồn tại phụ thuộc hàm giữa các thuộc tính ko phải là khóa Tách các thuộc tính đó thành lược đồ mới Ví dụ: MaSV Hoten Mamon Tenmon Sodvht 1 Hoa M1 CSDL 5 2 Tuấn M1 CSDL 5 3 Lan M2 TTNT 6 4 Hương M2 TTNT 6 Ví dụ: MaSV Hoten Mamon 1 Hoa M1 2 Tuấn M1 3 Lan M2 4 Hương M2 1 Hoa M2 Mamon Tenmon Sodvht M1 CSDL 5 M2 TTNT 6 R1 R2 Ví dụ 2: MaSV Mamon Tenmon Diem 1 M1 CSDL 5 2 M1 CSDL 4 3 M2 TTNT 7 4 M2 TTNT 6 R3 Ví dụ 2: MaSV Mamon Diem 1 M1 5 2 M1 4 3 M2 7 4 M2 6 Mamon Tenmon M1 CSDL M2 TTNT R4 R5 5. Dạng chuẩn Boyce-Codd  5.1. Định nghĩa  Lược đồ quan hệ R với tập các phụ thuộc hàm F được gọi là ở dạng chuẩn Boyce-Codd nếu X A đúng trên R, với A là thuộc tính không thuộc X thì X là một khoá bao hàm.  Nhận xét:  (1) Ta phải xét mọi phụ thuộc hàm không tầm thường X  A của F+  (2) X là một khoá bao hàm (siêu khoá) nghĩa là X phải chứa một khoá nào đó của R 5. Dạng chuẩn Boyce-Codd  5.1. Định nghĩa  Lược đồ quan hệ R với tập các phụ thuộc hàm F được gọi là ở dạng chuẩn Boyce-Codd nếu X A đúng trên R, với A là thuộc tính không thuộc X là một khoá bao hàm.  5.2. Nhận xét:  (1) Ta phải xét mọi phụ thuộc hàm không tầm thường X  A của F+  (2) X là một khoá bao hàm (siêu khoá) nghĩa là X phải chứa một khoá nào đó của R 5. Dạng chuẩn Boyce-Codd  Ví dụ: Cho lược đồ R(CSZ) với các phụ thuộc hàm: CS Z và Z C Lược đồ R có 2 khoá là SC và SZ Các thuộc tính đều là thuộc tính khoá, do đó lược đồ đạt 3NF. 5. Dạng chuẩn Boyce-Codd  Ví dụ: Vì Z C đúng trong CSZ nhưng Z không phải là khoá của CSZ  Lược đồ quan hệ CSZ không có dạng BCNF Dạng chuẩn Boyce-Codd(tt)  Nếu một lược đồ quan hệ không thoả mãn điều kiện BCNF, thủ tục chuẩn hóa bao gồm: – Loại bỏ các thuộc tính khóa phụ thuộc hàm vào thuộc tính không khóa ra khỏi quan hệ – tách chúng thành một quan hệ riêng có khoá chính là thuộc tính không khóa gây ra phụ thuộc. Ví dụ trên: R (A1,A2,A3,A4,A5) Với các phụ thuộc hàm: – A1,A2  A3,A4,A5 – A4  A2  lược đồ được tách ra như sau: – R1( A4, A2) – R2(A1, A4, A3, A5) SV_MH_GV(MaSV, MONHOC, GIANGVIEN) Dạng chuẩn Boyce-Codd(tt) Phụ thuộc vào MONHOC Ví dụ Phụ thuộc vào cả 2 MaSV, MaDA 6. Ý nghĩa dạng chuẩn Mục đích của dạng chuẩn BCNF là loại bỏ dư thừa mà các phụ thuộc hàm có thể gây ra. 7. Thiết kế cơ sở dữ liệu  7.1. Phân rã một lược đồ quan hệ  Xét quan hệ SINHVIEN MaSV TenSV DiaChi MaLop TenLop 11 Lan X CNA1 Cu nhan A1 12 Hai Y CNA1 Cu nhan A1 13 Tu Z CNA2 Cu nhan A2 7.1. Phân rã một lược đồ quan hệ  Lược đồ vi phạm 3NF do phụ thuộc bắc cầu: MaSV MaLop TenLop 7.1. Phân rã một lược đồ quan hệ  Các phụ thuộc hàm:  - Biết MaSV xác định duy nhất tên, địa chỉ, mã lớp. MASV TENSV,Diachi,Malop  - Biết MaLop  TenLop  Khoá của lược đồ là {MaSV}  Lược đồ đạt 2NF Do khoá chỉ có một thuộc tính nên luôn thoả điều kiện: “phụ thuộc đầy đủ vào khoá” 7.1. Phân rã một lược đồ quan hệ  Phân rã (tách) lược đồ quan hệ SINHVIEN thành hai lược đồ SV và LOP MaSV TenSV DiaChi MaLop 11 Lan X CNA1 12 Hai Y CNA1 13 Tu Z CNA2 Malop Tenlop CNA1 Cu nhan A1 CNA2 Cu nhan A2 SV LOP 7.1. Phân rã một lược đồ quan hệ  Kết luận: Mục đích của phép phân rã là tạo ra một lược đồ cơ sở dữ liệu mới có dạng chuẩn cao hơn lược đồ cơ sở dữ liệu ban đầu. Phép phân rã đạt hai yêu cầu: + Có nối không mất (bảo toàn thông tin) + Bảo toàn phụ thuộc (bảo toàn phụ thuộc hàm) 7.2. Kiểm tra tính chất nối không mất Thuật toán:  Input: - Lược đồ quan hệ R=A1…An - Một tập phụ thuộc hàm F - Một phân rã  = {R1, … ,Rk} Output: Một khẳng định  có phải là một phân rã có nối không mất hay không. 7.2. Kiểm tra tính chất nối không mất Phương pháp: Bước 1: Có n thuộc tính và k lươc đồ con, xây dựng bảng gồm n cột, k hàng: – Cột j tương ứng với thuộc tính Aj – Hàng i ứng với lược đồ quan hệ Ri Ở vị trí hàng i cột j đặt ký hiệu: - aj nếu Aj thuộc Ri - bij nếu Aj không thuộc Ri 7.2. Kiểm tra tính chất nối không mất  Phương pháp:  Bước 2:  Xét lặp đi lặp lại mỗi phụ thuộc  - X Y trong F cho đến khi không còn thay đổi nào nữa trong bảng.  - Mỗi lần xét X Y tìm những hàng giống nhau trên X thay thế ký hiệu giống nhau trên Y  Kết luận  Nếu sau khi sửa đổi các hàng của bảng như trên thu được một hàng a1…an (chứa toàn a) thì phân rã có nối không mất 7.2. Kiểm tra tính chất nối không mất  Kết luận  Ngược lại đây không phải là phân rã có nối không mất. Ví dụ:  Lược đồ:  R={MASV, TENSV, DIACHI, MALP, TENLP}  Và F = {f1, f2} trong đó:  f1: MASV  TENSV, DIACHI, MALP  f2: MALP  TENLP  Phân rã  = {R1, R2}  R1={MASV, TENSV, DIACHI, MALP}  R2={MALP, TENLP} Kiểm tra xem phân rã có đặc tính có nối mất hay không?  Bước 1: R MASV TENSV DIACHI MALP TENLP R1 a1 a2 a3 a4 b15 R2 b21 b22 b23 a4 a5 f2: MALP  TENLP R MASV TENSV DIACHI MALP TENLP R1 a1 a2 a3 a4 a5 R2 b21 b22 b23 a4 a5 Bước 2 Ví dụ:  Kết luận:  Đây là một phân rã có nối không mất. Ví dụ 2:  Xét phân rã R = SAIP thành  R1=SA và R2=SIP  Các phụ thuộc hàm:  S  A, SI  P  Phân rã có nối không mất hay mất? R S A I P R1 a1 a2 b13 b14 R2 a1 b22 a3 a4 Vì S A là hai hàng giống nhau ở cột S suy ra giá trị cột A bằng nhau R S A I P R1 a1 a2 b13 b14 R2 a1 a2 a3 a4 Ví dụ 2:  Vì hàng 2 toàn a, đây là kết nối không mất Ví dụ 3:  Xét phân rã R = SAIP thành R1=SAP và R2=SI Các phụ thuộc hàm là: S  A, SI  P R S A I P R1 a1 a2 b13 a4 R2 a1 b22 a3 b24 Vì S A là hai hàng giống nhau ở cột S suy ra giá trị cột A bằng nhau R S A I P R1 a1 a2 b13 a4 R2 a1 a2 a3 b24 Quan hệ này cũng thoá SI P bởi vì giá trị các thuộc tính ở vế trái phụ thuộc hàm SI của hai bộ là khác nhau Ta thấy quan hệ này thoả mãn tất các các phụ thuộc hàm nhưng không có dòng nào gồm toàn a, nên đây không phải là phân rã có nối không mất. Ví dụ 4:  Cho R = ABCDE  R1=AD, R2=AB, R3=BE, R4=CDE, R5=AE  Các phụ thuộc hàm: A  C, B  C, C  D,  DE  C, CE  A 7.3. Phép tách lược đồ quan hệ thành BCNF Vào: Lược đồ quan hệ R và tập phụ thuộc hàm F Ra: Phép tách của R không mất mát thông tin cho mỗi lược đồ quan hệ trong phép tách đều ở BCNF đối với phép chiếu của F trên lược đồ đó. 7.3. Phép tách lược đồ quan hệ thành BCNF Phương pháp: Cấu trúc phép tách  trên R theo phương pháp lặp liên tiếp. Tại mỗi bước phép tách  là bảo đảm không mất mát thông tin đối với F. Bước đầu:  chỉ bao gồm R Các bước tiếp: Nếu S là một lược đồ thuộc , S chưa ở BCNF chọn X A là phụ thuộc hàm thoả mãn trên S Trong đó X không chứa khoá của S, A  X 7.3. Phép tách lược đồ quan hệ thành BCNF Thay thế S trong bởi S1 và S2: S1= XA, S2=S-A Quá trình tiếp tục cho tới khi tất cả các lược đồ đều ở BCNF Ví dụ: Cho lược đồ R(CTHRSG) Trong đó: C: Giáo trình T: Thầy giáo H: Giờ R: Phòng học S: Sinh viên G: Lớp Ví dụ: Tập phụ thuộc hàm F: C  T: Mỗi giáo trình chỉ có một thầy dạy HR  C: Chỉ có một môn học ở một phòng học tại một thời điểm HT  R: Tại mỗi thời điểm mỗi thầy giáo chỉ có thể dạy ở một phòng học CS  G: Mỗi sinh viên chỉ hoc ở một lớp theo học mỗi giáo trình HS  R: Mỗi sinh viên chỉ có thể ở một phòng học tại một thời điểm. Khoá của R là HS Ví dụ: Tách lược đồ R thành BCNF: Xét CS  G vi phạm điều kiện BCNF vì CS không chứa khoá. Do vậy tách R thành: R1(CSG), R2(CTHRS) R(CTHRSG) Khoá = HS R1(CSG) Khoá = cS R2(CTHRS) Khoá = SH R21(CT) Khoá = C R22(CHRS) Khoá = HS R221(CHR) Khoá = CH,HR R222(CHS) Khoá = SH C  T CS  G HR  C HS  R HT  R C  T HT  R HR  C HS  R CH R HS  R HR  C CH R HR  C HS C CS G C T 7.4. Phép tách lược đồ quan hệ thành 3NF Vào: Lược đồ quan hệ R và tập phụ thuộc hàm F Ra: Phép tách của R không mất mát thông tin cho mỗi lược đồ quan hệ trong phép tách đều ở 3NF với phép chiếu của F trên lược đồ đó. 7.4. Phép tách lược đồ quan hệ thành 3NF Phương pháp: 1) Loại bỏ tất cả các thuộc tính của R nếu thuộc tính đó không liên quan đến một phụ thuộc hàm nào của F 2) Nếu có một phụ thuộc hàm nào của F mà liên quan tới tất cả thuộc tính của R thì kết quả chính là R 3) Phép tách đưa các lược đồ quan gồm các thuộc tính XA cho phụ thuộc hàm X A thuộc F 7.4. Phép tách lược đồ quan hệ thành 3NF Phương pháp: 3) Nếu X A1, X  A2,…,X  An thay thế thuộc tính XA1A2…An cho Xai Quá trình tiếp tục 7.4. Phép tách lược đồ quan hệ thành 3NF Ví dụ: Cho lược đồ quan hệ R(CTHRSG) với tập phụ thuộc hàm: C T, HR  C, HT  R, CS  G, HS  R Dùng thuật toán trên tập lược đồ có dạng: R1(CT), R2(CHR), R3(HRT), R4(CGS), R5(HRS) 59Cơ sở dữ liệu  Định nghĩa 1 Cơ sở dữ liệu phân tán (distributed database) là sự tập hợp dữ liệu mà về mặt luận lý chúng thuộc cùng một hệ thống nhưng được đặt ở nhiều nơi (site) của một mạng máy tính.  Sự phân tán dữ liệu (data distribution): dữ liệu phải được phân tán ở nhiều nơi.  Sự tương quan luận lý (logical correlation): dữ liệu của các nơi được sử dụng chung để cùng giải quyết một vấn đề. 8. Cơ sở dữ liệu phân tán 60Cơ sở dữ liệu  Ví dụ  Một ngân hàng có ba chi nhánh ở các vị trí địa lý khác nhau.  Tại mỗi chi nhánh có một máy tính và một cơ sở dữ liệu tài khoản, tạo thành một nơi (site) của cơ sở dữ liệu phân tán.  Các máy tính được kết nối với nhau thông qua một mạng máy tính truyền thông.  Một khách hàng có thể gửi tiền và rút tiền tại các chi nhánh. Cơ sở dữ liệu phân tán 61Cơ sở dữ liệu Cơ sở dữ liệu phân tán Hình 1.1. Cơ sở dữ liệu phân tán trên một mạng phân tán địa lý. Máy tính 1 Terminal T T Máy tính 3 T T T Mạng truyền thông Cơ sở dữ liệu 1 Máy tính 2 T T T Cơ sở dữ liệu 2 Cơ sở dữ liệu 3 Chi nhánh 1 Chi nhánh 2 Chi nhánh 3 62Cơ sở dữ liệu Cơ sở dữ liệu phân tán Hình 1.2. Cơ sở dữ liệu phân tán trên một mạng cục bộ. Máy tính 1 Máy tính 2 Máy tính 3 Mạng cục bộ Trung tâm máy tính Chi nhánh 1 T T T Cơ sở dữ liệu 1 Cơ sở dữ liệu 2 Cơ sở dữ liệu 3 Chi nhánh 2 T T T Chi nhánh 3 T T T 63Cơ sở dữ liệu Cơ sở dữ liệu phân tán Hình 1.3. Hệ thống đa xử lý (multiprocessor system). Máy tính phía sau 1 Mạng cục bộ Máy tính ứng dụng (phía trước) Cơ sở dữ liệu 1 Cơ sở dữ liệu 2 Cơ sở dữ liệu 3 Trung tâm máy tính Máy tính phía sau 2 Máy tính phía sau 3 Chi nhánh 1 T T T Chi nhánh 2 T T T Chi nhánh 3 T T T 64Cơ sở dữ liệu  Định nghĩa 2 Cơ sở dữ liệu phân tán là sự tập hợp dữ liệu được phân tán trên các máy tính khác nhau của một mạng máy tính. Mỗi nơi của mạng máy tính có khả năng xử lý tự trị và có thể thực hiện các ứng dụng cục bộ. Mỗi nơi cũng tham gia thực hiện ít nhất một ứng dụng toàn cục, mà nơi này yêu cầu truy xuất dữ liệu ở nhiều nơi bằng cách dùng hệ thống truyền thông con. Cơ sở dữ liệu phân tán 65Cơ sở dữ liệu  Định nghĩa 2  Sự phân tán dữ liệu (data distribution): dữ liệu phải được phân tán ở nhiều nơi.  Ứng dụng cục bộ (local application): ứng dụng được chạy hoàn thành tại một nơi và chỉ sử dụng dữ liệu cục bộ của nơi này.  Ứng dụng toàn cục (hoặc ứng dụng phân tán) (global application / distributed application): ứng dụng được chạy hoàn thành và sử dụng dữ liệu của ít nhất hai nơi. Cơ sở dữ liệu phân tán