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 - Vũ Quốc Tuấn: Nghiên cứu khoa học công nghệ
Tạp chí Nghiên cứu KH&CN Quân sự, Số 34, 12 - 2014 73
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ú...
8 trang |
Chia sẻ: quangot475 | Lượt xem: 585 | Lượt tải: 0
Bạn đang xem nội dung 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 - Vũ Quốc Tuấn, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Nghiªn cøu khoa häc c«ng nghÖ
T¹p chÝ Nghiªn cøu KH&CN Qu©n sù, Sè 34, 12 - 2014 73
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
Kü thuËt ®iÖn tö & Khoa häc m¸y tÝnh
V. Q. TuÊn, V. C. Thuý, "Ph¬ng ph¸p ma trËn trong c¬ së d÷ liÖu.” 74
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.
Nghiªn cøu khoa häc c«ng nghÖ
T¹p chÝ Nghiªn cøu KH&CN Qu©n sù, Sè 34, 12 - 2014 75
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ử 1 2, ,..., mr t t t . 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 1ija
nếu ti X tj và 0ija 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 1 2, ,..., mr t t t ứng với phân hoạch
1 2: , ,..., mt t t 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
Kü thuËt ®iÖn tö & Khoa häc m¸y tÝnh
V. Q. TuÊn, V. C. Thuý, "Ph¬ng ph¸p ma trËn trong c¬ së d÷ liÖu.” 76
... ... ... ... ... .. ...
tm 0 0 ... 0 ... 1
Ví dụ 8. Quan hệ tương đương : i jt t với mọi , 1,2,...,i j m trên 1 2, ,..., mr t t t 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 1 ij M t và 2 ij' M t là hai ma trận tương đương cấp m.
Khi đó, giao của 1M và 2M là một ma trận, kí hiệu là 1 2 ij M M s ,
với ij ij, ijmin( ' )s t t . Để nhận được ma trận 1 2M M , ta cần tính
2m giá trị ijs ; do đó độ
phức tạp thời gian khi tính 1 2M M từ 1M và 2M là
2( )O m .
Ví dụ 9. Với 1 2 3 4 5 6, , , , ,r t t t t t t . Phân hoạch 1 1 6 2 3 4 5: , , , , , t t t t t t có ma trận 1M
và phân hoạch 2 1 3 4 5 6 2: , , , , , t t t t t t có ma trận 2M .
1
1 0 0 0 0 1
0 1 1 0 0 0
0 1 1 0 0 0
0 0 0 1 1 0
0 0 0 1 1 0
1 0 0 0 0 1
M , 2
1 0 1 1 1 1
0 1 0 0 0 0
1 0 1 1 1 1
1 0 1 1 1 1
1 0 1 1 1 1
1 0 1 1 1 1
M ,
Giao của 1M và 2M là ma trận 3 1 2
1 0 0 0 0 1
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 1 0
0 0 0 1 1 0
1 0 0 0 0 1
M M M .
Định nghĩa 2. Cho trước 1 ij M t và 2 ij' M t là hai ma trận tương đương cấp m. Ta
nói 1 2M M nếu 'ij ijt t với mọi , 1,2,...,i j m .
Như vậy, để kiểm tra 1 2M M ta cần thực hiện
2m phép so sánh 'ij ijt t ; do đó độ
phức tạp thời gian để so sánh hai ma trận 1 2,M M cũng chỉ là
2( )O m .
Ví dụ 10. Với các ma trận 1 2 3, ,M M M trong ví dụ 9, dễ thấy rằng 3 1M M và
3 2M M .
Nghiªn cøu khoa häc c«ng nghÖ
T¹p chÝ Nghiªn cøu KH&CN Qu©n sù, Sè 34, 12 - 2014 77
3.3. Ma trận thuộc tính
Cho 1 2, ,..., mr T t t t 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: At 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 AM là ma trận tương đương của quan hệ A .
Định nghĩa 3. Ma trận AM 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à
1 2 5, ,...,r T t t t :
Bảng 3. Quan hệ ( , )r T
1A 2A 3A 4A 5A 6A
1t 4 1 K X 8.36 M
2t 3 2 J Y 5.14 F
3t 4 1 L X 8.38 M
4t 3 1 K X 8.29 F
5t 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 6
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
A AM M , 2 4
1 0 1 1 0
0 1 0 0 1
1 0 1 1 0
1 0 1 1 0
0 1 0 0 1
A AM M ,
3
1 0 0 1 0
0 1 0 0 1
0 0 1 0 0
1 0 0 1 0
0 1 0 0 1
AM , 5
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
AM
Đị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à ij XM a với ij 1a nếu và chỉ nếu ti[X] = tj[X]. Dễ thấy rằng
X A X AM M .
Ví dụ 12. Xét lại quan hệ ( , )r T trong bảng 3. Với 1 4,X A A ta có ma trận XM như
sau:
1 4
1 0 1 0 0
0 1 0 0 0
1 0 1 0 0
0 1 0 1 0
0 0 0 0 1
X A AM M M
Kü thuËt ®iÖn tö & Khoa häc m¸y tÝnh
V. Q. TuÊn, V. C. Thuý, "Ph¬ng ph¸p ma trËn trong c¬ së d÷ liÖu.” 78
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ó X Y X YM M M .
Chứng minh. Do phép có tính chất giao hoán và kết hợp nên:
( ) ( ) A X A A Y A A X Y AM M M .
Định lý 2. [1] Cho quan hệ ( , )r T . Khi đó, với mọi , X Y ta có
, X Y XY X YM M M M .
Chứng minh. Giả sử , {0,1}x y . Theo định nghĩa thì min( , )x y 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ì
X YM M .
Chứng minh. Đặt \Z X Y . Ta có X YZ YM M M theo định lý 2.
Định lý 4. [1] Cho quan hệ ( , )r T . Với , X Y , nếu X YM M thì X Z Y ZM M
với mọi Z .
Chứng minh. Vì X YM M nên X Y XM M M .
Do đó, ( ) ( ) ( ) ( ) X Z Y Z X Y Z Z X ZM M M M M M M M M M ;
Vậy ( ) ( ) X Z Y ZM M M M hay X Z Y ZM M .
Định lý 5. Cho quan hệ ( , )r T . Khi đó, với mọi , , X Y Z , nếu X YM M và
X ZM M thì X YZM M .
Chứng minh.Giả sử ij XM x , ij YM y và ij ZM z . Từ X YM M và X ZM M
ta có ij ijx y , ij ijx z . Suy ra min( , )ij ij ij ij ijx y z y z .
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 X YM M , nghĩa
là A X A A Y AM M .
Chứng minh. Giả sử 1 2, ,..., mr t t t , ij XM x và ij YM y .
+ Nếu X Y thì X YM M . Thật vậy, vì X Y nên theo định nghĩa phụ thuộc hàm
ta có: ,i jt t r nếu [ ] [ ]i jt X t X thì [ ] [ ]i jt Y t Y ; kết hợp với định nghĩa 4, suy ra:
nếu 1ijx thì 1ijy . Mặt khác, ,X YM M là các ma trận nhị phân nên X YM M .
+ Nếu X YM M thì X Y . Ta cần chỉ ra ,i jt t r , nếu [ ] [ ]i jt X t X thì
[ ] [ ]i jt Y t Y . Thật vậy, vì [ ] [ ]i jt X t X nên theo định nghĩa 4, ta có 1ijx ; mặt khác
do X YM M nên ij ijx y , suy ra 1ijy ; cũng theo định nghĩa 4, từ 1ijy ta có
[ ] [ ]i jt Y t Y .
Như vậy, để kiểm tra X Y ta chỉ cần kiểm tra X YM M ; độ phức tạp thời gian là
2( )O m .
Hệ quả. Nếu XM 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 ij AM t .
Nghiªn cøu khoa häc c«ng nghÖ
T¹p chÝ Nghiªn cøu KH&CN Qu©n sù, Sè 34, 12 - 2014 79
INPUT: Quan hệ ( , )r T 1 2, ,..., mt t t và A .
OUTPUT: Ma trận tương đương AM .
for i: = 1 to m do
for j: = 1 to m do
if [ ] [ ]i jt A t A then ij 1t else ij 0t ;
Nhận xét 1. Thuật toán 1 có độ phức tạp thời gian là 2( )O m .
Thuật toán 2. Thuật toán tính ma trận 1 2 M M M .
INPUT: Hai ma trận (vuông, nhị phân, cấp m) 1 2,M M .
OUTPUT: 1 2 M M M .
+ Quy tắc tính: 0 0 0 , 0 1 1 0 0 , 1 1 1 .
+ Giả sử ij 1 ij 2 ij, ' , '' M t M t M t , ta có:
for i: = 1 to m do
for j: = 1 to m do
if ij ij' ''t t then ij ij't t else ij ij''t t ;
Nhận xét 2. Thuật toán 2 có độ phức tạp thời gian là 2( )O m .
Thuật toán 3. Thuật toán kiểm tra phụ thuộc hàm X Y .
INPUT: Quan hệ ( , )r T 1 2, ,..., mt t t 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 XM = ?
+ Giả sử 1 2, ,..., XX x x x .
+ Tính
1x
M theo Thuật toán 1;
1
:X xM M ;
+ for i := 2 to X do
begin
+ Tính xiM ;
+ : X X xiM M M ;
end;
Bước 2. Tính YM = ?
+ Giả sử 1 2, ,..., YY y y y .
+ Tính
1y
M theo Thuật toán 1;
1
:Y yM M ;
+ for i := 2 to Y do
begin
+ Tính yiM ;
+ : Y Y yiM M M ;
end;
Bước 3. So sánh XM và YM ?
+ Giả sử ij XM x và ij YM y .
Kü thuËt ®iÖn tö & Khoa häc m¸y tÝnh
V. Q. TuÊn, V. C. Thuý, "Ph¬ng ph¸p ma trËn trong c¬ së d÷ liÖu.” 80
+ TEST := TRUE;
+ for i := 1 to m do
for j := 1 to m do
if ij ijx y 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à 2( )O m .
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.
Các file đính kèm theo tài liệu này:
- 10_vu_quoc_tuan_73_80_2864_2149219.pdf