1
A . M Ở Đ Ầ U
Cơ sở dữ liệu là hạt nhân không thể thiếu trong các hệ thống,
trong đó có các hệ thống máy tính và truyền thông. Cùng với sự phát
triển không ngừng của Internet, việc trao đổi thông tin và truyền dữ
liệu trên mạng là một nhu cầu tất yếu đặt ra. Với khối lượng thông tin
lớn được trao đổi, dữ liệu lưu trữ phân tán, các yêu cầu truy xuất có
thể xảy ra ở nhiều nơi, việc đảm bảo tính nhất quán, tránh dư thừa dữ
liệu, dị thường khi thêm, xóa bộ cũng như các bài toán liên quan đến
tổ chức, xử lý, nén dữ liệu,… luôn là vấn đề được quan tâm.
Bên cạnh yêu cầu đảm bảo dữ liệu không bị mất mát trên đường
truyền, một vấn đề khác đặt ra là tổ chức, thiết kế, quản lý dữ liệu sao
cho việc lưu trữ tốn ít bộ nhớ nhất, khai thác hiệu quả và thời gian
truyền dữ liệu được giảm tối đa.
Để lưu trữ, quản lý và khai thác dữ liệu ta có thể dùng nhiều mô
hình tổ chức dữ liệu khác nhau như: mô hình phân cấp, mô hình
mạng, mô hình quan hệ… Trong các mô hình đó, mô hình quan hệ
nhận được sự quan tâm của nhiều nhóm nghiên cứu vì được xây dựng
trên một cơ sở toán học chặt chẽ, áp dụng rộng các công cụ đại số và
logic. Trong mô hình quan hệ, việc nghiên cứu các ràng buộc dữ liệu
hay còn gọi là các phụ thuộc dữ liệu đóng vai trò quan trọng trong
việc mô tả thế giới thực, phản ánh ngữ nghĩa dữ liệu của cơ sở dữ
liệu. Việc nghiên cứu này là một vấn đề cần thiết, có ý nghĩa và giữ
một vai trò quan trọng trong việc đảm bảo tính nhất quán của dữ liệu.
Mục đích của việc nghiên cứu này là để bảo đảm cho dữ liệu trong cơ
sở dữ liệu không mâu thuẫn, phản ánh đúng thế giới thực Công trình được hoàn thành tại:
Học viện Công nghệ Bưu chính Viễn thông
Người hướng dẫn khoa học:
Hướng dẫn 1: PGS.TSKH NGUYỄN XUÂN HUY
Hướng dẫn 2: PGS.TS TỪ MINH PHƯƠNG Phản biện 1: PGS. TS Đoàn Văn Ban
Phản biện 2: PGS. TS Nguyễn Kim Anh
Phản biện 3: PGS. TS Nguyễn Hải Châu
Luận án được bảo vệ trước Hội đồng chấm luận án cấp Học viện tại
Học viện Công nghệ Bưu chính viễn thông
Vào hồi: 14 giờ, ngày 17 tháng 01 năm 2013

03/12/2010, tr.31-38.
[3]

Bùi Đ
ức Minh, L
ương Nguy
ễn Ho
àng Hoa (2011), “H
ệ sinh cân
bằng và bài toán biểu diễn cơ sở hệ sinh ánh xạ đóng”, Chuyên
san các công trình nghiên cứu, phát triển và ứng dụng CNTT-
TT, Tạp chí Công nghệ Thông tin & Truyền thông, Tập V-1, Số
5 (25), tr.15-21.
[4]

Nguy
ễn Xuân Huy, L
ê Th
ị Mỹ Hạnh, L
ương Nguy
ễn Ho
àng
Hoa, Bùi Đức Minh, Nguyễn Đức Vũ (2007), “Thiết kế cơ sở
dữ liệu theo tiếp cận dịch chuyển lược đồ quan hệ”, Kỷ yếu Hội
thảo Khoa học Quốc gia “Một số vấn đề chọn lọc của Công
nghệ thông tin và Truyền thông”, Đại Lải, 14-15/09/2007, NXB
KHTN, tr.499-506.
[5]

Hà Quang Th

B = {0,1}. Khi đó các công thức Boole CTB) là các công thức được
xây dựng trên các biến của U, các hằng 0/1 và các phép toán , , 
. Ký hiệu LU) là tập các CTB xây dựng trên tập các biến U.
Hai phép gán trị đặc biệt được quan tâm là phép gán trị đơn vị e =
1,1, ,1) và phép gán trị không z = 0,0, ,0).
Định nghĩa 1.3.3
Bảng chân lý của f, ký hiệu là T
f
, là tập các phép gán trị v sao cho fv)
nhận giá trị 1, T
f
= {v  B
n
| fv) =1}
Khi đó bảng chân lý T
F
của tập hữu hạn các công thức F trên U,
chính là giao của các bảng chân lý của mỗi công thức thành viên
trong F,
TT
f
Ff
F




