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

Bài viết 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.
Nội dung trích xuất từ tài liệu:
Về một phép biến đổi tiền xử lý hiệu quả các tập phụ thuộc hàmCông nghệ thông tin & Cơ sở toán học cho tin học 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àmban đầ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 trongthờ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ứngminh 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ấpnhận được trong chứng minh của Định lý 6 và đưa ra một chứng minh đúng và đơn giảnhơ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ả quantrọ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ứngminh đú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ầnthứ 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ảitiế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 PAREDAENS2.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ácbả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 ứngDom(Ai). Như vậy, một quan hệ R xác định trên  là một tập con của tích DescartesDom(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ạngX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ếuvớ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ưngcá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.162 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.”Nghiên cứu khoa học công nghệ 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  FDR2.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ộchà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: |SPar XY nếu Y  X và các quy tắc suy diễn sau:(Kí hiệu F |SPar F’ nghĩa là tập phụ thuộc hàm F’ được suy diễn logic từ tập phụ thuộchàm F theo hệ tiên đề SPar)Trans XY, Y Z |S XZ (quy tắc bắc cầu) ParAugmXY |SPar 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 |S XYZ (quy tắc hợp) ParComp XY, W Z |SPar XWYZ (quy tắc hợp thành)Inters XY, X Z |SPar XY Z trong đó Y Z   (quy tắc giao)Reduc XY |SPar XY Z trong đó Y Z   (quy tắc rút gọn)Frag XYZ |SPar XY (quy tắc phân mảnh)gAug XY |SPar UV trong đó X  U và V  XY (quy tắc gia tăng suyrộng)gTrans XY, Z U |SPar VW trong đó Z  XY, X  V và W  UV (quy tắcbắ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.Tạp chí Nghiên cứu KH&CN quân sự, Số 50, 08 - 2017 163 Công nghệ thông tin & Cơ sở toán học cho tin họcNhậ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 ...