..

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THƠNG

NGUYỄN VĂN CHUNG

MƠ HÌNH TỐI ƢU HĨA TRUY VẤN HAI PHA
TRONG CƠ SỞ DỮ LIỆU VÀ ỨNG DỤNG
Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Ngƣời hƣớng dẫn khoa học: PGS.TS LÊ HUY THẬP

Thái Nguyên - 2013
Số hóa bởi Trung tâm Học liệu




i
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 hồn tồ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

Số hóa bởi Trung tâm Học liệu




ii
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 chun mơn trong
q 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 hồn thành khóa học và luận văn.
Thái nguyên, tháng 09 năm 2013
Tác giả
Nguyễn Văn Chung

Số hóa bởi Trung tâm Học liệu




iii
MỤC LỤC
LỜI CAM ĐOAN .............................................................................................. i
LỜI CẢM ƠN ................................................................................................... ii
MỤC LỤC ........................................................................................................ iii
DANH MỤC CÁC KÝ HIỆU, VIẾT TẮT ...................................................... v

DANH MỤC CÁC BẢNG............................................................................... vi
DANH MỤC CÁC HÌNH VẼ ........................................................................ vii
MỞ ĐẦU ........................................................................................................... 1
1. Đặt vấn đề...................................................................................................... 1
2. Đối tƣợng và phạm vi nghiên cứu ................................................................. 1
3. Hƣớng nghiên cứu của đề tài ........................................................................ 1
4. Những nội dung nghiên cứu chính ................................................................ 1
Chƣơng 1: CƠ SỞ LÝ THUYẾT ...................................................................... 3
1.1. Giới thiệu về logic ...................................................................................... 3
1.2. Tổng quan về CSDL phân tán .................................................................... 9
1.2.1. Khơng gian tìm kiếm .......................................................................................10
1.2.2. Các chiến lƣợc tìm kiếm ..................................................................................13
1.2.3. Mơ hình chi phí phân tán .................................................................................15
1.2.4. Các dạng chi phí song song và mơ hình chi phí song song trên bộ tối ƣu hóa
truy vấn........................................................................................................................22
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
Số hóa bởi Trung tâm Học liệu




iv
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à tốn tử cảm thuộc tính .....................................................34
2.2.3. Bài tố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

Số hóa bởi Trung tâm Học liệu




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

DBMS (Database management system)
ESPS (Executor Sever Process)
JOQR (Join Ordering and Query Rewriting)
LAN (Local Area Network)
QEP (Query Execution Plan)
SPJ (Selection Projection Joint)
SQL (Structured Query Language)
WAN (Wide area network)
TW (Total Work)
RT (Response Time)
MC (Memory Consumption)

Số hóa bởi Trung tâm Học liệu





vi
DANH MỤC CÁC BẢNG
Bảng 1-1. Bảng chân trị các phép toán mệnh đề .............................................. 4
Bảng 1-2. Thứ tự ưu tiên của các phép tốn ..............................................................4

Số hóa bởi Trung tâm Học liệu




vii
DANH MỤC CÁC HÌNH VẼ
Hình 1-1. Q trình tối ưu hố vấn tin .......................................................................9
Hình 1-2. Sơ đồ kết nối các quan hệ .........................................................................11
Hình 1-3. Các cây nối tương đương .........................................................................12
Hình 1-4. Các loại cây ...............................................................................................13
Hình1–5. Xây dựng tối ưu hố 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 hố ...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 tố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
Số hóa bởi Trung tâm Học liệu




viii
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
Hình 3-13. Cây sau khi xếp lại phép nối của ví dụ 3 ...............................................61
Hình 3-14. Giao diện câu truy vấn ban đầu và sau biểu diễn lại ví dụ 3 ...............61
Hình 3-15. Kết quả của câu truy vấn ví dụ 3............................................................62
Hình 3-16. Sơ đồ phân mảnh ngang dữ liệu tại các nút của ví dụ 1.......................62
Hình 3-17. Cây gốc và các phương án tơ màu của ví dụ 1 .....................................63
Hình 3-18. Giao diện pha 2 của ví dụ 1....................................................................63
Hình 3-19. Giao diện kết quả pha 2 của ví dụ 1.......................................................64
Hình 3-20. Sơ đồ phân mảnh ngang dữ liệu tại các nút của ví dụ 2.......................64
Hình 3-21. Cây gốc và các phương án tơ màu của ví dụ 2 .....................................65

