ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN

NGUYỄN THỊ XUÂN THU

THU GỌN LƯỢC ĐỒ QUAN HỆ VÀ ỨNG DỤNG

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN


Thái Nguyên – 2010 LỜI CẢM ƠN

Lời đầu tiên, em xin chân thành bày tỏ lòng cảm ơn và kính trọng sâu
sắc đối với PGS.TS Nguyễn Xuân Huy, người đã tận tình hướng dẫn em
trong suốt quá trình hoàn thành luận văn này. Thầy đã mở ra cho em những
vấn đề khoa học rất lý thú, hướng em vào nghiên cứu các lĩnh vực hết sức
thiết thực và vô cùng bổ ích, đồng thời tạo điều kiện thuận lợi cho em học tập
và nghiên cứu. Em đã học hỏi được rất nhiều ở Thầy phong cách làm việc,
cũng như phương pháp nghiên cứu khoa học… Em luôn được Thầy cung cấp
các tài liệu, các chỉ dẫn hết sức quý báu khi cần thiết trong suốt thời gian
thực hiện luận văn.
Em cũng xin thể hiện sự kính trọng và lòng biết ơn đến Quý Thầy Cô
trong Khoa Công nghệ thông tin - ĐHTN, những người đã trang bị cho em
rất nhiều kiến thức chuyên ngành, cũng như sự chỉ bảo, giúp đỡ tận tình của
quý Thầy cô đối với em trong suốt quá trình học tập. Tất cả các kiến thức mà
em lĩnh hội được từ bài giảng của các Thầy cô là vô cùng quý giá.
Cuối cùng, em xin được cảm ơn các bạn học viên trong lớp Cao học

2.2. Thuật toán thu gọn LĐQH ........................................................................ 25
2.3. Định lý thiết lập công thức biểu diễn bao đóng ......................................... 29
2.4. Bổ đề về siêu khoá trong phép thu gọn ..................................................... 32
2.5. Hệ quả về siêu khoá trong phép thu gọn .................................................... 33
2.6. Bổ đề về khoá trong phép thu gọn.............................................................. 34
2.7. Định lý thứ nhất về cách biểu diễn khoá .................................................... 35
2.8. Định lý thứ hai về cách biểu diễn khoá ...................................................... 38
2.9. Lược đồ cân bằng ...................................................................................... 45
Chương 3
CÀI ĐẶT CHƯƠNG TRÌNH
ỨNG DỤNG KỸ THUẬT THU GỌN LƯỢC ĐỒ QUAN HỆ TRONG
THIẾT KẾ CƠ SỞ DỮ LIỆU
3.1. Giới thiệu................................................................................................... 52
3.2. Một số giao diện của chương trình............................................................. 53
3.3. Hướng dẫn sử dụng.................................................................................... 59
KẾT LUẬN VÀ KIẾN NGHỊ
1. Kết luận........................................................................................................ 61
2. Kiến nghị...................................................................................................... 61
TÀI LIỆU THAM KHẢO ............................................................................. 62
├ Suy dẫn theo quan hệ
 Là con
 Chứa
 Thuộc
 Không thuộc
 Với mọi
X
+
Bao đóng của tập thuộc tính X
 Tương đương
! Không tương đương
 Phép giao
 Phép hợp
DANH MỤC HÌNH VẼ Hình 3.1. Giao diện chính................................................................................. 53
Hình 3.2. Giao diện tạo LĐQH mới.................................................................. 54
Hình 3.3. Giao diện ghi dữ liệu......................................................................... 55
Hình 3.4. Giao diện mở dữ liệu......................................................................... 56 Hình 3.5. Giao diện xử lý ................................................................................. 57
Hình 3.6. Giao diện help................................................................................... 58

