Luận án Các phụ thuộc logic trong mô hình dữ liệu dạng khối

 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 
LUẬN ÁN TIẾN SĨ TOÁN HỌC 
 NGƯỜI HƯỚNG DẪN KHOA HỌC: 
 PGS. TSKH. NGUYỄN XUÂN HUY 
HÀ NỘI - 2015 
2 
LỜI CẢM ƠN 
 Để hoàn thành luận án này, tôi đã nhận được sự giúp đỡ rất nhiệt tình 
của các thày, cô giáo trong khoa Công nghệ Thông tin, Học viện Kỹ thuật 
Quân sự và trường Đại học Công đoàn. Tôi xin gửi lời cảm ơn tới các thày, cô 
giáo trong khoa Công nghệ Thông tin, Học viện kỹ thuật Quân sự và trường 
Đại học Công đoàn đã tạo điều kiện học tập, nghiên cứu và giúp đỡ tôi rất 
nhiều trong quá trình viết luận án. Đặc biệt tôi xin trân trọng cảm ơn 
PGS.TSKH. Nguyễn Xuân Huy, người đã tận tình hướng dẫn, chỉ bảo cho tôi 
trong toàn bộ quá trình học tập, nghiên cứu đề tài và giúp tôi hoàn thành bản 
luận án này. 
 Hà Nội, ngày 10 tháng 10 năm 2015 
 Tác giả luận án 
 Trần Minh Tuyến 
3 
LỜI CAM ĐOAN 
 Tôi xin cam đoan đây là công trình nghiên cứu của tôi dưới sự hướng 
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 
 1.1.2 Phân loại 21 
1.2 Mô hình dữ liệu dạng khối 23 
 1.2.1 Khối, lát cắt của khối 23 
 1.2.2 Đại số khối 26 
 1.2.3 Phụ thuộc hàm 31 
 1.2.4 Bao đóng của tập thuộc tính chỉ số 33 
 1.2.5 Khóa của lược đồ khối = (R,F) 34 
1.3 Ánh xạ đóng 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 
Chương 2: 
 Phép dịch chuyển lược đồ khối và lược đồ khối cân bằng 43 
2.1 Phép dịch chuyển lược đồ khối 43 
2.2 Thuật toán dịch chuyển lược đồ khối 45 
5 
2.3 Biểu diễn bao đóng và khóa qua phép dịch chuyển 47 
 2.3.1 Biểu diễn bao đóng 47 
 2.3.2 Biểu diễn khóa 49 
2.4 Khóa và các tập thuộc tính nguyên thủy, phi nguyên thủy 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ý 76 
 3.2.2 Phụ thuộc Boolean dương 77 
 3.3 Mối quan hệ giữa các kiểu phụ thuộc hàm và các công thức 
 Boolean dương trên khối 84 
3.4 Phụ thuộc Boolean dương tổng quát trên khối 86 
3.5 Thể hiện phụ thuộc Boolean dương tổng quát trên khối 92 
 KẾT LUẬN VÀ HƯỚNG NGHIÊN CỨU TIẾP THEO 95 
DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ 97 
TÀI LIỆU THAM KHẢO 99 
6 
 DANH MỤC CÁC KÍ HIỆU, CÁC CHỮ VIẾT TẮT 
Kí hiệu Ý nghĩa của kí hiệu 
XY Biểu diễn hợp của hai tập X và Y 
REL(U) Tập toàn thể các quan hệ trên tập thuộc tính U 
RELp(U) Tập toàn thể các quan hệ có không quá p bộ trên tập thuộc 
tính U, p 1. 
t*v Phép kết nối hai bộ t và v. 
t*S Phép kết nối bộ t với quan hệ S. 
t[X], t.X hạn chế của bộ (ánh xạ) t trên tập thuộc tính X. 
id  id’ Kí hiệu tích rời rạc của id và id’ 
MP Hợp của 2 tập con M và P 
M  {MX| X }. 
   {XY | X  , Y  }. 
