PHÁT TRIỂN MỘT SỐ PHỤ THUỘC
LOGIC TRONG CƠ SỞ DỮ LIỆU
1
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
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ƯƠNG NGUYỄN HOÀNG HOA
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.
PHÁT TRIỂN MỘT SỐ PHỤ THUỘC
LOGIC TRONG CƠ SỞ DỮ LIỆU
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
Chuyên ngành: Truyền dữ liệu và mạng máy tính
Mã ngành:
62 48 15 01
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à
TÓM TẮT LUẬN ÁN TIẾN SỸ KỸ THUẬT
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
HÀ NỘI – 2013
DANH MỤC CÁC CÔNG TRÌNH CÔNG BỐ
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
[1]
[2]
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
[3]
[4]
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
[5]
Có thể tìm hiểu luận án tại:
1. Thư viện Quốc gia
2. Thư viện Học viện Công nghệ Bưu chính Viễn thông
[6]
Bùi Đức Minh, Lương Nguyễn Hoàng Hoa, Cao Tùng Anh,
Nguyễn Gia Như, Nguyễn Xuân Huy (2010), “Biểu diễn cơ sở
của hệ sinh ánh xạ đóng”, Kỷ yếu Hội thảo Quốc gia "Một số
vấn đề chọn lọc của Công nghệ thông tin", Hưng Yên, 1920/08/2010, NXB KHKT Hà Nội, tr.51-58.
Bùi Đức Minh, Lương Nguyễn Hoàng Hoa, Cao Tùng Anh,
Nguyễn Minh Hiệp, Bùi Duy Tuấn, Nguyễn Xuân Huy (2010),
“Ánh xạ đóng và ứng dụng”, Kỷ yếu Hội thảo khoa học Công
nghệ Thông tin năm 2010, Trường Đại học Đà lạt, Đà Lạt,
03/12/2010, tr.31-38.
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 CNTTTT, Tạp chí Công nghệ Thông tin & Truyền thông, Tập V-1, Số
5 (25), tr.15-21.
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.
Hà Quang Thụy, Nguyễn Ngọc Hóa, Nguyễn Viết Thế, Lương
Nguyễn Hoàng Hoa (2011), “Giải pháp lọc nội dung hỗ trợ
quản lý và đảm bảo an toàn – an ninh trên Internet”, 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ố 6
(26), tr.260-270.
Luong Nguyen Hoang Hoa (2011), “Some results concerning
Generalized Positive Boolean Dependencies in relational
database”, Internatinal Journal of Computer Electrical
Engineering (IJCEE), Vol 6, 12/2011.
5
2
Cho tập thuộc tính U. Một phụ thuộc hàm (PTH) trên U là biểu thức
Trong quản lý các cơ sở dữ liệu, phụ thuộc dữ liệu được hiểu là
dạng : f: XY ; X,Y U
những mệnh đề mô tả các ràng buộc mà dữ liệu phải thỏa mãn trong
Nếu f: XY là một phụ thuộc hàm trên U thì ta nói tập thuộc tính Y
thực tế. Nhờ những mô tả phụ thuộc này mà hệ quản trị cơ sở dữ liệu
phụ thuộc vào tập thuộc tính X, hoặc tập thuộc tính X xác định hàm
có thể quản lý tốt được chất lượng dữ liệu. Phụ thuộc dữ liệu đầu tiên
tập thuộc tính Y.
được Codd tác giả của mô hình dữ liệu quan hệ đặt nền móng từ
1.3. Các công thức B ool e
những năm 70 với khái niệm phụ thuộc hàm. Sau đó một loạt tác giả
Định nghĩa 1.3.1
khác đã tiếp tục phát triển các dạng phụ thuộc bậc cao, phụ thuộc mờ
Cho U = {x1,...,xn} là tập hữu hạn các biến Boole, B là tập trị Boole,
cũng như xây dựng các hệ tiên đề cho các lớp phụ thuộc - tức là đặt
B = {0,1}. Khi đó các công thức Boole CTB) là các công thức được
nền móng cơ sở lý thuyết về phụ thuộc dữ liệu. Một trong số những
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 , ,
lớp phụ thuộc quan trọng đã được phát triển, đề xuất sau này là phụ
. Ký hiệu LU) là tập các CTB xây dựng trên tập các biến U.
thuộc Boole dương.
Hai phép gán trị đặc biệt được quan tâm là phép gán trị đơn vị e =
Với mong muốn phát triển, mở rộng lý thuyết về phụ thuộc
1,1,...,1) và phép gán trị không z = 0,0,...,0).
dữ liệu và ứng dụng. Mục tiêu của luận án là tiếp tục nghiên cứu,
Định nghĩa 1.3.3
phát triển một số vấn đề liên quan đến lớp phụ thuộc Boole dương và
Bảng chân lý của f, ký hiệu là Tf, là tập các phép gán trị v sao cho fv)
n
công cụ để mô tả, phản ánh lớp phụ thuộc này. Đây là vấn đề nghiên
nhận giá trị 1, Tf = {v B | fv) =1}
cứu đã và đang được nhiều nhà khoa học quan tâm.
Khi đó bảng chân lý TF của tập hữu hạn các công thức F trên U,
Mục đích nghiên cứ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,
TF T f
Nghiên cứu các lớp phụ thuộc Boole dương trong đó tập trung
chủ yếu việc vào việc đề xuất, phát triển một số khái niệm, tính
f F
Ta có, v TF khi và chỉ khi f F: fv) = 1.
chất của lớp phụ thuộc Boole dương tổng quát và một số khía
1. 4. Ph ụ th u ộc B ool e d ư ơ n g
cạnh ứng dụng của lớp phụ thuộc này.
Định nghĩa 1.4.1
Công thức f LU) được gọi là công thức Boole dương CTBD) nếu
fe) =1, trong đó e là phép gán trị đơn vị, e = (1,1,...,1).
Ký hiệu PU) là tập toàn bộ các công thức dương trên U.
Định nghĩa 1.4.2
Mỗi công thức Boole dương trong PU) được gọi là một phụ thuộc
Boole dương PTBD). Dễ thấy phụ thuộc hàm là một PTBD.
-
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
4
(1) Đề xuất, xây dựng khái niệm và một số tính chất của cơ sở hệ
là ánh xạ đóng. Trong chương cũng trình bày một số kết quả mới của
sinh ánh xạ đóng. Phát biểu và chứng minh các định lý, bổ đề
luận án liên quan đến hệ sinh ánh xạ đóng như biểu diễn cơ sở hệ
về biểu diễn cơ sở của hệ sinh ánh xạ đóng thông qua phép
sinh ánh xạ đóng qua hợp vế trái tối tiểu của hệ sinh cho trước và cơ
thu gọn hệ sinh. Đề xuất một dạng biểu diễn cơ sở hệ sinh
sở của hệ sinh sau khi thu gọn. Đề xuất lớp hệ sinh mới là hệ sinh cân
ánh xạ đóng với kỹ thuật thu gọn hệ sinh theo vế trái tối tiểu
bằng với mục đích nâng cao hiệu quả trong quá trình tính toán và một
của tập luật sinh.
dạng biểu diễn cơ sở của hệ sinh ban đầu thông qua cơ sở hệ sinh cân
(2) Đề xuất một lớp hệ sinh đặc biệt gọi là hệ sinh cân bằng để
bằng. Chương 3 trình bày một số khái niệm và kết quả của luận án
biểu diễn ánh xạ đóng và thu được một số kết quả ban đầu
liên quan đến việc tìm bao đóng, phủ, phủ không dư, bài toán thành
nâng cao hiệu quả tính toán khi sử dụng công cụ này.
viên và thể hiện của lớp phụ thuộc Boole dương tổng quát
(3) Đề xuất khái niệm phủ, phủ không dư và thuật toán tìm phủ
(PTBDTQ). Biểu diễn phụ thuộc Boole dương tổng quát dưới dạng
không dư cho lớp phụ thuộc Boole dương tổng quát. Đề xuất
hội các công thức suy dẫn và thuật toán xây dựng xây dựng tập
khái niệm bao đóng và thuật toán giải bài toán thành viên
PTBDTQ thỏa mãn quan hệ R cho trước cũng được trình bày trong
trong trường hợp tổng quát của lớp phụ thuộc Boole dương
chương này. Một số ứng dụng của ánh xạ đóng và hệ suy dẫn trong
tổng quát.
cơ sở dữ liệu cũng được giới thiệu trong chương này.
(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
B. NỘI DUNG
Chương 1 - Tổng quan về các phụ thuộc logic trong cơ sở dữ liệu
1. 1 M ột s ố khái niệm cơ bả n
Định nghĩa 1.1.1
Cho tập hữu hạn U = {A1, A2 , ... , An} khác rỗng (n 1). Các phần tử
Về cấu trúc, luận án được trình bày trong 3 chương, có phần
của U được gọi là thuộc tính. Ứng với mỗi thuộc tính AiU, i =
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ố
1,2,...,n có một tập chứa ít nhất hai phần tử dom(Ai ) được gọi là miền
liên quan đến luận án và tài liệu tham khảo. Chương 1trình bày khái
trị của thuộc tính Ai . Gọi D là hợp của các dom(Ai ), i = 1,2,...,n. Một
niệm chung về mô hình quan hệ và lớp phụ thuộc đầu tiên của phụ
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
thuộc logic là phụ thuộc hàm. Tổng quan về quá trình phát triển của
xạ
lớp các phụ thuộc Boole và đặt vấn đề xác định giới hạn của phụ
t(Ai ) dom(Ai ). Mỗi ánh xạ được gọi là một bộ của quan hệ R.
thuộc Boole trong điều kiện bảo toàn hiệu lực của định lý tương
1.2. Phụ thuộc hàm
đương. Chương 2 giới thiệu công cụ có thể vận dụng để nghiên cứu
Định nghĩa 1.2.1
các vấn đề thuộc về ngữ nghĩa dữ liệu, thiết kế CSDL và hệ suy dẫn
t:
UD
sao
cho
với
mỗi
Ai U
ta
có
9
6
hạn, F là tập các luật sinh trên U.
1.5. Phụ thuộc Boole dương tổng quát
Định nghĩa 2.3.2
Định nghĩa 1.5.1
Cho một hệ sinh AXĐ = (U, F) và các tập con X, Z của U. Ta gọi Z
Cho tập thuộc tính U. Ta quy ước rằng mỗi miền trị di của thuộc
là một tập bao của tập X trong hệ sinh nếu Z thỏa các tính chất sau
tính Ai , 1 i n, có chứa ít nhất hai phần tử. Với mỗi miền trị di , ta
đây:
xét ánh xạ i : didi B thoả ba tính chất sau:
(i) Z X,
i) Tính phản xạ: adi : ia,a) =1
(ii) L R F, L Z R Z.
ii) Tính đối xứng: a,b di : i a,b) = ib,a)
iii) Tính bộ phận: a, b di : i a,b) = 0.
Kí hiệu [X] là họ các tập bao của X trong hệ sinh AXĐ cho trước.
Định nghĩa 2.3.3
Quan hệ đẳng thức là trường hợp riêng của quan hệ trên.
Cho hệ sinh AXĐ = (U,F). Ta xác định ánh xạ f: SubSet(U)
Định nghĩa 1.5.2
SubSet(U) như sau, X U: f(X) = [X]. Nói cách khác f(X) là
Giả sử các ánh xạ i đã được xác định trên mỗi miền trị di của các
tập con nhỏ nhất của U thỏa các tính chất sau:
thuộc tính Ai trong tập U= {A1,A2,...,An}, 1 i n và R là một quan
(i) f(X) X,
hệ trên U. Với hai bộ u và v tuỳ ý trong quan hệ R ta định nghĩa
(ii) L R F, L f(X) R f(X).
u,v) là phép gán trị:
u,v) = 1u.A1,v.A1), 2u.A2,v.A2),...,nu.An,v.An ))
Với mỗi quan hệ R RELU) ta gọi bảng chân lý của quan hệ R là
tập
TR = {u,v) u, v R}
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
Định nghĩa 1.5.3
chất :
Mỗi công thức Boole dương trong PU) là một phụ thuộc Boole
X U: f(X) = h(X)
dương tổng quát PTBDTQ).
Định lý 2.3.2
Định lý tương đương
Cho hệ sinh AXĐ = (U,F) và hai tập con không giao nhau X và Y
Cho tập PTBDTQ F và một PTBDTQ f. Ba mệnh đề sau là tương
trong U. Khi đó:
đương,
f(XY) = X f\X(Y)
i)
F ╞ f suy dẫn logic)
Hệ quả 2.3.1
ii) F ├ f suy dẫn theo quan hệ)
Cho hệ sinh AXĐ = (U,F) và tập X U. Khi đó:
iii) F ├2 f suy dẫn theo quan hệ có không quá 2 bộ)
7
8
1.6. Phụ thuộc Boole dương đa trị
Cho tập U hữu hạn. Ánh xạ f: SubSet(U) SubSet(U) được gọi là
Định nghĩa 1.6.1
đó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
Tập trị Boole B = {b1,...,bk} gồm k giá trị trong khoảng [0;1], k 2
đây:
được sắp tăng và thỏa các điều kiện sau:
(i) Tính phản xạ: f(X) X,
(i) 0 B,
(ii) Tính đồng biến: Nếu X Y thì f(X) f(Y),
(ii) b B 1- b B.
(iii) Tính lũy đẳng: f(f(X)) = f(X).
Trong phần này chúng ta chọn thể hiện cho các phép toán và hàm
2.2. Giàn giao và điểm bất động của ánh xạ đóng
logic đa trị cơ sở như sau:
Định nghĩa 2.2.1
a,b B ,
Phép hội a b = min(a,b)
Phép tuyển a b = max(a,b)
Phép phủ định a = 1-a
Với mỗi trị b B ta định nghĩa hàm Ib như sau:
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
x B : Ib(x) = 1 nếu x = b, ngoài ra Ib(x) = 0.
Các hàm Ib , b B được gọi là các hàm phủ định tổng quát.
U, cụ thể là giao của mọi họ con trong G đều cho kết quả là một tập
con trong G,
G SubSet(U): ( H G
X
G)
X H
Ta gọi G là giàn giao trên tập hữu hạn U. Khi đó G chứa duy nhất
một họ con S sao cho mọi phần tử của G đều được biểu diễn qua giao
Định nghĩa 1.6.2
của các phần tử trong S, cụ thể là, S là tập con nhỏ nhất của G thỏa
Cho U = {x1,...,xn} là tập hữu hạn các biến Boole, B là tập trị Boole.
tính chất: G = { X1 … Xk | k 0, X1, … , Xk S }
Khi đó các công thức Boole đa trị CTBĐT) là các công thức được
S được gọi là tập sinh của giàn G và được ký hiệu là Gen(G), S =
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
Gen(G).
và các phép toán , , Ký hiệu MVLU) là tập các CTBĐT xây
2.3. Hệ sinh ánh xạ đóng
dựng trên tập các biến U và tập trị B cho trước, trong đó U gồm n
Định nghĩa 2.3.1
phần tử và B gồm k phần tử, n 1, k 2.
Cho tập hữu hạn U, luật sinh f trên U là biểu thức dạng f: L R; L,
Ch ư ơ n g 2- Án h xạ đ ón g v à h ệ s u y d ẫn
R U. Các tập L và R được gọi tương ứng là vế trái và vế phải của
2.1 Ánh xạ đóng
luật sinh f và được kí hiệu tương ứng là LS(f) và RS(f).
Định nghĩa 2.1.1
Ta gọi một hệ sinh AXĐ là cặp = (U,F), trong đó U là một tập hữu
13
10
(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.
f (X) = X f\X ()
Định nghĩa 2.3.4
Kết quả của luận án về phép thu gọn hệ sinh và biểu diễn cơ sở
Ta gọi cơ sở của hệ sinh AXĐ là cơ sở của ánh xạ cảm sinh của hệ
hệ sinh ánh xạ đóng theo cơ sở hệ sinh cân bằng được trình bày trong
sinh đó. Với mỗi hệ sinh AXĐ = (U,F), ta kí hiệu Base() là tập
dưới đây.
các cơ sở của ánh xạ cảm sinh của hệ sinh , UB là tập các phần tử cơ
Định lý 2.4.1
sở của hệ sinh , U0 là tập các phần tử phi cơ sở của , UI là giao các
Mọi hệ sinh AXĐ α = (U,F) đều đưa được về dạng cân bằng
cơ sở của .
β = (V,G) thỏa tính chất: Base(α) = UI Base(β)
Ta có U = UB | U0 là một phân hoạch của U.
Trong đó UI là giao các cơ sở của α với độ phức tạp tuyến tính theo
Công thức tìm giao các cơ sở của hệ sinh ánh xạ đóng được trình bày
2
chiều dài dữ liệu vào O(n m), trong đó n là số lượng phần tử trong U,
theo định lý sau:
m là số lượng luật sinh trong F.
Định lý 2.3.3
Biểu diễn cơ sở hệ sinh AXĐ theo cơ sở HSCB
Cho hệ sinh AXĐ = (U,F) với n phần tử trong tập U và m luật sinh
Cho hệ sinh AXĐ α = (U,F) với U ={a1 , a2,…, an}, F = {Li Ri i=1,
trong F. Khi đó có thể xác định giao các cơ sở bằng một thuật toán
2,…, m} Để tìm các cơ sở của hệ sinh AXĐ α, ta thực hiện theo các
tuyến tính với độ phức tạp O(mn) qua công thức
U
bước sau:
Bước 1:
m
- Xác định L =
- Tính C =
m
1
fα(UIiR’)
i
i
, R’= R \ L; UI = U \
i 1
U \
Bổ đề 2.3.1
m
L , R = R
I
(R \ L)
L R F
R
Cho hai hệ sinh AXĐ = (U,F), = (V,G) và X U. Biết = \X.
i 1
Khi đó:
i
Bước 2:
Xác định α’ = (U’,F’) = α\C với U’= U\C, F’ = {Li \C Ri \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
(i) Nếu M là siêu cơ sở của thì M\X là siêu cơ sở của .
(ii) Nếu Z là siêu cơ sở của thì XZ là siêu cơ sở của . Nói
riêng, nếu X Uo và Z là siêu cơ sở của thì Z là siêu cơ
sở của .
Hệ quả 2.3.2
Cho hệ sinh AXĐ = (U,F) và tập X U. Khi đó, nếu Z là siêu cơ
nhau, ta thu được hệ sinh cân bằng = (U’, F’).
sở của hệ sinh \ f(X) thì XZ là siêu cơ sở của hệ sinh .
Bước 3:
Bổ đề 2.3.2
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’.
Cho hai hệ sinh AXĐ = (U,F), = (V,G) và tập X Uo. Biết =
\X. Khi đó: Base() = Base()
11
12
Định nghĩa 2.3.5
được dưới dạng K = LM, trong đó L là một vế trái cực tiểu của F và
Cho , SubSet(U) và M, P SubSet(U). Ta định nghĩa phép
M là cơ sở của hệ sinh AXĐ \ f (L).
toán trên SubSet(U) như sau:
Bổ đề 2.3.4
- M P = MP (hợp của hai tập con M và P)
Cho hệ sinh =(U, F) và vế trái cực tiểu L. Khi đó nếu K L
- M = {MX | X } và
Base(\f (L)) và K không chứa vế trái cực tiểu nào khác ngoài L thì
- = {XY | X , Y }
K là cơ sở của .
Các định lý, bổ đề và hệ quả dưới đây sau trình bày cách biểu diễn cơ
Bổ đề 2.3.5
sở của hệ sinh ánh xạ đóng theo phép thu gọn hệ sinh.
Cho hệ sinh = (U, F) và vế trái cực tiểu L. Khi đó M
Định lý 2.3.4
Base(\f(L)), mọi cơ sở K của chứa trong LM đều phải chứa M.
Nếu thu gọn hệ sinh AXĐ = (U, F) theo tập X U để nhận được
2.4. Hệ sinh cân bằng
hệ sinh = \ X thì:
Định nghĩa 2.4.1
1. Base() = Base( ) khi và chỉ khi X Uo.
Hệ sinh AXĐ α = (U,F) được gọi là cân bằng nếu α thỏa các tính
2. Base() = X Base() khi và chỉ khi X UI.
chất (C1)-(C4) sau đây:
Hệ quả 2.3.3
Cho hệ sinh = (U,F) và các tập phần tử X Uo, Y UI. Nếu thực
hiện phép thu gọn theo XY để nhận được hệ sinh = \XY thì
Base() = 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) | fF}
Bổ đề 2.3.3
(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
Cho hệ sinh AXĐ =(U, F). Nếu L ML(F) thì L Base() khi và
Ngoài các tính chất (C1)-(C4) ở trên, hệ sinh cân bằng (HSCB) còn
chỉ khi f(L) = U.
có một số tính chất sau:
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
(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ở UI = .
17
14
EndUnification.
- Xác định tập L’ là tập chứa các vế trái cực tiểu của F’.
Theo giả thiết F là tập các PTBDTQ do đó trước hết cần đưa F về
- Giả sử tập L’ ={L1, L2, …, Lk}. Lần lượt tính A = f (Li ), i = 1, 2,
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.
…, k.
Thuật toán Reduction dưới đây thực hiện nhiệm vụ trên.
+ Nếu A = U thì Li Base().
Thuật toán 3.1.3
+ Nếu A U thì ta tiếp tục xét hệ sinh cân bằng = \ A.
Algorithm Reduction
+ Lặp lại bước 3 cho hệ sinh cân bằng .
Function: Thu gọn tập PTBDTQ
Input: Tập PTBDTQ F
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(), ta thực hiện như sau:
Output: Công thức thu gọn C của F
+ Nếu Base()={K1, K2, …, Ks}
Method
+ Xét lần lượt các tập Li Kj với i cố định và j=1, 2, …, s:
1. Đưa F về dạng chuẩn hội:
Nếu Li Kj chứa trong cơ sở đã tìm thấy của thì không xét.
C := ;
Nếu LiKj không chứa phần tử nào khác của L’ ngoài Li thì
for each member f in F do
LiKj Base().
C := C cnf(f);
endfor;
2. return (Unification(C));
EndReduction.
Cuối cùng, để giải bài toán thành viên F╞ f ta gọi thuật toán
Member_GPBD sau đây.
Thuật toán 3.1.4
Algorithm Member_GPBD
Format: Member_GPBD(F,f)
Function: Giải bài toán thành viên F ╞ f
Input:
Bước 4: Xác định Base() = UI Base()
Ch ư ơ n g 3- Ph át tr i ển l ớ p cá c p h ụ th u ộc Bo ol e
d ư ơ n g và ứ n g d ụn g á n h xạ đ ón g, h ệ s u y d ẫn tron 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 ?
- Tập PTBDTQ F
Định nghĩa 3.1.1
- PTBDTQ f
Cho tập PTBDTQ F trên U. Xét LĐQH a = (U, F). Bao đóng của tập
Output: True nếu F ╞ f ; ngoài ra: False
Method
1. C:=Reduce(F) cnf(f)
PTBDTQ F, ký hiệu F+ là tập PTBDTQ được suy dẫn từ F, cụ thể là
F+ = { g P(U) | F ╞ g } = { g P(U) | TF Tg }
trong đó P(U) là tập các công thức Boole dương trên U.
15
16
Theo định nghĩa 1.5.2 về định lý tương đương của PTBDTQ trong
Algorithm Resolution
chương 1, bài toán thành viên được giải thông qua mệnh đề sau:
Function: Chứng minh công thức E
+
f F khi và chỉ khi F╞ f
Input: Công thức dương E
Trước khi giải bài toán trên ta có một số nhận xét sau :
Output: True nếu E là công thức hằng đúng;
Nhận xét 3.1.1
ngược lại: False
Để chứng minh công thức dương E (là hằng đúng với mọi phép
gán trị) ta tiến hành theo các bước sau:
1. Biểu diễn E dưới dạng chuẩn hội tức là dạng tích của các
Method
1. Đưa E về dạng chuẩn hội: C:= cnf(E);
return(Unification(C) = );
2. Hợp giải:
tổng C = C1 C2 … Ck với mỗi nhân tử Ci là tổng của
EndResolution.
các biến và hằng 0/1.
Thuật toán Unification dưới đây thực hiện chức năng hợp nhất các
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:
nhân tử trong công thức dương dạng chuẩn hội C đến mức tối đa
Thuật toán 3.1.2
Algorithm Unification
Tìm hai nhân tử Ci và Cj có dạng Ci = (p x) và Cj = (q
Function: Hợp nhất các nhân tử trong công thức
x); Nếu tìm được thì thay Ci và Cj trong C bằng nhân
dương dạng chuẩn hội C đến mức tối đa.
tử (p q).
Input: Công thức dương C dạng chuẩn hội
C = C1 C2 … Ck;
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à
hằng đúng
Thuật toán 3.1.1
Output: công thức sau khi hợp nhất.
Method
while (còn xử lý được) do
Tìm hai nhân tử trong C có dạng
Ci = (p x) và Cj = (q x);
if
(tìm được)
Thay Ci và Cj trong C bằng (p q)
else break;
endif;
endwhile;
return C;
21
miền trị di của các thuộc tính Ai trong tập U= {A1 ,A2,...,An}, 1 i n
18
2. return Resolution(C);
thì bảng chân lý TR của quan hệ R được tính như sau:
TR = {(u,v) | u,v R}
Trong đó (u,v) được xác định như sau:
(u,v) = (1(u.A1 ,v.A1), 2(u.A2,v.A2),...,n(u.An,v.An))
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 TR;
2. Làm đóng TR thu được bảng
T:=Closed&_GPBD(TR);
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ệ RU 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
cứu ở trên có thể được ứng dụng để biểu diễn luật, tập luật và trích
chọn luật trong cơ sở tri thức.
EndMember.
Định nghĩa 3.1.3
Cho hai tập PTBDTQ F, G trong PU), ta nói F dẫn ra được G, ký
hiệu F╞ G, nếu TF TG . Ta nói F và G là tương đương, ký hiệu F
G, nếu TF = TG. Nếu F và G là tương đương thì ta nói rằng F là phủ
của G và ngược lại G là phủ của F.
Định nghĩa 3.1.4
Cho tập PTBDTQ G trên U. Phụ thuộc gG được gọi là dư thừa nếu
G G-{g}. Tập G được gọi là không dư nếu không phụ thuộc dư
thừa gG.
Định nghĩa 3.1.5
Cho hai tập PTBDTQ F, G trên U, g là một PTBDTQ. G được gọi là
phủ không dư của F nếu:
1) G là một phủ của F hay TG = TF
2) G có dạng không dư: gG: 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 TG = TF
g G: G\{g} ≢ G
Method
19
20
G:=F;
Với các ánh xạ i , 1 i n , được xác định trước thì quan hệ
for each g in F do
Armstrong đối với tập F các PTBDTQ cho trước không phải luôn
if Member_GPBD(G\{g},g)then
luôn tồn tại.
3. 2. B i ểu d i ễn p h ụ th u ộc B o ol e d ư ơ n g t ổn g q u á t
G:=G\{g};
d ư ớ i d ạn g h ội su y d ẫn
endif;
endfor;
Định nghĩa 3.2.1
return G;
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
End Nonredundant_GPBD.
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
Định nghĩa 3.1.6
thành phần tương ứng của u và v. Cụ thể là, nếu
Cho tập hữu hạn U và công thức Boole h trên U. Ta ký hiệu [h] là tập
u = (u1,u2,...,un) và v = (v1,v2,...,vn) thì
các công thức Boole trên U tương đương với công thức h. Như vậy:
g [h] g h Tg = Th
u & v = (u1v1, u2 v2,...,unvn)
Định nghĩa 3.2.2
Quan hệ tương đương thỏa các tính chất phản xạ, đối xứng và bắc
Tập các phép gán trị V được gọi là đóng đối với phép nhân & nếu V
cầu, do đó tập các công thức Boole dương trên U, L(U) được phân
chứa tích của mọi cặp phần tử trong V, tức là u,v V: u & v V.
hoạch thành các lớp tương đương theo nghĩa [g] = [h] g h
Dễ thấy, Set(u & v) = Set(u) Set(v).
Định nghĩa 3.1.7
Bài toán 3.2.1: Xác định điều kiện cần và đủ để có thể biểu diễn một
Cho quan hệ R trên tập thuộc tính U. Ký hiệu BD(R) là tập các
phụ thuộc Boole dương tổng quát dưới dạng hội suy dẫn?
PTBDTQ đúng trong R, cụ thể là BD(R) = { g P(U) | R(g) }.
Định lý 3.2.5
Ta có g BD(R) g P(U) TR Tg
Phụ thuộc Boole dương tổng quát g trên U có thể biểu diễn dưới dạng
Định nghĩa 3.1.8
hội suy dẫn khi và chỉ khi bảng chân lý của g chứa các phép gán trị
Cho quan hệ R trên U và tập PTBDTQ F trên U. Ta nói quan hệ R thể
+
hiện tập PTBDTQ F nếu BD(R) F và quan hệ R thể hiện chặt tập
+
đơn vị e, phép gán trị không z và đóng với phép &, cụ thể là khi và
chỉ khi g thỏa hai tính chất (i)-(ii) sau đây.
PTBDTQ F nếu BD(R) = F . Nếu quan hệ R thể hiện chặt tập
(i) g(e) = g(z) = 1,
PTBDTQ F ta cũng nói R là quan hệ Armstrong của tập PTBDTQ F.
(ii) u,v Bn : g(u) = g(v) = 1 g(u&v) = 1.
Định lý 3.1.3
Định nghĩa 3.2.3
Cho quan hệ R và tập PTBDTQ F trên U. Khi đó quan hệ R thể
Cho quan hệ R trên tập thuộc tính U. Với quan hệ đối sánh giữa các
hiện chặt tập PTBDTQ F khi và chỉ khi TR = TF .
bộ của R thỏa điều kiện ánh xạ i : didi B được xác định trên mỗi
Mệnh đề 3.1.2
22
3.3 . Ứn g dụn g án h xạ đón g và hệ su y 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
định lý 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 (định lý 2.3.5); Phát
biểu và chứng minh 02 bổ đề biểu diễn các cơ sở sinh từ cơ sở
của hệ sinh sau khi thực hiện phép thu gọn với vế trái cực tiểu
(bổ đề 2.3.4 và bổ đề 2.3.5); Đề 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 cơ sở hệ sinh ánh xạ
đóng khi sử dụng công cụ này.
2. Phát triển lớp phụ thuộc Boole dương tổng quát: Đề xuất khái
niệm bao đóng, 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; Xây dựng thuật
23
toán giải bài toán thành viên trong trường hợp tổng quát cho lớp
phụ thuộc Boole dương tổng quát; 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; Phát biểu và chứng minh mệnh đề về điều
kiện tồn tại của quan hệ Armstrong đối với PTBDTQ; Xây dựng
thuật toán tìm tập PTBDTQ thỏa mãn quan hệ R cho trước.
3. Ứng dụng các kết quả nghiên cứu để giải quyết một số bài toán
trong CSDL như bài toán tìm khóa, bao đóng.. và một số dạng
toán của hệ suy dẫn.
2. Kiến nghị hướng phát triển tiếp theo
-
Nghiên cứu và phát triển về phủ tối thiểu cho lớp phụ thuộc
Boole dương tổng quát.
-
Tiếp tục tìm hiểu và tổng quát hóa một số lớp phụ thuộc dữ liệu
có bản chất là phụ thuộc Boole dương được nghiên cứu gần đây
như phụ thuộc hàm mềm, phụ thuộc hàm có điều kiện, phụ thuộc
sai khác….
- Xem thêm -