chương 1. CÁC LỚP PHỤ THUỘC XẤP XỈ TRONG CƠ SỞ DỮ LIỆU 34 2. Xây dựng hàm lambda và độ đo. Đề xuất phụ thuộc hàm xấp xỉ tổng quát.
Xây dựng lược đồ quan hệ xấp xỉ thông qua độ đo. Phụ thuộc yếu. Đề xuất phụ thuộc yếu xấp xỉ. Đề xuất phụ thuộc Boole dương xấp xỉ.
Đề xuất thuộc Boole dương xấp xỉ tổng quát. Xây dựng phép sánh trị alpha dựa trên hàm lambda. Phụ thuộc Boole dương xấp xỉ tổng quát. Kết luận chương 2.
CÁC THUẬT TOÁN XỬ LÝ LƯỢC ĐỒ QUAN HỆ. Xây dựng phương pháp chuyển công thức logic về dạng chuẩn hội. Phương pháp logic. Phương pháp lập bảng.
Xây dưng phương pháp chứng minh công thức hằng đúng. Phương pháp chứng minh trực tiếp theo CNF. Phương pháp Vương Hạo. Phương pháp hợp giải.
Xây dựng thuật toán suy dẫn trong lược đồ quan hệ. Suy dẫn trong lược đồ quan hệ với phụ thuộc hàm. Các bài toán liên quan đến phụ thuộc dữ liệu. Thuật toán suy dẫn.
Xây dựng thuật toán tìm bao đóng với phụ thuộc Booe dương tổng quát. Xây dựng thuật toán tìm khóa với phụ thuộc Booe dương tổng quát. Kết luận chương 3. 75 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN.
76 DANH MỤC CÔNG TRÌNH ĐÃ CÔNG BỐ.79 TÀI LIỆU THAM KHẢO. 80 vii DANH MỤC THUẬT NGỮ, CÁC CHỮ VIẾT TẮT Ký hiệu Mô tả CSDL Cơ sở dữ liệu CSDLQH Cơ sở dữ liệu quan hệ CTB Công thức Boole CTBD Công thức Boole dương Đpcm Điều phải chứng minh CNF Công thức logic dạng chuẩn hội GT Giả thiết KL Kết luận LClosure Thuật toán bao đóng trong phụ thuộc logic LĐQH Lược đồ quan hệ LĐXX Lược đồ xấp xỉ NPC Lớp thuật toán NP- đầy đủ PTBD Phụ thuộc Boole dương PTBDTQ Phụ thuộc Boole dương tổng quát PTH Phụ thuộc hàm PTHXX Phụ thuộc hàm xấp xỉ PTHM Phụ thuộc hàm mạnh PTMTQ Phụ thuộc mạnh tổng quát PTY Phụ thuộc yếu PTYTQ Phụ thuộc yếu tổng quát Unif Thuật toán hợp giải PTNL Phụ thuộc nới lỏng PTHNL Phụ thuộc hàm nới lỏng PTBDXX Phụ thuộc Boole dương xấp xỉ PTBDXXTQ Phụ thuộc Boole dương xấp xỉ tổng quát PTYXX Phụ thuộc yếu xấp xỉ HSK Hàm sai khác PTHSK Phụ thuộc hàm sai khác viii DANH MỤC CÁC KÝ HIỆU Ký hiệu Diễn giải l Tân từ ra Độ đo của thuộc tính a da Độ sai khác của thuộc tính a aa Phép sánh trị tổng quát trên thuộc tính a ¬a, a’ Phủ định của a (U, F) Lược đồ quan hệ trên tập thuộc tính U và tập ràng buộc F fX Hàm sai khác f trên tập thuộc tính X ||X||, |X| Lực lượng của X ├ Phép suy dẫn theo quan hệ ╞, ® Phép suy dẫn theo logic ├2 suy dẫn theo quan hệ có không quá 2 bộ a, ai Thuộc tính da Miền trị của thuộc tính a f, g Phụ thuộc logic F, G Tập các phụ thuộc logic F = {f1, f2, …, fk} F+ Bao đóng của tập phụ thuộc F được suy dẫn theo logic F* Bao đóng của tập phụ thuộc F được suy dẫn theo quan hệ L(U) Tập các công thức Boole xây dựng trên U P(U) Tập các công thức Boole dương trên U r Quan hệ r r(f) Quan hệ r thỏa phụ thuộc f ix Ký hiệu Diễn giải r(F) Quan hệ r thỏa tập phụ thuộc F + ℝ Tập số thực không âm REL(U) Tập các quan hệ trên tập thuộc tính U SAT(F) Tập các quan hệ trên U thỏa tập ràng buộc F t, u, v,.a Giá trị của bộ t trên thuộc tính t.X a Bộ t trên tập thuộc tính X Tf Bảng chân lý của phụ thuộc hàm f TF Bảng chân lý của tập phụ thuộc hàm F Tr, Vr Bảng trị của quan hệ r Tập thuộc tính U XÈY Phép hợp hai tập X và Y XÇY Phép giao hai tập X và Y XÚY,X+Y Tuyển (tổng) logic X và Y XÙY,XY Hội (tích) logic X và Y X\Y,X-Y Hiệu hai tập X và Y X, Y Tập các thuộc tính X+ Bao đóng của tập X ℒ Σ={ga1,ga2,…,gan} Tập các phụ thuộc sai khác Tập các giá trị Boole ℤ+ Miền trị của tập các thuộc tính trong U Tập các phụ thuộc logic Tập số nguyên không âm x DANH MỤC HÌNH VÀ CÁC BẢNG Bảng 1. Bảng trị của quan hệ r ………………………………………. Quan hệ bảng giá taxi …………………………………….
Bảng trị Vf, Vg và các bảng chân lý Tf , Tg và TF …………. Bảng đặc tả các lớp con IE1-4 ………………. Quan hệ r với các thuộc tính:Huyết thống H, ADN mẹ: M …. Bảng trị của quan hệ r ………….
Bảng trị của hàm H ® B+M …………………………………. Quan hệ đơn hàng ………………………………. Bảng quy định các hàm lA …………………………………. Chuyển về dạng CNF ……………………….
Quan hệ Bảng 3. Các lớp phụ thuộc Boole dương ……………………. Đặc tả các loại phụ thuộc PTH truyền thống, phụ thuộc mạnh, yếu và đối ngẫu ……………………………………………………. Tính cấp thiết của đề tài luận án Với sự tiến bộ trong lĩnh vực khoa học và kỹ thuật, vai trò của các phụ thuộc dữ liệu trong quá trình thiết kế và sử dụng dữ liệu ngày càng trở nên quan trọng hơn.
Do đó, việc phát triển các dạng phụ thuộc dữ liệu đa dạng đang là một chủ đề nghiên cứu đang thu hút sự quan tâm lớn và có ý nghĩa đối với thực tế. Trong lĩnh vực đảm bảo tính nhất quán và ngữ nghĩa, đây cũng được coi là một trong những mục tiêu quan trọng khi thực hiện khai thác tri thức từ các nguồn dữ liệu đa dạng. Tình hình nghiên cứu trên thế giới Phụ thuộc dữ liệu đã được nghiên cứu trong nhiều công trình. Điển hình là năm 1970, Codd [1] [2] giới thiệu khái niệm đầu tiên về CSDL quan hệ và khái niệm phụ thuộc hàm (PTH) để phản ánh ngữ nghĩa của dữ liệu tồn tại trong thế giới thực.
Cùng với sự phát triển mạnh mẽ của lớp phụ thuộc hàm, một số phụ thuộc dữ liệu biến thể từ phụ thuộc hàm, cũng như hệ tiên đề cho lớp các phụ thuộc - tức là đặt nền móng cho cơ sở lý thuyết về phụ thuộc dữ liệu, cũng đã được giới thiệu bao gồm: phụ thuộc đối ngẫu, phụ thuộc yếu, phụ thuộc mạnh của nhóm nghiên cứu J. Fagin và Zaniolo và một số nhóm nghiên cứu khác đã đề xuất phụ thuộc đa trị cùng một số ứng dụng của nó [4] [5] [6], phụ thuộc đa trị mở rộng tập trị không chỉ nhận hai giá trị {0, 1} mà bao gồm n giá trị thực nằm trong trong khoảng [1, 0]. Năm 1981 - 1985, Berman, Delobel và cộng sự [7] [8] đã phát triển khái niệm phụ thuộc hàm thành khái niệm phụ thuộc Boole dương (PTBD), bao gồm những ràng buộc dữ liệu được biểu diễn bằng các công thức Boole dương (CTBD), nhưng vẫn giữ nguyên phép sánh trị đẳng thức. Sau đó, nhóm nghiên cứu Nguyễn Xuân Huy, Lê Thị Thanh [9] mở rộng phụ thuộc Boole dương 2 thành phụ thuộc Boole dương tổng quát (PTBDTQ), phụ thuộc Boole dương theo nhóm bộ và phụ thuộc Boole dương đa trị bằng việc thay thế phép sánh trị đẳng thức thành phép sánh trị tổng quát a thỏa ba tính chất đối xứng, phản xạ, bộ phận và chứng minh định lý tương đương cho phép thay việc kiểm tra phép suy dẫn theo dữ liệu bằng việc kiểm tra theo logic hình thức.
Năm 1995 Jyrki Kivinen và các đồng nghiệp đề xuất khái niệm phụ thuộc hàm xấp xỉ [10]. Phụ thuộc hàm xấp xỉ được phát triển từ khái niệm phụ thuộc hàm được phát biểu như sau: ta nói rằng X ® Y đúng trong quan hệ r nếu mọi cặp bộ u, v Î R thỏa u. Nếu r không thỏa mãn phụ ! thuộc hàm X®Y nhưng sau khi xóa đi n bộ trong r ta thu được r’ thỏa mãn phụ thuộc hàm X®Y thì quan hệ r thỏa mãn phụ thuộc hàm X®Y với độ xấp xỉ ## , trong đó #r là tổng số bộ của quan hệ r lúc đầu. Tiếp theo, các nhóm nghiên cứu Hultala Y và các đồng nghiệp [11], Ronald S.
[12] đã phát triển thêm một số thuật toán cho loại phụ thuộc hàm xấp xỉ này. Gần đây, xuất phát từ các phụ thuộc dữ liệu truyền thống có nhiều công bố nghiên cứu về các phụ thuộc dữ liệu mở rộng cho các loại dữ liệu khác nhau được thực hiện bởi nhiều tác giả. Cụ thể, năm 2004, Ilyas [12] và đồng nghiệp đã phát triển loại phụ thuộc hàm mới được gọi là phụ thuộc hàm mềm, đây là phụ thuộc hàm mà trị của tập thuộc tính trên X xác định trị của tập thuộc tính trên Y với độ không chắc chắn cho trước. Phụ thuộc hàm có điều kiện được Bohannon [13] [14] [15], cùng các đồng nghiệp đề xuất năm 2007 để làm sạch dữ liệu.
Với dữ liệu mờ, phụ thuộc hàm đối sánh [16] [17] [18] đã lần lượt được nghiên cứu. Phụ thuộc hàm độ đo [19] được đề xuất năm 2009. Phụ thuộc tuần tự được Golab và đồng nghiệp giới thiệu để khái quát dữ liệu theo thứ tự và thể hiện được các mối quan hệ giữa các thuộc tính có thứ tự [20]. Đầu năm 2011, nhóm nghiên cứu Song S.
đề xuất phụ thuộc sai khác (PTSK) để giải quyết các vấn đề như đảm bảo tính toàn vẹn, tối ưu truy vấn [20] Bản chất của phụ thuộc sai khác là mở rộng phép đối sánh trên 3 các thuộc tính trong phụ thuộc hàm. Nếu X®Y là một phụ thuộc hàm và γX, γY là hai hàm sai khác trên X và Y tương ứng thì quan hệ r thỏa phụ thuộc sai khác γX ® γY khi và chỉ khi với hai dòng bất kì u, v Î r, u.X thỏa hàm sai khác γX kéo theo u.Y thỏa hàm sai khác γY. Ở đây ta hiểu hàm sai khác mô tả mức độ khác nhau của những giá trị nằm trong miền trị của các thuộc tính. Hiện nay, một số hướng phát triển mới về phụ thuộc dữ liệu đang được các nhóm tập trung nghiên cứu như phụ thuộc so sánh của nhóm nghiên cứu Song S.S - 2013) [21]; hay việc phân tích các ràng buộc theo cấu trúc mẫu của Baixeries J.
- 2015 [22] mở rộng phụ thuộc hàm xấp xỉ với dữ liệu lớn phân tán của Li W. – 2016 [23] cũng được các nhóm đề xuất và ứng dụng vào thực tế. Gần đây nhất, [24] các tác giả Vincenzo Deufemia, Loredana Caruccio, Giuseppe Polese (2016) đã tổng kết 35 loại phụ thuộc mở rộng của các nhóm nghiên cứu trên thế giới. Tuy nhiên, ngoài các phụ thuộc mà các tác giả gọi là nhóm các phụ thuộc hàm nới lỏng vẫn còn một số phụ thuộc cơ bản chưa được đề cập tới như các phụ thuộc logic và phụ thuộc theo nhóm bộ, phụ thuộc đa trị.