MÔ HÌnh quan hệ nguyên nhân ra đỜi của mô HÌnh quan hệ



tải về 1.86 Mb.
trang8/17
Chuyển đổi dữ liệu17.08.2016
Kích1.86 Mb.
1   ...   4   5   6   7   8   9   10   11   ...   17

Số phụ thuộc hàm có thể có của Q(A1,A2,...,An) là 2n x 2n =22n

    1. HỆ LUẬT DẪN ARMSTRONG (Armstrong inference rule)

Người ta thường dùng F để chỉ tập các phụ thuộc hàm của lược đồ quan hệ Q. Ta có thể đánh số các phụ thuộc hàm của F là f1, f2, .., fm. Quy ước rằng chỉ cần mô tả các phụ thuộc hàm không hiển nhiên trong tập F (các phụ thuộc hàm hiển nhiên được ngầm hiểu là đã có trong F).

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

Nói rằng phụ thuộc hàm X  Y được suy diễn logic từ F nếu một quan hệ r 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 ký hiệu F+ là tập tất cả các phụ thuộc hàm được suy diễn logic từ F.

Các tính chất của tập F+

1. Tính phản xạ: Với mọi tập phụ thuộc hàm F+ ta luôn luôn có F  F+

2. Tính đơn điệu: Nếu F  G thì F+  G+

