Download miễn phí Luận văn Ứng dụng phép dịch chuyển lược đồ quan hệ trong cơ sở dữ liệu



MỤC LỤC
LỜI NÓI ĐẦU 1
CHưƠNG 1. TỔNG QUAN VỀ ĐỀ TÀI VÀ CÁC KHÁI NIỆM CƠ SỞ 4
1.1. TỔNG QUAN VỀ ĐỀ TÀI 4
1.1.1. Giới thiệu đề tài. 4
1.1.2. Nội dung của đề tài, các vấn đề cần giải quyết. 4
1.1.3. Phương pháp nghiên cứu. 5
1.1.4. Phạm vi ứng dụng. 5
1.1.5. Kết quả đạt được. 5
1.2. CÁC KHÁI NIỆM CƠ SỞ 6
1.2.1. Quan hệ, thuộc tính, bộ. 7
1.2.2. Đại số quan hệ. 10
1.2.3. Phụ thuộc hàm, Hệ tiên đề Armstrong, Lược đồ quan hệ. 13
1.2.4. Bao đóng của tập thuộc tính. 18
1.2.5. Phủ của tập phụ thuộc hàm 21
1.2.6. Khóa của lược đồ quan hệ. 27
1.2.7. Chuẩn hoá LĐQH trên cơ sở phụ thuộc hàm. 31
CHưƠNG 2. PHÉP DỊCH CHUYỂN LưỢC ĐỒ QUAN HỆ 36
2.1. Phép dịch chuyển LĐQH. 37
2.2. Thuật toán dịch chuyển LĐQH. 38
2.3. Định lý cơ bản của phép dịch chuyển LĐQH. 39
2.4. Dạng biểu diễn thứ nhất của khóa 43
2.5. Dạng biểu diễn thứ hai của khóa 45
2.6. Kết luận 50
CHưƠNG 3. CÀI ĐẶT CHưƠNG TRÌNH 51
3.1. Giới thiệu. 51
3.2. Các chức năng của chương trình. 51
3.3. Một số giao diện của chương trình. 52
3.4. Các thí dụ. 54
DANH MỤC BÀI BÁO, CÔNG TRÌNH NCKH 57
KẾT LUẬN VÀ HưỚNG PHÁT TRIỂN 58
TÀI LIỆU THAM KHẢO 60


http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2013-10-26-luan_van_ung_dung_phep_dich_chuyen_luoc_do_quan_he.vJygZaTQIC.swf /tai-lieu/de-tai-ung-dung-tren-liketly-42374/
Để tải bản DOC Đầy Đủ 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:

