ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
LỚP CAO HỌC QUA MẠNG – KHÓA 6
TIỂU LUẬN
MÔN HỌC: CƠ SỞ DỮ LIỆU NÂNG CAO
SỰ PHÂN BỐ CÁC PHÂN MẢNH TRONG
CƠ SỞ DỮ LIỆU PHÂN TÁN
Giảng viên: PGS.TS Đỗ Phúc
Sinh viên thực hiện: Nguyễn Hoàng Hạc
MSHV: CH1101081
TP. HCM, NĂM 2012
MỤC LỤC
2
Chương 1 GIỚI THIỆU
Trong một thiết kế cơ sở dữ liệu phân tán liên quan đến việc giải quyết các vấn
đề sau đây:
- Như thế nào thì một quan hệ trong hệ thống thông tin phải được phân mảnh?
- Có bao nhiêu bản sao của một mảnh cần được sao chép.
- Làm thế nào phân bố các phân mảnh đến từng vị trí trong hệ thống mạng.
- Những thông tin cần thiết cho sự phân mảnh và phân bố là gì?
Những vấn đề này rất phức tạp trong thiết kế cơ sở dữ liệu phân tán. Thậm chí,
khi xem xét từng vấn đề riêng lẻ, nó vẫn là một vấn đề nan giải. Để đơn giản hóa vấn
đề, chúng ta chỉ giải quyết vấn đề phân mảnh, giả định rằng tất cả các mối quan hệ
trong hệ thống thông tin đã được phân mảnh. Như vậy, vấn đề nghiên cứu ở đây là xác
định số lượng sao chép của mỗi mảnh và sau đó tìm kiếm một giải pháp phân mảnh tối
ưu, bao gồm cả những phân mảnh đã sao chép trong mạng diện rộng (WAN) sao cho
tổng chi phí truyền dữ liệu trong toàn hệ thống là nhỏ nhất.
Đối với yêu cầu đọc thông tin cho một giao dịch có thể chỉ đơn giản là lấy dữ
liệu từ các phân mảnh tại vị trí gốc hoặc có thể có một chút phức tạp để lấy các phân
mảnh từ một vị trí ở xa. Một yêu cầu ghi dữ liệu thì phức tạp hơn, với nhiều bản sao
của một phân mảnh được phân bố trong hệ thống mạng, để đảm bảo việc ghi dữ liệu

khăn trong thực tế. Ở đây, chúng tôi đề xuất một mô hình đơn giản và toàn diện, phản
ánh hành vi giao dịch trong cơ sở dữ liệu phân tán. Trong mô hình này, một thuật toán
xấp xỉ - SIMPLE – được đề nghị để giải quyết việc phân bố dữ liệu đơn giản. Đối với
mỗi mảnh f
i
, thuật toán SIMPLE bắt đầu phân bố các bản sao của phân mảnh f
i
đến các
nút (vị trí) j với B
ij
≥ 0. B
ij
là tổng khối lượng dữ liệu của phân mảnh f
i
gửi đến nút j
4
để xử lý các giao dịch được yêu cầu tại nút j trừ đi tổng khối lượng dữ liệu của tất cả
các nút cập nhật cho mảnh f
i
. Thuật toán SIMPLE tiếp tục tìm các nút khác để phân bố
bản sao của phân mảnh f
i
nhằm giảm tổng chi phí truyền tin. Kết quả, việc phân mảnh
bằng thuật toán của này là tối ưu hơn và tốt hơn so với phương pháp của Lin và những
người khác. Một số thí nghiệm đã được tiến hành để xác minh rằng công thức tính chi
phí thực sự có thể phản ánh chi phí truyền dữ liệu trong thực tế.
5
Chương 2 MÔ HÌNH PHÂN BỐ DỮ LIỆU
2.1 Vấn đề phân mảnh dữ liệu
Trước khi nghiên cứu về sự phân bố các phân mảnh, chúng ta phải xác định rõ

vị trí S
k
, chi phí truy vấn F
j
tại vị trí S
k
, chi phí cập nhật F
j
ở tất cả các vị
trí mà F
j
được lưu trữ và chi phí truyền dữ liệu
 Hiệu suất: hai chiến lược phổ biến là giảm thiểu thời gian đáp ứng và tối
