ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
________ ________
BÀI THU HOẠCH MÔN HỌC
CƠ SỞ DỮ LIỆU NÂNG CAO
Đề Tài:
Ứng Dụng Thuật Toán Năng Lượng Liên Kết
Trong Thiết Kế Cơ Sở Dữ Liệu Phân Tán
Học viên thực hiện:
Trần Thanh Quốc Thắng
MSSV: CH1101131

TP. HCM, năm 2012
Mở đầu
Nhu cầu về lưu trữ và truy xuất dữ liệu ngày nay đã trỡ thành một trong
những lĩnh vực trọng tâm đã và đang được nghiên cứu và phát triễn bởi tính
ứng dụng rộng rãi của nó trong hầu hết các lĩnh vực đời sống của con người
như kinh doanh, an ninh, giao thông, y tế…
Việc thiết kế các mô hình cơ sở dữ liệu mới đang ngày càng trỡ nên cấp
bách do nhu cầu lưu trữ dữ liệu ngày càng tăng, đòi hỏi phải có những mô
hình cơ sở dữ liệu thích hợp cho việc truy vấn thông tin nhanh và chính xác.
Vì vậy, việc ra đời của mô hình cơ sở dữ liệu phân tán như một điều tất yếu
bởi tính ưu việt của nó so với các mô hình trước đó.
Trong phạm vi hạn hẹp của bài thu hoạch này, tác giã sẽ đề cập tới việc
thiết kế một hệ cơ sở dữ liệu phân tán dựa vào việc phân mãnh các quan hệ
thông qua thuật toán năng lượng liên kết (Bond Energy Algorithm). Xin được
gửi lời cảm ơn đến Phó Giáo sư - Tiến sỹ Đỗ Phúc, người đã tận tâm truyền
đạt những kiến thức nền tảng cơ bản về môn học “Cơ Sở Dữ Liệu Nâng
Cao”.
MỤC LỤC
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG 1

chức phân bố trên nhiều vị trí địa lý khác nhau như các thành phố khác nhau
hay các quốc gia khác nhau. Trong những trường hợp như vậy, việc xây
dựng các hệ cơ sở dữ liệu tập trung đối với các tổ chức này thường là không
thực tế và không kinh tế. Vì vậy, nhu cầu phân tán cơ sở dữ liệu ngày càng
trỡ nên cần thiết và đòi hỏi phải có sự ra đời của một mô hình cơ sở dữ liệu
mới đáp ứng được yêu cầu trên. Một cơ sở dữ liệu phân tán là một cơ sở dữ
liệu logic đơn lẻ mà được trải ra về mặt vật lý trên nhiều máy tính ở nhiều vị
trí địa lý khác nhau.
2. Khái niệm về cơ sở dữ liệu phân tán
Cơ sở dữ liệu phân tán là tập cơ sở dữ liệu có quan hệ logic với nhau và
được trãi trên 1 mạng máy tính. Mỗi trạm của mạng có khả năng xử lý tự
quản và có thể thực hiện các ứng dụng cục bộ, mỗi một trạm cũng có thể
tham gia vào ít nhất 1 ứng dụng toàn cục, có yêu cầu truy xuất dữ liệu tại
nhiều trạm.
Cơ sở dữ liệu phân tán là một khái niệm không bao gồm các trường hợp
xử lý dữ liệu trong các hệ thống sử dụng bộ nhớ chung, kể cả bộ nhớ trong
hay bộ nhớ thứ cấp, nhất thiết phải là một hệ thống có sử dụng giao tiếp
mạng với các trạm làm việc độc lập.
Những đặc điểm của một hệ sơ sở dữ liệu phân tán bao gồm:
- Điều khiển tập trung
- Tự quản trạm
- Độc lập dữ liệu
MÔN HỌC: PHƯƠNG PHÁP NGHIÊN CỨU KHOA HỌC TRONG TIN HỌC 4
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
- Tính trong suốt phân tán cơ sở dữ liệu
- Rút gọn dư thừa
- Tính lặp dữ liệu
- Cấu trúc vật lý phức và truy xuất hiệu suất cao
- Chương trình chỉ đường

