Bài giảng Cơ sở dữ liệu nâng cao - Chương 1: Tổng quan cơ sở dữ liệu phân tán - Nguyễn Thị Mỹ Dung

 
 Công thức đo lực hút aff(Ai,Aj) 
 Gọi k là số các mảnh của R được phân mảnh. 
 Q = (q1,q2,,qm) là tập các câu vấn tin ( tức là 
tập các ứng dụng chạy trên quan hệ R). 
 Đặt Q(A,B) là tập các ứng dụng q của Q mà 
use(q,A).use(q,B)= 1. 
 Nói cách khác: 
 Q(A,B) = {qQ: use(q,A)=use(q,B)=1} 
 Chương 1: CSDL phân tán 55 
 Phân mảnh dữ liệu (8.2. tt) 
Trong đó: 
  ref1(qk) là số truy suất tới các thuộc tính (Ai, Aj) 
 cho mỗi ứng dụng qk tại vị trí S1 
  acc1(qk) là số đo tần số truy xuất ứng dụng qk 
 đến các thuộc tính Ai, Aj tại vị trí S1. 
 Chương 1: CSDL phân tán 56 
 Ví dụ ma trận tần suất truy cập 
 S1 S2 S3 
 q1 15 20 10 
 q2 5 0 0 
 q3 25 25 25 
 q4 3 0 0 
 Khi đó độ đo lực hút giữa A1, A1 được tính bằng: 
 푙 3
Aff (A1, A1) = =1 푙=1 1 푞 = 1 푞1 + 2 푞1 + 3 푞1 
Aff (A1, A1) = 1*45 + 0*5 + 0*75 + 0*3 = 45 
Tương tự: 
Aff (A2, A3) = 0*45 + 1*5 + 0*75 + 0*3 = 5 
 Chương 1: CSDL phân tán 57 
 Ví dụ ma trận lực hút thuộc tính (AA) 
 A1 A2 A3 A4 
 A1 45 0 45 0 
 A2 0 80 5 75 
 A3 45 5 53 3 
 A4 0 75 3 78 
Chương 1: CSDL phân tán 58 
 Phân mảnh dữ liệu (8.2. tt) 
 ii/ Thuật toán năng lượng liên kết BEA 
 Nó được thiết kế đặc biệt để xác định các nhóm 
gồm các mục tương tự, khác với 1 sắp xếp tuyến 
tính của các mục. 
 Thuật toán BEA lấy nguyên liệu là ma trận ái lực 
thuộc tính AA, hoán vị các hàng và cột rồi sinh ra 
một ma trân ái lực tụ CA (Clustered affmity matrix). 
 Hoán vị được thực hiện sao cho số đo ái lực 
chung AM (Global Affmity Measure) là lớn nhất. 
Trong đó AM là đại lượng: 
 Chương 1: CSDL phân tán 59 
 Thuật toán BEA (tt) 
  Năng lượng cầu nối giữa hai thuộc tính: 
 Bond(Ax , Ay) = ∑z=1n aff(Az , Ax)aff(Az, Ay) 
  Gom nhóm các thuộc tính: 
 - Cont(Ai,Ak,Aj) đây là số đo ái lực chung khi đặt 
thuộc tính Ak vào giữa các thuộc tính Ai, Aj. 
 Cont(Ai,Ak,Aj) = 
 2bond(Ai,Ak) + 2bond(Ak,Aj) – 2bond(Ai,Aj) 
 - Nếu bên trái Ai không có thuộc tính nào khác thì 
ta có công thức tính = 0. 
 - Hoặc bên phải Aj không có thuộc tính nào thì ta 
vẫn tính = 0. 
 Chương 1: CSDL phân tán 60 
 Ví dụ ma trận gom nhóm (CA) 
 Xét ma trận AA 
  Tính cầu nối (Bond) như sau: 
 Bond (A1, A2) = 
 45*0 + 0*80 + 45*5 + 0*75 = 225 