“Kỹ thuật thu gọn lược đồ quan hệ”. Bản chất của kỹ thuật này là loại bỏ khỏi
LĐQH ban đầu một số thuộc tính không quan trọng theo nghĩa chúng không làm
ảnh hưởng đến kết quả tính toán của các đối tượng đang quan tâm như bao đóng,
khoá, phản khoá… Mặc dù LĐQH thu được qua phép thu gọn không tương
đương với LĐQH ban đầu, nhưng ta có thể thu được các đối tượng cần tìm bằng
những phép toán đơn giản như loại bỏ hoặc thêm vào một số thuộc tính.
Đặc biệt là sau khi loại bỏ một số thuộc tính thì một số phụ thuộc hàm sẽ
được loại bỏ theo, vì chúng trở thành các phụ thuộc hàm tầm thường (có vế trái
chứa vế phải) hoặc mang thông tin tiền định. Kỹ thuật này có thể được ứng dụng
để giải quyết các bài toán cơ sở dữ liệu phức tạp. Đây là hướng nghiên cứu chính
của đề tài.
Luận văn được trình bày trong 3 chương:
Chương 1: Trình bày các kiến thức cơ bản về cơ sở dữ liệu.
Chương 2: Tìm hiểu về kỹ thuật thu gọn lược đồ quan hệ, các định lý cơ
bản của phép thu gọn và các dạng biểu diễn khoá thông qua phép thu gọn.
Chương 3: Cài đặt chương trình. Ứng dụng kỹ thuật thu gọn lược đồ quan
hệ trong thiết kế cơ sở dữ liệu.


mô hình dữ liệu quan hệ đã phát triển ở mức độ cao và đạt được những kết quả sâu sắc.
Hàng loạt vấn đề đã được nghiên cứu giải quyết như:
- Lý thuyết thiết kế CSDL, các phương pháp tách và tổng hợp các lược đồ quan hệ
theo tiêu chuẩn không tổn thất thông tin hay bảo toàn tính nhất thể của các ràng buộc
trên dữ liệu .
- Các loại ràng buộc dữ liệu, cấu trúc và các tính chất của chúng, ngữ nghĩa và khả
năng áp dụng phụ thuộc dữ liệu ví dụ như phụ thuộc hàm, phụ thuộc đa trị, phụ thuộc
kết nối, phụ thuộc lôgic...
- Các vấn đề tối ưu hoá: ở mức vật lí trong việc tổ chức quản lí các tệp; ở mức
đường truy nhập với các tệp chỉ số hay các danh sách sắp xếp; ở mức lôgic trên cơ sở
rút gọn các biểu thức biểu diễn các câu hỏi….
Trong luận văn này, em sẽ trình bày một số kiến thức cơ bản nhất về CSDL bao
gồm các kiến thức liên quan đến phụ thuộc hàm, khoá, các dạng chuẩn và đặc biệt là đi
sâu tìm hiểu kỹ thuật thu gọn lược đồ quan hệ cũng như các thuật toán để áp dụng
chúng vào việc xây dựng và thiết kế các bài toán CSDL hiện nay.
1.2 Phụ thuộc hàm
1.2.1 Định nghĩa phụ thuộc hàm
Cho tập thuộc tính U. Giả sử X, Y  U. Một phụ thuộc hàm (PTH) trên U
là biểu thức dạng f: X  Y. Nếu f: X  Y là một PTH trên U thì ta nói tập thuộc tính Y phụ thuộc hàm
vào tập thuộc tính X, hoặc tập thuộc tính X xác định hàm tập thuộc tính Y.
Cho quan hệ R(U) và một PTH f: X  Y trên U. Ta nói quan hệ R thỏa
PTH f (hay PTH f đúng trong quan hệ R), ký hiệu R(f), nếu hai bộ tùy ý trong R
giống nhau trên X thì cũng giống nhau trên Y, tức là
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).

+
.
F╞ f  f  F
+

