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



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

Bước 4: Tính Q1(F), Q2(F)

Q1(F)= F1+ ={AB,AAB,BA,BAB}{AB,BA} (chỉ lấy pth có vế phải 1 tt)

Q2(F)= F2+ ={BC,BBC,CB,CBC}{BC,CB}(chỉ lấy pth có vế phải 1 tt)

Bước 5:

G = Q1(F) Q2(F)={AB,AAB,BA,BAB,BC,BBC,CB,CBC}

F={AB,BC,CA} có AB, BC đều là thành viên của G, còn CA có là thành viên của G hay không ta tính CG+. CG+=ABC  CA cũng là thành viên của G. Vậy phép phân rã trên bảo toàn phụ thuộc hàm.
Bài toán trên có thể được giải theo các bước đơn giản sau cho từng lược đồ quan hệ con:

Tính cho Q1



Bước 1: Kê tất cả tập con của Q1+




A

B



A

B







AB

Bước 2: Tính bao đóng của các tập con của Q1+­­

=

A+=ABC

B+

=ABC







AB+

=ABC

Bước 3: Tính F1+=Q1(F)

AB

BA

AAB

BAB

Tính cho Q2

Bước 4: Kê tất cả tập con của Q2+




B

C



B

C







BC

Bước 5: Tính bao đóng của các tập con của Q2+­­

=

B+=ABC

C+

=ABC







BC+

=ABC

Bước 6: Tính F2+=Q2(F)

BC

CB

BBC

CBC

Bước 7:

G=Q1(F)Q2(F)={AB,AAB,BA,BAB,BC,BBC,CB,CBC}

F={AB,BC,CA} có AB, BC đều là thành viên của G còn CA có là thành viên của G hay không ta tính CG+. CG+=ABC  CA cũng là thành viên của G. Vậy phép phân rã trên bảo toàn phụ thuộc hàm.


        1. Ý nghĩa của phân rã có bảo toàn phụ thuộc hàm

Ví dụ 13: Cho lược đồ quan hệ Q(C,S,Z) và F={CSZ,ZC}. Phép tách =(Q1,Q2) tách Q thành hai lược đồ Q1(S,Z) và Q2(C,Z). Hỏi phép tách có bảo toàn phụ thuộc hàm không?

Giải:

Q1 có các tập thuộc tính con:






S

Z



S

Z







SZ

Bao đóng của các tập thuộc tính con Q1+

=

S+=S

Z+

=ZC







SZ+

=CSZ

F1+ chỉ gồm các phụ thuộc hàm hiển nhiên vì tất cả các phụ thuộc hàm sau đều không thỏa:

ZC

SZC

ZZC

SZCS




SZCZ




SZCSZ

Q2 có các tập thuộc tính con:




C

Z



C

Z







CZ

Bao đóng của các tập thuộc tính con Q2+

=

C+=C

Z+

=ZC







CZ+

=CZ

F2+ gồm các phụ thuộc:

ZC

ZZC

Q1(F)Q2(F)={ZC,ZZC}{ZC} không tương đương với F = {CSZ,ZC}



Vậy phép phân rã trên không bảo toàn phụ thuộc hàm, điều này có nghĩa khi ta đưa dữ liệu vào Q1 và Q2 sao cho không vi phạm phụ thuộc hàm hình chiếu của nó, nhưng khi kết nối chúng lại thì dữ liệu kết quả của lược đồ quan hệ Q lại vi phạm phụ thuộc hàm CSZ

Q1(F)={PTHHN}

Q2(F)={ZC, ZZC}

F={CSZ,ZC}

Q1

(S

Z)

Q2

(C

Z)

Q

(C

S

Z)




s1

z1




c1

z1




c1

s1

z1




s1

z2




c1

z2




c1

s1

z2

        1. Thuật toán kiểm tra bảo toàn phụ thuộc hàm

Thuật toán tìm bao đóng của tập thuộc tính X đối với G =  Qi(F)

Vào:  =(Q1,Q2,…,Qk),F,X

Ra: XG+

Bước 1: Với mỗi phụ thuộc hàm XYF ta thực hiện từ bước 2 đến bước 4

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

Bước 3: thế Z’ = Z’((Z’)+)

Bước 4: nếu ở Qi, Z’thay đổi thì thực hiện lại bước 3 cho Qđầu tiên

