Giải bài tập phân mảnh dọc môn Cơ sở dữ liệu và giải thuật | Trường đại học kinh doanh và công nghệ Hà Nội
2. Tính ma trận CA từ AAGỉ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 – A3
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). Tài liệu giúp bạn tham khảo, ôn tập và đạt kết quả cao. Mời đọc đón xem!
Môn: Cơ sở dữ liệu và giải thuật
Trường: Đại học Kinh Doanh và Công Nghệ Hà Nội
Thông tin:
Tác giả:
Tài liệu liên quan:
Preview text:
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)