Nói cách khác, PTH f được suy dẫn logic từ tập PTH F nếu xuất phát từ F,
áp dụng các luật F1, F2, F3 của hệ tiên đề Arsmtrong sau hữu hạn lần ta sẽ thu
được PTH f.
1.2.4.2 Suy dẫn theo quan hệ
Cho tập PTH F trên tập thuộc tính U và f là một PTH trên U. Ta nói PTH f
được suy dẫn theo quan hệ từ tập PTH F, ký hiệu F├ f, nếu mọi quan hệ R(U)
thỏa F thì R cũng thỏa f.
F├ f  SAT(F)  SAT(f)
Ký hiệu SAT(F) là tập toàn thể các quan hệ trên U thỏa tập PTH F.
Cho tập thuộc tính U và tập PTH F trên U, ta định nghĩa F
*
là tập các PTH f trên
U được suy dẫn theo quan hệ từ tập PTH F.
F* = {f: X  Y | X,Y  U, F├ f }
1.2.4.3 Suy dẫn theo quan hệ không có quá p bộ
Cho tập PTH F trên tập thuộc tính U và f là một PTH trên U. Ta nói PTH f
được suy dẫn theo quan hệ có không quá p bộ từ tập PTH F, ký hiệu F├
p
f, nếu
mọi quan hệ R
p
(U) thỏa F thì R cũng thỏa f.
F├
p
f  SAT

5. F  FD(SAT(F))
6.   SAT(FD ())
7. SAT(FD(SAT(F))) = SAT(F)
8. FD (SAT(FD ())) = FD ()
 Một số tính chất mở rộng của PTH
Sử dụng 3 tiên đề Armstrong ta dễ dàng chứng minh các tính chất F4-F11
sau đây. Một số tính chất được chia nhỏ nhằm mục đích mô tả các hệ tiên đề
khác cho PTH trong các mục tiếp theo.
 X,Y,Z, V  U,  A U:
F4. Tính tựa bắc cầu: XY, YZ V  XZ  V
F5. Tính phản xạ chặt: XX
F6. Mở rộng vế trái thu hẹp vế phải: X Y  XZ  Y\V
F7. Tính cộng đầy đủ: XY, Z V  XZ  YV F8. Mở rộng vế trái: XY, XZ  Y
F9. Cộng tính ở vế phải: XY, X Z  X  YZ
F10. Bộ phận ở vế phải : XYZ  X  Y
F11. Tính tích luỹ: XYZ, ZAV  X  YZA
1.3. Lược đồ quan hệ
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.4 Bao đóng của tập thuộc tính
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:

Enddif ;
Endfor ;
Until Y: = Z;
Return Y;
End Closure.

 Đá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
).
 Một số tính chất của bao đóng
Cho LĐQH a = (U, F). Khi đó X, Y  U ta có
1. Tính phản xạ: X  X
+

2. Tính đồng biến: X  Y  X
+
 Y
+

3. Tính lũy đẳng: (X
+
)
+
= X
+

4. (XY)
+

=Y
+
 X  Y

và Y 

X
 Bài toán thành viên
Đây là bài toán xác định xem một PTH có thuộc bao đóng của tập PTH không ?
Thuật toán giải quyết vấn đề này dựa trên một định lý cơ bản, thể hiện mối liên quan
giữa bao đóng của tập thuộc tính và bao đóng của tập PTH. Bài toán: Cho tập thuộc tính U, một tập các PTH F trên U và một PTH f : X  Y
trên U. Hỏi rằng f  F
+
(f có phải là thành viên của F
+
) hay không ?
X  Y  F
+
 Y  X
+

Ý tưởng thuật toán : Kiểm tra X  Y  F
+
không ?
- Tính X
+


F! G có nghĩa là F và G không tương đương.
Cho tập PTH F trên tập thuộc tính U và X là tập con của U, ta dùng ký hiệu X
F
+

trong trường hợp cần chỉ rõ bao đóng của tập thuộc tính X lấy theo tập PTH F.
1.5.1 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:
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

(ii) G có dạng không dư theo nghĩa sau: gG: G\{g}  G.
 Thuật toán tìm phủ không dư của tập PTH F
