S
ố hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn



LỜI CAM ĐOAN

Tôi xin cam đoan luận văn này là do bản thân tự nghiên cứu và thực hiện
theo sự hƣớng dẫn khoa học của thầy PGS. TS. Lê Huy Thập
Tôi hoàn toàn chịu trách nhiệm về tính pháp lý quá trình nghiên cứu khoa
học của luận văn này.

Ngƣời Cam Đoan Nguyễn Văn Chung

ii
S
ố hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn

LỜI CẢM ƠN

Lời đầu tiên tôi xin gửi lời cảm ơn đến thầy giáo PGS. TS. Lê Huy Thập
đã định hƣớng, hƣớng dẫn và giúp đỡ tôi rất nhiều về mặt chuyên môn trong
quá trình tìm hiểu và thực hiện luận văn.
Tôi xin gửi lời biết ơn sâu sắc đến các thầy, các cô đã dạy dỗ và truyền
đạt những kinh nghiệm quý báu cho chúng tôi trong suốt hai năm cao học ở
trƣờng Đại học Công nghệ thông tin và truyền thông Thái Nguyên.
Cuối cùng, xin chân thành cảm ơn gia đình và bạn bè đã động viên, quan
tâm, giúp đỡ tôi hoàn thành khóa học và luận văn. Thái nguyên, tháng 09 năm 2013

1.3. Kết luận chƣơng 1 25
Chƣơng 2: MÔ HÌNH TỐI ƢU HÓA TRUY VẤN HAI PHA 26
2.1. Mô hình tối ƣu hóa truy vấn hai pha JOQR 26
2.1.1. Cây truy vấn tiền xử lý 26
2.1.2. Cây toán tử 29
2.2. Tối ƣu hóa giai đoạn JOQR 31
iv
S
ố hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn

2.2.1. Cực tiểu hóa chi phí phân mảnh lại 32
2.2.2. Khả phân mảnh và toán tử cảm thuộc tính 34
2.2.3. Bài toán tối ƣu hóa 37
2.3. Kết luận chƣơng 2 48
Chƣơng 3: CHƢƠNG TRÌNH THỬ NGHIỆM 49
3.1. Ứng dụng tại trƣờng Cao đẳng kinh tế - kỹ thuật Vĩnh Phúc (Dạng demo) 49
3.1.1. Giới thiệu CSDL của trƣờng Cao đẳng kinh tế - kỹ thuật Vĩnh Phúc 49
3.1.2. Cực tiểu hóa chi phí phân mảnh lại CSDL tại mục 3.1.1 62
3.2. Kết luận chƣơng 3 66
KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN CỦA LUẬN VĂN 67
TÀI LIỆU THAM KHẢO 68

v
S
ố hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn

DANH MỤC CÁC KÝ HIỆU, VIẾT TẮT

DBMS (Database management system)
ESPS (Executor Sever Process)

Hình 1-4. Các loại cây 13
Hình1–5. Xây dựng tối ưu hoá một cách đơn định theo kiểu quy hoạch động 14
Hình 1-6. Hành động của thể tối ưu hoá trong một chiến lược ngẫu nhiên hoá 15
Hình 1-7. Truyền dữ liệu trong câu vấn tin 17
Hình 2-1. Cây truy vấn tiền xử lý 27
Hình 2-2. Cây toán tử tương ứng với cây trong hình 2-1 31
Hình 2-3. Sơ đồ phân mảnh ngang dữ liệu tại các nút 33
Hình 2-4. Các cây truy vấn khác nhau về phân hoạch dữ liệu, đường nét đứt cho
thấy phải phân bố lại quan hệ 33
Hình 2-5. Cây toán tử tương ứng với câu truy vấn 37
Hình 2-6. Cây gốc và các phương án tô màu 39
Hình 2-7. Đồ thị vấn tin 42
Hình 2-8. Cây nối của đồ thị vấn tin trên hình 2-7 43
Hình 2-9. Ảnh hưởng của thứ tự phép nối đến chi phí phân mảnh ngang 43
Hình 3-1. Sơ đồ kết nối các quan hệ 53
Hình 3-2. Màn hình chính của chương trình 54
Hình 3-3. Cây truy vấn ban đầu của ví dụ 1 55
Hình 3-4. Cây sau khi sắp lại phép nối ví dụ 1 55
Hình 3-5. Màn hình nhập câu truy vấn 56
Hình 3-6. Câu truy vấn ban đầu và sau biểu diễn lại ví dụ 1 56
Hình 3-7. Kết quả của câu truy vấn ví dụ 1 57
Hình 3-8. Cây truy vấn ban đầu của ví dụ 2 58
viii
S
ố hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn

