Luận văn Thuật toán thiết kế cơ sở dữ liệu

ao đóng (Closure) của tập phụ thuộc hàm F (ký hiệu là F+, đó là tập các phụ thuộc hàm có thể được suy dẫn logic từ F) để kiểm tra xem một phụ thuộc hàm X→Y có thuộc F+ hay không, người ta chỉ cần đi tìm bao đóng của X dựa trên tập các phụ thuộc hàm F (ký hiệu là XF+, đó là tập các thuộc tính có thể suy diễn từ X nhờ F), rồi kiểm tra xem Y có thuộc XF+ hay không. Ví dụ: Cho lược đồ quan hệ R (A,B,C,D,E,G,H) và tập phụ thuộc hàm F={AB®C, B®D, CD®E, CE®GH, G®A}. Áp dụng hệ tiên đề Amstrong, tìm một chuỗi suy diễn AB®E. Giải: 1. AB®C (cho trước phụ thuộc hàm f1) 2. AB®AB (tính chất phản xạ) 3. AB®B (luật tách) 4. B®D (cho trước phụ thuộc hàm f2) 5. AB®D (bắt cầu 3 & 4) 6. AB®CD (hợp 1 & 5) 7. CD®E (cho trước phụ thuộc hàm f3) 8. AB®E (bắt cầu 6 & 7). Kết thúc.  Ví dụ: Cho lược đồ quan hệ R (A,B,C,D,E,G,H,I,J) và tập các phụ thuộc hàm F = {AB®E, AG®J, BE®I, E®G, GI®H }. Tìm chuỗi suy diễn AB®GH. Giải: 1. AB®E (cho trước phụ thuộc hàm f1) 2. AB®AB (phản xạ) 3. AB®B (luật tách) 4. AB®BE (hợp của 1 & 3) 5. BE®I (cho trước phụ thuộc hàm f3) 6. AB®I (bắt cầu 4 & 5) 7. E®G (cho trước phụ thuộc hàm f4) 8. AB®G (bắt cầu 1 & 7) 9. AB®GI (hợp 6 & 8) 10. GI®H (cho trước phụ thuộc hàm f5) 11. AB®H (bắt cầu 9 & 10) 12. AB®GH (hợp 8 & 11) Phủ và phủ tối tiểu: Trong rất nhiều bài toán liên quan đến CSDL thì độ phức tạp tùy thuộc vào số phụ thuôc hàm cũng như các thuộc tính bên vế trái, vế phải của phụ thuộc hàm. Do đó, để giảm bớt độ phức tạp người ta thường xây dựng các tập phụ thuộc hàm tương đương với tập phụ thuộc hàm ban đầu nhưng đơn giản hơn. Phụ thuộc hàm tương đương: Hai tập phụ thuộc hàm F và G được gọi là tương đương với nhau nếu F+ = G+. Ký hiệu: F º G. " f Î F thì f Î G+ và " g Î G thì g Î F+. Phủ của 1 phụ thuộc hàm: Cho hai tập phụ thuộc hàm F, G. Ta nói F phủ G nếu F+ Ê G+. Phụ thuộc hàm đầy đủ: F là tập các phụ thuộc hàm trên lược đồ quan hệ Q, X là tập thuộc tính, ta có phụ thuộc hàm: X → Y Î F. Ta nói phụ thuộc hàm X → Y là đầy đủ nếu !$ A Î Z sao cho (X – A) → Y. Phụ thuộc hàm không dư thừa: F là tập phụ thuộc hàm không dư thừa nếu !$ F’ Ì F sao cho F’ = F. Ngược lại F là tập phụ thuộc hàm dư thừa. Ví dụ: Cho F = {A → BC, B → D, AB → D} F dư thừa vì: F º F’ = {A → BC, B → D} Phủ tối tiểu: Mục đích của việc tìm phủ tối tiểu là: Giảm lược bớt số thuộc tính của vế phải. Giảm số phụ thuộc hàm. Định nghĩa: Cho tập PTH F, G là phủ tối tiểu của F nếu G là phủ của F đồng thời thỏa 3 điều kiện sau: Vế phải của các PTH trên G chỉ chứa 1 thuộc tính. G chỉ gồm những phụ thuộc hàm đầy đủ. Không chứa phụ thuộc hàm thừa. Thuật toán xác định phủ tối tiểu: Bước 1: Loại khỏi F các phụ thuộc hàm có vế trái dư thừa. Lần lượt thực hiện các bước sau cho các phụ thuộc hàm X→Y của F. Với mọi tập con thật sự X’→Y Î F+ thì thay X→Y trong F bằng X’ → Y, thực hiện lại bước này. Bước 2: Tách phụ thuộc hàm có vế phải lớn hơn một thuộc tính thành các phụ thuộc hàm có vế phải có một thuộc tính. Bước 3: Loại khỏi F các phụ thuộc hàm dư thừa. Lần lượt xét các phụ thuộc hàm X ® Y của F Nếu X ® Y là thành viên của F – { X ® Y } thì loại X ® Y khỏi F. Thực hiện bước trên cho các phụ thuộc hàm tiếp theo của F. Các dạng chuẩn của lược đồ quan hệ: Trong thực tế, một ứng dụng có thể được phân tích thành nhiều lược đồ CSDL khác nhau và dĩ nhiên chất lượng thiết kế của các lược đồ này cũng khác nhau. Chất lượng thiết kế của một lược đồ CSDL được đánh giá dựa trên các tiêu chuẩn như: Sự trùng lắp thông tin: vì nó sẽ làm tăng không gian lưu trữ và gây nên tình huống thông tin bị mâu thuẫn sau những lần cập nhật CSDL. Chi phí kiểm tra ràng buộc toàn vẹn. Bảo toàn quy tắc quản lý tức là bảo toàn các phụ thuộc hàm. Bảo toàn thông tin. Ví dụ: Quan hệ QuảnLýHọcTập (MaSV, TenSV, NgaySinh, Phai, DiaChi, MaLop, TenLop, MaMonHoc, TenMonHoc, Diem) F = { f1: MaSV→TenSV, NgaySinh, Phai, DiaChi, MaLop. f2: MaLop → TenLop. f3: MaMonHoc → TenMonHoc. f4: TenMonHoc → MaMonHoc. f5: MaSV, MaMonHoc → Diem.} Quan hệ trên có sự trùng lắp thông tin. Sự trùng lắp thông tin này có thể gây một số vấn đề khi thao tác trên quan hệ. Giả sử: có 1 sinh viên thay đổi địa chỉ, thì hệ thống cần phải duyệt trên toàn bộ quan hệ để tìm và sửa địa chỉ các bộ liên quan đến sinh viên này. Nếu để xót thì sẽ dẫn đến tình trạng thông tin không nhất quán. Giả sử sinh viên có mã số 1180 hiện nay chỉ đăng ký học môn CSDL. Nếu muốn xóa kết quả điểm của môn này thì dẫn đến mất luôn thông tin của sinh viên. Khóa của quan hệ là: {MaSV, MaMonHoc}, {MaSV, TenMonHoc} nên ta không thể thêm một sinh viên vào nếu sinh viên đó chưa đăng ký môn học. Qua ví dụ trên, chúng ta thấy sự trùng lắp thông tin là nguyên nhân làm cho CSDL có chất lượng kém. Để hạn chế sự trùng lắp thông tin, người ta đưa ra các yêu cầu thiết kế cần thiết cho một quan hệ dựa trên khái niệm phụ thuộc hàm, được gọi là các dạng chuẩn của một quan hệ. Dạng chuẩn 1: Thuộc tính đơn: là thuộc tính mà giá trị của nó không phải là sự kết hợp bỡi nhiều thông tin có ý nghĩa khác nhau và hệ thống luôn truy xuất trên toàn bộ giá trị của nó ít khi truy xuất đến từng phần dữ liệu của nó. Ví dụ: Quan hệ VatTu (MãVậtTư, TênVậtTư, ĐơnVịTính) Nếu TênVậtTư bao gồm cả tên vật tư và quy cách của nó. Như vậy, TênVậtTư là thuộc tính kép. Định nghĩa dạng chuẩn 1: Một lược đồ quan hệ Q đạt dạng chuẩn 1 nếu mọi thuộc tính của Q đều là thuộc tính đơn. Dạng chuẩn 2: Phụ thuộc đầy đủ: Thuộc tính A được gọi là phụ thuộc đầy đủ vào tập thuộc tính X nếu: A Î X+F X ® A là PTH nguyên tố. Ví dụ: Quan hệ LopHoc (Lop, Mon, NgayKhaiGiang, HocPhi) F = { f1: Lop, Mon → NgayKhaiGiang ; f2: Mon → HocPhi}. Dựa vào F ta có khóa của quan hệ là {Lop, Mon}. Do đó: Lop, Mon → HocPhi là phụ thuộc hàm không đầy đủ vì chỉ cần Mon là xác định được HocPhi: Mon→HocPhi. Định nghĩa dạng chuẩn 2: Một lược đồ quan hệ Q đạt dạng chuẩn 2 nếu: Q ở dạng chuẩn 1. Mọi thuộc tính không khóa đều phụ thuộc đầy đủ vào các khóa của Q. Hệ quả: Nếu mỗi khóa của quan hệ Q chỉ có 1 thuộc tính thì Q đạt dạng chuẩn 2. Ví dụ: Quan hệ LopHoc (Lop, Mon, NgayKhaiGiang). F = {Lop, Mon → NgayKhaiGiang} Ta nói quan hệ LopHoc đạt dạng chuẩn 2 vì thuộc tính không khóa NgayKhaiGiang phụ thuộc hàm đầy đủ vào khóa. Dạng chuẩn 3: Phụ thuộc bắt cầu: Thuộc tính A Î Q+ được gọi là phụ thuộc bắt cầu vào thuộc tính X nếu tồn tại nhóm thuộc tính Y Í Q+ thỏa mãn 4 điều kiện sau: X ® Y Î F+ Y ® A Î F+ Y --/--> X A Ï {X Ç Y} Ví dụ: Quan hệ SinhVien (MaSV, TenSV, NgaySinh, QueQuan, MaLop, TenLop). TenLop phụ thuộc bắt cầu vào MaSV vì: MaSV → MaLop MaLop → TenLop MaLop --/--> MaSV TenLop Ï {MaSV Ç MaLop} Định nghĩa dạng chuẩn 3: Một lược đồ quan hệ Q đạt dạng chuẩn 3 nếu: Q ở dạng chuẩn 2 Mọi thuộc tính không khóa Q đều không phụ thuộc bắt cầu vào một khóa nào của Q. Ví dụ: Quan hệ SinhVien (MaSV, TenSV, NgaySinh, QueQuan, MaLop) là quan hệ đạt dạng chuẩn 3. Vì các thuộc tính không khóa TenSV, NgaySinh, QueQuan, MaLop không phụ thuộc bắt cầu vào khóa. Dạng chuẩn BCK: Định nghĩa: Một lược đồ quan hệ Q ở dạng chuẩn BCK nếu mọi phụ thuộc hàm không hiển nhiên đều có vế trái chứa khóa. X ® A Î F+ : A Ï X và phải chứa khóa của Q. Hệ quả: Nếu Q đạt dạng chuẩn BCK thì mọi vế trái của phụ thuộc hàm đều là siêu khóa. Ví dụ: Quan hệ TonKho (MaHangHoa, MaKho, SoLuongTon) Ta nói quan hệ TonKho đạt dạng chuẩn BCK. Chuẩn hóa quan hệ: Xuất phát từ giai đoạn phân tích yêu cầu, ta có thể có 1 trong 2 kết quả sau: Một cấu trúc CSDL ban đầu gồm các quan hệ con Qi cùng các phụ thuộc hàm F. Hoặc chỉ có một quan hệ phổ quát duy nhất Q chứa tất cả các thuộc tính cần được lưu trữ và các phụ thuộc hàm F. Chúng ta cần kiểm tra và chuẩn hóa các kết quả đầu tiên này dựa trên một số tiêu chuẩn thiết kế để có được một cấu trúc quan niệm CSDL được đánh giá tốt hơn, phù hợp hơn với yêu cầu của môi trường ứng dụng. Các tiêu chuẩn của quá trình chuẩn hóa: Hai tiêu chuẩn quan trọng cần đạt được trong quá trình chuẩn hóa một CSDL ở mức quan niệm là: CSDL kết quả cần đạt dạng chuẩn cao nhất: Dạng chuẩn được đề ra nhằm đáp ứng 2 yêu cầu sau: Cập nhật: hạn chế tối đa sự trùng lắp thông tin trong CSDL. Kiểm tra ràng buộc toàn vẹn: tạo điều kiện thuận lợi cho việc kiểm tra ràng buộc toàn vẹn ở dạng phụ thuộc dữ liệu. CSDL kết quả phải tương đương với CSDL phân tích lúc ban đầu: Với tiêu chuẩn này, các thông tin lưu trữ CSDL ban đầu đều phải được tìm thấy đầy đủ trong CSDL kết quả. Có ba quan niệm khác nhau về tiêu chuẩn này: Quan điểm 1: bảo toàn phụ thuộc hàm. Quan điểm này cho rằng các thông tin được lưu trữ trong CSDL là những thông tin được thể hiện thông qua các phụ thuộc hàm. Do đó cần phải bảo toàn phụ thuộc hàm trong khi biến đổi. Quan điểm 2: bảo toàn thông tin. Quan điểm này cho rằng các thông tin được lưu trữ trong CSDL ban đầu đều phải được tìm thấy đầy đủ trong CSDL kết quả. Quan điểm 3: biểu diễn tron vẹn. Yêu cầu CSDL kết quả vừa bảo toàn thông tin, vừa bảo toàn phụ thuộc hàm. Các phương pháp chuẩn hóa một lược đồ CSDL: Phương pháp phân rã: Định lý Delobel (1973): Cho lược đồ quan hệ Q và tập phụ thuộc hàm F. Nếu f: X → A Î F+ sao cho X È A là tập con thật sự của Q+ thì phép phân rã Q thành 2 lược đồ quan hệ con: Q1(X, A), F+1 = {f: Î F+ : VT(f) È VP(f) Ì Q+1} Q1(Q+\A), F+1 = {f: Î F+ : VT(f) È VP(f) Ì Q+2} Là bảo toàn thông tin. Ý tưởng: Dựa vào định lý Delobel, ta phân rã quan hệ Q thành 2 quan hệ Q1, Q2 bằng 1 phụ thuộc hàm f thỏa điều kiện của định lý. Lặp lại phân rã trên Q1, Q2 cho đến khi không còn phụ thuộc hàm f như vậy nữa. Thuật toán: PhanRa(Q, F) Vào: Ra: C = {Qi} //tập các quan hệ được phân rã. Begin: Bước 1: Loại bỏ các phụ thuộc hàm có VT È VP = Q+ khỏi F. F* = F\{f Î F : VT(f) È VP(f) = Q+} Bước 2: Nếu F* = Æ thì C = C È {Q} và kết thúc {Điểm dừng} Ngược lại, thực hiện phân rã Tìm tất cả các khóa của quan hệ. Chọn f: X → Y Î F với X không là siêu khóa và Y không chứa thuộc tính khóa. Phân rã thành 2 lược đồ con: Q+1 = {X, Y}; F1 = {f Î F+: VT(f) È VP(f) Í Q+1} Q+2 = Q+\Y; F2 = {f Î F+: VT(f) È VP(f) Í Q+2} Phân rã đệ qui Q1, Q2: Phanra(Q1, F1); Phanra(Q2, F2); End. Thuật toán trên là bảo toàn thông tin theo định lý Delobel. Ví dụ: Cho Q(S,D,I,M) F={SI®D;SD®M} Hãy phân rã Q thành các lược đồ con đạt dạng chuẩn 3 (dạng chuẩn BCK) bảo toàn thông tin. Giải: Bước 1: tìm tất cả khóa của Q Xi TNÈXi (TNÈXi)+ Siêu khóa Khóa Æ SI SDIM SI SI D SID SDIM SID Bước 2: phụ thuộc hàm SD ® M Î F có SD không là siêu khóa. Ta được phân rã như bên dưới. Nhược điểm của phương pháp này: Không bảo toàn phụ thuộc hàm. Có thể chứa một quan hệ con mà ngữ nghĩa của nó không có ích cho ứng dụng. Thuật toán này chỉ tiện trong trường hợp khối lượng tính toán trong việc tìm tất cả các khóa của quan hệ Q không lớn. Phương pháp tổng hợp: Mục tiêu của phương pháp: Tìm một cấu trúc CSDL gồm các Qi sao cho: Dễ dàng kiểm tra các phụ thuộc hàm. Tối thiểu đạt dạng chuẩn 3. Thuật toán: TongHop(Q, F) Vào: Ra: C = {} Begin Bước 1: Tìm phủ tối tiểu của F. Bước 2: Chia phủ tối tiểu thành những nhóm Fi. Mỗi nhóm Fi chứa các phụ thuộc hàm có cùng vế trái. Bước 3: Gộp các Fi có vế trái phụ thuộc lẫn nhau lại thành một nhóm. Bước 4: Tạo các quan hệ con Qi từ các nhóm phụ thuộc hàm Fi đã tạo ở bước 3. End. Ví dụ: Quan hệ Q(MSCĐ, MSSV, CĐ, HG) F = { f1 = MSCĐ ® CĐ, f2 = CĐ ® MSCĐ, f3 = CĐ, MSSV ® HG, f4 = MSCĐ, HG ® MSSV, f5 = CĐ, HG ® MSSV, f6 = MSCĐ, MSSV ® HG} Hãy phân rã quan hệ trên theo thuật toán tổng hợp. Giải: Bước 1: tìm phủ tối tiểu của F: Ftt = {f1, f2, f3, f4} Bước 2: phân nhóm Ftt mỗi nhóm chứa các phụ thuộc hàm có cùng vế trái. F1 f1 = MSCĐ ® CĐ F2 f2 = CĐ ® MSCĐ F3 f3 = CĐ, MSSV ® HG F4 f4 = MSCĐ, HG ® MSSV Bước 3: gộp các phụ thuộc hàm F’i có vế trái phụ thuộc lẫn nhau: F12 f1 = MSCĐ ® CĐ, f2 = CĐ ® MSCĐ F34 f3 = CĐ, MSSV ® HG,f4 = MSCĐ, HG ® MSSV Bước 4: tạo các quan hệ con Qi từ các phụ thuộc hàm F’i Q12 (MSCĐ, CĐ) F12 = {f1 = MSCĐ ® CĐ, f2 = CĐ ® MSCĐ} Q34 (CĐ, MSSV, MSCĐ, HG) F34 = {f3 = CĐ, MSSV ® HG,f4 = MSCĐ, HG ® MSSV} Đồ thị quan hệ: Dẫn nhập: Thao tác quan trọng và thường xảy ra nhất trong CSDL quan hệ là phép kết. Để thao tác này được thực hiện hiệu quả, hệ quản trị thường dựa trên các chỉ mục của các quan hệ liên quan. Do đó, vai trò của người thiết kế là làm thế nào xác định được đủ các chỉ mục cần thiết, với số thuộc tính vừa đủ để khai thác. Chỉ mục bao gồm nhiều thuộc tính hoặc tạo quá nhiều chỉ mục sẽ gây tốn chỗ và tốn kém trong quá trình bảo trì hệ thống và CSDL sẽ hoạt động chậm chạp. Để có thể xác định đúng các chỉ mục cần thiết, người ta sử dụng phương pháp biểu diễn quan hệ ở dạng đồ thị. Dạng đồ thị này cho phép làm nổi bậc các thuộc tính chung giữa hai hay nhiều quan hệ (vì đây là cơ sở của phép kết) qua đó giúp cho người thiết kế sau này dễ dàng đánh giá và chọn lựa đúng các chỉ mục. Một số khái niệm trong lý thuyết đồ thị: Đồ thị: Một đồ thị DT (N, C) được định nghĩa trên 1 tập nút N={n1,n2,,nn} và một tập cung C={c1,c2,,cn}. Nếu hiện diện cung có hướng thì đó là đồ thị có hướng, và 2 nút nối bỡi 1 cung có hướng được gọi là nút đi và nút đến. Nếu tất cả các cung đến vô hướng thì đó là đồ thị vô hướng, và các nút trên đồ thị đều được xem là nút xuất phát. Cung kề cận: 2 cung c1, c2 được gọi là kề cận nhau khi: Đồ thị có hướng: nếu nút đến của cung c1 là nút đi của cung c2. Đồ thị vô hướng: nếu chúng có cùng 1 nút xuất phát. Khuyên: Cung c là khuyên nếu 2 nút đi và đến của c là một. Đường đi trên đồ thị vô hướng: Đường đi trên đồ thị vô hướng là một chuỗi cung (c1,c2,,cp) sao cho: ci và ci+1 có chung một nút xuất phát. Nút xuất phát của c1, không chung nút xuất phát của c2, c1 được gọi là nút đầu của đường đi. Nút xuất phát của cp, không chung với nút xuất phát của cp+1, cp được gọi là nút cuối của đường đi. Mạch đi trên đồ thị có hướng: Mạch đi trên đồ thị có hướng là một chuỗi cung (c1,c2,,cp) sao cho: Nút đến của ci là nút đi của ci+1. Nút đi của c1 được gọi là nút đầu của mạch đi. Nút đến của cp được gọi là nút cuối của mạch đi. Chu trình: Chu trình là đường đi hay mạch đi trong đó: Nút đầu và nút cuối trùng nhau. Một cung không xuất hiện 2 lần trong chuỗi. Một dòng có gốc n1: Một dòng có gốc ni là một tập cung D = (c1,c2,,cp) sao cho: Một cung trong tập đó có nút xuất phát (hoặc nút đi) là ni. " ci, " ni, nút xuất phát (hoặc nút đi đến) của ci, $ 1 đường đi (hoặc 1 mạch đi) có nút đầu là n1, nút cuối là ni và gồm các cung của tập D. n1 n2 n3 c1 c2 Ví dụ: (c1,c2) là dòng có gốc n1. (c1,c2) không là dòng có gốc n2. Đồ thị con đường truy xuất: 1 1 Đồ thị con đường truy xuất (N, C, R, Cđ, f, g, h, i, j) là đồ thị có hướng với: N: tập nút, ký hiệu và nút vào Ü C Í (N x N): tập cung có hướng, ký hiệu ® hoặc ->> R: tập quan hệ Qi Đơn ánh f: N ® R: t(n1) = Qn, mỗi nút n ứng với 1 quan hệ Qn. gọi là quan hệ nút. Ánh xạ g: C ® R: g(ci) = Qc mỗi cung ứng với 1 quan hệ Qc, gọi là quan hệ cung. Ngược lại, tồn tại tối đa 2 cung này có 2 chiều ngược nhau, nút đi của cung thứ nhất là nút đến của cung thứ 2 và ngược lại. Điều kiện: f(N) È g(N) = R Cđ: tập con đường truy xuất. Cij Song ánh h: C ® Cđ: mỗi cung ứng với 1 con đường truy xuất. Cij ni nj : từ 1 quan hệ nút f(ni), có thể truy xuất đến 1 bộ của quan hệ nút f(nj) thông qua con đường truy xuất h(cij). ni nj: từ 1 quan hệ nút f(ni), có thể truy xuất đến n bộ của quan hệ nút f(nj) thông qua con đường truy xuất h(cij) Ánh xạ i: Cđ ® N x N x N: trên mỗi con đường truy xuất cij có gắn 1 tổ hợp (m, A, M) thể hiện số bộ có tối thiểu (m), trung bình (A), tối đa (M) của quan hệ nút f(nj) có thể truy xuất được từ 1 bộ của quan hệ nút f(ni) Ánh xạ j: N ® {0, 1}: khi j(ni) = 1 thì ni là một nút. Tổ chức dữ liệu: Để dễ dàng nắm bắt các thuật toán và tận dụng sức mạnh của các công cụ lập trình hiện đại, chúng em đề xuất một vài cấu trúc dữ liệu mới, hướng đối tượng trên nền .Net nhằm phục vụ cho việc triển khai các thuật toán. Ưu điểm của cấu trúc dữ liệu này dễ dàng nắm bắt, nhưng nhược điểm là hao tốn không gian bộ nhớ và tốn năng lực xử lý của hệ thống. Tập thuộc tính: Tập thuộc tính được mô tả bằng một mảng chứa một loạt các string mô tả cho từng thuộc tính. Ta xây dựng một lớp TapThuocTinh để chứa mảng thuộc tính, lớp này kế thừa từ đối tượng Object và interface IEnumerable (để sử dụng hàm foreach trên tập thuộc tính bằng cách khai báo thêm phương thức public IEnumerator GetEnumerator()) như sau: public ArrayList MangThuocTinh; Phụ thuộc hàm: Trong một số cấu trúc dữ liệu cũ trước đây, phụ thuộc hàm được biểu diễn bằng các bit mô tả vị trí của thuộc tính, yếu điểm của phương pháp này là việc biểu diễn phụ thuộc hàm phụ thuộc rất nhiều vị trí của các thuộc tính được sắp đặt trong phụ thuộc hàm. Nhưng ở đây tập thuộc tính của chúng ta được biểu diễn bằng một danh sách các thuộc tính, có nghĩa là người dùng có quyền sắp xếp, thêm bớt các phần tử, cũng có nghĩa là vị trí của các thuộc tính chỉ mang tính tương đối. Ta có thể thấy rằng phụ thuộc hàm chính là mối quan hệ giữa các thuộc tính theo hai vế: vế trái và vế phải, vì vậy ta có thể tận dụng cấu trúc dữ liệu của tập thuộc tính đã trình bày ở trên để mô tả phụ thuộc hàm. Ta xây dựng một lớp PhuThuocHam gồm các thuộc tính như sau: TapThuocTinh vetrai; TapThuocTinh vephai; Tập phụ thuộc hàm: Tập phụ thuộc hàm là tập hợp các phụ thuộc hàm được biểu diễn trong một mảng, mỗi string mô tả cho 1 phụ thuộc hàm: ArrayList TapPTH; Quan hệ: Quan hệ kế thừa từ lớp tập thuộc tính có các thành phần: một chuỗi mô tả tên của quan hệ, một mảng mô tả tập khóa của quan hệ được khai báo như sau: private string _name; public ArrayList tapkhoa; Lược đồ quan hệ: Bao gồm tập các quan hệ và tập các phụ thuộc hàm được xây dựng như bên dưới: ArrayList TapQuanHe; TapPhuThuocHam F; Node: Kế thừa từ một lớp đối tượng gồm các thuộc tính sau: Q là quan hệ PTHNi: mảng phụ thuộc hàm. PTH_thuaNi: mảng phụ thuộc hàm thừa. LKNi: mảng lồng khóa. LK_thuaNi: mảng lồng khóa thừa. Index: chỉ mục có kiểu số nguyên. CungNi: mảng chỉ cung Ni. CÀI ĐẶT MỘT SỐ THUẬT TOÁN Thuật toán tìm bao đóng: Thuật toán gốc: Thuật toán tìm bao đóng của X dựa trên tập phụ thuộc hàm F đối với quan hệ R được mô tả bằng ngôn ngữ Pascal như sau: Procedure Closure (X, F) Begin OldDep := Æ; NewDep := X; While NewDep OldDep Do Begin OldDep := NewDep; For every FD: W®Z Î F Do If W Í NewDep Then NewDep := NewDep È Z; End {If} End {For} End; Return NewDep; End; Cài đặt thuật toán: Function Closure (X, F) Tham biến TapThuocTinh tapX, TapPhuThuocHam F TapThuocTinh baodong = new TapThuocTinh(); baodong.AddItem(tapX); TapThuocTinh olddep = new TapThuocTinh(); while (baodong != olddep) { olddep.AddItem(baodong); PhuThuocHam tmp; int i; for ( i = 0; i < TapPTH.Count; ++i) { tmp = TapPTH[i]; if (tmp.vetrai.LatapCon(baodong)) { baodong.AddItem(tmp.vephai); } } } return baodong; end function; Ví dụ: Tap U = {C,T,H,R,S,G} Tap phu thuoc ham F = { f1: C → T; f2: H,R → C; f3: H,T → R; f4: C,S → G; f5: H,S → R} Tìm bao đóng của tập thuộc tính {H, R} Giải: Bước 1: Giả sử: Tập thuộc tính baodong = {H, R} Tập thuộc tính olddep = Æ Bước 2: Trong khi baodong olddep thì Olddep = baodong nghĩa là olddep = {H, R} Xét lần lượt các phụ thuộc hàm từ f1 đến f5 Vì vế trái của f2 = {H, R} nên đưa vế phải của f2 là {C} vào baodong, lúc này baodong = {H, R, C}. Bước 3: baodong = {H, R, C} olddep = {H, R} nên lặp lại bước 2 đưa {T} vào baodong. Vậy: Closure({H,R}) = {C,T,H,R}. Thuật toán tìm tất cả các khóa của quan hệ: Function: TimKhoa(F, TapKhoa) Vào: F: là tập phụ thuộc hàm. TapKhoa: là 1 mảng chứa khóa của quan hệ. Ra: 1 mảng chứa khóa của quan hệ. Begin: Gọi VX là tập thuộc tính của quan hệ. If (số thuộc tính trong VX != 0) { KhongBo = 0; //số lượng các phần tử không thể loại bỏ. Foreach ( thuộc tính A trong VX) { Tập thuộc tính Y = VX – A; Tập thuộc tính BaoDong = tính bao đóng (Y,F); If (VX là tập con của bao đóng (Y, F)) //Y là siêu khóa. { Tìm khóa; } Else { KhongBo ++; } } If (KhongBo = = số phần tử trong XA) { Cont = true; For (i = 0; i< số phần tử trong TapKhoa) { Tập thuộc tính ttt = TapKhoa[i]; If (ttt = = VX) { Cont = false; Break; } } If (Cont) { Thêm VX vào TapKhoa; } } } Return TapKhoa; End. Ví dụ: Cho lược đồ quan hệ U ={C,H,R,S} Tập phụ thuộc hàm: F={ H,R -> C ; H,S -> R} Tìm khóa của lược đồ quan hệ. Giải: H,R,S có bao đóng C,H,R,S Siêu khóa. R,S có bao đóng R,S không đi xuống. H,S có bao đóng C,H,R,S Siêu khóa. S có bao đóng S H có bao đóng H H,C,R có bao đóng C,H,R không đi xuống. C,R,S có bao đóng C,R,S không đi xuống. C,H,S có bao đóng C,H,R,S Siêu Khóa. H,S có bao đóng C,H,R,S Khóa. S có bao đóng S H có bao đóng H C,S có bao đóng C,S không đi xuống. C,H có bao đóng C,H không đi xuống. C,H,R có bao đóng C,H,R không đi xuống. ** Hiển thị khóa {H,S} có bao đóng {C,H,R,S}. Kiểm tra phụ thuộc hàm tương đương: Kiểm tra phụ thuộc hàm X ® Y có là thành viên của F+: Function: Member (F, X ® Y) Vào: F là tập phụ thuộc hàm. Phụ thuộc hàm X ® Y cần kiểm tra. Ra: true hoặc false. Begin: Gọi baodong là tập thuộc tính chứa bao đóng của X+. If (Y là tập con của baodong) { Return true; } Else Return false; EndIf; End. Thuật toán kiểm tra phụ thuộc hàm f trong F có thuộc G+: Function: derives(F, G) Vào: F là tập phụ thuộc hàm. G là tập phụ thuộc hàm. Ra: true hoặc false. Begin: Ketqua = true; Foreach ( phụ thuộc hàm X ® Y trong G) { Ketqua=Ketqua && (kiểm tra X®Y có là thành viên của F+); } Return Ketqua; End. Thuật toán kiểm tra F có tương đương với G: Function: Equivalence(F, G) Vào: F là tập phụ thuộc hàm. G là tập phụ thuộc hàm. Ra: true hoặc false. Begin: Gọi f là phụ thuộc hàm trong F. Gọi g là phụ thuộc hàm trong G. Return (kiểm tra f trong G) && (kiểm tra g trong F); End. Ví dụ: Cho lược đồ quan hệ Q (A, B, C, D, E) hai tập phụ thuộc hàm: F={A®BC, A®D, CD®E} và G={A®BCE,A®ABD,CD®E} F có tương đương với G không? Giải: " f Î F thì f Í G+ ? Xét A®BC: A+G = ABCED BC Î ABCED = A+G Vậy: A ® BC Î G+. Tương tự: Lần lượt xét các phụ thuộc hàm A®D, CD®E Î G+. Kết luận: f Í G+. (1) " g Î G thì g Í F+ ? Xét A®BCE: A+F = ABCED BCE Î ABCED = A+F Vậy: A ® BCE Î F+. Tương tự: Lần lượt xét các phụ thuộc hàm A®ABD,CD®E Î G+. Kết luận: g Í F+. (2) Từ (1) và (2): ta nói F º G. Tìm phủ tối tiểu của một tập phụ thuộc hàm: Thuật toán: MinimumCover (F) Vào: F: là tập phụ thuộc hàm trong Q. Ra: Tập phụ thuộc hàm. Begin: Bước 1: Với mỗi phụ thuộc hàm X ® Y trong F, ta xét xem X có dư thừa không: Foreach (phụ thuộc hàm X ® Y trong F) { Foreach (thuộc tính B trong X) { If (member (F, X – B ® Y)) { Thay X ® Y trong F bằng B ® Y; } } } Bước 2: Với mỗi phụ thuộc hàm X ® Y trong F, ta xét xem Y nhiều hơn 1 thuộc tính không. foreach (PhuThuocHam X ® Y trong F) { if (số thuộc tính trong Y > 1) { foreach (mỗi thuộc tính C trong Y) { Thêm X ® C vào F; } Xóa X ® Y trong F; } } Bước 3: Kiểm tra xem trong F có tồn tại phụ thuộc hàm thừa không: foreach (mỗi phụ thuộc hàm X ® Y trong F) { If (Equivalence(F – {X ® Y}, F)) Xóa phụ thuộc hàm X ® Y trong F; } End. Ví dụ: Cho lược đồ quan hệ Q(A, B, C, D) và tập phụ thuộc hàm F như sau: F={AB ® CD; B ® C; C ® D} Hãy tính phủ tối tiểu của F. Giải: Bước 1: AB®CD là phụ thuộc hàm có vế trái dư thừa? B → CD Î F+? trả lời: B+=BCD Þ B ® CD Î F+ Vậy AB ® CD là phụ thuộc hàm có vế trái dư thừa A Þ kết quả của bước 1 là: F º {B ® CD; B ® C; C ® D} Bước 2: Kết quả của bước 2 là: F º {B ® D; B ® C;C ® D} = F1tt Bước 3: Trong F1tt, B ® C là phụ thuộc hàm dư thừa? B®CÎG+? với G = F1tt-{B®C}={B®D; C®D} BG+=BD Þ B®C Ï G+ Þ trong F1tt B ® C không dư thừa. Trong F1tt,B ® D là phụ thuộc hàm dư thừa? B ® D Î G+? với G = F1tt - {B ® D}={B ® C;C ® D} BG+=BCD Þ B ® D Î G+ Þ trong F1tt, B ® D dư thừa. Kết quả của bước 3 cho phủ tối tiểu: F º {B ® C; C ® D} = Ftt Xác định dạng chuẩn: Thuật toán kiểm tra phụ thuộc hàm hiển nhiên: Function: isPhuThuocHienNhien() Vào: Æ Ra: true hoặc false. Begin: Cho phụ thuộc hàm X ® Y. If (Y là tập con X) Return true; Else Return false; End. Thuật toán kiểm tra phụ thuộc hàm nguyên tố: Function: isPrimitive(X®Y, F) Vào: X®Y là phụ thuộc hàm cần kiểm tra. F là tập phụ thuộc hàm trong quan hệ. Ra: true hoặc false. Begin: Foreach (mỗi phụ thuộc hàm f trong F – { X®Y }) { If ((vế trái của f là tập con của X) && (vế phải của f là tập con của Y)) Return false; } Return true. End. Thuật toán kiểm tra phụ thuộc hàm đầy đủ: Function: isPhuThuocDayDu(A, X, F) Vào: A là thuộc tính không khóa. X là thuộc tính khóa. F là tập phụ thuộc hàm. Ra: true hoặc false. Begin: Gọi BaoDong là kết quả của việc tìm bao đóng của X. If (A không là con của BaoDong) { Return false. } Gọi XA là phụ thuộc hàm có vế trái là X, vế phải là A. If (XA không là phụ thuộc hàm nguyên tố) { Return false. } Return true. End. Thuật toán kiểm tra chuẩn 2: Function: isDC2 (F) Vào: F là tập phụ thuộc hàm trong quan hệ. Ra: true hoặc false. Begin Tìm khóa(). Gọi TapKhoa là tập thuộc tính khóa vừa tìm được. Gọi Khoa là 1 thuộc tính trong TapKhoa Gọi KhongKhoa là thuộc tính không khóa. Foreach (KhongKhoa trong tập thuộc tính không khóa) { If (Không là phụ thuộc hàm đầy đủ (KhongKhoa, Khoa, F)) { Return false; } EndIf; } Return true; End; Thuật toán kiểm tra chuẩn 3: Function: isDC3 (F) Vào: F là tập phụ thuộc hàm trong quan hệ. Ra: true hoặc false. Begin Tìm khóa; Int count = số phụ thuộc hàm trong quan hệ. Int countVT = 0; Int countVP = 0; Foreach(phụ thuộc hàm trong tập phụ thuộc hàm) { If (phụ thuộc hàm không là phụ thuộc hàm hiển nhiên) { If(vế trái của phụ thuộc hàm là chứa khóa) countVT++; If(vế phải của phụ thuộc hàm là thuộc tính khóa) countVP++; } } If(countVT = = count || countVP = = count) Return true; Else Return false; End; Thuật toán kiểm tra BCK: Function: isDCBCK (F) Vào: F là tập phụ thuộc hàm trong quan hệ. Ra: true hoặc false. Begin Tìm khóa; Int count = số phụ thuộc hàm trong quan hệ. Int countVT = 0; Foreach(thuộc tính khóa trong tập thuộc tính khóa) { Foreach(phụ thuộc hàm trong tập phụ thuộc hàm) { If(phụ thuộc hàm không là phụ thuộc hàm hiển nhiên) { If(thuộc tính khóa là tập con của vế trái của phụ thuộc hàm) countVT++; } } } If(countVT = = count) Return true; Else Return false; End; Thuật toán kiểm tra dạng chuẩn của một lược đồ quan hệ: Function: DangChuan () Vào: Lược đồ quan hệ Q Tập phụ thuộc hàm F. Ra: Khẳng định Q đạt dạng chuẩn gì. Bước 1: Tìm tất cả các khóa của Q. Bước 2: Kiểm tra chuẩn 1: Mặc định, chuẩn 1 luôn luôn đúng. Qua bước 3. Bước 3: Kiểm tra chuẩn 2. If (là chuẩn 2) Qua bước 4. Else Kết luận lược đồ quan hệ đạt chuẩn 1. Bước 4: Kiểm tra chuẩn 3. If (là dạng chuẩn 3) Qua bước 5. Else Lược đồ quan hệ đạt dạng chuẩn 2. Bước 5: Kiểm tra chuẩn BCK. If (là chuẩn BCK) Kết luận lược đồ quan hệ đạt chuẩn BCK. Else Kết luận lược đồ quan hệ đạt chuẩn 3. Chuẩn hóa: Thuật toán phân rã: Function: PhanRa(C, F, Fnew) Vào: C: mảng chứa các quan hệ Qi sau khi thực hiện phân rã. F: tập phụ thuộc hàm trong quan hệ. Fnew: tập phụ thuộc hàm trong mỗi Qi. Ra: Æ Begin: TapThuocTinh Qplus = closure(F); TapPhuThuocHam Fstar = F; Bước 1: Xóa các phụ thuộc hàm X ® Y có X È Y = Qplus. foreach (phụ thuộc hàm X ® Y trong F) { TapThuocTinh tmp; Thêm X vào tmp; Thêm Y vào tmp; if (tmp = = Qplus) Xóa X ® Y trong Fstar; } Bước 2: kiểm tra số phụ thuộc hàm trong Fstar: if (số phụ thuộc hàm trong Fstar = = 0) { Thêm các thuộc tính trong quan hệ vào C; foreach (PhuThuocHam pth in F) { Fnew.Add(pth); } return; //kết thúc thuật toán. } else { QuanHe Q1; QuanHe Q2; TapPhuThuocHam F1; TapPhuThuocHam F2; K là khóa của Q. ttKhoa là tập thuộc tính khóa trong Q. //Chọn PhuThuocHam X ® A để bắt đầu phân rã foreach (PhuThuocHam XA Î F) { if (!XA.vetrai.isChua1khoa(K) && !XA.vephai.isLaThanhVienCua1khoa(ttKhoa)) { Thêm X vào Q1; Thêm A vào Q1; Q2.MangThuocTinh = (Q - A).MangThuocTinh; Thoát khỏi vòng for. } } foreach (phụ thuộc hàm Z ® B in F) { TapThuocTinh tmp; Thêm B vào tmp; Thêm Z vào tmp; if (tmp.LatapCon(Q1)) { F1.Add(Z ® B); continue; } if (tmp.LatapCon(Q2)) F2.Add(Z ® B); } Q1.PhanRa(C, F1, Fnew); Q2.PhanRa(C, F2, Fnew); } } End. Ví dụ: Cho Q(S, D, I, M) F = {SI ® D; SD ® M}. Hãy phân rã quan hệ trên. Giải: Bước 1: SI ® D: SI È D = SID ¹ Q+ = SDIM. SD ® M: SD È M = SDM ¹ Q+ = SDIM. Ta không xóa phụ thuộc hàm nào trong F. Bước 2: Chọn SI ® D là phụ thuộc hàm đầu tiên để phân rã. Þ Q1(SDI) : F1 = SI®D; Þ Q2(SIM) : SD ® M không là con của Q1, Q2 không thể thêm vào Q1, Q2. Þ F2 = Æ; Vậy sau khi phân rã ta được Q1 (SDI) và Q2 (SIM); bị mất phụ thuộc hàm SD ® M. Phương pháp phân rã bảo toàn thông tin và phụ thuộc hàm: Function: TongHopCaiTien (Q, F) Vào: Q: lược đồ quan hệ. F: tập phụ thuộc hàm. Ra: Một phân rã sao cho mỗi lược đồ quan hệ con đều đạt chuẩn 3 vừa bảo toàn thông tin vừa bảo toàn phụ thuộc hàm. Begin: Bước 1: Tìm Ftt: là phủ tối tiểu của F. Bước 2: Foreach (phụ thuộc hàm f trong Ftt) { If ($ f: VT(f) È VP(f) = = Q) { Q không thể phân rã. } } If ($ thuộc tính Î Q và thuộc tính Ï Ftt) { Tạo thành 1 quan hệ Q1 (thuộc tính). } Foreach (X ® A Î Ftt) { Tạo thành quan hệ Qi(XA). } Foreach (quan hệ q Î Qi) { Tìm khóa K của Q; If ($ q chứa khóa K của Q) { Kết thúc thuật toán; } Tạo thành quan hệ (K); } End. Ví dụ: Cho Q(ABCDEGH), F={AB®D; EH®G; G®C; D®C} Hãy phân rã Q thành các lược đồ con ở dạng chuẩn 3 vừa bảo toàn thông tin vừa bảo toàn phụ thuộc hàm. Giải: Tìm phủ tối tiểu Ftt của F. Ftt = F = {AB®D; EH®G; G®C; D®C} Áp dụng thuật toán Q được phân thành lược đồ CSDL sau: Q1{ABD), Q2(EHG), Q3(GC), Q4(DC) Tìm khóa của Q: khóa của Q là {A, B, E, H} Q1,Q2,Q3,Q4 không chứa khóa Þ để bảo toàn thông tin cần có Q5(A,B,E,H). vậy kết quả của phân rã là: Q1,Q2,Q3,Q4, Q5. Biểu diễn một cấu trúc CSDL quan hệ sang lược đồ quan hệ: C = {Qi}, " Qi có một tập khóa Ki. Bước 1: Biến C thành phân rã đồng nhất: Qi, Qj có khóa là Ki, Kj. Nếu Ki « Kj thì gộp Qi, Qj lại thành 1 quan hệ. " Qi, nếu Q+I có chứa 1 khóa Kj của Qj thì phải chứa tất cả các khóa của của Qj. Bước 2: Tạo nút và quan hệ nút: Mỗi quan hệ Qi là một nút Ni. Bước 3: Tạo nút bản lề và quan hệ nút bản lề (các thuộc tính xuấ hiện trên nhiều quan hệ): " Qi, Qj: Qij = Qi Ç Qj. Chừng nào: Q+ij ¹ Æ thì: Xác định tất cả các khóa của Qij (ký hiệu KQ+ij) Nếu !$ Qh Î C sao cho 1 khóa của Qh là một khóa của Qij thì tạo 1 nút bản lề Nbl với quan hệ Qbl = KQ+ij Ngược lại: tính lại thuộc tính : Q+ij = Q+ij - KQ+ij Bước 4: Tạo cung và quan hệ cung: chỉ tạo số khung tối thiểu xuất phát từ 1 nút. " Ni ứng với quan hệ Qi, xác định: PTH (Ni) = {Nj với Qj sao cho Q+i É KQ+j} PTH-thừa (Ni) = {Nj Î PTH (Ni) : $ Nh Î PTH (Ni) với Qh sao cho KQ+h É KQ+j} Lồng khóa (Ni) = {Nj với Qj sao cho KQ+i É KQ+j} Lồng khóa thừa (Ni) = {Nj Î Lồng khóa (Ni) : $ Nh Î Lồng khóa(Ni) với Qh sao cho KQ+h É KQ+j} Cung (Ni) = { (PTH (Ni) - PTH-thừa (Ni)) È (Lồng khóa (Ni) - Lồng khóa thừa (Ni))} " Nj Î Cung (Ni) thì: Tạo 1 cung có hướng cij từ Ni ® Nj. Qij = Qi [KQ+i È KQ+j]. Bước 5: Hủy những nút bản lề thừa: " Nk sao cho: Qk có 1 khóa duy nhất là Kk. Không có thuộc tính nào khác ngoài khóa Chỉ có một cung vào Nk xuất phát từ nút Ni Thì : Nhập Nk vào Ni Hủy cung cik. Bước 6: Mịn hóa các quan hệ: " Ni với Qi thì: " Nj Î Cung (Ni) với Qj thì: Hủy khỏi Q+i những thuộc tính khóa của Qj mà không phải là thuộc tính khóa của Qi. Bước 7: Tạo cung vô hướng: nếu toàn những cung có hướng thì không làm bước này. " Nk sao cho: Q+k = KQ+k (Qk không có thuộc tính không khóa) Chỉ có 2 cung ra khỏi Nk (không có cung vào), đến Ni, Nj với Qi, Qj sao cho KQk = KQi È KQj. Thì: Tạo 1 cung vô hướng nối Ni, Nj với Qij = Qk. Hủy nút Nk. Hủy 2 cung xuất phát từ Nk. Kết thúc. GIỚI THIỆU CHƯƠNG TRÌNH Các chức năng của chương trình: Tạo quan hệ. Lưu quan hệ dưới dạng tập tin .xml. Mở quan hệ. Tìm khóa của quan hệ. Tìm dạng chuẩn của quan hệ. Chuẩn hóa quan hệ bằng phương pháp phân rã. Chuẩn hóa quan hệ bằng phương pháp tổng hợp. Tìm phủ tối tiểu. Tìm đường đi của một nút trong lược đồ quan hệ. Giới thiệu chương trình: Giao diện chính của chương trình: Hình 1. Giao diện chương trình Các chức năng trên thanh Menu: Khi người dùng click vào menu Hệ thống chương trình sẽ hiển thị như hình bên dưới: Hình 2. Menu hệ thống Click vào chức năng tạo lược đồ quan hệ, chương trình sẽ hiển thị cữa sổ: Cho phép người dùng tạo các quan hệ. Tập thuộc tính của quan hệ. Tập phụ thuộc hàm của quan hệ. Thuộc tính ở vế trái của phụ thuộc hàm. Thuộc tính ở vế phải của phụ thuộc hàm. Hình 3. Tạo lược đồ quan hệ. Trong ô tập quan hệ, người dùng click phải vào chọn chức năng thêm quan hệ để tạo ra 1 quan hệ mới như hình bên dưới: Hình 4. Menu quan hệ Để tạo phụ thuộc hàm, người dùng chọn thuộc tính trong ô thuộc tính và kéo vào thuộc tính bên vế phải hoặc trái. Phụ thuộc hàm được tạo sẽ hiển thị trên ô phụ thuộc hàm. Click vào chức năng mở lược đồ quan hệ, chương trình sẽ gọi Dialog Open của Window cho phép người dùng chọn một tập tin .xml để mở: Hình 5. Dialog Open Sau khi chọn tập tin .xml, chương trình sẽ hiển thị như bên dưới: Hình 6. Giao diện mở tập tin .xml Click phải vào quan hệ, sẽ hiển thị menu như hình 4. Người dùng có thể click vào các chức năng trên menu này hoặc các button bên phía trái của quan hệ để sử dụng các chức năng của chương trình. Tìm khóa: click chọn quan hệ cần tìm khóa rồi chọn chức năng tìm khóa, chương trình sẽ hiển thị Dialog cho người dùng xem tất cả các khóa trong quan hệ mà chương trình tìm được như hình bên dưới: Hình 7. Dialog khóa của quan hệ Nếu các thuộc tính của quan hệ chưa được nhập thì chương trình sẽ không thể tìm khóa và hiển thị Dialog nhắc nhở người dùng nhập thuộc tính vào: Hình 8. Dialog nhập thuộc tính vào quan hệ Tìm phủ tối tiểu: click chọn quan hệ cần tìm phủ tối tiểu rồi chọn chức năng tìm phủ tối tiểu, chương trình sẽ hiển thị Dialog cho người dùng xem phủ tối tiểu mà chương trình tìm được dựa vào phụ thuộc hàm của quan hệ như hình bên dưới: Hình 9. Dialog phủ tối tiểu của quan hệ Xác định dạng chuẩn: click chọn quan hệ cần tìm phủ tối tiểu rồi chọn chức năng xác định dạng chuẩn, chương trình sẽ hiển thị Dialog cho người dùng xem dạng chuẩn của quan hệ mà chương trình tìm được, nếu quan hệ đạt dạng chuẩn thấp thì chương trình sẽ hiển thị Dialog dạng chuẩn thấp, ngược lại sẽ hiển thị Dialog dạng chuẩn cao: Hình 10. Dialog dạng chuẩn thấp của quan hệ Hình 11. Dialog dạng chuẩn cao của quan hệ. Chuẩn hóa: khi quan hệ đạt dạng chuẩn thấp người dùng click vào chức năng chuẩn hóa để tạo thành các quan hệ con đạt dạng chuẩn cao hơn. Hình 12. Giao diện chuẩn hóa. TỔNG KẾT VÀ ĐỊNH HƯỚNG PHÁT TRIỂN Những chức năng chương trình đã làm được: Tạo quan hệ. Lưu quan hệ dưới dạng tập tin .xml. Mở quan hệ. Tìm khóa của quan hệ. Tìm phủ tối tiểu của quan hệ. Tìm dạng chuẩn của quan hệ. Chuẩn hóa quan hệ bằng phương pháp phân rã. Chuẩn hóa quan hệ bằng phương pháp tổng hợp. Tìm đường đi của một nút trong lược đồ quan hệ. Hướng phát triển: Giao diện chương trình đẹp hơn. Thêm một số chức năng để chương trình hoàn thiện hơn. Tài liệu tham khảo: [1] Giáo trình cơ sở dữ liệu của thầy Cao Tùng Anh. [2] Giáo trình cơ sở dữ liệu của trường Cao Đẳng Công Nghiệp 4. [3] Giáo trình thiết kế cơ sở dữ liệu của thầy Văn Như Bích. [4] MSDN trong Visual Studio 2005. PHỤ LỤC Giới thiệu về .NET: .NET Framework là một platform mới làm đơn giản việc phát triển ứng dụng trong môi trường phân tán của Internet. .NET Framework được thiết kế đầy đủ để đáp ứng theo quan điểm sau: Để cung cấp một môi trường lập trình hướng đối tượng vững chắc, trong đó mã nguồn đối tượng được lưu trữ và thực thi một cách cục bộ. Thực thi cục bộ nhưng được phân tán trên Internet, hoặc thực thi từ xa. Để cung cấp một môi trường thực thi mã nguồn mà tối thiểu được việc đóng gói phần mềm và sự tranh chấp về phiên bản. Để cung cấp một môi trường thực thi mã nguồn mà đảm bảo việc thực thi an toàn mã nguồn, bao gồm cả việc mã nguồn được tạo bởi hãng thứ ba hay bất cứ hãng nào mà tuân thủ theo kiến trúc .NET. Để cung cấp một môi trường thực thi mã nguồn mà loại bỏ được những lỗi thực hiện các script hay môi trường thông dịch. Để làm cho những người phát triển có kinh nghiệm vững chắc có thể nắm vững nhiều kiểu ứng dụng khác nhau. Như là từ những ứng dụng trên nền Windows đến những ứng dụng dựa trên web. Để xây dựng tất cả các thông tin dựa triên tiêu chuẩn công nghiệp để đảm bảo rằng mã nguồn trên .NET có thể tích hợp với bất cứ mã nguồn khác. .NET Framework có hai thành phần chính: Common Language Runtime (CLR) và thư viện lớp .NET Framework. CLR là nền tảng của .NET Framework. Chúng ta có thể hiểu runtime như là một agent quản lý mã nguồn khi nó được thực thi, cung cấp các dịch vụ cốt lõi như: quản lý bộ nhớ, quản lý tiểu trình, và quản lý từ xa. Ngoài ra nó còn thúc đẩy việc sử dụng kiểu an toàn và các hình thức khác của việc chính xác mã nguồn, đảm bảo cho việc thực hiện được bảo mật và mạnh mẽ. Thật vậy, khái niệm quản lý mã nguồn là nguyên lý nền tảng của runtime. Mã nguồn mà đích tới runtime thì được biết như là mã nguồn được quản lý (managed code). Trong khi đó mã nguồn mà không có đích tới runtime thì được biết như mã nguồn không được quản lý (unmanaged code). Thư viện lớp, một thành phần chính khác của .NET Framework là một tập hợp hướng đối tượng của các kiểu dữ liệu được dùng lại, nó cho phép chúng ta có thể phát triển những ứng dụng từ những ứng dụng truyền thống command-line hay những ứng dụng có giao diện đồ họa (GUI) đến những ứng dụng mới nhất được cung cấp bởi ASP.NET, như là Web Form và dịch vụ XML Web. Sơ đồ kiến trúc của .NET Framework Web Services Web Forms Windows Forms Data and XML classes (ADO.NET, SQL, XSLT, Xpath, XML, ) Framework Base Class Library (IO, String, net, security, threading, text, reflection, collection, GUI, XML/SOAP) Common Language Runtime(CLR) Common Type Spec. (CTS) Common Lang. Spec. (CLS) Windows Platform Ngôn ngữ C#: Sơ lược về C#: Ngôn ngữ C# là một ngôn ngữ được dẫn xuất từ C và C++, nhưng nó được tạo từ nền tảng phát triển hơn. Microsoft bắt đầu với công việc trong C và C++ và thêm vào những đặc tính mới để làm cho ngôn ngữ này dễ sử dụng hơn. Nhiều trong số những đặc tính này khá giống với những đặc tính có trong ngôn ngữ Java. Không dừng lại ở đó, Microsoft đưa ra một số mục đích khi xây dựng ngôn ngữ này. Những mục đích này được được tóm tắt như sau: C# là ngôn ngữ đơn giản: vì nó dựa trên nền tảng C và C++. Nếu chúng ta thân thiện với C và C++ hoậc thậm chí là Java, chúng ta sẽ thấy C# khá giống về diện mạo, cú pháp, biểu thức, toán tử và những chức năng khác được lấy trực tiếp từ ngôn ngữ C và C++, nhưng nó đa được cải tiến để làm cho ngôn ngữ đơn giản hơn. Một vài trong các sự cải tiến là loại bỏ các dư thừa, hay là thêm vào những cú pháp thay đổi. C# là ngôn ngữ hiện đại: vì C# có các đặc tính như: xử lý ngoại lệ, thu gom bộ nhớ tự động, những kiểu dữ liệu mở rộng, và bảo mật mã nguồn. C# là ngôn ngữ hướng đối tượng: C# hỗ trợ tất cả những đặc tính: đóng gói (encapsulation), kế thừa (inheritance), và đa hình (polymorphism). Nạp chồng phương thức: Thông thường khi xây dựng các lớp, ta có mong muốn là tạo ra nhiều hàm có cùng tên. Ta có thể xây dựng nhiều các phương thức cùng tên nhưng nhận các tham số khác nhau. Chức năng này được gọi là nạp chồng phương thức. Một ký hiệu (signature) của một phương thức được định nghĩa như tên của phương thức cùng với danh sách tham số của phương thức. Hai phương thức khác nhau khi ký hiệu của chúng khác là khác nhau tức là khác nhau khi tên phương thức khác nhau hay danh sách tham số khác nhau. Danh sách tham số được xem là khác nhau bởi số lượng các tham số hoặc là kiểu dữ liệu của tham số. Ví dụ đoạn mã sau, phương thức thứ nhất khác phương thức thứ hai do số lượng tham số khác nhau. Phương thức thứ hai khác phương thức thứ ba do kiểu dữ liệu tham số khác nhau: void myMethod( int p1 ); void myMethod( int p1, int p2 ); void myMethod( int p1, string p2 ); Một lớp có thể có bất cứ số lượng phương thức nào, nhưng mỗi phương thức trong lớp phải có ký hiệu khác với tất cả các phương thức thành viên còn lại của lớp. Một số kiểu dữ liệu: Môi trường .NET cung cấp rất đa dạng số lượng các lớp về tập hợp, bao gồm: Array, ArrayList, Queue, Stack, BitArray, NameValueCollection, và StringCollection. Trong số đó tập hợp đơn giản nhất là Array, đây là kiểu dữ liệu tập hợp mà ngôn ngữ C# hỗ trợ xây dựng sẵn. Và thành phần không thể thiếu của kiểu dữ liệu tập hợp là phần chỉ mục indexer, đây là cách thiết lập để làm cho việc truy cập những thuộc tính giống nhau trở nên đơn giản hơn, một lớp được chỉ mục thì giống như một mảng. .NET cũng cung cấp nhiều các giao diện, như IEnumerable và ICollection. Những phần thực thi của các giao diện này cung cấp các tiêu chuẩn để tương tác với các tập hợp. Array: Mảng là một tập hợp có thứ tự của những đối tượng, tất cả các đối tượng này cùng một kiểu. Ngôn ngữ C# cung cấp cú pháp chuẩn cho việc khai báo những đối tượng Array. Tuy nhiên, cái thật sự được tạo ra là đối tượng của kiểu System.Array. Khai báo mảng Chúng ta có thể khai báo một mảng trong C# với cú pháp theo sau: [] Cặp dấu ngoặc vuông ([]) báo cho trình biên dịch biết rằng chúng ta đang khai báo một mảng. Kiểu dữ liệu là kiểu của các thành phần chứa bên trong mảng. Chúng ta tạo thể hiện của mảng bằng cách sử dụng từ khóa new như sau: int[] myIntArray; myIntArray = new int[6]; Khai báo này sẽ thiết lập bên trong bộ nhớ một mảng chứa sáu số nguyên. Truy cập các thành phần trong mảng Để truy cập vào thành phần trong mảng ta có thể sử dụng toán tử chỉ mục ([]). Mảng dùng cơ sở 0, do đó chỉ mục của thành phần đầu tiên trong mảng luôn luôn là 0. Như ví dụ trước thành phần đầu tiên là myArray[0]. Mảng là đối tượng nên có những thuộc tính. Một trong những thuộc tính hay sử dụng là Length, thuộc tính này sẽ báo cho biết số đối tượng trong một mảng. Một mảng có thể được đánh chỉ mục từ 0 đến Length –1. Do đó nếu có năm thành phần trong mảng thì các chỉ mục là: 0, 1, 2, 3, 4. Khởi tạo thành phần của mảng Chúng ta có thể khởi tạo nội dung của một mảng ngay lúc tạo thể hiện của mảng bằng cách đặt những giá trị bên trong dấu ngoặc ({}). C# cung cấp hai cú pháp để khởi tạo các thành phần của mảng, một cú pháp dài và một cú pháp ngắn: int[] myIntArray = new int[5] { 2, 4, 6, 8, 10}; int[] myIntArray = { 2, 4, 6, 8, 10}; Không có sự khác biệt giữa hai cú pháp trên, và hầu hết các chương trình đều sử dụng cú pháp ngắn hơn do sự tự nhiên và lười đánh nhiều lệnh của người lập trình. Sử dụng từ khóa params Chúng ta có thể tạo một phương thức rồi sau đó hiển thị các số nguyên ra màn hình console bằng cách truyền vào một mảng các số nguyên và sử dụng vòng lặp foreach để duyệt qua từng thành phần trong mảng. Từ khóa params cho phép chúng ta truyền một số biến của tham số mà không cần thiết phải tạo một mảng. Ví dụ, chúng ta sẽ tạo một phương thức tên DisplayVals(), phương thức này sẽ lấy một số các biến của tham số nguyên: public void DisplayVals( params int[] intVals) Phương thức có thể xem mảng này như thể một mảng được tạo ra tường minh và được truyền vào tham số. Sau đó chúng ta có thể tự do lặp lần lượt qua các thành phần trong mảng giống như thực hiện với bất cứ mảng nguyên nào khác: foreach (int i in intVals) { Console.WriteLine(“DisplayVals: {0}”, i); } Tuy nhiên, phương thức gọi không cần thiết phải tạo tường minh một mảng, nó chỉ đơn giản truyền vào các số nguyên, và trình biên dịch sẽ kết hợp những tham số này vào trong một mảng cho phương thức DisplayVals, ta có thể gọi phương thức như sau: t.DisplayVals(5,6,7,8); và chúng ta có thể tự do tạo một mảng để truyền vào phương thức nếu muốn: int [] explicitArray = new int[5] {1,2,3,4,5}; t.DisplayArray(explicitArray); Câu lệnh lặp foreach Câu lệnh lặp foreach khá mới với những người đa học ngôn ngữ C, ừ khóa này được sử dụng trong ngôn ngữ Visual Basic. Câu lệnh foreach cho phép chúng ta lặp qua tất cả các mục trong một mảng hay trong một tập hợp. Cú pháp sử dụng lệnh lặp foreach như sau: foreach ( in ) { // thực hiện thông qua tương ứng với // từng mục trong mảng hay tập hợp } Bộ chỉ mục: Đôi khi chúng ta chúng ta mong muốn truy cập một tập hợp bên trong một lớp như thể bản thân lớp là một mảng. Ví dụ, giả sử chúng ta tạo một điều khiển kiểu ListBox tên là myListBox chứa một danh sách các chuỗi lưu trữ trong một mảng một chiều, một biến thành viên private myStrings. Một List Box chứa các thuộc tính thành viên và những phương thức và thêm vào đó mảng chứa các chuỗi của nó. Tuy nhiên, có thể thuận tiện hơn nếu có thể truy cập mảng ListBox với chỉ mục như thể ListBox là một mảng thật sự. Ví dụ, ta có thể truy cập đối tượng ListBox được tạo ra như sau: string theFirstString = myListBox[0]; string theLastString = myListBox[myListBox.Length - 1]; Bộ chỉ mục là một cơ chế cho phép các thành phần client truy cập một tập hợp chứa bên trong một lớp bằng cách sử dụng cú pháp giống như truy cập mảng ([]). Chỉ mục là một loại thuộc tính đặc biệt và bao gồm các phương thức get() và set() để xác nhận những hành vi của chúng. Chúng ta có thể khai báo thuộc tính chỉ mục bên trong của lớp bằng cách sử dụng cú pháp như sau: this [ ] { get; set; } Kiểu trả về được quyết định bởi kiểu của đối tượng được trả về bởi bộ chỉ mục, trong khi đó kiểu của đối mục được xác định bởi kiểu của đối mục dùng để làm chỉ số vào trong tập hợp chứa đối tượng đích. Mặc dù kiểu của chỉ mục thường dùng là các kiểu nguyên, chúng ta cũng có thể dùng chỉ mục cho tập hợp bằng các kiểu dữ liệu khác, như kiểu chuỗi. Chúng ta cũng có thể cung cấp bộ chỉ mục với nhiều tham số để tạo ra mảng đa chiều. Từ khóa this tham chiếu đến đối tượng nơi mà chỉ mục xuất hiện. Như một thuộc tính bình thường, chúng ta cũng có thể định nghĩa phương thức get() và set() để xác định đối tượng nào trong mảng được yêu cầu truy cập hay thiết lập. Giao diện tập hợp: Môi trường .NET cung cấp những giao diện chuẩn cho việc liệt kê, so sánh, và tạo các tập hợp. Một số các giao diện trong số đó được liệt kê trong bảng sau: Giao diện Mục đích IEnumerable Liệt kê thông qua một tập hợp bằng cách sử dụng foreach. ICollection Thực thi bởi tất cả các tập hợp để cung cấp phương thức CopyTo() cũng như các thuộc tính Count, ISReadOnly, ISSynchronized, và SyncRoot. IComparer So sánh giữa hai đối tượng lưu giữ trong tập hợp để sắp xếp các đối tượng trong tập hợp. Ilist Sử dụng bởi những tập hợp mảng được chỉ mục IDictionary Dùng trong các tập hợp dựa trên khóa và giá trị như Hashtable và SortedList. IDictionaryEnumerator Cho phép liệt kê dùng câu lệnh foreach qua tập hợp hỗ trợ Idictionary. Bảng: Giao diện cho tập hợp Sau đây là phần trình bày về giao diện IEnumerable: Chúng ta có thể hỗ trợ cú pháp foreach trong lớp ListBoxTest bằng việc thực thi giao diện IEnumerator. Giao diện này chỉ có một phương thức duy nhất là GetEnumerator(), công việc của phương thức là trả về một sự thực thi đặc biệt của IEnumerator. Do vậy, ngữ nghĩa của lớp Enumerable là nó có thể cung cấp một Enumerator: public IEnumerator GetEnumerator() { return (IEnumerator) new ListBoxEnumerator(this); } Enumerator phải thực thi những phương thức và thuộc tính IEnumerator. Chúng có thể được thực thi trực tiếp trong lớp chứa (trong trường hợp này là lớp ListBoxTest) hay bởi một lớp phân biệt khác. Cách tiếp cận thứ hai thường được sử dụng nhiều hơn, do chúng được đóng gói trong lớp Enumerator hơn là việc phân vào trong các lớp chứa. Do lớp Enumerator được xác định cho lớp chứa, vì theo như trên thì lớp ListBoxEnumerator phải biết nhiều về lớp ListBoxTest. Nên chúng ta phải tạo cho nó một sự thực thi riêng chứa bên trong lớp ListBoxTest. Lưu ý rằng phương thức GetEnumerator truyền đối tượng List-BoxTest hiện thời (this) cho enumerator. Điều này cho phép enumerator có thể liệt kê được các thành phần trong tập hợp của đối tượng ListBoxTest. Ở đây lớp thực thi Enumerator là ListBoxEnumerator, đây là một lớp private được định nghĩa bên trong lớp ListBoxTest. Lớp này thực thi đơn giản bao gồm một thuộc tính public, và hai phương thức public là MoveNext(), và Reset(). Đối tượng ListBoxTest được truyền vào như một đối mục của bộ khởi tạo. Ở đây nó được gán cho biến thành viên myLBT. Trong hàm khởi tạo này cũng thực hiện thiết lập giá trị biến thành viên index là -1, chỉ ra rằng chưa bắt đầu thực hiện việc enumerator đối tượng: public ListBoxEnumerator(ListBoxTest lbt) { this.lbt = lbt; index = -1; } Phương thức MoveNext() gia tăng index và sau đó kiểm tra để đảm bảo rằng việc thực hiện không vượt quá số phần tử trong tập hợp của đối tượng: public bool MoveNext() { index++; if (index >= lbt.strings.Length) return false; else return true; } Phương thức IEnumerator.Reset() không làm gì cả nhưng thiết lập lại giá trị của index là -1. Thuộc tính Current trả về đối tượng chuỗi hiện hành. Đó là tất cả những việc cần làm cho lớp ListBoxTest thực thi một giao diện IEnumerator. Câu lệnh foreach sẽ được gọi để đem về một enumerator, và sử dụng nó để liệt kê lần lượt qua các thành phần trong mảng.