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 
 -50- 
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 
relation schemas with functional dependencies are 
well-known in theory of relational databases. 
However, the problems of closures and keys in 
relation schemas with positive Boolean dependencies 
are still opened. This paper proposes a solution to 
these problems. The results are presented by 
unification method which is a new technique to 
construct the basic algorithms for logic dependencies 
in data and knowledge bases. 
Keywords: Positive Boolean dependencies, 
unification algorithm, membership problem, key 
algorithm, closure algorithm. 
I. GIỚI THIỆU 
Khóa của lƣợc đồ quan hệ là tập tối thiểu các thuộc 
tính nhằm xác định đơn trị một bộ trong cơ sở dữ liệu 
quan hệ. Khóa giữ vai trò quan trọng trong các bài 
toán tìm kiếm và suy dẫn. Chính vì vậy mà bài toán 
tìm khóa luôn đƣợc đề cập nhƣ một đối tƣợng cơ bản 
trong nghiên cứu về các loại phụ thuộc nhƣ phụ thuộc 
hàm, phụ thuộc đa trị, phụ thuộc sai khác [12, 13, 14], 
v.v.. Khái niệm khóa lại đƣợc dẫn xuất từ khái niệm 
bao đóng của một tập thuộc tính. Do đó bài toán tìm 
bao đóng và tìm khóa trong lƣợc đồ quan hệ có trang 
bị phụ thuộc Boole dƣơng và phụ thuộc Boole dƣơng 
tổng quát [10, 11, 14] đang là vấn đề mở. Bài báo này 
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 [1]. 
Sau phần giới thiệu của bài báo, phần 2 và 3 trình 
bày vắn tắt các khái niệm và kết quả nghiên cứu trƣớc 
đó về phụ thuộc Boole dƣơng. Phần 4 là 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. Phần 5 đề 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. Phần 6 là kết luận của bài 
báo. 
II. CÔNG THỨC BOOLE DƢƠNG 
Cho U = {x1,..., xn} là tập hữu hạn các biến Boole 
nhận giá trị trong tập B = {0, 1}. Tập các công thức 
Boole (CTB), kí hiệu L(U), bao gồm các biểu thức 
đƣợc xây dựng từ các biến trong U, các hằng 0/1 và 
các phép toán logic , , , . Mỗi vector 0/1, v = 
(v1,...,vn) trong không gian B
n đƣợc gọi là phép gán trị. 
Khi đó với mỗi CTB f L(U), f(v) là trị của công 
thức f đối với phép gán trị v. Kí hiệu e là phép gán trị 
đơn vị, e = (1,1,...,1). Công thức f L(U) gọi là công 
thức Boole dương (CTBD) nếu f(e) = 1. 
Ký hiệu P(U) là tập các công thức Boole dƣơng 
trên U. Với mỗi công thức Boole f L(U), kí hiệu Tf = 
{v Bn | f(v) = 1} là bảng chân lí của f. Mỗi tập công 
thức F  L(U) đƣợc hiểu là một hội logic của các công 
thức thành phần, {f | f F}. Khi đó, TF =  {Tf | f 
F} là bảng chân lí của tập công thức F. Ta đã biết f 
g (F g) khi và chỉ khi Tf  Tg (TF  Tg). 
Theo qui ƣớc của lí thuyết cơ sở dữ liệu và tri thức, 
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à 
“+”, dấu phép phủ định “” đƣợc thay bằng “’”. Tập 
các thuộc tính (biến logic) đƣợc viết liền nhau nhƣ 
một dãy kí tự. 
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 
 -51- 
III. PHÉP SÁNH TRỊ 
Ta quy ƣớc mỗi miền trị dx của biến x trong U có 
chứa ít nhất hai phần tử. Với mỗi miền trị dx, xét ánh 
xạ x: dx dx
 B thoả ba tính chất sau [11, 14]: 
a, b dx 
 x(a, a) = 1 
 x(a, b) = x(b, a) 
 c dx: x(a, c) = 0 
 x chính là quan hệ (hai ngôi) bộ phận thực sự, 
