ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN VĂN CƢỜNG

CÁC THUẬT TỐN TƠ MÀU TỐI ƢU
CHO MỘT CÂY TRUY VẤN VÀ ỨNG DỤNG

LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN

Hà Nội – 2015


2

ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN VĂN CƢỜNG

CÁC THUẬT TỐN TƠ MÀU TỐI ƢU
CHO MỘT CÂY TRUY VẤN VÀ ỨNG DỤNG
Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thơng tin
Mã số: 60.48.01.04

LUẬN VĂN THẠC SỸ CƠNG NGHỆ THÔNG TIN

NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS LÊ HUY THẬP

Hà Nội – 2015

giả đƣợc tơi trích dẫn, tham chiếu rõ ràng trong “DANH MỤC TÀI LIỆU
THAM KHẢO” ở cuối luận văn.
Học viên

Nguyễn Văn Cƣờng


5

MỤC LỤC
LỜI CẢM ƠN .................................................................................................. 3
LỜI CAM ĐOAN ............................................................................................ 4
MỤC LỤC ........................................................................................................ 5
DANH MỤC CÁC CỤM TỪ VIẾT TẮT, NGHĨA TIẾNG VIỆT ............. 7
DANH MỤC SƠ ĐỒ, HÌNH VẼ, BẢNG ...................................................... 8
MỞ ĐẦU ........................................................................................................ 10
Chƣơng 1 : TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN, GIAO TÁC PHÂN TÁN VÀ
XỬ LÝ SONG SONG .............................................................................................................. 11

1.1. Giới thiệu cơ sở dữ liệu phân tán.......................................................... 11
1.1.1. Khái niệm .......................................................................................... 11
1.1.2. Quản trị cơ sở dữ liệu phân tán ......................................................... 12
1.1.3. Kiến trúc của cơ sở dữ liệu phân tán ................................................. 13
1.1.4. Đặc trƣng của cơ sở dữ liệu phân tán ................................................ 15
1.1.5. Các cơ chế truy xuất CSDL phân tán ................................................ 16
1.2. Giao tác phân tán ................................................................................... 17
1.2.1. Quản lý khóa trong giao tác .............................................................. 17
1.2.2. Xử lý giao tác khi xảy ra sự cố ......................................................... 18
1.3. Xử lý song song ....................................................................................... 19
1.3.1. Một số thuật toán xử lý dữ liệu song song ........................................ 19

3.3.2 Ví dụ 2 ................................................................................................ 57
3.3.3 Ví dụ 3 ................................................................................................ 58
3.3.4 Hình ảnh Demo .................................................................................. 61
3.4. Kết chƣơng .............................................................................................. 62
KẾT LUẬN .................................................................................................... 64
DANH MỤC TÀI LIỆU THAM KHẢO ..................................................... 65


7

DANH MỤC CÁC CỤM TỪ VIẾT TẮT, NGHĨA TIẾNG VIỆT
TT
1
2
3
4
5
6
7
8

Từ viết
tắt
CM
CSDL
DBM
DC
DD
DDB
DM

Database management
Data Communication
Data Dictionary
Distributed Database
Distributed Merging
Data Placement

Trộn tập trung
Cơ sở dữ liệu
Quản trị cơ sở dữ liệu
Truyền thông dữ liệu
Từ điển dữ liệu
Cơ sở dữ liệu phân tán
Trộn tập trung
Sắp đặt dữ liệu

Join Ordering and Query
Rewriting
Massively Parallel
Processor
Paralel Associative Join
Parallel Hash Join
Parallel Nested Loop
Parallel Virtual Machine
Query Excution Plan
Refragmentation

Sắp xếp thứ tự các phép nối và
viết lại câu truy vấn
Bộ xƣ̉ lý Song song lớn

Hình 1.20: Kết quả nối bằng ............................................................................... 30
Hình 1.21: Kết quả nối nửa ................................................................................. 31
Hình 2.1: Quá trình tối ƣu hố truy vấn .............................................................. 33
Hình 2.2: Cây truy vấn tiền xử lý ........................................................................ 34
Hình 2.3: Cây tốn tử tƣơng đƣơng cây hình 2.5................................................ 36


