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ệ

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 157
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Ệ 
Vũ Quốc Tuấn1*, Hồ Thuần2 
Tóm tắt: Trong [1] đã đưa ra một điều kiện cần để một tập thuộc tính là khóa 
của lược đồ quan hệ. Trong [2], các tác giả cũng đưa ra một điều kiện cần khác để 
một tập thuộc tính là khóa của lược đồ quan hệ. Trong [3] đã chỉ ra rằng chỉ cần 
cải tiến điều kiện cần trong [1] theo một cách tiếp cận đơn giản hơn thì có thể suy 
ra được điều kiện cần trong [2]. 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] thực sự là trùng với kết quả đã được công bố trong [4]. 
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 [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 là khóa. 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 (ideal 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. Trong [3] đã chỉ ra 
rằng chỉ cần cải tiến điều kiện cần trong [1] theo một cách tiếp cận khác đơn giản 
hơn thì có thể suy ra được điều kiện cần trong [2]. 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] thực sự là trùng với kết quả đã được công 
bố trong [4]. 
Bài báo được tổ chức như sau: phần thứ hai nhắc lại một số khái niệm và kết 
quả quan trọng của mô hình quan hệ. Phần thứ ba trình bày lại một số kết quả và 
nhận xét trong [1, 2, 3, 4] để tiện so sánh, đồng thời chứng minh điều kiện cần 
trong [2] trùng với kết quả trong [4]. Kết luận được giới thiệu trong phần thứ tư. 
2. MÔ HÌNH QUAN HỆ 
Phần này nhắc lại một số khái niệm quan trọng trong mô hình dữ liệu quan hệ 
nhằm mục đích sử dụng cho các phần tiếp theo. 
2.1. Lược đồ quan hệ 
Lược đồ quan hệ. Một lược đồ quan hệ S là một cặp có thứ tự S = , 
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 = 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 = . 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. 
2.2. Phụ thuộc hàm 
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ý 
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ệ.” 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.