Bài giảng Lý thuyết cơ sở dữ liệu - Chương 5: Chuẩn hóa cơ sở dữ liệu (Data normalization)

Chia sẻ: Tần Mộc Phong | Ngày: | Loại File: PDF | Số trang:52

Thêm vào BST

Báo xấu

80
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Lý thuyết cơ sở dữ liệu - Chương 5: Chuẩn hóa cơ sở dữ liệu (Data normalization) cung cấp cho học viên những kiến thức về phép tách lược đồ quan hệ; phép tách - kết nối không mất mát thông tin; phụ thuộc hàm đầy đủ; phụ thuộc hàm bắc cầu; kiểm tra phép tách - kết nối không mất thông tin;... Mời các bạn cùng tham khảo chi tiết nội dung bài giảng!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Lý thuyết cơ sở dữ liệu - Chương 5: Chuẩn hóa cơ sở dữ liệu (Data normalization)

CHƯƠNG V: CHUẨN HÓA CSDL Data normalization
I. Một số khái niệm cơ bản ¡ Phép tách lược đồ quan hệ R= {A1, A2, .. An} là việc thay thế lược đồ quan hệ R bằng tập các lược đồ con {R1, R2, .., Rk}, trong đó Ri Ì R, i = 1,..,k - Ri là các lược đồ con (Ri gồm một số thuộc tính từ R) và R = R1 È R2 È ... È Rk Không đòi hỏi các Ri phải là phân biệt Mục đích: Loại bỏ các dị thường dữ liệu Cơ sở dữ liệu 3
Ví dụ MSKH TÊNKH TP PVC MSMH TÊNMH ĐG SL S1 An HCM 01 P1 Táo 650 300 S1 An HCM 01 P2 Cam 500 200 S1 An HCM 01 P3 Chanh 450 400 S2 Hòa HN 02 P1 Táo 650 100 S2 Hoà HN 02 P3 Chanh 450 300 S3 Thanh NT 03 P2 Cam 500 200 S4 Trang NT 03 P2 Cam 500 210 MSKH TÊNKH TP S1 An HCM MSKH MSMH SL S2 Hoà HN S1 P1 300 S3 Bình NT TP PVC S1 P2 200 S4 Trang NT HCM 01 S1 P3 400 HN 02 S2 P1 100 MSMH TÊNMH ĐG S2 P3 300 NT 03 P1 Táo 650 S3 P2 200 S4 P2 210 P2 Cam 500 P3 Chanh 450 Cơ sở dữ liệu 4
Phép tách-Kết nối không mất mát thông tin ¡ Nói rằng phép tách R thành các lược đồ con R1, R2, …, Rk là phép tách - kết nối không mất mát thông tin đối với F nếu với mỗi quan hệ r trên R thoả F thì r = PR1(r) * P R2 (r) * ... * P Rk(r) tức là r được tạo nên từ phép kết nối tự nhiên của các hình chiếu của nó trên các Ri, i= 1..,k Cơ sở dữ liệu 5
Phụ thuộc hàm đầy đủ ¡ Cho lược đồ quan hệ (U,F) và tập X, YÍU. ¡ PTH X ® Y được gọi là PTH đầy đủ nếu không tồn tại X’ là tập con thực sự của X mà X’ ® Y, tức là: - X®Y - "X’ Ì X thì X’ /® Y, mọi tập con thực sự của X đều không thể xác định hàm Y ¡ VD: F = { A ® BCD; BCD ® E; CD ® EI } BCD®E là một phụ thuộc hàm không đầy đủ vì CD® E A ® BCD và CD ® EI là phụ thuộc đầy đủ Cơ sở dữ liệu 6
Phụ thuộc hàm bắc cầu ¡ Cho lược đồ quan hệ a = (U,F), X Í U, A Î U ¡ Thuộc tính A được gọi là phụ thuộc hàm bắc cầu vào tập thuộc tính X nếu như $ Y Í U để: - X ® Y, Y ® A - Nhưng Y /à X với A Ï XY ¡ VD: R(ABCDE), F = {ABàCD, DàE}, khoá: AB. - Ta có: AB à E là pth bắc cầu vì: $D Ì R: AB à D DàE D /à AB E Ï ABD Cơ sở dữ liệu 7
II. Kiểm tra phép tách-kết nối không mất thông tin ¡ Input: - R = {A1, A2, .., An} – n thuộc tính và tập pth F - Phép tách p = (R1, R2, .., Rk) – k lược đồ con ¡ Output: Kiểm tra phép tách có mất mát thông tin hay không ? Cơ sở dữ liệu 8
Thuật toán Bước 1: Lập bảng với n+1 cột và k+1 hàng -Cột thứ j (j = 0 ® n ) ó thuộc tính thứ j của lược đồ (Aj) -Hàng thứ i ( i = 0® k)ó lược đồ Ri -Tại ô (i,j) điền kí hiệu aj nếu Aj Î Ri, ngược lại điền kí hiệu bij Bước 2: thay đổi giá trị cho bảng (Lặp liên tục) -Lần lượt xét các pth (X®Y) Î F -Nếu tồn tại hai hàng mà tất cả các cột ứng với thuộc tính X có giá trị bằng nhau thì thay đổi cho bằng nhau ở thuộc tính Y Nguyên tắc: nếu có một giá trị aj trong các cột tương ứng với các thuộc tính của Y thì thay thế hết thành aj, nếu không thay thế hết bằng ký hiệu bij -Lặp lại bước 2 (kể cả lặp lại các phụ thuộc hàm đã áp dụng) cho tới khi không làm thay đổi giá trị của bảng Bước 3: Đánh giá kết quả -Nếu xuất hiện một hàng gồm toàn kí hiệu a1, a2, .. , an thì phép tách-kết nối là không mất mát thông tin, -ngược lại là phép tách-kết nối mất mát thông tin. Cơ sở dữ liệu 9
BÀI TẬP ¡ Cho lược đồ quan hệ R(ABCDE) và tập phụ thuộc hàm: G1= {AB®D, C®B, CB®E, E®DC} Kiểm tra phép tách lược đồ thành các lược đồ con có mất thông tin không: R1(ABC), R2(CBE), R3(DE)
BÀI TẬP ¡ Cho lược đồ quan hệ HoaDon(MaHD, NgayLap, MaNV, TenNV, MaH, TenH, DG, SL) và F= { MaHD ® NgayLap; MaNV ® TenNV; MaH ® TenH; MaHD,MaH ® DG, SL} Kiểm tra phép tách lược đồ thành các lược đồ con có mất thông tin không: R1(MaNV, TenNV), R2(MaH,TenH), R3(MaHD, NgayLap, MaH, SL, DG)
III. Chuẩn hóa lược đồ quan hệ ¡ Chuẩn hóa là quá trình khảo sát danh sách các thuộc tính và áp dụng các quy tắc phân tích vào danh sách đó, biến đổi thành nhiều tập nhỏ hơn ó Tách bảng thành nhiều bảng nhỏ hơn ¡ Sao cho: - Tối thiểu việc lặp lại - Tránh dị thường thông tin - Xác định và giải quyết được sự không rõ ràng, nhập nhằng trong suy diễn Cơ sở dữ liệu 24
¡ Các loại dạng chuẩn gồm: - Dạng chuẩn 1 (1NF – First Normal Form) - Dạng chuẩn 2 (2NF – Second Normal Form) - Dạng chuẩn 3 (3NF) - Dạng chuẩn Boye Code (BCNF) BCNF 3NF 2NF 1NF Cơ sở dữ liệu 25
1. Dạng chuẩn 1NF ¡ Lược đồ quan hệ R được gọi là 1NF nếu và chỉ nếu tất cả các thuộc tính của R thoả mãn cả 3 điều kiện sau: - Tất cả các thuộc tính có kiểu xác định (nguyên tố) - Giá trị của các thuộc tính là đơn trị, - Không có một thuộc tính nào có giá trị tính toán từ 1 số thuộc tính khác ¡ Chú ý: khi xét dạng chuẩn nếu không nói gì thêm thì dạng chuẩn đang xét ít nhất là đạt dạng chuẩn một 1 ¡ Biểu diễn sơ đồ dạng 1NF: R(A1,A2,A3, A4, A5) 2 3 4 Cơ sở dữ liệu 26
2. Dạng chuẩn 2NF ¡ LĐQH R được gọi là đạt dạng chuẩn 2 nếu R đã ở dạng chuẩn 1 và tất cả các thuộc tính không khóa (thuộc tính không tham gia vào khóa) đều phụ thuộc hàm đầy đủ vào khóa. ¡ Mục đích: - Giản ước sự dư thừa dữ liệu - Tránh các dị thường cập nhật gây nên do sự dư thừa dữ liệu này 1 ¡ Biểu diễn sơ đồ dạng 2NF: R(A1,A2,A3, A4, A5) 4 3 Cơ sở dữ liệu 33
Thuật toán kiểm tra dạng chuẩn 2 ¡ Bước 1: Tìm tất cả các khóa của quan hệ ¡ Bước 2: Với mỗi khóa K, tìm bao đóng của tất cả các tập con thực sự S của K - Chú ý: nếu khóa có một thuộc tính đơn thì không cần phải kiểm tra và ở 2NF ¡ Bước 3: - nếu có bao đóng S+ chứa thuộc tính không khóa thì quan hệ không đạt chuẩn 2 - ngược lại thì quan hệ đạt chuẩn 2 (không tồn tại S mà S+ chứa thuộc tính không khóa) Cơ sở dữ liệu 36
Ví dụ: kiểm tra dạng 2NF của quan hệ ¡ QLSV (MaSV, Ten, NS, DC, TenLop, KhoaHoc, MaMH, TenMH, Diem) F={ f1: MaSV à Ten, NS, DC, TenLop f2: TenLop à KhoaHoc; f3: MaMH à TenMH; f4: MaSV, MaMH à Diem } Cơ sở dữ liệu 37
Thuật toán đưa về dạng 2NF ¡ Nhóm các thuộc tính phụ thuộc vào một phần của khoá và thuộc tính một phần tách thành quan hệ mới, lấy phần đó làm khoá chính cho quan hệ. ¡ Giữ các thuộc tính phụ thuộc hoàn toàn vào khoá và giữ lại khoá của quan hệ đó R(A1,A2,A3, A4, A5) R1(A2, A4) R(A1,A2,A3, A5) Cơ sở dữ liệu 41
¡ Ví dụ 3: - Cho R2 (SoHD, MaSP, TenSP, SoLuong) Và F = { MaSP à TenSP } - Hỏi quan hệ có ở dạng 2NF không? Nếu chưa tách thành lược đồ ở dạng 2NF Cơ sở dữ liệu 43
3. Dạng chuẩn 3NF ¡ Lược đồ R ở 3NF nếu: - Ở dạng 2NF - Mọi thuộc tính không khóa đều không phụ thuộc bắc cầu vào bất kỳ khóa chính của quan hệ ¡ Hoặc Xét mọi pth X à A thì - Hoặc X là một siêu khóa của R - Hoặc A là một thuộc tính khóa của R 1 ¡ Sơ đồ: R(A1,A2,A3, A4, A5) 4 Cơ sở dữ liệu 47
Thuật toán kiểm tra dạng chuẩn 3 ¡ Output: kết luận Q đạt chuẩn 3 hay không đạt chuẩn 3 ¡ Thuật toán: - Bước 1: tìm tất cả khóa của Q - Bước 2: từ F tạo tập phụ thuộc hàm tương đương F’ có vế phải một thuộc tính - Bước 3: Kiểm tra Nếu mọi phụ thuộc hàm XàA Î F’ với AÏX đều có X là khóa hoặc A là thuộc tính khóa thì Q đạt chuẩn 3 ngược lại Q không đạt chuẩn 3 ($ X → A mà X không là khóa và A không là thuộc tính khóa) Cơ sở dữ liệu 50