CÀI ĐẶT CHƯƠNG TRÌNH

CHƯƠNG 3.

3.1. Giới thiệu.

Chương trình được được xây dựng trên nền DEV - C++ để mô phỏng phép giản lược lược đồ quan hệ và các thuật toán tìm bao đóng theo tiếp cận giản lược, thuật toán tìm cơ sở theo tiếp cận giản lược.

3.2. Các chức năng chính của chương trình:

" Tên chương trình "Thu gọn lược đồ quan hệ" có các chức năng chính sau:

1. Tính bao đóng

2. Tìm cơ sở 2

3. Thu gọn lược đồ

0. Thoát khỏi chương trình

" Chương trình áp dụng một số thuật toán sau:

- Thuật toán tính bao đóng.

Algorithm Closure

Input:- Tập thuộc tính X ⊂ U

- Tập PTH F

Output: 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 ;

Enddif ;

Endfor ;

Until Y: = Z;

Return Y;

End Closure.

- Thuật toán tìm cơ sở theo tiếp cận giản lược.

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

Function: Tìm một cơ sở của LĐQH

Input: - Tập thuộc tính U

- Tập PTH F

Output: Cơ sở B ⊂ U thoả

i) B⁺ = U

ii) A⊆B : (B{A})⁺ ≃ U

Method

B := U;

For each attribute A in U do

If A ⊆ (B{A})⁺ then

B := B {A}

Endif;

Endfor;

Return B;

End Base.

- Thuật toán giản lược lược đồ

Input: - LĐQH p = (U,F)

- Tập thuộc tính M ⊂U

Output:

- LĐQH q = (V,G) = pM, V = UM, G = FM.

Method

V := UM;

G := ⊕

For each FD L↑R in F do

G := G ∩ {LM↑RM};

Endfor;

G := Natural_Reduced(G);

Return (V,G);

End Translation.

Thủ tục Natural_Reduced(G) đưa tập PTH G về dạng thu gọn tự nhiên bằng cách loại khỏi G những PTH tầm thường (có vế trái chứa vế phải), chuyển đổi mỗi PTH có hai vế trái phải rời nhau và gộp các PTH có cùng vế trái.

3.3. Giao diện chương trình.

Chương trình cài đặt mô phỏng các ví dụ giản lược lược đồ quan hệ, tìm bao đóng theo tiếp cận giản lược, tìm cơ sở theo tiếp cận giản lược trên nền ngôn ngữ lập trình DEV - C++.

Hình 3.1 Giao diện chính của chương trình

Đây là giao diện của chương trình gồm các thành phần chính sau:

- Tên chương trình " THU GON LUOC ĐO QUAN HE"

- Tên tác giả chương trình

- Go: Người dùng nhập tên file và Enter

Test tệp luocdo1:Cho LĐQH p = (U,F) trong đó: U = ABCDE

F = {BC → size 12{ rightarrow } {} D

CD → size 12{ rightarrow } {} A

D → size 12{ rightarrow } {} E

A → size 12{ rightarrow } {} B}

a. Thu gọn p để được q=(V,G) theo thuộc tính X=BD

b. Tính (AC)⁺

c. Tìm cơ sở 1 của p

d. p có còn cơ sở nào khác ngoài cơ sở 1 không ? Vì sao ?

Giải

a. Thu gọn p để được q=(V,G) theo thuộc tính X=BD

V = UX = ABCDEBD = ACE

G = FX = {C → size 12{ rightarrow } {} ⊕ (loại), C → size 12{ rightarrow } {} A, ⊕ → size 12{ rightarrow } {} E, A → size 12{ rightarrow } {} ⊕ (loại)}

q = (V, G), V = ACE

G = {C → size 12{ rightarrow } {} A,

⊕ → size 12{ rightarrow } {} E}

b. Tính (AC)⁺

X₀ = AC

X ₁ = ACB (vì A → size 12{ rightarrow } {} B)

X ₂ = ACBD (vì CB → size 12{ rightarrow } {} D)

X ₃ = ACBDE (vì D → size 12{ rightarrow } {} E)

Vậy (AC)⁺ = ABCDE

