Xem mẫu
- 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 sánh trị cho thuộc bởi các giá trị của thuộc tính khác. Trong phụ thuộc
tính này. hàm, giá trị của X xác định đầy đủ giá trị của Y. Trong
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
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ụ,
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
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
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ỏ
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ử
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
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.
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ụ
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
các giá trị đƣợc so sánh chính xác trên tập thuộc tính X;
và đƣợc gọi là bảng trị của quan hệ r [10, 14, 15].
với X, Y U.
IV. QUAN HỆ GIỮA CÁC LOẠI PHỤ THUỘC
Trƣớc hết, ta xây dựng độ đo cho tập các điểm S
LOGIC TRONG CỞ SỞ DỮ LIỆU
trong không gian, khoảng cách giữa hai điểm bất kỳ d:
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,
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:
vấn,…Với đề xuất đầu tiên cho khía cạnh hƣớng lƣợc
a, b dx:
đồ, là định nghĩa cơ sở trên phép suy dẫn thông
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
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)
đồ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).
đã đề xuất các loại phụ thuộc khác nhau để phù hợp
hơn với đặc trƣng của dữ liệu, ví dụ nhƣ việc lấy đƣợc
-51-
- 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
Đƣờ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ạ
độ đ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.
trong S, d(S) = .
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
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
Ta nói có phụ thuộc hàm độ đo X→Y nếu thuộc logic logic sánh trị trị
. Trong đó, T.Y = {t.Y | t T}, Phụ thuộc Thỏa tập mẫu {0,1}
{[ ] } là phân hoạch của quan hệ r trên tập có điều kiện Tp
thuộc tính X. Phụ thuộc = (Với xác [0;1]
Phụ thuộc đối sánh [6]. Phụ thuôc đối sánh đƣợc đề hàm mềm suất cao)
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]
đối sánh với biến đối tƣợng. Trong quan hệ r, với mỗi hàm độ đo cách
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}
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ử
đƣợc định nghĩa trên miền khoảng cách của x, : dx sánh đối sánh cho
dx {true, false}, với u, v dx. Cho tập các thuộc tính vế trái và
X, toán tử đồng dạng trên X nhận trị true nếu các cho vế phải
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]
đối sánh trên thuộc tính x đƣợc định nghĩa trên tuần tự
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]
đồng dạng. sai khác thỏa độ sai
khác a với hai
Một phụ thuộc đối sánh có dạng: [X][Y],
tính chất
trong đó X, Y U, và , biểu thị sự tƣơng ứng
không âm và
đồng dạng các toán tử đối sánh trên tập thuộc tính X
đối xứng
và Y theo thứ tự.
Phụ thuộc , , , Phép sánh {0,1}
Phụ thuộc tuần tự [7]. Golab đề xuất phụ thuộc tuần Boole đẳng thức (=)
tự có dạng: X → g Y, với X U là các thuộc tính có dƣơng
thứ tự, Y U đƣợc trang bị một độ đo nào đó, g là Phụ thuộc , , , Thỏa phép {0,1}
khoảng thời gian. Điều đó nói lên rằng khi các bộ đƣợc Boole sánh trị với
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
trong SQL), thì khoảng cách giữa các giá trị Y của hai quát phản xạ, đối
bộ bất kỳ liên tiếp nhau trong khoảng thời gian g. xứng và bộ
Một phụ thuộc tuần tự có điều kiện là một cặp: (X phận.
→ 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]
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
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
quan hệ r có dạng g: X Y, trong đó X, Y là các tập phản xạ, đối
con của tập thuộc tính U; X, Y là các hàm sai khác xứng và bộ
phận.
-52-
- 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
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)
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]
một phụ thuộc Boole dương tổng quát (PTBDTQ).
Cho tập PTBD F và một PTBD f trên U. Ba mệnh
Quan hệ r trên tập thuộc tính U thỏa PTBDTQ f (tập
đề sau là tương đương:
PTBDTQ F) và viết r(f) (r(F)) nếu Tr Tf (Tr TF).
F f (suy dẫn logic)
Phụ thuộc Boole dƣơng đa trị [14]. Tập trị Boole
F├ f (suy dẫn theo quan hệ)
B = {b1,...,bk} gồm k giá trị thực trong đoạn [0; 1], k ≥
F├2 f (suy dẫn theo quan hệ có không quá 2 bộ)
2 đƣợc sắp tăng và thỏa các điều kiện sau:
V.2. Bài toán thành viên
0 B,
Kí hiệu F+ = {f P(U) | F├ f } là tập toàn bộ các
b B 1 b B.
PTBD đƣợc suy dẫn theo quan hệ từ tập PTBD F. Nếu
Với mỗi trị b B ta định nghĩa hàm Ib
F├ f , có nghĩa f F+ thì f là thành viên của F+. Hiển
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ì
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?
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à
(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
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+?
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
đ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
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ó
V. LỚP CÁC PHỤ THUỘC LOGIC không quá hai bộ.
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
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
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
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
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
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
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
trƣờng hợp các thuộc tính có vô hạn giá trị thì tiếp cận
V.1. Định lý tƣơng đƣơng
theo quan hệ là không thể. Do đó, theo định lý tƣơng
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ể
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
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 .
thỏa tập PTB F, R(F), nếu Tr TF. Ta nói tập PTBD F
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)
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
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
Boole U đƣợc giải theo thuật toán hợp giải nhƣ sau
Ta nói F suy ra f theo quan hệ có không quá hai bộ
[1]
và viết F├2 f, nếu với mọi quan hệ r trên tập thuộc tính
U và có không quá hai bộ, r thỏa F thì r thỏa f:
-53-
- 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
Để 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
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
ngƣợc lại F không suy dẫn đƣợc f. thuộc tính sau:
Bƣớc 1. Chuẩn hóa CNF. Đƣa g về dạng chuẩn hội X+ = {a U | X a F+}
(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
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
các biến đơn hoặc phủ định của biến đơn trong g. Gọi thuộc tính a UX, nếu X a F+ thì bổ sung thêm
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ở
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.
(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
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
nhau là x và x'. Ta gọi thủ tục này là Unif(h).
đó sẽ tƣơng đƣơng với điều kiện Unif(FXa') = .
Lƣu ý x x+0 0+x, nên ta có thể thay (a+B)a’ hoặc
Thuật toán 5.3. (Thuật toán tìm bao đóng)
(a’+B)a bằng B trong quá trình hợp giải.
Algorithm Closure_PBD(X, F)
Bƣớc 3. Kết luận. Nếu h bị xóa hết (kết quả nhận đƣợc
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
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
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+}
thì kết luận F không suy dẫn ra f.
Method
Tổng hợp các bƣớc trên ta thu đƣợc thuật toán
Member_PBD(F, f) kiểm tra tập PTBD f có là thành Y X; // Y chứa kết quả
viên trong tập F+ ? V U-X; // phần bù của X
Nếu f F+ thuật toán cho giá trị 1 (true), ngƣợc lại repeat
thuật toán cho ra giá trị 0 (false). Z Y;
Thuật toán 5.2. [18] (Thuật toán thành viên) for each attribute a in V do
Algorithm Member_ PBD(F, f) if Unif(FYa') = then
Input: Tập PTBD F; PTBD f. add a to Y;
Output: true, if Ff ; else false endif;
Method endfor;
g Ff’; // gán Ff' cho g until Y = Z;
h CNF(g) ; return Y;
return Unif(h) = ; End Closure_PBD.
End Member_ PBD. Theo mệnh đề 5.1 thì thuật toán tìm bao đóng trong
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).
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
= {b’+c, a’+b}, X = ab, tìm bao đóng X+?
V.3. Thuật toán bao đóng
Ta có F = (b’+c)(a’+b) hiện ở dạng CNF.
-54-
- 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
Đặ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
trong V. phụ thuộc Boole dƣơng F = {b’+c, a’+b}, hãy xác
Với c V, ta có Unif(FXc’) = (b’+c)(a’+b)abc’ = định một khóa K trong quan hệ r?
(c+a')abc' = bcc' = . Vậy Y = abc. Trƣớc hết ta đƣa F về dạng CNF, F =
(b’+c)(a’+b).
Với d V, ta có Unif(FXd’) = (b’+c)(a’+b)abcd’ =
(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.
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
a, b, c và d trong K:
V.4. Thuật toán tìm khóa
Xét a: K-a = bcd. Ta có: Unif(Fbcda’) =
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
khóa nếu thay đổi, K = abcd.
- K+ = U Xét b: K-b = acd. Ta có: Unif(Facdb’) =
- a K: (K a)+ ≠ U (b’+c)(a'+b)acdb’ = (b'+c)bcdb' = . Vậy, K = acd.
Để 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’
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.
(K a)+ = U thì loại a ra khỏi K.
Xét d: K-d = a. Ta có Unif(Fad') = (b'+c)(a'+b)ad' =
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
(Ka)+ = U tƣơng đƣơng với điều kiện (Ka)a. Điều cùng ta thu đƣợc khóa k = ad.
kiện này lại tƣơng đƣơng với điều kiện
VI. KẾT LUẬN
Unif(F(K a)a') = .
Thuật toán hợp giải có thể đƣợc cài đặt nhƣ một
Thuật toán 5.4. (Thuật toán tìm khóa)
tiện ích trong các thƣ viện của các ngôn ngữ lập trình
Algorithm Key_PBD(U, F) logic nhƣ Prolog, P#, Lisp. Nghiên cứu các phụ thuộc
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
Output: K U: phép ta thiết kế và quản lí các cơ sở dữ liệu và tri thức
với những phụ thuộc phức tạp và đa dạng một cách
- K+ = U
thống nhất. Các kết quả thu đƣợc trong bài này có thể
- 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
Method tập dữ liệu lớn.
K U;
TÀI LIỆU THAM KHẢO
for each attribute a in K do
[1] BAADER F., SNYDER W., “Hanbook of Automated
if Unif(F(K - a)a') = Ø then Reasonning”. Ed. Alan Robinson and Andrei Voronkov,
delete a from K; Elsevier Science Publishers B.V, 2001.
[2] BOHANNON P., FAN W., GEERTS F., JIA X.,
endif
KEMENTSIETSIDIS A., (2007), “Conditional
endfor functional dependencies for data cleaning”, In ICDE,
return K; pp.746-755.
[3] BRAVO L., FAN W., MA S., (2007), “Extending
End Key_PBD.
dependencies with condition”, In VLDB, pp.243-254.
Theo mệnh đề 5.1 thì thuật toán tìm khóa trong lớp
các phụ thuộc Boole dƣơng là NP đầy đủ (NPC).
-55-
- 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
[4] DAVID MAIER, V. M MEGLER, KRISTIN TUFTE [16] NGUYỄN XUÂN HUY, ĐÀM GIA MẠNH, VŨ THỊ
(2014), Challenges for Dataset Search, “Database THANH XUÂN, KIM LAN HƢƠNG (2001), “Về một
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
Computer Science Volum 8421, 1-15. khiển học, 17 (4), tr. 17-22.
[5] FAN W., GEERTS F., LAKSHMANAN L. V. S., [17] NGUYỄN XUÂN HUY, ĐOÀN VĂN BAN, ĐÀM GIA
XIONG M., (2009), “Discovering conditional MẠNH, NGUYỄN THẾ DŨNG (2001), “Về mối liên hệ
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í
[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.
about record matching rules”, PVLDB. [18] TRƢƠNG THỊ THU HÀ, “Độ phức tạp của các thuật
[7] GOLAB L., KARLOFF H., KORN F., SAHA A., toán chuẩn hóa phụ thuộc Boole dương", Tạp chí
SRIVASTAVA D., (2009), “Sequential Công nghệ thông tin và truyền thông, ISSN 1859 –
dependencies”, PVLDB, 2(1), pp.574-585. 3526, Tập V-1, Số 12(32), 12-2014.
[8] ILYAS I. F., MARKL V., HAAS P. J., BROWN P.,
ABOULNAGA A., (2004), “Cords: Automatic Nhận bài ngày: 29/02/2016
discovery of correlations and soft functional
dependencies”, In Sigmod Conference, pp.647-658.
[9] KOUDAS N., SAHA A., SRIVASTAVA D.,
VENKATASUBRAMANIAN S., (2009), “Metric
functional dependencies”, In ICDE, pp.1275-1278.
[10] NGUYEN XUAN HUY, LE THI THANH,
“Generalized Positive Boolean Dependencies”, J. Inf.
Process. Cybern. EIK, 28, 1992, 6, 363-370.
[11] SAGIV Y., DELOBEL C., PARKER D. S., FAGIN R.,
“An equivalence between Relational Database
Dependencies and a Fragment of Propositional Logic”,
J.ACM, 28, 1981, 435 - 453. Corrigendum J. ACM, 34,
1987, 1016 -1018.
[12] SONG S., CHEN L. and CHENG H., “Efficient
Determination of Distance Thresholds for Differential
Dependencies”, IEEE Transactions on knowledge and
data engineering, Vol. 26, No. 9, 2014, 2179-2192.
[13] SONG S., CHEN L., “Differential Dependencies:
Reasoning and Discovery”, ACM Trans. Datab. Syst.
9, 4, Article 39, (March 2011), 42 pages.
[14] NGUYỄN XUÂN HUY, “Các phụ thuộc logic trong
cơ sở dữ liệu”, NXB Thống Kê, 2006.
[15] NGUYỄN XUÂN HUY, CAO TÙNG ANH, TRƢƠNG
THỊ THU HÀ, LƢƠNG NGUYỄN HOÀNG HOA, BÙI
ĐỨC MINH (2012), “Các biến thể của phụ thuộc sai khác
trong cơ sở dữ liệu quan hệ”, Kỷ yếu Hội thảo quốc gia lần
thứ XV: “Một số vấn đề chọn lọc của Công nghệ thông tin
và Truyền thông”, NXB Khoa học và Kỹ thuật, ISBN 978-
604-67-0251-137- 41.
-56-
- 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
SƠ LƢỢC VỀ TÁC GIẢ
TRƢƠNG THỊ THU HÀ NGUYỄN XUÂN HUY
Sinh năm 1979 tại Nghệ An. Sinh năm 1944, Hải Phòng.
Tốt nghiệp Cử nhân CNTT tại Tốt nhiệp Cử nhân Toán, ĐH Sƣ
Trƣờng ĐH Sƣ phạm Hà Nội năm phạm Leningrad (Liên Xô) năm
2000, Thạc sĩ CNTT tại Trƣờng 1973, Tiến sỹ CNTT năm 1982,
ĐH Công nghệ, ĐH Quốc gia Hà Tiến sỹ khoa học CNTT, Viện
Nội năm 2006. Đang là nghiên Hàn lâm Khoa học Liên Xô năm
cứu sinh tại Khoa CNTT, Học 1990.
viện Kỹ thuật Quân sự. Là Trƣởng Phòng Cơ sở dữ liệu
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
doanh và Công nghệ Hà Nội. Việt Nam từ năm 1997-2009.
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
mềm. mềm. Email: nxhuy564@gmail.com
Email: thuha.bh@gmail.com
NGUYỄN THỊ VÂN
Sinh năm 1985 tại Hà Tĩnh.
Tốt nghiệp Cử nhân CNTT tại
Trƣờng ĐH Kinh doanh và Công
nghệ Hà Nội năm 2011, Thạc sĩ
ngành Khoa học máy tính tại
Trƣờng ĐH CNTT và Truyền
thông năm 2014.
Hiện công tác tại Khoa CNTT,
Trƣờng Cao đẳng Cộng đồng Hà Nội.
Lĩnh vực nghiên cứu: Các phụ thuộc logic trong cơ sở
dữ liệu, mô hình dữ liệu và cơ sở dữ liệu.
Email: van.cdcd@gmail.com
-57-
nguon tai.lieu . vn