Tương tự tính: Bond (A1, A3); Bond (A1, A4); Bond (A2, A3); 
Bond (A2, A4); Bond (A3, A4); 
  Gom nhóm: 
 Chọn ngẫu nhiên 2 cột đầu tiên A1, A2. 
 Chèn cột A3 vào giữa A1, A2. Ta có các vị trí: 
 Cont (_, A3, A1) = 2bond(_,A3) + 
 2bond(A3,A1) – 2bond(_,A1) = 8820 
 Cont (A1,A3,A2) = 2bond (A1,A3) + 
 2bond(A3, A2) – 2bond (A1,A2) = 10150 
 Cont (A2,A3,_) = 2bond (A2,A3) + 
 2bond(A3, _) – 2bond (A2,_) = 1780 
Chương 1: CSDL phân tán 61 
 Ví dụ ma trận gom nhóm (CA) (tt) 
 Chọn vị trí có năng lượng liên kết cao nhất: 
A1, A3, A2 
 Tương tự: Chèn A4 vào vị trí thích hợp. Ta có các 
vị trí: {A4, A1, A3, A2}; {A1, A4, A3, A2}; {A1, A3, A4, 
A2}; {A1, A3, A2, A4} 
 Cont (_,A4,A1) = 2bond (_,A4) + 
 2bond(A4, A1) – 2 bond (_,A1) = 270 
 Cont (A1,A4,A3) = 2bond (A1,A4) + 
 2bond(A4, A3) – 2bond (A1,A3) = - 7014 
 Cont (A3,A4,A2) = 2bond (A3,A4) + 
 2bond(A4, A2) – 2bond (A3,A2) = 23486 
 Chương 1: CSDL phân tán 62 
 Ví dụ ma trận gom nhóm (CA) (tt) 
 Cont (A2,A4,_) = 2bond (A2,A4) + 
 2bond(A4, _) – 2bond (A2,_) = 23730 
 Chọn vị trí có năng lượng liên kết cao nhất: 
A1, A3, A2, A4 
 A1 A3 A2 A4 
 A1 45 45 0 0 
 A3 45 53 5 3 
 A2 0 5 80 75 
 A4 0 3 75 78 
 Chương 1: CSDL phân tán 63 
 Phân mảnh dữ liệu (8.2. tt) 
 iii/ Thuật toán phân hoạch 
 Mục đích của hành động tách thuộc tính là tìm ra 
các tập thuộc tính được truy xuất cùng nhau hoặc 
hầu như là các tập ứng dụng riêng biệt. 
 Xét ma trận gom nhóm (thuộc tính tụ): 
 Chương 1: CSDL phân tán 64 
 Phân mảnh dữ liệu (8.2. tt) 
 Tập ứng dụng Q={q1, q2,,qq} và định nghĩa tập 
ứng dụng chỉ truy xuất TA, chỉ truy xuất BA hoặc cả 
hai, những tập này được định nghĩa như sau: 
 AQ(qi) = Aj  use (qi, Aj) = 1 
 TQ = qi  AQ (qi)  TA  
 BQ = qi  AQ (qi)  BA  
 Chương 1: CSDL phân tán 65 
 Phân mảnh dữ liệu (8.2. tt) 
 Vị trí tốt nhất để phân chia là vị trí tạo ra các tập 
