HỌC VIỆN CÔNG NGHỆ BƢU CHÍNH VIỄN THÔNG

Dƣơng Thị Nguyệt NGHIÊN CỨU CÁC KỸ THUẬT TÁCH-GỘP SONG SONG TRÊN
CƠ SỞ DỮ LIỆU PHÂN TÁN VÀ ỨNG DỤNG

Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01.01 TÓM TẮT LUẬN VĂN THẠC SĨ

HÀ NỘI - 2014 Luận văn đƣợc hoàn thành tại:
HỌC VIỆN CÔNG NGHỆ BƢU CHÍNH VIỄN THÔNG
Ngƣời hƣớng dẫn khoa học: PGS. NCVC. TS. Lê Huy Thập

động trên hệ thống mạng, để tăng tốc độ xử lý thì không những xây dựng hạ tầng
mạng có đƣờng truyền lớn, mà chúng ta cần phải nghĩ đến việc phân tán dữ liệu nhƣ
thế nào trong hệ thống bởi vì nó quyết định rất lớn đến kết quả xử lý thông tin.
Trong thời gian qua tôi đã tìm hiểu về hệ thống cơ sở dữ liệu phân tán và
thấy rằng để giải quyết vấn đề ách tắc vào ra thƣờng gặp trong các hệ CSDL song
song, ngoài việc áp dụng một kiến trúc phần cứng thích hợp, ngƣời ta tiến hành
phân mảnh dữ liệu một cách hợp lý cho các bộ xử lý và thực hiện câu vấn tin đã cho
một cách đồng thời trên các mảnh. Hiện nay các chƣơng trình viết bằng ngôn ngữ
SQL dùng để xử lý CSDL đều có thể đƣa vào các máy đa xử lý để thực hiện song
song. Phần mềm SQL viết cho các hệ thống đơn xử lý có thể đƣa vào các máy tính
song song để thực hiện song song thông qua chƣơng trình dịch của ngôn ngữ lập
trình song song.
Do đó tôi đã chọn đề tài luận văn là: “Nghiên cứu các kỹ thuật tách – gộp
song song trên CSDL phân tán và ứng dụng”, nội dung luận văn này sẽ nghiên
cứu và đề xuất các giải pháp tách-gộpsong song và cho thấy đƣợc kết quả các thuật
toán này sẽ làm tăng rất nhiều về hiệu năng xử lý dữ liệu và truyền dữ liệu so với cơ
sở dữ liệu tập trung.

2

CHƢƠNG 1: CƠ SỞ LÝ THUYẾT
1.1 Tổng quan về CSDL phân tán
Hệ cơ sở dữ liệu phân tán (Distributed Database System – DDBS) là một tập
hợp dữ liệu có liên đới logic và đƣợc phân bố trên các nút của một mạng máy tính.
Cơ sở dữ liệu phân tán (CSDLPT) có các đặc điểm: Tính phân tán và tính
tƣơng quan logic.
1.2 Các kỹ thuật phân mảnh dữ liệu trong CSDL
Quy tắc phân mảnh đúng đắn
Phải tuân thủ ba quy tắc trong khi phân mảnh mà chúng bảo đảm rằng CSDL
sẽ không có thay đổi nào về ngữ nghĩa khi phân mảnh:Tính đầy đủ, tính tái thiết

1.2.1.1 Phân mảnh ngang (Vòng tròn Robin)
Phần giả mã đƣợc viết nhƣ sau:
Ký hiệu Y = { n
0
, n
1, …,
n
p-1,
n
p
}
For i = 0 to N-1
For Each element In Y
If element mod N = i
Save element vào vùng i
Y - = element
End if
Next element
End For
Cách phân mảnh này dễ cài đặt và không xảy ra tình trạng thiếu cân đối về
dữ liệu vì các vùng chỉ hơn kém nhau tối đa một bộ.
Kỹ thuật phân mảnh này dựa trên thứ tự các bộ nên nó không phụ thuộc vào
bất cứ một thuộc tính nào của quan hệ đƣợc phân mảnh.
Phân mảnh Robin không thích hợp với các truy vấn khoảng vì phải tiến hành
tìm kiếm trên tất cả các vùng có lƣu quan hệ đang xét.
2.2.1.2 Phân mảnh ngang theo hàm băm
Phân mảnh theo hàm băm là trƣờng hợp tổng quát của Robin. Giả sử cần
phân mảnh quan hệ R cho N vùng đƣợc đánh số 0, 1, …, N-1 với thuộc tính phân
4


