ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
KHOA HỆ THỐNG THÔNG TIN
Lớp: HTTT02
BÁO CÁO MÔN THIẾT KẾ CSDL
GIÁO VIÊN HƯỚNG DẪN:Phan Nguyễn Thụy An.
Trương Quang Khánh. MSSV: 07520175
Nguyễn Tùng Sơn. MSSV: 07520305
Lê Quốc Vương. MSSV: 07520423
TP.HCM, tháng 12 năm 2009
2
I. Các thuật toán cài cài đặt trong chương trình:
1. Cấu trúc dữ liệu:
Tất cả các thành phần AttSet (tập thuộc tính), AttSetList (danh sách các tập
thuộc tính), FD (phụ thuộc hàm), FDSet (danh sách các phụ thuộc hàm hay tập phụ
thuộc hàm) đều được tổ chức dưới dạng mảng Boolean với chiều dài tối đa là 255. Tất
cả các phép toán liên quan đến quan hệ như: hợp, trừ, giao, so sánh bằng, xét là con...
và các thuật toán đều được xây dựng dựa trên cấu trúc dữ liệu dạng này.
2. Các thuật toán:
2.1. Thuật toán tìm bao đóng:
+Input:
_Tập thuộc tính cần tìm bao đóng (a).
_Tập phụ thuộc hàm dựa trên đó để tìm bao đóng (fSet).
_Chuỗi string là chuỗi chứa tất cả các tập thuộc tính của quan hệ (u).
+Output:
_Tập thuộc tính bao đóng (X’).
Tên hàm xây dựng tương ứng: Public Function closure(ByVal a As
AttSet, ByVal fSet As FDSet, ByVal u As String) As AttSet
+Thuật toán:
_B1: Gán X’=A (với A là tập thuộc tính cần tìm bao đóng).
_B2:
3
Do { X=X’
Với mọi phụ thuộc hàm (PTH) p->q thuộc fSet
{If (p là con có thể bằng với X’)
X’=X’ hợp với {q}
}
}while(X’ không bằng U và X không bằng X’)
_B3: Trả về X’.
2.2. Thuật toán kiểm tra phụ thuộc hàm thành viên:
+Input:
_PTH cần kiểm tra thành viên (f).
_Tập PTH dựa trên đó để kiểm tra thành viên (fSet).
_Chuỗi string là chuỗi chứa tất cả các tập thuộc tính của quan hệ (u).
+Output:
_Giá trị True/False.
+Tên hàm xây dựng tương ứng: Public Function FDMember(ByVal f As
FD, ByVal fSet As FDSet, ByVal u As String) As Boolean
+Thuật toán:
_B1: Với mỗi PTH p->q trong fSet
{Nếu tồn tại p = vế trái của f và q = vế phải của f
Trả về True.
}
_B2: Nếu vế phải của f không thuộc tập u
4
Trả về False.
_B3: Đặt Temp = fSet – f
left = vế trái của f
right = vế phải của f
Nếu right là con của bao đóng của left dựa trên tập PTH Temp
Trả về True
Ngược lại
Trả về False
2.3. Thuật toán tìm khóa:
+Input:
_Tập PTH dựa trên đó để tìm khóa (fSet).
_Chuỗi string là chuỗi chứa tất cả các tập thuộc tính của quan hệ (u).
+Output:
_Danh sách các khóa của quan hệ (Key).
+Tên hàm xây dựng tương ứng: FindKey(ByVal fSet As FDSet, ByVal u
As String) As AttSetList
+Thuật toán:
_B1:
Gán các tập thuộc tính sau:
Trái: Tập chứa tất cả các thuộc tính nằm bên vế trái của tất cả các PTH trong fSet.
Phải: Tập chứa tất cả các thuộc tính nằm bên vế phải của tất cả các PTH trong fSet.
Gốc = Trái-phải
5
Treo = u-(Trái hội Phải)
Trung gian = Trái giao Phải
_B2:
Đặt danh sách khóa cần tìm là Key, khóa tạm thời là K, danh sách khóa tạm thời là
KeyTemp
_B3:
K = Gốc hội Treo
If bao đóng của K = u
Thêm K vào Key
Trả về Key
Ngược lại làm B4
_B4:
Tìm tất cả các tập con khác rỗng của tập Trung gian
Với mọi tập con a đó
{ If bao đóng của (a hội với K) = u
Thêm (a hội K) vào KeyTemp
}
_B5:
Với mỗi tập khóa sK đã thêm vào KeyTemp
{ If không tồn tại tập nào trong KeyTemp là con không bằng sK
Thêm sK vào Key
}