Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/
1

ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

PHẠM KHÁNH TOÀN
KHẢO SÁT CƠ SỞ CỦA ÁNH XẠ ĐÓNG
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
KHẢO SÁT CƠ SỞ CỦA ÁNH XẠ ĐÓNG Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Ngƣời hƣớng dẫn khoa học: PGS.TSKH Nguyễn Xuân Huy

THÁI NGUYÊN - 2013


giúp đỡ và tạo mọi điều kiện thuận lợi trong quá trình học tập và nghiên cứu.
Trân trọng cảm ơn các thầy cô giáo, gia đình, các bạn lớp cao học Khoa
học máy tính CK10C và các bạn đồng nghiệp đã luôn quan tâm, hỗ trợ,
khuyến khích học viên trong suốt thời gian học tập và thực hiện đề tài.
Xin chân thành cám ơn!
Học viên
Phạm Khánh Toàn

Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/
i
MỤC LỤC

Trang phụ bìa
Lời cam đoan
Lời cảm ơn
MỤC LỤC i
DANH MỤC CÁC KÝ HIỆU, CHỮ CÁI VIẾT TẮT iii
DANH MỤC CÁC BẢNG iv
DANH MỤC HÌNH VẼ iv
MỞ ĐẦU 1
1. Lý do chọn đề tài 1
1.1. Cơ sở lí luận 1
1.2. Cơ sở thực tiễn 1
2. Đối tượng và phạm vi nghiên cứu 1
2.1. Đối tượng nghiên cứu 1
2.2. Phạm vi nghiên cứu 2
3. Nhiệm vụ nghiên cứu 2

2.2. Các dạng toán của một hệ suy dẫn 21
2.2.1. Dạng toán 1 21
2.2.2. Dạng toán 2 22
2.2.3. Các thí dụ 23
Chƣơng 3. CÀI ĐẶT CHƢƠNG TRÌNH 38
3.1. Giới thiệu 38
3.2. Các lớp đối tượng của chương trình 38
3.3. Giao diện của chương trình 39
3.4. Kiểm thử, đánh giá 43
KẾT LUẬN VÀ ĐỀ NGHỊ 58
1. Kết luận 58
2. Đề nghị 58
TÀI LIỆU THAM KHẢO 59

Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/
iii
DANH MỤC CÁC KÝ HIỆU, CHỮ CÁI VIẾT TẮT

AXĐ
Ánh xạ đóng

Thuộc

Không thuộc

Là tập con

Chứa tập con
\
Phép trừ tập hợp

Bảng 2.4 Luật - Ngữ nghĩa các tập đối tượng về hình tam giác, hình
thang và các tính chất 28
Bảng 2.5 Ký pháp - Ngữ nghĩa các tập đối tượng về các học phần
chuyên ngành ĐHSP Ngữ văn 34
Bảng 2.6 Luật - Ngữ nghĩa các tập đối tượng về các học phần chuyên
ngành ĐHSP Ngữ văn 35 Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/
v
DANH MỤC HÌNH VẼ

Hình 3.1 Giao diện chính chương trình 39
Hình 3.2 Giao diện chương trình khi mặc định lấy dữ liệu 40
Hình 3.3 Giao diện chương trình khi chạy file Test1 40
Hình 3.4 Giao diện chương trình hiển thị ngữ nghĩa các luật 41
Hình 3.5 Giao diện chương trình đưa ra kết quả dạng toán 1 42
Hình 3.6 Giao diện chương trình đưa ra kết quả dạng toán 2 42
Hình 3.7 Đọc đề bài từ file dagiac1 44
Hình 3.8 Kết quả câu 1a bài toán dagiac1 45
Hình 3.9 Kết quả câu 1b bài toán dagiac1 45
Hình 3.10 Kết quả câu 1c bài toán dagiac1 45
Hình 3.11 Đọc đề bài từ file tamgiac1 47
Hình 3.12 Kết quả câu 2a, 2b bài toán tamgiac1 47
Hình 3.13 Đọc đề bài từ file dagiac2 50
Hình 3.14 Kết quả câu 2a bài toán dagiac2 50
Hình 3.15 Kết quả câu 2b bài toán dagiac2 51
Hình 3.16 Kết quả câu 2c bài toán dagiac2 51
Hình 3.17 Đọc đề bài từ file tamgiac2 53
Hình 3.18 Kết quả câu 4a, 4b bài toán tamgiac2 53