Where <Condition
0
>
Vùng 1
Select *
From <Tên quan hệ>
Where <Condition
1
>
…
Vùng n
Select *
From <Tên quan hệ>
Where <Condition
n
>
Chú ý rằng các Condition
i
, Condition
j
, với i # j là các khoảng loại trừ nhau.
1.2.1.4 Phân mảnh ngang dẫn xuất
Phân mảnh ngang dẫn xuất đƣợc định nghĩa trên một quan hệ thành viên của
một đƣờng nối dựa theo phép toán chọn trên quan hệ chủ nhân của đƣờng nối
đó.Chúng ta cần lƣu ý 2 điểm.Một là đƣờng nối giữa quan hệ chủ nhân và thành
viên đƣợc định nghĩa là một đƣờng nối bằng.Thứ hai, nối bằng có thể đƣợc cài đặt
nhờ các nối nửa. Điều này rất quan trọng với mục đích của chúng ta vì chúng ta
muốn phân hoạch quan hệ thành viên theo phân mảnh của chủ nhân nhƣng cũng
muốn mảnh thu đƣợc chỉ định nghĩa trên các thuộc tính của quan hệ thành viên.
Nhƣ thế nếu cho trƣớc một đƣờng nối L, trong đó owner(L) = S và

chứa một tập con các thuộc tính cùng với khóa của quan hệ R. Mục đích của phân
mảnh dọc là phân mảnh một quan hệ thành một tập các quan hệ nhỏ hơn, để có
nhiều ứng dụng chỉ cần chạy trên một mảnh. Nhƣ vậy một cách phân mảnh tối ƣu là
phân mảnh sinh ra một lƣợc đồ phân mảnh cho phép giảm tối đa thời gian thực thi
các ứng dụng chạy trên các mảnh đó.
Phân mảnh dọc 1 quan hệ tổng thể n-bộ R là tách R thành các quan hệ con n-
bộ R
1
, R
2
, … R
k
sao cho quan hệ R có thể đƣợc khôi phục lại từ các quan hệ con
này bằng phép nối R = R1 R2 … Rk.
Phân mảnh là phức tạp hơn phân mảnh ngang, vì số lựa chọn có thể có của
phân mảnh dọc là rất lớn. Trong phân mảnh ngang, nếu tổng các vị từ đơn giảncủa
tập Pr là n thì số mảnh ngang có thể có tối đa là 2n (vì có 2n vị từ hội s = cấp) chƣa
nói trong số chúng có một số sẽ mâu thuẫn với các phép kéo theo do đó sẽ làm giảm
số mảnh phải xem xét. Còn trong phân mảnh dọc nếu một quan hệ có m thuộc tính
không phải là khóa thì số mảnh dọc có thể có sẽ là số Bell thứ m B(m). Với m đủ
lớn thì số Bell B(m) mm, ví dụ m=10, B(m) =115.000; m=9, B(m) = 109;
7

m=30,(m) = 10
23
, …. Qua những ví dụ này ta thấy để tìm các phân mảnh dọc tối ƣu
là bài toán Heuricstic.
1.2.3 Phân mảnh hỗn hợp
Trong đa số các trƣờng hợp, phân mảnh ngang hoặc phân mảnh dọc đơn giản
cho một lƣợc đồ CSDL không đủ đáp ứng các yêu cầu từ các ứng dụng.Trong