Hình 3-9. Cây sau khi sắp lại phép nối ví dụ 2 58
Hình 3-10. Giao diện câu truy vấn ban đầu và sau biểu diễn lại ví dụ 2 59
Hình 3-11. Kết quả của câu truy vấn ví dụ 2 59
Hình 3-12. Cây truy vấn ban đầu của ví dụ 3 60

Các biểu thức logic
Cơ sở dữ liệu phân tán
Xử lý song song và phân tán
3. Hƣớng nghiên cứu của đề tài
Các dạng chi phí song song
Nghiên cứu mô hình tối ƣu hóa hai pha.
4. Những nội dung nghiên cứu chính
Luận vă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 tài liệu tham khảo.
Chƣơng 1: Cơ sở lý thuyết
Chƣơng 2: Mô hình tối ƣu hóa truy vấn hai pha
Chƣơng 3: Chƣơng trình thử nghiệm
Kết luận và hƣớng phát triển của luận văn
2
S
ố hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn

5. Phƣơng pháp nghiên cứu
Nghiên cứu kỹ các kiến thức, chủ đề có liên quan đến đề tài.
Nghiên cứu các mô hình chi phí song song và mô hình chi phí song
song trên bộ tối ƣu hóa truy vấn.
Nắm vững các kiến thức cơ bản của tối ƣu hóa hai pha.
6. Ý nghĩa khoa học của đề tài
Luận văn giúp cho việc tối ƣu hóa câu truy vấn phân tán bằng phƣơng
pháp hai pha.
3
S
ố hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn

Chƣơng 1: CƠ SỞ LÝ THUYẾT

Bảng 1-1. Bảng chân trị các phép toán mệnh đề
1.1.5. Thứ tự ƣu tiên của các phép toán logic
Thứ tự ƣu tiên của các phép toán logic đƣợc liệt kê theo mức ƣu tiên từ
trên xuống dƣới, từ trái sang phải ở bảng 1-2:
Bảng 1-2. Thứ tự ưu tiên của các phép toán
Ký hiệu phép toán
Nghĩa của phép toán
, ,

Phủ định
,
Hội, tuyển
,
Kéo theo, Kéo theo hai chiều
Ghi chú:
Nếu các phép toán trong cùng một dòng có thứ tự nhập nhằng hoặc
muốn chỉ ra mức ƣu tiên của phép toán thì cần bổ sung thêm dấu ( ).
Ví dụ 1.1.4:

