Đề kiểm tra cuối học kỳ 1 Hệ quản trị cơ sở dữ liệu - Mã đề W21 - Năm học 2019 - 2020 - Trường Đại học Bách Khoa (có đáp án)

Nội dung text: Đề kiểm tra cuối học kỳ 1 Hệ quản trị cơ sở dữ liệu - Mã đề W21 - Năm học 2019 - 2020 - Trường Đại học Bách Khoa (có đáp án)

1. Câu 6. Giả sử các bản ghi trong tập tin Student được sắp thứ tự vật lý theo vùng tin khóa ID. Chỉ mục B+-tree được định nghĩa trên vùng tin ID. Chỉ mục này là dạng chỉ mục A. Thưa, không có dùng neo khối. C. Thưa, có dùng neo khối. B. Dày, có dùng neo khối. D. Dày, không có dùng neo khối. E. Ý kiến khác. Câu 7. Giả sử các bản ghi trong tập tin Student không được băm hay sắp thứ tự vật lý theo bất kỳ vùng tin nào. Chỉ mục B+-tree được định nghĩa trên vùng tin ID. Thao tác nào trên tập tin này không hiệu quả? A. Thêm mới 1 bản ghi với ID = 1234567890. C. Tìm kiếm trên chỉ mục với ID = 1234567890. B. Tìm kiếm tuần tự với ID = 1234567890. D. Cả ba thao tác trên. E. Ý kiến khác. Câu 8. Cho chỉ mục thứ cấp B-tree có số lượng con trỏ cây p ở mỗi nút là 38. Số mức (bao gồm mức gốc, root) của B-tree này là bao nhiêu khi chỉ mục cho vùng tin khóa ID không có thứ tự của tập tin dữ liệu gồm 2,000,000 bản ghi? A. 3 B. 4 C. 5 D. 6 E. Ý kiến khác. Câu 9. Sự khác biệt giữa chỉ mục cụm và chỉ mục thứ cấp trên vùng tin khóa ID của 1 tập tin là A. Chỉ mục cụm là chỉ mục thưa và chỉ mục thứ cấp là chỉ mục dày. B. Chỉ mục cụm có thể dùng neo khối, nhưng chỉ mục thứ cấp không thể dùng neo khối. C. Không gian lưu trữ của chỉ mục cụm nhỏ hơn so với không gian lưu trữ của chỉ mục thứ cấp. D. Câu A, B, và C đều đúng. E. Ý kiến khác. Câu 10. Dạng biểu diễn bên trong nào mà các DBMS thường dùng khi xử lý và tối ưu hóa truy vấn SQL? A. Cây truy vấn. C. Biểu thức đại số quan hệ. B. Đồ thị truy vấn. D. Câu lệnh SELECT của ngôn ngữ SQL. E. Ý kiến khác. Câu 11. Sắp thứ tự ngoại không được dùng trong việc xử lý cho phép toán nào sau đây? A. Kết 2 tập tin dữ liệu với phương pháp sắp thứ tự-trộn (sort-merge join). B. Trả về kết quả khi câu lệnh có mệnh đề “ORDER BY”. C. Chọn các bản ghi của tập tin dữ liệu với điều kiện “>”. D. Hợp 2 tập tin dữ liệu. E. Ý kiến khác. Câu 12. Cho tập tin Customer có vùng tin khóa ID là vùng tin được dùng sắp thứ tự cho các bản ghi, có chỉ mục sơ cấp B+-tree trên vùng tin này. Phép chọn ID>1000(Customer) có thể được xử lý theo các phương pháp nào sau đây? A. Tìm kiếm tuần tự. B. Tìm kiếm nhị phân. C. Tìm kiếm qua chỉ mục B+-tree. D. Cả ba phương pháp trên. E. Ý kiến khác. Câu 13. Chi phí tính toán cần được xem xét khi tối ưu hóa dựa trên chi phí cho loại cơ sở dữ liệu nào? A. Cơ sở dữ liệu nhỏ. C. Cơ sở dữ liệu phân tán. B. Cơ sở dữ liệu lớn. D. Cả ba trường hợp trên. E. Ý kiến khác. Mã đề: W21 2
2. Câu 20. Cho nội dung điều khiển tương tranh của lịch biểu sau với kỹ thuật dựa trên thứ tự nhãn thời gian đa phiên bản (multiversion timestamp ordering). Tác vụ ghi của giao tác T1 sẽ được xử lý như thế nào? T1 T2 T3 X A. Từ chối vì không đảm bảo thứ tự cho các tác vụ read_TS=0 TS(T1) = 50 TS(T2) = 65 TS(T3) = 45 xung đột giữa T1 và T2. write_TS=0 B. Tạo phiên bản mới cho X với read_TS = 50 và r1(X) write_TS = 50. r (X) 2 C. Từ chối vì không đảm bảo thứ tự cho các tác vụ w (X) 2 xung đột giữa T1 và T3. r3(X) D. Chưa đủ thông tin mô tả để xác định cách xử lý w1(X) cho tác vụ ghi của giao tác T1. E. Ý kiến khác. Câu 21. Cho nội dung điều khiển tương tranh của lịch biểu sau dựa trên thứ tự nhãn thời gian (timestamp ordering). Điền giá trị nhãn thời gian đọc (read_TS) và nhãn thời gian ghi (write_TS) cho Y? T1 T2 T3 Y read_TS = 0 TS (T1) = 48 TS(T2) = 55 TS(T3) = 22 write_TS = 0 read_TS = 48 r (Y) 1 write_TS = 0 read_TS = 55 r (Y) 2 write_TS = 0 read_TS = 55 r (Y) 3 write_TS = 0 read_TS = w (Y) 2 write_TS = read_TS = w (Y) 3 write_TS = A. Y có read_TS = 55 và write_TS = 0 sau khi T2 thực hiện w2(Y) vì w2(Y) bị từ chối và T2 bị quay lui với TS mới. Y có read_TS = 55 và write_TS = 22 sau khi T3 thực hiện w3(Y). B. Không đủ thông tin để xác định read_TS và write_TS cho Y. C. Y có read_TS = 55 và write_TS = 55 sau khi T2 thực hiện w2(Y). Các giá trị này không đổi sau khi T3 thực hiện w3(Y) vì w3(Y) bị từ chối và T3 bị quay lui với TS mới. D. Y có read_TS = 55 và write_TS = 55 sau khi T2 thực hiện w2(Y). Y có read_TS = 22 và write_TS = 22 sau khi T3 thực hiện w3(Y). E. Ý kiến khác. Câu 22. Giao thức ghi nhật ký trước (Write-Ahead Logging) đảm bảo phục hồi cho A. các giao tác đã commit với các nội dung AFIM và các giao tác chưa commit với các nội dung BFIM trong các kỹ thuật phục hồi tại chỗ. B. các giao tác đã commit với các nội dung AFIM và các giao tác chưa commit với các nội dung BFIM trong tất cả các kỹ thuật phục hồi. C. các giao tác đã commit với các nội dung BFIM và các giao tác chưa commit với các nội dung AFIM trong các kỹ thuật phục hồi tại chỗ. D. các giao tác đã commit với các nội dung BFIM và các giao tác chưa commit với các nội dung AFIM trong tất cả các kỹ thuật phục hồi. E. Ý kiến khác. Mã đề: W21 4
3. Hệ số phân khối của kết quả kết đầy đủ giữa Student và Major là 2 với cách phân khối không phủ. 25.1. Mô tả đặc điểm lưu trữ vật lý của mỗi tập tin dữ liệu: Student, Major. (0.5 điểm) 25.2. Cho cây truy vấn sau dùng để lấy ra mã số sinh viên, họ, và tên của những sinh viên có quê quán ở thành phố Hồ Chí Minh, mới nhập học vào năm 2017 ở khoa Khoa Học và Kỹ Thuật Máy Tính. Vẽ cây truy vấn tương đương cây truy vấn đã cho. (0.5 điểm) 25.3. Cho các phương pháp xử lý cho phép toán chọn sau đây: Phương pháp 1: Tìm kiếm tuần tự Phương pháp 2: Tìm kiếm nhị phân Phương pháp 3: Tìm kiếm dựa trên chỉ mục Sử dụng phương pháp tối ưu hóa truy vấn dựa trên chi phí, chi phí của mỗi phương pháp là bao nhiêu cho phép chọn đã chọn? Phương pháp nào nên được chọn? (1.25 điểm) Phép chọn: (Student) 25.4. Giả sử thực hiện phép kết Student ⨝MCode = Code Major bằng tối ưu hóa dựa trên chi phí. Xác định chi phí của mỗi phương pháp sau cho phép kết. Phương pháp nào nên được chọn để xử lý phép kết cho câu truy vấn? (0.75 điểm) Phương pháp 4: Kết với 1 vòng lặp (single loop) Phương pháp 5: Kết với băm (hash join). Giả sử tập tin dữ liệu Major là tập tin nhỏ, có thể được băm và lưu trong vùng đệm. Câu 26. Cho lịch biểu S trong bảng sau. 26.1. Giả sử phần này bỏ qua các thông tin về commit, checkpoint, sự cố làm hệ thống ngưng thực thi. Lịch biểu S được viết lại là: S: r1(A); r3(A); r2(B); r1(B); w2(B); r3(B); w3(A); w1(B) Lịch biểu này có khả tuần tự hóa (serializable) không tính đến thời điểm trước 11g30? Nếu có thì lịch biểu tuần tự tương đương là gì? Nếu không thì tại sao? (0.5 điểm) Thời gian T1 T2 T3 26.2. Giả sử lịch biểu S được điều khiển tương 10g00 r1(A) tranh bằng kỹ thuật khóa hai pha với khóa chia sẻ 10g05 r3(A) (shared, read) và khóa loại trừ (exclusive, write). 10g10 r2(B) Trình bày trình tự thực hiện các thao tác khóa và mở khóa tương ứng cho S. Khóa chết có xảy ra 10g15 r1(B) không? Vì sao? Nếu khóa chết xảy ra thì trình bày 10g20 w (B, 5, 10) 2 cách giải quyết để các giao tác có thể hoàn thành 10g30 r3(B) tất cả các tác vụ trên trước 11g30. (1.25 điểm) 10g35 commit 26.3. Trình bày nội dung sổ ghi nhật ký trước 10g40 [checkpoint] 11g30. (0.5 điểm) 11g00 w3(A, 3, 9) 26.4. Giả sử hệ thống thực hiện checkpoint lúc 11g10 w1(B, 5, 18) 10g40 và tiếp theo gặp sự cố lúc 11g30. Mô tả quá 11g30 - sự cố làm hệ thống ngưng thực thi - trình phục hồi cho các giao tác nếu kỹ thuật cập nhật trì hoãn được sử dụng. (0.75 điểm) (Cán bộ coi thi không giải thích gì thêm.) Mã đề: W21 6
4. Họ - Tên: Mã Số Sinh Viên: . Mã đề: W21 PHẦN TRẢ LỜI I. Phần trắc nghiệm: Câu 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 A √ √ √ √ √ √ B √ √ √ √ √ √ √ C √ √ √ √ √ √ D √ √ √ √ √ E II. Phần tự luận: Câu 25.1. Student là tập tin có thứ tự với các bản ghi được sắp thứ tự theo giá trị của vùng tin MCode. Major là tập tin không có thứ tự. Câu 25.2. Cây truy vấn tương đương. Câu 25.3. Xử lý và tối ưu hóa dựa trên chi phí cho phép chọn. Môn: Hệ Quản Trị Cơ Sở Dữ Liệu (CO3021) Học kỳ 1 - 2019-2020 Ngày: 27/12/2019 8
5. Họ - Tên: Mã Số Sinh Viên: . Mã đề: W21 Deadlock xảy ra khi T1 thực hiện w1(B, 5, 18). Khi này, T1 đợi T2 và T3 để có được khóa write_lock(B). Trước đó, T2 đợi T1 để có được khóa write_lock(B) và T3 đợi T1 để có được khóa write_lock(A). Giải quyết bằng cách ngưng thực thi và quay lui T1, tiếp tục thực hiện T2 và T3, T1 được khởi động lại. Đồ thị đợi Câu 26.3. Nội dung sổ ghi nhật ký Môn: Hệ Quản Trị Cơ Sở Dữ Liệu (CO3021) Học kỳ 1 - 2019-2020 Ngày: 27/12/2019 10