Hỏi Đáp Là gì

Phủ tối thiểu của phụ thuộc hàm là gì

Tháng Sáu 26, 2011

Tìm phủ tối thiểu của 1 tập Phụ thuộc hàm

Hướng dẫn – Tìm phủ tối thiểu của 1 Phụ thuộc hàm [minimal cover]
Thuật toán tìm phủ tối thiểu của một tập phụ thuộc hàm
1. Tách các phụ thuộc hàm sao cho vế phải chỉ còn một thuộc tính. [ví dụ: A->BC thành A->B và A->C]
2. Bỏ các thuộc tính dư thừa ở vế trái. [ví dụ: cho F = {A → B, B → C, AB → D} các phụ thuộc hàm có vế trái 1 thuộc tính là đầy đủ nên ta không xét, xét AB → D có B dư thừa[bỏ B] vì bao đóng của A có chứa B. A+=ABC] [dễ hiểu là chúng ta bỏ thuộc tính bên vế trái, khi và chỉ khi bao đóng của các thuộc tính còn lại có chứa thuộc tính đó]
3. Loại khỏi F các phụ thuộc hàm dư thừa. [Các thuộc tính ở vế phải của PTH chỉ xuất hiện di nhất 1 lần thì không thể loại bỏ. Còn lại tính bao đóng của tập thuộc tính vế trái nếu có xuất hiện thuộc tính vế phải thì có thể loại bỏ thuộc tính đó và đó là PTH dư thừa.]

Ví dụ: Cho lược đồ quan hệ Q[A,B,C,D] và tập pth F={AB->CD, B->C, C->D} Tìm phủ tối thiểu?
1. Tách các phụ thuộc hàm sao cho vế phải chỉ còn một thuộc tính.
+ ta có F={AB->C, AB->D, B->C, C->D}
2. Bỏ các thuộc tính dư thừa ở vế trái.
+ B->C, C->D Không xét vì vế trái chỉ có một thuộc tính.
+ xét AB->C : Nếu Bỏ A thì B+=BCD không chứa A nên không thể Bỏ A. Nếu Bỏ B thì A+=A. không bỏ được thuộc tính nào.
+ xét AB->D : Nếu Bỏ A thì B+=BCD không chứa A nên không thể Bỏ A. Nếu Bỏ B thì A+=A. không bỏ được thuộc tính nào.
3. Loại khỏi F các phụ thuộc hàm dư thừa.
+ xét AB->C : Tính AB+=ABCD = Q nên loại bỏ AB->C
+ xét AB->D : tính AB+=ABCD = Q nên loại bỏ AB->D
+ B->C : tính B+=B không thể bỏ.
+ C->D : tính C+=C không thể bỏ.

Phủ tối thiểu là Ftt = {B->C, C->D}

This entry was posted on Chủ Nhật, 26 Tháng Sáu 2011 at 1:30 chiều and posted in Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed.

Download PHỤ THUỘC HÀM - WordPress.com...

PHỤ THUỘC HÀM [functional dependency]

Phụ thuộc hàm [FD]  Định nghĩa: Cho một lược đồ quan hệ gồm n

thuộc tính: Q[A1, A2,…, An]  X, Y là hai tập con của Q+={A1, A2,…, An}.  r là một quan hệ trên Q.  t1, t2 là hai bộ bất kỳ của r. Phụ thuộc hàm giữa hai thuộc tính X và Y ký hiệu là X Y được định nghĩa như sau: X Y [t1.X = t2.X  t1.Y = t2.Y] [Ta nói X xác định Y hay Y phụ thuộc hàm vào X]

Phụ thuộc hàm [FD]  Ví dụ: cho lược đồ quan hệ: Q[A, B, C, D, E]

I. AB  C

II. B  D

III. DE  A [T]

[T]

Phụ thuộc hàm [FD]  Phụ thuộc hàm hiễn nhiên:

Nếu X  Y thì X Y.  Với r là quan hệ bất kỳ, F là tập phụ thuộc hàm thỏa trên r, ta luôn có F {các phụ thuộc hàm hiển nhiên}

Phụ thuộc hàm [FD]  Thuật toán Satifies: Cho quan hệ r và X, Y là hai