thoả các tính chất phản xạ và đối xứng trên miền trị dx. 
Việc xác định x đƣợc hiểu là thiết lập một phép sánh 
trị trên miền trị dx cho x. 
Quan hệ bằng =x đƣợc định nghĩa:  a, b dx: 
=x(a, b) = 1, khi và chỉ khi a = b là trƣờng hợp riêng 
của phép sánh trị và đƣợc ngầm định trong trƣờng hợp 
không định nghĩa tƣờng minh phép sánh trị cho thuộc 
tính này. 
Cho quan hệ r trên tập thuộc tính U, với mỗi bộ v 
r, thuộc tính x U và tập con thuộc tính X  U, kí 
hiệu u.x (u.X) là trị của thuộc tính u (của tập con thuộc 
tính X) trong bộ u. Với mỗi cặp bộ u, v r, u = (u1, 
u2,... , un), v = (v1, v2,... , vn), ta đặt tƣơng ứng một 
vector t Bn, t = (t1, t2,... , tn) và kí hiệu là (u,v), 
trong đó thành phần ứng với thuộc tính x trong U 
chính là ảnh của ánh xạ x (u.x, v.x). Khi đó mỗi quan 
hệ r sẽ đƣợc đặt tƣơng ứng với tập các vector 0/1: 
Tr = { (u, v) | u,v r} 
và đƣợc gọi là bảng trị của quan hệ r [10, 14, 15]. 
IV. QUAN HỆ GIỮA CÁC LOẠI PHỤ THUỘC 
LOGIC TRONG CỞ SỞ DỮ LIỆU 
 Phụ thuộc hàm đã là cách thức truyền thống để 
thiết kế lƣợc đồ, ràng buộc toàn vẹn, tối ƣu hoá truy 
vấn,Với đề xuất đầu tiên cho khía cạnh hƣớng lƣợc 
đồ, 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, 
trong hƣớng dữ liệu thực tiễn không phải lúc nào cũng 
đồng nhất. Do đó, rất nhiều nhóm nghiên cứu gần đây 
đã đề 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 
dữ liệu ngƣợc nhau, phục hồi dữ liệu, loại bỏ dữ liệu 
trùng lặp[4, 16, 17]. 
Phụ thuộc hàm có điều kiện [2, 3, 5]. Phụ thuộc hàm 
có điều kiện là mở rộng các phụ thuộc hàm bằng cách 
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 
minh là hiệu quả hơn so với phụ thuộc hàm trong việc 
phát hiện và sửa chữa các điểm không nhất quán (tình 
trạng không sạch) của dữ liệu. 
Một phụ thuộc hàm có điều kiện trên quan hệ r là 
một cặp (X x, TP) thỏa mãn: 
 X  U và x U, với U là tập các thuộc tính 
 X x là một phụ thuộc hàm 
 TP là tập bộ mẫu trong X và x tƣơng ứng. 
Phụ thuộc hàm mềm [8]. Ilyas nghiên cứu phụ thuộc 
hàm mềm với các giá trị của thuộc tính đƣợc dự đoán 
bởi các giá trị của thuộc tính khác. Trong phụ thuộc 
hàm, giá trị của X xác định đầy đủ giá trị của Y. Trong 
phụ thuộc hàm mềm, giá trị của X xác định giá trị của 
Y nhƣng không đầy đủ, chỉ với xác suất cao. Ví dụ, 
trong một cơ sở dữ liệu của xe ô tô, một phụ thuộc 
mềm có thể: model → make. Với model = 323, ta suy 
ra make = Mazda với xác suất cao, nhƣng xác suất nhỏ 
có thể là BMV. Do đó phụ thuộc hàm mềm đƣợc sử 
dụng trong việc cải tiến sự đánh giá chọn lọc trong tối 
ƣu hoá truy vấn và làm nên chỉ số so sánh tối thiểu. 
Phụ thuộc hàm độ đo [9]. Koudas nghiên cứu các phụ 
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ới X, Y  U. 
Trƣớc hết, ta xây dựng độ đo cho tập các điểm S 
trong không gian, khoảng cách giữa hai điểm bất kỳ d: 
dx dx ℝ là độ đo đƣợc xác định trên miền của x, 
thỏa ba tính chất: 
a, b dx: 
 d(a, b) ≥ 0, d(a, b) = 0 khi và chỉ khi a = b 
 d(a, b) = d(b, a) 
 c dx: d(a, c) + d(c, b) ≥ d(a, b). 
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 
 -52- 
