F F1tt={ACDE,ACDB,ACDI,CEA,CED}
Mọi phụ thuộc hàm của F1tt đều có vế trái là siêu khóa Q đạt dạng chuẩn BC
Ví dụ 8: Q(SV,MH,THAY)F = {SV,MH THAY;THAY MH}
Quan hệ trên đạt chuẩn 3 nhưng không đạt chuẩn BC..
Ví dụ 9:
Chẳng hạn cho Q(A,B,C,D) và F={AB C; D B; C ABD}
thì Q là 3NF nhưng không là BCNF
Nếu F={B D,A C,C ABD} là 2 NF nhưng không là 3 NF
Thuật toán kiểm tra dạng chuẩn của một lược đồ quan hệ.
Vào: lược đồ quan hệ Q, tập phụ thuộc hàm F
Ra: khẳng định Q đạt chuẩn gì?
Bước 1: Tìm tất cả khóa của Q
Bước 2: Kiểm tra chuẩn BC nếu đúng thì Q đạt chuẩn BC, kết thúc thuật toán
ngược lại qua bước 3
Bước 3: Kiểm tra chuẩn 3 nếu đúng thì Q đạt chuẩn 3, kết thúc thuật toán
ngược lại qua bước 4
Bước 4: Kiểm tra chuẩn 2 nếu đúng thì Q đạt chuẩn 2, kết thúc thuật toán.
ngược lại Q đạt chuẩn 1
Định nghĩa: Dạng chuẩn của một lược đồ cơ sở dữ liệu là dạng chuẩn thấp nhất trong các dạng chuẩn của các lược đồ quan hệ con.
-
PHÉP TÁCH KẾT NỐI BẢO TOÀN
-
Phép tách kết nối bảo toàn thông tin (lossless-join decomposition)
Cho lược đồ quan hệ Q(TENNCC,DIACHI,SANPHAM,DONGIA) có quan hệ tương ứng là r
Đặt r1 là quan hệ có được bằng cách chiếu r lên Q1(TENNCC,SANPHAM,DONGIA),
Đặt r2 là quan hệ có được bằng cách chiếu r lên Q2(TENNCC,DIACHI)
Đặt r’là quan hệ có được bằng cách kết tự nhiên giữa r1 và r2 qua TENNCC.
chẳng hạn:
r
|
|
|
|
TENNCC
|
DIACHI
|
SANPHAM
|
DONGIA
|
Hung
|
12 Nguyễn Kiệm
|
Gạch ống
|
200
|
Hung
|
12 Nguyễn Kiệm
|
Gạch thẻ
|
250
|
Hung
|
40 Nguyễn Oanh
|
Gạch ống
|
200
|
r2 = r.Q2+
|
|
r1 = r.Q1+
|
TENNCC
|
DIACHI
|
|
TENNCC
|
SANPHAM
|
DONGIA
|
Hung
|
12 Nguyễn Kiệm
|
|
Hung
|
Gạch ống
|
200
|
Hung
|
40 Nguyễn Oanh
|
|
Hung
|
Gạch thẻ
|
250
|
TENNCC
r’ = r1|><|r2
|
TENNCC
|
DIACHI
|
SANPHAM
|
DONGIA
|
Hung
|
12 Nguyễn Kiệm
|
Gạch ống
|
200
|
Hung
|
12 Nguyễn Kiệm
|
Gạch thẻ
|
250
|
Hung
|
40 Nguyễn Oanh
|
Gạch ống
|
200
|
Hung
|
40 Nguyễn Oanh
|
Gạch thẻ
|
250
|
Kết quả là r r’ hay r r.Q1|><|r.Q2.
Với kết quả trên, ta nói phép tách (Q1,Q2) tách Q thành Q1, Q2 là tách-kết nối (phân rã) mất mát thông tin.
Nếu r = r.Q1|><|r.Q2 ta nói phép tách (Q1,Q2) là tách-kết nối không mất mát thông tin (tách kết nối bảo toàn thông tin hay phân rã bảo toàn thông tin).
Vậy với điều kiện nào thì phép tách trở thành tách-kết nối không mất mát thông tin?
-
Định nghĩa phép tách Q thành 2 lược đồ con
Q là lược đồ quan hệ, Q1, Q2 hai lược đồ con có:
Q1+ Q2+ = X
Q1+ Q2+ = Q+
Nói rằng lược đồ quan hệ Q được tách thành hai lược đồ con Q1, Q2 theo phép tách (Q1,Q2) là phép tách kết nối không mất (hay phép tách bảo toàn thông tin) nếu với r là quan hệ bất kỳ của Q ta có:
r = r.Q1r.Q2
Tức là r được tạo nên từ phép kết nối tự nhiên của các hình chiếu của nó trên các Q1,Q2
-
Tính chất
Nếu Q là một lược đồ quan hệ, Q1,Q2 là hai lược đồ quan hệ con có
Q1+ Q2+ = X
Q1+ Q2+ = Q+
X Q2+
Thì r = r.Q1r.Q2
Chứng minh:
t r t r.Q1r.Q2
t r t1r1 t1 = t.Q1 t2r2 t2 = t.Q2 t1.X = t2.X = t.X
t r.Q1r.Q2 (Theo định nghĩa)
t r.Q1r.Q2 t r
t r.Q1r.Q2 t1r1 t1 = t.Q1 (1)
mà t1 r1=r.Q1 nên theo định nghĩa phép chiếu ta lại có t’r t1 = t’.Q1 (2)
(1) và (2) t’.Q1 = t.Q1 t’.X = t.X t’.Q2 = t.Q2 (do X Q2)
t’ = t t r
Ví dụ 10: cho Q(SAIP), Q1 =(SA) , Q2 =(SIP) F={SA,SIP}. Hỏi việc tách Q thành Q1 và Q2 có gây ra mất mát thông tin không?
Áp dụng tính chất trên, ta có
Q1+ Q2+ = S
Q1+ Q2+ = SAIP = Q+
S SA = Q1+
Theo tính chất trên, với mọi quan hệ r của Q ta luôn có r = r.Q1r.Q2. Suy ra phép tách trên là phép tách kết nối bảo toàn thông tin.
-
Phép tách Q thành n lược đồ con
Q là một lược đồ quan hệ, F là tập phụ thuộc hàm. Q được tách thành các lược đồ con Q1, Q2, Q3...,Qn theo từng bước mà ở mỗi bước một lược đồ được tách thành hai lược đồ con và thỏa mãn điều kiện của tính chất bảo toàn thông tin thì với r là quan hệ bất kỳ của Q ta luôn có:
r = r.Q1|><|r.Q2|><|r.Q3..... |><|r.Qn
Chứng minh:
Ta chứng minh bằng phương pháp qui nạp.
Ở bước i = 1 thì r = r.Q1|><|r.Q1m đúng theo định lý bảo toàn thông tin
Giả sử biểu thức trên đúng ở bước i = k nghĩa là ta có:
r = r.Q1|><|r.Q2|><|r.Q3..... |><|r.Qk |><|r.Qkm (1)
ta phải chứng minh r = r.Q1|><|r.Q2|><|r.Q3.....|><|r.Qk|><|r.Qk+1|><|r.Qk+1m
Với Qkm được tách thành hai lược đồ con Qk+1 và Qk+1m theo đúng điều kiện của tính chất bảo toàn thông tin nghĩa nếu s là quan hệ của Qkm thì s = s.Qk+1|><|s.Qk+1m
r.Qkm = (r.Qkm).Qk+1|><|(r.Qkm).Qk+1m = r.Qk+1|><|r.Qk+1m
r = r.Q1|><|r.Q2|><|r.Q3.....|><|r.Qk|><|r.Qk+1|><|r.Qk+1m
-
Thuật toán kiểm tra phép tách kết nối bảo toàn thông tin
-
Thuật toán
Dữ liệu vào: lược đồ quan hệ Q(A1,A2,…An), tập phụ thuộc hàm F, phép tách =(Q1,Q2,…,Qk).
Dữ liệu ra: kết luận phép tách có phải là phép tách bảo toàn thông tin ?
-
Thiết lập bảng với k+1 dòng, n+1 cột . Cột j ứng với thuộc tính Aj (j=1...n), hàng i ứng với lược đồ quan hệ Qi(i=1…k). Tại ví trí hàng i, cột j ta điền ký hiệu Aj nếu Aj Qi, nếu không ta đặt ký hiệu bt vào vị trí đó. (với t đầu tiên bằng 1) và sau đó tăng t lên một đơn vị.
-
Xét lần lượt các phụ thuộc hàm trong F, áp dụng cho bảng vừa mới thành lập ở trên. Giả sử xét (X Y) F, chúng ta tìm những hàng giống nhau ở tất cả các thuộc tính của X, nếu thấy những hàng như vậy ta sẽ làm cho các ký hiệu của hai hàng này bằng nhau ở tất cả các thuộc tính của Y. Khi làm cho 2 ký hiệu này bằng nhau, nếu một trong hai ký hiệu là aj thì cho ký hiệu kia trở thành aj, nếu hai ký hiệu là bk hoặc bl thì có thể cho chúng trở thành bt hoặc bt (với t = min (k,l)). Bước này được tiếp tục cho các phụ thuộc hàm còn lại của F cho đến khi không còn áp dụng được nữa.
-
Xét bảng kết quả, nếu thấy trong bảng này có một hàng chứa toàn aj (i=1..n) thì kết luận đó là phép kết nối bảo toàn thông tin, ngược lại là phép kết nối mất mát thông tin.
Chú ý: một điều quan trọng cần phải nhớ là khi cho hai ký hiệu bằng nhau thì phải cho bằng nhau ở tất cả các xuất hiện của chúng trong bảng chứ không phải chỉ cho bằng nhau ở những ký hiệu trong phạm vi các phụ thuộc X Y F.
Ví dụ 11: Với Q(ABCDE)
Q1 = (AD),Q2 =(AB), Q3 =(BE), Q4 =(CDE), Q5 =(AE)
F = {AC,BC,AD,DEC,CEA}
Kiểm tra tính bảo toàn thông tin của phép phân rã Q thành Q1,Q2,Q3,Q4,Q5.
-
Bước 1:
|
a1
|
a2
|
a3
|
a4
|
a5
|
|
Bước 2:
|
Điền b1,b2,b3, ...
|
|
A
|
B
|
C
|
D
|
E
|
|
|
A
|
B
|
C
|
D
|
E
|
Q1(AD)
|
a1
|
|
|
a4
|
|
|
Q1(AD)
|
a1
|
b1
|
b2
|
a4
|
b3
|
Q2(AB)
|
a1
|
a2
|
|
|
|
|
Q2(AB)
|
a1
|
a2
|
b4
|
b5
|
b6
|
Q3(BE)
|
|
a2
|
|
|
a5
|
|
Q3(BE)
|
b7
|
a2
|
b8
|
b9
|
a5
|
Q4(CDE)
|
|
|
a3
|
a4
|
a5
|
|
Q4(CDE)
|
b10
|
b11
|
a3
|
a4
|
a5
|
Q5(AE)
|
a1
|
|
|
|
a5
|
|
Q5(AE)
|
a1
|
b12
|
b13
|
b14
|
a5
|
-
Sửa bảng giá trị để nó thỏa AC
Sửa b4,b13 thành b2
|
|
Sửa bảng giá trị để nó thỏa BC
Sửa b8 thành b2
|
|
A
|
B
|
C
|
D
|
E
|
|
|
A
|
B
|
C
|
D
|
E
|
Q1(AD)
|
a1
|
b1
|
b2
|
a4
|
b3
|
|
Q1(AD)
|
a1
|
b1
|
b2
|
a4
|
b3
|
Q2(AB)
|
a1
|
a2
|
b2
|
b5
|
b6
|
|
Q2(AB)
|
a1
|
a2
|
b2
|
b5
|
b6
|
Q3(BE)
|
b7
|
a2
|
b8
|
b9
|
a5
|
|
Q3(BE)
|
b7
|
a2
|
b2
|
b9
|
a5
|
Q4(CDE)
|
b10
|
b11
|
a3
|
a4
|
a5
|
|
Q4(CDE)
|
b10
|
b11
|
a3
|
a4
|
a5
|
Q5(AE)
|
a1
|
b12
|
b2
|
b14
|
a5
|
|
Q5(AE)
|
a1
|
b12
|
b2
|
b14
|
a5
|
Chia sẻ với bạn bè của bạn: |