Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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. | 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Ề 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