R
= {R
1
, R
2
, R
3
, … R
r
} và các thuộc
tính khóa K
R =
K
R
i
, R
i
F
R
Do vậy nếu điều kiện mỗi R
i
là đầy đủ phép toán nối sẽ tái thiết lại đúng R.
Một điểm quan trọng là mỗi mảnh R
i
phải chứa các thuộc tính khóa của R.
8

1.3 Các phƣơng pháp xử lí song song
1.3.1 Song song liên truy vấn
1.3.1.1 Lập lịch cạnh tranh

là một vấn đề.
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 .
Bộ lập lịch
Toán tử phục
vụ
Toán tử phục
vụ
Tập các toán tử và
bộ điều phối
Hàng đợi của các
câu truy vấn

Hình 1.13 Sơ đồ lập lịch theo phƣơng án
1.3.2. Song song nội truy vấn
Song song nội truy vấn là dạng song song hóa thi hành song song một truy
vấn đơn trên nhiều bộ xử lý. Điều đó 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 toán trên truy vấn đó.Có hai cơ chế song song
nội truy vấn.
1.3.2.1 Song song độc lập
Ký hiệu Op
i
là một phép toán nào đó, Op
i
và Op
j
với i # j đƣợc gọi là song
song độc lập với nhau, nếu chúng ngƣợc thực hiện song song và USE(Op
i
)

2
để thực hiện phép nối
PROJ‟‟
=
PROJ
2 PNO
PROJ
3
(3)
Khi các tính toán này đã hoàn tất, chúng ta có thể thực hiện
PROJ‟
PNO
PROJ‟‟(4)
Muốn đạt đƣợc song song hóa cao hơn ta có thể sắp đặt sao cho khi mới hình
thành các bộ trong PROJ‟, PROJ‟‟ thì chúng sẽ đƣợc thực hiện nối ngay mà không
chờ cho đến khi kết thúc các phép nối này.
1.3.2.2. Song song đƣờng ống
Cách xử lý tuần tự kiểu đƣờng ống là một kỹ thuật quan trọng để xử lý câu
truy vấn.Nó là một dãy các thao tác đƣợc sắp đặt sao cho đầu ra của thao tác này là
đầu vào của thao tác kế tiếp.Ƣu điểm của kỹ thuật này là không cần lƣu trữ kết quả
tạm thời trong quá trình xử lý mà thực hiện tính toán ngay.Do đó sẽ hạn chế các
thao tác đọc ghi các kết quả trung gian. Trong hệ thống song song, các kỹ thuật
đƣờng ốngchủ yếu đƣợc sử dụng với cùng mục đích nhƣ hệ thống tuần tự.Tuy
nhiên, nó đƣợc dùng nhƣ một biện pháp song song hóa một phần. Nghĩa là 2 phép
toán khác nhau có thể thực hiện đồng thời bằng cách lấy kết quả của phép toán này
làm dữ liệu vào cho phép toán kia. Đó là cơ chế song song đƣờng ống.
11

1.3.2.3. Song song nội toán tử
Song song nội toán tử thực hiện một phép toán quan hệ bằng cách dùng

