intTypePromotion=1

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

Chia sẻ: ViTomato2711 ViTomato2711 | Ngày: | Loại File: PDF | Số trang:8

0
24
lượt xem
0
download

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

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:
Lưu

Nội dung Text: 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<br /> <br /> <br /> Thuật toán xác định bao đóng và khóa theo tiếp<br /> cận hợp giải trong lớp các phụ thuộc logic<br /> Unification Algorithms for Closures and Keys in Relation Schemas<br /> with Class of Logic Dependencies<br /> Trƣơng Thị Thu Hà, Nguyễn Thị Vân, Nguyễn Xuân Huy<br /> <br /> Abstract: The algorithms for closures and keys in đó về phụ thuộc Boole dƣơng. Phần 4 là một số hƣớng<br /> 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<br /> 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<br /> However, the problems of closures and keys in khóa và tìm bao đóng trong lớp các phụ thuộc logic<br /> 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<br /> are still opened. This paper proposes a solution to<br /> báo.<br /> these problems. The results are presented by<br /> unification method which is a new technique to II. CÔNG THỨC BOOLE DƢƠNG<br /> construct the basic algorithms for logic dependencies Cho U = {x1,..., xn} là tập hữu hạn các biến Boole<br /> in data and knowledge bases. nhận giá trị trong tập B = {0, 1}. Tập các công thức<br /> Keywords: Positive Boolean dependencies, Boole (CTB), kí hiệu L(U), bao gồm các biểu thức<br /> unification algorithm, membership problem, key đƣợc xây dựng từ các biến trong U, các hằng 0/1 và<br /> algorithm, closure algorithm. các phép toán logic , , , . Mỗi vector 0/1, v =<br /> (v1,...,vn) trong không gian Bn đƣợc gọi là phép gán trị.<br /> I. GIỚI THIỆU Khi đó với mỗi CTB f  L(U), f(v) là trị của công<br /> 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ị<br /> 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<br /> 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.<br /> 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<br /> 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 =<br /> 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<br /> 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<br /> 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 <br /> 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 <br /> 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).<br /> 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,<br /> 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<br /> nhân trong đại số, dấu phép tuyển có thể đƣợc viết là<br /> trình bày các thuật toán tìm bao đóng và khóa theo tiếp<br /> “+”, dấu phép phủ định “” đƣợc thay bằng “’”. Tập<br /> cận của phép hợp giải trong logic hình thức [1].<br /> các thuộc tính (biến logic) đƣợc viết liền nhau nhƣ<br /> 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ự.<br /> bày vắn tắt các khái niệm và kết quả nghiên cứu trƣớc<br /> <br /> <br /> -50-<br /> 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<br /> <br /> 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<br /> Ta quy ƣớc mỗi miền trị dx của biến x trong U có trùng lặp…[4, 16, 17].<br /> 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<br /> 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<br /> a, b  dx củng cố các mẫu của các hằng số có quan hệ về ngữ<br /> nghĩa. Các phụ thuộc hàm có điều kiện đã đƣợc chứng<br />  x(a, a) = 1<br /> minh là hiệu quả hơn so với phụ thuộc hàm trong việc<br />  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<br />  c  dx: x(a, c) = 0 trạng không sạch) của dữ liệu.<br /> 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à<br /> 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:<br /> 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<br /> trị trên miền trị dx cho x.<br />  X  x là một phụ thuộc hàm<br /> 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.<br /> =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<br /> 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<br /> không định nghĩa tƣờng minh phép sánh trị cho thuộc bởi các giá trị của thuộc tính khác. Trong phụ thuộc<br /> tính này. hàm, giá trị của X xác định đầy đủ giá trị của Y. Trong<br /> Cho quan hệ r trên tập thuộc tính U, với mỗi bộ v  phụ thuộc hàm mềm, giá trị của X xác định giá trị của<br /> r, thuộc tính x  U và tập con thuộc tính X  U, kí Y nhƣng không đầy đủ, chỉ với xác suất cao. Ví dụ,<br /> hiệu u.x (u.X) là trị của thuộc tính u (của tập con thuộc trong một cơ sở dữ liệu của xe ô tô, một phụ thuộc<br /> tính X) trong bộ u. Với mỗi cặp bộ u, v  r, u = (u1, mềm có thể: model → make. Với model = 323, ta suy<br /> u2,... , un), v = (v1, v2,... , vn), ta đặt tƣơng ứng một ra make = Mazda với xác suất cao, nhƣng xác suất nhỏ<br /> vector t  Bn, t = (t1, t2,... , tn) và kí hiệu là (u,v), có thể là BMV. Do đó phụ thuộc hàm mềm đƣợc sử<br /> trong đó thành phần ứng với thuộc tính x trong U dụng trong việc cải tiến sự đánh giá chọn lọc trong tối<br /> chính là ảnh của ánh xạ x (u.x, v.x). Khi đó mỗi quan ƣu hoá truy vấn và làm nên chỉ số so sánh tối thiểu.<br /> hệ r sẽ đƣợc đặt tƣơng ứng với tập các vector 0/1: Phụ thuộc hàm độ đo [9]. Koudas nghiên cứu các phụ<br /> Tr = {(u, v) | u,v  r} thuộc với độ đo gần giống trên tập thuộc tính Y khi cho<br /> các giá trị đƣợc so sánh chính xác trên tập thuộc tính X;<br /> và đƣợc gọi là bảng trị của quan hệ r [10, 14, 15].<br /> với X, Y  U.<br /> IV. QUAN HỆ GIỮA CÁC LOẠI PHỤ THUỘC<br /> Trƣớc hết, ta xây dựng độ đo cho tập các điểm S<br /> LOGIC TRONG CỞ SỞ DỮ LIỆU<br /> trong không gian, khoảng cách giữa hai điểm bất kỳ d:<br /> Phụ thuộc hàm đã là cách thức truyền thống để dx  dx ℝ là độ đo đƣợc xác định trên miền của x,<br /> thiết kế lƣợc đồ, ràng buộc toàn vẹn, tối ƣu hoá truy thỏa ba tính chất:<br /> vấn,…Với đề xuất đầu tiên cho khía cạnh hƣớng lƣợc<br /> a, b  dx:<br /> đồ, là định nghĩa cơ sở trên phép suy dẫn thông<br /> thƣờng () và phép sánh trị đẳng thức (=). Tuy nhiên,  d(a, b) ≥ 0, d(a, b) = 0 khi và chỉ khi a = b<br /> trong hƣớng dữ liệu thực tiễn không phải lúc nào cũng  d(a, b) = d(b, a)<br /> đồng nhất. Do đó, rất nhiều nhóm nghiên cứu gần đây  c  dx: d(a, c) + d(c, b) ≥ d(a, b).<br /> đã đề xuất các loại phụ thuộc khác nhau để phù hợp<br /> hơn với đặc trƣng của dữ liệu, ví dụ nhƣ việc lấy đƣợc<br /> <br /> -51-<br /> 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<br /> <br /> Đƣờng kính của tập các điểm S trong không gian thỏa độ sai khác a: da2  D thỏa hai tính chất phản xạ<br /> độ đo là khoảng cách lớn nhất giữa cặp điểm p, q và đối xứng của độ đo.<br /> trong S, d(S) = .<br /> Cho quan hệ r trên tập thuộc tính U; hai tập con X, Bảng 1. So sánh các loại phụ thuộc logic<br /> Y  U. Cho tập bộ T r, độ đo d trên Y, tham số  ≥ 0. Loại phụ Phép toán Phép Tập<br /> Ta nói có phụ thuộc hàm độ đo X→Y nếu thuộc logic logic sánh trị trị<br /> . Trong đó, T.Y = {t.Y | t  T}, Phụ thuộc  Thỏa tập mẫu {0,1}<br /> {[ ] } là phân hoạch của quan hệ r trên tập có điều kiện Tp<br /> thuộc tính X. Phụ thuộc  = (Với xác [0;1]<br /> Phụ thuộc đối sánh [6]. Phụ thuôc đối sánh đƣợc đề hàm mềm suất cao)<br /> xuất đầu tiên trong Fan (2008) với việc đặc tả các luật Phụ thuộc  Độ đo khoảng [0;1]<br /> đối sánh với biến đối tƣợng. Trong quan hệ r, với mỗi hàm độ đo cách <br /> thuộc tính x có một miền khoảng cách tƣơng ứng dx. Phụ thuộc  Đồng dạng {0,1}<br /> Một toán tử đồng dạng  trên một thuộc tính x hàm đối trên toán tử<br /> đƣợc định nghĩa trên miền khoảng cách của x, : dx  sánh đối sánh  cho<br /> dx {true, false}, với u, v  dx. Cho tập các thuộc tính vế trái và <br /> X, toán tử đồng dạng trên X nhận trị  true nếu các cho vế phải<br /> toán tử đồng dạng trên x  X đều là true. Một toán tử Phụ thuộc  Thời khoảng g [a..b]<br /> đối sánh   trên thuộc tính x đƣợc định nghĩa trên tuần tự<br /> miền khoảng cách của x. Nó là true nếu hai giá trị Phụ thuộc  Hàm sai khác [0;1]<br /> đồng dạng. sai khác  thỏa độ sai<br /> khác a với hai<br /> Một phụ thuộc đối sánh có dạng: [X][Y],<br /> tính chất<br /> trong đó X, Y  U, và ,  biểu thị sự tƣơng ứng<br /> không âm và<br /> đồng dạng các toán tử đối sánh trên tập thuộc tính X<br /> đối xứng<br /> và Y theo thứ tự.<br /> Phụ thuộc , , ,  Phép sánh {0,1}<br /> Phụ thuộc tuần tự [7]. Golab đề xuất phụ thuộc tuần Boole đẳng thức (=)<br /> tự có dạng: X → g Y, với X  U là các thuộc tính có dƣơng<br /> thứ tự, Y  U đƣợc trang bị một độ đo nào đó, g là Phụ thuộc , , ,  Thỏa phép {0,1}<br /> khoảng thời gian. Điều đó nói lên rằng khi các bộ đƣợc Boole sánh trị  với<br /> sắp xếp trên X (thí dụ nhƣ theo thuật toán group by X dƣơng tổng ba tính chất<br /> trong SQL), thì khoảng cách giữa các giá trị Y của hai quát phản xạ, đối<br /> bộ bất kỳ liên tiếp nhau trong khoảng thời gian g. xứng và bộ<br /> Một phụ thuộc tuần tự có điều kiện là một cặp: (X phận.<br /> → g Y, tr) với tr là bộ mẫu. Với mỗi mẫu tr đặc tả một Phụ thuộc , , ,  Thỏa phép [0;1]<br /> dãy giá trị của X để đồng nhất một tập các bộ trên r. Boole sánh trị  với<br /> Phụ thuộc sai khác [12, 13]. Phụ thuộc sai khác trên dƣơng đa trị ba tính chất<br /> quan hệ r có dạng g: X Y, trong đó X, Y là các tập phản xạ, đối<br /> con của tập thuộc tính U; X, Y là các hàm sai khác xứng và bộ<br /> phận.<br /> <br /> <br /> -52-<br /> 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<br /> <br /> Phụ thuộc Boole dƣơng tổng quát [14]. Mỗi công F├2 f   r(U), ||r||  2 : r(F)  r(f)<br /> thức Boole dƣơng f trong P(U) với phép sánh trị  là Định lý 5.1. (Định lý tƣơng đƣơng) [10, 11, 15]<br /> một phụ thuộc Boole dương tổng quát (PTBDTQ).<br /> Cho tập PTBD F và một PTBD f trên U. Ba mệnh<br /> Quan hệ r trên tập thuộc tính U thỏa PTBDTQ f (tập<br /> đề sau là tương đương:<br /> PTBDTQ F) và viết r(f) (r(F)) nếu Tr  Tf (Tr  TF).<br />  F  f (suy dẫn logic)<br /> Phụ thuộc Boole dƣơng đa trị [14]. Tập trị Boole<br />  F├ f (suy dẫn theo quan hệ)<br /> B = {b1,...,bk} gồm k giá trị thực trong đoạn [0; 1], k ≥<br />  F├2 f (suy dẫn theo quan hệ có không quá 2 bộ)<br /> 2 đƣợc sắp tăng và thỏa các điều kiện sau:<br /> V.2. Bài toán thành viên<br />  0  B,<br /> Kí hiệu F+ = {f  P(U) | F├ f } là tập toàn bộ các<br />   b  B  1 b  B.<br /> PTBD đƣợc suy dẫn theo quan hệ từ tập PTBD F. Nếu<br /> Với mỗi trị b  B ta định nghĩa hàm Ib<br /> F├ f , có nghĩa f  F+ thì f là thành viên của F+. Hiển<br />  x  B : Ib(x) = 1 nếu x = b, ngoài ra Ib(x) = 0 nhiên, nếu f  F thì F├ f. Vấn đề đặt ra là ngoài F thì<br /> Cho U = {x1,...,xn} là tập hữu hạn các biến Boole, F+ còn chứa PTBD nào khác?<br /> B là tập trị Boole. Khi đó các công thức Boole đa trị Bài toán thành viên [18]: Cho F là tập PTBD và f là<br /> (CTBĐT) là các công thức đƣợc xây dựng trên các một PTBD trên U. Hãy xác định F├ f ? Nói cách khác<br /> biến của U, các trị trong B , các hàm Ib với b  B và là xác định f  F+?<br /> các phép toán , , , . Mỗi công thức Boole dƣơng Định lý 5.1 cho thấy việc kiểm tra F├ f tƣơng<br /> đa trị f với f (e) =1 thỏa phép sánh trị  trên tập trị B đƣơng với việc kiểm tra suy dẫn logic F  f và cũng<br /> là phụ thuộc Boole dương đa trị (PTBDĐT). tƣơng đƣơng với việc kiểm tra trên các quan hệ có<br /> V. LỚP CÁC PHỤ THUỘC LOGIC không quá hai bộ.<br /> Trong [10, 14, 15] đã chỉ ra mối quan hệ giữa một Định lý tƣơng đƣơng cũng cho biết bài toán thành<br /> số loại phụ thuộc trong cơ sở dữ liệu,…và gọi chung viên tƣơng đƣơng với bài toán suy dẫn của logic mệnh<br /> là lớp các phụ thuộc logic (PTLG). Mỗi phụ thuộc đề trong lớp các phụ thuộc Boole dƣơng. Nếu chọn<br /> trong lớp này chính là một biểu thức Boole trên tập cách kiểm tra F├ f theo quan hệ thì ta phải xây dựng<br /> hữu hạn các thuộc tính. Thí dụ, phụ thuộc hàm là 2m quan hệ, trong đó m là tích các lực lƣợng của miền<br /> trƣờng hợp riêng của PTBDTQ khi các biểu thức logic trị của các thuộc tính. Để xây dựng bảng chân lí T cho<br /> có dạng hội suy dẫn và các phép sánh trị =. mỗi quan hệ gồm k bộ ta phải xét k2 cặp bộ. Trong<br /> trƣờng hợp các thuộc tính có vô hạn giá trị thì tiếp cận<br /> V.1. Định lý tƣơng đƣơng<br /> theo quan hệ là không thể. Do đó, theo định lý tƣơng<br /> Cho tập các PTBD F và một PTBD f trên tập thuộc đƣơng, thay vì kiểm tra F├ f theo quan hệ, ta có thể<br /> tính U. Cho quan hệ r trên tập thuộc tính U. Quan hệ chứng minh F  f theo logic, cụ thể là vận dụng thuật<br /> r(U) thỏa PTBD f và viết r(f) nếu Tr  Tf, quan hệ r(U) toán hợp giải để chứng minh F  f .<br /> thỏa tập PTB F, R(F), nếu Tr  TF. Ta nói tập PTBD F<br /> suy ra PTBD f theo quan hệ và viết F├ f , nếu với mọi Thuật toán 5.1. (Thuật toán hợp giải)<br /> quan hệ r(U), r thỏa F kéo theo r thỏa f: Trong logic, bài toán suy dẫn F f đối với tập<br /> F├ f   r(U): r(F)  r(f) công thức Boole F và công thức Boole f trên tập biến<br /> Boole U đƣợc giải theo thuật toán hợp giải nhƣ sau<br /> Ta nói F suy ra f theo quan hệ có không quá hai bộ<br /> [1]<br /> và viết F├2 f, nếu với mọi quan hệ r trên tập thuộc tính<br /> U và có không quá hai bộ, r thỏa F thì r thỏa f:<br /> <br /> <br /> -53-<br /> 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<br /> <br /> Để chứng minh F  f ta xét phủ định g = (F  f)’ Gọi U là tập các thuộc tính và F là tập PTBD trên<br />  Ff’. Nếu chứng minh đƣợc Ff’ là sai thì F  f, U, X  U. Ta định nghĩa bao đóng X+ của X là tập các<br /> ngƣợc lại F không suy dẫn đƣợc f. thuộc tính sau:<br /> Bƣớc 1. Chuẩn hóa CNF. Đƣa g về dạng chuẩn hội X+ = {a  U | X  a  F+}<br /> (CNF) h, tức là viết g dƣới dạng hội của các tuyển cơ Để tìm bao đóng X+ của X, ta khởi tạo X+ = X sau<br /> sở, trong đó mỗi hạng tử của mọi tuyển cơ sở đều là đó vận dụng thuật toán thành viên để xét cho từng<br /> các biến đơn hoặc phủ định của biến đơn trong g. Gọi thuộc tính a  UX, nếu X  a  F+ thì bổ sung thêm<br /> thủ tục này là CNF, ta có h = CNF(g). a vào X+. Tiếp tục quá trình cho đến khi không mở<br /> Bƣớc 2. Hợp giải. Lần lƣợt thay cặp nhân tử rộng thêm X+ đƣợc nữa.<br /> (a+B)(a’+C) trong h bằng (B+C) cho đến khi không Để ý rằng nếu F đã đƣợc đƣa về dạng CNF thì điều<br /> còn thay đƣợc nữa, hoặc gặp hai nhân tử phủ định kiện X  a  F+ sẽ cho ta CNF(F(X  a)') = FXa', do<br /> nhau là x và x'. Ta gọi thủ tục này là Unif(h).<br /> đó sẽ tƣơng đƣơng với điều kiện Unif(FXa') = .<br /> Lƣu ý x  x+0  0+x, nên ta có thể thay (a+B)a’ hoặc<br /> Thuật toán 5.3. (Thuật toán tìm bao đóng)<br /> (a’+B)a bằng B trong quá trình hợp giải.<br /> Algorithm Closure_PBD(X, F)<br /> Bƣớc 3. Kết luận. Nếu h bị xóa hết (kết quả nhận đƣợc<br /> là tập rỗng ), tức là hợp giải thành công thì kết luận Input: Tập PTBD F dạng CNF<br /> F  f; ngƣợc lại, với mọi khả năng thay thế nhƣ trên, Tập thuộc tính X  U<br /> h không bị xóa hết, tức là hợp giải không thành công Output: X+ = {a  U | X  a  F+}<br /> thì kết luận F không suy dẫn ra f.<br /> Method<br /> Tổng hợp các bƣớc trên ta thu đƣợc thuật toán<br /> Member_PBD(F, f) kiểm tra tập PTBD f có là thành Y  X; // Y chứa kết quả<br /> viên trong tập F+ ? V  U-X; // phần bù của X<br /> Nếu f  F+ thuật toán cho giá trị 1 (true), ngƣợc lại repeat<br /> thuật toán cho ra giá trị 0 (false). Z  Y;<br /> Thuật toán 5.2. [18] (Thuật toán thành viên) for each attribute a in V do<br /> Algorithm Member_ PBD(F, f) if Unif(FYa') =  then<br /> Input: Tập PTBD F; PTBD f. add a to Y;<br /> Output: true, if Ff ; else false endif;<br /> Method endfor;<br /> g  Ff’; // gán Ff' cho g until Y = Z;<br /> h  CNF(g) ; return Y;<br /> return Unif(h) =  ; End Closure_PBD.<br /> End Member_ PBD. Theo mệnh đề 5.1 thì thuật toán tìm bao đóng trong<br /> Mệnh đề 5.1. Bài toán thành viên trong lớp các phụ lớp các phụ thuộc Boole dƣơng là NP đầy đủ (NPC).<br /> thuộc Boole dương thuộc lớp NP đầy đủ (NPC) [18] Thí dụ 5.1. Cho tập thuộc tính U = abcd, tập PTBD F<br /> = {b’+c, a’+b}, X = ab, tìm bao đóng X+?<br /> V.3. Thuật toán bao đóng<br /> Ta có F = (b’+c)(a’+b) hiện ở dạng CNF.<br /> <br /> <br /> -54-<br /> 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<br /> <br /> Đặt Y = X = ab, V = U-X = cd. Xét các thuộc tính Thí dụ 5.2. Cho tập các thuộc tính U ={a, b, c, d}, tập<br /> trong V. phụ thuộc Boole dƣơng F = {b’+c, a’+b}, hãy xác<br /> Với c  V, ta có Unif(FXc’) = (b’+c)(a’+b)abc’ = định một khóa K trong quan hệ r?<br /> (c+a')abc' = bcc' = . Vậy Y = abc. Trƣớc hết ta đƣa F về dạng CNF, F =<br /> (b’+c)(a’+b).<br /> Với d  V, ta có Unif(FXd’) = (b’+c)(a’+b)abcd’ =<br /> (a'+c)abcd’ = cbcd’ ≠  nên Y không thay đổi. Cuối Áp dụng thuật toán tìm khóa, đặt K = U = abcd.<br /> cùng ta thu đƣợc X+ = (ab)+ = abc. Lần lƣợt rút gọn khóa K bằng cách xét từng thuộc tính<br /> a, b, c và d trong K:<br /> V.4. Thuật toán tìm khóa<br /> Xét a: K-a = bcd. Ta có: Unif(Fbcda’) =<br /> Cho F là tập PTBD trên U. Tập K  U đƣợc gọi là (b’+c)(a'+b)bcda’ = (a'+c)bcda' ≠ . Vậy, K không<br /> khóa nếu thay đổi, K = abcd.<br /> - K+ = U Xét b: K-b = acd. Ta có: Unif(Facdb’) =<br /> - a  K: (K a)+ ≠ U (b’+c)(a'+b)acdb’ = (b'+c)bcdb' = . Vậy, K = acd.<br /> Để tìm tập khóa K, trƣớc tiên đặt K = U. Sau đó rút Xét c: K-c = ad. Ta có Unif(Fadc') = (b’+c)(a'+b)adc’<br /> gọn K bằng cách xét từng thuộc tính a trong K, nếu = (b'+c)bdc' = cdc' = . Vậy, K = ad.<br /> (K a)+ = U thì loại a ra khỏi K.<br /> Xét d: K-d = a. Ta có Unif(Fad') = (b'+c)(a'+b)ad' =<br /> Do ta luôn bảo toàn bất biến K+ = U nên điều kiện (b'+c)bd' = cd' ≠ . Vậy, K không thay đổi. Cuối<br /> (Ka)+ = U tƣơng đƣơng với điều kiện (Ka)a. Điều cùng ta thu đƣợc khóa k = ad.<br /> kiện này lại tƣơng đƣơng với điều kiện<br /> VI. KẾT LUẬN<br /> Unif(F(K a)a') = .<br /> Thuật toán hợp giải có thể đƣợc cài đặt nhƣ một<br /> Thuật toán 5.4. (Thuật toán tìm khóa)<br /> tiện ích trong các thƣ viện của các ngôn ngữ lập trình<br /> Algorithm Key_PBD(U, F) logic nhƣ Prolog, P#, Lisp. Nghiên cứu các phụ thuộc<br /> Input: Tập thuộc tính U; Tập PTBD F dạng CNF Boole dƣơng theo tiếp cận của logic hình thức cho<br /> Output: K  U: phép ta thiết kế và quản lí các cơ sở dữ liệu và tri thức<br /> với những phụ thuộc phức tạp và đa dạng một cách<br /> - K+ = U<br /> thống nhất. Các kết quả thu đƣợc trong bài này có thể<br /> - a  K: Unif(F(K - a)a') = Ø đƣợc vận dụng trong lĩnh vực khai thác tri thức từ các<br /> Method tập dữ liệu lớn.<br /> K  U;<br /> TÀI LIỆU THAM KHẢO<br /> for each attribute a in K do<br /> [1] BAADER F., SNYDER W., “Hanbook of Automated<br /> if Unif(F(K - a)a') = Ø then Reasonning”. Ed. Alan Robinson and Andrei Voronkov,<br /> delete a from K; Elsevier Science Publishers B.V, 2001.<br /> [2] BOHANNON P., FAN W., GEERTS F., JIA X.,<br /> endif<br /> KEMENTSIETSIDIS A., (2007), “Conditional<br /> endfor functional dependencies for data cleaning”, In ICDE,<br /> return K; pp.746-755.<br /> [3] BRAVO L., FAN W., MA S., (2007), “Extending<br /> End Key_PBD.<br /> dependencies with condition”, In VLDB, pp.243-254.<br /> Theo mệnh đề 5.1 thì thuật toán tìm khóa trong lớp<br /> các phụ thuộc Boole dƣơng là NP đầy đủ (NPC).<br /> <br /> -55-<br /> 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<br /> <br /> [4] DAVID MAIER, V. M MEGLER, KRISTIN TUFTE [16] NGUYỄN XUÂN HUY, ĐÀM GIA MẠNH, VŨ THỊ<br /> (2014), Challenges for Dataset Search, “Database THANH XUÂN, KIM LAN HƢƠNG (2001), “Về một<br /> System for Advanced Applications”, Lecture Notes in lớp công thức logic suy dẫn”, Tạp chí Tin học và điều<br /> Computer Science Volum 8421, 1-15. khiển học, 17 (4), tr. 17-22.<br /> [5] FAN W., GEERTS F., LAKSHMANAN L. V. S., [17] NGUYỄN XUÂN HUY, ĐOÀN VĂN BAN, ĐÀM GIA<br /> XIONG M., (2009), “Discovering conditional MẠNH, NGUYỄN THẾ DŨNG (2001), “Về mối liên hệ<br /> functional dependencies”, In ICDE, pp. 1231-1234. giữa suy diễn phụ thuộc hàm và suy diễn logic”, Tạp chí<br /> [6] FAN W., LI J., JIA X., MA S., (2009), “Reasoning Tin học và điều khiển học, 17(4), tr.11-16.<br /> about record matching rules”, PVLDB. [18] TRƢƠNG THỊ THU HÀ, “Độ phức tạp của các thuật<br /> [7] GOLAB L., KARLOFF H., KORN F., SAHA A., toán chuẩn hóa phụ thuộc Boole dương", Tạp chí<br /> SRIVASTAVA D., (2009), “Sequential Công nghệ thông tin và truyền thông, ISSN 1859 –<br /> dependencies”, PVLDB, 2(1), pp.574-585. 3526, Tập V-1, Số 12(32), 12-2014.<br /> [8] ILYAS I. F., MARKL V., HAAS P. J., BROWN P.,<br /> ABOULNAGA A., (2004), “Cords: Automatic Nhận bài ngày: 29/02/2016<br /> discovery of correlations and soft functional<br /> dependencies”, In Sigmod Conference, pp.647-658.<br /> [9] KOUDAS N., SAHA A., SRIVASTAVA D.,<br /> VENKATASUBRAMANIAN S., (2009), “Metric<br /> functional dependencies”, In ICDE, pp.1275-1278.<br /> [10] NGUYEN XUAN HUY, LE THI THANH,<br /> “Generalized Positive Boolean Dependencies”, J. Inf.<br /> Process. Cybern. EIK, 28, 1992, 6, 363-370.<br /> [11] SAGIV Y., DELOBEL C., PARKER D. S., FAGIN R.,<br /> “An equivalence between Relational Database<br /> Dependencies and a Fragment of Propositional Logic”,<br /> J.ACM, 28, 1981, 435 - 453. Corrigendum J. ACM, 34,<br /> 1987, 1016 -1018.<br /> [12] SONG S., CHEN L. and CHENG H., “Efficient<br /> Determination of Distance Thresholds for Differential<br /> Dependencies”, IEEE Transactions on knowledge and<br /> data engineering, Vol. 26, No. 9, 2014, 2179-2192.<br /> [13] SONG S., CHEN L., “Differential Dependencies:<br /> Reasoning and Discovery”, ACM Trans. Datab. Syst.<br /> 9, 4, Article 39, (March 2011), 42 pages.<br /> [14] NGUYỄN XUÂN HUY, “Các phụ thuộc logic trong<br /> cơ sở dữ liệu”, NXB Thống Kê, 2006.<br /> [15] NGUYỄN XUÂN HUY, CAO TÙNG ANH, TRƢƠNG<br /> THỊ THU HÀ, LƢƠNG NGUYỄN HOÀNG HOA, BÙI<br /> ĐỨC MINH (2012), “Các biến thể của phụ thuộc sai khác<br /> trong cơ sở dữ liệu quan hệ”, Kỷ yếu Hội thảo quốc gia lần<br /> thứ XV: “Một số vấn đề chọn lọc của Công nghệ thông tin<br /> và Truyền thông”, NXB Khoa học và Kỹ thuật, ISBN 978-<br /> 604-67-0251-137- 41.<br /> <br /> <br /> <br /> -56-<br /> 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<br /> <br /> SƠ LƢỢC VỀ TÁC GIẢ<br /> TRƢƠNG THỊ THU HÀ NGUYỄN XUÂN HUY<br /> Sinh năm 1979 tại Nghệ An. Sinh năm 1944, Hải Phòng.<br /> Tốt nghiệp Cử nhân CNTT tại Tốt nhiệp Cử nhân Toán, ĐH Sƣ<br /> Trƣờng ĐH Sƣ phạm Hà Nội năm phạm Leningrad (Liên Xô) năm<br /> 2000, Thạc sĩ CNTT tại Trƣờng 1973, Tiến sỹ CNTT năm 1982,<br /> ĐH Công nghệ, ĐH Quốc gia Hà Tiến sỹ khoa học CNTT, Viện<br /> Nội năm 2006. Đang là nghiên Hàn lâm Khoa học Liên Xô năm<br /> cứu sinh tại Khoa CNTT, Học 1990.<br /> viện Kỹ thuật Quân sự. Là Trƣởng Phòng Cơ sở dữ liệu<br /> Hiện công tác tại Khoa CNTT, trƣởng Đại học Kinh và Lập trình, Viện CNTT, Viện Hàn lâm KH&CN<br /> doanh và Công nghệ Hà Nội. Việt Nam từ năm 1997-2009.<br /> Lĩnh vực nghiên cứu: Cơ sở dữ liệu, Công nghệ phần Hƣớng nghiên cứu: Cơ sở dữ liệu và Công nghệ phần<br /> mềm. mềm. Email: nxhuy564@gmail.com<br /> Email: thuha.bh@gmail.com<br /> <br /> <br /> NGUYỄN THỊ VÂN<br /> Sinh năm 1985 tại Hà Tĩnh.<br /> Tốt nghiệp Cử nhân CNTT tại<br /> Trƣờng ĐH Kinh doanh và Công<br /> nghệ Hà Nội năm 2011, Thạc sĩ<br /> ngành Khoa học máy tính tại<br /> Trƣờng ĐH CNTT và Truyền<br /> thông năm 2014.<br /> Hiện công tác tại Khoa CNTT,<br /> Trƣờng Cao đẳng Cộng đồng Hà Nội.<br /> Lĩnh vực nghiên cứu: Các phụ thuộc logic trong cơ sở<br /> dữ liệu, mô hình dữ liệu và cơ sở dữ liệu.<br /> Email: van.cdcd@gmail.com<br /> <br /> <br /> <br /> <br /> -57-<br />
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2