Đƣờng kính của tập các điểm S trong không gian 
độ đo là khoảng cách lớn nhất giữa cặp điểm p, q 
trong S, d(S) = . 
Cho quan hệ r trên tập thuộc tính U; hai tập con X, 
Y  U. Cho tập bộ T r, độ đo d trên Y, tham số  ≥ 0. 
Ta nói có phụ thuộc hàm độ đo X
→Y nếu 
 . Trong đó, T.Y = {t.Y | t T}, 
 {[ ] } là phân hoạch của quan hệ r trên tập 
thuộc tính X. 
Phụ thuộc đối sánh [6]. Phụ thuôc đối sánh đƣợc đề 
xuất đầu tiên trong Fan (2008) với việc đặc tả các luật 
đối sánh với biến đối tƣợng. Trong quan hệ r, với mỗi 
thuộc tính x có một miền khoảng cách tƣơng ứng dx. 
Một toán tử đồng dạng trên một thuộc tính x 
đƣợc định nghĩa trên miền khoảng cách của x, : dx 
dx {true, false}, với u, v dx. Cho tập các thuộc tính 
X, toán tử đồng dạng trên X nhận trị true nếu các 
toán tử đồng dạng trên x X đều là true. Một toán tử 
đối sánh   trên thuộc tính x đƣợc định nghĩa trên 
miền khoảng cách của x. Nó là true nếu hai giá trị 
đồng dạng. 
Một phụ thuộc đối sánh có dạng: [X ] [Y], 
trong đó X, Y  U, và ,  biểu thị sự tƣơng ứng 
đồng dạng các toán tử đối sánh trên tập thuộc tính X 
và Y theo thứ tự. 
Phụ thuộc tuần tự [7]. Golab đề xuất phụ thuộc tuần 
tự có dạng: X → g
Y, với X  U là các thuộc tính có 
thứ tự, Y  U đƣợc trang bị một độ đo nào đó, g là 
khoảng thời gian. Điều đó nói lên rằng khi các bộ đƣợc 
sắp xếp trên X (thí dụ nhƣ theo thuật toán group by X 
trong SQL), thì khoảng cách giữa các giá trị Y của hai 
bộ bất kỳ liên tiếp nhau trong khoảng thời gian g. 
Một phụ thuộc tuần tự có điều kiện là một cặp: (X 
→ g
Y, tr) với tr là bộ mẫu. Với mỗi mẫu tr đặc tả một 
dãy giá trị của X để đồng nhất một tập các bộ trên r. 
Phụ thuộc sai khác [12, 13]. Phụ thuộc sai khác trên 
quan hệ r có dạng g: X Y, trong đó X, Y là các tập 
con của tập thuộc tính U; X, Y là các hàm sai khác 
thỏa độ sai khác a: da
2
 D thỏa hai tính chất phản xạ 
và đối xứng của độ đo. 
Bảng 1. So sánh các loại phụ thuộc logic 
Loại phụ 
thuộc logic 
Phép toán 
logic 
Phép 
sánh trị 
Tập 
trị 
Phụ thuộc 
có điều kiện 
 Thỏa tập mẫu 
Tp 
{0,1} 
Phụ thuộc 
hàm mềm 
 = (Với xác 
suất cao) 
[0;1] 
Phụ thuộc 
hàm độ đo 
 Độ đo khoảng 
cách  
[0;1] 
Phụ thuộc 
hàm đối 
sánh 
 Đồng dạng 
trên toán tử 
đối sánh cho 
vế trái và  
cho vế phải 
{0,1} 
Phụ thuộc 
tuần tự 
 Thời khoảng g [a..b] 
Phụ thuộc 
sai khác 
 Hàm sai khác 
 thỏa độ sai 
