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