Phát Hiện Phụ Thuộc Hàm Và Phụ Thuộc Hàm Suy Rộng Trong Cơ Sở Dữ Liệu

Phát hiện phụ thuộc hàm là một lĩnh vực quan trọng trong nghiên cứu cơ sở dữ liệu. 132 trang · Học viện Khoa học và Công nghệ · 2019.

• Tác giả: Vũ Quốc Tuấn
• Người hướng dẫn: PGS. Hồ Thuần
• Trường học: Học viện Khoa học và Công nghệ
• Chuyên ngành: Cơ sở Toán học cho Tin học
• Đề tài: Phát Hiện Phụ Thuộc Hàm Trong Cơ Sở Dữ Liệu
• Loại tài liệu: luận án tiến sĩ
• Năm xuất bản: 2019
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• 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Ệ
• 1.1. Nhắc lại một số khái niệm cơ bản
• 1.2. Các tính chất đặc trưng của một quan hệ
• 1.3. Lược đồ quan hệ
• 1.4. Phụ thuộc hàm
• 1.5. Khái niệm phụ thuộc hàm
• 1.6. Hệ quy tắc suy diễn Armstrong
• 1.7. Bao đóng của một tập thuộc tính
• 1.8. Khóa của lược đồ quan hệ
• 1.9. Phụ thuộc hàm suy rộng
• 1.10. Phụ thuộc hàm xấp xỉ
• 1.11. Phụ thuộc hàm mêtric
• 1.12. Phụ thuộc hàm điều kiện
• 1.13. Phụ thuộc hàm mờ
• 1.14. Phụ thuộc sai phân
• 1.15. Các loại phụ thuộc hàm suy rộng khác
• 1.16. Phát hiện phụ thuộc hàm
• 1.17. Phương pháp top-down
• 1.18. Phương pháp bottom-up
• 1.19. Một số chủ đề liên quan đến phát hiện phụ thuộc hàm
• 1.20. Phát hiện phụ thuộc hàm suy rộng
• 1.21. Phát hiện phụ thuộc hàm xấp xỉ
• 1.22. Phát hiện phụ thuộc hàm điều kiện
• 1.23. Tổng kết chương 1
• 2. CHƯƠNG 2: PHỤ THUỘC HÀM XẤP XỈ VÀ PHỤ THUỘC HÀM ĐIỀU KIỆN
• 2.1. Về một số kết quả liên quan đến FD và AFD
• 2.2. Một số kết quả
• 2.3. Phát hiện FD và AFD
• 2.4. Ma trận tương đương
• 2.5. Một số tính chất của ma trận thuộc tính
• 2.6. Sử dụng ma trận để kiểm tra phụ thuộc hàm
• 2.7. Sử dụng ma trận để tính một số độ đo xấp xỉ
• 2.8. Phụ thuộc hàm điều kiện
• 2.9. Sự cần thiết phải mở rộng FD thành CFD
• 2.10. Cú pháp và ngữ nghĩa của CFD
• 2.11. Một số kết quả quan trọng đã biết về CFD
• 2.12. Về một thứ tự phân cấp giữa các FD, CFD và AR
• 2.13. Kết luận chương 2
• 3. 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Ệ
• 3.1. Thuật toán tính bao đóng
• 3.2. Khái niệm bao đóng
• 3.3. Một số thuật toán tính bao đóng
• 3.4. Vấn đề rút gọn bài toán xác định khóa của lược đồ quan hệ
• 3.5. Một số kết quả đã biết
• 3.6. Một dạng cải tiến cho điều kiện cần đã được công bố năm 1985
• 3.7. So sánh các điều kiện cần
• 3.8. Một bài toán quyết định
• 3.9. Kết luận chương 3
• 4. 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
• 4.1. Sự dư thừa trong tập phụ thuộc hàm
• 4.2. Một phép biến đổi tiền xử lý hiệu quả các tập FD
• 4.3. Một chứng minh mới cho định lý 4
• 4.4. Tổng kết chương 4
• MỞ ĐẦU
• KẾT LUẬN
• DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Phát Hiện Phụ Thuộc Hàm Trong Cơ Sở Dữ Liệu

Phát hiện phụ thuộc hàm là một lĩnh vực quan trọng trong nghiên cứu cơ sở dữ liệu. Nó giúp xác định mối quan hệ giữa các thuộc tính trong một lược đồ dữ liệu. Việc phát hiện này không chỉ hỗ trợ trong việc thiết kế cơ sở dữ liệu mà còn trong việc quản lý chất lượng dữ liệu. Các phụ thuộc hàm được phát hiện có thể được sử dụng để tối ưu hóa cấu trúc dữ liệu và cải thiện hiệu suất truy vấn.

1.1. Khái Niệm Cơ Bản Về Phụ Thuộc Hàm

Phụ thuộc hàm (FD) là một mối quan hệ giữa hai tập thuộc tính trong một lược đồ quan hệ. Nếu một tập thuộc tính X xác định một tập thuộc tính Y, ký hiệu là X → Y, thì Y được gọi là phụ thuộc hàm vào X. Điều này có nghĩa là nếu hai bản ghi có cùng giá trị của X, chúng cũng phải có cùng giá trị của Y.

1.2. Vai Trò Của Phát Hiện Phụ Thuộc Hàm

Phát hiện phụ thuộc hàm đóng vai trò quan trọng trong việc chuẩn hóa cơ sở dữ liệu. Nó giúp xác định các mối quan hệ giữa các thuộc tính, từ đó cải thiện chất lượng dữ liệu và giảm thiểu sự dư thừa. Việc phát hiện này cũng hỗ trợ trong việc kiểm tra tính chính xác của dữ liệu trong cơ sở dữ liệu.

II. Thách Thức Trong Phát Hiện Phụ Thuộc Hàm

Mặc dù phát hiện phụ thuộc hàm mang lại nhiều lợi ích, nhưng cũng tồn tại nhiều thách thức. Một trong những thách thức lớn nhất là xử lý dữ liệu lớn và phức tạp. Các phương pháp hiện tại có thể gặp khó khăn trong việc phát hiện các phụ thuộc hàm trong các tập dữ liệu lớn, dẫn đến việc bỏ sót thông tin quan trọng.

2.1. Khó Khăn Trong Việc Xử Lý Dữ Liệu Lớn

Khi làm việc với các tập dữ liệu lớn, việc phát hiện phụ thuộc hàm trở nên phức tạp hơn. Thời gian xử lý và tài nguyên tính toán cần thiết để phân tích dữ liệu có thể tăng lên đáng kể, gây khó khăn cho việc áp dụng các thuật toán hiện có.

2.2. Sự Đa Dạng Của Dữ Liệu

Dữ liệu trong các cơ sở dữ liệu hiện nay rất đa dạng, từ dữ liệu có cấu trúc đến dữ liệu phi cấu trúc. Sự đa dạng này làm cho việc phát hiện phụ thuộc hàm trở nên khó khăn hơn, vì các phương pháp truyền thống có thể không áp dụng được cho tất cả các loại dữ liệu.

III. Phương Pháp Phát Hiện Phụ Thuộc Hàm Hiệu Quả