9

Hình 2.4: Các cây truy vấn khác nhau về phân hoạch dữ liệu ............................ 40
Hình 2.5: Chi phí các phƣơng án tơ màu (i) Cây ban đầu, (ii) Chi phí 7, (iii) chi
phí 6 ..................................................................................................................... 42
Hình 2.6: Phân rã bài tốn sau khi tơ màu nút i .................................................. 43
Hình 2.7: Cây truy vấn với thuộc tính phân mảnh khác nhau ............................ 46
Hình 2.8: Điều kiện nối là thuộc tính: TP ........................................................... 49
Hình 3.1: Cơ sở dữ liệu quản lý phạm nhân ....................................................... 55
Hình 3.2: Cây truy vấn ban đầu. ......................................................................... 56
Hình 3.3: Cây truy vấn sau khi sắp xếp lại thứ tự phép nối ................................ 56
Hình 3.4: Phân mảnh quan hệ tại hai nút. ........................................................... 57
Hình 3.5: Cây truy vấn ban đầu và các phƣơng án tơ màu ................................. 58
Hình 3.6: Phân bố dữ liệu và cây truy vấn tối ƣu ............................................... 59
Hình 3.7: Cây truy vấn khác nhau về phân hoạch dữ liệu .................................. 59
Hình 3.8: Cây truy vấn sau khi tách nút TP_GD ................................................ 60
Hình 3.9: Cây truy vấn tối ƣu với chi phí 6 ........................................................ 60
Hình 3.10: Kết quả truy vấn sau khi sắp xếp lại thứ tự phép nối........................ 61
Hình 3.11: Kết quả chọn các màu để tơ và chi phí phân mảnh lại...................... 62
Hình 3.12: Tính tốn giá trị Optc theo bổ đề 2.1 ................................................ 62
Hình 3.13: Một số Modul khác của phần Demo ................................................. 62



tác giả nghiên cứu các phƣơng pháp tối ƣu hóa truy vấn và các thuật tốn tơ màu
tối ƣu cho một cây truy vấn . Chƣơng 3, nghiên cứu ứng dụng thuật toán đối với
một số câu truy vấn đặc thù của cơ sở dữ liệu “Phần mềm quản lý phạm nhân”.


11

Chƣơng 1 : TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN, GIAO TÁC
PHÂN TÁN VÀ XỬ LÝ SONG SONG
1.1. Giới thiệu cơ sở dữ liệu phân tán
1.1.1. Khái niệm
Cơ sở dữ liệu (CSDL) phân tán[5] là một tập hợp dữ liệu, mà về mặt logic
tập hợp này thuộc cùng một hệ thống, nhƣng về mặt vật lý dữ liệu đó đƣợc phân
tán trên các vị trí khác nhau của một mạng máy tính.
Theo định nghĩa, dữ liệu đƣợc phân tán ở nhiều nơi. Tại mỗi vị trí, dữ liệu
đƣợc xây dựng theo một cấu trúc chung, đƣợc sử dụng chung để cùng giải quyết
một vấn đề. Xem Hình 1.2.
Có hai điểm quan trọng trong định nghĩa đó là phân tán và tƣơng quan
logic. Về phân tán, dữ liệu không chỉ đƣợc đặt tại một vị trí mà đƣợc phân bố
rộng khắp trên nhiều máy tính đặt tại nhiều vị trí khác nhau. Về tƣơng quan
logic, nhìn tổng thể, dữ liệu thuộc cùng một hệ thống, ngƣời dùng không thấy
đƣợc sự phân tán dữ liệu, nhƣng thực tế nó đƣợc phân tán tại các nút mạng và có
thuộc tính ràng buộc chúng với nhau. Đó là điểm phân biệt một cơ sở dữ liệu
phân tán với một cơ sở dữ liệu tập trung. Hệ quản trị CSDL chịu trách nhiệm
quản lý và phân quyền truy nhập dữ liệu tới các nút trong mơi trƣờng mạng.
Xem Hình 1.1, Hình 1.2 và Hình 1.3.

Hình 1.1: Tổng quan CSDL phân tán



