HỌC VIỆN CÔNG NGHỆ BƢU CHÍNH VIỄN THÔNG
LƢƠNG NGUYỄN HOÀNG HOÀNG HOA
PHÁT TRIỂN MỘT SỐ PHỤ THUỘC
LOGIC TRONG CƠ SỞ DỮ LIỆU
Chuyên ngành: Truyền dữ liệu và mạnh máy tính
Mã ngành:
62 48 15 01
TÓM TẮT LUẬN ÁN TIẾN SỸ KỸ THUẬT
NGƢỜI HƢỚNG DẪN KHOA HỌC:
1. PGS. TSKH NGUYỄN XUÂN HUY
2. PGS. TS TỪ MINH PHƢƠNG
HÀ NỘI – 2012
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:
Phản biện 2:
Phản biện 3:
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ễ thông
Vào hồi:
giờ, ngày tháng năm 200
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
DANH MỤC CÁC CÔNG TRÌNH CÔNG BỐ
[1]
[2]
[3]
[4]
[5]
[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.
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
2
Trong quản lý các cơ sở dữ liệu, phụ thuộc dữ liệu đƣợc hiểu là
những mệnh đề mô tả các ràng buộc mà dữ liệu phải thỏa mãn trong
thực tế. Nhờ những mô tả phụ thuộc này mà hệ quản trị cơ sở dữ liệu
có thể quản lý tốt đƣợc chất lƣợng dữ liệu. Phụ thuộc dữ liệu đầu tiên
đƣợc Codd tác giả của mô hình dữ liệu quan hệ đặt nền móng từ
những năm 70 với khái niệm phụ thuộc hàm. Sau đó một loạt tác giả
khác đã tiếp tục phát triển các dạng phụ thuộc bậc cao, phụ thuộc mờ
cũng nhƣ xây dựng các hệ tiên đề cho các lớp phụ thuộc - tức là đặt
nền móng cơ sở lý thuyết về phụ thuộc dữ liệu. Một trong số những
lớp phụ thuộc quan trọng đã đƣợc phát triển, đề xuất sau này là phụ
thuộc Boole dƣơng.
Với mong muốn phát triển, mở rộng lý thuyết về phụ thuộc
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,
phát triển một số vấn đề liên quan đến lớp phụ thuộc Boole dƣơng và
công cụ để mô tả, phản ánh lớp phụ thuộc này. Đây là vấn đề nghiên
cứu đã và đang đƣợc nhiều nhà khoa học quan tâm.
Mục đích nghiên cứu
-
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
chất của lớp phụ thuộc Boole dƣơng tổng quát và một số khía
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ố
liên quan đến luận án và tài liệu tham khảo. Chƣơng 1trình bày khái
niệm chung về mô hình quan hệ và lớp phụ thuộc đầu tiên của phụ
thuộc logic là phụ thuộc hàm. Tổng quan về quá trình phát triển của
lớp các phụ thuộc Boole và đặt vấn đề xác định giới hạn của phụ
thuộc Boole trong điều kiện bảo toàn hiệu lực của định lý tƣơng
đƣơng. Chƣơng 2 giới thiệu công cụ có thể vận dụng để nghiên cứu
các vấn đề thuộc về ngữ nghĩa dữ liệu, thiết kế CSDL và hệ suy dẫn
4
là ánh xạ đóng. Trong chƣơng cũng trình bày một số kết quả mới của
luận án liên quan đến hệ sinh ánh xạ đóng nhƣ biểu diễn cơ sở hệ
sinh ánh xạ đóng qua hợp vế trái tối tiểu của hệ sinh cho trƣớc và cơ
sở của hệ sinh sau khi thu gọn. Đề xuất lớp hệ sinh mới là hệ sinh cân
bằng với mục đích nâng cao hiệu quả trong quá trình tính toán và một
dạng biểu diễn cơ sở của hệ sinh ban đầu thông qua cơ sở hệ sinh cân
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
liên quan đến việc tìm bao đóng, phủ, phủ không dƣ, bài toán thành
viên và thể hiện của lớp phụ thuộc Boole dƣơng tổng quát
(PTBDTQ). 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 và thuật toán xây dựng xây dựng tập
PTBDTQ thỏa mãn quan hệ R cho trƣớc cũng đƣợc trình bày trong
chƣơng này. Một số ứng dụng của ánh xạ đóng và hệ suy dẫn trong
cơ sở dữ liệu cũng đƣợc giới thiệu trong chƣơng này.
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ử
của U đƣợc gọi là thuộc tính. Ứng với mỗi thuộc tính AiU, i =
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
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
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:
UD
sao
cho
với
mỗi
AiU
ta
t(Ai) dom(Ai). 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
có
5
Cho tập thuộc tính U. Một phụ thuộc hàm (PTH) trên U là biểu thức
dạng : f: XY ; X,Y U
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
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
tập thuộc tính Y.
1.3. Các công thức Boole
Định nghĩa 1.3.1
Cho U = {x1,...,xn} là tập hữu hạn các biến Boole, B là tập trị Boole,
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 LU) 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à Tf, là tập các phép gán trị v sao cho fv)
nhận giá trị 1, Tf = {v B n | fv) =1}
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,
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
f F
Ta có, v TF khi và chỉ khi f F: fv) = 1.
1.4. Phụ thuộc Boole dƣơng
Đị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.
6
1.5. Phụ thuộc Boole dƣơng tổng quát
Định nghĩa 1.5.1
Cho tập thuộc tính U. Ta quy ƣớc rằng mỗi miền trị di của thuộc
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
xét ánh xạ i: didi B thoả ba tính chất sau:
i) Tính phản xạ: adi: ia,a) =1
ii) Tính đối xứng: a,b di: ia,b) = ib,a)
iii) Tính bộ phận: a, b di: ia,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ị di của các
thuộc tính Ai trong tập U= {A1,A2,...,An}, 1 i n và R là một quan
hệ trên U. Với hai bộ u và v tuỳ ý trong quan hệ R ta định nghĩa
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}
Định nghĩa 1.5.3
Mỗi công thức Boole dƣơng trong PU) 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
Tập trị Boole B = {b1,...,bk} gồm k giá trị trong khoảng [0;1], k 2
đƣợc sắp tăng và thỏa các điều kiện sau:
(i) 0 B,
(ii) b B 1- b B.
Trong phần này chúng ta chọn thể hiện cho các phép toán và hàm
logic đa trị cơ sở nhƣ sau:
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:
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.
Định nghĩa 1.6.2
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 , , Ký hiệu MVLU) 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ạ đóng và hệ suy 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
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
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
tính chất: G = { X1 … Xk | k 0, X1, … , Xk S }
S đƣợc gọi là tập sinh của giàn G và đƣợc ký hiệu là Gen(G), S =
Gen(G).
2.3. Hệ sinh ánh xạ đóng
Định nghĩa 2.3.1
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,
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
luật sinh f và đƣợc kí hiệu tƣơng ứng là LS(f) và RS(f).
Ta gọi một hệ sinh AXĐ là cặp = (U,F), trong đó U là một tập hữu
9
hạn, F là tập các luật sinh trên U.
Định nghĩa 2.3.2
Cho một hệ sinh AXĐ = (U, F) và các tập con X, Z của U. Ta gọi Z
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
đây:
(i) Z X,
(ii) L R F, L Z R Z.
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
Cho hệ sinh AXĐ = (U,F). Ta xác định ánh xạ f: SubSet(U)
SubSet(U) nhƣ sau, X U: f(X) = [X]. Nói cách khác f(X) là
tập con nhỏ nhất của U thỏa các tính chất sau:
(i) f(X) X,
(ii) L R F, L f(X) R f(X).
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Đ = (U,F) và hai tập con không giao nhau X và Y
trong U. Khi đó:
f(XY) = X f\X(Y)
Hệ quả 2.3.1
Cho hệ sinh AXĐ = (U,F) và tập X U. Khi đó:
10
f (X) = X f\X ()
Định nghĩa 2.3.4
Ta gọi cơ sở của hệ sinh AXĐ là cơ sở của ánh xạ cảm sinh của hệ
sinh đó. Với mỗi hệ sinh AXĐ = (U,F), ta kí hiệu Base() là tập
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ơ
sở của hệ sinh , U0 là tập các phần tử phi cơ sở của , UI là giao các
cơ sở của .
Ta có U = UB | U0 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
UI U \
Bổ đề 2.3.1
( R \ L)
LRF
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 .
(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ơ
sở của hệ sinh \ f(X) thì XZ là siêu cơ sở của hệ sinh .
Bổ đề 2.3.2
Cho hai hệ sinh AXĐ = (U,F), = (V,G) và tập X Uo. 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 = \ X thì:
1. Base() = Base() khi và chỉ khi X Uo.
2. Base() = X Base() khi và chỉ khi X UI.
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
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
đƣợc dƣới dạng K = LM, trong đó L là một vế trái cực tiểu của F và
M là cơ sở của hệ sinh AXĐ \ f (L).
Bổ đề 2.3.4
Cho hệ sinh =(U, F) và vế trái cực tiểu L. Khi đó nếu K L
Base(\f (L)) và K không chứa vế trái cực tiểu nào khác ngoài L thì
K là cơ sở của .
Bổ đề 2.3.5
Cho hệ sinh = (U, F) và vế trái cực tiểu L. Khi đó M
Base(\f(L)), mọi cơ sở K của chứa trong LM đều phải chứa M.
2.4. Hệ sinh cân bằng
Định nghĩa 2.4.1
Hệ sinh AXĐ α = (U,F) đƣợc gọi là cân bằng nếu α thỏa các tính
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ở UI = .
13
(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(α) = UI Base(β)
Trong đó UI 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(n2m), 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 ={a1, a2,…, an}, F = {LiRi i=1,
2,…, m} Để tìm các cơ sở của hệ sinh AXĐ α, ta thực hiện theo các
bƣớc sau:
Bƣớc 1:
m
- Xác định L =
- Tính C =
Li , R =
1
fα(UIiR’)
m
Ri , R’= R \ L; UI = U \
i 1
m
R
i 1
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
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’.
14
- Xác định tập L’ là tập chứa các vế trái cực tiểu của F’.
- Giả sử tập L’ ={L1, L2, …, Lk}. Lần lƣợt tính A = f (Li), i = 1, 2,
…, k.
+ Nếu A = U thì Li 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(), ta thực hiện nhƣ sau:
+ Nếu Base()={K1, K2, …, Ks}
+ Xét lần lƣợt các tập LiKj với i cố định và j=1, 2, …, s:
Nếu LiKj chứa trong cơ sở đã tìm thấy của thì không xét.
Nếu LiKj không chứa phần tử nào khác của L’ ngoài Li thì
LiKj Base().
Bƣớc 4: Xác định Base() = UI Base()
Chƣơng 3- Phát triển lớp các phụ thuộc Boole
dƣơng và ứng dụng ánh xạ đóng, hệ suy dẫn trong
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 ?
Định nghĩa 3.1.1
Cho tập PTBDTQ F trên U. Xét LĐQH a = (U, F). Bao đóng của tập
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
Theo định nghĩa 1.5.2 về định lý tƣơng đƣơng của PTBDTQ trong
chƣơng 1, bài toán thành viên đƣợc giải thông qua mệnh đề sau:
f F+ khi và chỉ khi F╞ f
Trƣớc khi giải bài toán trên ta có một số nhận xét sau :
Nhận xét 3.1.1
Để 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
tổng C = C1 C2 … Ck với mỗi nhân tử Ci 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ử Ci và Cj có dạng Ci = (p x) và Cj = (q
x); Nếu tìm đƣợc thì thay Ci và Cj 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à
hằng đúng
Thuật toán 3.1.1
16
Algorithm Resolution
Function: Chứng minh công thức E
Input: Công thức dương E
Output: True nếu E là công thức hằng đúng;
ngược lại: False
Method
1. Đưa E về dạng chuẩn hội: C:= cnf(E);
return(Unification(C) = );
2. Hợp giải:
EndResolution.
Thuật toán Unification dƣới đây thực hiện chức năng hợp nhất các
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
Function: Hợp nhất các nhân tử trong công thức
dương dạng chuẩn hội C đến mức tối đa.
Input: Công thức dương C dạng chuẩn hội
C = C1 C2 … Ck;
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;
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
Output: Công thức thu gọn C của F
Method
1. Đưa F về dạng chuẩn hội:
C := ;
for each member f in F do
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:
- Tập PTBDTQ F
- PTBDTQ f
Output: True nếu F ╞ f ; ngoài ra: False
Method
1. C:=Reduce(F) cnf(f)
- Xem thêm -