TQ và BQ sao cho tổng truy nhập từng mảnh là 
tối đa, tổng truy nhập cả 2 mảnh là tối thiểu. Các 
phương trình chi phí như sau: 
 Z = CTQ*CBQ – COQ2 
 Chọn điểm phân hoạch 
 với giá trị Z là lớn nhất 
 Chương 1: CSDL phân tán 66 
 Ví dụ phân hoạch 
 Xét ma trận gom nhóm CA 
 Áp dụng thuật giải VF 
 Tạo phân hoạch TQ = {A1} , BQ = {A3 , A2 , A4} 
 A1 A3 A2 A4 
 A1 45 45 0 0 
 A3 45 53 5 3 
 A2 0 5 80 75 
 A4 0 3 75 78 
 Chương 1: CSDL phân tán 67 
 Ví dụ phân hoạch (tt) 
 CTQ = 0 // không có q nào truy cập A1 
 CBQ = acc(q3) + acc(q2) + acc(q4) = 83 
 // q3, q2, q4 chỉ truy cập tập con {A3, A2, A4} 
 COQ = acc(q1) = 45 //q1 truy cập cả 2 TQ, BQ 
 Z = CTQ * CBQ – COQ2 = -2025 
 Tạo phân hoạch TQ = {A1, A3} , BQ = { A2 , A4} 
 CTQ = acc(q1) = 45 //q1 chỉ truy cập {A1, A3} 
 CBQ = acc(q3) = 75 //q3 chỉ truy cập {A2, A4} 
 COQ = acc(q2) + acc(q4) = 8 
 // q2, q4 truy cập cả 2 TQ, BQ 
 Z = CTQ * CBQ – COQ2 = 3311 
 Chương 1: CSDL phân tán 68 
 Ví dụ phân hoạch (tt) 
 Tạo phân hoạch TA = {A1, A3, A2} , BA = {A4} 
 CTQ = 50 
 CBQ = 0 
 COQ = 78 
 Z = CTQ * CBQ – COQ2 = -6084 
 Chọn phân hoạch TA = {A1 , A3} , BA = {A2 , 
 A4} 
 Giả sử A1 là khóa ta sẽ có 2 phân hoạch {A1, A3} 
 {A1, A2, A4} 
 Chương 1: CSDL phân tán 69 
 Bài tập 
 Dùng thuật toán BEA và VF để phân mảnh dọc. 
Cho ma trận truy vấn: Q = {Q1,Q2, Q3, Q4}, ma trận 
quan hệ A = {A1, A2, A3, A4}, ma trận tần số truy cập 
S = {S1, S2, S3}. 
 A1 A2 A3 A4 S1 S2 S3 
 Q1 0 1 1 0 Q1 10 20 0 
 Q2 1 1 1 0 Q2 5 0 10 
 Q3 1 0 0 1 Q3 0 35 5 
 Q4 0 0 1 0 Q4 0 10 0 
 Chương 1: CSDL phân tán 70 
 Bài tập (tt) 
 Yêu cầu: 
 1. Dùng độ đo lực hút tính ma trận ái lực (AA)? 
 2. Dùng thuật toán BEA để chuyển ma trận AA sang 
ma trận gom nhóm (CA)? 
 3. Dùng thuật toán VF tính điểm chéo trên ma trận 
CA? 
 Hướng dẫn câu 1: 
 B1: Tính tổng tần số truy cập trên ma trận S 
 B2: Tính ma trận AA theo công thức 
 Aff(A1,A1) = A1 * Q1 + A1 * Q2 + A1* Q3 + A1 * Q4 
 Aff(A1,A2) = Aff(A2,A1) =A1,A2 * Q1 + A1,A2 * Q2 + 
A1,A2 * Q3 + A1,A2 * Q4 
Chương 1: CSDL phân tán 71 
 Phân mảnh dữ liệu (tt) 
 3. Phân mảnh hỗn hợp 
 Kết hợp cả 2 dạng phân mảnh ngang và phân 
mảnh dọc. 
 Chương 1: CSDL phân tán 72 
 Ví dụ về phân mảnh dữ liệu 
Ví dụ: Xét cơ sở dữ liệu của một công ty phần mềm được tổ 
 chức như sau: 
 NHANVIEN (MANV, TENNV, CHUCVU): quan hệ này 
 chứa dữ liệu về nhân viên của công ty. 
 TLUONG (CHUCVU, LUONG): quan hệ này chứa dữ liệu 
 liên quan về lương và chức vụ của nhân viên. 
 DUAN (MADA, TENDA, NGANSACH): quan hệ này chứa 
 dữ liệu về các dự án mà công ty đang thực hiện. 
 HOSO (MANV, MADA, NHIEMVU, THOIGIAN): quan hệ 
 này chứa dữ liệu về hồ sơ của nhân viên được phân công 
 thực hiện dự án). 
 Cơ sở dữ liệu của một công ty máy tính 
 NHANVIEN (E) HOSO(G) 
