HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
QUÁCH THỊ QUỲNH TRANG
NGHIÊN CỨU LÝ THUYẾT, ỨNG DỤNG HỆ THỐNG
THÔNG TIN VÀ NHỮNG VẤN ĐỀ LIÊN QUAN

CHUYÊN NGÀNH: TRUYỀN DỮ LIỆU VÀ MẠNG MÁY TÍNH
MÃ SỐ: 60.48.15

Người hướng dẫn khoa học: PGS.TS NGUYỄN BÁ TƯỜNG

LUẬN VĂN THẠC SĨ KỸ THUẬT
vấn đề cơ bản nhất gắn chặt với hệ tin đó là những bài toán gắn với phân loại theo
quan điểm giống nhau trên các thuộc tính, quan hệ bất khả phân biệt IND(X) với X
là tập thuộc tính.
Nghiên cứu lý thuyết và ứng dụng hệ thống thông tin và những vấn đề liên quan 2
Chương I. LÝ THUYẾT TẬP HỢP
1.1. Giới thiệu tập hợp
Trong toán học, tập hợp có thể hiểu tổng quát là một sự tụ tập của một số hữu
hạn hay vô hạn các đối tượng nào đó. Các đối tượng này được gọi là các phần tử
của tập hợp. Tập hợp là một khái niệm nền tảng (fundamental) và quan trọng của
Lý thuyết tập hợp cũng thừa nhận có một tập hợp không chứa phần tử nào, được
gọi là tập hợp rỗng, ký hiệu là . Các tập hợp có chứa ít nhất một phần tử được gọi
là tập hợp không rỗng.
 Tập hợp có thể được xác định bằng lời:
A là tập hợp bốn số nguyên dương đầu tiên.
B là tập hợp các màu trên quốc kỳ Pháp.
 Có thể xác định một tập hợp bằng cách liệt kê các phần tử của chúng giữa
cặp dấu { }, chẳng hạn:
C = {4, 2, 1, 3}
D = {đỏ, trắng, xanh}
1.2. Quan hệ tương đương
- 3 tính chất của quan hệ tương đương R
1.1. Phản xạ: xRx với x  U
1.2. Đối xứng: xRy suy ra yRx với x,y  U
1.3. Bắc cầu: xRy và yRz suy ra xRz với x, y, z  U

 Một số thuộc tính có thể là dư thừa, nghĩa là trong các thuộc tính điều
kiện ta cụ thể bỏ đi các thuộc tính thừa và không làm thay đổi các nhóm
phân loại theo thuộc tính quyết định
Ví dụ: Trong bảng dưới đây là hệ thống thông tin với ba thuộc tính điều kiện {A, B,
C} và một thuộc tính quyết định {D}.
Bảng 2.1: Hệ quyết định dư thừa thông tin
Đối tượng A B C D
1 0 0 1 0
2 1 0 0 1
3 0 0 1 0
4 0 0 1 0
5 1 0 0 1
6 1 0 0 1
7 1 0 0 1
Nghiên cứu lý thuyết và ứng dụng hệ thống thông tin và những vấn đề liên quan 4
8 1 0 0 1
9 0 0 1 0
10 1 0 0 1
11 0 0 1 0

Nếu xét ba điều kiện {A, B, C} thì có thể bỏ đi một thuộc tính C mà khi phân loại
các đối tượng theo các thuộc tính AB ta được các nhóm như khi phân loại theo các
thuộc tính AB
2.3. Quan hệ bất khả phân biệt ( quan hệ bằng nhau) trong hệ tin

