Đại Học Quốc Gia TP.HCM
Trường Đại Học Công Nghệ Thông Tin
  
TIỂU LUẬN MÔN
CƠ SỞ DỮ LIỆU NÂNG CAO
Đề tài:
GIẢI THUẬT PHÂN MẢNH DỌC
& CÀI ĐẶT
GVHD: PGS.TS. ĐỖ PHÚC
Học viên: DAI NGUYÊN THIỆN
Lớp: Cao học khóa 6 Mã số: CH1101043
NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN


đơn lẻ.
Liên quan logic: Trong cơ sở dữ liệu phân tán, dữ liệu có một số đặc tính liên kết
chặt chẽ với nhau như tính kết nối, tính liên quan logíc Trong cơ sở dữ liệu tập trung,
mỗi vị trí quản lý một cơ sở dữ liệu và người sử dụng phải truy cập đến cơ sở dữ liệu ở
những vị trí khác nhau để lấy thông tin tổng hợp.
Xây dựng một hệ CSDL phân tán là xu hướng hiện nay vì nó có nhiều ưu điểm
như ưu điểm về tổ chức và tính kinh tế, tận dụng những cơ sở dữ liệu sẵn có (hình thành
cơ sở dữ liệu phân tán từ các cơ sở dữ liệu tập trung có sẵn ở các vị trí địa phương), thuận
Cài đặt thuật giải phân mảnh dọc Page 4
lợi cho nhu cầu phát triển, Giảm chi phí truyền thông, tăng khả năng thực hiện công việc
thực hiện (do xử lý song song tại nhiều vị trí), …
Vấn đề là xây dựng và cài đặt một cơ sở dữ liệu phân tán. Cần giải quyết vấn đề
xây dựng và cài đặt cơ sở dữ liệu phân tán cụ thể như vấn đề thiết kế phân tán, thiết kế cơ
sở dữ liệu
Thiết kế một hệ CSDL phân tán cần quan tâm nhiều vấn đề, tiêu chí như mức độ
chia sẻ, kiểu mẫu truy xuất, mức độ hiểu biết về kiểu mẫu truy xuất hay chiến lược thiết
kế từ trên xuống hay từ dưới lên, … Một trong những vấn đề mấu chốt của thiết kế
CSDL phân tán là việc phân mảnh (ngang, dọc, hổn hợp). Trong phạm vi bài viết này,
chúng tôi sẽ trình bày lại tóm tắt lý thuyết phân mảnh dọc và cài đặt các thuật toán phân
mảnh dọc bằng C#
II. NỘI DUNG
1. Phân mảnh dọc
Phân mảnh dọc cho một quan hệ R sinh ra các mảnh R
1
, R
2
, …, R
n
. Mỗi mảnh con
R

Những thông tin chính cần cho phân mảnh dọc có liên quan đến các ứng dụng.
Phân mảnh dọc đặt vào trong một mảnh các thuộc tính thường được truy xuất chung với
nhau  người ta đặt ra một giá trị đo thể hiện tính thường đi chung với nhau. Đại lượng
này được gọi là “ái lực” (affinity) của các thuộc tính.
Yêu cầu dữ liệu chính liên quan đến các ứng dụng là tần số truy xuất (access
frequency) của chúng. Gọi Q = {q
1
, q
2
, …,q
q
} là tập các câu truy vấn của người dùng (các
ứng dụng) sẽ chạy trên quan hệ R(A
1
, A
2
, …, A
n
). Với mỗi câu truy vấn qi và mỗi thuộc
tính A
j
người ta đưa ra một giá trị sử dụng thuộc tính (attribute usage value), ký hiệu là
use(q
i
,A
j
) và được định nghĩa như sau:

a) Ma trận sử dụng thuộc tính, ma trận tần xuất truy cập, Ma trận ái
lực thuộc tính