MANV TENNV CHUCVU MANV MADA NHIEMVU THOIGIAN 
A1 Nam Phân tích HT A1 D1 Quản lý 12 
A2 Trung Lập trình viên A2 D1 Phân tích 34 
A3 Đông Phân tích HT A2 D2 Phân tích 6 
A4 Bắc Phân tích HT A3 D3 Kỹ thuật 12 
A5 Tây Lập trình viên A3 D4 Lập trình 10 
A6 Hùng Kỹ sư điện A4 D2 Quản lý 6 
A7 Dũng Phân tích HT A5 D2 Quản lý 20 
A8 Chiến Thiết kế DL A6 D4 Kỹ thuật 36 
 A7 D3 Quản lý 48 
 A8 D3 Lập trình 15 
 DUAN (J) TLUONG (S) 
 MADA TENDA NGANSACH CHUCVU LUONG 
 D1 CSDL 20000 Kỹ sư điện 1000 
 D2 CÀI ĐẶT 12000 
 D3 BẢO TRÌ 28000 Phân tích HT 2500 
 D4 PHÁT TRIỂN 25000 Lập trình viên 3000 
 Thiết kế DL 4000 
Ví dụ về phân mảnh dữ liệu 
Ví dụ về phân mảnh dữ liệu 
 IX. Cấp phát tài nguyên trong hệ phân tán 
 1. Bài toán cấp phát (allocation problem): 
 Giả sử có một tập các mảnh F = {F1, F2, ..., Fk } và 
một mạng máy tính bao gồm các vị trí S= {S1, S2, ..., 
Sm } trên đó có một tập các ứng dụng Q={Q1, Q2, ..., 
Qq } đang thực thi. 
 Hãy tìm một phân phối tối ưu các mảnh F cho các 
vị trí S. 
IX. Cấp phát tài nguyên trong hệ phân tán 
Một phân phối được gọi là tối ưu nếu thỏa mãn hai yếu tố sau: 
a. Chi phí nhỏ nhất: hàm chi phí bao gồm: 
• Chi phí lưu mỗi mảnh dữ liệu Fi tại vị trí Sj 
• Chi phí truy vấn Fi tại vị trí Sj 
• Chi phí cập nhật Fi tại tất cả các vị trí có chứa nó 
• Chi phí truyền dữ liệu. 
Bài toán cấp phát sẽ tìm một lược đồ cấp phát với hàm chi phí 
 là cực tiểu. 
b. Hiệu quả: chiến lược cấp phát được thiết kế nhằm cực tiểu 
 hóa thời gian thực hiện và tăng tối đa lưu lượng hệ thống tại 
 mỗi vị trí. 
IX. Cấp phát tài nguyên trong hệ phân tán 
 Bài toán cấp phát tổng quát, ký hiệu DAP (Database 
 Allocation Problem), là một bài toán NP-đầy đủ. Vì thế hầu 
 hết các nghiên cứu đã được dành cho việc tìm ra được các 
 thuật giải heuristic để có được lời giải tối ưu cho loại bài 
 toán này. 
 Hiện nay chưa có một mô hình heuristic tổng quát nào 
 nhận một tập các mảnh và sinh ra một chiến lược cấp phát 
 gần tối ưu ứng với các ràng buộc cho trước mà chỉ mới 
 đưa ra một số giả thiết đơn giản hóa và dễ áp dụng cho 
 một số cách đặt vấn đề đơn giản. 
 IX. Cấp phát tài nguyên trong hệ phân tán 
 2. Thông tin cấp phát 
 Ở giai đoạn cấp phát, chúng ta cần các thông tin định 
lượng về cơ sở dữ liệu, về các ứng dụng chạy trên đó, về cấu 
trúc mạng, về khả năng xử lý và giới hạn lưu trữ của mỗi vị trí 
trên mạng. 
 a. Thông tin về cơ sở dữ liệu 
 b. Thông tin về ứng dụng 
 c. Thông tin về vị trí 
 d. Thông tin về mạng 
 X. XỬ LÝ TRUY VẤN TRONG CSDL PHÂN TÁN 
 + Vai trò của thể xử lý vấn tin phân tán là ánh xạ câu truy vấn 