Ta có, v  T
F
khi và chỉ khi f F: fv) = 1.

cạnh ứng dụng của lớp phụ thuộc này.
- Nghiên cứu về ánh xạ đóng và tổng quát hóa một số kết quả về
lớp các phụ thuộc Boole dương theo ngôn ngữ ánh xạ đóng. Đề
xuất công cụ toán học để biểu diễn ánh xạ đóng, nâng cao hiệu
quả tính toán khi sử dụng công cụ này.
Những đóng góp của luận án
Luận án đã giải quyết được các vấn đề sau:
3

(1) Đề xuất, xây dựng khái niệm và một số tính chất của cơ sở hệ
sinh ánh xạ đóng. Phát biểu và chứng minh các định lý, bổ đề
về biểu diễn cơ sở của hệ sinh ánh xạ đóng thông qua phép
thu gọn hệ sinh. Đề xuất một dạng biểu diễn cơ sở hệ sinh
ánh xạ đóng với kỹ thuật thu gọn hệ sinh theo vế trái tối tiểu
của tập luật sinh.
(2) Đề xuất một lớp hệ sinh đặc biệt gọi là hệ sinh cân bằng để
biểu diễn ánh xạ đóng và thu được một số kết quả ban đầu
nâng cao hiệu quả tính toán khi sử dụng công cụ này.
(3) Đề xuất khái niệm phủ, phủ không dư và thuật toán tìm phủ
không dư cho lớp phụ thuộc Boole dương tổng quát. Đề xuất
khái niệm bao đóng và thuật toán giải bài toán thành viên
trong trường hợp tổng quát của lớp phụ thuộc Boole dương
tổng quát.
(4) Xác định điều kiện cần và đủ để biểu diễn phụ thuộc Boole
dương tổng quát dưới dạng hội các công thức suy dẫn.
(5) Xây dựng thuật toán tìm tập PTBDTQ thỏa mãn quan hệ R
cho trước.
Bố cục của luận án
Về cấu trúc, luận án được trình bày trong 3 chương, có phần
mở đầu, phần kết luận, phần mục lục, phần các công trình đã công bố

2
, , A
n
} khác rỗng (n 1). Các phần tử
của U được gọi là thuộc tính. Ứng với mỗi thuộc tính A
i
U, i =
1,2, ,n có một tập chứa ít nhất hai phần tử dom(A
i
) được gọi là miền
trị của thuộc tính A
i
. Gọi D là hợp của các dom(A
i
), i = 1,2, ,n. Một
quan hệ R với các thuộc tính U, ký hiệu là R(U), là một tập các ánh
xạ t: UD sao cho với mỗi A
i
U ta có
t(A
i
) dom(A
i
). Mỗi ánh xạ được gọi là một bộ của quan hệ R.
1.2. Phụ thuộc hàm
Định nghĩa 1.2.1
9

hạn, F là tập các luật sinh trên U.
Định nghĩa 2.3.2

Ta gọi f

là ánh xạ cảm sinh của hệ sinh AXĐ

, X là vật, f

(X) là
ảnh của ánh xạ cảm sinh f

. Dễ thấy f

(X) là tập bao (nhỏ nhất) của X
trong hệ sinh AXĐ

.
Định lý 2.3.1
1. Với mỗi hệ sinh

= (U,F), ánh xạ cảm sinh f

là AXĐ trên U.
2. Với mỗi AXĐ h trên U, tồn tại một hệ sinh

= (U,F) thỏa tính
chất :
 X  U: f

(X) = h(X)
Định lý 2.3.2
Cho hệ sinh AXĐ

d
i
 B thoả ba tính chất sau:
i) Tính phản xạ: ad
i
:

i
a,a) =1
ii) Tính đối xứng: a,b  d
i
:

i
a,b) =

i
b,a)
iii) Tính bộ phận: a, b  d
i
:

i
a,b) = 0.
Quan hệ đẳng thức là trường hợp riêng của quan hệ trên.
Định nghĩa 1.5.2
Giả sử các ánh xạ

i
đã được xác định trên mỗi miền trị d


n
u.A
n
,v.A
n
))
Với mỗi quan hệ R  RELU) ta gọi bảng chân lý của quan hệ R là
tập
T
R
= {

u,v)  u, v  R}