2. Đối tƣợng và phạm vi nghiên cứu
2.1. Đối tượng nghiên cứu
Xuất phát từ khuôn khổ của bậc học thạc sĩ, với khả năng thực tế của cá
nhân, học viên nghiên cứu, khảo sát cơ sở của ánh xạ đóng làm nền tảng phát
triển các hệ suy dẫn.

Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/
2
2.2. Phạm vi nghiên cứu
- Dạng biểu diễn cơ sở hệ sinh ánh xạ đóng, bao gồm dạng biểu diễn
thứ nhất và dạng biểu diễn thứ hai của cơ sở.
- Ứng dụng ánh xạ đóng vào các hệ suy dẫn.
3. Nhiệm vụ nghiên cứu
Thực hiện đề tài này, luận văn giải quyết các nhiệm vụ sau:
- Tìm hiểu cơ sở lí luận của đề tài.
- Tìm hiểu tính chất của ánh xạ đóng và 2 dạng biểu diễn cơ sở của hệ
sinh ánh xạ đóng.
4. Hƣớng nghiên cứu
- Giới thiệu tổng quan thuật toán và các kỹ thuật liên quan.
- Vận dụng ngôn ngữ ánh xạ đóng để phát triển các kết quả về cơ sở,
biểu diễn cơ sở, suy luận trong hệ suy dẫn,…
- Nghiên cứu ánh xạ đóng để tổng quát hóa trong lý thuyết cơ sở dữ
liệu và các hệ suy dẫn.
- Cài đặt thử nghiệm các thuật toán sử dụng cơ sở ánh xạ đóng.
5. Phƣơng pháp nghiên cứu
Để giải quyết các nhiệm vụ trong đề tài luận văn, học viên sử dụng chủ
yếu các phương pháp sau đây:
- Phương pháp phân loại, tổng hợp các công trình nghiên cứu trong và
ngoài nước đã công bố liên quan đến đề tài.
- Phương pháp xây dựng chương trình khảo sát các tình huống

[4]. Các phần tử của tập hợp được ký hiệu bằng các chữ Latin viết thường đầu
bảng chữ a, b, c, Các tập được ký hiệu bằng các chữ LATIN HOA cuối bảng
chữ X, Y, Z, Các phần tử trong một tập thường được liệt kê như một xâu ký
tự, không có các ký hiệu biểu diễn tập, chẳng hạn ta viết X = abc thay vì viết X
= {a,b,c}. XY biểu diễn hợp của hai tập X và Y, X Y. Phép trừ hai tập X và Y
được ký hiệu là X\Y. Tập vũ trụ hay tập nền U được cho trước luôn luôn là hữu
hạn và khác trống. Kí hiệu SubSet(U) là tập các tập con của U với thứ tự bộ
phận bao hàm ( ).
Các khái niệm về lược đồ quan hệ (LĐQH) và phép dịch chuyển
LĐQH trình bày trong [1] là trường hợp riêng của khái niệm về hệ sinh của
AXĐ và phép thu gọn hệ sinh thông qua các tương ứng sau đây:
Cơ sở dữ liệu
Ánh xạ đóng
Tập thuộc tính U
Tập phần tử U
Phụ thuộc hàm X Y
Luật sinh X Y
LĐQH (U, F)
Hệ sinh (U, F)
Bao đóng của tập thuộc tính ()
+

Ánh xạ đóng f()
Khóa
Khóa (Cơ sở)
Phản khóa
Phản khóa (Phản cơ sở)
1.1. Ánh xạ đóng
Định nghĩa
Cho tập U. Ánh xạ f: SubSet(U) SubSet(U)

(C6) f(X Y) f(X) f(Y)
Thí dụ
Ta xét phản thí dụ cho các tính chất (C5) và (C6) trong mệnh đề trên.
Cụ thể, ta sẽ xây dựng AXĐ f sao cho f(XY) f(X)f(Y) và f(X Y) f(X) f(Y)
với các tập X và Y cụ thể.
Xét ánh xạ f trên tập U = ABC như sau:
f(AB) = f(BC) = U,
Với mọi X U, X AB và X BC ta đặt f(X) = X.
Dễ thấy f là AXĐ và
f(AB) = ABC AB = f(A)f(B), minh họa cho tính chất (C5).
f(AB BC) = f(B) = B ABC = f(AB) f(BC), minh họa cho tính chất (C6).

Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/
6
1.3. Hội các ánh xạ đóng
Định nghĩa
Cho các AXĐ f và g trên U. Ta xác định ánh xạ h trên U như sau,
h(X) = f(X) g(X), với mọi X U. Ta gọi ánh xạ h là hội của các ánh xạ f
và g, ký hiệu là h = f g.
Mệnh đề
Hội của hai AXĐ trên U là một AXĐ trên U.
1.4. Điểm bất động của ánh xạ đóng
Định nghĩa
Cho AXĐ f trên tập U. Tập con X U được gọi là điểm bất động của
AXĐ f nếu f(X) = X .
Ký hiệu Fix(f) là tập toàn bộ các điểm bất động của AXĐ f.
Vì f(U) = U nên Fix(f) luôn chứa U như phần tử lớn nhất. Ngoài ra, dựa vào
tính lũy đẳng của các AXĐ ta có thể đặc tả Fix(f) như sau:
Fix(f) = { f(X) | X U }
Thí dụ

