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



tải về 1.86 Mb.
trang14/17
Chuyển đổi dữ liệu17.08.2016
Kích1.86 Mb.
1   ...   9   10   11   12   13   14   15   16   17

F1+=Q1(F)={SDM,SDSM,SDDM,SDSDM}{SDM}= F1

F2+=Q2(F)={SID,SISD,SIDI,SISDI}{SID}= F2

Q1 và Q2 đều đạt dạng chuẩn BC vì trong Qi chỉ có phụ thuộc hàm có vế trái là khóa. F1 được tạo thành bằng cách lấy các phụ thuộc hàm của Q1(F)có vế phải một thuộc tính. Tương tự cho F2

Ví dụ 17: cho Q(CTHRSG), F={CT;HRC;HTR;CSG;HSR} hãy phân rã Q thành các lược đồ con đạt chuẩn BC bảo toàn thông tin. (giải như ví dụ trên)



Tính chất: Theo thuật toán trên, khi phân rã Q thành Q1(XY)với XYQ2 thì tập khóa SQ của Q luôn luôn bằng với tập khóa SQ2 của Q2.

Chứng minh

Thật vậy, K là một khóa của Q  K là một siêu khóa của Q2. Giả sử có K’ K và K’ là khóa của Q2  K’(Q+-Y) mà XY  K’Q+. Điều này mâu thuẫn với K là khóa của Q  K là khóa của Q2. Ngược lại cũng đúng.

Dựa vào tính chất trên, ta cải tiến thuật toán phân rã nhằm giảm bớt khối lượng tính các phụ thuộc hàm của tập F+

Thuật toán phân rã Q,F thành dạng chuẩn BC (hay chuẩn 3) bảo toàn thông tin

Bước 1: Tìm tập tất cả khóa SK của Q

Bước 2: Tìm phụ thuộc hàm X  Y  F có X không là siêu khóa và Y không chứa thuộc tính khóa. Nếu tìm thấy thì tách Q thành Q1 và Q2 theo quy tắc sau:

Q1=Q[XY]; Tính F1 bằng cách tính bao đóng tất cả tập con của XY

Q2=Q[Q+ -Y] SK cũng là tập khóa của Q2

thực hiện bước 1 cho Q1

thực hiện bước 2 cho Q2

Ngược lại nếu không tìm thấy thì có hai trường hợp:

Trường hợp 1: mọi phụ thuộc hàm trong Fi đều cóvế trái là siêu khóa thì Qi đạt chuẩn BC

Trường hợp 2: nếu có phụ thuộc hàm có vế trái không là siêu khóa và vế phải là thuộc tính khóa thì Qi đạt chuẩn 3.

Chú ý: Thuật toán này chỉ tiện trong trường hợp khối lượng tính toán trong việc tìm tất cả khóa của lược đồ quan hệ Q không lớn. Nói cách khác tập trung gian TG có ít thuộc tính. Ngược lại ta phải dùng thuật toán của phần tiếp theo.

Ví dụ 18: phân rã lược đồ ở ví dụ trên thành các lược đồ con ở dạng chuẩn BC bảo toàn thông tin.

Trong F có 4 phụ thuộc hàm CT,HRC,HTR,CSG làm Q không đạt dạng chuẩn 3 hay BC và phép phân rã trên đã chọn ngẫu nhiên phụ thuộc hàm CT để phân rã thành Q1 và tập thuộc tính của Q12 chính là tập thuộc tính của Q bỏ thuộc tính T.Tập phụ thuộc hàm F12 sẽ chứa các phụ thuộc hàm của F bỏ đi các phụ thuộc hàm có vế trái hay vế phải chứa thuộc tính T. Như vậy tùy theo cách chọn phụ thuộc hàm để phân rã thành Q1 mà số lượng phụ thuộc hàm mang xuống Q12 khác nhau và chất lượng phân rã cũng khác nhau. Kết quả của phép phân rã trên chính là Q1, Q2, Q3 của hình trên. Phép phân rã bảo toàn thông tin, và các lược đồ con đạt chuẩn BC nhưng phép phân rã không bảo toàn phụ thuộc hàm vì G = F1  F2  F3 = {CT; HRC; CHR; HSRG} không tương đương với F (HTR  G+ và CSG  G+). Ta hãy xem phép phân rã sau sẽ cho kết quả tốt hơn.