khác a với hai 
tính chất 
không âm và 
đối xứng 
[0;1] 
Phụ thuộc 
Boole 
dƣơng 
, , , Phép sánh 
đẳng thức (=) 
{0,1} 
Phụ thuộc 
Boole 
dƣơng tổng 
quát 
, , , Thỏa phép 
sánh trị với 
ba tính chất 
phản xạ, đối 
xứng và bộ 
phận. 
{0,1} 
Phụ thuộc 
Boole 
dƣơng đa trị 
, , , Thỏa phép 
sánh trị với 
ba tính chất 
phản xạ, đối 
xứng và bộ 
phận. 
[0;1] 
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 
 -53- 
Phụ thuộc Boole dƣơng tổng quát [14]. Mỗi công 
thức Boole dƣơng f trong P(U) với phép sánh trị là 
một phụ thuộc Boole dương tổng quát (PTBDTQ). 
Quan hệ r trên tập thuộc tính U thỏa PTBDTQ f (tập 
PTBDTQ F) và viết r(f) (r(F)) nếu Tr  Tf (Tr  TF). 
Phụ thuộc Boole dƣơng đa trị [14]. Tập trị Boole 
B = {b1,...,bk} gồm k giá trị thực trong đoạn [0; 1], k ≥ 
2 đƣợc sắp tăng và thỏa các điều kiện sau: 
 0 B, 
  b B 1 b B. 
Với mỗi trị b B ta định nghĩa hàm Ib 
 x B : Ib(x) = 1 nếu x = b, ngoài ra Ib(x) = 0 
Cho U = {x1,...,xn} là tập hữu hạn các biến Boole, 
B là tập trị Boole. Khi đó các công thức Boole đa trị 
(CTBĐT) là các công thức đƣợc xây dựng trên các 
biến của U, các trị trong B , các hàm Ib với b B và 
các phép toán , , , . Mỗi công thức Boole dƣơng 
đa trị f với f (e) =1 thỏa phép sánh trị trên tập trị B 
là phụ thuộc Boole dương đa trị (PTBDĐT). 
V. LỚP CÁC PHỤ THUỘC LOGIC 
Trong [10, 14, 15] đã chỉ ra mối quan hệ giữa một 
số loại phụ thuộc trong cơ sở dữ liệu,và gọi chung 
là lớp các phụ thuộc logic (PTLG). Mỗi phụ thuộc 
trong lớp này chính là một biểu thức Boole trên tập 
hữu hạn các thuộc tính. Thí dụ, phụ thuộc hàm là 
trƣờng hợp riêng của PTBDTQ khi các biểu thức logic 
có dạng hội suy dẫn và các phép sánh trị =. 
V.1. Định lý tƣơng đƣơng 
Cho tập các PTBD F và một PTBD f trên tập thuộc 
tính U. Cho quan hệ r trên tập thuộc tính U. Quan hệ 
r(U) thỏa PTBD f và viết r(f) nếu Tr  Tf, quan hệ r(U) 
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 
quan hệ r(U), r thỏa F kéo theo r thỏa f: 
F├ f  r(U): r(F) r(f) 
Ta nói F suy ra f theo quan hệ có không quá hai bộ 
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: 
F├2 f  r(U), ||r|| 2 : r(F) r(f) 
Định lý 5.1. (Định lý tƣơng đƣơng) [10, 11, 15] 
Cho tập PTBD F và một PTBD f trên U. Ba mệnh 
đề sau là tương đương: 
 F f (suy dẫn logic) 
 F├ f (suy dẫn theo quan hệ) 
 F├2 f (suy dẫn theo quan hệ có không quá 2 bộ) 
V.2. Bài toán thành viên 
Kí hiệu F+ = {f P(U) | F├ f } là tập toàn bộ các 
PTBD đƣợc suy dẫn theo quan hệ từ tập PTBD F. Nếu 
F├ f , có nghĩa f F+ thì f là thành viên của F+. Hiển 
nhiên, nếu f F thì F├ f. Vấn đề đặt ra là ngoài F thì 
F
+
 còn chứa PTBD nào khác? 
