ĐẠI HỌC QUỐC GIA TP.HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CAO HỌC KHÓA VI - KHÓA HỌC 2012 - 2014
****

****
Giáo viên hướng dẫn:
PGS. TS. Đỗ Phúc
Người thực hiện:
Trần Thị Kiều Diễm (MS: CH1101074)
Trang 1/1410/04/2015
LỜI NÓI ĐẦU
1. Giới thiệu đề tài
Trong cuộc sống hiện đại ngày nay của chúng ta, sự bùng nổ của ngành
công nghệ thông tin và sự tiện ích của Internet, nhu cầu sử dụng các dịch vụ như
thương mại điện tử, giao dịch điện tử, quản lí công ty xuyên quốc gia,…đã rất
được quan tâm và theo đó mô hình cơ sở dữ liệu phân tán được ra đời nhằm đáp
ứng nhu cầu từ thực tiễn.
Trước hết, ta nên hiểu cơ sở dữ liệu phân tán không phải là một tập hợp
những tập tin được lưu riêng lẻ tại mỗi nút của một mạng máy tính mà đó là những
tập tin có tính liên đới logic, có cấu trúc chung và được truy xuất qua một giao
diện chung. Nhiệm vụ của các nhà quản trị cơ sở dữ liệu là đưa ra mô hình cơ sở
dữ liệu phân tán tối ưu nhất và một trong các chiến lược đó là phương pháp phân
mảnh, thật sự trong một cơ sở dữ liệu thì dữ liệu đã được cấu trúc bằng các quan
hệ, tuy nhiên mỗi bộ trên một quan hệ không phải lúc nào cũng có tần số được truy
xuất như nhau, do đó chúng ta cần phân mảnh các quan hệ thành các mảnh con
sao cho những bộ có tần số truy xuất gần giống nhau sẽ được tổ chức trong cùng
một mảnh. Có 2 thuật toán phân mảnh là phân mảnh ngang và phân mảnh dọc.
Phạm vị bài thu hoạch này xin trình bày cơ sở lý thuyết của thuật toán phân
mảnh dọc, từ một quan hệ cho trước với ma trận sử dụng và ma trận tần số truy
xuất ta có được 2 mảnh con.

và mỗi thuộc tính A
j
ta định nghĩa giá
trị sử dụng (attribute usage value) như sau:



=
ji
ji
ji
Achieuthamkhongq
Achieuthamq
Aquse
0
1
),(
− Ví dụ: Xét quan hệ PROJ gồm 4 thuộc tính {PNO; PNAME;
BUDGET; LOC}
q
1
: Tìm ngân sách của dự án, cho biết mã số dự án.
SELECT BUDGET
FROM PROJ
WHERE PNO = Value
q
2
: Tìm tên và ngân sách của tất cả dự án.
SELECT PNAME, BUDGET
FROM PROJ

− Định nghĩa: Cho S={s1,…,sL} là tập các site, với mỗi câu vấn tin qi
và mỗi vị trí sj ta định nghĩa ma trận tần số truy xuất (access frequency matrix)
Acc(qi, sj), như sau: Acc(q
i
, s
j
) = k, với mọi k>=0.
− Ví dụ:
003
252525
005
102015
4
3
2
1
321
q
q
q
q
sss
2. Giới thiệu các thuật toán dùng trong phân mảnh dọc
a. Thuật toán tính độ đo ái lực Aff(A
i
,A
j
):
− Định nghĩa: Độ đo ái lực thuộc tính giữa 2 thuộc tính Aivà Aj của
quan hệ R[A1,A2,…,An] ứng với tập quan hệ Q = (q1, q2, …, qq) được định nghĩa

− Output: Ma trận ái lực gom cụm CA là một sắp xếp của các hoán vị
AA
− Thuật toán:
1. Kh i t o: C đ nh m t trong các c t c a AA và đặt vào CA.
2. Lặp: Đặt n-i cột còn lại vào i+1 vị trí còn lại trong ma trận CA.
Đối với từng cột, chọn vị trí đóng góp (contri bution) lớn nhất vào độ đo ái lực
toàn cục.
3. Sắp thứ tự hàng: Sắp xếp các dòng theo thứ tự cột.
Tính các giá trị để tìm được vị trí đặt A
k
vào vị trí thích hợp trong
CA đã được tạo ra tại bước 2
cont(A
i
, A
k
, A
j
) = 2bond(A
i
, A
k
)+2bond(A
k
, A
l
) –2bond(A
i
, A
j

chọn đặt cố định. Tìm vị trí đặt A
3
:
AA =
783750
353545
755800
045045
4
3
2
1
4321
A
A
A
A
AAAA
CA =
750
545
800
045
21
AA

• Thứ tự trước (0-3-1) :
cont(A
0
,A

, A
2
)–2bond(A
1
,A
2
)
=2* 4410 + 2* 890 – 2*225 = 10150
• Thứ tự cuối (2-3-4) :
cont (A
2
,A
3
,A
0
)= 2bond(A
2
, A
3
)+2bond(A
3
, A
0
)–2bond(A
2
,A
0
)
=1780
Do vậy ma trận CA có dạng:

A2, …,An} thành hai cụm {A1, A2, …, Ai} và {Ai+1, …, An} sao cho số ứng
dụng truy cập cả hai là ít nhất và số ứng dụng truy cập mỗi cụm là lớn nhất.
− Xét ma trận ái lực gom cụm CA sau:
A
1
A
i
A
i+1
A
n
A
1
: TA
A
i
A
i+1
: BA
A
n
Tập {A
1
, , A
i
} ở góc trên trái và tập {A
1+1
, , A
n
} ở góc dưới phải.

=
∑ ∑
∈ ∈
OQq Ss
ijij
i j
qaccqref )()(
− Cuối cùng tính: CTQ*CBQ - COQ
2
− Với ví dụ trên:
AQ(q1) = {A1, A3}
AQ(q2) = {A2, A3}
AQ(q3) = {A2, A4}
AQ(q4) = {A3, A4}
Chọn điểm chia lần lượt là A1, A2, A3, cuối cùng ta chong được điểm
chia là A3 vì khi đó
TA={A1, A3}
BA={A2, A4}
TQ={q1}
BQ={q3}
OQ={q2, q4}
CTQ= 45
CBQ=75
Bài thu hoạch môn Cơ sở dữ liệu nâng cao
COQ=8
CTQ*CBQ - COQ
2
= 3311 (là max)
Vậy ta có hai phân mảnh: R1 = {A
1

void readfile(char path[20],int q, int n, int s, int key);
void ShowUse(int q, int n);
void ShowAcc(int q, int s);
void SolveAff(int n);
void ShowAff(int n);
Bài thu hoạch môn Cơ sở dữ liệu nâng cao
int bond(int i,int j);
int cont(int i, int k, int j);
void seclectMaxCont();
void ShowCA(int n);
void BEA();
int TQ(int qi);
int BQ(int qi);
int CTQ();
int CBQ();
int COQ();
int selectPoint();
void showFragment();
void VFA();
void main()
{ printf("Moi nhap duong dan den tep vf.txt: ");
scanf("%s\n",&path);
readfile(path, q, n, s, key);
ShowUse(q,n);
ShowAcc(q,s);
SolveAff(n);
ShowAff(n);
ShowCA(n);
BEA();
showFragment();