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

1. Câu 6. 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. 6 B. 5 C. 4 D. 3 E. Ý kiến khác. Câu 7. 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 8. 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 9. 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 10. 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 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. Chọn các bản ghi của tập tin dữ liệu với điều kiện “>”. B. Kết 2 tập tin dữ liệu với phương pháp sắp thứ tự-trộn (sort-merge join). C. Trả về kết quả khi câu lệnh có mệnh đề “ORDER BY”. D. Hợp 2 tập tin dữ liệu. E. Ý kiến khác. Câu 12. 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. Đồ thị truy vấn. C. Biểu thức đại số quan hệ. B. Cây truy vấn. D. Câu lệnh SELECT của ngôn ngữ SQL. 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 lớn. C. Cơ sở dữ liệu nhỏ. B. Cơ sở dữ liệu phân tán. D. Cả ba trường hợp trên. E. Ý kiến khác. 2
2. E. Ý kiến khác. Câu 20. 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. Không đủ thông tin để xác định read_TS và write_TS cho Y. B. 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). 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 21. 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. Chưa đủ thông tin mô tả để xác định cách xử lý read_TS=0 TS(T1) = 50 TS(T2) = 65 TS(T3) = 45 cho tác vụ ghi của giao tác T1. 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. Từ chối vì không đảm bảo thứ tự cho các tác vụ w1(X) xung đột giữa T1 và T2. E. Ý kiến khác. Câu 22. Cho hiện trạng của hệ thống ngay khi hệ thống gặp sự cố lúc 9g00. Giả sử kỹ thuật cập nhật tức thời với dạng UNDO/NO-REDO được dùng để phục hồi hệ thống. Xác định phục hồi cho mỗi giao tác. Mã đề: W31 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 ở Huế, mới nhập học vào năm 2018 ở 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(Z); r3(Z); r2(Y); r1(Y); w2(Y); r3(Y); w3(Z); w1(Y) 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 9g30? 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 8g00 r1(Z) tranh bằng kỹ thuật khóa hai pha với khóa chia sẻ 8g05 r3(Z) (shared, read) và khóa loại trừ (exclusive, write). 8g10 r2(Y) 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 8g15 r1(Y) không? Vì sao? Nếu khóa chết xảy ra thì trình bày 8g20 w (Y, 5, 10) 2 cách giải quyết để các giao tác có thể hoàn thành 8g30 r3(Y) tất cả các tác vụ trên trước 9g30. (1.25 điểm) 8g35 commit 26.3. Trình bày nội dung sổ ghi nhật ký trước 8g40 [checkpoint] 8g30. (0.5 điểm) 9g00 w3(Z, 3, 9) 26.4. Giả sử hệ thống thực hiện checkpoint lúc 9g10 w1(Y, 5, 18) 8g40 và tiếp theo gặp sự cố lúc 9g30. Mô tả quá 9g30 - 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ã đề: W31 6
4. Họ - Tên: Mã Số Sinh Viên: . Mã đề: W31 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ã đề: W31 Deadlock xảy ra khi T1 thực hiện w1(Y, 5, 18). Khi này, T1 đợi T2 và T3 để có được khóa write_lock(Y). Trước đó, T2 đợi T1 để có được khóa write_lock(Y) và T3 đợi T1 để có được khóa write_lock(Z). 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