Số hóa bởi trung tâm học liệu
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 NGỌC TOÁN

CÁC THUẬT TOÁN BIẾN ĐỔI
LƢỢC ĐỒ QUAN HỆ VÀ ỨNG DỤNG
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

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 Số hóa bởi trung tâm học liệu
i
LỜI CAM ĐOAN

Học viên cam đoan luận văn này là do bản thân tự nghiên cứu và thực hiện
theo sự hƣớng dẫn khoa học của thầy giáo PGS. TSKH. Nguyễn Xuân Huy.
Học viên hoàn toàn chịu trách nhiệm về tính pháp lý quá trình nghiên
cứu khoa học của luận văn này.
Thái Nguyên, ngày 10 tháng 11 năm 2013
Ngƣời cam đoan

Số hóa bởi trung tâm học liệu
iii
MỤC LỤC LỜI CAM ĐOAN i
LỜI CẢM ƠN ii
MỤC LỤC iii
DANH MỤC CÁC KÝ HIỆU, CHỮ CÁI VIẾT TẮT v
DANH MỤC CÁC HÌNH vi
MỞ ĐẦU 1
1. Lý do chọn đề tài 1
2. Đối tƣợng và phạm vi nghiên cứu 1
3. Hƣớng nghiên cứu của đề tài 1
4. Phƣơng pháp nghiên cứu 2
5. Ý nghĩa khoa học của đề tài 2
6. Tên đề tài 2
7. Bố cục luận văn 2
Chƣơng 1. CÁC KHÁI NIỆM VỀ LƢỢC ĐỒ QUAN HỆ 3
1.1. Quan hệ và bộ 3
1.2. Phụ thuộc hàm, hệ tiên đề Armstrong, lƣợc đồ quan hệ 3
1.2.1. Phụ thuộc hàm 3
1.2.2. Hệ tiên đề Armstrong 4
1.2.3. Lƣợc đồ quan hệ 4
1.3. Bao đóng của tập thuộc tính 4
1.4. Phủ của tập phụ thuộc hàm 8
1.5. Cơ sở của lƣợc đồ quan hệ 10
1.6. Cách tính giao các cơ sở 12


Khác

Thuộc

Không thuộc

Là tập con

Suy ra
:=
Gán
\
Phép trừ tập hợp

Phép giao tập hợp

Phép hợp tập hợp

Tƣơng đƣơng

Tƣơng đƣơng
!
Không tƣơng đƣơng

Chứa tập con

Với mọi

Tập rỗng

khoa học, xây dƣng,… Việc dùng phƣơng tiện tin học để tổ chức và khai thác
cơ sở dữ liệu đã đƣợc phát triển từ những năm 60. Trong những năm gần đây
vai trò của máy tính trong việc lƣu trữ thông tin ngày càng trở nên quan trọng.
Vì vậy đã tạo ra những kho dữ liệu khổng lồ. Quản lý các cơ sở dữ liệu lớn và
phức tạp đòi hỏi nhiều thuật toán hữu hiệu để tính toán các đối tƣợng nhƣ bao
đóng, khóa, phủ
Một số thuật toán tốt theo nghĩa độ phức tạp tính toán giới hạn ở các
hàm tuyến tính hoặc đa thức theo chiều dài dữ liệu vào đã đƣợc công bố nhƣ
thuật toán tính bao đóng của tập thuộc tính, thuật toán tìm một khóa, thuật
toán xác định thành viên hay thuật toán xác định PTH suy dẫn, thuật toán tìm
giao các khóa, thuật toán xác định một LĐQH có một khóa duy nhất
2. Đối tƣợng và phạm vi nghiên cứu
Luận văn tập trung tìm hiểu các thuật toán biến đổi lƣợc đồ quan hệ và
ứng dụng thông qua phép biến đổi của lƣợc đồ quan hệ theo một tập thuộc
tính X. Tiếp tục phát triển dạng biểu diễn cơ sở thứ nhất và khảo sát biểu diễn
cơ sở dạng thứ 2 của lƣợc đồ quan hệ. Xây dựng một hệ trình minh họa và
đánh giá các kết quả lý thuyết.
3. Hƣớng nghiên cứu của đề tài
- Giới thiệu tổng quan về phép biến đổi của lƣợc đồ quan hệ
- Các thuật toán biến đổi, giản lƣợc lƣợc đồ quan hệ
- Thuật toán biểu diễn cơ sở, tính bao đóng
- Cài đặt chƣơng trình

