Về thuật toán tìm tất cả các khóa của lược đồ quan hệ

Vũ Trí Dũng<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 58(10): 41 - 44<br /> <br /> VỀ THUẬT TOÁN TÌM TẤT CẢ CÁC KHOÁ CỦA LƯỢC ĐỒ QUAN HỆ<br /> Vũ Trí Dũng<br /> <br /> *<br /> <br /> Trường trung cấp nghề Kinh tế - Kỹ thuật Hà Nam<br /> TÓM TẮT<br /> Lý thuyết thiết kế cơ sở dữ liệu (CSDL) đóng vai trò quan trọng trong công nghệ thông<br /> tin. Để quản lý tốt được chất lượng dữ liệu và thiết kế một CSDL tốt, ta phải xác định<br /> được dạng chuẩn và chuẩn hoá lược đồ quan hệ (LĐQH). Theo định nghĩa [1,2,4], việc<br /> xác định dạng chuẩn của LĐQH (3NF, 2NF) với yếu tố tiên quyết là phải tìm được tất cả<br /> các khoá của LĐQH, từ đó có thể chỉ ra các thuộc tính khoá, các thuộc tính không khoá<br /> và xác định được dạng chuẩn của LĐQH. Bài báo phát triển thuật toán tìm tất cả các<br /> khoá của lược đồ quan hệ dựa trên kết quả của Lucchesi và Osborn [3] với những cải<br /> tiến như sau. Thứ nhất, giảm số lần duyệt các khóa xuống còn 1 cho mỗi khóa. Thứ hai,<br /> với số thuộc tính không nhiều, giới hạn đến 64, thuật toán tổ chức các tập thuộc tính<br /> dưới dạng số nguyên do đó tăng thêm tốc độ duyệt tìm.<br /> Key words: Relational schema, key, functional dependency, database.<br /> *<br /> <br /> 1. MỞ ĐẦU<br /> Bài báo giả thiết rằng bạn đọc đã làm quen<br /> với các khái niệm cơ bản của cơ sở dữ liệu<br /> quan hệ [1,2,4]. Phần này chỉ nhắc lại một số<br /> định nghĩa, định lý và thuật toán liên quan<br /> đến việc phát triển thuật toán tìm tất cả các<br /> khoá của LĐQH. Các định nghĩa, định lý,<br /> thuật toán và kí hiệu trong bài báo sử dụng<br /> theo tài liệu [1].<br /> Các định nghĩa:<br /> Cho lược đồ quan hệ (LĐQH) p = (U,F), trong<br /> đó U là tập hữu hạn các thuộc tính, F là tập<br /> +<br /> phụ thuộc hàm (PTH) trên U. Tập X = {A ÎU<br /> +<br /> | X Î AÎF } được gọi là bao đóng của tập<br /> thuộc tính X Í U. Tập K Í U được gọi là khóa<br /> của LĐQH p nếu (i) K+ = U và (ii) "A Î K:<br /> +<br /> (K\A) ≠ U. Nếu K thoả điều kiện (i) thì K<br /> được gọi là một siêu khoá. Tập PTH trong bài<br /> được giả thiết là được cho dưới dạng thu gọn<br /> tự nhiên, trong đó các vế trái của mọi PTH<br /> khác nhau đôi một và mọi vế phải và trái của<br /> mọi PTH là rời nhau. Trong [1] chỉ ra rằng có<br /> thể đưa mọi tập PTH về dạng thu gọn tự<br /> nhiên với thời gian tuyến tính theo chiều dài<br /> dữ liệu vào, tức là theo n.m, trong đó n là số<br /> lượng thuộc tính trong U và m là số lượng<br /> PTH trong F. Thuật toán tìm một khóa của<br /> LĐQH, Key(V,F) xuất phát từ một siêu khóa<br /> V cho trước có độ phức tạp đa thức theo<br /> chiều dài dữ liệu vào là O(n2m) [1], trong đó<br /> <br /> *<br /> <br /> Vu Tri Dung, Tel: 0983035969,<br /> E-mail: vutridungvn@gmail.com<br /> <br /> Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên<br /> <br /> O(nm) là độ phức tạp của thuật toán tìm bao<br /> đóng [4].<br /> Các định lý<br /> Cho LĐQH p = (U,F) với n thuộc tính trong U<br /> và m PTH trong F<br /> * Gọi UI là giao các khóa của p. Khi đó có thể<br /> xác định giao các khóa bằng một thuật toán<br /> tuyến tính theo mn qua công thức<br /> <br /> UI =U \<br /> <br /> U (R \ L)<br /> <br /> L ® RÎ F<br /> <br /> * Gọi UI là giao của các khóa trong p. Khi đó<br /> +<br /> p có một khóa duy nhất khi và chỉ khi UI =U.<br /> * Định lý Lucchesi – Osborn [3]<br /> Cho LĐQH p = (U,F), biết v khóa của p là<br /> {K 1, K2,..., Kv}, khi đó p còn khóa nữa khi và<br /> chỉ khi tồn tại một khoá KÎ {K1, K2,..., Kv} và<br /> tồn tại một PTH L®R Î F thoả: LÈ(K\R)<br /> không chứa bất kỳ khoá nào trong số khoá đã<br /> tìm được.<br /> 2. VỀ THUẬT TOÁN TÌM TẤT CẢ CÁC<br /> KHOÁ CỦA LĐQH<br /> Liệt kê tất cả các khoá của LĐQH là bài toán<br /> thuộc lớp NPC [1,3], có độ phức tạp hàm mũ.<br /> Thông thường, để tìm được tất cả các khoá<br /> của LĐQH, ta sử dụng phương pháp vét cạn<br /> các khả năng có thể tồn tại khoá, đó là xét tất<br /> cả các tập con của tập thuộc tính U.<br /> Bài báo này đề xuất phương pháp dựa trên<br /> định lý Lucchesi - Osborn tìm tất cả các khoá<br /> của LĐQH với số lần duyệt tối thiểu.<br /> Trong các thuật toán sử dụng các biến và các<br /> kí hiệu như sau:<br /> <br /> http://www.lrc-tnu.edu.vn<br /> <br /> Vũ Trí Dũng<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> K = tập khoá của LĐQH.<br /> UI = tập giao của các khoá.<br /> Hàm logic Scan(X,K,i) cho giá trị true nếu tập<br /> X không chứa i khóa đầu tiên trong tập khoá<br /> K . Dễ thấy hàm này có độ phức tạp O(i.n)<br /> i = biến i làm chỉ số của tập khoá K .<br /> j = biến j dùng để đếm số lượng khoá.<br /> Thuật toán AllKeys_D1 cải tiến dựa theo<br /> phương pháp vét cạn tất cả các khả năng tồn<br /> tại khoá, nhưng thuật toán được cải tiến để<br /> tối ưu thời gian tính toán.<br /> <br /> 58(10): 41 - 44<br /> <br /> X := UI ÈZ ("Z Í Y), (vì như thế phải tốn thời<br /> gian duyệt 2 lần, tốn thời gian lưu trữ và tốn<br /> +<br /> bộ nhớ), mà tìm bao đóng (X ) ngay khi xây<br /> dựng các tập Z Í Y.<br /> Thuật toán AllKeys_D1 liệt kê tất cả các<br /> khoá của LĐQH đã được cải tiến trên thực tế<br /> và làm giảm đáng kể thời gian tính toán. Tuy<br /> nhiên, với những cơ sở dữ liệu cỡ lớn và<br /> phức tạp thì thuật toán này trở nên không<br /> hiệu quả vì phải xử lý số lượng lớn các vòng<br /> lặp.<br /> <br /> + Bước 2: Nếu UI = U thì LĐQH có một khóa<br /> duy nhất;<br /> <br /> Dựa trên thuật toán tìm một khóa của LĐQH<br /> (Key), thuật toán tìm phủ thu gọn tự nhiên<br /> (Natural_Reduced) [1] và định lý Lucchesi Osborn, bài báo phát triển thuật toán<br /> AllKeys_D2 tìm tất cả các khoá của LĐQH<br /> với số lần duyệt tối thiểu.<br /> <br /> K := KÈUI; chuyển tới Bước 4<br /> <br /> * Ý tưởng:<br /> <br /> * Ý tưởng:<br /> + Bước 1: Tìm giao các khoá:<br /> UI := KeyIntersec(U,F);<br /> +<br /> <br /> + Bước 1: Tìm phủ thu gọn tự nhiên<br /> Ngược lại chuyển tới Bước 3<br /> + Bước 3:<br /> 3.1 tính Y := U \ UI;<br /> 3.2 Với tập con Z trong Y<br /> 3.2.1 Tính X:=UI È Z;<br /> 3.2.2 Gọi hàm Scan(X,K,i) để kiểm tra: nếu X<br /> không chứa bất kỳ khoá nào trong tập khoá K<br /> +<br /> và X = U thì nạp X vào kết quả: K := K ÈX;<br /> + Bước 4: return K ;<br /> Thuật toán AllKeys_D1 tương tự như<br /> phương pháp tìm khoá vét cạn. Tuy nhiên,<br /> thuật toán trở nên hữu hiệu hơn do có một<br /> số cải tiến sau:<br /> 1) Vì giao các khoá là thành phần có mặt<br /> trong mọi khoá [1], nên trước hết ta tìm giao<br /> các khoá, rồi trừ các thuộc tính thuộc tập giao<br /> các khoá có trong tập U đi, do đó số lượng<br /> thuộc tính trong tập U được giảm đi bằng số<br /> lượng tập giao các khoá, dẫn đến số vòng lặp<br /> sẽ được giảm đi đáng kể.<br /> 2) Với mỗi tập X := UIÈZ ("Z Í Y), nếu tập<br /> nào chứa một trong các khoá của LĐQH p =<br /> (U,F) (chứa Key(p)) đã tìm được thì bỏ qua<br /> mà không đi tìm bao đóng của tập X đó nữa,<br /> do đó làm giảm đáng kể thời gian tính toán<br /> (bởi vì thực tế có khá nhiều tập X chứa các<br /> khoá đã tìm được trước đó).<br /> 3.Không xây dựng các tập Z Í Y xong rồi<br /> mới duyệt mọi tập con Z để tìm bao đóng của<br /> <br /> Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên<br /> <br /> + Bước 2: (i) Tìm một khoá của LĐQH;<br /> (ii) Thêm khoá vừa tìm được vào tập khoá K<br /> + Bước 3: Duyệt lần lượt từng khoá Ki trong<br /> tập khoá K và thực hiện lặp:<br /> Với mỗi PTH L®R trong tập F, nếu L không<br /> chứa Ki thì thực hiện:<br /> 3.1 Tính X := LÈ (Ki\R);<br /> 3.2 Gọi hàm Scan để kiểm tra: nếu X không<br /> chứa bất kỳ khoá K nào trong tập khóa K thì<br /> thực hiện<br /> 3.2.1 Gọi hàm Key(X,F) để tìm thêm khoá K<br /> từ siêu khoá X;<br /> 3.2.2 Thêm khoá K vào tập khoá K ;<br /> Duyệt đến khi hết khoá có trong tập khoá K ;<br /> +Bước 4 return K ;<br /> * Algorithm AllKeys_D2<br /> 1....1<br /> <br /> Format: AllKeys_D2(U,F)<br /> <br /> Input:<br /> <br /> - Tập thuộc tính U<br /> - Tập PTH F<br /> <br /> Output:<br /> <br /> - Tập khóa K Thoả:<br /> <br /> "K Î K :<br /> +<br /> (ii) K = U<br /> <br /> (i) K Í U<br /> +<br /> <br /> (iii)"AÎK: (K\A) ≠ U<br /> Method<br /> Natural_Reduced(F);<br /> <br /> http://www.lrc-tnu.edu.vn<br /> <br /> Vũ Trí Dũng<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> K := {Key(U,F)};<br /> i := 0;<br /> <br /> 58(10): 41 - 44<br /> <br /> khoá có trong K nữa do đó làm giảm số lần<br /> so sánh.<br /> <br /> j := 1;<br /> <br /> repeat<br /> <br /> Thí dụ: Cho LĐQH p = (U,F)<br /> i := i + 1;<br /> for each FD L®R Î F do<br /> if L ⊉ Ki then<br /> X := LÈ(K i \ R);<br /> <br /> Tập thuộc tính U = ABCDEH<br /> Tập PTH F = {AE®D, BC®E, E®BC,<br /> AE®CE}. Tìm mọi khóa của LĐQH ?<br /> Giải:<br /> <br /> if Scan(X,K,j) then<br /> add Key(X,F)<br /> <br /> Sau khi thực hiện thủ tục Natural_Reduced ta<br /> thu được:<br /> <br /> j := j + 1;<br /> <br /> F = {AE®DC (1), BC®E (2), E®BC (3)}<br /> <br /> to K ;<br /> endif;<br /> endif;<br /> endfor;<br /> until i = j;<br /> return K ;<br /> end AllKeys_D2.<br /> Dễ nhận thấy rằng thuật toán AllKeys_D2<br /> hiệu quả hơn hẳn do có các cải tiến sau:<br /> 1) Sử dụng thuật toán thu gọn tự nhiên, do đó<br /> loại bỏ được các PTH có vế trái trùng nhau<br /> dẫn đến làm giảm số lượng PTH, đồng thời<br /> loại bỏ các thuộc tính thuộc vế trái mà có mặt<br /> trong vế phải của các PTH (các PTH tầm<br /> thường), vì vậy làm giảm số vòng lặp.<br /> 2) Định lý Lucchesi - Osborn đã chứng minh,<br /> nếu trong LĐQH tồn tại một khoá K Î K và<br /> tồn tại một PTH L®R Î F thoả X:= LÈ (K\R)<br /> mà không chứa bất kỳ khoá nào trong số<br /> khoá đã tìm được (*) thì X là một siêu khoá<br /> [3]. Do đó ta lấy từng khoá trong tập khoá K<br /> (khoá đầu tiên tìm được qua thuật toán Key)<br /> thực hiện lần lượt với mỗi PTH thao tác trừ đi<br /> vế phải rồi hợp với vế trái mà thoả (*) thì thực<br /> hiện việc tìm khoá từ siêu khoá X. Khoá mới<br /> tìm được đem bổ sung vào tập khoá K .<br /> Duyệt cho đến hết số khoá có trong tập khoá<br /> K thì thuật toán dừng, do đó số lần lặp của<br /> vòng lặp repeat-until chỉ bằng số lượng khoá<br /> của LĐQH.<br /> 3) Khi xét một khoá Ki với PTH L®RÎF, nếu<br /> Ki Í L thì bỏ qua, không thực hiện việc tính X<br /> và không phải kiểm tra so sánh X với các<br /> <br /> Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên<br /> <br /> Gọi thủ tục Key(U,F) dể khởi trị ta thu được K<br /> = {AEH}.<br /> Lần lặp repeat-until thứ 1<br /> Ta lần lượt duyệt khóa K = AEH với các PTH<br /> trong F. Ta tìm được<br /> Với PTH (1) X = AEH, chứa khóa AEH nên<br /> bỏ qua.<br /> Với PTH (2): X = ABCH, không chứa khóa<br /> nào trong K ; Hàm Key(ABCH,F) cho ta thêm<br /> khóa mới ABCH. Ta có K = {AEH, ABCH}.<br /> Với PTH (3): X = AEH, chứa khóa AEH nên<br /> bỏ qua.<br /> Lần lặp repeat-until thứ 2<br /> K = ABCH<br /> Với PTH (1): X = ABEH, chứa khóa AEH nên<br /> bỏ qua.<br /> Với PTH (2): X = ABCH, chứa khóa ABCH<br /> nên bỏ qua.<br /> Với PTH (3): X = AEH, chứa khóa AEH nên<br /> bỏ qua.<br /> Đến đây các khóa trong K đã được duyệt<br /> hết. Ta dừng thuật toán với kết quả<br /> K = {AEH, ABCH}.<br /> 3. KẾT LUẬN<br /> Thuật toán AllKeys_D2 có thể ứng dụng cài<br /> đặt trong các phần mềm thiết kế các CSDL<br /> chuẩn hoá. Để thuật toán có hiệu quả hơn<br /> nữa, có thể kết hợp phép dịch chuyển LĐQH<br /> [1], khi đó LĐQH được thu gọn hơn cả về số<br /> lượng thuộc tính và số lượng PTH<br /> <br /> http://www.lrc-tnu.edu.vn<br /> <br /> Vũ Trí Dũng<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 58(10): 41 - 44<br /> <br /> TÀI LIỆU THAM KHẢO<br /> [1]. Nguyễn Xuân Huy (2006), Các phụ thuộc<br /> logic trong cơ sở dữ liệu, Viện Khoa học và<br /> Công nghệ Việt Nam, Nxb Thống kê, Hà Nội.<br /> [2]. Vũ Đức Thi, (1997), Cơ sở dữ liệu: Kiến<br /> thức và thực hành, Nxb Thống kê, Hà Nội.<br /> [3]. Claudio l. lucchesi, Sylvia l. osborn,<br /> (1978), “Candidate keys for relations”, Journal<br /> of computer and system sciences, 17, (2), pp<br /> 270-279.<br /> [4]. Ullman J., biên dịch Trần Đức Quang,<br /> (2002), Nguyên lý các hệ cơ sở dữ liệu và cơ<br /> sở tri thức, tập 1&2, Nxb Thống kê, Hà Nội.<br /> <br /> Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên<br /> <br /> http://www.lrc-tnu.edu.vn<br /> <br /> Vũ Trí Dũng<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 58(10): 41 - 44<br /> <br /> SUMMARY<br /> ON THE ALGORITHM FOR FINDING ALL KEYS OF A RELATIONAL SCHEMA<br /> <br /> Vu Tri Dung*<br /> Economics and Technology Secondary Vocational Training School, Ha Nam province<br /> <br /> The theory of designing database plays an important role in information technology. In order to<br /> design a good database, we have to define the normal form of relational schema. This paper<br /> presents some improvements of the algorithm for finding all the keys of a relational schema, so<br /> that we can find out the key attributes, not-key attributes and define the normal form of relational<br /> schema and normalize the relational schema easily.<br /> Key words: Relational schema, key, functional dependency, database.<br /> <br /> *<br /> <br /> Vu Tri Dung,Tel: 0983035969, E-mail: vutridungvn@gmail.com<br /> <br /> Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên<br /> <br /> http://www.lrc-tnu.edu.vn<br /> <br />