Armstrong Ao [7]
B
o
= {F5, F10, F11}
S
o
= {F1, F4}
D
o
= {F3, F5, F6, F7}
M
o
= {F4, F5, F8}
1.2.4. Bao đóng của tập thuộc tính
Địn h n g h ĩ a
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 thuộc tính
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
_______________________________________________________
Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 19
X
+
= {A U | X  AF+}
Thuật toán tìm bao đóng của một 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.
Để xác định bao đóng X+ của tập thuộc tính X ta xây dựng dãy bao nhau
X
(0)
 X(1)  …  X(i) như sau
 Xuất phát: Đặt X(0)=X,
 Với i > 0, ta đặt

)(
)()1(
iXL
FRL
ii RXX


 
 Nếu X(i+1) = X(i) thì dừng thuật toán và cho kết quả X + = X(i) .
Algorithm Closure
Format: Closure(X,F)
Input: - Tập PTH F trên U
- Tập con thuộc tính X của U
Output: - Y = X+ = {A U | XA F+}
Method
Y:=X;
repeat
Z:=Y;
for each FD LR in F do
if L  Y then
Y:=YR;
endif;
endfor;
until Y=Z;
return Y;
end Closure.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
_______________________________________________________
Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 20
Thuật toán trên có độ phức tạp O(mn2 ), trong đó n là số lượng thuộc tính trong U,
m là số lượng PTH trong tập F.
Quy ước giản lược
Ta thường viết XY thay vì viết XYF+ hay F╞ XY.
Bài toán thành viê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 ?
Địn h l ý
(Định lý thành viên)
XY  F + khi và chỉ khi Y  X +
Thuật toán cho bài toán thành viên
Algorithm IsMember
Format: IsMember(f,F)
Input: - Tập PTH F trên U
- PTH f trên U
Output: - True, nếu f F+;
- False, trong trường hợp phủ định.
Method
IsMember := (RS(f)  Closure(LS(f),F));
end IsMember.
Một số tính chất của bao đóng
Cho LĐQH a = (U,F). Khi đó  X, Y  U ta có
(C1) Tính phản xạ: X  X +
(C2) Tính đồng biến: X  Y X + Y +
(C3) Tính lũy đẳng: (X +)+ = X +
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
_______________________________________________________
Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 21
Ngoài ra, sử dụng ba tính chất (C1), (C2) và (C3) nói trên ta dễ dàng chứng
minh các tính chất (C4)-(C8) sau đây:
(C4) (XY)
+
 X +Y +
(C5) (X
+
Y)
+
= (XY
+
)
+
= ( XY)
+
(C6) XY khi và chỉ khi Y+ X+
(C7) XX+ và X+X
(C8) X
+
= Y
+
khi và chỉ khi XY và YX
1.2.5. Phủ của tập PTH
Địn h n g h ĩ a
Cho hai tập PTH F và G trên cùng một tập thuộc tính U. Ta nói F suy dẫn ra
được G, ký hiệu F╞ G, nếu gG: F╞ g. Ta nói F tương đương với G, ký
hiệu F  G, nếu F╞ G và G╞ F.
Nếu F  G ta nói G là một phủ của F.
Ký hiệu F ≢ G có nghĩa 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
XF
+
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.
Phủ thu gọn tự nhiên
Địn h n g h ĩ a
Cho hai tập PTH F và G trên cùng một tập thuộc tính U. G là phủ thu gọn tự
nhiên của F nếu
1. G là một phủ của F, và
2. G có dạng thu gọn tự nhiên theo nghĩa sau:
2a. 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) = 
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
_______________________________________________________
Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 22
2b. 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
Algorithm Natural_Reduced
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)LiRi,LjRjG: ij  LiLj
Method
G:=;
for each FD LR in F do
Z:=R\L;
if Z then
if there is an FD LY in G then
replace LY in G by LYZ
else add LZ to G;
endif;
endif;
endfor;
return G;
end Natural_Reduced.
Nếu dùng kỹ thuật chỉ dẫn để tổ chức truy nhập trực tiếp tới các thuộc tính và
PTH thì thuật toán thu gọn tự nhiên Natural_Reduced đòi hỏi độ phức tạp tính toán
là O(mn) trong đó m là số lượng PTH trong tập F, n là số lượng thuộc tính trong U.
Để ý rằng mn là chiều dài dữ liệu vào của thuật toán, do đó O(mn) chính là độ phức
tạp tuyến tính theo chiều dài dữ liệu vào.
Ta dễ dàng chứng minh tính đúng của mệnh đề sau,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
_______________________________________________________
Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 23
Mệnh đ ề
Nếu F và G là hai tập PTH trên cùng một tập thuộc tính U thì F  G khi và chỉ
khi X  U: XF
+
= XG
+
Phủ không dư
Địn h n g h ĩ a
Cho hai tập PTH F và G trên tập thuộc tính U. G được gọi là phủ không dư
của F nếu
(i) G là một phủ của F, và
(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
Algorithm Nonredundant
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
G:=F;
for each FD g in F do
if IsMember(g,G\{g})then
G:=G\{g};
endif;
endfor;
return G;
end Nonredundant.
Phủ thu gọn
Phủ thu gọn trái
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
_______________________________________________________
Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 24
Địn h n g h ĩ a
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 trái
của F nếu
(i) G là một phủ của F, và
(ii) (LRG,AL): G\{LR}{L\AR} ≢ G
Thuật toán tìm phủ thu gọn trái của tập PTH
Để ý rằng AL ta có L\A L, nên
g: LRG,AL): G\{g}{L\AR}╞ LR,
do đó ta chỉ cần kiểm tra G ╞ L\AR ?
Algorithm Left_Reduced
Format: Left_Reduced(F)
Input: - Tập PTH 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
G:= F;
for each FD g:L  R in F do
X:=L;
for each attribute A in X do
if IsMember(L\AR,G)then
delete A from L in G;
endif;
endfor;
endfor;
return G;
end Left_Reduced.
Phủ thu gọn phải
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
_______________________________________________________
Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 25
Địn h n g h ĩ a
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
Để ý rằng, AR: R\A R, nên (g: LRG,AR): G╞ LR\A
do đó ta chỉ cần kiểm tra G\{LR}{LR\A}╞ LA.
Algorithm Right_Reduced
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
G:= F;
for each FD g:L  R in F do
H:=G\{LR};
X:=R;
for each attribute A in X do
if A in Closure(L,H{LR\A})then
delete A from R in G;
endif;
endfor;
endfor;
return G;
e...

---