AXĐ Ánh xạ đóng 
f * g Hội của hai ánh xạ đóng f và g. 
SubSet(U) Tập tất cả các tập con của U. 
 Suy dẫn logic. 
 Suy dẫn theo quan hệ. 
2 Suy dẫn theo quan hệ có không quá 2 phần tử. 
CTB Công thức Boolean. 
CTBD Công thức Boolean dương. 
PTBD Phụ thuộc Boolean dương. 
PTBDTQ Phụ thuộc Boolean dương tổng quát. 
Fix(f) Tập toàn bộ các điểm bất động của f. 
Gen(G) Tập sinh của giàn giao G. 
Coatom(G) Đối nguyên tử của giàn giao G 
MAX(M) Tập các phần tử cực đại của M. 
7 
PTH Phụ thuộc hàm. 
Uo Tập tất cả các thuộc tính không khoá. 
UK Tập tất cả các thuộc tính khoá. 
UI Tập tất cả các thuộc tính nằm trong mọi khoá. 
LS(f) Vế trái của phụ thuộc hàm f. 
RS(f) Vế phải của phụ thuộc hàm f. 
LS(F) Hợp các vế trái của tất cả các phụ thuộc hàm f F. 
RS(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 
Bảng 1.1: Biểu diễn lát cắt của khối KH_HANG. 25 
9 
DANH SÁCH HÌNH VẼ 
 Trang 
Hình 1: Biểu diễn khối CAN_BO_2. 11 
Hình 2: Biểu diễn khối dữ liệu đa chiều. 12 
Hình 1.1: Biểu diễn khối KH_HANG. 24 
Hình 3.1: Biểu diễn khối KH_HANG và phụ thuộc Boolean dương f. 77 
Hình 3.2: Biểu diễn khối chân lý r1 của khối KH_HANG. 78 
Hình 3.3: Biểu diễn khối KH_HANG và PTBDTQ g. 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 ten luong trinh_do 
 A01 A 350 ThS 
 A02 B 300 DH 
 A03 C 250 CD 
 Bảng 1: Biểu diễn quan hệ CAN_BO_1. 
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: 
 Hình 1: Biểu diễn khối CAN_BO_2. 
 Với khối CAN_BO_2 thì mỗi khi có một cán bộ nào trong cơ quan 
được tăng lương hoặc thay đổi trình độ, thậm chí cả đổi tên thì ta bổ sung năm 
đó vào trục thời gian và khối sinh tương ứng một lát cắt mới, ứng với năm 
vừa bổ sung để người quản lý cập nhật thông tin (trục thời gian có thể tính 
 A01 A 550 TS 
 A01 A 350 ThS 
 t 1 A01 A 200 DH 
 B02 B 400 Ths 
 A02 B 300 DH 
 t 2 A02 B 250 DH 
 C01 C 350 DH 2015 
 A03 
 t 3 A03 C 200 CD 2007 
ma ten luong trinh_do 
 C 250 CD 2010 
12 
theo năm, tháng hoặc ngày,... tùy theo yêu cầu quản lý của từng cơ quan). 
Như vậy, ta có thể quản lý cán bộ trong cơ quan suốt cả quá trình công tác. 
Nhìn vào khối: CAN_BO_2, ta dễ dàng thấy quá trình tăng lương cũng 
như quá trình nâng cao trình độ của 3 cán bộ ứng với các bản ghi t1, t2, t3, ở 
đây các năm 2007, 2010, 2015 cũng chỉ là minh họa; ta có thể bổ sung thêm 
các năm tùy ý trên trục thời gian này của khối mỗi khi cần cập nhật thông tin 
cho các cán bộ trong cơ quan. 
Trong những năm gần đây, 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,...[14], 
[15], [16], [18], [19], [20], [21], [26], [32]. Một kỹ thuật thường được dùng 
trong các hệ thống kho dữ liệu để xử lý phân tích trực tuyến - OLAP (On-
Line Analytical Processing) là kỹ thuật sử dụng cách thể hiện dữ liệu đa 
chiều gọi là các khối (cube) nhằm cung cấp khả năng truy xuất nhanh đến dữ 
liệu của kho dữ liệu. 
Với cấu trúc của khối dữ liệu đa chiều thì mỗi chiều tương ứng với một 
thuộc tính, nó cung cấp cho người quản lý một khung nhìn đa chiều về dữ 
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ư 
bao đóng, khóa,... 
 Mặc dù lược đồ khối thu được qua phép thu gọn nhìn chung không 
tương đương với lược đồ khối ban đầu, nhưng ta lại thu được các đối tượng 
cần tìm bằng những phép toán đơn giản hơn. 
14 
 Cũng như trong mô hình dữ liệu quan hệ, các phụ thuộc dữ liệu trong 
mô hình khối đóng vai trò quan trọng đối với việc phản ánh ngữ nghĩa của dữ 
liệu. Phụ thuộc đầu tiên là phụ thuộc hàm, được E. Codd - tác giả của mô hình 
dữ liệu quan hệ đề xuất. Phụ thuộc này cũng đã được phát triển thành phụ 
thuộc hàm trong mô hình dữ liệu dạng khối. Khi khối suy biến thành quan hệ 
thì khái niệm phụ thuộc hàm trong mô hình dữ liệu dạng khối lại trở thành 
khái niệm phụ thuộc hàm trong mô hình dữ liệu quan hệ. 
 Với mô hình dữ liệu quan hệ, sau phụ thuộc hàm thì một trong các lớp 
phụ thuộc quan trọng được phát triển là phụ thuộc Boolean dương, phụ thuộc 
Boolean dương tổng quát, phụ thuộc Boolean dương đa trị, Ở đây, khái 
quát hóa các lớp phụ thuộc này vào một khái niệm chung là phụ thuộc logic. 
Việc nghiên cứu phụ thuộc logic trong mô hình dữ liệu quan hệ được nhiều 
tác giả quan tâm và các kết quả tìm thấy đã được sử dụng hữu ích trong quá 
trình thiết kế các cơ sở dữ liệu. 
 Tuy nhiên, trong mô hình dữ liệu dạng khối, cho đến hiện nay thì các 
phụ thuộc logic còn chưa được quan tâm nhiều, ví dụ như: các khái niệm về 
phụ thuộc Boolean dương, phụ thuộc Boolean dương tổng quát trên khối,... 
vẫn chưa có. Chính vì vậy, đề tài muốn đi sâu tìm hiểu xem trong mô hình dữ 
liệu dạng khối thì các phụ thuộc logic này sẽ được định nghĩa như thế nào? 
Chúng có những tính chất, đặc trưng gì? Mối quan hệ của chúng với các khái 
niệm tương ứng trong mô hình dữ liệu quan hệ như thế nào?,... và chắc rằng 
với các phụ thuộc logic mới được đề xuất trong mô hình dữ liệu dạng khối thì 
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. 
- Năm 1996 tác giả C. Dyreson đã đề xuất một mở rộng của mô hình 
dữ liệu quan hệ, đó là các khối dữ liệu (data cube) [17]. 
- Năm 1997, các tác giả R. Agrawal, A. Gupta, and S. Sarawagi đã 
đề xuất một mở rộng của mô hình dữ liệu quan hệ, đó là mô hình 
dữ liệu đa chiều (Modeling Multidimensional Databases) [41]. 
16 
- Năm 1997 các tác giả S. Chaudhuri and U. Dayal đã đề xuất khái 
niệm nhà kho dữ liệu (Data Warehousing) [49]. 
- Năm 2001 Paulraj Ponniah đã bàn về nhà kho dữ liệu trong bài báo 
“Data warehousing fundamentals” [38]. 
- Năm 2002 Inmon W.H. đã trình bày về việc xây dựng nhà kho dữ 
liệu trong bài báo “Building the Data Warehouse “ [26]. 
- Năm 2003 các tác giả Maurizio Rafanelli, M.Rafanelli, ... Q h, nghĩa là h BD(r). 
 Như vậy, ta đã chứng minh được: 
(i) g BD(r): Tr  Tg 
(ii)  h BD(r): Tr = Th 
kết hợp với định nghĩa của TBD(r) là giao của các Tg , g BD(r) ta suy ra: 
 Tr = TBD(r). 
94 
 Mệnh đề 3.8 
 Cho R = (id; A1,A2,...,An ), r(R) là một khối, r , U = 
n
i
i
1
)(id
,  là tập 
các PTBDTQ trên U. Khi đó khối r thể hiện chặt tập PTBDTQ  khi và chỉ 
khi: Tr = T . 
Chứng minh 
 Sử dụng tính chất: BD(r) = (BD(r)) + và từ mệnh đề về bảng chân lý của 
BD(r) , Tr = TBD(r) ta có: khối r thể hiện chặt tập PTBDTQ  BD(r) =  
+
 BD(r) =  TBD(r) = T Tr = T. 
 Nhận xét 
 Cho R = (id; A1,A2,...,An ), r(R) là một khối, r , U = 
n
i
i
1
)(id
,  là tập 
các PTBDTQ trên U. Khi đó, nếu id = {x} thì khối r suy biến thành quan hệ 
và ta có trong mô hình dữ liệu quan hệ: quan hệ r thể hiện chặt tập PTBDTQ 
 khi và chỉ khi: Tr = T . 
Kết luận 
 Chương này đã đề xuất các khái niệm mới như: phụ thuộc Boolean 
dương, phụ thuộc Boolean dương tổng quát,... Chứng minh các tính chất của 
ánh xạ đóng trên khối, điều kiện cần và đủ của tập thuộc tính chỉ số bất động, 
tập sinh, tập các đối nguyên tử,... Các tính chất, định lý tương đương,... của 
phụ thuộc Boolean dương, phụ thuộc Boolean dương tổng quát trên khối và 
các tính chất của thể hiện phụ thuộc Boolean dương tổng quát trên khối cũng 
đã được phát biểu và chứng minh ở đây. 
95 
KẾT LUẬN VÀ HƯỚNG NGHIÊN CỨU TIẾP THEO 
Sau khi đề xuất và nghiên cứu tính chất của các phụ thuộc logic trong 
mô hình dữ liệu dạng khối, luận án đã đạt được một số kết quả chính sau đây: 
- Đề xuất phép dịch chuyển lược đồ khối, các thuật toán dịch chuyển, 
chứng minh tính đúng và độ phức tạp của các thuật toán này. Chứng minh các 
tính chất về biểu diễn bao đóng của tập thuộc tính chỉ số và khóa của khối, 
khóa của lát cắt qua phép dịch chuyển. 
- Chứng minh các định lý cần và đủ về khóa của lược đồ khối, khóa của 
lát cắt ban đầu và khóa của lược đồ khối, khóa của lát cắt sau khi dịch chuyển. 
Chứng minh các định lý tương đương về bao đóng của tập thuộc tính chỉ số 
trên lát cắt và trên khối. 
- Đề xuất khái niệm lược đồ khối cân bằng, chứng minh các tính chất 
về mối quan hệ giữa các lược đồ cân bằng trên khối và trên các lát cắt. Chứng 
minh định lý cần và đủ để một lược đồ khối cân bằng, đưa ra thuật toán dịch 
chuyển lược đồ khối về dạng cân bằng, chứng minh tính đúng và độ phức tạp 
của nó. 
- Chứng minh một số tính chất của ánh xạ đóng trên khối, điều kiện cần 
và đủ của tập thuộc tính bất động, tập sinh,... Chứng minh một số định lý 
tương đương về khóa trên khối và trên các lát cắt. 
- Đề xuất khái niệm phụ thuộc Boolean dương trên khối, chứng minh 
định lý tương đương, một số điều kiện cần và đủ của các phép suy dẫn. 
Chứng minh các tính chất và mối quan hệ giữa các kiểu phụ thuộc hàm và các 
công thức Boolean dương trên khối, trên lát cắt. 
96 
- Đề xuất khái niệm phụ thuộc Boolean dương tổng quát trên khối, 
chứng minh định lý tương đương, các điều kiện cần và đủ của các phép suy 
dẫn đối với phụ thuộc Boolean dương tổng quát trên khối. Chứng minh điều 
kiện cần và đủ của thể hiện chặt một tập phụ thuộc Boolean dương tổng quát 
trên khối. 
Các kết quả nghiên cứu ở trên đã làm rõ thêm cấu trúc các phụ thuộc 
logic trong thiết kế của mô hình dữ liệu dạng khối. Trong trường hợp khối suy 
biến thành quan hệ, một số kết quả này lại trùng với các kết quả đã được 
nhiều tác giả đưa ra đối với quan hệ trong mô hình dữ liệu quan hệ. Một số 
kết quả khác được xét trong trường hợp riêng của tập các phụ thuộc hàm F 
trong lược đồ khối, như tập phụ thuộc hàm Fh, tập phụ thuộc hàm Fhx,... Trên 
cơ sở của các kết quả này, ta có thể nghiên cứu tiếp mối quan hệ giữa các loại 
phụ thuộc logic khác với phép dịch chuyển trên lược đồ khối, các trường hợp 
khác của các tập phụ thuộc hàm trên khối, trên lát cắt,.... Các kết quả nghiên 
cứu đó góp phần làm hoàn chỉnh thêm lí thuyết thiết kế của mô hình dữ liệu 
dạng khối. 
97 
DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ 
[1] Trịnh Đình Thắng, Trần Minh Tuyến (2010), Phép dịch chuyển lược 
đồ khối và vấn đề biểu diễn bao đóng, khóa trong mô hình dữ liệu 
dạng khối, Kỷ yếu Hội thảo quốc gia lần thứ XIII “Một số vấn đề 
chọn lọc của Công nghệ Thông tin và Truyền thông”, Hưng Yên, tr. 
276-286. 
[2] Trịnh Đình Thắng, Trần Minh Tuyến (2011), 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, 
Kỷ yếu Hội thảo quốc gia lần thứ 13 "Một số vấn đề chọn lọc của 
Công nghệ Thông tin và Truyền thông", Cần Thơ, tr. 159-170. 
[3] Trinh Dinh Thang, Tran Minh Tuyen (2012), Key and key attributes set, 
non-key attributes set with translation of block schemes, International 
Journal of Advanced Research in Computer Science, vol. 3, No.3, 
India, pp. 335-339. 
[4] Trịnh Đình Thắng, Trần Minh Tuyến (2012), Lược đồ 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, 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", Hà Nội, tr. 174-179. 
[5] Trần Minh Tuyến (2013), Lược đồ cân bằng với phép dịch chuyển lược 
đồ khối, Tạp chí khoa học và kỹ thuật, chuyên san Công nghệ Thông 
tin và Truyền thông số 2, Học viện kỹ thuật quân sự, Hà Nội, S.153, 
tr. 28-36. 
[6] Trịnh Đình Thắng, Trần Minh Tuyến (2013), Ánh xạ đóng và phép dịch 
chuyển lược đồ khối, Kỷ yếu Hội nghị quốc gia lần thứ VI về Nghiên 
cứu cơ bản và ứng dụng Công nghệ Thông tin (FAIR), Thừa Thiên–
98 
Huế, tr. 174-179. 
[7] Tran Minh Tuyen, Trinh Dinh Thang, Nguyen Xuan Huy (2015), Some 
properties of the positive boolean dependencies in the database model 
of block form, Journal of Computer Science and Cybernetics, V.31, 
N.2, Viet Nam, pp. 159-169. 
[8] Trần Minh Tuyến, Trịnh Đình Thắng (2014), Phụ thuộc Boole dương 
tổng quát trong mô hình dữ liệu dạng khối, Kỷ yếu Hội thảo quốc gia 
lần thứ XVII "Một số vấn đề chọn lọc của Công nghệ Thông tin và 
Truyền thông", Buôn Ma Thuột, tr. 274-279. 
99 
TÀI LIỆU THAM KHẢO 
[1] Nguyễn Xuân Huy, Lê Đức Minh, Vũ Ngọc Loãn (2000), Các ánh xạ 
đóng và ứng dụng trong cơ sở dữ liệu, Tạp chí Tin học và Điều khiển 
học, T.16, S.4, tr. 1-6. 
[2] 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, T.17, S.4, tr. 11-16. 
[3] Nguyễn Xuân Huy, Đàm Gia Mạnh, Vũ Thanh Xuân, Kim Lan Hương 
(2001), Về một lớp công thức suy dẫn, Tạp chí Tin học và Điều khiển 
học, T.17, S.4, tr. 17-22. 
[4] Nguyễn Xuân Huy, Trịnh Đình Thắng (1998), Mô hình cơ sở dữ liệu 
dạng khối, Tạp chí Tin học và Điều khiển học, T.14, S.3, tr. 52-60. 
[5] Nguyễn Xuân Huy, Trịnh Đình Thắng (1999), Một vài thuật toán cài đặt 
các phép toán của đại số quan hệ trong mô hình dữ liệu dạng khối, Tạp 
chí Tin học và Điều khiển học, T.15, S.3, tr. 8-17. 
[6] Nguyễn Xuân Huy (2006), Các phụ thuộc logic trong cơ sở dữ liệu, NXB 
Thống kê, Hà Nội. 
[7] Trịnh Đình Thắng (2001), Một số kết quả về bao đóng, khóa và phụ thuộc 
hàm trong mô hình dữ liệu dạng khối, Kỷ yếu Hội thảo quốc gia lần thứ 
IV “Một số vấn đề chọn lọc của Công nghệ Thông tin”, Hải Phòng, tr. 
245-251. 
[8] Trịnh Đình Thắng (2005), Một số kết quả về phụ thuộc hàm, phủ của các 
phụ thuộc hàm và các dạng chuẩn trong mô hình dữ liệu dạng khối, Kỷ 
yếu Hội thảo quốc gia lần thứ 8 "Một số vấn đề chọn lọc của Công nghệ 
Thông tin và Truyền thông", Hải Phòng, tr. 580-586. 
[9] Trịnh Đình Thắng, Trịnh Đình Vinh (2008), Phụ thuộc đa trị trong mô 
100 
hình dữ liệu dạng khối, Kỷ yếu Hội thảo quốc gia lần thứ 11 "Một số vấn 
đề chọn lọc của Công nghệ Thông tin và Truyền thông", Huế, tr. 321-328. 
[10] Trịnh Đình Thắng (2011), Mô hình dữ liệu dạng khối, NXB Lao động. 
[11] Vũ Đức Thi, Trịnh Đình Vinh (2009), Phụ thuộc đa trị xấp xỉ trong mô 
hình dữ liêu dạng khối, 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 và Truyền thông”, Biên Hoà, tr. 341-350. 
[12] Vũ Đức Thi, Trịnh Đình Vinh (2010), a-Phụ thuộc hàm và a-Bao đóng 
trong mô hình cơ sở dữ liêu dạng khối, Tạp chí Tin học và Điều khiển 
học, 26(2), tr. 131-139. 
[13] Trịnh Đình Vinh, Vũ Đức Thi (2010), Phủ của tập phụ thuộc hàm và 
vấn đề tựa chuẩn hoá trong mô hình dữ liêu dạng khối, Tạp chí Tin học 
và Điều khiển học, 26(4), tr. 312-320. 
TiÕng Anh: 
[14] Akrivi Vlachou, Christos Doulkeridis, Kjetil Norvag, Yannis Kotidis 
(2012), Peer-to-Peer Query Processing over Multidimensional Data 
(SpringerBriefs in Computer Science) Paperback, Springer; 2012 
edition. 
[15] Apostolos Benisis (2010), Business Process Management:: A Data 
Cube To Analyze Business Process Simulation Data For Decision 
Making Paperback, VDM Verlag Dr. Müller. 
[16] Brian Ciampa (2014), The Data Warehouse Workshop: Providing 
Practical Experience to the Aspiring ETL Developer Paperback, 
CreateSpace Independent Publishing Platform. 
[17] C. Dyreson (1996), Information retrieval from an incomplete data cube, 
In Proc. of the 22
nd
. Int. Conf. on Very Large Data Bases (VLDB) 
pages 532-543. Morgan Kaufmann Publishers. 
101 
[18] C. Imhoff, N. Galemmo, and J. G. Geiger.(2003), Mastering Data 
Warehouse Design: Relational and Dimensional Techniques. John 
Wiley. 
[19] Christian S.Jensen, Torben Bach Pedersen, Christian Thomsen, & 1 mo-
re (2010), Multidimensional Databases and Data Warehousing 
(Synthesis Lectures on Data Management) Paperback, Morgan and 
Claypool Publishers; 1 edition. 
[20] Daniel T. Larose (2006), Data mining method and models, Wiley-
interscience. A john wiley & sons, Inc Publication. 
[21] E. Thomsen. (1997), OLAP Solutions: Building Multidimensional 
Information Systems. John Wiley. 
[22] GARCIA-MOLINA H, ULLMAN J., WIDOM J.(2002), Database 
System: The Complete Book, Prentice Hall. 
[23] Haiping Lu, Konstantinos N. Plataniotis, Anastasios Venetsanopoulos 
(2013), Multilinear Subspace Learning: Dimensionality Reduction of 
Multidimensional Data (Chapman & Hall/Crc Machine Learning & 
Pattern Recognition) Hardcover, Chapman and Hall/CRC; 1 edition. 
[24] Hong Yao, Howard J. Hamilton, Cory J. Butz, FD_Mine (2002), 
“Discovering Functional Dependencies in a Database Using 
Equivalences”, Second IEEE International Conference on Data Mining. 
[25] Hu X.H., Lin T.Y. and Han J.C. (2004), A new rough sets model based 
on database systems, Fundamenta Informaticae, 59(1), pp. 135-152. 
[26] Inmon W.H. (2002), Building the Data Warehouse (Third Edition), John 
Wiley & Sons, Inc. 
[27] J. Widom (1995), Research problems in data warehousing. CIKM’95. 
102 
[28] John Paredes (2009), The Multidimensional Data Modeling Toolkit: 
Making Your Business Intelligence Applications Smart with Oracle 
OLAP Paperback, OLAP World Press. 
[29] Kwok-Wa Lam, Victor C.S.Lee (2004), Building Decision Trees Using 
Functional Dependencies, Processdings of the International 
Conference on Information Technology: Coding and Computing 
(ITCC’04). 
[30] K. M. Azharul Hasan, Tatsuo Tsuji (2011), Extendible Arrays for 
Multidimensional Databases: Concept, Implementation and 
Evaluation Paperback, LAP LAMBERT Academic Publishing. 
[31] Krish Krishnan (2013), Data Warehousing in the Age of Big Data (The 
Morgan Kaufmann Series on Business Intelligence) Paperback, Morgan 
Kaufmann; 1 edition. 
[32] Ladjel Bellatreche, Mukesh K. Mohania (2014), Data Warehousing and 
Knowledge Discovery: 16th International Conference, DaWaK 2014, 
Munich, Germany, September 2-4, 2014. Proceedings (Lecture Notes ... 
Applications, incl. Internet/Web, and HCI) Paperback, Springer; 2014 
edition. 
[33] Maier, D. (1983), The Theory of Relational Databases, Computer 
Science Press, Rockville, Md. 
[34] Maurizio Rafanelli, M.Rafanelli (2003), Multidimensional Databases: 
Problems and Solutions Hardcover, Idea Group Publishing. 
[35] M.Rafanelli(Ed.) (2003), Multidimensional Databases: Problems and 
Solutions, Idea Group. 
[36] Mark W. Humphries Michael W. Hawkins Michelle C. Dy (1998), Data 
Warehousing Architecture and Implementation, Prentice Hall PTR; 
Pap/ Cdr edition. 
103 
[37] OLAP council (1998). MDAPI specification version 2.0. In 
[38] Paulraj Ponniah (2001), Data warehousing fundamentals, John Wiley & 
Sons Inc. 
[39] P. O'Neil and D. Quass (1997), Improved query performance with 
variant indexes. SIGMOD'97. 
[40] Qiang Yang, Joshua Zhexue Huang, Michaeng Ng (2003), A data Cube 
Model for Prediction- Based Web Prefetching, Journal of Intelligent 
Information Systems, Vol. 20, Issue 1, pp. 11-30. 
[41] R. Agrawal, A. Gupta, and S. Sarawagi (1997), Modeling 
Multidimensional Databases, In Proc. of 13 th, Int. Conf. on Data 
Engineering (ICDE) pages 232-243. IEEE press. 
[42] R. Kimball and M. Ross (2002), The Data Warehouse Toolkit: The 
Complete Guide to Dimensional Modeling. 2ed. John Wiley. 
[43] Ralph Kimball, Margy Ross, Warren Thornthwaite, Joy Mundy, Bob 
Becker (2008), The Data Warehouse Lifecycle Toolkit Paperback, 
Wiley; 2 edition. 
[44] Ralph Kimball, Margy Ross (2013). The Data Warehouse Toolkit: The 
Definitive Guide to Dimensional Modeling Paperback, Wiley; 3 edition. 
[45] Ralph Kimball (2014), Kimball's Data Warehouse Toolkit Classics: 3 
Volume Set Paperback, Wiley; 2 edition. 
[46] Robert Laberge (2011), The Data Warehouse Mentor: Practical Data 
Warehouse and Business Intelligence InsightsPaperback, McGraw-Hill 
Osborne Media; 1 edition. 
[47] Sid Adelman, Larissa T. Moss (2000), Data Warehouse Project 
Management Paperback, Addison-Wesley Professional; 1 edition. 
104 
[48] Stanislaw Kozielski, Robert Wrembel (2008), New Trends in Data 
Warehousing and Data Analysis (Annals of Information Systems), 
Springer; 1st Edition. 2nd Printing. 
[49] S. Chaudhuri and U. Dayal (1997), An Overview of Data Warehousing 
and OLAP technology, SIGMOD Record, 26(1): pp. 65-74. 
[50] S. Sarawagi and M. Stonebraker (1994), Efficient organization of large 
multidimensional arrays, ICDE'94. 
[51] T.B. Pedersen and C.S. Jensen (1999), Multidemensional data Modeling 
for complex data, In proc. of 15
th
 Int. Conf. on data Engineering 
(ICDE) pages 336-345, IEEE Computer Society. 
[52] Thalheim B. (1987), Dependencies in relational databases , Teubner - 
Verlag, Leipzig. 
[53] Ullman, J. D. (1982), Principles of Database systems, Computer 
Science Press, Rockville, Md. 
[54] Ullman, J. D. (1989), Principles of Database and Knowlege - Base 
systems , vol.1,2 , Computer Science Press. 
[55] Vidette Poe (1996), Building A Data Warehouse for Decision Support, 
Prentice Hall PTR. 
[56] W. H. Inmon (2005), Building the Data Warehouse Paperback, Wiley; 
4 edition. 
[57] W. H. Inmon (1996), Building the Data Warehouse, John Wiley. 
[58] Ziv Pollak (2009), Cube Based Incremental Data Mining: Using Multi-
Dimensional Cubes for Incremental Data Mining Paperback, VDM 
Verlag.