Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Bài viết phát biểu và chứng minh một số tính chất của khối dữ liệu khi thể hiện tập các phụ thuộc hàm trong mô hình dữ liệu dạng khối. Điều kiện cần và đủ để hai tập phụ thuộc hàm trên lược đồ khối là tương đương, tính chất của hai tập phụ thuộc hàm tương đương trên khối dữ liệu. Tính chất của mối tương quan giữa các thể hiện trên khối cũng được phát biểu và chứng minh . | Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin FAIR Nha Trang ngày 8-9 10 2020 DOI 10.15625 vap.2020.00231 VỀ VẤN ĐỀ THỂ HIỆN TẬP PHỤ THUỘC HÀM CỦA KHỐI DỮ LIỆU TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI Trịnh Đình Thắng1 Trần Minh Tuyến2 1 Đại học Sư phạm Hà Nội 2 2 Đại học Công đoàn thangdhsp2@hpu2.edu.vn tuyentm@dhcd.edu.vn TÓM TẮT Bài báo phát biểu và chứng minh một số tính chất của khối dữ liệu khi thể hiện tập các phụ thuộc hàm trong mô hình dữ liệu dạng khối. Điều kiện cần và đủ đẻ hai tập phụ thuộc hàm trên lược đồ khối là tương đương tính chất của hai tập phụ thuộc hàm tương đương trên khối dữ liệu. Tính chất của mối tương quan giữa các thể hiện trên khối cũng được phát biểu và chứng minh. Ngoài ra thuật toán làm đóng khối trị của khối dữ liệu đối với phép nhân các phần tử và độ phức tạp của nó cũng đã được trình bày và chứng minh tính đúng ở đây. Từ khóa Thể hiện tập phụ thuộc hàmn công thức Boolean khối chân lý lược đồ khối. I. MÔ HÌNH DỮ LIỆU DẠNG KHỐI A. Khối lược đồ khối Định nghĩa I.1 1 Gọi R id A1 A2 . An là một bộ hữu hạn các phần tử trong đó id là tập chỉ số hữu hạn khác rỗng Ai i 1 n là các thuộc tính. Mỗi thuộc tính Ai i 1.n có miền giá trị tương ứng là dom Ai . Một khối r trên R kí hiệu r R gồm một số hữu hạn phần tử mà mỗi phần tử là một họ các ánh xạ từ tập chỉ số id đến các miền trị của các thuộc tính Ai i 1.n . Nói một cách khác t r R t ti id dom Ai i 1.n . Ta kí hiệu khối đó là r R hoặc r id A1 A2 . An đôi khi nếu không gây nhầm lẫn ta kí hiệu đơn giản là r. Định nghĩa I.2 1 Cho R id A1 A2 . An r R là một khối trên R. Với mỗi x id ta kí hiệu r Rx là một khối với Rx x A1 A2 . An sao cho tx r Rx tx tix ti i 1.n ở đây t r R t ti id dom Ai i 1.n x Khi đó r Rx được gọi là một lát cắt trên khối r R tại điểm x. B. Phụ thuộc hàm Sau đây để cho đơn giản ta sử dụng các kí hiệu x i x Ai id i x i x id . Ta gọi x i x id i 1.n là các thuộc tính chỉ số của lược đồ khối R id A1 A2 . An . Định nghĩa I.3 1 n Cho R id .