đa hóa hoạt động của hệ thống tại mỗi vị trí.
Biện pháp tối ưu được đề nghị trong mô hình phân bố này là chi phí tối thiểu.
Đối với một mạng WAN với giới hạn băng thông 50 Kbps, thời gian truy cập thiết bị
ngoại vi và thời gian xử lý CPU không phải là yếu tố chính để xem xét trong việc giảm
tổng chi phí. Như vậy, vấn đề phân bố được đơn giản hóa để phân bố các bản sao của
một phân mảnh đến các vị trí sao cho có tổng chi phí truyền dữ liệu là tối thiểu.
6
2.2 Thông tin yêu cầu
Trước khi xác định công thức chi phí, một số thông tin phải được phân tích
trước, đó là số lượng dữ liệu của một cơ sở dữ liệu, hành vi giao dịch, thông tin các vị
trí và thông tin của mạng.
2.2.1 Thông tin cơ sở dữ liệu (Database Information)
Kích thước của mỗi phân mảnh – size(F
j
) cần được xác định rõ bởi vì nó đóng
vai trò quan trọng trong tính toán chi phí truyền dữ liệu
2.2.2 Thông tin giao dịch (Transaction Information)

3
0 0 3 0 0
T
4
3 0 2 0 0
UM
F
1
F
2
F
3
F
4
F
5
7
T
1
0 0 0 1 2
T
2
0 3 0 0 0
T
3
2 1 0 1 0
T
4
0 0 0 0 3
Trong ma trận truy cập và cập nhật RM và UM, giao dịch T

T
1
0.1 0.1 0 0.3 0.2
T
2
0.1 0.3 0 1 0
T
3
2 5 0.1 0.5 0
T
4
0.5 0 10 0 4
Trong ma trận SEL, giao dịch T
3
truy xuất chỉ có 0,1% của mảnh F
3
. Cập nhật
mảnh F
1
là 2%, F
2
là 5% và F
4
là 0,5%.
Hơn nữa, chúng ta cũng cần phải xác định ma trận tần số FREQ cho biết tần số
thực hiện của tất cả các giao dịch thực hiện tại mỗi vị trí:
FREQ
S
1
S

2.2.4 Thông tin của mạng (Network Information)
Trong môi trường WAN, chi phí truyền dữ liệu được tính bởi hai thành phần
chính đó là những thành phần ảnh hưởng trực tiếp đến tổng chi phí. C
ini
là chi phí cố
định để khởi tạo một gói dữ liệu với kích thước p_size. Trong khi CTR
i, j
là chi phí
truyền một đơn vị dữ liệu từ vị trí S
i
đến vị trí S
j
. Như vậy, chi phí truyền dữ liệu với
kích thước là m_size có thể được tính dưới một hàm tuyến tính như sau:
Chúng ta giả định rằng mỗi vị trí trong mạng được kết nối đến một vị trí khác
bằng một kết nối truyền thông hợp lý. Vì vậy, chi phí CTR
i, j
có thể được tính thông qua
một ma trận chi phí truyền dữ liệu CTR. Để đơn giản hóa vấn đề, chúng ta giả định
rằng CTR là một ma trận đối xứng:
CTR
S
1
S
2
S
3
S
4
S

load
và chi phí truyền tin cho xử lý giao dịch CC
proc
.
CC
load
là chi phí tải tất cả bản sao các phân mảnh đến các vị trí trong mạng trước
khi giao dịch được xử lý được tính như sau:
Với FAT (Fragment Allocation Table) là ma trận được biểu diễn như sau:
SI là vị trí chính (site master) chịu trách nhiệm cho việc tải tất cả các bản sao
của phân mảnh đến các vị trí khác trong hệ thống.
CC
proc
là chi phí bao gồm ba thành phần: giao dịch truy xuất TR
i
, giao dịch cập
nhật TU
i
, và xây dựng kết nối VC
ini
. Được tính bằng công thức sau:
10
Với FREQ
i, k
là tần số thực hiện giao dịch T
i
tại vị trí S
k
. Ngoài ra, chi phí giao
dịch truy xuất TR