Nghiên cứu lý thuyết và ứng dụng hệ thống thông tin và những vấn đề liên quan 5
5 Hùng 83 Thái Nguyên
6 Trường 84 Thái Nguyên
7 Trang 84 Hà Tĩnh
8 Hoàn 84 Hà Tĩnh
Khi đó:
1 IND(NS) 2 & 1 IND(NS) 3 & 2 IND(NS)1& 2 IND(NS) 3 & 4 IND(NS) 5.
Rõ ràng quan hệ IND(X) là quan hệ tương đương.
Khi đó O/IND(X) là phân hoạch tương đương
O/IND(X) = { p
1
, p
2
, …, p
k
} mà mỗi p
i
là một nhóm gồm các đối tượng giống nhau
trên tập X. Xét ví dụ về tập sinh viên trên đây
O/IND(NS) = {p
1
, p
2
, p

phân loại chúng một cách chắc chắn vào một lớp của phân hoạch O theo tập thuộc
tính D. Ta nói D phụ thuộc vào C với mức k ( 0  k 1) biểu thị là C 
k
D nếu:

||
|)(S|
),(
C
O
DPO
DCk 


Vì

)(/
C
)()(OS
DINDOX
XCDP


, suy ra



)(/
||
|)(|

2
a
3
a
4
x
0
1 A 2 34 Vàng
x
1
2 A 3 23 Trắng
x
2
4 B 3 33 Xanh
x
3
1 B 2 11 Vàng
x
4
3 B 1 33 Trắng
x
5
1 B 4 11 Vàng
Tập thuộc tính điều kiện: D = {a
0
, a
2
}.
Tập thuộc tính quyết định: C = {a
1

}}
Ta có POS
C
(D) = {x
1
}{x
2
}{x
3
}{x
4
}{x
5
} = {x
1
, x
2
, x
3
, x
4
, x
5
}
Vậy độ phụ thuộc k được tính như sau:

6
5
x, x, x, x,x,x
x, x, x, x,x

AH03 1.75 4.0 3.5 0 2NT 0
AH04 1.55 5.0 4.0 1 1 0
AH05 1.5 5.0 6.0 1.5 2NT 0

Một lớp các bài toán liên quan đến hệ quyết định đó là tìm các luật của hệ quyết
định: từ tập thuộc tính điều kiện làm thế nào để có được một giá trị mong muốn
trong tập quyết định. Ví dụ nhìn vào bảng trên ta thấy có một số luật như sau:
Rule 1.
Nếu (Môn 1 = 7.25) & (Môn 2 = 5.0) & (Môn 3 = 6.5) & ( ĐƯT = 1) & ( KV=1) &
( KQ = 1) thì sẽ đậu vào trường Đại học Quốc gia.
Rule 2.
Nếu (Môn 1 = 7.0) & (Môn 2 = 5.5) & (Môn 3 = 8.0) & ( ĐƯT = 0) & ( KV=2)
&(KQ = 1) thì sẽ đậu vào trường Đại học Quốc gia.
Rule 3.
Nếu (Môn 1 = 1.75) & (Môn 2 = 4.0) & (Môn 3 = 3.5) & ( ĐƯT = 0) & ( KV=2NT
) &(KQ = 0) thì không đậu vào trường Đại học Quốc gia.
Rule 4.
Nếu (Môn 1 = 1.55) & (Môn 2 = 5.0) & (Môn 3 = 4.0) & ( ĐƯT = 1) & ( KV=1)
&(KQ = 0) thì không đậu vào trường Đại học Quốc gia.
Rule 5.
Nghiên cứu lý thuyết và ứng dụng hệ thống thông tin và những vấn đề liên quan 8
Nếu (Môn 1 = 1.5) & (Môn 2 = 5.0) & (Môn 3 = 6.0) & ( ĐƯT = 1.5) & (
KV=2NT) &(KQ = 0) thì không đậu vào trường Đại học Quốc gia.
2.6. Hệ khai thác dữ liệu ( data mining system)

i
2
i
3
i
4
i
5
i
6
i
7

o
1
1 1 1 1 1 1 1
o
2
1 1 1 0 0 1 0
o
3
1 1 0 1 0 0 0
o
4
1 0 0 0 1 0 0
o
5
1 0 0 0 0 0 0

2.7. Độ phổ biến

các tập con của I thành hai phần. Một phần gồm các tập s mà sp(s) < minsup và
phần kia gồm các tập s mà sp(s) mà sp(s)

minsup. Trong khai thác dữ liệu tập {s
Nghiên cứu lý thuyết và ứng dụng hệ thống thông tin và những vấn đề liên quan 9

I : sp(s)

minsup} được gọi là các tập phổ biến với ngưỡng minsup. Gọi FS là
họ các tập s mà sp(s)

minsup. Một bài toán quan trọng trong khai thác dữ liệu là
tìm các thuật toán có độ phức tạp bé nhất để tính FS.
2.8. Luật kết hợp
Cho hai tập hàng X, Y

I.
Luật kết hợp của X và Y ký hiệu X

