Một số kết quả về thuật toán tính bao đóng và rút gọn bài toán tìm khóa của lược đồ quan hệ

Nội dung text: Một số kết quả về thuật toán tính bao đóng và rút gọn bài toán tìm khóa của lược đồ quan hệ

1. Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông Một số kết quả về thuật toán tính bao đóng và rút gọn bài toán tìm khóa của lược đồ quan hệ Vũ Quốc Tuấn, Hồ Thuần Học viện Khoa học và Công nghệ, Viện Hàn lâm Khoa học và Công nghệ Việt Nam E-mail: vqtuanhd@gmail.com, hothuan1812@yahoo.com Tác giả liên hệ: Vũ Quốc Tuấn Ngày nhận: 27/03/2017, ngày sửa chữa: 04/08/2017, ngày duyệt đăng: 13/11/2017 Tóm tắt: Trong lĩnh vực trí tuệ nhân tạo và cơ sở dữ liệu quan hệ, khóa của lược đồ quan hệ và bao đóng của một tập thuộc tính đối với một tập phụ thuộc hàm có vai trò quan trọng và được sử dụng trong nhiều bài toán như tối ưu hóa truy vấn, chuẩn hóa lược đồ quan hệ, loại bỏ ràng buộc dư thừa, v.v. Do đó, độ phức tạp của thuật toán tìm bao đóng và việc rút gọn bài toán tìm khóa là các vấn đề luôn được quan tâm. Trong vài năm gần đây, các vấn đề này được xới lại với hàng loạt các công trình mới nhằm giải quyết bài toán tính bao đóng và tìm tập các khóa của lược đồ quan hệ một cách hiệu quả hơn theo nhiều tiếp cận khác nhau. Trong bài báo này, chúng tôi đề xuất một thuật toán cải tiến tính bao đóng và đưa ra một số kết quả về rút gọn bài toán tìm khóa nhằm nâng cao hiệu năng tính toán khi giải quyết các vấn đề có liên quan. Từ khóa: Cơ sở dữ liệu quan hệ, lược đồ quan hệ, phụ thuộc hàm, bao đóng của một tập thuộc tính, khóa của lược đồ quan hệ. Title: Some Results for the Closure Computing Algorithm and Reducing the Key Finding Problem of a Relation Schema Abstract: In artificial intelligence and relational databases, the key for a relation schema and the closure of a set of attributes under a set of functional dependencies are important and used in several problems such as query optimization, relational schema normalization, removing redundant constraints, etc. Therefore, the complexity of closure computing algorithms and reducing the key finding problem are always interesting problems. In recent years, these problems have been revisited with a series of new studies, to be solved more efficiently by several different approaches. In this paper, we propose an improved closure computing algorithm and provide some results for reducing the key finding problem to enhance the computing performance for solving related problems. Keywords: Relational database, relation schema, functional dependency, closure of a set of attributes, key for a relation schema. I. MỞ ĐẦU Phụ thuộc hàm. Cho Ω là tập thuộc tính và S Ω là một ( ) lược đồ quan hệ trên Ω. Giả sử X, Y Ω, khi đó Y được ⊆ Phần này nhắc lại một số khái niệm quan trọng trong lý gọi là phụ thuộc hàm vào X trên lược đồ S Ω , ký hiệu là ( ) thuyết cơ sở dữ liệu quan hệ nhằm mục đích sử dụng cho X Y, nếu với mọi quan hệ r trên lược đồ S Ω , với hai → ( ) các phần tiếp theo. bộ bất kỳ t , t r mà t X = t X thì t Y = t Y . 1 2 ∈ 1[ ] 2[ ] 1[ ] 2[ ] Lược đồ quan hệ. Một lược đồ quan hệ S là một cặp có Nếu Y phụ thuộc hàm vào X thì ta cũng nói “X xác định thứ tự S = Ω, F , trong đó Ω là tập hữu hạn các thuộc tính hàm Y”. Với mỗi quan hệ r trên lược đồ S Ω , ta nói r thỏa h i ( ) của quan hệ, F là tập các ràng buộc giữa các thuộc tính. mãn (hay thỏa) phụ thuộc hàm X Y (hay phụ thuộc hàm → X Y đúng trên r) nếu và chỉ nếu với mọi bộ t , t r, Cho lược đồ quan hệ S = Ω, F với Ω = A1, A2, , → 1 2 ∈ h i { t X = t X kéo theo t Y = t Y . Trong bài báo này, An . Nếu không quan tâm đến tập các ràng buộc F thì ta 1[ ] 2[ ] 1[ ] 2[ ] } ta hạn chế F (của lược đồ S = Ω, F ) chỉ gồm các phụ sẽ dùng ký hiệu S Ω thay cho S = Ω, F . h i ( ) h i thuộc hàm. Ta dùng ký hiệu r S để chỉ một quan hệ r (hay một thể ( ) hiện r) của lược đồ quan hệ S. Với một bộ t của r S và Hệ quy tắc suy diễn Armstrong. Với lược đồ quan hệ ( ) X Ω , ta ký hiệu t X là bộ chỉ chứa các giá trị của bộ S = Ω, F và X, Y Ω, ta ký hiệu XY thay cho X Y. ⊆ [ ] h i ⊆ ∪ t tại các thuộc tính trong X. Với mọi X, Y, Z Ω, hệ quy tắc suy diễn Armstrong đối ⊆ 12
2. Tập V-2, Số 18 (38), 12/2017 Thuật toán 1: Tính bao đóng X+ Thuật toán 2: Tính bao đóng X+ [4] Input: Input: Ω, F, X Ω Ω, F, X Ω ⊆ ⊆ Output: X+ Output: X+ begin begin + X = X Xnew = X; repeat repeat for each Y Z F do X = X ; ( → ) ∈ old new if Y X+ then for each Y Z F do ⊆ ( → ) ∈ X+ = X+ Z; if Y X then ∪ ⊆ new end if X = X Z; . (I) new new ∪ end for each F = F Y Z ; − { → } until không còn thuộc tính nào được thêm vào X+; else if Z X then ⊆ new return X+; F = F Y Z ; . (II) − { → } end else F = F Y Z ; . (III) − { → } F = F Y X Z X ; . (III) ∪ { − new → − new} với các phụ thuộc hàm gồm ba quy tắc sau đây: end if A1. (Phản xạ): Nếu Y X thì X Y; end for each ⊆ → A2. (Gia tăng): Nếu X Y thì XZ YZ; until Xnew = Xold hoặc F = 0 ; → → ( + ) (| | ) A3. (Bắc cầu): Nếu X Y và Y Z thì X Z. return X = Xnew; → → → end Ký hiệu F+ là tập tất cả các phụ thuộc hàm được suy diễn từ F bằng cách áp dụng một số hữu hạn lần các quy tắc của hệ quy tắc suy diễn Armstrong. i) Dùng một tập để lưu giữ các thuộc tính còn phải thêm Bao đóng của một tập thuộc tính. Cho tập phụ thuộc vào bao đóng; hàm F xác định trên tập thuộc tính Ω (phụ thuộc hàm (FD: ii) Dùng một mảng được đánh chỉ số bởi các thuộc tính functional dependency) Y Z xác định trên tập thuộc tính → Ai để lưu giữ các phụ thuộc hàm có vế trái chứa Ai; Ω nếu Y, Z Ω) và X Ω. Ta gọi bao đóng của tập thuộc iii) Lưu giữ số thuộc tính thuộc vế trái của mỗi phụ thuộc ⊆ ⊆ + tính X đối với tập phụ thuộc hàm F, ký hiệu là XF , là tập hàm còn chưa có mặt trong bao đóng. tất cả các thuộc tính A của Ω sao cho X A được suy → Các chiến lược này đã giúp một số tác giả xây dựng được diễn từ F nhờ hệ quy tắc suy diễn Armstrong, các thuật toán tuyến tính tính bao đóng, tức có độ phức tạp + + X = A Ω X A F . thời gian là O np . Đó là các thuật toán của Beeri trong [1], F ∈ | ( → ) ∈ ( ) của Diederich trong [2] và của Paredaens trong [3]. Khóa của lược đồ quan hệ. Cho lược đồ quan hệ S = Ω, F và K Ω. Ta nói K là một khóa của S nếu hai điều h i ⊆ kiện sau đây đồng thời được thỏa mãn: 2. Thuật toán của Mora và cộng sự i) K Ω F+; Thuật toán 2 và các thuật toán tính bao đóng của ( → ) ∈ + ii) Nếu K 0 K thì K 0 Ω < F . Diederich, Beeri và Paredaens đã được chạy thử nghiệm ⊂ ( → ) và cho kết quả được trình bày trong [4], cụ thể như sau: II. THUẬT TOÁN CẢI TIẾN TÍNH BAO ĐÓNG sinh ngẫu nhiên tập thuộc tính Ω, tập phụ thuộc hàm F và tập con X Ω; các tập phụ thuộc hàm được sinh ngẫu CỦA MỘT TẬP THUỘC TÍNH ⊆ nhiên lần lượt có 25, 50, 75, 100, 125, 150, 175 và 200 phụ X+ 1. Thuật toán chuẩn tính bao đóng thuộc hàm, số lượng các thuộc tính ở vế trái và vế phải của Thuật toán 1 là thuật toán tính bao đóng X+. Dễ chứng các phụ thuộc hàm biến đổi từ 1 đến 300, kích thước của minh được rằng độ phức tạp thời gian của Thuật toán 1 là các tập phụ thuộc hàm từ 50 đến 61770 thuộc tính (kích O np min n, p , trong đó n là số thuộc tính trong Ω và p là thước của một tập phụ thuộc hàm F được định nghĩa là ( { }) số phụ thuộc hàm trong F. Như vậy, thuật toán trên không tổng các kích thước của các phụ thuộc hàm trong F; kích là tuyến tính theo tích np. Để có các thuật toán tính bao thước của X Y là X + Y ; X là số thuộc tính của tập → | | | | | | đóng với độ phức tạp tuyến tính, cần sử dụng một số cấu X); thực hiện thử nghiệm các thuật toán 1817 lần. Kết quả trúc dữ liệu thích hợp nhằm giảm chi phí của việc duyệt thử nghiệm cho thời gian tính toán của 1817 lần thực hiện các tập F và Ω. Các chiến lược rút gọn bao gồm: được cho trong Bảng I, trong đó thời gian trung bình tính 13
3. Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông + Bảng I Thuật toán 3: Tính bao đóng X KẾT QUẢ THỬ NGHIỆM Input: Ω, F, X Ω Thuật toán Trung bình ⊆ Output: X+ X+ Thuật toán tính bao đóng của Diederich 4593,48 begin Thuật toán tính bao đóng X+ của Beeri 7013,56 Xnew = X; + Thuật toán tính bao đóng X của Paredaens 5863,35 repeat Thuật toán tính bao đóng của nhóm A. Mora và 1262,41 Xold = Xnew; cộng sự (Thuật toán 2) for each Y Z F do ( → ) ∈ if Z X then ⊆ new F = F Y Z ; . (I) theo đơn vị giây. Từ bảng kết quả trên, ta thấy Thuật toán 2 − { → } else if Y X then tiêu tốn ít thời gian hơn ba thuật toán còn lại. ⊆ new begin . (II) X = X Z; new new ∪ 3. Thuật toán cải tiến tính bao đóng F = F Y Z ; − { → } Ta nhận thấy rằng, so với các thuật toán tính bao đóng end đã nêu trong mục II-1, Thuật toán 2 có ưu điểm là làm else đơn giản hóa tập F bằng cách loại bỏ FD Y Z trong F begin . (III) → F = F Y Z ; sau khi đã dùng nó để tính giá trị mới của Xnew hoặc thay − { → } thế FD Y Z trong F bằng một FD đơn giản hơn trong F = F Y Xnew Z Xnew ; → ∪ { − → − } trường hợp cả hai vế của FD này đều không là những tập end con của Xnew. Tuy nhiên, tính đúng đắn của Thuật toán 2 end if không được chứng minh một cách tường minh. Hơn nữa, end for each until X = X or F = 0 ; nhược điểm của nó là mỗi lần duyệt tập F, tất cả các FD có ( new old) (| | ) X ; vế trái và vế phải cùng chứa trong Xnew vẫn được kiểm tra return new vế trái để từ đó tính giá trị mới của Xnew (điều này làm mất end thời gian không cần thiết vì giá trị Xnew thực chất không thay đổi). Thuật toán 3 tránh được những phép kiểm tra và tính toán không cần thiết này vì thực hiện loại bỏ ngay từ Bây giờ ta phải chứng minh đầu các FD có vế phải chứa trong X nên thời gian thực new Y Xnew Xnew1 Y Xnew1. (3) hiện nhanh hơn so với Thuật toán 2. ( − ) ⊆ ⇐⇒ ⊆ Thật vậy, từ Y X ta có Với Thuật toán 3, ta có bổ đề sau đây. ⊆ new1 Y X X . Bổ đề 1. Thuật toán 3 là đúng đắn, có nghĩa nó tính đúng ( − new) ⊆ new1 + bao đóng X của X đối với F. Từ Y X X , Y X X X và (2), ( − new) ⊆ new1 ( ∩ new) ⊆ new ⊆ new1 ta có Chứng minh: Vì Thuật toán 3 là một cải tiến của Thuật Y = Y X Y X X . toán 2 và do đó cũng là cải tiến của Thuật toán 1 nên để ( − new) ∪ ( ∩ new) ⊆ new1 chứng minh tính đúng đắn của Thuật toán 3, ta chỉ cần chỉ Từ hai kết quả trên, ta suy ra (3) được chứng minh.  ra rằng việc thay thế Ví dụ 1. Cho F = d a, ad c, e bi, ke m, ce { → → → → → Y Z bởi Y Xnew Z Xnew (1) ik, d bei, h cde . Chúng ta tính bao đóng của tập → − → − → → } thuộc tính X = acd theo Thuật toán 3. Trong Bảng II, ký không có ảnh hưởng gì đến kết quả của việc tính bao đóng. hiệu (I), (II), (III) tương ứng với các đoạn mã (I), (II), (III) Thật vậy, Thuật toán 3 sẽ thay thế Y Z bởi Y X → − new → trong Thuật toán 3 được áp dụng; ký hiệu là phụ thuộc Z X trong trường hợp cả Y và Z đều không phải là × − new hàm trong cột tương ứng bị loại bỏ khỏi F. Kết quả ta được tập con của X . Do đó, từ (1) ta suy ra Y X , Ø vì + new − new X = acdbeikm. So với Thuật toán 2, ta thấy có 4 vị trí nếu Y X = Ø thì Y là tập con của X (mâu thuẫn). − new new (các ô có màu xám) chứng tỏ Thuật toán 3 thực hiện hiệu Mặt khác, ta luôn có quả hơn. Chẳng hạn, với (d a) hoặc (ad c) hoặc → → (e bi) thì Thuật toán 3 chỉ cần kiểm tra vế phải và loại Y Xnew Y Xnew = Y. (2) → ( − ) ∪ ( ∩ ) bỏ ngay trong khi Thuật toán 2 phải kiểm tra vế trái rồi hợp Giả sử sau phép thay thế (1), Xnew thay đổi và nhận giá vế phải vào Xnew (nhưng thực sự Xnew không thay đổi) sau trị mới là X với X X . đó mới loại bỏ. Như vậy, chỉ với 7 phụ thuộc hàm trong new1 new ⊆ new1 14
4. Tập V-2, Số 18 (38), 12/2017 Bảng II MINH HỌA THUẬT TOÁN 3 F d a ad c e bi ke m ce ik d bei h cde → → → → → → → Xnew acd acdbei (I) (I) (III) (II) (I) F e bi ke m e ik × × → → → × × Xnew acdbei acdbeik (I) (III) (II) F k m × → × Xnew acdbeik acdbeikm (II) F × ví dụ trên, Thuật toán 3 đã tiết kiệm được 4 thao tác tính Trong [5] đã chứng minh các kết quả sau: toán vô ích so với Thuật toán 2. Định lý 1 ([5, Định lý 1]). Cho S = Ω, F là một lược đồ h i quan hệ và X là một khóa của S, khi đó III. MỘT SỐ KẾT QUẢ VỀ RÚT GỌN BÀI TOÁN Ω R X Ω R L R . (4) TÌM KHÓA \ ⊆ ⊆ ( \ ) ∪ ( ∩ ) Định lý 2 ([5, Định lý 4]). Cho S = Ω, F là một lược đồ Trong [5], dựa trên ngữ nghĩa quen thuộc của các phụ h i quan hệ, khi đó thuộc hàm trong mô hình cơ sở dữ liệu quan hệ và thuật G = Ω R. (5) toán tính bao đóng của một tập thuộc tính, các tác giả đã \ xây dựng được một điều kiện cần để một tập thuộc tính Mệnh đề 1 ([5, Trong chứng minh Định lý 1]). Ta có thuộc Ω là khóa của S. Tiếp đó, một số hướng cải tiến cho R L H, có nghĩa các thuộc tính trong R L đều là các \ ⊆ \ điều kiện cần thu được cũng đã được xem xét. Trong [6], thuộc tính không khóa. dựa trên việc nghiên cứu các toán tử lý tưởng không tất định (ideal non-deterministic operators) trong khuôn khổ Từ (4), dễ dàng suy ra các nhận xét sau: của lý thuyết dàn, các tác giả của [6] cũng đưa ra một điều Nhận xét 1. Ω R L R là siêu khóa chứa tất cả các ( \ ) ∪ ( ∩ ) kiện cần để một tập thuộc tính là khóa. Như vậy, chúng ta khóa của S. Lưu ý là trong phân tích Ω = Ω R R L ( \ )∪( ∩ )∪ có hai kết quả cho cùng một bài toán được công bố cách R L , chỉ tập L R có khả năng chứa cả hai loại thuộc ( \ ) ( ∩ ) nhau 26 năm mà thoạt nhìn dường như khác nhau. tính là thuộc tính khóa và thuộc tính không khóa. Thêm vào đó, nếu có R L , Ø thì siêu khóa Ω R L R Ω Trong phần này, chúng tôi sẽ chứng minh rằng điều kiện ( \ ) ( \ )∪( ∩ ) ⊂ cần trong [6] chính là một dạng cải tiến của điều kiện cần và việc tìm tập tất cả các khóa chứa trong một siêu khóa trong [5]. Mối quan hệ giữa các dạng của điều kiện cần để nhỏ hơn thực sự Ω sẽ ít tốn kém hơn. Điều này rõ ràng một tập thuộc tính là khóa của một lược đồ quan hệ với liên quan đến việc rút gọn bài toán tìm khóa của một lược đồ quan hệ. Thật vậy, giả sử đã xác định được Z Ω là việc rút gọn bài toán tìm khóa cũng được chỉ ra. ⊂ tập chứa tất cả các khóa của lược đồ quan hệ S = Ω, F . h i Khi đó việc rút gọn bài toán cho việc tìm khóa của S được 1. Nhắc lại một số kết quả đã biết tiến hành qua các bước sau: Trong mục này, một số kết quả trong [5] và [6] được 1) Xác định lược đồ quan hệ S0 = Ω0, F0 trong đó Ω0 = h i nhắc lại để tiện so sánh. Lưu ý rằng thuật ngữ khóa dùng Z Ω R và F0 = Li Ω0 Ri Ω0 Li Ri \( \ ) { ∩ → ∩ | ( → ) ∈ ở đây được hiểu theo nghĩa khóa tối thiểu. F, i = 1, 2, , m ; } 2) Tìm K theo một thuật toán nào đó; Cho S = Ω, F là một lược đồ quan hệ, trong đó Ω = S0 h i 3) Dễ thấy rằng KS = Ω R K K KS . A , A , , An là tập hữu hạn các thuộc tính và F = 0 { 1 2 } { ( \ ) ∪ | ∈ } L1 R1, , Lm Rm Li, Ri Ω, i = 1, , m là tập Nhận xét 2. Các khóa Kj KS không chứa nhau và có { → → | ⊆ ∀ } ∈ hữu hạn các phụ thuộc hàm đúng trên S. cấu trúc chung là Kj = Ω R Zj với Zj L R. Điều ( \ ) ∪ ⊆ ∩ m m Ký hiệu L = Li, R = Ri, KS là tập tất cả các này tạo thuận lợi cho việc xác định các khóa của S. ∪i=1 ∪i=1 khóa của S, KS = Ki Ki là khóa của S , G = Kj KS Kj Nhận xét 3. Trường hợp tồn tại tập Z H sao cho { | } ∩ ∈ ⊆ là giao của tất cả các khóa của S, H = Kj KS Kj là tập tất L R Z , Ø thì Ω R L R Z sẽ là một ∪ ∈ ( ∩ ) ∩ ( \ ) ∪ [( ∩ ) \ ] cả các thuộc tính khóa của S, H = Ω H là tập tất cả các siêu khóa chứa tất cả các khóa của S và siêu khóa này rõ \ thuộc tính không khóa của S. ràng chứa thực sự trong siêu khóa Ω R L R . ( \ ) ∪ ( ∩ ) 15
5. Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông Khi đó Chứng minh: Giả sử điều ngược lại, tức là tồn tại + K KS sao cho K R Ω R , Ø, có nghĩa là tồn tại Ω R Kj Ω R L R Z , Kj KS, ∈ ∩ ∩ ( \ ) ( \ ) ⊆ ⊆ ( \ ) ∪ [( ∩ ) \ ] ∈ A Ω sao cho A K, A R và theo định nghĩa bao đóng, ∀ ∈ ∈ ∈ Ω R A. Vì A R nên A < Ω R. Từ điều kiện (4), có sẽ là một dạng cải tiến của điều kiện cần (4). \ → ∈ \ Ω R K. Kết hợp với A < Ω R, suy ra Ω R K A. ( \ ) ⊆ \ \ ⊆ \ Trong [6, 7], có đưa ra định nghĩa và định lý sau (các Từ đó, K A Ω R. Mặt khác, Ω R A. Kết quả là, \ → \ \ → ký hiệu được sửa lại cho phù hợp với hệ thống ký hiệu đã K A A với A K, chứng tỏ K không là khóa của S. \ → ∈ dùng ở trên). Vậy, K R Ω R + = Ø, có nghĩa là R Ω R + H. ∩ ∩ ( \ ) ∩ ( \ ) ⊆ Định nghĩa 1 ([7, Định nghĩa 3.3]). Cho S = Ω, F là  h i một lược đồ quan hệ, khi đó lõi (core) và thân (body) của Từ Nhận xét 3, định lý sau đây là hiển nhiên. S được định nghĩa như sau: Định lý 4. Cho S = Ω, F là một lược đồ quan hệ, khi đó h i Ω R K Ω R L R R Ω R + , (9) core Ω, F = Ω Ri , ( ) \ \ ⊆ ⊆ ( \ ) ∪ [( ∩ ) \ ∩ ( \ ) ] Li Ri F ( →Ø)∈ với mọi K KS.
   © ª ∈ ­ ® + body Ω, F = Li Ω core Ω, F . Ta xem (9) như một dạng cải tiến của (4). Sau đây là ( ) « ∩ ¬ \ ( ) + Li Ri F một ví dụ trong đó L R R Ω R , Ø có nghĩa ©( →Ø)∈ ª   ( ∩ ) ∩ ∩ ( \ ) ­ ® là Bằng những tính toán đơn giản, ta nhận được
   « ¬ Ω R L R R Ω R + Ω R L R . core Ω, F = Ω R, (6) ( \ ) ∪ [( ∩ ) \ ∩ ( \ ) ] ⊂ ( \ ) ∪ ( ∩ ) ( ) \ Ví dụ 2. Xét lược đồ quan hệ S =
   Ω, F , trong đó Ω = body Ω, F = L Ω Ω R + . (7) h i ( ) ∩ [ \ ( \ ) ] a, b, c, d, e, f, g, h, i và F = a b, b c, d e, h { } { → → → → i, i h . Ví dụ 1[[7, Ví dụ 3.1]] Cho S = Ω, F là một lược đồ → } h i quan hệ, trong đó tập thuộc tính Ω = a, b, c, d, e, f, g, h Với lược đồ quan hệ này, ta có: L = abdhi, R = bcehi, { } + và tập phụ thuộc hàm F = ab c, a g, g c, b L R = bhi, Ω R = adf g; Ω R = abcde f g, R { → → → → ∩ + \ ( \ ) ∩ h, bh d, c d, e f, f e . Ω R = bce. Dễ thấy rằng KS = adf gh, adf gi . Từ đó → → → → } ( \ ) { } + H = a, d, f, g, h, i và H = b, c, e . Bổ đề 3 được nghiệm Ta có L = abce f gh, R = cde f gh, Ω R = ab, Ω R = { } + { } + \ ( \ ) đúng vì R Ω R = bce H. abcdgh, L Ω Ω R = e f . Từ đó, core Ω, F = ab ∩ ( \ ) ⊆ ∩ [ \ ( \ ) ] ( ) Hơn nữa, ta còn có L R R Ω R + = b , Ø. và body Ω, F = e f . ( ∩ ) ∩ ∩ ( \ ) ( ) Và như vậy, với lược đồ quan hệ S được cho trong Ví dụ 2, Định lý 3 ([6, 7, Định lý 3.4]). Cho S = Ω, F là một
   h i ta có lược đồ quan hệ và K là một khóa (tối tiểu) của S, khi đó, + ta có core K core body , có nghĩa là Ω R K Ω R L R R Ω R , ⊆ ⊆ ( ∪ ) \ ⊆ ⊆ ( \ ) ∪ [( ∩ ) \ ∩ ( \ ) ] + với mọi K KS. Cụ thể là, adf g K adf ghi
   , với Ω R K Ω R L Ω Ω R . (8) ∈ ⊆ ⊆ \ ⊆ ⊆ ( \ ) ∪ [ ∩ [ \ ( \ ) ]] K adf gh, adf gi . ∈ { } Rõ ràng (8) là phát biểu của một điều kiện cần để K là khóa của S. Chứng minh của (8) được cho trong [6] cùng 3. So sánh hai điều kiện cần (8) và (9) với một số ví dụ minh họa. Nhận xét 4. Trong (8) dễ thấy rằng L Ω Ω R + = L Ω R + . 2. Một dạng cải tiến cho điều kiện cần (4) ∩ [ \ ( \ ) ] \ ( \ ) Thật vậy, giả sử x L Ω Ω R + . Lúc đó, x L, Trong [5] có chứng minh bổ đề sau: ∈ ∩ [ \ ( \ ) ] ∈ x Ω Ω R +, suy ra x L, x < Ω R +, vì thế ∈ \ ( \ ) ∈ ( \ ) Bổ đề 2 ([5, Bổ đề 3]). Cho S = Ω, F là một lược đồ x L Ω R +. Ngược lại, giả sử x L Ω R +. Khi h i ∈ \ ( \ ) ∈ \ ( \ ) quan hệ và X là một khóa của S, khi đó đó, x L, x < Ω R +, suy ra x L, x Ω Ω R +, vì ∈ ( \ ) ∈ ∈ \ ( \ ) vậy x L Ω Ω R + . X R L R + = Ø. ∈ ∩ [ \ ( \ ) ] ∩ ∩ ( \ ) Do Nhận xét 4, để đơn giản, ta vẫn đánh số bao hàm Bổ đề 2 dễ dàng được mở rộng thành Bổ đề 3 sau đây. thức kép + Bổ đề 3. Cho S = Ω, F là một lược đồ quan hệ, khi đó Ω R K Ω R L Ω R , K KS, (8) h i \ ⊆ ⊆ ( \ ) ∪ [ \ ( \ ) ] ∀ ∈ + + K R Ω R = Ø K KS R Ω R H. là (8). ∩ ∩ ( \ ) ∀ ∈ ⇒ ∩ ( \ ) ⊆ 16