Phép phân rã cũng cho kết quả phép phân rã bảo toàn thông tin, các lược đồ con Q1,Q2,Q3,Q4 đạt chuẩn BC và phép phân rã không bảo toàn phụ thuộc hàm vì G = F1  F2  F3  F4 ={CSG;HRC;CHR;CT;HSC} không tương đương với F (HTR  G+).Phép phân rã này tốt hơn vì chỉ có một phụ thuộc hàm HTR không thuộc G+ trong khi phép phân rã trên có tới 2 phụ thuộc hàm HTR và CSG không thuộc G+.Sở dĩ phép phân rã thứ 2 tốt hơn vì ở bước chọn phụ thuộc hàm để phân rã thành Q1 phép phân rã đã chọn phụ thuộc hàm sao cho khi chiếu F xuống Q12 số phụ thuộc hàm mang xuống càng nhiều càng tốt.



Ví dụ 19: cho Q(A,B,C,D,E,G), F={AEC;CGA;BDG;GAE} hãy phân rã Q thành các lược đồ con đạt chuẩn BC bảo toàn thông tin.

Nếu Q được phân rã thành:

(Q1(BDG), Q2(A,B,C,D,E)) lược đồ cơ sở dữ liệu đạt chuẩn 3

(Q1(BDG), Q2(A,C,E), Q3(A,B,D,E)) lược đồ cơ sở dữ liệu đạt chuẩn BC



        1. Bổ đề:

Nếu Q không ở dạng chuẩn BC thì có thuộc tính A,B thuộc Q+ sao cho (Q+-AB)A

Chứng minh:

Q không ở dạng chuẩn BC  có XA sao cho X không là siêu khóa  có thuộc tính B  XA (vì nếu không có B  XA thì X phải là siêu khóa)  (Q+-AB)  X  (Q+-AB)A



Nhận xét:

  • Một lược đồ Q ở dạng chuẩn BC vẫn có thể có AB sao cho (Q+-AB)A

  • Một lược đồ Q không có AB sao cho (Q+-AB)A thì Q ở dạng chuẩn BC

        1. Thuật toán

Thuật toán phân rã sau không cần tìm tất cả khóa của lược đồ quan hệ Q

Thuật Toán phân rã Q, F thành dạng chuẩn BC bảo toàn thông tin

Bước 1: Z’ = Q+

Bước 2: phân rã Z’ theo thuật toán chi tiết để được 2 lược đồ Z’-A và XA trong đó XA ở dạng chuẩn BC và X  A

Nếu thuật toán chi tiết cho kết quả thì qua bước 3

Ngược lại kết thúc thuật toán

Bước 3: nhận XA là một lược đồ con của các lược đồ kết quả Q1,...,Qk

Bước 4: thực hiện phân rã Z’-A,F
Thuật toán chi tiết

Bước 1: nếu Z’ không chứa AB sao cho (Z’-AB)A. thì

báo không phân rã được.

Ngược lại qua bước 2

Bước 2: đặt Y’ = Z’

Bước 3: nếu Y’ chứa AB sao cho (Y’-AB)A. thì gán Y’ = Y’–B thực hiện lại bước 2

Bước 4: bước 3 cho kết quả Y’ = XA với XA ở dạng chuẩn BC và X  A. Trả về XA
Nhận xét

Ở mỗi bước 2 của thuật toán phân rã Q,F ta thu được 2 lược đồ Qi+=Z’-A,Q1+=XA với Qi+Q1+ = (Z’-A)XA = X và XQ1+ và Q1 là lược đồ ở dạng chuẩn BC. Thuật toán lại tiếp tục phân rã Qi theo đúng cách đã làm  thuật toán phân rã bảo toàn thông tin và các lược đồ con Qi đạt dạng chuẩn BC.