Số hóa bởi trung tâm học liệu
2
4. Phƣơng pháp nghiên cứu
- Phƣơng pháp tổng hợp, phân tích các kết quả của các nhà nghiên cứu
liên quan đến lĩnh vực nghiên cứu trên các tài liệu đã xuất bản, trên các bài
báo, tạp chí khoa học, trên mạng Internet
- Giải quyết các vấn đề đặt ra trong phạm vi đề tài là tiên đề hóa. Các

Cho tập hữu hạn U = {A
1
, A
2
, , A
n
} khác trống (n ≥ 1). Các phần tử
của U đƣợc gọi là thuộc tính, ứng với mỗi thuộc tính A
i
U, i = 1, 2, , n có
một tập không rỗng dom(A
i
) đƣợc gọi là miền trị của thuộc tính A
i
(thập chí
đƣợc giả thiết là chứa hơn 1 giá trị).
Đặt
)(
1
A
i
n
i
domUD

Một quan hệ R với các thuộc tính U = {A
1
, A
2
, , A

R(X Y) u,v R: u.X = v.X u.Y = v.Y
Cho quan hệ R(U) và tập PTH F trên tập thuộc tính U. Ta nói quan hệ
R thỏa tập PTH F, ký hiệu R(F), nếu R thỏa mọi PTH trong F, tức là R(F)
f F: R(f).
1.2.2. Hệ tiên đề Armstrong [2, 3]
Cho quan hệ R(U). Giả sử X, Y, Z, W U.
F1. Tính phản xạ:
Nếu X Y thì X Y

F2. Tính gia tăng:
Nếu X Y thì XZ YZ

F3. Tính bắc cầu:
Nếu X Y và Y Z thì X Z

Chú ý: Các PTH có vế trái chứa vế phải nhƣ mô tả trong F1 đƣợc gọi là
tầm thƣờng. Các PTH tầm thƣờng thoả trong mọi quan hệ.
1.2.3. Lược đồ quan hệ [2]
Lƣợc đồ quan hệ (LĐQH) là một cặp p = (U, F) trong đó U là tập hữu
hạn các thuộc tính, F là tập các PTH trên U.
Quy ƣớc: Trong trƣờng hợp không chỉ rõ tập PTH F, ta xem LĐQH chỉ
là một tập hữu hạn các thuộc tính U.
1.3. Bao đóng của tập thuộc tính [2]
Cho tập PTH F trên tập thuộc tính U và một tập con các thuộc tính X
trong U. Bao đóng của tập thuộc tính X, ký hiệu X
+
, là tập tất cả các thuộc tính
A U mà PTH X A có thể đƣợc suy diễn logic từ F nhờ hệ tiên đề Armstrong:
X
+

5. (X
+
Y)
+
= (XY
+
)
+
= (XY)
+

6. X Y Y X
+

7. X X
+
và X
+
X8. X
+
=Y
+
X Y

và Y

X

 Đánh giá độ phức tạp
Giả sử n là số lƣợng các thuộc tính trong U, m là số lƣợng các PTH
trong F thì thuật toán trên có độ phức tạp đa thức bậc hai theo chiều dài dữ
liệu O(mn
2
).
Ví dụ 1: Cho lƣợc đồ quan hệ R = (U,F)
U = ABCDEGH
F= {AB C, D EG, ACD B, C A, BE C, CE AG,
BC D, CG BD, G H}
a. Tính D
+

b. Tính (BE)
+

c. Tính (DE)
+

d. Tính (CG)
+

Giải
a. Tính D
+

X
0
= D
1. X

Số hóa bởi trung tâm học liệu
7
c. Tính (DE)
+

X
0
= DE
1. X
1
= DEG (áp dụng D EG)
2. X
2
= DEGH (áp dụng G H)
Vậy (DE)
+
= DEGH
d. Tính (CG)
+

X
0
= CG
1. X
1
= CGA (áp dụng C A)
2. X
2
= CGABD (áp dụng CG BD)
3. X

2. X
2
= CGEA (áp dụng CG EA)
3. X
3
= CGEAB (áp dụng AEB BC)
4. X
4
= CGEABD (áp dụng BG CD)
Vậy C
+
= ABCDEG

Số hóa bởi trung tâm học liệu
8
b. Tính B
+

X
0
= B
1. X
1
= BCG (áp dụng B CG)
2. X
2
= BCGD (áp dụng BG CD)
3. X
3
= BCGDEA (áp dụng CG EA)

tập PTH F.
 Phủ thu gọn tự nhiên
Cho hai tập PTH F và G trên cùng một thuộc tính U. G là phủ thu gọn
tự nhiên của F nếu:
1. G là phủ của F, và
2. G có dạng thu gọn tự nhiên theo nghĩa sau:

Số hóa bởi trung tâm học liệu
9
a. Hai vế trái và phải của mọi PTH trong G rời nhau (không giao nhau)
f G: LS(f) RS(f) =
b. Các vế trái của mọi PTH trong G khác nhau đôi một.
f, g G: f g LS(f) LS(g)
 Thuật toán tìm phủ thu gọn tự nhiên của tập PTH F
Algorithm Natural_Reduced
Function: Tính phủ thu gọn tự nhiên của tập PTH
Format: Natural_Reduced (F)
Input: Tập PTH F
Output: Một phủ thu gọn tự nhiên G của F
i) G F
ii) L R G: L R =
iii) L
i
R
i
, L
j
R
j
G: i j L