Bài toán thành viên [18]: Cho F là tập PTBD và f là 
một PTBD trên U. Hãy xác định F├ f ? Nói cách khác 
là xác định f F+? 
Định lý 5.1 cho thấy việc kiểm tra F├ f tƣơng 
đƣơng với việc kiểm tra suy dẫn logic F f và cũng 
tƣơng đƣơng với việc kiểm tra trên các quan hệ có 
không quá hai bộ. 
Định lý tƣơng đƣơng cũng cho biết bài toán thành 
viên tƣơng đƣơng với bài toán suy dẫn của logic mệnh 
đề trong lớp các phụ thuộc Boole dƣơng. Nếu chọn 
cách kiểm tra F├ f theo quan hệ thì ta phải xây dựng 
2
m
 quan hệ, trong đó m là tích các lực lƣợng của miền 
trị của các thuộc tính. Để xây dựng bảng chân lí T cho 
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 
theo quan hệ là không thể. Do đó, theo định lý tƣơng 
đƣơng, thay vì kiểm tra F├ f theo quan hệ, ta có thể 
chứng minh F f theo logic, cụ thể là vận dụng thuật 
toán hợp giải để chứng minh F f . 
Thuật toán 5.1. (Thuật toán hợp giải) 
Trong logic, bài toán suy dẫn F f đối với tập 
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 
[1] 
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 
 -54- 
Để chứng minh F f ta xét phủ định g = (F f)’ 
 Ff’. Nếu chứng minh đƣợc Ff’ là sai thì F f, 
ngƣợc lại F không suy dẫn đƣợc f. 
Bƣớc 1. Chuẩn hóa CNF. Đƣa g về dạng chuẩn hội 
(CNF) h, tức là viết g dƣới dạng hội của các tuyển cơ 
sở, trong đó mỗi hạng tử của mọi tuyển cơ sở đều là 
các biến đơn hoặc phủ định của biến đơn trong g. Gọi 
thủ tục này là CNF, ta có h = CNF(g). 
Bƣớc 2. Hợp giải. Lần lƣợt thay cặp nhân tử 
(a+B)(a’+C) trong h bằng (B+C) cho đến khi không 
còn thay đƣợc nữa, hoặc gặp hai nhân tử phủ định 
nhau là x và x'. Ta gọi thủ tục này là Unif(h). 
Lƣu ý x  x+0  0+x, nên ta có thể thay (a+B)a’ hoặc 
(a’+B)a bằng B trong quá trình hợp giải. 
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 
F f; ngƣợc lại, với mọi khả năng thay thế nhƣ trên, 
h không bị xóa hết, tức là hợp giải không thành công 
thì kết luận F không suy dẫn ra f. 
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 
viên trong tập F+ ? 
Nếu f F+ thuật toán cho giá trị 1 (true), ngƣợc lại 
thuật toán cho ra giá trị 0 (false). 
Thuật toán 5.2. [18] (Thuật toán thành viên) 
Algorithm Member_ PBD(F, f) 
Input: Tập PTBD F; PTBD f. 
Output: true, if F f ; else false 
Method 
g  Ff’; // gán Ff' cho g 
h  CNF(g) ; 
return Unif(h) =  ; 
End Member_ PBD. 
Mệnh đề 5.1. Bài toán thành viên trong lớp các phụ 
thuộc Boole dương thuộc lớp NP đầy đủ (NPC) [18] 
V.3. Thuật toán bao đóng 
Gọi U là tập các thuộc tính và F là tập PTBD trên 
U, X  U. Ta định nghĩa bao đóng X+ của X là tập các 
thuộc tính sau: 
X
+
 = {a U | X a F+} 