M
(X) = f(X ) M
Định lý [3]
Với mọi AXĐ f trên U và với mọi tập con M của U, f
M
là một AXĐ
trên M.
1.6. Cơ sở của ánh xạ đóng [3]
Định nghĩa
Cho AXĐ f trên U. Tập con K của U được gọi là cơ sở của AXĐ f nếu
K thỏa đồng thời hai tính chất sau:
(i) Tính toàn thể: f(K) = U, và
(ii) Tính tối tiểu: X K: f(X) U.
Nếu K thỏa tính chất (i) thì K được gọi là siêu cơ sở của AXĐ f.
Kí hiệu X K cho biết X là tập con thực sự của K, tức là X K và X K.
Mệnh đề
1. Mọi AXĐ trên tập hữu hạn đều có ít nhất một cơ sở.
2. Hai cơ sở bất kỳ của cùng một AXĐ không bao nhau.
3. Số cơ sở tối đại của một AXĐ là tổ hợp chặp n/2 của n, trong đó n
là số phần tử của U, x là nền nguyên của x (số nguyên lớn nhất không vượt
quá x), tức là bằng C
n
n/2
.
Bổ đề
- Bổ đề 1: Cho K là một cơ sở của AXĐ f trên U. Khi đó
X K: f(X) K = X.
Nhận xét
Do f(X) K = f
K

của U. Ngoài ra, ta ký hiệu U
I
là giao các cơ sở của f.
Định lý (Giao các cơ sở của ánh xạ đóng)
Cho AXĐ f trên tập hữu hạn U. Khi đó giao các cơ sở của f được tính
theo công thức:

UX
I
XXfUU )\)((\

1.7. Hệ sinh ánh xạ đóng
1.7.1. Định nghĩa hệ sinh [2]
Cho tập hữu hạn U, một luật sinh f trên U là biểu thức dạng f: L R;
L, R U. Các tập L và R được gọi tương ứng là vế trái và vế phải của luật
sinh f và được kí hiệu tương ứng là LS(f) và RS(f).
Ta gọi một hệ sinh AXĐ là cặp = (U,F), trong đó U là một tập hữu
hạn, F là tập các luật sinh trên U.

Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/
9
1.7.2. Định lý hệ sinh cho ánh xạ đóng [2]
Với mỗi AXĐ h trên U, tồn tại một hệ sinh = (U,F) thỏa tính chất:
f (X) = h(X)
Thuật toán
Cho hệ sinh = (U,F) và tập con X của U. Hãy tính f (X).
Thuật toán Image dưới đây tính f (X) với thời gian đa thức theo chiều
dài dữ liệu vào, O(|U|
2
.|F|). Tư tưởng của thuật toán là xây dựng dãy các tập

f (X) = X
i
.
Algorithm Image
Format: Image(U,F,X)
Input: - Hệ sinh = (U,F)
- Tập con X của U
Output: - f (X)
Method
Y := X;
repeat
Z := Y;
for each rule L R in F do
if L Y then
Y := Y R;
endif;
endfor;
until Y = Z;
return Y;
end Image.

Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/
10
1.8. Thu gọn hệ sinh ánh xạ đóng
1.8.1. Định nghĩa [2]
Cho hai hệ sinh = (U,F), = (V,G) và tập M U. Ta nói hệ sinh
nhận được từ hệ sinh qua phép thu gọn theo tập M, và kí hiệu là = \M,
nếu sau khi loại bỏ mọi xuất hiện của các phần tử của M trong hệ sinh thì
thu được hệ sinh .
Thao tác loại bỏ M thực hiện trên hệ sinh = (U,F) để thu được hệ sinh

Khi đó f (XY) = Xf
\X
(Y). [2]
1.8.3. Hệ quả về công thức tính ảnh cho một tập
Cho hệ sinh = (U, F) và tập X U.
Khi đó f (X) = X f
\X
( ). [2]
Công thức trên được dùng làm cơ sở cho thuật toán tính ảnh của ánh xạ
cảm sinh với thời gian tuyến tính theo kích thước của hệ sinh.
Tư tưởng của thuật toán là: Để tính f (X) trong hệ sinh = (U,F) ta
thực hiện phép rút gọn = \X.
Trong hệ sinh ta cần tính f ( ).
Dễ thấy rằng f ( ) khi và chỉ khi trong hệ sinh có luật sinh dạng
R với R .
Nếu có những luật như vậy, ta gom các vế phải R của chúng đưa vào
kết quả và lại thực hiện tiếp các phép rút gọn trên hệ sinh . Quá trình này sẽ
kết thúc khi trong không còn luật dạng R, R .
Thí dụ
Cho hệ sinh = (U,F), trong đó:
U = abcdeh
F = {ae d,
bc e,
e bc}

Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/
12
Tính: 1. f (ahe) và 2. f (e) ?
Ta có, theo hệ quả về công thức tính ảnh cho một tập:
1. f (ahe) = ahe f

là tập các phần tử phi cơ sở của , tức là tập các phần tử không có
trong bất kỳ cơ sở nào của .
- U
I
là giao các cơ sở của .
Ta có U = U
K
| U
0
là một phân hoạch của U.
Định lý 1
Cho hệ sinh AXĐ = (U,F) với n phần tử trong tập U và m luật sinh
trong F. Khi đó có thể xác định giao các cơ sở bằng một thuật toán tuyến tính
theo mn qua công thức:

FRL
I
LRUU )\(\Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/
13
Bổ đề 1
Với mọi AXĐ f trên U và mọi tập con X,Y U ta có:
f(Xf(Y)) = f(f(X)Y) = f(XY).
Bổ đề 2 [4]
Cho hai hệ sinh = (U,F), = (V,G) và X U. Biết = \X. Khi đó:
(i) Nếu M là siêu cơ sở của thì M\X là siêu cơ sở của .
(ii) Nếu Z là siêu cơ sở của thì XZ là siêu cơ sở của . Nói riêng, nếu
X U

I
= abcdeh\de = abch.
Đặt = (V,G) với V = U\abch = de, G = F\abch = {e d, e}
Ta tính được Base( ) = { }.
Vậy Base( ) = abch Base( ) = abch { } = abch
2. Với hệ sinh đã cho ta tính được:
U
K
= abch nên U
0
= U\U
K
= abcdeh\abch = de.
Đặt = \de = (P, W)
Ta có P = U\de = abch, W = F\de = {a (loại), bc (loại)}
Do đó Base( ) = abch.
Theo định lý về dạng biểu diễn thứ nhất của cơ sở, vì U
0
= de nên
Base( ) = Base( ) = abch
Hệ quả 2 [4]
(Thu gọn hệ sinh theo các bộ phận không cơ sở và giao các cơ sở)
Cho hệ sinh = (U,F) và các tập phần tử X U
0
, Y U
I
.
Nếu thực hiện phép thu gọn theo XY để nhận được hệ sinh = \XY thì:
Base( ) = Y Base( ).
Dạng biểu diễn thứ hai

Bổ đề 4 [4]
Cho hệ sinh = (U, F), nếu L ML(F) thì L Base( ) khi và chỉ khi
f (L) = U.
Thí dụ 2
Với hệ sinh cho trong thí dụ 1, = (U,F), trong đó:
U= abcdeh
F = {ae d,

Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/
16
a c,
e bc,
eh a,
ac eh,
bd c}.
Ta có ML(F) = {a, e, bd}.
Ta thấy:
1. f (a) = acehbd = U. Vậy a là cơ sở của .
2. f (e) = ebc U. Vậy e không phải là cơ sở của .
3. f (bd) = bdc U. Vậy bd không phải là cơ sở của
Định lý 3 [1]
(Dạng biểu diễn thứ hai cơ sở hệ sinh ánh xạ đóng)
Cho hệ sinh = (U, F). Khi đó mọi cơ sở K của hệ sinh đều biểu
diễn được dưới dạng K = LM, trong đó L là một vế trái cực tiểu của F và M là
cơ sở của hệ sinh \f (L).
Bổ đề 5 [4]
Cho hệ sinh = (U, F) và vế trái cực tiểu L. Khi đó nếu K L
Base( \f (L)) và K không chứa vế trái cực tiểu nào khác ngoài L thì K là cơ sở
của .
Thí dụ 3