Y là luật chỉ khả năng xuất hiện của Y khi X
xuất hiện.
Giả sử nếu lấy X = {i
1
, i

5
}) = sp({i
1
,i
2
,i
3
,i
4
,i
5
}) / sp({i
1
,i
2
}) = 1/3. CF({i
1
}

{i
2
})
= sp({i
1
,i
2
}) / sp({i
1
}) = (3/5)/(5/5) = 3/5
2.9. Rút gọn hệ tin

R
A B C D E H I J L M N
Nghiên cứu lý thuyết và ứng dụng hệ thống thông tin và những vấn đề liên quan 10
t
1
0 1 2 3 3 4 2 1 2 3 4
t
2
0 0 0 0 3 3 3 3 4 0 3
t
3
1 2 1 1 2 2 4 2 6 1 1
t
4
4 4 4 5 5 5 5 5 5 5 5
t
5
1 3 3 3 4 7 6 7 8 9 0
t
6
2 5 6 4 5 6 8 6 7 8 9
t
7
2 6 5 2 2 1 7 8 3 4 4

Bước 1: Tính nửa trên của E.
Bước 2: Lập họ cực đại M của E.
M gồm các phần tử của E ( không xét trên đường chéo chính) không chứa trong các
phần tử khác. Tức M = {e
ij
mà không có e
kl
chứa e
ij
}.
Bước 3: Đặt k = U
Bước 4: Lặp for each A in U nếu k- A không chứa trong một phần tử nào của M
then k:= k-A; { khi đó A gọi là thuộc tính thừa}
{ kết thúc vòng lặp ta được 1 reduct của S}
b. Thuật toán tìm hết các Reduct của S = ( O, U) dựa vào ma trận D
Input S = ( O, U)
Output k
1
, k
2
, …, k
l
là các reduct của S.
Nội dung thuật toán 2.2 :
Bước 1: Tính nửa trên D.
Nghiên cứu lý thuyết và ứng dụng hệ thống thông tin và những vấn đề liên quan