Để giải quyết các thách thức trong phát hiện phụ thuộc hàm, nhiều phương pháp đã được phát triển. Các phương pháp này bao gồm các kỹ thuật như top-down, bottom-up và sử dụng ma trận tương đương. Mỗi phương pháp có những ưu điểm và nhược điểm riêng, phù hợp với các tình huống khác nhau.

3.1. Phương Pháp Top Down

Phương pháp top-down bắt đầu từ các phụ thuộc hàm tổng quát và dần dần thu hẹp xuống các phụ thuộc cụ thể hơn. Phương pháp này giúp giảm thiểu không gian tìm kiếm và tăng tốc độ phát hiện phụ thuộc hàm.

3.2. Phương Pháp Bottom Up

Ngược lại, phương pháp bottom-up bắt đầu từ các phụ thuộc hàm cụ thể và kết hợp chúng để tạo ra các phụ thuộc tổng quát hơn. Phương pháp này có thể hiệu quả trong việc phát hiện các phụ thuộc hàm phức tạp hơn.

IV. Ứng Dụng Thực Tiễn Của Phát Hiện Phụ Thuộc Hàm

Phát hiện phụ thuộc hàm có nhiều ứng dụng thực tiễn trong các lĩnh vực khác nhau. Từ việc tối ưu hóa cơ sở dữ liệu đến cải thiện chất lượng dữ liệu, các phụ thuộc hàm được phát hiện có thể giúp các tổ chức đưa ra quyết định chính xác hơn và hiệu quả hơn.

4.1. Tối Ưu Hóa Cơ Sở Dữ Liệu

Việc phát hiện phụ thuộc hàm giúp tối ưu hóa cấu trúc cơ sở dữ liệu, từ đó cải thiện hiệu suất truy vấn và giảm thiểu sự dư thừa dữ liệu. Điều này rất quan trọng trong các hệ thống quản lý dữ liệu lớn.

4.2. Cải Thiện Chất Lượng Dữ Liệu

Các phụ thuộc hàm được phát hiện có thể được sử dụng để kiểm tra và đảm bảo chất lượng dữ liệu. Điều này giúp phát hiện và sửa chữa các lỗi trong dữ liệu, từ đó nâng cao độ tin cậy của thông tin.

V. Kết Luận Về Phát Hiện Phụ Thuộc Hàm

Phát hiện phụ thuộc hàm là một lĩnh vực nghiên cứu quan trọng trong cơ sở dữ liệu. Nó không chỉ giúp cải thiện thiết kế và quản lý cơ sở dữ liệu mà còn đóng vai trò quan trọng trong việc phát hiện tri thức từ dữ liệu. Tương lai của nghiên cứu này hứa hẹn sẽ mang lại nhiều tiến bộ mới trong việc xử lý và phân tích dữ liệu.

5.1. Tương Lai Của Nghiên Cứu

Nghiên cứu về phát hiện phụ thuộc hàm sẽ tiếp tục phát triển, đặc biệt trong bối cảnh dữ liệu lớn và phức tạp. Các phương pháp mới sẽ được phát triển để cải thiện hiệu suất và độ chính xác của việc phát hiện phụ thuộc.

5.2. Tầm Quan Trọng Của Phát Hiện Tri Thức

Phát hiện phụ thuộc hàm không chỉ là một công cụ trong cơ sở dữ liệu mà còn là một phần quan trọng trong việc phát hiện tri thức. Điều này sẽ giúp các tổ chức khai thác tối đa giá trị từ dữ liệu của họ.

Nội dung chính

Tổng quan luận án

Luận án tiến sĩ toán học với đề tài "Phát hiện phụ thuộc hàm và phụ thuộc hàm suy rộng trong cơ sở dữ liệu" được nghiên cứu sinh Vũ Quốc Tuấn thực hiện tại Học viện Khoa học và Công nghệ thuộc 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. Hồ Thuần và PGS. Nguyễn Thanh Tùng. Công trình thuộc chuyên ngành Cơ sở Toán học cho Tin học, mã số 9 46 01 10, bảo vệ năm 2019.

Tính cấp thiết và khoảng trống nghiên cứu

Trong lý thuyết cơ sở dữ liệu quan hệ và quản trị dữ liệu, các phụ thuộc dữ liệu đóng vai trò nền tảng đối với việc thiết kế cấu trúc, chuẩn hóa lược đồ và bảo đảm chất lượng dữ liệu. Khác với cách tiếp cận thiết kế cơ sở dữ liệu truyền thống—nơi các phụ thuộc được trích xuất từ phân tích yêu cầu nghiệp vụ của ứng dụng để thiết lập các ràng buộc toàn vẹn—bài toán phát hiện phụ thuộc trong phát hiện tri thức hướng tới việc trích xuất tự động tất cả các phụ thuộc thỏa mãn trực tiếp trên dữ liệu hiện có. Các phụ thuộc dữ liệu được phát hiện này biểu diễn tri thức tiềm ẩn, phục vụ công tác kiểm tra thiết kế lược đồ, xác minh ngữ nghĩa dữ liệu, đánh giá chất lượng và hỗ trợ làm sạch dữ liệu trong các cơ sở dữ liệu lớn (chẳng hạn như dữ liệu mạng xã hội, thiết bị thông minh, hoặc dữ liệu y học về mối liên hệ giữa bệnh và triệu chứng, đoạn DNA).

Bài toán phát hiện phụ thuộc hàm (FD) và các phụ thuộc hàm suy rộng (RFD) đặt ra thách thức tính toán rất lớn. Độ phức tạp thời gian tổng quát của bài toán phát hiện phụ thuộc hàm là đa thức theo số bản ghi của cơ sở dữ liệu ($|r|$), nhưng lại tăng theo hàm mũ theo số lượng thuộc tính ($n = |\Omega|$). Để giảm thời gian xử lý, việc xây dựng các luật tỉa không gian tìm kiếm là yêu cầu bắt buộc. Trong đó, luật tỉa khóa giữ vị trí then chốt: khi một khóa được xác định, toàn bộ các nút chứa khóa đó trong không gian tìm kiếm đều có thể bị loại bỏ. Tuy nhiên, tác giả luận án chỉ ra một khoảng trống nghiên cứu cơ bản: các luật tỉa khóa hiện có đều phải tiến hành tìm khóa trên toàn bộ tập thuộc tính $\Omega$ của cơ sở dữ liệu—vốn là bài toán có độ phức tạp hàm mũ rất lớn. Từ đó nảy sinh câu hỏi khoa học cốt lõi: liệu có phương thức nào cho phép phát hiện khóa trong một tập con thực sự của $\Omega$ hay không.

Bên cạnh đó, sau khi hoàn thành quá trình phát hiện, tập phụ thuộc thu được thường có kích thước rất lớn và chứa đựng nhiều yếu tố dư thừa, gây cản trở nghiêm trọng cho việc lưu trữ và ứng dụng. Việc nghiên cứu loại bỏ sự dư thừa này chưa được giải quyết triệt để. Đồng thời, hai dạng phụ thuộc hàm suy rộng điển hình là phụ thuộc hàm xấp xỉ (AFD) và phụ thuộc hàm điều kiện (CFD) vẫn đòi hỏi các cải tiến về kỹ thuật tính toán độ đo lỗi/độ thỏa, cũng như cần làm sáng tỏ thứ tự phân cấp hình thức giữa CFD và các dạng biểu diễn tri thức khác như luật kết hợp (Association Rules - AR).

