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

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.” 162 
VỀ MỘT PHÉP BIẾN ĐỔI TIỀN XỬ LÝ HIỆU QUẢ 
CÁC TẬP PHỤ THUỘC HÀM 
Vũ Quốc Tuấn1*, Hồ Thuần2 
Tóm tắt: Trong [1] và [2], Ángel Mora và các cộng sự đã thiết kế một phép biến 
đổi tiền xử lý sử dụng toán tử thay thế của logic thay thế SLFD để loại bỏ dư thừa 
trong tập phụ thuộc hàm ban đầu nhằm thu được một tập phụ thuộc hàm tương 
đương với kích thước nhỏ hơn trong thời gian đa thức. Cơ sở và tính đúng đắn của 
phép biến đổi tiền xử lý này được chứng minh bởi Định lý 6 trong [1]. Trong bài 
báo này, chúng tôi sẽ chỉ ra một lỗi sai không chấp nhận được trong chứng minh 
của Định lý 6 và đưa ra một chứng minh đúng và đơn giản hơn cho định lý đó. Một 
số nhận xét về phép biến đổi tiền xử lý cũng được đưa ra. 
Từ khóa: Cơ sở dữ liệu quan hệ, Lược đồ quan hệ, Phụ thuộc hàm, Phép biến đổi tiền xử lý. 
1. MỞ ĐẦU 
Trong [1] và [2], Ángel Mora và các cộng sự đã thiết kế một phép biến đổi tiền xử lý sử 
dụng toán tử thay thế của logic thay thế SLFD để loại bỏ dư thừa trong tập phụ thuộc hàm 
ban đầu nhằm thu được một tập phụ thuộc hàm tương đương với kích thước nhỏ hơn trong 
thời gian đa thức. Cơ sở và tính đúng đắn của phép biến đổi tiền xử lý này được chứng 
minh bởi định lý 6 trong [1]. Trong bài báo này, chúng tôi sẽ chỉ ra một lỗi sai không chấp 
nhận được trong chứng minh của Định lý 6 và đưa ra một chứng minh đúng và đơn giản 
hơn cho định lý đó. Một số nhận xét về phép biến đổi tiền xử lý cũng được đưa ra. 
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ệ, giới thiệu về logic Paredaens dựa vào cách trình bày trong [2]. 
Trong phần này cũng nhắc lại định nghĩa thế nào là một tập F các phụ thuộc hàm có dư thừa, 
phát biểu lại Định lý 6 trong [1] và chỉ ra chỗ sai trong chứng minh của định lý đó. Chứng 
minh đúng của Định lý 1 được cho trong phần thứ ba cùng với một số nhận xét. Trong phần 
thứ ba cũng giới thiệu về thủ tục removeRedundancy được trình bày trong [2] với một vài cải 
tiến cùng một số ví dụ ứng dụng. Kết luận được giới thiệu trong phần thứ tư. 
2. MÔ HÌNH QUAN HỆ VÀ LOGIC PAREDAENS 
2.1. Mô hình quan hệ 
Trong mô hình quan hệ của E.F.Codd, dữ liệu được lưu trữ dưới dạng các quan hệ (các 
bảng). Mỗi quan hệ được định nghĩa trên một tập hữu hạn các thuộc tính 
 = {A1, A2,..., An}, trong đó mỗi thuộc tính Ai lấy giá trị trong một miền tương ứng 
Dom(Ai). Như vậy, một quan hệ R xác định trên  là một tập con của tích Descartes 
Dom(A1) Dom(A2) ... Dom(An). Nói cách khác, R là một tập các bộ t có dạng t = (a1, 
a2,...,an) trong đó ai Dom(Ai) với mọi i = 1, 2, ..., n. 
Cho X  , t R. Khi đó, hình chiếu của t trên X, ký hiệu t[X] là bộ sao cho t[X](ai) = 
t(ai), ai Dom(Ai) với mọi Ai X. 
Định nghĩa 1 (Phụ thuộc hàm). Cho R là một quan hệ trên . Mọi khẳng định có dạng 
X Y , trong đó, X, Y   được gọi là một phụ thuộc hàm trên R. Ta nói R thỏa X Y nếu 
với mọi t1, t2 R có t1[X] = t2[X] kéo theo t1[Y] = t2[Y]. 
Ký hiệu FDR là tập sau: 
FDR = {X Y | X, Y  , R thỏa X Y} 
Trong [3], W.W. Armstrong đã chứng minh ngữ nghĩa của phụ thuộc hàm, đặc trưng 
các tính chất thỏa mãn tập FDR, được phát biểu dưới dạng các tiên đề Armstrong dưới đây. 
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 163
Cho R là một quan hệ trên , khi đó: 
1. Nếu Y  X   thì X Y FDR 
2. Nếu X Y FDR thì X XY FDR 
3. Nếu X Y, Y Z FDR thì X Z FDR 
4. Nếu X Y, X Z FDR thì X YZ FDR 
5. Nếu X Y FDR thì X Y X FDR 
6. Nếu X Y FDR, X  U   và V  XY thì U V FDR 
7. Nếu X Y, X' Z FDR, X'  XY, X  U  A và V  ZU thì U V FDR 
2.2. Logic Paredaens 
Logic Paredaens được gọi là LPar cho phép đặc tả hình thức và thao tác các phụ thuộc 
hàm. 
Định nghĩa 2 (Ngôn ngữ Par). Cho  là tập vô hạn đếm được các nguyên tử (atoms) và 
 là một liên kết nhị phân (binary connective), ta định nghĩa ngôn ngữ: 