tập con của Q+, Thuật toán SATIFIES sẽ trả về trị true nếu X  Y ngược lại là false  SATIFIES[r,X,Y]  Sắp các bộ của quan hệ r theo X để các giá trị giống nhau trên X nhóm lại với nhau  Nếu tập các bộ cùng giá trị trên X cho các giá trị trên Y giống nhau thì trả về true ngược lại là False

Phụ thuộc hàm [FD]  Ví dụ: SATIFIES[phanCong,MAYBAY,GIOKH]

Phụ thuộc hàm [FD]  Cách tìm tất cả tập con của Q+:  Số tập con có thể có của Q+ = {A ,A ,...,A } là 2n  Số phụ thuộc hàm có thể có: 2nx2n 

ABC

ABD

Ví dụ: Q+=[A, B, C, D]

• Số tập con: 24=16 • Số PTH: =24x24=256

AC BC ABC

Hệ luật dẫn Armstrong  Phụ thuộc hàm được suy diễn logic từ F  Phụ thuộc hàm X  Y được suy diễn logic từ F

nếu một quan hệ r bất kỳ thỏa mãn tất cả các phụ thuộc hàm của F thì cũng thỏa phụ thuộc hàm X  Y. Ký hiệu F|= X  Y.  Bao đóng của F [F+]  Bao đóng của F ký hiệu F+ là tập tất cả các phụ

thuộc hàm được suy diễn logic từ F.

Hệ luật dẫn Armstrong  Các tính chất của tập F+  Tính phản xạ: F  F+  Tính đơn điệu: Nếu F  G thì F+  G+  Tính lũy đẳng: [F+]+ = F+.  Gọi G là tập tất cả các phụ thuộc hàm có thể có

của r, phần phụ của F ký hiệu F- = G - F+

Hệ luật dẫn Armstrong  Hệ luật dẫn Amstrong:  Cho X,Y,Z,W là tập con của Q+  r là quan hệ bất kỳ của Q.  Ba luật của tiên đề Amstrong: 1. Luật phản xạ [reflexive rule]:

Nếu Y  X thì X  Y 2. Luật tăng trưởng[augmentation rule]:

Nếu Z  Q và X  Y thì XZ  YZ 3. Luật bắc cầu [Transivity Rule] Nếu X  Y và Y  Z thì X  Z

Hệ luật dẫn Armstrong  Ba hệ quả của tiên đề Amstrong: 1. Luật hợp [Union Rule]

Nếu X  Y và X  Z thì X  YZ 2. Luật bắc cầu giả [Pseudotransivity Rule] Nếu X  Y và WY  Z thì XW  Z 3. Luật phân rã [Decomposition Rule] Nếu X  Y và Z  Y thì X  Z

Bao đóng của tập thuộc tính X [closures of attribute sets]  Định nghĩa:  Q là lược đồ quan hệ.  r là một quan hệ trên Q,  F là tập các phụ thuộc hàm trong Q.  X, Ai là các tập con của Q+

Bao đóng của tập thuộc tính X đối với F ký hiệu là X+ được định nghĩa: X+=Ai với X Ai là phụ thuộc hàm được suy diễn từ F nhờ hệ tiên đề Armstrong

Bao đóng của tập thuộc tính X [closures of attribute sets]  Thuật toán tìm bao đóng:  Tính liên tiếp tập các tập thuộc tính X0,X1,X2,...

theo phương pháp sau:  Bước 1: X0 = X  Bước 2: lần lượt xét các phụ thuộc hàm của F Nếu YZ có Y  Xi thì Xi+1 = Xi Z Loại phụ thuộc hàm Y  Z khỏi F  Bước 3: Nếu ở bước 2 không tính được Xi+1 thì Xi chính là bao đóng của X  Ngược lại lặp lại bước 2

Bao đóng của tập thuộc tính X [closures of attribute sets] Ví dụ: Cho lược đồ quan hệ Q[A,B,C,D,E,G,H] và tập phụ thuộc hàm F={BA; DACE; DH; GH C; ACD}. Tìm bao đóng của X = {AC} trên F  X[0] = {A,C} , {A,C}{D}  X[1] = {A,C,D}, {A, D}{C,E}  X[2] = {A,C,D,E}, {D}{H}  X[3] = {A,C,D,E,H}  X+= X[3]

Cho X = {B, D} ->X+?

