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

Chuyên khảo phân tích Phát hiện phụ thuộc hàm và phụ thuộc suy rộng trong cơ sở dữ liệu, đánh giá các khía cạnh quan trọng, đề xuất hướng nghiên cứu tiếp theo.

• 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ọ.

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. Mỗi giá trị trong một bộ phải là một giá trị nguyên tố. Mô hình dữ liệu quan hệ không cho phép có các thuộc tính phức hợp hoặc các thuộc tính đa trị. Đặc trưng này đòi hỏi mỗi thuộc tính đa trị phải được biểu diễn bằng một quan hệ và mỗi thuộc tính phức hợp phải được biểu diễn bằng các thành phần đơn của nó.

Trường hợp một số ô trong bảng (quan hệ) có thể là chưa biết được giá trị của chúng vào thời điểm đang xét hoặc không có giá trị nào thích hợp đặt cho một ô (thuộc tính) của một bộ nào đó thì một giá trị đặc biệt, gọi là giá trị null, được sử dụng cho các ô kiểu này. Thứ tự của các thuộc tính trong một quan hệ là không quan trọng khi đảm bảo được sự tương ứng giữa các thuộc tính với các giá trị. Vì các phần tử trong một tập hợp là không có thứ tự nên các bộ không có một thứ tự bắt buộc trong một quan hệ. Định nghĩa quan hệ cũng cho thấy rằng hai quan hệ được xem là đồng nhất nếu chúng có cùng các bộ cho dù thứ tự các bộ trong chúng khác nhau.

Lược đồ quan hệ Một lược đồ quan hệ S là một cặp có thứ tự S = <Ω, F>, trong đó Ω là 7 tập hữu hạn các thuộc tính của quan hệ, F là tập các ràng buộc giữa các thuộc tính. Một ràng buộc trên tập thuộc tính {A1, A2,…,An} là một tính chất trên tập tất cả các quan hệ xác định trên tập thuộc tính này. Mỗi ràng buộc còn được gọi là một phụ thuộc dữ liệu. Một lược đồ quan hệ được sử dụng để mô tả về cấu trúc và các ràng buộc của một quan hệ.

Một quan hệ có thể liên tục thay đổi theo thời gian nhưng cấu trúc và các ràng buộc của nó có thể ổn định trong một khoảng thời gian nhất định. Cho lược đồ quan hệ S = <Ω, F> với Ω = {A1, A2,…,An}. Nếu không quan tâm đến tập các ràng buộc F thì ta sẽ dùng ký hiệu S(A1, A2,…,An) hoặc S(Ω) thay cho S = <Ω, F>. Ta dùng ký hiệu r(S) để chỉ một quan hệ r (hay một thể hiện r) của lược đồ quan hệ S.

Với một bộ t của r(S) và X  Ω, ta ký hiệu t[X] là bộ chỉ chứa các giá trị của bộ t tại các thuộc tính trong X. Một lược đồ cơ sở dữ liệu quan hệ là một tập các lược đồ quan hệ S’ = {S1, S2,…,Sp}. Một thể hiện của một lược đồ cơ sở dữ liệu quan hệ S’ là một tập các thể hiện DB = {r1(S1), r2(S2),…, rp(Sp)}. Một cơ sở dữ liệu quan hệ là một thể hiện của một lược đồ cơ sở dữ liệu quan hệ.

Một cơ sở dữ liệu quan hệ cỡ lớn là một cơ sở dữ liệu quan hệ chứa một lượng lớn dữ liệu (cỡ vài chục thuộc tính, hàng trăm nghìn bản ghi). Phụ thuộc hàm Phụ thuộc hàm là một loại phụ thuộc dữ liệu giữa hai nhóm thuộc tính của một lược đồ quan hệ và nó thể hiện tính chất ngữ nghĩa của các thuộc tính. Khái niệm phụ thuộc hàm Phụ thuộc hàm. Cho  là tập thuộc tính và S() là một lược đồ quan hệ trên .