3. Tính lũy đẳng: Với mọi tập phụ thuộc hàm F ta luôn luôn có (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+



Chứng minh

  1. X  Y  F  r thỏa X  Y  X  Y  F+

  2. Nếu X  Y là phụ thuộc hàm thuộc F+ ta phải chứng minh X  Y thuộc G+

Giả sử r thỏa tất cả các phụ thuộc hàm của G (1)

 r thỏa tất cả phụ thuộc hàm của F vì F  G

 r thỏa phụ thuộc hàm X  Y (2) vì X  YF+

(1) và (2)  X  Y  G+  F+  G+­­



  1. F  F+ (tính phản xạ)  F+  (F+)+ (1)

Nếu X  Y  (F+)+ (2) X  Y  F+ thật vậy: (3)

Giả sử r thỏa tất cả các phụ thuộc hàm của F (4)

 r thỏa tất cả các phụ thuộc hàm của F+ (theo định nghĩa)

 r thỏa tất cả các phụ thuộc hàm của (F+)+ (theo định nghĩa)

 r thỏa X  Y (vì (2))  X  Y  F+­­

(1) và (3)  (F+)+ = F+



      1. Hệ luật dẫn Armstrong

Hệ luật dẫn là một phát biểu cho biết nếu một quan hệ r thỏa mãn một vài phụ thuộc hàm thì nó phải thỏa mãn phụ thuộc hàm khác.

Với X,Y,Z,W là tập con của Q+. r là quan hệ bất kỳ của Q. Ta có 6 luật dẫn sau:



  1. Luật phản xạ (reflexive rule): X  X

  2. Luật thêm vào (augmentation rule): Cho X  Y XZ Y

  3. Luật hợp (union rule): Cho X  Y, X  Z X YZ

  4. Luật phân rã (decomposition rule): Cho X  YZ X Y

  5. Luật bắc cầu (transitive rule): Cho X  Y, Y  Z X Z

  6. Luật bắc cầu giả (pseudo transitive rule): Cho X  Y, YZ  W XZ W

Hệ tiên đề Armstrong (Armstrong’s Axioms) gồm 3 luật: (1), (2) và (5)

Chứng minh

Với t1,t2 là hai bộ bất kỳ của quan hệ r.

Luật phản xạ: Ta có (t1.X = t2.X  t1.X = t2.X) theo định nghĩa suy ra X  X

Luật thêm vào: giả sử có t1.XZ = t2.XZ (1)

 t1.X = t2.X

 t1.Y = t2.Y (do X  Y) (2)

 XZ  Y (do (1)  (2))

Luật hợp: giả sử có t1.X = t2.X (1)

 t1.X = t2.X và t1.Z = t2.Z

 t1.XZ = t2.XZ (2)

 X  YZ (do (1)  (2))

Luật phân rã: gỉa sử có: t1.X = t2.X (1)

 t1.YZ = t2.YZ (do X  YZ)

 t1.Y = t2.Y (2)

 X  Y (do (1)  (2))

Luật bắc cầu: giả sử có t1.X = t2.X (1)

 t1.Y = t2.Y

 t1.Z = t2.Z (2)

 X  Z (do (1)  (2))

Luật bắc cầu giả: giả sử có: t1.XZ = t2.XZ (1)

 t1.X = t2.X và t1.Z = t2.Z (2)

 t1.Y = t2.Y (do X  Y) (3)

 t1.YZ = t2.YZ (Kết hợp (2) và (3))

 t1.W = t2.W (do YZ  W) (4)

 XZ  W

Trong 6 luật trên, chỉ cần 3 luật 1, 2 và 6 là đủ, nghĩa là các luật còn lại có thể suy dẫn từ ba luật này.



        1. Hệ luật dẫn Armstrong là đúng

Nói rằng X  Y là phụ thuộc hàm được suy diễn nhờ vào luật dẫn Armstrong nếu tồn tại các tập phụ thuộc hàm F0  F1 ...  Fn sao cho X  Y  Fn với F0,F1,...,Fn lần lượt được hình thành thỏa phương pháp sau:

Bước 1: F0 = F

Bươc 2:chọn một số phụ thuộc hàm trong Fi áp dụng hệ luật dẫn Armstrong để thu được một số phụ thuộc hàm mới. Đặt Fi+1= Fi  {các phụ thuộc hàm mới}

Ví dụ: Cho F = {AB  C,C  B,BC  A} thì có F0  F1  F2 sao cho C  A  F2

F0 = {AB  C,C B, BC  A} áp dụng luật hợp cho C  B và C  C

F1 = {AB  C,C  B, BC A, C BC} áp dụng luật bắc cầu.

F2 = {AB  C,C  B, BC  A, C BC, C  A}


Hệ quả: Hệ luật dẫn Armstrong là đúng nghĩa là nếu F là tập các phụ thuộc hàm đúng trên quan hệ r và X  Y là một phụ thuộc hàm được suy diễn từ F nhờ hệ luật dẫn Armstrong thì X  Y đúng trên quan hệ r. Vậy X  Y là phụ thuộc hàm được suy diễn logic từ F
Phần tiếp theo chúng ta sẽ chứng minh hệ luật dẫn Armstrong là đầy đủ, nghĩa là mọi phụ thuộc hàm X  Y được suy diễn logic từ F sẽ được suy diễn từ F nhờ hệ luật dẫn Armstrong.

        1. Bao đóng của tập thuộc tính X (closures of attribute sets)

          1. Định nghĩa

Q là lược đồ quan hệ, r là quan hệ tương ứng, 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+ (hoặc ) được định nghĩa như sau:

X+ =  Ai với X  Ai là phụ thuộc hàm được suy diễn từ F nhờ hệ tiên đề Armstrong

Tính chất:

  • bao đóng của Q là Q+

          1. Các tính chất của bao đóng

Nếu X,Y là các tập con của tập thuộc tính Q+ thì ta có các tính chất sau đây:

1. Tính phản xạ: X  X+

2. Tính đơn điệu: Nếu X  Y thì X+  Y+

3. Tính lũy đẳng: X++ = X+

4. (XY)+  X+Y+

5. (X+Y)+ = (XY+)+ = (X+Y+)+

6. X  Y  Y+  X+

7. X  X+ và X+  X

8. X+ = Y+  X  Y và Y  X

Chứng minh:

1. X  X  X+  X

2. A  X+  X  A  Y  A  A  Y+

3. A  X++  X+  A và X  X+ (áp dụng 8)  X  A  AX+

 X++  X+. Áp dụng 1  X++  X+

...............................................

7. X  A1 và X A2  X  A1A2 .... XAi = X+

X+  X  X+  X (Phụ thuộc hàm hiển nhiên)

...............................................



          1. 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

Ví dụ 1:

Cho lược đồ quan hệ Q(ABCDEGH) và tập phụ thuộc hàm F

F = { f1: B  A

f2: DA  CE

f3: D  H

f4: GH  C

f5: AC  D }

Tìm bao đóng của các tập X = {AC} dựa trên F.



Giải:

Bước 1: X0 = AC

Bước 2: Do f1, f2, f3, f4 không thỏa. f5 thỏa vì X+  AC

X1 = AC  D = ACD

Lập lại bước 2: f1 không thỏa, f2 thỏa vì X1  AD:

X2 = ACD  CE = ACDE

f3 thỏa vì X2  D

X3 = ACDE  H = ACDEH

f4 không thỏa, f5 không xét vì đã thỏa

Lập lại bước 2: f2,f3 không xét vì đã thỏa, f1,f4 không thỏa,f5 không xét vì đã thỏa.Trong bước này X3 không thay đổi => X+=X3={ACDEH} là bao đóng của X



Ví du 2:

Q(A,B,C,D,E,G)

F = {f1: A  C;

f2: A  EG;

f3: B  D;

f4: G  E}

X = {A,B}; Y = {C,G,D}

Kết qua:

X+ = {ABCDEG}

Y+ = {CGDE}


          1. Định lý

Thuật toán tìm bao đóng cho kết quả Xi = X+

Chứng minh

1. Ta chứng minh Xi X+ bằng phương pháp qui nạp.

Bước cơ sở chứng minh X  X0

Theo tính phản xạ của hệ luật dẫn thì X  X theo thuật toán thì X0 = X  X  X0

Vậy X0  X+

Bước qui nạp giả sử có X  Xi-1 ­ (1) ta phải chứng minh X  Xi

Theo thuật toán tìm bao đóng thì có fj = Xj  Yj để Xi-1  Xj và Xi = Xi-1  Yj

 Xi-1  Yj (2).(1)và (2)  X  Yj (3)

(1) và (3)  X Xi-1Yj = Xi  X  Xi

Vậy Xi  X+­­

2. Ta chứng minh A  X+  A  Xi để kết luận Xi  X+

A  X+ nên có một phụ thuộc hàm X  A. Theo thuật toán tìm bao đóng thì X  Xi  A Xi



          1. Hệ quả

  1. Q là lược đồ quan hệ. F là tập phụ thuộc hàm, A là thuộc tính chỉ xuất hiện ở vế phải của các phụ thuộc hàm trong F thì X+ = (X – A)+  A

  2. Q là lược đồ quan hệ. F là tập phụ thuộc hàm, X là tập con của Q+ và Y = {các thuộc tính xuất hiện ở vế phải của các phụ thuộc hàm trong F} thì X+  X  Y.

Chứng minh

  1. Theo thuật toán tìm bao đóng thì bao đóng X+ hay (X-A)+ được hình thành qua một số bước. Ta chứng minh biểu thức X+ = (X – A)+  A theo qui nạp.

Bước cơ sở: X0 = X, (X-A)0 = X - A  X0 =(X - A)0  A đúng

Bước qui nạp: giả sử ta có Xi-1 =(X - A)i-1  A. Bao đóng Xi được hình thành do có fj = Xj  Yj để:

Xi-1  XjXi = Xi-1  Yj = (X - A)i-1  A  Yj (1).

Sự hình thành Xi luôn kéo theo sự hình thành (X-A)i vì:

Xi-1 = (X - A)i-1 ­­­ A  Xj do Xj không chứa A nên:

(X - A)i-1  Xj vậy (X - A)i = (X - A)i-1  Yj (2)

(1) và (2) cho:

Xi = (X - A)i  A là điều phải chứng minh


  1. Bước cơ sở: X0 = X  X0  X  Y

Bước qui nạp: giả sử có Xi-1  X  Y ta chứng minh Xi  X  Y.

Bao đóng Xi được hình thành do có fj = Xj  Yj để:

Xi-1  XjXi = Xi-1  Yj  X  Y  Yj­­ do Yj là vế phải của phụ thuộc hàm nên Y  Yj = Y vậy Xi  X  Y


      1. Hệ luật dẫn Armstrong là đầy đủ

        1. Định lý

Hệ luật dẫn Armstrong là đầy đủ nghĩa là mọi phụ thuộc hàm X Y được suy diễn logic từ F sẽ được suy diễn từ F nhờ hệ luật dẫn Armstrong.

Chứng minh:

Để chứng minh X  Y được suy diễn từ F nhờ hệ luật dẫn Armstrong ta chứng minh bằng phương pháp phản chứng nghĩa là nếu X  Y không suy diễn được từ hệ luật dẫn Armstrong thì có quan hệ r thỏa các phụ thuộc hàm F nhưng không thỏa phụ thuộc hàm X  Y (điều này nghịch lý với giả thuyết là mọi quan hệ r thỏa các phụ thuộc hàm trong F thì r cũng thỏa phụ thuộc hàm X  Y).

Thật vậy giả sử Q(A1,A2,...,An) là lược đồ quan hệ, ai,bi là các giá trị khác nhau trên miền giá trị Ai. r là quan hệ trên Q có hai bộ t và t’được xác định như sau:

t=(a1,a2,...,an)



Vậy quan hệ r có t.X = t’.X nhưng t.Y  t’.Y (t.Y gồm các giá trị ai còn t’.Y phải có ít nhất một bi nếu không Y  X+  X  Y được suy dẫn từ hệ luật dẫn Armstrong ). Như vậy r không thỏa phụ thuộc hàm X  Y.

Bây giờ ta chứng minh quan hệ r thỏa mọi phụ thuộc hàm trong F. Gọi W  Z là phụ thuộc hàm trong F.

Nếu W  X+  t.W  t’.W  mệnh đề (t.W = t’.W  t.Z = t’.Z)đúng

Nếu W  X+  t.Z = t’.Z = bộ các ai

 mệnh đề (t.W = t’.W  t.Z = t’.Z)đúng



        1. Hệ quả:

Bao đóng của tập thuộc tính X đối với F là:

X+ =  Ai với X  Ai là phụ thuộc hàm được suy diễn logic từ F

Tính chất

X Y F+ Y X+

Chứng minh

X  Y  có k sao cho Y = Ak   Ai = X+

Y  X+  X+ = Y  (X+ - Y)  X  Y  (X+ - Y)  X  Y

Bài toán thành viên

Nói rằng X  Y là thành viên của F nếu X  Y  F+

Một vấn đề quan trọng khi nghiên cứu lý thuyết CSDL là khi cho trước tập các phụ thuộc hàm F và một phụ thuộc hàm X  Y, làm thế nào để biết X  Y có thuộc F+ hay không bài toán này được gọi là bài toán thành viên. Để trả lời câu hỏi này ta có thể tính F+ rồi xác định xem X  Y có thuộc F+ hay không. Việc tính F+ là một công việc đòi hỏi thời gian và công sức. Tuy nhiên, thay vì tính F+ chúng ta có thể dùng thuật toán sau để xác định X  Y có là thành viên của F hay không. Thuật toán này sử dụng tính chất vừa chứng minh trên.

Thuật toán xác định f = XY có là thành viên của F hay không

Bước 1: tính X+

Bước 2: so sánh X+ với Y nếu X+­­­  Y thì ta khẳng định X  Y là thành viên của F

Bạn đọc hãy nắm thật kỹ thuật toán này – nó mở đầu cho một loạt ứng dụng về sau.



    1. THUẬT TOÁN TÌM F+

      1. Thuật toán cơ bản

Để tính bao đóng F+ của tập các phụ thuộc hàm F ta thực hiện các bước sau:

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+

Ví dụ 3:

Cho lược đồ quan hệ Q(A,B,C) F = {AB  C,C  B} là tập phụ thuộc hàm trên Q. F+ được tính lần lượt theo các bước trên là như sau:



Bước 1: Các tập con của Q+



A

B

C



{A}

{B}

{C}







{A,B}

{A,C}










{B,C}










{A,B,C}

Bước 2: các phụ thuộc hàm có thể có của F (không kê các phụ thuộc hàm hiển nhiên)

AB

ABC

BC

ABCF

CA

CBCF+

ACBCF+

BCAC

AAB

AABC

BAC

ABACF+

CBF

CABC

ACABCF+

BCABC

AC

BA

BBC

ABBCF+

CAB

ACBF+

BCA




AAC

BAB

BABC

ABABCF+

CAC

ACABF+

BCAB




Bước 3: bao đóng của các tập con của Q đối với F

+ = A+ = A C+ = BC

ABC+ =ABC B+ = B AC+ = ABC

AB+ = ABC BC+ = BC



Bước 4: F = {AB  C,C  B} suy ra:

F+ = {ABC,ABAC,ABBC,ABABC,CB,CBC,ACB,ACAB,ACBC,ACABC}



      1. Thuật toán cải tiến

Dựa vào thuật toán cơ bản trên, ta nhận thấy có thể tính F+ theo các bước sau:

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 4: 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+.

Ví dụ bao đóng A+ = A chỉ gồm các phụ thuộc hàm hiển nhiên

bao đóng {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



    1. BÀI TẬP

  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



  1. Cho Q+={ABCD}

  1. Tìm tất các các tập con của Q

  2. 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)

  1. Tìm bao đóng F+ của quan hệ phanCong(PHICONG,MAYBAY,NGAYKH,GIOKH)

  2. Cho F = {ABC,BD,CDE,CEGH,GA}

  1. 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

  2. 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+={ABCDEGH})

  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}.

  1. Hãy chứng tỏ phụ thuộc hàm ABGH được suy diễn từ F nhờ luật dẫn Armstrong

  2. Tìm bao đóng của {AB}

  1. Cho F={AD,ABE,BIE,CDI,EC} tìm bao đóng của {AE}+={ACDEI}
1   ...   4   5   6   7   8   9   10   11   ...   17


Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2016
được sử dụng cho việc quản lý

    Quê hương