Bao đóng của tập thuộc tính X [closures of attribute sets]  Ví du 2: cho lược đồ quan hệ: Q[A,B,C,D,E,G]

F = { f1: A → C; f2: A → EG; f3: B → D; f4: G → E}  Tìm bao đóng của X+ và Y+ của X = {A,B}; Y = {C,G,D}  Kết quả : X+ = {ABCEG} , Y+ = {CGDE}

Sử dụng bao đóng của tập thuộc tính  Kiểm tra siêu khóa [Testing for superkey]  Đẻ kiẻ m tra X có phả i là siêu khóa: tính X+, né u X+

chứa tá t cả cá c thuọ c tính củ a R thì X là siêu khóa.  X là khó a dự tuyẻ n [candidate key] né u không tập con nào trong só cá c tạ p con củ a nó là khó a.  Kiểm tra một phụ thuộc hàm XY có được suy dẫn từ F.  Kiểm tra 2 tập phụ thuộc hàm tương đương F+=G+  Với mỗi phụ thuộc hàm YZ trong F Tính Y+ trên tập phụ thuộc hàm G Nếu Z  Y+ thì YZ trong G+ và ngược lại

Phụ thuộc hàm dư thừa  Tạ p cá c phụ thuọ c hà m có thẻ là dư thừa vì

chú ng có thẻ suy diẽ n từ cá c FDs khá c.  Ví dụ : AC là dư thừa đó i với F: [AB, BC, A C]  Mọ t phà n củ a phụ thuọ c hà m cũ ng có thể dư thừa.  Ví dụ : F=[A B, BC, AC,D] có thẻ được vié t lạ i: F=[A B, BC, AD]

Bao đóng của tập phụ thuộc hàm  Bao đóng của F ký hiệu F+ là tập tất cả các phụ

thuộc hàm được suy diễn logic từ F.  Thuật toán tìm bao đóng F+  Bước 1: Tìm tất cả tập con của Q+  Bước 2: Tìm tất cả các phụ thuộc hàm có thể có của Q.  Bước 3: Tìm bao đóng của tất cả tập con của Q.  Bước 4: Dựa vào bao đóng của tất cả các tập con đã tìm để xác định phụ thuộc hàm nào thuộc F+

Bao đóng của tập phụ thuộc hàm  Ví dụ: Q[A,B,C] F = {AB  C,C  B} F+ ?  B1: tìm tất cả tập con của các thuộc tính Q+

 B2: Tìm bao đóng của tất

cả các tập con thuộc tính A+ = A  B+ = B C+ = BC AC+ = ABC AB+ = ABC BC+ = BC



{A}

{B}

{C}

{A,B}

{A,C} {B,C} {A,B,C}

Bao đóng của tập phụ thuộc hàm  Tìm tất cả các phụ thuộc hàm có thể có: AB

ABC

BC

AAB AABC BAC AC

BA

BBC

ABCF

CA

ABACF+ CBF ABBCF+

CAB

CBCF+ CABC ACBF+

AAC BAB BABC ABABCF+ CAC ACABF+

ACBCF+

BCAC

ACABCF+ BCABC BCA BCAB

 Kết quả: F+ = {ABC, ABAC,ABBC, ABABC,

CB,CBC,ACB, ACAB,ACBC, ACABC}

Bao đóng của tập phụ thuộc hàm  Thuật toán tìm F+ cải tiến:  Bước 1: Tìm tất cả tập con của Q+  Bước 2: Tìm bao đóng của tất cả tập con của Q+  Bước 3: Dựa vào bao đóng của các tập con đã tìm

để suy ra các phụ thuộc hàm thuộc F+

Bao đóng của tập phụ thuộc hàm  Ví dụ:  A+ = A chỉ gồm các phụ thuộc hàm hiển nhiên  {AB}+ = ABC cho các phụ thuộc hàm không hiển

nhiên sau: ABC, AB  AC, AB  BC, AB  ABC  Tìm tất cả các tập con của {ABC} rồi bỏ các tập con của {AB} Các tập con của {ABC} là: ,{A},{B},{AB},{C},{AC},{BC},{ABC} Bỏ các tập con của {AB} là: ,{A},{B},{AB},{C},{AC},{BC},{ABC}  Các tập còn lại chính là vế phải của phụ thuộc hàm có vế trái là AB