Thuật toán chi tiết tìm Ql đạt chuẩn BC sao cho Ql+ chứa nhiều thuộc tính nhất. Để tìm được Ql như vậy thuật toán chi tiết tìm hai thuộc tính ABQ+ sao cho (Q+-AB)A. Nếu tìm thấy chứng tỏ Q chưa đạt chuẩn BC và thuật toán giảm B trong Q với hy vọng thu được lược đồ con Ql đạt chuẩn BC và thỏa phụ thuộc hàm (Q+-AB)A. Thuật toán chi tiết tiếp tục tìm và giảm cho tới khi thu được lược đồ con không có hai thuộc tính AB sao cho (Q+-AB)A  Ql là lược đồ con đạt chuẩn BC cần tìm.

Ví dụ 19: Cho quan hệ Q(B,O,S,Q,I,D) và tập phụ thuộc hàm F

F = {S  D,

I  B

IS  Q


B  O}

Hãy phân rã Q thành các lược đồ con đạt dạng chuẩn BC và bảo toàn thông tin.



Giải

***Đặt Z’= Q+= BOSQID

Thực hiện thuật toán chi tiết

Y’= BOSQID

Chọn 2 thuộc tính . Tìm bao đóng của tập hợp thuộc tính còn lại. Nếu bao đóng chứa 1 trong 2 thuộc tính chọn chẳng hạn A, nghĩa là ta đã tìm được 2 thuộc tính AB sao cho (Y’-AB)A

Chọn BO:(SQID)+  B

Giảm O trong Y’ ta được Y’= BSQID

Chọn BS:(QID)+  B

Giảm S trong Y’ ta được Y’= BQID

Chọn BQ:(ID)+  B

Giảm Q trong Y’ ta được Y’= BID

Chọn BD: I+  B

Giảm D trong Y’ ta được Y’= BI  Q1=(BI) và F1={IB}

Để tính F1 ta phải tính bao đóng của tất cả tập con của {BI}F1

***Giảm B trong Z’ ta được Z’= OSQID

Đặt Y’=OSQID

Chọn OD: (SQI)+  D;

Giảm O trong Y’ ta được Y’= SQID

chọn QD: (SI)+  D

giảm Q trong Y’ ta được Y’= SID

chọn ID: S+  D;

giảm I trong Y’ ta được Y’= SD  Q2=(SD) và F2={SD}

Để tính F2 ta phải tính bao đóng của tất cả tập con của {SD}  F2

*** Giảm D trong Z’ ta được Z’= OSQI

Đặt Y’=OSQI

chọn OQ: (SI)+  Q

giảm O trong Y’ ta được Y’= SQI  Q3=(SQI) và F3={SIQ}

Ở bước trên không chọn AB để bao đóng tập hợp thuộc tính còn lại chứa A hay B

Để tính F3 ta phải tính bao đóng của tất cả tập con của {SQI}  F3

*** Giảm Q trong Z’ ta được Z’= OSI

Đặt Y’=OSI

Chọn OS: I+=IBO  O

giảm S trong Y’ ta được Y’= OI  Q4=(OI) và F4={IO}
*** Giảm O trong Z’ ta được Z’= SI  Q5=(SI)và F5={PTHHN}

Ta có thể hiểu Q3(SQI)là tổ hợp của 2 lược đồ con Q5(SI) và Q3(SQI)



Vậy kết quả phân rã là:

1:Q1(BI) F1={IB}

2:Q2(SD) F2={SD}

3:Q3(SQI) F3={SIQ}

4:Q4(OI) F4={IO}


        1. Chú ý

  • Nên tránh phân rã nếu lược đồ đã ở dạng chuẩn mong muốn.

  • Nên xem xét tổ hợp các lược đồ quan hệ con thành lược đồ lớn hơn nếu lược đồ lớn hơn vẫn đạt dạng chuẩn mong muốn.

  • Một kết quả phân rã bảo toàn phụ thuộc hàm sẽ có giá trị hơn kết quả phân rã không bảo toàn phụ thuộc hàm. Giữa hai kết quả phân rã đều không bảo toàn phụ thuộc hàm thì kết quả phân rã thỏa nhiều phụ thuộc hàm trong F sẽ có giá trị hơn .

  • Không có thuật toán phân rã lược đồ Q thành các lược đồ con ở dạng chuẩn BC vừa bảo toàn thông tin vừa bảo toàn phụ thuộc hàm.

  • Vẫn có lược đồ Q được phân rã thành các lược đồ con ở dạng chuẩn BC vừa bảo toàn thông tin vưa bảo toàn phụ thuộc hàm.


