Đề tài: TÁCH – KẾT NỐI KHÔNG TỔN THẤT THÔNG TIN

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àncá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ộchà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ị....
Nội dung trích xuất từ tài liệu:
Đề tài: TÁCH – KẾT NỐI KHÔNG TỔN THẤT THÔNG TIN ĐỀ TÀITÁCH – KẾT NỐI KHÔNG TỔN THẤT THÔNG TINHọc viên: Nhóm 4 – lớp CH10CNK2 Giảng viên: TS.Phạm Thế Quế Mục lụcMục lục .............................................................................................................................11. Mở đầu..........................................................................................................................22. 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 .........................................................................33. 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ý ....................................................................................................................64. Phép tách bảo toàn phụ thuộc hàm ...............................................................................85. 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 ......................................................106. Kết luận ......................................................................................................................107. Tài liệu tham khảo: .....................................................................................................10Họ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: CH10CNK21. 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 trongquá 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éptách lược đồ quan hệ chưa chuẩn hoá về tập các lược đồ quan hệ chiếu đã được chuẩnhoá, 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ácquan 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àncá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ộchà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 tin2.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 nthuộ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 pcò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ácphụ 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ộctính tương ứng Ωi. Và các lược đồ Si = : = πΩi (S) gọi là các lược đồ chiếu trêncá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ủ ...