Bao đóng của tập phụ thuộc hàm  1/ Cho quan hệ sau:  r[ A B C D E]  a1 b1 c1 d1 e1  a1 b2 c2 d2 d1  a2 b1 c3 d3 e1  a2 b1 c4 d3 e1  a3 b2 c5 d1 e1

Phụ thuộc hàm nào sau đây thỏa r: AD,ABD,CBDE,EA,AE

Bao đóng của tập phụ thuộc hàm 1. Cho Q+={ABC}.  a] Tìm tất các các tập con của Q  b] Tìm tất cả các phụ thuộc hàm có thể có của Q

[không liệt kê phụ thuộc hàm hiển nhiên] 2. Cho F = {ABC, BD, CE, CEGH, GA}  a] Hãy chứng tỏ phụ thuộc hàm ABE,AB  G được suy diễn từ F nhờ luật dẫn Armstrong  b] Tìm bao đóng của AB[với bài toán không nói gì về lược đồ quan hệ Q ta ngầm hiểu Q+ là tập thuộc tính có trong F nghĩa là Q+={ABCEGH}]

Bao đóng của tập phụ thuộc hàm 1. Cho F = {AD,AB  DE,CE  G,E  H}. Hãy tìm

bao đóng của AB. 2. Cho F={AB  E, AG  I, BE  I, E  G, GI  H}.  Hãy chứng tỏ phụ thuộc hàm AB  GH được suy diễn từ F nhờ luật dẫn Armstrong  Tìm bao đóng của {AB} 3. Cho F={A  D, AB  E, BI  E, C  I, E  C} tìm bao đóng của {AE}+

Phụ thuộc hàm tương đương  Định Nghĩa: Hai tập phụ thuộc hàm F và G là

tương đương [Equivalent] nếu F+ = G+  ký hiệu F = G.  Thuật toán xác định F và G có tương đương không  Bước 1: Với mỗi phụ thuộc hàm XY của F ta xác định xem XY có là thành viên của G không  Bước 2: Với mỗi phụ thuộc hàm XY của G ta xác định xem XY có là thành viên của F không  Nếu cả hai bước trên đều đúng thì F G

Phụ thuộc hàm tương đương  Ví dụ: Cho lược đồ quan hệ Q[ABCE] hai tập phụ

thuộc hàm:  F={ABC,AD,CE}  G = {ABCE,AABD,CE}

a] F có tương đương với G không? b] F có tương đương với G’={ABCE} không?

Phụ thuộc hàm tương đương a]  Tính A+ dựa trên tập G A+=ABCE  trong G+ có ABC và AD

 F  G+  F+  G+ [1].  Tính A+ dựa trên tập F A+=ABCE  trong F+ có ABCE và AABD  F+  G  F+  G+ [2] [1] và[2]  F+ = G+  F  G. b] Do = C  G’+ không chứa phụ thuộc hàm CE  F không tương đương với G’

Phủ tối thiểu của tập phụ thuộc hàm [minimal cover]  Phụ thuộc hàm có vế trái dư thừa:  F là tập các phụ thuộc hàm trên lược đồ quan hệ Q.  ZYF.  Phụ thuộc hàm Z  Y có vế trái dư thừa nếu có

một AZ sao cho: F  F-{Z  Y}{[Z-A]  Y}

Ví dụ 1: Q[A,B,C], F={ABC; BC} F  F-{ABC}{[AB-A]C}={BC} AB  C: là phụ thuộc hàm không đầy đủ B  C :là phụ thuộc hàm đầy đủ

Phủ tối thiểu của tập phụ thuộc hàm [minimal cover] Ví dụ 2: cho tập phụ thuộc hàm F = {A BC , B  C, AB  D}. Phụ thuộc hàm AB  D có vế trái dư thừa B vì: F = F – {AB  D} {A  D} = {A  BC, B  C, A  D}  F là tập phụ thuộc hàm có vế trái không dư thừa

nếu F không chứa phụ thuộc hàm có vế trái dư thừa.

Phủ tối thiểu của tập phụ thuộc hàm [minimal cover]  Thuật toán loại các phụ thuộc hàm có vế trái