Mỗi quan hệ tổng thể có thể chia thành một các phần không giao nhau gọi là
phân mảnh (Fragmentation). Sơ đồ phân mảnh mô tả các ánh xạ giữa quan hệ
tổng thể và các mảnh. Các mảnh đƣợc mô tả bằng tên của quan hệ tổng thể cùng
với chỉ mục của mảnh. Chẳng hạn, Rj đƣợc hiểu là mảnh thứ j của quan hệ R


14

hoặc Rij đƣợc hiểu là mảnh thứ j của quan hệ R đƣợc đặt tại trạm i. Xem hình
1.6.

Hình 1.5: Kiến trúc cơ bản của CSDL phân tán

Hình 1.6: Các đoạn và hình ảnh vật lý của một quan hệ tổng thể


15

1.1.3.3. Sơ đồ định vị
Sơ đồ định vị xác định đoạn dữ liệu Rj đƣợc định vị tại trạm thứ i trên mạng.
Tất cả các đoạn đƣợc liên kết với cùng một quan hệ tổng thể R và đƣợc định vị
tại cùng một trạm i cấu thành ảnh vật lý quan hệ tổng thể R tại trạm i. Do đó, ta
có thể ánh xạ 1-1 giữa một ảnh vật lý và một cặp (quan hệ tổng thể, trạm). Các
ảnh vật lý có thể chỉ ra bằng tên của một quan hệ tổng thể và một chỉ mục của
trạm. Mảnh thứ j của quan hệ R tại trạm i đƣợc ký hiệu là Rij. Xem hình 1.6.
1.1.3.4 .Sơ đồ ánh xạ cục bộ
Thực hiện ánh xạ các ảnh vật lý lên các đối tƣợng đƣợc thực hiện bởi hệ quản
trị cơ sở dữ liệu cục bộ. Tất cả các đoạn của một quan hệ tổng thể trên cùng một
trạm tạo ra ảnh vật lý.
1.1.4. Đặc trưng của cơ sở dữ liệu phân tán

chế thay thế hoặc dùng chƣơng trình hồi phục khi sự cố xảy ra.
1.1.4.6. Tin cậy và nhất quán
Hệ thống yêu cầu độ tin cậy nhƣ bảo mật dữ liệu, có các chức năng sao lƣu,
khơi phục khi xảy ra lỗi, hỏng dữ liệu. Ngoài ra, hệ thống phải đảm bảo nhất
quán nội dung cơ sở dữ liệu. Dữ liệu tại các nút là nhƣ nhau.
1.1.4.7. Tính trong suốt
Tính trong suốt của một hệ phân tán là việc che đi các thành phần riêng biệt
của hệ đối với ngƣời sử dụng và những ngƣời lập trình ứng dụng. Các loại trong
suốt có thể là Trong suốt phân mảnh (Fragmentation Transparency), trong suốt
về vị trí (Location Transparency) và trong suốt ánh xạ cục bộ (Local Mapping
Transparency).
1.1.5. Các cơ chế truy xuất CSDL phân tán
1.1.5.1. Truy xuất từ xa khơng qua chương trình phụ trợ
Ứng dụng phát ra một yêu cầu truy xuất CSDL tại vị trí bất kỳ. Hệ quản
trị CSDL phân tán gửi yêu cầu truy xuất đến vị trí chứa dữ liệu. Hệ quản trị cơ
sở dữ liệu cục bộ (nơi có dữ liệu cần truy xuất) thực hiện truy vấn và trả kết quả
về nơi yêu cầu (Xem hình 1.7).

Hình 1.7: Cơ chế truy xuất từ xa


17

1.2.5.2. Truy xuất từ xa thơng qua chương trình phụ trợ
Một ứng dụng yêu cầu thực hiện một chƣơng trình phụ trợ đặt tại vị trí từ
xa. Chƣơng trình phụ trợ này sẽ truy xuất CSDL từ xa và trả lại kết quả cho ứng
dụng đang yêu cầu (Xem hình 1.8).

Hình 1.8: Cơ chế truy xuất thơng qua chƣơng trình phụ trợ
1.2. Giao tác phân tán

