Một số kết quả về rút gọn bài toán tìm khóa

g [2, 3], 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 (Định nghĩa 3.3 trong [3]). Cho S = 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) =  \ 
( )i i
i
L R F
R
 
     
 và body(, F) = 
( )i i
i
L R F
L
 
     
  [ \ core(, F)+] 
Bằng những tính toán đơn giản, ta nhận được: 
core(, F) =  \ R và body(, F) = L  [ \ ( \ R)+] 
Ví dụ 1 (Ví dụ 3.1 trong [3]). Cho S = 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 = abcefgh, R = cdefgh,  \ R = ab, ( \ R)+ = abcdgh, L  [  \ ( \ 
R)+] = ef. Từ đó core(, F) = ab và body(, F) = ef. 
Định lý 3 (Định lý 3.4 trong [2, 3]). Cho S = 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 
  \ R  K  ( \ R)  [L  [ \ ( \ R)+] ] (2) 
Công nghệ thông tin & Cơ sở toán học cho tin học 
V. Q. Tuấn, H. Thuần, “Một số kết quả về rút gọn bài toán tìm khóa.” 104 
Rõ ràng (2) 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 (2) được cho trong [2] 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 (1) 
Trong [1] có chứng minh bổ đề sau: 
Bổ đề 1 (Bổ đề 3 trong [1]). Cho S = là một lược đồ quan hệ và X là một 
khóa của S. Khi đó 
X  R  (L \ R)+ =  
Bổ đề 1 dễ dàng được mở rộng thành bổ đề 2 dưới đây: 
Bổ đề 2. Cho S = là một lược đồ quan hệ. Khi đó 
K  R  ( \ R)+ = ,  SK  , 
có nghĩa R  ( \ R)+  H 
Chứng minh. Giả sử ngược lại:  SK K sao cho K  R  ( \ R)
+ ≠ , có nghĩa 
 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 (1) có  \ R  K. Kết hợp với A   \ R, suy ra 
 \ R  K \ A. Từ đó có 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. Tóm lại ta đã chứng minh được 
K  [R  ( \ R)+] = ,  SK K , 
có nghĩa R  ( \ R)+  H 
Từ nhận xét 3, định lý sau đây là hiển nhiên. 
Định lý 4. Cho S = là một lược đồ quan hệ. Khi đó 
  \ R  K  ( \ R)  [(L  R) \ (R  ( \ R)+ )],  SK  (3) 
Ta xem (3) như một dạng cải tiến của (1). 
Sau đây là một ví dụ trong đó (L  R)  (R  ( \ R)+ ) ≠ , có nghĩa 
 ( \ R)  [(L  R) \ (R  ( \ R)+) ]  ( \ R)  (L  R). 
Ví dụ 2. Xét lược đồ quan hệ S = 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 = 
adfg; 
( \ R)+ = abcdefg, R  ( \ R)+ = bce. Dễ thấy rằng S = {adfgh, adfgi}. Từ 
đó H = {a, d, f, g, h, i} và H = {b, c, e}. 
Bổ đề 2 đượ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ó 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 47, 02 - 2017 105
 \ R  K  ( \ R)  [(L  R) \ (R  ( \ R)+ )],  SK  , 
cụ thể là adfg  K  adfghi với K {adfgh, adfgi}. 
3. SO SÁNH HAI ĐIỀU KIỆN CẦN (2) VÀ (3) 
Để dễ so sánh, ta phát biểu lại hai điều kiện cần (2) và (3) như sau: 
Cho lược đồ quan hệ S = . Khi đó 
  \ R  K  ( \ R)  [L  [ \ ( \ R)+ ]],  SK  
  \ R  K  ( \ R)  [(L  R) \ (R  ( \ R)+ )],  SK  
Nhận xét 4. Dễ thấy rằng L  [ \ ( \ R)+ ] = L \ ( \ R)+. Thật vậy, giả sử x  L 
 [ \ ( \ R)+ ]  x  L, x   \ ( \ R)+  x  L, x  ( \ R)+  x L \ ( \ 
R)+. Ngược lại, giả sử x L \ ( \ R)+  x  L, x  ( \ R)+  x  L, x   \ ( \ 
R)+  x  L  [ \ ( \ R)+ ]. 
Định nghĩa 2. Ta nói rằng điều kiện (2) tốt hơn điều kiện (3) 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 (3) là một dạng cải tiến của (1). Tương tự, 
ta có định nghĩa khi nào thì (3) tốt hơn (2). Để so sánh (2) với (3) ta có định lý sau: 
Định lý 5. Hai điều kiện (2) và (3) 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)+ ) (4) 
Giả sử x là một thuộc tính bất kỳ thuộc L \ ( \ R)+. 
 x  L \ ( \ R)+  (x  L) và x  ( \ R)+  (x  L), x  ( \ R) và x  ( \ R)+ 
 (x  L), x  R và x  ( \ R)+  (x  L  R) và x  [R  ( \ R)+]  x  (L  
R) \ [(R  ( \ R)+], 
có nghĩa L \ ( \ R)+  (L  R) \ (R  ( \ R)+ ) (5) 
Bây giờ ta chứng minh điều ngược lại: 
 x  (L  R) \ [R  ( \ R)+ ]  (x  L), (x  R) và (x  [R  ( \ R)+]) 
 (x  L), (x  R) và (x  ( \ R)+)  x  L \ ( \ R)+, 
có nghĩa (L  R) \ (R  ( \ R)+ )  L \ ( \ R)+ (6) 
Kết hợp (5) và (6), ta có: L \ ( \ R)+ = (L  R) \ (R  ( \ R)+ ). Định lý 5 được 
chứng minh. 
Để minh họa cho định lý 5, ta trở lại với ví dụ 1 và 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 = abcefgh, R = cdefgh, L  R = cefgh,  \ R = 
ab, ( \ R)+ = abcdgh, R  ( \ R)+ = cdgh. 
Công nghệ thông tin & Cơ sở toán học cho tin học 
V. Q. Tuấn, H. Thuần, “Một số kết quả về rút gọn bài toán tìm khóa.” 106 
Từ đó L \ ( \ R)+ = ef và (L  R) \ (R  ( \ R)+ ) = ef. 
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 = adfg; ( \ R)+ ) = abcdefg, 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 = , 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 = 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  
j S
j
K K
H K

  
Từ đó  \ Z   \ H = H . 
Bổ đề 3. Cho S = 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ổ đề 3, ta trở lại với điều kiện (2), là định lý 3.4 
trong [3]. 
 ( \ R)  K  ( \ R)  [L \ ( \ R)+ ],  SK K 