6. Tập V-2, Số 18 (38), 12/2017 Định nghĩa 2. Ta nói rằng điều kiện (8) tốt hơn điều kiện 4. Một bài toán quyết định (9) nếu Cho S = Ω, F là một lược đồ quan hệ và cho Z Ω. h i ⊂ L Ω R + L R R Ω R + Bài toán đặt ra là quyết định xem Z có phải là tập chứa tất \ ( \ ) ⊆ ( ∩ ) \ ∩ ( \ ) cả các khóa của S không.
   và tồn tại một lược đồ quan hệ sao cho Giả sử Z chứa tất cả các khóa của S. Điều đó có nghĩa là Ω + Ω + . L R L R R R Z H = Kj . \ ( \ ) ⊂ ( ∩ ) \ ∩ ( \ ) ⊇ Kj KS Hiểu theo nghĩa đó, ta thấy điều kiện (9) là
   một dạng Ø∈ Từ đó Ω Z Ω H = H. cải tiến của (4). Tương tự, ta có định nghĩa khi nào thì (9) \ ⊆ \ tốt hơn (8). Bổ đề 4. Cho S = Ω, F là một lược đồ quan hệ và cho h i Để so sánh (8) với (9) ta có định lý sau. Z Ω. Khi đó Z chứa tất cả các khóa của S khi và chỉ ⊂ khi Ω Z chỉ gồm các thuộc tính không khóa, có nghĩa là Định lý 5. Hai điều kiện (8) và (9) chỉ là một và được diễn \ đạt bằng những biểu thức khác nhau. Ω Z H. \ ⊆ Chứng minh: Để chứng minh Định lý 5, rõ ràng chỉ Để thấy được ý nghĩa của Bổ đề 4, ta trở lại với điều cần chứng minh kiện (8), là Định lý 3.4 trong [7]. Rõ ràng, điều kiện này khẳng định rằng L Ω R + = L R R Ω R + . (10) \ ( \ ) ( ∩ ) \ ∩ ( \ ) Z = Ω R L Ω R + (13) Giả sử x là một thuộc tính bất kỳ thuộc L Ω
   R +. Khi ( \ ) ∪ [ \ ( \ ) ] + \( \ ) + là tập (siêu khóa) chứa tất cả các khóa của S. đó, với mọi x L Ω R , ta có x L và x < Ω R . Từ ∈ \( \ ) ∈ ( \ ) 1 đó, x L, x < Ω R và x < Ω R +, suy ra x L, x R Để kiểm tra tính chất trên, ta có thể dùng Bổ đề 4. Ta có ∈ +( \ ) ( \ ) ∈ ∈+ và x < Ω R , suy ra x L R và x < R Ω R , Ω Z = Ω Ω R L Ω R + ( \ ) ∈ ( ∩ + ) [ ∩ ( \ ) ] \ \[( \ ) ∪ \ ( \ ) ] suy ra x L R R Ω R , có nghĩa là + ∈ ( ∩ ) \ ∩ ( \ ) = R L Ω R
   + + \ \ ( \ ) L Ω R L R
   R Ω R . (11) = R L R Ω R + . \ ( \ ) ⊆ ( ∩ ) \ ∩ ( \ ) ( \ ) ∪ ∩ (
   \ ) Bây giờ ta chứng minh điều ngược lại. Với
   mọi x Như vậy
   + ∈ L R R Ω R , ta có x L, x R và x < R + ( ∩ ) \ ∩ ( \ ) ∈ ∈ [ ∩ Ω Z = R L Ω R Ω + Ω + \ \ \ ( \ ) R , suy ra x L, x R và x < R , suy ra + ( \ ) ] + ∈
   ∈ ( \ ) = R L R Ω R H, x L Ω R , có nghĩa là ( \ ) ∪ ∩ (
   \ ) ⊆ ∈ \ ( \ ) + + + do đã có R L H (theo [5]) và R
   Ω R H L R R Ω R L Ω R . (12) ( \ ) ⊆ ∩ ( \ ) ⊆ ( ∩ ) \ ∩ ( \ ) ⊆ \ ( \ ) (theo Bổ đề 3). Điều này chứng tỏ rằng Z = Ω R L ( \ ) ∪ [ \ Kết hợp (11) và (12), ta có
   Ω R + là siêu khóa chứa tất cả các khóa của S. ( \ ) ] L Ω R + = L R R Ω R + . \ ( \ ) ( ∩ ) \ ∩ ( \ ) IV. KẾT LUẬN
   Định lý được chứng minh.  Trong bài báo này, chúng tôi đã đề xuất một thuật toán Để minh họa cho Định lý 5, ta trở lại với Ví dụ 1 và Ví cải tiến (Thuật toán 3) tính bao đóng của một tập thuộc dụ 2. Với Ví dụ 1, Ω = a, b, c, d, e, f, g, h , F = ab tính đối với một tập phụ thuộc hàm. Vì tất cả các FD có { } { → c, a g, g c, b h, bh d, c d, e f, f vế phải chứa trong X đều bị loại bỏ trước khi thực sự → → → → → → → new e . Ta có, L = abce f gh, R = cde f gh, L R = ce f gh, tiến hành tính bao đóng nên Thuật toán 3 rõ ràng là hiệu } + ∩+ Ω R = ab, Ω R = abcdgh, R Ω R = cdgh. Từ quả hơn Thuật toán 2. Đặc biệt là trong trường hợp tập F \ ( + \ ) ∩ ( \ ) + đó L Ω R = e f và L R R Ω R = e f . ban đầu gồm một số phụ thuộc hàm có vế phải chứa trong \ ( \ ) ( ∩ ) \ ∩ ( \ ) Với Ví dụ 2, Ω = a, b, c, d, e, f, g, h, i , F = a Xnew hoặc trong quá trình tính giá trị mới của Xnew, việc { }
   { → b, b c, d e, h i, i h . Ta có, L = abdhi, thay thế một phụ thuộc hàm bằng một phụ thuộc hàm đơn → → → → } R = bcehi, L R = bhi, Ω R = adf g; Ω R + = giản hơn, làm xuất hiện một phụ thuộc hàm mới có vế phải ∩ + \ ( \+ ) abcde f g, R Ω R = bce. Từ đó L Ω R = hi chứa trong Xnew. Hơn nữa, tính đúng đắn của Thuật toán 2 ∩ ( \ ) \ ( \ ) và L R R Ω R + = hi. không được chứng minh tường minh khi thực hiện phép ( ∩ ) \ ∩ ( \ ) thay thế các phụ thuộc hàm bằng các phụ thuộc hàm đơn Liên quan tới các điều
   kiện cần để một tập thuộc tính K Ω là khóa của lược đồ quan hệ S = Ω, F , ta có thể ⊆ h i 1Ở đây, với ba tập bất kỳ A, B, C Ω, ta đã áp dụng biến đổi quen xem xét và giải quyết bài toán sau. thuộc A B C = A B A C ⊆. \( \ ) ( \ ) ∪ ( ∩ ) 17
7. Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông giản hơn. Với bổ đề 0, chúng tôi đã chứng minh tính đúng [7] P. Cordero, M. Enciso, and A. Mora, “Automated reasoning đắn này trong Thuật toán 3. Với việc rút gọn bài toán tìm to infer all minimal keys,” in Proceedings of the Twenty- Third International Joint Conference on Artificial Intelligence khóa, chúng tôi cũng đã chứng minh được điều kiện cần (8) (IJCAI), 2013, pp. 817–823. trùng với điều kiện cần (9) là một dạng cải tiến của điều kiện cần (4). Đây là những điều kiện cần để một tập con của Ω là khóa tối tiểu của lược đồ quan hệ S = Ω, F . Việc h i Vũ Quốc Tuấn sinh năm 1982 tại Hải tìm một điều kiện cần tốt hơn (8) hoặc (9) nhằm rút gọn Dương. Ông tốt nghiệp Trường Đại học hơn nữa bài toán tìm khóa là một vấn đề đáng quan tâm. Khoa học Tự nhiên, Đại học Quốc gia Hà Nội, ngành Toán-Tin ứng dụng, năm 2005. Năm 2010, ông nhận bằng Thạc sĩ Công nghệ Thông tin tại Trường Đại học Sư TÀI LIỆU THAM KHẢO phạm Hà Nội. Hiện nay, ông đang công [1] C. Beeri and P. A. Bernstein, “Computational problems re- tác tại Trường Cao đẳng Hải Dương và là lated to the design of normal form relational schemas,” ACM Transactions on Database Systems (TODS), vol. 4, no. 1, pp. nghiên cứu sinh tại Học viện Khoa học và Công nghệ, Viện Hàn 30–59, 1979. lâm Khoa học và Công nghệ Việt Nam. Lĩnh vực nghiên cứu [2] J. Diederich and J. Milton, “New methods and fast algorithms của ông bao gồm khai phá dữ liệu, các hệ cơ sở dữ liệu và for database normalization,” ACM Transactions on Database cơ sở tri thức. Systems (TODS), vol. 13, no. 3, pp. 339–365, 1988. [3] J. Paredaens, P. De Bra, M. Gyssens, and D. Van Gucht, “The Structure of the Relational Database Model,” EATCS Hồ Thuần sinh năm 1933 tại Bắc Ninh, Monographs on Theoretical Computer Science, vol. 17, 1989. nguyên là Trưởng phòng Lập trình, Viện [4] A. Mora, G. Aguilera, M. Enciso, P. Cordero, and I. P. de Guzmán, “A new closure algorithm based in logic: SLFD- Khoa học tính toán và Điều khiển, Viện Closure versus classical closures,” Inteligencia Artificial. Re- Hàn lâm Khoa học và Công nghệ Việt vista Iberoamericana de Inteligencia Artificial, vol. 10, no. 31, Nam. Ông tốt nghiệp Trường Đại học Tổng pp. 31–40, 2006. hợp năm 1960, bảo vệ Tiến sĩ ngành Toán [5] H. Thuan and L. V. Bao, “Some results about key of relational học tính toán năm 1979 và được phong Phó schemas,” Acta Cybernetica, vol. 7, no. 1, pp. 99–113, 1985. Giáo sư năm 1984. Hiện nay, ông là cán bộ [6] A. Mora, I. P. de Guzmán, M. Enciso, and P. Cordero, “Ideal non-deterministic operators as a formal framework to reduce nghỉ hưu. Lĩnh vực nghiên cứu của ông gồm các hệ cơ sở dữ liệu the key finding problem,” International Journal of Computer và cơ sở tri thức, phân tích và thiết kế thuật toán, lý thuyết mật Mathematics, vol. 88, no. 9, pp. 1860–1868, 2011. mã và an toàn dữ liệu. 18