quyết định ủy thác hoặc hủy bỏ. Nếu một thành viên không thể ủy thác cục bộ
giao tác con của nó thì tất cả các thành viên khác phải hủy bỏ cục bộ.
1.2.2.1. Sự cố về vị trí
- Một thành viên gặp sự cố trƣớc khi ghi mẫu tin “ready” vào nhật ký.
Nếu thời gian quá hạn của điều phối viên đã hết, điều phối viên quyết định hủy
bỏ giao tác, tất cả các thành viên trực thuộc hủy bỏ những giao tác con của nó.
Thành viên bị sự cố đƣợc phục hồi, quy trình sẽ bắt đầu lại mà không cần phải
tập hợp thông tin từ những vị trí khác.
- Một thành viên gặp sự cố sau khi ghi mẫu tin “ready” vào nhật ký.
Những vị trí đúng sẽ kết thúc giao tác (commit hoặc abort). Vị trí có sự cố phục
hồi bằng cách: (i)Truy cập thơng tin phục hồi từ xa ; (ii) Điều phối viên và tất cả
những thành viên trực thuộc khác sẽ thực hiện nhƣ khi trƣớc khi ghi mẫu tin
“ready”, thành viên bị sự cố sẽ thực hiện bắt đầu lại nhƣ đã mô tả.
- Điều phối viên gặp sự cố sau khi ghi mẫu tin “prepare” nhƣng trƣớc khi ghi
mẫu tin “global_commit” hoặc “global_abort” vào nhật ký.
Các thành viên đã trả lời READY phải chờ sự phục hồi của điều phối viên.
Quy trình bắt đầu lại của điều phối viên thừa nhận giao thức ủy thác từ lúc khởi
đầu.
- Điều phối viên gặp sự cố sau khi ghi mẫu tin “global_commit” hoặc
“global_abort” nhƣng trƣớc khi ghi mẫu tin “complete” vào nhật ký.
Điều phối viên phải gửi lại cho tất cả các thành viên những quyết định. Tất cả
những thành viên không nhận đƣợc lệnh phải chờ cho đến khi điều phối viên
phục hồi.
- Điều phối viên gặp sự cố sau khi ghi mẫu tin “complete” vào nhật ký. Trong
trƣờng hợp này, giao tác đã kết thúc và khơng có hành động cần thiết để thực
hiện lại.


19


các tốn tử đại số quan hệ. Thực hiện truy vấn song song nhiều toán tử cần phải
đảm bảo sự cân bằng giữa tính tốn song song và chi phí cho q trình trao đổi
thơng tin.
Giả sử quan hệ R đƣợc phân thành m mảnh và sắp đặt trên m vị trí. Quan hệ S
đƣợc phân thành n mảnh và sắp đặt trên n vị trí. Giả thiết m node và n node tách


20

rời nhau. Các node chứa các mảnh của quan hệ R đƣợc ký hiệu R-node, tƣơng tự
cho S là S-node.
Có ba thuật toán kết nối song song cho việc xử lý dữ liệu[5]: Thuật tốn vịng
lặp lồng song song, thuật toán nối kết hợp song song và thuật toán nối băm song
song.
1.3.1.1. Thuật tốn vịng lặp lồng song song
Thuật

tốn

vịng

lặp

lồng

song

song[5]

thay


Ví dụ 1.2 : với m=n=2 ta có kết quả nhƣ Hình 1.10:

Hình 1.10: Thuật toán nối kết hợp song song

thế


21

1.3.1.3. Thuật toán nối băm song song
Thuật toán nối băm song song[5] là sự tổng qt hóa của thuật tốn nối
kết hợp song song, đƣợc áp dụng trong trƣờng hợp kết nối bằng nhau không cần
sự phân mảnh cụ thể nào của quan hệ toán hạng. Ý tƣởng cơ bản của thuật toán
là phân mảnh các quan hệ R và S thành p mảnh R1, R2,…,Rp và S1, S2, …, Sp sao
cho:
Ví dụ 1.3 : với m=n=2 ta có kết quả nhƣ Hình 1.11:

