Một số kết quả liên quan đến rút gọn bài toán tìm khóa của lược đồ quan hệ

 Tuấn, H. Thuần, “Một số kết quả liên quan  tìm khóa của lược đồ quan hệ.” 158 
hiệu là X  Y, nếu với mọi quan hệ r trên lược đồ S() và 
 t1, t2  r, t1[X] = t2[X]  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 
 t1, t2  r, t1[X] = t2[X]  t1[Y] = t2[Y] 
Trong bài báo này, ta hạn chế F (của lược đồ S = ) chỉ gồm các phụ 
thuộc hàm. 
2.3. Hệ quy tắc suy diễn Armstrong 
Hệ quy tắc suy diễn Armstrong. Với lược đồ quan hệ S = 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 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. 
2.4. Bao đóng của một tập thuộc tính 
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 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à FX , 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. 

FX = {A    (X  A)  F
+}. 
2.5. Khóa của lược đồ quan hệ 
Khóa của lược đồ quan hệ. Cho lược đồ quan hệ S = 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+. 
Nếu K thỏa mãn điều kiện (i) thì K được gọi là một siêu khóa. Như vậy, mọi khóa 
của S = đều là siêu khóa của S = . 
3. MỘT SỐ KẾT QUẢ 
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

 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 54, 04 - 2018 159
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. 
3.1. Một số kết quả đã biết 
Định lý 1 (Định lý 1 trong [1]). Cho S = là một lược đồ quan hệ và K là 
một khóa của S. Khi đó: 
( \ R)  K  ( \ R)  (L  R) (1) 
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. Thêm vào 
đó, nếu ( \ R)  (L  R)   thì 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 'S 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). 
Định lý 2 (Định lý 2 trong [4]). Cho S = là một lược đồ quan hệ và K là 
một khóa của S. Khi đó: 
( \ R)  K  ( \ R)  [(L  R) \ ( \ R)+] (2) 
Dễ thấy rằng (2) là một dạng cải tiến của (1). Ví dụ 1 sau đây cho thấy 
[(L  R) \ ( \ R)+]  (L  R) 
Ví dụ 1 (Ví dụ trong [4]). Cho S = là một lược đồ quan hệ, trong đó tập 
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ả liên quan  tìm khóa của lược đồ quan hệ.” 160 
thuộc tính  = {a, b, c, g, h} và tập phụ thuộc hàm 
F = {a  b, b  c, g  h, h g}. 
Ta có: 
L = abgh 
R = bcgh 
 \ R = a 
( \ R)+ = abc 
(L  R) = bgh 
(L  R) \ ( \ R)+ = gh  (L  R) 
Mệnh đề 1 (Trong chứng minh của Định lý 2 trong [4]). Cho S = là một 
lược đồ quan hệ. Khi đó 
( \ R)+ \ ( \ R)  H , 
có nghĩa các thuộc tính trong ( \ R)+ \ ( \ R) đều là các thuộc tính không khóa. 
Nhận xét 4. Ở đây để dễ theo dõi, chúng tôi trình bày chi tiết hơn cách thức suy ra 
(2) từ (1). Thật vậy, từ (1) và kết quả trong mệnh đề 1, ta có: 
( \ R)  K  ( \ R)  [(L  R) \ [( \ R)+ \ ( \ R)]] (a) 
Sử dụng hệ thức quen thuộc giữa ba tập hợp A, B, C bất kỳ 
A \ (B \ C) = (A \ B)  (A  C) 
ta suy ra 
[(L  R) \ [( \ R)+ \ ( \ R)]] 
= [(L  R) \ ( \ R)+]  [(L  R)  ( \ R)] 
= [(L  R) \ ( \ R)+] vì [(L  R)  ( \ R)] =  (b) 
Kết hợp (a) và (b) ta nhận được (2). 
Trong [2, 5], 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 (Định nghĩa 3.3 trong [5]). 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
 
     
 
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 
body(, F) = L  [ \ ( \ R)+] 
Ví dụ 2 (Ví dụ 3.1 trong [5]). 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}. 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 54, 04 - 2018 161
Ta có: 
L = abcefgh 
R = cdefgh 
 \ R = ab 
