BỘ GIÁO DỤC VÀ ĐÀO TẠO
BỘ QUỐC PHÒNG
HỌC VIỆN KỸ THUẬT QUÂN SỰ
TRẦN MINH TUYẾN
CÁC PHỤ THUỘC LOGIC
TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI
LUẬN ÁN TIẾN SĨ TOÁN HỌC
HÀ NỘI - 2015
1
BỘ GIÁO DỤC VÀ ĐÀO TẠO
BỘ QUỐC PHÒNG
HỌC VIỆN KỸ THUẬT QUÂN SỰ
TRẦN MINH TUYẾN
CÁC PHỤ THUỘC LOGIC
TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI
Chuyên ngành: Cơ sở toán học cho tin học
Mã số: 62 46 01 10
dẫn khoa học của PGS.TSKH. Nguyễn Xuân Huy. Các kết quả được viết
chung với các đồng tác giả đã được sự chấp thuận của các tác giả trước khi
đưa vào luận án.
Các kết quả nêu trong luận án là trung thực và chưa từng được ai công
bố trong bất kỳ công trình nào khác.
Tác giả luận án
Trần Minh Tuyến
4
MỤC LỤC
Trang
MỞ ĐẦU
10
Chương 1: Mô hình dữ liệu dạng khối
20
1.1 Mô hình dữ liệu
20
1.1.1 Khái niệm
20
36
1.3.1 Khái niệm
36
1.3.2 Khóa của ánh xạ đóng
38
1.4 Các công thức Boolean
39
1.4.1 Khái niệm
39
1.4.2 Bảng trị và bảng chân lý
40
1.4.3 Suy dẫn logic
41
1.4.4 Công thức Boolean dương
41
54
2.5 Lược đồ khối cân bằng
61
2.6 Thuật toán dịch chuyển lược đồ khối về dạng cân bằng
65
2.7 Tập các vế trái cực tiểu
69
Chương 3:
Phụ thuộc Boolean dương và phụ thuộc
Boolean dương tổng quát trên khối
72
3.1 Lược đồ khối và ánh xạ đóng
72
3.2 Phụ thuộc Boolean dương trên khối
76
3.2.1 Khối chân lý
99
6
DANH MỤC CÁC KÍ HIỆU, CÁC CHỮ VIẾT TẮT
Kí hiệu
XY
REL(U)
RELp(U)
t*v
t*S
t[X], t.X
id id’
M P
M
AXĐ
f*g
SubSet(U)
2
CTB
CTBD
PTBD
PTBDTQ
Fix(f)
Gen(G)
7
PTH
Uo
UK
UI
LS(f)
RS(f)
LS(F)
RS(F)
Phụ thuộc hàm.
Tập tất cả các thuộc tính không khoá.
Tập tất cả các thuộc tính khoá.
Tập tất cả các thuộc tính nằm trong mọi khoá.
Vế trái của phụ thuộc hàm f.
Vế phải của phụ thuộc hàm f.
Hợp các vế trái của tất cả các phụ thuộc hàm f F.
Hợp các vế phải của tất cả các phụ thuộc hàm f F.
8
DANH SÁCH BẢNG
Trang
Bảng 1: Biểu diễn quan hệ CAN_BO_1.
10
88
Hình 3.4: Biểu diễn khối chân lý r2 của khối KH_HANG.
88
10
MỞ ĐẦU
1. Lý do lựa chọn đề tài
Để có thể xây dựng được một hệ thống cơ sở dữ liệu tốt, người ta
thường sử dụng các mô hình dữ liệu thích hợp.
Đã có một số loại mô hình được sử dụng trong các hệ thống cơ sở dữ
liệu như: mô hình thực thể - liên kết, mô hình mạng, mô hình phân cấp, mô
hình hướng đối tượng, mô hình dữ liệu datalog [53], [54], và mô hình quan hệ
[33], [52], [53], [54]. Trong số các mô hình này, có ba mô hình dữ liệu
thường được sử dụng: mô hình phân cấp, mô hình mạng và mô hình quan hệ.
Đối với ba mô hình này thì mô hình quan hệ được quan tâm hơn cả. Mô hình
này do E. Codd đề xuất ra năm 1970. Sở dĩ mô hình quan hệ được quan tâm
như vậy là vì nó được xây dựng trên một cơ sở toán học chặt chẽ - đó là lý
thuyết toán học về các quan hệ có áp dụng rộng rãi các công cụ đại số và
logic. Tuy nhiên, do các quan hệ có cấu trúc phẳng (tuyến tính) nên mô hình
này chưa đủ đáp ứng đối với các ứng dụng phức tạp, các cơ sở dữ liệu có cấu
trúc phi tuyến,...
Ví dụ: Khi cần theo dõi hồ sơ cán bộ trong một cơ quan, ta lập bảng sau:
CAN_BO_1:
ma
11
Bảng này gồm các trường: ma (mã cán bộ), ten (tên cán bộ), luong
(lương hàng tháng), trinh_do (trình độ cán bộ). Bảng này chính là một quan
hệ trong mô hình dữ liệu quan hệ. Mỗi khi lương của một cán bộ thay đổi thì
người quản lý cập nhật lương mới cho cán bộ đó, như vậy giá trị của lương cũ
mất đi mà thay bằng giá trị lương mới. Tình trạng tương tự với thuộc tính:
trinh_do (trình độ cán bộ) khi mà trình độ của một cán bộ thay đổi. Do đó, với
cách quản lý nhân sự theo bảng trên thì người quản lý không thể theo dõi
được quá trình tăng lương hoặc quá trình nâng cao trình độ của những cán bộ
mình quản lý. Đối với họ thì trong cách quản lý này, việc theo dõi quá trình
phát triển của mỗi người theo thời gian là một công việc khó khăn.
Tuy nhiên, trong mô hình dữ liệu dạng khối thì việc này lại trở nên đơn
giản hơn. Ta có thể thấy điều đó qua cách quản lý cán bộ theo mô hình khối
dữ liệu, cụ thể như hình ảnh của khối CAN_BO_2 dưới đây:
CAN_BO_2:
ma
ten
A01
A01
t1
A01
A
C01
TS
ThS
DH
B
B
trinh_do
550
350
B02
t2
luong
350
250
200
DH
2015
2010
liệu. Khối dữ liệu dưới đây là một ví dụ:
Hình 2: Biểu diễn khối dữ liệu đa chiều.
13
Với khối dữ liệu đa chiều như ở hình 2 ta thấy đây là khối dữ liệu 3
chiều. Một là chiều Thời gian gồm 4 mốc: Jan-01, Feb-01, Mar-01 và Apr-01,
hai là chiều Địa điểm gồm 2 nơi: Tokyo và Rome, ba là chiều Sản phẩm gồm
3 loại máy tính: Standard PC, Executive PC và Ambassador PC.
Cũng theo hướng nghiên cứu này một mô hình dữ liệu mới đã được đề
xuất, đó là mô hình dữ liệu dạng khối [4], [5], [7],... Mô hình dữ liệu này có
thể xem là một mở rộng của mô hình dữ liệu quan hệ.
Trong mô hình dữ liệu dạng khối, các khái niệm như: khối, lược đồ
khối, lát cắt, đại số khối, phụ thuộc hàm, bao đóng của tập thuộc tính chỉ số,...
đã được nghiên cứu [4], [5], [7], [8], [9], [10], [11], [12], [13].
Trong mô hình dữ liệu dạng khối, các lược đồ khối, khối nói chung là
lớn và phức tạp. Chính vì vậy mà mô hình này đòi hỏi phải có các thuật toán
tốt theo nghĩa, độ phức tạp tính toán chấp nhận được, chẳng hạn là hàm tuyến
tính hoặc đa thức theo chiều dài của dữ liệu vào. Các thuật toán này giúp ta
tìm bao đóng, khóa của lược đồ khối, khối, giải bài toán thành viên,...
Một cách tự nhiên, nếu kích thước của lược đồ khối càng nhỏ thì các
thuật toán đó càng phát huy hiệu quả hơn. Từ đó, một số hướng nghiên cứu
nhằm tinh giản các lược đồ khối được thực hiện thông qua các phép biến đổi
tương đương, chẳng hạn đưa tập phụ thuộc hàm về dạng thu gọn, thu gọn tự
nhiên, dạng không dư, dạng tối ưu,... cũng được quan tâm.
Đi theo hướng này, phép dịch chuyển lược đồ khối nhằm thu gọn, loại
bỏ khỏi lược đồ ban đầu những thuộc tính không quan trọng theo nghĩa chúng
không làm ảnh hưởng tới kết quả tính toán các đối tượng đang quan tâm như
việc sử dụng chúng sẽ có hiệu quả trong việc thiết kế các cơ sở dữ liệu dạng
khối trên thực tế.
2. Mục tiêu, đối tượng và phương pháp nghiên cứu
Mục tiêu của luận án là đề xuất các khái niệm và tìm hiểu tính chất các
loại phụ thuộc logic trong mô hình dữ liệu dạng khối như: phụ thuộc Boolean
15
dương, phụ thuộc Boolean dương tổng quát, ánh xạ đóng và mối quan hệ với
phép dịch chuyển lược đồ khối,… Mối quan hệ giữa phụ thuộc logic trong mô
hình dữ liệu dạng khối với các phụ thuộc tương ứng trong mô hình dữ liệu
quan hệ,... Bên cạnh đó, đề tài cũng tìm hiểu về quan hệ giữa phụ thuộc logic
trên lược đồ khối và phụ thuộc tương ứng trên lược đồ lát cắt, từ đó xem xét
về cấu trúc của các phụ thuộc logic trong mô hình dữ liệu dạng khối.
Đối tượng nghiên cứu của luận án chính là các phụ thuộc logic, ánh xạ
đóng, lược đồ cân bằng,… trong mô hình dữ liệu dạng khối với phép dịch
chuyển lược đồ khối. Mối quan hệ của chúng trên lược đồ khối và trên lược
đồ lát cắt, trên cơ sở đó xác định rõ các cấu trúc cụ thể của các phụ thuộc
logic trong mô hình dữ liệu dạng khối.
Phương pháp nghiên cứu của luận án: Hướng nghiên cứu của luận án là
nghiên cứu lý thuyết, do đó luận án sử dụng các công cụ của toán học, logic
(các phương pháp suy luận, chứng minh, lập bảng chân lý,…) để nghiên cứu
tìm ra các kết quả mới về các phụ thuộc logic trên lược đồ khối, phép dịch
chuyển lược đồ khối, ánh xạ đóng trên khối,…
3. Tổng quan tình hình nghiên cứu liên quan đến luận án
3.1 Các nghiên cứu trên thế giới
Hiện nay, trên thế giới việc mở rộng mô hình dữ liệu quan hệ của
E. Codd đề xuất năm 1970 cũng đã được nhiều nhà nghiên cứu
quan tâm.
Ng,… trong các bài báo của mình đã bàn về nhà kho dữ liệu, cơ sở
dữ liệu đa chiều và mô hình khối dữ liệu [18], [34], [35], [40].
- Năm 2009 John Paredes đã bàn về các công cụ của mô hình dữ liệu
đa chiều [28].
- Năm 2010 các tác giả Apostolos Benisis, Christian S.Jensen, Torben
Bach Pedersen, Christian Thomsen, & 1 mo-re trong các bài báo
của mình cũng đã nói tới khối dữ liệu, cơ sở dữ liệu đa chiều và
nhà kho dữ liệu [15], [19].
- Năm 2013 các tác giả Ralph Kimball, Margy Ross, Haiping
Lu, Konstantinos N. Plataniotis, Anastasios Venetsanopoulos đã
trình bày về bộ công cụ của nhà kho dữ liệu, dữ liệu đa
chiều,…[23], [44].
- Năm 2014 các tác giả Ladjel Bellatreche, Mukesh K. Mohania,
Ralph Kimball trong các bài báo của mình đã bàn về nhà kho dữ
liệu và các công cụ của nó [32], [45].
3.2 Các nghiên cứu tại Việt Nam
- Tại Việt Nam, năm 1998 các tác giả Nguyễn Xuân Huy, Trịnh Đình
Thắng đã đề xuất ra một mở rộng của mô hình quan hệ, đó là mô
17
hình dữ liệu dạng khối [4], mô hình này khác với các mô hình mà
các nhà khoa học nước ngoài đã đề xuất.
- Trong mô hình dữ liệu dạng khối, các tác giả đã đưa ra các khái
niệm như: khối, lược đồ khối, lát cắt, đại số quan hệ trên khối, các
thuộc tính chỉ số, phụ thuộc hàm,… đồng thời chứng minh nhiều
tính chất trên các khái niệm này [4], [5], [7], [8].
- Năm 2008 các tác giả Trịnh Đình Thắng và Trịnh Đình Vinh đã đề
xuất khái niệm phụ thuộc đa trị trong lược đồ khối và chứng minh
5. Một số kết quả nghiên cứu của luận án
Các kết quả nghiên cứu của luận án được đưa ra ở toàn bộ các
chương 2 và 3. Cụ thể như sau:
- Đề xuất khái niệm về phép dịch chuyển lược đồ khối và chứng minh
các kết quả về biểu diễn bao đóng và khóa qua phép dịch chyển lược
đồ khối.
- Mối quan hệ giữa khóa và các tập thuộc tính nguyên thủy, phi
nguyên thủy với phép dịch chuyển lược đồ khối.
- Đề xuất khái niệm lược đồ khối cân bằng và chứng minh các kết quả
về lược đồ khối cân bằng, vế trái cực tiểu và khóa với phép dịch
chuyển lược đồ khối.
- Chứng minh các tính chất của ánh xạ đóng trong mô hình dữ liệu
dạng khối với phép dịch chuyển lược đồ khối.
- Đề xuất khái niệm phụ thuộc Boolean dương trên lược đồ khối và
chứng minh các tính chất của nó trong mô hình dữ liệu dạng khối.
- Đề xuất khái niệm phụ thuộc Boolean dương tổng quát trên lược đồ
khối, chứng minh các tính chất và thể hiện của nó trong mô hình dữ
liệu dạng khối.
19
6. Bố cục của luận án
Luận án gồm phần mở đầu, 3 chương tiếp theo và cuối cùng là phần
kết luận.
Chương 1 trình bày một vài nét cơ bản nhất về mô hình dữ liệu và
giới thiệu một mô hình dữ liệu cụ thể: đó là mô hình dữ liệu dạng khối một mở rộng của mô hình dữ liệu quan hệ. Ánh xạ đóng và các tính chất
của nó cùng với các khái niệm về công thức Boolean, công thức Boolean
dương, ... cũng đã được giới thiệu ở đây.
Chương 2 đưa ra các kết quả nghiên cứu đầu tiên của luận án: đề
trọng trong khoa học kỹ thuật, giáo dục, kinh doanh,... cũng như trong mọi
hoạt động khác của xã hội dưới mọi quy mô, từ xí nghiệp, công ty,... cho đến
cấp quốc gia, quốc tế. Việc nắm bắt thông tin nhanh, nhiều, chính xác và kịp
thời ngày càng đóng vai trò quan trọng trong việc quản lý, điều hành công
việc. Mọi thông tin quản lý trên máy tính điện tử theo bất cứ quy trình cụ thể
nào cũng đều phải được thể hiện bằng các dữ liệu lưu trữ trên các thiết bị
mang tin, trên cơ sở đó tổ chức quản lý và khai thác dữ liệu. Dữ liệu là những
sự kiện có thể ghi lại được và có ý nghĩa.
Một tập hợp các dữ liệu có liên quan với nhau, mô hình hóa các đối tượng
của một phần thế giới thực (công ty, trường học, ngân hàng...), gọi là một cơ
sở dữ liệu. Các cơ sở dữ liệu phải được tổ chức quản lý sao cho những người
sử dụng có thể tìm kiếm dữ liệu, cập nhật dữ liệu và lấy dữ liệu ra khi cần
thiết.
21
Một hệ quản trị cơ sở dữ liệu là một tập hợp chương trình giúp cho người
sử dụng tạo ra, bảo trì và khai thác một cơ sở dữ liệu. Nó là một hệ thống
phần mềm phổ dụng, thuận tiện cho quá trình định nghĩa, xây dựng và thao
tác cơ sở dữ liệu với các ứng dụng khác nhau.
Các loại cấu trúc cơ sở dữ liệu và mối liên hệ giữa chúng đóng vai trò
quan trọng trong việc xác định tính hiệu quả của hệ quản trị cơ sở dữ liệu. Do
đó, việc thiết kế cơ sở dữ liệu là một hoạt động chủ yếu trong môi trường cơ
sở dữ liệu.
Quá trình thiết kế cơ sở dữ liệu được thực hiện đơn giản hơn nhiều khi ta
sử dụng các mô hình. Các mô hình là sự trừu tượng đơn giản của các sự kiện
trong thế giới thực. Nó cho phép khảo sát đặc điểm của các thực thể và các
mối liên hệ được tạo ra giữa các thực thể đó. Một mô hình cơ sở dữ liệu là
một tập hợp các khái niệm dùng để biểu diễn các cấu trúc của cơ sở dữ liệu.
được gọi là mô hình dữ liệu mức logic. Các mô hình dữ liệu thể hiện che dấu
một số chi tiết về việc lưu trữ dữ liệu nhưng có thể được cài đặt trực tiếp trên
hệ thống máy tính.
Các mô hình dữ liệu thể hiện là các mô hình được sử dụng thường xuyên
nhất trong các hệ cơ sở dữ liệu thương mại. Ba mô hình được quan tâm nhiều
thuộc loại này là: mô hình mạng, mô hình phân cấp và mô hình quan hệ.
Trong ba mô hình này thì mô hình quan hệ được quan tâm nhiều hơn cả. Đã
có nhiều tài liệu, bài báo trình bày các kết quả nghiên cứu về mô hình quan hệ
[1], [2], [3], [24], [29], [33], [52], [53], [54]. Sở dĩ mô hình quan hệ được
quan tâm như vậy vì nó được xây dựng trên một cơ sở toán học chặt chẽ - đó
là lí thuyết toán học về các quan hệ có áp dụng rộng rãi các công cụ đại số và
logic. Mô hình dữ liệu quan hệ có tính độc lập dữ liệu cao, dễ dàng sử dụng
và mô phỏng các hệ thống thông tin đa dạng trong thực tiễn.
23
Bên cạnh ưu điểm, mô hình dữ liệu quan hệ cũng còn có một số nhược
điểm. Trong mô hình này, cơ sở dữ liệu được xem như là một tập hợp các
quan hệ. Mỗi quan hệ có thể xem như một bảng gồm có các hàng và các cột,
mỗi cột ứng với một thuộc tính, mỗi hàng gọi là một bộ. Do các quan hệ có
cấu trúc phẳng (tuyến tính) nên mô hình này chưa đủ đáp ứng đối với các ứng
dụng phức tạp, các cơ sở dữ liệu có cấu trúc phi tuyến,...
Để khắc phục những nhược điểm trên, việc nghiên cứu nhằm mở rộng
mô hình dữ liệu quan hệ đã được nhiều nhà khoa học quan tâm. Một số tác giả
đã mở rộng mô hình dữ liệu quan hệ thành mô hình dữ liệu đa chiều và kho
dữ liệu,…[17], [41], [49], [51]. Sau đó nhiều tác giả khác trên thế giới đã
quan tâm nghiên cứu đến các mô hình dữ liệu này [38], [26], [34], [35], [18],
[40], [28], [15], [19], [14], [23], [44], [16], [32], [45],... Cũng theo hướng
nghiên cứu này, một mô hình dữ liệu mới đã được đề xuất và nghiên cứu, đó
11
12
10
200
A02
t2
A02
A03
A03
3
9
8
350
0
250
5
5
4
9
2/1/2015
1/1/2015
Hình 1.1: Biểu diễn khối KH_HANG
Với khối KH_HANG như ở hình 3, ta có:
Mã của khách hàng t1 vào ngày 1/1/2015 là: t1(1/1/2015,maKH) = A01.
Số lượng bánh mỳ khách hàng t2 mua ngày 2/1/2015 là:
t2(2/1/2015,Bmỳ) = 9.
Số lượng sữa khách hàng t3 mua ngày 3/1/2015 là: t3(3/1/2015,Sữa) = 5.
Định nghĩa 1.2 [4]
Cho R = (id; A1, A2,..., An ), r(R) là một khối trên R. Với mỗi x id ta kí
hiệu r(Rx) là một khối với Rx = ({x}; A1, A2,..., An ) sao cho:
tx (t1x , tx2 ,..., txn ) r( Rx ) txi t i | x, i 1..n ,
ở đây
.
Khi đó r(Rx) được gọi là một lát cắt trên khối r(R) tại điểm x.
Copyright: Tài liệu đại học ©