Thu gọn lược đồ quan hệ và ứng dụng

[Thornton]

Download miễn phí Luận văn Thu gọn lược đồ quan hệ và ứng dụng

MỤCLỤC
Trang
Trang phụ bìa . . . .
Lời cam đoan. . . .
Lời Thank . . . .
Mục lục . . . . i
Danh mục các ký hiệu, chữ cái viết tắt . . ii
Danh mục hìnhvẽ . . . iii
MỞ ĐẦU . . . . 1
Chương 1
CÁC KIẾN THỨC CƠ BẢN VỀ CƠ SỞ DỮ LIỆU
1.1. Khái quát về cơ sở dữ liệu . . . 2
1.2. Phụ thuộc hàm . . . 3
1.3. Lược đồ quan hệ . . . 7
1.4. Bao đóng của tập thuộc tính. . . 7
1.5. Phủ của tập phụ thuộc hàm . . . 9
1.6. Khoá của lược đồ quan hệ. . . 14
1.7. Chuẩn hoá LĐQH trên cơ sở PTH . . 20
Chương 2
KỸ THUẬT THU GỌN LƯỢC ĐỒ QUAN HỆ
2.1. Địnhnghĩa kỹ thuật thu gọn LĐQH . . 25
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


http://cloud.liketly.com/flash/edoc/-images-nopreview.swf /tai-lieu/de-tai-ung-dung-tren-liketly-53846/
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí

Tóm tắt nội dung tài liệu:

F
Output: - Một phủ thu gọn trái G của F
i) GF
ii) g: LR  G, A L: G\{g}{L\{A}R} ! 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 := L;
For each attribute A in X do
If R Closure (U, G, L\{A}R) then
Delete A from L in G;
Endif
Endfor
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;
If R =  then
Delete LR from G;
Endif;
Endfor;
Return G;
End Right_Reduced.
1.5.4 Phủ tối tiểu
Cho hai tập F và G trên tập thuộc tính U. G được gọi là phủ tối tiểu của F nếu :
i) G là một phủ của F
ii) Vế phải của PTH trong G chỉ chứa một thuộc tính.
 Thuật toán tìm phủ tối tiểu của tập PTH
Algorithm MinCover
Function: Tính phủ tối tiểu của tập PTH
Format: MinCover (F)
Input: - Tập PTH F
Output: - Một phủ tối tiểu G của F
Method
// Tách mỗi PTH LR trong F thành các PTH LA, AR
G := ;
For each FD LR in F do
For each attribute A in R\L do
If LA not_in G then
Add LA to G;
Endif;
Endfor;
Endfor;
G := Reduced (G);
Return G;
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 hay 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
hay thứ cấp) nếu A không có mặt trong bất kỳ khóa nào. Ký hiệu UK là tập các thuộc
tính khóa của LĐQH p và U0 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
thuộc tính A của K, nếu bất biến (K\{A})+ = U được bảo toàn thì A loại khỏi K. Có thể
thay kiểm tra (K\{A})+ = U bằng kiểm tra A  (K\{A})+ .
Algorithm Key
Function: Tìm một khoá của LĐQH
Format: Key (U,F)
Input: - Tập thuộc tính U
- Tập PTH F
Output: Khoá K  U thoả
i) K+ = U
ii) AK : (K\{A})+  U
Method
K := U;
For each attribute A in U do
If A  (K\{A})+ then
K := K \ {A}
Endif;
Endfor;
Return K;
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 n2m. Tổng hợp lại, độ phức tạp tính toán của
thuật toán là O(n3m).
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 }
Tìm khoá của LĐQH đã cho ?
Ta thấy, LĐQH P có khoá K = A, vì thoả mãn 2 điều kiện :
(i) K+ = A+ = ABCDE = U
(ii) A tối tiểu ( theo nghĩa (K \ {A})+  U ).
Mặt khác, tương tự như trên, ta cũng dễ thấy rằng LĐQH P còn khoá thứ 2, đó là K =
DE.
Để trả lời cho câu hỏi: Lược đồ có trên một khoá hay không, ta đi tìm giao các khoá.
1.6.1 Cách tính giao các khoá
Những phần tử không xuất hiện ở vế phải thì nó có mặt ở mọi khoá, đó chính là
giao các khoá.
Vậy giao các khoá chính là những thuộc tính không xuất hiện ở vế phải.
Giả sử M là giao các khoá. Nếu M+ = U thì lược đồ chỉ có đúng 1 khoá, nếu M+ 
U thì lược đồ có trên 1 khoá.
Gọi M là giao các khoá khi và chỉ khi : M+ = U.
Cho LĐQH p = (U,F) với n thuộc tính trong U và m PTH trong F. Gọi M là giao
các khoá của p. Khi đó có thể xác định giao các khoá bằng một thuật toán tuyến tính
theo mn qua công thức: 
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+. Nếu M+ = U  Lược đồ có 1 khoá M là duy nhất
M+  U  Lược đồ có trên 1 khoá
Gọi thuật toán Key – Tìm khoá 1
Gọi thuật toán Key 2 – Tìm khoá 2
Tư tưởng: Xuất phát từ tập thuộc tính M = U, trước hết duyệt các thuộc tính A của
K, nếu bất biến (M\{A})+ = 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\K.
Algorithm Key 2
Function: Tìm một khoá thứ 2 của LĐQH
Format: Key 2 (U,F)
Input: - Tập thuộc tính U
- Tập PTH F
- Khoá K  U
Output: Khoá thứ hai, nếu có, M  U thoả
i) M+ = U
ii) AM : (M\{A})+  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 }
a. Hãy xác định phần giao của các khoá trong P
b. Tìm một khoá K1 của P
c. P có còn khoá nào khác ngoài K1 không ? Vì sao ?
d. Xác định tập các thuộc tính không khoá U0 của P
Giải
a. Xác định phần giao của các khoá trong P
Theo công thức, ta có: 
FRL
LRUM

 )\(\ = ABCDE – ABDE = C
b. Tìm một khoá K1 của P
Đặt K0 = U = ABCDE
K1 = K0 – E = ABCD vì (K0 - E)+ = U và D E
K2 = K1 – D = ABC vì (K1 - D)+ = U và BC D
K3 = K2 = ABC vì (K2 - C)+  U
K4 = K3 – B = AC vì (K3 - B)+ = U và A B
K5 = K4 = AC vì (K4 - A)+  U
Vậy khoá K1 của P là AC.
c. P còn khoá khác ngoài khoá K1 vì:
M+ = C+ = C  U nên lược đồ có hơn một khoá.
Dễ thấy rằng, ngoài khoá K1, lược đồ còn có khoá K2 = BC vì thoả mãn 2 điều kiện
sau:
(i) K+ = BC+ = ABCDE = U
(ii) BC tối tiểu ( theo nghĩa (K \ {BC})+  U ).
Tương tự, ta còn tìm được khoá thứ 3 của lược đồ quan hệ P như sau: K3 = CD.
d. Xác định tập các thuộc tính không khoá U0
của P.
- Thuộc tính khoá là thuộc tính có mặt trong mọi khoá, ký hiệu là Uk.
- Thuộc tính không khoá là thuộc tính không có mặt trong bất cứ khoá nào, ký hiệu U0.
Ta có: Uk = ABCD,  U0 = E.
1.7 Chuẩn hóa LĐQH trên cơ sở PTH
1.7.1 Các dạng chuẩn
a. Dạng chuẩn 1 (1NF)
LĐQH p = (U,F) được gọi là lược đồ ở dạng chuẩn 1 (1NF) nếu mọi thuộc tính
trong U đều không phải là thuộc tính phức hợp (điều n...