c. Tìm cơ sở 1củ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 bằng cách gạch dưới ví dụ: A'.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	D	E
DE (thử loại bỏ C)				D	E
CE (thử loại bỏ D)			C		E
CD (thử loại bỏ E)	A	B	C	D	E

Nhìn vào bảng trên ta thấy thử loại bỏ C, D và bao đóng thuộc tính còn lại size 12{ <> } {} U

Vậy cơ sở 1 của p là: CD

d. P còn cơ sở khác ngoài cơ sở 1?

U_I = Uvế phải của F = ABCDE – ABDE = C

M ⁺ = C ⁺ = C size 12{ <> } {} U nên lược đồ có hơn một cơ sở.

Vậy ngoài cơ sở B₁, lược đồ còn có cơ sở B₂ = 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}) ⁺ size 12{ <> } {} U ).

ζ Dữ liệu đưa vào chương trình được mã hóa như sau:

File: luocdo1
Mô tả	Chú thích
5	// có 5 thuộc tính
A	A // 1
B	B // 2
C	C // 3
D	D // 4
E	E // 5
4	// Có 4 phụ thuộc hàm
2 3 -> 4	2 3 -> 4 // BC ->D
3 4 -> 1	3 4-> 1 // C D -> A
4 -> 5	4 -> 5 // D -> E
1 -> 2	4 -> 1 // A -> B

Sau khi người dùng nhập tên file và Enter chương trình sẽ thực hiện đưa ra kết quả như hình 3.2

- In ra số thuộc tính của file, gồm 5 thuộc tính

- In ra mã số (1..5) tương ứng với các thuộc tính

- In ra số phụ thuộc hàm, gồm 5 phụ thuộc hàm và mã (F1..F5) phụ thuộc hàm tương ứng

- Tìm được cơ sở thứ nhất của lược đồ quan hệ là CD

Hình 3.2 In số thuộc tính, phụ thuộc hàm trong tệp ld1 và tìm cơ sở 1

Sau đó ấn phím bất kì chương trình trở về menu chính

ζ Chức năng của các mục trong menu

- Chọn 1. Tính bao đóng

Hình 3.3 Tính bao đóng của mã số 1 3 (A, C)

Chọn 1 tính bao đóng chương trình yêu cầu người sử dụng nhập vào để tính.

Ví dụ ta nhập mã số 1 3 (A C) như hình 3.3 chương trình cho kết quả là:

- Mã số cần tính là 1 3 (A C)

- Kết quả tính được là 1 2 3 4 5 (A B C D E)

- Chọn 2. Tìm cơ sở 2

Khi người sử dụng chọn 2 để tìm cơ sở 2 chương trình tự động tìm và đưa ra kết quả như hình 3.4

Hình 3.4 Tìm cơ sở 2

- Chọn 3. Thu gọn lược đồ

Chương trình yêu cầu người sử dụng nhập vào mã số các thuộc tính thu gọn. Ví dụ ta nhập vào mã số 2 4 ( B D) như hình 3.5. Chương trình in ra kết quả:

+ Số thuộc tính 3 (1 3 5 tương đương A C E)

+ Số phụ thuộc hàm 2 {C↑A, ⊕↑E}

+ Tìm được cơ sở 1 là C

Hình 3.5 Thu gon lược đồ

- Chọn 0. Thoát khỏi chương trình.

Hình 3.6 Thoát khỏi chương trình

Test tệp luocdo2:Cho LĐQH p = (U,F)

U = ABCDEH

F={ AE ↑ D,

A ↑ DH,

BC ↑ E,

E ↑ BC}

a. Với M = ADH, xác định q = (V,G) = pM?

Tính V = UM = ABCDEHADH = BCE

Tính G = FM = {E ↑ ⊕ (loại),

⊕ ↑ ⊕ (loại),

BC ↑ E,

E ↑ BC}

Lược đồ quan hệ q = (V,G) trong đó:

V = BCE

G = {BC ↑ E,

E ↑ BC}

b. Tính (CE)⁺

X₀ = CE

X₁ = CEB (vì E ↑ BC)

Vậy (CE)⁺ = BCE

c. Tìm một cơ sở 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 đó. 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 bằng cách gạch dưới B'.Những thuộc tính không loại được thì tô đậm.

