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

Chia sẻ: Thi Thi | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

52
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ả.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 (TenHang) và giá bán (GiaBan). Giả sử mỗi loại hàng có một mã số duy nhất và một tên duy nhất. Khi đó, {MaSo}{TenHang}, {TenHang}{GiaBan}, {MaSo}{GiaBan} và dễ nhận thấy rằng {MaSo}{TenHang, GiaBan}.  Hệ quy tắc suy diễn Armstrong. Với lược đồ quan hệ S = 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. (Phản xạ): Nếu Y  X thì X  Y. Q2. (Gia tăng): Nếu X  Y thì XZ  YZ. Q3. (Bắc cầu): Nếu X  Y và Y  Z thì X  Z. Từ hệ quy tắc suy diễn Armstrong, ta có các quy tắc suy diễn bổ sung dưới đây: Quy tắc hợp: Nếu X  Y và X  Z thì X  YZ. Quy tắc tách: Nếu X  Y và Z  Y thì X  Z. Quy tắc giả bắc cầu: Nếu X  Y và WY  Z thì WX  Z. 74 V. Q. TuÊn, V. C. Thuý, "Ph¬ng ph¸p ma trËn … trong c¬ së d÷ liÖu.” Nghiªn cøu khoa häc c«ng nghÖ Ví dụ 4. Trở lại ví dụ 3. Từ {MaSo}{TenHang} và {TenHang}{GiaBan} ta có {MaSo}{GiaBan} theo quy tắc bắc cầu. Từ {MaSo}{TenHang} và {MaSo}{GiaBan} ta có {MaSo}{TenHang, GiaBan} theo quy tắc hợp.  Quan hệ tương đương. Cho r là một quan hệ trên lược đồ quan hệ S() và X  . Quan hệ r là một tập các bộ, mỗi bộ là một hàng (một dòng) trong r. Xét quan hệ X trên r được định nghĩa như sau: t X u khi và chỉ khi t[X] = u[X] với mọi t, u  r. Dễ dàng thấy rằng X là một quan hệ tương đương. Ví dụ 5. Trở lại ví dụ 1, xét quan hệ SV trong bảng 1. Ta thấy hai bộ ứng với mã số K40-01 và K41-01 tương đương với nhau trên tập thuộc tính X = {Mã khoa, Địa chỉ}. Hai bộ còn lại tương đương trên tập {Mã khoa}. 3. MA TRẬN TƯƠNG ĐƯƠNG 3.1. Phân hoạch Cho r là một quan hệ trên lược đồ quan hệ S(). Với mỗi tập thuộc tính X  , ta xây dựng một quan hệ tương đương X như ở trên; quan hệ X này sẽ phân hoạch tập các bộ của r thành các lớp tương đương. Ký hiệu lớp tương đương của một bộ t  r khi phân hoạch theo X là [t]X, nghĩa là [t]X = {u  r: t[X] = u[X]}. Tập X = {[t]X : t  r} gồm các lớp tương đương được gọi là phân hoạch của r trên X. Ví dụ 6. Phân hoạch quan hệ SV trong bảng 1 theo tập thuộc tính {Mã khoa} ta sẽ được hai lớp tương đương: lớp thứ nhất gồm hai bộ ứng với các mã số K40-01 và K41-01, lớp thứ hai gồm hai bộ còn lại. 3.2. Ma trận tương đương Cho r là một quan hệ trên lược đồ quan hệ S(). Giả sử r  t1 , t2 ,..., tm  . Mỗi quan hệ tương đương X trên r có thể được biểu diễn dưới dạng một ma trận vuông như dưới đây với aij  1 nếu ti X tj và aij  0 nếu ngược lại. X t1 t2 ... tj ... tm t1 a11 a12 ... a1j ... a1m t2 a21 a22 ... a2j ... a2m ... ... ... ... ... ... ... ti ai1 ai2 ... aij ... aim ... ... ... ... ... .. ... tm am1 am2 ... amj ... amm Các ma trận được cảm sinh từ các quan hệ tương đương X trên r được gọi là ma trận tương đương trên r. Ví dụ 7. Quan hệ tương đương "=" trên r  t1 , t2 ,..., tm  ứng với phân hoạch   : t1 ,t2  ,...,tm  có ma trận tương đương là ma trận đơn vị cấp m. = t1 t2 ... ti ... tm t1 1 0 ... 0 ... 0 t2 0 1 ... 0 ... 0 ... ... ... ... ... ... ... ti 0 0 ... 1 ... 0 T¹p chÝ Nghiªn cøu KH&CN Qu©n sù, Sè 34, 12 - 2014 75 Kü thuËt ®iÖn tö & Khoa häc m¸y tÝnh ... ... ... ... ... .. ... tm 0 0 ... 0 ... 1 Ví dụ 8. Quan hệ tương đương : t i  t j với mọi i, j  1, 2,..., m trên r  t1 , t2 ,..., tm  có ma trận tương đương là ma trận vuông cấp m với tất cả các phần tử đều bằng 1.  t1 t2 ... ti ... tm t1 1 1 ... 1 ... 1 t2 1 1 ... 1 ... 1 ... ... ... ... ... ... ... ti 1 1 ... 1 ... 1 ... ... ... ... ... .. ... tm 1 1 ... 1 ... 1  Định nghĩa 1. Cho trước M 1  tij  và M 2  t 'ij  là hai ma trận tương đương cấp m. Khi đó, giao của M1 và M 2 là một ma trận, kí hiệu là M 1  M 2   sij  , với sij  min(tij,t 'ij ) . Để nhận được ma trận M1  M 2 , ta cần tính m 2 giá trị sij ; do đó độ phức tạp thời gian khi tính M1  M 2 từ M1 và M 2 là O(m2 ) . Ví dụ 9. Với r  t1 , t2 , t3 , t4 , t5 , t6  . Phân hoạch 1 : t1 , t6  ,t2 , t3  ,t4 , t5  có ma trận M 1 và phân hoạch  2 : t1 , t3 , t4 , t5 , t6  ,t2  có ma trận M 2 . 1 0 0 0 0 1 1 0 1 1 1 1 0 1 1 0 0 0  0 1 0 0 0 0    0 1 1 0 0 0 1 0 1 1 1 1 M1    , M2   , 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 1 0  1 0 1 1 1 1     1 0 0 0 0 1  1 0 1 1 1 1  1 0 0 0 0 1 0 1 0 0 0 0   0 0 1 0 0 0 Giao của M 1 và M 2 là ma trận M 3  M1  M 2   . 0 0 0 1 1 0 0 0 0 1 1 0   1 0 0 0 0 1   Định nghĩa 2. Cho trước M 1  tij  và M 2   t 'ij  là hai ma trận tương đương cấp m. Ta nói M1  M 2 nếu tij  t 'ij với mọi i, j  1, 2,..., m . Như vậy, để kiểm tra M1  M 2 ta cần thực hiện m 2 phép so sánh tij  t 'ij ; do đó độ phức tạp thời gian để so sánh hai ma trận M1 , M 2 cũng chỉ là O(m2 ) . Ví dụ 10. Với các ma trận M 1 , M 2 , M 3 trong ví dụ 9, dễ thấy rằng M 3  M 1 và M3  M2 . 76 V. Q. TuÊn, V. C. Thuý, "Ph¬ng ph¸p ma trËn … trong c¬ së d÷ liÖu.” Nghiªn cøu khoa häc c«ng nghÖ 3.3. Ma trận thuộc tính Cho r  T  t1 , t2 ,..., tm  là một quan hệ trên tập thuộc tính  = {A1, A2,..., An}, kí hiệu là r ( T, ) . Với mỗi thuộc tính A , ta xây dựng một quan hệ tương đương  A trên T như sau: t  A u nếu và chỉ nếu t[A] = u[A] với mọi t, u  T ; nghĩa là các bộ t, u có cùng giá trị trên thuộc tính A. Gọi M A là ma trận tương đương của quan hệ  A .  Định nghĩa 3. Ma trận M A của quan hệ tương đương  A được xây dựng như ở trên được gọi là ma trận của thuộc tính A (hay của tập thuộc tính {A}). Ví dụ 11. Xét một quan hệ r ( T, ) được cho trong bảng 3 với  = {A1, A2,..., A6} và r  T  t1 , t2 ,..., t5  : Bảng 3. Quan hệ r ( T, ) A1 A2 A3 A4 A5 A6 t1 4 1 K X 8.36 M t2 3 2 J Y 5.14 F t3 4 1 L X 8.38 M t4 3 1 K X 8.29 F t5 4 2 J Y 5.27 M Với mỗi thuộc tính A ta có các ma trận sau: 1 0 1 0 1  1 0 1 1 0 0 1 0 1 0  0 1 0 0 1     M A1  M A6  1 0 1 0 1  , M A2  M A4  1 0 1 1 0 ,     0 1 0 1 0  1 0 1 1 0 1 0 1 0 1  0 1 0 0 1  1 0 0 1 0  1 0 00 0 0 1 0 0 1  0 1 00  0    M A3  0 0 1 0 0  , M A5  0 0 10 0     1 0 0 1 0  0 0 00 1 0 1 0 0 1  0 0 01  0  Định nghĩa 4. Cho trước quan hệ r( T, ) và một tập con X   . Ma trận tương đương của X được định nghĩa là M X   aij  với aij  1 nếu và chỉ nếu ti[X] = tj[X]. Dễ thấy rằng M X   AX M A . Ví dụ 12. Xét lại quan hệ r ( T, ) trong bảng 3. Với X   A1 , A4  ta có ma trận M X như sau: 1 0 1 0 0 0 1 0 0 0   M X  M A1  M A4  1 0 1 0 0   0 1 0 1 0 0 0 0 0 1  T¹p chÝ Nghiªn cøu KH&CN Qu©n sù, Sè 34, 12 - 2014 77 Kü thuËt ®iÖn tö & Khoa häc m¸y tÝnh 3.4. Một số tính chất của ma trận thuộc tính Từ định nghĩa về ma trận của tập thuộc tính (định nghĩa 4) và hệ quy tắc suy diễn Armstrong, ta dễ dàng suy ra được các tính chất sau:  Định lý 1. [1] Cho quan hệ r ( T, ) . Khi đó, với mọi X , Y   ta có M X  M Y  M X Y . Chứng minh. Do phép  có tính chất giao hoán và kết hợp nên: ( AX M A )  ( AY M A )   AX Y M A .   Định lý 2. [1] Cho quan hệ r ( T, ) . Khi đó, với mọi X , Y   ta có M X Y  M XY  M X , M Y . Chứng minh. Giả sử x, y {0,1} . Theo định nghĩa thì x  y  min( x, y) nên x  y  x, y .   Định lý 3. [1] Cho quan hệ r ( T, ) . Khi đó, với mọi X , Y   , nếu X  Y thì M X  MY . Chứng minh. Đặt Z  X \ Y . Ta có M X  M YZ  M Y theo định lý 2.   Định lý 4. [1] Cho quan hệ r (T, ) . Với X , Y   , nếu M X  M Y thì M X  Z  M Y  Z với mọi Z   . Chứng minh. Vì M X  M Y nên M X  M Y  M X . Do đó, ( M X  M Z )  ( M Y  M Z )  ( M X  M Y )  ( M Z  M Z )  M X  M Z ; Vậy ( M X  M Z )  ( M Y  M Z ) hay M X  Z  M Y  Z .  Định lý 5. Cho quan hệ r ( T, ) . Khi đó, với mọi X , Y , Z   , nếu M X  M Y và M X  M Z thì M X  M YZ . Chứng minh.Giả sử M X   xij  , M Y   yij  và M Z   zij  . Từ M X  M Y và M X  M Z ta có xij  yij , xij  zij . Suy ra xij  min( yij , zij )  yij  zij .  5. Phụ thuộc hàm  Định lý 5. [1] Phụ thuộc hàm X  Y đúng trên r ( T, ) khi và chỉ khi M X  M Y , nghĩa là  AX M A   AY M A . Chứng minh. Giả sử r  t1 , t2 ,..., tm  , M X   xij  và M Y   yij  . + Nếu X  Y thì M X  M Y . Thật vậy, vì X  Y nên theo định nghĩa phụ thuộc hàm ta có:  ti , t j  r nếu ti [ X ]  t j [ X ] thì ti [Y ]  t j [Y ] ; kết hợp với định nghĩa 4, suy ra: nếu xij  1 thì yij  1 . Mặt khác, M X , M Y là các ma trận nhị phân nên M X  M Y . + Nếu M X  M Y thì X  Y . Ta cần chỉ ra  ti , t j  r , nếu ti [ X ]  t j [ X ] thì ti [Y ]  t j [Y ] . Thật vậy, vì ti [ X ]  t j [ X ] nên theo định nghĩa 4, ta có xij  1 ; mặt khác do M X  M Y nên xij  yij , suy ra yij  1 ; cũng theo định nghĩa 4, từ yij  1 ta có ti [Y ]  t j [Y ] .  Như vậy, để kiểm tra X  Y ta chỉ cần kiểm tra M X  M Y ; độ phức tạp thời gian là O( m 2 ) .  Hệ quả. Nếu M X  M  thì X là siêu khoá, nghĩa là X   đúng trên r ( T, ) . 4. PHÁT HIỆN PHỤ THUỘC HÀM  Thuật toán 1. Thuật toán tìm ma trận M A  tij  . 78 V. Q. TuÊn, V. C. Thuý, "Ph¬ng ph¸p ma trËn … trong c¬ së d÷ liÖu.” Nghiªn cøu khoa häc c«ng nghÖ INPUT: Quan hệ r ( T, )  t1 , t2 ,..., tm  và A  . OUTPUT: Ma trận tương đương M A . for i: = 1 to m do for j: = 1 to m do if ti [ A]  t j [ A] then tij  1 else tij  0 ; Nhận xét 1. Thuật toán 1 có độ phức tạp thời gian là O(m 2 ) .  Thuật toán 2. Thuật toán tính ma trận M  M1  M 2 . INPUT: Hai ma trận (vuông, nhị phân, cấp m) M1 , M 2 . OUTPUT: M  M1  M 2 . + Quy tắc tính: 0  0  0 , 0  1  1  0  0 , 1  1  1 . + Giả sử M  tij  , M 1  t 'ij  , M 2   t ''ij  , ta có: for i: = 1 to m do for j: = 1 to m do if t 'ij  t ''ij then tij  t 'ij else tij  t ''ij ; Nhận xét 2. Thuật toán 2 có độ phức tạp thời gian là O(m 2 ) .  Thuật toán 3. Thuật toán kiểm tra phụ thuộc hàm X  Y . INPUT: Quan hệ r ( T, )  t1 , t2 ,..., tm  và X , Y   . OUTPUT: TRUE nếu X  Y đúng trên r ( T, ) hoặc FALSE nếu ngược lại. Bước 1. Tính M X = ?  + Giả sử X  x1 , x2 ,..., x X .  + Tính M x1 theo Thuật toán 1; M X : M x1 ; + for i := 2 to X do begin + Tính M xi ; + M X : M X  M xi ; end; Bước 2. Tính M Y = ?  + Giả sử Y  y1 , y2 ,..., y Y .  + Tính M y1 theo Thuật toán 1; M Y : M y1 ; + for i := 2 to Y do begin + Tính M yi ; + M Y : M Y  M yi ; end; Bước 3. So sánh M X và M Y ? + Giả sử M X   xij  và M Y   yij  . T¹p chÝ Nghiªn cøu KH&CN Qu©n sù, Sè 34, 12 - 2014 79 Kü thuËt ®iÖn tö & Khoa häc m¸y tÝnh + TEST := TRUE; + for i := 1 to m do for j := 1 to m do if xij  yij then begin TEST := FALSE; break; end; + return TEST; Nhận xét 3. Thuật toán 3 có độ phức tạp thời gian là O(m2 ) . 5. KẾT LUẬN Bài báo đã nghiên cứu về ma trận thuộc tính và phương pháp ma trận để kiểm tra một phụ thuộc hàm có được thoả mãn hay không đối với một quan hệ cho trước. Phương pháp ma trận tỏ ra đơn giản và hiệu quả vì độ phức tạp thời gian tính toán của phương pháp này chỉ là đa thức. Trong các bài báo tiếp theo, chúng tôi sẽ nghiên cứu tiếp các tính chất quan trọng của ma trận tương đương, phương pháp ma trận để phát hiện khoá của quan hệ, đồng thời mở rộng phương pháp ma trận để phát hiện phụ thuộc hàm xấp xỉ. TÀI LIỆU THAM KHẢO [1]. J.W. Guan, D.A. Bell and Z. Guan, “Matrix computation for information systems”, Information Sciences 131 (2001), pp. 129 -156. [2]. D. Maier, “The theory of relational databases”, Computer Science Press, (1983). [3]. Hong Yao, Howard J. Hamilton, Cory J. Butz, “FD_Mine: Discovering Functional Dependencies in a Database Using Equivalences”, Second IEEE International Conference on Data Mining, (2002). [4]. Laurentiu B. Cristofor, “A rough set based generalization of functional dependencies”, Department of Math and Computer Science, UMass/Boston, May 8, (2000). [5]. Nguyễn Đăng Khoa, Vũ Huy Hoàng, “Phụ thuộc hàm suy rộng trên cơ sở lý thuyết tập thô”, Tạp chí Tin học và Điều khiển học, T.20, S.1, (2004). [6]. Y. Huhtala and et al, “Efficient discovery of functional and approximate dependencies using partitions”, (1998). ABSTRACT MATRIX METHOD FOR DISCOVERING FUNCTIONAL DEPENDENCIES IN A DATABASE Discovering functional dependencies from a database is an important technique in data mining. In this paper, we present an algorithm for finding functional dependencies using equivalence matrices. The advantage of this algorithm is that matrices can be computed simply and efficiently. Keywords: Data mining, Database, Relation, Relation scheme, Functional dependency, Equivalence matrix. Nhận bài ngày 28 tháng 07 năm 2014 Hoàn thiện ngày 09 tháng 10 năm 2014 Chấp nhận đăng ngày 05 tháng 12 năm 2014 Địa chỉ: * Khoa Tự nhiên - Trường Cao đẳng Hải Dương. ** Trung tâm Dịch vụ Giá trị Gia tăng, Công ty Thông tin di động VMS-MobiFone. 80 V. Q. TuÊn, V. C. Thuý, "Ph¬ng ph¸p ma trËn … trong c¬ së d÷ liÖu.”