Bài giảng Cơ sở dữ liệu: Chương 6 - Trịnh Xuân

Chia sẻ: 5A4F5AFSDG 5A4F5AFSDG | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

143
lượt xem 4
download

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

Chương 6: Chuẩn hóa cơ sở dữ liệu (Data normalization). Nội dung chương này gồm có: Một số khái niệm cơ bản, phụ thuộc hàm đầy đủ, phụ thuộc hàm bắc cầu, chuẩn hóa lược đồ quan hệ, các bất thường của quan hệ ở 1NF, thuật toán kiểm tra dạng chuẩn 2,... Mời các bạn cùng tham khảo.

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 Cơ sở dữ liệu: Chương 6 - Trịnh Xuân

I. Một số khái niệm cơ bản !  Định nghĩa: Phép tách các 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 CHƯƠNG VIII: đó Ri ⊂ R, i = 1,..,k - Ri là các lược đồ con CHUẨN HÓA CSDL và R = R1 ∪ R2 ∪ ... ∪ Rk Data normalization 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ụ Phép tách-Kết nối không mất mát thông tin MSKH TÊNKH TP PVC MSMH TÊNMH ĐG SL S1 S1 An An HCM HCM 01 01 P1 P2 Táo Cam 650 500 300 200 !  Giả sử R tách thành các lược đồ con R1, R2, .., S1 An HCM 01 P3 Chanh 450 400 Rk và F là một tập pth. S2 S2 Hòa Hoà HN HN 02 02 P1 P3 Táo Chanh 650 450 100 300 !  Nói rằng phép tách R thành các lược đồ con R1, S3 Thanh NT 03 P2 Cam 500 200 R2, …, Rk là tách - kết nối không mất mát S4 Trang NT 03 P2 Cam 500 210 thông tin đối với F nếu với mỗi quan hệ r trên R thoả F thì MaCTY ĐC MH GIA 1 Thanh Xuân 1 10000 1 Thanh Xuân 2 15000 2 Đống Đa 1 12000 r = ΠR1(r) * Π R2 (r) * ... * Π Rk(r) 2 Đống Đa 2 16000 MaCTY MH GIA MaCTY ĐC 1 1 10000 tức là r được tạo nên từ phép kết nối tự nhiên 1 Thanh Xuân 2 Đống Đa 1 2 15000 của các hình chiếu của nó trên các Ri, i= 1..,k 2 1 12000 Cơ sở dữ liệu 2 2 16000 4 Cơ sở dữ liệu 5 Phụ thuộc hàm đầy đủ Phụ thuộc hàm bắc cầu !  Cho lược đồ quan hệ (U,F), X, Y⊆U. !  Cho lược đồ quan hệ α = (U,F), X ⊆ U, A ∈ U, !  Khi đó Y được gọi là phụ thuộc hàm đầy đủ vào tập X nếu thuộc tính A được gọi là phụ thuộc hàm bắc cầu như Y phụ thuộc hàm vào X nhưng không phụ thuộc hàm vào tập thuộc tính X nếu như ∃ Y ⊆ X để: vào bất kỳ tập con thực sự nào của X, tức là: -  X → Y, Y → A -  X → Y -  Nhưng Y /! X với A ∉ XY -  ∀Z ⊂ X thì Z /→ Y, mọi tập con thực sự của X đều không thể xác định hàm Y !  VD: R(ABCDE), F = {AB ! CD, D ! E}, khoá: AB. !  VD: F = {AB ! C, A ! C}. -  Ta có: AB ! E là pth bắc cầu vì: ∃ D ⊂ R: "  AB ! D D!E -  Ta có pth AB ! C không phải là pth đầy đủ vì có pth A !C "  D /! AB E ∉ ABD Cơ sở dữ liệu 6 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 Thuật toán Bước 1: Lập bảng với n+1 cột và k+1 hàng !  Input: - Cột thứ j# thuộc tính thứ j của lược đồ (Aj) -  R = {A1, A2, .., An} – n thuộc tính tập pth F và - Hàng thứ i # 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 -  phép tách p = (R1, R2, .., Rk) – k lược đồ con Bước 2: thay đổi giá trị cho bảng !  Lần lượt xét các pth (X→Y) ∈ F !  Output: Kiểm tra phép tách có mất mát !  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 thông tin hay không ? nhau thì phải bằng nhau ở thuộc tính Y " 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 gì bảng nữa 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 8 Cơ sở dữ liệu 9 Ví dụ 1: !  Cho quan hệ: S# Sname Add Item Price !  Lập bảng: 3 hàng – 6 cột CungCap( MaNCC, Sname, Add, Item, Price ) S#, Sname, Add a1 a2 a3 b14 b15 !  Tập phụ thuộc hàm: MaNCC→Sname,Add, S#, Item, Price a1 b22 b23 a4 a5 !  Xét S# → Sname, Add: Sname,Item→Price -  có cả hai hàng bằng !  Kiểm tra phép tách thành hai sơ đồ con nhau tại thuộc tính S# CongTy{MaNCC, Sname, Add} và -  làm bằng nhau các kí S# Sname Add Item Price hiệu đối với thuộc tính MatHang{MaNCC, Item, Price} có mất mát thông Sname và Add a1 a2 a3 b14 b15 tin? "  làm b22 thành a2 "  làm b23 thành a3 a1 b22 b23 a4 a5 !  Bảng có một hàng bao a2 a3 gồm các ký hiệu a => phép tách không mất mát thông tin Cơ sở dữ liệu 10 Cơ sở dữ liệu 11 Ví dụ: Ví dụ !  R={MSNV,TenNV,MaSoDA,TenDA, DiadiemDa, Sogio} !  R={MSNV, TenNV, MaSoDA, TenDA, DiadiemDa, Sogio} !  F = { MSNV ! TenNV, !  F = { MSNV ! TenNV, MasoDA ! {TenDA, DiadiemDA}, MasoDA ! {TenDA, DiadiemDA}, {MaSoDA, MSNV} ! Sogio } {MaSoDA, MSNV} ! Sogio } !  Kiểm tra phép tách thành !  Kiểm tra phép tách thành -  R1 = { MSNV, TenNV} -  R1 = {TenNV, DiadiemDA} -  R2 = { MaSoDa, TenDA, DiadiemDA} -  R2 = { MSNV, MasoDA, Sogio, TenDA, DiadiemDA} -  R3 = { MSNV, MasoDA, Sogio} !  Có mất mát thông tin? !  Có mất mát thông tin? Cơ sở dữ liệu 12 Cơ sở dữ liệu 13
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 !  Các loại dạng chuẩn gồm: thuộc tính và áp dụng các quy tắc phân tích vào -  Dạng chuẩn 1 (1NF – First Normal Form) 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 -  Dạng chuẩn 2 (2NF – Second Normal Form) !  Sao cho: -  Dạng chuẩn 3 (3NF) -  Tối thiểu việc lặp lại -  Dạng chuẩn Boye Code (BCNF) -  Tránh dị thường thông tin BCNF -  Xác định và giải quyết được sự không rõ ràng, 3NF nhập nhằng trong suy diễn 2NF 1NF Cơ sở dữ liệu 21 Cơ sở dữ liệu 22 1. Dạng chuẩn 1NF MSKH TenKH TP PVC MSMH TenMH ĐG SL !  Lược đồ quan hệ R được gọi là 1NF nếu và chỉ nếu tất S1 An HCM 01 P1 Táo 650 300 cả các thuộc tính của R thoả mãn cả 3 điều kiện sau: P2 Cam 500 200 P3 Chanh 450 400 -  là kiểu nguyên tố, S2 Hòa HN 02 P1 Táo 650 100 -  giá trị của các thuộc tính trên các bộ là đơn trị, P3 Chanh 450 300 S3 Thanh NT 03 P2 Cam 500 200 -  không có một thuộc tính nào có giá trị tính toán từ S4 Trang NT 03 P2 Cam 500 210 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 !  Biểu diễn sơ đồ dạng 1NF: 1 R(A1,A2,A3, A4, A5) 2 3 4 Cơ sở dữ liệu 23 Cơ sở dữ liệu 24 Các bất thường của quan hệ ở 1NF !  Lược đồ ở dạng 1NF gặp khó khăn thêm-xóa-sửa ! Kết luận: Để kiểm tra một lược đồ có là !  Nguyên nhân: Tồn tại thuộc tính không khóa phụ dạng 1NF không thực hiện kiểm tra thuộc hàm riêng phần vào khóa nếu: !  Giải quyết: đưa về dạng chuẩn cao hơn 2NF -  Không có thuộc tính đa trị MSKH TÊNKH TP PVC MSMH TÊNMH ĐG SL -  Không có thuộc tính phức hợp S1 S1 An An HCM HCM 01 01 P1 P2 Táo Cam 650 500 300 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 Cơ sở dữ liệu 25 Chương 4. Cơ sở dữ liệu
2. Dạng chuẩn 2NF Thuật toán kiểm tra dạng chuẩn 2 !  LĐQH R được gọi là đạt dạng chuẩn 2 nếu R đã ở !  Bước 1: Tìm tất cả các khóa của quan hệ dạng chuẩn 1 và tất cả 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 (thuộc tính không tham gia vào khóa) đều phụ thuộc con thực sự S của K hàm đầy đủ vào khóa. -  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 !  Mục đích: -  Giản ước sự dư thừa dữ liệu !  Bước 3: -  Tránh các dị thường cập nhật gây nên do sự dư thừa -  nếu có bao đóng S+ chứa thuộc tính không khóa thì dữ liệu này 1 quan hệ không đạt chuẩn 2 !  Biểu diễn sơ đồ dạng 2NF: -  ngược lại thì quan hệ đạt chuẩn 2 (không tồn tại S mà R(A1,A2,A3, A4, A5) S+ chứa thuộc tính không khóa) 4 3 Cơ sở dữ liệu 30 Cơ sở dữ liệu 33 Ví dụ: kiểm tra dạng 2NF của quan hệ Thuật toán đưa về dạng 2NF !  1- QLSV (MaSV, Ten, NS, DC, TenLop, KhoaHoc, MaMH, TenMH, !  Nhóm các thuộc tính phụ thuộc vào một phần của Diem) khoá và thuộc tính một phần tách thành quan hệ F = { f1: MaSV ! Ten, NS, DC, TenLop mới, lấy phần đó làm khoá chính cho quan hệ. f2: TenLop ! KhoaHoc; f3: MaMH ! TenMH; !  Giữ các thuộc tính phụ thuộc hoàn toàn vào khoá f4 : TenMH ! MaMH; và giữ lại khoá của quan hệ đó f5: MaSV, MaMH ! Diem } R(A1,A2,A3, A4, A5) !  2- KQHT (MaSV, MaMH, TenMH, Diem) FKQHT = { f1: MaMH ! TenMH; f2 : TenMH ! MaMH; f3: MaSV, MaMH ! Diem } R1(A2, A4) !  3- SV (MaSV, Ten, NS, DC, TenLop, KhoaHoc) FSV = { f1:MaSV ! Ten, NS, DC, TenLop; R(A1,A2,A3, A5) f2: TenLop ! KhoaHoc} Cơ sở dữ liệu 34 Cơ sở dữ liệu 38 !  Ví dụ 3: -  Cho R2 (Số hoá đơn, Số sản phẩm, Tên sản phẩm, Lượng yêu cầu) Ví dụ: -  F = { Số sản phẩm ! Tên sản phẩm } -  Hỏi quan hệ có ở dạng 2NF không? Nếu chưa NV( MaNV, MaPhong,TenNV, Gioitinh, Diachi,TenPhong ) tách thành lược đồ ở dạng 2NF Kết quả là gì? Cơ sở dữ liệu 39 Cơ sở dữ liệu 40
Các bất thường của quan hệ ở 2NF 3. Dạng chuẩn 3NF !  Khi tiến hành Thêm-Sửa-Xóa có thể không !  Lược đồ R ở 3NF nếu: thực hiện được hoặc tạo ra dị thường dữ liệu. -  Ở dạng 2NF -  Mọi thuộc tính không khóa đều không phụ thuộc bắc !  Nguyên nhân: Tồn tại thuộc tính không cầu vào bất kỳ khóa chính của quan hệ khóa phụ thuộc bắc cầu vào khóa !  Xét mọi pth X ! A thì !  Giải quyết: đưa về chuẩn cao hơn 3NF -  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 !  Sơ đồ: 1 R(A1,A2,A3, A4, A5) 4 Cơ sở dữ liệu 43 Cơ sở dữ liệu 44 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 !  Ví dụ 1: Xét quan hệ CNHAN nhu sau: !  Thuật toán: -  CNHAN(MACN, LOAINGHE, HESOTHUONG) -  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 -  các pth: F có vế phải một thuộc tính "  MACN → LOAINGHE -  Bước 3: Kiểm tra "  MACN → HESOTHUONG "  Nếu mọi phụ thuộc hàm X!A ∈ F với A∉X đều "  LOAINGHE → HESOTHUONG có X là khóa hoặc A là thuộc tính khóa thì Q đạt chuẩn 3 "  Hỏi lược đồ có đạt chuẩn 3 không? "  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 47 Cơ sở dữ liệu 48 Đưa về dạng 3NF ! Ví dụ 2: Cho lược đồ quan hệ !  Tạo quan hệ mới gồm các thuộc tính phụ Q(A,B,C,D) và thuộc bắc cầu vào thuộc tính khóa, lấy thuộc F = { AB !C, D !B, C !ABD}. Hỏi Q tính bắc cầu làm khoá có đạt chuẩn 3 không? !  Giữ lại các thuộc tính phụ thuộc trực tiếp vào khoá !  Thuộc tính bắc cầu nằm ở hai quan hệ R(A1,A2, A3, A4, A5) R1(A2, A4) R(A1, A2, A3, A5) Cơ sở dữ liệu 49 Cơ sở dữ liệu
!  Ví dụ 4: Xét lược đồ quan hệ !  NHÂNVIÊN_ĐƠNVỊ( HọtênNV, MãsốNV, Ngàysinh, Ví dụ: Địachỉ, MãsốĐV, TênĐV, MãsốNQL) !  Với các phụ thuộc hàm: NV(MaNV,MaPhong,TenNV,Gioitinh,Diachi,TenPhong) -  MãsốNV→HọtênNV, Ngàysinh,Địachỉ,MãsốĐV,TênĐV, MãsốNQL -  MãsốĐV→ TênĐV, Mã sốNQL Kết quả 3NF là gì? !  Lược đồ có ở dạng 3NF không? Tách về 3NF Cơ sở dữ liệu 51 Cơ sở dữ liệu 52 Ví dụ: Xây dựng chuẩn 3NF Kết quả ở 2NF MSKH MSMH SL !  Ví dụ:Tập pth F được định nghĩa trên R như sau: MSKH TÊNKH TP PVC S1 P1 300 S1 An HCM 01 S1 P2 200 !  F= { 1. MSKH ! TÊNKH,TP 2. MSMH ! TÊNMH,ĐG S1 P3 400 S2 Hoà HN 02 3. MSKH, MSMH ! SL 4. TP ! PVC} S2 P1 100 S3 Thanh NT 03 !  Khoá: MSKH, MSMH $ đưa về 3NF S2 P3 300 S4 Trang NT 03 S3 P2 200 S4 P2 210 MSKH TÊNKH TP PVC MSMH TÊNMH ĐG SL FR1 = {MSKH ! TÊNKH, TP FĐH = {MSKH, MSMH ! SL} S1 An HCM 01 P1 Táo 650 300 TP ! PVC} S1 An HCM 01 P2 Cam 500 200 S1 An HCM 01 P3 Chanh 450 400 MSMH TÊNMH ĐG S2 Hòa HN 02 P1 Táo 650 100 P1 Táo 650 S2 Hoà HN 02 P3 Chanh 450 300 P2 Cam 500 S3 Thanh NT 03 P2 Cam 500 200 P3 Chanh 450 S4 Trang NT 03 P2 Cam 500 210 FMH = {MSMH! TÊNMH, ĐG} Cơ sở dữ liệu 55 Cơ sở dữ liệu 56 Kết quả ở 3NF 4. Dạng chuẩn BCNF (Boyce Codd) MSKH S1 TÊNKH An TP HCM TP PVC !  Định nghĩa: Lược đồ quan hệ R ở dạng HCM 01 S2 Hoà HN HN 02 chuẩn BCNF nếu với mọi pth X→A của R, S3 Bình NT NT 03 A∉X thì X là một siêu khóa nhỏ nhất ! các FVC = {TP ! PVC} S4 Trang NT thuộc tính đều phụ thuộc trực tiếp vào khóa FKH = {MSKH ! TÊNKH, TP} MSKH MSMH SL !  Sơ đồ: S1 P1 300 MSMH TÊNMH ĐG S1 P2 200 1 S1 P3 400 P1 Táo 650 S2 P2 Cam 500 S2 P1 P3 100 300 R(A1,A2,A3, A4, A5) P3 Chanh 450 S3 P2 200 S4 P2 210 FMH = {MSMH! TÊNMH, ĐG} FĐH = {MSKH, MSMH ! SL} Cơ sở dữ liệu 57 Cơ sở dữ liệu 58
Thuật toán kiểm tra dạng chuẩn BCNF !  Bước 1: Tìm tất cả các khóa của quan hệ Q ! Ví dụ 1: Cho R = { C, S, Z}, Phụ thuộc !  Bước 2: Từ tập pth F tạo tập pth tương đương với F gọi là F có vế phải một thuộc tính hàm: CS→Z, Z →C !  Bước 3: ! Xác định dạng chuẩn cao nhất -  nếu mọi pth X→A ∈F đều có X là khóa thì Q đạt chuẩn BCNF -  ngược lại Q không đạt chuẩn BCNF (∃ X → A mà X không là khóa) # mọi pth đều có vế trái là khóa thì đạt chuẩn BCNF ngược lại thì không Cơ sở dữ liệu 60 Cơ sở dữ liệu 61 Đưa về dạng BCNF !  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ệ và tạo 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ụ: Hoc(MaSV, MaMon, Diem, MaGV) R(A1, A2, A3, A4, A5) R1(A4, A2) Kết quả là gì? R(A1, A4, A3, A5) Cơ sở dữ liệu 63 Cơ sở dữ liệu 64 * Quá trình chuẩn hóa 1 1NF R(A1,A2,A3, A4, A5) 2 3 4 1 2NF R(A1,A2,A3, A4, A5) 4 3 1 3NF R(A1,A2,A3, A4, A5) 4 1 BCNF R(A1,A2,A3, A4, A5) Cơ sở dữ liệu 66
IV. Chuẩn hóa quan hệ 1. Thuật toán phân rã thành các BCNF !  Chuẩn hóa quan hệ là việc phân rã một lược đồ !  Input: Quan hệ R và tập PTH F quan hệ thành các lược đồ con ở dạng chuẩn 3 !  Output: tách thành các lược đồ ở BCNF hoặc ở dạng chuẩn BCNF sao cho vẫn bảo toàn !  Các bước: phụ thuộc và không mất mát dữ liệu -  Ban đầu phép tách S chỉ là R -  Chọn pth X!A trong đó X không chứa khóa của S và A∉X ! PTH vi phạm BCNF -  Thay thế S bởi S1 và S2. Trong đó: "  S1 = XA "  S2 = S \ A (loại thuộc tính A khỏi S) -  Quá trình trên tiếp tục cho đến khi tất cả các lược đồ quan hệ đều ở BCNF Cơ sở dữ liệu 67 Cơ sở dữ liệu 68 Ví dụ: Tách lược đồ về dạng BCNF !  Cho lược đồ R(CTHRSG), trong đó: C T: Mỗi khoá học (course) có một thầy (teacher) duy nhất. HR C: Tại một thời điểm (Hour) tại phòng học (room) chỉ có một khoá học duy nhất. -  C – Course; T – Teacher; H – Hour: Giờ học HT R: Tại một thời điểm và một giáo viên chỉ ở một phòng duy nhất -  R – Room; S – Student; G – Group CS G: Một sinh viên học một course thì chỉ ở một lớp duy nhất. !  PTH F = { C!T; HR!C; HT!R; CS!G; HS!R } HS R: Một SV, ở một thời điểm nhất định chỉ ở trong một phòng duy nhất. !  Khóa: HS C – Cource T – Teacher H – Hour R – Room S – Student G – Group CSDL Tâm 7h 21 N.V Hà CSDL.1 CSDL Tâm 7h 21 T.V Huy CSDL.1 CSDL Tâm 7h 21 Đ.T Lan CSDL.1 CTDL Xuân 9h 22 N.V Hà CTDL.1 CTDL Xuân 9h 22 Đ.T Lan CTDL.1 CTDL Xuân 9h 22 L.T Linh CTDL.1 TRR Linh 7h 23 T.V An TRR.1 TRR Linh 7h 23 Đ.V Hưởng TRR.2 Cơ sở dữ liệu 74 !  Xét CS!G !  Xét C!T -  Tách thành R1(CSG) và R2(CTHRS) -  Tách thành R21(CT) và R22(CHRS) R1(CSG) R2(CTHRS) R1(CSG) R21(CT) R22(CHRS) C– S– G– C– T– H– R– S – Student C– S – Student G – Group C– T– C– H– R– S – Student Cource Student Group Cource Teacher Hour Room Cource Cource Teacher Cource Hour Room CSDL N.V Hà CSDL.1 CSDL Tâm 7h 21 N.V Hà CSDL N.V Hà CSDL.1 CSDL Tâm CSDL 7h 21 N.V Hà CSDL T.V Huy CSDL.1 CSDL Tâm 7h 21 T.V Huy CSDL T.V Huy CSDL.1 CTDL Xuân CSDL 7h 21 T.V Huy CSDL Đ.T Lan CSDL.1 CSDL Tâm 7h 21 Đ.T Lan CSDL Đ.T Lan CSDL.1 TRR Linh CSDL 7h 21 Đ.T Lan CTDL N.V Hà CTDL.1 CTDL Xuân 9h 22 N.V Hà CTDL N.V Hà CTDL.1 CTDL 9h 22 N.V Hà CTDL Đ.T Lan CTDL.1 CTDL Xuân 9h 22 Đ.T Lan CTDL Đ.T Lan CTDL.1 CTDL 9h 22 Đ.T Lan CTDL L.T Linh CTDL.1 CTDL Xuân 9h 22 L.T Linh CTDL L.T Linh CTDL.1 CTDL 9h 22 L.T Linh TRR T.V An TRR.1 TRR Linh 7h 23 T.V An TRR T.V An TRR.2 TRR 7h 23 T.V An TRR Đ.V Hưởng TRR.2 TRR Linh 7h 23 Đ.V Hưởng TRR Đ.V Hưởng TRR.2 TRR 7h 23 Đ.V Hưởng Cơ sở dữ liệu 75 Cơ sở dữ liệu 76
C– R221(CHR) H– R– 2. Thuật toán phân rã thành các 3NF Cource Hour Room !  Xét CH!R CSDL 7h 21 !  Input: Lược đồ R và tập các phụ thuộc hàm F -  Tách thành R221(CHR) và R222(CHS) CTDL 9h 22 !  Output: Tách thành các lược đồ ở 3NF TRR 7h 23 !  Thuật toán: R1(CSG) R21(CT) R222(CHS) -  Loại bỏ các thuộc tính R nếu thuộc tính đó không liên quan C– S – Student G – Group C– T– C– Cource H– Hour S – Student đến PTH của F (không có mặt ở cả hai vế của PTH) Cource Cource Teacher CSDL N.V Hà CSDL.1 CSDL Tâm CSDL 7h N.V Hà -  Nếu có một PTH của F liên quan đến tất cả các thuộc tính CTDL Xuân CSDL 7h T.V Huy của R thì kết quả chính là R (không tách nữa) CSDL T.V Huy CSDL.1 CSDL Đ.T Lan CSDL.1 TRR Linh CSDL 7h Đ.T Lan -  Xét các PTH X!A vi phạm 3NF (phụ thuộc bắc cầu vào CTDL N.V Hà CTDL.1 CTDL 9h N.V Hà khóa) và tách thành một lược đồ XA CTDL Đ.T Lan CTDL.1 CTDL 9h Đ.T Lan "  Nếu tồn tại các PTH X!A1, X!A2, …, X!An thì gộp thành XA1A2..An CTDL L.T Linh CTDL.1 CTDL 9h L.T Linh TRR T.V An TRR.2 TRR 7h T.V An TRR Đ.V Hưởng TRR.2 TRR 7h Đ.V Hưởng Cơ sở dữ liệu 77 Cơ sở dữ liệu 79 Ví dụ: Tách về 3NF !  Cho lược đồ R(CTHRSG), trong đó: -  C – Course; T – Teacher; H – Hour: Giờ học % Xét C!T vi phạm 3NF (phụ thuộc bắc cầu vào khoá), -  R – Room; S – Student; G – Group % Tách R thành R1(C,T) và R2(C,H,R,S,G). !  PTH F={ C!T; HR!C; HT!R; CS!G; HS!R} !  Khóa: CHS R1 R2 R C– T– C– H– R– S – Student G– C – Cource T – Teacher H – Hour R – Room S – Student G – Group Cource Teacher Cource Hour Room Group CSDL Tâm 7h 21 N.V Hà CSDL.1 CSDL Tâm CSDL 7h 21 N.V Hà CSDL.1 CSDL Tâm 7h 21 T.V Huy CSDL.1 CTDL Xuân CSDL 7h 21 T.V Huy CSDL.1 CSDL Tâm 7h 21 Đ.T Lan CSDL.1 TRR Linh CSDL 7h 21 Đ.T Lan CSDL.1 CTDL Xuân 9h 22 N.V Hà CTDL.1 CTDL 9h 22 N.V Hà CTDL.1 CTDL Xuân 9h 22 Đ.T Lan CTDL.1 CTDL 9h 22 Đ.T Lan CTDL.1 CTDL Xuân 9h 22 L.T Linh CTDL.1 CTDL 9h 22 L.T Linh CTDL.1 TRR Linh 7h 23 T.V An TRR.1 TRR 7h 23 T.V An TRR.1 TRR Linh 7h 23 Đ.V Hưởng TRR.1 TRR 7h 23 Đ.V Hưởng TRR.1 Cơ sở dữ liệu 80 Cơ sở dữ liệu 81 R1 C– T– % Xét CS!G vi phạm 3NF(phụ thuộc bộ phận vào khoá), Cource Teacher %  Xét HR!C vi phạm 3NF, tách R22 thành CSDL Tâm R221(H,R,C) và R222(H,S,R) R1 % tách R2 thành R21(C,S,G) và R22(C,H,R,S). CTDL Xuân C– T– Cource Teacher TRR Linh R21 R222 CSDL Tâm R21 R22 C– S – Student G– H– R– S – Student CTDL Xuân C– S – Student G– C– H– R– S – Student Cource Group Hour Room TRR Linh Cource Group Cource Hour Room CSDL N.V Hà CSDL.1 7h 21 N.V Hà CSDL N.V Hà CSDL.1 CSDL 7h 21 N.V Hà CSDL T.V Huy CSDL.1 7h 21 T.V Huy R221 CSDL T.V Huy CSDL.1 CSDL 7h 21 T.V Huy CSDL Đ.T Lan CSDL.1 7h 21 Đ.T Lan C– H– R– CSDL Đ.T Lan CSDL.1 CSDL 7h 21 Đ.T Lan CTDL N.V Hà CTDL.1 9h 22 N.V Hà Cource Hour Room CTDL N.V Hà CTDL.1 CTDL 9h 22 N.V Hà CTDL Đ.T Lan CTDL.1 9h 22 Đ.T Lan CSDL 7h 21 CTDL Đ.T Lan CTDL.1 CTDL 9h 22 Đ.T Lan CTDL L.T Linh CTDL.1 9h 22 L.T Linh CTDL 9h 22 CTDL L.T Linh CTDL.1 CTDL 9h 22 L.T Linh TRR T.V An TRR.1 7h 23 T.V An TRR 7h 23 TRR T.V An TRR.1 TRR 7h 23 T.V An TRR Đ.V Hưởng TRR.1 7h 23 Đ.V Hưởng TRR Cơ sở dữ liệu Đ.V Hưởng TRR.1 TRR 7h 23 Đ.V Hưởng 82 Cơ sở dữ liệu 83
The End! Cơ sở dữ liệu 85 Cơ sở dữ liệu 90