dư thừa:  Xét lần lượt các phụ thuộc hàm X Y trong F  Với mọi tập con X’≠  của X, nếu X’ Y  F+ thì thay X Y bằng X’ Y . Ví dụ 3: F = {A BC , B  C, AB  D}, phụ thuộc hàm AB  D có A+=ABC  A  DF+  Trong F ta thay AB  D bằng A  D  F = {A  BC,B  C, A  D}

Phủ tối thiểu của tập phụ thuộc hàm [minimal cover]  Phụ thuộc hàm dư thừa:  F là tập phụ thuộc hàm không dư thừa nếu

không tồn tại F’ F sao cho F’ F. Ngược lại F là tập phụ thuộc hàm dư thừa. Ví dụ: Cho F = {A  BC, B  D, AB  D} thì F dư thừa vì F  F’= {ABC, BD}

Phủ tối thiểu của tập phụ thuộc hàm [minimal cover]  Tập phụ thuộc hàm tối thiểu [minimal cover]  F được gọi là một tập phụ thuộc hàm tối thiểu

[hay phủ tối thiểu] nếu F thỏa đồng thời ba điều kiện sau: F là tập phụ thuộc hàm có vế trái không dư thừa F là tập phụ thuộc hàm có vế phải một thuộc tính. F là tập phụ thuộc hàm không dư thừa

Phủ tối thiểu của tập phụ thuộc hàm [minimal cover]  Thuật toán tìm phủ tối thiểu của một tập phụ

thuộc hàm  Bước 1: Loại bỏ các phụ thuộc hàm có vế trái dư thừa.  Bước 2: Tách các phụ thuộc hàm có vế phải nhiều hơn một thuộc tính thành các phụ thuộc hàm có vế phải một thuộc tính.  Bước 3: Loại bỏ các phụ thuộc hàm dư thừa.

Phủ tối thiểu của tập phụ thuộc hàm [minimal cover]  Ví dụ 1: Cho lược đồ quan hệ Q[A,B,C,D] và tập

phụ thuộc F ={AB CD, B  C, C  D}. Tìm phủ tối thiểu của F.  Bước 1: AB  CD là phụ thuộc hàm có vế trái dư thừa?  Xét B  CDF+ ?  Tính B+ =BCD  B  CD F+  Vậy AB  CD là phụ thuộc hàm có vế trái dư thừa A  F={B  CD; B  C; C  D}

Phủ tối thiểu của tập phụ thuộc hàm [minimal cover]  Bước 2:

tách các phụ thuộc hàm có vế phải nhiều hơn 1 thuộc tính thành các phụ thuộc hàm có vế phải 1 thuộc tính F={BD; B  C; C  D}=F1tt  Bước 3: Trong F1tt, B  C là phụ thuộc hàm dư thừa? B  C  G+ ? với G = F1tt - {B  C}={B  D;C  D} BG+=BD  B  C  G+  trong F1tt B  C không dư thừa.

Phủ tối thiểu của tập phụ thuộc hàm [minimal cover] Trong F1tt,B  D là phụ thuộc hàm dư thừa?

B D  G+ ? với G = F1tt - {B  D}={B  C; C  D} BG+=BC D B  D G+ trong F1tt, B  D dư thừa.  Kết quả của bước 3 cho phủ tối thiểu: F={B  C;C  D}=Ftt

Phủ tối thiểu của tập phụ thuộc hàm [minimal cover]  Ví dụ 6: Cho lược đồ quan hệ Q[A,B,C,D] và tập

phụ thuộc F như sau: F = {A C; C  A; CB  D; AD  B; CD  B; AB  D}  Hãy tìm phủ tối thiểu của F

Phủ tối thiểu của tập phụ thuộc hàm [minimal cover]  kết quả:

Ftt = {A  C; C  A; C,D  B; A,B  D}

KHÓA CỦA LƯỢC ĐỒ QUAN HỆ [Key]  Định Nghĩa: Cho lược đồ quan hệ Q[A1,A2,…,An] Q+ là tập thuộc tính của Q. F là tập phụ thuộc hàm trên Q. K là tập con của Q+

K là một khóa của Q nếu: K+ = Q+ Không tồn tại K'  K sao cho K’+= Q+

KHÓA CỦA LƯỢC ĐỒ QUAN HỆ [Key]  Tập thuộc tính S được gọi là siêu khóa nếu S K  Thuộc tính A được gọi là thuộc tính khóa nếu

