Cơ sở dữ liệu - Bài 4: Phụ thuộc hàm

CƠ SỞ DỮ LIỆU Bài 4: PHỤ THUỘC HÀM 13/08/2012 1 HVĐ – THQL BÀI TOÁN THỰC TẾ • Nghiên cứu hình thức các ràng buộc – Xây dựng cấu trúc bảo đảm các ràng buộc tự động thoả, do đó không cần lập trình – Đánh giá một lược đồ cơ sở dữ liệu 13/08/2012 HVĐ – THQL 2 MỤC TIÊU • Kiến thức: – Phụ thuộc hàm – Dạng chuẩn – Kỹ thuật tableaux • Kỹ năng: – Tìm phủ tối tiểu – Xác định dạng chuẩn – Đánh giá lược đồ CSDL • Yêu cầu: áp dụng thực tế 13/08/2012 HVĐ – THQL 3 NỘI DUNG • Phụ thuộc hàm • Phủ tối tiểu • Dạng chuẩn • Kỹ thuật tableaux • Đánh giá lược đồ CSDL • Khảo sát tình huống 13/08/2012 HVĐ – THQL 4 PHỤ THUỘC HÀM • Phụ thuộc hàm – Khái niệm – Bài toán thành viên • Phủ tối tiểu • Dạng chuẩn • Kỹ thuật tableaux • Đánh giá lược đồ CSDL • Khảo sát tình huống 13/08/2012 HVĐ – THQL 5 QUAN HỆ HÀM • Hình bên có – Quan hệ thuần túy – Quan hệ đường • Không có quan hệ hàm • Quan hệ hàm từ X vào Y • Quan hệ hàm từ Y vào X • Hàm từ X vào Y: – Mỗi x có duy nhất y – Nếu chiếu xuống XY • Bảng: x xuất hiện một lần • Lược đồ: X là siêu khoá 13/08/2012 6 HVĐ – THQL X Y MaSV MaLop S01 S02 S03 S04 L1 L2 L2 L2 PHỤ THUỘC HÀM • Phụ thuộc hàm là một loại ràng buộc toàn vẹn • Phụ thuộc hàm là luật – PTH X  Y ngụ ý: biết X sẽ xác định được Y – Quan hệ r thỏa X  Y • Các dòng có X giống nhau thì Y cũng vậy • r[X,Y] có X siêu khoá – Luật nên lưu riêng để áp dụng, ví dụ • HDSo  NLap • MaHG  Dgia • HDSo,MaHG  SoL 13/08/2012 7 HVĐ – THQL HDSo NLap MaHG DGia SoL H01 H01 H02 H02 12 12 14 14 H01 H02 H01 H03 12 5 12 20 5 2 4 3 HDSo NLap H01 H02 12 14 THẢO LUẬN • Tìm các phụ thuộc hàm • Tổ chức lại các bảng • Bài tập 1, 13a 13/08/2012 8 HVĐ – THQL MSV HT ML TL MM TM STC MGV TGV KH ĐT a Tèo 1 T x DSTT 5 p Minh T 6 a Tèo 1 T y LTHT 3 q Lan T 7 a Tèo 1 T z CSDL 3 p Minh T 9 b Nị 2 K x DSTT 5 q Lan T 5 b Nị 2 K y LTHT 3 q Lan T 7 b Nị 2 K z CSDL 3 p Minh T 8 c Bi 1 T x DSTT 5 p Minh T 6 c Bi 1 T y LTHT 3 q Lan T 4 c Bi 1 T z CSDL 3 p Minh T 8 QUY TẮC QUẢN LÝ • Cho cơ sở dữ liệu lưu các dữ liệu liên quan đến {Gviên, Sviên, Lớp , Môn, Khoa, Điểm, Tênsv} • Các quy tắc sau đây, cái nào là phụ thuộc hàm – Sinh viên thuộc về một lớp – Sinh viên thuộc về một khoa – Lớp thuộc về một khoa – Sinh viên học một môn phải có điểm – Sinh viên phải có tên – Mỗi lớp có không quá 30 sinh viên • Tổ chức lại các bảng 13/08/2012 9 HVĐ – THQL BÀI TOÁN THÀNH VIÊN • Ta nói f là hệ quả của F (hay được suy từ F) nếu một quan hệ r bất kỳ thoả F thì thoả f • Ký hiệu tập các phụ thuộc hàm hệ quả là F+ và được gọi là bao đóng của F • Bài toán kiểm tra f  F được gọi là bài toán thành viên 13/08/2012 HVĐ – THQL 10 LUẬT DẪN • Bộ luật – F1: XX – F2: XY suy ra XZY – F3: XY và XZ suy ra XYZ – F4: XYZ suy ra XY và XZ – F5: XY và YZ suy ra XZ – F6: XY và YZW suy ra XZW • Hệ tiên đề Amstrong {F1, F2, F6} • {AD,ABE,BIE,CDI,EC}⊨ AEDI 13/08/2012 HVĐ – THQL 11 BAO ĐÓNG • X+F = { A | (X  A)  F+ } • Áp dụng Y  X+F  X  Y (F+) • Kiểm tra tính thành viên f = AEDI đối với F = {AD,ABE,BIE,CDI,EC} – Tính AE+ = AEDCI – Ta có DI  AE + – Suy ra f F+ 13/08/2012 12 HVĐ – THQL THẢO LUẬN • Bài tập 2, 3, 4, 5 13/08/2012 HVĐ – THQL 13 PHỦ TỐI TIỂU • Phụ thuộc hàm • Phủ tối tiểu – Khái niệm – Thuật toán • Dạng chuẩn • Kỹ thuật tableaux • Đánh giá lược đồ CSDL • Khảo sát tình huống 13/08/2012 HVĐ – THQL 14 PHỦ TỐI TIỂU • Phụ thuộc hàm, như luật, đúng trong ngữ cảnh nhất định. Với ngữ cảnh cho trước chúng ta có tập phụ thuộc hàm • Xác định phụ thuộc hàm để lưu riêng một cách tuỳ tiện có thể dẫn đến dư thừa • Tập phụ thuộc hàm không dư thừa được gọi là phủ tối tiểu – Vế phải gồm một thuộc tính – Vế trái không dư thừa – Không có phụ thuộc hàm dư thừa • Dư thừa được xác định nhờ hệ tiên đề Armstrong 13/08/2012 15 HVĐ – THQL THẢO LUẬN • Các ký tự GSLMKNDHY là viết tắt của Gviên, Sviên, Lớp, Môn, Khoa, Ngành, Điểm, Hệ, học kỲ • Xét hai ngữ cảnh – Tổng quát: NM  Y, SM  D, N  K, L  HN, S  HN, M  H, LM  G – Trong một học kỳ: S  L • Với mỗi ngữ cảnh cho biết F có tối tiểu không 13/08/2012 16 HVĐ – THQL TÌM PHỦ TỐI TIỂU • Cơ sở: bài toán thành viên • Các bước – Phân rã – Rút gọn vế trái – Rút gọn phụ thuộc hàm 13/08/2012 17 HVĐ – THQL VÍ DỤ • Dùng thuật toán: – Phân rã – Rút gọn VT – Rút gọn PTH • Dùng bộ luật dẫn 13/08/2012 18 HVĐ – THQL A->C AB->C C->DI CD->I EC->AB EI->C A->C AB->C C->D C->I CD->I EC->A EC->B EI->C C A+=A EI+=EI A->C C->DI EC->AB EI->C A->C C->D C->I EC->A EC->B EI->C A+=ACDI B+=B C+=CDI D+=D E+=E I+=I THẢO LUẬN • Dùng luật • Dùng thuật toán 13/08/2012 19 HVĐ – THQL { S -> D, I -> B, IS -> Q, B -> O } { A -> BC, B -> AC, C -> A } { AB -> C, C -> A, BC -> D, ACD -> B, D -> EG, BE -> C, CG -> BD, CE -> AG } DƯ THỪA PHẢI • Tìm những thuộc tính xuất hiện ở vế phải nhiều lần (ví dụ D) • Chọn một PTH liên quan (ví dụ H->KDN) • Bỏ thuộc tính này, rồi tính bao đóng (ví dụ H+ =HKDN) • Kết luận (ví dụ H->KDN dư thừa D) R(KDHNMLG) F={ K -> D, H -> KDN, M -> G, HM -> L} 13/08/2012 20 HVĐ – THQL THỬ SỨC • Xét I và C->DI • Thử bỏ I, được C->D, tính C+ = CDI • Vậy C->DI dư thừa phải F = {A->C AB->C C->DI CD->I EC->AB EI->C} 13/08/2012 21 HVĐ – THQL DƯ THỪA TRÁI • Chọn một PTH có hơn 1 thuộc tính ở vế trái (ví dụ HNM->L) • Bỏ 1 thuộc tính, tính bao đóng (ví dụ HM+ =HMLKNDG) • Kết luận (ví dụ HNM->L dư thừa N) R(KDHNMLG) F={ K -> D, H -> KN, M -> G, HNM -> L} 13/08/2012 22 HVĐ – THQL THỬ SỨC • Xét CD -> I • Tính C+ = CDI, chứa D • Vậy CD -> I dư thừa trái F = {A->C AB->C C->DI CD->I EC->AB EI->C} 13/08/2012 23 HVĐ – THQL DẠNG CHUẨN • Phụ thuộc hàm • Phủ tối tiểu • Dạng chuẩn – Khái niệm – Bài toán tìm tập khoá – Bài toán xác định dạng chuẩn – Bài toán tìm tập phụ thuộc hàm chiếu • Kỹ thuật tableaux • Đánh giá lược đồ CSDL • Khảo sát tình huống 13/08/2012 HVĐ – THQL 24 VI PHẠM DẠNG CHUẨN • Dạng chuẩn là một khái niệm dùng để đo mức độ dư thừa trong lưu trữ, qua việc phát hiện các PTH • Tìm thấy 1 PTH là tìm ra 1 vi phạm dạng chuẩn • Trong các bảng trên, tìm thấy có các vi phạm dạng chuẩn sau – Ở bảng bên trái, là P  N – Ở bảng bên phải, là M  G 13/08/2012 HVĐ – THQL 25 HDSo NLap MaHG DGia SoL H01 H01 H02 H02 12 12 14 14 H01 H02 H01 H03 12 5 12 20 5 2 4 3 TẬP CÁC KHOÁ • Một phụ thuộc hàm vế trái chứa khoá không là một vi phạm dạng chuẩn • Một thuộc tính ở vế phải không tham gia vào bất kỳ khoá nào rất dễ được xử lý • Xét PTH X A, các loại vi phạm dạng chuẩn – A tham gia vào một khoá, vi phạm chuẩn BC – A không tham gia vào bất kỳ khoá nào • X không chứa trong bất kỳ khoá nào, vi phạm chuẩn 3 • X chứa trong một khoá, vi phạm chuẩn 2 13/08/2012 HVĐ – THQL 26 CÁC KHÁI NIỆM • Thuộc tính khoá và thuộc tính không khoá • Chuẩn BC • Chuẩn 3 và phụ thuộc bắc cầu • Chuẩn 2 và phụ thuộc đầy đủ 13/08/2012 HVĐ – THQL 27 DẠNG CHUẨN 1 • Mọi giá trị của thuộc tính là nguyên tố, theo nghĩa các thành phần con phải dùng hàm mới truy xuất được, chẳng hạn với Date nếu muốn biết Day ta phải dùng hàm Day() • Lược đồ quan hệ ở chuẩn 1 nếu tập giá trị của các thuộc tính là nguyên tố. • Lược đồ CSDL ở chuẩn 1 nếu tất cả các lược đồ con đều ở chuẩn 1 • Ta thừa nhận với mô hình quan hệ các lược đồ đều đạt chuẩn 1 13/08/2012 HVĐ – THQL 28 BÀI TOÁN TÌM TẬP KHOÁ • Xét lược đồ , với R = (STVCDP) và F = {S → T, V → SC, SD → PV } • Theo định nghĩa, phải kiểm tra 62 ứng viên • Nhận xét – Loại T, C và P, còn 7 ứng viên – Buộc D phải có, còn 4 ứng viên là {D, DS, DV, DSV} – Thử D (bỏ), thử DS (nhận, do đó loại DSV), thử DV (nhận) – Vậy tập khoá {DS, DV} 13/08/2012 HVĐ – THQL 29 GIỚI THIỆU THUẬT TOÁN • Xét lược đồ , với R = (GLMPB) và F = {L→ P, LM→ G, BL → M, BG → L, BP→ G} • Thực hiện – Phải chứa B, ta có 15 ứng viên là {B, BG, BL, BM, BP, BGL, BGM, BGP, BLM, BLP, BMP, BGLM, BGLP, BGMP, BLMP}; – Thử B (loại), còn 14 ứng viên. Thử BG (nhận, loại 6 ứng viên, còn {BL, BM, BP, BLM, BLP, BMP, BLMP}); – Thử BL (nhận, loại 3 ứng viên còn {BM, BP, BMP}); – Thử BM (loại), còn 2 ứng viên; – Thử BP (nhận, loại hết ứng viên) – Vậy tập khoá {BG, BL, BP} 13/08/2012 HVĐ – THQL 30 CÂY TÌM TẬP KHOÁ • Gốc • Phát triển 13/08/2012 HVĐ – THQL 31 R=(SDIBQO) F={S -> D, I -> B, IS -> Q, B -> O } IS+=R R=(GLMPB) F={L -> P, LM -> G, BL -> M, BG -> L BP -> G } R=(STVCDP) F={S -> T, V -> SC, SD -> PV } D+=D SV DS+=R DV+=R B+=B GLMP BG+=R BL+=R BM+=BM BP+=R THUẬT TOÁN TÌM TẬP KHOÁ • Tính: – Đỉnh gốc, X = R – VP, và – Tập bổ sung, Z = VT – X+ • Đỉnh là khóa nếu bao đóng bằng với R • Với mỗi đỉnh X không là khóa: – Xác định tập bổ sung (R’ – X+) – Phát triển cây với thuộc tính bổ sung mà không làm đỉnh mới có thuộc tính dư thừa 13/08/2012 HVĐ – THQL 32 THỬ SỨC • Gốc là E, tập ứng viên bổ sung R’ = {ACI} • Với E, phát triển 3 nhánh EA, EC, EI • EA, EC và EI đều là khóa • Vậy tập khóa là {EA, EC, EI} F = {A->C C->DI EC->AB EI->C} 13/08/2012 33 HVĐ – THQL THUẬT TOÁN XÁC ĐỊNH DC • Nếu không tìm thấy vi phạm thì lược đồ đạt chuẩn BC, kết thúc • Xác định tập các khoá • Nếu không tìm thấy vi phạm chuẩn 3, kết luận lược đồ đạt chuẩn 3, kết thúc • Nếu không tìm thấy vi phạm chuẩn 2, kết luận lược đồ đạt chuẩn 2, kết thúc • Kết luận lược đồ đạt chuẩn 1 13/08/2012 HVĐ – THQL 34 XÁC ĐỊNH DẠNG CHUẨN • R = (PMLGN), F = {PM LG, P  N} • Có vi phạm P  N • Tập khóa {PM} gồm 1 khóa duy nhất • Vi phạm P  N có – Vế trái N là thuộc tính không khóa – Vế phải P nằm trong khóa • Vậy lược đồ đạt chuẩn 1 13/08/2012 35 HVĐ – THQL THỬ SỨC • A -> C là 1 vi phạm, lược đồ không đạt chuẩn BC • Xác định tập khóa {EA, EC, EI} • C tham gia khóa, chưa thể kết luận thêm F = {A->C C->DI EC->AB EI->C} 13/08/2012 36 HVĐ – THQL THỬ SỨC • Kết luận lược đồ đạt chuẩn 1 F = {A->C C->DI EC->AB EI->C} 13/08/2012 37 HVĐ – THQL PTH vi phạm Chuẩn vi phạm A -> C BC C -> DI 2 CHIẾU CỦA TẬP PTH • Tính ABH(F), F = {A  C, B  D, CD  H} – Tính ABHF = {A, B, AB}; – Tính A+ = AC, B+ = BD, AB+ = R; – Suy ra ABH(F) = {AB H} • Thuật toán tính S(F): – Tính SF – Mỗi X thuộc, tính X+ – Suy ra S(F) 13/08/2012 HVĐ – THQL 38 THẢO LUẬN • Cho F = {AB  CD, C  D, D  C}, tính – ABC(F) – CD(F). • Bài tập 4a 13/08/2012 HVĐ – THQL 39 KỸ THUẬT TABLEAUX • Phụ thuộc hàm • Phủ tối tiểu • Dạng chuẩn • Kỹ thuật tableaux • Đánh giá lược đồ CSDL • Khảo sát tình huống 13/08/2012 HVĐ – THQL 40 KỸ THUẬT TABLEAUX • Với B → C, 2 dòng đầu sửa b4 thành b1 • Với A → D, dòng đầu và cuối, sửa b2 thành a4 • Không còn vi phạm • Lưu ý: không cần đánh số các giá trị a 13/08/2012 HVĐ – THQL 41 ĐÁNH GIÁ LƯỢC ĐỒ CSDL • Phụ thuộc hàm • Phủ tối tiểu • Dạng chuẩn • Kỹ thuật tableaux • Đánh giá lược đồ CSDL – Lược đồ phổ quát – Dạng chuẩn – Bảo toàn thông tin – Bảo toàn phụ thuộc • Khảo sát tình huống 13/08/2012 HVĐ – THQL 42 LƯỢC ĐỒ PHỔ QUÁT • Biết lược đồ quan hệ gốc • Xác định lược đồ quan hệ gốc • Ví dụ cơ sở dữ liệu bán hàng • Thảo luận cơ sở dữ liệu thể thao đội 13/08/2012 HVĐ – THQL 43 DẠNG CHUẨN CỦA LƯỢC ĐỒ CSDL • Xác định tập PTH chiếu • Dạng chuẩn thấp nhất của các lược đồ quan hệ • Nếu kiểm tra chuẩn BC, không cần chiếu tập PTH gốc 13/08/2012 HVĐ – THQL 44 KIỂM TRA BẢO TOÀN THÔNG TIN • Xác định quan hệ phổ quát • Lập bảng Tρ • Dùng quy trình thay thế đuổi, được Tρ * • Kết luận • Tuy nhiên, nếu phát hiện BTPT, chỉ cần kiểm tra lược đồ con chứa khóa của lược đồ gốc 13/08/2012 HVĐ – THQL 45 { (SD), (I B), (ISQ), (BO) } Tp (S D I B Q O) a a 1 2 3 4 5 6 a a 7 8 a 9 a 10 a 11 12 13 14 a 15 a Tp* (S D I B Q O) a a 1 2 3 4 5 6 a a 7 a a a a a a a 12 13 14 a 15 a R=(SDIBQO) F={S -> D, I -> B, IS -> Q, B -> O } THỬ SỨC F = {A->C C->DI EC->AB EI->C} ρ = {CDI, ECAB} 13/08/2012 46 HVĐ – THQL KIỂM TRA BẢO TOÀN PHỤ THUỘC • Khái niệm – Ép thoả (phụ thuộc hàm được bao) – Đặc trưng đầy đủ (phụ thuộc hàm được in) • Tính bao đóng không cần chiếu • Kiểm tra bảo toàn phụ thuộc – Với mỗi phụ thuộc hàm không được bao – Nếu không là thành viên, kết luận không bảo toàn – Kết luận bảo toàn 13/08/2012 HVĐ – THQL 47 VD KIỂM TRA BTPT 13/08/2012 HVĐ – THQL 48 F={ AB, BC, CD, DA } ={ (AB), (BC), (CD)} AB BC CD D DC DCB DCBA TRỞ LẠI MỤC TIÊU • Kiến thức: – Phụ thuộc hàm – Dạng chuẩn – Kỹ thuật tableaux • Kỹ năng: – Tìm phủ tối tiểu – Xác định dạng chuẩn – Đánh giá lược đồ CSDL • Yêu cầu: áp dụng thực tế 13/08/2012 HVĐ – THQL 49 KHẢO SÁT TÌNH HUỐNG • Phụ thuộc hàm • Phủ tối tiểu • Dạng chuẩn • Kỹ thuật tableaux • Khảo sát tình huống 13/08/2012 HVĐ – THQL 50 BÁN HÀNG • R = (PNMLG), tìm F: F = {PM NLG, P  N} • Tìm phủ tối tiểu: PTT(F) = {PM LG, P  N} • Xác định dạng chuẩn: đạt dạng chuẩn 1 • Lưu trong 2 lược đồ R1 = (PMLG), R2 = (PN) – Tìm PMLG(F) và xác định dạng chuẩn của R1 – Tìm PN(F) và xác định dạng chuẩn của R2 13/08/2012 HVĐ – THQL 51 THẢO LUẬN • Tìm F • Xác định dạng chuẩn 13/08/2012 HVĐ – THQL 52 HDSo NLap MaHG DGia SoL H01 H01 H02 H02 12 12 14 14 H01 H02 H01 H03 12 5 12 20 5 2 4 3 PHÂN CÔNG GIẢNG DẠY • Xét lược đồ (GLM) với F = {G  M, LM  G} • Xác định dạng chuẩn – Có vi phạm chuẩn BC: G  M – Tìm tập khoá: {LM, LG} – Không có vi phạm chuẩn 3 – Không có vi phạm chuẩn 2 – Vậy lược đồ đạt chuẩn 3 • Để ý: nếu lưu riêng {GM}, chúng ta được phân rã {(GM), (GL)} không bảo toàn phụ thuộc. Nhưng nếu vẫn giữ lại (GML) và cài đặt 1 ràng buộc tồn tại thay cho PTH, được phân rã đặc trưng đầy đủ F và đạt chuẩn BC 13/08/2012 HVĐ – THQL 53 KẾT LUẬN • Phụ thuộc hàm: Là quan hệ hàm, cho thấy có dư thừa trong lưu trữ; Lưu riêng là một giải pháp • Ta có bài toán tìm phủ tối tiểu • Dạng chuẩn: Đo mức độ dư thừa trong lưu trữ • Ta có bài toán tìm tất cả các khoá • Phân rã là cách tăng chuẩn hơn nữa đạt cấu trúc đẹp (ép thỏa hoặc đặc trưng F) • Ta có bài toán đánh giá – Có thể xác định chuẩn của phân rã mà không phải chiếu F – Có thể kiểm tra BTPT không cần chiếu F – Kiểm tra tính BTTT dùng kỹ thuật tableaux • Bổ sung các ràng buộc tồn tại để được phân rã đạt chuẩn BC, đặc trưng đầy đủ F 13/08/2012 54 HVĐ – THQL