dụng các tệp truyền thống hay các cơ sở dữ liệu mạng, phân cấp cũ hơn.
Phức tạp hơn nữa, dữ liệu trên các vị trí thường không tương thích. Các
mâu thuẫn điển hình bao gồm các khác biệt về cú pháp (sự biểu diễn khác
nhau của các khoản mục dữ liệu tại hai vị trí) và các khác biệt về ngữ nghĩa
4. Vấn đề về phân mãnh trong thiết kế cơ sở dữ liệu phân tán
Một cơ sở dữ liệu phân tán dựa trên mô hình quan hệ trước hết phải
tuân thủ các quy tắc về chuẩn hóa cho cơ sở dữ liệu quan hệ. Thêm vào đó,
để phân tán cơ sở dữ liệu cần có thao tác chính là phân mãnh các quan hệ.
Mục đích chính của việc phân mãnh các quan hệ là nhằm để nhận ra
các đoạn không trùng nhau. Có 2 cách phân mãnh chính:
- Phân mãnh ngang: là quá trình chia các bộ của quan hệ thành các tập
con. Mỗi tập con này có thuộc tính vị trí thông thường.
- Phân mãnh dọc: là quá trình chia nhỏ tập thuộc tính của một quan hệ
thành những quan hệ nhỏ hơn. Phân đoạn đúng khi mỗi thuộc tính của các
quan hệ con đều ánh xạ ít nhất sang một thuộc tính của quan hệ ban đầu.
Hơn nữa, có thể tạo lại quan hệ ban đầu bằng cách liên kết các quan hệ con
với nhau.
Để đảm bảo tính nhất quán của cơ sở dữ liệu, đặc biệt về ngữ nghĩa của
dữ liệu, khi phân mãnh cần tuân thủ các tính chất sau:
- Tính đầy đủ
- Tính tái thiết được
- Tính tách biệt
MÔN HỌC: PHƯƠNG PHÁP NGHIÊN CỨU KHOA HỌC TRONG TIN HỌC 6
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
II. Thuật toán năng lượng liên kết
1. Giới Thiệu
Có hai phương pháp chính thường được dùng trong việc tìm kiếm các
phân mãnh dọc là:
- Phương pháp nhóm: khởi đầu bằng tập các mãnh, mỗi mãnh có 1

Thuật toán năng lượng liên kết dựa vào ma trận ái lực thuộc tính AA để
sinh ra một ma trận ái lực tụ CA dựa trên các hoán vị hàng và cột, hoán vị
được thực hiện sao cho số đo ái lực chung AM là lớn nhất
Khi đặt 1 thuộc tính mới A
k
vào giữa A
i
và A
j
thì số đo độ đóng góp thực
cho ái lực chung là:
Với:
3. Các bước của thuật toán năng lượng liên kết
Bước 1: khởi gán và cố định một trong các cột của AA vào trong CA
Bước 2: lấy lần lượt một trong n-1 cột còn lại, đặt chúng vào i+1 vị trí
còn lại trong ma trận CA. Nơi đặt được chọn sao cho nó đóng góp nhiều nhất
cho số ái lực chung.
Bước 3: sau khi sắp xếp xong vị trí các cột ở bước 2, tiến hành sắp xếp
lại thứ tự của các hàng sao cho phù hợp với vị trí tương ứng của các cột
MÔN HỌC: PHƯƠNG PHÁP NGHIÊN CỨU KHOA HỌC TRONG TIN HỌC 8
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
Phần 2: Ứng Dụng Tìm Kiếm Phân Mãnh Dọc
I. Giới thiệu tổng quan về ứng dụng
Hình 1. Màn hình khởi tạo của ứng dụng
Hình 2. Màn hình kết quả của ứng dụng
MÔN HỌC: PHƯƠNG PHÁP NGHIÊN CỨU KHOA HỌC TRONG TIN HỌC 9
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
Ứng dụng tìm kiếm phân mãnh dọc cho phép người dùng nhập vào một