AK với K là khóa bất kỳ của Q. Ngược lại A được gọi là thuộc tính không khóa.  Một lược đồ quan hệ có thể có nhiều khóa và tập thuộc tính không khóa cũng có thể bằng rỗng.

KHÓA CỦA LƯỢC ĐỒ QUAN HỆ [Key]  Thuật toán tìm một khóa của một lược đồ

quan hệ Q  Bước 1: gán K = Q+  Bước 2: A là một thuộc tính của K, đặt K’ = K - A. Nếu K’+= Q+ thì gán K = K' thực hiện lại bước 2 Nếu muốn tìm các khóa khác [nếu có] của lược đồ quan hệ, ta có thể thay đổi thứ tự loại bỏ các phần tử của K.

KHÓA CỦA LƯỢC ĐỒ QUAN HỆ [Key]  Ví dụ: cho lược đồ quan hệ Q và tập phụ thuộc

hàm F như sau: ‒ Q[A,B,C,D,E] ‒ F={ABC, AC  B, BC  DE} tìm khóa K B1: K=Q+  K=ABCDE B2:[K\A]+ [BCDE]+=BCDE ≠ Q+  K=ABCDE B3:[K\B]+ [ACDE]+= ABCDE = Q+  K=ACDE B4: [K\C]+ [ADE]+ = ADE ≠ Q+  K=ACDE B5: [K\D]+  [ACE]+ = ACEBD=Q+  K=ACE B6: [K\E]+ [AC]+ = ACBDE =Q+  K=AC

KHÓA CỦA LƯỢC ĐỒ QUAN HỆ [Key]  Ví dụ: cho lược đồ quan hệQ[ABCDEGHI] và tập

thuộc tính F={AC B; BI  AC; ABC  D; H  I; ACE  BCG; CG  AE}  Tìm K  Đáp án: K=CGH

KHÓA CỦA LƯỢC ĐỒ QUAN HỆ [Key]  Thuật toán tìm tất cả khóa của lược đồ quan hệ:  Bước 1: Xác định tất cả các tập con khác rỗng của

Q+={X1, X2, …,X2n-1 }  Bước 2: Tìm bao đóng của các Xi  Bước 3: Siêu khóa là các Xi có Xi+= Q+ Giả sử ta đã có các siêu khóa là S = {S1,S2,…,Sm}  Bước 4: xét mọi Si, Sj con của S [i ≠ j], nếu Si  Sj thì loại Sj [i,j=1..n], kết quả còn lại của S chính là tập tất cả các khóa cần tìm.

KHÓA CỦA LƯỢC ĐỒ QUAN HỆ [Key]  Ví dụ: Tìm tất cả các khóa của lược đồ quan hệ

và tập phụ thuộc hàm như sau:

KHÓA CỦA LƯỢC ĐỒ QUAN HỆ [Key]  Thuật toán [cải tiến] tìm tất cả khóa của một

lược đồ quan hệ  Bước1: tạo tập thuộc tính nguồn TN, tập thuộc tính trung gian TG  Bước2: Nếu TG =  thì lược đồ quan hệ chỉ có một khóa K = TN kết thúc  Ngược lại Qua bước 3  Bước3: tìm tất cả các tập con Xi của tập trung gian TG

KHÓA CỦA LƯỢC ĐỒ QUAN HỆ [Key]  Bước 4: tìm các siêu khóa Si bằng cách Xi  if [TN  Xi]+ = Q+ then  Si = TN Xi  Bước 5:

tìm khóa bằng cách loại bỏ các siêu khóa không tối thiểu   Si, Sj S  if Si Sj then Loại Sj ra khỏi Tập siêu khóa S  S còn lại chính là tập khóa cần tìm.

KHÓA CỦA LƯỢC ĐỒ QUAN HỆ [Key] Ví dụ: cho lược đồ quan hệ Q[CSZ] và tập phụ thuộc hàm F={CS Z; Z  C}. Áp dụng thuật toán cải tiến:  TN = {S}; TG = {C,Z}  Gọi Xi là các tập con của tập TG:

BÀI TẬP

Bài Viết Liên Quan

Toplist mới

Bài mới nhất

Chủ Đề