Par = {X Y | X, Y 2
 và X } 
Bây giờ, hệ tiên đề SPar được đưa vào như sau: 
Định nghĩa 3. LPar là logic được cho bởi cặp (Par, SPar) trong đó SPar là một lược đồ tiên 
đề AxPar : |
ParS
 X Y nếu Y  X và các quy tắc suy diễn sau: 
(Kí hiệu F |
ParS
 F’ nghĩa là tập phụ thuộc hàm F’ được suy diễn logic từ tập phụ thuộc 
hàm F theo hệ tiên đề SPar) 
 Trans X Y, Y Z |
ParS
 X Z (quy tắc bắc cầu) 
 Augm X Y |
ParS
 X XY (quy tắc gia tăng) 
Trong SPar ta có các quy tắc suy diễn sau: 
 Union X Y, X Z |
ParS
 X YZ (quy tắc hợp) 
 Comp X Y, W Z |
ParS
 XW YZ (quy tắc hợp thành) 
 Inters X Y, X Z |
ParS
 X Y Z trong đó Y Z  (quy tắc giao) 
 Reduc X Y |
ParS
 X Y Z trong đó Y Z  (quy tắc rút gọn) 
 Frag X YZ |
ParS
 X Y (quy tắc phân mảnh) 
 gAug X Y |
ParS
 U V trong đó X  U và V  XY (quy tắc gia tăng suy 
rộng) 
 gTrans X Y, Z U |
ParS
 V W trong đó Z  XY, X  V và W  UV (quy tắc 
bắc cầu suy rộng) 
Nhận xét 1. Có thể xem logic Paredaens là sự mô tả chi tiết hơn của hệ tiên đề Armstrong, 
với việc bổ sung các quy tắc hợp thành, quy tắc giao và quy tắc phân mảnh. 
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.” 164 
Nhận xét 2. Dễ thấy rằng logic Paredaens cũng như các logic khác cho phụ thuộc hàm 
([3]. [4], [5], [6]) đều có cùng cấu trúc trong cú pháp, ngữ nghĩa và hệ tiên đề và do đó 
chúng tương đương nhau. 
Nhận xét 3. Để đơn giản trong thao tác với các phụ thuộc hàm cũng như suy diễn ra các 
phụ thuộc hàm mới từ một tập các phụ thuộc hàm cho trước, ta có thể sử dụng một hệ tiên 
đề tương đương với hệ tiên đề Armstrong như đã làm trong [7] bao gồm 3 tiên đề sau với 
X, Y, Z là các tập con của : 
A1. Nếu Y  X thì X Y (quy tắc phản xạ) 
A2. Nếu X Y thì XZ YZ (quy tắc gia tăng) 
A3. Nếu X Y và Y Z thì X Z (quy tắc bắc cầu) 
với việc ngầm hiểu các quy tắc suy diễn khác là những quy tắc suy diễn dễ dàng được suy 
từ hệ tiên đề Armstrong với ba tiên đề A1, A2, A3. 
Trong phần dưới đây, ta hình thức hóa khái niệm dư thừa liên quan tới một tập F các 
phụ thuộc hàm cho trước trên . 
Định nghĩa 4. Cho F  Par và f = X Y F. 
Ta nói f là dư thừa (không cần thiết) trong F nếu F \{ f } |
ParS
 f 
Ta nói f là l-dư thừa trong F nếu tồn tại Z , Z  X sao cho 
(F \{ f })  {(X Z) Y} |
ParS
 f 
