Bài tập nhóm: Thiết kế cơ sở dữ liêu

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ả.
Nội dung trích xuất từ tài liệu:
Bài tập nhóm: Thiết kế cơ sở dữ liêuĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINHTRƯỜ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 2I. 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. 3II. 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 {U n-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 {U n} 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 ungvao 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 FunctionHam tang gia tri mang nhi phan len 1Private Shared Sub ChangeNext(ByRef Bin As Boolean(), ByVal index AsInteger) Bin(index) = Not Bin(index) If Bin(index) = False Then ChangeNext(Bin, index + 1) End If 5End 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 ...