Thạc Sĩ 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Ỹ
NĂM 2014


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ỤNG 31
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
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
2.3. Cơ sở và phản cơ sở ánh xạ đóng . 43
2.3.1. Cơ sở ánh xạ đóng . 43
2.3.2. Phản cơ sở ánh xạ đóng . 44
2.4. Giàn giao 45
2.4.1. Một số khái niệm cơ bản 45
2.4.2. Sự tương quan giữa tập phản cơ sở và tập đối nguyên tử 48
2.5. Ứng dụng giàn giao với bài toán ẩn tập mục nhạy cảm . 50
2.5.1. Đặt vấn đề 50
2.5.2. Phát biểu bài toán . 51
2.5.3. Cơ sở lý thuyết . 53
2.5.4. Thuật toán ẩn tập mục nhạy cảm . 56
2.5.5. Kết quả thử nghiệm 60
2.6. Giàn giao và ứng dụng trong khai thác tập phổ biến 61
2.6.1. Cơ sở lý thuyết . 62
2.6.2. Thuật toán xác định họ các tập phổ biến tối đại 63
2.7. Kết luận chương 2 65


CHƯƠNG 3 HỆ SINH AXĐ VÀ MỘT SỐ KẾT QUẢ NGHIÊN CỨU 66
3.1. Hệ sinh ánh xạ đóng . 68
3.1.1. Khái niệm hệ sinh AXĐ . 68
3.1.2. Ánh xạ cảm sinh 69
3.1.3. Thuật toán xác định ảnh một tập con trong hệ sinh . 70
3.2. Giản lược tập luật sinh 71
3.2.1. Một số khái niệm cơ sở 71
3.2.2. Tập giản lược tự nhiên . 75
3.2.3. Tập giản lược không dư . 76
3.3. Thu gọn hệ sinh ánh xạ đóng 78
3.3.1. Các khái niệm và thuật toán thu gọn hệ sinh AXĐ . 79
3.3.2. Biểu diễn ảnh tập con theo phép thu gọn hệ sinh AXĐ . 80
3.4. Cơ sở và phản cơ sở hệ sinh ánh xạ đóng 81
3.4.1. Cơ sở hệ sinh AXĐ 82
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
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

1. Đặt vấn đề
PHẦN MỞ ĐẦU

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
quan giữa các đối tượng khóa (cơ sở) và phản khóa (phản cơ sở) trong một lược đồ
quan hệ (LĐQH). Đây là hai khái niệm đối ngẫu nhau theo nghĩa khóa là tập con
nhỏ nhất các thuộc tính có ảnh là U, phản khóa là tập con lớn nhất các thuộc tính có
ảnh khác U, với U là tập toàn thể các thuộc tính trong lược đồ quan hệ đang khảo
sát. Cũng trong công trình này, các tác giả đã chỉ ra từ tập các khóa của một LĐQH,
có thể dễ dàng thu được tập các phản khóa của LĐQH này với một thuật toán có độ
phức tạp tính toán là đa thức và ngược lại, từ tập các phản khóa của một LĐQH thì
tập các khóa của LĐQH này hoàn toàn xác định với một thuật toán có độ phức tạp
tính toán đa thức. Phát biểu này cho thấy khi tính toán, biễu diễn các đối tượng
trong lược đồ quan hệ thì khóa và phản khóa có vai trò và ý nghĩa quan trọng như
nhau. Năm 1992, nhóm nghiên cứu Nguyễn Xuân Huy và Lê Thị Thanh, trong [42]
đã mở rộng PTBD thành phụ thuộc Boole dương tổng quát (PTBDTQ). Với loại
phụ thuộc này, phép so sánh đẳng thức được thay bằng phép toán trên quan hệ hai
ngôi thỏa các tính chất phản xạ, đối xứng và bộ phận. Định lý tương đương vẫn
được bảo toàn đối với PTBDTQ. Năm 1994, trong [3] các nhà nghiên cứu lại tiếp
tục mở rộng PTBDTQ, phát triển thành phụ thuộc Bool dương đa trị (PTBĐT) và
phụ thuộc Bool dương theo nhóm bộ (PTBDTNB). Định lý tương đương vẫn được
bảo toàn đối với các loại phụ thuộc này. Gần đây nhất, từ năm 2011 đến nay, trong
[8], [47] các nhóm nghiên cứu của Shaoxu Song, Lei Chen và Nguyễn Xuân Huy
cùng các nghiên cứu sinh đã đề xuất khái niệm phụ thuộc sai khác và giải quyết một
số vấn đề kinh điển liên quan đến lớp phụ thuộc này như bài toán suy dẫn, tìm khoá
và các phủ,
Trong toán học có hai khái niệm được quan tâm nhiều là ánh xạ co và ánh xạ
đóng. Ánh xạ co biến đổi một tập đối tượng thành một tập con của nó, ngược lại ánh
xạ đóng biến đổi một tập đối tượng thành một tập chứa nó. Trong giải tích và topo,
ánh xạ đóng thường được vận dụng cho các hàm liên tục. Cụ thể, một tập đóng là
tập chứa các dãy điểm có giới hạn thì sẽ chứa giới hạn của dãy đó. Trong khuôn khổ
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
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
thác luật kết hợp, . Việc tiếp tục nghiên cứu lý thuyết giàn để phát triển, biểu diễn
các đối tượng của hệ suy dẫn cũng như ứng dụng vào một số lĩnh vực trong công
nghệ thông tin cũng là một vấn đề rất đáng quan tâm.