Bài giảng Cơ sở dữ liệu - Bài 7: Phụ thuộc dữ liệu trong mô hình quan hệ - Vũ Văn Định

Bài 7. PHỤ THUỘC DỮ LIỆU TRONG MÔ HÌNH QUAN HỆ I. Phụ thuộc hàm (Functional Dependencies : FD) 1. Định nghĩa : Cho R(U) là một lược đồ quan hệ với U = { A1, .. ,An} là tập thuộc tính. X và Y là tập con của U. Nói rằng X  Y (đọc là X xác định hàm Y hoặc Y phụ thuộc hàm vào X) nếu r là một quan hệ xác định trên R (U) sao cho bất kỳ hai bộ t1, t2  r mà t1[X]= t2[X] thì t1[Y] = t2[Y] TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí  Ví dụ : Trong quan hệ SV, mỗi thuộc tính DIACHI, NS, KETQUA đều phụ thuộc hàm (pth ) vào thuộc tính SV#. Mỗi giá trị SV# xác định duy nhất một giá trị tương ứng đối với từng thuộc tính đó. Khi đó , có thể viết : SV#  DIACHI SV#  NS SV#  KETQUA  Nếu Y X thì hiển nhiên X  Y TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 2. Hệ tiên đề cho phụ thuộc hàm 2.1. K/n bao đóng của một tập phụ thuộc hàm • Gọi F là tập tất cả các pth đối với lược đồ quan hệ R(U) và X Y là một pth, X, Y  U. • Nói rằng X Y được suy diễn logic từ F nếu mỗi quan hệ r trên R( U) đều thoả các pth của F thì cũng thoả X  Y. • Chẳng hạn F = { A  B, B  C} thì A  C • Tập tất cả các pth được suy diễn logic từ F được gọi là bao đóng của F. Kí hiệu là F+. • Nếu F+ = F thì F là họ đầy đủ của các pth TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 2.2. Hệ tiên đề Amstrong  Năm 1974, Amstrong đưa ra hệ luật dẫn hay các tính chất của phụ thuộc hàm, gọi là hệ tiên đề Amstrong:  Cho X, Y, Z, W  U . Ta có các luật sau : A1. Luật phản xạ : Nếu Y  X thì X Y A2. Luật bổ sung : X  Y thì XZ  YZ A3. Luật bắc cầu : Nếu X  Y và Y  Z thì X Z TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí  Hệ tiên đề Amstrong được chứng minh là đúng đắn và đầy đủ thông qua 3 bổ đề sau:  Bổ đề 1 : Hệ tiên đề Astrong là đúng. Có nghĩa là, với F là một tập các pth đúng trên quan hệ r. Nếu X  Y là một pth được suy dẫn từ F nhờ hệ tiên đề Amstrong thì X Y là đúng trên quan hệ r TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí  Bổ đề 2: Từ hệ tiên đề Amstrong ta suy ra một số luật sau đây: a. Luật hợp : Nếu X  Y và X  Z thì X  YZ b. Luật tách : Nếu X  Y và Z  Y thì X  Z c. Luật tựa bắc cầu : Nếu X  Y và WY  Z thì XW  Z TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí  Khái niệm bao đóng của tập các thuộc tính đối với tập các phụ thuộc hàm. Gọi F là tập các pth trên tập thuộc tính U, X U . X + là bao đóng của X (đối với F ) được định nghĩa như sau : X + = { A | X  A  F+ } Nói cụ thể : X + là tập tất cả các thuộc tính A mà pth XA có thể được suy diễn logic từ F nhờ hệ tiên đề Amstrong TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí  Bổ đề 3 : X  Y suy dẫn từ hệ tiên đề Amstrong khi và chỉ khi Y  X + Như vậy : (1). X  X+ (2). f: XY  F+ Y  X+ TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 2.3 Thuật toán tìm bao đóng của tập thuộc tính Thuật toán CLOSURE. Input : Tập thuộc tính X và tập phụ thuộc hàm F Output : Bao đóng X của F CLOSURE (X,F) Begin olddep:= ; newdep:=olddep While newdep olddep do Begin olddep:= newdep For each W  Z  F do if W  newdep then newdep:= newdep  Z End Return ( newdep) End. TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí VD: Cho U = ABCDEG F = { AB C (f1) D  EG (f2) C  A (f3) BE  C (f4) BC  D (f5) CG  BD (f6) ADC  B (f7) CE  AG (f8) } Cho X= BD. Tính ( BD)+F TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí Giải: X(0): = BD X(1): = BD  EG ( do (f2) ) X(2): = BDEG  C ( do (f4) ) X(3): = BDEGC  { A ( do (f2) )  C ( do (f4) )  D ( do ( f5) )  BD ( do (f6) )  AG ( do (f8)) } X(4): = BDEGCA = U => X+F = X (4) TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 3. Tập phụ thuộc hàm tương đương 3.1 Định nghĩa Hai tập pth F và G được gọi là tương đương nếu F+ = G+. Khi đó ta nói F phủ G ( hay G phủ F). Kí hiệu : F G  Bổ đề 1: Mỗi tập các pth F đều được phủ bằng tập các pth G mà vế phải các pth đó bao gồm không quá một thuộc tính.  Bổ đề 2: F G F suy dẫn được ra G và G suy dẫn được ra F TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí Ví dụ : Cho quan hệ Q (ABCDE) với: F = {A BC , A D,CD  E } G = {A BCE , A ABD, CD  E} * F suy dẫn được ra G vì : A  C, A  D => A  CD CD  E => A  BCE. Tương tự, dễ dàng chứng minh : A  ABD. Vậy F suy dẫn được ra G. * Ngược lại, ta nhận thấy F  G , do đó hiển nhiên G suy dẫn được ra F. Kết luận : F  G A  E TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 3.2 Phủ tối thiểu Định nghĩa : Một tập phụ thuộc hàm F được gọi là tối thiểu nếu :  Mỗi vế phải của một phụ thuộc hàm F chỉ có một thuộc tính.  F gồm toàn những pth đầy đủ, nghĩa là không tồn tại một phụ thuộc hàm X  A thuộc F và một tập con Z của X mà : F+ = ( F - { X  A }  { Z  A}) +  Không tồn tại một phụ thuộc hàm X  A thuộc F mà : F+ = ( F - { X  A }) + TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 3.3 Thuật toán MINIMALCOVER tìm phủ tối thiểu của tập phụ thuộc hàm F Input: Tập phụ thuộc hàm F Output : G- là phủ tối thiểu của F MINIMALCOVER (G, F) G:=F Thay thế từng phụ thuộc hàm X { A1, A2,..,An} trong G bằng các phụ thuộc hàm X A1, X  A2, .., X  An For each 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 TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí For each X  A trong G If ( G - { X  A }) tương đương với G Then Loại X  A ra khỏi G Return (G) End. TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí Ví dụ 1: Cho F = { A B , B  A, B  C, A  C, C  A}. Tìm phủ tối thiểu G của F Giải : Tất cả các pth của F đều thoả mãn điều kiện 1 vì vế trái chỉ có một thuộc tính. Vế phải của mỗi pth chỉ có một thuộc tính nên không cần xét đk2. Xét đk 3, ta thấy : Nếu koại bỏ pth B  A và A  C ta được một tập pth G G={A B , B  C, A  C }  F Không thể loại bỏ thêm một pth nào nữa vì tập pth còn lại sẽ không tương đương với F. Vậy G là tập pth tối thiểu của F. TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí Ví dụ 2: Cho F = { AB C, A  B, B  A}. Tìm phủ tối thiểu G của F Giải : Tất cả các pth của F đều thoả mãn điều kiện 1 vì vế trái chỉ có một thuộc tính. Xét đk2: ta thấy pth là không đầy đủ vì : (F- {AB C} {A C})  F Vậy loại bỏ pth AB  C và thay bằng pth A  C ta được tập pth G: G={A C , A B, B  A }  F Nhận thấy, không thể loại bỏ thêm một pth nào nữa vì tập pth còn lại sẽ không tương đương với F. Vậy G là tập pth tối thiểu của F. TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 4. Bài toán tìm khoá của quan hệ 4.1 Thuật toán tìm khoá dựa trên đồ thị Định nghĩa khoá được viết lại bằng pth. Cho Q là lược đồ quan hệ định nghĩa trên tập các thuộc tính U = { A1, A2, .. , An} với tập các pth F= { f1, f2, .. ,fn} xác định trên Q. K  U là khoá của R nếu thoả mãn hai điều kiện sau : (1): K  U (2):  K'  K mà K'  U TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí Biểu diễn lược đồ quan hệ Q(U) bằng đồ thị có hướng như sau: - Mỗi nút của đồ thị là tên của một thuộc tính thuộc Q - Cung nối hai thuộc tính A và B thể hiện cho pth A B - Thuộc tính chỉ có các mũi tên đi ra, tức là chỉ ở vế trái của pth gọi là nút gốc - Thuộc tính mà chỉ có mũi tên đi vào, tức là chỉ nằm ở vế phải của pth gọi là nút lá. - Khoá của lược đồ quan hệ phải bao phủ tập nút gốc và không được chứa bất cứ nút lá nào của đồ thị TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí Thuật toán tìm khoá: -B1: Vẽ đồ thị của lược đồ quan hệ -B2: Xác định tập các nút gốc ( G) và tập các nút lá ( L) -B3: Xuất phát từ tập các nút gốc(G), đặt K bằng G ( khởi đầu ta đặt khoá là tập các nút gốc) -B4: Dựa trên tập các pth F, tìm bao đóng của tập K ( tìm K+F) + Nếu K+F = U thì K chính là khoá . Dừng lại. + Ngược lại thì bổ sung một thuộc tính không thuộc tập nút lá (L) vào K. Khi đó K = K+1 nút không thuộc tập L. Trở lại B4. TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 4.2 Thuật toán tìm khoá dựa trên bao đóng của tập thuộc tính * Ý tưởng : Bắt đầu từ tập R vì R+ = R. Ta bớt dần các phần tử của R để nhận được tập bé nhất mà bao đóng của nó vẫn bằng R. Vào : r(R), F Ra : K ( Khoá ) B1: gán K = R B2: Lặp lại các bước sau : Loại khỏi K phần tử A mà ( K \A)+ =R Nhận xét: Thuật toán trên chỉ tìm được một khoá trong sơ đồ quan hệ. Nếu cần tìm nhiều khoá, ta thay đổi trật tự loại bỏ các phần tử của K. TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí Ví dụ : Cho R = { ABCDEGHI} F = { AC B , BI  ACD, ABC  D, H  I, ACE  BCG, CG  AE}. Tìm khoá K ? Giải : B1: Gán K= R = { ABCDEGHI} B2: Lần lượt loại bỏ các phần tử khỏi K. -Loại phần tử A : ta có : {BCDEGHI}+ = R vì pth CG  AE nên A thuộc về {BCDEGHI}+ nên K ={BCDEGHI} -Loại phần tử B : ta có : {CDEGHI}+ = R vì pth CG  AE khiến A thuộc về {CDEGHI}+ và pth AC  B khiến B thuộc về {CDEGHI}+ nên K ={CDEGHI} TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí -Loại phần tử C : ta có : {DEGHI}+  R nên K vẫn là {CDEGHI} -Loại phần tử D : ta có : {CEGHI}+ = R vì CG  AE, AC  B, ABC  D nên D có trong {CEGHI}+ . Nên K ={CEGHI} -Loại phần tử E : ta có : {CGHI}+ = R vì CG  AE khiến E thuộc về {CGHI}+ nên K ={CGHI} -Loại phần tử H : ta có : {CGI}+  R nên K vẫn là {CGHI} -Loại phần tử I : ta có : {CGH}+ = R vì H  I, khiến I thuộc về {CGH}+ nên K ={CGH} Kết luận : K= { CGH } là một khoá của r (R) TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí