BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC
VÀ CÔNG NGHỆ VIỆT NAM
VIỆN CÔNG NGHỆ THÔNG TIN
BÙI ĐỨC MINH
NGHIÊN CỨU HỆ SINH ÁNH XẠ ĐÓNG
VÀ ỨNG DỤNG TRONG THỂ HIỆN
NGỮ NGHĨA DỮ LIỆU
LUẬN ÁN TIẾN SĨ TOÁN HỌC
2. TS. HOÀNG QUANG
HÀ NỘI - 2014
1 LỜI CAM ĐOAN
Tôi cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả
trong luận án là trung thực và chưa từng công bố trong bất kỳ công trình nào khác.
Tác giả luận án
Bùi Đức Minh
2
LỜI CÁM ƠN Luận án được thực hiện và hoàn thành tại Viện Công nghệ Thông tin, Viện
Khoa học và Công nghệ Việt Nam, dưới sự hướng dẫn khoa học của PGS TSKH
PHẦN MỞ ĐẦU 9
CHƯƠNG 1 MỘT SỐ KHÁI NIỆM CƠ BẢN VỀ CƠ SỞ DỮ LIỆU QUAN
HỆ VÀ KHAI PHÁ DỮ LIỆU 18
1.1. Khái niệm về cơ sở dữ liệu quan hệ 19
1.2. Phụ thuộc hàm 19
1.2.1. Khái niệm phụ thuộc hàm 20
1.2.2. Lược đồ quan hệ 21
1.2.3. Bao đóng tập phụ thuộc hàm 21
1.2.4. Định lý tương đương 22
1.2.5. Bao đóng tập thuộc tính 23
1.2.6. Bài toán thành viên 24
1.3. Khóa và phản khóa của lược đồ quan hệ 24
1.3.1. Khóa của lược đồ quan hệ 25
1.3.2. Phản khóa của lược đồ quan hệ 26
1.4. Một số khái niệm trong khai phá dữ liệu 27
1.4.1. Một số khái niệm cơ bản 27
1.4.2. Luật kết hợp và kết nối Galois 29
1.5. Kết luận chương 1 30
CHƯƠNG 2 ÁNH XẠ ĐÓNG&LÝ THUYẾT GIÀN GIAO VÀ ỨNG DỤNG31
2.1. Ánh xạ đóng 33
2.1.1. Các khái niệm và tính chất ánh xạ đóng 33
2.1.2. Phép hạn chế trên ánh xạ đóng 35
2.1.3. Điểm bất động(tập đóng) trên ánh xạ đóng 35
2.2. Các phép toán trên ánh xạ đóng 36
4
2.2.1. Phép toán hội 36
2.2.2. Phép toán hợp thành 36
2.2.3. Ứng dụng phép toán hợp thành 41
3.4.2. Phản cơ sở hệ sinh AXĐ 83
3.4.3. Một dạng biểu diễn phản cơ sở hệ sinh AXĐ 84
3.4.4. Sự tương quan giữa các đối tượng trong hệ sinh AXĐ 87
5
3.5. Ứng dụng hệ sinh AXĐ giải bài toán hệ suy dẫn 90
3.5.1. Các khái niệm và quy tắc suy dẫn 90
3.5.2. Một số dạng bài toán suy dẫn 90
3.6. Hệ sinh cân bằng 94
3.6.1. Các khái niệm và một số tính chất 94
3.6.2. Thuật toán thu gọn hệ sinh AXĐ về dạng cân bằng 97
3.7. Ứng dụng hệ sinh AXĐ trong cơ sở dữ liệu 100
3.7.1. Bài toán phân rã và kết nối các quan hệ 100
3.7.2. Một dạng biểu diễn phản khóa của lược đồ quan hệ 103
3.8. Kết luận chương 3 105
PHẦN KẾT LUẬN 106
DANH MỤC CÔNG TRÌNH ĐÃ CÔNG BỐ 109
TÀI LIỆU THAM KHẢO 110
6
DANH MỤC CÁC HÌNH
Hình 2.1. Đồ thị của giàn các tập mục phổ biến 53
Hình 2.2. Giàn giao đầy đủ của Poset(ABE) 54
Hình 2.3. Giàn các tập phổ biến sau khi xóa tập mục nhạy cảm 59
PTBDĐT: Phụ thuộc Boole dương đa trị
PTBDTNB: Phụ thuộc Boole dương theo nhóm bộ
PTH: Phụ thuộc hàm
9
PHẦN MỞ ĐẦU
1. Đặt vấn đề
Trong nghiên cứu và mô tả thế giới thực, cùng với việc phản ánh ngữ nghĩa dữ
liệu của cơ sở dữ liệu (CSDL) thì lý thuyết về phụ thuộc dữ liệu đóng một vai trò rất
cơ bản. Phụ thuộc dữ liệu trong thiết kế và quản trị một cơ sở dữ liệu được hiểu là
sự mô tả các ràng buộc mà dữ liệu phải thỏa mãn trong bài toán thực tế. Đây cũng là
yếu tố quyết định đến chất lượng dữ liệu trong quá trình xử lý và quản trị một hệ
thống. Phụ thuộc dữ liệu được Codd [16], người đặt những nền móng ban đầu cho
mô hình dữ liệu quan hệ từ những năm 70 với phụ thuộc logic đầu tiên là phụ thuộc
hàm (PTH). Đây là loại phụ thuộc thiết lập mối quan hệ về mặt ngữ nghĩa giữa các
tập thuộc tính trong cơ sở dữ liệu. Định lý tương đương khẳng định sự tương đương
giữa các loại suy dẫn bao gồm suy dẫn logic, suy dẫn theo quan hệ và suy dẫn theo
quan hệ có không quá p bộ là định lý rất cơ bản trong lý thuyết về phụ thuộc logic
này. Sau đó, trong các công trình được công bố tiếp theo [10], [11], [12], các tác giả
khác đã tiếp tục phát triển và xây dựng các hệ tiên đề với các dạng phụ thuộc bậc
cao góp phần đặt những nền tảng đầu tiên về cơ sở lý thuyết cho phụ thuộc dữ liệu.
Cụ thể, vào những năm 80, các nhóm nghiên cứu của Berman, Blok và Sagiv,
Delobel [13], [14], [46] đã mở rộng khái niệm PTH sang khái niệm phụ thuộc Boole
dương (PTBD), các ràng buộc dữ liệu được mô tả thông qua các công thức Boole
dương với phép sánh đẳng thức. Công thức Bool dương là những công thức có trị là
1 khi giá trị của các biến thành phần là 1. Định lý tương đương vẫn đúng đối với
phụ thuộc logic này. Cũng trong thời gian này, nhóm nghiên cứu Viện Hàn lâm
Khoa học Hungary, trong [22] công bố vào năm 1988 đã phát biểu về mối tương
của luận án, khái niệm ánh xạ đóng được vận dụng theo tiếp cận của toán học rời
rạc, cụ thể là ánh xạ đóng được thiết lập trên tập hữu hạn U thỏa các tính chất phản
xạ, đồng biến và lũy đẳng. Khái niệm này đã được các nhóm nghiên cứu trong [15],
[25] sử dụng như một công cụ toán học để trợ giúp việc mô tả các khía cạnh về mặt
11
lý thuyết cũng như ứng dụng trong một số lĩnh vực thuộc công nghệ thông tin như
cơ sở dữ liệu, các hệ suy dẫn, khai phá dữ liệu, ….
Trong lý thuyết cơ sở dữ liệu quan hệ, có thể tìm thấy rất nhiều các ánh xạ
đóng như phép tính bao đóng tập thuộc tính, phép tính bao đóng tập phụ thuộc hàm,
phép kết nối trong đại số quan hệ, …. Kết nối Galois [40] được sử dụng rất phổ
biến khi xác định tập phổ biến trong khai phá dữ liệu cũng là một ánh xạ đóng. Việc
biểu diễn, tính toán các đối tượng theo ngôn ngữ ánh xạ đóng nhằm nâng cao hiệu
quả tính toán đã được nhiều tác giả công bố trong nhiều công trình [5], [6], [15].
Bên cạnh đó, từ đầu những năm 2000, các nhóm nghiên cứu gồm nhiều đơn vị
tham gia như Viện Công nghệ Thông tin, Trường Đại học Khoa học Tự nhiên thuộc
Đại học Quốc gia Hà Nội, Trường Đại học Bách khoa Đà Nẵng và các tác giả
khác, trong các công trình [6], [7], [15] đã phát triển, vận dụng lý thuyết ánh xạ
đóng vào việc giải quyết một số bài toán và thu được một số kết quả khả quan bước
đầu như chứng minh sự tương đương giữa cấu trúc phụ thuộc hàm và ánh xạ đóng,
thiết lập sự tương quan giữa khóa của lược đồ quan hệ và cơ sở của ánh xạ đóng, …
Các kết quả nghiên cứu này cho thấy có thể vận dụng khái niệm ánh xạ đóng để tiếp
tục nghiên cứu các vấn đề thuộc về ngữ nghĩa dữ liệu.
Ngoài ra, lý thuyết giàn cũng được nhiều nhà khoa học, chẳng hạn như G.
Birkhoff công bố trong nhiều công trình và xuất bản thành sách [25] bắt đầu từ
những năm 1940. Cho đến cuối những năm 90 trở lại đây, trong các công trình [6],
[40], các tác giả đã vận dụng lý thuyết giàn giao để chứng minh một số bài toán
biểu diễn các đối tượng của một hệ suy dẫn cũng như ứng dụng lý thuyết giàn vào
lĩnh vực khai phá dữ liệu, cụ thể là khai thác tập phổ biến, tập phổ biến đóng, khai
quản lý vẫn khá lớn, khái niệm tập phổ biến tối đại được sử dụng để giải quyết vấn
đề này. Tập phổ biến tối đại là tập phổ biến thỏa tính chất không tồn tại tập phổ biến
là tập cha của tập này. Khái niệm tập phổ biến tối đại được trình bày trong [18] vào
năm 1997 và đến 2005 thì nhóm nghiên cứu của Zaki trong [34] cũng đề xuất một
thuật toán để khai thác một cách hiệu quả tập phổ biến tối đại. Phương pháp chính
mà nhóm của Zaki đề xuất trong thuật toán này là sử dụng chiến lược tìm kiếm quay
lui và sử dụng một số kỹ thuật tối ưu trong việc xén không gian tìm kiếm. Thuật
13
toán này đã cải thiện hiệu quả tính toán khá tốt. Từ năm 2007 đến nay, nhiều thuật
toán khai thác tập phổ biến liên tục được đề xuất và cải tiến trên các cơ sở dữ liệu
lớn được công bố, chẳng hạn như trong [33], [51] sử dụng các kỹ thuật như
BitTableFI, trong [37] sử dụng kỹ thuật khai thác song song, trong [30] sử dụng kỹ
thuật phân hoạch thứ cấp, … Bài toán khai thác tập phổ biến tối đại có sử dụng lại
các thuật toán trên nhằm mục tiêu cải tiến hiệu quả tính toán là vấn đề cần tiếp tục
nghiên cứu, bổ sung.
Song song đó, một vấn đề thường gặp khi cung cấp dữ liệu khai thác cho các
trung tâm khai thác dữ liệu, một số cơ sở không muốn công bố các luật vi phạm đến
tính riêng tư của cơ sở mình. Thí dụ, X là tập mục thể hiện các thông tin về các máy
bay xuất xưởng, Y là tập mục chứa các thông tin về các sự cố và tai nạn hàng không
của loại máy bay đó. Việc công bố mối tương quan giữa X và Y là điều bất lợi cho
hãng sản xuất. Các tập mục X, Y như thế được gọi là các tập mục nhạy cảm. Để ẩn
các tập mục nhạy cảm này và không vi phạm các nguyên tắc trao đổi dữ liệu, đã có
các thuật toán đề xuất của nhóm nghiên cứu của Xingzhi và cộng sự trong [50] vào
năm 2007, sau đó được cải tiến bởi nhóm nghiên cứu của George V. Moustakides
và các cộng sự trong [28] công bố vào năm 2008 với thuật toán MaxMin khảo sát
các tập mục nằm sát trên và sát dưới các tập mục nhạy cảm với chức năng xác định
các mục dữ liệu cần sửa nhằm giảm độ phổ biến của các tập mục nhạy cảm. Các
thuật toán trên đã góp phần giải quyết được yêu cầu đề ra của bài toán. Tuy nhiên,
phản cơ sở, … của hệ sinh sau khi thu gọn bằng một số các phép toán đơn giản. Từ
đó, các tác giả trong nhiều công trình [5], [6] đã phát biểu nhiều định lý, bổ đề với
mục tiêu biểu diễn và tính toán các đối tượng như cơ sở, phản cơ sở, … của một hệ
sinh trở nên đơn giản hơn và hiệu năng tính toán được cải thiện. Tuy nhiên, việc
chọn lựa các phần tử để loại bỏ trong hệ sinh, hay nói cách khác, việc chọn lựa một
tập con như thế nào để đạt hiệu quả khi thực hiện phép thu gọn là vấn đề cần tiếp
tục nghiên cứu.
Bên cạnh kỹ thuật thu gọn hệ sinh, trong thời gian gần đây, một hệ sinh đặc
biệt gọi là hệ sinh cân bằng được đề xuất trong [V], [VI] và được trình bày trong
luận án của tác giả Lương Nguyễn Hoàng Hoa [2]. Hệ sinh AXĐ α = (U, F) gọi là
cân bằng nếu α thỏa các tính chất: Hợp các vế trái, vế phải của các luật sinh trong F
đúng bằng tập U; F không chứa các luật sinh tầm thường, tức là các luật sinh có vế
trái chứa vế phải; Hai vế trái và phải của mọi luật sinh trong F rời nhau (không giao
15
nhau); Các vế trái của mọi luật sinh trong F khác nhau đôi một.
Các tác giả đã chỉ ra sau khi thu gọn một hệ sinh về hệ sinh cân bằng thi tập cơ
sở của hệ sinh ban đầu được dễ dàng xác định thông qua phép hợp tập cơ sở của hệ
sinh cân bằng sau khi thu gọn với tập U
I
(U
I
là giao các cơ sở của hệ sinh ban đầu).
Thuật toán xác định U
I
được thực hiện với độ phức tạp tính toán đa thức. Vấn đề
cần tiếp tục nghiên cứu là xây dựng một thuật toán để thu gọn một hệ sinh bất kỳ về
dạng hệ sinh cân bằng.
2. Mục đích của luận án
sở dữ liệu quan hệ, cụ thể như khái niệm về quan hệ, bộ, thuộc tính, LĐQH, khái
niệm phụ thuộc hàm, bao đóng của tập phụ thuộc hàm, bao đóng tập thuộc tính, bài
toán thành viên, khóa và phản khóa, …. Ngoài ra, trong chương cũng trình bày
thêm một số khái niệm cơ bản được sử dụng khi khai phá dữ liệu như khái niệm về
cơ sở dữ liệu giao tác, tập phổ biến, luật kết hợp, … , kết nối Galois và một số tính
chất cơ bản.
Chương 2. Ánh xạ đóng & Lý thuyết giàn giao và ứng dụng
Chương này giới thiệu một số khái niệm, tính chất của ánh xạ đóng và lý
thuyết giản giao. Kết quả mới trong chương gồm có phát biểu về một điều kiện đủ
để phép hợp thành các AXĐ là một AXĐ và điều kiện để một họ con các AXĐ
đóng với phép hợp thành. Ngoài ra, một số kết quả đạt được khi xây dựng các ứng
dụng của AXĐ, lý thuyết giàn giao trong các bài toán khai phá dữ liệu và lý thuyết
cơ sở dữ liệu cũng được trình bày ở đây.
Chương 3. Hệ sinh ánh xạ đóng và một số kết quả nghiên cứu
Trong chương chủ yếu trình bày các định nghĩa, tính chất quan trọng của hệ
sinh AXĐ và các định lý, bổ đề biểu diễn cơ sở, phản cơ sở của hệ sinh AXĐ thông
17
qua kỹ thuật thu gọn hệ sinh. Kết quả mới và chủ yếu trong chương này là đề xuất
một dạng biểu diễn phản cơ sở của hệ sinh theo vế phải tối đại của tập luật sinh
cùng với thuật toán thu gọn một hệ sinh bất kỳ về một hệ sinh đơn giản gọi là hệ
sinh cân bằng và định lý về tính đúng của thuật toán. Bên cạnh đó, trong chương
cũng trình bày một số kết quả nghiên cứu thu được khi xây dựng các dạng giản lược
của tập luật sinh, sự tương quan giữa các đối tượng trong hệ sinh AXĐ, ….
Các ký hiệu và quy ước sau cũng được sử dụng xuyên suốt trong các chương.
Các phần tử của tập hợp được ký hiệu bằng các ký tự đầu bảng chử cái A, B, C,…
Các tập được ký hiệu bằng các ký tự cuối bảng chữ cái X, Y, Z, Các phần tử trong
một tập được liệt kê như một xâu ký tự, không sử dụng các ký hiệu biểu diễn tập
hợp truyền thống, chẳng hạn ta viết X = ABC thay vì viết X = {A, B, C}, XY là biểu
phát biểu về sự tương đương giữa các loại suy dẫn theo tiên đề, suy dẫn theo quan
hệ và suy dẫn theo quan hệ có không quá p bộ. Một trong những khái niệm cơ bản
của phụ thuộc hàm là bao đóng của tập thuộc tính, các tính chất cơ bản của phép
toán lấy bao đóng cùng với thuật toán tìm bao đóng của tập thuộc tính cũng được
trình bày ở đây. Cuối cùng trong phần này là phát biểu bài toán thành viên về điều
kiện cần và đủ để một phụ thuộc hàm được suy dẫn từ một tập phụ thuộc hàm cho
trước. Các khái niệm cơ bản có liên quan đến phụ thuộc hàm như khóa, phản khóa
cùng với đặc trưng của các thuộc tính khóa, công thức tính giao các khóa và điều
kiện để một LĐQH có khóa duy nhất được trình bày trong phần thứ ba của chương.
Phần cuối cùng trong chương sẽ trình bày một số khái niệm cơ bản trong lĩnh vực
khai phá dữ liệu như khái niệm về cơ sở dữ liệu giao tác, khái niệm tập phổ biến,
khái niệm luật kết hợp và một vài tính chất quan trọng trong kết nối Galois.
19
1.1. Khái niệm về cơ sở dữ liệu quan hệ
Cơ sở dữ liệu quan hệ và các khái niệm cơ bản đã được trình bày đầu tiên
trong các công trình của Codd [16]. Trong [9], [10] đã trình bày khá đầy đủ các khái
niệm liên quan đến các hệ cơ sở dữ liệu và tri thức. Riêng về cơ sở dữ liệu quan hệ,
các tác giả trong các công trình [1], [6], [9], [10], [11], [23], [26], [28], [35], [49] đã
giới thiệu khá đầy đủ những khái niệm và các bài toán cơ bản liên quan đến các vấn
đề lý thuyết cũng như thực hành. Ở đây, chỉ trình bày tóm tắt lại các khái niệm về
quan hệ, thuộc tính, bộ cùng một vài ký hiệu và quy ước.
Định nghĩa 1.1
Cho tập hữu hạn và khác rỗng U = {A
1
, A
2
, , A
n
một thuộc tính, mỗi dòng tương ứng với một bộ, ký hiệu là t(U). Nếu một quan hệ
không chứa bộ nào thì ta gọi đó là quan hệ rỗng, ký hiệu là
1.2. Phụ thuộc hàm
Một trong những lớp phụ thuộc logic được Codd đề xuất đầu tiên [16] là phụ
thuộc hàm đóng một vai trò quan trọng trong việc thiết kế và xử lý các cơ sở dữ
liệu. Các khái niệm cơ bản về phụ thuộc hàm, bao đóng tập phụ thuộc hàm, các loại
suy dẫn theo tiên đề, suy dẫn theo quan hệ, định lý tương đương giữa các loại suy
dẫn và lược đồ quan hệ sẽ được trình bày trong phần này. Ngoài ra, khái niệm bao
đóng của tập thuộc tính và bài toán thành viên cùng với thuật toán tìm bao đóng tập
thuộc tính cũng được trình bày ở đây. Các khái niệm này cũng được nhiều tác giả
công bố đầy đủ trong các công trình [1], [6], [9], [10], [11], [16], [23], [35].
Copyright: Tài liệu đại học ©