Ngược lại kết thúc thuật toán và trả về Z’(là bao đóng XG+)
Thuật toán kiểm tra bảo toàn phụ thuộc hàm

Vào:  =(Q1,Q2,…,Qk),F

Ra: kết luận phép tách  bảo toàn hay không bảo toàn phụ thuộc hàm

Bước 1: Với mỗi phụ thuộc hàm XYF ta thực hiện từ bước 2 đến bước 3:

Bước 2: Tìm bao đóng XG+ với G =  Qi(F)

Bước 3: Nếu Y  XG+ thì XY Qi(F)+

Bước 4: Nếu tất cả phụ thuộc XYF đều thuộc Qi(F)+ thì ta kết luận phân rã  bảo toàn phụ thuộc hàm ngược lại  không bảo toàn phụ hàm
Ví dụ 14: thực hiện lại ví dụ 13, nghĩa là kiểm tra phép tách có bảo toàn phụ thuộc hàm không?
Vào: Q(C,S,Z),F={CSZ,ZC},Q1(S,Z) và Q2(C,Z)

Đương nhiên ZCG = Q1(F)Q2(F) ZC  (Q1(F)Q2(F))+



  1. Z’=CS

  2. gán Z’= Z’((Z’)+ ): Z’ = CS(SSZ)=CS

Bước 1 và 2 có Z’ không thay đổi, ta sang lược đồ Q2 và tính tiếp Z’

  1. gán Z’= Z’((Z’)+ ): Z’ = CS(CCZ)=CS

Z’không thay đổi và hết lược đồ quan hệ  ngưng không tính tiếp Z’

  1. Vậy =CS CSZ  (Q1(F)  Q2(F))+ phép phân rã không bảo toàn phụ thuộc hàm.

Ví dụ 15: thực hiện lại ví dụ 12 với nội dung kết luận phép tách  có bảo toàn phụ thuộc hàm không (không tính F+)

Vào: Q(A,B,C),F={AB,BC,CA},Q1(A,B) và Q2(B,C)

Hiển nhiên G = Q1(F)  Q2(F)  {AB,BC}



Ta xác định CA có thuộc (Q1(F)  Q2(F))+

  1. Z’=C

  2. gán Z’= Z’((Z’)+ ): Z’ = C(AB)=C

Bước 1 và 2 có Z’ không thay đổi, ta sang lược đồ Q2 và tính tiếp Z’

  1. gán Z’= Z’((Z’)+ ): Z’ = C(ABCBC)=BC

Z’thay đổi  tính tiếp Z’bắt đầu từ lược đồ Q1

  1. gán Z’= Z’((Z’)+ ): Z’ = BC(ABCAB)=ABC

do Z’=Q+  Z’ sẽ không bao giờ thay đổi.

  1. vậy =ABC  CA(Q1(F)  Q2(F))+ phép phân rã bảo toàn phụ thuộc hàm.

    1. THIẾT KẾ CSDL BẰNG CÁCH PHÂN RÃ

      1. Phân rã thành dạng chuẩn BC (hay chuẩn 3) bảo toàn thông tin

        1. Cách thông thường

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ất cả khóa 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]; F1Q1(F)tìm bao đóng của tất cả tập con của XY để suy ra Q1(F)F1

Q2=Q[Q+ -Y] F2Q2(F)tìm bao đóng của tất cả tập con của Q+-Y để suy ra Q2(F)F2

thực hiện thuật toán phân rã (Q1,F1)

thực hiện thuật toán phân rã (Q2,F2)

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.

Ví dụ 16: cho Q(S,D,I,M) F={SID;SDM} 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:

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

i

TNXi

(TNXi)+

Siêu khóa

Khóa



SI

SDIM

SI

SI

D

SID

SDIM

SID




Bước 2: phụ thuộc hàm SD  M  F có SD không là siêu khóa.



Chú ý: để tính được F1,F2,K1,K2 như hình trên, ta phải tính bao đóng của tất cả tập con của{SDM} và {SDI} F1,F2 rồi tìm tất cả khóa của Q1 và Q2.




S+=S

D+

=D

M+

=M




S+=S

D+

=D

I+

=I










SD+

=SDM

SM+

=SM







SD+

=SDM

SI+

=SDIM
















DM+

=DM













DI+

=DI
















SDM+

=SDM













SDI+

=SDIM



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