cấp cao trên một CSDL phân tán vào một chuỗi các thao tác của 
đại số quan hệ trên các mảnh, thể hiện các bước: 
 Câu truy vấn phải được phân rã thành một chuỗi các phép toán 
 quan hệ được gọi là vấn tin đại số. 
 Thứ hai, dữ liệu cần truy xuất phải được cục bộ hóa để các 
 thao tác trên các quan hệ được chuyển thành các thao tác trên dữ 
 liệu cục bộ (các mảnh). 
 Cuối cùng câu truy vấn đại số trên các mảnh phải được mở 
 rộng để bao gồm các thao tác truyền thông và được tối ưu hóa 
 để hàm chi phí là thấp nhất. 
 + Hàm chi phí muốn nói đến các tính toán như thao tác xuất 
nhập đĩa, tài nguyên CPU, và mạng truyền thông. 
 Xử lý truy vấn trong csdl phân tán (tt) 
VD 1: 
Xét một tập con của lược đồ CSDL đã được cho 
 NV( MNV, TênNV, Chức vụ) 
 PC (MNV, MDA, Nhiệm vụ, Thời gian) 
Và một câu truy vấn đơn giản sau: 
“Liệt kê tên của các nhân viên hiện đang quản lý một dự 
 án” 
Biểu thức truy vấn bằng phép tính quan hệ theo cú pháp 
 của SQL là: 
 SELECT TênNV 
 FROM NV, PC 
 WHERE NV.MNV=PC.MNV 
 AND Nhiệmvụ=”Quảnlý” 
 Xử lý truy vấn trong csdl phân tán (tt) 
VD1: 
Hai biểu thức tương đương trong đại số quan hệ do biến đổi chính xác 
 từ câu vấn tin trên là: 
 TênNV( Nhiệmvụ=”Quảnlý” NV.MNV=PC.MNV (NV x PC)) 
 và 
 TênNV(NV|><|MNV(Nhiệmvụ=” Quảnlý” (PC))) 
- Hiển nhiên là trong câu vấn tin thứ hai, chúng ta tránh sử dụng tích 
 Descartes, vì thế tiêu dùng ít tài nguyên máy tính hơn câu vấn tin thứ 
 nhất và vì vậy nên được giữ lại. 
- Trong các hệ phân tán, đại số quan hệ không đủ để diễn tả các chiến 
 lược thực thi. Nó phải được cung cấp thêm các phép toán trao đổi dữ 
 liệu giữa các vị trí. Bên cạnh việc chọn thứ tự cho các phép toán đại 
 số quan hệ, thể xử lý vấn tin phân tán cũng phải chọn các vị trí tốt 
 nhất để xử lý dữ liệu, và có thể cả cách biến đổi dữ liệu. 
 Xử lý truy vấn trong csdl phân tán (tt) 
VD2: 
 Thí dụ này minh họa tầm quan trọng của việc chọn lựa vị trí và cách 
 truyền dữ liệu của một câu vấn tin đại số. Chúng ta xét câu vấn tin của 
 thí dụ trên: 
 TênNV(NV|><|MNV(Nhiệmvụ=”Quảnlý”(PC))) 
chúng ta giả sử rằng các quan hệ NV và PC được phân mảnh ngang như 
 sau: 
 NV1=MNV “E3”(NV) 
 NV2=MNV > “E3”(NV) 
 PC1=MNV “E3”(PC) 
 PC2=MNV “E3”(PC) 
Các mảnh PC1, PC2, NV1, NV2 theo thứ tự được lưu tại các vị trí 1, 2, 
 3 và 4 và kết quả được lưu tại vị trí 5 
Mũi tên từ vị trí i đến vị trí j có nhãn R chỉ ra rằng quan hệ R 
được chuyển từ vị trí i đến vị trí j. Chiến lược a) sử dụng sự 
kiện là các quan hệ được phân mảnh theo cùng một cách để 
thực hiện song song các phép toán chọn và nối. Chiến lược b 
tập trung tất cả các dữ liệu tại vị trí lưu kết quả trước khi xử lý 
câu truy vấn. 
 Xử lý truy vấn trong csdl phân tán (tt) 
