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 />