Luận án Phát hiện phụ thuộc hàm và phụ thuộc hàm suy rộng trong cơ sở dữ liệu

BỘ GIÁO DỤC VÀ ĐÀO TẠO 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Ệ ----------------------------- VŨ QUỐC TUẤN PHÁT HIỆN PHỤ THUỘC HÀM VÀ PHỤ THUỘC HÀM SUY RỘNG TRONG CƠ SỞ DỮ LIỆU LUẬN ÁN TIẾN SỸ TOÁN HỌC HÀ NỘI – 2019 BỘ GIÁO DỤC VÀ ĐÀO TẠO 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Ệ ----------------------------- VŨ QUỐC TUẤN PHÁT HIỆN PHỤ THUỘC HÀM VÀ PHỤ THUỘC HÀM SUY RỘNG TRONG CƠ SỞ DỮ LIỆU LUẬN ÁN TIẾN SỸ TOÁN HỌC Chuyên ngành: Cơ sở Toán học cho Tin học Mã số: 9 46 01 10 Người hướng dẫn khoa học: 1. PGS. TS. Hồ Thuần 2. PGS. TS. Nguyễn Thanh Tùng Hà Nội – 2019 i LỜI CAM ĐOAN Tác giả xin cam đoan đây là công trình nghiên cứu do chính tác giả thực hiện dưới sự hướng dẫn khoa học của PGS. TS. Hồ Thuần và PGS. TS. Nguyễn Thanh Tùng tại Học viện Khoa học và Công nghệ - Viện Hàn lâm Khoa học và Công nghệ Việt Nam. Tất cả các kết quả trình bày trong luận án là trung thực, không sao chép từ bất kỳ công trình nào khác. Nếu có điều gì không trung thực, tác giả xin chịu hoàn toàn trách nhiệm. Tác giả Vũ Quốc Tuấn ii LỜI CẢM ƠN Luận án này được thực hiện tại Học viện Khoa học và Công nghệ, Viện Hàn lâm Khoa học và Công nghệ Việt Nam dưới sự hướng dẫn khoa học của PGS. TS. Hồ Thuần và PGS. TS. Nguyễn Thanh Tùng. Tác giả xin bày tỏ lòng biết ơn sâu sắc tới các Thầy đã tận tình chỉ bảo, động viên, hướng dẫn và tạo mọi điều kiện thuận lợi để tác giả hoàn thành luận án. Tác giả xin trân trọng cảm ơn tập thể các Thầy Cô trong Viện Công nghệ Thông tin đã có nhiều ý kiến đóng góp và phản biện trong suốt quá trình tác giả nghiên cứu và hoàn chỉnh luận án. Tác giả xin chân thành cảm ơn các nhà khoa học, các tác giả của các công trình đã được tham khảo và trích dẫn trong luận án. Tác giả 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ệ đã tạo những điều kiện tốt nhất để tác giả có được môi trường nghiên cứu và hoàn thành chương trình nghiên cứu sinh của mình. Xin chân thành cảm ơn các Phòng ban của Viện Công nghệ Thông tin đã giúp đỡ, tạo điều kiện cho tác giả trong suốt quá trình thực hiện luận án. Tác giả xin cảm ơn Ban giám hiệu Trường Cao đẳng Hải Dương, Khoa Tự Nhiên và Khoa Điện-Cơ-Tin đã tạo điều kiện thuận lợi cho tác giả thực hiện luận án. Xin cảm ơn tất cả các bạn đồng nghiệp đã luôn chia sẻ, động viên tác giả trong những lúc khó khăn. Cuối cùng, tác giả xin bày tỏ lòng biết ơn đối với những người thân trong gia đình, đặc biệt là mẹ và vợ, đã luôn ủng hộ và động viên cho tác giả trong suốt thời gian hoàn thành luận án. iii MỤC LỤC Danh sách hình vẽ v Danh sách bảng v Danh sách chữ viết tắt vi MỞ ĐẦU 1 Chương 1. PHỤ THUỘC HÀM VÀ PHỤ THUỘC HÀM SUY RỘNG TRONG MÔ HÌNH DỮ LIỆU QUAN HỆ 6 1.1. Nhắc lại một số khái niệm cơ bản ................................................................. 6 1.1.1. Miền ...................................................................................................... 6 1.1.2. Quan hệ ................................................................................................. 6 1.1.3. Các tính chất đặc trưng của một quan hệ ............................................... 7 1.1.4. Lược đồ quan hệ .................................................................................... 7 1.2. Phụ thuộc hàm .............................................................................................. 8 1.2.1. Khái niệm phụ thuộc hàm ...................................................................... 8 1.2.2. Hệ quy tắc suy diễn Armstrong ............................................................. 9 1.2.3. Bao đóng của một tập thuộc tính ........................................................... 9 1.2.4. Khóa của lược đồ quan hệ ..................................................................... 9 1.3. Phụ thuộc hàm suy rộng ............................................................................. 10 1.3.1. Phụ thuộc hàm xấp xỉ .......................................................................... 11 1.3.2. Phụ thuộc hàm mêtric .......................................................................... 13 1.3.3. Phụ thuộc hàm điều kiện ..................................................................... 14 1.3.4. Phụ thuộc hàm mờ ............................................................................... 16 1.3.5. Phụ thuộc sai phân............................................................................... 17 1.3.6. Các loại phụ thuộc hàm suy rộng khác ................................................ 18 1.4. Phát hiện phụ thuộc hàm............................................................................. 18 1.4.1. Phương pháp top-down ....................................................................... 19 1.4.2. Phương pháp bottom-up ...................................................................... 28 1.4.3. Một số chủ đề liên quan đến phát hiện phụ thuộc hàm ......................... 32 1.5. Phát hiện phụ thuộc hàm suy rộng .............................................................. 34 1.5.1. Phát hiện phụ thuộc hàm xấp xỉ ........................................................... 34 1.5.2. Phát hiện phụ thuộc hàm điều kiện ...................................................... 36 1.6. Tổng kết chương 1 ...................................................................................... 39 iv Chương 2. PHỤ THUỘC HÀM XẤP XỈ VÀ PHỤ THUỘC HÀM ĐIỀU KIỆN 41 2.1. Về một số kết quả liên quan đến FD và AFD .............................................. 41 2.1.1. Phân hoạch .......................................................................................... 41 2.1.2. Một số kết quả ..................................................................................... 42 2.2. Phát hiện FD và AFD ................................................................................. 45 2.2.1. Ma trận tương đương ........................................................................... 45 2.2.2. Một số tính chất của ma trận thuộc tính ............................................... 48 2.2.3. Sử dụng ma trận để kiểm tra phụ thuộc hàm ........................................ 49 2.2.4. Sử dụng ma trận để tính một số độ đo xấp xỉ ....................................... 50 2.3. Phụ thuộc hàm điều kiện............................................................................. 54 2.3.1. Sự cần thiết phải mở rộng FD thành CFD ............................................ 54 2.3.2. Cú pháp và ngữ nghĩa của CFD ........................................................... 54 2.3.3. Một số kết quả quan trọng đã biết về CFD ........................................... 57 2.4. Về một thứ tự phân cấp giữa các FD, CFD và AR ...................................... 62 2.5. Kết luận chương 2 ...................................................................................... 72 Chương 3. THUẬT TOÁN TÍNH BAO ĐÓNG VÀ VẤN ĐỀ RÚT GỌN BÀI TOÁN TÌM KHÓA CỦA LƯỢC ĐỒ QUAN HỆ 73 3.1. Thuật toán tính bao đóng ............................................................................ 73 3.1.1. Khái niệm bao đóng ............................................................................ 73 3.1.2. Một số thuật toán tính bao đóng .......................................................... 74 3.2. Vấn đề rút gọn bài toán xác định khóa của lược đồ quan hệ ........................ 87 3.2.1. Một số kết quả đã biết ......................................................................... 87 3.2.2. Một dạng cải tiến cho điều kiện cần đã được công bố năm 1985.......... 89 3.2.3. So sánh các điều kiện cần .................................................................... 91 3.2.4. Một bài toán quyết định ....................................................................... 95 3.3. Kết luận chương 3 ...................................................................................... 96 Chương 4. VỀ MỘT PHÉP BIẾN ĐỔI TIỀN XỬ LÝ HIỆU QUẢ CÁC TẬP PHỤ THUỘC HÀM 97 4.1. Giới thiệu ................................................................................................... 97 4.2. Sự dư thừa trong tập phụ thuộc hàm ......................................................... 100 4.3. Một phép biến đổi tiền xử lý hiệu quả các tập FD ..................................... 101 4.3.1. Logic Paredaens ................................................................................ 102 4.3.2. Một chứng minh mới cho định lý 4.1 ................................................. 107 4.4. Tổng kết chương 4 .................................................................................... 113 KẾT LUẬN 114 DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ 116 TÀI LIỆU THAM KHẢO 117 v DANH SÁCH HÌNH VẼ Hình 1.1. Minh họa dàn thuộc tính........................................................... 20 Hình 2.1. Các luật suy diễn đối với CFD ................................................. 60 DANH SÁCH BẢNG BIỂU Bảng 1.1. Quan hệ Nhân viên ................................................................... 11 Bảng 1.2. Quan hệ Phim .......................................................................... 13 Bảng 1.3. Quan hệ Qh1............................................................................. 14 Bảng 1.4. Quan hệ Cust ........................................................................... 15 Bảng 1.5. Quan hệ Qh2............................................................................. 17 Bảng 1.6. Quan hệ Qh3............................................................................. 19 Bảng 1.7. Minh họa phụ thuộc hàm điều kiện .......................................... 38 Bảng 2.1. Một quan hệ minh họa ............................................................. 47 Bảng 2 .2. Quan hệ r ................................................................................ 67 Bảng 2.3. Quan hệ r1 ................................................................................ 68 Bảng 2.4. Quan hệ r2 ................................................................................ 68 Bảng 2.5. Quan hệ r3 ................................................................................ 68 Bảng 2.6. Quan hệ r4 ................................................................................ 68 Bảng 3.1. Minh họa cho ví dụ 3.3 ............................................................ 80 Bảng 3.2. Kết quả thử nghiệm .................................................................. 82 Bảng 3.3. Minh họa thuật toán 3.7 ........................................................... 84 Bảng 4.1. Quan hệ phân công .................................................................. 98 Bảng 4.2. Minh họa cho ví dụ 4.6 .......................................................... 111 Bảng 4.3. Minh họa cho ví dụ 4.7 .......................................................... 112 vi DANH SÁCH CHỮ VIẾT TẮT Từ viết tắt Tiếng Anh Tiếng Việt FD Functional dependency Phụ thuộc hàm RFD Relaxed functional dependencies Phụ thuộc hàm suy rộng AFD Approximate functional dependency Phụ thuộc hàm xấp xỉ MFD Metric functional dependency Phụ thuộc hàm mêtric FFD Fuzzy functional dependency Phụ thuộc hàm mờ DD Differential dependencies Phụ thuộc sai phân CFD Conditional Functional dependency Phụ thuộc hàm điều kiện AR Association Rule Luật kết hợp eCFD Extended Conditional Functional dependency Phụ thuộc hàm điều kiện mở rộng CIND Conditional Inclusion Dependency Phụ thuộc bao hàm điều kiện 1 MỞ ĐẦU Các phụ thuộc dữ liệu có vai trò quan trọng trong thiết kế cơ sở dữ liệu, quản lý chất lượng dữ liệu và biểu diễn tri thức. Việc sử dụng các phụ thuộc trong thiết kế cơ sở dữ liệu và quản lý chất lượng dữ liệu được giới thiệu trong phần lớn các sách về cơ sở dữ liệu. Các phụ thuộc trong trường hợp này được trích xuất từ các yêu cầu về ứng dụng, được sử dụng trong việc chuẩn hóa cơ sở dữ liệu và được cài đặt trong cơ sở dữ liệu đã được thiết kế để đảm bảo chất lượng dữ liệu. Ngược lại, các phụ thuộc trong phát hiện tri thức được trích xuất từ dữ liệu hiện có của cơ sở dữ liệu. Quá trình trích xuất này được gọi là phát hiện phụ thuộc với mục đích tìm tất cả các phụ thuộc được thỏa mãn (đúng) trên dữ liệu hiện có. Mục đích của việc phát hiện phụ thuộc là tìm các phụ thuộc quan trọng đúng (thỏa mãn) trên dữ liệu của cơ sở dữ liệu. Các phụ thuộc (được phát hiện) biểu diễn tri thức (thuộc lĩnh vực hoạt động nào đó) và có thể được sử dụng để kiểm tra thiết kế cơ sở dữ liệu cũng như đánh giá chất lượng dữ liệu. Ví dụ. Bằng việc kiểm tra dữ liệu của một cơ sở dữ liệu y học có hai thuộc tính Bệnh và Triệu chứng, nếu viêm phổi là một giá trị của Bệnh và sốt là một giá trị của Triệu chứng, đồng thời nếu mỗi bệnh nhân viêm phổi đều bị sốt thì sốt được cho là có liên quan đến viêm phổi. Nếu điều này xảy ra (đúng) đối với mọi cặp giá trị Triệu chứng và Bệnh thì Bệnh xác định hàm Triệu chứng và đây là một phụ thuộc hàm. Nếu phụ thuộc hàm này là một tri thức mới, nó sẽ giúp cho việc chẩn đoán bệnh hiệu quả hơn. Trong lĩnh vực khoa học sức khỏe hiện đại, việc tìm các mối liên hệ và các phụ thuộc như vậy (giữa các đoạn DNA và Bệnh) trở nên rất quan trọng đối với sự phát triển của y học. Bên cạnh việc phát hiện tri thức, các phụ thuộc được phát hiện từ dữ liệu có thể được sử dụng để kiểm tra xem các phụ thuộc đã được định nghĩa trước đây trên cơ sở dữ liệu có đúng (thỏa mãn) và đầy đủ hay không, đồng thời có thể dùng để kiểm tra ngữ nghĩa của dữ liệu trong cơ sở dữ liệu. 2 Một ứng dụng nữa của các phụ thuộc (được phát hiện) là để đánh giá chất lượng của dữ liệu. Vai trò chính của việc cài đặt các phụ thuộc trong một cơ sở dữ liệu là để đảm bảo chất lượng dữ liệu của cơ sở dữ liệu. Do đó, trên cơ sở phân tích các phụ thuộc được phát hiện và các phụ thuộc phải có giữa các thuộc tính của dữ liệu, ta có thể tìm và xác định được sự không nhất quán giữa các thuộc tính và các lỗi sai trên dữ liệu; từ đó, đánh giá được chất lượng dữ liệu. Từ những năm đầu thập kỷ 80 của thế kỷ 20, bài toán phát hiện phụ thuộc đã thu hút được sự quan tâm của đông đảo các nhà khoa học thuộc nhiều lĩnh vực nghiên cứu khác nhau như thiết kế cơ sở dữ liệu, học máy và phát hiện tri thức ([3], [10], [12], [18], [21], [26], [32], [33], [34], [37], [42], [45], [57], [65], [72], [75],...). Và cho đến thời điểm hiện tại, vấn đề phát hiện phụ thuộc từ các tập dữ liệu lớn (big data) càng trở nên quan trọng vì trong các tập dữ liệu lớn này chứa rất nhiều tri thức quý giá. Hiện nay, với sự phát triển của toàn xã hội và các thiết bị số, đặc biệt là các ứng dụng mạng xã hội và điện thoại thông minh (smartphone), lượng dữ liệu trong các ứng dụng tăng rất nhanh làm nảy sinh vấn đề lưu trữ, quản lý dữ liệu và đặc biệt là vấn đề phát hiện tri thức từ các tập dữ liệu lớn đó. Bài toán phát hiện phụ thuộc hàm và phụ thuộc hàm suy rộng trong cơ sở dữ liệu là một trong những vấn đề quan trọng của phát hiện tri thức (dưới dạng các phụ thuộc). Ba loại phụ thuộc điển hình được chú ý phát hiện là phụ thuộc hàm (FD: Functional Dependency), phụ thuộc hàm xấp xỉ (AFD: Approximate Functional Dependency) và phụ thuộc hàm điều kiện (CFD: Conditional Functional Dependency). AFD là sự mở rộng của FD, tính chất xấp xỉ dựa trên độ thỏa hoặc độ đo lỗi; CFD là sự mở rộng của FD, nhằm nắm bắt những yếu tố không nhất quán trong dữ liệu. Các hướng nghiên cứu giải quyết bài toán phát hiện FD suy rộng trong cơ sở dữ liệu, trước hết tập trung vào vấn đề phát hiện FD do loại phụ thuộc này là trường hợp riêng của tất cả các loại FD suy rộng, các kết quả về phát hiện FD có thể được thích nghi để phát hiện các loại phụ thuộc khác (chẳng 3 hạn AFD). Mô hình chung của bài toán phát hiện FD là xây dựng không gian tìm kiếm các FD, kiểm tra sự thỏa mãn của từng FD, tỉa không gian tìm kiếm, xuất ra tập FD đã phát hiện được và làm gọn tập FD này (giảm bớt sự dư thừa). Trong bài toán phát hiện FD, phát hiện khóa là trường hợp đặc biệt và cũng là bài toán rất đáng quan tâm do khóa đóng vai trò quan trọng trong chuẩn hóa cơ sở dữ liệu quan hệ. Độ phức tạp thời gian tổng quát của bài toán phát hiện FD là đa thức theo số bản ghi trong cơ sở dữ liệu nhưng là hàm mũ theo số thuộc tính của cơ sở dữ liệu đó. Do đó, để giảm thời gian xử lý, cần xây dựng các luật tỉa hiệu quả. Trong số các luật tỉa đã được đề xuất, tỉa khóa là rất quan trọng, khi phát hiện được khóa thì có thể tỉa (xóa) mọi nút chứa khóa trong không gian tìm kiếm. Tuy nhiên, các luật tỉa khóa hiện có vẫn còn nhược điểm là tìm khóa trên toàn bộ tập thuộc tính  của cơ sở dữ liệu (đây thực sự là vấn đề rất khó vì độ phức tạp thời gian có thể là hàm mũ theo số thuộc tính của ), vậy có cách nào phát hiện được khóa trong một tập con thực sự của  hay không? Câu hỏi trên chính là một trong những động lực cơ bản của luận án này. Sau khi đã phát hiện được tập các phụ thuộc, tập này có thể rất lớn và gây khó khăn cho việc sử dụng vì chứa những dư thừa không cần thiết. Vấn đề quan trọng đặt ra là làm thế nào để loại bỏ được (càng nhiều càng tốt) sự dư thừa trong tập phụ thuộc đã được phát hiện. Đây cũng là bài toán được quan tâm trong luận án. Một hướng nghiên cứu nữa trong luận án là tập trung nghiên cứu, phát hiện hai loại FD suy rộng điển hình, đó là AFD và CFD. Cả AFD và CFD đều có nhiều ứng dụng và xuất hiện nhiều trong các cơ sở dữ liệu quan hệ, đặc biệt CFD còn là công cụ mạnh trong giải quyết bài toán làm sạch dữ liệu ([12]). Với AFD, vấn đề quan trọng nhất là cải tiến và phát triển các kỹ thuật tính toán các độ thỏa hoặc độ đo lỗi ([34], [72]); với CFD, ngoài việc phát hiện, thì việc tìm hiểu về một thứ tự phân cấp giữa CFD và một số loại phụ thuộc khác cũng là vấn đề rất đáng quan tâm. 4 Trong những năm gần đây, các hướng nghiên cứu về cải tiến thuật toán tính bao đóng của một tập thuộc tính đối với một tập FD, vấn đề rút gọn cho bài toán xác định khóa của lược đồ quan hệ, vấn đề về các phép biến đổi tiền xử lý hiệu quả các tập FD cho trước đã được xới lại, làm mới với hàng loạt các công trình của các tác giả nước ngoài ([22], [23], [24], [25], [52], [53], [54], [55]), trong khi ở trong nước, có nhiều công trình được công bố liên quan tới các phương pháp và thuật toán xác định các tập rút gọn (reduct) của một bảng quyết định theo nhiều tiếp cận khác nhau. Mục tiêu của luận án là nghiên cứu nhằm thu được một số kết quả giúp giải quyết có hiệu quả một số vấn đề như đã phân tích ở trên trong phạm vi cơ sở dữ liệu quan hệ. Để thực hiện các mục tiêu trên, chúng tôi tập trung vào các nội dung sau: 1) Nghiên cứu tổng quan về các loại FD suy rộng, các phương pháp phát hiện FD và FD suy rộng trong cơ sở dữ liệu quan hệ. 2) Nghiên cứu về AFD và CFD: kỹ thuật tính độ thỏa hoặc độ đo lỗi trong AFD, về một thứ tự phân cấp giữa CFD và một số loại phụ thuộc khác. 3) Nghiên cứu các thuật toán tính bao đóng của tập thuộc tính đối với một tập FD. Cải tiến được các thuật toán này sẽ làm tăng hiệu năng phát hiện khóa của lược đồ quan hệ. Nghiên cứu vấn đề rút gọn cho bài toán xác định khóa của lược đồ quan hệ, đây là vấn đề quan trọng, là cơ sở cho các luật tỉa khóa nhằm thu hẹp không gian tìm kiếm khi phát hiện các FD. 4) Nghiên cứu về một phép biến đổi tiền xử lý các tập FD nhằm thu được một tập FD tương đương nhưng đơn giản hơn tập FD ban đầu. Với các nội dung nghiên cứu trên, luận án được cấu trúc gồm phần mở đầu, bốn chương nội dung và phần kết luận. Chương 1. Trình bày tổng quan về mô hình dữ liệu quan hệ, các khái niệm FD, bao đóng của một tập thuộc tính, khóa của lược đồ quan hệ,Trong đó tập trung trình bày về FD suy rộng và khát