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