Đề tài Chương trình hỗ trợ thiết kế cơ sở dữ liệu

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(S