Về một phép biến đổi tiền xử lý hiệu quả các tập phụ thuộc hàm

òng 1. 
1. U  X AxFD (tiên đề phản xạ) 
Khẳng định này rõ ràng là sai vì trong phát biểu phần (b) của Định lý 1, ta có các giả 
thiết X  U, X  UV, X  Y = . 
Do đó, chiều {XY, U(V  Y)} |
ParS
 {X  Y, U  V} với các giả thiết nêu trên 
chưa được chứng minh. 
3. MỘT CHỨNG MINH MỚI CHO ĐỊNH LÝ 1 
Để đơn giản cách chứng minh Định lý 1, ta sử dụng hệ ba tiên đề tương đương với hệ 
tiên đề Armstrong với X, Y, Z  , trong đó,  là vũ trụ các thuộc tính. 
A1. Nếu Y  X thì X  Y (Tiên đề phản xạ) 
A2. Nếu X  Y thì XZ  YZ (Tiên đề gia tăng) 
A3. Nếu X  Y và Y  Z thì X  Z (Tiên đề bắc cầu) 
cùng với các quy tắc suy diễn quen thuộc, dễ dàng được suy ra từ hệ ba tiên đề A1, A2, A3 
như: 
Nếu X  Y và U  V thì XU  YV (Quy tắc hợp) 
Nếu X  Y thì X  Z với mọi Z  Y (Quy tắc tách hay phân mảnh) 
Sau đây là một chứng minh mới cho Định lý 1. 
Trước hết, Định lý 1 được phát biểu lại như sau: 
(a). Nếu X  U , X  Y =  thì hai tập phụ thuộc hàm 
{XY, UV}  {X  Y, (U  Y)  (V  Y)} 
trong đó,  là tương đương theo nghĩa sử dụng hệ quy tắc suy diễn Armstrong, hệ phụ 
thuộc hàm thứ nhất có thể suy ra hệ phụ thuộc hàm thứ hai và ngược lại. 
(b). Nếu X  U, X  UV thì 
{XY, UV}  {X  Y, U  (V  Y} 
Chứng minh. 
(a).  
Vì X  U nên X  Y  U  Y . Vì X  Y =  nên X  Y = X  U  Y . Từ đó ta có dãy 
suy diễn sau: 
1. (U  Y)  X (A1) 
2. XY (Giả thiết) 
3. (U  Y)  Y (1, 2, A3) 
4. (U  Y)  (U Y) (A1) 
5. (U  Y)  UY (3, 4, Quy tắc hợp) 
6. (U  Y)  U (5, Quy tắc tách) 
7. U  V (Giả thiết) 
8. (U  Y)  V (6, 7, A3) 
9. (U  Y)  (V  Y) (8, Quy tắc tách do (V  Y)  V) 
(a).  
1. XY (Giả thiết) 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 50, 08 - 2017 167
2. (U  Y)  (V  Y) (Giả thiết) 
3. U  X (A1, vì X  U) 
4. U  Y (3, 1, A3) 
5. U  VY (2, 4, Quy tắc hợp) 
6. U  V (5, Quy tắc tách) 
(b).  
1. U  V (Giả thiết) 
2. U  (V  Y) (1, Quy tắc tách) 
(b).  
1. XY (Giả thiết) 
2. U  (V  Y) (Giả thiết) 
3. U  U(V  Y) (2, A2) 
4. U(V  Y)  (UV  Y) (A1) 
do có U  (V  Y)  (U  Y)  (V  Y) và (U  Y)  (V  Y) = UV  Y 
5. U  (UV  Y) (3, 4, A3) 
6. (UV  Y)  X (A1) 
do có X  UV và X  Y =  nên X = (X  Y)  UV  Y 
7. (UV  Y)  Y (6, 1, A3) 
8. U  Y (5, 7, A3) 
9. U  UVY (5, 8, A2) 
10. U  V (9, Quy tắc tách) 
Nhận xét 6. Trong chứng minh mới của Định lý 1, việc chứng minh phần (a) về cơ bản là 
giống với chứng minh phần (a) trong [1]. Cái khác nhau là ở chỗ cách thức giải thích các 
bước suy diễn. Trong [1], các tác giả dùng các tiên đề và các quy tắc suy diễn trong logic 
Paredaens, còn trong chứng minh mới, chúng tôi sử dụng hệ tiên đề quen thuộc của 
Armstrong, nên việc giải thích các bước suy diễn là đơn giản, rõ ràng hơn. 
Để khắc phục lỗi sai trong chứng minh phần (b) của Định lý 1 trong [1], chứng minh 
phần (b) của chúng tôi ở đây là hoàn toàn mới. Nó khiến cho Định lý 1 trong [1], một Định 
lý rất hay, là nền tảng cho phép biến đổi tiền xử lý loại bỏ hiệu quả các dư thừa trong một 
tập phụ thuộc hàm cho trước, đứng vững và sử dụng được. 
Nhận xét 7. Trong thực hành, trong nhiều trường hợp, để đơn giản hơn, ta có thể dùng quy 
tắc thay thế sau: 
Cho hệ hai phụ thuộc hàm {XY, UV}. Nếu X  U, X  V và X  Y =  thì, do 
tương đương, có thể thay thế {XY, UV} bằng hệ hai phụ thuộc hàm {XY, U(V  
Y)} nói chung đơn giản hơn. Nói cách khác, nếu X  U, X  V và X  Y =  thì 
{X  Y, U  V}  {X  Y, U  (V  Y)} (3) 
Điều này hiển nhiên đúng vì nếu X  U, X  V và X  Y =  thì đương nhiên X  U, 
X  UV và X  Y =  và ta rơi vào trường hợp (b) của Định lý 1. 
Nhận xét 8. Trên cơ sở các phép thay thế (1), (2), (3), ta có thể làm đơn giản hơn thủ tục 
removeRedundancy trong [1] bằng thủ tục Loại bỏ dư thừa cho các tập phụ thuộc hàm F 
ở dạng thu gọn gồm các bước sau: 
Procedure Loại bỏ dư thừa 
Input: F (Một tập phụ thuộc hàm ở dạng thu gọn) 
Công nghệ thông tin & Cơ sở toán học cho tin học 
V. Q. Tuấn, H. Thuần, “Về một phép biến đổi tiền xử lý hiệu quả các tập phụ thuộc hàm.” 168 
Output: F' (Một tập phụ thuộc hàm tương đương với F với dư thừa ít hơn) 
Begin 
Repeat 
B1. Thực hiện các phép hợp cho các phụ thuộc hàm có cùng vế trái; 
B2. Thực hiện các phép thay thế (1), (2), (3); 
Until (không thực hiện các thao tác B1 và B2 thêm được nữa); 
B3. Kiểm tra xem trong tập phụ thuộc hàm thu được, có phụ thuộc hàm nào được 
suy ra từ hai phụ thuộc hàm khác từ việc áp dụng (A3). Nếu có thì loại bỏ nó. 
End; 
Nhận xét 9. Trong [1] và [2], các tác giả đã cho chạy thủ tục removeRedundancy trên 
nhiều tập phụ thuộc hàm với số lượng và kích thước khác nhau và đã thấy rằng tỷ lệ phần 
trăm số lần áp dụng các quy tắc thay thế là rất cao và tăng đáng kể với độ phức tạp của các 
tập phụ thuộc hàm. 
Ngoài ra, các tác giả của [1] và [2] đã rút ra các kết luận tổng quát sau: 
- Đối với 28,25% các tập phụ thuộc hàm, không cần thiết áp dụng quy tắc bắc cầu (A3) 
và phép biến đổi tiền xử lý loại bỏ dư thừa một cách hiệu quả. 
- Kích thước của các tập phụ thuộc hàm được rút gọn tới 52,89% 
- Khi số các thuộc tính tăng lên thì số trường hợp trong đó không cần áp dụng quy tắc 
bắc cầu (A3) cũng tăng lên. Điều này chứng tỏ quy tắc thay thế đặc biệt thích hợp để làm 
việc với các lược đồ cơ sở dữ liệu lớn. 
- Số phần trăm các áp dụng của quy tắc thay thế không phụ thuộc vào số thuộc tính và 
độ dài của phụ thuộc hàm. 
Nhận xét 10. Để thấy được ý nghĩa và ưu việt của các quy tắc thay thế (tức phép biến đổi 
tiền xử lý các tập phụ thuộc hàm), ta xét hai ví dụ sau, trong đó, ví dụ 1 được lấy lại từ ví 
dụ 1 trong [2] với việc chỉnh sửa lại một sai sót nhỏ. 
Ví dụ 1 ([2]). Cho F = {abc, abce, bdac, afb, cdba}. Ta có thể áp dụng các 
phép thay thế để thu được một tập phụ thuộc hàm với dư thừa ít hơn. 
Như vậy, sau khi thực hiện phép biến đổi tiền xử lý, ta thu được tập F' tương đương với 
F nhưng chứa ít dư thừa hơn. 
F' = {abce, bda, cdb}. 
Ví dụ 2. Áp dụng các phép thay thế đối với tập phụ thuộc hàm F = {ba, bgh, da, 
bih, abde, abfg, abcdj, abck}. 
Quy tắc áp dụng F 
Quy tắc hợp: 
ba, bgh |
ParS
 bagh 
bagh, da, bih, abde, 
abfg, abcdj, abck 
Quy tắc hợp: 
abde, abfg |
ParS
 abdefg 
bagh, da, bih, abdefg, 
abcdj, abck 
Quy tắc hợp: 
abcdj, abck |
ParS
 abcdjkh 
bagh, da, bih, abdefg, 
abcdjk 
Subst: bagh, da, bi, abdefg, 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 50, 08 - 2017 169
bagh, bih |
ParS
 bi abcdjk 
A1: 
|
ParS
 bi (sẽ được loại bỏ) bagh, da, abdefg, abcdjk 
Subst: 
bagh, abdefg |
ParS
 bdef bagh, da, bdef, abcdjk 
Quy tắc hợp: 
bagh, bdef |
ParS
 badefgh badefgh, da, abcdjk 
Subst: 
badefgh, abcdjk |
ParS
 bcjk badefgh, da, bcjk 
rSubst: 
da, badefgh |
ParS
 bdefgh bdefgh, da, bcjk 
Như vậy, cuối cùng ta thu được tập F' = {bdefgh, da, bcjk} tương đương với F 
nhưng chứa ít dư thừa hơn. 
4. KẾT LUẬN 
Phép biến đổi tiền xử lý để loại bỏ dư thừa trong các tập phụ thuộc hàm được trình bày 
trong [1] và [2] là mới và tỏ ra rất hiệu quả. Cơ sở của phép biến đổi tiền xử lý này là Định 
lý 1 (trong [1]) và cũng là Định lý 6 (trong [2]). 
Đáng tiếc là chứng minh phần (b) của Định lý 1 là sai và không chấp nhận được. Trong 
bài báo này, chúng tôi đã đưa ra một chứng minh mới cho Định lý 1, cũng như đưa ra một 
quy tắc thay thế mới đơn giản và dễ áp dụng trong thực hành. Điều này khiến cho Định lý 
1 ([1], [2]) đứng vững và áp dụng được. 
Xây dựng thêm các quy tắc thay thế mới cho việc tiền xử lý các tập phụ thuộc hàm 
cũng là một hướng nghiên cứu đáng quan tâm. 
TÀI LIỆU THAM KHẢO 
[1]. P. Cordero et al., "SLFD Logic: Elimination of data redundancy in Knowledge 
Representation", Advances in Artificial Intelligence, IBERAMIA 2002, LNAI 2527, 
pp.141-150, 2002. 
[2]. Ángel Mora et al., "An Efficient Preprocessing Transformation for Functional 
Dependencies Sets Based on the Substitution Paradigm", R. Conejo et al. (Eds.): 
CAEPIA - TTIA 2003, LNAI 3040, pp. 136-146, 2004. 
[3]. P. Atzeni and V.D.Antonellis, "Relational Database Theory", The 
Benjamin/Cummings Publishing Company Inc, 1993. 
[4]. R. Fagin, "Functional dependencies in a Relational Database and Propositional 
Logic", IBM Journal of Research and Development 21(6), pp. 534-544, 1977. 
[5]. T. Ibaraki et al, "Functional dependencies in Horn theories", Artificial Intelligence 
108(1-2), pp. 1-30, 1999. 
[6]. J. D. Ullman, "Database and Knowledge-base Systems", Computer Science Press, 
1988. 
[7]. Ho Thuan and Le Van Bao, "Some results about keys of relational schemas", Acta 
Cybernetica, Tom 7, Fasc. 1, Szeged, pp. 99-113, 1985. 
Công nghệ thông tin & Cơ sở toán học cho tin học 
V. Q. Tuấn, H. Thuần, “Về một phép biến đổi tiền xử lý hiệu quả các tập phụ thuộc hàm.” 170 
ABSTRACT 
ABOUT AN EFFICIENT PREPROCESSING TRANSFORMATION FOR 
FUNCTIONAL DEPENDENCIES SETS 
In [1] and [2], Ángel Mora et al designed a preprocessing transformation using 
the substitution paradigm of SLFD logic to eliminate data redundancy in a given set 
of functional dependencies in order to obtain an equivalent set of functional 
dependencies with a smaller size in polynomial time. The basis and correctness of 
this preprocessing transformation have been proved by Theorem 6 in [1]. In this 
paper, we show a serious error in the proof of Theorem 6 and give a simpler and 
correct proof for that theorem. Some remarks about the preprocessing 
transformation are also given. 
Keywords: Relational database, Relation schema, Functional dependency, Preprocessing transformation. 
Nhận bài ngày 01 tháng 6 năm 2017 
Hoàn thiện ngày 24 tháng 7 năm 2017 
Chấp nhận đăng ngày 18 tháng 8 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.