Bài tập Hệ quản trị CSDL

Nội dung text: Bài tập Hệ quản trị CSDL

1. Bài tập Hệ quản trị CSDL A LỊCH BIỂU KHẢ TUẦN TỰ 1. Kiểm tra tính khả tuần tự của các lịch biểu sau. Nếu lịch biểu là khả tuần tự, hãy cho biết lịch tuần tự tương đương: Chú ý: oi(X) cho biết thao tác o của giao tác Ti trên đơn vị dữ liệu X. o có thể là read (r), write (w), read lock (rl), wl (write lock), un (unlock) a. S1: r2(Z); r2(Y); w2(Y); r3(Y); r3(Z); r1(X); w1(X); w3(Y); w3(Z); r2(X); r1(Y); w1(Y); w2(X) b. S2: r3(Y); r3(Z); r1(X); w1(X); w3(Y); w3(Z); r2(Z); r1(Y); w1(Y); r2(Y); w2(Y); r2(X); w2(X) c. S3: wl3(A); wl4(B); un3(A); rl1(A); un4(B); wl3(B); rl2(A); un3(B); rl1(B); un2(A); un1(A); wl4(A); un1(B); rl2(B); un4(A); un2(B). d. S4: rl1(A); un1(A); wl3(A); rl2(B); un3(A); rl4(A); un2(B); wl5(B); un4(A); wl2(A); wl1(C); un1(C); rl2(C); rl3(C); un5(B); wl4(B); un2(C); un3(C); un2(A); un4(B); wl5(C); un5(C) 2. Cho các lịch biểu sau: S5: r1(X);r2(Z);r1(Z);r3(X);r3(Y);w1(X);c1;w3(Y);c3;r2(Y);w2(Z);w2(Y);c2; S6: r1(X);r2(Z);r1(Z);r3(X);r3(Y);w1(X);w3(Y);r2(Y);w2(Z);w2(Y);c1;c2;c3; S7:r1(X);r2(Z);r3(X);r1(Z);r2(Y);r3(Y);w1(X);c1;w2(Z);w3(Y);w2(Y);c3;c2; Đối với từng lịch biểu có không rollback dây chuyền không, có thể phục hồi không? B ĐIỀU KHIỂN ĐỒNG THỜI DÙNG KỸ THUẬT KHÓA 1. Cho cấu trúc phân cấp các hạt dữ liệu sau: A B C D E F G Và cho 3 giao tác: T1: Đọc A, Ghi B, Đọc C, Ghi E
2. T2: Đọc C, Ghi F T3: Đọc B, Đọc E a. Đặt các khóa phù hợp với kỹ thuật lập lịch khả tuần tự theo cơ chế khóa 2 pha, nếu HQT CSDL hỗ trợ 2 phương thức khóa là Slock và Xlock. b. Đặt các khóa phù hợp với nghi thức khóa phân cấp, GT chỉ nhả khóa khi không cần thiết giữ khóa nữa và HQT CSDL hỗ trợ phương thức khóa đơn giản là Lock. c. Lập lịch theo kỹ thuật xác nhận hợp lệ sao cho không có GT nào bị rollback. 2. Cho các lịch biểu sau: S1: r1(A), r2(B), r3(C), w1(B), w2(C), w3(D) S2: r1(A), r2(B), r3(C), r1(B), r2(C), r3(D), w1(C), w2(D), w3(E) S3: r1(A), r2(B), r3(C), r1(B), r2(C), r3(D), w1(A), w2(B), w3(C) Đối với từng lịch biểu a. Đặt các khóa phù hợp với bộ lập lịch hỗ trợ shared lock và exclusive lock: đặt shared lock ngay trước thao tác đọc (nhưng sau đó không có thao tác ghi trên cùng đvdl bởi cùng giao tác), đặt exclusive lock ngay trước những thao tác đọc khác và thao tác ghi. Đặt unlock vào cuối giao tác. Cho biết quá trình thực hiện của lịch biểu. b. Đặt shared lock và exclusive lock cho phép khóa tăng cấp (upgrading), unlock vào cuối giao tác. Cho biết quá trình thực hiện lịch biểu nếu bộ lập lịch hỗ trợ shared lock, exclusive lock và upgrading. c. Đặt shared lock, exclusive lock, update lock và unlock: shared lock trước mỗi thao tác đọc không có tăng cấp, đặt update lock trước mỗi thao tác đọc có tăng cấp, đặt exclusive lock trước mỗi thao tác ghi. Đặt unlock ở cuối mỗi giao tác. Cho biết quá trình thực hiện lịch biểu nếu bộ lập lịch hỗ trợ shared lock, exclusive lock và update lock. 3. Đối với từng lịch biểu sau, đặt các khóa phù hợp (read, write, increment) trước từng thao tác và unlock ở cuối giao tác. Cho biết quá trình thực hiện lịch biểu nếu bộ lập lịch hỗ trợ 3 loại khóa này. a. r1(A); r2(B); inc1(B); inc2C; w1(C); w2(D) b. r1(A); r2(B); inc1(B); inc2(A); w1(C); w2(D) 4. Cho 4 giao tác sau: T1: l1(A); r1(A); l1(B); w1(B); u1(A); u1(B) 2
3. T2: l2(C); r2(C); l2(A); w2(A); u2(C); u2(A) T3: l3(B); r3(B); l3(C); w3(C); u3(B); u3(C) T4: l4(D); r4(D); l4(A); w4(A); u4(D); u4(A) a. Giả sử lịch biểu như sau; hãy cho biết quá trình thực hiện lịch biểu. Dùng đồ thị chờ để kiểm tra deadlock: T1 T2 T3 T4 l1(A); r1(A); l2(C); r2(C); l3(B); r3(B); l4(D); r4(D); l2(A); l3(C); l4(A); l1(B); b. Giả sử dùng phương pháp lock các đơn vị dữ liệu theo thứ tự alphabet của đvdl để ngăn ngừa deadlock. c. Cho biết quá trình thực hiện một lịch biểu gồm 4 giao tác dùng phương pháp dò tìm deadlock theo thuật toán Wait-Die, giả sử khi giao tác rollback, GT không bắt đầu lại trước khi giao tác khác kết thúc. d. Tương tự như câu c. nhưng theo thuật toán Wound-wait. 5. Cho cấu trúc CSDL sau: TAIKHOAN (MATK, SODU, SODUCO, SODUNO, MAKH) KHACHANG (MAKH, TENKH, ĐCKH, ĐTKH) GIAODICH (MAGD, NGAYGD, TKNO, TKCO, SOTIEN) 3
4. Trong đó, SODU cho biết giá trị của tài khỏan, được tính từ SODUCO và SODUNO. Mỗi khi có một giao dịch diễn ra(gửi hoặc rút hoặc chuyển tiền) thì sẽ có 1 dòng dữ liệu được thêm vào bảng GIAODICH. TKNO hoặc TKCO có thể mang giá trị NULL. a. Hãy viết (bằng mã giả) các giao tác sau: i) Gửi tiền ii) Rút tiền iii) Chuyển tiền b. Hãy chọn đơn vị dữ liệu và thiết lập phương thức khóa trên đó cho hợp lý để cho mọi giao dịch, gồm 3 giao dịch chủ yếu trên và các giao dịch thống kê có thể xảy ra đồng thời mà vẫn đảm bảo tính đúng đắn trên CSDL và hệ thống họat động không trì trệ. C ĐIỀU KHIỂN ĐỒNG THỜI DÙNG KỸ THUẬT NHÃN THỜI GIAN 1. Cho lịch biểu S: r2(A), r3(A), w2(B), w3(A), r1(B), r4(B), r1(A), w1(C), w4(A) a. Hãy xét tính khả tuần tự của lịch biểu với: i. A, B, C lưu trên 3 đvdl khác nhau. ii. B, C lưu trên cùng đvdl, A trên đvdl khác. b. Dùng kỹ thuật đkđt dùng nhãn thời gian với nhãn thời gian của 4 GT lần lượt là 300, 310, 320 và 330. c. Dùng kỹ thuật đkđt dùng nhãn thời gian với nhãn thời gian của 4 GT lần lượt là 250, 200, 210 và 275. 2. Cho lịch biểu sau: S1: r1(B), r2(A), r3(C), w1(B), w1(A), w2(C), w3(A) S2: r1(A), w1(A), r2(A), w2(A), r3(A), r4(A) a. Hãy cho biết quá trình thực hiện S1 với bộ lập lịch dùng kỹ thuật điều khiển đồng thời dựa trên nhãn thời gian, biết rằng TS(T1) = 200, TS(T2) = 150, TS(T3) = 175 b. Hãy cho biết quá trình thực hiện S2 với bộ lập lịch dùng kỹ thuật điều khiển đồng thời dựa trên nhãn thời gian, biết rằng TS(T1) = 150, TS(T2) = 200, TS(T3) = 175, TS(T4) = 225 c. Hãy thực hiện lịch biểu S2 với nhãn thời gian các GT như b. nhưng bộ lập lịch cùng kỹ thuật điều khiển đồng thời đa phiên bản. 4
5. 3. Cho các lịch biểu sau, cho biết quá trình thực hiện lịch biểu, biết rằng bộ lập lịch cùng kỹ thuật điều khiển đồng thời dựa trên nhãn thời gian và nhãn thời gian sẽ được gán theo thứ tự giao tác bắt đầu. a. st1, st2, r1(A), r2(B), w2(A), w1(B) b. st1, r1(A), st2, w2(B), r2(A), w1(B) c. st1, st2, st3, r1(A), r2(B), w1(C), r3(B), r3(C), w2(B), w3(A) 4. Cho biết quá trình thực hiện lịch biểu nếu bộ lập lịch điều khiển đồng thời dùng kỹ thuật nhãn thời gian đa phiên bản: a. st1, st2, st3, st4, w1(A), w2(A), w3(A), r2(A), r4(A) b. st1, st2, st3, st4, w1(A), w3(A), r4(A), r2(A) Nếu bộ lập lịch không hỗ trợ đa phiên bản thì quá trình thực hiện lịch biểu ra sao? D ĐIỀU KHIỂN ĐỒNG THỜI DÙNG KỸ THUẬT XÁC NHẬN HỢP LỆ Biết rằng: Ri(X): giao tác Ti bắt đầu, read set là X. Vi: Ti validate. Wi(X): Ti finish và write set là X. Cho biết quá trình thực hiện của từng chuỗi thao tác sau nếu lịch biểu dùng kỹ thuật xác nhận tính hợp lệ: d. R1(A,B); R2(B,C);V1;R3(C,D);V3;W1(A);V2;W2(A);W3(B); e. R1(A,B); R2(B,C);V1;R3(C,D);V3;W1(A);V2;W2(A);W3(D); f. R1(A,B); R2(B,C);V1;R3(C,D);V3;W1(C);V2;W2(A);W3(D); 5