Định nghĩa 1.5.3
Mỗi công thức Boole dương trong PU) là một phụ thuộc Boole
dương tổng quát PTBDTQ).
Định lý tương đương
Cho tập PTBDTQ F và một PTBDTQ f. Ba mệnh đề sau là tương
đương,
i) F ╞ f suy dẫn logic)
ii) F ├ f suy dẫn theo quan hệ)
iii) F ├
2
f suy dẫn theo quan hệ có không quá 2 bộ)
7

1.6. Phụ thuộc Boole dương đa trị
Định nghĩa 1.6.1

, ,x
n
} 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 I
b
với b  B
và các phép toán , ,  Ký hiệu MVLU) là tập các CTBĐT xây
dựng trên tập các biến U và tập trị B cho trước, trong đó U gồm n
phần tử và B gồm k phần tử, n  1, k  2.
Ch ươ ng 2- Ánh xạ đ ón g và hệ s uy dẫ n
2.1 Ánh xạ đóng
Định nghĩa 2.1.1
8

Cho tập U hữu hạn. Ánh xạ f: SubSet(U)  SubSet(U)

được gọi là
đóng trên tập U nếu với mọi tập con X, Y  U thỏa các tiên đề sau
đây:
(i) Tính phản xạ: f(X)  X,
(ii) Tính đồng biến: Nếu X  Y thì f(X)  f(Y),
(iii) Tính lũy đẳng: f(f(X)) = f(X).
2.2. Giàn giao và điểm bất động của ánh xạ đóng
Định nghĩa 2.2.1
Cho AXĐ f trên tập U hữu hạn. Tập con X  U được gọi là điểm bất
động (hay còn gọi là tập đóng) của AXĐ f nếu f(X) = X .
Định nghĩa 2.2.4
Giả sử G là một họ các tập con đóng với phép giao của tập hữu hạn
U, cụ thể là giao của mọi họ con trong G đều cho kết quả là một tập


(C8) Nếu hệ sinh AXĐ α = (U,F) là HSCB thì  A  U, ta có
α\A cũng là HSCB. Tính chất này hiển nhiên đúng.
Kết quả của luận án về phép thu gọn hệ sinh và biểu diễn cơ sở
hệ sinh ánh xạ đóng theo cơ sở hệ sinh cân bằng được trình bày trong
dưới đây.
Định lý 2.4.1
Mọi hệ sinh AXĐ α = (U,F) đều đưa được về dạng cân bằng
β = (V,G) thỏa tính chất: Base(α) = U
I
 Base(β)
Trong đó U
I
là giao các cơ sở của α với độ phức tạp tuyến tính theo
chiều dài dữ liệu vào O(n
2
m), trong đó n là số lượng phần tử trong U,
m là số lượng luật sinh trong F.
Biểu diễn cơ sở hệ sinh AXĐ theo cơ sở HSCB
Cho hệ sinh AXĐ α = (U,F) với U ={a
1
, a
2
,…, a
n
}, F = {L
i
R
i
 i=1,

I
R’)
Bước 2:
Xác định α’ = (U’,F’) = α\C với U’= U\C, F’ = {L
i
\C  R
i
\C 
i = 1, 2, …, m}
Loại khỏi F’ những luật sinh có dạng   ,   B, B  
(B

).
Thực hiện nhóm những luật sinh trong F’ có vế trái giống
nhau, ta thu được hệ sinh cân bằng

= (U’, F’).
Bước 3:
Tìm cơ sở của hệ sinh cân bằng


- Xác định tập L

là tập chứa các vế trái của F’.
10

f

(X) = X f


là một phân hoạch của U.
Công thức tìm giao các cơ sở của hệ sinh ánh xạ đóng được trình bày
theo định lý sau:
Định lý 2.3.3
Cho hệ sinh AXĐ

= (U,F) với n phần tử trong tập U và m luật sinh
trong F. Khi đó có thể xác định giao các cơ sở bằng một thuật toán
tuyến tính với độ phức tạp O(mn) qua công thức

FRL
I
LRUU

 )\(\

Bổ đề 2.3.1
Cho hai hệ sinh AXĐ

= (U,F),

= (V,G) và X  U. Biết

=

\X.
Khi đó:
(i) Nếu M là siêu cơ sở của

thì M\X là siêu cơ sở của


= (V,G) và tập X  U
o
. Biết

=

\X. Khi đó: Base(

) = Base(

)
11

Định nghĩa 2.3.5
Cho ,   SubSet(U) và M, P  SubSet(U). Ta định nghĩa phép
toán  trên SubSet(U) như sau:
- M  P = MP (hợp của hai tập con M và P)
- M   = {MX | X  } và
-    = {XY | X  , Y  }
Các định lý, bổ đề và hệ quả dưới đây sau trình bày cách biểu diễn cơ
sở của hệ sinh ánh xạ đóng theo phép thu gọn hệ sinh.
Định lý 2.3.4
Nếu thu gọn hệ sinh AXĐ

= (U, F) theo tập X  U để nhận được
hệ sinh

=


) = Y  Base(

).
Định nghĩa 2.3.7
Cho hệ sinh

