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ệ

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ần này nhắc lại một số khái niệm quan trọng trong lý thuyết cơ sở dữ liệu quan hệ nhằm mục đích sử dụng cho các phần tiếp theo. Lược đồ quan hệ. Một lược đồ quan hệ S là một cặp có thứ tự S = 〈Ω, F〉, trong đó Ω là tập hữu hạn các thuộc tính của quan hệ, F là tập các ràng buộc giữa các thuộc tính. Cho lược đồ quan hệ S = 〈Ω, F〉 với Ω = {A1, A2, . . . , An}. Nếu không quan tâm đến tập các ràng buộc F thì ta sẽ dùng ký hiệu S(Ω) thay cho S = 〈Ω, F〉. 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à X ⊆ Ω , ta ký hiệu t[X] là bộ chỉ chứa các giá trị của bộ t tại các thuộc tính trong X . 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 gọi là phụ thuộc hàm vào X trên lược đồ S(Ω), ký hiệu là X → Y , nếu với mọi quan hệ r trên lược đồ S(Ω), với hai bộ bất kỳ t1, t2 ∈ r mà t1[X] = t2[X] thì t1[Y ] = t2[Y ]. Nếu Y phụ thuộc hàm vào X thì ta cũng nói “X xác định hàm Y”. Với mỗi quan hệ r trên lược đồ S(Ω), ta nói r thỏa 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ộ t1, t2 ∈ r , t1[X] = t2[X] kéo theo t1[Y ] = t2[Y ]. Trong bài báo này, ta hạn chế F (của lược đồ S = 〈Ω, F〉) chỉ gồm các phụ thuộc hàm. Hệ quy tắc suy diễn Armstrong. Với lược đồ quan hệ S = 〈Ω, F〉 và X , Y ⊆ Ω, ta ký hiệu XY thay cho X ∪ Y . Với mọi X , Y , Z ⊆ Ω, hệ quy tắc suy diễn Armstrong đối 12 Tập V-2, Số 18 (38), 12/2017 Thuật toán 1: Tính bao đóng X+ Input: Ω, F, X ⊆ Ω Output: X+ begin X+ = X repeat for each (Y → Z) ∈ F do if Y ⊆ X+ then X+ = X+ ∪ Z; end if end for each until không còn thuộc tính nào được thêm vào X+; return X+; end với các phụ thuộc hàm gồm ba quy tắc sau đây: A1. (Phản xạ): Nếu Y ⊆ X thì X → Y ; A2. (Gia tăng): Nếu X → Y thì XZ → YZ; A3. (Bắc cầu): Nếu X → Y và Y → Z thì X → Z . 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. Bao đóng của một tập thuộc tính. Cho tập phụ thuộc hàm F xác định trên tập thuộc tính Ω (phụ thuộc hàm (FD: functional dependency) Y → Z xác định trên tập thuộc tính Ω nếu Y , Z ⊆ Ω) và X ⊆ Ω. Ta gọi bao đóng của tập thuộc tính X đối với tập phụ thuộc hàm F, ký hiệu là X+F , là tập tất cả các thuộc tính A của Ω sao cho X → A được suy diễn từ F nhờ hệ quy tắc suy diễn Armstrong, X+F = { A ∈ Ω| (X → A) ∈ F+} . 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 kiện sau đây đồng thời được thỏa mãn: i) (K → Ω) ∈ F+; ii) Nếu K ′ ⊂ K thì (K ′→ Ω) < F+. II. THUẬT TOÁN CẢI TIẾN TÍNH BAO ĐÓNG CỦA MỘT TẬP THUỘC TÍNH 1. Thuật toán chuẩn tính bao đóng X+ Thuật toán 1 là thuật toán tính bao đóng X+. Dễ chứng minh được rằng độ phức tạp thời gian của Thuật toán 1 là O(npmin{n, p}), trong đó n là số thuộc tính trong Ω và p là số phụ thuộc hàm trong F. Như vậy, thuật toán trên không là tuyến tính theo tích np. Để có các thuật toán tính bao đóng với độ phức tạp tuyến tính, cần sử dụng một số cấu trúc dữ liệu thích hợp nhằm giảm chi phí của việc duyệt các tập F và Ω. Các chiến lược rút gọn bao gồm: Thuật toán 2: Tính bao đóng X+ [4] Input: Ω, F, X ⊆ Ω Output: X+ begin Xnew = X; repeat Xold = Xnew; for each (Y → Z) ∈ F do if Y ⊆ Xnew then Xnew = Xnew ∪ Z; . (I) F = F − {Y → Z}; else if Z ⊆ Xnew then F = F − {Y → Z}; . (II) else F = F − {Y → Z}; . (III) F = F ∪ {Y − Xnew → Z − Xnew}; . (III) end if end for each until (Xnew = Xold) hoặc (|F | = 0); return X+ = Xnew; end i) Dùng một tập để lưu giữ các thuộc tính còn phải thêm vào bao đóng; ii) Dùng một mảng được đánh chỉ số bởi các thuộc tính Ai để lưu giữ các phụ thuộc hàm có vế trái chứa Ai; iii) Lưu giữ số thuộc tính thuộc vế trái của mỗi phụ thuộc hàm còn chưa có mặt trong bao đóng. Các chiến lược này đã giúp một số tác giả xây dựng được các thuật toán tuyến tính tính bao đóng, tức có độ phức tạp thời gian là O(np). Đó là các thuật toán của Beeri trong [1], của Diederich trong [2] và của Paredaens trong [3]. 2. Thuật toán của Mora và cộng sự Thuật toán 2 và các thuật toán tính bao đóng của 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: 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 nhiên lần lượt có 25, 50, 75, 100, 125, 150, 175 và 200 phụ thuộc hàm, số lượng các thuộc tính ở vế trái và vế phải của các phụ thuộc hàm biến đổi từ 1 đến 300, kích thước của các tập phụ thuộc hàm từ 50 đến 61770 thuộc tính (kích thước của một tập phụ thuộc hàm F được định nghĩa là tổng các kích thước của các phụ thuộc hàm trong F; kích thước của X → Y là |X | + |Y |; |X | là số thuộc tính của tập X); thực hiện thử nghiệm các thuật toán 1817 lần. Kết quả thử nghiệm cho thời gian tính toán của 1817 lần thực hiện được cho trong Bảng I, trong đó thời gian trung bình tính 13 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 KẾT QUẢ THỬ NGHIỆM Thuật toán Trung bình Thuật toán tính bao đóng X+ của Diederich 4593,48 Thuật toán tính bao đóng X+ của Beeri 7013,56 Thuật toán tính bao đóng X+ của Paredaens 5863,35 Thuật toán tính bao đóng của nhóm A. Mora và cộng sự (Thuật toán 2) 1262,41 theo đơn vị giây. Từ bảng kết quả trên, ta thấy Thuật toán 2 tiêu tốn ít thời gian hơn ba thuật toán còn lại. 3. Thuật toán cải tiến tính bao đóng Ta nhận thấy rằng, so với các thuật toán tính bao đóng đã nêu trong mục II-1, Thuật toán 2 có ưu điểm là làm đơn giản hóa tập F bằng cách loại bỏ FD Y → Z trong F 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 trường hợp cả hai vế của FD này đều không là những tập con của Xnew. Tuy nhiên, tính đúng đắn của Thuật toán 2 không được chứng minh một cách tường minh. Hơn nữa, nhược điểm của nó là mỗi lần duyệt tập F, tất cả các FD có vế trái và vế phải cùng chứa trong Xnew vẫn được kiểm tra vế trái để từ đó tính giá trị mới của Xnew (điều này làm mất 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ừ đầu các FD có vế phải chứa trong Xnew nên thời gian thực hiện nhanh hơn so với Thuật toán 2. Với Thuật toán 3, ta có bổ đề sau đây. Bổ đề 1. Thuật toán 3 là đúng đắn, có nghĩa nó tính đúng bao đóng X+ của X đối với F. Chứng minh: Vì Thuật toán 3 là một cải tiến của Thuật toán 2 và do đó cũng là cải tiến của Thuật toán 1 nên để chứng minh tính đúng đắn của Thuật toán 3, ta chỉ cần chỉ ra rằng việc thay thế Y → Z bởi Y − Xnew → Z − Xnew (1) không có ảnh hưởng gì đến kết quả của việc tính bao đóng. Thật vậy, Thuật toán 3 sẽ thay thế Y → Z bởi Y−Xnew → Z − Xnew trong trường hợp cả Y và Z đều không phải là tập con của Xnew. Do đó, từ (1) ta suy ra Y − Xnew , Ø vì nếu Y − Xnew = Ø thì Y là tập con của Xnew (mâu thuẫn). Mặt khác, ta luôn có (Y − Xnew) ∪ (Y ∩ Xnew) = Y . (2) Giả sử sau phép thay thế (1), Xnew thay đổi và nhận giá trị mới là Xnew1 với Xnew ⊆ Xnew1. Thuật toán 3: Tính bao đóng X+ Input: Ω, F, X ⊆ Ω Output: X+ begin Xnew = X; repeat Xold = Xnew; for each (Y → Z) ∈ F do if Z ⊆ Xnew then F = F − {Y → Z}; . (I) else if Y ⊆ Xnew then begin . (II) Xnew = Xnew ∪ Z; F = F − {Y → Z}; end else begin . (III) F = F − {Y → Z}; F = F ∪ {Y − Xnew → Z − Xnew}; end end if end for each until (Xnew = Xold) or (|F | = 0); return Xnew; end Bây giờ ta phải chứng minh (Y − Xnew) ⊆ Xnew1 ⇐⇒ Y ⊆ Xnew1. (3) Thật vậy, từ Y ⊆ Xnew1 ta có (Y − Xnew) ⊆ Xnew1. Từ (Y − Xnew) ⊆ Xnew1, (Y ∩ Xnew) ⊆ Xnew ⊆ Xnew1 và (2), ta có Y = (Y − Xnew) ∪ (Y ∩ Xnew) ⊆ Xnew1. Từ hai kết quả trên, ta suy ra (3) được chứng minh.  Ví dụ 1. Cho F = {d → a, ad → c, e→ bi, ke→ m, ce→ 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ý hiệu (I), (II), (III) tương ứng với các đoạn mã (I), (II), (III) trong Thuật toán 3 được áp dụng; ký hiệu × là phụ thuộc hàm trong cột tương ứng bị loại bỏ khỏi F. Kết quả ta được X+ = acdbeikm. So với Thuật toán 2, ta thấy có 4 vị trí (các ô có màu xám) chứng tỏ Thuật toán 3 thực hiện hiệu 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 bỏ ngay trong khi Thuật toán 2 phải kiểm tra vế trái rồi hợp vế phải vào Xnew (nhưng thực sự Xnew không thay đổi) sau đó mới loại bỏ. Như vậy, chỉ với 7 phụ thuộc hàm trong 14 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 toán vô ích so với Thuật toán 2. III. MỘT SỐ KẾT QUẢ VỀ RÚT GỌN BÀI TOÁN TÌM KHÓA Trong [5], dựa trên ngữ nghĩa quen thuộc của các phụ thuộc hàm trong mô hình cơ sở dữ liệu quan hệ và thuật 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 thuộc Ω là khóa của S. Tiếp đó, một số hướng cải tiến cho điều kiện cần thu được cũng đã được xem xét. Trong [6], 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ổ của lý thuyết dàn, các tác giả của [6] cũng đưa ra một điều kiện cần để một tập thuộc tính là khóa. Như vậy, chúng ta có hai kết quả cho cùng một bài toán được công bố cách nhau 26 năm mà thoạt nhìn dường như khác nhau. 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 trong [5]. Mối quan hệ giữa các dạng của điều kiện cần để một tập thuộc tính là khóa của một lược đồ quan hệ với việc rút gọn bài toán tìm khóa cũng được chỉ ra. 1. Nhắc lại một số kết quả đã biết Trong mục này, một số kết quả trong [5] và [6] được nhắc lại để tiện so sánh. Lưu ý rằng thuật ngữ khóa dùng ở đây được hiểu theo nghĩa khóa tối thiểu. Cho S = 〈Ω, F〉 là một lược đồ quan hệ, trong đó Ω = {A1, A2, . . . , An} là tập hữu hạn các thuộc tính và F = { L1 → R1, . . . , Lm → Rm | Li, Ri ⊆ Ω, ∀ i = 1, . . . ,m} là tập hữu hạn các phụ thuộc hàm đúng trên S. Ký hiệu L = ∪m i=1Li , R = ∪mi=1Ri , KS là tập tất cả các khóa của S, KS = {Ki |Ki là khóa của S}, G = ∩K j ∈KSKj là giao của tất cả các khóa của S, H = ∪K j ∈KSKj là tập tất cả các thuộc tính khóa của S, H = Ω \ H là tập tất cả các thuộc tính không khóa của S. Trong [5] đã chứng minh các kết quả sau: Định lý 1 ([5, Định lý 1]). Cho S = 〈Ω, F〉 là một lược đồ quan hệ và X là một khóa của S, khi đó Ω \ R ⊆ X ⊆ (Ω \ R) ∪ (L ∩ R) . (4) Định lý 2 ([5, Định lý 4]). Cho S = 〈Ω, F〉 là một lược đồ quan hệ, khi đó G = Ω \ R. (5) Mệnh đề 1 ([5, Trong chứng minh Định lý 1]). Ta có R \ L ⊆ H, có nghĩa các thuộc tính trong R \ L đều là các thuộc tính không khóa. Từ (4), dễ dàng suy ra các nhận xét sau: Nhận xét 1. (Ω \ R)∪ (L ∩ R) là siêu khóa chứa tất cả các khóa của S. Lưu ý là trong phân tích Ω = (Ω \ R)∪(R ∩ L)∪ (R \ L), chỉ tập (L ∩ R) có khả năng chứa cả hai loại thuộc 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) ⊂ Ω và việc tìm tập tất cả các khóa chứa trong một siêu khóa nhỏ hơn thực sự Ω sẽ ít tốn kém hơn. Điều này rõ ràng 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à tập chứa tất cả các khóa của lược đồ quan hệ S = 〈Ω, F〉. Khi đó việc rút gọn bài toán cho việc tìm khóa của S được tiến hành qua các bước sau: 1) Xác định lược đồ quan hệ S′ = 〈Ω′, F ′〉 trong đó Ω′ = Z\(Ω \ R) và F ′ = { Li ∩Ω′→ Ri ∩Ω′ | (Li → Ri) ∈ F, i = 1, 2, . . . ,m}; 2) Tìm KS′ theo một thuật toán nào đó; 3) Dễ thấy rằng KS = { (Ω \ R) ∪ K | K ∈ KS′}. Nhận xét 2. Các khóa Kj ∈ KS không chứa nhau và có cấu trúc chung là Kj = (Ω \ R) ∪ Z j với Z j ⊆ L ∩ R. Điều này tạo thuận lợi cho việc xác định các khóa của S. Nhận xét 3. Trường hợp tồn tại tập Z ⊆ H sao cho (L ∩ R) ∩ Z , Ø thì (Ω \ R) ∪ [(L ∩ R) \ Z] sẽ là một siêu khóa chứa tất cả các khóa của S và siêu khóa này rõ ràng chứa thực sự trong siêu khóa (Ω \ R) ∪ (L ∩ R). 15 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 đó (Ω \ R) ⊆ Kj ⊆ (Ω \ R) ∪ [(L ∩ R) \ Z], ∀Kj ∈ KS, sẽ là một dạng cải tiến của điều kiện cần (4). Trong [6, 7], có đưa ra định nghĩa và định lý sau (các ký hiệu được sửa lại cho phù hợp với hệ thống ký hiệu đã dùng ở trên). Định nghĩa 1 ([7, Định nghĩa 3.3]). Cho S = 〈Ω, F〉 là một lược đồ quan hệ, khi đó lõi (core) và thân (body) của S được định nghĩa như sau: core (Ω, F) = Ω \ ©­« ⋃ (Li→Ri )∈F Ri ª®¬ , body (Ω, F) = ©­« ⋃ (Li→Ri )∈F Li ª®¬ ∩ [ Ω \ core (Ω, F)+] . Bằng những tính toán đơn giản, ta nhận được core (Ω, F) = Ω \ R, (6) body (Ω, F) = L ∩ [Ω \ (Ω \ R)+]. (7) Ví dụ 1[[7, Ví dụ 3.1]] Cho S = 〈Ω, F〉 là một lược đồ quan hệ, trong đó tập thuộc tính Ω = {a, b, c, d, e, f , g, h} và tập phụ thuộc hàm F = {ab → c, a → g, g → c, b → h, bh→ d, c→ d, e→ f , f → e}. Ta có L = abce f gh, R = cde f gh, Ω\R = ab, (Ω\R)+ = abcdgh, L ∩ [Ω \ (Ω \ R)+] = e f . Từ đó, core (Ω, F) = ab và body (Ω, F) = e f . Định lý 3 ([6, 7, Định lý 3.4]). Cho S = 〈Ω, F〉 là một 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)+]]. (8) 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 với một số ví dụ minh họa. 2. Một dạng cải tiến cho điều kiện cần (4) Trong [5] có chứng minh bổ đề sau: Bổ đề 2 ([5, Bổ đề 3]). Cho S = 〈Ω, F〉 là một lược đồ quan hệ và X là một khóa của S, khi đó X ∩ R ∩ (L \ R)+ = Ø. Bổ đề 2 dễ dàng được mở rộng thành Bổ đề 3 sau đây. Bổ đề 3. Cho S = 〈Ω, F〉 là một lược đồ quan hệ, khi đó K ∩ R ∩ (Ω \ R)+ = Ø ∀K ∈ KS ⇒ R ∩ (Ω \ R)+ ⊆ H. 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 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ó (Ω \ R) ⊆ K . Kết hợp với A < Ω \ R, suy ra Ω \ R ⊆ K \ A. Từ đó, K \ A→ Ω \ R. Mặt khác, Ω \ R→ A. Kết quả là, K \ A → A với A ∈ K , chứng tỏ K không là khóa của S. Vậy, K ∩ R ∩ (Ω \ R)+ = Ø, có nghĩa là R ∩ (Ω \ R)+ ⊆ H.  Từ Nhận xét 3, định lý sau đây là hiển nhiên. Định lý 4. Cho S = 〈Ω, F〉 là một lược đồ quan hệ, khi đó Ω \ R ⊆ K ⊆ (Ω \ R) ∪ [(L ∩ R) \ (R ∩ (Ω \ R)+)], (9) với mọi K ∈ KS . Ta xem (9) như một dạng cải tiến của (4). Sau đây là một ví dụ trong đó (L ∩ R) ∩ (R ∩ (Ω \ R)+) , Ø có nghĩa là (Ω \ R) ∪ [(L ∩ R) \ (R ∩ (Ω \ R)+)] ⊂ (Ω \ R) ∪ (L ∩ R) . Ví dụ 2. Xét lược đồ quan hệ S = 〈Ω, F〉, trong đó Ω = {a, b, c, d, e, f , g, h, i} và F = {a → b, b → c, d → e, h → i, i → h}. Với lược đồ quan hệ này, ta có: L = abdhi, R = bcehi, L ∩ R = bhi, Ω \ R = adf g; (Ω \ R)+ = abcde f g, R ∩ (Ω \ 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 đúng vì R ∩ (Ω \ R)+ = bce ⊆ H. Hơn nữa, ta còn có (L ∩ R) ∩ (R ∩ (Ω \ R)+) = b , Ø. Và như vậy, với lược đồ quan hệ S được cho trong Ví dụ 2, ta có Ω \ R ⊆ K ⊆ (Ω \ R) ∪ [(L ∩ R) \ (R ∩ (Ω \ R)+)], với mọi K ∈ KS . Cụ thể là, adf g ⊆ K ⊆ adf ghi, với K ∈ {adf gh, adf gi}. 3. So sánh hai điều kiện cần (8) và (9) Nhận xét 4. Trong (8) dễ thấy rằng L ∩ [Ω \ (Ω \ R)+] = L \ (Ω \ R)+ . Thật vậy, giả sử x ∈ L ∩ [Ω \ (Ω \ R)+]. Lúc đó, x ∈ L, x ∈ Ω \ (Ω \ R)+, suy ra x ∈ L, x < (Ω \ R)+, vì thế x ∈ L \ (Ω \ R)+. Ngược lại, giả sử x ∈ L \ (Ω \ R)+. Khi đó, x ∈ L, x < (Ω \ R)+, suy ra x ∈ L, x ∈ Ω \ (Ω \ R)+, vì vậy x ∈ L ∩ [Ω \ (Ω \ R)+]. Do Nhận xét 4, để đơn giản, ta vẫn đánh số bao hàm thức kép Ω \ R ⊆ K ⊆ (Ω \ R) ∪ [L \ (Ω \ R)+], ∀K ∈ KS, (8) là (8). 16 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 (9) nếu L \ (Ω \ R)+ ⊆ (L ∩ R) \ (R ∩ (Ω \ R)+) và tồn tại một lược đồ quan hệ sao cho L \ (Ω \ R)+ ⊂ (L ∩ R) \ (R ∩ (Ω \ R)+) . Hiểu theo nghĩa đó, ta thấy điều kiện (9) là một dạng 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). Để so sánh (8) với (9) ta có định lý sau. Đị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. Chứng minh: Để chứng minh Định lý 5, rõ ràng chỉ cần chứng minh L \ (Ω \ R)+ = (L ∩ R) \ (R ∩ (Ω \ R)+) . (10) Giả sử x là một thuộc tính bất kỳ thuộc L \(Ω \ R)+. Khi đó, với mọi x ∈ L\(Ω \ R)+, ta có x ∈ L và x < (Ω \ R)+. Từ đó, x ∈ L, x < (Ω \ R) và x < (Ω \ R)+, suy ra x ∈ L, x ∈ R và x < (Ω \ R)+, suy ra x ∈ (L ∩ R) và x < [R ∩ (Ω \ R)+], suy ra x ∈ (L ∩ R) \ (R ∩ (Ω \ R)+) , có nghĩa là L \ (Ω \ R)+ ⊆ (L ∩ R) \ (R ∩ (Ω \ R)+) . (11) Bây giờ ta chứng minh điều ngược lại. Với mọi x ∈ (L ∩ R) \ (R ∩ (Ω \ R)+) , ta có x ∈ L, x ∈ R và x < [R ∩ (Ω \ R)+], suy ra x ∈ L, x ∈ R và x < (Ω \ R)+, suy ra x ∈ L \ (Ω \ R)+, có nghĩa là (L ∩ R) \ (R ∩ (Ω \ R)+) ⊆ L \ (Ω \ R)+ . (12) Kết hợp (11) và (12), ta có L \ (Ω \ R)+ = (L ∩ R) \ (R ∩ (Ω \ R)+) . Định lý được chứng minh.  Để minh họa cho Định lý 5, ta trở lại với Ví dụ 1 và Ví dụ 2. Với Ví dụ 1, Ω = {a, b, c, d, e, f , g, h}, F = {ab → c, a → g, g → c, b → h, bh → d, c → d, e → f , f → e}. Ta có, L = abce f gh, R = cde f gh, L ∩ R = ce f gh, Ω \ R = ab, (Ω \ R)+ = abcdgh, R ∩ (Ω \ R)+ = cdgh. Từ đó L \ (Ω \ R)+ = e f và (L ∩ R) \ (R ∩ (Ω \ R)+) = e f . Với Ví dụ 2, Ω = {a, b, c, d, e, f , g, h, i}, F = {a → b, b → c, d → e, h → i, i → h}. Ta có, L = abdhi, R = bcehi, L ∩ R = bhi, Ω \ R = adf g; (Ω \ R)+ = abcde f g, R ∩ (Ω \ R)+ = bce. Từ đó L \ (Ω \ R)+ = hi và (L ∩ R) \ (R ∩ (Ω \ R)+) = hi. 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ể xem xét và giải quyết bài toán sau. 4. Một bài toán quyết định Cho S = 〈Ω, F〉 là một lược đồ quan hệ và cho Z ⊂ Ω. 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. Giả sử Z chứa tất cả các khóa của S. Điều đó có nghĩa là Z ⊇ H = ⋃ K j ∈KS Kj . Từ đó Ω \ Z ⊆ Ω \ H = H. Bổ đề 4. Cho S = 〈Ω, F〉 là một lược đồ quan hệ và cho 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à Ω \ Z ⊆ H. Để thấy được ý nghĩa của Bổ đề 4, ta trở lại với điều kiện (8), là Định lý 3.4 trong [7]. Rõ ràng, điều kiện này khẳng định rằng Z = (Ω \ R) ∪ [L \ (Ω \ R)+] (13) là tập (siêu khóa) chứa tất cả các khóa của S. Để kiểm tra tính chất trên, ta có thể dùng Bổ đề 4. Ta có1 Ω \ Z = Ω \ [(Ω \ R) ∪ (L \ (Ω \ R)+)] = R \ (L \ (Ω \ R)+) = (R \ L) ∪ (R ∩ (Ω \ R)+) . Như vậy Ω \ Z = R \ (L \ (Ω \ R)+) = (R \ L) ∪ (R ∩ (Ω \ R)+) ⊆ H, do đã có (R \ L) ⊆ H (theo [5]) và R ∩ (Ω \ R)+ ⊆ H (theo Bổ đề 3). Điều này chứng tỏ rằng Z = (Ω \ R) ∪ [L \ (Ω \ R)+] là siêu khóa chứa tất cả các khóa của S. IV. KẾT LUẬN Trong bài báo này, chúng tôi đã đề xuất một thuật toán cải tiến (Thuật toán 3) tính bao đóng của một tập thuộc tính đối với một tập phụ thuộc hàm. Vì tất cả các FD có vế phải chứa trong Xnew đều bị loại bỏ trước khi thực sự tiến hành tính bao đóng nên Thuật toán 3 rõ ràng là hiệu quả hơn Thuật toán 2. Đặc biệt là trong trường hợp tập F ban đầu gồm một số phụ thuộc hàm có vế phải chứa trong Xnew hoặc trong quá trình tính giá trị mới của Xnew, việc thay thế một phụ thuộc hàm bằng một phụ thuộc hàm đơn giản hơn, làm xuất hiện một phụ thuộc hàm mới có vế phải chứa trong Xnew. Hơn nữa, tính đúng đắn của Thuật toán 2 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 1Ở đây, với ba tập bất kỳ A, B, C ⊆ Ω, ta đã áp dụng biến đổi quen thuộc A \ (B \C) = (A \ B) ∪ (A∩C). 17 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 đắn này trong Thuật toán 3. Với việc rút gọn bài toán tìm khóa, chúng tôi cũng đã chứng minh được điều kiện cần (8) 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 tìm một điều kiện cần tốt hơn (8) hoặc (9) nhằm rút gọn hơn nữa bài toán tìm khóa là một vấn đề đáng quan tâm. TÀI LIỆU THAM KHẢO [1] C. Beeri and P. A. Bernstein, “Computational problems re- lated to the design of normal form relational schemas,” ACM Transactions on Database Systems (TODS), vol. 4, no. 1, pp. 30–59, 1979. [2] J. Diederich and J. Milton, “New methods and fast algorithms for database normalization,” ACM Transactions on Database 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 Monographs on Theoretical Computer Science, vol. 17, 1989. [4] A. Mora, G. Aguilera, M. Enciso, P. Cordero, and I. P. de Guzmán, “A new closure algorithm based in logic: SLFD- Closure versus classical closures,” Inteligencia Artificial. Re- vista Iberoamericana de Inteligencia Artificial, vol. 10, no. 31, pp. 31–40, 2006. [5] H. Thuan and L. V. Bao, “Some results about key of relational schemas,” Acta Cybernetica, vol. 7, no. 1, pp. 99–113, 1985. [6] A. Mora, I. P. de Guzmán, M. Enciso, and P. Cordero, “Ideal non-deterministic operators as a formal framework to reduce the key finding problem,” International Journal of Computer Mathematics, vol. 88, no. 9, pp. 1860–1868, 2011. [7] P. Cordero, M. Enciso, and A. Mora, “Automated reasoning to infer all minimal keys,” in Proceedings of the Twenty- Third International Joint Conference on Artificial Intelligence (IJCAI), 2013, pp. 817–823. Vũ Quốc Tuấn sinh năm 1982 tại Hải Dương. Ông tốt nghiệp Trường Đại học 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ư phạm Hà Nội. Hiện nay, ông đang công tác tại Trường Cao đẳng Hải Dương và là nghiên cứu sinh tại 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. Lĩnh vực nghiên cứu của ông bao gồm khai phá dữ liệu, các hệ cơ sở dữ liệu và cơ sở tri thức. Hồ Thuần sinh năm 1933 tại Bắc Ninh, nguyên là Trưởng phòng Lập trình, Viện Khoa học tính toán và Điều khiển, Viện Hàn lâm Khoa học và Công nghệ Việt Nam. Ông tốt nghiệp Trường Đại học Tổng hợp năm 1960, bảo vệ Tiến sĩ ngành Toán học tính toán năm 1979 và được phong Phó Giáo sư năm 1984. Hiện nay, ông là cán bộ nghỉ hưu. Lĩnh vực nghiên cứu của ông gồm các hệ cơ sở dữ liệu và cơ sở tri thức, phân tích và thiết kế thuật toán, lý thuyết mật mã và an toàn dữ liệu. 18