Ta nói f là r-dư thừa trong F nếu tồn tại U , U  Y sao cho 
(F \{ f })  { X (Y U)} |
ParS
 f 
Ta nói F có dư thừa nếu nó có chứa một phần tử hoặc là dư thừa hoặc là l-dư thừa hoặc 
là r-dư thứa trong F. 
Sau đây, không giảm tổng quát, ta chỉ xét các tập phụ thuộc hàm F, trong đó, các phụ 
thuộc hàm thuộc F đều có vế trái và vế phải rời nhau, có nghĩa với mọi phụ thuộc hàm 
X Y F ta có X  Y = . 
Một tập các phụ thuộc hàm có tính chất như vậy được gọi là một tập phụ thuộc hàm 
được thu gọn (reduced functional dependencies set). 
Trong [1] có phát biểu và chứng minh định lý sau: 
Định lý 1 (Định lý 6 trong [1] và là Định lý 1 trong [2]) 
Cho X Y, U V LFD với X  Y = . 
(a). Nếu X  U thì {X Y, U V} 
ParS
 {X Y, (U Y) (V Y)} (1) 
Do đó, nếu U  Y  hay V  Y =  thì U V theo thứ tự là l-dư thừa hay r-dư thừa 
trong {X Y, U V}. 
(b). Nếu X  U và X  UV thì {X Y, U V} 
ParS
 {X Y, U (V Y)} (2) 
Do đó, nếu V  Y  thì U V là r-dư thừa trong {X Y, U V}. 
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 165
(Kí hiệu F 
ParS
 F’ nghĩa là tập phụ thuộc hàm F’ tương đương với tập phụ thuộc hàm F 
theo hệ tiên đề SPar, từ F có thể suy ra F’ và ngược lại) 
Chứng minh của Định lý 1 (là Định lý 6 trong [1]) được trình bày lại đầy đủ như sau: 
Chứng minh. 
(a). 
1. X Y (giả thiết) 
2. (U Y) Y (1, gia tăng suy rộng) 
3. (U Y) (U Y) AxFD (tiên đề phản xạ) 
4. (U Y) UY (2, 3, quy tắc hợp) 
5. (U Y) U (4, gia tăng suy rộng) 
6. U V (giả thiết) 
7. (U Y) V (5, 6, bắc cầu suy rộng) 
8. (U Y) (V Y) (7, gia tăng suy rộng) 
(a).  
1. U X AxFD (tiên đề phản xạ) 
2. X Y (giả thiết) 
3. U Y (1, 2, bắc cầu suy rộng) 
4. (U Y) (V Y) (giả thiết) 
5. U VY (3, 4, quy tắc hợp) 
6. U V (2, 5, gia tăng suy rộng) 
(b). 
1. U V (giả thiết) 
2. U (V Y) (1, gia tăng suy rộng) 
(b).  
1. U X AxFD (tiên đề phản xạ) 
2. X Y (giả thiết) 
3. U Y (1, 2, bắc cầu suy rộng) 
4. U (V Y) (giả thiết) 
5. U VY (3, 4, quy tắc hợp) 
6. U V (2, 5, gia tăng suy rộng) 
Cái hay và mới của Định lý 1 là nó cho phép đưa vào hai quy tắc thay thế quan trọng 
được ký hiệu theo thứ tự là Subst và rSubst 
 Subst X Y, U V |
ParS
 (U Y) (V Y) nếu X  U, X  Y =  
 rSubst X Y, U V |
ParS
 U (V Y) nếu X  U, X  UV, X  Y =  
Rõ ràng là không có hệ tiên đề nào cho phụ thuộc hàm có những quy tắc thay thế nói 
trên, có khả năng phát hiện và loại bỏ dư thừa trong một tập phụ thuộc hàm một cách hiệu 
quả như vậy. 
Dưới đây là một số nhận xét về phần chứng minh của Định lý 1 nêu ở trên. 
Nhận xét 4. Trong chứng minh chiều , phần (a) của Định lý 1, các dòng 5. và 6. được 
viết lại là 
5. U VY (3, 4, Quy tắc hợp) 
6. U V (2, 5, Quy tắc gia tăng suy rộng) 
Rõ ràng dòng 6. phải sửa lại là 
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.” 166 
6. U V (5, Quy tắc gia tăng suy rộng) 
Nhận xét 5. Trong chứng minh chiều , phần (b) của Định lý 1, ta hãy xem dò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.