Bài giảng Cơ sở dữ liệu phân tán - Chương 2: Nguyên lý hệ cơ sở dữ liệu phân tán

3 ...
Ng 
Duc
 Thu
an
Định nghĩa không hình thức
Tập các vị từ hội Pr là tối thiểu nếu không tồn 
tại Pr’ Ì Pr là đầy đủ
Ng 
Duc
 Thu
an
Trở lại ví dụ:
(1) Pr = { } No
(2) Pr = {LOC=Sa, LOC=Sb} Yes
(3) Pr = {LOC=Sa, LOC=Sb, Sal<10} Yes
Đầy dủ ?
Pr(2) là tập con của Pr(3),
Do đó Pr(3) không là tối thiểu ...
Ng 
Duc
 Thu
an
Phân mảnh ngang suy dẫn
E(ENO, NAME, SAL, LOC)
J(ENO, DESCRIPTION,…)
Quan hệ một - nhiều
(chủ)
(thành viên)
Truy vấn:
Cho biết tên nhân viên,
danh sách các dự án mà nhân viên tham gia
E Þ F={ E1, E2} by LOC
Ng 
Duc
 Thu
an
E1
(at Sa) (at Sb)
E2
# NM Loc Sal
5 Joe Sa 10
8 Tom Sa 15
…
# NM Loc Sal
7 Sally Sb 25
12 Fred Sb 15
…
# Description
5 work on 347 hw
7 go to moon
5 build table
12 rest
…
J
Ng 
Duc
 Thu
an
E1
(at Sa) (at Sb)
E2# NM Loc Sal5 Joe Sa 10
8 Tom Sa 15
…
# NM Loc Sal
7 Sally Sb 25
12 Fred Sb 15
…
J1 J2
J1 = J E1 J2 = J E2
# Des
5 work on 347 hw
5 build table
…
# Des
7 go to moon
12 rest
…
Ng 
Duc
 Thu
an
Phân mảnh ngang suy dẫn
R, F = { F1, F2, ... Fn} 
ß
S, D = {D1, D2, …Dn} ở đây Di =S Fi
Qui ước : R là chủ
S là thành viên
Fcó thể là 
cơ sở hay suy dẫn
Ng 
Duc
 Thu
an
• Kiểm tra tính đầy đủ và tách biệt 
của phân mảnh suy dẫn
E Nhưng #= 33 không thuộc E1 và cũng không thuộc E2!
# Des
…
33 build chair
…
Ví dụ : Phát biểu J là:
Những bộ J sẽ không thuộc J1 cũng như không thuộc J2
Phân mảnh không đày đủ
Ng 
Duc
 Thu
