Học viên: Nhóm 4 – lớp CH10CNK2
Giảng viên: TS.Phạm Thế Quế
Mục lục
Mục lục.............................................................................................................................1
1. Mở đầu..........................................................................................................................2
2. Phép tách – kết nối không tổn thất thông tin................................................................2
2.1 Phép tách ................................................................................................................2
2.2. Phép chiếu .............................................................................................................2
2.3. Phép nối tự nhiên...................................................................................................3
2.4 Tách - kết nối tự nhiên ...........................................................................................3
2.5 Phép tách không tổn thất thông tin.........................................................................3
3. Thuật toán kiểm tra tách không tổn thất thông tin .......................................................5
3.1 Thuật toán...............................................................................................................5
3.2 Định lý ....................................................................................................................6
4. Phép tách bảo toàn phụ thuộc hàm...............................................................................8
5. Thuật toán kiểm tra bảo toàn phụ thuộc hàm ...............................................................9
5.1. Thuật toán tìm bao đóng của tập thuộc tính ..........................................................9
5.2. Thuật toán kiểm tra bảo toàn phụ thuộc hàm ......................................................10
6. Kết luận ......................................................................................................................10
7. Tài liệu tham khảo:.....................................................................................................10
Học viên: Nhóm 4 – lớp CH10CNK2
Giảng viên: TS.Phạm Thế Quế
TÁCH – KẾT NỐI KHÔNG TỔN THẤT THÔNG TIN
Giảng viên: TS.Phạm Thế Quế
Học viên: Đỗ Anh Tuấn
Lớp: CH10CNK2
1. Mở đầu
Mục tiêu của lý thuyết CSDL là tính độc lập của dữ liệu. Cấu trúc lưu trữ các hệ cơ
sở dữ liệu phản ảnh tính hiện thực, khách quan và tính toàn vẹn dữ liệu. Vì vậy trong
quá trình chuẩn hoá dữ liệu và tìm kiếm thông tin, cần thiết phải thực hiện các phép
tách lược đồ quan hệ chưa chuẩn hoá về tập các lược đồ quan hệ chiếu đã được chuẩn
hoá, sao cho quá trình tách không làm tổn thất thông tin (lossless- mất mát thông tin),
theo nghĩa các quan hệ gốc được khôi phục chính xác từ phép kết nối tự nhiên của các
quan hệ chiếu.
Tách - kết nối các lược đồ quan hệ có làm tổn thất thông tin hay không, có bảo toàn
các phụ thuộc hay không đã được nhiều người quan tâm nghiên cứu, giải quyết. A.V.
Ho , C.Beeri & J.D. Ullman giới thiệu thuật toán xác định phép kết nối các lược đồ
quan hệ không có tổn thất thông tin với giả thiết các phụ thuộc dữ liệu là các phụ thuộc
hàm. Các ông cũng đã mở rộng vấn đề này cho các trường hợp phụ thuộc dữ liệu là
phụ thuộc đa trị.
2. Phép tách – kết nối không tổn thất thông tin
2.1 Phép tách
Cho s = <Ω, F > là một lược đồ quan hệ, trong đó Ω = {A , A ,..., A } là tập các
1
2
n
thuộc tính và F là tập các phụ thuộc hàm. Gọi ϕ[Ω , Ω , .. , Ω ] là một phép tách (hay
1
2
p
còn gọi là một phân hoạch) của S= <Ω, F >, nếu:
a) Ωi Í Ω , i=1÷ p
b) Ω = Ω1 È .. È Ωp
c) Fi:= F|Ωi := πΩi (F ) := {X → Y Î F , XY Í Ωi } , i = 1 ÷ p.
d) Si := <Ωi, Fi>: = πΩi (S), i = 1 ÷ p.
Như vậy, nếu ϕ [Ω1 , Ω2 , .. , Ωp ] là một phép tách của s= <Ω, F >, khi đó tập các
phụ thuộc Fi := F|Ωi = πΩi (F ) được gọi là tập các phụ thuộc chiếu F trên các tập thuộc
tính tương ứng Ωi. Và các lược đồ Si = <Ωi, Fi>: = πΩi (S) gọi là các lược đồ chiếu trên
các tập thuộc tính Ωi với i =1÷ p. Nếu R là một quan hệ trên tập các thuộc tính Ω, khi
đó các quan hệ chiếu sẽ là RΩi : = πΩi (R) , i =1÷ p, nghĩa là các quan hệ chiếu πΩi (R)
chỉ bao gồm các thuộc tính Ωi, i =1÷ p.
2.2. Phép chiếu
Phép chiếu quan hệ Ω trên một số thuộc tính được một quan hệ Ω’. Quan hệ mới có
các thuộc tính là thuộc tính chiếu, có các bộ là một phần của các bộ của quan hệ ban
đầu
Ω’= πAi,Ai+1,…Aj(Ω) với (i≠j)
Học viên: Nhóm 4 – lớp CH10CNK2
Giảng viên: TS.Phạm Thế Quế
2.3. Phép nối tự nhiên
Phép nối tự nhiên của quan hệ Ω1(A1,A2,…An) và quan hệ Ω2(B1,B2,…Bm) là một
quan hệ Ω3 ký hiệu là Ω3= Ω1 |><| Ω2 có thuộc tính là hợp các thuộc tính của hai quan
hệ Ω1, Ω2 và các bộ là ghép nối các bộ của hai quan hệ Ω1, Ω2 theo sự bằng nhau của
các giá trị các thuộc tính chung.
Ω1(A1,A2,…An)|><| Ω2(B1,B2,…Bm)=Ω3(A1,A2,…An, B1,B2,…Bm)
2.4 Tách - kết nối tự nhiên
Phép tách ϕ [Ω1 , Ω2 , .. , Ωp ] được gọi là phép tách - kết nối tự nhiên của của lược
đồ quan hệ S= <Ω, F >, nếu:
a) ϕ [Ω1 , Ω2 , .. , Ωp ] là một phép tách của S= <Ω, F >.
b) Kết quả của phép kết nối tự nhiên của các lược đồ chiếu πΩi (S), i = 1 ÷ p, là một
lược đồ mϕ (S) trên các thuộc tính Ω = Ω È Ω È… È Ω
1
2
p
mϕ (S):=πΩ1 (S) |><| πΩ2 (S) |><| ... |><| πΩp (S) = S1 |><| S2 |><|.. ...... |><| Sp
Nghĩa là với mọi quan hệ RÎS = <Ω, F >, khi đó mϕ(R ) là kết quả phép kết nối tự
nhiên của các quan hệ chiếu tương ứng Ri := RΩi := πΩi (R), i =1 ÷ p, được biểu diễn
như sau: R Í mϕ (R):= πΩ1 (R) |><| πΩ2 (R) |><| ... |><| πΩp (R).
Từ định nghĩa trên có thể suy ra, nếu một thể hiện I Î mϕ (S) khi đó:
P
|><| πΩp (I) = {a1, a2,..., ap}| Nếu Aj Î Ωi , tại vị trí j ứng Ri nhận giá trị aj , các vị trí
i=1
khác nhận giá trị khác ai , i =1 ÷ p
2.5 Phép tách không tổn thất thông tin
Phép tách ϕ [Ω1 , Ω2 , .. , Ωp ] được gọi phép tách không tổn thất thông tin của lược
đồ quan hệ S= <Ω, F >, nếu:
a) ϕ [Ω1 , Ω2 , .. , Ωp ] là phép tách – kết nối tự nhiên
b) S= mϕ (S):=πΩ1 (S) |><| πΩ2 (S) |><| ... |><| πΩp (S) = S1 |><| S2 |><| .... |><| Sp
Nghĩa là với mọi quan hệ R ÎS, khi đó R được khôi phục chính xác từ phép kết nối
tự nhiên của các quan hệ chiếu Ri = πΩi (R ), i = 1 ÷ p.
Tức là: R = πΩ1 (R) |><| πΩ2 (R ) |><| ... |><| πΩp (R ) : = R1 |><| R2 |><| ... |><| Rp
Thông tin của một quan hệ R bất kỳ có thể nhận được từ các quan hệ chiếu Ri ứng
với phép tách ϕ.
Học viên: Nhóm 4 – lớp CH10CNK2
Giảng viên: TS.Phạm Thế Quế
Ví dụ1 : Tách quan hệ không tổn thất thông tin
Lược đồ quan hệ quản lý phát hành báo chí QLBC gồm các thuộc tính:
Ω ={MK#, TK, DC, MB#, TB, GIA, SL}
và F={MK#→TK,MK#→DC,MB#→TB,MB#→ GIA, (MK#,MB#) → SL}
MK#: Mã khách hàng
TK : Tên khách hàng
DC : Địa chỉ khách hàng
MB#: Mã báo, tạp chí
TB : Tên báo, tạp chí
GIA: Đơn giá báo, tạp chí
SL : Số lượng báo, tạp chí khách đặt mua
Trong lược đồ quan hệ QLBC, các thông tin về tên khách (TK) , địa chỉ (DC), tên
báo (TB) .. lặp lại rất nhiều lần trong các quan hệ thể hiện, đó là nguyên nhân dẫn đến
sự xuất hiện các bất thường, nhập nhằng thông tin. Phép tách j được mô tả dưới đây,
sẽ tách lược đồ QLBC thành 3 lược đồ chiếu. Lược đồ S3 = <Ω3, F3> chỉ cần lưu trữ
thông tin về số lượng các loại báo của mỗi một khách hàng đặt mua. Lược đồ quan hệ
S1 = <Ω1 , F1> lưu trữ thông tin về khách đặt mua báo , và tương tự trong lược đồ quan
hệ S2 = <Ω2 , F2> lưu trữ thông tin về các loại báo. Có thể kiểm tra phép tách j không
tổn thất thông tin và bảo toàn được các phụ thuộc hàm.
Phép tách j [Ω , Ω , Ω ] :
1
2
3
• Ω ={M#, TK,DC } , F ={MK# → TK, MK# → DC}.
1
1
• Ω ={MB#, TB, GIA } , F ={MB# → TB, MB# → GIA}.
2
2
• Ω ={M#, MB#, SL} , F ={(MK#,MB#) → SL}.
3
3
Như vậy mục tiêu của phép tách lược đồ quan hệ là nhằm loại bỏ các dị thường
thông tin khi thực hiện các phép lưu trữ như chèn thêm, loại bỏ hay sửa đổi thông tin
trong trong các quan hệ lưu trữ. Tuy nhiên khi thực hiện phép tách, thông tin của lược
đồ quan hệ có bị tổn thất hay không. Nói cách khác nếu kết nối tự nhiên các thành phần
lược đồ quan hệ chiếu, liệu thông tin của lược đồ quan hệ gốc có tổn thất thông tin hay
không, các phụ thuộc hàm có được bảo toàn hay không? Ta xét Ví dụ2
Ví dụ2 : Thí dụ sau mô tả phép tách tổn thất thông tin và không tổn thất thông tin:
Có quan hệ tổng quát về xe. Quan hệ Xe(n_xe,mác,giá,màu,năm) với các thể hiện của
hai xe, khác nhau về nhãn xe và màu sắc.
Xe
n_xe
mác
màu
năm
giá
A11
Honda
Xanh
1995
500
A22
Honda
Đỏ
1995
500
a) Phép tách – kết nối không tổn thất thông tin: phân rã quan hệ xe thành quan hệ
R1(n_xe,mác,giá) và R2(mác, năm, giá) có các thể hiện:
R1
n_xe
mác
giá
R2
mác
năm
giá
A11
Honda
500
Honda
1995
500
A22
Honda
500
Nối tự nhiện theo các thuộc tính cùng tên của hai quan hệ R1 và R2 thu được quan
hệ mới như quan hệ Xe ban đầu
b) Phép tách-kết nối tổn thât thông tin: phân rã quan hệ Xe thành các quan hệ
R1(n_xe, năm), R2(năm, màu, giá) và R3(mác, năm) có các thể hiện:
Học viên: Nhóm 4 – lớp CH10CNK2
Giảng viên: TS.Phạm Thế Quế
n_xe
năm
R2
năm
màu
giá
R3
mác
năm
A11
1995
1995
Xanh
500
Honda 1995
A22
1995
1995
Đỏ
500
Nối tự nhiên theo các thuộc tính cùng tên của hai quan hệ R1 và R2 thu được quan
hệ R12 có thể hiện:
R12
n_xe
giá
năm
màu
A11
500
1995
Xanh
A22
500
1995
Đỏ
A11
500
1995
Đỏ
A22
500
1995
Xanh
Nối tự nhiên theo các thuộc tính cùng tên của hai quan hệ R12 và R3 thu được
quan hệ R123 có thể hiện khác với thể của quan hệ Xe ban đầu
R123
n_xe
mác
màu
năm
Giá
A11
Honda
Xanh
1995
500
A22
Honda
Đỏ
1995
500
A11
Honda
Đỏ
1995
500
A22
Honda
Xanh
1995
500
Trong quan hệ Xe ban đầu ta có thể biết xe số A11 có màu xanh còn trong quan hệ
R123 thông tin về màu của xe A11 đã bị mất.
R1
3. Thuật toán kiểm tra tách không tổn thất thông tin
3.1 Thuật toán
Input:
S = < Ω , F > là một lược đồ quan hệ .
Ω = {A1 , A2 ,.. , An } tập các thuộc tính.
F = {f : Lj → Rj | Lj, Rj Í Ω } tập các phụ thuộc hàm.
j [Ω1 , Ω2 , .. , Ωp ] là một phép tách
Output:
Một khẳng định phép tách - kết nối j có tổn thất thông tin hay không.
Phương pháp:
- Tạo một bảng gồm n cột và p dòng. Cột thứ j tương ứng với thuộc tính Aj , hàng
thứ i tương ứng với lược đồ quan hệ chiếu Ri:
• Cột : A1 , A2 , .. , An
• Hàng: R1, R2 , ...., Rp
- Các phần tử của bảng:
a(i,j) = ai nếu Ai Î Ωi
a(i,j) = bij nếu Ai ∉ Ωi
Với i = 1 ÷ n, j = 1 ÷ p.
- Áp dụng các phụ thuộc X→ YÎ F để thay đổi các giá trị của bảng như sau: tìm
các hàng giống nhau trên trong các cột thuộc tính của X, trong các cột thuộc tính Y nếu
có giá trị là a sẽ thay giá trị các cột trong Y là ai , nếu không có ai , thay thế bằng bij .
- Xét lặp các phụ thuộc trong F cho đến khi không có sự thay đổi trong bảng.
Học viên: Nhóm 4 – lớp CH10CNK2
Giảng viên: TS.Phạm Thế Quế
- Việc duyệt bảng bao gồm sắp xếp bảng theo cột có tính các thuộc tính xuất hiện
vế trái của phụ thuộc hàm. Nếu có k thuộc tính như vậy thì việc thực hiện sắp xếp cần
thực hiện trong n * k bước.
- Điền các ký hiệu trong các cột có thuộc tính xuất hiện vế phải của phụ thuộc hàm
nếu các hàng bằng nhau trên vế trái. Công việc này cầnO(k) thời gian cho mỗi phụ
thuộc. Tổng tất cả độ dài vế trái của tất cả các phụ thuộc hàm trong một lần duyệt
không quá n, nên toàn bộ thời gian cho một lần duyệt nhiều nhất là k*n.
- Khi không còn một ký hiệu nào được làm bằng nhau trong một lần duyệt thì có
thể kết thúc việc lặp các bước duyệt vì bảng thu được thoả mọi phụ thuộc.
- Kiểm tra có tồn tại một hàng Ri sao cho giá trị của chứa các ký hiệu a1, a2,..., an
hay không. Nếu có, tách - kết nối không tổn thất thông tin. Ngược lại, không tồn tại
dòng nào như vậy, nghĩa là các lược đồ quan hệ chiếu khi kết nối bị tổn thất thông tin.
Điều này có thể suy ra từ định nghĩa của phép tách – kết nối tự nhiên.
- Do đó thời gian tiêu dùng toàn bộ cho thuật toán nhiều nhất là k*n2*p, Nếu k ≤ n
4
và p ≤ n hiển nhiên thuật toán có thời gian chi phí nhiều nhất là n .
3.2 Định lý
Bảng kết quả của thuật toán trên cho phép ta kết luận được tính bảo toàn hay
không bảo toàn thông tin của phép tách
Chứng minh:
Ta chứng minh nếu bảng kết quả của thuật toán không có hàng chỉ chứa toán giá
trị a thì phép tách không bảo toàn thông tin. Thật vậy:
Ta xây dựng một quan hệ R có các giá trị như bảng kết quả của thuật toán, các
hàng là các bộ. Quan hệ R thỏa tập phụ thuộc hàm F vì thuật toán đã sửa các giá trị để
R khỏi vi phạm các phụ thuộc hàm trong F, suy ra R là một quan hệ của lược đồ S. Ta
tách quan hệ R thành các quan hệ Ri với Ri = R.Si và dùng phép kết tự nhiên để kết
chúng lại. Nếu:
- $k Sk+ÇSi+ = Æ "iÞR1|><|R2…|><|Rk không tồn tại Þphép tách không bảo toàn
thông tin
- "i, $k Si+ÇSk+ = Xik ≠ Æ mà mỗi Ri đều có một bộ ti chứa toàn giá trị a Þ các ti
nối được với nhau vì có cùng giá trị trên Xik Þ có một bộ tÎ R1|><|R2…|><|Rk có toàn
giá trị a, bộ này lại không có trong R Þ R≠ R1|><|R2…|><|Rk Þ phép tách không bảo
toàn thông tin.
Ta chứng minh nếu bảng kết quả của thuật toán có hàng chỉ chứa toán giá trị a thì
phép tách bảo toàn thông tin. Ta chứng mình điều này qua 2 bước:
Bước 1: chứng minh nếu t Î R Þ tÎ R1|><|R2…|><|Rk . Suy ra RÍ
R1|><|R2…|><|Rk . Giả sử t=(a1, a2,…an) Î R. Ta tách quan hệ R thành các Ri=R.Si với
ti=t.Si. Có 2 trường hợp:
- "i, $k Si+ÇSk+ = Xik ≠ Æ Þ các ti nối được với nhau vì có cùng giá trị trên
Xik Þ bộ tÎ R1|><|R2…|><|Rk ÞRÎ R1|><|R2…|><|Rk
- $k Sk+ÇSi+ = Æ "i Þ bảng kiểm tra bảo toàn thông tin ở giai đoạn chưa
thỏa các phụ thuộc hàm, có dạng:
Học viên: Nhóm 4 – lớp CH10CNK2
A1
Giảng viên: TS.Phạm Thế Quế
A2
…
Ak
Ak+1
…
S1
bk1
bk2
b..
S2
b..
…
…
…
b..
…
…
Sk(A1,A2,… b..
b..
b..
ak
ak+1
…
+
Với mọi XÍQ tk.X ≠ ti.X với i≠k nên khi làm bằng các giá trị theo các phụ thuộc
hàm X→Y thì các giá trị b ở dòng Sk không thay đổi còn các giá trị b ở các cột
Ak,Ak+1…không thay đổi thành a được. Suy ra bảng kết quả của thuật toán không bao
giờ chứa dòng có giá trị toàn a. Vậy trường hợp $k Sk+ÇSi+ = Æ "i không xảy ra khi
bảng kiểm tra bảo toàn thông tin có một dòng toàn a.
Bước 2: Chứng minh nếu tÎ R1|><|R2…|><|Rk ÞtÎR. Suy ra R1|><|R2…|><|Rk
ÍR. Giả sử t=(a1,…an) Î R1|><|R2…|><|Rk theo định nghĩa suy ra "i, $ti sao cho t.Si = ti.
Nhưng Ri=R.Si+ Þ$ti’ Î R sao cho ti’.Si+=t.Si+ "i. Trường hợp xấu nhất là các ti’là các
dòng khác nhau. Trong trường hợp này, ta có thể xem ti’ là dòng Si của bảng kiểm tra
bảo toàn thông tin với các giá trị b xem như chưa biết. Nhưng các dòng Qi phải thỏa
các phụ thuộc hàm trong F, phép làm bằng các giá trị theo các phụ thuộc hàm đã dần
dần xác định được tất cả các giá trị b của một dòng ti’ nào đó, là dòng có toàn giá trị a.
Vậy có một i’ để ti’ = t ÞtÎR ÞR Ê R1|><|R2…|><|Rk . Từ đó suy ra R =
R1|><|R2…|><|Rk. Hay nói cách khác, phép tách bảo toàn thông tin.
Ví dụ3:
Cho Ω :={A,B, C,D, E, F} tập các thuộc tính. Xét phép tách – kết nối j [Ω1, Ω2,
Ω3, Ω4, Ω5] trong đó: Ω1:= {A, B}, Ω2:= {A , C, D}, Ω3:= {B, C, D}, Ω4:= {A, E, F},
Ω5:= {C, D, E} và F := {A → B, CD → A, BC → D, AE → F, CE → D}.
Bước 1: Thành lập bảng ban đầu gồm 5 hàng và 6 cột
A
B
C
D
Ω1
a1
a2
b13
b14
E
b15
F
b16
Ω2
a1
b22
a3
a4
b25
b26
Ω3
b31
a2
a3
a4
b35
b36
Ω4
Ω5
a1
b51
b42
b52
b43
a3
b44
a4
a5
a5
a6
b56
D
b14
a4
a4
b44
a4
E
b15
b25
b35
a5
a5
F
b16
b26
b36
a6
b56
Bước 2: Áp dụng A®B suy ra b22=b42=a2
A
B
C
Ω1
a1
a2
b13
Ω2
a1
a2
a3
Ω3
b31
a2
a3
Ω4
a1
a2
b43
Ω5
b51
b52
a3
Học viên: Nhóm 4 – lớp CH10CNK2
Giảng viên: TS.Phạm Thế Quế
Bước 3: Áp dụng CD®A suy ra b31=b51=a1
A
B
C
Ω1
a1
a2
b13
Ω2
a1
a2
a3
Ω3
a1
a2
a3
Ω4
a1
a2
b43
Ω5
a1
b52
a3
D
b14
a4
a4
b44
a4
E
b15
b25
b35
a5
a5
F
b16
b26
b36
a6
b56
Bước 4: Áp dụng BC®D bảng không thay đổi
Bước 5: Áp dụng AE®F suy ra b56=a6
A
B
C
Ω1
a1
a2
b13
Ω2
a1
a2
a3
Ω3
a1
a2
a3
Ω4
a1
a2
b43
Ω5
a1
b52
a3
D
b14
a4
a4
b44
a4
E
b15
b25
b35
a5
a5
F
b16
b26
b36
a6
a6
Bước 6: Áp dụng CE®D bảng không thay đổi
Bước 7: Quay lại áp dụng A ®B suy ra b52=a2
A
B
C
Ω1
a1
a2
b13
Ω2
a1
a2
a3
Ω3
a1
a2
a3
Ω4
a1
a2
b43
Ω5
a1
a2
a3
D
b14
a4
a4
b44
a4
E
b15
b25
b35
a5
a5
F
b16
b26
b36
a6
a6
Bước 8: Áp dụng CD → A, BC → D, AE → F, CE → D bảng không thay đổi. Ta nhận
thấy trong bảng này tồn tại hàng thứ 5 có chứa đủ các ký hiệu {a1, a2, a3, a4, a5, a6}.
Suy ra phép tách – kết nối j là không tổn thất thông tin.
4. Phép tách bảo toàn phụ thuộc hàm
Phép tách j [Ω1, Ω2 , .. , Ωp] của lược đồ quan hệ S= <Ω, F >, và một tập phụ thuộc
hàm F. Hình chiếu của F trên một tập các thuộc tính Ωi ký hiệu là πQi(F) là tập các phụ
thuộc hàm X→ Y ÎF+ với XYÍ Ωi. Hay πQi(F)=Fi+={X→Y|X→YÎF+ và XYÍ Ωi}.
Khi đó phép tách j là bảo toàn phụ thuộc hàm F nếu: F º È πQi(F)
Ví dụ 4: Mô tả phép tách bảo toàn phụ thuộc hàm
Cho lược đồ quan hệ Q(A,B,C) và F={A®B,B ®C, C ®A}. Phép phân rã
j=[Q1,Q2] tách Q thành Q1(A,B) và Q2(B,C). Phép phân rã trên có bảo toàn phụ thuộc
hàm F không?
Học viên: Nhóm 4 – lớp CH10CNK2
Giảng viên: TS.Phạm Thế Quế
Ta tính cho Q1:
Bước 1: Liệt kê các tập con của Q1: Æ,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
Ta tính cho Q2:
Bước 4: Liệt kê các tập con của Q2: Æ,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 F1+=πQ2(F): B®C,C®B, B ®BC,C ®BC
Bước 7: G=πQ1(F)È πQ2(F)={A®B,B®A, A ®AB,B ®AB, B®C,C®B, B
®BC,C ®BC}. Mà 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+=ABC
suy ra 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
Ví dụ 5: Mô tả phép tách không bảo toàn phụ thuộc hàm
Cho lược đồ quan hệ Q(C,S,Z) và F={CS®Z,Z ®C}. Phép phân rã j=[Q1,Q2] tách
Q thành Q1(S,Z) và Q2(C,Z). Phép phân rã trên có bảo toàn phụ thuộc hàm F không?
Ta tính cho Q1:
Bước 1: Liệt kê các tập con của Q1: Æ,S,Z,SZ
Bước 2: tính bao đóng của các tập con của Q1: Æ+= Æ, S+=S,Z+=ZC,
SZ+=CSZ
Bước 3: F1+ chỉ bao 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,Z®ZC, SZ ®C,SZ ®CS, SZ ®CZ,
SZ ®CSZ
Ta tính cho Q2:
Bước 4: Liệt kê các tập con của Q2: Æ,Z,C,CZ
Bước 5: tính bao đóng của các tập con của Q2: Æ+= Æ, C+=C,Z+=ZC,
CZ+=CZ
Bước 6: tính F1+=πQ2(F): Z®C,Z®ZC
Bước 7: G=πQ1(F)ÈπQ2(F)={Z®C,Z®ZC} 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
5. Thuật toán kiểm tra bảo toàn phụ thuộc hàm
5.1. Thuật toán tìm bao đóng của tập thuộc tính
Input: j [Ω1, Ω2 , .. , Ωp ], F, tập thuộc tính X
Output: X+
Phương pháp:
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: Thay thế Z’=Z’ È ((Z’ÇQi+)+ Ç Qi+)
Học viên: Nhóm 4 – lớp CH10CNK2
Giảng viên: TS.Phạm Thế Quế
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 X+)
5.2. Thuật toán kiểm tra bảo toàn phụ thuộc hàm
Input: j [Ω1, Ω2 , .. , Ωp ], F
Output: Một khẳng định phép tách j có bảo toàn phụ thuộc hàm hay không?
Phương pháp:
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 hàm X→ Y ÎF đều thuộc È πQi(F)+ thì ta kết luận
phép tách j bảo toàn phụ thuộc hàm và ngược lại j không bảo toàn phụ thuộc hàm
Ví dụ 6: Áp dụng thuật toán kiểm tra bảo toàn phụ thuộc hàm với ví dụ 4
Input: Q(A,B,C), F={A®B,B ®C, C ®A}, Q1(A,B) và Q2(B,C).
Phương pháp: 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))+ hay không?
Bước 1. Gán Z’=C
Bước 2. Gán Z’=Z’ È((Z’ÇQ1+)+ÇQ1+)ÛZ’=C È(ÆÇAB)=C. Bước 1 và 2 Z’
không thay đổi ta sang lược đồ Q2 và tính tiếp Z’
Bước 3: Gán Z’=Z’ È((Z’ÇQ2+)+ÇQ2+)ÛZ’=CÈ(ABCÇBC)=BC. Tại đây Z’ thay
đổi nên ta tính tiếp Z’ từ lược đồ Q1
Bước 4: Gán Z’=Z’ È((Z’ÇQ1+)+ÇQ1+)ÛZ’=BCÈ(ABCÇAB)=ABC. Do Z’=Q+
nên Z’ sẽ không bao giờ thay đổi
Bước 5: Vậy CG+=ABC suy ra C ®A Î (πQ1(F)È πQ2(F))+ nên phép phân rã bảo
toàn phụ thuộc hàm
6. Kết luận
Khi thiết kế CSDL quan hệ đòi hỏi tìm được một tập các lược đồ quan hệ “tốt”,
nhằm: Tránh dư thừa dữ liệu; Tránh bất thường khi sửa dữ liệu; Đảm bảo mối quan hệ
giữa các thuộc tính đều được thể hiện; Có thể kiểm tra việc cập nhật dữ liệu có vi phạm
ràng buộc CSDL không
Để thực hiện được điều đó cần thiết phải chuẩn hóa dữ liệu và trong quá trình
chuẩn hóa dữ liệu cần thiết phải thực hiện các phép tách lược đồ quan hệ chưa chuẩn
hóa về tập các lược đồ quan hệ chiếu đã được chuẩn hóa sao cho quá trình tách không
làm tổn thất thông tin và bảo toàn được các phụ thuộc hàm
7. Tài liệu tham khảo:
[1] TS. Phạm Thế Quế. Cơ sở dữ liệu. Học viện công nghệ bưu chính viễn thông. Hà
Nội – 2006.
[2] Đỗ Trung Tuấn. Cơ sở dữ liệu. Nhà xuất bản giáo dục 1998.
Học viên: Nhóm 4 – lớp CH10CNK2
Giảng viên: TS.Phạm Thế Quế
- Xem thêm -