( \ R)+ = abcdgh 
L  [  \ ( \ R)+] = ef 
Từ đó: 
core(, F) = ab 
body(, F) = ef. 
Định lý 3 (Định lý 3.4 trong [2, 5]). 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)+] ] (3) 
Mệnh đề 2 (Nhận xét 4 trong [3]). Cho S = là một lược đồ quan hệ. 
Khi đó 
L  [ \ ( \ R)+ ] = L \ ( \ R)+ 
3.2. So sánh hai điều kiện cần (2) và (3) 
Rõ ràng (2) và (3) đều là các điều kiện cần để một tập thuộc tính là khóa của 
lược đồ quan hệ. Điều kiện (2) được công bố năm 1996, trong khi điều kiện (3) 
được công bố năm 2011. Định lý sau chỉ rõ mối quan hệ giữa (2) và (3). 
Định lý 4. 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. Từ kết quả trong mệnh đề 2, điều kiện cần (3) được viết lại thành: 
 \ R  K  ( \ R)  [L \ ( \ R)+] 
Để chứng minh (2) và (3) chỉ là một, ta sẽ chỉ ra rằng 
[(L  R) \ ( \ R)+] = [L \ ( \ R)+] 
Thật vậy, rõ ràng ta có (L  R)  L nên 
[(L  R) \ ( \ R)+]  [L \ ( \ R)+] 
Ta chỉ cần chứng minh điều ngược lại là 
 L \ ( \ R)+  (L  R) \ ( \ R)+ 
Giả sử x là một thuộc tính bất kỳ thuộc [L \ ( \ R)+] 
 x  L, x  ( \ R)+ 
 x  L, x  ( \ R), x  ( \ R)+ 
 x  L, x  R, x  ( \ R)+ 
 x  (L  R) \ ( \ R)+. 
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ả liên quan  tìm khóa của lược đồ quan hệ.” 162 
4. KẾT LUẬN 
Trong bài báo này, với việc rút gọn bài toán tìm khóa, chúng tôi đã trình bày chi 
tiết hơn cách thức suy ra (2) từ (1), đồng thời đã chứng minh được điều kiện cần 
(2) trùng với điều kiện cần (3). Đây là những điều kiện cần để một tập con của  là 
khóa của lược đồ 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]. Vũ Quốc Tuấn và Hồ thuần, "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ệ", Kỷ yếu Hội thảo Quốc gia lần 
thứ XX, Một số vấn đề chọn lọc của CNTT và TT, Quy Nhơn-Bình Định 23-
24/11/2017, tr.174-180. 
[4]. Ho Thuan, Souafi Souad and Mohamed Benkada Djamila, "Some more 
properties and remarks about keys for relation scheme", Tạp chí Tin học và 
Điều khiển học, T.12, S.4 (1996) (101-113). 
[5] 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, (IJCAI13), F.Rossi ed.,pp.817-823, 
AAAI Press, 2013. 
ABSTRACT 
SOME RESULTS RELATED TO REDUCING 
THE KEY FINDING PROBLEM OF A RELATION SCHEMA 
In [1], it has proposed a necessary condition for a set of attributes to be a 
key of a relation schema. In [2], A. Mora et al. have proposed another 
necessary condition for a set of attributes to be a key of a relation schema. In 
[3], it has been shown that we could get the necessary condition in [2] by 
improving the necessary condition in [1] in a simpler approach. In this paper, 
we will prove that the necessary condition in [2] actually coincides with the 
result published in [4]. 
Keywords: Relational database, Relation schema, Functional dependency, Key for a relation schema. 
Nhận bài ngày 18 tháng 11 năm 2017 
Hoàn thiện ngày 31 tháng 12 năm 2017 
Chấp nhận đăng ngày 10 tháng 4 năm 2018 
Đị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.