Tính toán và in ma trận CA ra màn hình
public void Insert_Column_3()
Tìm vị trí thích hợp cho cột 3
public void Insert_Column_4()
Tìm vị trí thích hợp cho cột 4
Các biến chính của chương trình bao gồm:
Bảng 2: Các biến chính trong chương trình
MÔN HỌC: PHƯƠNG PHÁP NGHIÊN CỨU KHOA HỌC TRONG TIN HỌC 11
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
Tên biến Chức năng
public int [,] qA
Ma trận truy xuất thuộc tính
public int [,] qS
Ma trận số đo tần số truy xuất ứng dụng
public int [,] AA
Ma trận ái lực thuộc tính đầy đủ
public int [,] CA
Ma trận kết quả
public int [] CA_pos
Vị trí sắp xếp của ma trận kết quả CA
Hàm tính toán cho ma trận ái lực thuộc tính đầy đủ AA được hiện thực
như sau:
public void CalculateAA()
{
int i, j, k, l;
for (i = 0; i < 4; i++)
{
for (j = 0; j < 4; j++)
{

vị trí các cột 3 và 4.
Hàm tính toán vị trí cột 3:
public void Insert_Column_3()
{
int pos0, pos1, pos2;
pos0 = 2 * Bond(2, CA_pos[0]);
MÔN HỌC: PHƯƠNG PHÁP NGHIÊN CỨU KHOA HỌC TRONG TIN HỌC 12
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
pos1 = 2 * Bond(CA_pos[0], 2) + 2 * Bond(2, CA_pos[1]) - 2 *
Bond(CA_pos[0], CA_pos[1]);
pos2 = 2 * Bond(CA_pos[1], 2);
int max = ((pos0 >= pos1 ? pos0 : pos1)) >= pos2 ? (pos0 >= pos1 ? pos0 :
pos1) : pos2;
if(max == pos0)
{
CA_pos[2] = CA_pos[1];
CA_pos[1] = CA_pos[0];
CA_pos[0] = 2;
}
if (max == pos1)
{
CA_pos[2] = CA_pos[1];
CA_pos[1] = 2;
}
if (max == pos2)
{
CA_pos[2] = 2;
}
}

}
if (max == pos3)
{
CA_pos[3] = 3;
}
}
MÔN HỌC: PHƯƠNG PHÁP NGHIÊN CỨU KHOA HỌC TRONG TIN HỌC 13
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
Việc tạo ra ma trận kết quả CA sẽ nhờ vào ma trận ái lực thuộc tính đầy
đủ AA và biến CA_pos dùng để lưu trữ các vị trí mới của các cột CA sau khi
đã qua tính toán. Hàm hiện thực của việc tạo ra ma trận CA như sau:
public void Cal_Print_CA()
{
// Calculate CA
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
CA[i, j] = AA[CA_pos[i], CA_pos[j]];
}
}
// Print CA
label48.Text = Convert.ToString(CA[0, 0]);
label49.Text = Convert.ToString(CA[0, 1]);
label50.Text = Convert.ToString(CA[0, 2]);
label51.Text = Convert.ToString(CA[0, 3]);
label52.Text = Convert.ToString(CA[1, 0]);
label53.Text = Convert.ToString(CA[1, 1]);
label54.Text = Convert.ToString(CA[1, 2]);

1. Bài giảng môn học “Thiết kế CSDL phân tán” .
Giảng viên : PGS.TS Đỗ Phúc
Chương trình đào tạo thac sĩ CNTT qua mạng.
2. M. Tamer Ozsu and Patrick Valduriez, "Principles of Distributed
Database Systems," Second Edition, Prentice Hall 1998.
3. Nguyễn Đức Thuần, bài giảng “Cơ sở dữ liệu phân tán”, đại học Thủy
Sản 2008
4. />MÔN HỌC: PHƯƠNG PHÁP NGHIÊN CỨU KHOA HỌC TRONG TIN HỌC 16