Hình 3-22. Giao diện pha 2 của ví dụ 2....................................................................65
Hình 3-23. Giao diện kết quả pha 2 của ví dụ 1.......................................................66

Số hóa bởi Trung tâm Học liệu




1
MỞ ĐẦU
1. Đặt vấn đề
Tối ƣu hóa vấn tin là quá trình tìm một phƣơng án thực hiện câu vấn tin
QEP (Query Execution Plan) tối ƣu (theo nghĩa hạ thấp tối đa hàm chi phí,
hoặc cực đại hàm lợi ích ở một dạng nào đó). Tối ƣu câu truy vấn trong cơ sở
dữ liệu song song bằng mơ hình tối ƣu hóa truy vấn hai pha bao gồm:
i. Sắp xếp lại thứ tự các phép nối
ii. Biểu diễn lại cây truy vấn.
Bộ tối ƣu hóa thực hiện hai bƣớc này để tạo ra một cây truy vấn tiền xử
lý, xác định những yếu tố nhƣ thứ tự thực hiện các phép toán và chiến lƣợc
thực hiện mỗi phép toán. Bộ tối ƣu sẽ triển khai các mơ hình và giải thuật
song song để tìm kiếm một phƣơng án tốt nhất cho việc thi hành song song.
2. Đối tƣợng và phạm vi nghiên cứu
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
Số hóa bởi Trung tâm Học liệu




2
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.

Số hóa bởi Trung tâm Học liệu




3
Chƣơng 1: CƠ SỞ LÝ THUYẾT
1.1. Giới thiệu về logic
1.1.1. Khái niệm về mệnh đề và chân trị
Một mệnh đề là một phát biểu nào đó mà chỉ cho hai giá trị: True hoặc

False. Giá trị True, hoặc False của một mệnh đề đƣợc gọi là chân trị của mệnh
đề. Chân trị True đƣợc viết là 1, chân trị False đƣợc viết là 0
Ví dụ 1.1.1:

"6 là số chẵn" - mệnh đề đúng nên chân trị 1.
"6 là số nguyên tố" - mệnh đề sai nên chân trị 0.

1.1.2. Mệnh đề sơ cấp
Là mệnh đề không thể phân nhỏ hơn đƣợc nữa - có thể nói mệnh đề sơ
cấp là một phát biểu đơn giản nhất.
Ví dụ 1.1.2: "Số chẵn chia hết cho hai".
Các mệnh đề sơ cấp thƣờng đƣợc gắn với các ký hiệu là các ký tự viết
thƣờng: p, q, r, ... mà ta gọi là các biến mệnh đề hay biến logic.
1.1.3. Mệnh đề phức hợp
Mệnh đề phức hợp là mệnh đề đƣợc tạo ra từ các mệnh đề sơ cấp hoặc
các mệnh đề phức hợp khác bằng cách dùng các từ liên kết, AND - "và", OR "hoặc", ...
Ví dụ 1.1.3: "Số 2 là số chẵn và là số nguyên tố" gồm 2 mệnh đề "Số 2 là
số chẵn" từ nối "và" và "Số 2 là số nguyên tố"
1.1.4. Các phép toán mệnh đề
(phủ định);
theo);

(hội);

(tuyển);

(hoặc hay tổng trực giao);