Base (B)	A'	B '	C '	D '	E'	H'
BCDEH (thử loại bỏ A)		B	C	D	E	H
ACDEH (thử loại bỏ B)	A	B	C	D	E	H
ADEH (thử loại bỏ C)	A	B	C	D	E	H
AEH (thử loại bỏ D)	A	B	C	D	E	H
AH (thử loại bỏ E)	A			D		H
AE (thử loại bỏ H)	A	B	C	D	E	H

Vậy cơ sở 1 của p là AE

d. p có còn cơ sở nào khác ngoài cơ sở 1 không ? Vì sao ?

U_I = Uvế phải của F = ABCDEH –BCDEH = A

A ⁺ = ADH size 12{ <> } {} U nên lược đồ có hơn một cơ sở.

Vậy ngoài cơ sở 1, lược đồ còn có cơ sở 2 là ABC vì thoả 2 điều kiện sau:

(i) B⁺ = (ABC)⁺ = ABCDE = U

(ii) BC tối tiểu ( theo nghĩa (B {BC}) ⁺ size 12{ <> } {} U ).

ζ Dữ liệu được mã hóa khi nạp vào chương trình như sau:

File: luocdo2
Mô tả	Chú thích
6	// có 6 thuộc tính
A	A // 1
B	B // 2
C	C // 3
D	D // 4
E	E // 5
H	H // 6
4	// 4 Phụ thuộc hàm
15 -> 4	15 -> 4 // AE -> D
1 -> 4 6	1 -> 4 6 // A -> DH
2 3 -> 5	2 3 -> 5 // BC -> E
5 -> 2 3	5 -> 2 3 // E -> BC

Sau khi nhập file luocdo2 ấn Enter chương trình đưa ra kết quả như hình 3.7 gồm:

- Số thuộc tính của LĐQH là 6 và mã số tương ứng với các thuộc tính.

- Số phụ thuộc hàm là 4 và mã số tương ứng với các PTH

- Tìm được cơ sở 1 là AE

Hình 3.7 In số thuộc tính, phụ thuộc hàm trong tệp luocdo2 và tìm cơ sở 1

- Chọn 1 tính bao đóng: chương trình yêu cầu người sử dụng nhập mã số các thuộc tính để tính. Ví dụ nhập 3 5 (C E) chương trình đưa ra kết quả như hình 3.8

Hình 3.8 Tính bao đóng mã số thuộc tính 3 và 5

- Chọn 2 tìm cơ sở 2 chương trình tìm trên LĐQH p đưa ra kết quả như hình 3.9

Hình 3.9 Tìm cơ sở 2

Hình 3.10 Thu gọn lược đồ với mã số thuộc tính 1 4 6 (ADH)

Chọn 3 thu gọn lược đồ, chương trình yêu cầu nhập mã số thuộc tính để thu gọn. Ví dụ: nhập 1 4 6 (A D H) chương trình đưa ra kết quả như hình 3.10

V = BCE

G = {BC Γ E, E Γ BC}

Tìm được cơ sở của lược đồ thu gọn là E.

KẾT LUẬN VÀ ĐỀ NGHỊ

1. Kết luận

Những nội dung chính đã được giải quyết trong luận văn:

- Lý thuyết:

+ Trình bày tổng quát hóa về lý thuyết cơ sở dữ liệu.

+ Tìm hiểu và trình bày các định nghĩa cơ sở; các tính chất.

+ Thuật toán thu gọn lược đồ quan hệ

+ Thuật toán tìm cơ sở.

+ Thuật toán tính bao đóng.

- Thực nghiệm:

+ Xây dựng hệ thống thí dụ để ứng dụng.

+ Cài đặt chương trình để kiểm thử và đánh giá các kết quả.

2. Đề nghị

- Xây dựng các tập thuộc tính, phụ thuộc hàm, áp dụng thuật toán để giải quyết các bài toán về cơ sở dữ liệu.

- Ứng dụng chương trình để hỗ trợ cho sinh viên thực hành về cơ sở dữ liệu, sau đó kiểm tra kết quả tính bao đóng, tìm cơ sở và thu gọn lược đồ quan hệ.

- Tiếp tục và hoàn thiện phần mềm với chức năng, giao diện thuận lợi cho người sử dụng.