Hình 1.11: Thuật tốn nối băm song song
1.3.2. Các phương pháp xử lý song song
Các phép truy vấn trong mơ hình quan hệ rất thích hợp cho việc thực hiện
song song. Truy vấn quan hệ thực chất là các phép tốn quan hệ thực hiện trên
các dịng dữ liệu có cùng cấu trúc. Hơn nữa, kết quả của mỗi phép tốn là một
quan hệ nên ta có thể kết hợp các phép tốn thành các dịng dữ liệu song song.
Có hai loại dịng dữ liệu song song: song song đường ống và song song phân
mảnh. Có thể sử dụng các thủ tục tuần tự sẵn có để thực hiện các phép tốn đã
có một cách song song mà khơng phải xây dựng các phép tốn song song mới.
Có 3 cơ chế xử lý song song cơ bản:
- Song song liên truy vấn (inter - query parallelism)
- Song song nội truy vấn (intra - query parallelism)

năng sử dụng hệ thống của phƣơng pháp này chƣa cao.
ii. Lập lịch theo phương án
- Một bộ lập lịch chung cho tất cả các truy vấn.
- Bộ lập lịch biết nhu cầu tài nguyên của tất cả các truy vấn hoạt động nên
nó có thể lập lịch cho các phép toán của các cây toán tử này, dựa vào việc các
yêu cầu này có phù hợp với điều kiện của hệ thống song song đang có hay
khơng.
- Chiến lƣợc chọn "tốt nhất" đƣợc áp dụng để chọn ra một phép toán từ
nhiều phép toán đang đợi.
- Sử dụng toán tử phục vụ tốt hơn để thực hiện trƣớc.
Phƣơng pháp này có khả năng sử dụng hệ thống tốt hơn nhƣng không "công
bằng" nhƣ phƣơng pháp lập lịch trên cơ sở cạnh tranh. Bởi vì, các truy vấn liên
quan đến tính phức tạp của chúng (chẳng hạn xử lý tên các quan hệ rất nhỏ hoặc
rất lớn) có thể rơi vào tình trạng chờ đợi mãi mãi, vì không thể thực hiện do


23

khơng giành đƣợc tài ngun. Ngồi ra, bộ lập lịch cũng có thể đƣa đến hiện
tƣợng "điểm nóng" khi mà nhu cầu tài nguyên của nhiều truy vấn tối ƣu đối với
hệ thống, thì việc chọn ra một truy vấn để thực hiện trƣớc là một vấn đề khó.
Các hệ Oracle 7 và Oracle RDB là các ví dụ về các hệ CSDL song song
dùng chung vùng và có hỗ trợ cơ chế song song liên truy vấn.
1.3.2.2. Song song nội truy vấn
Song song nội truy vấn là dạng song song hoá thi hành song song một truy
vấn đơn trên nhiều bộ xử lý. Nghĩa là, nó thực hiện từng truy vấn một và cho
phép thực hiện đồng thời các phép tốn trên truy vấn đó. Có hai cơ chế song
song nội truy vấn.
i. Song song độc lập
Ký hiệu Opi là một phép tốn nào đó, Opi và Opj với i  j đƣợc gọi là song


P1

Montereal

P2

Database Develop

P2

135000

P2

NewYork

P3

CAD/CAM

P3

250000

P3

NewYork

P4


PNO

PROJ3

(1)

Chọn bộ xử lý pl để thực hiện phép nối cho quan hệ trung gian PROJ':
PROJ' =

PROJ1

PROJ2

PNO

(2)


24

chọn bộ xử lý p2 để thực hiện phép nối
PROJ" =

PROJ2

(3)
(3)

PROJ3

Các lệnh SQL gộp nhóm
Một lệnh gộp nhóm SQL là một truy vấn thao tác trên các nhóm mẫu tin có
cùng một tính chất nào đó. Các lệnh gộp nhóm thƣờng gặp nhƣ MIN, MAX,
AVERAGE, COUNT, SUM, ... chúng đƣợc sử dụng trong các câu truy vấn SQL
nhƣ sau:
SELECT <FieldList>, <GroupingStatements>
FROM <RelationList>
WHERE <ConditionalExpressions>