an
Cần thỏa các tham chiếu ràng buộc toàn vẹn :
Kết nối attr(#) của quan hệ thành viên
ß
Kết nối attr(#)của quan hệ chủ
Để đạt tính đầy đủ
Ng 
Duc
 Thu
an
# NM Loc Sal
5 Joe Sa 10
…
# NM Loc Sal
5 Fred Sb 20
…
Ví dụ:
E1 E2
# Description
5 day off
…
# Description
5 day off
…
# Description
5 day off
…
J1
J
J2
Phân mảnh 
không tách biệt!
Ng 
Duc
 Thu
an
kết nối attribute(#)
nên là khóa của quan hệ chủ
Để đạt tính tách biệt
Ng 
Duc
 Thu
an
Tổng kết :Phân mảnh ngang
l Kiểu: cơ sở (primary), (suy dẫn)derived
l Đạc tính: tính đầy đủ (completeness), tính 
tách biệt (disjointness)
l Vị từ :tối thiểu (minimal), (đầy đủ) uniform
Ng 
Duc
 Thu
an
Phân mảnh dọc
E1
# NM Loc Sal
5 Joe Sa 10
7 Sally Sb 25
8 Fred Sa 15
…
# NM Loc
5 Joe Sa
7 Sally Sb
8 Fred Sa
…
# Sal
5 10
7 25
8 15
…
E
E2
Ví dụ:
Ng 
Duc
 Thu
anR[T] Þ R1[T1] Ti Í T
Rn[Tn]
Giống như sự chuẩn hóa các quan hệ
...
Ng 
Duc
 Thu
an
Tính chất: R[T] Þ Ri[Ti] 
(1)Tính đầy đủ
U Ti = T
all i
Ng 
Duc
 Thu
an(2) Tính tách biệt
Ti Ç Tj = Æ for all i,j i¹j
E(#,LOC,SAL)
E1(#,LOC)
E2(SAL)
Ng 
Duc
 Thu
an
# NM Sal
5 Joe 10
7 Sally 25
…
E
E1
# NM
5 Joe
7 Sally
…
Sal
10
25
E2
# NM Sal
5 Joe 10
7 Sally 10
5 Joe 25
7 Sally 25
Ng 
Duc
 Thu
an
(2)Tính tách biệt
Ti Ç Tj = Æ for all i,j i¹j
E(#,LOC,SAL) E1(#,LOC)
E2(SAL)
Không là 1 tính chất suy dẫn!!
(Không thể kiến thiết lại R!)
Ng 
Duc
 Thu
an
(3) Tính kiến thiết:Kết nối không mất thông tin
Ri = R
all i
E Một cách để kết nối không mất thông tin:
Mọi phân mảnh đều chứa khóa,
Key Í Ti for all i
Ng 
Duc
 Thu
an
ó Làm thế nào để quyết định các 
thuộc tính gộp nhóm với nhau?
E1(#,NM,LOC)
E2(#,SAL)
Example:
E(#,NM,LOC,SAL) E1(#,NM)
E2(#,LOC)
E3(#,SAL)
?
Ng 
Duc
 Thu
an
Ái Lực thuộc tính (Attribute affinity)
l Xét lược đồ quan hệ R(A1, A2,…,An)
l Các ứng dụng Q(q1, q2,….,qm)
l Use (qi, Aj) = 1, nếu Aj được qi tham chiếu
0, trong trường hợp ngược lại
Use(qi, Aj) : giá trị sử dụng thuộc tính
Ng 
Duc
 Thu
an
Ái Lực thuộc tính (Attribute affinity)
l Ví dụ * Ma trận mẫu về giá trị sử dụng thuộc tính 
(Ma trậnái lực thuộc tính AA)
1100q4
1010q3
0110q2
0101q1
A4A3A2A1
Ng 
Duc
 Thu
an
Ái Lực thuộc tính (Attribute affinity)
l Giá trị sử dụng thuộc tính không đủ cơ sở
cho việc phân mảnh: chúng không biểu thị 
độ lớn của tần số ứng dụng.
l Số đo lực hút (affinity) của 2 thuộc tính Ai, Aj 
ký hiệu aff(Ai, Aj) biểu thị cho cầu nối (bond) 
giữa 2 thuộc tính, dựa vào sự truy xuất của 
các ứng dụng 
Ng 
Duc
 Thu
an
Ái Lực thuộc tính (Attribute affinity)
l Tamer Ôzsu nêu công thức để đo ái lực của 2 
thuộc tính Ai, Aj:
l Gọi k là số mảnh của quan hệ R. R =R1R2R3..Rk
l Q = {q1,q2,..,qm} : tập các ứng dụng trên R
l Q(A,B) là tập các ứng dụng q của Q mà:
use(q,A). Use(q,B) =1
Ng 
Duc
 Thu
an
Ái Lực thuộc tính (Attribute affinity)
l Ái lực giữa 2 thuộc tính Ai và Aj của quan hệ R và tập ứng 
dụng Q được định nghĩa:
l Aff(Ai, Aj) = ∑ ∑ refl(q)accl(q)
qєQ(Ai, Aj) l є Rl
refl(q) : số truy xuất đến các thuộc tính (Ai, Aj) cho mỗi ứng
dụng q tại vị trí Rl
accl(q) : tần số truy xuất ứng dụng q đến các thuụoc tính Ai,Aj 
tại vị trí l.
Ng 
Duc
 Thu
an
Ái Lực thuộc tính (Attribute affinity)
l Ví dụ : Xét lại ví dụ * , giả sử refl(q) =1 cho tất cả q 
và Sl, và số mảnh là 3. Tần số ứng dụng cho mọi 
cặp thuộc tính là:
l accl(q1) = 15 ,accl(q1) = 20 , accl(q1) = 10
l accl(q2) = 5 ,accl(q2) = 0 , accl(q2) = 0
l accl(q3) = 25 ,accl(q3) = 25 , accl(q3) = 25
l accl(q4) = 3 ,accl(q4) = 0 , accl(q3) =0
Ng 
Duc
 Thu
an
Ái Lực thuộc tính (Attribute affinity)
l Lúc này số đo ái lực giữa thuộc tính A1 và
A3 là:
l Aff(A1, A3) = ∑ ∑ accl(q)
qєQ(Ai, Aj) l=1
=accl(q1) + acc2(q1) + acc3(q1) = 45
3
Ng 
Duc
 Thu
an
783750A4
353545A3
755800A2
045045A1
A4A3A2A1
Ma trận ái lực thuộc tính (Attribute affinity matrix)
Ng 
Duc
 Thu
an
Thuật toán năng lượng nối BEA (Bond 
Energy Algorithm)
l Tác giả : Hofer & Severance, 1975 và Navathe et 
al, 1984.
l Ý nghĩa: 
– Xác định các nhóm thuộc tính
– Độ phức tạp O(n2)
– Không làm thay đổi kết quả tụ nhóm
Thuật toán thực hiện các hoán vị hàng, cột sinh ra 1 ma 
trận ái lực CA ( Cluster affintity 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
Ng 
Duc
 Thu
an
Thuật toán năng lượng nối BEA (Bond 
Energy Algorithm)
l AM = ∑ ∑ aff(Ai, Aj) [aff(Ai, Aj-1) + aff(Ai, 
Aj+1) + aff(Ai-1, Aj) +aff(Ai+1, Aj) ]
Với aff(A0, Aj)= aff(Ai, A0) = aff(An+1, Aj) =
aff(Ai, An+1) = 0 , cho mọi i, j 
(Ý nghĩa ?)
n n
i=1 J=1
Ng 
Duc
 Thu
an
Thuật toán năng lượng nối BEA (Bond 
Energy Algorithm)
l Hàm cực đại hóa chỉ xét những lân cận gần nhất , 
vì thế các giá trị lớn được nhóm lại với nhau, các 
giá trị nhỏ được nhóm lại với nhau. Ma trận ái lực 
thuộc tính AA có tính đối xứng nên số đo ái lực có
thể rút gọn:
l AM = ∑ ∑ aff(Ai, Aj) [aff(Ai, Aj-1) + aff(Ai,Aj+1) ]
n n
i=1 J=1
Ng 
Duc
 Thu
an
Thuật toán năng lượng nối BEA (Bond 
Energy Algorithm)
l Quá trình sinh ma trận ái lực gồm 3 bước:
l 1. Khởi gán: Đặt và cố định 1 trong các cột của AA 
vào trong CA. Cột 1 được chọn.
l 2. Thực hiện lặp: Lấy lần lượt 1 trong n-i cột còn lại 
(i là số cột đã được đặt vào CA) và thử đặt vào i+1 vị
trí còn lại trong ma trận CA. Chọn đặt sao cho AM là
lớn nhất. Lặp đến hết các cột.
l Sắp thứ tự hàng: Khi thứ tự cột đã xác định, các 
hàng cũng cần đặt lại để các vị trí tương đối của 
chúng phù hợp với các vị trí trí tương đối của cột.
Ng 
Duc
 Thu
an
Thuật toán năng lượng nối BEA (Bond 
Energy Algorithm)
l Một ví dụ tính toán cho thuật toán BEA
Ng 
Duc
 Thu
an
Thuật toán phân mảnh dọc
l Tính ma trận ái lực CA
l Tìm “ điểm chia “ : Ái lực lớn nhất cho mỗi 
phân mảnh
787530A4
758050A3
355345A2
004545A1
A4A3A2A1
Ng 
Duc
 Thu
an
Phân mảnh lai tạp (Hybrid Fragmentation)
R
R1 R2
R11 R12 R21 R22
Ngang
Dọc
Ng 
Duc
 Thu
an
Kiến thiết lại phân mảnh lai tạp
R11 R12 R21 R22
Ngang
Dọc
U
Ng 
Duc
 Thu
an
Allocation
Example: E(#,NM,LOC,SAL) Þ
F1 = sloc=Sa E ; F2 = sloc=Sb E
Qa: select … where loc=Sa...
Qb: select … where loc=Sb…
Site a Site b
F1,F2
làm gì ở đâu?
?
Ng 
Duc
 Thu
an
Các vấn đề thảo luận
l Các truy vấn bắt đầu từ đâu
l Chi phí truyền thông là gì?
kích thước kết quả,quan hệ,…
l Dung lượng lưu trữ là gì, chi phí tại các site?
Và kích thước của các phân mảnh?
Ng 
Duc
 Thu
an
l Chiến lược xử lý truy vấn?
– Các kết nối thực hiện như thế nào?
– Các kết quả được kết xuất như thế nào?
Các vấn đề khác
Ng 
Duc
 Thu
an
l Chi phí của việc cập nhật các bản sao?
l Ghi và điều khiển tương tranh?
l ...
Vì sao tiến hành lặp các phân 
mảnh?
Ng 
Duc
 Thu
an
Bài toán tối ưu:
l Việc sắp đặt các phân mảnh tốt nhất /số 
lượng các bản sao tốt nhất để:
– Thời gian trả lời truy vấn bé nhất
– Thông lượng lớn nhất
– Các chi phí nhỏ nhất
– ...
l Các vấn đề ràng buộc?
– Khả năng lưu trữ
– Khả năng của băng thông,..
– ...
Đây là một bài toán khó vô cùng
Ng 
Duc
 Thu
an
Mô hình đơn giản
Phân mảnh đơn F
Các Site S1, … Sm
Các biến X1, …, Xm
Xj = 0 if F không lưu trử tại Sj
1 if F lưu trữ Sj
Tổng chi phí = Chi phí đọc+ Chi phí ghi+
Chi phí lưu trữ
Xác định các giá trị cho Xj, 1 £ j £ m, 
Sao cho chi phí là nhỏ nhất
Ng 
Duc
 Thu
an
Chi phí đọc
Chi phí đọc= å [ti ´ MIN Cij]
i: site có yêu cầu
ti: số lượng tin đọc tại Si
Cij: Chi phí lấy tin truy xuất phân mảnh F tại 
Sj từ Si
ji=1
m
Ng 
Duc
 Thu
an
Chi phí ghi =
å å Xj ui C’ij
i: site có yêu cầu 
j: Site được cập nhật
Xj: 0 nếu F không lưu trữ tại Sj
1 nếu F lưu trữ tại Sj
ui: lượng tin ghi tại Si
C’ij: Chi phí ghi của việc cập nhật F tại Sj từ Si
i=1 j=1
m m
Ng 
Duc
 Thu
an
Chi phí lưu trữ:
å Xi di
Xi: 0 nếu F không lưu trữ tại Sj
1nếu F lưu trữ tại Sj
di: Chi phí lưu trữ của F tại Si
i=1
m
Ng 
Duc
 Thu
an
Hàm mục tiêu:
min å [ti ´MIN Cij + å Xj ´ ui ´ C’ij ]
+ å Xi ´ di
ji=1 j=1
i=1
m m
m
Ng 
Duc
 Thu
an
Có thể có thêm các chi phí phức tạp 
hơn:
Ví dụ:
-Nhiều phân mảnh
-Kích thước phân mảnh
-Chi phí điều khiển tương tranh
Ng 
Duc
 Thu
an
Định vị
l Ngay cả trường hợp đơn giản nhất cũng là 
NP-đầy đủ
l Thông thường chúng ta có thể sử dụng 
trường hợp
– Đặt các phân mảnh ở đó chúng được truy xuất 
nhiều nhất
Ng 
Duc
 Thu
an
Tổng kết
l Phân mảnh ngang, dọc
l Phân mảnh tốt
l Thiết kế phân mảnh tốt
l Định vị