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
2
1 n ] là một phép tách (hay
Cho s = <Ω, F > là một lược đồ quan hệ, trong đó Ω = {A , A ,..., A } là tập các
Ωi
, Ω 2 , .. , Ω p thuộc tính và F là tập các phụ thuộc hàm. Gọi ϕ[Ω 1 còn gọi là một phân hoạch) của S= <Ω, F >, nếu:
} , i = 1 ÷ p. (F ) := {X → Y Î F , XY Í Ωi (S), i = 1 ÷ p. Í Ω , i=1÷ p a) Ωi È .. È Ωp b) Ω = Ω1 c) Fi:= F|Ωi := π d) Si := <Ωi, Fi>: = π
Ωi
Ωi ] là một phép tách của s= <Ω, F >, khi đó tập các , Ω2 (F ) được gọi là tập các phụ thuộc chiếu F trên các tập thuộc (S) gọi là các lược đồ chiếu trên Ω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 (R)
, .. , Ωp Như vậy, nếu ϕ [Ω1 = π := F|Ωi = <Ωi, Fi>: = π
Ωi
Ωi
(R) , i =1÷ p, nghĩa là các quan hệ chiếu π : = π
phụ thuộc Fi tính tương ứng Ωi. Và các lược đồ Si các tập thuộc tính Ωi đó các quan hệ chiếu sẽ là R Ωi 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
] được gọi là phép tách - kết nối tự nhiên của của lược , Ω2 , .. , Ωp Phép tách ϕ [Ω1
Ωi
đồ quan hệ S= <Ω, F >, nếu: , Ω2 , .. , Ωp ] là một phép tách của S= <Ω, F >. a) ϕ [Ω1 b) Kết quả của phép kết nối tự nhiên của các lược đồ chiếu π (S), i = 1 ÷ p, là một
lược đồ m (S) trên các thuộc tính Ω = Ω È Ω 1 È… È Ω 2
ϕ (S):=π
Ω1
Ω2
Ωp
ϕ
ϕ
(S) |><| π (S) |><| ... |><| π m (S) = S1 |><|.. ...... |><| Sp
Ωi
Nghĩa là với mọi quan hệ RÎS = <Ω, F >, khi đó m := π := R p |><| S2 (R ) là kết quả phép kết nối tự (R), i =1 ÷ p, được biểu diễn nhiên của các quan hệ chiếu tương ứng Ri
Ωi (R) |><| ... |><| π
Ω2
Ω1
ϕ
(R):= π (R) |><| π (R). như sau: R Í m
Ωp 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
] được gọi phép tách không tổn thất thông tin của lược , Ω2 , .. , Ωp Phép tách ϕ [Ω1
] là phép tách – kết nối tự nhiên
đồ quan hệ S= <Ω, F >, nếu: , Ω2 , .. , Ωp (S):=π
a) ϕ [Ω1 b) S= m
(S) |><| π
(S) |><| ... |><| π
(S) = S1
Ω1
Ω2
Ωp
|><| S2
|><| .... |><| Sp
ϕ
Ωi
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 (R ), i = 1 ÷ p. tự nhiên của các quan hệ chiếu Ri = π
Ω2
Ωp
Ω1
(R ) |><| ... |><| π (R) |><| π |><| ... |><| Rp (R ) : = R1 |><| R2
Tức là: R = π 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ế
TK : Tên khách hàng MB#: Mã báo, tạp chí GIA: Đơn giá báo, tạp chí 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 DC : Địa chỉ khách hàng TB : Tên 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 ={MK# → TK, MK# → DC}. ={M#, TK,DC } , F • Ω 1 1 ={MB# → TB, MB# → GIA}. ={MB#, TB, GIA } , F • Ω 2 2 ={(MK#,MB#) → SL}. ={M#, MB#, SL} , F • Ω 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
mác Honda Honda năm 1995 1995 n_xe A11 A22 giá 500 500 màu Xanh Đỏ 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 R2 R1(n_xe,mác,giá) và R2(mác, năm, giá) có các thể hiện: mác Honda năm 1995 giá 500
n_xe A11 A22 mác Honda Honda giá 500 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ế
R1 R2 R3
mác năm Honda 1995 n_xe A11 A22 năm 1995 1995 năm màu 1995 Xanh 1995 Đỏ giá 500 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 A11 A22 A11 A22 giá 500 500 500 500 năm 1995 1995 1995 1995 màu Xanh Đỏ Đỏ 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 mác Honda Honda Honda Honda màu Xanh Đỏ Đỏ Xanh n_xe A11 A22 A11 A22 năm 1995 1995 1995 1995 Giá 500 500 500 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.
3. Thuật toán kiểm tra tách không tổn thất thông tin
} tập các thuộc tính. , A2 ,.. , An
, .. , Ωp
, hàng 3.1 Thuật toán Input: S = < Ω , F > là một lược đồ quan hệ . Ω = {A1 F = {f : Lj → Rj | Lj, Rj Í Ω } tập các phụ thuộc hàm. j [Ω1 ] là một phép tách , Ω2 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
thứ i tương ứng với lược đồ quan hệ chiếu Ri: , .. , An • Cột : A1 , A2 , ...., Rp • Hàng: R1, R2 - 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.
4
- 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
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:
+ = Æ "iÞR1|><|R2…|><|Rk không tồn tại Þphép tách không bảo toàn
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: +ÇSi - $k Sk
thông tin
+Ç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.
- "i, $k Si
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: +ÇSk
+ = Xik ≠ Æ Þ các ti nối được với nhau vì có cùng giá trị trên
+ = Æ "i Þ bảng kiểm tra bảo toàn thông tin ở giai đoạn chưa
+ÇSi
- "i, $k Si Xik Þ bộ tÎ R1|><|R2…|><|Rk ÞRÎ R1|><|R2…|><|Rk - $k Sk thỏa các phụ thuộc hàm, có dạng:
Học viên: Nhóm 4 – lớp CH10CNK2 Giảng viên: TS.Phạm Thế Quế
A1
+ÇSi
A2 b.. … b.. … b.. … … … S1 S2 … Sk(A1,A2,… b.. Ak bk1 b.. b.. ak Ak+1 bk2 … … ak+1
+ Þ$ti’ Î R sao cho ti’.Si
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 + = Æ "i không xảy ra khi giờ chứa dòng có giá trị toàn a. Vậy trường hợp $k Sk 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. + "i. Trường hợp xấu nhất là các ti’là các +=t.Si Nhưng Ri=R.Si 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:
B a2 A a1 F b16 C b13 E b15 D b14
a4 a1 a3 b22 b25 b26
a2 a3 b31 b35 b36 a4
a1 b51 b44 a4 b43 a3 b42 b52 a6 b56 a5 a5
A a1 a1 b31 a1 b51 F b16 b26 b36 a6 b56 E b15 b25 b35 a5 a5 B a2 a2 a2 a2 b52 D b14 a4 a4 b44 a4 C b13 a3 a3 b43 a3
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 Ω1 Ω2 Ω3 Ω4 Ω5 Bước 2: Áp dụng A®B suy ra b22=b42=a2 Ω1 Ω2 Ω3 Ω4 Ω5
Học viên: Nhóm 4 – lớp CH10CNK2 Giảng viên: TS.Phạm Thế Quế
A a1 a1 a1 a1 a1 B a2 a2 a2 a2 b52 C b13 a3 a3 b43 a3 D b14 a4 a4 b44 a4 E b15 b25 b35 a5 a5 F b16 b26 b36 a6 b56
C b13 a3 a3 b43 a3 B a2 a2 a2 a2 b52 A a1 a1 a1 a1 a1 D b14 a4 a4 b44 a4 E b15 b25 b35 a5 a5 F b16 b26 b36 a6 a6
Bước 3: Áp dụng CD®A suy ra b31=b51=a1 Ω1 Ω2 Ω3 Ω4 Ω5 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 Ω1 Ω2 Ω3 Ω4 Ω5 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
Ω1 Ω2 Ω3 Ω4 Ω5 A a1 a1 a1 a1 a1 B a2 a2 a2 a2 a2 C b13 a3 a3 b43 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:
+=πQ1(F): A®B,B®A, A ®AB,B ®AB
+=πQ2(F): B®C,C®B, B ®BC,C ®BC
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 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 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 +=ABC 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 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 + chỉ bao gồm các phụ thuộc hàm hiển nhiên vì tất cả các phụ Bước 3: F1 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:
tương đương với
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 +=πQ2(F): Z®C,Z®ZC Bước 6: tính F1 Bước 7: G=πQ1(F)ÈπQ2(F)={Z®C,Z®ZC} không 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
+)+ Ç Qi
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
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+)
+ với G = È πQi(F) + thì X→ Y Î È πQi(F)+
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 Bước 3: Nếu YÍ XG 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
+)ÛZ’=C È(ÆÇAB)=C. Bước 1 và 2 Z’
có thuộc (πQ1(F)È πQ2(F))+ hay không?
+)+ÇQ1
+)ÛZ’=CÈ(ABCÇBC)=BC. Tại đây Z’ thay
+)+ÇQ2
+)ÛZ’=BCÈ(ABCÇAB)=ABC. Do Z’=Q+
Bước 1. Gán Z’=C Bước 2. Gán Z’=Z’ È((Z’ÇQ1 không thay đổi ta sang lược đồ Q2 và tính tiếp Z’
+)+ÇQ1
+=ABC suy ra C ®A Î (πQ1(F)È πQ2(F))+ nên phép phân rã bảo
Bước 3: Gán Z’=Z’ È((Z’ÇQ2 đổi nên ta tính tiếp Z’ từ lược đồ Q1 Bước 4: Gán Z’=Z’ È((Z’ÇQ1 nên Z’ sẽ không bao giờ thay đổi
Bước 5: Vậy CG 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.