Các cá thể mới sinh ra trong quá trình tiến hoá nhờ sự lai ghép ở thế hệ cha-mẹ.
Một cá thể mới có thể mang những tính trạng của cha-mẹ (di truyền), cũng có thể mang
những tính trạng hoàn toàn mới (đột biến). Di truyền và đột biến là hai cơ chế có vai
trò quan trọng như nhau trong tiến trình tiến hoá, dù rằng đột biến với xác suất nhỏ hơn
nhiều so với hiện tượng di truyền. Thuật giải di truyền là thuật toán lặp đi lặp lại khả
năng thích ứng của quần thể cơ sở, sử dụng các phép toán di truyền (chọn lựa tái sinh,
phép lai ghép và phép đột biến) dựa trên sự lựa chọn tự nhiên. Thuật giải di truyền đã
được chứng minh là một phương pháp hữu dụng trong việc tối ưu hóa, quan sát và máy
học,…. Nó mã hoá một giải pháp tiềm tàng đến một vấn đề chi tiết trên một cấu trúc dữ
liệu đơn giản giống nhiễm sắc thể và các phép toán liên kết.
12
3.2 Các thành phần chính của thuật giải di truyền
3.2.1 Nhiễm sắc thể (Chromosomes)
Trong quá trình phân chia của các tế bào của con người, nhiễm sắc thể (chứa
trong nhân bao gồm DNA (deoxyribonucleic acid), protein và RNA (ribonucleic acid)).
Trong nhiễm sắc thể là những gen, mang thông tin di truyền. Mỗi gen đặc biệt là
protein và là yếu tố độc lập của thông tin di truyền, quyết định đặc thù cho từng cá thể.
Trong thuật giải di truyền, nhiễm sắc thể là tập hợp các gen (các giá trị độc lập).
Mỗi nhiễm sắc thể thể hiện cho một giải pháp của vấn đề nhất định. Các gen có thể là
các biến boolean, số nguyên, dấu chấm động hoặc chuỗi Tập hợp các nhiễm sắc thể
khác nhau (cá thể) tạo thành một quần thể. Bằng phương pháp tiến hóa như: lai ghép,
lựa chọn và đột biến. Một quần thể mới được tạo ra.
3.2.2 Chọn lọc (Selection)
Trong tự nhiên, những cá thể có tính thích nghi cao nhất sẽ tồn tại đó là sự chọn
lọc. Các cá thể thích nghi với môi trường tốt hơn sẽ có cơ hội để tồn tại và tạo ra một
quần thể mới mang những gien tốt của quần thể cũ. Trong thuật giải di truyền, sự chọn
lọc các cá thể dựa trên một hàm thích nghi (fitness function). Các cá thể có hàm thích
nghi tốt sẽ được lai ghép để tạo thành một quần thể mới.
Chúng ta sử dụng một sự pha trộn của các phương pháp chọn lọc cho việc tái
sinh các nhiễm sắc thể.

của một gen trong nhiễm sắc thể. Nhiễm sắc thể có gen thay đổi hoặc nhiễm sắc thể
được phát sinh ngẫu nhiên cũng là một cách đột biến.
3.3 Giải thuật chung cho thuật giải di truyền
Thuật giải di truyền làm việc như sau:
- Cho P là một quần thể của các nhiễm sắc thể |P|.
- P(0) là quần thể khởi tạo được phát sinh ngẫu nhiên.
- P(t) là quần thể tại thời điểm t.
- Quần thể mới P(t+1) được tạo ra bằng cách sử dụng một tập các toán tử phát
sinh (tái sinh, lai ghép, đột biến) trên P(t).
- Mỗi nhiễm sắc thể trong P(t+1) được tái sinh theo tỷ lệ giá trị thích nghi của
nó tại thời điểm t.
- Lai ghép là tổ hợp lại 2 nhiễm sắc thể từ việc cắt chúng ở những vị trí ngẫu
nhiên và sự thay đổi những thông tin di truyền bằng cách ghép một hay nhiều đoạn
gien của hai (hay nhiều) nhiễm sắc thể cha-mẹ với nhau.
- Đột biến là hiện tượng cá thể con mang một (số) tính trạng không có trong mã
di truyền của cha-mẹ.
Nói chung, hiệu quả của thuật giải di truyền là một quần thể mới được tạo và
cho ra các giải pháp tốt hơn với các giá trị cao hơn của hàm thích nghi.
15
Khi chúng ta sử dụng thuật giải di truyền để giải quyết một vấn đề. Chúng ta
cần phải xem xét 5 yếu tố chính sau:
1. Lược đồ trình bày mối kết hợp của các nhiễm sắc.
2. Phương pháp tạo ra quần thể khởi tạo.
3. Hàm thích nghi cho các cá thể (nhiễm sắc thể).
4. Các toán tử phát sinh quần thể mới.
5. Tham số khởi tạo được cung cấp cho thuật giải di truyền.
16
Chương 4 TỐI ƯU SỰ PHÂN MẢNH BẰNG THUẬT GIẢI DI TRUYỀN
Phân tán tài nguyên không phải là một bài toán chỉ của hệ cơ sở dữ liệu phân
tán, mặc dù đối với cơ sở dữ liệu phân tán nó có những đặc trưng riêng, bài toán này đã