Rõ ràng (2) khẳng định rằng Z = ( \ R)  [L \ ( \ R)+ ] 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 đó, ta có thể dùng bổ đề 3. 
Ta có: 
 \ Z =  \ [( \ R)  (L \ ( \ R)+) ] = R \ (L \ ( \ R)+) = (R \ L)  (R  ( \ R)+) 
(Ở đây, với ba tập bất kỳ A, B, C  , ta đã áp dụng một biến đổi quen thuộc 
A \ (B \ C) = (A \ B)  (A  C)) 
Như vậy,  \ Z = R \ (L \ ( \ R)+) = (R \ L)  (R  ( \ R)+) H (7) 
Do đã có (R \ L) H (theo [1]) và R  ( \ R)+ H (theo bổ đề 2). 
Chứng tỏ Z = ( \ R)  [L \ ( \ R)+ ] là siêu khóa chứa tất cả các khóa của S. 
5. KẾT LUẬN 
Trong bài báo này, dựa trên ngữ nghĩa quen thuộc của phụ thuộc hàm trong mô 
hình cơ sở dữ liệu quan hệ, chúng tôi đã chứng minh được điều kiện cần (2) (trong 
[2, 3]) trùng với điều kiện cần (3) là một dạng cải tiến của điều kiện cần (1) (trong 
[1]). Đâ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 đồ 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 47, 02 - 2017 107
quan hệ S = . Việc tìm một điều kiện cần tốt hơn (2) hoặc (3) nhằm rút gọn 
hơn nữa bài toán tìm khóa là một vấn đề rất đáng quan tâm. 
TÀI LIỆU THAM KHẢO 
[1]. Ho Thuan and Le Van Bao, "Some results about keys of relational schemas", 
Acta Cybernetica, Tom 7, Fasc.1, Szeged, pp. 99-113, 1985. 
[2]. 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, 1860–1868, 
June 2011. 
[3]. P. Cordero, M. Enciso, A. Mora, "Automated Reasoning to Infer all Minimal 
Keys", In Proceedings of the Twenty-Third International Joint Conference on 
Artificial Intelligence, (IJCAI13), F.Rossi ed.,pp.817-823, AAAI Press, 2013. 
[4]. Ho Thuan, "Contribution to the theory of relational databases", Tanulmányok 
184/1986, Studies 184/1986, Budapest, Hungary. 
ABSTRACT 
SOME RESULTS FOR REDUCING THE KEY FINDING PROBLEM 
Let S = be a relation schema, where  = {A1, A2,..., An} is a finite 
set of attributes and F = {L1 R1,...,Lm  Rm | Li, Ri  , i = 1,...,m} is a 
finite set of functional dependencies that hold on S. In [1], using the well-
known semantics of functional dependency in the theory of relational 
databases and the algorithm to compute the closure of a subset of attributes, a 
necessary condition for which a subset X   is a minimal key for S was 
established and some improvements of it were given. In [2], basing on the 
study of idean non-deterministic operators in the framework of the lattice 
theory, the authors of [2] gave another necessary condition for which a subset 
of  is a minimal key for a relation schema S = . Thus, we have two 
results for the same problem, the first one was published in 1985 and the last 
one, in 2011, and apparently, they seem quite different. In this paper, we show 
that the necessary condition in [2] is only an improved version of that one in 
[1]. The relationship between the necessary conditions for which a subset of  
is a minimal key for the relation scheme S = and the reduction of the 
key finding problem was also showed. 
Keywords: Relational database, Relation scheme, Functional dependency, Keys for a relation scheme. 
Nhận bài ngày 18 tháng 11 năm 2016 
Hoàn thiện ngày 31 tháng 12 năm 2016 
Chấp nhận đăng ngày 20 tháng 02 năm 2017 
Địa chỉ: 1 Trường Cao đẳng Hải Dương; 
 2 Viện Công nghệ thông tin - Viện HLKH-CNVN; 
 * Email: vqtuanhd@gmail.com