WHERE LOC = Value
Q4: Tìm tổng ngân sách dự án cho mỗi thành phố
SELECT SUM(BUDGET)
FROM PROJ
WHERE LOC = Value
Để thuận tiện, chúng ta đặt:
A1 = PNO, A2 = PNAME, A3 = BUDGET, A4 = LOC
Giá trị sử dụng được định nghĩa dưới dạng ma trận (trong đó số hạng (i,j) biểu thị
use(q
i
,A
j
)
Cài đặt thuật giải phân mảnh dọc Page 7
Ma trận giá trị sử dụng thuộc tính
Độ đo ái lực thuộc tính giữa 2 thuộc tính Ai và Aj của quan hệ R[A1, A2, …, An]
ứng với tập quan hệ Q = (q
1
, q
2
, …, q
q
) được định nghĩa như sau:
Với ref
l
(q
k
) là số truy xuất đến các thuộc tính (A
i
,A

) = 20 acc
3
(q
1
) = 10
acc
1
(q
2
) = 5 acc
2
(q
2
) = 0 acc
3
(q
2
) = 0
acc
1
(q
3
) = 25 acc
2
(q
3
) = 25 acc
3
(q
3

toán năng lượng liên kết BEA (bond energy algorithm)
Thuật toán năng lượng liên kết BEA nhận đầu vào là ma trận ái lực thuộc tính AA,
thực hiện việc hoán vị các hàng cột để sinh ra ma trận ái lực gom cụm CA (clustered
affinity matrix). Hoán vị được thực hiện sao cho số đo ái lực chung AM (global affinity
measure) là lớn nhất
Trong đó
aff(A
0,
A
j
) = aff(A
i,
A
0
) = aff(A
n+1,
A
j
) = aff(A
i,
A
n+1
) = 0
các điều kiện này đề cập đến các trường hợp một thuộc tính được đặt vào CA ở
bên trái của thuộc tính ở cột đầu tiên hoặc bên phải của thuộc tính cột cuối cùng trong các
hoán vị cột và bên trên của hàng trên cùng hay bên dưới hàng cuối cùng trong các hoán
vị hàng.
Hàm cực đại chỉ xét những lân cận gần nhất, vì thế nó gom cụm các giá trị lớn với
nhau và các giá trị nhỏ với nhau. Vì ma trận ái lực thuộc tính AA có tính đối xứng nên ta
có thể viết lại công thức trên như sau:

End for
Tính cont(A
index-1
, A
index,
A
index+1
) //điều kiện biên
loc

nơi đặt, được cho bởi giá trị cont lớn nhất
For i from index to loc by -1 do
CA(*, j)

CA(*, j-1)
End for
CA(*, loc)

AA(*, index)
index

index +1
end while
sắp thứ tự các hàng theo thứ tự tương đối của các cột
End {BEA}
Để bước thứ hai của thuật toán hoạt động, chúng ta cần định nghĩa xem đóng góp
(contribution) của thuộc tính vào số đo ái lực mang ý nghĩa gì.
Ta đã có:
Viết lại:
Cài đặt thuật giải phân mảnh dọc Page 10

,A
j
) + bond(A
j
,Ai) + bond(A
j
,A
j+1
)
Bây giờ xét việc đặt một thuộc tính mới A
k
giữa các thuộc tính A
i
và A
j
trong ma
trận ái lực gom cụm CA. Số đo ái lực chung mới có thể viết như sau

Do đó, đóng góp thực (net contribution) cho số đo ái lực chung khi đặt thuộc tính
A
k
giữa A
i
và A
j
là

Thí dụ về xét quá trình gom cụm các thuộc tính của quan hệ PROJ
Theo thuật toán BEA, đầu tiên, ta chép cột 1(A
1

Tính toán tương tự cho cột A
4
chỉ ra rằng cần phải đặt cột A
4
bên phải của cột A
2
.
(hình c)
Cuối cùng, sắp lại thứ tự hàng như thứ tự cột ta được ma trận CA như hình d
d) Thuật toán phân hoạch
Chia tập các thuộc tính gom cụm {A1, A2, …, Am} thành hai (hay nhiều hơn) các
tập {A1, A2, …, Ai} và {A
i+1
, …, Am} sao cho không có (hay có tối thiểu) các ứng dụng
truy cập cả hai (hay nhiều hơn) các tập hợp chia này.
Xét ma trận ái lực gom cụm CA như hình dưới đây
Cài đặt thuật giải phân mảnh dọc Page 13
Điểm x trên đường chéo xác định 2 tập : tập {A1, A2, …, Ai} nằm ở góc trên bên
trái, còn tập {A
i+1
, …, Am}. Gọi tập thứ nhất là TA và tập thứ hai là BA
Xét tập ứng dụng Q = {q
1
, q
2
, …, q
q
}
Định nghĩa
• TQ = tập các ứng dụng chỉ truy cập TA

n-1
best := CTQ
n-1
* CBQ
n-1
– (COQ
n-1
)
2
do {xác định cách phân hoạch tốt nhất}
Begin
For i from n-2 to 1 by -1 do
Begin
Tính CTQ
i
Cài đặt thuật giải phân mảnh dọc Page 15
Tính CBQ
i
Tính COQ
i
z := CTQ
i
* CBQ
i
– COQ
i
2
if z > best then
begin
best := z

A1 45 45 0 0 q
1
1 0 1 0
CA A3 45 53 5 3 q
2
0 1 1 0
A2 0 5 80 75 q
3
0 1 0 1
A4 0 3 75 78 q
4
0 0 1 1
acc S
1
S
2
S
3
S
4
… Sum
q
1
15 20 10 45
q
2
5 0 0 5
Có ba phương án chia: q
3
25 25 25 75

45 (Từ ma trận acc: Xem TQ gồm những q nào: cộng tất cả các S dòng q đó )
Cài đặt thuật giải phân mảnh dọc Page 17
CBQ
=
75 (Từ ma trận acc: Xem BQ gồm những q nào: cộng tất cả các S dòng q đó )
COQ
=
8 (Từ ma trận acc: Xem OQ gồm những q nào: cộng tất cả các S dòng q đó )
Tính:
CTQ*CBQ - COQ
2
= 3311
Phương án 3:
TA = {A1,A3, A2}
BA = {A4}
Tương tự trên:
TQ = {q1,q2} (TQ gồm những truy vấn q mà có AQ(q) là "con" của TA)
BQ = { } (BQ gồm những truy vấn q mà có AQ(q) là "con" của BA)
OQ = {q3,q4} (OQ gồm những truy vấn q còn lại của Q.)
CTQ
=
50 (Từ ma trận acc: Xem TQ gồm những q nào: cộng tất cả các S dòng q đó )
CBQ
=
0 (Từ ma trận acc: Xem BQ gồm những q nào: cộng tất cả các S dòng q đó )
COQ
=
78 (Từ ma trận acc: Xem OQ gồm những q nào: cộng tất cả các S dòng q đó )
Tính:
CTQ*CBQ - COQ

thỏa
A = ∪ R
i
Thì tính đúng đắn của phân mảnh dọc được bảo đảm
ii. Tính tái thiết được
Có thể xây dựng lại quan hệ ban đầu bằng phếp nối. Đối với qua hệ R có phân
mảnh dọc F
R
= {R
1
, R
2
, …, R
r
} và các thuộc tính khóa K

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 R
i
phải chứa các thuộc tính khóa của R hoặc chứa một mã TID
được gán bởi hệ thống
iii. Tính tách biệt
Tích tách biệt trong phân mảnh dọc không quan trọng như trong phân mảnh
ngang. Có 2 trường hợp cần xem xét ở đây:
Nếu dùng TID thì các mảnh tách biệt vì TID được nhân bản trong mỗi mảnh đều
do hệ thống gán và là những thực thể đã được quản lý và người dùng hoàn toàn không
nhìn thấy được.
Nếu các thuộc tính khóa được nhân bản trong mỗi mảnh  không thể nói chúng

public matran(int hang, int cot) public TextBox[,] matrix
public int sohang
public int socot
public Label[] tenhang
public Label[] settenhang(string st)
public void setnullhang()
public void setnullcot()
public void setnullmatran()
public Label[] tencot
public Label[] settencot(string st)
}
public void vematran(matran M, int x, int y, string rowname, string colname)
Hàm vẽ ma trận: tham số
• matran M: ma trận cần vẽ lên màn hình
• int x, int y: tọa độ x, y nơi sẽ vẽ ma trận
• string rowname, string colname: tên hàng, tên cột (A, Q, S)
hàm này sẽ vẽ ra màn hình lân lượt mảng Label chứa tên hàng, tên cột của ma trận
M, sau đó vẽ ma trận là mảng 2 chiều các Textbox
public void xoamatran(matran m)
Hàm xóa ma trận m
public void vematranAA(matran M, int x, int y)
Tham số: matran M: ma trận AA, intx, int y: tọa độ vẽ ma trận
Xử lý: tính (từ ma trận sử dụng thuộc tính và ma trận tần suất sử dụng) và vẽ ma
trận AA
public void vematranCA(matran M, int[] ord,int x, int y)
Tham số: matran M: ma trận CA, intx, int y: tọa độ vẽ ma trận
Xử lý: tính (từ ma trận AA và mảng int[] ord) và vẽ ma trận CA