Ví dụ 20: cho lược đồ Q(CSZ) có F={CSZ,ZC}. Q không thể phân rã thành các lược đồ con ở dạng chuẩn BC vừa bảo toàn thông tin vừa bảo toàn phụ thuộc hàm. Thật vậy:

TN={S} TG={CZ}



Tất cả khóa của Q là:

Xi

TNXi

(TNXi)+

siêu khóa

khóa



S

S







Z

SZ

SZC

SZ

SZ

C

SC

SZC

SC

SC

ZC

SZC

SZC

SZC




Vậy Q đạt dạng chuẩn 3 nhưng không ở dạng chuẩn BC vì có ZC có vế trái không là siêu khóa. Nhưng nếu ta phân rã Q thành các lược đồ con có ít hơn 3 thuộc tính thì phụ thuộc CSZ không suy ra được từ các phụ thuộc hình chiếu.

      1. Phân rã thành dạng chuẩn 3 vừa bảo toàn thông tin vừa bảo toàn phụ thuộc hàm

Thuật Toán phân rã Q, F thành dạng chuẩn 3, bảo toàn thông tin, bảo toàn phụ thuộc hàm

Dữ liệu vào: lược đồ quan hệ Q và tập phụ thuộc hàm F.

Dữ liệu ra: một phân rã sao cho mỗi lược đồ quan hệ con đều đạt chuẩn 3 vừa bảo toàn thông tin vừa bảo toàn phụ thuộc hàm.
Tìm phủ tối thiểu Ftt của F
Nếu có một phụ thuộc hàm nào của Ftt mà liên quan đến tất cả các thuộc tính của Q thì kết quả phân rã chính là Q ( Q không thể phân rã)
Nếu có những thuộc tính của Q không nằm trong một phụ thuộc nào của Ftt - dù ở vế phải hay vế trái của F thì chúng tạo thành một lược đồ cần tìm.
Cứ mỗi phụ thuộc hàm X  A  Ftt thì XA là một lược đồ cần tìm
Nếu có một lược đồ con chứa khóa K của Q thì kết thúc thuật toán

Ngược lại tạo một lược đồ con K
Ví dụ 21: cho lược đồ Q(CTHRSG),F={CT,HRC,THR,CSG,HSR}.Hãy phân rã Q thành các lược đồ con đạt dạng chuẩn 3 vừa bảo toàn thông tin vừa bảo toàn phụ thuộc hàm.

Gỉai:

  • F=Ftt={CT,HRC,THR,CSG,HSR} là phủ tối thiểu.

  • Áp dụng thuật toán trên Q được phân rã thành các lược đồ con

Q1(CT),Q2(HRC),Q3(THR),Q4(CSG),Q5(HSR)

  • Khóa của Q

    Xi

    TNXi

    (TNXi)+

    siêu khóa

    khóa



    HS

    CTHRSG

    HS

    HS

    C

    HSC

    CTHRSG

    HSC




    T

    HST

    CTHRSG

    HST




    CT

    HSCT

    CTHRSG

    HSCT




    R

    HSR

    CTHRSG

    HSR




    CR

    HSCR

    CTHRSG

    HSCR




    TR

    HSTR

    CTHRSG

    HSTR




    CTR

    HSCTR

    CTHRSG

    HSCTR




  • Q5 chứa khóa của Q nên Q1,Q2,Q3,Q4,Q5 là kết quả của phân rã.

Định lý: Thuật toán trên tạo ra một phân rã ở dạng chuẩn 3 vừa bảo toàn thông tin vừa bảo toàn phụ thuộc hàm

Chứng minh:

  1. Nếu Ftt có phụ thuộc hàm fi liên quan đến tất cả thuộc tính thì Q đạt chuẩn 3. Thật vậy:

