Bước 4: Tính Q1(F), Q2(F)
Q1(F)= F1+ ={AB,AAB,BA,BAB}{AB,BA} (chỉ lấy pth có vế phải 1 tt)
Q2(F)= F2+ ={BC,BBC,CB,CBC}{BC,CB}(chỉ lấy pth có vế phải 1 tt)
Bước 5:
G = Q1(F) Q2(F)={AB,AAB,BA,BAB,BC,BBC,CB,CBC}
F={AB,BC,CA} có AB, BC đều là thành viên của G, còn CA có là thành viên của G hay không ta tính CG+. CG+=ABC CA 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+
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)
Tính cho Q2
Bước 4: Kê tất cả tập con của Q2+
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 7:
G=Q1(F)Q2(F)={AB,AAB,BA,BAB,BC,BBC,CB,CBC}
F={AB,BC,CA} có AB, BC đều là thành viên của G còn CA có là thành viên của G hay không ta tính CG+. CG+=ABC CA 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.
-
Ý 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={CSZ,ZC}. 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:
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:
ZC
|
SZC
|
ZZC
|
SZCS
|
|
SZCZ
|
|
SZCSZ
|
Q2 có các tập thuộc tính con:
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:
Q1(F)Q2(F)={ZC,ZZC}{ZC} không tương đương với F = {CSZ,ZC}
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 CSZ
Q1(F)={PTHHN}
|
Q2(F)={ZC, ZZC}
|
F={CSZ,ZC}
|
Q1
|
(S
|
Z)
|
Q2
|
(C
|
Z)
|
Q
|
(C
|
S
|
Z)
|
|
s1
|
z1
|
|
c1
|
z1
|
|
c1
|
s1
|
z1
|
|
s1
|
z2
|
|
c1
|
z2
|
|
c1
|
s1
|
z2
| -
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 XYF 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 XYF 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ì XY Qi(F)+
Bước 4: Nếu tất cả phụ thuộc XYF đề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={CSZ,ZC},Q1(S,Z) và Q2(C,Z)
Đương nhiên ZCG = Q1(F)Q2(F) ZC (Q1(F)Q2(F))+
-
Z’=CS
-
gán Z’= Z’((Z’)+ ): Z’ = CS(SSZ)=CS
Bước 1 và 2 có Z’ không thay đổi, ta sang lược đồ Q2 và tính tiếp Z’
-
gán Z’= Z’((Z’)+ ): Z’ = CS(CCZ)=CS
Z’không thay đổi và hết lược đồ quan hệ ngưng không tính tiếp Z’
-
Vậy =CS CSZ (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={AB,BC,CA},Q1(A,B) và Q2(B,C)
Hiển nhiên G = Q1(F) Q2(F) {AB,BC}
Ta xác định CA có thuộc (Q1(F) Q2(F))+
-
Z’=C
-
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’
-
gán Z’= Z’((Z’)+ ): Z’ = C(ABCBC)=BC
Z’thay đổi tính tiếp Z’bắt đầu từ lược đồ Q1
-
gán Z’= Z’((Z’)+ ): Z’ = BC(ABCAB)=ABC
do Z’=Q+ Z’ sẽ không bao giờ thay đổi.
-
vậy =ABC CA(Q1(F) Q2(F))+ phép phân rã bảo toàn phụ thuộc hàm.
-
THIẾT KẾ CSDL BẰNG CÁCH PHÂN RÃ
-
Phân rã thành dạng chuẩn BC (hay chuẩn 3) bảo toàn thông tin
-
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]; F1Q1(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] F2Q2(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={SID;SDM} 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
Xi
|
TNXi
|
(TNXi)+
|
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
|
|
Chia sẻ với bạn bè của bạn: |