CHƢƠNG 2: CÁC THUẬT TOÁN TÁCH GỘP SONG SONG
Qua tìm hiểu tại chƣơng 1 ta thấy việc phân mảnh đều cho chúng ta các
quan hệ. Vì vậy mảnh ở đây có thể đồng nhất với quan hệ. Khi tái thiết các
mảnh hay ghép, nối các mảnh chúng ta dùng các thuật ngữ đồng nghĩa nhƣ Hợp
hoặc Ghép và Nối.
Ngoài việc xây dựng các phép toán song song, chúng ta còn có thể sử dụng
các phép toán quan hệ truyền thống với các dòng dữ liệu song song.Mỗi phép toán
quan hệ có một tập các cổng vào chứa các mẫu tin và một cổng ra chứa dòng dữ
liệu kết quả. Dòng dữ liệu song song thực hiện bằng cách tách và ghép các dòng dữ
liệu thành các cổng tuần tự có hai phép toán song song cơ bản: phép ghép (merge
operator ) và phép tách (spliting operator).
Ngoài ra, phép ghép cũng có thể xem là phép kết hợp nhiều dòng dữ liệu
song song độc lập thành một dòng dữ liệu đơn (tuần tự) đƣợc tách thành nhiều dòng
dữ liệu song song độc lập.Một phép tách đƣợc dùng để phân mảnh hoặc lặp lại dòng
kết quả ra của một phép toán quan hệ.
Cấu trúc các câu lệnh song song:
Cấu trúc Parbegin và Parend, Cobegin và Coend
Trong chƣơng trình, những tiến trình không sử dụng dữ liệu chung hay độc
lập với nhau thì thực hiện đƣợc đồng thời. Giả thiết các lệnh S1, S2, , Sn đƣợc
thực hiện song song trên n tiến trình (hay n bộ xử lí) riêng biệt. Khi đó chúng ta có
thể viết thành khối song song nhƣ sau:
13

Parbegin
Hoặc
Cobegin
S1;

S1;
S2;

nhƣ trong cấu trúc Par sau:
Par {
<câu lệnh 1>

<câu lệnh k>}
14

Từ khóa Par chỉ ra rằng những câu lệnh trong phần thân đƣợc thực hiện một
cách đồng thời. Đây là song song mức dòng lệnh.
2.1. Giải pháp phân mảnh lại ReF
2.1.1. Tổng quan giải pháp
Thuật toán thực hiện qua 2 bƣớc:
Bƣớc 1: Các nút không thực hiện gộp nhóm trực tiếp các phần dữ liệu trên
địa chỉ lƣu trữ của nó, mà trƣớc tiên phân mảnh lại quan hệ trên thuộc tính nhóm
GROUP BY.
Bƣớc 2: Các vị trí thực hiện gộp nhóm thành phần dữ liệu sau khi đã phân
mảnh lại.
Xét Ví dụ 2.2: Giả sử cho bảng thống kê nhân viên năm 2011 tại các chi
nhánhnhƣ hình 2.5.Thực hiện phân mảnh lại cho cơ sở dữ liệu của công ty.
Ví dụ trên sau khi ứng dụng thuật toán Ref ta có:
Dữ liệu tại Hà Nội Dữ liệu tại Đà Nẵng
Dữ liệu tại Hồ Chí
Minh
Bacluong = TS Bacluong = KS
Bacluong = CD
Gộp nhóm Gộp nhómGộp nhóm

Hình 2.5 Gộp nhóm theo thuật toán Ref
15



CSDL lớn sẽ có thể xảy ra hiện tƣợng “thắt cổ chai” làm tăng thời gian xử lý và
giảm tốc độ xử lý dữ liệu.
2.3. Giải pháp trộn phân tán DM
2.3.1. Tổng quan giải pháp
Giải pháp trộn này gồm 2 bƣớc sau:
- Bƣớc 1: Mỗi nút thực hiện gộp nhóm các mẫu tin trên vùng của nó.
- Bƣớc 2: Sau đó, các giá trị gộp nhóm riêng đƣợc phân mảnh theo hàm trên
thuộc tính nhóm GROUP BY và các nút thực hiện trộn các giá trị gộp nhóm cục bộ
này thành một cách đồng thời.
Ƣu điểm: Các nút thực hiện trộn các giá trị gộp nhóm thành phần một cách
đồng thời nên giai đoạn trộn không còn là vấn đề bế tắc nữa.
Nhƣợc điểm: Do một giá trị nhóm đƣợc tích lũy trên tất cả các nút nên đòi
hỏi bộ nhớ phải lớn.
Ví dụ 2.3:Giả sử công ty TNHH Hoàng Hà có 3 trụ sở tại Hà Nội, Sài Gòn
và Đà Nẵng. Tại các chi nhánh công ty có danh sách nhân viên nhƣ bảng2.1.
Hãy đếm số lƣợng nhân viên trong công ty lần lƣợt theo bậc lƣơng: TS, KS,
CD.
Bảng 2.1 Danh sách nhân viên của công ty tại các chi nhánh