private void btnDefrag_Click(object sender, EventArgs e)
Hàm xử lý sự kiện khi người dùng nhấp chuột vào nút Phân mảnh. Xử lý: xóa rồi
tính và vẽ lại các ma trận AA và CA, tính phân mảnh và hiện kết quả phân mảnh
III.KẾT LUẬN
Thử nghiệm chương trình cho thấy chạy tốt và có thể thực hiện lại với số liệu từ
bài toán khác.
Các ma trận là các mảng control Textbox được khai báo trong quá trình chạy 
khi thay đổi số thuộc tính, số query, số Site chương trình vẫn thể hiện đúng trong ngữ
cảnh mới.
Cài đặt thuật giải phân mảnh dọc Page 23
Tuy nhiên, các kết quả tính toán trung gian không hiển thị ra trong quá trình chạy
chương trình.
IV. TÀI LIỆU THAM KHẢO
[1] PGS.TS. Đỗ Phúc. Slide Bài giảng CSDL phân tán. ĐHCNTT-ĐHQG TPHCM
[2] M. Tamer Özsu, Patrick Valduriez. Nguyên lý các hệ cơ sở dữ liệu phân tán. (bản dịch:
Trần Đức Quang) Nhà xuất bản Thống Kê
Xin chân thành cảm ơn Thầy đã truyền đạt lại cho chúng em những ý tưởng, bài
học rất hay những kiến thức mới, bổ ích và nhất là lòng nhiệt huyết, đam mê nghiên cứu
khoa học.
TP.HCM, ngày 18 tháng 08 năm 2012
Sinh viên thực hiện
Dai Nguyên Thiện
Cài đặt thuật giải phân mảnh dọc Page 24