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.
AMBIENT/
Chủ đề:
Nội dung Text: Báo cáo môn: Thiết kế cơ sở dữ liêu
- ĐẠ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
}
- 6
Trả về Key
2.4. Thuật toán tìm một phủ tối tiểu:
+Input:
_Tập PTH dựa trên đó để tìm 1 phủ tối tiểu (PTT) cho 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:
_1 PTT tìm được.
+Tên hàm xây dựng tương ứng: Public Function MinimalCover(ByVal
fset As FDSet, ByVal u As String) As FDSet
+Thuật toán:
_B1:
Với mỗi PTH f trong fSet, tách vế phải của f về dạng vế phải chỉ chứa 1 thuộc tính
_B2: Loại bỏ PTH dư thừa:
Với mỗi PTH f trong tập PTH fSet vừa thực hiện trong B1.
{ Đặt fTemp = fSet-f, left là vế trái của f, right là vế phải của f.
Nếu right là con của (bao đóng của left dựa trên fTemp) thì f là PTH dư thừa
Loại bỏ f khỏi fSet
}
_B3: Loại bỏ PTH không đầy đủ:
Với mỗi PTH f mà vế trái của f có nhiều hơn 2 thuộc tính trong tập PTH fSet vừa thực
hiện trong B2.
{ Đặt fTemp = fSet-f, left là vế trái của f.
- 7
Với mỗi thuộc tính a trong left
{ Đặt sleft = left -a
If a là con của (bao đóng của sleft dựa trên fTemp)
Loại a khỏi left
}
}
_B4 : Lặp lại B2 để loại bỏ dư thừa trong trường hợp B3 sinh ra PTH dư thừa
_B5 : Gom những PTH có vế trái như nhau để thu gọn tập PTH
2.5. Thuật toán kiểm tra dạng chuẩn 2:
+Input:
_Tập PTH dựa trên đó để kiểm tra dạng chuẩn (fSet).
_Danh sách các khóa của quan hệ (key).
_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 twoNF(ByVal fSet As
FDSet, ByVal key As AttSetList, ByVal u As String) As Boolean
+Thuật toán:
_B1:
Đặt nK là tập thuộc tính chứa các thuộc tính không là khóa của quan hệ.
Với mỗi khóa K trong danh sách khóa (key) của quan hệ
{
- 8
Tìm bao đóng của tất cả các tập con thật sự (con không bằng) của K
}
_B2:
Với mội bao đóng S+ tìm được ở B1
{
Với mội thuộc tính a thuộc nK
{
If a là con của S+
Trả về False
}
}
Trả về True
2.6. Thuật toán kiểm tra dạng chuẩn 3:
+Input:
_Tập PTH dựa trên đó để kiểm tra dạng chuẩn (fSet).
_Danh sách các khóa của qun hệ (key).
+Output:
_Giá trị True/False.
+Tên hàm xây dựng tương ứng: Public Function ThreeNF(ByVal fset
As FDSet, ByVal key As AttSetList) As Boolean
+Thuật toán:
Với mỗi PTH f trong fSet
- 9
{
Đặt left = vế trái của f, right = vế phải của f
Với mỗi tập khóa k trong key
{
If k là con left hoặc right là con k
Return True
}
}
Return False
2.7. Thuật toán kiểm tra dạng chuẩn BC:
+Input:
_Tập PTH dựa trên đó để kiểm tra dạng chuẩn (fSet).
_Danh sách các khóa của qun hệ (key).
+Output:
_Giá trị True/False.
+Tên hàm xây dựng tương ứng: Public Function BC(ByVal fset As
FDSet, ByVal key As AttSetList) As Boolean
+Thuật toán:
Với mỗi PTH f trong fSet
{
Đặt left = vế trái của f.
Với mỗi tập khóa k trong key
- 10
{
If k là con left
Return True
}
}
Return False
2.8. Thuật toán phân rã quan hệ thành các quan hệ đạt dạng chuẩn 3, bảo toàn
PTH và bảo toàn thông tin:
+Input:
_Tập PTH (fset) dựa trên đó để phân rã.
_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:
_1 Tập các thuộc tính của các phân rã tìm được.
_Tên hàm xây dựng tương ứng: Public Function
Decomposition3NF(ByVal fset As FDSet, ByVal u As String)
As AttSetList
+Thuật toán:
_B1: Tìm phủ tối tiểu(PTT) của fset.Các bước sau sẽ dựa trên PTT của fset
_B2: Nếu có một phụ thuôc hàm(FD) trong fset chứa u thì trả về u
_B3 :Tìm các thuộc tính treo, mỗi thuộc tính tạo thành một quan hệ
_B4:Với các FD trong PTT có cùng vế trái tạo thành một quan hệ.
_B5:Tìm khóa . Những mỗi khóa chưa thuộc một quan hệ nào sẽ tạo thành một quan
hệ
- 11
2.9. Thuật toán phân rã quan hệ thành các quan hệ đạt dạng chuẩn BC và bảo toàn
thông tin:
+Input:
_Tập PTH (fset) dựa trên đó để phân rã.
_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:
_1 Tập các thuộc tính của các phân rã tìm được.
_Tên hàm xây dựng tương ứng: Public Function
DecompositionBCNF(ByVal fset As FDSet, ByVal u As String)
As AttSetList
+Thuật toán:
_B1:
Tìm FD trong fset vi phạm điều kiện BC.
Tách thành một quan hệ.Loại khỏi u các thuộc tính của FD vi phạm
Đánh dấu những FD ( sẽ không xét đến trong các lần sau)có chứa thuộc tính vế
phải của FD đã tách thành 1 quan hệ
Lặp lại các bước trên cho đến khi tất cả các FD trong fset đã được đánh dấu. Lưu ý
các FD được tách ra không loại bỏ fset, fset sẽ được dùng đến trong B2
Nếu U khác rỗng thì sang bước 2
_B2:
X U ( còn lại sau B2)
IF X+ X and X+ U then
X ->( (X+ - X) U) vi phạm BC
- 12
U = U – ((X+ - X) U)
Tạo một quan hệ mới gồm X, (X+ - X) U
Cuối
If U then tạo một quan hệ gồm các thuộc tính còn lại của U
2.10. Thuật toán kiểm tra bảo toàn phụ thuộc hàm sau khi phân rã:
+Input:
_Tập PTH dựa trên đó để kiểm tra (fSet).
_.Tập các thuộc tính của các quan hệ được phân rã(R)
_Chuỗi string chứa tất cả các 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
PreserveDependency(ByVal fset As FDSet, ByVal R As
AttSetList, ByVal u As String) As Boolean
+Thuật toán:
X -> Y fset
A=X
For each Ri R
T = (A Ri)+ Ri
A=A T
Cuối For each
- 13
If Y A then
Return false
Cuối
Return true
II. Cách ghi một file txt để load trong chương trình:
Cách 1:
ABCDEFGH;
A->B;
C->D;
E->F;
...;
ABC->G;
Cách 2:
ABCDEFGH;
A->B;C->D;E->F;...;BC->G;
III. Phân công công việc:
1. Trương Quang Khánh:
_Cài đặt cấu trúc dữ liệu cho 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) và các xử lý liên quan (các phép toán cơ bản cần thiết khi thao
tác trên tập thuộc tính: hội, giao, hợp, trừ, là con...)
_Nghiên cứu và cài đặt thuật toán tìm các tập con khác rỗng của 1 tập thuộc tính.
_Nghiên cứu và cài đặt thuật toán tìm khóa.
- 14
_Nghiên cứu và cài đặt thuật toán tìm phủ tối tiểu.
_Nghiên cứu và cài đặt thuật toán phân rã quan hệ thành dạng chuẩn 3 và BC.
_Nghiên cứu và cài đặt thuật toán kiểm tra bảo toàn phụ thuộc hàm.
2.Nguyễn Tùng Sơn:
_Nghiên cứu thuật toán và cấu trúc dữ liệu.
_Nghiên cứu và cài đặt thuật toán tìm khóa.
_Nghiên cứu và cài đặt thuật toán tìm bao đóng.
_Cài đặt giao diện.
_Viết báo cáo.
3.Lê Quốc Vương:
_Cài đặt cấu trúc dữ liệu cho các thành phần: FD (phụ thuộc hàm), FDSet(danh sách
các phụ thuộc hàm) và các xử lý liên quan (các phương thức cơ bản cần thiết khi thao
tác trên phụ thuộc hàm: trừ, lấy giá trị, xuất ra chuỗi...)
_Nghiên cứu và cài đặt thuật toán tìm bao đóng.
_Nghiên cứu và cài đặt thuật toán kiểm tra phụ thuộc hàm thành viên.
_Nghiên cứu và cài đặt thuật toán tìm khóa.
_Nghiên cứu và cài đặt thuật toán xác định dạng chuẩn.
_Cài đặt việc nhập/xuất dữ liệu từ file.
- 15
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