Khi đó Y được gọi là phụ thuộc hàm vào X trên lược đồ S(), ký hiệu là X  Y, nếu với mọi quan hệ r trên lược đồ S(), với hai bộ bất kỳ t1, t2  r mà t1[X] = t2[X] thì t1[Y] = t2[Y]. 8 Nếu Y phụ thuộc hàm vào X thì ta cũng nói "X xác định hàm Y". Với mỗi quan hệ r trên lược đồ S(), ta nói r thỏa mãn (hay thỏa) phụ thuộc hàm X  Y (hay phụ thuộc hàm X  Y đúng trên r) nếu và chỉ nếu với mọi bộ t1, t2  r, t1[X] = t2[X] kéo theo t1[Y] = t2[Y]. Trong luận án này, ta hạn chế F của lược đồ S = <, F> chỉ gồm các phụ thuộc hàm.

Hệ quy tắc suy diễn Armstrong Với lược đồ quan hệ S = <, F> và X, Y  , ta ký hiệu XY thay cho X  Y. Với mọi X, Y, Z  , hệ quy tắc suy diễn Armstrong đối với các phụ thuộc hàm gồm ba quy tắc sau đây: Q1. (Gia tăng): Nếu X  Y thì XZ  YZ. (Bắc cầu): Nếu X  Y và Y  Z thì X  Z.

Ký hiệu F+ là tập tất cả các phụ thuộc hàm được suy diễn từ F bằng cách áp dụng một số hữu hạn lần các quy tắc của hệ quy tắc suy diễn Armstrong. Bao đóng của một tập thuộc tính Cho tập phụ thuộc hàm F xác định trên tập thuộc tính  (phụ thuộc hàm Y  Z xác định trên tập thuộc tính  nếu Y, Z  ) và X  . Ta gọi bao đóng của tập thuộc tính X đối với tập phụ thuộc hàm F, ký hiệu là X F , là tập tất cả các thuộc tính A của  sao cho X  A được suy diễn từ F nhờ hệ quy tắc suy diễn Armstrong. Khóa của lược đồ quan hệ Một quan hệ là một tập hợp các bộ.

Các phần tử trong một tập hợp là phân biệt nên không thể có hai bộ trùng nhau trong một quan hệ. Như vậy, với mỗi lược đồ quan hệ S = <Ω, F>, tồn tại một tập thuộc tính SK  Ω có tính chất: với mỗi thể hiện r(S) thì t1[SK] ≠ t2[SK], với t1, t2 là hai bộ khác nhau bất kỳ trong r. 9 Siêu khóa của một lược đồ quan hệ S là một tập gồm một hay nhiều thuộc tính của lược đồ S có tính chất xác định duy nhất một bộ trong mỗi thể hiện của S. Cho lược đồ quan hệ S = <Ω, F>.

Nếu SK là siêu khóa của S thì mọi tập con của Ω mà chứa SK cũng là siêu khóa của S. Một siêu khóa "nhỏ nhất" được gọi là một khóa. Khóa của một lược đồ quan hệ S là một siêu khóa của S sao cho mọi tập con thực sự của siêu khóa này đều không phải là siêu khóa của S. Mỗi lược đồ quan hệ luôn có ít nhất một khóa và có thể có nhiều khóa.

Một thuộc tính xuất hiện trong một khóa nào đó được gọi là thuộc tính khóa. Ngược lại, một thuộc tính không xuất hiện trong bất kỳ khóa nào được gọi là thuộc tính không khóa. Sử dụng khái niệm phụ thuộc hàm, khái niệm khóa và siêu khóa của lược đồ quan hệ được định nghĩa lại như sau: Cho lược đồ quan hệ S = <, F> và K  . Ta nói K là một khóa của S nếu hai điều kiện sau đây đồng thời được thỏa mãn: (i).

Nếu K'  K thì (K'  )  F+ Nếu K   thỏa mãn điền kiện (i) thì K được gọi là một siêu khóa của S. Như vậy, mọi khóa của S đồng thời cũng là siêu khóa của S.