Algorithm Nonredundant
Funtion : Tính phủ không dư
Format: Nonredundant (F)
Input: - Tập PTH F
Output: - Một phủ không dư G của F
(i) G  F
(ii) gG: G\{g} G
Method
U : = Attr (F) ;
// Tập thuộc tính của F
G : = F;
For each FD g : L R in F do
If R  Closure (U,G\{g},L) then
G := G\{g};
Endif;
Endfor;
Return G;
End Nonredundant.
1.5.3 Phủ thu gọn
Cho hai tập PTH F và G trên tập thuộc tính U. G được gọi là phủ thu gọn của F
nếu G đồng thời là phủ thu gọn trái và thu gọn phải của F.
 Thuật toán tìm phủ thu gọn của tập PTH
Algorithm Reduced
Funtion: Tính phủ thu gọn của tập PTH
Format: Reduced (F)
Input: - Tập PTH F
Output: - Một phủ thu gọn của F


Endfor
Return G;
End Left_Reduced
1.5.3.2 Phủ thu gọn phải Cho hai tập PTH F và G trên tập thuộc tính U, G được gọi là phủ thu gọn phải của
F nếu:
i) G là một phủ của F, và
ii) (LR  G, AR) : G\{LR}{LR\A}  G
 Thuật toán tìm phủ thu gọn phải của tập PTH
Ta thấy rằng g: LR  G, A  R : G╞ g’: LR \ {A}, vì R\{A}  R , do đó
ta chỉ cần kiểm tra G \ {g}  {g’}╞ g ?
Algorithm Right_Reduced
Function : Tính phủ thu gọn phải của tập PTH
Format: Right_Reduced (F)
Input: - Tập PTH F
Output: - Một phủ thu gọn phải G của F
i) GF
ii) g: LR  G, A R: G\{g} {LR\A} ! G
Method
U : = Attr (F) ; // Tập thuộc tính của F
G := F;
For each FD g: LR in F do
X:=R;
For each attribute A in X do
If A in Closure (U, G\{g}  {LR\{A}},L) then
Delete A from R in G;
Endif;
Endfor;

End Mincover.
1.6 Khóa của lược đồ quan hệ
Cho LĐQH p = (U, F). Tập thuộc tính K  U được gọi là khóa của LĐQH
p nếu:
(i) K
+
= U
(ii) AK: (K\{A})
+
 U
Hai điều kiện trên tương đương với
(i) K  U
(ii) AK: (K\{A})

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

End key.

Độ phức tạp tính toán: Thuật toán duyệt n thuộc tính, với mỗi thuộc tính thực
hiện phép lấy bao đóng với độ phức tạp n
2
m. Tổng hợp lại, độ phức tạp tính toán của
thuật toán là O(n
3
m).
Ví dụ 1: 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 khoá của p.
Dễ thấy rằng, LĐQH p có khoá K = C, vì thoả mãn hai điều kiện:
(i) K
+
= C
+
= ABCDE = U
(ii) C tối tiểu ( theo nghĩa (K \ {C})
+
 U ).
Ví dụ 2: Cho P = (U,F), trong đó : U = ABCDE
F = { C  B
DE  AC
A  DE }

FRL
LRUM

 )\(\
.  Thuật toán xác định giao các khoá trong LĐQH
Algorithm KeyIntersec
Format: KeyIntersec(U,F)
Input: - Tập thuộc tính U
- Tập PTH F
Output: - Giao các khoá

FRL
LRUM

 )\(\

Method
M:=U;
For each FD LR in F do
M:=M\(R\L);
Endfor;
Return M;
End KeyIntersec.

1.6.2 Thuật toán tìm 2 khoá của LĐQH
Bước 1: Tính giao các khoá
Bước 2: Lấy M

 U
Nếu không có khoá thứ 2: 
Method M := U;
For each attribute A in K do
If A  (M\{A})
+
then
M := M \ {A}
Endif;
Endfor;
For each attribute A in U \ K do
If A  (M\{A})
+
then
M := M \ {A}
Endif;
Endfor;
If M = K then return 
Else return M;
Endif
End key 2.

Ví dụ: Cho LĐQH P = (U,F) trong đó: U = ABCDE
F = { BC  D
CD  A
D  E
A  B }

0
- E)
+
= U và D  E

Trích đoạn Thuật toán thu gọn LĐQH Định lý thiết lập công thức biểu diễn bao đóng

---