Thuật toán xác định bao đóng và khóa theo tiếp cận hợp giải trong lớp các phụ thuộc logic

Bài viết trình bày các thuật toán tìm bao đóng và khóa theo tiếp cận của phép hợp giải trong logic hình thức, một số hƣớng nghiên cứu của các nhóm tác giả về các loại phụ thuộc logic trong cơ sở dữ liệu, đề xuất thuật toán tìm khóa và tìm bao đóng trong lớp các phụ thuộc logic dựa trên thuật toán hợp giải.
Nội dung trích xuất từ tài liệu:
Thuật toán xác định bao đóng và khóa theo tiếp cận hợp giải trong lớp các phụ thuộc logic Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 16 (36), tháng 12/2016 Thuật toán xác định bao đóng và khóa theo tiếp cận hợp giải trong lớp các phụ thuộc logic Unification Algorithms for Closures and Keys in Relation Schemas with Class of Logic Dependencies Trƣơng Thị Thu Hà, Nguyễn Thị Vân, Nguyễn Xuân Huy Abstract: The algorithms for closures and keys in đó về phụ thuộc Boole dƣơng. Phần 4 là một số hƣớng relation schemas with functional dependencies are nghiên cứu của các nhóm tác giả về các loại phụ thuộc well-known in theory of relational databases. logic trong cơ sở dữ liệu. Phần 5 đề xuất thuật toán tìm However, the problems of closures and keys in khóa và tìm bao đóng trong lớp các phụ thuộc logic relation schemas with positive Boolean dependencies dựa trên thuật toán hợp giải. Phần 6 là kết luận của bài are still opened. This paper proposes a solution to báo. these problems. The results are presented by unification method which is a new technique to II. CÔNG THỨC BOOLE DƢƠNG construct the basic algorithms for logic dependencies Cho U = {x1,..., xn} là tập hữu hạn các biến Boole in data and knowledge bases. nhận giá trị trong tập B = {0, 1}. Tập các công thức Keywords: Positive Boolean dependencies, Boole (CTB), kí hiệu L(U), bao gồm các biểu thức unification algorithm, membership problem, key đƣợc xây dựng từ các biến trong U, các hằng 0/1 và algorithm, closure algorithm. các phép toán logic , , , . Mỗi vector 0/1, v = (v1,...,vn) trong không gian Bn đƣợc gọi là phép gán trị. I. GIỚI THIỆU Khi đó với mỗi CTB f  L(U), f(v) là trị của công Khóa của lƣợc đồ quan hệ là tập tối thiểu các thuộc thức f đối với phép gán trị v. Kí hiệu e là phép gán trị tính nhằm xác định đơn trị một bộ trong cơ sở dữ liệu đơn vị, e = (1,1,...,1). Công thức f  L(U) gọi là công quan hệ. Khóa giữ vai trò quan trọng trong các bài thức Boole dương (CTBD) nếu f(e) = 1. toán tìm kiếm và suy dẫn. Chính vì vậy mà bài toán Ký hiệu P(U) là tập các công thức Boole dƣơng tìm khóa luôn đƣợc đề cập nhƣ một đối tƣợng cơ bản trên U. Với mỗi công thức Boole f  L(U), kí hiệu Tf = trong nghiên cứu về các loại phụ thuộc nhƣ phụ thuộc {v  Bn | f(v) = 1} là bảng chân lí của f. Mỗi tập công hàm, phụ thuộc đa trị, phụ thuộc sai khác [12, 13, 14], thức F  L(U) đƣợc hiểu là một hội logic của các công v.v.. Khái niệm khóa lại đƣợc dẫn xuất từ khái niệm thức thành phần, {f | f  F}. Khi đó, TF =  {Tf | f  bao đóng của một tập thuộc tính. Do đó bài toán tìm F} là bảng chân lí của tập công thức F. Ta đã biết f  bao đóng và tìm khóa trong lƣợc đồ quan hệ có trang g (F  g) khi và chỉ khi Tf  Tg (TF  Tg). bị phụ thuộc Boole dƣơng và phụ thuộc Boole dƣơng Theo qui ƣớc của lí thuyết cơ sở dữ liệu và tri thức, tổng quát [10, 11, 14] đang là vấn đề mở. Bài báo này dấu phép hội thƣờng đƣợc bỏ qua, giống nhƣ phép nhân trong đại số, dấu phép tuyển có thể đƣợc viết là trình bày các thuật toán tìm bao đóng và khóa theo tiếp “+”, dấu phép phủ định “” đƣợc thay bằng “’”. Tập cận của phép hợp giải trong logic hình thức [1]. các thuộc tính (biến logic) đƣợc viết liền nhau nhƣ Sau phần giới thiệu của bài báo, phần 2 và 3 trình một dãy kí tự. bày vắn tắt các khái niệm và kết quả nghiên cứu trƣớc -50- Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 16 (36), tháng 12/2016 III. PHÉP SÁNH TRỊ dữ liệu ngƣợc nhau, phục hồi dữ liệu, loại bỏ dữ liệu Ta quy ƣớc mỗi miền trị dx của biến x trong U có trùng lặp…[4, 16, 17]. chứa ít nhất hai phần tử. Với mỗi miền trị dx, xét ánh Phụ thuộc hàm có điều kiện [2, 3, 5]. Phụ thuộc hàm xạ x: dx  dx  B thoả ba tính chất sau [11, 14]: có điều kiện là mở rộng các phụ thuộc hàm bằng cách a, b  dx củng cố các mẫu của các hằng số có quan hệ về ngữ nghĩa. Các phụ thuộc hàm có điều kiện đã đƣợc chứng  x(a, a) = 1 minh là hiệu quả hơn so với phụ thuộc hàm trong việc  x(a, b) = x(b, a) phát hiện và sửa chữa các điểm không nhất quán (tình  c  dx: x(a, c) = 0 trạng không sạch) của dữ liệu. x chính là quan hệ (hai ngôi) bộ phận thực sự, Một phụ thuộc hàm có điều kiện  trên quan hệ r là thoả các tính chất phản xạ và đối xứng trên miền trị dx. một cặp (X  x, TP) thỏa mãn: Việc xác định x đƣợc hiểu là thiết lập một phép sánh  X  U và x  U, với U là tập các thuộc tính trị trên miền trị dx cho x.  X  x là một phụ thuộc hàm Quan hệ bằng =x đƣợc định nghĩa:  a, b  dx:  TP là tập bộ mẫu trong X và x tƣơng ứng. =x(a, b) = 1, khi và chỉ khi a = b là trƣờng hợp riêng Phụ thuộc hàm mềm [8]. Ilyas nghiên cứu phụ thuộc của phép sánh trị và đƣợc ngầm định trong trƣờng hợp hàm mềm với các giá trị của thuộc tính đƣợc dự đoán không định nghĩa tƣờng minh phép ...