Phụ thuộc hàm & Dạng chuẩn

Click to edit Master title style Click to edit Master text styles Second level Third level Fourth level Fifth level 11/5/2012 SGU - CNTT - Cơ sở dữ liệu ‹#› Phụ thuộc hàm & Dạng chuẩn ThS. Hoàng Mạnh Hà hoangha84@gmail.com https://sites.google.com/site/hoangha84 Nội dung Phụ thuộc hàm Dạng chuẩn SGU - CNTT - Cơ sở dữ liệu 2 Phụ thuộc hàm SGU - CNTT - Cơ sở dữ liệu 3 Định nghĩa Là một khái niệm quan trọng trong lý thuyết thiết kế lược đồ quan hệ. Một phụ thuộc hàm là một ràng buộc giữa 2 tập thuộc tính. Giả sử có lược đồ quan hệ R(A1,A2,…,An) và X, Y là tập con của {A1,A2,…,An} Ta nói: Y phụ thuộc hàm vào X (hay X xác định Y), ký hiệu XY nếu mỗi giá trị X trong R xác định duy nhất một giá trị Y trong R. SGU - CNTT - Cơ sở dữ liệu 4 Định nghĩa Nếu có X Y thì ta có: ∀r1, r2 ∈ R sao cho r1.X=r2.X thì r1.Y=r2.Y Xét lược đồ quan hệ: PHIM (TENPHIM, NAMSX, THOILUONG, LOAIPHIM, XUONGSX, DIENVIEN) SGU - CNTT - Cơ sở dữ liệu 5 Ví dụ TENPHIM  LOAIPHIM TENPHIM  THOILUONG TENPHIM  XUONGSX SGU - CNTT - Cơ sở dữ liệu 6 TEN PHIM NAMSX THOI LUONG LOAI PHIM XUONG SX DIENVIEN Star Wars 1977 124 Color Fox Carrie Fisher Star Wars 1977 124 Color Fox Mark Hamill Star Wars 1977 124 Color Fox Harrison Ford Mighty Ducks 1991 104 Color Disney Emilio Esteves Wayne’s World 1992 95 Color Paramount Dana Carvey Wayne’s World 1992 95 Color Paramount Mike Meyers Hệ luật Armstrong   SGU - CNTT - Cơ sở dữ liệu 7 Hệ luật Armstrong   SGU - CNTT - Cơ sở dữ liệu 8 Hệ quả từ tập phụ thuộc hàm Cho F là tập các phụ thuộc hàm định nghĩa trên R. Nếu có một phụ thuộc hàm f cũng thỏa với mọi thể hiện của R thì ta gọi f là phụ thuộc hàm hệ quả của F. VD: R(A, B, C, G, H, I) và tập phụ thuộc hàm F định nghĩa trên R: F={f1: A→B; f2: A→C; f3: CG→H; f4: CG→I; f5: B→H} Ta có f6: A→H là phụ thuộc hàm hệ quả từ F SGU - CNTT - Cơ sở dữ liệu 9 Bao đóng của tập phụ thuộc hàm Cho F là một tập các phụ thuộc hàm được định nghĩa trên R. Tập hợp các phụ thuộc hàm hệ quả từ F được gọi là bao đóng của F. Bao đóng của F ký hiệu là F+ Ta có F⊆F+ SGU - CNTT - Cơ sở dữ liệu 10 Thuật toán tìm bao đóng của F Bước 1: F+=F Bước 2: Áp dụng các luật dẫn Armstrong để tìm phụ thuộc hàm hệ quả f từ F+ Bổ sung f vào F+ Bước 3: Lặp lại bước 2 cho đến khi không thể tìm được f khác từ F+ SGU - CNTT - Cơ sở dữ liệu 11 Thuật toán tìm bao đóng của F Ví dụ: R(A, B, C) và F={f1: A → B; f2: B → C} F+={f1: A → B; f2: B → C; f3: A → C} SGU - CNTT - Cơ sở dữ liệu 12 Bao đóng của tập thuộc tính Cho F là tập các phụ thuộc hàm được định nghĩa trên R và tập thuộc tính X (X ⊆ R+) Bao đóng của tập thuộc tính X dựa trên F được ký hiệu là X+F X+F={Y | X → Y được suy dẫn từ F} SGU - CNTT - Cơ sở dữ liệu 13 Thuật toán tìm bao đóng của X   SGU - CNTT - Cơ sở dữ liệu 14 Thuật toán tìm bao đóng của X Ví dụ: Cho lược đồ R(A, B, C, D, E, G) và tập phụ thuộc hàm F={ f1:AB→C; f2: BC→AD; f3: D→E; f4: CG→B} Tìm (AB)+F ? (AB)+F= {A, B, C, D, E} SGU - CNTT - Cơ sở dữ liệu 15 Phụ thuộc hàm suy dẫn Cho phụ thuộc hàm f: X→Y, f suy dẫn từ F (ký hiệu F ⊢ f) nếu và chỉ nếu Y ⊆ (X)+F VD: f: AB→E suy dẫn từ F do E ∈ (AB)+F SGU - CNTT - Cơ sở dữ liệu 16 Tập phụ thuộc hàm tương đương   SGU - CNTT - Cơ sở dữ liệu 17 Phủ Một tập phụ thuộc hàm G được gọi là phủ của F nếu G tương đương với F (G ≡ F) Ví dụ: F = {A→BC; A→ D; CD → E} G= {A → BCE; A → ABD; CD → E} SGU - CNTT - Cơ sở dữ liệu 18 Phủ tối tiểu Phủ tối tiểu là một tập hợp các phụ thuộc hàm sao cho nếu ta loại bớt một phụ thuộc hàm trong đó thì tập phụ thuộc hàm còn lại không còn là một phủ của F. Phủ tối tiểu được định nghĩa thông qua 2 khái niệm phụ thuộc hàm đầy đủ và phụ thuộc hàm dư thừa. SGU - CNTT - Cơ sở dữ liệu 19 Phụ thuộc hàm đầy đủ Xét phụ thuộc hàm X → Y Nếu không có X’ ⊂ X sao cho F ≡ F – {X → Y} ∪ {X’ → Y} thì Y phụ thuộc đầy đủ vào X Nghĩa là: Y phụ thuộc hàm vào X và không phụ thuộc hàm vào tập con nào của X. Ví dụ: R(A, B, C, D, E, I) và F={A → BCD; BCD → E; CD → EI} F: BCD → E là phụ thuộc hàm không đầy đủ vì có phụ thuộc hàm CD → E SGU - CNTT - Cơ sở dữ liệu 20 Phụ thuộc hàm dư thừa Xét phụ thuộc hàm X → Y Nếu F ≡ F – {X → Y} thì X → Y được gọi là phụ thuộc hàm dư thừa. Nghĩa là: một phụ thuộc hàm f là dư thừa đối với F nếu ta bỏ f ra khỏi F và vẫn tìm lại được f từ tập phụ thuộc hàm đã loại bỏ f. Ví dụ: R(A, B, C, D) F={ A → B, B → A, B → C, A → C, C→ A} SGU - CNTT - Cơ sở dữ liệu 21 Phủ tối tiểu Cho một tập phụ thuộc hàm F sao cho mỗi vế phải chỉ chứa 1 thuộc tính. G được gọi là một phủ tối tiểu của F, ký hiệu G=PTT(F), nếu G là phủ của F và thỏa 2 điều kiện: G chỉ chứa phụ thuộc hàm đầy đủ Không ∃ X → Y ∈ G và X’ ⊂ X sao cho G ≡ G – {X → Y} ∪ {X’ → Y} G không chứa phụ thuộc hàm dư thừa Không ∃ X → Y ∈ G sao cho G ≡ G – {X → Y} SGU - CNTT - Cơ sở dữ liệu 22 Phủ tối tiểu Ví dụ: F = {A → B, B → A, B → C, A → C, C → A} TH1: F’={A → B, B → C, C → A} ≡ F TH2: F’’={A → B, B → A, A → C, C → A} ≡ F Một tập phụ thuộc hàm F có thể có nhiều phủ tối tiểu, số lượng phụ thuộc hàm trong các phủ tối tiểu có thể không bằng nhau. SGU - CNTT - Cơ sở dữ liệu 23 Thuật toán tìm PTT F’=F Bước 1: Phân rã vế phải Phân rã các PTH có vế phải nhiều hơn 1 TT Bước 2: Tìm các phụ thuộc hàm không đầy đủ Xử lý vế trái của các PTH trong F’ (Loại bỏ thuộc tính dư thừa): Tìm bao đóng của tập TT bên vế trái VD: f: AC → B Nếu A thừa thì C → B thuộc (F)+ nên ta tính (C)+. Nếu B thuộc (C)+ thì A là thừa và ngược lại.Tương tự nếu C thừa SGU - CNTT - Cơ sở dữ liệu 24 Thuật toán tìm PTT Bước 3: Loại bỏ các phụ thuộc hàm dư thừa Xét từng phụ thuộc hàm f: X → Y thuộc F’ Nếu (X+)F’ – f = Y thì f là thừa, có thể loại bỏ khỏi F’ còn ngược lại f không thừa. Kết quả F’ cuối cùng là PTT của F. LƯU Ý: Nên làm bước 3 trước bước 2 để giảm tính toán SGU - CNTT - Cơ sở dữ liệu 25 Bài tập PTT Cho tập quan hệ R = (A, B, C, D, E, G)F = { AC → B, B → ACD, ABC → D, ACE → BC, CD → AE } Cho tập quan hệ R(A,B,C,D) F={AB → CD, B → C, C → D} Cho tập quan hệ R = {ABCDEFGH} F = {AB → CDE; CD → E; F → G; AF → H} SGU - CNTT - Cơ sở dữ liệu 26 Định nghĩa khóa bằng PTH Cho R(R+) và một tập phụ thuộc hàm F trên R. R+ là tập thuộc tính của R. Cho K ⊂ R+, K là một khóa của R khi thỏa 2 điều kiện: K → R+ Không tồn tại K’ ⊂ K sao cho K’ → R+ SGU - CNTT - Cơ sở dữ liệu 27 Thuật toán tìm khóa   SGU - CNTT - Cơ sở dữ liệu 28 Thuật toán tìm khóa Nhận xét: số lượng tổ hợp có thể có của R+ là quá lớn. Do đó cần giới hạn lại số lượng tổ hợp Thuộc tính đích: là TT chỉ xuất hiện ở vế phải của tất cả các phụ thuộc hàm thuộc F+. TT đích không xuất hiện trong bất kỳ khóa nào của R. Thuộc tính nguồn: là TT chỉ xuất hiện ở vế trái. Mọi TT nguồn phải xuất hiện trong mọi khóa của R. SGU - CNTT - Cơ sở dữ liệu 29 Ví dụ R(ABCDEG) với F={AD→ B, EG→ A, BC→ G}. Xác định khóa của R. Vế trái: ADEGBC Vế phải: BAG  TT nguồn: DEC TT đích: không có TT còn lại: ABG Tổ hợp có thể: A, B, G, AB, AG, BG, ABG Các khóa có thể: DEC, DECA, DECB, DECG, DECAB… SGU - CNTT - Cơ sở dữ liệu 30 Ví dụ Tìm bao đóng của các khóa (DECA)+F =… (DECB)+F =… (DECG)+F =… (DECAB)+F =… Tìm tổ hợp nhỏ nhất có bao đóng bằng R+ SGU - CNTT - Cơ sở dữ liệu 31 Thuật toán tìm khóa Cho R(R+) và một tập phụ thuộc hàm F trên R. R+ là tập thuộc tính của R. K0=R+ A là thuộc tính thuộc R+. Nếu (K0 – A)+=R+ thì K1= K0 – A Lặp lại cho các thuộc tính còn lại của R+. SGU - CNTT - Cơ sở dữ liệu 32 Bài tập tìm khóa Cho tập quan hệ R={A,B,C,D,E} và F={AB→C, AC → B, BC → DE} Cho tập quan hệ R = {ABCDEFGH} F = {AB → CDE; CD → E; F → G; AF → H} SGU - CNTT - Cơ sở dữ liệu 33 Dạng chuẩn SGU - CNTT - Cơ sở dữ liệu 34 Lược đồ CSDL tốt Sự trùng lặp các giá trị trên các bộ: Giảm tối đa thông tin trùng lặp → giảm không gian lưu trữ. SGU - CNTT - Cơ sở dữ liệu 35 TEN PHIM NAMSX THOI LUONG LOAI PHIM XUONG SX DIENVIEN Star Wars 1977 124 Color Fox Carrie Fisher Star Wars 1977 124 Color Fox Mark Hamill Star Wars 1977 124 Color Fox Harrison Ford Mighty Ducks 1991 104 Color Disney Emilio Esteves Wayne’s World 1992 95 Color Paramount Dana Carvey Wayne’s World 1992 95 Color Paramount Mike Meyers Lược đồ CSDL tốt Khi lưu trữ thông tin trùng lặp còn xảy ra 3 vấn đề lớn: Thêm một bộ mới: phải thêm chính xác các giá trị trùng lặp. VD thêm 1 diễn viên mới cho phim Star Wars. Xóa một bộ: có khả năng gây mất thông tin. VD xóa diễn viên Emilio Esteves. Sửa giá trị: phải kiểm tra thông tin trùng lặp có còn nhất quán không. VD sửa thời lượng cho phim Star Wars. SGU - CNTT - Cơ sở dữ liệu 36 Lược đồ CSDL tốt Giá trị rỗng trong các bộ: Nếu một thuộc tính không áp dụng cho một bộ trong quan hệ (thuộc tính dư thừa) ta phải đặt giá trị null tại thuộc tính đó → lãng phí không gian và có thể ảnh hưởng đến việc hiểu nghĩa. Giá trị null có thể có nhiều nghĩa: Không áp dụng cho bộ Giá trị thuộc tính này của bộ là không biết Giá trị là xác định nhưng chưa được nhập. Trong 1 số tình huống thì null là hợp lệ, có thể sử dụng. SGU - CNTT - Cơ sở dữ liệu 37 Tiếp cận phân rã quan hệ Quan điểm: các quan hệ con của lược đồ CSDL ban đầu sẽ lần lượt được phân rã thành các quan hệ con với số lượng thuộc tính ít hơn sao cho cấu trúc kết quả Không còn trùng lặp thông tin Đạt được các tiêu chuẩn đề ra ở mức cao nhất. Quá trình phân rã là một quá trình được lặp lại với các quan hệ con nếu có thể phân rã được tiếp. SGU - CNTT - Cơ sở dữ liệu 38 Dạng chuẩn 1 Định nghĩa: Một quan hệ đạt dạng chuẩn 1 là quan hệ mà các giá trị trên từng thuộc tính phải là giá trị nguyên tố. Không thỏa DC1: Thỏa DC1: SGU - CNTT - Cơ sở dữ liệu 39 Tên phim Diễn viên Star Wars Carrie Fisher, Mark Hamill, Harrison Ford Tên phim Diễn viên Star Wars Carrie Fisher Star Wars Mark Hamill Star Wars Harrison Ford Dạng chuẩn 2 Định nghĩa: Một quan hệ đạt DC2 nếu và chỉ nếu nó đạt DC1 và tất cả các thuộc tính không khóa phụ thuộc đầy đủ vào khóa.  Cần xác định khóa của quan hệ trước SGU - CNTT - Cơ sở dữ liệu 40 Ví dụ dạng chuẩn 2 Quan hệ GIANGDAY với các thuộc tính: MS_CBGD: mã số cán bộ giảng dạy; T_CBGD: tên; HH_CBGD: học hàm; ML_TT: mức lương; MS_MH: mã số môn học; TSSV: tổng số sinh viên. F: {f1: MS_CBGD → T_CBGD, HH_CBGD, ML_TT; f2: HH_CBGD → ML_TT f3: MS_CBGD, MS_MH → TSSV} SGU - CNTT - Cơ sở dữ liệu 41 Ví dụ dạng chuẩn 2 Khóa của GIANGDAY: (MS_CBGD, MS_MH) Phụ thuộc hàm f1 làm các thuộc tính không khóa T_CBGD, HH_CBGD, ML_TT không phụ thuộc đầy đủ vào khóa (MS_CBGD, MS_MH) Tách phụ thuộc hàm không đầy đủ trên khóa ra khỏi quan hệ cũ và đổi tên quan hệ mới nếu cần. CANBO (MS_CBGD, T_CBGD, HH_CBGD, ML_TT) GIANGDAY (MS_CBGD, MS_MH, TSSV) SGU - CNTT - Cơ sở dữ liệu 42 Dạng chuẩn 3 Định nghĩa: một quan hệ đạt DC3 nếu nó đạt DC2 và tất cả thuộc tính không khóa không phụ thuộc bắc cầu vào khóa. VD: CANBO (MS_CBGD, T_CBGD, HH_CBGD, ML_TT) Phụ thuộc hàm f2: HH_CBGD → ML_TT Do đó ML_TT là thuộc tính không khóa phụ thuộc bắc cầu vào khóa SGU - CNTT - Cơ sở dữ liệu 43 Dạng chuẩn 3 Để đưa quan hệ thành DC3, phải loại bỏ phụ thuộc hàm gây ra vi phạm thành quan hệ mới và đổi tên nếu cần. CANBO (MS_CBGD, T_CBGD, HH_CBGD, ML_TT)  CANBO (MS_CBGD, T_CBGD, HH_CBGD) HOCHAM (HH_CBGD, ML_TT) SGU - CNTT - Cơ sở dữ liệu 44 Dạng chuẩn BCK Định nghĩa: Một quan hệ đạt dạng chuẩn BCK (Boyce Codd Kent) khi nó đạt DC3 và với mọi phụ thuộc hàm X → A, A ∉ X thì X là một siêu khóa của quan hệ. TT_PV(MA_UV, NGAY_PV, GIO_PV, MA_NV, PHONG_PV) F = { f1: MA_UV, NGAY_PV → GIO_PV, MA_NV, PHONG_PV; f2: MA_NV, NGAY_PV → PHONG_PV} TT_PV đạt DC3 nhưng không đạt DC BCK do f2 SGU - CNTT - Cơ sở dữ liệu 45 Dạng chuẩn BCK GIANGDAY (MS_CBGD, MS_MH, TSSV) CANBO (MS_CBGD, T_CBGD, HH_CBGD) HOCHAM (HH_CBGD, ML_TT)  Đạt DC3 và BCK SGU - CNTT - Cơ sở dữ liệu 46 Dạng chuẩn BCK Để biến đổi từ DC3 lên DC BCK bằng cách bỏ phụ thuộc hàm vi phạm ra khỏi quan hệ gốc thành các quan hệ mới và đổi tên nếu cần thiết. VD: TT_PV(MA_UV, NGAY_PV, GIO_PV, MA_NV, PHONG_PV)  PHONGVAN (MA_UV, NGAY_PV, GIO_PV, MA_NV) NV_PHONG (MA_NV, NGAY_PV, PHONG_PV) SGU - CNTT - Cơ sở dữ liệu 47 Dạng chuẩn của lược đồ CSDL Là dạng chuẩn thấp nhất của tất cả các quan hệ trong lược đồ CSDL đó. VD: lược đồ CSDL gồm 2 quan hệ A và B trong đó quan hệ A đạt DC2, quan hệ B đạt DC BCK  Lược đồ CSDL đạt DC2. SGU - CNTT - Cơ sở dữ liệu 48 Kết luận DC BCK là dạng chuẩn nhằm giảm thiểu thông tin trùng lặp và giải quyết tương đối hiệu quả việc kiểm tra phụ thuộc hàm. Tuy nhiên đôi khi việc kiểm tra phụ thuộc hàm lại không thuận tiện vì phải thực hiện trên nhiều quan hệ. Do đó phải lựa chọn 1 cấu trúc hợp lý, phù hợp với yêu cầu khai thác CSDL đôi khi ở dạng chuẩn thấp hơn nhưng việc kiểm tra phụ thuộc hàm và thời gian xử lý tốt hơn. SGU - CNTT - Cơ sở dữ liệu 49 Bài tập tổng hợp SGU - CNTT - Cơ sở dữ liệu 50 Bài tập tổng hợp Cho tập phụ thuộc hàm: Tìm bao đóng: A+, B+, AB+, AE+ SGU - CNTT - Cơ sở dữ liệu 51 Bài tập tổng hợp ABE có phải là khóa? SGU - CNTT - Cơ sở dữ liệu 52 Bài tập tổng hợp B G có thể suy từ F không? SGU - CNTT - Cơ sở dữ liệu 53 Bài tập tổng hợp 2 tập phụ thuộc hàm này có tương đương: SGU - CNTT - Cơ sở dữ liệu 54 Bài tập tổng hợp Tìm khóa của R = {A, B, C, D, E, F, G} với F = {ABC→DE, AB→D, DE→ABCF, E→C} Tìm khóa của R = {ABCDEFGH} với F = {AB → CDE; CD → E; F → G; AF → H} Tìm khóa của R = {ABCDE} và F={DE → A, B → C, E → AD}. SGU - CNTT - Cơ sở dữ liệu 55 Bài tập tổng hợp Cho Tìm phụ thuộc hàm dư thừa SGU - CNTT - Cơ sở dữ liệu 56 Bài tập tổng hợp Tìm phủ tối thiểu: F = {AB→D, B→C, AE→B, A→D, D→EF} SGU - CNTT - Cơ sở dữ liệu 57 Bài tập tổng hợp Cho R = ABCDEFGH, với tập phụ thuộc hàm sau: a. Tìm phủ tối thiểu b. Tìm tất cả khóa c. Xác định chuẩn hóa cao nhất mà R đạt được, chuẩn hóa R đến BCNF SGU - CNTT - Cơ sở dữ liệu 58 SGU - CNTT - Cơ sở dữ liệu 59