Đề tài Nghiên cứu, tìm hiểu và nắm rõ các yêu cầu cũng như thuật toán để thiết kế được những cơ sở dữ liệu hoạt động hiệu quả

ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN KHOA CÔNG NGHỆ PHẦN MỀM THIẾT KẾ CƠ SỞ DỮ LIỆU Nhóm 21: +Đoàn Đình Phúc 07520278 +Nguyễn Quốc Huy 05720546 Hồ Chí Minh – 1/2010 2 I. Giới thiệu thông tin chung: I.1. Thông tin nhóm thực hiện:  Nhóm 21  Thành viên: o Đoàn Đình Phúc MSSV: 07520278 o Nguyễn Quốc Huy MSSV: 07520546 I.2. Mục tiêu của đồ án: Nhằm nghiên cứu, tìm hiểu và nắm rõ các yêu cầu cũng như thuật toán để thiết kế được những cơ sở dữ liệu hoạt động hiệu quả. I.3. Kết quả đạt được của nhóm: Thiết lập được 1 chương trình với các chức năng cơ bản đáp ứng nhu cầu hỗ trợ việc học tập cũng như sử dụng thiết kế cơ sở dữ liệu. 3 II. Các thuật toán chính đã sử dụng: II.1. Thuật toán danh sách các tập con của 1 tập thuộc tính  Ý tưởng:  Ý tưởng 1: Gọi {Un-1} danh sách tập con của tập n-1 thuộc tính, {Un + n } là danh sách tập hợp được tạo bằng cách thêm thuộc tính thứ n vào tất cả tập hợp của {Un} và {n} là tập hợp chỉ chứa 1 thuộc tính thứ n o {Un+1} = {Un} + {Un + n} + {n}  Ý tưởng 2: Số tập con khác rỗng của 1 tập có n thuộc tính đúng bằng 2^n - 1. Sử dụng mảng 1 chiều có n phần tử để biểu diễn 1 số nhị nhân có giá trị thập phân tương ứng từ 1 đến 2^n -1. Với mỗi số nhị phân thu được, ánh xạ thành tập thuộc tính với quy ước 1 là có, 0 là không có thuộc tinh đó  Lựa chọn: Dựa trên việc test thử nghiệm theo câu trúc của chương trình, nhóm quyết đinh chọn ý tưởng thứ hai vì tốc độ xử lí nhanh hơn 60 – 70%  Thuật toán: o B1: Bắt đầu  Nhận tập thuộc tính đầu vào có n thuộc tính  Tạo mảng 1 chiều Bin có n phần tử kiểu dữ liệu logic (boolean) mặc định là false o B2:Lặp lại B3, B4 2^n -1 lần o B3: Tăng giá trị của số nhị phân mảng biểu diễn lên 1 đơn vị o B4: Ánh xa theo mảng nhị phân để nhận được tập thuộc tính tương ứng. Thêm vào danh sách kết quả 4 o B5: Sắp xếp lại danh sách kết quả o B6: Trả về danh sách kết quả o B7: Kết thúc  Đoạn chương trình: ''' ''' Return an AttSetList contains all not-null subsets of X ''' Public Shared Function SubSets(ByVal X As AttSet) As AttSetList 'DS KQ Dim result As New AttSetList 'So lan lap se thuc hien Dim Times As Integer = 2 ^ X.Count - 1 'Mang nhi phan Dim Bin(X.numAtt) As Boolean 'Vong lap chay 2^n - 1 lan For index As Integer = 1 To Times 'Tap thuoc tinh de luu 1 tap con Dim tmpAttSet As New AttSet 'Tang gia tri mang nhi phan len 1 tinh tu vi tri dau ChangeNext(Bin, 0) 'Bat dau ânh xa mang thanh tap thuoc tinh tuong ung For index1 As Integer = 0 To X.Count - 1 'Neu la tru thi them thuoc tinh o vi tri tuong ung vao tap con hien tai If Bin(index1) = True Then tmpAttSet.AddAtt(X.Items(index1)) End If Next 'Them tap con vua tim dc vao kq result.AddNewSet(tmpAttSet) Next 'KQ Return result End Function 'Ham tang gia tri mang nhi phan len 1 Private Shared Sub ChangeNext(ByRef Bin As Boolean(), ByVal index As Integer) Bin(index) = Not Bin(index) If Bin(index) = False Then ChangeNext(Bin, index + 1) End If 5 End Sub  Hoạt động: o Chạy tốt với những tập thuôc tính ít hơn 12 phần tử, đối với trương hợp 12 thuộc tính thì mất khoảng 15s (theo tốc độ máy của nhóm). Nguyên nhân 1 phần là do ảnh hưởng của cấu trúc dữ liệu lưu trữ. o Kết quả trả về không được sắp xếp, nên trong 1 số trường hợp phải sắp xếp lại bằng 1 hàm khác. II.2. Thuật toán tìm bao đóng của 1 tập thuộc tính trong 1 lược đồ quan hệ  Ý tưởng: Duyệt lần lượt tất cả các phụ thuộc hàm trong tập phụ thuộc hàm cho đến khi nào tập thuộc tính kết quả không phát triển thêm thuộc tính mới thì ngừng lại  Thuật toán: o B1: Bắt đầu  Nhận tập thuộc tính cần tìm bao đóng X  Xác định tập phụ thuộc hàm F = {fi} ; i = 1…n fi = pi -> qi  (X)+ = X o B2:  (X)+tạm= (X)+ o B3:  Với mỗi fi : pi -> qi thuộc F  Nếu (X)+ chứa pi thì (X)+ = (X)+ U {qi} 6 o B4: Nếu (X)+ (X)+tạm thì lặp lại B2 o B5: Kết quả = (X)+ o B6: kết thúc  Đoạn chương trình: ''' ''' Return Closure of AttSet X in Schema R ''' Public Shared Function Closure(ByVal R As Schema, ByVal X As AttSet) As AttSet Dim Result As New AttSet 'Neu X chi bao gom cac TT cua R.U 'If AttSet.Contains(R.U, X) Then Result.CopyFrom(X) Dim numAtt As Integer 'Bat dau vong lap Do 'Giu lai KQ truoc numAtt = Result.numAtt 'Voi moi PTH cua R For index As Integer = 0 To R.F.numFD - 1 'Ve trai Dim Left As AttSet = R.F(index).getLeft 'Ve phai Dim Right As AttSet = R.F(index).getRight 'Neu Neu KQ hien tai co chua ve trai cua PTH dang xet thi tham cac TT ve phai vao KQ If AttSet.Contains(Result, Left) Then Result.AddFrom(Right) End If Next 'Lap lai den khi nao KQ ko thay di nua Loop While numAtt Result.numAtt ' End If 'KQ Return Result End Function  Hoạt động: Đoạn chương trình chạy tốt trong cấu trúc dữ liệu của nhóm và các bộ dữ liệu test II.3. Thuật toán kiểm tra phụ thuộc hàm thành viên: 7  Ý tưởng: Nếu một phụ thuộc hàm f : p -> q là thành viên của 1 tập phụ thuộc hàm F trong 1 lược đồ quan hệ R thì bao đóng của p trong lược đồ R sẽ chứa q  Thuật toán: o B1: Bắt đầu  Xác đinh các tập thuộc tính vế trái (p) và vế phải (q) của f  Nhận lược đồ quan hệ R để xác định tập phụ thuộc hàm F o B2: Tìm báo đóng của vế trái  (p)+ = Baodong(R,p) o B3:  Với mỗi thuộc tính qi thuộc {q}  Nếu qi không thuộc (p)+ thì chuyển xuống B5. o B4: Kết quả = f là thành viên của F trong R. Chuyển xuống B6. o B5: Kết quả = f là không thành viên của F trong R. o B6: Kết thúc.  Đoạn chương trình: ''' ''' Return a value indicating that if FD f is a member of the specified Schema ''' Public Shared Function IsMember(ByVal R As Schema, ByVal f As FD) As Boolean Dim ClosureLeft As AttSet = Schema.Closure(R, f.getLeft) 'Neu bao dong cua ve trai cua f co chua ve phai thi tra ve dung If ClosureLeft.Contains(f.getRight) Then Return True End If 'Neu khong tra ve sai Return False End Function 8  Hoạt động: Đoạn chương trình chạy tốt trong cấu trúc dữ liệu của nhóm và các bộ dữ liệu test thư nghiệm II.4. Thuật toán tìm danh sách khóa của 1 lược đồ quan hệ:  Ý tưởng: Sử dụng thuật toán tìm khóa đã học trong chương trình  Thuật toán: o B1: Bắt đầu  Xác nhận lược đồ quan hệ R cần tìm danh sách khóa, tập thuộc tính U và tập phụ thuộc hàm F o B2: Xác đinh các tập thuộc tính cho yêu cầu tìm khóa  Trái = tập hợp tất thuộc tính vế trái của tất cả phụ thuộc hàm của tập F  Phải = tập hợp tất thuộc tính vế phải của tất cả phụ thuộc hàm của tập F  Gốc = Trái / Phải  Trung gian = Trái ∩ Phải  Treo = R.U / (Trái + Phải)  Nguồn = Gốc + Treo o B3: Kiểm tra bao đóng của Nguồn  (Nguồn)+ = BaoDong(R, Nguồn)  Nếu (Nguồn)+ = R.U thì thêm tập Nguồn vào danh sách kết quả. Chuyển xuống B5. o B4:  Với mỗi tập con Xi của tập Trung gian 9  Nếu Xi thuộc danh sách bỏ qua thì chuyển qua tập con tiếp theo  Tạm = Nguồn + Xi  Nếu (Tạm)+ = R.U thì o Thêm tập Tạm vào danh sách kết quả o Thêm tập Xi vào danh sách bỏ qua o B5: Kết quả = danh sách kết quả o B6: Kết thúc  Đoạn chương trình: ''' ''' Return a AttSetList Contains all keys of the specified Schema ''' ''' Schema R ''' ''' Public Shared Function KeysList(ByVal R As Schema) As AttSetList Dim Result As New AttSetList 'Tat ca TT ve trai cua R Dim Left As AttSet = R.F.LeftAttributes 'Tat ca TT ve phai cua R Dim Right As AttSet = R.F.RightAttributes 'Goc = Left/Right Dim Roots As AttSet = AttSet.Diff(Left, Right) 'La = Right/Left Dim Leaves As AttSet = AttSet.Diff(Right, Left) 'Trung gian = Giao(Left,Right) Dim Intermedia As AttSet = AttSet.Intersection(Left, Right) 'Treo = R.U/Hop(Left, Right) Dim HangOver As AttSet = AttSet.Diff(R.U, AttSet.Union(Left, Right)) 'Nguon = Goc + Treo Dim Source As AttSet = AttSet.Union(Roots, HangOver) 'Neu bao dong cua nguon bang R.U thi them nguon vao ds khoa If Schema.Closure(R, Source).Equals(R.U) Then Result.AddNewSet(Source) Else 'Neu nguon khong la khoa 'Ds cac tap con cua trung gian Dim SubSetsList As AttSetList = AttSet.SubSets(Intermedia) 10 'Ds cac tap con da ket hop voi nguon thanh khoa Dim ExcludeSets As New AttSetList 'Voi moi tap con, tru tap con cuoi cung For index As Integer = 0 To SubSetsList.NumSet - 1 Dim tmpAttSet As AttSet = SubSetsList.AttSet(index) Dim InExcludeSets As Boolean = False 'Voi moi tap con da thuoc khoa For index1 As Integer = 0 To ExcludeSets.NumSet - 1 'Neu tap con chua tap con da la khoa If tmpAttSet.Contains(ExcludeSets.AttSet(index1)) Then 'dieu chinh gia tri bien InExcludeSets = True Exit For End If Next 'Neu khong thuoc khoa thi If Not InExcludeSets Then 'Khoa tam la hop cua nguon va tap con hien tai Dim tmpKey As AttSet = AttSet.Union(Source, tmpAttSet) 'Neu bao dong cua khoa tam bang R.U thi them vao KQ If Schema.Closure(R, tmpKey).Equals(R.U) Then Result.AddNewSet(tmpKey) 'Them Tap con thuoc khoa vao DS ExcludeSets.AddNewSet(tmpAttSet) End If End If 'Tap con tiep theo cua trung gian Next End If 'KQ Return Result End Function  Hoạt động: Đoạn chương trình chay tốt và cho kết quả tương đối chinh xác trong các bộ dữ liệu thử. Tuy nhiên do bị ảnh hưởng bởi thuất toán tìm tập con nên nếu lược đồ quan hệ có trên 12 thuộc tính thuộc tập trung gian có thể sẽ ảnh hưởng đến thời gian tính toán ra kết quả II.5. Thuật toán tìm phủ tối thiểu: 11  Ý tưởng: Sử dụng thuật toán tìm phủ tối thiểu được học trong chương trình o B1: Biến đổi tập phụ thuộc hàm để mọi phụ thuộc hàm trong tập đều có vế phải 1 thuộc tính o B2: Loại bỏ các phụ thuộc dư thừa o B3: Sửa các phụ thuộc hàm không đầy đủ (dư thừa thuộc tính ở vế trái)  Vấn đề mắc phải: o Với bộ dữ liệu test:  R=(U,F) ; U = {A,B,C,D} F = {A,C,D -> B; D->C; C->A; B->C}  Hiện tại, PTH D->C chưa phải là phụ thuộc hàm dư thừa vì F’ = F – (D->C) = {A,C,D->B; C->A; B->C}  F’ và F không tương đương vì (D->C) không là thành viên của F’, do đó cho dù loại đươc PTH này thì kết quả thu được sẽ không đúng  Xét tính đầy đủ của PTH, ta sửa PTH A,C,D->B không đầy đủ thành D->B  Vào lúc này, PTH D-> C mới trở thành dư thừa vì  F’’ = F – (D->C) = {D->B; C->A; B->C}  F’’ và F tương đương vì (D)+ trong F’’ = {D,B} o Hướng giải quyết:  Cách 1: Lặp lại từ B2 mỗi khi B3 có thay đổi 1 PTH nào đó 12  Cách 2: Theo suy luận của nhóm, nếu ta làm đầy đủ hoàn toàn (không dư thừa 1 thuộc tính nào ở vế trái) tất cả PTH trước rồi mới loại bỏ các PTH dư thừa thì vẫn bảo đảm vì  Khi loại bỏ PTH dư thừa không làm thay đổi bao đóng của tập PTH. Nếu nếu xét làm đầy đủ các PTH trước khi loại bỏ PTH dư thừa thì kết quả thu được cũng không thay đổi, các phụ thuộc hàm dư thừa có thể sẽ chỉ bị biến đổi nhưng vẫn dư thừa  Xét PTH không đày đủ trước sẽ làm xuất hiện các PTH không đầy đủ còn ẩn như trong ví dụ test ở trên. Sau đó ta mới loại bỏ dư thừa  Thuật toán: Trên cơ sơ đó, nhóm quyết định sử dụng thuật toán tìm phủ tối tiểu như sau o B1: Bắt đầu  Xác định lược đồ quan hệ R nhập vào, phân tích tập thuộc tính U và tập phụ thuocj hàm F o B2: Biến đổi tập PTH F thành tập phụ thuộc hàm có vế phải đơn  Với mỗi f : p -> q thuộc F  Với tập thuộc tính qi chỉ có 1 thuộc tính của q o Tạo phụ thuộc hàm p -> qi o Thêm PTH này vào F  Xóa f khỏi F o B3: Sửa các PTH không đầy đủ  Với mỗi PTH f: p -> q thuộc F 13  Nếu p có 1 thuộc tính thì f là PTH đầy đủ, chuyển sang PTH tiếp theo  Với mỗi tập con pi của tập p (được xếp theo chiều tăng dần số thuộc tinh của mỗi tập con) o Nếu (pi)+ trong R có chứa q thì đây là PTH không đầy đủ.  Lập PTH đầy đủ f’:pi -> q  F = F - {f} + {f’}  Chuyển sang PTH tiếp theo trong F (*Giải thích thuật toán: f: p -> là không đầy đủ khi tồn tại 1 tập pi là con của p mà F ≡ F – {f} + {pi -> q}. Về cơ bản khi thay đổi hai PTH đó trong F thì bao đóng của F vẫn không thay đổi nên nói cách khác, f không đầy đủ khi pi -> q là 1 PTH thành viên của F trong R, với pi là 1 tập con của p) o B4: Loại PTH dư thừa  Với mỗi f: p -> q thuộc F  Tạo tập PTH tạm F’ = F – f  Nếu (p)+ trong F’ có chứa q thì f là phụ thuộc hàm dư thừa o Loại F = F – {f}  Chuyển sang PTH tiếp theo trong F o B5: Kết quả bằng Tập PTH F hiện tại o B6: kết thúc  Đoạn chương trình ''' 14 ''' Return the Minimum Cover FDSet of the specified Schema ''' Public Shared Function MinimalCover(ByVal R As Schema) As FDSet Dim tmpR As New Schema tmpR.CopySchema(R) 'B1: Tach cac PTH ve phai 1 TT tmpR.FDSet = tmpR.F.ToMonoFDSet 'B2: Sua cac PTH khong day du tmpR = tmpR.Complete 'B3: Loai cac PTH du thua tmpR = tmpR.RemoveRedundant() 'KQ Return tmpR.F End Function (*Các thuật toán con xin vui lòng theo dõi trong source code của chương trình)  Hoạt động : Đoạn chương trình hoạt động tốt trong các bộ dữ liệu thử của nhóm. Tuy nhiên do cac thuật toán có sử dụng đên tim tập con nên với trường hợp số thuộc tính 1 vế lớn kết quả có thể sẽ ra chậm. II.6. Các thuật toán xác định dạng chuẩn:  Ý tưởng: o Dạng chuẩn 2: Kiểm tra tất cả PTH có dạng Khóa -> thuộc tính không Khóa có phải là PTH đầy đủ hay không. o Dạng chuẩn 3: Một lược đồ quan hệ đạt dạng chuẩn 3 khi tất cả các phụ thuộc hàm không hiển nhiên X -> Y của tập phụ thuộc hàm thỏa mãn ít nhất 1 trong 2 điều kiện:  X là siêu khóa (chứa khóa)  Y là thuộc tính khóa o Dạng chuẩn BC: Một lược đồ quan hệ đạt dạng chuẩn 3 khi tất cả các phụ thuộc hàm không hiển nhiên X -> Y của tập phụ thuộc hàm đều có vế trái là siêu khóa 15  Thuật toán o Dạng chuẩn 2:  B1: Bắt đầu  Xác nhận lược đồ quan hệ R, phân tích tập thuộc tính U và tập PTH F  K = {Ki} là tập khóa của R  N = {ni} với ni là các thuộc tính không khóa của R  B2:  Với mỗi Ki thuộc K o Với mỗi ni thuộc N  Xét pth f: Ki -> ni có là PTH đầy đủ hay không (*)  Nếu có chuyển sang thuộc tính kế tiếp trong N  Nếu không chuyển xuống B4  B3: R đạt dạng chuẩn 2, chuyển xuông B5  B4: R không đạt dạng chuẩn 2  B5: Kết thúc (*): Xem lại thuật toán ở B3 trong thuật toán tìm Phủ tối thiểu o Dạng chuẩn 3:  B1: Bắt đầu  Xác nhận lược đồ quan hệ R, phân tích tập thuộc tính U và tập PTH F  K = {Ki} là tập hợp các khóa Ki của R 16  A = {ai} là tập cuhứa các thuộc tính khóa của R  B2:  Với mỗi f: p -> q thuộc F o Nếu f là PTH hiển nhiên thì chuyển sang PTH tiêp theo o Với mỗi Ki thuộc K, nếu Ki chứa p thì chuyển sang PTH tiếp theo o Nếu A chứa q thì chuyển sang PTH tiếp theo o Chuyển xuống B4 (Khi f nào đó không thỏa 1 trong 3 điều kiện trên)  B3: Lược đồ quan hệ đạt dạng chuẩn 3, chuyển xuống B5  B4: Lược đồ quan hệ không đạt dạng chuẩn 3  B5: Kết thúc o Dạng chuẩn BC  B1: Bắt đầu  Xác nhận lược đồ quan hệ R, phân tích tập thuộc tính U và tập PTH F  K = {Ki} là tập hợp các khóa Ki của R  B2:  Với mỗi f: p -> q thuộc F o Nếu f là PTH hiển nhiên thì chuyển sang PTH tiêp theo o Với mỗi Ki thuộc K, nếu Ki chứa p thì chuyển sang PTH tiếp theo 17 o Chuyển xuống B4 (Khi f nào đó không thỏa 1 trong 2 điều kiện trên)  B3: Lược đồ quan hệ đạt dạng chuẩn BC, chuyển xuống B5  B4: Lược đồ quan hệ không đạt dạng chuẩn BC.  B5: Kết thúc  Đoạn chương trình: Xin theo dõi trong source code của chương trình III. Các thuật toán ngoài yêu cầu:  Thuật toán kiểm tra phụ thuộc bắc cầu  Thuật toán Tìm hình chiếu tập phụ thuộc hàm của 1 tập thuộc tình trên R  Thuật toán phân rã lược đồ đát DC Boyce-Codd và bảo toàn thông tin *Các thuật toán trên nhóm đã test và kết quả hoạt động tốt IV. Các thuật toán có khả năng phát triển:  Phân rã đạt dạng chuẩn 3 và bảo toàn phụ thuộc hàm  Kiểm tra tập lược đồ sau khi phân rã bảo toàn thông tin  Kiểm tra tập lược đồ sau khi phân rã bảo toàn phụ thuộc hàm V. Kết thúc và hướng phát triển: - Nhìn chung chương trình của nhóm hoạt động tốt, nhưng hạn chế vẫn còn ở thuật toán tìm danh sách tập con. Một phần khác có thể do cấu trúc biểu diễn của nhóm chưa hiệu quả. Những vấn đề này có thể khắc phục để xây dựng 1 chương trình hiệu quả hơn.