(kéo


(kéo theo hai chiều),... chân trị từng trƣờng hợp đƣợc cho trong

bảng 1-1:

Số hóa bởi Trung tâm Học liệu




4
Bảng 1-1. Bảng chân trị các phép toán mệnh đề
P

q

0

0

1

0

0

0

1

1


0

0

1

1

0

1

1

1

0

1

1

0

0

0

1


1

0

0

1

1

1

0

1

1

0

1

1

0

p

p


q

p

q

p

q

p

q

p

q

p

q

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 tố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 tốn thì cần bổ sung thêm dấu ( ).
Ví dụ 1.1.4:
p

q có nghĩa là p

( q) .

Còn p q r để ƣ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 (p q ) r .

1.1.6. Biểu thức logic
Biểu thức logic có thể nói chính là mệnh đề phức hợp, biểu thức logic
thƣờng đƣợc ký hiệu bởi các chữ in hoa
Ví dụ 1.1.5:
E= p

(q

r) )

(r s)

Số hóa bởi Trung tâm Học liệu




5
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à

chỉ khi E và F ln có cùng chân trị.
Để kiểm tra xem hai biểu thức logic có tƣơng đƣơng với nhau hay không
chúng ta dựa vào bảng chân trị hay bằng phƣơng pháp chứng minh logic.
Ví dụ 1.1.6:
Cho hai biểu thức logic E = p

q và F = p

q thì E

F.

Biểu thức logic E đƣợc gọi là hằng True nếu chân trị của E luôn luôn là
1, tức là E

1.

Ví dụ 1.1.7:
p thì E là hằng đúng vì E

E=p

1.

Biểu thức logic E đƣợc gọi là hằng False nếu chân trị của E luôn luôn là

0, tức là E

0.

Ví dụ 1.1.8:
E=p

p thì E

0.

Chú ý:
Theo định nghĩa E1

F1 khi và chỉ khi E1

F1, điều này có thể viết

gọn nhƣ sau:
E1

F1

1.

Ví dụ 1.1.9:
E1 = p

p thì E1


E1 = (p

q)

( p

1.
q) thì E1

Quan hệ bắc cầu: Nếu E

Số hóa bởi Trung tâm Học liệu

F và F

1.
G thì E

G.




6
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

vi. Luật về phản tử bù
p


p

1

p

p

0

vii. Luật kéo theo
p

q

p

q

viii. Luật tƣơng đƣơng
p

q

(p

q)

(q


p)

ix. Các luật đơn giản của phép tuyển
p

p

p

p

1

1

p

0

p

Số hóa bởi Trung tâm Học liệu




7
p


(p

q)

p

x. Các luật đơn giản của phép hội
p

p

p

p

1

p

p

0

0

p

(p

q)


p

1.1.8. Quy tắc thay thế tƣơng đƣơng
Cho E là một biểu thức logic, nếu thay thế một biểu thức con của nó bởi
một biểu thức tƣơng đƣơng với biểu thức con đó, biểu thức logic E' mới nhận
đƣợc sẽ tƣơng đƣơng với E
Ví dụ 1.1.10:
E= p

q
q, do đó ta có thể thay thế q bởi

Vì q
E' = = p

q và đƣợc

q

Dùng bảng chân trị cho E và E' ta sẽ thấy E

E'.

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
E' = (p

(q

r))

