Giải quyết bài toán phân mảng dọc

TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT HỒ CHÍ MINH Họ và tên: Đinh Thị Huyền SBD: 13610017 Lớp: CNTT – K3 Giải quyết bài toán phân mảng dọc Đề bài: Cho quan hệ toàn cục Project như sau: Project(PNo, Name, Location, Budget, MgrName, Duration) Xét các truy vấn: q1: Tìm thông tin tên và kinh phí các dự án: SELECT Name, Budget FROM Project q2: Xác định thông tin tên, địa điểm và thời gian thực hiện các dự án SELECT Name, Location, Duration FROM Project q3: Tìm tất cả các địa điểm dự án theo người quản lý SELECT Location FROM Project WHERE MgrName = value q4: Tìm thông tin tên, kinh phí các dự án theo thời gian thực hiện dự án SELECT Name, Budget FROM Project WHERE Duration = value S1 S2 S3 q1 2 8 0 q2 3 0 1 q3 a 10 0 q4 a 0 5 Tần số sử dụng các truy vấn qi tại các site Sj như sau: Trong đó: a – 2 số cuối của mã số sinh viên của học viên a/ Xây dựng ma trận ái lực của các thuộc tính quan hệ Project; b/ Cho biết số truy xuất đến các cặp thuộc tính cho mỗi ứng dụng tại các vị trí refi(qj) = 1. Phân đoạn dọc quan hệ Project sử dụng thuật toán năng lượng kết BEA. BÀI LÀM Project(PNo, Name, Location, Budget, MgrName, Duration) Name: A1 Location: A2 Budget: A3 MgrName: A4 Duration: A5 Ma trận Use : Ma trận tần số truy cập: A1 A2 A3 A4 A5 q1 1 0 1 0 0 q2 1 1 0 0 1 q3 0 1 0 1 0 q4 1 0 1 0 1 S1 S2 S3 q1 2 8 0 q2 3 0 1 q3 17 10 0 q4 17 0 5 Ta tính được ma trận AA: A1 A2 A3 A4 A5 A1 36 4 32 0 26 A2 4 31 0 27 4 A3 32 0 32 0 22 A4 0 27 0 27 0 A5 26 4 22 0 26 Dùng thuật toán năng lượng liên kết để tính ma trận CA: Xét ma trận AA và ma trận CA sau đây với A1, A2 đã được đặt: A1 A2 A1 36 4 A2 4 31 A3 32 0 A4 0 27 A5 26 4 Ta cần chèn thêm A3, có 3 khả năng: Chèn A3 trước A1: A3 A1 A2 A1 32 36 4 A2 0 4 31 A3 32 32 0 A4 0 0 27 A5 22 26 4 Cont (_, A3, A1) = bound(_, A3) + bound(A3,A1) – bound(_,A1) = 0 + 2748 – 0 = 2748 Chèn A3 vào giữa A1, A2: A1 A3 A2 A1 36 32 4 A2 4 0 31 A3 32 32 0 A4 0 0 27 A5 26 22 4 Cont (A1, A3, A2) = bound(A1, A3) + bound(A3,A2) – bound(A1,A2) = 2748 + 216 – 372 = 2592 Chèn A3 sau A2: A1 A2 A3 A1 36 4 32 A2 4 31 0 A3 32 0 32 A4 0 27 0 A5 26 4 22 Cont (A2, A3, _) = bound(A2, A3) + bound(A3,_) – bound(A2,_) = 0 – 0 = 216 Ta thấy khả năng thứ nhất cho kết quả lớn nhất à chọn chèn A3 vào trước A1 àMa trận CA sau khi thêm cột A3: A3 A1 A2 A1 32 36 4 A2 0 4 31 A3 32 32 0 A4 0 0 27 A5 22 26 4 Tiếp tục chèn thêm A4, có 4 khả năng: Chèn A4 trước A3: A4 A3 A1 A2 A1 0 32 36 4 A2 27 0 4 31 A3 0 32 32 0 A4 27 0 0 27 A5 0 22 26 4 Cont (_, A4, A3) = bound(_, A4) + bound(A4,A3) – bound(_,A3) = 0 + 0 + 0 = 0 Chèn A4 vào giữa A3, A1: A3 A4 A1 A2 A1 32 0 36 4 A2 0 27 4 31 A3 32 0 32 0 A4 0 27 0 27 A5 22 0 26 4 Cont (A3, A4, A1) = bound(A3, A4) + bound(A4,A1) – bound(A3,A1) = 0 + 108 – 2748 = -2640 Chèn A4 vào giữa A1, A2: A3 A1 A4 A2 A1 32 36 0 4 A2 0 4 27 31 A3 32 32 0 0 A4 0 0 27 27 A5 22 26 0 4 Cont (A1, A4, A2) = bound(A1, A4) + bound(A4,A2) – bound(A1,A2) = 108 + 1566 – 372 = 1302 Chèn A4 sau A2: A3 A1 A2 A4 A1 32 36 4 0 A2 0 4 31 27 A3 32 32 0 0 A4 0 0 27 27 A5 22 26 4 0 Cont (A2, A4, _) = bound(A2, A4) + bound(A4, _) – bound(A2, _) = 1566 + 0 – 0 = 1566 Ta thấy khả năng thứ 4 cho kết quả lớn nhất à chọn chèn A4 vào sau A2 àMa trận CA sau khi thêm cột A4: A3 A1 A2 A4 A1 32 36 4 0 A2 0 4 31 27 A3 32 32 0 0 A4 0 0 27 27 A5 22 26 4 0 Tiếp tục chèn thêm A5, có 5 khả năng: Chèn A5 trước A3: A5 A3 A1 A2 A4 A1 26 32 36 4 0 A2 4 0 4 31 27 A3 22 32 32 0 0 A4 0 0 0 27 27 A5 26 22 26 4 0 Cont (_, A5, A3) = bound(_, A5) + bound(A5, A3) – bound(_, A3) = 0 + 2108 – 0 = 2108 Chèn A5 vào giữa A3 và A1: A3 A5 A1 A2 A4 A1 32 26 36 4 0 A2 0 4 4 31 27 A3 32 22 32 0 0 A4 0 0 0 27 27 A5 22 26 26 4 0 Cont (A3, A5, A1) = bound(A3, A5) + bound(A5, A1) – bound(A3, A1) = 2108 + 2332 – 2748 = 1692 Chèn A5 vào giữa A1 và A2: A3 A1 A5 A2 A4 A1 32 36 26 4 0 A2 0 4 4 31 27 A3 32 32 22 0 0 A4 0 0 0 27 27 A5 22 26 26 4 0 Cont (A1, A5, A2) = bound(A1, A5) + bound(A5, A2) – bound(A1, A2) = 2332 + 332 – 372 = 2292 Chèn A5 vào giữa A2 và A4: A3 A1 A2 A5 A4 A1 32 36 4 26 0 A2 0 4 31 4 27 A3 32 32 0 22 0 A4 0 0 27 0 27 A5 22 26 4 26 0 Cont (A2, A5, A4) = bound(A2, A5) + bound(A5, A4) – bound(A2, A4) = 332 + 108 – 1566 = -1126 Chèn A5 sau A4: A3 A1 A2 A4 A5 A1 32 36 4 0 26 A2 0 4 31 27 4 A3 32 32 0 0 22 A4 0 0 27 27 0 A5 22 26 4 0 26 Cont (A4, A5, _) = bound(A4, A5) + bound(A5, _) – bound(A4, _) = 108 + 0 – 0 = 108 Ta thấy khả năng thứ 3 cho kết quả lớn nhất à chọn chèn A5 vào giữa A1 và A2 àMa trận CA sau khi thêm cột A5: A3 A1 A5 A2 A4 A3 32 32 22 0 0 A1 32 36 26 4 0 A5 22 26 26 4 0 A2 0 4 4 31 27 A4 0 0 0 27 27 A3 A1 A5 A2 A4 A1 32 36 26 4 0 A2 0 4 4 31 27 A3 32 32 22 0 0 A4 0 0 0 27 27 A5 22 26 26 4 0 à Tổ chức lại dòng: A3 A1 A5 A2 A4 A3 32 32 22 0 0 A1 32 36 26 4 0 A5 22 26 26 4 0 A2 0 4 4 31 27 A4 0 0 0 27 27 A3 A1 A5 A2 A4 A3 32 32 22 0 0 A1 32 36 26 4 0 A5 22 26 26 4 0 A2 0 4 4 31 27 A4 0 0 0 27 27 VF1 VF2 VF1 VF2 Access VF1 only: 0 Access VF1 only: 10 Access VF1 and VF2: 32 Access VF1 and VF2: 26 Access VF2 only: 31 Access VF2 only: 27 Sq = (0*31) – 32^2 = -1024 sq = (10*27) – 26^2 = -406 A3 A1 A5 A2 A4 A3 32 32 22 0 0 A1 32 36 26 4 0 A5 22 26 26 4 0 A2 0 4 4 31 27 A4 0 0 0 27 27 A3 A1 A5 A2 A4 A3 32 32 22 0 0 A1 32 36 26 4 0 A5 22 26 26 4 0 A2 0 4 4 31 27 A4 0 0 0 27 27 VF1 VF2 VF1 VF2 Access VF1 only: 22 Access VF1 only: 0 Access VF1 and VF2: 4 Access VF1 and VF2: 27 Access VF2 only: 27 Access VF2 only: 0 Sq = (22*27) – 4^2 = 578 sq = 0 – 27^2 = -729