Luận văn Ứng dụng phép dịch chuyển lược đồ quan hệ trong cơ sở dữ liệu

Armstrong Ao [7] B o = {F5, F10, F11} S o = {F1, F4} D o = {F3, F5, F6, F7} M o = {F4, F5, F8} 1.2.4. Bao đóng của tập thuộc tính Địn h n g h ĩ a Cho tập PTH F trên tập thuộc tính U và một tập con các thuộc tính X trong U. Bao đóng của tập thuộc tính X, ký hiệu X+ là tập thuộc tính Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 19 X + = {A U | X  AF+} Thuật toán tìm bao đóng của một tập thuộc tính Cho tập PTH F trên tập thuộc tính U và một tập con các thuộc tính X trong U. Để xác định bao đóng X+ của tập thuộc tính X ta xây dựng dãy bao nhau X (0)  X(1)  …  X(i) như sau  Xuất phát: Đặt X(0)=X,  Với i > 0, ta đặt  )( )()1( iXL FRL ii RXX      Nếu X(i+1) = X(i) thì dừng thuật toán và cho kết quả X + = X(i) . Algorithm Closure Format: Closure(X,F) Input: - Tập PTH F trên U - Tập con thuộc tính X của U Output: - Y = X+ = {A U | XA F+} Method Y:=X; repeat Z:=Y; for each FD LR in F do if L  Y then Y:=YR; endif; endfor; until Y=Z; return Y; end Closure. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 20 Thuật toán trên có độ phức tạp O(mn2 ), trong đó n là số lượng thuộc tính trong U, m là số lượng PTH trong tập F. Quy ước giản lược Ta thường viết XY thay vì viết XYF+ hoặc F╞ XY. Bài toán thành viên Cho tập thuộc tính U, một tập các PTH F trên U và một PTH f: XY trên U. Hỏi rằng f F+ (f có phải là thành viên của F+) hay không ? Địn h l ý (Định lý thành viên) XY  F + khi và chỉ khi Y  X + Thuật toán cho bài toán thành viên Algorithm IsMember Format: IsMember(f,F) Input: - Tập PTH F trên U - PTH f trên U Output: - True, nếu f F+; - False, trong trường hợp phủ định. Method IsMember := (RS(f)  Closure(LS(f),F)); end IsMember. Một số tính chất của bao đóng Cho LĐQH a = (U,F). Khi đó  X, Y  U ta có (C1) Tính phản xạ: X  X + (C2) Tính đồng biến: X  Y X + Y + (C3) Tính lũy đẳng: (X +)+ = X + Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 21 Ngoài ra, sử dụng ba tính chất (C1), (C2) và (C3) nói trên ta dễ dàng chứng minh các tính chất (C4)-(C8) sau đây: (C4) (XY) +  X +Y + (C5) (X + Y) + = (XY + ) + = ( XY) + (C6) XY khi và chỉ khi Y+ X+ (C7) XX+ và X+X (C8) X + = Y + khi và chỉ khi XY và YX 1.2.5. Phủ của tập PTH Địn h n g h ĩ a Cho hai tập PTH F và G trên cùng một tập thuộc tính U. Ta nói F suy dẫn ra được G, ký hiệu F╞ G, nếu gG: F╞ g. Ta nói F tương đương với G, ký hiệu F  G, nếu F╞ G và G╞ F. Nếu F  G ta nói G là một phủ của F. Ký hiệu F ≢ G có nghĩa F và G không tương đương. Cho tập PTH F trên tập thuộc tính U và X là tập con của U, ta dùng ký hiệu XF + trong trường hợp cần chỉ rõ bao đóng của tập thuộc tính X lấy theo tập PTH F. Phủ thu gọn tự nhiên Địn h n g h ĩ a Cho hai tập PTH F và G trên cùng một tập thuộc tính U. G là phủ thu gọn tự nhiên của F nếu 1. G là một phủ của F, và 2. G có dạng thu gọn tự nhiên theo nghĩa sau: 2a. Hai vế trái và phải của mọi PTH trong G rời nhau (không giao nhau.) f  G: LS(f)  RS(f) =  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 22 2b. Các vế trái của mọi PTH trong G khác nhau đôi một. f, g  G: f  g  LS(f)  LS(g) Thuật toán tìm phủ thu gọn tự nhiên Algorithm Natural_Reduced Format: Natural_Reduced(F) Input: - Tập PTH F Output: - Một phủ thu gọn tự nhiên G của F (i) G  F     (ii)LR  G: L R =      (iii)LiRi,LjRjG: ij  LiLj Method G:=; for each FD LR in F do Z:=R\L; if Z then if there is an FD LY in G then replace LY in G by LYZ else add LZ to G; endif; endif; endfor; return G; end Natural_Reduced. Nếu dùng kỹ thuật chỉ dẫn để tổ chức truy nhập trực tiếp tới các thuộc tính và PTH thì thuật toán thu gọn tự nhiên Natural_Reduced đòi hỏi độ phức tạp tính toán là O(mn) trong đó m là số lượng PTH trong tập F, n là số lượng thuộc tính trong U. Để ý rằng mn là chiều dài dữ liệu vào của thuật toán, do đó O(mn) chính là độ phức tạp tuyến tính theo chiều dài dữ liệu vào. Ta dễ dàng chứng minh tính đúng của mệnh đề sau, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 23 Mệnh đ ề Nếu F và G là hai tập PTH trên cùng một tập thuộc tính U thì F  G khi và chỉ khi X  U: XF + = XG + Phủ không dư Địn h n g h ĩ a Cho hai tập PTH F và G trên tập thuộc tính U. G được gọi là phủ không dư của F nếu (i) G là một phủ của F, và (ii) G có dạng không dư theo nghĩa sau: gG: G \{g} ≢ G Thuật toán tìm phủ không dư của tập PTH Algorithm Nonredundant Format: Nonredundant(F) Input: - Tập PTH F Output: - Một phủ không dư G của F (i) G  F (ii) g  G: G\{g} ≢ G Method G:=F; for each FD g in F do if IsMember(g,G\{g})then G:=G\{g}; endif; endfor; return G; end Nonredundant. Phủ thu gọn Phủ thu gọn trái Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 24 Địn h n g h ĩ a Cho hai tập PTH F và G trên tập thuộc tính U. G được gọi là phủ thu gọn trái của F nếu (i) G là một phủ của F, và (ii) (LRG,AL): G\{LR}{L\AR} ≢ G Thuật toán tìm phủ thu gọn trái của tập PTH Để ý rằng AL ta có L\A L, nên g: LRG,AL): G\{g}{L\AR}╞ LR, do đó ta chỉ cần kiểm tra G ╞ L\AR ? Algorithm Left_Reduced Format: Left_Reduced(F) Input: - Tập PTH F Output: - Một phủ thu gọn trái G của F (i) G  F (ii) g:LR G,AL: G\{g}{L\AR}≢G Method G:= F; for each FD g:L  R in F do X:=L; for each attribute A in X do if IsMember(L\AR,G)then delete A from L in G; endif; endfor; endfor; return G; end Left_Reduced. Phủ thu gọn phải Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 25 Địn h n g h ĩ a Cho hai tập PTH F và G trên tập thuộc tính U. G được gọi là phủ thu gọn phải của F nếu (i) G là một phủ của F, và (ii) (LRG, AR): G\{LR}{LR\A} ≢ G Thuật toán tìm phủ thu gọn phải của tập PTH Để ý rằng, AR: R\A R, nên (g: LRG,AR): G╞ LR\A do đó ta chỉ cần kiểm tra G\{LR}{LR\A}╞ LA. Algorithm Right_Reduced Format: Right_Reduced(F) Input: - Tập PTH F Output: - Một phủ thu gọn phải G của F (i) G  F (ii)(g:LR G,AR): G\{g}{LR\A}≢G Method G:= F; for each FD g:L  R in F do H:=G\{LR}; X:=R; for each attribute A in X do if A in Closure(L,H{LR\A})then delete A from R in G; endif; endfor; endfor; return G; end Right_Reduced. Phủ thu gọn Địn h n g h ĩ a Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 26 Cho hai tập PTH F và G trên tập thuộc tính U. G được gọi là phủ thu gọn của F nếu G đồng thời là phủ thu gọn trái và thu gọn phải của F. Thuật toán tìm phủ thu gọn của tập PTH Algorithm Reduced Format: Reduced(F) Input: - Tập PTH F Output: - Một phủ thu gọn của F Method return Right_Reduced(Left_Reduced(F)); end Reduced. Phủ tối tiểu Địn h n g h ĩ a Cho hai tập PTH F và G trên tập thuộc tính U. G được gọi là phủ tối tiểu của F nếu (i) G là một phủ thu gọn của F, (ii) Vế phải của mọi PTH trong G chỉ chứa một thuộc tính. Thuật toán tìm phủ tối tiểu của tập PTH Algorithm MinCover Format: MinCover(F) Input: - Tập PTH F Output: - Một phủ tối tiểu G của F Method // Tách mỗi PTH LR trong F thành các PTH có // vế phải chỉ chứa một thuộc tính LA, A  R G:=; for each FD LR in F do for each attribute A in R\L do if LA not_in G then Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 27 add LA to G; endif; endfor; endfor; G:=Nonredundant(Left_Reduced(G)); return G; end MinCover. 1.2.6. Khóa của lược đồ quan hệ Khóa của lược đồ quan hệ Địn h n g h ĩ a Cho LĐQH a = (U, F). Tập thuộc tính K  U được gọi là khoá của LĐQH a nếu (i) K + = U (ii) A K: (K \A)+ U Hai điều kiện trên tương đương với (i') KU (ii') A K: K\A ↛ U Nếu K thoả điều kiện (i) (hoặc (i')) thì K được gọi là một siêu khoá. Thuộc tính A  U được gọi là thuộc tính khoá (nguyên thuỷ hoặc cơ sở) nếu A có trong một khoá nào đấy. A được gọi là thuộc tính không khoá (phi nguyên thuỷ hoặc thứ cấp) nếu A không có trong bất kỳ khoá nào. Cho LĐQH a = (U, F). Ta ký hiệu UK là tập các thuộc tính khóa của a và U0 là tập các thuộc tính không khóa của a. Dễ thấy UK |Uo là một phân hoạch của U. C h ú ý Trong một số tàì liệu thuật ngữ khoá được dùng theo nghĩa siêu khoá và thuật ngữ khoá tối tiểu được dùng theo nghĩa khoá. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 28 Thuật toán tìm một khóa của LĐQH Tư tưởng: Xuất phát từ một siêu khóa K tùy ý của LĐQH, duyệt lần lượt các thuộc tính A của K, nếu bất biến (K\A)+ = U được bảo toàn thì loại A khỏi K. Có thể thay kiểm tra (K\A)+ = U bằng kiểm tra A (K\A)+. Algorithm Key Format: Key(U,F) Input: - Tập thuộc tính U - Tập PTH F Output: - Khóa K  U thỏa (i) K+ = U     (ii)AK: (K\A)+ U Method K:= U; for each attribute A in U do if A in Closure(K\A,F) then K:=K\A endif; endfor; return K; end Key. Thuật toán duyệt n thuộc tính, với mỗi thuộc tính thực hiện phép lấy bao đóng với độ phức tạp n2m. Tổng hợp lại, độ phức tạp tính toán của thuật toán là O(n3m). Một số tính chất của khóa Các tính chất đơn giản Cho LĐQH (U,F). Khi đó 1. K  U là một khoá khi và chỉ khi U phụ thuộc đầy đủ vào K. 2. Hai khoá khác nhau của một LĐQH không bao nhau. 3. Mọi LĐQH đều có ít nhất một khoá. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 29 Địn h l ý ( Đặc trưng của các thuộc tính khóa [7]) Cho K là một khóa của LĐQH a = (U,F). Khi đó với mọi tập con X của K ta có: X + K=X. Chứn g m i n h Vì X  X+ và X  K nên X  X+K. Ta cần chứng minh X+K  X. Giả sử AX+K và AX. Ta xét tập M = K\A. Dễ thấy X  M. Ta có, theo tính chất đồng biến của bao đóng, AX+  M+. Từ đây suy ra K  M+, do đó, theo tính chất lũy đẳng của bao đóng và tính chất khóa của K ta có, U = K+  M++ = M+, tức là M là bộ phận thực sự của khóa K lại đồng thời là siêu khóa, trái với định nghĩa khóa. Vậy A X ■ Địn h l ý (Công thức tính giao các khóa) Cho LĐQH a = (U,F) với n thuộc tính trong U và m PTH trong F. Gọi UI là giao các khóa của a. Khi đó có thể xác định giao các khóa bằng một thuật toán tuyến tính theo mn qua công thức  FRL I LRUU   )\(\ Chứn g m i n h Trước hết để ý rằng các PTH LR và L(R\L) là tương đương, do đó ta có thể giả thiết rằng mọi PTH trong F đều có dạng LR, LR = , tức là giả thiết rằng tập PTH F được cho dưới dạng thu gọn tự nhiên. Do giả thiết này ta có R\L=R. Dễ nhận thấy, theo công thức tính UI trong định lý, UI là tập các thuộc tính không có mặt trong vế phải của mọi PTH trong F, do đó chúng phải có mặt trong mọi khóa. Giả sử A là một thuộc tính có trong vế phải của PTH LAR' nào đó của F. Ta chứng minh A sẽ không xuất hiện trong một khóa K nào đấy của a. Thật vậy, xét tập X = U\A. Dễ thấy X  L và X+ = XAR' = U và do đó X là siêu khóa. Từ siêu khóa X không chứa A ta lấy ra được một khóa K không chứa A ■ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 30 Thuật toán xác định giao các khóa trong LĐQH Algorithm KeyIntersec Format: KeyIntersec(U,F) Input: - Tập thuộc tính U - Tập PTH F Output: - Giao các khóa  FRL LRUM   )\(\ Method M:=U; for each FD LR in F do M:= M\(R\L); endfor; return M; end KeyIntersec. Theo thuật toán trên, để tính giao các khóa ta cần thực hiện m lần lặp ứng với số lượng PTH trong tập F. Trong mỗi lần lặp, phép toán trên tập hợp n phần tử có độ phức tạp O(n) do đó độ phức tạp của thuật toán tính giao các khóa, KeyIntersec là O(mn). Tích mn chính là chiều dài của biểu diễn LĐQH a = (U,F) tức là chiều dài của dữ liệu vào trong thuật toán. Địn h l ý (Định lý về khóa duy nhất, Hồ Thuần, Lê Văn Bào) Cho LĐQH a = (U,F). Gọi UI là giao của các khóa trong a. Khi đó a có một khóa duy nhất khi và chỉ khi UI + = U. Chứn g m i n h Nếu UI + = U thì UI là siêu khóa. Vì UI là giao của các khóa đồng thời lại là siêu khóa nên a không thể còn khóa nào khác ngoài UI. Ngược lại, nếu a chỉ có một khóa duy nhất K thì giao của các khóa đương nhiên là UI = K, và do đó, theo tính chất của khóa UI + = K + = U ■ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 31 Th í d ụ Cho LĐQH a = (U, F), U = ABCDE, F = {ABC, ADB, BD}. Ta có, giao của các khóa là UI = ABCDE\BCD = AE. UI + = (AE) + = AE  U nên a có hơn một khóa. Vì UI là giao các khóa nên ta có thể bổ sung cho UI một số thuộc tính để thu được các khóa. Dễ xác định được a có hai khóa là K1 = ABE và K2= ADE. Ta còn có, tập các thuộc tính khóa là UK = ABDE, tập các thuộc tính không khóa là Uo = C. 1.2.7. Chuẩn hóa LĐQH trên cơ sở PTH Phép tách Địn h n g h ĩ a Cho lược đồ quan hệ a = (U,F). Một phép tách lược đồ a là một họ các tập con của U,  = (X1, X2,...,Xk) thỏa tính chất UX i k i  1  Phép tách  = (X1, X2,...,Xk) trên lược đồ a được gọi là không tổn thất (hoặc không mất thông tin) đối với tập PTH F nếu  R(U)  SAT(F): R[X1]  R[X2]  ...  R[Xk] = R Ngược lại, nếu không tồn tại đẳng thức thì ta gọi  là phép tách tổn thất. Kiểm tra tính tổn thất của phép tách bằng kỹ thuật bảng Algorithm Lossless_Join_Testing Input - LĐQH p = (U,F) - Phép tách  = (X1, X2,...,Xk) Output  True, nếu  là một phép tách không tổn thất  False, ngoài ra. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 32 Method 1. Khởi trị: Lập bảng T với các cột là các thuộc tính trong U và k dòng, mỗi dòng ứng với một thành phần của Xi trong : Dòng i chứa các ký hiệu phân biệt (KHPB) aj ứng với các thuộc tính Aj trong Xi và các ký hiệu không phân biệt (KHKPB) bij ứng với các thuộc tính Aj trong U-Xi . Chú ý rằng mọi KHPB trong cột j của T là giống nhau và bằng aj còn mọi KHKPB trong bảng T lúc đầu là khác nhau. 2. Sửa bảng: Lặp đến khi bảng T không còn thay đổi: Vận dụng các F-luật để biến đổi bảng như sau: Với mỗi PTH L  R trong F, nếu trong bảng T có chứa hai dòng u và v giống nhau trên L thì sửa các ký hiệu của chúng cho giống nhau trên mọi cột A R trong bảng T như sau: a. nếu u.A = v.A: không sửa, b. nếu một trong hai ký hiệu u.A hoặc v.A là KHPB thì sửa mọi xuất hiện trong bảng của KHKPB thành KHPB đó, c. nếu cả hai ký hiệu u.A và v.A đều là KHKPB thì sửa mọi xuất hiện trong bảng của ký hiệu có chỉ số thứ nhất lớn hơn thành ký hiệu thứ hai. 3. Kết luận: Gọi bảng kết quả là T*. Nếu T* chứa một dòng toàn KHPB thì return True nếu không return False. end Lossless_Join_Testing. Th í d ụ a) Dùng kỹ thuật bảng để kiểm tra tính kết nối không tổn thất của phép tách trong LĐQH p = (U,F), U = ABCD, F = { A  B, AC  D },  = (AB, ACD). T  T* 1. A 2. B 3. C 4. D 1. AB a1 a2 b13 b14 2. ACD a1 b22 / a2 a3 a4 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 33 Vì T* chứa dòng thứ hai gồm toàn ký hiệu phân biệt nên phép tách đã cho là không tổn thất. b) Dùng kỹ thuật bảng để kiểm tra tính kết nối không tổn thất của phép tách trong LĐQH p = (U,F), U = ABCDE, F = { A  C, B  C, C  D, DE  C, CE  A },  = (AD, AB, BE, CDE). T  T* 1. A 2. B 3. C 4. D 5. E 1. AD a1 b12 b13 / a3 a4 b15 2. AB a1 a2 b23 / b13 / a3 b24 / a4 b25 3. BE b31 a2 b33 / b13 / a3 b34 / a4 a5 4. CDE b41 / b31 b42 a3 a4 a5 Vì T* không chứa dòng nào gồm toàn ký hiệu phân biệt nên phép tách đã cho là tổn thất. Tính chất của phép tách Mệnh đ ề Cho LĐQH a = (U, F). Nếu X  Y thì phép tách (XY, U\(Y\X)) là không tổn thất. Các dạng chuẩn Địn h n g h ĩ a LĐQH p = (U,F) được gọi là lược đồ a) dạng chuẩn 1 (1NF) nếu mọi thuộc tính trong U đều không phải là thuộc tính phức hợp, b) dạng chuẩn 2 (2NF) nếu p là LĐ 1NF và mọi thuộc tính không khoá đều phụ thuộc đầy đủ vào mọi khoá,  A  Uo ,  K  Key(p) : K + A c) dạng chuẩn 3 (3NF) nếu p là LĐ 1NF và mọi thuộc tính không khoá đều phụ thuộc trực tiếp vào mọi khoá, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 34  A  Uo ,  K  Key(p) : K * A d) dạng chuẩn 3 (3NF) nếu p là LĐ 1NF và mọi PTH không tầm thường XA, A là thuộc tính không khóa đều cho ta X là một siêu khoá,  (X  A, A  Uo – X )  X + = U e) dạng chuẩn Boyce-Codd (BCNF) nếu p là LĐ 1NF và mọi thuộc tính đều phụ thuộc trực tiếp vào mọi khoá,  A  U ,  K  Key(p) : K * A f) dạng chuẩn Boyce-Codd (BCNF) nếu p là LĐ 1NF và mọi PTH không tầm thường XY đều cho ta X là một siêu khóa.  (X  Y, Y – X   )  X + = U Sơ đồ tương quan giữa các dạng chuẩn BCNF  3NF  2NF Thuật toán chuẩn hoá 3NF không tổn thất và bảo toàn PTH Algorithm 3NF Function: Chuẩn hóa 3NF không tổn thất và bảo toàn PTH. Input: LĐQH p = (U,F) Output: Các LĐQH 3NF (U1,K1),(U2,K2),...,(Us ,Ks) thoả RREL(U): R[U1]R[U2]...R[Us] = R K1, K2,..., Ks - khoá của các lược đồ tương ứng F  i=1..s(F+[Ui]) Method 1. Tìm một phủ tối tiểu của F: G = {K1  A1,K2  A2,..., Km  Am} 2. Ghép các PTH có cùng vế trái trong G để thu được phủ G = {K1  X1, K2  X2,..., Ks  Xs}. 3. // Xét phép tách  = (K1X1,...,KsXs). Nếu  // chứa một siêu khóa nào đó // của p thì return {(K1X1,K1),...,( KsXs,Ks)} Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 35 // nếu không return {(K1X1,K1),...,(KsXs,Ks), // (K,K)} với K là một khóa của p. construct  = (K1X1,K2X2,...,KsXs); for each component V = KiXi in  do if V+ = U then // V = KiXi là siêu khóa return {(K1X1,K1),...,(KsXs,Ks)}; endif; endfor; K = Key(U,F); return {(K1X1,K1),...,(KsXs,Ks),(K,K)}; End 3NF. Th í d ụ Xác định và giải thích dạng chuẩn cao nhất của LĐQH sau: a = (U, F), U = ABCD, F = { A  C, D  B, C  ABD } LĐQH a có 2 khoá là A và C vì A+ = C+ = ABCD = U. Tập thuộc tính khoá là Uk = AC, tập thuộc tính không khoá là Uo = BD. Ta có, DB, B là thuộc tính không khóa và D không phải là một siêu khóa do đó a không ở 3NF và đương nhiên không ở BCNF. Vì hai khoá A và C đều chỉ có một thuộc tính nên các thuộc tính không khoá khác là B và D đều phụ thuộc đầy đủ vào hai khoá này. Vậy a ở 2NF. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 36 CHƯƠNG 2 PHÉP DỊCH CHUYỂN LƯỢC ĐỒ QUAN HỆ Quản lý các cơ sở dữ liệu lớn và phức tạp đòi hỏi nhiều thuật toán hữu hiệu để tính toán các đối tượng như bao đóng, khóa, phủ... Một số thuật toán tốt theo nghĩa độ phức tạp tính toán giới hạn ở các hàm tuyến tính hoặc đa thức theo chiều dài dữ liệu vào đã được công bố như thuật toán tính bao đóng của tập thuộc tính, thuật toán tìm một khóa, thuật toán xác định thành viên hay thuật toán xác định phụ thuộc hàm suy dẫn, thuật toán tìm giao các khóa, thuật toán xác định một lược đồ quan hệ có một khóa duy nhất.... [1, 2, 8]. Một nhận xét tự nhiên là nếu kích thước của LĐQH càng nhỏ thì các thuật toán càng phát huy hiệu quả hơn. Một số hướng nghiên cứu tinh giản các lược đồ cơ sở dữ liệu được thực hiện thông qua các phép biến đổi tương đương, chẳng hạn đưa tập PTH về dạng thu gọn hoặc thu gọn tự nhiên, dạng không dư, dạng tối ưu (chứa ít ký hiệu nhất)... đã được công bố [3, 5, 6, 7]. Trong phép dịch chuyển lược đồ quan hệ [7]. Bản chất của kỹ thuật này là loại bỏ khỏi LĐQH ban đầu một số thuộc tính không quan trọng theo nghĩa chúng không làm ảnh hưởng đến kết quả tính toán các đối tượng đang quan tâm như bao đóng, khóa, phản khóa... Mặc dù LĐQH thu được qua phép dịch chuyển không tương đương với LĐQH ban đầu, nhưng ta có thể thu được các đối tượng cần tìm bằng những phép toán đơn giản như loại bỏ hoặc thêm một số thuộc tính. Điều lý thú là sau khi loại bỏ một số thuộc tính thì một số PTH sẽ được loại bỏ theo, vì chúng trở thành các PTH tầm thường (có vế trái chứa về phải) hoặc mang thông tin tiền định (đó là các phụ thuộc hàm dạng   X). Th í d ụ Cho LĐQH a = (U,F) với tập thuộc tính U = ABCDEH và tập PTH F = {AE  D, BC E, E  BC}. Để tìm tập khóa Key(a) của lược đồ a chúng ta xây dựng một Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 37 lược đồ b bằng cách xóa khỏi lược đồ a các thuộc tính A, D và H. Ta thu được lược đồ b = (V,G) trong đó V= U\ADH = BCE, G = {E  Ø, BC  E, E  BC}. Tiếp đến ta loại PTH tầm thường E  Ø khỏi G. Ta thu được G = {BC  E, E  BC}. Ta dễ dàng tìm được hai khóa của lược đồ b, Key(b) = {BC, E}. Để thu được Key(a) ta chỉ việc thêm tập thuộc tính AH (không thêm D) vào mỗi khóa của lược đồ b. Vậy Key(a) = {AHBC, AHE}. Dù F đã là tập PTH tối ưu [7] nhưng G còn chứa ít ký hiệu hơn F. 2.1. Phép dịch chuyển LĐQH Địn h n g h ĩ a Cho hai LĐQH a = (U,F), b = (V,G) và tập thuộc tính M  U. Ta nói LĐQH b nhận được từ LĐQH a qua phép dịch chuyển theo tập thuộc tính M, nếu sau khi loại bỏ mọi xuất hiện của các thuộc tính của M trong lược đồ a thì thu được lược đồ b. Nếu sau khi thực hiện phép dịch chuyển theo M cho LĐQH a ta thu được LĐQH b thì ta viết b = a\M Thao tác loại bỏ M được thực hiện trên lược đồ a = (U,F) để thu được lược đồ b=(V,G) như sau: 1. Tính V = U\M có độ phức tạp O(n) với n là số lượng thuộc tính trong U. 2. Với mỗi PTH X  Y trong F ta tạo một PTH X\M  Y\M cho G. Thủ tục này được ký hiệu là G = F\M. Tính F\M đòi hỏi độ phức tạp O(mn) với m là số lượng PTH trong F. Như vậy b = a\M = (U\M,F\M) được thực hiện với độ phức tạp O(mn), tức là tuyến tính theo chiều dài dữ liệu vào (LĐQH a). Sau khi thực hiện thủ tục G = F\M nếu  G chứa các PTH tầm thường (dạng X  Y, X  Y) thì ta loại các PTH này khỏi G, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 38  G chứa các PTH trùng lặp thì ta lược bớt các PTH này. Th í d ụ Cho LĐQH a = (U,F), U = ABCDEH, F = {AE  D, A  DH, BC  E, E  BC}. Với M = ADH, hãy xác định b = (V,G) = a\M. Ta có V= U\ADH = ABCDEH\ADH=BCE, G = {E  Ø (loại),    (loại), BC  E, E  BC} ≡ {BC  E, E  BC}. Ta cũng dễ nhận thấy phép dịch chuyển thỏa tính hợp thành, cụ thể là nếu a là LĐQH trên tập thuộc tính U và X, Y là hai tập con của U thì a\(XY) = (a\X)\Y Trong trường hợp X và Y là hai tập con rời nhau của U ta có a\XY = (a\X)\Y = (a\Y)\X 2.2. Thuật toán dịch chuyển LĐQH Thuật toán Translation dưới đây mô tả phép dịch chuyển một LĐQH với độ phức tạp O(mn). Algorithm Translation Format: Translation(a,M) Input: - LĐQH a = (U,F) - Tập thuộc tính M  U Output: - LĐQH b = (V,G) = a\M, V = U\M, G = F\M. Method V := U\M; G := ; for