Luận án Tiến sĩ: Phát triển Phụ thuộc Boole Dương Xấp Xỉ trong Cơ sở Dữ liệu Quan Hệ

BỘ GIÁO DỤC VÀ ĐÀO TẠO i VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ …….***………… NGUYỄN THỊ VÂN PHÁT TRIỂN PHỤ THUỘC BOOLE DƯƠNG XẤP XỈ TRONG CƠ SỞ DỮ LIỆU QUAN HỆ LUẬN ÁN TIẾN SĨ HỆ THỐNG THÔNG TIN Hà Nội - 2023 BỘ GIÁO DỤC VÀ ĐÀO TẠO i VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ …….***………… NGUYỄN THỊ VÂN PHÁT TRIỂN PHỤ THUỘC BOOLE DƯƠNG XẤP XỈ TRONG CƠ SỞ DỮ LIỆU QUAN HỆ LUẬN ÁN TIẾN SĨ HỆ THỐNG THÔNG TIN Ngành: Hệ thống thông tin Mã số: 9 48 01 04 Xác nhận của Học viện Người hướng dẫn Khoa học và Công nghệ (Ký, ghi rõ họ tên) PGS. Nguyễn Xuân Huy Hà Nội - 2023 ii LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của tôi và được hướng dẫn bởi Thầy PGS. TSKH Nguyễn Xuân Huy. Những kết quả trong luận án có nghiên cứu chung với các đồng tác giả đều được sự đồng ý của các tác giả trước khi được sử dụng trong luận án.

Những kết quả được trình bày trong công trình đều trung thực và không được sao chép từ các công trình được công bố khác. Nếu xảy ra việc gian lận trong luận án này tôi sẽ chịu hoàn toàn mọi trách nhiệm. Tôi xin cam đoan mọi giúp đỡ trong quá trình thực hiện luận án đã được NCS cảm ơn, mọi thông tin về nguồn trích dẫn và chú thích rõ ràng trong luận án đều và đã được NCS nêu rõ nguồn gốc. Hà nội, Ngày 26 tháng 9 năm 2023 Tác giả Nguyễn Thị Vân iii LỜI CẢM ƠN Trong thời gian thực hiện nghiên cứu và hoàn thiện luận án, NCS nhận được nhiều sự giúp đỡ, tạo điều kiện từ các Thầy, Cô, các nhà nghiên cứu và đồng nghiệp.

NCS xin được bày tỏ lời cảm ơn tự đáy lòng đến những người đã trợ giúp và chia sẻ khó khăn trong suốt thời gian qua. Trước hết, NCS xin được bày tỏ lòng biết ơn nhất đến Thầy PGS. TSKH Nguyễn Xuân Huy, người luôn đồng hành và tận tình giúp đỡ NCS trong suốt chặng đường nghiên cứu, định hướng cho NCS. NCS xin trân trọng cảm ơn các nhà khoa học các Thầy và Cô trong Viện công nghệ Thông tin – Học viện Khoa học và Công nghệ đã khuyến khích, tạo điều kiện thuận lợi và có nhiều ý kiến đóng góp quý báu trong chặng đường NCS nghiên cứu và thực hiện để hoàn thành được luận án.

NCS xin trân trọng cảm ơn Lãnh đạo Viện Công nghệ Thông tin, Học viện Khoa học và Công nghệ đã khuyến khích và tạo những điều kiện tốt nhất để NCS có được môi trường nghiên cứu tốt nhất. NCS xin chân thành gửi lời cảm ơn tới các Phòng ban của Học viện Khoa học và Công nghệ đã nhiệt tình giúp đỡ, tạo những điều kiện tốt nhất cho NCS trong suốt quá nghiên cứu và thực hiện luận án. NCS xin chân thành cảm ơn thầy giáo PGS.TS Đặng Văn Đức, PGS.TS Nguyễn Long Giang đã tận tình chỉ bảo và là tấm gương về nghiên cứu khoa học cho NCS trên bước đường học tập. TS Nguyễn Thanh Thuỷ, PGS.TS Ngô Quốc Tạo, GS.TS Từ Minh Phương, PGS.TS Trịnh Đình Thắng, GS.TS Lê Hoài Bắc, PGS.TS Đoàn Văn Ban, TS Nguyễn Duy Phương…là những người Thầy mà NCS đã học hỏi được rất nhiều, và đã có nhiều ý kiến quý báu giúp NCS hoàn thiện luận án của mình.

NCS cũng xin bày tỏ lời cảm ơn đến anh chị, bạn bè và TS Trương Thị Thu Hà đã đồng hành cùng NCS trong quá trình học tập. Cuối cùng, NCS biết ơn những người thân yêu trong gia đình đã luôn bên cạnh ủng hộ và dành những lời động viên cho NCS trong suốt quá trình NCS hoàn thành luận án. Hà nội, Ngày 26 tháng 9 năm 2023 Tác giả Nguyễn Thị Vân iv MỤC LỤC LỜI CẢM ƠN. ii MỤC LỤC.

iii DANH MỤC CÁC THUẬT NGỮ, CÁC CHỮ VIẾT TẮT. vii MỞ ĐẦU. Tính cấp thiết của đề tài luận án. Mục tiêu nghiên cứu.

Đối tượng và phạm vi nghiên cứu. Phương pháp nghiên cứu. Nội dung nghiên cứu. Ý nghĩa khoa học và thực tiễn.

Bố cục của luận án. CÁC LỚP PHỤ THUỘC DỮ LIỆU TRONG CƠ SỞ DỮ LIỆU. Phụ thuộc hàm. Phụ thuộc hàm nới lỏng.

Phụ thuộc Boole dương. Công thức Boole. Bảng trị và bảng chân lý. Phụ thuộc Boole dương tổng quát.

Phân loại các lớp phụ thuộc Boole dương tổng quát. Kết luận 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.