- Các khái niệm Các vấn đề bất thường trong truy xuất đồng thời Lịch thao tác (Schedule. - Kỹ thuật khóa Kỹ thuật nhãn thời gian Các kỹ thuật khác Truy xuất đồng thời (Access Concurrency. - Giao tác (Transaction. - Đơn vị dữ liệu (Granule. - Các truy xuất dữ liệu của CSDL xảy ra cùng thời gian trong môi trường nhiều người dùng (multi user. - Truy xuất đồng thời không tranh chấp. - n truy xuất trên n dữ liệu khác nhau Truy xuất đồng thời có tranh chấp. - n truy xuât đồng thời trên k dữ liệu chung. - Là một dãy các thao tác (actions) trên dữ liệu được coi như là một đơn vị xử lý nguyên tố (processing unit. - Các xử lý bên trong một giao tác phải hoàn thành tất cả hoặc thất bại tất cả. - Khi một giao tác được thực hiện hoàn tất thì nó phải đảm bảo tính nhất quán của CSDL (biến CSDL thành một trạng thái nhất quán mới. - Một giao tác là một đơn vị xử lý nguyên tố không chia nhỏ được Nhất quán (Consistency. - Biến cơ sở dữ liệu từ trạng thái nhất quán này đến trạng thái nhất quán khác Cô lập (Isolation. - Không bị ánh hưởng bởi các giao tác khác Bền vững (Durability. - Các thay đổi mà giao tác thực hiện trên dữ liệu của CSDL phải được phản ánh bền vững lên CSDL Active giai đoạn đầu tiên khi giao tác bắt đầu thực thi Partially committed sau khi lệnh cuối cùng trong giao tác thi hành. - Failed sau khi phát hiện không thể thực hiện bình thường được. - Aborted sau khi giao tác bị rolled back và CSDL phục hồi lại trạng thái trước của nó. - Hai lựa chọn khi một giao tác bị abort. - Khởi động lại giao tác ◦ Hủy giao tác Committed Partially Committed ◦ Sau khi thực hiện thành công. - Sau khi thực hiện câu lệnh SQL thì CSDL vẫn giữ nguyên được trạng thái nhất quán Không có sự thay đổi nào xảy ra trên CSDL. - BEGIN Bắt đầu giao tác TRANSACTION COMMIT Kết thúc giao tác TRANSACTION ROLLBACK Hủy giao tác TRANSACTION Là khối lượng dữ liệu nhỏ nhất mà CSDL có thể thao tác Đơn vị dữ liệu có thể là ◦ Trường (Field. - Kích thước của đơn vị dữ liệu ánh hưởng đến hiệu năng xử lý đồng thời Các khái niệm Các vấn đề bất thường trong truy xuất đồng thời Lịch thao tác (Schedule. - Kỹ thuật khóa Kỹ thuật nhãn thời gian Các kỹ thuật khác 1. - Vấn đề mất dữ liệu đã cập nhật 2. - Vấn đề đọc phải dữ liệu chưa được xác nhận 4. - Kỹ thuật khóa Kỹ thuật nhãn thời gian Các kỹ thuật khác Định nghĩa lịch thao tác Lịch tuần tự - khả tuần tự Thuật toán kiểm tra tính khả tuần tự Lịch thao tác của n giao tác xử lý đồng thời T1,T2,….,Tn là một thứ tự thực hiện các hành động của n giao tác này Lịch thao tác phải đảm bảo thứ tự của các hành động trong cùng một giao tác Một lịch S được lập từ n giao tác xử lý đồng thời T1,T2,….,Tn được gọi là lịch tuần tự nếu với mọi giao tác Ti, các hành động của Ti được thực hiện liên tiếp nhau Một lịch S lập từ n giao tác xử lý đồng thời T1,T2,….,Tn được gọi là lịch khả tuần tự nếu khi thực hiện S, cho kết quả giống một lịch tuần tự nào đó được lập từ n giao tác này Hai thao tác Oi,Oj của hai giao tác xử lý đồng thời Ti,Tj được gọi là tương thích nếu việc thực hiện theo thứ tự < Oi,Oj > cho kết quả giống việc thực hiện theo thứ tự Hai thao tác thực hiện trên hai đơn vị dữ liệu khác nhau thì tương thích Hai thao tác tương thích Oi,Oj có thể thay đổi thứ tự thực hiện cho nhau mà không làm thay đổi kết quả, nên còn được gọi là hai thao tác khả hoán Bảng khả hoán của hai thao tác trên cùng đơn vị dữ liệu Read Write Read Yes No Write No No Một lịch S được gọi là khả tuần tự nếu chúng ta có thể giao hoán các thao tác khả hoán để đưa S về một lịch tuần tự S7 T1 T2 T3 1 Read(A);A:=A-10 2 Read(B);B:=B-20 3 Read(C). - Bộ lập lịch sẽ phải thực hiện các hành động của nó theo các thuật toán điều khiển đồng thời Đảm bảo đơn vị xử lý trung tâm của máy tính (CPU) được xử dụng một cách hiệu quả Tạo điều kiện về cô lập dữ liệu để đảm bảo rằng hai giao tác không cập nhật cùng một đơn vị dữ liệu ở cùng một thời điểm Các khái niệm Các vấn đề bất thường trong truy xuất đồng thời Lịch thao tác (Schedule. - Kỹ thuật khóa Kỹ thuật nhãn thời gian Các kỹ thuật khác Các kỹ thuật điều khiển đồng thời Khóa đơn giản Khóa đọc ghi Khóa trên dữ liệu phân cấp Những kỹ thuật cho phép bộ lập lịch sử dụng để tạo một lịch khả tuần tự từ n giao tác thực hiện đồng thời. - Kỹ thuật khoá đơn giản còn gọi khoá nhị phân (Binary locks. - Các giao tác trước khi muốn đọc/ghi lên 1 đơn vị dữ liệu phải phát ra yêu cầu xin khóa (lock) đơn vị dữ liệu đó. - Yêu cầu này được bộ phận quản lý khóa xử lý (Lock Manager. - Yêu cầu xin khóa được chấp thuận nếu đơn vị dữ liệu chưa bị khóa bởi một giao tác nào khác Sau khi thao tác xong thì giao tác này phải phát ra lệnh giải phóng đơn vị dữ liệu (unclock. - Giao tác đúng đắn: Giao tác Ti đọc hay ghi lên đơn vị dữ liệu A phải được thực hiện sau khi Ti khóa trên A và trước khi Ti giải phóng khóa A. - Lịch thao tác hợp lệ: Khi Ti đang giữ khóa trên một đơn vị dữ liệu A thì không Ti nào khác được khóa trên A. - S Giao tác T1, T2 có đúng đắn không. - Lịch S có hợp lệ không Giao tác Ti nào đúng đắn. - Input: Lịch S được lập từ n giao tác xử lý đồng thời T1,T2,…Tn theo kỹ thuật khóa đơn giản Output: S khả tuần tự hay không. - Xây dựng 1 đồ thị có hướng G ◦ Mỗi giao tác Ti là đỉnh của đồ thị ◦ Nếu một giao tác Tj phát ra Lockj(A) sau một giao tác Ti phát ra Locki(A) thì vẽ một cung từ Ti đến Tj S khả tuần tự nếu G không có chu trình Ví dụ S T1 T2 Lịch S có khả Lock(A) tuần tự Read(A). - B:=B+100 Write(B) Unlock(B) Bài tập S Lịch S có khả tuần tự không? Bài tập S Lịch S có khả tuần tự không. - Ngăn ngừa khóa chết Một giao tác T phải xin khóa tất cả các đơn vị dữ liệu mà mình sẽ thao tác, nếu được chấp thuận tất cả thì sẽ thao tác, ngược lại phải giải phóng các khóa đã được cấp trên các đơn vị dữ liệu Phát hiện khóa chết: Xây dựng đồ thị chờ (Waiting Graph) G ◦ Mỗi giao tác là một nút của đồ thị G ◦ Nếu có giao tác Tj phát ra yêu cầu khóa đơn vị dữ liệu A, và phải chờ vì A đã bị khóa bởi Ti, thì vẽ cung nối Ti,Tj ◦ Nếu G xuất hiện chu trình Xảy ra khóa chết Trong một giao tác, tất cả các thao tác khóa đều phải xảy ra trước các thao tác giải phóng khóa Nếu lịch S thỏa nghi thức khóa 2 giai đoạn (2PL) thì S khả tuần tự Chứng minh 2PL Có giải quyết được vấn đề deadlock không. - Các kỹ thuật điều khiển đồng thời Khóa đơn giản Khóa đọc ghi Khóa trên dữ liệu phân cấp Định lý: Lịch S thỏa thì S khả tuần tự Các kỹ thuật điều khiển đồng thời Khóa đơn giản Khóa đọc ghi Khóa trên dữ liệu phân cấp Quan hệ TAIKHOAN(MATK, SODU. - Giao tác gửi và rút tiền ◦ Khóa relation Các giao tác thay đổi giá trị số dư của 1 tài khoản X sẽ yêu cầu khóa độc quyền Vì khóa ở mức độ quan hệ nên toàn bộ bảng bị khóa Các giao tác khác muốn truy cập tài khoản Y (khác X) cũng phải chờ Vô lý Tốc độ xử lý chậm ◦ Khóa tuple hay disk block 2 Tài khoản ở 2 block khác nhau có thể cập nhật cùng thời điểm Xử lý nhanh Giao tác tính tổng tiền của các tài khoản ◦ Khóa relation. - Quản lý khóa ở nhiều mức độ ◦ Tính chất hạt (granularity) tăng khi đơn vị dữ liệu bị khóa càng lớn ◦ Tính đồng thời (concurrency) tăng khi đơn vị dữ liệu bị khóa càng nhỏ Relations là đơn vị dữ liệu khóa lớn nhất Một relation gồm 1 hoặc nhiều blocks (pages. - Warning (intention to) shared lock: IS ◦ Warning (intention to) exclusive lock: IX Cho biết các khóa có thể cùng tồn tại trên một node dữ liệu Yêu cầu khóa Trạng thái hiện hành Cho biết các khóa có thể phát trên node con khi node cha đang có một khóa nào đó 1. - T2 có thể truy xuất f3.1 bằng khóa X được không. - Kỹ thuật khóa Kỹ thuật nhãn thời gian Các kỹ thuật khác Giới thiệu Kỹ thuật nhãn thời gian toàn phần Kỹ thuật nhãn thời gian riêng phần Kỹ thuật nhãn thời gian nhiều phiên bản Một giao tác T khi phát sinh thì được gán một nhãn thời gian timestampTS(T) ghi nhận lại thời điểm phát sinh của T. - Mỗi đơn vị dữ liệu A cũng có một nhãn TS(A) nhãn này ghi lại nhãn thời gian TS(T) của giao tác T đã thao tác (read/ write) A thành công sau cùng Để giảm bớt trường hợp các giao tác bị Abort, người ta tách nhãn của đơn vị dữ liệu thành hai loại nhãn. - Gắn các nhãn thời gian TS(T), RT(A), WT(A. - Xử lý các tình huống. - Đọc quá trễ ◦ Ghi quá trễ ◦ Đọc dữ liệu rác ◦ Qui tắc ghi Thomas T vào trước U : TS(T)