2.10. Quan hệ trên tập thuộc tính U
Mỗi tập con r của tích Descartes (Decac) các miền giá trị V(A
i
) với
i = 1, 2, 3, , n được gọi là một quan hệ trên U.
Về sau ta thường ký hiệu r hoặc R là quan hệ trên U. Vậy R là quan hệ trên tập
thuộc tính U nếu: R  V(A
1
)  V(A
2)
  V(A
n
)
.
.
Từ định nghĩa ta thấy tích Decac V(A
1
)  V(A
2
)  V(A
n
) có rất nhiều tập con nên
trên U có nhiều quan hệ khác nhau.
2.11. Quan hệ R trên tập thuộc tính U là một Hệ tin
Từ định nghĩa Quan hệ và định nghĩa Hệ tin ta nhận thấy rằng:
Mọi quan hệ r trên U, với R = {t
1
, t
2
, , t

Q.Anh 83 NA
o
3
Q.Anh 83 NA
o
4
Q.Anh 83 NA
o
5
Q.Anh 83 NA

Đây là hệ tin mà các đối tượng giống nhau ( bất khả phân biệt ) trên tập thuộc tính
U. Tức là trong hệ tin này ta luôn có:
f( o
1
, HOTEN) = Q.ANH, f( o
1
, NS) = 83, f( o
1
, QUE) = NA
f( o
2
, HOTEN) = Q.ANH, f( o
2
, NS) = 83, f( o
2
, QUE) = NA
f( o
3
, HOTEN) = Q.ANH, f( o

, , A
n
} là tập thuộc tính, F
là tập phụ thuộc hàm trên U. (Khái niệm phụ thuộc hàm sẽ được đề cập ở phần sau)
Tập thuộc tính k

U được gọi là khoá tối thiểu của W = < U, F > nếu nó thoả mãn
hai điều kiện:
(1) k
+
= U ( hay k

U)
(2) k tối thiểu.
Nghiên cứu lý thuyết và ứng dụng hệ thống thông tin và những vấn đề liên quan 13
Như vậy tập k  U được gọi là khóa tối thiểu của sơ đồ quan hệ W = < U, F > nếu k
là tập tối thiểu kéo theo U.
Tức là k là khoá tối thiểu nếu: k
+
= U ( hay k

U) và bớt khỏi k dù một phần tử thì
bao đóng của tập còn lại khác U. Vậy tập k  U gọi là khóa tối thiểu nếu: k
+

.
Bước 3: Siêu khoá là các A
i
của bao đóng đúng bằng U. Giả sử ta đã có các siêu
khoá là S = {S
1
, S
2
, , S
m
}
Bước 4: Xây dựng tập chứa tất cả các khoá của W từ tập S bằng cách xét mọi S
i
, S
j

con c
ủa S (i ≠ j),
nếu S
i
 S
j
thì ta loại S
j
( i, j = 1 n), kết quả còn lại của S chính là
tất cả các khoá cần tìm
Thuật toán cải tiến
Trước khi đi vào thuật toán cải tiến, ta cần quan tâm một số khái niệm sau:
+
 A
A TD  có X là vế trái của một phụ thuộc hàm trong F sao cho
X → A (1) và A ∉ X
 X  k
+
= ( k - A)
+
 A vì A ∉ X X  (k - A)
+
(k - A) → X (2)
Từ (1) và (2) ta có
(k - A) → A A  (k - A)
+
 (k - A)
+
 A = (k - A)
+
 k
+
= (k - A)
+

mâu thuẫn với điều k là khóa.
Dựa vào hệ quả trên ta có thuật toán tìm tất cả khóa sau:
Dữ liệu vào: Lược đồ quan hệ Q và tập phụ thuộc hàm F
Dữ liệu ra: Tất cả các khóa của quan hệ
Thuật toán 2.7: Thuật toán tìm tất cả khóa của một lược đồ quan hệ
Bước 1: Tạo tập thuộc tính nguồn TN, tập thuộc tính trung gian TG
Bước 2: if TG = ∅ then lược đồ quan hệ chỉ có một khóa k

Bước 5: Tìm khóa bằng cách loại bỏ các siêu khóa không tối thiểu
S
i
, S
j
S
if S
i
S
j
then Loại S
j
ra khỏi Tập siêu khóa S
S còn lại chính là tập khóa cần tìm.
Nghiên cứu lý thuyết và ứng dụng hệ thống thông tin và những vấn đề liên quan 16
Chương III: PHỤ THUỘC HÀM TRÊN QUAN HỆ R VÀ
PHỤ THUỘC HÀM SUY RỘNG
3.1. Phụ thuộc hàm trong quan hệ R
Chúng ta đã có khái niệm cơ bản về phụ thuộc hàm (Functional Dependency) trong
một quan hệ. Phụ thuộc hàm có tầm quan trọng rất lớn trong việc phân tích và thiết
kế mô hình dữ liệu.
Khái niệm: Quan hệ R được định nghĩa trên tập thuộc tính U = { A1, A2, , An}.
A, B U là 2 tập con của tập thuộc tính U. Nếu tồn tại một ánh xạ f: A  B thì ta
nói rằng A xác định hàm B, hay B phụ thuộc hàm vào A, và ký hiệu là A  B.

f2: Số-hóa-đơn, Mã-hàng  Đơn-giá.
f3: Số-hóa-đơn, Mã-hàng  Trị-giá.
f4: Số-lượng-đạt, Đơn-giá  Trị-giá.
Thuộc tính Đơn-giá phụ thuộc hàm không đầy đủ vào khóa (Số-hóa-đơn, Mã-hàng),
bởi vì nó chỉ phụ thuộc vào mặt hàng (thông qua Mã-hàng).
3.2. Phụ thuộc hàm trong quan hệ dựa vào quan hệ bất khả phân biệt IND(X),
IND(Y)
Cho quan hệ R trên tập thuộc tính A = { A
1
, A
2
, , A
n
} ; X, Y

A
Phụ thuộc hàm trong quan hệ R dựa vào các quan hệ IND(X), IND(Y).
Ta nói X xác định phụ thuộc hàm Y ( Y phụ thuộc hàm vào X ) trong R, ký hiệu X

Y nếu IND(X)  IND(Y). Khi đó ta cũng nói R thoả phụ thuộc hàm X→ Y.
Nghiên cứu lý thuyết và ứng dụng hệ thống thông tin và những vấn đề liên quan 18
KẾT LUẬN
Hệ tin là một công cụ đắc lực và không thể thiếu của lý thuyết tập thô, tập mờ.
Hệ tin là trường hợp tổng quát của mô hình quan hệ. Tất các các tính chất, ứng dụng

Bảng 2.6: Ví dụ về hàm thông tin 9
Bảng 2.7: Hệ tin có các đối tượng giống nhau 11