qp
có nghĩa là
)q(p
.
Còn
rqp
để ƣu tiên phép toán hay cần cho thêm dấu () để chỉ rõ
sự ƣu tiên, chẳng hạn
r)q(p
.
1.1.6. Biểu thức logic

1
0
1
1
0
0
0
1
1
0
0
1
1
1
0
1
1
0
1
1
0
5
S
ố hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn

P = E, F G, (G H) ( G E), ; trong đó P, E, F, G, H là các biểu
thức logic.
Bảng chân trị của các biểu thức logic là bảng liệt kê chân trị có thể có
theo mọi khả năng chân trị của các biến mệnh đề có trong biểu thức
Hai biểu thức logic E và F đƣợc gọi là tƣơng đƣơng và viết E F khi và

E
1
= p p thì E
1
1.
E
1
= (p q) ( p q) thì E
1
1.
Quan hệ bắc cầu: Nếu E F và F G thì E G.
6
S
ố hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn

1.1.7. Các luật logic
i. Luật phủ định của phủ định
p p
ii. Luật giao hoán
p q q p
p q q p
iii. Luật kết hợp
p (q r) (p q) r
p (q r) (p q) r
iv. Luật phân phối
p (q r) (p q) (p r)
p (q r) (p q) (p r)
v. Luật Demorgan
(p q) p q
(p q) p q

1.1.9. Quy tắc bất biến đối với biểu thức logic hằng True
Cho E là một biểu thức logic hằng True, nếu thay thế một biến mệnh đề
p nào đó trong E bởi một biểu thức logic bất kỳ ta sẽ nhận đƣợc biểu thức
logic E' mới cũng là hằng True.
Ví dụ 1.1.11:
E = (p q) ( p q) thì E 1(E là hằng True).
Bây giờ ta thay thế q trong E bởi q r ta sẽ đƣợc:
E' = (p (q r)) ( p (q r)) theo quy tắc 2 ta cũng có E' 1.
1.1.10. Biểu thức hội cơ bản
Biểu thức logic F = F (p
1
, p
2
, , p
n
), trong đó p
i
(i =
n,1
) là các biến
mệnh đề sơ cấp, đƣợc gọi là biểu thức hội cơ bản, nếu:
8
S
ố hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn

F = q
1
q
2
q

E = q
1
q
2
q
n
: với q
i
= p
i
hoặc q
i
=
i
p
(i =
n,1
).
Ví dụ 1.1.13:
F(x, y, z) = x
y
z, trong đó x, y, z là các biến mệnh đề sơ cấp.
1.1.12. Biểu thức tuyển chính tắc
Biểu thức logic E = E (p
1
, p
2
, , p
n
), trong đó p

x
y z), E
3
= (x y z) là các biểu
thức hội cơ bản
Định lý 1.1.1:
Mọi biểu thức logic E (p
1
, p
2
, , p
n
) đều tƣơng đƣơng với một biểu thức
tuyển chính tắc duy nhất. Tức E (p
1
, p
2
, , p
n
) E
1
E
2
E
m
(duy
nhất) với E
i
(i =
m,1

(i =
n,1
) là các biến
mệnh đề sơ cấp, đƣợc gọi là dạng hội chính tắc, nếu:
9
S
ố hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn

F = F
1
F
2
F
n
: với F
i
(i =
n,1
) là biểu thức tuyển cơ bản của các p
i
Ví dụ 1.1.15:
F(p
1
, p
2
, p
3
) = (p
1


1
p
p
2
p
3
), F
3
= (
1
p
p
2
p
3
) là
các biểu thức tuyển cơ bản.
Định lý 1.1.2:
Mọi biểu thức logic F (p
1
, p
2
, , p
n
) đều tƣơng đƣơng với một biểu thức
hội chính tắc duy nhất. Tức F (p
1
, p
2
, , p

(i =
n,1
).
1.2. Tổng quan về CSDL phân tán
Tối ƣu hóa vấn tin là tìm phƣơng án thực hiện câu vấn tin để tiêu tốn ít
nhất thời gian hoặc kinh phí (một hàm mục tiêu nào đó). Thể tối ƣu hóa vấn
tin, là một phần mềm chịu trách nhiệm thực hiện tối ƣu hóa câu vấn tin, nó
đƣợc tạo ra bới ba thành phần: Không gian tìm kiếm, mô hình chi phí và
chiến lƣợc tìm kiếm (xem hình l-1).
Hình 1-1. Quá trình tối ưu hoá vấn tin

CÂU VẤN TIN
QEP TỐT NHẤT
QEP TƢƠNG ĐƢƠNG
Phƣơng pháp
tìm kiếm
Qui tắc biến đổi
câu vấn tin

Mô hình chi phí,
hay hàm mục
tiêu

Tạo ra không gian
tìm kiếm

10
S
ố hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn


Để nêu bật các đặc trƣng của thể tối ƣu hoá vấn tin, chúng ta thƣờng tập
trung nghiên cứu các cây nối là loại cây toán tử với các phép toán nối hoặc
phép toán tích Descartes hoặc phép toán hợp.
Ví dụ 1.2.1:
Xét cơ sở dữ liệu của công ty, với các quan hệ (hình 1-2) nhƣ sau:

Hình 1-2. Sơ đồ kết nối các quan hệ
Trong đó:
Quan hệ PROJ: Projects - Các dự án
PNO: Mã dự án
PNAME: Tên dự án
BUDGET: Ngân sách dự án
LOC: Location - Nơi triển khai dự án
Quan hệ PAY: Payments - Chi trả lương
TITLE - Trình độ chuyên môn
SAL: Salary - Lƣơng
Quan hệ EMP: Employees - Nhân công
ENO: Mã nhân công
ENAME: Tên nhân công
TITLE - Trình độ chuyên môn
12
S
ố hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn

Quan hệ ASG: Assignments - Phân công công việc
ENO, PNO
RESP: Responsibility - Đảm trách (Nhiệm vụ)
DUR: Duration - Thời gian làm việc
Xét câu vấn tin “Cho biết tên nhân viên đang tham gia một dự án nào đó”
SELECT ENAME
PROJEMPEMP

ASG

PROJ

(a)
(b)
PROJEMPASG
13
S
ố hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn


R
4
R
2
R
1

R
1
R
2
(a) Cây tuyến tính

(b) Cây xum xuê
14
S
ố hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn Hình1–5. Xây dựng tối ưu hoá một cách đơn định theo kiểu quy hoạch động
Để hạ thấp chi phí tối ƣu hoá, trong quá trình xây dựng phƣơng án có thể

TR
* #bytes
Hai thành phần đầu là thời gian xử lý cục bộ, trong đó T
CPU
là thời gian xử
lý một chỉ thị (lệnh) của CPU và #insts là số chỉ thị; T
I/O
là thời gian cho một
xuất, nhập đĩa và I/Os số lần xuất nhập đĩa; T
MSG
là thời gian cố định để khởi
hoạt và nhận một thông báo và #msgs là số thông báo; T
TR
là thời gian cần để
truyền một đơn vị dữ liệu từ vị trí này sang vị trí khác, đơn vị dữ liệu ở đây tính
theo byte (#bytes là số đơn vị dữ liệu), nhƣng cũng có thể tính theo những đơn
vị khác. Những nghiên cứu đầu tiên cho thấy trên WAN, tỷ số giữa thời gian
truyền và thời gian xuất nhập là 20:1, vì vậy đa phần các hệ DBMS phân tán
đƣợc thiết kế trên WAN đều bỏ qua chi phí xử lý cục bộ, hơn nữa chi phí T
MSG

* #msgs cũng đƣợc xem là nhƣ nhau và chúng ta giả thiết T
TR
là một giá trị
không đổi. Điều này có thể không đúng trong các mạng WAN, vì khoảng cách
giữa các vị trí không bằng nhau. Tuy nhiên giả thiết ấy làm đơn giản quá trinh
tối ƣu hóa rất nhiều. Vì thế thời gian truyền #bytes dữ liệu từ vị trí này đến vị
trí khác đƣợc giả thiết là một hàm tuyến tính theo #bytes:
R
2

CT(#bytes) = T
MSG
+ T
TR
* #byte
Chi phí nói chung đƣợc diễn tả theo đơn vị thời gian, và từ đó cũng có
thể chuyển thành đơn vị tính toán khác nhƣ tiền tệ chẳng hạn.
Topo mạng có ảnh hƣởng rất lớn đến tỷ số giữa các thành phần này.
Trong mạng WAN và Internet, thời gian truyền thông thƣờng chiếm đa phần.
Tuy nhiên trong các mạng LAN thì vì tốc độ lớn nên thành phần truyền thông
cân bằng hơn. Vì thế phần lớn các hệ DBMS phân tán đƣợc thiết kế trên các
mạng WAN đều bỏ qua chi phí xứ lý cục bộ và tập trung vào vấn đề cực tiểu
hóa chi phí truyền. Ngƣợc lại các DBMS phân tán đƣợc thiết cho mạng LAN
đều xét đến cả ba thành phần chi phí này. Các mạng nhanh hơn, cả loại WAN
lẫn LAN thiên về chi phí truyền khi tất cả mọi thứ khác đều nhƣ nhau. Tuy
nhiên thời gian truyền vẫn là một yếu tố chiếm đa phần trong các mạng WAN
và lnternet bởi vì dữ liệu cần phải đƣợc di chuyển đi đến các vị từ xa hơn.
Khi thời gian đáp ứng vấn tin là hàm mục tiêu của thể tối ƣu hoá, chúng
ta cần phải xét đến vấn đề xử lý cục bộ song song và truyền song song. Công
thức tổng chi phí là:
Total_time = T
CPU
* seq_#insts + T
I/O
* seg_#I/Os
+ T
MSG
* seg_#msgs + T
TR
* seg_#bytes