Phương pháp ma trận phát hiện phụ thuộc hàm trong cơ sở dữ liệu

Phát hiện phụ thuộc hàm từ một cơ sở dữ liệu là một kỹ thuật khai phá dữ liệu quan trọng. Trong bài báo này, chúng tôi trình bày một thuật toán phát hiện các phụ thuộc hàm sử dụng ma trận tương đương. Ưu điểm của phương pháp này là các ma trận có thể tính toán một cách đơn giản và hiệu quả.
Nội dung trích xuất từ tài liệu:
Phương pháp ma trận phát hiện phụ thuộc hàm trong cơ sở dữ liệu Nghiªn cøu khoa häc c«ng nghÖ PH­¬NG PH¸P MA TRËN PH¸T HIÖN PHô THUéC HµM TRONG C¬ Së D÷ LIÖU VŨ QUỐC TUẤN*, VŨ CHÍNH THÚY** Tóm tắt: Phát hiện phụ thuộc hàm từ một cơ sở dữ liệu là một kỹ thuật khai phá dữ liệu quan trọng. Trong bài báo này, chúng tôi trình bày một thuật toán phát hiện các phụ thuộc hàm sử dụng ma trận tương đương. Ưu điểm của phương pháp này là các ma trận có thể tính toán một cách đơn giản và hiệu quả. Từ khóa: Khai phá dữ liệu, Cơ sở dữ liệu, Quan hệ, Lược đồ quan hệ, Phụ thuộc hàm, Ma trận tương đương. 1. GIỚI THIỆU Cơ sở dữ liệu là một hướng nghiên cứu quan trọng của công nghệ thông tin và đã được ứng dụng thành công trong nhiều lĩnh vực. Phụ thuộc hàm là một loại ràng buộc dữ liệu giữa các thuộc tính trong một quan hệ. Tính nhất quán dữ liệu có thể được bảo đảm nhờ sử dụng các phụ thuộc hàm để loại bỏ dữ liệu dư thừa, phụ thuộc hàm cũng thể hiện ngữ nghĩa giữa các thuộc tính và có thể tồn tại cả trong các tập dữ liệu độc lập với mô hình quan hệ. Nghiên cứu về phụ thuộc hàm cũng là một hướng trong thiết kế cơ sở dữ liệu quan hệ. Phát hiện các phụ thuộc hàm từ một cơ sở dữ liệu là một kỹ thuật khai phá dữ liệu quan trọng. Trong những năm gần đây, việc nghiên cứu, ứng dụng nhằm phát hiện tri thức, khai phá dữ liệu từ các phụ thuộc hàm đã đạt được những kết quả có ý nghĩa. Bài báo này trình bày một phương pháp tiếp cận mới để xác định các phụ thuộc hàm trong cơ sở dữ liệu quan hệ, đó là phương pháp dùng ma trận. Ưu điểm của phương pháp này là các ma trận có thể tính toán một cách đơn giản và hiệu quả. 2. CÁC KHÁI NIỆM CƠ SỞ Phần này nhắc lại một số khái niệm quan trọng trong lý thuyết cơ sở dữ liệu quan hệ nhằm mục đích sử dụng cho các phần tiếp theo.  Quan hệ. Một quan hệ r xác định trên tập thuộc tính  = {A1, A2,..., An} được định nghĩa như sau: r  {(a1, a2,..., an)  ai  Dom(Ai), i = 1, 2,..., n}, trong đó, Dom(Ai) là miền trị của thuộc tính Ai, i = 1, 2,..., n. Về mặt trực quan, ta có thể hình dung một quan hệ như 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. Ví dụ 1. Xét quan hệ SV (sinh viên) được cho ở Bảng 1; mỗi hàng trong bảng này cho thông tin về một sinh viên cụ thể. Tên bảng và tên các cột được dùng để giúp cho việc hiểu ý nghĩa của mỗi hàng. Thông thường, mọi giá trị trong một cột đều thuộc cùng một kiểu dữ liệu. Bảng 1. Quan hệ SV. Mã số Họ tên Mã khoa Ngày sinh Địa chỉ K40-01 Vũ Văn Hoàng TN 10/10/1980 Tứ Kỳ-HD K40-02 Trần Cường XH 23/06/1983 Nam Sách-HD K41-01 Lê Thị Thảo TN 25/11/1979 Tứ Kỳ-HD K41-02 Nguyễn Minh Tiến XH 17/07/1981 Bình Giang-HD T¹p chÝ Nghiªn cøu KH&CN Qu©n sù, Sè 34, 12 - 2014 73  Kü thuËt ®iÖn tö & Khoa häc m¸y tÝnh  Lược đồ quan hệ. Một lược đồ quan hệ S là một cặp có thứ tự S = , trong đó  là 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ộ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ể 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. Ví dụ 2. Xét quan hệ TKB (thời khoá biểu) dưới đây được sử dụng cho một cơ sở đào tạo; dữ liệu trong quan hệ TKB có thể thường xuyên thay đổi trong khi cấu trúc của nó vẫn ổn định; mặc dù dữ liệu trong quan hệ thay đổi nhưng luôn phải thỏa mãn các ràng buộc để đảm bảo tính đúng đắn của thời khóa biểu, chẳng hạn: mọi giáo viên đều không được phép dạy ở hơn một phòng tại cùng một thời điểm. Bảng 2. Quan hệ TKB. Ngày Tiết thứ Môn Phòng Giáo viên 10/05 1 Cơ sở dữ liệu 123 Vũ Tuấn 10/05 2 Cơ sở dữ liệu 123 Vũ Tuấn 11/05 3 Toán rời rạc 213 Phạm Hoa ... ... ... ... ... Cho lược đồ quan hệ S = 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 = . 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.  Phụ thuộc hàm. Cho  là tập thuộc tính và S() là một lược đồ quan hệ trên . Giả sử X, Y  . 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]. 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]. Ví dụ 3. Một cửa hàng cần quản lý dữ liệu về các loại hàng hóa mà họ bán ra. Thông tin về mỗi loại hàng bao gồm mã số (MaSo), tên hàng ( ...