Ta có kết quả gộp nhóm theo phƣơng pháp trộn phân tán đƣợc trình bày
trên hình 2.6
18

Bacluong = TS
Bacluong = KS
Bacluong = CD

Hình 2.8 Gộp nhóm theo phƣơng pháp trộn phân tán
2.3.2. Đề xuất và thể hiện thuật toán trộn phân tán

mảnh giả định nhƣ hình 3.1.
Hà Nội Sài Gòn
Đà Nẵng
Môi trường mạng
CSDL2
CSDL1
CSDL3

Hình 3.1 Sơ đồ lƣu trữ dữ liệu phân tán
3.2 Tạo CSDL phân tán
- Sử dụng mô hình client/server
20

- Thực hiện nhân bản dữ liệu đầy đủ: Toàn bộ cơ sở dữ liệu sẽ đƣợc tạo trên
tất cảmỗi trạm.
Ƣu điểm: Điều này sẽ cải thiện tính sẵn sàng cao nhất vì nếu sự cố trên trạm
này thì vẫn có dữ liệu trên trạm khác và cải thiện hiệu nănglấy dữ liệu trên mạng
cho các truy vấn toàn bộvì dữ liệu sẽ đƣợc lấy từ các trạm cục bộ. Nhƣợc điểm: Các
thao tác cập nhập dữ liệu rất chậm vì phải copy, đồng bộ dữ liệu cho mọi trạm. Kỹ
thuật điểu khiển tƣơng tranh và phục hồi sẽ phức tạp hơn.
Dữ liệu tại HCM
Dữ liệu tại Đà Nẵng
Dữ liệu tại Hà Nội
Nhập dữ
liệu
Nhập dữ
liệu
Nhập dữ
liệu
Dữ liệu tại Hà Nội

Nguyen Huong Lan
CN
HAN
3
PGD
HANE2
Le Van Minh
TS
HAN
5
GD
HANE3
Le Quang Luong
KS
HAN
2
TP
HANE4
Nguyen Van Anh
CD
HAN
4
KT
HANE5
Mai Thi Lan
CN
HAN
3
TEST
HANE6

Bui Tien Doan
KS
HAN
4
TEST
HANE12
Vu Trong Hoang
TS
HAN
4
KT
HANE13
Vu Quang Vinh
KS
HAN
5
QL
HANE14
Mai Thi Lan
TC
HAN
2
TEST
HANE15
Le Van Tuan
TC
HAN
2
HT
Bảng 3.2: Danh mục nhân viên Đà Nẵng (DANHMUC_DAN)

4
PGD
DANE5
Do Van Anh
CN
DAN
4
QL
DANE6
Vu Thi Lien
CD
DAN
3
TEST
DANE7
Pham Thi Tram
TC
DAN
2
HT
DANE8
Le Huyen Trang
KS
DAN
3
LT
DANE9
Doan Tien Hung
KS
DAN

TS
HCM
5
GD
HCME5
Hoang Minh Son
KS
HCM
4
PGD
HCME6
Nguyen Tien Manh
CN
HCM
2
LT
HCME7
Ha Thi Le
CD
HCM
2
TEST
HCME8
Do The Thanh
TC
HCM
1
HT
HCME9
Pham Van Anh

23

a. Đầu tiên đăng nhập hệ thống
b. Màn hình trang chủ
Chƣơng trình giúp ngƣời quản trị CSDL và NSD thao tác trực tiếp tại chi
nhánh trên hệ thống thực hiện các thao tác thông qua màn hình giao diện nhƣ
sau:

Hình 3.4 Màn hình chính
c. Màn hình danh mục Nhân viên

Hình 3.5 Màn hình Danh mục nhân viên