fiFtt  fi là phụ thuộc hàm có vế phải 1 thuộc tính  fi có dạng KA  K là siêu khóa. Nếu khóa của Q là K’ K thì ta có K’A  KA là phụ thuộc hàm có vế trái dư thừa điều này mâu thuẫn với fiFtt. Vậy K là khóa của Q  nếu Q có thuộc tính không khóa thì A là thuộc tính không khóa duy nhất của Q và mọi phụ thuộc hàm có vế phải là A phải có vế trái là K  lược đồ quan hệ Q không có phụ thuộc hàm có vế trái không là siêu khóa và vế phải không là thuộc tính khóa  Q đạt chuẩn 3.

  1. Nếu lược đồ Q(W) gồm các thuộc tính không xuất hiện trong Ftt thì Q đạt chuẩn 3. Thật vậy:

V là tập con bất kỳ của W ta có V+=V  F’ của Q’ chỉ gồm các phụ thuộc hàm hiển nhiên  trong F’ không có phụ thuộc hàm có vế trái không là siêu khóa và vế phải là thuộc tính không khóa Q’ đạt chuẩn 3.

  1. Ta chứng minh mỗi lược đồ con ở dạng chuẩn 3. Thật vậy:

Theo thuật toán thì mỗi lược đồ con Qi có dạng YB với YB  Y là siêu khóa. Giả sử trong Qi có phụ thuộc hàm XA có vế trái không là siêu khóa và vế phải không là thuộc tính khóa. Ta phân làm hai trường hợp:

Trường hợp 1: A=B  XB  X  Y  YB là phụ thuộc có vế trái dư thừa, điều này trái với YB là phụ thuộc hàm trong phủ tối thiểu.

Trường hợp 2: AB  AY (1). Gọi K là khóa của Qi  K  Y (2). A là thuộc tính không khóa nên A  K (3).(1)(2)(3) K  Y (4).K là khóa nên KB  YB là phụ thuộc hàm có vế trái dư thừa. Điều này trái với điều phụ thuộc hàm YB là phụ thuộc hàm của phủ tối thiểu Ftt

  1. Ta chứng minh phép phân rã bảo toàn phụ thuộc hàm. Thật vậy:

Hiển nhiên Ftt  G = Qi(Ftt) Ftt+  G+ (1)

Hơn nữa Ftt+  G = Qi(Ftt) Ftt++  G+  Ftt+  G+ (2)



(1)và (2)  Ftt+ = G+

  1. Ta chứng minh phép phân rã bảo toàn thông tin. Thật vậy:

Lập bảng kiểm tra bảo toàn thông tin. Ta lần lượt đồng nhất các giá trị của bảng trên theo các phụ thuộc hàm được phát hiện ở mỗi bước của thuật toán tìm bao đóng của tập thuộc tính Qi+ với Qi+ chứa khóa K của lược đồ Q. Phụ thuộc hàm đầu tiên được phát hiện là YAjFtt sao cho Qi+Y và AjQi+.Ở dòng của lược đồ Ql(YAj) có giá trị aj ở cột Aj nên khi làm bằng giá trị kết quả là ở cột Aj của dòng có lược Qi có thêm giá trị aj. Tiếp tục cho các phụ thuộc hàm phát hiện tiếp theo ta sẽ có thêm các giá trị a ở các cột khác của dòng Qi. Do Qi chứa khóa nên các giá trị a mới thêm vào của dòng Qi sẽ xuất hiện ở tất cả các thuộc tính của lược đồ Q. Suy ra hàng của lược đồ Qi sẽ chứa toàn a là điều phải chứng minh. Để làm sáng tỏ ý tưởng của phần chứng minh này ta xét trường hợp cụ thể của ví dụ 21 :

Bước 1: ta lập bảng kiểm tra bảo toàn thông tin:




C

T

H

R

S

G

Q1(CT)

a1

a2













Q2(HRC)

a1




a3

a4







Q3(THR)




a2

a3

a4







Q4(CSG)

a1










a5

a6

Q5(HSR)







a3

a4

a5



1   ...   9   10   11   12   13   14   15   16   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