+
U
Hai điều kiện trên tƣơng đƣơng với
(i) B U
(ii) A B: (B\{A})

! U
Nếu B thỏa mãn điều kiện (i) thì B đƣợc gọi là một siêu cơ sở.
Thuộc tính A U đƣợc gọi là thuộc tính cơ sở (nguyên thủy hoặc cơ
sở) nếu A có mặt trong một cơ sở nào đấy. A đƣợc gọi là thuộc tính không cơ
sở (phi nguyên thủy hoặc thứ cấp) nếu A không có mặt trong bất kỳ cơ sở
nào. Ký hiệu U
B
là tập các thuộc tính cơ sở của LĐQH p và U
0
là tập các
thuộc tính không cơ sở của p.
Chú ý: Trong một số tài liệu, thuật ngữ cơ sở đƣợc dùng theo nghĩa
siêu cơ sở và thuật ngữ cơ sở tối tiểu đƣợc dùng theo nghĩa cơ sở .
 Thuật toán tìm một cơ sở của LĐQH
Tƣ tƣởng: Xuất phát từ một siêu cơ sở B tuỳ ý của LĐQH, duyệt lần
lƣợt các thuộc tính A của B, nếu bất biến (B\{A})
+
= U đƣợc bảo toàn thì A
loại khỏi B. Có thể thay kiểm tra (B\{A})
+
= U bằng kiểm tra A (B\{A})
+

Algorithm Base

m).
Ví dụ 3: Cho LĐQH p = (U,F), trong đó:
U = {A, B, C, D, E}
F = { D E
AB CD
C AB }
Hãy tìm một cơ sở của p.
Dễ thấy rằng, LĐQH p có cơ sở B = C, vì thoả mãn hai điều kiện:
(i) B
+
= C
+
= ABCDE = U
(ii) C tối tiểu ( theo nghĩa (B \ {C})
+
U ).
Ví dụ 4: Cho P = (U,F), trong đó: U = ABCDE
F = { C B
DE AC
A DE }