giải bài toán tối ưu tổng quát. Trong phạm vi của đề tài môn học này, tôi đề xuất một
phương pháp đó là sử dụng thuật giải di truyền để tìm cách phân bố các phân mảnh là
tối ưu nhất có thể.
4.1 Biễu diễn nhiễm sắc thể cho thuật giải di truyền
Chúng ta sử dụng thuật giải di truyền để xác định sự phân bố các phân mảnh ở
các vị trí sao cho là tối ưu nhất. Nhiễm sắc thể ở đây được biểu diễn là các FAT
(Fragment Allocation Table), mỗi FAT là một ma trận được biểu diễn như sau:
FAT
S
1
S
2
S
3
S
4
F
1
0 1 0 0
F
2
0 0 1 0
F
3
0 0 0 1
F
4
0 0 1 0
17
Như vậy, từ ma trận FAT trên cho chúng ta biết sự phân bố của các mảnh như

thức đã được trình bày ở trên:
4.4 Chọn lọc
Các nhiễm sắc thể được chọn lọc dựa trên hàm thích nghi của nhiễm sắc thể.
Chỉ những nhiễm sắc thể có hàm thích nghi tốt nhất mới được chọn lựa trong quá trình
tiến hóa
4.5 Tái sinh
4.5.1 Lai ghép
Lai ghép giữa hai nhiễm sắc thể được thực hiện bằng phương pháp sau:
18
 Chọn 2 nhiễm sắc thể trong quần thể mới vừa được chọn lọc để tiến hành
lai ghép
 Lai ghép giữa hai nhiễm sắc thể được thực hiện bằng cách hoán chuyển
hai dòng bất kỳ của 2 nhiễm sắc thể. Chúng ta có được 2 nhiễm sắc thể
mới bổ sung vào quần thể mới
FAT1 FAT2
S
1
S
2
S
3
S
4
S
1
S
2
S
3
S

S
1
S
2
S
3
S
4
F
1
0 1 0 0 F
1
1 0 0 1
F
2
0 0 1 0 F
2
0 0 1 0
F
3
0 0 0 1 F
3
1 0 0 0
F
4
0 1 0 0 F
4
0 0 1 0
4.5.2 Đột biến
Quá trình đột biến được thực hiện bằng cách chọn ngẫu nhiên một nhiễm sắc thể

0 0 0 1
F
4
0 1 0 0
FAT’
S
1
S
2
S
3
S
4
F
1
0 1 1 0
F
2
0 0 1 0
F
3
0 0 0 1
F
4
0 1 0 0
4.6 Thuật giải
Đầu vào:
 Ma trận truy xuất (RM)
 Ma trận cập nhật (UM)
 Ma trận chọn lọc (SEL)

Xác suất lai ghép (
P
c
) 30%
Xác suất đột biến (
P
m
) 10%
Số lần tiến hoá 50
Tham số cho cơ sở dữ liệu:
Tham số thực hiện Giá trị
21
Kích thước gói dữ liệu (p_size) 1.024 byte
Chi phí khởi tạo gói dữ liệu (Cini) 0,032 ms / byte
Chi phí tạo kết nối (VCini) 6.576 ms
4.7.1 Màn hình nhập liệu
 Nhập các thông tin về cơ sở dữ liệu
 Nhập thông tin cho thuật giải di truyền
 Thực hiện: tìm ma trận FAT bằng thuật giải di truyền
4.7.2 Kết quả chương trình
 Ma trận FAT có chi phí truyền thông là nhỏ nhất
22
4.8 Kết luận
Với dữ liệu như trên, chúng ta nhận thấy rằng phân mảnh thứ 5 (F4) không
được truy xuất bởi bất kỳ giao dịch nào trong ma trận RM. Tuy nhiên, giao dịch thứ 1
(T0) và thứ 4 (T3) thực hiện cập nhật trong ma trận UM. Giao dịch giao dịch thứ 1 (T0)
và thứ 4 (T3) dựa vào ma trận tần số truy cập (FREQ) chỉ được phân bố tại các vị trí
thứ 3 (S1), thứ 3 (S2) và thứ 4 (S3). Như vậy, theo mô hình phân mảnh này, mảnh thứ
5 (F4) sẽ được phân bố một trong các vị trí trên theo chi phí truyền thông.
Chương trình thực hiện khá hiệu quả đối với dữ liệu mẫu của bài báo đưa ra. Vì