lOMoAR cPSD| 48704538
GIẢI BÀI TẬP PHÂN MẢNH DỌC
Dùng thuật toán BEA và VF để phân mảnh dọc quan hệ RA như sau:
q = { q1 , q2 , q3 , q4} A = { A1 , A2 , A3 , A4} S = { S1 , S2 , S3} Cho : - Use (qi , Aj)
với thuộc A1 là khóa A1 A2 A3 A4 q1 0 1 1 0 q2 1 1 1 0 q3 1 0 0 1 q4 0 0 1 0 - Access frenquency S1 S2 S3 q1 10 20 0 q2 5 0 10 q3 0 35 5 q4 0 10 0
1) Tính ma trận AA ?
2) Từ AA tính ma trận CA ?
3) Dùng VF tìm điểm chia dọc theo CA ? Câu 1 : Tính AA
Trước tiên tính độ đo ái lực aff(Ai , Aj) = ∑ all queries that access Ai and Aj (query access) aff(A2 , A3) = 45 aff( A2 , A4) = 0 aff(A3 , A4) = 0 aff(A3, A3) = 55 aff(A2, A3, A4)= A2 A3 A4 A2 45 45 0 A3 45 55 0 A4 0 0 40
2 . Tính ma trận CA từ AA
Gỉa sử ma trận CA đã bố trí 2 cột đầu tiên là A2, A3, chèn A4 vào ma trận. Chiến lược 1: Chèn A4 trước A2, A3 :A4 – A2 – A3 Chiến lược 2: Chèn A4 giữa A2, A3 : A2 – A4 – A 3 Chiến lược 3:
Chèn A4 sau A2, A3:A2 – A3 – A4
- Cont(_ , A4 , A2) = 2bond(A0,A4) + 2bond(A4,A2) - 2bond(_,A2) =
2bond(A4,A2) = 0 (2 * (45*0 + 45*0 + 0*40) lOMoAR cPSD| 48704538
- Cont(A2 , A4 , A3) = 2bond(A2,A4) + 2bond(A4,A3) - 2bond(A2,A3) = -9000
- Cont(A3 , A4 , _) = 2bond(A3,A4) + 2bond(_ ,A4) - 2bond(A3, _) = 2bond(A3,A4) = 0
Vậy ta có 2 cách bố trí ma trận: Cont(A3 , A4 , _) Cont(_ , A4 , A2)
Chọn 1 trong 2 cách ta có ma trận CA = A2 A3 A4 A2 45 45 0 A3 45 55 0 A4 0 0 40
Câu 3 : VF ( tìm điểm neo trên đường chéo) ?
Tập các ứng dụng chỉ truy cập TA :
TQ = {qi | AQ(qi) ⊆ TA} Tập
các ứng dụng chỉ truy cập BA : BQ = {qi | AQ(qi) ⊆ BA}
Tập các ứng dụng vừa truy cập TA và BA : OQ = {qi |Q\TQ ∪ BQ} với
AQ (qi ) = { AJ | use(qi , AJ =1)
Tổng số các truy cập đến các thuộc tính bởi ứng dụng truy cập cả TA và BA:
Tổng số các truy cập đến các thuộc tính bởi ứng dụng chỉ truy cập TA
Tổng số các truy cập đến các thuộc tính bởi ứng dụng chỉ truy cập BA
- B0: chọn điểm chia
- B1: tính TA, BA (bỏ thuộc tính khóa) - B2: tính TQ, BQ và OQ. Cụ thể:
TQ: dựa vào TA và ma trận use
BQ: dựa vào BA và ma trận use OQ = Q – { TQ ∪ BQ } lOMoAR cPSD| 48704538
- B3: tính CTQ, CBQ và COQ (dựa vào TQ, BQ, OQ vừa tìm được và ma trận acc) -
B4: tính (CTQ * CBQ - COQ2)
Lặp lại B0 cho tới khi hết điểm chia
Cuối cùng, chọn 1 điểm chia sao cho giá trị (CTQ * CBQ - COQ2) là lớn nhất
Trong bài này ta có 2 điểm chia tại A2 và A3:
Xét phương án 1: Điểm chia A2 TA = {A2} BA = { A3,A 4} TQ
= Φ ( do không có query nào chỉ truy cập trên A 2) BQ
= { q3, q4 } ( do q3 chỉ truy cập A4, q4 chỉ truy cập A3) OQ
= Q – { TQ ∪ BQ } = {q1, q2} Do TQ = Φ nên CTQ = 0
CBQ = 50 (= tổng q3 và q4 trên ma trận acc )
COQ = 45 (= tổng q1 và q2 trên ma trận acc )
 CTQ*CBQ – COQ2 = 0 * 50 - 452 = -2025 Xét
phương án 2: Điểm chia A3 (tính tương tự) TA = { A2, A 3} BA = { A 4} CTQ*CBQ – COQ2 = - 1625
 Chọn điểm chia tại A3
Vậy ta chọn phương án 2 với 2 phân mảnh dọc {A1, A2, A3} và {A1, A4} (do A1 là khóa,
ta bổ sung vào kết quả cuối cùng)