Số hóa bởi trung tâm học liệu
12
Tìm cơ sở của LĐQH đã cho?
Ta thấy, LĐQH P có cơ sở B = A, vì thoả mãn 2 điều kiện:
(i) B
+
= A
+
= ABCDE = U

- Tập PTH F
Output: Giao các cơ sở

FRL
LRUM )\(\

Method
M:=U;
For each FD L R in F do

Số hóa bởi trung tâm học liệu
13
M:=M\(R\L);
Endfor;
Return M;
End BaseIntersec.
Ví dụ 5: Cho p = (U,F), trong đó: U = ABCDE
F = {AB C
AD B
B D}
Ta có, giao của các cơ sở là U
I
= ABCDE\BCD = AE
U
I
+
= (AE)
+
= AE U nên p có hơn một cơ sở. Vì U
I

= U đƣợc bảo toàn thì loại A khỏi M.
Sau đó duyệt tƣơng tự với các thuộc tính trong U\B.
Algorithm Base 2
Function: Tìm một cơ sở thứ 2 của LĐQH
Input: - Tập thuộc tính U
- Tập PTH F
- Cơ sở B U

Số hóa bởi trung tâm học liệu
14
Output: Cơ sở thứ hai, nếu có, M U thoả
i) M
+
= U
ii) A M : (M\{A})
+
U
Nếu không có cơ sở thứ 2:
Method
M := U;
For each attribute A in B do
If A (M\{A})
+
then
M := M \ {A}
Endif;
Endfor;
For each attribute A in U \ B do
If A (M\{A})
+

= U\vế phải của F = ABCDE – ABDE = C
b. Tìm một cơ sở B
1
của P
Lập bảng
Loại thử thuộc tính nào ta đánh dấu phẩy (') bên cạnh thuộc tính đó.
Nếu bao đóng các thuộc tính còn lại bằng U thì loại thuộc tính đó ký hiệu ( _ )
ví dụ: A
'
(loại). Những thuộc tính không loại đƣợc thì tô đậm.
Base (B)
A
'
B
'
C
'
D
'
E
'
BCDE (thử loại bỏ A)
A
B
C
D
E
CDE (thử loại bỏ B)
A
B

+
= C U nên lƣợc đồ có hơn một cơ sở .
Vậy ngoài cơ sở B
1
, lƣợc đồ còn có cơ sở B
2
= BC vì thoả 2 điều kiện sau:
(i) B
+
= (BC)
+
= ABCDE = U
(ii) BC tối tiểu ( theo nghĩa (B \ {BC})
+
U ).
d. Xác định tập các thuộc tính không cơ sở U
0

của P.
- Thuộc tính cơ sở là thuộc tính có mặt trong mọi cơ sở, ký hiệu là U
B.
- Thuộc tính không cơ sở là thuộc tính không có mặt trong bất cứ cơ sở
nào, ký hiệu U
0
.
Ta có: U
B
= ABCD U
0
= E.

Với M = CFG, hãy xác định q = (V,G) = p\M.

Số hóa bởi trung tâm học liệu
17
Giải
Bƣớc 1: Tính V = U \ M = ABCDEFG \ CFG = ABDE
Vậy V = ABDE
Bƣớc 2: Tính G = F\M = { AB DE,
BD A,
DE , (Loại)
E , (Loại)}
Vậy G = {AB DE,
BD A}
Lƣợc đồ quan hệ q = (V,G) trong đó:
V = ABDE
G = {AB DE,
BD A}
Ta cũng dễ nhận thấy kỹ thuật thu gọn LĐQH thoả tính hợp thành và
giao hoán, cụ thể nếu p là LĐQH trên tập thuộc tính U và X, Y là hai tập con
rời nhau của U thì
p\XY = (p\X)\Y = (p\Y)\X
2.2. Thuật toán biến đổi LĐQH [2, 3]
Algorithm Translation
Input:
- LĐQH p = (U,F)
- Tập thuộc tính M U
Output:
LĐQH q = (V,G) = p\M, V = U\M, G = F\M.
Method
V := U\M;