( p

(q

r ta sẽ đƣợc:

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 (p1, p2, ..., pn), trong đó pi (i = 1, n ) 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:
Số hóa bởi Trung tâm Học liệu





8
F = q1

q2

qn : với qi = pi hoặc qi = p i (i = 1, n ).

....

Ví dụ 1.1.12:
F(x, y, z) = x

z, trong đó x, y, z là các biến mệnh đề sơ cấp.

y

1.1.11. Biểu thức tuyển cơ bản
Biểu thức logic E = E (p1, p2, ..., pn), trong đó pi (i = 1, n ) là các biến
mệnh đề sơ cấp, đƣợc gọi là biểu thức tuyển cơ bản, nếu:
E = q1

q2

....

qn : với qi = pi hoặc qi = p i (i = 1, n ).


Ví dụ 1.1.13:
F(x, y, z) = x

z, trong đó x, y, z là các biến mệnh đề sơ cấp.

y

1.1.12. Biểu thức tuyển chính tắc
Biểu thức logic E = E (p1, p2, ..., pn), trong đó pi (i = 1, n ) là các biến
mệnh đề sơ cấp, đƣợc gọi là dạng tuyển chính tắc, nếu:
E = E1

E2

En : với Ei (i = 1, n ) là biểu thức hội cơ bản của các pi

....

Ví dụ 1.1.14:
E(x, y, z) = (x

y

z)

(x

y


chính tắc vì E1 = (x

y

z), E2 = ( x

z)
y

(x

y

z), là biểu thức tuyển

z), E3 = (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 (p1, p2, ..., pn) đều tƣơng đƣơng với một biểu thức
tuyển chính tắc duy nhất. Tức E (p1, p2, ..., pn)

E1

E2


....

Em (duy

nhất) với Ei (i = 1, m ) là các biểu thức hội cơ bản.
Ei = q1

q2

....

qn với qi = pi hoặc qi = p i (i = 1, n ).

1.1.13. Biểu thức hội chính tắc
Biểu thức logic F = F (p1, p2, ..., pn), trong đó pi (i = 1, n ) là các biến
mệnh đề sơ cấp, đƣợc gọi là dạng hội chính tắc, nếu:

Số hóa bởi Trung tâm Học liệu




9
F = F1

F2

....

Fn : với Fi (i = 1, n ) là biểu thức tuyển cơ bản của các pi


Ví dụ 1.1.15:
F(p1, p2, p3) = (p1

p2

tuyển chính tắc vì F1 = (p1

p3)
p2

( p1

p2

p3), F2 = ( p1

p3)
p2

(p1

p2

p3), là biểu thức

p3), F3 = ( p1

p2


p3) 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 (p1, p2, ..., pn) đều tƣơng đƣơng với một biểu thức
hội chính tắc duy nhất. Tức F (p1, p2, ..., pn)

F1

F2

....

Fm (duy nhất)

với Fi (i = 1, m ) là các biểu thức tuyển cơ bản.
Ei = q1

q2

....

qn với qi = pi hoặc qi = p i (i = 1, n ).

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).

CÂU VẤN TIN

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

Qui tắc biến đổi
câu vấn tin

QEP TƢƠNG ĐƢƠNG

Phƣơng pháp
tìm kiếm

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

QEP TỐT NHẤT

Hình 1-1. Q trình tối ưu hố vấn tin

Số hóa bởi Trung tâm Học liệu




10
Khơng gian tìm kiếm là tập các phƣơng án có thể thực hiện câu vấn tin.
Những phƣơng án này là tƣơng đƣơng, theo nghĩa là chúng sinh ra cùng một
kết quả nhƣng khác nhau về cách thực hiện. Do khác nhau về cách thực hiện vì

thế khác nhau về hiệu năng. Khơng gian tìm kiếm thu đƣợc bằng cách áp dụng
các qui tắc biến đổi, chẳng hạn những qui tắc của phép tốn đại số quan hệ.
Mơ hình chi phí làm nhiệm vụ tiên đoán chi phi của một phƣơng án thực
hiện đã cho. Để làm điều này, mơ hình chi phí phải có đủ thơng tin cần thiết
về mơi trƣờng thực hiện phân tán.
Chiến lƣợc tìm kiếm sẽ tìm trong khơng gian tìm kiếm để chọn ra
phƣơng án tốt nhất dựa theo mơ hình chi phí. Nó xác định các phƣơng án nào
cần đƣợc kiểm tra và theo thứ tự nào. Chi tiết về môi trƣờng (tập trung hay
phân tán) đƣợc ghi nhận trong khơng gian tìm kiếm và mơ hình chi phí.
1.2.1. Khơng gian tìm kiếm
Khơng gian tìm kiếm là tập các QEP biểu diễn cho câu vấn tin. Các QEP
là tƣơng đƣơng, theo nghĩa chúng sinh ra cùng một kết quả nhƣng khác nhau
ở thứ tự thực hiện các thao tác cài đặt, vì thế sẽ khác nhau về hiệu năng.
Khơng gian tìm kiếm thu đƣợc bằng cách áp dụng các qui tắc biến đổi. Mơ
hình (hàm) chi phí đƣợc dùng để chỉ ra chi phí của QEP tƣơng ứng. Chiến
lƣợc tìm kiếm làm nhiệm vụ tìm kiếm, khám phá khơng gian tìm kiếm và chọn
ra QEP tốt nhất dựa theo mơ hình chi phí. Nó xác định xem QEP nào đƣợc
kiểm tra và theo thứ tự nào. Một QEP tƣơng đƣơng với một cây toán tử.
Cây tốn tử là một đồ thị vơ hƣớng, khơng chu trình, đƣợc dùng để thể
hiện một câu vấn tin bậc thấp (Đại số quan hệ), gốc là các trƣờng nằm sau
SELECT, lá là các quan hệ cơ sở nằm sau FROM, và các nút là các phép toán
nằm sau WHERE nhƣng đƣợc chuyển sang dạng phép toán đại số quan hệ.
Cách thực hiện các phép toán trên cây theo hƣớng từ lá về gốc.

Số hóa bởi Trung tâm Học liệu




11

Để 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 tốn nối hoặc
phép tốn tích Descartes hoặc phép tố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 độ chun mơn
Số hóa bởi Trung tâm Học liệu




12
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
FROM

EMP , ASG , PROJ

WHERE

(EMP.ENO = ASG.ENO)

AND

(ASG.PNO = PROJ.PNO)

Câu vấn tin này sinh ra ba cây nối tƣơng đƣơng ở hình 1-3
PNO

ENO

EMP

ASG

ENO

PROJ

PNO

ASG


ENO, PNO

EMP

PROJ

ASG

PROJ

(b)

(a)

EMP

(c)

Hình 1-3. Các cây nối tương đương
Với câu vấn tin đã cho, số cây toán tử tƣơng đƣơng sẽ rất nhiều có thể
lên tới O(n!) với n quan hệ, nên ngƣời ta thƣờng dùng các phƣơng pháp
heuristic chẳng hạn: thực hiện phép chọn và chiếu khi truy xuất đến các quan
hệ cơ sở, hoặc tránh lấy các cây có tích Descartes (tức là bỏ cây c trong hình
1-3, vì phép tích Descartes tạo ra nhiều bộ).
Một cây tốn tử đƣợc gọi là tuyến tính nếu tại mỗi nút tốn tử có ít nhất
một tốn hạng là một quan hệ cơ sở (hình 1-4a).

Số hóa bởi Trung tâm Học liệu





13
Một cây xum x thì tổng qt hơn và có thể có các nút tốn tử khơng có
quan hệ cơ sở làm toán hạng, nghĩa là các toán hạng đều là quan hệ trung gian
(hình 1-4b).
Nếu chỉ xét các cây tuyến tính, kích thƣớc của khơng gian tìm kiếm sẽ
đƣợc rút gọn lại O(2N). Tuy nhiên cây xum xuê sẽ rất tiện lợi khi thực hiện
song song trong môi trƣờng phân tán.
Nếu chỉ xét cây tuyến tính, thì kích thƣớc khơng gian tìm kiếm chỉ cịn
O(2N) với N quan hệ. Trong mơi trƣờng phân tán cây xum x rất có lợi cho
việc thực hiện song song.

R4

R3

R1

R2 R3

R4

R2
R1
(a) Cây tuyến tính

(b) Cây xum xuê


Hình 1-4. Các loại cây
1.2.2. Các chiến lƣợc tìm kiếm
Quy hoạch động. Chiến lƣợc tìm kiếm tối ƣu hoá vấn tin sử dụng nhiều
nhất là quy hoạch động với tính chất đơn định. Chiến lƣợc đơn định tiến hành
bằng cách xây dựng các QEP nhƣ sau: Bắt đầu từ các quan hệ cơ sở sau đó
nối thêm quan hệ tại mỗi bƣớc cho đến khi thu đƣợc tất cả các QEP có thể có.
Hình 1-5 cho thấy cách quy hoạch động xây dựng (đơn định) tất cả các QEP
có thể có theo chiều ngang trƣớc khi nó chọn ra QEP tốt nhất.

Số hóa bởi Trung tâm Học liệu




14

Hình1–5. Xây dựng tối ưu hố một cách đơn định theo kiểu quy hoạch động
Để hạ thấp chi phí tối ƣu hố, trong q trình xây dựng phƣơng án có thể
có, một phƣơng án khơng có khả năng dẫn đến QEP tối ƣu sẽ đƣợc xén bỏ.
Ngƣợc lại chiến lƣợc đơn định sẽ xét QEP theo chiều sâu.
Việc dùng quy hoạch động và các phƣơng án trên bảo đảm tìm ra tất cả
các QEP tuy nhiên với chi phí cao, vì thế ngƣời ta đang tập trung vào lối tiếp
cận chiến lƣợc ngẫu nhiên hoá (randomised strategy) để làm giảm độ phức tạp
của tối ƣu hoá, nhƣng tất nhiên là khơng đảm bảo tìm đƣợc phƣơng án tối ƣu
tồn cục.
Ngẫu nhiên hố. Quy trình tiếp cận chiến lƣợc ngẫu nhiên hoá nhƣ sau:
Trƣớc tiên một hoặc nhiều QEP khởi đầu đƣợc xây dựng trực tiếp (theo
ý muốn chủ quan), sau đó cải thiện phƣơng án bằng cách thăm dị các lân cận
của QEP đã có, ví dụ ở hình 1-6 là một cách biến đổi điển hình bằng cách
hốn đổi hai quan hệ toán hạng đƣợc chọn ngẫu nhiên từ QEP hình 1-6(a)

sang QEP hình 1-6(b).

Số hóa bởi Trung tâm Học liệu




15

R3

R1

R2

R2

R1

(a)

R3
(b)

Hình 1-6. Hành động của thể tối ưu hố trong một chiến lược ngẫu nhiên hố
1.2.3. Mơ hình chi phí phân tán
1.2.3.1. Hàm chi phí (hàm mục tiêu)
Hàm chi phí có thể là tổng thời gian, hoặc là một chi phí nào đó, nếu
hiểu theo thời gian thì hàm chi phí có thể là:
Total_Time = TCPU * #insts + TI/O * I/Os + TMSG * #msgs + TTR * #bytes

Hai thành phần đầu là thời gian xử lý cục bộ, trong đó TCPU là thời gian xử
lý một chỉ thị (lệnh) của CPU và #insts là số chỉ thị; TI/O là thời gian cho một
xuất, nhập đĩa và I/Os số lần xuất nhập đĩa; TMSG 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; TTR 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í TMSG
* #msgs cũng đƣợc xem là nhƣ nhau và chúng ta giả thiết TTR 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:
Số hóa bởi Trung tâm Học liệu




16
CT(#bytes) = TMSG + TTR * #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 tố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

= TCPU * seq_#insts + TI/O * seg_#I/Os
+ TMSG * seg_#msgs + TTR * seg_#bytes

trong đó seq_#x, với x có thể là số các chỉ thị (insts), số các xuất nhập I/O, số
các thông báo (msgs) hoặc số bytes. Ở đây mọi xử lý truyền dữ liệu thực hiện
song song đang đƣợc bỏ qua.
Ví dụ 1.2.2:
Chúng ta minh họa sự khác biệt giữa tổng chi phí và thời gian đáp ứng qua
ví dụ ở hình 1-7, trong đó tổng thời gian đƣợc tính tại vị trí 3, dữ liệu đƣợc lấy
từ vị trí 1 và 2. Để đơn giản, chúng ta giả sử rằng chỉ xét đến chi phí truyền.

Số hóa bởi Trung tâm Học liệu