TÁCH – KẾT NỐI KHÔNG TỔN THẤT THÔNG TIN

Chia sẻ: Do Anh Tuan | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST

Báo xấu

400
lượt xem 23
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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,

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: TÁCH – KẾT NỐI KHÔNG TỔN THẤT THÔNG TIN

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 = 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= , 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 (S), i = 1 ÷ p. Như vậy, nếu ϕ [Ω1 , Ω2 , .. , Ωp ] là một phép tách của s= , 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 (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 |>
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 = 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 = lưu trữ thông tin về khách đặt mua báo , và tương tự trong lược đồ quan hệ S2 = 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. năm Xe n_xe mác màu 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: năm R1 n_xe mác giá R2 mác 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ăm năm năm R1 n_xe R2 màu giá R3 mác 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: năm R12 n_xe giá 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 năm R123 n_xe mác màu 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. 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|>
Học viên: Nhóm 4 – lớp CH10CNK2 Giảng viên: TS.Phạm Thế Quế A1 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|>
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 D E F Ω1 a1 a2 b13 b14 b15 b16 Ω2 a1 a2 a3 a4 b25 b26 Ω3 a1 a2 a3 a4 b35 b36 Ω4 a1 a2 b43 b44 a5 a6 Ω5 a1 b52 a3 a4 a5 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 D E F Ω1 a1 a2 b13 b14 b15 b16 Ω2 a1 a2 a3 a4 b25 b26 Ω3 a1 a2 a3 a4 b35 b36 Ω4 a1 a2 b43 b44 a5 a6 Ω5 a1 b52 a3 a4 a5 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 D E F Ω1 a1 a2 b13 b14 b15 b16 Ω2 a1 a2 a3 a4 b25 b26 Ω3 a1 a2 a3 a4 b35 b36 Ω4 a1 a2 b43 b44 a5 a6 Ω5 a1 a2 a3 a4 a5 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= , 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ế