Sử dụng mô hình chi phí đơn giản, giả sử: 
- Thao tác truy xuất một bộ (tuple access) được ký hiệu 
là tupacc, là một đơn vị và thao tác truyền một bộ (tuple 
transfer) tuptrans là 10 đơn vị. 
- Các quan hệ NV và PC tương ứng có 400 và 1000 bộ, 
và có 20 giám đốc dự án thống nhất cho các vị trí. 
- Các quan hệ PC và NV được gom cục bộ tương ứng 
theo các thuộc tính Nhiệmvụ và MNV. Vì vậy có thể 
truy xuất trực tiếp đến các bộ của PC dựa trên giá trị của 
thuộc tính Nhiệmvụ (tương ứng là MNV cho NV) 
 Xử lý truy vấn trong csdl phân tán (tt) 
 * Tổng chi phí của chiến lược a có thể được tính như sau: 
1.Tạo ra PC’ bằng cách chọn trên PC cần (10+10)* tupacc = 20 
2. Truyền PC’ đến vị trí của NV cần (10+10)*tuptrans = 200 
3. Tạo NV’ bằng cách nối PC’ và NV’ cần (10+10)*tupacc*2 = 40 
4. Truyền NV’ đến vị trí nhận kết quả cần (10+10)*tuptrans = 200 
 Tổng chi phí 460 
 * Tổng chi phí cho chiến lược b có thể được tính như sau: 
1. Truyền NV đến vị trí 5 cần 400*tuptrans = 4.000 
2. truyền PC đến vị trí 5 cần 1000*tuptrans =10.000 
3. Tạo ra PC’ bằng cách chọn trên PC cần 1000*tupacc = 1.000 
4. Nối NVvà PC cần 400*20*tupacc = 8.000 
 Tổng chi phí là 23.000
 Xử lý truy vấn trong csdl phân tán (tt) 
 - Chỉ số đánh giá tiêu dùng tài nguyên là tổng chi phí (total 
cost) phải trả khi xử lý truy vấn. 
- Tổng chi phí là tổng thời gian cần để xử lý các phép toán 
vấn tin tại các vị trí khác nhau và truyền dữ liệu giữa các 
vị trí. 
- Một công cụ khác là thời gian đáp ứng của câu vấn tin, là 
thời gian cần thiết để chạy câu vấn tin. 
- Trong môi trường CSDL phân tán, tổng chi phí cần phải 
giảm thiểu là chi phí CPU, chi phí xuất nhập và chi phí 
truyền. 
 Xử lý truy vấn trong csdl phân tán (tt) 
 - Độ phức tạp của các phép toán quan hệ: 
 + Các phép toán chọn, Chiếu (Không loại bỏ trùng lặp) 
 có độ phức tạp là O(n); 
 + Các phép chiếu (Có loại bỏ trùng lặp), trùng lặp, nối, 
 nối nửa, chia có độ phức tạp là O(n*logn); 
 + Tích Descartes có độ phức tạp là O(n2) 
 (N biểu thị lực lượng của quan hệ nếu các bộ thu được 
 độc lập với nhau) 
Đánh giá: 
- Các thao tác có tính chọn lựa làm giảm đi lực lượng cần 
phải thực hiện trước tiên. 
- Các phép toán cần phải được sắp xếp để tránh thực hiện 
tích Descartes hoặc để lại thực hiện sau. 
 Tổng kết chương 
 - Giới thiệu về CSDL phân tán 
 - Kiến trúc cơ bản của CSDL phân tán 
 - Các đặc điểm chính của hệ phân tán 
 - Phương pháp thiết kế CSDL phân tán 
 - Phân mảnh dữ liệu và phương pháp phân mảnh 
 - Xử lý truy vấn trong CSDL phân tán và môi 
trường phân tán. 
 Chương 1: CSDL phân tán 91