Phụ thuộc hàm đầy đủ là gì năm 2024

• 1. và các dạng chuẩn ( Functional Dependency and Normal Forms) Giảng viên: PGS.TS. Đỗ Phúc Khoa Hệ thống thông tin Trường Đại học Công nghệ thông tin, ĐHQG-HCM Ôn thi cao học CNTT năm 2009 2 Nội dung Phụ thuộc hàm Hệ tiên đề Armstrong Bao đóng của tập thuộc tính Bài toán thành viên Phủ tối tiểu Khóa và thuật toán tìm khóa Các dạng chuẩn Chuẩn hóa lược đồ quan hệ Các thuật toán kiểm tra phân rã nối không mất tin Thuật toán phân rã LĐQH đạt DC3 3 Phụ thuộc hàm Functional Dependencies (1) PTH (FDs) được dùng để đo mức độ hoàn thiện của thiết kế các quan hệ PTH và khóa được dùng để xác định dạng chuẩn của quan hệ PTH là các ràng buộc (constraints) được suy từ ý nghĩa và các liên hệ giũa các thuộc tính dữ liệu 4 Định nghĩa phụ thuộc hàm Functional Dependencies (2) X -> Y đúng nếu bất kỳ khi nào hai bộ (tuple) có cùng giá trị X phải có cùng giá trị Y Với bất kỳ hai bộ t1 và t2 trong thể hiện quan hệ r(R): Nếu t1[X]=t2[X] thì t1[Y]=t2[Y] X -> Y trong R xác định ràng buộc trên tất cả thể hiện r(R) Ký hiệu X -> Y ( đọc là “X xác định duy nhất Y”) PTH được suy từ các ràng buộc trong thế giới thực trên các thuộc tính. 5 Ví dụ về phụ thuộc hàm (1) Mã nhân viên xác định tên nhân viên SSN -> ENAME Mã đề án xác định tên đề án và địa điểm PNUMBER -> {PNAME, PLOCATION} Mã nhân viên và mã đề án xác định giờ làm việc trong tuần của nhân viên cho đề án {SSN, PNUMBER} -> HOURS 6 Ví dụ về ràng buộc PTH (2) PTH là một tính chất của các thuộc tính trong lược đồ R Ràng buộc phải thỏa trên tất cả các thể hiện của quan hệ r(R) Nếu K là khóa của R thì K xác định phụ thuộc với tất cả các thuộc tính của R (vì chúng ta không bao giờ có hai bộ phân biệt mà t1[K]=t2[K])
• 2. tất cả PTH khả dĩ Cho thể hiện của quan hệ, tìm tất cả các PTH khả dĩ: R ( A B C) ---- 1 2 4 1 2 4 2 5 7 3 5 7 Các PTH: A->B, A->C, B->C,AB->C,…. Thuật toán ? 8 Tính F+, bao đóng của tập các PTH F Khi thiết kế CSDL quan hệ,chúng ta bắt đầu bằng cách xem xét tập các PTH khả dĩ. Khảo sát được tất cả các PTH là điều quan trọng, do vậy làm thế nào để có tất cả PTH. Bao đóng (closure) của tập PTH F là tập tất cả PTH có thể suy diễn logic từ F. Ta ký hiệu bao đóng của F là F+ Ta tính F+ bằng cách áp dùng hệ tiên đề Armstrong 9 Các luật suy diễn cho PTH (1) Cho tập PTH F, ta có thể suy ra thêm các PTH khác thỏa. Hệ tiên đề Armstrong: IR1. (Luật phản xạ) Nếu Y ⊆ X, thì X -> Y Vd: ABC BC IR2. (Luật tăng trưởng) nếu X -> Y thì XZ -> YZ Vd: nếu C D thì ABC ABD IR3. (Luật bắc cầu) Nếu X -> Y và Y -> Z thì X -> Z Vd: Nếu AB CD và CD EF thì AB EF Hệ tiên đề Armstrong là đúng và đủ 10 Các luật suy diễn khác của PTH (2) Có thể suy thêm các luật hữu ích khác từ hệ tiên đề Armstrong: (Luật hợp) Nếu X -> Y và X -> Z thì X -> YZ Vd: Nếu AB CD và AB EF thì AB CDEF (Luật tách) Nếu X -> YZ thì X -> Y và X -> Z Vd: Nếu AB CDEF thì AB CD và AB EF và AB C và AB D và AB E và AB F (Luật bắc cầu giả) Nếu X -> Y và WY -> Z thì WX->Z Vd: Nếu AB EF và DEF G thì ABD G 11 Bài tập: Cho quan hệ R = (A, B, C, G, H, I) và tập PTH: F = {A B, A C, CG H, CG I, B H} Dùng hệ tiên đề Armstrong và các luật mở rộng của nó để tính F+ (Luật phản xạ) Nếu Y ⊆ X, thì X -> Y (Luật tăng trưởng) Nếu X -> Y thì XZ -> YZ (Luật bắc cầu) Nếu X -> Y và Y -> Z thì X -> Z (Luật hợp) Nếu X -> Y và X -> Z thì X -> YZ (Luật tách) Nếu X -> YZ thì X -> Y và X -> Z (Luật bắc cầu giả) Nếu X -> Y và WY -> Z thì WX -> Z 12 Áp dụng hệ tiên đề Armstrong Bài tập: Hãy dùng hệ tiên đề Armstrong để chứng minh: Nếu X -> Y và U -> V thì XU -> YV CM: 1. X -> Y ( gt) 2. XU-> YU, (tăng trưởng U vào (1) ) 3. U -> V (gt) 4. YU -> YV (tăng trưởng Y vào (3) 5. XU -> YV ( bắc cầu (2) và (4) )
• 3. tập thuộc tính The Closure of Attribute Sets 14 Bao đóng của tập thuộc tính F+ có thể có kích thước lớn, tìm F+ mất nhiều công sức Nếu chúng ta có thể xác định duy nhất tất cả thuộc tính trong R bằng một tập con thuộc tính X thì X là siêu khóa của R Bao đóng của X trên F (được ký hiệu là X+) là tập con của tập thuộc tính được xác định duy nhất bởi X qua các PTH trong F 15 Thuật toán tính X+ ( bao đóng của X trên F) X+ = X // khởi tạo repeat oldX+ = X+ for each FD Y Z in F do // kiểm tra từng PTH if Y is a subset of X+, then // nếu vế trái trong X+ X+ = X+ U Z // thêm vế phải vào X+ until X+ == oldX+ // lặp trong khi X+ thay đổi 16 Ví dụ tính bao đóng của tập thuộc tính R=(A,B,C,D,E,H) F { AB → C, BC → AD, D → E, CE → B} How to compute closure of {A,B}, i.e., {A,B}+? 1. Start with X={A,B} 2. Add C to X due to AB → C; X={A,B,C} 3. Add A,D to X due to BC → AD; X={A,B,C,D} 4. Add E to X due to D → E; X={A,B,C,D,E} 5. No more attributes can be added to X 6. {A,B}+ = {A,B,C,D,E} 17 Ví dụ tính bao đóng X+ Cho quan hệ R = (A, B, C, G, H, I) và tập PTH F = {A B, A C, CG H, CG I, B H}, Tính (AG)+ ? Ta muốn kiểm tra AG là siêu khóa của R. Dùng thuật toán tính bao đóng (AG)+. Nếu (AG)+ chứa tất cả thuộc tính của R thì AG là siêu khóa của R. 18 Ví dụ tiếp theo Cho R = (A, B, C, G, H, I) và F = {A B, A C, CG H, CG I, B H}, tính(AG)+ X+ = X repeat oldX+ = X+ for each FD Y Z in F do if Y is a subset of X+, then X+ = X+ U Z until X+ == oldX+
• 4. = { AB -> E, BE -> I, E -> C, CI -> D } Chứng minh AB -> CD suy được từ F. Simple Proof: (AB)+ = ABEICD which includes CD. Proof using Armstrong's Axioms: 1. AB > E, Given 2. E > C, Given 3. AB > C, Transitivity on (1) and (2) 4. AB > BE, Augment (1) by B 5. BE > I, Given 20 Tiếp theo 6. AB > I, Transitivity on (4) and (5) 7. ABC > CI, Augment (6) by C 8. AB > ABC, Augment (3) by AB 9. AB > CI, Transitivity on (7) and (8) 10. CI > D, Given 11. AB > D, Transitivity on (9) and (10) 12. ABC > CD, Augment (11) by C 13. AB --> CD, Transitivity on (8) and (12) Tìm khóa Find Keys 22 Định nghĩa khóa và các thuộc tính tham gia vào khóa (1) Siêu khóa (superkey) của một lược đồ quan hệ R = {A1, A2, ...., An} là tập thuộc tính S ⊆ R thỏa tính chất không có hai bộ t1 và t2 trong một trạng thái hợp lệ r của R mà t1[S] = t2[S] Khóa ( key) K là siêu khóa với tính chất bổ sung là khi xóa thuộc tính nào khỏi K sẽ khiến K không còn là siêu khóa. 23 Định nghĩa khóa và các thuộc tính tham gia vào khóa (2) Nếu lược đồ quan hệ có nhiều hơn một khóa, mỗi khóa sẽ được gọi là khóa dự tuyển (candidate key). Một trong các khóa dự tuyển được lựa chọn làm khóa chính (primary key), các khóa còn lại làm khóa phụ (secondary keys). Thuộc tính khóa là thuộc tính nằm trong một khóa dự tuyển. Thuộc tính không khóa không phải là thuộc tính khóa 24 Khóa của quan hệ Định nghĩa: Cho quan hệ r( R ), tập K ⊂ R được gọi là khóa của quan hệ r nếu:K+=R nếu bớt một phần tử khỏi K thì bao đóng của nó sẽ khác R. Như thế tập K ⊂ R nếu K+=R và ( K A )+ ≠ R , ∀ A ⊂ R. Một quan hệ có thể có nhiều khóa.
• 5. khóa Cho R = { A, B, C, D, E, G } và F= {AB->C, D->EG , BE -> C , BC -> D , CG ->BD, ACD ->B, CE -> AG} Ta sẽ thấy các tập thuộc tính: K1 = { A, B} , K2 = {B,E} , K3={C,G} , K4={C,E} , K5 = {C,D}, K6={B,C} đều là khóa 26 Tìm khóa (1) Gọi LHS là tập các thuộc tính nằm ở vế trái của các PTH. Đây là tập các ứng viên của siêu khóa. Dùng bao đóng của tập thuộc tính và tính chất của siêu khóa để kiểm tra ứng viên có có phải là siêu khóa hay không? Nếu không phải thì bỏ qua ứng viên đó. 27 Vế trái CHRS, dàn các tập hợp con của CHRS 28 Tìm khóa (1) Nếu ứng viên là siêu khóa thì tiếp tục kiểm tra các tập con của ứng viên này. Lặp lại cho đến khi gặp siêu khóa nhỏ nhất Siêu khóa nhỏ nhất là khóa dự tuyển (candidate keys) 29 Ví dụ tìm khóa (1) Cho LĐQH r(R) với R = {A, B, C, D, E, G, H,I} và tập PTH F F={ AB -> CDEFGH, C -> BEI, G -> H } Tìm tất cả các khóa dự tuyển của LĐQH trên và chỉ định khóa chính ? 30 Ví dụ tìm khóa (2) Bước 1: Tìm siêu khóa Tập LHS : ABCG Bước 2: Kiểm tra các tập con để tìm siêu khóa ; tập con nhỏ nhất để tìm khó dự tuyển Kiểm tra ABC ABC+ = ABCDEGHI =R
• 6. khóa (3) Kiểm tra ACG ACG+= ABCDEGHI =R Kiểm tra BCG BCG+= BCGEHI ≠ R ? KHÔNG Can ABG ABG+ = ABCDEGHI =R VẬy ABC, ABG, ACG là các siêu khóa 32 Ví dụ tìm khóa (4) Lặp lại bước 2 cho ABC: Xét AB AB+ = ABCDEGHI = R Xét AC AC+ = ABCDEGHI = R Xét BC determine A? No BC+ = BCEI ≠ R ? KHÔNG Vậy AB và AC là siêu khóa 33 Ví dụ tìm khóa (5) Lặp lại bước 2 cho ACG: Xét AC AC+ = ABCDEGHI = R Xét AG AG+ = AGH ≠ R ? KHÔNG Xét CG CG+ = CGBEHI ≠ R ? KHÔNG Vậy AC là siêu khóa 34 Ví dụ tìm khóa (6) Lặp lại bước 2 cho ABG: Xét AB AB+=ABCDEGHI = R Xét AG AG+ = AGH ≠ R ? KHÔNG Xét BG BG+= BGH ≠ R ? KHÔNG Vậy AB là siêu khóa 35 Ví dụ tìm khóa (7) Tiếp tục lặp bước 2 cho AB: Xét A A+= A ≠ R Xét B B+= B ≠ R Vậy AB là siêu khóa nhỏ nhất (minimal superkey) 36 Ví dụ tìm khóa (8) Tiếp tục lặp bước 2 cho AC: Xét A A+= A ≠ R Xét C C+=CBEI ≠ R Vậy AC là siêu khóa nhỏ nhất Tóm lại ta có AB và AC là các khóa dự tuyển, chọn một trong hai làm khóa chính
• 7. khóa: cho R = { A,B,C,D,E,G,H,I} F= { AC → B, BI → ACD, ABC → D , H → I , ACE → BCG , CG → AE } Tìm khóa ? (1) Bước 1: Gán K = R = {A,B,C,D,E,G,H,I} Bước 2: Lần lượt loại các thuộc tính của K 38 Tìm khóa ? (1) Loại phần tử A: ta có {B,C,D,E,G,H,I}+ = R vì pth CG → AE khiến A thuộc về {B,C,D,E,G,H,I}+ nên K = {B,C,D,E,G,H,I}. Loại phần tử B, ta có {C,D,E,G,H,I}+ = R vì pth CG → AE khiến A thuộc về {C,D,E,G,H,I}+ và pth AC → B nên K {C,D,E,G,H,I}. 39 Tìm khóa ? ( 2) Loại phần tử C, ta có {D,E,G,H,I}+ ≠ R nên K vẫn là {C, D,E,G,H,I} Loại phần tử D, ta có: {C, E,G,H,I}+ = R vì pth CG → AE khiến A thuộc về {C, E,G,H,I}+ và pth AC → B nên K ={C,E,G,H,I}. Loại phần tử E, ta có: {C, G,H,I}+ = R vì pth CG → AE , AC → B , ABC→ D nên K ={C,G,H,I}. 40 Tìm khóa ? (3) Loại phần tử G, ta có: {C, H,I}+ ≠ R nên K vẫn là {C, G,H,I}. Loại phần tử H, ta có: {C, G,I}+ ≠ R nên K vẫn là {C, G,H,I}. Loại phần tử I, ta có: {C,G,H}+ = R vì CG → AE , AC → B, ABC→ D nên K={C,G,H}. Vậy K={ C,G,H} là một khóa của r ( R ) 41 Bài tập 1 Cho LĐQH r( R) với R=ABCD và tập PTH F ={AB->C, C->D, D->A} Tìm các khóa dự tuyển ? Xét các tập con của ABCD Khóa AB,DB AB+=ABCD=R và DB=DBAC=R 42 Bài tập 2 Cho LĐQH r( R) với R=ABCD và tập PTH F ={AB->C, B->D, D->B} Tìm các khóa dự tuyển ? Xét các tập con của ABD Khóa AB,AD AB+=ABCD=R và AD=DBAC=R
• 8. tập PTH F={XY->W, Y->Z, WZ->P, WP->QR, Q->X} CM XY->P có thể suy được từ F (1) Ta có XY-> W ( cho) (2) Ta có WZ->P (cho) (3)XYZ->P ( bắc cầu giả (1) và (2) (4) Y->Z ( cho) (5) XY->P ( bắc cầu giả (4) và (3) Có thể dùng bao đóng XY+=XYWZPQR đpcm Tương đương giữa các tập PTH 45 Bài toán thành viên Procedure Member Vào: F và PTH X → Y Ra : Đúng nếu F |= X → Y và Sai nếu nguợc lại Cách thức: Member(F, X → Y) Begin If Y ⊂ Closure(X,F) Then return (True) Else Return (False) End 46 Tương đương của tập các PTH Hai tập PTH F và G là tương đương nếu: Mọi PTH của F đều có thể suy được từ G và Mọi PTH của G đều có thể suy được từ F Do vậy F và G là tương đương nếu F + = G + Định nghĩa: F phủ G nếu mọi PTH của G đều suy được từ F ( G + ⊆ F +) F và G là tương đương nếu F phủ G và G phủ F 47 Thuật toán DERIVES kiểm tra F |= G Vào : hai tập PTH F và G Ra: Đúng nếu F |= G và sai nếu ngược lại. Cách thức: DERIVES (F,G) Begin V:= true; For each X → Y ∈ G do V := V AND member(F, X → Y) Return (V); End. Dựa trên hàm DERIVES để xây dựng hàm tương đương của hai tập PTH. 48 Thuật toán EQUIVALENCE kiểm tra F tương đương G Vào: hai tập PTH F và G Ra: Đúng nếu F tương đương G, sai nếu ngược lại Cách thức EQUIVALENCE( F, G) Begin V := Derives (F,G) AND Derives(G,F) Return (V) End.
• 9. tra tương đương Kiểm tra 2 tập PTH tương đương? Giải thích lý do F = { AB -> C, B -> C, A -> D } G = { A -> B, B -> C, C -> D } Giải: Hai tập PTH F và G là không tương đương vì PTH A -> B ∈ G nhưng không thể suy được từ F ( Bao đóng A+ trên F là AD và không chứa B). PTH C -> D ∈ G cũng không suy được từ F ( Bao đóng C+ trên F là C and và cũng không chứa D ) 50 Phủ của tập PTH, tập PTH tương đương Cho F và G là tập các PTH, ta nói F tương đương với G và ký hiệu F ≡ G nếu F+= G+. Nếu F và G là tương đương thì ta nói F phủ G hay G phủ F. 51 Tương đương giữa 2 tập PTH Bài tập: Cho quan hệ Q(ABCDE) với: F = {A BC , A D CD E } và G = { A BCE A ABD CD E } 52 Tương đương giữa 2 tập PTH Ta cần CM: F ╞ G ⇔ F ├ G Xét PTH A E ∈ G suy được từ F nhờ vào các luật dẫn.Trong F,ta có: {A C; A D}├ {A CD; CD ├ E} ├ A E (bắc cầu) Kết luận: F ╞ G Ta nhận thấy F ⊆ G , do đó hiển nhiên G ╞ F Kết luận: F ≡ G 53 PTH đầy đủ Cho quan hệ r(U), F và X,Y ⊂ U, PTH f: X → Y∈ F là đầy đủ với X nếu không tồn tại X’ ⊂ X sao cho F|=X’→ Y. 54 Phủ tối tiểu của PTH Minimal Covers of FDs (1) Tập PTH là tối tiểu nếu thỏa các điều kiện sau: (1) Mọi PTH của F đều có một thuộc tính duy nhất ở vế phải (RHS). (2) Không thể loại bất kỳ PTH nào khỏi F mà tập các PTH còn lại vẫn tương đương với F. (3) Không thể thay thế PTH X -> A của F với PTH Y -> A khi Y ⊂ X mà vẫn có tập PTH tương đương với F (tất cả các PTH đều là PTH đầy đủ)
• 10. của PTH Mọi tập PTH đều tương đương với một phủ tối tiểu Có thể tương đương với nhiều phủ tiểu Có thuật toán để tính phủ tối tiểu 56 Thuật toán tìm phủ tối thiểu của F MINIMALCOVER(F,G) Vào: tập phụ thuộc hàm F Ra: G là phủ tối thiểu của F G := F Thay thế từng PTH X { A, A2, . . . , An} trong G bằng các PTH X A1, X A2, . . . , X An FOR EACH PTH X A trong G FOR EACH B ∈ X IF ( G { X A} ) ∪ ( X {B}) A ) tương đương với G Then Thay X A bằng ( X {B}) A trong G FOR EACH X A trong G IF ( G { X A} ) tương đương với G then loại X A khỏi G RETURN (G) END. 57 Ví dụ tìm phủ tối thiểu Cho tập thuộc tính R = {PCHART} và tập phụ thuộc hàm F như sau: F = { P → CHART CH → PART C → T A → R } 58 Các bước của thuật toán (1) Bước 1: G = F. Bước 2: G = { P → C;P → H; P→ A; P→ R; P→T; CH → P; CH → A; CH → R; CH → T; C → T; A → R } ( 11 PTH) Buớc 3: Kiểm tra PTH đầy đủ. Xóa lần lượt các thuộc tính trong vế trái của các PTH mà vế trái có nhiều thuộc tính, ví dụ CH → P; CH → A; CH → R; CH → T (Vế trái có 2 thuộc tính). 59 Các bước của thuật toán (2) 3.a. (Xóa thuộc tính C từ CH → P), chứng tỏ có thể suy H → P từ G. (sai) 3.b. (Xóa thuộc tính H from CH → P) chứng tỏ có thể suy C→P có thể được suy ra từ G. (sai) 3.c.(Xóa thuộc tính C từ CH → A) chứng tỏ có thể suy H→A từ G. (sai) 3.d.(Xóa thuộc tính h từ CH → A) chứng tỏ có thể suy C→A từ G. (sai) 60 Các bước của thuật toán (3) 3.e.(Xóa thuộc tính C từ CH → R) chứng tỏ có thể suy H→R từ G. (sai) 3.f.(Xóa thuộc tính H từ CH → R) chứng tỏ có thể suy C→R từ G. (sai) 3.g(Xóa thuộc tính C từ CH → T) chứng tỏ có thể suy H→T từ G. (sai) 3.h. (Xóa thuộc tính H từ CH → T) chứng tỏ có thể suy C→T từ G. (đúng)
• 11. thuật toán (4) Do vậy, vào cuối bước 3, ta có : G= { P→C; P→H; P→ A; P→ R; P→ T; CH → P; CH → A; CH → R; C→ T; A→ R } ( 10 PTH) Loại CH → T 62 Các bước của thuật toán (5) Bước 4: Kiểm tra có thể loại bỏ các PTH trong G . Mỗi lần loại bỏ sẽ phát sinh tập các PTH mới G'. 4.a. Có thể loại P→C ? (không ) 4.b. Có thể loại P→ H? (không) 4.c. Có thể loại P→A ? (không) 4.d. Có thể loại P→R ? (được vì P→A và A→R) 4.e. Có thể loại P→ T ? (được vì P→C và C→T) 4.f. Có thể loại CH → P ? (không) 4.g. Có thể loại CH → A ? (được, vì CH→ P và P→A) 4.h. Có thể loại CH→ R ? (được vì CH→ P and P→R) 63 Các bước của thuật toán (6) 4.i. Có thể loại C→ T ? (không) 4.j. Có thể loại A→ R ? (không) Do vậy vào cuối bước 4, ta có: G = { P→C; P→H; P→A; CH -> P; C -> T; A → R } Kết quả: Phủ tối thiểu của F là : G = { P→C; P→ H; P→ A; CH→ P; C→ T; A→ R} 64 Bài tập tìm phủ tối tiểu Cho R = ABCDE và F = { A -> C, BD -> E, B -> D, B -> E, C -> AD }. 1) Tìm phủ tối thiểu của PTT(F) ? Đáp PTT(F)= { A-> C, B -> D, B-> E, C-> A, C-> D } 2) Tìm tất cả các khóa của F ? Đáp: AB và BC Các dạng chuẩn Normal Forms 66 Các dạng chuẩn Dạng chuẩn 1 (DC1): First Normal Form (1NF) Dạng chuẩn 2 (DC2): Second Normal Form (2NF) Dạng chuẩn 3 (DC3): Third Normal Form (3NF) Để chuẩn hóa 1NF-> 2NF-> 3NF
• 12. thuộc hàm riêng phần partial functional dependency X → A được gọi là phụ thuộc hàm riêng phần nếu tồn tại Y ⊂ X để cho Y → A. Phụ thuộc hàm đầy đủ full functional dependency X → A được gọi là phụ thuộc hàm đầy đủ nếu không tồn tại Y ⊂ X để cho Y → A. Phụ thuộc bắc cầu transitive dependency X → A được gọi là phụ thuộc bắc cầu nếu tồn tại Y để cho X → Y, Y → A, Y −/→ X và A ∉ XY. 68 Dạng chuẩn 1 (1NF - First Normal Form) Định nghĩa Quan hệ R ở dạng chuẩn 1 (1NF - First Normal Form) nếu mọi thuộc tính của R đều chứa các giá trị nguyên tố (atomic value), giá trị này không là một danh sách các giá trị hoặc các giá trị phức hợp (composite value). Các thuộc tính của quan hệ R Không là thuộc tính đa trị (multivalued attribute). Không là thuộc tính phức hợp (composite attribute). 69 Ví dụ quan hệ không ở DC1 {435}DienVo Ngoc1311 {312,400,435 } MocLe Son1412 {312,512}1311DienTran An1235 MANOILAM)MACBPTLOAINGHEHOTEN(MACNCNHAN Lý do là thuộc tính MANOILAM có các giá trị không phải là nguyên tử. Một quan hệ ở 1NF nếu các gía trị của tất cả thuộc tính trong quan hệ là nguyên tử. Ví dụ quan hệ sau đây không phải là 1NF 70 Dạng chuẩn 2 Định nghĩa Quan hệ R ở dạng chuẩn 2 (2NF - Second Normal Form) nếu R ở dạng chuẩn 1 và mọi thuộc tính không khóa đều phụ thuộc hàm đầy đủ vào mọi khóa của R. 71 Ví dụ về quan hệ ở DC2 Ví dụ: Cho LĐQH R = {A,B,C,D,E,G} và F = { A → BC, C → DE, E → G } Ta thấy A là khóa vì A+ = R ( tập thuộc tính của quan hệ). Các thuộc tính không khóa là {B,C,D,E,G}. Do khóa chỉ có một thuộc tính nên quan hệ R ở 2NF. 72 Dạng chuẩn 3 Third Normal Form (2) Lược đồ quan hệ R ở 3NF nếu nó ở 2NF và không có thuộc tính không khóa nào trong A trong R là phụ thuộc bắc cầu vào khóa Có thể phân rã quan hệ thành các quan hệ ở 3NF qua tiến trình chuẩn hóa 3NF
• 13. đồ quan hệ R ở 3NF nếu nó ở 2NF và không có thuộc tính không khóa A nào trong R là phụ thuộc bắc cầu vào bất kỳ khóa nào của R Định nghĩa: Lược đồ quan hệ R ở 3NF nếu có PTH X -> A thỏa trên R thì: X là siêu khóa của R, hay A là thuộc tính khóa của R 74 Ví dụ về quan hệ không ở DC3 Xét quan hệ CNHAN nhu sau: CNHAN(MACN LOAINGHE HESOTHUONG) Khóa của quan hệ là MACN Ta thấy có các pth trong quan hệ: MACN → LOAINGHE MACN → HESOTHUONG LOAINGHE → HESOTHUONG Pth bắt cầu: MACN -> LOAINGHE và LOAINGHE -> HESOTHUONG Thuộc tính không khóa HESOTHUONG phụ thuộc bắc cầu vào thuộc tính khóa MACN, do đó quan hệ CNHAN không phải là 3NF. 75 Bài tập 1 Xét LĐQH r(R) với R=ABCDE và tập PTH F = {AB->CE, E->AB, C->D} Dạng chuẩn cao nhất của quan hệ này là gì ? 1) Tìm khóa: AB, E AB+=ABCDE và E+=ABCDE 76 Bài tập 1 ( Xét DC cao nhất) Thuộc tính không khóa {C,D} 2) Xác định dạng chuẩn 2 Các thuộc tính không khóa phải phụ thuộc đầy đủ vào khóa. Đúng nên ở DC2 3) Xác định dạng chuẩn 3 Các thuộc tính không khóa phải không được phụ thuộc bắc cầu vào khóa Hoặc nếu có PTH X->A thì X phải là siêu khóa hoặc A là thuộc tính khóa Xét PTH C->D ta có C không phải siêu khóa, D cũng không phải thuộc tính khóa Ta có AB->C và C-> D, vậy D phụ thuộc bắc cầu vào khóa AB 77 Bài tập 2( Xét DC cao nhất) Cho LĐQH r(R) với R=ABCD F= {A->C, D->B, C->ABD} Xác định dạng chuẩn cao nhất Giải: Xác định khóa: A, C A+=ACBD C+ACBD Do tất cả các PTH đều có vế trái chỉ chứa 1 thuộc tính nên DC2 78 Bài tập 2( Xét DC cao nhất) Các thuộc tính khóa A,C Các thuộc tính không khóa B,D PTH D->B có vế trái D không phải là siêu khóa. Ta có C->D và D->B phụ thuộc bắc cầu: không ở DC3 Dạng chuẩn cao nhất là DC2
• 14. CSDL quan hCSDL quan hệệ CSDLQH yêu cầu tìm tập các lược đồ quan hệ “tốt” Các PTH được dùng để lọc sơ đồ ER (phân rã quan hệ phổ quát) Thiết kế tồi có thể đưa đến sai sót 80 VVấấn đn đềề thithiếết kt kếế không tkhông tồồii first_name last_name address department position salary Dewi Srijaya 12a Jln Lempeng Toys clerk 2000 Izabel Leong 10 Outram Park Sports trainee 1200 John Smith 107 Clementi Rd Toys clerk 2000 Axel Bayer 55 Cuscaden Rd Sports trainee 1200 Winny Lee 10 West Coast Rd Sports manager 2500 Sylvia Tok 22 East Coast Lane Toys manager 2600 Eric Wei 100 Jurong drive Toys assistant manager 2200 ? ? ? ? security guard 1500 Redundant storage Update anomaly Potential deletion anomaly Insertion anomaly Assume the position determines the salary: position → salary key T1 81 VVíí ddụụ vvềề chuchuẩẩn hn hóóaa first_name last_name address department position Dewi Srijaya 12a Jln lempeng Toys clerk Izabel Leong 10 Outram Park Sports trainee John Smith 107 Clementi Rd Toys clerk Axel Bayer 55 Cuscaden Rd Sports trainee Winny Lee 10 West Coast Rd Sports manager Sylvia Tok 22 East Coast Lane Toys manager Eric Wei 100 Jurong drive Toys assistant manager position salary clerk 2000 trainee 1200 manager 2500 assistant manager 2200 security guard 1500 T2 T3 No Redundant storage No Update anomaly No Deletion anomaly No Insertion anomaly 82 ChuChuẩẩn hn hóóaa Chuẩn hóa là tiến trình phân rã lược đồ quan hệ R thành các into mảnh (vd bảng nhỏ hơn) R1, R2,.., Rn sao cho: Phân rã không mất tin (Lossless decomposition): Các mảnh chứa cùng thông tin như bản gốc. Ngược lại sẽ bị mất tin. 83 ChuChuẩẩn hn hóóaa Bảo toàn phụ thuộc (Dependency preservation): Cần bảo toàn các phụ thuộc trong từng quan hệ Ri Dạng tốt (Good form): Các mảnh Ri không nên bị dư (bảng bị dư nếu có PTH mà vế trái LHS không phải là khóa). 84 Phân rã kPhân rã kếết không mt không mấất tint tin Phân rã R không mất tin thành 2 quan hệ R1 và R2 nếu có thể khôi phục lại quan hệ R từ R1 và R2: R= R1 R2 SELECT first_name, last_name, address, department, T2.position, salary FROM T2, T3 WHERE T2.position = T3.position
• 15. rã kếết không mt không mấất tint tin Phân rã R thành R1 và R2 là không mất tin (lossless) nếu và chỉ nếu ít nhất một trong các PTH sau có mặt trong F+: R1 ∩ R2 → R1 R1 ∩ R2 → R2 Nói cách khác, tập thuộc tính chung của R1 và R2 phải là khóa dự tuyển cho R1 hay R2. 86 VVíí ddụụ vvềề phân rã cphân rã cóó mmấất tint tin A B a a b 1 2 1 A a b B 1 2 R1=∏A(R) ∏A(R) ∏B(R) A B a a b b 1 2 1 2 R1=∏B(R) R 87 Phân rã bPhân rã bảảo too toààn phn phụụ thuthuộộcc Phân rã lược đồ quan hệ R với tập PTH F thành tập các bảng (mảnh) Ri với PTH Fi Fi là tập các phụ thuộc trong F+ (bao đóng của F) chỉ bao hàm các thuộc tính có trong Ri. Phân rã bảo toàn phụ thuộc nếu và chỉ nếu (∪i Fi)+ = F+ 88 VVíí ddụụ vvềề phân rã không bphân rã không bảảo too toààn phn phụụ thuthuộộcc R = (A, B, C), F = {{A}→{B}, {B}→{C}, {A}→{C}}. Key: A Có PTH {B}→ {C}, với vế tráikhông phải khóa ( có thể bị dư trong R.) Giải: Tách thành 2 bảng R1(A,B), R2(A,C) (chuẩn hóa) A B C 1 2 3 2 2 3 3 2 3 4 2 4 Phân rã là không mất tin vì thuộc tính chung là A ( khóa của R1 và R2) Phân rã là không bảo toàn phụ thuộc vì F1={{A}→{B}}, F2={{A}→{C}} và (F1∪F2)+≠F+ PTH {B}→{C}. Đã bị mất A C 1 3 2 3 3 3 4 4 A B 1 2 2 2 3 2 4 2 89 VVíí ddụụ vvềề phân rã bphân rã bảảo too toààn phn phụụ thuthuộộcc R = (A, B, C), F = {{A}→{B}, {B}→{C}, {A}→{C}}. Key: A Tách R thành 2 bảng R1(A,B), R2(B,C) A B C 1 2 3 2 2 3 3 2 3 4 2 4 A B 1 2 2 2 3 2 4 2 B C 2 3 2 4 Phân rã là không mất tin vì thuộc tính chung là B ( khóa của R2 ) Phân rã bảo toàn phụ thuộc vì F1={{A}→{B}}, F2={{B}→{C}} và (F1∪F2)+=F+ 90 Thuật toán kiểm tra phép phân rã không mất tin Vào: Lược đồ quan hệ R={A1, A2, . . . , An}, tập các pth F và phép tách ρ( R1,R2, . . . , Rk) Ra: Kết luận phép tách ρ không mất tin. Các buớc của thuật toán: Thiết lập một bảng với n cột( thuộc tính) và k dòng (quan hệ), cột thứ j ứng với thuộc tính Aj, dòng thứ i ứng với lược đồ Ri . Tại dòng i và cột j , ta điền ký hiệu aj nếu thuộc tinh Aj ∈ Ri. Ngược lại ta điền ký hiệu bij.
• 16. thuật toán kiểm tra phép phân rã không mất tin Cho LĐQH r( R) với R={A,B,C,D} Và tập PTH F F={A->B, AC->D} Phép phân rã ρ(AB,ACD) Kiểm tra phép phân rã ρ không mất tin 92 Tạo bảng a4a3b22a1ACD b14b13a2a1AB DCBA PTH: A->B , AC->D 93 Làm bằng dùng PTH A->B a4a3b22/a2a1ACD b14b13a2a1AB DCBA Dùng PTH A->B để làm bằng phần tử b22 thành a2 Vì bảng có dòng 2 chứa toàn ai nên phân rã trên là không mất tin 94 Kiểm tra phép phân rã mất tin Cho LĐQH r( R) với R={A,B,C,D,E} Và tập PTH F F={A->C, B->C,C->D,DE->C,CE->A} Phép phân rã ρ(AD,AB,BE,CDE) Kiểm tra phép phân rã ρ là mất tin 95 Phân rã bảo toàn phụ thuộc Một phân rã ρ=(R1,R2, . . ., Rk) của lược đồ quan hệ R trên tập PTH F bảo toàn phụ thuộc nếu có thể suy ra được F từ các hình chiếu của F trên Ri. Hình chiếu của F trên một tập các thuộc tính Z, ký hiệu là ΠZ(F) là tập các phụ thuộc X → Y thuộc F+ sao cho XY ⊂ Z ( chú ý X → Y có thể không thuộc F và chỉ thuộc F+). Ta nói phân rã ρ bảo toàn tập PTH F nếu hợp tất cả các PTH trong ΠRi(F) với i=1,2,…,k khẳng định logic tất cả PTH trong F. 96 Thuật toán kiểm tra bảo toàn phụ thuộc Vào: Phân rã ρ=(R1,R2, . . ., Rk) và tập pth F Ra: Đúng nếu ρ bảo toàn phụ thuộc và sai nếu ngược lại Gọi G là hợp của tất cả ΠRi(F) với i=1,…,k Dùng thuật toán EQUIVALENCE để xem xét G có tương đương với F hay không. Nếu có trả về đúng, ngược lại trả về sai.
• 17. rã lược đồ thành DC3 không mất tin, bảo toàn phụ thuộc Bước 1: Loại khỏi R tất cả các thuộc tính không có mặt trong vế trái và vế phải của tất cả các PTH trong F. Bước 2: Nếu có PTH X->Y mà XY=R thì kết quả chính là R Bước 3: Với từng PTH X->A của F, tạo lược đồ XA. Bước 4:Nếu có các PTH X->A1, X->A2,…,X->An thì tạo lược đồ XA1A2..An thay cho từng lược đồ XAi. Bước 5: Nếu tất cả các phần tử của khóa K không xuất hiện ở vế trái trong bất kỳ quan hệ nào được tạo ở bước 4 thì tạo quan hệ mới có thuộc tính là khóa K 98 Ví dụ Cho LĐQH r (R) với R=XYZWQ và tập PTH F F={X->Y, XZ->W, YW->Q} Tìm một khóa dự tuyển: XZ XZ+=XZWYQ Bước 1:Không có thuộc tính nào thỏa nên không thực hiên bước 1. Bước 2:Không có PTH nào thỏa nên không thực hiện bước 2. Bước 3:Xét PTH X->Y, ta có quan hệ R(XY) 99 Ví dụ Bước 3:Xét PTH XZ->W, ta có quan hệ R(XZW) Bước 3:Xét PTH YW->Q, ta có quan hệ R(YWQ) Bước 4: Không có quan hệ nào có chung vế trái của các PTH nên không gộp Bước 5: Các thuộc tính khóa XZ xuất hiện ở vế trái của PTH XZ->W, do vậy KHÔNG tạo quan hệ mới Kết quả: R1(XY), R2(XZW) và R3(YWQ) đạt DC3 không mất tin và bảo toàn phụ thuộc. 100 BBàài ti tậập 1p 1 Cho LĐQH r( R) với R={A,B,C,D,E} và tập PTH F={A→BC}. Một phân rã R1(A,B,C) and R2(A,D,E) Phân rã này không mất tin? Đúng vì thuộc tính chung A là thuộc tính khóa của R1 Phân rã này có bảo toàn phụ thuộc? Đúng vì PTH:A→BC được duy trì trong R1 Phân rã R1(A,B,C) và R2(C,D,E) không mất tin? Không vì C ( thuộc tính chung) không phải là khóa của bất kỳ bảng nào. 101 Bài tập 2 Cho LĐQH r(R) với R= {A, B, C, D, E} và tập PTH F = {A->BC, CD->E, B->D, E->A}. Xét phân rã R1= (A, B, C) R2= (A, D, E) Phân rã không mất tin? Đúng vì thuộc tính chung A là khóa của R1. Phân rã bào toàn phụ thuộc? Không: ta mất các PTH CD->E và B->D 102 Bài tập 3: Cho LĐQH r(R) với R={A, B, C, D} và tập PTH F={AB->CD, B ->C}. R ở DC2? Khóa: AB vì AB+ = ABCD=R B →C vi phạm DC2 vì B là tập con của khóa và C không phải là thuộc tính khóa.
• 18. LĐQH r(R) với R={A, B, C, D} and F={AB->CD, C->D}. R ở dạng chuẩn 2? Khóa: AB ta có AB+= ABCD Ta có C->D, C không phải là tập con của khóa vậy R ở dạng chuẩn 2 104 Bài tập 5 Cho LĐQH r(R) với R={A, B, C, D, E} và tập PTH F={A->B, BC->E, ED->A} Tìm các khóa của R ACD , BCD , CDE Phân rã R đạt 3NF. R đã ở DC3 vì tất cả các thuộc tính đều là thuộc tính khóa. 105 Bài tập 6 Cho quan hệ Sale (Customer, Store, Product, Price) Và ràng buộc: Khách mua hàng chỉ mua hàng trong 1 cửa hàng duy nhất. Trong một của hàng các sản phẩm có một đơn giá duy nhất ứng với từng sản phẩm của cửa hàng. Mô tả trên ứng với các PTH sau: {Customer} → {Store} {Store, Product} → {Price} Khóa dự tuyển: {Customer, Product} 106 Bài tập 6 (tt) Quan hệ Sale có ở dạng chuẩn 3? Không vì cả 2 PTH đều vi phạm định nghĩa DC3. Phân rã Sale thành DC3 R1(Customer,Store), R2(Store,Product,Price) Phân rã bảo toàn phụ thuộc? Đúng vì từng PTH đều nằm trong từng quan hệ 107 Bài tập 7 Phân rã (Customer,Store), (Store,Product,Price) là mất tin vì thuộc tính chung Store không phải là khóa của bất kỳ bảng con nào KEY: Customer, Product Kết 2 bảng con (trên thuộc tính chung store) không khôi phục trở lại bảng gốc . Kết quả kết tạo ra 4 mẩu tin trong khi bảng gốc chỉ có 3 mẩu tin. Vấn đề phát sinh vì không có bảng con nào chứa khóa dự tuyển Lời giải: thêm bảng con (Customer, Product) trong phân rã. ( thuật toán phân rã đạt DC3) pr1p1s1c2 pr2p2s1c1 pr1p1s1c1 PriceProduc t StoreCustome r s1c2 s1c1 StoreCustomer pr2p2s1 pr1p1s1 PriceProductStore c2 c1 c1 Customer p1 p2 p1 Product 108 Bài tập 8 Cho LĐQH r(R) với R ={A, B, C, D, E, F, G}, F={AB ->CD, C->EF, G->A, G->F, CE->F} Phân rã thành các quan hệ ở DC3 Tính phủ tối tiểu FC={AB->CD, C->EF, G->AF} Các khóa dự tuyển : GB Phân rã đạt DC3 R1={ABCD} , R2={CEF} , R3={GAF} , R4={GB}
• 19. LĐQH r(R) với R = {A,B,C,D}. Phân rã R thành các quan hệ ở DC3 theo từng PTH sau: {B}→{C} , {D}→{A} Khóa dự tuyển: BD Phân rã: (B,C), (D,A), (B,D) 110 Cho LĐQH r(R) với R = {A,B,C,D}. Phân rã R thành các quan hệ ở DC3 theo từng PTH sau{A,B,C}→{D} , {D}→{A} Khóa dự tuyển: ABC, BCD Phân rã R(A,B,C,D) đã ở DC3 Quan hệ r ( R ) có dư thừa? Có vì vế trái của PTH {D}→{A} có thuộc tính D không phải là khóa Phân rã R(A,B,C,D) theo cách bảo toànn phụ thuộc và không dư thừa? Không có {A,B,C}→{D} chứa 4 thuộc tính. Nếu phân rã R sẽ mất PTH này. 111 Bài tập 10 Xác định dạng chuẩn cao nhất cỉa các LĐQH sau: R1(A, C, B, D, E), F1={A→B, C→D} Khóa là ACE DC1 (cả 2 PTH đều vi phạm DC2) R2(A, B, C, F), F2={AB→C, C→F}, Khóa là 2NF (C→F vi phạm DC3) R3(A, B, C), F3={AB→C, C→B} Khóa là AB, AC , Tất cả thuộc tính của quan hệ đều là thuộc tính khóa, nên ở DC3. 112 Cho LĐQH r(R) với R = {A,B,C,D,E}. F = {A→BC, CD →E, B → D, E→A }. Các phân rã sau là không mất tin ? 1) R1 = {A,B,C}, R2 ={A,D,E}. 2) R1 = {A,B,C}, R2 ={C,D,E}. 1) Vì R1 ∩ R2 = A và A là khóa của R1, phân rã là không mất tin. 2) Do R1 ∩ R2 = C và C không phải là khóa của R1 R2,nên phân ra này không phải là phân rạ không mất tin. Bài tập 11: Phân rã không mất tin (LJD) 113 R = {A,B,C,D,E}. F = {A→BC, CD →E, B → D, E→A }. R1 = {A,B,C}, R2 = {A,D,E}. Phân rã trên có bảo toàn phụ thuộc? Không vì mất CD → E và B → D. Bài tập 12 : Phân rã bảo toàn PTH 114 Cho LĐQH r(R) với R =(A, B, C, D). F = {C→D, C→A, B→C}. 1) Xác định các khóa dự tuyển. 2) Xác định dạng chuẩn cao nhất. 3) Phân rã R thành các quan hệ ở DC3. Bài tập 13
• 20. C, D). F = {C→D, C→A, B→C}. 1) Xác định các khóa dự tuyển. B+ = B (B→B) = BC (B→C) = BCD (C→D) = ABCD (C→A) Khóa dự tuyển là B. B là khóa dự tuyển DUY NHẤT Bài tập 13 (1) 116 R =(A, B, C, D). F = {C→D, C→A, B→C}. 2) Xác định dạng chuẩn cao nhất. Khóa là B R không ở DC3 vì: PTH C→D vi phạm, C→D không hiển nhiên ({D} ⊄ {C}). C không phải là siêu khóa. D không phải là thành phần của khóa bất kỳ. C→A gây ra vi phạm Tương tự ở trên B→C không gây vi phạm Bài tập 13 (2) 117 R =(A, B, C, D). F = {C→D, C→A, B→C}. 3) Phân rã R thành các quan hệ ở DC3. Phủ chính tắ (canonical cover) là Fc = {C→DA, B→C}. Đối với từng PTH trong Fc tạo bảng R1 = {C, D, A}, R2 = {B, C}. Bảng R2 chứa khóa dự tuyển cho R -kết thúc. Bài tập 13 (3) 118 Bài tập 14 R = (A, B, C, D) F = {AB→C, AB→D, C→A, D→B} Đúng. Xác định tất cả các khóa dự tuyển : AB, BC, CD, AD Kiểm tra tất cả PTH thỏa DC3 119 Bài tập 15 R = (A, B, C, D) F = {ABC→D, D→A} 1. Xác định tất cả khóa dự tuyển của R ABC, BCD 2. Xác định dạng chuẩn cao nhất Dạng chuẩn 3 vì tất cả các thuộc tính đều là thuộc tính khóa. 120 Tài liệu tham khảo David Maier, Theory of Relational Database, Computer Science Press, 1983 Đỗ Phúc, Nguyễn Đăng Tỵ: Cơ sở dữ liệu , NXB ĐHQG-HCM, 2004 Lê Tiến Vượng: Nhập môn cơ sở dữ liệu quan hệ, NXb Thống kê, 2003 Nguyễn Xuân Huy, Lê Hoài Bắc, Bài tập CSDL, NXB Thống Kê, 2003 Nguyễn Văn Tâm, Nguyễn Hữu Hạnh, Cơ sở dữ liệu quan hệ: Lý thuyết và thực hành. NXB Thống kê, 2002

