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

Chia sẻ: đinh Thị Huyền | Ngày: | Loại File: DOC | Số trang:10

Thêm vào BST

Báo xấu

66
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài thi: Giải quyết bài toán phân mảng dọc dưới đây giới thiệu tới các bạn một bài thi mẫu về môn học Phân mảng dọc, đây là một trong những kiến thức cơ bản mà các bạn chuyên ngành Công nghệ thông tin cần nắm. Mời các bạn tham khảo tài liệu để bổ sung thêm cho mình tư liệu về việc giải một bài toán phân mảng.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài thi: 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 Tần số sử dụng các truy vấn qi tại các site Sj như sau: S1 S2 S3 Trong đó: a – 2 số cuối của mã số sinh viên của học viên q1 2 8 0 a/ Xây dựng ma trận ái lực của các thuộc tính quan hệ Project; q2 3 0 1 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ử q3 a 10 0 dụng thuật toán năng lượng kết BEA. q4 a 0 5
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 S1 S2 S3 q1 1 0 1 0 0 q1 2 8 0 q2 1 1 0 0 1 q2 3 0 1 q3 0 1 0 1 0 q3 17 10 0 q4 1 0 1 0 1 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: 1. Chèn A3 trước A1: A3 A1 A2 Cont (_, A3, A1) = A1 32 36 4 bound(_, A3) + bound(A3,A1) – bound(_,A1) = A2 0 4 31 0 + 2748 – 0 = 2748 A3 32 32 0 A4 0 0 27 A5 22 26 4 2. Chèn A3 vào giữa A1, A2: A1 A3 A2 Cont (A1, A3, A2) = A1 36 32 4 bound(A1, A3) + bound(A3,A2) – bound(A1,A2) = A2 4 0 31 2748 + 216 – 372 = 2592 A3 32 32 0 A4 0 0 27 A5 26 22 4
3. Chèn A3 sau A2: A1 A2 A3 Cont (A2, A3, _) = A1 36 4 32 bound(A2, A3) + bound(A3,_) – bound(A2,_) = A2 4 31 0 216 0 – 0 = 216 A3 32 0 32 A4 0 27 0 A5 26 4 22 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: 1. Chèn A4 trước A3: A4 A3 A1 A2 Cont (_, A4, A3) = A1 0 32 36 4 bound(_, A4) + bound(A4,A3) – bound(_,A3) = A2 27 0 4 31 0 + 0 + 0 = 0 A3 0 32 32 0 A4 27 0 0 27 A5 0 22 26 4
2. Chèn A4 vào giữa A3, A1: A3 A4 A1 A2 Cont (A3, A4, A1) = A1 32 0 36 4 bound(A3, A4) + bound(A4,A1) – bound(A3,A1) = A2 0 27 4 31 0 + 108 – 2748 = 2640 A3 32 0 32 0 A4 0 27 0 27 A5 22 0 26 4 3. Chèn A4 vào giữa A1, A2: A3 A1 A4 A2 Cont (A1, A4, A2) = A1 32 36 0 4 bound(A1, A4) + bound(A4,A2) – bound(A1,A2) = A2 0 4 27 31 108 + 1566 – 372 = 1302 A3 32 32 0 0 A4 0 0 27 27 A5 22 26 0 4 4. Chèn A4 sau A2: A3 A1 A2 A4 Cont (A2, A4, _) = A1 32 36 4 0 bound(A2, A4) + bound(A4, _) – bound(A2, _) = A2 0 4 31 27 1566 + 0 – 0 = 1566 A3 32 32 0 0 A4 0 0 27 27 A5 22 26 4 0
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: 1. Chèn A5 trước A3: A5 A3 A1 A2 A4 Cont (_, A5, A3) = A1 26 32 36 4 0 bound(_, A5) + bound(A5, A3) – bound(_, A3) = A2 4 0 4 31 27 0 + 2108 – 0 = 2108 A3 22 32 32 0 0 A4 0 0 0 27 27 A5 26 22 26 4 0 A3 A5 A1 A2 A4 A1 32 26 36 4 0 2. Chèn A5 vào giữa A3 và A1: A2 0 4 4 31 27 Cont (A3, A5, A1) = A3 32 22 32 0 0 bound(A3, A5) + bound(A5, A1) – bound(A3, A1) = A4 0 0 0 27 27 A5 22 26 26 4 0
2108 + 2332 – 2748 = 1692 3. Chèn A5 vào giữa A1 và A2: A3 A1 A5 A2 A4 Cont (A1, A5, A2) = A1 32 36 26 4 0 bound(A1, A5) + bound(A5, A2) – bound(A1, A2) = A2 0 4 4 31 27 2332 + 332 – 372 = 2292 A3 32 32 22 0 0 A4 0 0 0 27 27 A5 22 26 26 4 0 4. Chèn A5 vào giữa A2 và A4: A3 A1 A2 A5 A4 Cont (A2, A5, A4) = A1 32 36 4 26 0 bound(A2, A5) + bound(A5, A4) – bound(A2, A4) = A2 0 4 31 4 27 332 + 108 – 1566 = 1126 A3 32 32 0 22 0 A4 0 0 27 0 27 A5 22 26 4 26 0 A3 A1 A2 A4 A5 5. Chèn A5 sau A4: A1 32 36 4 0 26 Cont (A4, A5, _) = bound(A4, A5) + bound(A5, _) – bound(A4, _) = A2 0 4 31 27 4 108 + 0 – 0 = 108 A3 32 32 0 0 22 A4 0 0 27 27 0 A5 22 26 4 0 26
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 A1 A5 A2 A4 A1 32 36 26 4 0 A3 32 32 22 0 0 A2 0 4 4 31 27  Tổ chức A1 32 36 26 4 0 lại dòng: A3 32 32 22 0 0 A5 22 26 26 4 0 A4 0 0 0 27 27 A2 0 4 4 31 27 A5 22 26 26 4 0 A4 0 0 0 27 27 A3 A1 A5 A2 A4 A3 A1 A5 A2 A4 A3 32 32 22 0 0 A3 32 32 22 0 0 A1 32 36 26 4 0 A1 32 36 26 4 0 A5 22 26 26 4 0 A5 22 26 26 4 0 A2 0 4 4 31 27 A2 0 4 4 31 27 A4 0 0 0 27 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 A1 A5 A2 A4 A3 32 32 22 0 0 A3 32 32 22 0 0 A1 32 36 26 4 0 A1 32 36 26 4 0 A5 22 26 26 4 0 A5 22 26 26 4 0 A2 0 4 4 31 27 A2 0 4 4 31 27 A4 0 0 0 27 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