=(U, F). Ta ký hiệu ML(F) là tập các vế trái cực tiểu
của F, ML(F) = MIN {LS(f) | fF}
Bổ đề 2.3.3
Cho hệ sinh AXĐ

=(U, F). Nếu L  ML(F) thì L  Base(

) khi và
chỉ khi f

(L)

= U.
Kết quả của luận án về dạng biểu diễn cơ sở hệ sinh ánh xạ đóng theo
phép thu gọn hệ sinh với vế trái tối tiểu của tập luật sinh được trình
bày qua định lý, bổ đề dưới đây.
Định lý 2.3.5
Cho hệ sinh AXĐ

=(U, F). Khi đó mọi cơ sở K của

đều biểu diễn
12


chất (C1)-(C4) sau đây:
(C1) Hợp các vế trái, vế phải của các luật sinh trong F đúng
bằng tập U: LS(F) = RS(F) = U
(C2) F không chứa các luật sinh tầm thường, tức là các luật
sinh có vế trái chứa vế phải:  X,Y  U: X  Y  (X  Y  F)
(C3) Hai vế trái và phải của mọi luật sinh trong F rời nhau
(không giao nhau): f  F: LS(f)  RS(f) = 
(C4) Các vế trái của mọi luật sinh trong F khác nhau đôi một:
 f, g  F: LS(f) = LS(g)  f = g
Ngoài các tính chất (C1)-(C4) ở trên, hệ sinh cân bằng (HSCB) còn
có một số tính chất sau:
(C5) Nếu tập luật sinh F trong hệ sinh AXĐ α = (U,F) thỏa
C2-C4 và chỉ có một luật sinh thì α không thể là HSCB.
(C6) Từ tính chất C5 ta suy ra hệ sinh AXĐ chỉ có một thuộc
tính thì không thể là HSCB.
(C7) Trong HSCB

= (U,F), giao các cơ sở U
I
= .
17

EndUnification.
Theo giả thiết F là tập các PTBDTQ do đó trước hết cần đưa F về
dạng chuẩn hội và thực hiện các bước hợp giải đến mức tối đa.
Thuật toán Reduction dưới đây thực hiện nhiệm vụ trên.
Thuật toán 3.1.3
Algorithm Reduction
Function: Thu gọn tập PTBDTQ
Input: Tập PTBDTQ F

2
, …, L
k
}. Lần lượt tính A = f


(L
i
), i = 1, 2,
…, k.
+ Nếu A = U thì L
i
 Base(

).
+ Nếu A

U thì ta tiếp tục xét hệ sinh cân bằng

=

\ A.
+ Lặp lại bước 3 cho hệ sinh cân bằng

.
Giả sử đến một lúc nào đó thì ta xác định được Base(

). Để bổ
sung các phần tử cho Base(


thì
L
i
K
j
 Base(

).
Bước 4: Xác định Base(

) = U
I
 Base(

)
Ch ươ ng 3 - Phát triển lớ p cá c p hụ th uộc Bo ole
dư ơng và ứ ng d ụng án h xạ đón g, h ệ s uy d ẫn tro n g
cơ sở dữ li ệu
3.1. Phát triển lớp các phụ thuộc Boole dương tổng quát
Bài toán suy dẫn cho phụ thuộc Boole dương tổng quát được phát
biểu như sau:
Cho LĐQH a =

U ,F ), F là tập các PTBDTQ và một PTBDTQ f.
Xác định f F
+
(hay F╞ f) hay không, trong đó F
+
là bao đóng của
tập PTBDTQ F ?

k
với mỗi nhân tử C
i
là tổng của
các biến và hằng 0/1.
2. Thực hiện các bước hợp giải đến khi không thể biến đổi C
được nữa:
 Tìm hai nhân tử C
i
và C
j
có dạng C
i
= (p  x) và C
j
= (q
 x); Nếu tìm được thì thay C
i
và C
j
trong C bằng nhân
tử (p  q).
3. Kết luận: Nếu C =  thì công thức E được chứng minh;
ngược lại E không phải là công thức hằng đúng.
Thuật toán giải bài toán trên được thể hiện dưới dạng các thành phần
theo kiến trúc sau :
Gọi công thức chuẩn hội C là khả hợp nếu sau khi thực hiện bước 2
của sơ đồ thuật toán trên ta thu được công thức rỗng; ngược lại, kết
luận C là không khả hợp.
Thuật toán Resolution dưới đây chứng minh công thức dương E là

