Cơ sở dữ liệu - Chương 6 - ThS. Nguyễn Vương Thịnh
Chia sẻ bởi Nguyễn Vương Thịnh |
Ngày 19/03/2024 |
10
Chia sẻ tài liệu: Cơ sở dữ liệu - Chương 6 - ThS. Nguyễn Vương Thịnh thuộc Công nghệ thông tin
Nội dung tài liệu:
TRƯỜNG ĐẠI HỌC HÀNG HẢI VIỆT NAM
KHOA CÔNG NGHỆ THÔNG TIN
BÀI GIẢNG HỌC PHẦN
CƠ SỞ DỮ LIỆU VÀ QUẢN TRỊ CƠ SỞ DỮ LIỆU
Giảng viên: ThS. Nguyễn Vương Thịnh
Bộ môn: Hệ thống thông tin
Hải Phòng, 2016
Chương 6
CHUẨN HÓA CƠ SỞ DỮ LIỆU
2
Thông tin về giảng viên
3
Thông tin về học phần
PHƯƠNG PHÁP HỌC TẬP, NGHIÊN CỨU
Nghe giảng, thảo luận, trao đổi với giảng viên trên lớp.
Tự nghiên cứu tài liệu và làm bài tập ở nhà.
PHƯƠNG PHÁP ĐÁNH GIÁ
SV phải tham dự ít nhất 75% thời gian.
Có 02 bài kiểm tra viết giữa học phần (X2 = (L1 + L2)/2), 01 bài kiểm tra thực hành (X3). Điểm quá trình X = (X2 + X3)/2.
Thi kết thúc học phần bằng hình thức trắc nghiệm khách quan trên máy tính (Z = 0.5X + 0.5Y).
4
Tài liệu tham khảo
Elmasri, Navathe, Somayajulu, Gupta, Fundamentals of Database Systems (the 4th Edition), Pearson Education Inc, 2004.
Nguyễn Tuệ, Giáo trình Nhập môn Hệ Cơ sở dữ liệu, Nhà xuất bản Giáo dục Việt Nam, 2007.
Nguyễn Kim Anh, Nguyên lý của các hệ Cơ sở dữ liệu, Nhà xuất bản Đại học Quốc gia Hà Nội, 2004.
5
Tài liệu tham khảo
CHUẨN HÓA CƠ SỞ DỮ LIỆU
6.1. TẠI SAO PHẢI CHUẨN HÓA CƠ SỞ DỮ LIỆU?
6.2. CÁC DẠNG CHUẨN HÓA CỦA CƠ SỞ DỮ LIỆU
6.3. CÁC PHÉP TÁCH BẢO TOÀN THÔNG TIN VÀ BẢO TOÀN PHỤ THUỘC HÀM
6.4. PHÉP TÁCH VỀ DẠNG CHUẨN BOYCE CODD (BCNF) BẢO TOÀN THÔNG TIN
6.5. PHÉP TÁCH VỀ DẠNG CHUẨN 3 (3NF) BẢO TOÀN THÔNG TIN VÀ BẢO TOÀN PHỤ THUỘC HÀM
6
7
6.1. TẠI SAO PHẢI CHUẤN HÓA CƠ SỞ DỮ LIỆU?
Ví dụ 6.1: Xét quan hệ trên lược đồ quan hệ
Kết_Quả_Học_Phần(Mã SV, Họ và tên, Mã HP, Tên HP, Điểm)
NHƯỢC ĐIỂM
1. Dư thừa dữ liệu: Cùng 01 sinh viên nhưng không chỉ có mã sinh viên mà họ tên sinh viên cũng bị lặp đi lặp lại nhiều lần ở các vị trí khác nhau. Tương tự, cùng một học phần thì không chỉ có mã học phần mà tên học phần cũng bị lặp lại ở những vị trí khác nhau.
8
2. Khó khăn khi cập nhật dữ liệu:
Thêm: Ta không thể thêm tên một học phần mới vào quan hệ nếu học phần đó chưa được sinh viên nào đăng ký. Tương tự ta không thể thêm thông tin về một sinh viên mới nếu sinh viên đó chưa đăng ký một học phần nào.
Xóa: Nếu ta xóa thông tin về học phần "Toán rời rạc" thì cũng sẽ mất luôn thông tin của sinh viên "Nguyễn Văn Bình" có mã sinh viên là "HHA003" vì chỉ có một bản ghi duy nhất có chứa thông tin về sinh viên này.
Sửa: Giả sử có nhiều sinh viên đăng ký học môn "Toán rời rạc", khi đó sẽ có nhiều bản ghi có liên quan đến "Toán rời rạc". Nếu ta muốn đổi tên môn "Toán rời rạc" thành "Toán tin" thì ta sẽ phải cập nhật tên môn ở nhiều vị trí tương ứng, gây mất nhiều thời gian và dễ xảy ra sai sót.
3. Không nhất quán dữ liệu: Là hệ quả của 02 điều trên.
9
6.2. CÁC DẠNG CHUẨN HÓA CƠ SỞ DỮ LIỆU
6.2.1. DẠNG CHUẨN 1 (1NF)
Một lược đồ quan hệ R(Ω) được gọi là ở dạng chuẩn 1 (1NF) nếu như toàn bộ các thuộc tính đều mang giá trị đơn và nguyên tố.
Ví dụ 6.2: Các lược đồ quan hệ sau đây không thỏa mãn chuẩn 1:
10
6.2.2. DẠNG CHUẨN 2 (2NF)
Một lược đồ quan hệ R(Ω) được gọi là ở dạng chuẩn 2 (2NF) nếu nó ở dạng chuẩn 1 và mỗi thuộc tính không khóa (nếu có) đều phải phụ thuộc hàm đầy đủ vào một khóa nào đó của lược đồ quan hệ.
Lưu ý một số khái niệm:
Thuộc tính không khóa (nonprime attribute) là thuộc tính không nằm trong bất kỳ một khóa nào của lược đồ quan hệ.
Y được gọi là phụ thuộc hàm đầy đủ vào X nếu X → Y và không tồn tại X’⊆ X sao cho X’→Y (nói cách khác: phụ thuộc hàm đầy đủ có nghĩa là Y chỉ phụ thuộc hàm vào X chứ không phụ thuộc vào một tập con nào đó của X).
Ví dụ 6.2: Xét lược đồ quan hệ
Kết Quả Học Phần(Mã SV, Họ và tên, Mã HP, Tên HP, Điểm)
Có tập phụ thuộc hàm:
F = {Mã SV → Họ và tên, Mã HP → Tên HP, {Mã SV, Mã HP} → Điểm}
Khóa K = {Mã SV, Mã HP}
Họ và tên phụ thuộc hàm vào Mã SV là 1 phần của khóa
Tên HP phụ thuộc hàm vào Mã HP là 1 phần của khóa
KHÔNG THỎA MÃN CHUẨN 2
11
Hệ quả:
Nếu một lược đồ quan hệ đạt chuẩn 1 và tập thuộc tính không khóa của nó là tập rỗng thì đương nhiên lược đồ quan hệ đó đạt chuẩn 2.
Nếu tất cả các khóa của lược đồ quan hệ chỉ gồm một thuộc tính thì lược đồ quan hệ đó đạt chuẩn 2.
THUẬT TOÁN KIỂM TRA MỘT LƯỢC ĐỒ QUAN HỆ CÓ ĐẠT CHUẨN 2
Input: Lược đồ quan hệ R(Ω) và tập phụ thuộc hàm F
Output: Khẳng định R(Ω) có đạt chuẩn 2 hay không.
Bước 1: Tìm tất cả các khóa của lược đồ quan hệ và xác định các thuộc tính không khóa.
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ật sự S của K.
Bước 3: Nếu tồn tại một bao đóng S+ nào đó chứa thuộc tính không khóa thì R(Ω) không đạt chuẩn 2. Ngược lại thì đạt chuẩn 2.
Lưu ý: Đối với những bài toán đơn giản, người ta thường xuất phát từ định nghĩa của dạng chuẩn 2 để xác định xem một lược đồ quan hệ có thỏa mãn dạng chuẩn 2 hay không thay vì phải sử dụng thuật toán nêu trên.
12
Ví dụ 6.3:
Cho lược đồ quan hệ R(A,B,C,D) và tập phụ thuộc hàm:
F = {AB → C, B → D, BC → A}
Hỏi lược đồ quan hệ này có đạt chuẩn 2 hay không?
Giải
Đầu tiên ta tìm tất cả các khóa của lược đồ quan hệ:
TN = B, TG = AC
Ta có hai khóa K1 = AB, K2 = BC. Thuộc tính không khóa là D. Ta thấy B→D trong khi B ⊂ K1. Vậy thuộc tính không khóa D phụ thuộc hàm vào một phần của khóa nên lược đồ quan hệ không thỏa mãn chuẩn 2.
13
Ví dụ 6.4: Cho lược đồ quan hệ R(A,B,C,D) và tập phụ thuộc hàm
F = {B → D, A → C, C → ABD}.
Hỏi lược đồ quan hệ này có đạt chuẩn 2 hay không?
Giải
Đầu tiên ta tìm tất cả các khóa của lược đồ quan hệ:
TN =⍉ , TG = ABC
Ta có hai khóa K1 = A, K2 = C. Tất cả các khóa của lược đồ quan hệ đều có một thuộc tính nên theo hệ quả 2, lược đồ quan hệ đạt chuẩn 2.
14
6.2.3. DẠNG CHUẨN 3 (3NF)
A. Định nghĩa cổ điển
Một lược đồ quan hệ R(Ω) được gọi là ở dạng chuẩn 3 (3NF) nếu nó đã ở dạng chuẩn 2 và không tồn tại thuộc tính không khóa phụ thuộc hàm bắc cầu vào khóa chính của lược đồ quan hệ.
Lưu ý: Một 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 tồn tại tập thuộc tính Y để cả ba điều sau được thỏa mãn:
X → Y, Y → A
Y → X ∉ F+
A ∉ XY
B. Định nghĩa tổng quát
Một lược đồ quan hệ R(Ω) được gọi là ở dạng chuẩn 3 (3NF) nếu với mọi phụ thuộc hàm X→A ∈ F+ (A ∉ X) ta đều có:
Hoặc X là siêu khóa.
Hoặc A là thuộc tính khóa.
15
Ví dụ 6.5: Xét lược đồ quan hệ:
SinhVien(MaSV, HoTen, MaLop, TenLop)
Tập phụ thuộc hàm: F = {MaLop → TenLop; MaSV → HoTen, MaLop}
Khóa chính K = {MaSV}
Lược đồ này không thỏa mãn chuẩn 3 vì có thuộc tính không khóa là TenLop phụ thuộc hàm bắc cầu vào khóa chính MaSV như sau:
MaSV → MaLop và MaLop → TenLop.
16
Hệ quả:
Nếu một lược đồ quan hệ đạt chuẩn 3 thì đương nhiên đạt chuẩn 2.
Nếu một lược đồ quan hệ không có thuộc tính không khóa thì đạt chuẩn 3.
THUẬT TOÁN KIỂM TRA MỘT LƯỢC ĐỒ QUAN HỆ CÓ ĐẠT CHUẨN 3
Input: Lược đồ quan hệ R(Ω) và tập phụ thuộc hàm F.
Output: Khẳng định R(Ω) có đạt chuẩn 2 hay không.
Bước 1: Tìm tất cả các khóa của lược đồ quan hệ R(Ω).
Bước 2: Từ tập phụ thuộc hàm F, tạo ra tập phụ thuộc hàm F’ tương đương với F và có vế phải chỉ có một thuộc tính (nhờ sử dụng luật phân rã).
Bước 3: Nếu mọi phụ thuộc hàm X→A ∈ F’ với A ∉ X đều có X là siêu khóa hoặc A là thuộc tính khóa thì lược đồ quan hệ đạt chuẩn 3. Ngược lại thì lược đồ quan hệ không đạt chuẩn 3.
17
Ví dụ 6.6: Cho lược đồ quan hệ R(A,B,C,D) và tập phụ thuộc hàm:
F = {AB → C, D → B, C → ABD}
Hỏi lược đồ quan hệ này có đạt chuẩn 3 hay không?
Giải
Bước 1: Sau khi áp dụng thuật toán tìm tất cả các khóa, ta tìm được 3 khóa: K1 = AB, K2 = AD, K3 = C. Như vậy, các thuộc tính khóa là: A, B, C, D.
Bước 2: Xây dựng tập phụ thuộc hàm F’ tương đương với F có vế phải một thuộc tính nhờ luật phân rã:
F’ = {AB → C, D → B, C → A, C → B, C → D}
Bước 3: Duyệt các phụ thuộc hàm trong F’, ta thấy tất cả các phụ thuộc hàm đều có vế phải là thuộc tính khóa nên lược đồ quan hệ đạt chuẩn 3.
18
Ví dụ 6.7: Cho lược đồ quan hệ R(A,B,C,D) và tập phụ thuộc hàm:
F = {B → D, A → C, C → ABD}
Hỏi lược đồ quan hệ này có đạt chuẩn 3 hay không?
Giải
Bước 1: Sau khi áp dụng thuật toán tìm tất cả các khóa, ta tìm được 2 khóa: K1 = A và K2 = C. Các thuộc tính khóa là: A, C.
Bước 2: Xây dựng tập phụ thuộc hàm F’ tương đương với F có vế phải một thuộc tính nhờ luật phân rã:
F’ = {B → D, A → C, C → A, C → B, C → D}
Bước 3: Duyệt các phụ thuộc hàm trong F’ ta thấy phụ thuộc hàm B → D có vế trái không phải là siêu khóa, vế phải cũng không phải là thuộc tính khóa. Vậy lược đồ quan hệ không đạt chuẩn 3.
19
6.2.4. DẠNG CHUẨN BOYCE CODD (BCNF)
Một lược đồ quan hệ R(Ω) được gọi là ở dạng chuẩn Boyce Codd (BCNF) nếu với mọi phụ thuộc hàm X → A ∈ F+ (A ∉ X) ta đều có X là siêu khóa.
Gần giống định nghĩa tổng quát của chuẩn 3, nhưng chặt chẽ hơn ở chỗ không chấp nhận trường hợp A là thuộc tính khóa.
Hệ quả: Nếu một lược đồ quan hệ đạt chuẩn Boyce Codd thì đương nhiên đạt chuẩn 3.
20
THUẬT TOÁN KIỂM TRA MỘT LƯỢC ĐỒ QUAN HỆ CÓ ĐẠT CHUẨN BOYCE CODD
Input: Lược đồ quan hệ R(Ω) và tập phụ thuộc hàm F.
Output: Khẳng định R(Ω) có đạt chuẩn Boyce Codd hay không.
Bước 1: Tìm tất cả các khóa của lược đồ quan hệ R(Ω).
Bước 2: Từ tập phụ thuộc hàm F, tạo ra tập phụ thuộc hàm F’ tương đương với F và có vế phải chỉ có một thuộc tính (nhờ sử dụng luật phân rã).
Bước 3: Nếu mọi phụ thuộc hàm X→A ∈ F’ với A ∉ X đều có X là siêu khóa thì lược đồ quan hệ đạt chuẩn Boyce Codd. Ngược lại thì lược đồ quan hệ không đạt chuẩn Boyce Codd.
21
Ví dụ 6.8: Cho lược đồ quan hệ R(A,B,C,D,E,I) và tập phụ thuộc hàm F = {ACD → EBI, CE → AD}. Hỏi lược đồ quan hệ này có đạt chuẩn Boyce Codd hay không?
Giải
Bước 1: Sau khi áp dụng thuật toán tìm tất cả các khóa, tìm được 2 khóa: K1 = ACD, K2 = CE.
Bước 2: Xây dựng tập phụ thuộc hàm tương đương F’ có vế phải một thuộc tính nhờ luật phân rã:
F’ = {ACD → E, ACD → B, ACD → I, CE → A, CE → D}
Bước 3: Duyệt các phụ thuộc hàm trong F’ ta thấy các phụ thuộc hàm đều có vế trái là khóa ACD hoặc CE nên đương nhiên lược đồ quan hệ thỏa mãn chuẩn Boyce Codd.
22
6.2.5. XÁC ĐỊNH DẠNG CHUẨN CAO NHẤT CỦA LƯỢC ĐỒ QUAN HỆ
Một lược đồ quan hệ đã đạt dạng chuẩn nào thì đương nhiên cũng thỏa mãn các dạng chuẩn thấp hơn.
23
THUẬT TOÁN XÁC ĐỊNH DẠNG CHUẨN CAO NHẤT CỦA LƯỢC ĐỒ QUAN HỆ
Input: Lược đồ quan hệ R(Ω) và tập phụ thuộc hàm F.
Output: Dạng chuẩn cao nhất của lược đồ quan hệ R(Ω).
Bước 1: Tìm tất cả các khóa của R(Ω).
Bước 2: Kiểm tra xem R(Ω) có đạt chuẩn Boyce Codd không. Nếu R(Ω) có đạt chuẩn Boyce Codd thì kết luận chuẩn Boyce Codd là dạng chuẩn cao nhất của lược đồ quan hệ và kết thúc thuật toán. Ngược lại nếu không đạt chuẩn Boyce Codd thì chuyển qua bước 3.
Bước 3: Kiểm tra xem R(Ω) có đạt chuẩn 3 không. Nếu R(Ω) có đạt chuẩn 3 thì kết luận chuẩn 3 là dạng chuẩn cao nhất của lược đồ quan hệ và kết thúc thuật toán. Ngược lại nếu không đạt chuẩn 3 thì chuyển qua bước 4.
Bước 4: Kiểm tra xem R(Ω) có đạt chuẩn 2 không. Nếu R(Ω) có đạt chuẩn 2 thì kết luận chuẩn 2 là dạng chuẩn cao nhất của lược đồ quan hệ và kết thúc thuật toán. Ngược lại thì kết luận R(Ω) đạt chuẩn 1.
Để xác định dạng chuẩn cao nhất của lược đồ quan hệ người ta sẽ kiểm tra lần lượt từ chuẩn Boyce Codd đến các dạng chuẩn thấp hơn.
24
6.3. CÁC PHÉP TÁCH BẢO TOÀN THÔNG TIN VÀ
BẢO TOÀN TẬP PHỤ THUỘC HÀM
Đảm bảo việc khôi phục nguyên vẹn quan hệ gốc ban đầu từ các quan hệ con sau khi tách, không phát sinh các bộ phụ thêm.
DanhSachHocSinh(MaHS, HoTen, DiemThi, MaLop, TenLop, PhongHoc)
HocSinh(MaHS, HoTen, DiemThi, MaLop)
Lop(MaLop, TenLop, PhongHoc)
26
B. Thuật toán kiểm tra một phép tách có bảo toàn thông tin
Input: Lược đồ quan hệ R(Ω) với Ω = {A1, A2,..., An} và tập phụ thuộc hàm F.
Phép tách R(Ω) thành m lược đồ con R1(Ω1), R2(Ω2), ... , Rm(Ωm)
Output: Khẳng định phép tách có bảo toàn thông tin hay không.
Bước 1: Tạo một ma trận S có m hàng và n cột. Mỗi cột tương ứng với một thuộc tính Aj trong Ω và mỗi hàng tương ứng với một lược đồ quan hệ con Ri(Ωi) .
Bước 2: Đặt phần tử S(i, j) của ma trận nhận giá trị bằng 1 nếu Aj∈ Ωi và ngược lại, S(i, j) nhận giá trị bằng 0 nếu Aj ∉ Ωi
Bước 3: Lặp lại thao tác sau đây cho tới khi nào không còn sự thay đổi trong ma trận S: Với mỗi phụ thuộc hàm X → Y trong F, xác định các hàng trong S có chứa các giá trị 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 giá trị 1 trong các cột ứng với tập thuộc tính Y thì làm cho các cột tương ứng của các hàng khác cũng chứa giá trị 1.
Bước 4: Nếu tồn tại 01 hàng có chứa toàn giá trị 1 thì phép tách là bảo toàn thông tin, ngược lại là không bảo toàn.
Ví dụ 6.9: Cho lược đồ quan hệ
PhanCong(MaNV, TenNV, ChuyenMon, MaDA, TenDA, DiaDiem, NgayBD, NgayKT)
Và tập phụ thuộc hàm:
F = { MaNV → TenNV, ChuyenMon;
MaDA → TenDA, DiaDiem;
MaNV, MaDA → NgayBD, NgayKT }
Người ta tách lược đồ quan hệ PhanCong thành các lược đồ con sau đây:
NhanVien(MaNV, TenNV, ChuyenMon)
DuAn(MaDA, TenDA, DiaDiem)
PhanCongNV(MaNV, MaDA, NgayBD, NgayKT)
Hỏi phép tách trên có bảo toàn thông tin không?
Giải
28
6.3.2. PHÉP TÁCH BẢO TOÀN TẬP PHỤ THUỘC HÀM
29
6.4. PHÉP TÁCH VỀ DẠNG CHUẨN BOYCE CODD BẢO TOÀN THÔNG TIN
Thuật toán tách
Input: Lược đồ quan hệ gốc R(Ω) và tập phụ thuộc hàm F.
Output: Tập D gồm các lược đồ quan hệ con R1(Ω1), R2(Ω2), ... , Rm(Ωm) thỏa mãn BCNF và bảo toàn thông tin
Bước 1: Khởi tạo D = {R(Ω)}
Bước 2: Lặp lại thao tác sau đây: Với mỗi lược đồ quan hệ Ri(Ωi) trong D không ở BCNF, tìm một phụ thuộc hàm X → Y vi phạm định nghĩa BCNF và thay thế Ri(Ωi) bằng 02 lược đồ quan hệ Si(ΩiY) và Ti(X∪Y). Quá trình lặp dừng khi không còn lược đồ quan hệ nào trong D không thỏa mãn BCNF.
30
Ví dụ 6.10: Xét lược đồ quan hệ R(A,B,C,D,E,F) và tập phụ thuộc hàm:
F = {A → BCDEF, BC → ADEF, B → F, D → E, D → B}
Hãy tách lược đồ trên thành các lược đồ con thỏa mãn BCNF và bảo toàn thông tin.
Giải
R(A,B,C,D,E,F)
F = {A → BCDEF, BC → ADEF, B → F, D → E, D → B}
K1 = A, K2 = BC
R1(B,F)
F1 = {B → F}
K = B
R2(A,B,C,D,E)
F2 = {A → BCDE, BC → ADE, D → E, D → B}
K1 = A, K2 = BC
R21(D,E)
F21 = {D → E}
K = D
R22(A,B,C,D)
F22 = {A → BCD, BC → AD, D → B}
K1 = A, K2 = BC
R222(A,C,D)
F222 = {A → CD}
K = A
R221(D,B)
F221 = {D → B}
K = D
D = {R1(B,F), R21(D,E), R221(D,B), R222(A,C,D)}
31
Ví dụ 6.11: Xét lược đồ quan hệ
PhanCong(MaNV, TenNV, ChuyenMon, MaDA, TenDA, DiaDiem, NgayBD, NgayKT)
và tập phụ thuộc hàm:
F = { MaNV → TenNV, ChuyenMon;
MaDA → TenDA, DiaDiem;
MaNV, MaDA → NgayBD, NgayKT }
Hãy tách lược đồ trên thành các lược đồ con thỏa mãn BCNF và bảo toàn thông tin.
Giải
PhanCong(MaNV, TenNV, ChuyenMon, MaDA, TenDA, DiaDiem, NgayBD, NgayKT)
F = {MaNV → TenNV, ChuyenMon; MaDA → TenDA, DiaDiem; MaNV, MaDA → NgayBD, NgayKT}
K = {MaNV, MaDA}
NhanVien(MaNV,TenNV, ChuyenMon)
F1 = {MaNV → TenNV, ChuyenMon}
K = MaNV
PhanCong1(MaNV, MaDA, TenDA, DiaDiem, NgayBD, NgayKT)
F2 = {MaDA → TenDA, DiaDiem; MaNV, MaDA → NgayBD, NgayKT}
K = {MaNV, MaDA}
DuAn(MaDA, TenDA, DiaDiem)
F3 = {MaDA → TenDA}
K = MaDA
PhanCongNV(MaNV, MaDA, NgayBD, NgayKT)
F4 = {MaNV, MaDA → NgayBD, NgayKT}
K = {MaNV, MaDA}
D = {NhanVien, DuAn, PhanCongNV}
32
6.5. PHÉP TÁCH VỀ DẠNG CHUẨN 3 BẢO TOÀN THÔNG TIN VÀ BẢO TOÀN PHỤ THUỘC HÀM
Thuật toán tách
Input: Lược đồ quan hệ gốc R(Ω) và tập phụ thuộc hàm F.
Output: Tập D gồm các lược đồ quan hệ con R1(Ω1), R2(Ω2), ... , Rm(Ωm) thỏa mãn chuẩn 3, bảo toàn thông tin và bảo toàn phụ thuộc hàm.
Bước 1: Tìm phủ tối thiểu G của F (nếu F chưa phải là tập PTH tối thiểu).
Bước 2: Với mỗi phụ thuộc hàm X → A trong G ta tạo ra một lược đồ quan hệ con S(X∪{A}) trong D. Nếu có nhiều phụ thuộc hàm có chung vế trái: X→A1, X→A2,..., X→Ak thì thay vì phải tạo lược đồ quan hệ con ứng với từng phụ thuộc hàm riêng lẻ, ta tạo ra một lược đồ quan hệ con chung S(X∪{A1}∪{A2}∪...∪{Ak})
Lưu ý: X là khóa chính của các lược đồ quan hệ con này.
Bước 3: Nếu không có lược đồ quan hệ con nào trong D chứa một khóa của R thì tạo thêm một lược đồ quan hệ con trong D có các thuộc tính là thuộc tính khóa cấu thành một khóa nào đó của R.
33
Ví dụ 6.12: Xét lược đồ quan hệ
PhanCong(MaGV, TenGV, MaPhong, DiaDiem, MaMon, TenMon)
và tập phụ thuộc hàm:
F = {MaGV → TenGV; MaPhong → DiaDiem; MaMon → TenMon }
Hãy tách lược đồ trên thành các lược đồ con thỏa mãn 3NF, bảo toàn thông tin và bảo toàn tập phụ thuộc hàm.
Giải
1. Bản thân tập F đã là tập phụ thuộc hàm tối thiểu rồi nên ta không cần tìm phủ tối thiểu G của F nữa.
2. Khóa của lược đồ quan hệ là K = {MaGV, SoPhong, MaMon}
3. Áp dụng thuật toán, ta lần lượt tạo ra các lược đồ quan hệ R(XA) tương ứng với các phụ thuộc hàm X → A:
GiangVien(MaGV, TenGV) có F = {MaGV → TenGV} và K = MaGV
PhongHoc(MaPhong, DiaDiem) có F = {MaPhong → DiaDiem} và K = MaPhong
MonHoc(MaMon, TenMon) có F = {MaMon → TenMon} và K = MaMon
4. Trong các lược đồ quan hệ con đã tạo không có lược đồ nào có chứa khóa của lược đồ quan hệ gốc nên ta tạo ra một lược đồ quan hệ nữa chứa toàn các thuộc tính của khóa: PhanCongGiangDay(MaGV, MaPhong, MaMon) có K = Ω
Kết quả của phép tách là:
D = {GiangVien, PhongHoc, MonHoc, PhanCongGiangDay}
34
Q & A
35
KHOA CÔNG NGHỆ THÔNG TIN
BÀI GIẢNG HỌC PHẦN
CƠ SỞ DỮ LIỆU VÀ QUẢN TRỊ CƠ SỞ DỮ LIỆU
Giảng viên: ThS. Nguyễn Vương Thịnh
Bộ môn: Hệ thống thông tin
Hải Phòng, 2016
Chương 6
CHUẨN HÓA CƠ SỞ DỮ LIỆU
2
Thông tin về giảng viên
3
Thông tin về học phần
PHƯƠNG PHÁP HỌC TẬP, NGHIÊN CỨU
Nghe giảng, thảo luận, trao đổi với giảng viên trên lớp.
Tự nghiên cứu tài liệu và làm bài tập ở nhà.
PHƯƠNG PHÁP ĐÁNH GIÁ
SV phải tham dự ít nhất 75% thời gian.
Có 02 bài kiểm tra viết giữa học phần (X2 = (L1 + L2)/2), 01 bài kiểm tra thực hành (X3). Điểm quá trình X = (X2 + X3)/2.
Thi kết thúc học phần bằng hình thức trắc nghiệm khách quan trên máy tính (Z = 0.5X + 0.5Y).
4
Tài liệu tham khảo
Elmasri, Navathe, Somayajulu, Gupta, Fundamentals of Database Systems (the 4th Edition), Pearson Education Inc, 2004.
Nguyễn Tuệ, Giáo trình Nhập môn Hệ Cơ sở dữ liệu, Nhà xuất bản Giáo dục Việt Nam, 2007.
Nguyễn Kim Anh, Nguyên lý của các hệ Cơ sở dữ liệu, Nhà xuất bản Đại học Quốc gia Hà Nội, 2004.
5
Tài liệu tham khảo
CHUẨN HÓA CƠ SỞ DỮ LIỆU
6.1. TẠI SAO PHẢI CHUẨN HÓA CƠ SỞ DỮ LIỆU?
6.2. CÁC DẠNG CHUẨN HÓA CỦA CƠ SỞ DỮ LIỆU
6.3. CÁC PHÉP TÁCH BẢO TOÀN THÔNG TIN VÀ BẢO TOÀN PHỤ THUỘC HÀM
6.4. PHÉP TÁCH VỀ DẠNG CHUẨN BOYCE CODD (BCNF) BẢO TOÀN THÔNG TIN
6.5. PHÉP TÁCH VỀ DẠNG CHUẨN 3 (3NF) BẢO TOÀN THÔNG TIN VÀ BẢO TOÀN PHỤ THUỘC HÀM
6
7
6.1. TẠI SAO PHẢI CHUẤN HÓA CƠ SỞ DỮ LIỆU?
Ví dụ 6.1: Xét quan hệ trên lược đồ quan hệ
Kết_Quả_Học_Phần(Mã SV, Họ và tên, Mã HP, Tên HP, Điểm)
NHƯỢC ĐIỂM
1. Dư thừa dữ liệu: Cùng 01 sinh viên nhưng không chỉ có mã sinh viên mà họ tên sinh viên cũng bị lặp đi lặp lại nhiều lần ở các vị trí khác nhau. Tương tự, cùng một học phần thì không chỉ có mã học phần mà tên học phần cũng bị lặp lại ở những vị trí khác nhau.
8
2. Khó khăn khi cập nhật dữ liệu:
Thêm: Ta không thể thêm tên một học phần mới vào quan hệ nếu học phần đó chưa được sinh viên nào đăng ký. Tương tự ta không thể thêm thông tin về một sinh viên mới nếu sinh viên đó chưa đăng ký một học phần nào.
Xóa: Nếu ta xóa thông tin về học phần "Toán rời rạc" thì cũng sẽ mất luôn thông tin của sinh viên "Nguyễn Văn Bình" có mã sinh viên là "HHA003" vì chỉ có một bản ghi duy nhất có chứa thông tin về sinh viên này.
Sửa: Giả sử có nhiều sinh viên đăng ký học môn "Toán rời rạc", khi đó sẽ có nhiều bản ghi có liên quan đến "Toán rời rạc". Nếu ta muốn đổi tên môn "Toán rời rạc" thành "Toán tin" thì ta sẽ phải cập nhật tên môn ở nhiều vị trí tương ứng, gây mất nhiều thời gian và dễ xảy ra sai sót.
3. Không nhất quán dữ liệu: Là hệ quả của 02 điều trên.
9
6.2. CÁC DẠNG CHUẨN HÓA CƠ SỞ DỮ LIỆU
6.2.1. DẠNG CHUẨN 1 (1NF)
Một lược đồ quan hệ R(Ω) được gọi là ở dạng chuẩn 1 (1NF) nếu như toàn bộ các thuộc tính đều mang giá trị đơn và nguyên tố.
Ví dụ 6.2: Các lược đồ quan hệ sau đây không thỏa mãn chuẩn 1:
10
6.2.2. DẠNG CHUẨN 2 (2NF)
Một lược đồ quan hệ R(Ω) được gọi là ở dạng chuẩn 2 (2NF) nếu nó ở dạng chuẩn 1 và mỗi thuộc tính không khóa (nếu có) đều phải phụ thuộc hàm đầy đủ vào một khóa nào đó của lược đồ quan hệ.
Lưu ý một số khái niệm:
Thuộc tính không khóa (nonprime attribute) là thuộc tính không nằm trong bất kỳ một khóa nào của lược đồ quan hệ.
Y được gọi là phụ thuộc hàm đầy đủ vào X nếu X → Y và không tồn tại X’⊆ X sao cho X’→Y (nói cách khác: phụ thuộc hàm đầy đủ có nghĩa là Y chỉ phụ thuộc hàm vào X chứ không phụ thuộc vào một tập con nào đó của X).
Ví dụ 6.2: Xét lược đồ quan hệ
Kết Quả Học Phần(Mã SV, Họ và tên, Mã HP, Tên HP, Điểm)
Có tập phụ thuộc hàm:
F = {Mã SV → Họ và tên, Mã HP → Tên HP, {Mã SV, Mã HP} → Điểm}
Khóa K = {Mã SV, Mã HP}
Họ và tên phụ thuộc hàm vào Mã SV là 1 phần của khóa
Tên HP phụ thuộc hàm vào Mã HP là 1 phần của khóa
KHÔNG THỎA MÃN CHUẨN 2
11
Hệ quả:
Nếu một lược đồ quan hệ đạt chuẩn 1 và tập thuộc tính không khóa của nó là tập rỗng thì đương nhiên lược đồ quan hệ đó đạt chuẩn 2.
Nếu tất cả các khóa của lược đồ quan hệ chỉ gồm một thuộc tính thì lược đồ quan hệ đó đạt chuẩn 2.
THUẬT TOÁN KIỂM TRA MỘT LƯỢC ĐỒ QUAN HỆ CÓ ĐẠT CHUẨN 2
Input: Lược đồ quan hệ R(Ω) và tập phụ thuộc hàm F
Output: Khẳng định R(Ω) có đạt chuẩn 2 hay không.
Bước 1: Tìm tất cả các khóa của lược đồ quan hệ và xác định các thuộc tính không khóa.
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ật sự S của K.
Bước 3: Nếu tồn tại một bao đóng S+ nào đó chứa thuộc tính không khóa thì R(Ω) không đạt chuẩn 2. Ngược lại thì đạt chuẩn 2.
Lưu ý: Đối với những bài toán đơn giản, người ta thường xuất phát từ định nghĩa của dạng chuẩn 2 để xác định xem một lược đồ quan hệ có thỏa mãn dạng chuẩn 2 hay không thay vì phải sử dụng thuật toán nêu trên.
12
Ví dụ 6.3:
Cho lược đồ quan hệ R(A,B,C,D) và tập phụ thuộc hàm:
F = {AB → C, B → D, BC → A}
Hỏi lược đồ quan hệ này có đạt chuẩn 2 hay không?
Giải
Đầu tiên ta tìm tất cả các khóa của lược đồ quan hệ:
TN = B, TG = AC
Ta có hai khóa K1 = AB, K2 = BC. Thuộc tính không khóa là D. Ta thấy B→D trong khi B ⊂ K1. Vậy thuộc tính không khóa D phụ thuộc hàm vào một phần của khóa nên lược đồ quan hệ không thỏa mãn chuẩn 2.
13
Ví dụ 6.4: Cho lược đồ quan hệ R(A,B,C,D) và tập phụ thuộc hàm
F = {B → D, A → C, C → ABD}.
Hỏi lược đồ quan hệ này có đạt chuẩn 2 hay không?
Giải
Đầu tiên ta tìm tất cả các khóa của lược đồ quan hệ:
TN =⍉ , TG = ABC
Ta có hai khóa K1 = A, K2 = C. Tất cả các khóa của lược đồ quan hệ đều có một thuộc tính nên theo hệ quả 2, lược đồ quan hệ đạt chuẩn 2.
14
6.2.3. DẠNG CHUẨN 3 (3NF)
A. Định nghĩa cổ điển
Một lược đồ quan hệ R(Ω) được gọi là ở dạng chuẩn 3 (3NF) nếu nó đã ở dạng chuẩn 2 và không tồn tại thuộc tính không khóa phụ thuộc hàm bắc cầu vào khóa chính của lược đồ quan hệ.
Lưu ý: Một 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 tồn tại tập thuộc tính Y để cả ba điều sau được thỏa mãn:
X → Y, Y → A
Y → X ∉ F+
A ∉ XY
B. Định nghĩa tổng quát
Một lược đồ quan hệ R(Ω) được gọi là ở dạng chuẩn 3 (3NF) nếu với mọi phụ thuộc hàm X→A ∈ F+ (A ∉ X) ta đều có:
Hoặc X là siêu khóa.
Hoặc A là thuộc tính khóa.
15
Ví dụ 6.5: Xét lược đồ quan hệ:
SinhVien(MaSV, HoTen, MaLop, TenLop)
Tập phụ thuộc hàm: F = {MaLop → TenLop; MaSV → HoTen, MaLop}
Khóa chính K = {MaSV}
Lược đồ này không thỏa mãn chuẩn 3 vì có thuộc tính không khóa là TenLop phụ thuộc hàm bắc cầu vào khóa chính MaSV như sau:
MaSV → MaLop và MaLop → TenLop.
16
Hệ quả:
Nếu một lược đồ quan hệ đạt chuẩn 3 thì đương nhiên đạt chuẩn 2.
Nếu một lược đồ quan hệ không có thuộc tính không khóa thì đạt chuẩn 3.
THUẬT TOÁN KIỂM TRA MỘT LƯỢC ĐỒ QUAN HỆ CÓ ĐẠT CHUẨN 3
Input: Lược đồ quan hệ R(Ω) và tập phụ thuộc hàm F.
Output: Khẳng định R(Ω) có đạt chuẩn 2 hay không.
Bước 1: Tìm tất cả các khóa của lược đồ quan hệ R(Ω).
Bước 2: Từ tập phụ thuộc hàm F, tạo ra tập phụ thuộc hàm F’ tương đương với F và có vế phải chỉ có một thuộc tính (nhờ sử dụng luật phân rã).
Bước 3: Nếu mọi phụ thuộc hàm X→A ∈ F’ với A ∉ X đều có X là siêu khóa hoặc A là thuộc tính khóa thì lược đồ quan hệ đạt chuẩn 3. Ngược lại thì lược đồ quan hệ không đạt chuẩn 3.
17
Ví dụ 6.6: Cho lược đồ quan hệ R(A,B,C,D) và tập phụ thuộc hàm:
F = {AB → C, D → B, C → ABD}
Hỏi lược đồ quan hệ này có đạt chuẩn 3 hay không?
Giải
Bước 1: Sau khi áp dụng thuật toán tìm tất cả các khóa, ta tìm được 3 khóa: K1 = AB, K2 = AD, K3 = C. Như vậy, các thuộc tính khóa là: A, B, C, D.
Bước 2: Xây dựng tập phụ thuộc hàm F’ tương đương với F có vế phải một thuộc tính nhờ luật phân rã:
F’ = {AB → C, D → B, C → A, C → B, C → D}
Bước 3: Duyệt các phụ thuộc hàm trong F’, ta thấy tất cả các phụ thuộc hàm đều có vế phải là thuộc tính khóa nên lược đồ quan hệ đạt chuẩn 3.
18
Ví dụ 6.7: Cho lược đồ quan hệ R(A,B,C,D) và tập phụ thuộc hàm:
F = {B → D, A → C, C → ABD}
Hỏi lược đồ quan hệ này có đạt chuẩn 3 hay không?
Giải
Bước 1: Sau khi áp dụng thuật toán tìm tất cả các khóa, ta tìm được 2 khóa: K1 = A và K2 = C. Các thuộc tính khóa là: A, C.
Bước 2: Xây dựng tập phụ thuộc hàm F’ tương đương với F có vế phải một thuộc tính nhờ luật phân rã:
F’ = {B → D, A → C, C → A, C → B, C → D}
Bước 3: Duyệt các phụ thuộc hàm trong F’ ta thấy phụ thuộc hàm B → D có vế trái không phải là siêu khóa, vế phải cũng không phải là thuộc tính khóa. Vậy lược đồ quan hệ không đạt chuẩn 3.
19
6.2.4. DẠNG CHUẨN BOYCE CODD (BCNF)
Một lược đồ quan hệ R(Ω) được gọi là ở dạng chuẩn Boyce Codd (BCNF) nếu với mọi phụ thuộc hàm X → A ∈ F+ (A ∉ X) ta đều có X là siêu khóa.
Gần giống định nghĩa tổng quát của chuẩn 3, nhưng chặt chẽ hơn ở chỗ không chấp nhận trường hợp A là thuộc tính khóa.
Hệ quả: Nếu một lược đồ quan hệ đạt chuẩn Boyce Codd thì đương nhiên đạt chuẩn 3.
20
THUẬT TOÁN KIỂM TRA MỘT LƯỢC ĐỒ QUAN HỆ CÓ ĐẠT CHUẨN BOYCE CODD
Input: Lược đồ quan hệ R(Ω) và tập phụ thuộc hàm F.
Output: Khẳng định R(Ω) có đạt chuẩn Boyce Codd hay không.
Bước 1: Tìm tất cả các khóa của lược đồ quan hệ R(Ω).
Bước 2: Từ tập phụ thuộc hàm F, tạo ra tập phụ thuộc hàm F’ tương đương với F và có vế phải chỉ có một thuộc tính (nhờ sử dụng luật phân rã).
Bước 3: Nếu mọi phụ thuộc hàm X→A ∈ F’ với A ∉ X đều có X là siêu khóa thì lược đồ quan hệ đạt chuẩn Boyce Codd. Ngược lại thì lược đồ quan hệ không đạt chuẩn Boyce Codd.
21
Ví dụ 6.8: Cho lược đồ quan hệ R(A,B,C,D,E,I) và tập phụ thuộc hàm F = {ACD → EBI, CE → AD}. Hỏi lược đồ quan hệ này có đạt chuẩn Boyce Codd hay không?
Giải
Bước 1: Sau khi áp dụng thuật toán tìm tất cả các khóa, tìm được 2 khóa: K1 = ACD, K2 = CE.
Bước 2: Xây dựng tập phụ thuộc hàm tương đương F’ có vế phải một thuộc tính nhờ luật phân rã:
F’ = {ACD → E, ACD → B, ACD → I, CE → A, CE → D}
Bước 3: Duyệt các phụ thuộc hàm trong F’ ta thấy các phụ thuộc hàm đều có vế trái là khóa ACD hoặc CE nên đương nhiên lược đồ quan hệ thỏa mãn chuẩn Boyce Codd.
22
6.2.5. XÁC ĐỊNH DẠNG CHUẨN CAO NHẤT CỦA LƯỢC ĐỒ QUAN HỆ
Một lược đồ quan hệ đã đạt dạng chuẩn nào thì đương nhiên cũng thỏa mãn các dạng chuẩn thấp hơn.
23
THUẬT TOÁN XÁC ĐỊNH DẠNG CHUẨN CAO NHẤT CỦA LƯỢC ĐỒ QUAN HỆ
Input: Lược đồ quan hệ R(Ω) và tập phụ thuộc hàm F.
Output: Dạng chuẩn cao nhất của lược đồ quan hệ R(Ω).
Bước 1: Tìm tất cả các khóa của R(Ω).
Bước 2: Kiểm tra xem R(Ω) có đạt chuẩn Boyce Codd không. Nếu R(Ω) có đạt chuẩn Boyce Codd thì kết luận chuẩn Boyce Codd là dạng chuẩn cao nhất của lược đồ quan hệ và kết thúc thuật toán. Ngược lại nếu không đạt chuẩn Boyce Codd thì chuyển qua bước 3.
Bước 3: Kiểm tra xem R(Ω) có đạt chuẩn 3 không. Nếu R(Ω) có đạt chuẩn 3 thì kết luận chuẩn 3 là dạng chuẩn cao nhất của lược đồ quan hệ và kết thúc thuật toán. Ngược lại nếu không đạt chuẩn 3 thì chuyển qua bước 4.
Bước 4: Kiểm tra xem R(Ω) có đạt chuẩn 2 không. Nếu R(Ω) có đạt chuẩn 2 thì kết luận chuẩn 2 là dạng chuẩn cao nhất của lược đồ quan hệ và kết thúc thuật toán. Ngược lại thì kết luận R(Ω) đạt chuẩn 1.
Để xác định dạng chuẩn cao nhất của lược đồ quan hệ người ta sẽ kiểm tra lần lượt từ chuẩn Boyce Codd đến các dạng chuẩn thấp hơn.
24
6.3. CÁC PHÉP TÁCH BẢO TOÀN THÔNG TIN VÀ
BẢO TOÀN TẬP PHỤ THUỘC HÀM
Đảm bảo việc khôi phục nguyên vẹn quan hệ gốc ban đầu từ các quan hệ con sau khi tách, không phát sinh các bộ phụ thêm.
DanhSachHocSinh(MaHS, HoTen, DiemThi, MaLop, TenLop, PhongHoc)
HocSinh(MaHS, HoTen, DiemThi, MaLop)
Lop(MaLop, TenLop, PhongHoc)
26
B. Thuật toán kiểm tra một phép tách có bảo toàn thông tin
Input: Lược đồ quan hệ R(Ω) với Ω = {A1, A2,..., An} và tập phụ thuộc hàm F.
Phép tách R(Ω) thành m lược đồ con R1(Ω1), R2(Ω2), ... , Rm(Ωm)
Output: Khẳng định phép tách có bảo toàn thông tin hay không.
Bước 1: Tạo một ma trận S có m hàng và n cột. Mỗi cột tương ứng với một thuộc tính Aj trong Ω và mỗi hàng tương ứng với một lược đồ quan hệ con Ri(Ωi) .
Bước 2: Đặt phần tử S(i, j) của ma trận nhận giá trị bằng 1 nếu Aj∈ Ωi và ngược lại, S(i, j) nhận giá trị bằng 0 nếu Aj ∉ Ωi
Bước 3: Lặp lại thao tác sau đây cho tới khi nào không còn sự thay đổi trong ma trận S: Với mỗi phụ thuộc hàm X → Y trong F, xác định các hàng trong S có chứa các giá trị 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 giá trị 1 trong các cột ứng với tập thuộc tính Y thì làm cho các cột tương ứng của các hàng khác cũng chứa giá trị 1.
Bước 4: Nếu tồn tại 01 hàng có chứa toàn giá trị 1 thì phép tách là bảo toàn thông tin, ngược lại là không bảo toàn.
Ví dụ 6.9: Cho lược đồ quan hệ
PhanCong(MaNV, TenNV, ChuyenMon, MaDA, TenDA, DiaDiem, NgayBD, NgayKT)
Và tập phụ thuộc hàm:
F = { MaNV → TenNV, ChuyenMon;
MaDA → TenDA, DiaDiem;
MaNV, MaDA → NgayBD, NgayKT }
Người ta tách lược đồ quan hệ PhanCong thành các lược đồ con sau đây:
NhanVien(MaNV, TenNV, ChuyenMon)
DuAn(MaDA, TenDA, DiaDiem)
PhanCongNV(MaNV, MaDA, NgayBD, NgayKT)
Hỏi phép tách trên có bảo toàn thông tin không?
Giải
28
6.3.2. PHÉP TÁCH BẢO TOÀN TẬP PHỤ THUỘC HÀM
29
6.4. PHÉP TÁCH VỀ DẠNG CHUẨN BOYCE CODD BẢO TOÀN THÔNG TIN
Thuật toán tách
Input: Lược đồ quan hệ gốc R(Ω) và tập phụ thuộc hàm F.
Output: Tập D gồm các lược đồ quan hệ con R1(Ω1), R2(Ω2), ... , Rm(Ωm) thỏa mãn BCNF và bảo toàn thông tin
Bước 1: Khởi tạo D = {R(Ω)}
Bước 2: Lặp lại thao tác sau đây: Với mỗi lược đồ quan hệ Ri(Ωi) trong D không ở BCNF, tìm một phụ thuộc hàm X → Y vi phạm định nghĩa BCNF và thay thế Ri(Ωi) bằng 02 lược đồ quan hệ Si(ΩiY) và Ti(X∪Y). Quá trình lặp dừng khi không còn lược đồ quan hệ nào trong D không thỏa mãn BCNF.
30
Ví dụ 6.10: Xét lược đồ quan hệ R(A,B,C,D,E,F) và tập phụ thuộc hàm:
F = {A → BCDEF, BC → ADEF, B → F, D → E, D → B}
Hãy tách lược đồ trên thành các lược đồ con thỏa mãn BCNF và bảo toàn thông tin.
Giải
R(A,B,C,D,E,F)
F = {A → BCDEF, BC → ADEF, B → F, D → E, D → B}
K1 = A, K2 = BC
R1(B,F)
F1 = {B → F}
K = B
R2(A,B,C,D,E)
F2 = {A → BCDE, BC → ADE, D → E, D → B}
K1 = A, K2 = BC
R21(D,E)
F21 = {D → E}
K = D
R22(A,B,C,D)
F22 = {A → BCD, BC → AD, D → B}
K1 = A, K2 = BC
R222(A,C,D)
F222 = {A → CD}
K = A
R221(D,B)
F221 = {D → B}
K = D
D = {R1(B,F), R21(D,E), R221(D,B), R222(A,C,D)}
31
Ví dụ 6.11: Xét lược đồ quan hệ
PhanCong(MaNV, TenNV, ChuyenMon, MaDA, TenDA, DiaDiem, NgayBD, NgayKT)
và tập phụ thuộc hàm:
F = { MaNV → TenNV, ChuyenMon;
MaDA → TenDA, DiaDiem;
MaNV, MaDA → NgayBD, NgayKT }
Hãy tách lược đồ trên thành các lược đồ con thỏa mãn BCNF và bảo toàn thông tin.
Giải
PhanCong(MaNV, TenNV, ChuyenMon, MaDA, TenDA, DiaDiem, NgayBD, NgayKT)
F = {MaNV → TenNV, ChuyenMon; MaDA → TenDA, DiaDiem; MaNV, MaDA → NgayBD, NgayKT}
K = {MaNV, MaDA}
NhanVien(MaNV,TenNV, ChuyenMon)
F1 = {MaNV → TenNV, ChuyenMon}
K = MaNV
PhanCong1(MaNV, MaDA, TenDA, DiaDiem, NgayBD, NgayKT)
F2 = {MaDA → TenDA, DiaDiem; MaNV, MaDA → NgayBD, NgayKT}
K = {MaNV, MaDA}
DuAn(MaDA, TenDA, DiaDiem)
F3 = {MaDA → TenDA}
K = MaDA
PhanCongNV(MaNV, MaDA, NgayBD, NgayKT)
F4 = {MaNV, MaDA → NgayBD, NgayKT}
K = {MaNV, MaDA}
D = {NhanVien, DuAn, PhanCongNV}
32
6.5. PHÉP TÁCH VỀ DẠNG CHUẨN 3 BẢO TOÀN THÔNG TIN VÀ BẢO TOÀN PHỤ THUỘC HÀM
Thuật toán tách
Input: Lược đồ quan hệ gốc R(Ω) và tập phụ thuộc hàm F.
Output: Tập D gồm các lược đồ quan hệ con R1(Ω1), R2(Ω2), ... , Rm(Ωm) thỏa mãn chuẩn 3, bảo toàn thông tin và bảo toàn phụ thuộc hàm.
Bước 1: Tìm phủ tối thiểu G của F (nếu F chưa phải là tập PTH tối thiểu).
Bước 2: Với mỗi phụ thuộc hàm X → A trong G ta tạo ra một lược đồ quan hệ con S(X∪{A}) trong D. Nếu có nhiều phụ thuộc hàm có chung vế trái: X→A1, X→A2,..., X→Ak thì thay vì phải tạo lược đồ quan hệ con ứng với từng phụ thuộc hàm riêng lẻ, ta tạo ra một lược đồ quan hệ con chung S(X∪{A1}∪{A2}∪...∪{Ak})
Lưu ý: X là khóa chính của các lược đồ quan hệ con này.
Bước 3: Nếu không có lược đồ quan hệ con nào trong D chứa một khóa của R thì tạo thêm một lược đồ quan hệ con trong D có các thuộc tính là thuộc tính khóa cấu thành một khóa nào đó của R.
33
Ví dụ 6.12: Xét lược đồ quan hệ
PhanCong(MaGV, TenGV, MaPhong, DiaDiem, MaMon, TenMon)
và tập phụ thuộc hàm:
F = {MaGV → TenGV; MaPhong → DiaDiem; MaMon → TenMon }
Hãy tách lược đồ trên thành các lược đồ con thỏa mãn 3NF, bảo toàn thông tin và bảo toàn tập phụ thuộc hàm.
Giải
1. Bản thân tập F đã là tập phụ thuộc hàm tối thiểu rồi nên ta không cần tìm phủ tối thiểu G của F nữa.
2. Khóa của lược đồ quan hệ là K = {MaGV, SoPhong, MaMon}
3. Áp dụng thuật toán, ta lần lượt tạo ra các lược đồ quan hệ R(XA) tương ứng với các phụ thuộc hàm X → A:
GiangVien(MaGV, TenGV) có F = {MaGV → TenGV} và K = MaGV
PhongHoc(MaPhong, DiaDiem) có F = {MaPhong → DiaDiem} và K = MaPhong
MonHoc(MaMon, TenMon) có F = {MaMon → TenMon} và K = MaMon
4. Trong các lược đồ quan hệ con đã tạo không có lược đồ nào có chứa khóa của lược đồ quan hệ gốc nên ta tạo ra một lược đồ quan hệ nữa chứa toàn các thuộc tính của khóa: PhanCongGiangDay(MaGV, MaPhong, MaMon) có K = Ω
Kết quả của phép tách là:
D = {GiangVien, PhongHoc, MonHoc, PhanCongGiangDay}
34
Q & A
35
* Một số tài liệu cũ có thể bị lỗi font khi hiển thị do dùng bộ mã không phải Unikey ...
Người chia sẻ: Nguyễn Vương Thịnh
Dung lượng: |
Lượt tài: 0
Loại file:
Nguồn : Chưa rõ
(Tài liệu chưa được thẩm định)