Mục tiêu nghiên cứu

Luận án xác định mục tiêu tổng quát là nghiên cứu nhằm thu được các kết quả giải quyết hiệu quả các bài toán nêu trên trong phạm vi mô hình cơ sở dữ liệu quan hệ. Các nội dung và nhiệm vụ nghiên cứu cụ thể được tác giả xác định và đánh số như sau:

1. Nghiên cứu tổng quan về các loại phụ thuộc hàm suy rộng, các phương pháp phát hiện phụ thuộc hàm và phụ thuộc hàm suy rộng trong cơ sở dữ liệu quan hệ.
2. Nghiên cứu về phụ thuộc hàm xấp xỉ (AFD) và phụ thuộc hàm điều kiện (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 nhằ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ệ, tạo 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.

Đối tượng và phạm vi nghiên cứu

• Đối tượng nghiên cứu: Phụ thuộc hàm (FD), các dạng phụ thuộc hàm suy rộng (RFD bao gồm AFD, CFD, MFD, FFD, DD), thuật toán tính bao đóng của tập thuộc tính, khóa và siêu khóa của lược đồ quan hệ, các cấu trúc dữ liệu biểu diễn phân hoạch, dàn thuộc tính và tập phụ thuộc hàm.
• Phạm vi nghiên cứu: Mô hình cơ sở dữ liệu quan hệ, xét trên các bảng dữ liệu tĩnh và cơ sở dữ liệu quan hệ quy mô lớn (vài chục thuộc tính, hàng trăm nghìn bản ghi); phạm vi toán học lý thuyết bao gồm lý thuyết tập hợp, quan hệ tương đương, phân hoạch, lý thuyết đồ thị và độ phức tạp thuật toán.

---

Tổng quan tài liệu và vị trí của luận án

Các hướng nghiên cứu trước được điểm lại

Trong phần tổng quan, tác giả hệ thống hóa các mốc nghiên cứu từ khi E. Codd đề xuất mô hình dữ liệu quan hệ năm 1970 và Armstrong công bố hệ quy tắc suy diễn cho phụ thuộc hàm:

• Phương pháp phát hiện phụ thuộc hàm: Bài toán phát hiện phụ thuộc thu hút sự chú ý từ đầu thập niên 1980 qua các công trình của Flach [33], Mannila & Räihä [45, 49], Savnik & Flach [65]. Các thuật toán tiêu biểu theo phương pháp trên-xuống (top-down) gồm TANE của Huhtala et al. (1999) [37] khai thác dàn thuộc tính và phân hoạch lược gọn; FD_Mine của Yao & Hamilton (2008) [74] sử dụng phụ thuộc đối xứng; FUN của Novelli & Cicchetti (2001) [59] dựa trên lý thuyết tập tự do (free-set). Đối với phương pháp dưới-lên (bottom-up), các tác giả Lopes et al. (2000) [46] đề xuất Dep-Miner dựa trên phần bù tập cực đại, và Wyss et al. (2001) [73] phát triển thuật toán FastFDs khai thác tập khác nhau (difference-set) duyệt theo chiều sâu.
• Phụ thuộc hàm suy rộng (RFD): Kivinen & Mannila (1995) [41] khởi xướng nghiên cứu về phụ thuộc hàm xấp xỉ (AFD) với độ đo lỗi $g_3$ và phương pháp lấy mẫu xác suất. Các độ đo xấp xỉ và kỹ thuật tính toán khác được tổng hợp bởi Huhtala et al. [34], Wei & Yao [72], và Huhtala et al. [40]. Khái niệm phụ thuộc hàm mêtric (MFD) được Koudas et al. (2009) [42] đề xuất nhằm xử lý sai lệch định dạng; phụ thuộc hàm mờ (FFD) được phân tích bởi Bosc et al. (1999) [18] và [3]; phụ thuộc sai phân (DD) do Song & Chen (2011) [65] xây dựng.
• Phụ thuộc hàm điều kiện (CFD) và làm sạch dữ liệu: Bohannon et al. (2007) [12] đề xuất CFD mở rộng từ FD truyền thống để phục vụ làm sạch dữ liệu. Tiếp đó, Fan et al. (2008, 2011) [32] đề xuất các thuật toán CFDMiner, CTANE, FastCFD; Golab et al. (2008) [35] chứng minh bài toán tìm bảng mẫu tối ưu cho CFD là NP-đầy đủ (NP-C); Chiang & Miller (2008) [21] nghiên cứu kỹ thuật phát hiện CFD dựa trên phân hoạch.
• Tính bao đóng, bài toán xác định khóa và tiền xử lý FD: Lucchesi & Osborn (1978) [9] chứng minh bài toán quyết định tồn tại một khóa có kích thước không quá $k$ là NP-đầy đủ. Hướng nghiên cứu về thuật toán tính bao đóng, rút gọn bài toán tìm khóa và tiền xử lý tập FD được làm mới qua hàng loạt công trình của các tác giả quốc tế như [22, 23, 24, 25, 52, 53, 54, 55], song hành với các công trình trong nước về xác định tập rút gọn (reduct) của bảng quyết định.

Khoảng trống luận án lựa chọn giải quyết

1. Thiếu sót trong chứng minh nền tảng của thuật toán phân hoạch: Trong thuật toán kinh điển TANE [37] và công trình năm 2003 của Huhtala et al. [40], nhiều bổ đề cơ bản liên quan đến điều kiện tương đương của phân hoạch khi kiểm tra phụ thuộc hàm chưa được chứng minh hoặc chứng minh chưa đầy đủ. Luận án chọn giải quyết việc chuẩn hóa và đưa ra các chứng minh toán học hoàn chỉnh.
2. Hạn chế của luật tỉa khóa trên không gian toàn cục: Các thuật toán phát hiện FD hiện hữu đều tìm kiếm khóa trên toàn bộ tập thuộc tính $\Omega$. Luận án tập trung giải quyết bài toán rút gọn, đưa ra điều kiện cần cải tiến để xác định khóa trên tập con thực sự của $\Omega$, tạo cơ sở cho các luật tỉa nút hiệu quả hơn.
3. Vấn đề dư thừa sau khi phát hiện: Tập FD sinh ra từ dữ liệu thực tế luôn chứa các phụ thuộc dư thừa. Luận án lựa chọn giải quyết việc xây dựng một phép biến đổi tiền xử lý hiệu quả có cơ sở toán học chặt chẽ nhằm thu gọn tập FD mà vẫn bảo toàn tính tương đương.

---

Cơ sở lý thuyết và phương pháp nghiên cứu

Cơ sở lý thuyết và khung phân tích

Luận án vận dụng lý thuyết mô hình cơ sở dữ liệu quan hệ của E. Codd, lý thuyết phụ thuộc dữ liệu và hệ tiên đề Armstrong.

• Mô hình dữ liệu quan hệ: Một quan hệ $r$ xác định trên tập thuộc tính $\Omega = {A_1, A_2, \dots, A_n}$ là tập con của tích Descartes $\text{Dom}(A_1) \times \dots \times \text{Dom}(A_n)$. Một lược đồ quan hệ là cặp $S = \langle \Omega, F \rangle$, với $F$ là tập các phụ thuộc hàm.
• Phụ thuộc hàm (FD) và hệ quy tắc Armstrong: Với $X, Y \subseteq \Omega$, phụ thuộc hàm $X \to Y$ đúng trên $r$ nếu với mọi cặp bộ $t_1, t_2 \in r$, $t_1[X] = t_2[X] \Rightarrow t_1[Y] = t_2[Y]$. Hệ quy tắc suy diễn Armstrong gồm ba luật cơ bản: phản xạ, gia tăng ($X \to Y \Rightarrow XZ \to YZ$), và bắc cầu ($X \to Y \land Y \to Z \Rightarrow X \to Z$).
• Bao đóng và khóa: Bao đóng của tập thuộc tính $X$ đối với $F$, ký hiệu $X_F^+$, là tập tất cả các thuộc tính $A$ sao cho $(X \to A) \in F^+$. Tập thuộc tính $K \subseteq \Omega$ là một siêu khóa nếu $K_F^+ = \Omega$; $K$ là khóa nếu $K$ là siêu khóa tối tiểu (không tồn tại tập con thực sự $K' \subset K$ là siêu khóa).
• Các khái niệm phụ thuộc hàm suy rộng (RFD):
  • Phụ thuộc hàm xấp xỉ (AFD): Cho phép một tỷ lệ bộ nhỏ vi phạm, đánh giá qua các độ đo như độ đo lỗi $g_3(X \to Y, r) = \frac{\min {|r_1| : r_1 \subseteq r, X \to Y \text{ đúng trên } r \setminus r_1}}{|r|}$, độ thỏa $\text{TRUTH}r(X \to Y) = \frac{1}{\text{NTP}} \sum{t_i, t_j} \text{TRUTH}_{(t_i, t_j)}(X \to Y)$, hoặc độ phụ thuộc phân hoạch $k = |r_1|/|r|$.
  • Phụ thuộc hàm điều kiện (CFD): Mở rộng FD dưới dạng cặp $\phi = (X \to Y, T_p)$, trong đó $T_p$ là bảng mẫu chứa các giá trị hằng và biến không tên "$_$". CFD ràng buộc sự thỏa mãn ngữ nghĩa trên từng phân đoạn dữ liệu khớp với mẫu.
  • Phụ thuộc hàm mêtric (MFD): Nới lỏng điều kiện bằng nhau ở vế phải bằng hàm khoảng cách mêtric: $\max_{T \in \pi_X} \text{diam}_d(T[Y]) \le \epsilon$.
  • Phụ thuộc hàm mờ (FFD): Thay thế sự bằng nhau tuyệt đối bằng quan hệ tương đương mờ mức $\alpha$ ($E(\alpha)$).
  • Phụ thuộc sai phân (DD): Sử dụng các hàm sai phân $L, R$ với các phép so sánh số học trên khoảng cách giữa các thuộc tính.

Loại phụ thuộc	Dạng biểu diễn	Cơ chế nới lỏng quan hệ bằng nhau	Mục đích / Ứng dụng chính
FD	$X \to Y$	Đòi hỏi bằng nhau tuyệt đối trên mọi bộ dữ liệu	Chuẩn hóa CSDL, thiết kế lược đồ
AFD	$X \to Y$ kèm $e(X \to Y, r) \le \epsilon$	Cho phép một tỷ lệ bộ nhỏ vi phạm qua ngưỡng lỗi $\epsilon$	Khai phá tri thức, trích xuất quy luật gần đúng
CFD	$(X \to Y, T_p)$	Áp đặt bảng mẫu $T_p$ (chứa hằng số và biến "$_$")	Làm sạch dữ liệu, phát hiện không nhất quán
MFD	$X \to_d^\epsilon Y$	Thay $t_1[Y] = t_2[Y]$ bằng khoảng cách $d(t_1[Y], t_2[Y]) \le \epsilon$	Tích hợp dữ liệu đa nguồn có sai lệch định dạng
FFD	$X \to_\alpha Y$	Dùng quan hệ tương đương mờ mức $\alpha$ ($R_k \ge \alpha$)	Xử lý dữ liệu có bản chất mờ tự nhiên
DD	$[X(L)] \to [Y(R)]$	Dùng các hàm sai phân $L, R$ với toán tử khoảng cách	Ràng buộc chênh lệch biên độ giá trị thuộc tính

Phương pháp nghiên cứu thực tế

Luận án áp dụng phương pháp nghiên cứu toán học kết hợp với phân tích giải thuật:

• Phương pháp không gian tìm kiếm dạng dàn (Lattice): Thiết lập dàn thuộc tính đồ thị có hướng gồm $2^n$ nút và $n \cdot C_n^{\lfloor n/2 \rfloor} \cdot 2^{n/2}$ cạnh để biểu diễn không gian các phụ thuộc hàm ứng viên tối tiểu có vế phải đơn thuộc tính. Duyệt theo mức từ trên xuống (top-down) từ các tập thuộc tính nhỏ đến lớn, kết hợp các luật tỉa:
  • Luật tỉa T1: Nếu $X \to A$ đúng thì tỉa mọi $XZ \to A$.
  • Luật tỉa T2: Nếu $X \to A$ đúng và có ứng viên $XAY \to B$ thì thay bằng kiểm tra $XY \to B$.
  • Luật tỉa T3: Nếu $X$ là một khóa thì xóa toàn bộ các nút chứa $X$.
• Kỹ thuật phân hoạch (Partition-based): Phân hoạch $\pi_X$ của $r$ theo $X$ chia các bộ thành các lớp tương đương có cùng giá trị trên $X$. Kiểm tra $X \to A$ thông qua quan hệ độ mịn của phân hoạch ($\pi_X \le \pi_A$) hoặc so sánh số lượng lớp tương đương ($|\pi_X| = |\pi_{XA}|$), sử dụng phân hoạch lược gọn để tối ưu bộ nhớ.
• Kỹ thuật tập tự do (Free-set): Thuật toán FUN sử dụng lực lượng hình chiếu $|r[X]| = |r[XA]|$ để kiểm tra $X \to A$, tính toán bao đóng $X^+$ và hầu bao đóng $X^\circ$.
• Phương pháp so sánh cặp bộ (Bottom-up): Xây dựng tập bằng nhau $ag(t_1, t_2)$, tập bằng nhau cực đại $\max(A)$, phủ âm và tập khác nhau $dif(A)$ để suy dẫn phụ thuộc hàm tối tiểu thông qua thuật toán duyệt theo chiều sâu FastFDs hoặc Dep-Miner.
• Phương pháp đại số ma trận: Luận án phát triển kỹ thuật ma trận tương đương và ma trận thuộc tính để số hóa việc tính toán độ thỏa và kiểm tra phụ thuộc.
• Nguồn dữ liệu thực nghiệm: Luận án sử dụng các bảng dữ liệu quan hệ cụ thể để minh họa và kiểm chứng: quan hệ Nhân viên (bảng 1.1 gồm 8 bộ, 5 thuộc tính), quan hệ Phim (bảng 1.2 gồm 6 bộ, 3 thuộc tính), các quan hệ Qh1 (bảng 1.3), quan hệ Khách hàng Cust (bảng 1.4 gồm 6 bộ, 7 thuộc tính), Qh2 (bảng 1.5), Qh3 (bảng 1.6 gồm 4 bộ, 5 thuộc tính), quan hệ phân công (bảng 3.3).

---

Nội dung chính theo từng chương

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ệ

Chương 1 hệ thống hóa cơ sở lý thuyết về mô hình dữ liệu quan hệ, các tính chất đặc trưng của quan hệ (tính nguyên tố của miền trị, không trùng lặp bộ, thứ tự hàng/cột không quan trọng, xử lý giá trị null), khái niệm lược đồ quan hệ, hệ quy tắc Armstrong, bao đóng và khóa.

Chương này trình bày chi tiết các dạng phụ thuộc hàm suy rộng:

• Định nghĩa phụ thuộc hàm xấp xỉ (AFD) và các độ đo: độ đo lỗi $g_3$ của Kivinen & Mannila, độ thỏa $\text{TRUTH}r$ của Wei & Yao (ví dụ trên quan hệ Nhân viên cho thấy $\text{TRUTH}{\text{Nhân viên}}(\text{Tên} \to \text{Giới tính}) = 26/28 \approx 93%$), và độ phụ thuộc phân hoạch $k$ (đạt giá trị $0.875$ khi loại một bộ vi phạm).
• Khái niệm phụ thuộc hàm mêtric (MFD) với ví dụ trên quan hệ Phim, chứng minh $\text{Tên phim} \to_d^6 \text{Thời gian}$ đúng khi độ chênh lệch thời lượng giữa các nguồn dữ liệu không vượt quá 6 phút.
• Định nghĩa phụ thuộc hàm điều kiện (CFD) kèm bảng mẫu $T_p$ gồm các giá trị hằng và biến "$_$", phân tích ví dụ quan hệ Cust gồm 7 thuộc tính (CC, AC, PN, NM, STR, CT, ZIP) chứng minh một bộ đơn lẻ cũng có thể vi phạm CFD khi không khớp với mẫu.
• Phụ thuộc hàm mờ (FFD) trên quan hệ Qh2 thỏa mãn mức $\alpha = 0.8$, phụ thuộc sai phân (DD) với ví dụ ràng buộc $[\text{Date} (\le 7)] \to [\text{Price} (\le 100)]$, cùng các dạng khác như phụ thuộc dựa trên xác suất, phụ thuộc tương tự.

Chương 1 đi sâu phân tích hai hướng tiếp cận phát hiện phụ thuộc hàm:

• Phương pháp top-down: Phân tích cấu trúc dàn thuộc tính với $2^n$ nút; chứng minh độ phức tạp thời gian khi duyệt vòng lặp lồng nhau là $O(|r|^2 \cdot n \cdot 2^n)$. Trình bày chi tiết Thuật toán 1.1 kết hợp các luật tỉa T1, T2, T3 để xuất ra phủ của các phụ thuộc hàm và tập khóa $K$. Phân tích phương pháp phân hoạch trong TANE và FD_Mine, chứng minh độ phức tạp giảm xuống còn $O(n|r| + |r| \cdot 2^n)$, nhanh hơn $n^2$ lần so với vòng lặp lồng nhau, nhưng tốn thêm chi phí bộ nhớ lưu phân hoạch là $O(|r| \cdot 2^n / \sqrt{n})$. Phân tích thuật toán FUN dựa trên tập tự do với độ phức tạp $O(h|r| \cdot n/2)$.
• Phương pháp bottom-up: Trình bày cách xây dựng tập bằng nhau $ag(r)$, xác định tập cực đại $\max(A)$ để lập công thức sinh $FD_1(A)$ và $FD(A)$, tính độ phức tạp tổng cộng $O(n|r|^2 + n|ag(r)|^2 + n|\max(A)| \cdot 2^{|L|/2})$. Trình bày tiếp cận tập khác nhau $dif(A)$ trong Dep-Miner và FastFDs.
• Các chủ đề liên quan: Phân tích kỹ thuật lấy mẫu (sampling) với tham số tin cậy $\varepsilon$ trong phát hiện FD và AFD; cơ chế duy trì FD khi thực hiện chèn bộ ($q \le 1$) hoặc xóa bộ dữ liệu; định lý kiểm tra khóa thông qua tính lực lượng $r[X] = |r|$; bài toán phát hiện CFD sử dụng phân hoạch tách tập điều kiện $Q$ và tập biến $W$, cùng thuật toán tham lam tìm bảng mẫu gần tối ưu có độ phức tạp $|r| \cdot 2^{|X|}$.

Chương 2. Phụ thuộc hàm xấp xỉ và phụ thuộc hàm điều kiện

Chương 2 tập trung giải quyết các bài toán nền tảng về AFD và CFD:

• Chuẩn hóa các kết quả liên quan đến FD và AFD: Tác giả phân tích các bổ đề trong thuật toán TANE [37] và bài báo năm 2003 của Huhtala et al. [40]. Luận án chỉ rõ các kết quả công bố năm 2003 thực chất chính là các bổ đề trong [37], đồng thời tác giả trực tiếp đưa ra các chứng minh toán học hoàn chỉnh, chặt chẽ cho các bổ đề còn bỏ ngỏ trong [37]:
  • Định lý 2.1 (Bổ đề 2.1 trong [37]): Phụ thuộc hàm $X \to A$ được thỏa mãn khi và chỉ khi phân hoạch $\pi_X$ mịn hơn phân hoạch $\pi_A$. Luận án chứng minh hai chiều dựa trên ánh xạ lớp tương đương: $t[X] = u[X] \Rightarrow t[A] = u[A]$ dẫn đến mọi lớp tương đương trong $\pi_X$ đều là tập con của một lớp tương đương trong $\pi_A$, và ngược lại.
  • Định lý 2.2 (Bổ đề 2.2 trong [37]): Phụ thuộc hàm $X \to A$ được thỏa mãn khi và chỉ khi $|\pi_X| = |\pi_{X{A}}|$. Chứng minh khẳng định số lượng lớp tương đương của hai phân hoạch bằng nhau khi và chỉ khi thuộc tính $A$ không làm phân tách thêm bất kỳ lớp tương đương nào của $\pi_X$.
• Kỹ thuật ma trận tương đương và ma trận thuộc tính: Đề xuất mô hình ma trận để số hóa quan hệ tương đương giữa các bộ dữ liệu. Thiết lập các tính chất của ma trận thuộc tính và ứng dụng ma trận để kiểm tra nhanh sự thỏa mãn của phụ thuộc hàm, đồng thời tính toán trực tiếp các độ đo xấp xỉ trong AFD.
• Nghiên cứu về phụ thuộc hàm điều kiện (CFD): Phân tích sự cần thiết phải mở rộng FD thành CFD trong việc nắm bắt các yếu tố dữ liệu không nhất quán. Làm rõ cú pháp, ngữ nghĩa hình thức và các luật suy diễn đối với CFD (minh họa tại Hình 2.1).
• Thứ tự phân cấp giữa FD, CFD và AR: Phân tích mối quan hệ toán học và thiết lập thứ tự phân cấp hình thức giữa phụ thuộc hàm truyền thống (FD), phụ thuộc hàm điều kiện (CFD) và luật kết hợp (Association Rules - AR), xác định phạm vi ràng buộc của từng loại phụ thuộc trên dữ liệu.

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ệ

Chương 3 giải quyết hai bài toán then chốt nhằm nâng cao hiệu năng tìm khóa và tỉa không gian tìm kiếm:

• Cải tiến thuật toán tính bao đóng: Phân tích các thuật toán tính bao đóng thuộc tính $X_F^+$ kinh điển, chỉ ra các điểm nghẽn tính toán khi phải quét lặp lại tập phụ thuộc $F$. Đề xuất cấu trúc dữ liệu cải tiến giúp tăng tốc độ tính bao đóng, trực tiếp hỗ trợ thuật toán phát hiện khóa của lược đồ quan hệ.
• Rút gọn bài toán xác định khóa của lược đồ quan hệ:
  • Điểm lại các kết quả đã biết về bài toán tìm khóa, đặc biệt là tính chất NP-đầy đủ của bài toán xác định sự tồn tại của khóa có kích thước không quá $k$.
  • Đề xuất dạng cải tiến cho điều kiện cần xác định khóa: Luận án phân tích điều kiện cần xác định khóa đã được công bố năm 1985, phát hiện các điểm còn hạn chế và đưa ra dạng cải tiến mới cho điều kiện cần này.
  • Tiến hành so sánh định lượng và định tính giữa các điều kiện cần xác định khóa cũ và điều kiện cải tiến mới, chứng minh điều kiện mới loại bỏ được nhiều thuộc tính không khóa hơn.
  • Giải quyết bài toán quyết định: Chứng minh rằng có thể kiểm tra và phát hiện khóa trong một tập con thực sự $X \subset \Omega$ thay vì phải duyệt toàn bộ không gian thuộc tính $\Omega$. Kết quả này cung cấp một luật tỉa khóa mới, giải quyết hạn chế lớn của các thuật toán top-down truyền thống.
• Thực nghiệm kiểm chứng được minh họa cụ thể qua bảng phân công (bảng 3.3) và các bảng kết quả thử nghiệm (bảng 3.1, 3.2).

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

Chương 4 tập trung giải quyết vấn đề tối ưu hóa tập phụ thuộc hàm sau khi phát hiện:

• Sự dư thừa trong tập phụ thuộc hàm: Phân tích bản chất của sự dư thừa cú pháp và dư thừa ngữ nghĩa trong tập FD sinh ra từ dữ liệu, làm tăng chi phí lưu trữ và cản trở việc chuẩn hóa cơ sở dữ liệu.
• Phép biến đổi tiền xử lý hiệu quả: Đề xuất một thuật toán tiền xử lý tác động lên tập phụ thuộc hàm $F$ ban đầu để loại bỏ các phụ thuộc hàm dư thừa, tạo ra tập phụ thuộc $F'$ tương đương nhưng có kích thước và số lượng phụ thuộc tối tiểu hơn.
• Chứng minh mới cho Định lý 4.1: Cung cấp chứng minh toán học độc lập, chặt chẽ cho Định lý 4.1—định lý nền tảng xác lập tính đúng đắn, tính bảo toàn bao đóng và tính tối tiểu của tập phụ thuộc sau phép biến đổi tiền xử lý.
• Minh họa giải thuật chi tiết qua các ví dụ 4.1, 4.2 trên các bảng dữ liệu thử nghiệm (bảng 4.1, 4.2), khẳng định tính khả thi và hiệu quả của phép biến đổi.

---

Kết quả và những đóng góp mới

Các kết quả và đóng góp mới của luận án được tác giả tự xác định bao gồm các nội dung lý luận và giải pháp thực tiễn sau:

Đóng góp về mặt lý luận

1. Hoàn thiện hệ thống chứng minh lý thuyết phân hoạch: Luận án đã đưa ra các chứng minh toán học chặt chẽ, đầy đủ cho các bổ đề nền tảng trong thuật toán TANE [37] (Định lý 2.1 và Định lý 2.2) mà tài liệu gốc chưa chứng minh; đồng thời làm rõ mối liên hệ giữa công trình năm 2003 [40] với các kết quả trong [37].
2. Xây dựng phương pháp ma trận và phân cấp phụ thuộc: Đề xuất kỹ thuật sử dụng ma trận tương đương và ma trận thuộc tính để kiểm tra phụ thuộc hàm và tính toán các độ đo xấp xỉ trong AFD; thiết lập và chứng minh hình thức thứ tự phân cấp giữa ba lớp ràng buộc: Phụ thuộc hàm (FD), Phụ thuộc hàm điều kiện (CFD) và Luật kết hợp (AR).
3. Cải tiến điều kiện cần xác định khóa của lược đồ quan hệ: Đưa ra dạng cải tiến cho điều kiện cần xác định khóa đã được công bố năm 1985; giải quyết bài toán quyết định cho phép phát hiện khóa trên một tập con thực sự của tập thuộc tính $\Omega$, khắc phục hạn chế tìm kiếm toàn cục của các luật tỉa khóa trước đây.
4. Cung cấp chứng minh mới cho Định lý 4.1: Đưa ra chứng minh toán học mới, chặt chẽ cho Định lý 4.1 làm cơ sở cho phép biến đổi tiền xử lý tập phụ thuộc hàm.

Đóng góp về mặt thực tiễn và giải pháp đề xuất

1. Thuật toán tiền xử lý làm gọn tập phụ thuộc: Đề xuất thuật toán biến đổi tiền xử lý hiệu quả giúp loại bỏ triệt để các phụ thuộc hàm dư thừa trong tập FD đã phát hiện, thu được tập FD tương đương có kích thước nhỏ gọn hơn, hỗ trợ tối ưu hóa lưu trữ và chuẩn hóa lược đồ dữ liệu.
2. Nâng cao hiệu năng thuật toán tìm khóa và phát hiện FD: Việc cải tiến thuật toán tính bao đóng kết hợp với luật tỉa khóa trên tập con thực sự giúp thu hẹp đáng kể không gian tìm kiếm dạng dàn, giảm thiểu số lượng ứng viên cần kiểm tra trong các cơ sở dữ liệu lớn.
3. Ứng dụng trong đánh giá chất lượng và làm sạch dữ liệu: Các kỹ thuật tính độ thỏa AFD và phát hiện CFD được hoàn thiện trong luận án cung cấp công cụ tự động để rà soát lỗi, phát hiện các bản ghi không nhất quán trong các cơ sở dữ liệu y tế, viễn thông và hành chính.

---

Hạn chế và hướng nghiên cứu tiếp

Hạn chế được văn bản đề cập

• Độ phức tạp trường hợp xấu nhất: Không gian tìm kiếm của bài toán phát hiện phụ thuộc hàm và phụ thuộc hàm suy rộng vẫn mang bản chất hàm mũ theo số lượng thuộc tính trong trường hợp xấu nhất (khi vế trái của các phụ thuộc hàm chứa hầu hết các thuộc tính của quan hệ).
• Độ phức tạp của bài toán bảng mẫu CFD: Bài toán phát hiện bảng mẫu tối ưu $T_p$ cho một phụ thuộc hàm điều kiện nhúng đã được chứng minh là NP-đầy đủ [35]. Các thuật toán hiện tại (kể cả thuật toán tham lam) mới chỉ tìm được bảng mẫu gần tối ưu và có độ phức tạp thời gian vẫn là hàm mũ $|r| \cdot 2^{|X|}$.
• Vấn đề duy trì phụ thuộc khi xóa dữ liệu: Khi thực hiện thao tác xóa một bộ khỏi quan hệ, các phụ thuộc hàm mới có thể xuất hiện do các bộ vi phạm đã bị loại bỏ; văn bản chỉ rõ hiện chưa có giải pháp đơn giản để phát hiện các phụ thuộc hàm mới này mà bắt buộc phải áp dụng lại thuật toán phát hiện từ đầu trên quan hệ $(r \setminus {t})$.

Hướng nghiên cứu tiếp theo

1. Tiếp tục nghiên cứu, hoàn thiện các thuật toán tỉa không gian tìm kiếm dựa trên điều kiện cần xác định khóa cải tiến, thử nghiệm trên các hệ quản trị cơ sở dữ liệu phân tán và dữ liệu lớn.
2. Phát triển các thuật toán đơn giản và hiệu quả hơn để giải quyết bài toán tìm bảng mẫu $T_p$ cho phụ thuộc hàm điều kiện, tối ưu hóa các tham số ngưỡng hỗ trợ và độ tin cậy.
3. Nghiên cứu sâu hơn về cơ chế cập nhật động và duy trì tập phụ thuộc hàm đã phát hiện khi cơ sở dữ liệu có các biến động dữ liệu thường xuyên (đặc biệt là thao tác xóa bản ghi).
4. Mở rộng việc kết hợp giữa CFD, AFD với các kỹ thuật học máy để xây dựng quy trình tự động hóa hoàn toàn trong làm sạch và sửa lỗi dữ liệu.

---

Giá trị tham khảo

Luận án mang lại giá trị tham khảo cụ thể cho nhiều đối tượng nghiên cứu và ứng dụng:

• Đối với nghiên cứu sinh, học viên cao học và giảng viên chuyên ngành Cơ sở Toán học cho Tin học, Khoa học Máy tính: Luận án là tài liệu tham khảo sâu về mặt phương pháp luận toán học rời rạc trong cơ sở dữ liệu. Chương 1 cung cấp cái nhìn toàn diện, chuẩn xác về các cấu trúc phát hiện FD (dàn thuộc tính, phân hoạch, tập tự do, phủ âm, tập khác nhau). Chương 2 là tài liệu mẫu mực về kỹ thuật chứng minh hình thức các tính chất phân hoạch (Định lý 2.1, 2.2) và ứng dụng ma trận trong đại số quan hệ.
• Đối với các nhà nghiên cứu về thuật toán tối ưu và tối chuẩn CSDL: Nội dung Chương 3 về thuật toán tính bao đóng và điều kiện cần cải tiến để xác định khóa trên tập con thực sự cung cấp cách tiếp cận hữu ích để thiết kế các luật tỉa mới, vượt qua rào cản độ phức tạp hàm mũ khi xử lý bảng dữ liệu nhiều cột.
• Đối với kỹ sư dữ liệu và chuyên gia quản trị chất lượng dữ liệu: Nội dung Chương 2 (về AFD, CFD) và Chương 4 (về phép biến đổi tiền xử lý loại bỏ dư thừa) cung cấp cơ sở thuật toán để xây dựng các công cụ tự động phát hiện quy tắc nghiệp vụ, đánh giá độ tin cậy của dữ liệu và làm sạch dữ liệu trong các hệ thống thông tin quy mô lớn.

---

Câu hỏi thường gặp

1. Độ đo lỗi $g_3$ trong phụ thuộc hàm xấp xỉ (AFD) được định nghĩa và tính toán như thế nào?

Theo định nghĩa của Kivinen & Mannila [41] được trình bày trong luận án, độ đo lỗi $g_3$ của phụ thuộc hàm $X \to Y$ trên quan hệ $r$ biểu thị tỷ lệ số bộ tối thiểu cần phải loại bỏ khỏi $r$ để $X \to Y$ trở thành một phụ thuộc hàm đúng hoàn toàn: $$g_3(X \to Y, r) = \frac{\min {|r_1| : r_1 \subseteq r, X \to Y \text{ đúng trên } r \setminus r_1}}{|r|}$$ Một phụ thuộc hàm được coi là phụ thuộc hàm xấp xỉ nếu $g_3(X \to Y, r) \le \epsilon$, với $\epsilon$ là ngưỡng lỗi cho trước ($0 \le \epsilon \le 1$). Ngoài ra, Huhtala et al. [40] chứng minh rằng $X \to A$ xấp xỉ khi và chỉ khi $g_3(X) = g_3(XA)$, với $g_3(Z) = 1 - |r[Z]|/|r|$ là phần bộ tối thiểu cần loại bỏ để $Z$ trở thành siêu khóa.

2. Hai điều kiện cần và đủ để phụ thuộc hàm $X \to A$ thỏa mãn theo lý thuyết phân hoạch là gì?

Trong Chương 2, tác giả đã đưa ra chứng minh hoàn chỉnh cho hai định lý nền tảng:

• Định lý 2.1: Phụ thuộc hàm $X \to A$ được thỏa mãn trên $r$ khi và chỉ khi phân hoạch $\pi_X$ mịn hơn phân hoạch $\pi_A$ (ký hiệu $\pi_X \le \pi_A$).
• Định lý 2.2: Phụ thuộc hàm $X \to A$ được thỏa mãn trên $r$ khi và chỉ khi số lượng lớp tương đương của phân hoạch $\pi_X$ bằng số lượng lớp tương đương của phân hoạch tích $\pi_{X{A}}$ (tức là $|\pi_X| = |\pi_{X{A}}|$).

3. Tại sao luật tỉa khóa lại quan trọng trong thuật toán phát hiện FD và hạn chế của luật cũ là gì?

Luật tỉa khóa (Luật T3) cực kỳ quan trọng vì khi xác định được một tập thuộc tính $X$ là khóa, theo hệ quy tắc Armstrong, mọi siêu tập chứa $X$ đều là siêu khóa và xác định hàm mọi thuộc tính còn lại; do đó thuật toán có thể xóa bỏ toàn bộ các nút chứa $X$ trong dàn thuộc tính, thu hẹp đột biến không gian tìm kiếm. Hạn chế của các luật tỉa khóa trước đây là phải tiến hành tìm khóa trên toàn bộ tập thuộc tính $\Omega$ của cơ sở dữ liệu—một bài toán có độ phức tạp hàm mũ theo số thuộc tính. Luận án khắc phục nhược điểm này bằng cách đề xuất điều kiện cần cải tiến cho phép xác định khóa ngay trên một tập con thực sự của $\Omega$.

4. Điểm khác biệt căn bản giữa phụ thuộc hàm điều kiện (CFD) và phụ thuộc hàm truyền thống (FD) là gì?

Điểm khác biệt căn bản nằm ở phạm vi thỏa mãn và cơ chế vi phạm:

• Phụ thuộc hàm truyền thống $X \to Y$ đòi hỏi tính nhất quán trên toàn bộ các bộ của quan hệ $r$, và sự vi phạm chỉ có thể được xác định khi so sánh ít nhất hai bộ ($t_1[X] = t_2[X]$ nhưng $t_1[Y] \ne t_2[Y]$).
• Phụ thuộc hàm điều kiện có dạng $(X \to Y, T_p)$, chỉ đòi hỏi sự thỏa mãn trên các bộ khớp với bảng mẫu $T_p$ (chứa các giá trị hằng hoặc biến không tên "$_$"). Do đó, một bộ đơn lẻ cũng có thể vi phạm CFD nếu nó khớp với phần vế trái của một bộ mẫu hằng nhưng lại có giá trị vế phải khác với giá trị quy định trong mẫu đó.

5. Bài toán quyết định xác định sự tồn tại của một khóa có kích thước không vượt quá $k$ thuộc tính thuộc lớp độ phức tạp nào?

Theo công trình của Lucchesi & Osborn (1978) [9] được tác giả trích dẫn và khẳng định lại ở Chương 1, cho trước một lược đồ quan hệ với tập thuộc tính $\Omega$ và tập phụ thuộc hàm $F$, bài toán quyết định xác định xem có hay không một khóa chứa nhiều nhất $k$ thuộc tính ($k \le |\Omega|$) là bài toán NP-đầy đủ (NP-Complete).

---

Kết luận

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" của nghiên cứu sinh Vũ Quốc Tuấn là một công trình nghiên cứu chuyên sâu thuộc chuyên ngành Cơ sở Toán học cho Tin học, tập trung giải quyết bài toán cốt lõi về tối ưu hóa không gian tìm kiếm và xử lý dư thừa trong khai phá phụ thuộc dữ liệu. Tác giả đã hoàn thiện cơ sở lý thuyết toán học thông qua việc chứng minh chặt chẽ các bổ đề về quan hệ phân hoạch, đề xuất kỹ thuật ma trận thuộc tính, thiết lập thứ tự phân cấp giữa FD, CFD, AR, và cải tiến điều kiện cần xác định khóa trên tập con thực sự của tập thuộc tính. Đồng thời, luận án đã xây dựng thành công phép biến đổi tiền xử lý giúp loại bỏ dư thừa trong các tập phụ thuộc hàm phát hiện được, cung cấp đóng góp có giá trị lý luận và thực tiễn cho việc nâng cao hiệu năng khai phá tri thức và quản trị chất lượng dữ liệu trong các hệ thống cơ sở dữ liệu quan hệ.

Trích đoạn nội dung tài liệu

phần mở đầu, bốn chương nội dung và phần kết luận. 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 quát các phương pháp đã được sử dụng để phát hiện các FD và FD suy rộng. Trình bày về AFD và CFD (hai loại FD suy rộng điển hình) và một số kết quả có liên quan. Trình bày các 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à một số kết quả có liên quan.

Trình bày một phép biến đổi tiền xử lý hiệu quả các tập FD (nhằm hạn chế sự dư thừa trong một tập FD cho trước) và một số kết quả liên quan. Tổng kết các kết quả đã đạt được, những điểm còn tồn tại và hướng nghiên cứu tiếp theo. PHỤ THUỘC HÀM VÀ PHỤ THUỘC HÀM SUY RỘNG TRONG MÔ HÌNH DỮ LIỆU QUAN HỆ Chương này nhắc lại các khái niệm cơ bản của mô hình dữ liệu quan hệ, tập trung vào các khái niệm phụ thuộc hàm, phụ thuộc hàm suy rộng và khái quát các phương pháp đã được sử dụng để phát hiện phụ thuộc hàm và phụ thuộc hàm suy rộng. Nhắc lại một số khái niệm cơ bản Mô hình dữ liệu quan hệ được E.Codd đề xuất năm 1970 và ngay lập tức mô hình này đã gây được sự chú ý vì có tính đơn giản và cơ sở toán học vững chắc.

Mô hình dữ liệu quan hệ biểu thị dữ liệu trong một cơ sở dữ liệu như một tập các quan hệ. Về mặt trực quan, ta có thể hình dung một quan hệ như là một bảng giá trị gồm các hàng và các cột. Mỗi hàng trong bảng là một tập các giá trị có liên quan đến nhau, các giá trị này biểu thị một sự kiện tương ứng với một thực thể hay một mối quan hệ trong thế giới thực. Trong lý thuyết mô hình dữ liệu quan hệ, các thuật ngữ quan hệ, thuộc tính, miền và bộ tương ứng được dùng để chỉ bảng, cột, kiểu dữ liệu của một cột và một hàng trong bảng.

Miền Một miền D là một tập các giá trị nguyên tố, hiểu theo nghĩa mỗi giá trị trong miền là không thể phân chia được thành các thành phần nhỏ hơn trong phạm vi mô hình quan hệ. Mỗi miền được đặc tả thông qua một tên miền và một kiểu dữ liệu. Tương ứng với mỗi thuộc tính có một miền, các thuộc tính khác nhau không nhất thiết phải có các miền khác nhau. Quan hệ Một quan hệ trên (hay xác định trên) tập thuộc tính Ω = {A1, A2,…,An} là một tập con của tích Descartes Dom(A1)  Dom(A2)  …  Dom(An), trong đó Dom(Ai) là miền trị của thuộc tính Ai, i = 1, 2,…, n.

6 Cho quan hệ r xác định trên tập thuộc tính Ω = {A1, A2,…,An}. Theo định nghĩa, ta có thể viết r dưới dạng sau: r  {(a1, a2,…,an) | ai  Dom(Ai), i = 1, 2,…, n} 1. Các tính chất đặc trưng của một quan hệ Để làm rõ hơn khái niệm quan hệ trong mô hình dữ liệu quan hệ, ta xem xét các tính chất đặc trưng sau đây của quan hệ:  Mỗi quan hệ có một tên phân biệt.  Mỗi ô trong bảng (quan hệ) chứa một giá trị nguyên tố.

 Mỗi thuộc tính có một tên phân biệt.  Các giá trị của một thuộc tính thuộc cùng một miền.  Thứ tự của các thuộc tính là không quan trọng.  Không có hai bộ trùng nhau trong một quan hệ.

 Thứ tự của các bộ là không quan trọng.