Tìm hai nhân tử trong C có dạng
C
i
= (p  x) và C
j
= (q  x);
if (tìm được)
Thay C
i
và C
j
trong C bằng (p  q)
else break;
endif;
endwhile;
return C;
21

miền trị d
i
của các thuộc tính A
i
trong tập U= {A
1
,A
2
, ,A
n
}, 1  i  n
thì bảng chân lý T

n
))
Bài toán 3.2.3
Cho quan hệ R trên tập thuộc tính U. Xây dựng tập PTBDTQ thỏa
mãn R.

Thuật toán BD(R) tìm tập PTBDTQ F thỏa mãn quan hệ R cho trước
như dưới đây.
Algorithm BD
Input: - Quan hệ R trên U
Output: - Tập PTBDTQ BD(R).
Method
1. Xây dựng bảng T
R
;
2. Làm đóng T
R
thu được bảng
T:=Closed&_GPBD(T
R
);
3. G := DF(T);
4. F := Nonredundant_GPBD(G);
return F;
End BD.
Từ kết quả của bài toán BD(R) ta suy ra hệ quả 3.2.4 dưới đây.
Hệ quả 3.2.4
Với mỗi quan hệ RU luôn tìm được tập PTBDTQ F trên U thỏa
mãn quan hệ R.
Các kết quả về lớp phụ thuộc Boole dương tổng quát được nghiên

= T
F

2) G có dạng không dư: gG: G \{g} ≢ G
Thuật toán Nonredundant_GPBD dưới đây tìm phủ không dư của tập
PTBDTQ.
Thuật toán 3.1.6
Algorithm Nonredundant_GPBD
Input:- Tập PTBDTQ F
Output: - Một phủ không dư G của F
 G  F hay T
G
= T
F



g  G: G\{g} ≢ G
Method
19

G:=F;
for each g in F do
if Member_GPBD(G\{g},g)then
G:=G\{g};
endif;
endfor;
return G;
End Nonredundant_GPBD.
Định nghĩa 3.1.6

R
= T
F
.
Mệnh đề 3.1.2
20

Với các ánh xạ 
i
, 1
i n
 
, được xác định trước thì quan hệ
Armstrong đối với tập F các PTBDTQ cho trước không phải luôn
luôn tồn tại.
3.2.B iểu di ễn p h ụ th uộc Bo ol e d ươ ng tổn g quá t
dư ới dạn g h ội s u y d ẫn
Định nghĩa 3.2.1
Cho V là tập các phép gán trị trên U. Với hai phép gán trị u,v  V ta
xét phép toán nhân, ký hiệu là u & v, như là phép nhân logic trên các
thành phần tương ứng của u và v. Cụ thể là, nếu
u = (u
1
,u
2
, ,u
n
) và v = (v
1
,v

n
: g(u) = g(v) = 1  g(u&v) = 1.
Định nghĩa 3.2.3
Cho quan hệ R trên tập thuộc tính U. Với quan hệ đối sánh giữa các
bộ của R thỏa điều kiện ánh xạ

i
: d
i
d
i
 B được xác định trên mỗi
22

3.3. Ứng dụng ánh xạ đóng và hệ suy dẫn trong CSDL
Vận dụng các kết quả lý thuyết chung về các AXĐ ta có thể nhận
được các kết quả liên quan đến các LĐQH đã công bố trước đây như
bao đóng, khóa và phản khóa. Toán tử lấy bao đóng của tập các thuộc
tính, tập phụ thuộc Boole dương tổng quát cũng được chứng minh là
một ánh xạ đóng
Hệ sinh ánh xạ đóng và các khái niệm liên quan được trình bày trong
chương 2 cũng có thể ứng dụng để giải quyết một số lớp bài toán liên
quan đến hệ suy dẫn.
C. KẾT LUẬN VÀ KIẾN NGHỊ HƯỚNG PHÁT TRIỂN
1. Kết luận
Luận án tập trung nghiên cứu, phát triển một số vấn đề liên quan
đến lớp phụ thuộc Boole dương tổng quát và ánh xạ đóng – công cụ
để mô tả và phản ánh lớp phụ thuộc này. Cụ thể một số đóng góp mới
của luận án liên quan đến các nội dung nghiên cứu là:
1. Ánh xạ đóng và hệ sinh ánh xạ đóng: Phát biểu và chứng minh