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

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.” 102 
MỘT SỐ KẾT QUẢ VỀ RÚT GỌN BÀI TOÁN TÌM KHÓA 
Vũ Quốc Tuấn1*, Hồ Thuần2 
Tóm tắt: Cho S = 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. Trong [1], 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 X   là khóa (theo nghĩa tối tiểu) 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 [2], dựa 
trên việc nghiên cứu các toán tử iđêan không tất định (idean non-deterministic 
operators) trong khuôn khổ của lý thuyết dàn, các tác giả của [2] 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 bài báo này, chúng tôi sẽ chứng minh rằng điều kiện cần trong [2] 
chính là một dạng cải tiến của điều kiện cần trong [1]. 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. 
Từ khóa: Cơ sở dữ liệu quan hệ, Lược đồ quan hệ, Phụ thuộc hàm, Khóa của lược đồ quan hệ. 
1. MỞ ĐẦU 
Trong mục này, một số kết quả trong [1] và [2] đượ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 tiểu. 
Cho S = 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: 
1
m
i
i
L L
  , 
1
m
i
i
R R
  , S là tập tất cả các khóa của S, S = {Kj | Kj là 
khóa của S}, 
j S
j
K
G K
 

là giao của tất cả các khóa của S, 
j S
j
K
H K
 

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 [1] đã chứng minh các kết quả sau: 
Định lý 1 (Định lý 1 trong [1]). Cho S = là một lược đồ quan hệ và X là 
một khóa của S. Khi đó: 
  \ R  X  ( \ R)  (L  R) (1) 
Định lý 2 (Định lý 4 trong [1]). Cho S = là một lược đồ quan hệ. Khi đó 
G =  \ R. 
Mệnh đề 1 (Trong chứng minh của Định lý 1 trong [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ừ (1), ta dễ dàng suy ra: 
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)  (L  R)  (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 đó, 
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 103
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 = . 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' = , trong đó, ' = Z \ ( \ R) và 
 F' = {Li  ' Ri  ' | (Li Ri) F, i = 1, 2,..., m}. 
2) Tìm 'SK theo một thuật toán nào đó. 
3) Dễ thấy rằng S = {( \ R)  K | K 'S }. 
Nhận xét 2. Các khóa j SK  không chứa nhau và có cấu trúc chung là jK = ( \ 
R)  jZ với jZ  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). 
Khi đó: ( \ R)  jK  ( \ R)  [(L  R) \ Z],  j SK  
sẽ là một dạng cải tiến của điều kiện cần (1). 
Trong [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