Phụ thuộc hàm đầy đủ xảy ra khi nào?

Bao đóng của tập phụ thuộc hàm F, ký hiệu F + là tập tất cả các phụ thuộc hàm được suy ra từ F. Nếu F = F + thì F là họ đầy đủ của các phụ thuộc hàm.

Báo động trong cơ sở dữ liệu là gì?

Trong khoa học máy tính, bao đóng (closure) là một hàm hay một tham chiếu tới một hàm cùng với môi trường tham chiếu - một bảng chứa tham chiếu đến mỗi biến không phải cục bộ (hay còn gọi là biến tự do). Closure còn được gọi với tên là lexical closure (bao đóng hay function closure (bao đóng hàm).

Cơ sở dữ liệu quan hệ là gì?

Cơ sở dữ liệu quan hệ (tiếng Anh: relational database) là một cơ sở dữ liệu (phổ biến nhất là kỹ thuật số) dựa trên mô hình quan hệ dữ liệu, theo đề xuất của Edgar F. Codd vào năm 1970. Một hệ thống phần mềm sử dụng để duy trì cơ sở dữ liệu quan hệ là một hệ quản trị cơ sở dữ liệu quan hệ (RDBMS).

Cơ sở dữ liệu dùng để làm gì?

Cơ sở dữ liệu hỗ trợ các hoạt động nội bộ trong công ty và lưu trữ hoạt động tương tác với khách hàng cũng như nhà cung cấp. Chúng cũng lưu giữ thông tin quản trị và nhiều dữ liệu chuyên biệt hơn, chẳng hạn như các mô hình kỹ thuật hoặc kinh tế.