Để tìm bao đóng X+ của X, ta khởi tạo X+ = X sau 
đó vận dụng thuật toán thành viên để xét cho từng 
thuộc tính a U X, nếu X a F+ thì bổ sung thêm 
a vào X+. Tiếp tục quá trình cho đến khi không mở 
rộng thêm X+ đƣợc nữa. 
Để ý rằng nếu F đã đƣợc đƣa về dạng CNF thì điều 
kiện X a F+ sẽ cho ta CNF(F(X a)') = FXa', do 
đó sẽ tƣơng đƣơng với điều kiện Unif(FXa') = . 
Thuật toán 5.3. (Thuật toán tìm bao đóng) 
Algorithm Closure_PBD(X, F) 
Input: Tập PTBD F dạng CNF 
 Tập thuộc tính X  U 
Output: X+ = {a U | X a F+} 
Method 
Y  X; // Y chứa kết quả 
V  U-X; // phần bù của X 
repeat 
Z  Y; 
for each attribute a in V do 
 if Unif(FYa') =  then 
 add a to Y; 
 endif; 
endfor; 
until Y = Z; 
return Y; 
End Closure_PBD. 
Theo mệnh đề 5.1 thì thuật toán tìm bao đóng trong 
lớp các phụ thuộc Boole dƣơng là NP đầy đủ (NPC). 
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+? 
Ta có F = (b’+c)(a’+b) hiện ở dạng CNF. 
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 
 -55- 
Đặt Y = X = ab, V = U-X = cd. Xét các thuộc tính 
trong V. 
Với c V, ta có Unif(FXc’) = (b’+c)(a’+b)abc’ = 
(c+a')abc' = bcc' = . Vậy Y = abc. 
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 
cùng ta thu đƣợc X+ = (ab)+ = abc. 
V.4. Thuật toán tìm khóa 
Cho F là tập PTBD trên U. Tập K  U đƣợc gọi là 
khóa nếu 
- K+ = U 
- a K: (K a)+ ≠ U 
Để tìm tập khóa K, trƣớc tiên đặt K = U. Sau đó rút 
gọn K bằng cách xét từng thuộc tính a trong K, nếu 
(K a)+ = U thì loại a ra khỏi K. 
Do ta luôn bảo toàn bất biến K+ = U nên điều kiện 
(K a)+ = U tƣơng đƣơng với điều kiện (K a) a. Điều 
kiện này lại tƣơng đƣơng với điều kiện 
Unif(F(K a)a') = . 
Thuật toán 5.4. (Thuật toán tìm khóa) 
Algorithm Key_PBD(U, F) 
Input: Tập thuộc tính U; Tập PTBD F dạng CNF 
Output: K  U: 
- K+ = U 
- a K: Unif(F(K - a)a') = Ø 
Method 
K  U; 
for each attribute a in K do 
if Unif(F(K - a)a') = Ø then 
delete a from K; 
 endif 
endfor 
return K; 
End Key_PBD. 
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). 
Thí dụ 5.2. Cho tập các thuộc tính U ={a, b, c, d}, tập 
phụ thuộc Boole dƣơng F = {b’+c, a’+b}, hãy xác 
định một khóa K trong quan hệ r? 
Trƣớc hết ta đƣa F về dạng CNF, F = 
(b’+c)(a’+b). 
Áp dụng thuật toán tìm khóa, đặt K = U = abcd. 
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: 
Xét a: K-a = bcd. Ta có: Unif(Fbcda’) = 
(b’+c)(a'+b)bcda’ = (a'+c)bcda' ≠ . Vậy, K không 
thay đổi, K = abcd. 
Xét b: K-b = acd. Ta có: Unif(Facdb’) = 
(b’+c)(a'+b)acdb’ = (b'+c)bcdb' = . Vậy, K = acd. 
Xét c: K-c = ad. Ta có Unif(Fadc') = (b’+c)(a'+b)adc’ 
= (b'+c)bdc' = cdc' = . Vậy, K = ad. 
Xét d: K-d = a. Ta có Unif(Fad') = (b'+c)(a'+b)ad' = 
(b'+c)bd' = cd' ≠ . Vậy, K không thay đổi. Cuối 
cùng ta thu đƣợc khóa k = ad. 
VI. KẾT LUẬN 
Thuật toán hợp giải có thể đƣợc cài đặt nhƣ một 
tiện ích trong các thƣ viện của các ngôn ngữ lập trình 
logic nhƣ Prolog, P#, Lisp. Nghiên cứu các phụ thuộc 
Boole dƣơng theo tiếp cận của logic hình thức cho 
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 
thống nhất. Các kết quả thu đƣợc trong bài này có thể 
đƣợc vận dụng trong lĩnh vực khai thác tri thức từ các 
tập dữ liệu lớn. 
TÀI LIỆU THAM KHẢO 
[1] BAADER F., SNYDER W., “Hanbook of Automated 
Reasonning”. Ed. Alan Robinson and Andrei Voronkov, 
Elsevier Science Publishers B.V, 2001. 
[2] BOHANNON P., FAN W., GEERTS F., JIA X., 
KEMENTSIETSIDIS A., (2007), “Conditional 
functional dependencies for data cleaning”, In ICDE, 
pp.746-755. 
[3] BRAVO L., FAN W., MA S., (2007), “Extending 
dependencies with condition”, In VLDB, pp.243-254. 
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 
 -56- 
[4] DAVID MAIER, V. M MEGLER, KRISTIN TUFTE 
(2014), Challenges for Dataset Search, “Database 
System for Advanced Applications”, Lecture Notes in 
Computer Science Volum 8421, 1-15. 
[5] FAN W., GEERTS F., LAKSHMANAN L. V. S., 
XIONG M., (2009), “Discovering conditional 
functional dependencies”, In ICDE, pp. 1231-1234. 
[6] FAN W., LI J., JIA X., MA S., (2009), “Reasoning 
about record matching rules”, PVLDB. 
[7] GOLAB L., KARLOFF H., KORN F., SAHA A., 
SRIVASTAVA D., (2009), “Sequential 
dependencies”, PVLDB, 2(1), pp.574-585. 
[8] ILYAS I. F., MARKL V., HAAS P. J., BROWN P., 
ABOULNAGA A., (2004), “Cords: Automatic 
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. 
[16] NGUYỄN XUÂN HUY, ĐÀM GIA MẠNH, VŨ THỊ 
THANH XUÂN, KIM LAN HƢƠNG (2001), “Về một 
lớp công thức logic suy dẫn”, Tạp chí Tin học và điều 
khiển học, 17 (4), tr. 17-22. 
[17] NGUYỄN XUÂN HUY, ĐOÀN VĂN BAN, ĐÀM GIA 
MẠNH, NGUYỄN THẾ DŨNG (2001), “Về mối liên hệ 
giữa suy diễn phụ thuộc hàm và suy diễn logic”, Tạp chí 
Tin học và điều khiển học, 17(4), tr.11-16. 
[18] TRƢƠNG THỊ THU HÀ, “Độ phức tạp của các thuật 
toán chuẩn hóa phụ thuộc Boole dương", Tạp chí 
Công nghệ thông tin và truyền thông, ISSN 1859 – 
3526, Tập V-1, Số 12(32), 12-2014. 
Nhận bài ngày: 29/02/2016 
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 
 -57- 
SƠ LƢỢC VỀ TÁC GIẢ 
TRƢƠNG THỊ THU HÀ 
Sinh năm 1979 tại Nghệ An. 
Tốt nghiệp Cử nhân CNTT tại 
Trƣờng ĐH Sƣ phạm Hà Nội năm 
2000, Thạc sĩ CNTT tại Trƣờng 
ĐH Công nghệ, ĐH Quốc gia Hà 
Nội năm 2006. Đang là nghiên 
cứu sinh tại Khoa CNTT, Học 
viện Kỹ thuật Quân sự. 
Hiện công tác tại Khoa CNTT, trƣởng Đại học Kinh 
doanh và Công nghệ Hà Nội. 
Lĩnh vực nghiên cứu: Cơ sở dữ liệu, Công nghệ phần 
mềm. 
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 
NGUYỄN XUÂN HUY 
Sinh năm 1944, Hải Phòng. 
Tốt nhiệp Cử nhân Toán, ĐH Sƣ 
phạm Leningrad (Liên Xô) năm 
1973, Tiến sỹ CNTT năm 1982, 
Tiến sỹ khoa học CNTT, Viện 
Hàn lâm Khoa học Liên Xô năm 
1990. 
Là Trƣởng Phòng Cơ sở dữ liệu 
và Lập trình, Viện CNTT, Viện Hàn lâm KH&CN 
Việt Nam từ năm 1997-2009. 
Hƣớng nghiên cứu: Cơ sở dữ liệu và Công nghệ phần 
mềm. Email: nxhuy564@gmail.com