Hệ quản trị cơ sở dữ liệu - Chương 0: Giới thiệu

359 trang vanle 2350

Download

Bạn đang xem 20 trang mẫu của tài liệu "Hệ quản trị cơ sở dữ liệu - Chương 0: Giới thiệu", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

he_quantri_cosodulieu_chuong_0_gioithieu.pdf

Nội dung text: Hệ quản trị cơ sở dữ liệu - Chương 0: Giới thiệu

LOGO HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU Chương 0: GIỚI THIỆU Giáo viên lý thuyết: Nguyễn Trường Sơn (ntson@it.hcmus.edu.vn ) Quy tắc gửi email: Subject: [DTTX] HQTCSDL 2014 Tieu de email 1
NỘI DUNG § Đặt vấn đề § Mục tiêu môn học § Nội dung môn học § Hình thức đánh giá § Tài liệu tham khảo § Trao đổi & thảo luận 2
ĐẶT VẤN ĐỀ § Ứng dụng có sử dụng CSDL rất rất phổ biến hiện nay, bao phủ hầu hết trong các hoạt động kinh tế, xã hội, giáo dục, y tế à Tầm quan trọng của một công cụ trị CSDL § Lịch sử phát triển của mô hình CSDL cũng qua nhiều giai đoạn: § Tương ứng với sự phát triển của mô hình lưu trữ dữ liệu là sự phát triển của phần mềm cài đặt mô hình dữ liệu đó (HQTCSDL) 3
ĐẶT VẤN ĐỀ Môn học: HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU Các phần mềm này hoạt động như thế nào ? Tại sao ? Có những thành phần nào ? 4
MỤC TIÊU MÔN HỌC Cung cấp cho sinh viên kiến thức nền tảng về các Hệ quản trị Cơ sở dữ liệu (HQTCSDL): Các thành LÝ phần của một HQTCSDL và các chức năng của THUYẾT chúng, các cơ chế quản lý truy xuất đồng thời, an toàn và an ninh dữ liệu, tối ưu hoá câu hỏi, các cấu trúc tổ chức lưu trữ bên trong. Tìm hiểu và vận dụng các kỹ thuật quản lý truy THỰC xuất đồng thời của một HQTCSDL cụ thể: MS HÀNH SQL Server 5
NỘI DUNG MÔN HỌC § Chương 1: Tổng quan về HQTCSDL – Yêu cầu về dữ liệu trong CSDL – Khái niệm HQTCSDL – Kiến trúc của HQTCSDL – Phân loại HQTCSDL § Chương 2: Giao tác và lịch giao tác – Giao tác – Lịch giao tác • Lịch tuần tự • Lịch Khả tuần tự 6
NỘI DUNG MÔN HỌC § Chương 3: Điều khiển truy xuất đồng thời – Các vấn đề của truy xuất đồng thời – Kỹ thuật khoá – Kỹ thuật nhãn thời gian – Kỹ thuật lạc quan – Một số vấn đề khác § Chương 4: An toàn và an ninh dữ liệu – An toàn dữ liệu – An ninh dữ liệu § Chương 5: Xử lý câu truy vấn – Quy trình xử lý – Phân tích cú pháp ngữ nghĩa 7 –
NỘI DUNG MÔN HỌC – Chuyển về dạng biểu diễn trong – Tối ưu hoá câu hỏi – Ước lượng kích thước cây truy vấn – Phát sinh và thực thi mã lệnh § Chương 6: Tổ chức dữ liệu – Mẫu tin – Tổ chức lưu trữ mẫu tin § Chương 7: Các hệ CSDL phân tán – Kiến trúc Client Server – Kiến trúc phân tán – Thiết kế CSDL phân tán – Các khái niệm cơ bản – Các vấn đề của hệ phân tán 8
HÌNH THỨC ĐÁNH GIÁ § LÝ THUYẾT – Thi viết / trắc nghiệm (Không sử dụng tài liệu): 4à5đ – Bài tập / Kiểm tra: 2 à 3đ – Điểm tối đa: 7đ § THỰC HÀNH – Làm bài tập & bài thực hành – Điểm tối đa: 3đ § QUY ĐỊNH: – Những bài thi giống nhau sẽ bị 0 ĐIỂM MÔN HỌC (không quan tâm đến ai chép bài của ai) 9
PHẦN MỀM 10
TÀI LIỆU THAM KHẢO § Fundamentals of Database Systems, 4th Edition, Elmasri Navathe § Database Management Systems, 3rd Edition, Raghu Ramakrishnan and Johannes Gehrke § Database System Concepts, 4th Edition, Silberschatz−Korth −Sudarshan § Database Systems Implementation, Hector Garcia- Molina, D. Ullman, Jennifer D. Widom 11
LOGO HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU Chương 1: TỔNG QUAN VỀ HQT CSDL GVLT: Nguyễn Trường Sơn
Nội dung
Nội dung § Yêu cầu về dữ liệu trong CSDL § Khái niệm HQT CSDL § Kiến trúc của một HQT CSDL § Phân loại HQT CSDL
Yêu cầu về dữ liệu trong CSDL § Dữ liệu trong CSDL phải được thể hiện ở các mức độ trừu tượng khác nhau (3 mức độ): – Mức ngoài (External level) • Mô tả một phần của CSDL mà một đối tượng / một nhóm người dùng được quyền tiếp cận – Mức luận lý (Logic level) • Mô tả những thông tin gì được lưu trữ trong CSDL và những mối quan hệ giữa những thông tin đó – Mức vật lý (Physical level) • Dữ liệu được lưu trữ như thế nào trên thiết bị lưu trữ. à Làm tăng tính độc lập (data independence) của cách thức lưu trữ dữ liệu, thiết kế dữ liệu và chương trình sử dụng dữ liệu.
Yêu cầu về dữ liệu trong CSDL § Các mức độ trừu tượng của dữ liệu: External External External Schema 1 Schema 2 Schema 3 Logical Schema Physical Schema DISK
Yêu cầu về dữ liệu trong CSDL § Dữ liệu trong CSDL cần có các đặc trưng: – Ít hoặc không trùng lắp dữ liệu – Chia sẽ cho nhiều người dùng mà không gây ra xung đột – An ninh, bảo mật – Khôi phục khi có sự cố – Độc lập dữ liệu • Độc lập luận lý: Khả năng thay đổi lược đồ mức luận lý mà không lảm ảnh hưởng đến lược đồ ngoài cũng như chương trình ứng dụng. • Độc lập vật lý: Khả năng thay đổi tổ chức vật lý của CSDL mà không làm ảnh hưởng đến lược đồ luận lý. § Vì vậy cần có một hệ thống quản lý hiệu quả dữ liệu trong CSDL.
Lợi ích của tính độc lập dữ liệu External § Độc lập luận lý: Schema 1 – Cho phép thêm bớt thuộc tính, bảng, các mối quan hệ mà không cần phải viết lại chương trình, Logical Schema § Độc lập vật lý: – Cho phép thay đổi thiết bị lưu trữ, cách Physical thức lưu trữ, các cấu trúc dữ liệu, các tổ Schema chức tập tin khác nhau, các kiểu tổ chức chỉ mục khác nhau, DISK
Khái niệm HQT CSDL § Là một hệ thống phần mềm cung cấp các công cụ để xây dựng, khai thác và quản lý cơ sở dữ liệu. – Xây dựng (Sử dụng ngôn ngữ DDL): Định nghĩa cấu trúc CSDL, lưu trữ dữ liệu – Khai thác (Sử dụng ngôn ngữ DML): Truy vấn dữ liệu, Cập nhật dữ liệu – Quản lý: • Quản lý an toàn và bảo mật • Điều khiển truy xuất đồng thời. • Khôi phục khi có sự cố. • § Một số HQTCSDL: MS SQL Server, Oracle, DB2,
Các lợi ích của HQT CSDL § Độc lập dữ liệu § Truy cập dữ liệu hiệu quả § Toàn vẹn dữ liệu § An ninh dữ liệu § Truy xuất đồng thời § Khôi phục sau sự cố § Giảm thời gian phát triển ứng dụng § § §
Lịch sử phát triển của các HQT CSDL Decade of RDBMS 1960s 1970s 1980s – 1990s 2000s Mô hình Mô hình mạng quan hệ Mô hình No SQL CODASYL đối tượng Database Mô hình phân cấp QUEL SEQUEL SQL IMS Ingres PostgreSQL dBASE MongoDB, Oracle SABRE Ingres Corp Sybase NoSQL Database, system MS SQL Server Prototypes Apache for ODBMS Cassandra , System R Non-Stop SQL SQL/DS DB2 Allbase Oracle
Kiến trúc của một HQT CSDL Sophiscatedusers, application Unsophisticated users (customers, travel agents, etc.) programmers, DB administrators Application Front Web forms SQL Interface Ends command flows SQL COMMANDS DBMS interactions Plan Executor Parser Query Evaluation Operator Evaluator Optimizer Concurency Engine Control Files and Access methods Transaction Manager Recovery Buffer Manager Lock Manager Manager Disk Space Manager references Index files System Catalog DATABASES Data files
Kiến trúc của một HQT CSDL § Các thành phần chính: Giao diện lập trình Xử lý câu truy vấn An ninh và bảo mật Khôi phục sau sự cố Người sử dụng Xử lý truy xuất đồng Tổ chức quản lý lưu thời trữ
Thành phần Giao diện lập trình § HQTCSDL cung cấp giao diện lập trình dễ sử dụng với một ngôn ngữ lập trình CSDL: – Giao diện: tương tác dòng lệnh (command line), đồ họa (GUI) – Ngôn ngữ: SQL, T-SQL – VD: MS SQL Server cung cấp ngôn ngữ Transacion SQL (T-SQL) § Các loại ngôn ngữ sử dụng trong HQTCSDL: – Ngôn ngữ định nghĩa dữ liệu (DDL – Data Definition Language): Giúp người dùng ra lệnh cho HQTCSDL tạo ra các cấu trúc dữ liệu của CSDL (Cách tổ chức dữ liệu và mối liên hệ giữa các đối tượng dữ liệu). – Ngôn ngữ thao tác CSDL (DML – Data Manupulation Language) : Giúp người dùng tích luỹ, hiệu chỉnh và khai thác dữ liệu
Thành phần An ninh và bảo mật § Bảo mật dữ liệu: HQTCSDL hỗ trợ các tính năng về chứng thực, phân quyền giúp kiểm soát tốt những người dùng hợp pháp của hệ thống § An ninh dữ liệu: HQTCSDL hỗ trợ các phương pháp mã hóa dữ liệu để ngăn chặn các tấn công của những đối tượng tin tặc (đánh cắp thông tin trên đường truyền, đánh cắp nội dung CSDL).
Thành phần Khôi phục sau sự cố § Mục tiêu: Đảm bảo sự tổn thất, sai sót về mặt dữ liệu là ít nhất có thể. § Cách tiếp cận: Để đảm bảo tính bền vững của CSDL, mọi thay đổi lên CSDL phải được ghi nhận lại trong nhật ký (Log) § Các thành phần hỗ trợ quá trình khôi phục sau sự cố: – Bộ phận quản lý nhật ký (Log manager) : đảm bảo ghi nhận đầy đủ và chính xác mọi thay đổi trên CSDL vào nhật ký. – Bộ phận quản lý khôi phục sự cố (Recovery Manager): dựa vào nhật ký để phục hồi lại CSDL về trạng thái nhất quán trước đó (Trạng thái thoả tất cả RBTV của CSDL)
Xử lý truy xuất đồng thời § Mục tiêu: – Đảm bảo các xử lý có thể được thực hiện đồng thời mà làm không làm cho dữ liệu bị mất tính nhất quán (vi phạm các ràng buộc toàn vẹn) § Các thành phần con: Bộ phận quản lý giao tác (Transaction Manager & Locking Manager) § Phương pháp: – Sử dụng khái niệm giao tác (transaction) để biểu diễn một đơn vị xử lý, một giao tác bao gồm các hành động mà được thực hiện tòn bộ hoặc không có hành động nào được thực hiện. T – Bộ lập lịch (scheduler) có nhiệm vụ lập 1 lịchthực hiện từ n giao tác không tách biệt về thời gian sao cho kết quả không vi phạm tính nhất quán của CSDL. – Sử dụng cơ chế khóa (lock) để khóa các đơn vị dữ liệu nào đó khi cần à ngăn 2 giao tác cùng thao tác lên 1 đơn vị dữ liệu ấy tại cùng 1 điểm à Hỗ trợ để lập lịch.
Điều khiển đồng thời (tt) CLIENT 1 CLIENT 2 SERVER CLIENT 3 LỊCH TUẦN TỰ LỊCH ĐỒNG THỜI T1 T2 T3
Điều khiển đồng thời (tt) § Vấn đề deadlock – Do sử dụng cơ chế khóa nên các giao tác sẽ phải chờ khi cần truy xuất 1 đơn vị dữ liệu đang bị khóa. – Tình huống chờ vĩnh viễn mà vẫn không được truy xuất đơn vị dữ liệu bị khóa gọi là Deadlock (khoá chết) • Các giao tác chờ đợi lẫn nhau để được cấp phát tài nguyên và không giao tác nào có thể hoàn tất. – Thành phần quản lý giao tác sẽ phải can thiệp vào: • Hoặc hủy bỏ một trong các giao tác gây deadlock • Hoặc ngăn chặn từ trước để không bao giờ sảy ra deadlock
Xử lý truy vấn § Biểu diễn câu truy vấn ở dạng ngôn ngữ cấp cao (SQL) và thực hiện câu truy vấn có hiệu quả. § Query compiler – biên dịch truy vấn – Xây dựng cấu trúc phân tích câu truy Query parser vấn dưới dạng cây – Kiểm tra ngữ nghĩa của câu truy vấn Query – Chuyển đổi cấu trúc cây sang ngôn preprocessor ngữ đại số quan hệ Query – Sắp xếp các phép toán nhằm mục đích optimizer tối ưu hóa câu truy vấn
Quản lý lưu trữ § Thành phần có nhiệm vụ điều khiển việc đọc/ghi dữ liệu qua lại giữa bộ nhớ và thiết bị lưu trữ § Làm việc với các khái niệm: – Tập tin dữ liệu – Từ điển dữ liệu • Lưu trữ các metadata (Siêu dữ liệu) về cấu trúc của CSDL, đặc biệt là lược đồ của CSDL – Chỉ mục • Giúp cho việc tìm kiếm Dữ liệu được nhanh chóng
Phân loại HQT CSDL § Theo mô hình dữ liệu: – Phân cấp – Mạng – Quan hệ – Đối tượng § Theo kiến trúc tính toán: – Tập trung (Centralized database system) – Khách / chủ (Client server database system) – Phân tán (Distributed database system) § Theo đặc tính: – HQTCSDL thời gian thực (real-time database system) – HQTCSDL chịu lỗi cao (high fault tolerance database system) – HQTCSDL đa phương tiện (multi-media database syste)
Mô hình phân cấp DEPT (DEPT#, BUDGET) (NAME, SALARY) EMP 17, 25M CHILD OFFICE Adam, 14K John, 12K (CHILD NAME, AGE) (OFFICE#, SIZE) Fisher, 10K 12, 500 Dave, 7 Peter, 4 12, 500 Sue, 10 12, 500
Mô hình mạng DEPT (DEPT#, BUDGET) (NAME, SALARY) 17, 25M EMP OFFICE Adam, 14K (OFFICE#, SIZE) John, 12K CHILD Fisher, 10K Dave, 7 (CHILD NAME, AGE) Peter, 4 12, 500 Sue, 10
Mô hình quan hệ OCCUPIED DEPT Fisher 12 17 25M DEPT (DEPT #, BUDGET) John 12 OFFICE OFFICE (OFFICE #, SIZE) Adam 12 12 500 EMP (NAME, SALARY) CHILD (CHILD NAME, AGE) CHILD EMP WORKS (DEPT #, NAME) Sue 10 Fisher 10K Peter 4 John 12K OFFSPRING (NAME, CHILD NAME) Dave 7 Adam 14K OCCUPIED (NAME, OFFICE #) OFFSPRING WORKS Fisher Sue 17 Fisher Fisher Peter 17 John Jone Dave 17 Adam
Phân loại HQTCSDL § Theo kiến trúc tính toán: Tập trung: Phân tán Khách / chủ
TÓM TẮT CHƯƠNG 1 § Sự cần thiết phải có HQTCSDL § Một số thành phần chính – Dữ liệu cần được trình bày ở nhiều của HQTCSDL mức khác nhau – Giao diện lập trình – Các đặc trưng cần phải có của dữ liệu – Xử lý đồng thời khi lưu trữ trong CSDL – An ninh và bảo mật – Tính chất độc lập dữ liệu – Khôi phục sau sự cố – Xử lý truy vấn – Quản lý lưu trữ § Lịch sử phát triển của HQTCSDL § Phân loại HQTCSL § Kiến trúc tổng quan của – Theo mô hình dữ liệu HQTCSDL – Theo kiến trúc tính toán – Theo đặc tính
ĐỌC THÊM Chapter 1. Introduction to database systems (p.3 à p.23) Chapter 1. Introduction (p.1 à p.24) Chapter 1 & 2
BÀI TẬP Đọc sách Database Management Systems, 2nd Editon (Có thể tham khảo các sách khác & google) và làm những nội dung sau: § A. Trình bày lại nội dung phần 1.10 trong sách § B. Trả lời các câu hỏi trong phần bài tập Exercises 1.1 đến 1.8 (giải thích ngắn gọn, đầy đủ & súc tích):
BÀI TẬP Đọc sách Database Management Systems, 2nd Editon (Có thể tham khảo các sách khác & google) và làm những nội dung sau: § A. Trình bày lại nội dung phần 1.10 trong sách § B. Trả lời các câu hỏi trong phần bài tập Exercises 1.1 đến 1.8 (giải thích ngắn gọn, đầy đủ & súc tích):
LOGO HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU Chương 2: GIAO TÁC VÀ LỊCH GIAO TÁC GVLT: Nguyễn Trường Sơn 1
Nội dung trình bày § Giới thiệu § Giao tác – Khái niệm – Tính ACID của giao tác – Các thao tác của giao tác – Các trạng thái của giao tác § Lịch thao tác – Giới thiệu – Khái niệm – Lịch tuần tự – Lịch khả tuần tự 2
Giới thiệu § Hai yêu cầu cơ bản của ứng dụng khai thác CSDL trong thực tế: – Cho phép nhiều người dùng đồng thời khai thác CSDL nhưng phải giải quyết được các tranh chấp. – Sự cố kỹ thuật có thể luôn luôn xảy ra nhưng phải giải quyết được vấn đề về nhất quán dữ liệu. § Một số ví dụ về ứng dụng có sử dụng CSDL : – Hệ thống giao dịch ở ngân hàng – Hệ thống đặt vé máy bay – Hệ thống quản lý học sinh – 3
Giới thiệu – Một số tình huống GHẾ (Mã ghế, Mã CB, Trạng thái) CHUYẾN BAY(Mã CB, Ngày giờ, Số ghế còn) § Hệ thống đặt vé máy bay: – “Khi hành khách mua vé” – “Khi hai hành khách cùng đặt một ghế trống” – TÀI KHOẢN(Mã TK, Số dư) GIAO DỊCH(Mã GD, Loại, Số tiền) § Hệ thống ngân hàng: – “Khi chuyển tiền từ tài khoản A sang tài khoản B” – “Khi rút tiền của một tài khoản” – “Nhiều người cùng rút tiền trên một tài khoản” – § Hệ thống quản lý học sinh: Lớp học(Mã lớp, Tên, Sĩ số) – Thêm một học sinh mới Học sinh (Mã HS, Họ tên, Mã lớp) – Chuyển lớp 4 –
Giới thiệu – Một số tình huống § “Hai (nhiều) hành khách cùng đặt một ghế trống” – Lỗi: Có thể có nhiều hành khách đều đặt được dù chỉ còn 1 ghế 1. Tìm thấy một ghế trống 2. Đặt ghế GHẾ (Mã ghế, Mã CB, Trạng thái) Mã ghế Mã CB Trạng thái 1001 100 No 1002 100 No 1. Tìm thấy một ghế trống 2. Đặt ghế 1003 100 Yes No à Phải giải quyết được tranh chấp để đảm 1050 bảo được nhất100 quán dữ liệuNo . 5
Giới thiệu – Một số tình huống § “Chuyển tiền từ tài khoản A sang tài khoản B” – Lỗi: Có thể đã rút tiền từ A nhưng chưa cập nhật số dư của B TÀI KHOẢN(Mã TK, Số dư) Mã TK Số dư A A 50 1. update TAIKHOAN set SoDu=SoDu-50 B 100 where MATK=A C 60 Sự cố 2. update TAIKHOAN set SoDu=SoDu+50 where MATK=B N 90 à Phải đảm bảo được nhất quán dữ liệu khi có sự cố. 6
Giới thiệu – Một số tình huống § “Nhiều người cùng rút tiền từ một tài khoản” – Lỗi: Có thể rút nhiều hơn số tiền thực có TÀI KHOẢN(Mã TK, Số dư) Rút 70 Mã TK Số dư Rút 80 A 100 Rút 90 1. Đọc số dư của tài khoản A vào X 2. Cập nhật số dư mới của tài khoản A bằng X – Số tiền à Phải giải quyết được tranh chấp để đảm bảo được nhất quán dữ liệu. 7
Giới thiệu – Một số tình huống § “Thêm một học sinh mới” – Lỗi: Có thể xảy ra trường hợp học sinh đã được thêm nhưng sĩ số không được cập nhật. Lớp học(Mã lớp, Tên, Sĩ số) Mã lớp Tên Sĩ số 1 10A 3 1. Thêm vào một học sinh của lớp Học sinh (Mã HS, Họ tên, Mã lớp) Sự cố Mã HS 2 Họ 10B tên Mã0 lớp 2. Cập nhật sĩ số lớp tăng lên 1 1 An 1 2 Thảo 1 à Phải đảm bảo được nhất quán dữ liệu khi có sự cố. 3 Bình 1 8
Giới thiệu § Nhận xét: – Thường xuyên xảy ra vấn đề nhất quán dữ liệu nếu một xử lý gặp sự cố hoặc khi các xử lý được gọi truy xuất đồng thời. § Cần 1 khái niệm biểu diễn một đơn vị xử lý với các tính chất: – Nguyên tố – Cô lập – Nhất quán Giao tác – Bền vững Là một khái niệm nền tảng của điều khiển truy xuất đồng thời và khôi phục khi có sự cố. 9
Nội dung trình bày § Giới thiệu § Giao tác – Khái niệm – Tính ACID của giao tác – Các thao tác của giao tác – Các trạng thái của giao tác § Lịch thao tác – Giới thiệu – Khái niệm – Lịch tuần tự – Lịch khả tuần tự 10
Giao tác là gì ? § Giao tác (Transaction) là một đơn vị xử lý nguyên tố gồm một chuỗi các hành động đọc / ghi trên các đối tượng CSDL – Nguyên tố: Không thể phân chia được nữa. Các hành động trong một giao tác hoặc là thực hiện được tất cả hoặc là không thực hiện được bất cứ hành động nào. statement 1 statement 2 T statement 3 statement n § Trong kiến trúc hệ quản trị CSDL: – Bộ phận Điều khiển đồng thời đóng vai trò quản lý giao tác. 11
Tính chất ACID của giao tác § Tính nguyên tố (Atomicity) – Hoặc là toàn bộ hoạt động được phản ánh đúng đắn trong CSDL, hoặc không có hoạt động nào cả. § Tính nhất quán (Consistency) – Khi một giao tác kết thúc (thành công hay thất bại), CSDL phải ở trạng thái nhất quán (Đảm bảo mọi RBTV). Một giao tác đưa CSDL từ trạng thái nhất quán này sang trạng thái nhất quán khác. § Cô lập (Isolation) – Một giao tác khi thực hiện sẽ không bị ảnh hưởng bởi các giao tác khác thực hiện đồng thời với nó. § Bền vững (Durability) – Mọi thay đổi trên CSDL được ghi nhận bền vững vào thiết bị lưu trữ dù có sự cố có thể xảy ra. 12
Ví dụ về tính chất ACID Chuyển khoản tiền từ tài khoản A sang tài khoản B Mã TK Số dư Giao tác Chuyển khoản 1. update TAIKHOAN set SoDu=SoDu-50 A 50 where MATK=A B 100 Sự cố 2. update TAIKHOAN set C 60 SoDu=SoDu+50 where MATK=B Cuối giao tác N 90 Atomicity: Hoặc cả 2 bước trên đều thực Consitency : Với giao tác chuyển hiện hoặc không bước nào được thực hiện. tiền, tổng số dư của A và B luôn Nếu có sự cố bước 2 thì HQT CSDL có cơ luôn không đổi. chế khôi phục lại dữ liệu như lúc ban đầu. 13
Ví dụ về tính chất ACID Lớp học(Mã lớp, Tên, Sĩ số) Mã lớp Tên Sĩ số Thêm học sinh mới vào một lớp 1 10A 3 Giao tác Thêm học sinh mới Học sinh (Mã HS, Họ tên, Mã lớp) 1. Thêm một học sinh vào bảng học sinh Mã2 HS Họ10B tên 0 Mã lớp 2. Cập nhật sĩ số của lớp tăng lên 1 Sự cố Cuối giao tác 1 An 1 2 Thảo 1 Atomicity: Hoặc cả 2 bước trên đều thực 3 Bình 1 hiện hoặc không bước nào được thực hiện. Nếu có sự cố bước 2 thì HQT CSDL có cơ Consistency: Sĩ số của lớp phải chế khôi phục lại dữ liệu như lúc ban đầu. luôn bằng số học sinh thực sự và không quá 3. 14
Ví dụ về tính chất ACID Rút ền (TK1, 80) Gửi ền (TK1, 50) Tài khoản (Mã TK, Số dư ) T1 Thời gian T2 Mã TK Số dư Đọc số dư: t 1 100 Đọc số dư: t 2 500 Cập nhật số dư (=t-80) 3 200 Cập nhật số dư (=t+50) Isolation: Tính chất cô lập đảm bảo mặc dù các giao tác có thể đan xen nhau nhưng kết quả của chúng tương tự với một kết quả tuần tự nào đó à Các giao tác không bị ảnh hưởng bởi các giao tác khác khi thực thi. 15
Đơn vị dữ liệu § Đối tượng CSDL mà giao tác thực hiện các xử lý đọc /ghi còn được gọi là đơn vị dữ liệu. § Một đơn vị dữ liệu (element) có thể là các thành phần : – Quan hệ (Relations) – Khối dữ liệu trên đĩa (Blocks) – Bộ (Tuples) § Một CSDL bao gồm nhiều đơn vị dữ liệu. 16
Các thao tác của giao tác Input(X) X Read(X,t) Write(X,t) X t Output(X) Buffer Database Read (A, t) : Đọc đơn vị dữ liệu A vào t Write (A, t) : Ghi t vào đơn vị dữ liệu A [5] Chapter 17, Database systems: the complete book 17
Ví dụ về biểu diễn giao tác § Giả sử có 2 đơn vị dữ liệu A và B với ràng buộc A = B (nếu có một trạng thái nào đó mà A ≠B thì sẽ mất tính nhất quán) § Giao tác T thực hiện 2 bước: – A = A * 2 – B = B * 2 T Read(A, t); § Biểu diễn T: t =t*2; Write(A, t) Read(B, t); t =t*2; Write(B, t) § Hoặc: T: Read(A, t); t =t*2; Write(A, t); Read(B, t); t =t*2; Write(B, t) 18
Giao tác: Ví dụ (tt) Hành động t Mem A Mem B Disk A Disk B Input (A) 8 8 8 Read (A, t) 8 8 8 8 t := t * 2 16 8 8 8 Write (A, t) 16 16 8 8 Input (B) 16 16 8 8 8 Read (B, t) 8 16 8 8 8 t := t * 2 16 16 8 8 8 Write (B, t) 16 16 16 8 8 Output (A) 16 16 16 16 8 Output (B) 16 16 16 16 16 19
Các trạng thái của giao tác Sau khi lệnh thi hành Sau khi mọi hành động cuối cùng thực hiện hoàn tất thành công PARTIALLY COMMITTED COMMITTED ACTIVE Ngay khi bắt đầu thực hiện thao tác FAILED ABORTED đọc/ghi Sau khi giao tác được quay lui Sau khi nhận ra không thể thực và CSDL được phục hồi về hiện các hành động được nữa trạng thái trước trạng thái bắt đầu giao tác 20
Khai báo giao tác trong T-SQL BEGIN TRANSACTION Bắt đầu giao tác COMMIT TRANSACTION Kết thúc giao tác thành công Kết thúc giao tác không thành công. CSDL được đưa về tình ROLLBACK TRANSACTION trạng trước khi thực hiện giao tác. 21
Nội dung trình bày § Giới thiệu § Giao tác – Khái niệm – Tính ACID của giao tác – Các thao tác của giao tác – Các trạng thái của giao tác § Lịch thao tác – Giới thiệu – Khái niệm – Lịch tuần tự – Lịch khả tuần tự 22
Các cách thực hiện của các giao tác § Thực hiện tuần tự: Các thao tác khi thực hiện mà không giao nhau về mặt thời gian. é Ưu: Nếu thao tác đúng đắn thì luôn luôn đảm bảo nhất quán dữ liệu. ê Khuyết: Không tối ưu về việc sử dụng tài nguyên và tốc độ. § Thực hiện đồng thời: Các lệnh của các giao tác khác nhau xen kẽ nhau trên trục thời gian. ê Khuyết: Gây ra nhiều phức tạp về nhất quán dữ liệu é Ưu: • Tận dụng tài nguyên và thông lượng (throughput). Ví dụ: Trong khi một giao tác đang thực hiện việc đọc / ghi trên đĩa, một giao tác khác đang xử lý tính toán trên CPU. • Giảm thời gian chờ. Ví dụ: Chia sẽ chu kỳ CPU và truy cập đĩa để làm giảm sự trì hoãn trong các giao tác thực thi. 23
Lịch thao tác là gì ? § Định nghĩa: Một lịch thao tác S được lập từ n giao tác T1, T2, , Tn được xử lý đồng thời là một thứ tự thực hiện xen kẽ các hành động của n giao tác này. § Thứ tự xuất hiện của các thao tác trong lịch phải giống với thứ tự xuất hiện của chúng trong giao tác. § Bộ lập lịch (Scheduler): Là một thành phần của DBMS có nhiệm vụ lập một lịch để thực hiện n giao tác xử lý đồng thời. § Các loại lịch thao tác: – Lịch tuần tự (Serial) – Lịch khả tuần tự (Serializable): • Conlict – Serializability • View – Serializability 24
Lịch tuần tự § Một lịch S được gọi là tuần tự nếu các hành động của các giao tác Ti được thực hiện liên tiếp nhau, không có sự giao nhau về mặt thời gian. S T1 T2 T 4 T 3 T 5 25
Lịch tuần tự Ví dụ: T1 T2 A B �↓ T1 T2 A B �↓� 25 25 � 25 25 Read(A, t) Read(A, s) t:=t+100 s:=s*2 Write(A,t) 125 Write(A,s) 50 Read(B, t) Read(B, s) t:=t+100 s:=s*2 Write(B, t) 125 Write(B, s) 50 Read(A, s) Read(A, t) s:=s*2 t:=t+100 Write(A,s) 250 Write(A,t) 150 Read(B, s) Read(B, t) s:=s*2 t:=t+100 Write(B, s) 250 Write(B, t) 150 T1 T2 T 2 T1 Lịch tuần tự luôn luôn đảm bảo được tính nhất quán của CSDL 26
Lịch xử lý đồng thời § Lịch xử lý đồng thời là lịch mà các giao tác trong đó giao nhau về mặt thời gian T4 S T1 T5 T2 T3 Lịch xử lý đồng thời Lịch đồng thời luôn luôn tiềm ẩn khả năng làm cho CSDL mất tính nhất quán 27
Lịch đồng thời S3 T1 T2 A B Ví dụ: 25 25 § S3 là một lịch xử lý đồng thời vì các Read(A, t) t:=t+100 giao tác giao thoa với nhau Write(A,t) 125 Read(A, s) s:=s*2 § Lịch xử lý đồng thời S3 gây ra sự Write(A,s) 250 Read(B, s) mất nhất quán dữ liệu s:=s*2 – Trước S khi thực hiện Write(B, s) 50 Read(B, t) • A=B t:=t+100 – Sau khi S kết thúc Write(B, t) 150 • A ≠ B 28
Lịch khả tuần tự § Một lịch S được lập ra từ n giao tác T1, T2, , Tn xử lý đồng thời được gọi là lịch khả tuần tự nếu nó cho cùng kết quả với một lịch tuần tự nào đó được lập ra từ n giao tác này. S T4 T1 T5 T2 T3 t Tương đương T1 T2 T4 T3 T5 S’ t Lịch khả tuần tự cũng không gây nên tình trạng mất nhất quán dữ liệu 29
Lịch khả tuần tự Ví dụ: T1 T2 A B S4 § Trước S4 khi thực hiện 25 25 – A=B=c Read(A, t) t:=t+100 – với c là hằng số Write(A,t) 125 § Sau khi S kết thúc Read(A, s) 4 s:=s*2 – A=2*(c+100) Write(A,s) 250 – B=2*(c+100) Read(B, t) t:=t+100 § Trạng thái CSDL nhất quán Write(B, t) 125 Read(B, s) § S4 là khả tuần tự s:=s*2 Write(B, s) 250 ( Kết quả của lịch S4 tương tự với kết quả của lịch tuần tự S ) 30
Lịch khả tuần tự Ví dụ: T1 T2 A B S5 § Trước S5 khi thực hiện 25 25 Read(A, t) – A=B=c t:=t+100 – với c là hằng số Write(A,t) 125 Read(A, s) § Sau khi S5 kết thúc s:=s*2 – A = 2*(c+100) Write(A,s) 250 Read(B, s) – B = 2*c + 100 s:=s*2 Write(B, s) 50 à Trạng thái CSDL không nhất quán Read(B, t) S không khả tuần tự t:=t+100 § 5 Write(B, t) 150 31
Lịch khả tuần tự Ví dụ: T1 T2 A B S5b § Trước S5b khi thực hiện 25 25 Read(A, t) – A=B=c t:=t+100 – với c là hằng số Write(A,t) 125 Read(A, s) § Sau khi S5b kết thúc s:=s*1 – A = 1*(c+100) Write(A,s) 125 Read(B, s) – B = 1*c + 100 s:=s*1 25 Write(B, s) à Trạng thái CSDL vẫn nhất quán Read(B, t) t:=t+100 Write(B, t) 125 q Để xem xét tính mất nhất quán một cách kỹ lưỡng à phải hiểu rõ ngữ nghĩa của từng giao tác à không khả thi q Thực tế chỉ xem xét các lệnh của giao tác là đọc hay ghi 32
Biểu diễn lịch thao tác Cách 1 S T1 T2 Cách 2 Read(A, t) t:=t+100 S T1 T2 Write(A,t) Read(A) Read(A, s) Write(A) s:=s*2 Write(A,s) Read(A) Read(B, t) Write(A) t:=t+100 Read(B) Write(B, t) Write(B) Read(B, s) Read(B) s:=s*2 Write(B) Write(B, s) Cách 3 S: R1(A); W1(A); R2(A); W2(A); R1(B); W1(B); R2(B); W2 (B) 33
Lịch khả tuần tự § Có 2 loại lịch khả tuần tự: Conlict § Dựa trên ý tưởng hoán vị các hành động không Serializable xung đột để chuyển một lịch đồng thời S về một lịch tuần tự S’. Nếu có một cách biến đổi như vậy thì S là một lịch conlict serializable. View § Dựa trên ý tưởng lịch đồng thời S và lịch tuần Serializable tự S’ đọc và ghi những giá trị dữ liệu giống nhau. Nếu có một lịch S’ như vậy thì S là một lịch view serializable. 34
Conflict Serializability § Ý tưởng: Xét 2 hành động liên tiếp nhau của 2 giao tác khác nhau trong một lịch thao tác, khi 2 hành động đó được đảo thứ tự có thể dẫn đến 1 trong 2 hệ quả: – Hoạt động của cả hai giao tác chứa 2 hành động ấy không bị ảnh hưởng gì T T’ à 2 hành động đó không xung đột Hành động 1 với nhau Hành động 2 – Hoạt động của ít nhất một trong 2 Hành động 1’ giao tác chứa 2 hành động ấy bị ảnh Hành động 2’ hưởng à 2 hành động xung đột Hành động 3 Hành động 4 Hành động 3’ Hành động 4’ 35
Conflict Serializability (tt) § Cho lịch S có 2 giao tác Ti và Tj, xét các trường hợp: – ri (X) ; rj(Y) • Không bao giờ có xung đột, ngay cả khi X=Y • Cả 2 thao tác không làm thay đổi giá trị của X và Y – ri (X) ; wj(Y) • Không xung đột khi X ≠ Y – Tj không thay đổi dữ liệu đọc của Ti – Ti không sử dụng dữ liệu ghi của Tj • Xung đột khi X = Y – wi (X) ; rj(Y) • Không xung đột khi X ≠ Y, Xung đột khi X=Y – wi (X) ; wj(Y) • Không xung đột khi X ≠ Y, Xung đột khi X=Y 36
Conflict Serializability (tt) § Tóm lại, hai hành động xung đột nếu chúng: v Thuộc 2 giao tác khác nhau v Truy xuất đến 1 đơn vị dữ liệu v Trong chúng có ít nhất một hành động ghi (write) § Hai hành động xung đột thì không thể nào đảo thứ tự của chúng trong một lịch thao tác. 37
Conflict Serializability (tt) § Ví dụ: S S ’ 6 T1 T2 6 T1 T2 Read(A) Read(A) Write(A) Write(A) Read(A) Read(B) Write(A) Write(B) Read(B) Read(A) Write(B) Write(A) Read(B) Read(B) Write(B) Write(B) S6 có khả năng chuyển đổi thành S6’ bằng cách hoán vị các cặp hành động không xung đột hay không ? 38
Conflict Serializability (tt) § Định nghĩa: – S và S’ là những lịch thao tác conlict equivalent nếu S có thể chuyển được thành S’ thông qua một chuỗi các hoán vị những thao tác không xung đột. – Một lịch thao tác S là conlict serializable nếu S là conlict equivalent với một lịch thao tác tuần tự nào đó. § S là conlict serializable thì S khả tuần tự. § S là khả tuần tự thì không chắc S conlict serializable § Lịch S ở slide trước có phải conlict serializable hay không ? 39
Conflict Serializability (tt) § Xét lịch S7 như sau: T1 T2 S7 1 Read(A) 2 Read(A) 3 Write(A) 4 Write(A) § Lịch S7 trên có thỏa Conlict Serializability hay không ? 40
Conflict Serializability (tt) § Xét lịch S8 như sau: T1 T2 S8 1 Read(A) 2 Write(A) 3 Read(A) 4 Write(A) 5 Read(B) 6 Write(B) 7 Read(B) 8 Write(B) § Lịch S8 trên có thỏa Conlict Serializability hay không ? 41
Kiểm tra Conflict Serializability § Cho lịch S9: – S9 có conlict serializability hay không ? § Ý tưởng: – Các hành động xung đột trong lịch S được thực hiện theo thứ tự nào thì các giao tác thực hiện chúng trong S’ (kết quả sau hoán vị) cũng theo thứ tự đó. T1 T2 T1 T2 S9 S9’ Read(A) Read(A) Write(A) Write(A) Read(A) Read(B) Write(A) Write(B) Read(B) Read(A) Write(B) Write(A) Read(B) Read(B) Write(B) Write(B) 42
Kiểm tra Conflict Serializability § Cho lịch S có 2 giao tác T1 và T2: – T1 thực hiện hành động A1 – T2 thực hiện hành động A2 – Ta nói T1 thực hiện trước hành động T2 trong S, ký hiệu T1 <S T2, khi: • A1 được thực hiện trước A2 trong S – A1 không nhất thiết phải liên tiếp A2 • A1 và A2 là 2 hành động xung đột (A1 và A2 cùng thao tác lên 1 đơn vị dữ liệu và có ít nhất 1 hành động là ghi trong A1 và A2) 43
Kiểm tra Conflict Serializability Phương pháp Precedence Graph: § Cho lịch S bao gồm các thao tác T1, T2, , Tn § Đồ thị trình tự của S (Precedence graph) của S ký hiệu là P(S) có: – Đỉnh là các giao tác Ti – Cung đi từ Ti đến Tj nếu Ti <S Tj § S Conlict Serializable khi và chỉ khi P(S) không có chu trình § Thứ tự hình học các đỉnh là thứ tự của các giao tác trong lịch tuần tự tương đương với S. § Với 2 lịch S và S’ được lập từ cùng các giao tác, S và S’ conlict equivalent khi và chỉ khi P(S)=P(S’) 44
Kiểm tra Conflict Serializability § Ví dụ 1: S10 có Conlict Serializability hay không ? T T T S 1 2 3 10 2 3 Read(A) Read(B) Write(A) Read(A) Write(B) Write(A) Read(B) 1 2 Write(B) ¯ P(S10 ) không có chu trình 1 2 3 ¯ S10 conlict-serializable theo thứ tự T1, T2, T3 45
Kiểm tra Conflict Serializability § Ví dụ 1: S10 có Conlict Serializability hay không ? T1 T2 T3 T1 T2 T3 S10 S Read(A) Read(B) Read(B) Write(B) Write(A) Read(A) Read(A) Write(B) Write(A) Write(A) Read(B) Read(B) Write(B) Read(A) Write(B) Write(A) 46
Kiểm tra Conflict Serializability § Ví dụ 2: S11 có Conlict Serializability hay không ? S11: r2(A) r1(B) w2(A) r2(B) r3(A) w1(B) w3(A) w2(B) T1 T2 T3 S11 2 3 Read(A) Read(B) Write(A) Read(B) 2 1 Read(A) Write(B) Write(A) 1 2 Write(B) ¯ P(S11) có chu trình 1 2 3 ¯ S11 không conlict-serializable 47
Bài tập Conflict-Serializability § Cho các lịch S sau: 1. S: w1(A) r2(A) r3(A) w4 (A) 2. S: w3(A) w2(C) r1(A) w1(B) r1(C) w2(A) r4(A) w4(D) 3. S: r1(A) w2(A) w1(A) w3(A) 4. S: r2(B) w2(A) r1(A) r3(A) w1(B) w2(B) w3(B) 5. S: w1(X) w2(Y) w2(X) w1(X) w3(X) 6. S: r2(A) r1(B) w2(A) r3(A) w1(B) r2(B) w2(B) 7. S: r2(A) r1(B) w2(A) r2(B) r3(A) w1(B) w3(A) w2(B) § Vẽ P(S) § S có conlict-serializable không? Nếu có thì S tương đương với lịch tuần tự nào ? 48
Bài tập 1 § Cho lịch S: S: w1(A) r2(A) r3(A) w4 (A) T1 T2 T3 T4 S Write(A) Read(A) Read(A) Write(A) § Vẽ P(S) § S có conlict-serializable không? 49
Bài tập 2 § Cho lịch S: S: w3(A) w2(C) r1(A) w1(B) r1(C) w2(A) r4(A) w4(D) T1 T2 T3 T4 S Write(A) Write(C) Read(A) Write(B) Read(C) Write(A) Read(A) § Vẽ P(S) Write(D) § S có conlict-serializable không? 50
Bài tập 3 § Cho lịch S: S: r1(A) w2(A) w1(A) w3(A) T1 T2 T3 S Read(A) Write(A) Write(A) Write(A) § Vẽ P(S) § S có conlict-serializable không? 51
Bài tập 4 § Cho lịch S: S: r2(B) w2(A) r1(A) r3(A) w1(B) w2(B) w3(B) § Vẽ P(S) § S có conflict-serializable không ? 52
Bài tập 5 § Cho lịch S: S: w1(X) w2(Y) w2(X) w1(X) w3(X) S § Vẽ đồ thị P(S) § S có conflict serializable hay không ? 53
View-Serializability § Xét lịch S T1 T2 T3 S 1 2 Read(A) Write(A) Write(A) 3 Write(A) ¯ P(S) có chu trình ¯ S khả tuần tự hay không ? ¯ S không conflict-serializable 54
View-Serializability (tt) § So sánh lịch S và 1 lịch tuần tự S’ – Giả sử trước khi lịch S thực hiện, có giao tác Tb thực hiện việc ghi A và sau khi S thực hiện có giao tác Tf thực hiện việc đọc A. – Nhận xét lịch S và S’: • Đều có T1 thực hiện read(A) từ giao tác Tb à Kết quả đọc luôn giống nhau • Đều có T3 thực hiện việc ghi cuối cùng lên A. T2, T3 không có lệnh đọc A à Dù S hay S’ được thực hiện thì kết quả đọc A của Tf luôn giống nhau à Kết quả của S và S’ giống nhau à S vẫn khả tuần tự T1 T2 T3 T1 T2 T3 S S’ Read(A) Read(A) Write(A) Write(A) Write(A) Write(A) Write(A) Write(A) Không conlict-serializable Serial 55
View-Serializability (tt) § Khả tuần tự View (View-serializability): – Một lịch S được gọi là khả tuần tự view nếu tồn tại một lịch tuần tự S’ được tạo từ các giao tác của S sao cho S và S’ đọc và ghi những giá trị giống nhau. – Lịch S được gọi là khả tuần tự view khi và chỉ khi nó tương đương view (view-equivalent) với một lịch tuần tự S’ 56
View-Serializability (tt) § Ví dụ: Cho lịch S và S’ như sau: S : r2(B) w2(A) r1(A) r3(A) w1(B) w2(B) w3(B) S’: r2(B) w2(A) w2(B) r1(A) w1(B) r3(A) w3(B) T1 T2 T3 T1 T2 T3 S S Read(B) Read(B) Write(A) Write(A) Read(A) Write(B) Read(A) Read(A) Write(B) Write(B) Write(B) Write(B) Read(A) Write(B) S khả tuần tự view 57
View-Serializability (tt) § View-equivalent: S và S’ là những lịch view-equivalent nếu thỏa các điều kiện sau: – Nếu trong S có Ti đọc giá trị ban đầu của A thì nó cũng đọc giá trị ban đầu của A trong S’. – Nếu Ti đọc giá trị của A được ghi bởi Tj trong S thì Ti cũng phải đọc giá trị của A được ghi bởi Tj trong S’. – Với mỗi dvdl A, giao tác thực hiện lệnh ghi cuối cùng lên A (nếu có) trong S thì giao tác đó cũng phải thực hiện lệnh ghi cuối cùng lên A trong S’. § Một lịch giao tác S là view-serializable: – Nếu S là view-equivalent với một Lịch giao tác tuần tự S’ nào đó § Nếu S là conlict-serializable à S view-serializable. ß Chứng minh (*) 58
View Serializability () Lịch thao tác View-Serializable Conlict- Serializable 59
Kiểm tra View Serializability § Cho 1 Lịch giao tác S § Thêm 1 giao tác cuối Tf vào trong S sao cho Tf thực hiện việc đọc hết tất cả đơn vị dữ liệu ở trong S – S = w1(A) w2(A) rf(A) § Thêm 1 giao tác đầu tiên Tb vào trong S sao cho Tb thực hiện việc ghi các giá trị ban đầu cho tất cả đơn vị dữ liệu – S = wb(A) w1(A) w2(A) 60
Kiểm tra View-Serializability (tt) § Vẽ đồ thị phức (PolyGraph) cho S, ký hiệu G(S) với – Đỉnh là các giao tác Ti (bao gồm cả Tb và Tf) – Cung: • (1) Nếu giá trị mà ri(X) đọc được là do Tj ghi (ri(X) có gốc là Tj) thì vẽ cung đi từ Tj đến Ti X j i • (2) Với mỗi wj(X) ri(X), xét wk(X) khác Tb sao cho Tk không chèn vào giữa Tj và Ti 61
Kiểm tra View-Serializability (tt) • (2a) Nếu Tj ≠ Tb và Ti ≠ Tf thì vẽ cung Tk → Tj và Ti → Tk Tk Tj Ti Tj Ti Tk Write(X) Write(X) Write(X) Read(X) Read(X) Write(X) X X X X k j i j i k X X Tk có thể nằm trước Tj hoặc sau Ti 62
Kiểm tra View-Serializability (tt) • (2b) Nếu Tj = Tb thì vẽ cung Ti → Tk • (2c) Nếu Ti = Tf thì vẽ cung Tk → Tj Tj = Tb Ti Tk Tk Tj Ti = Tf Write(X) Write(X) Write(X) Read(X) Read(X) Write(X) X X X X j i k k j i 63
Ví dụ Tb T1 T2 T3 Tf S’ T1 T2 T3 S Write(A) Read(A) Read(A) Write(A) Write(A) Write(A) Write(A) Write(A) Write(A) Read(A) A A b 1 2 3 f 64
Ví dụ Tb T1 T2 T3 Tf S’ T1 T2 T3 S Write(A) Read(A) Read(A) Write(A) Write(A) Write(A) Write(A) Write(A) Write(A) Read(A) A A A b 1 2 3 f A 65
Ví dụ (tt) Tb T1 T2 T3 Tf S’ T1 T2 T3 S Write(A) Read(A) Read(A) Write(A) Write(A) Write(A) Write(A) Write(A) Write(A) Read(A) A ¯ G(S) không có chu trình A A A A b 1 2 3 f ¯ S view-serializable theo thứ A tự Tb, T1, T2, T3, Tf 66
Ví dụ (tt) Tb T1 T2 T3 Tf S’ T1 T2 T3 S Write(A) Read(A) Read(A) Write(A) Write(A) Read(A) Read(A) Write(A) Write(A) Write(A) Write(A) Read(A) A b 1 2 A 3 A f 67
Ví dụ (tt) Tb T1 T2 T3 Tf S’ T1 T2 T3 S Write(A) Read(A) Read(A) Write(A) Write(A) Read(A) Read(A) Write(A) Write(A) Write(A) Write(A) Read(A) A A b 1 2 A 3 A f A 68
Ví dụ (tt) Tb T1 T2 T3 Tf S’ T1 T2 T3 S Write(A) Read(A) Read(A) Write(A) Write(A) Read(A) Read(A) Write(A) Write(A) Write(A) Write(A) Read(A) A A A b 1 2 A 3 A f A A Chọn 1 trong 2 cung sao cho không có chu trình 69
Ví dụ (tt) Tb T1 T2 T3 Tf S’ T1 T2 T3 S Write(A) Read(A) Read(A) Write(A) Write(A) Read(A) Read(A) Write(A) Write(A) Write(A) Write(A) Read(A) A A A A b 1 2 A 3 A f A A A ¯ G(S) có chu trình 70
Ví dụ (tt) Tb T1 T2 T3 Tf S’ T1 T2 T3 S Write(A) Read(A) Read(A) Write(A) Write(A) Read(A) Read(A) Write(A) Write(A) Write(A) Write(A) Read(A) A A A b 1 2 A 3 A f A A A ¯ G(S) không có chu trình sau khỉ bỏ cung 71 ¯ S view-serializable
Bài tập View-Serializability § Cho lịch S: 1. S: r2(B) w2(A) r1(A) r3(A) w1(B) w2(B) w3(B) 2. S: w1(A) r3(A) r2(A) w2(A) r1(A) w3(A) 3. S: r2(A) r1(A) w1(C) r3(C) w1(B) r4(B) w3(A) r4(C) w2(D) r2(B) w4(A) w4(B) 4. S: w1(A) r2(A) w2(A) r1(A) 5. S: r1(A) r3(D) w1(B) r2(B) w3(B) r4(B) w2(C) r5(C) w4(E) r5(E) w5(B) 6. S: w1(A) r2(A) w3(A) r4(A) w5(A) r6(A) 7. S: r1(X) r2(X) w1(X) w2(X) § Yêu cầu: – Vẽ G(S) – S có view-serializable hay không ? 72
TÓM TẮT CHƯƠNG 2 § Một số tình huống về tranh chấp § Khái niệm giao tác § Tính chất ACID của giao tác § Lịch thao tác: – Lịch tuần tự – Lịch đồng thời – Lịch Khả tuần tự – Lịch khả tuần tự xung đột (Conlict Serializability) – Kiểm tra khả tuần tự xung đột bằng đồ thị trình tự (Prcedence graph) – Lịch khả tuần tự view (View Serializability) – Kiểm tra khả tuần tự view bằng đồ thị phức (Poly graph) 73
Bài tập T1 T2 T3 S Read(B) Write(A) Read(A) ¯ Vẽ G(S) Read(A) ¯ S có view-serializable? Write(B) Write(B) Write(B) 74
Bài tập (tt) T1 T2 T3 T4 S Read(A) Read(A) ¯ Vẽ G(S) Write(C) ¯ S có view-serializable? Read(C) Write(B) Read(B) Write(A) Read(C) Write(D) Read(B) Write(A) Write(B) 75
TÀI LIỆU THAM KHẢO § [1] Database Management Systems, 3rd Edition, Raghu Ramakrishnan and Johannes Gehrke § [2] Fundamentals of Database Systems, 4th Edition, Elmasri Navathe § [3] Database System Concepts, 4th Edition, Silberschatz−Korth −Sudarshan § [4] Database Systems Implementation, Hector Garcia-Molina, D. Ullman, Jennifer D. Widom § [5] Database systems: the complete book, Hector Garcia- Molina, Jeffrey D. Ullman, Jennifer Widom, Pearson Prentice Hall, 2009 76
TÀI LIỆU THAM KHẢO § § slides/slides3ed-english/Ch17_CC-95.pdf § and-conlict-serializable/ § § 77
LOGO HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU Chương 3: ĐIỀU KHIỂN TRUY XUẤT ĐỒNG THỜI GVLT: Nguyễn Trường Sơn 1
Nội dung trình bày § Phân loại các vấn đề của truy xuất đồng thời § Các kỹ thuật điều khiển đồng thời: – Kỹ thuật khoá (Locking) – Kỹ thuật nhãn thời gian (Timestamp) – Kỹ thuật xác nhận hợp lệ (Validation) § Vấn đề khoá chết § Các vấn đề khác 2
Nội dung trình bày § Phân loại các vấn đề của truy xuất đồng thời: – Mất dữ liệu cập nhật – Không đọc lại được dữ liệu – Bóng ma – Đọc phải dữ liệu rác § Các kỹ thuật điều khiển đồng thời: – Kỹ thuật khoá – Kỹ thuật nhãn thời gian – Kỹ thuật xác nhận hợp lệ § Vấn đề khoá chết § Các vấn đề khác 3
Vấn đề mất dữ liệu đã cập nhật § Xét 2 giao tác T1 và T2 và đơn vị dữ liệu A vốn có giá trị ban đầu là 50: – T1: Read(A); A:=A+10; Write(A) – T2: Read(A); A:=A+20; Write(A) A=50 T1 T2 t1 Read(A) « Nếu T1 và T2 thực hiện tuần tự t2 Read(A) (T1 rồi T2 hoặc T2 rồi T1) thì t3 A:=A+10 cuối cùng A = 80 t4 A:=A+20 « Nếu T1 và T2 thực hiện đồng t5 Write(A) thời như lịch bên: A = 70 t6 Write(A) Nhận xét: ² Dữ liệu do T1 ghi đã bị T2 làm mất ² Lỗi: MẤT DỮ LIỆU CẬP NHẬT (LOST UPDATE) 4
Vấn đề không thể đọc lại § Xét 2 giao tác T1 và T2 và đơn vị dữ liệu A vốn có giá trị ban đầu là 50 « Kết quả quan sát: A=50 T1 T2 ² Nếu T1 và T2 thực hiện t1 Read(A) tuần tự thì các lần đọc A của t2 Read(A) A=50 T2 giống nhau. t3 A:=A-10 ² Nếu T1 và T2 thực hiện t4 Print(A) A=50 đồng thời như lịch bên à 2 t5 Write(A) lần đọc dữ liệu của T2 có t6 Read(A) A=40 kết quả khác nhau t7 Print(A) A=40 « Lỗi không đọc lại được dữ liệu: ² Trong một giao tác mà các lần đọc cùng 1 đơn vị dữ liệu cho kết quả khác nhau 5
Vấn đề “bóng ma” § Xét 2 giao tác T1 và T2 được xử lý đồng thời – A là một tập các đơn vị dữ liệu a1, a2, a3, a4, – T1 xử lý trên toàn bộ tập A – Khi T1 đang xử lý, T2 thêm hay xóa một hay một số phần tử trong tập A T1 T2 t1 Read(A) t2 Xử lý 1 trên A t3 Thêm ai vào A t4 Xử lý 2 trên A t5 Xoá aj khỏi A t6 Xử lý 3 trên A 6
Vấn đề đọc dữ liệu rác § Xét 2 giao tác T1 và T2 được xử lý đồng thời – T2 đã đọc dữ liệu được ghi bởi T1 nhưng sau đó T1 yêu cầu hủy việc ghi A=50 T1 T2 t1 Read(A) t2 A:=A+10 t3 Write(A) t4 Read(A) t5 Print(A) t6 Abort 7
Nhận xét § Các lỗi truy xuất đồng thời của các giao tác T1, , Tn là do: – Kết quả của lịch tuần tự được lập từ các giao tác T1, , Tn và lịch đồng thời S từ các giao đó khác nhau: Không đảm bảo tính nhất quán dữ liệu. – Lịch đồng thời S không phải là một lịch khả tuần tự. § Câu hỏi: – Làm sao bộ lập lịch có thể tạo được một lịch S khả tuần tự ? Các kỹ thuật điều khiển đồng thời 8
Các kỹ thuật điều khiển đồng thời § Là 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. T1 T2 Tn Kỹ thuật khoá Bộ lập lịch Kỹ thuật nhãn thời gian Kỹ thuật xác nhận hợp lệ Lịch khả tuần tự 9
Nội dung trình bày § Các vấn đề của truy xuất đồng thời § Các kỹ thuật điều khiển đồng thời: – Kỹ thuật khoá  Khoá đơn giản  Khoá đọc ghi  Khoá đa hạt – Kỹ thuật nhãn thời gian  Nhãn thời gian toàn phần  Nhãn thời gian riêng phần  Nhãn thời gian nhiều phiên bản – Kỹ thuật lạc quan § Vấn đề khoá chết § Các vấn đề khác 10
Kỹ thuật khoá đơn giản § Kỹ thuật khoá đơn giản còn gọi khoá nhị phân (Binary locks) § Bộ lập lịch với cơ chế khóa đơn giản (locking scheduler) – Là bộ lập lịch với thêm 2 hành động :  Lock : Phát khoá  Unlock : Giải phóng khóa – Các khóa được ghi nhận trong bảng khóa (Lock Table) T1 T2 Tn Bảng Bộ lập lịch khóa Lịch khả tuần tự 11
Kỹ thuật khóa đơn giản § Quy định: – 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 1 yêu cầu xin khóa (lock) đơn vị dữ liệu đó  Ký hiệu: Lock(A) hay l(A) – Yêu cầu này được bộ phận quản lý khóa xử lý (Lock Manager)  Nếu yêu cầu được chấp thuận thì giao tác mới được phép đọc/ghi lên đơn vị dữ liệu  Yêu cầu xin khóa được bộ cấp phát 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 phải phát ra lệnh giải phóng đơn vị dữ liệu (unlock)  Ký hiệu: Unlock(A) hay u(A) BẢNG KHÓA Element Transaction Bảng khóa ghi nhận giao tác T1 đang giữ khóa A T1 trên đơn vị dữ liệu A 12
Kỹ thuật khóa đơn giản (tt) § Quy tắc: – 1. Giao tác đúng đắn: Việc giao tác Ti đọc hay ghi lên đơn vị dữ liệu A phải sau khi Ti phát khoá trên A và trước khi Ti giải phóng khoá trên A. Phát khoá và giải phóng khoá phải đi đôi với nhau (lock trước, unlock sau)  Ti: l(A) r(A) / w(A) u(A) – 2. Lịch thao tác hợp lệ: Khi Ti đang giữ khoá trên một đơn vị dữ liệu A thì không Ti nào khác được phát khoá trên A.  S: li(A) ui(A) Không được có l (A) j 13
Kỹ thuật khóa đơn giản (tt) T1 T2 S Lock(A) § Ví dụ: Read(A, t) – Giao tác T1 và T2 có đúng t := t + 100 Write(A, t) đắn hay không ? Unlock(A) Lock(A) Read(A, s) – Lịch S có hợp lệ hay không ? s := s * 2 Write(A, s) Unlock(A) Lock(B) Read(B, s) s := s * 2 Write(B, s) Unlock(B) Lock(B) Read(B, t) t := t + 100 Write(B, t) Unlock(B) 14
Kỹ thuật khóa đơn giản (tt) § Ví dụ S1 T1 T2 T3 S2 T1 T2 T3 Lock(A) Lock(A) Lock(B) Read(A) Read(A) Write(B) Write(B) Unlock(A) Lock(B) Unlock(B) Unlock(A) Lock(B) Unlock(B) Read(B) Read(B) Write(B) Write(B) Lock(B) Unlock(B) Read(B) Lock(B) Unlock(B) Read(B) Unlock(B) Cho biết lịch nào hợp lệ? Giao tác nào là đúng đắn ? 15
Kỹ thuật khóa đơn giản (tt) § Ví dụ: S1 T1 T2 T3 S2 T1 T2 T3 Lock(A) Lock(A) Lock(B) Read(A) Read(A) Write(B) Write(B) Unlock(A) Lock(B) Unlock(B) Unlock(A) Lock(B) Unlock(B) Read(B) Read(B) Write(B) Write(B) Lock(B) Unlock(B) Read(B) Lock(B) Unlock(B) Read(B) Unlock(B) Cho biết lịch nào hợp lệ? Giao tác nào là đúng đắn ? 16
Kỹ thuật khóa đơn giản (tt) § Bài toán: Kiểm tra tính khả tuần tự của lịch S – 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? § Phương pháp: Xây dựng 1 đồ thị có hướng G – B1: Mỗi giao tác Ti là 1 đỉnh của đồ thị – B2: Nếu một giao tác Tj phát ra Lockj(A) sau một giao tác Ti phát ra Unlocki(A) thì sẽ vẽ cung từ Ti đến Tj , i ≠ j – B3: S khả tuần tự nếu G không có chu trình 17
Kỹ thuật khóa đơn giản (tt) T1 T2 S Lock(A) Read(A, t) Lịch S có khả tuần tự hay không ? t := t + 100 Write(A, t) Unlock(A) Lock(A) Read(A, s) s := s * 2 Write(A, s) Unlock(A) Lock(B) Read(B, s) s := s * 2 Write(B, s) Unlock(B) Lock(B) Read(B, t) t := t + 100 Write(B, t) Unlock(B) 18
Kỹ thuật khóa đơn giản (tt) T1 T2 S Lock(A) Read(A, t) Lịch S có khả tuần tự hay không ? t := t + 100 Write(A, t) Unlock(A) Lock(A) Read(A, s) s := s * 2 Write(A, s) B1 T1 T2 G Unlock(A) Lock(B) B2 Read(B, s) s := s * 2 B3 G có chu trình à S không khả tuần Write(B, s) tự Unlock(B) Lock(B) Read(B, t) t := t + 100 Write(B, t) Unlock(B) 19
Kỹ thuật khóa đơn giản (tt) § Mục tiêu: Vậy làm sao để kỹ thuật khóa cho ta lịch khả tuần tự § Giải pháp : Tuân theo quy tắc sau: – (1) và (2): Giống như cũ – (3) Giao tác phải thỏa nghi thức khóa 2 giai đoạn (2PL: two phases locking) : Trong 1 giao tác, tất cả các thao tác phát khóa đều xảy ra trước tất cả các thao tác giải phóng khóa. T : .l(A) l(B) u(A) u(B) Không có giải Không có phát phóng bất kỳ ra bất kỳ khóa nào khóa nào § Định lý: – Nếu lịch S thoả nghi thức 2PL thì S conlict-serializable 20
Nghi thức khoá 2 giai đoạn § Nghi thức khoá 2 giai đoạn chia việc xin khoá và giải phóng khoá của giao tác thành 2 giai đoạn (phase) phân biệt: growing shrinking – Growing phase (pha phát khoá): #lock phase phase được  Giao tác chỉ được phép xin khoá chứ không giữ được phép giải phóng khoá trong pha này bởi Ti (số lượng khoá được giữ chỉ được phép ngày càng tăng)  Giai đoạn này kết thúc ở lệnh xin khoá cuối cùng. time – Shrinking phase (pha giải phóng khoá):  Giao tác chỉ được phép giải phóng khoá chứ không được phép xin khoá trong pha này  Giao tác này bắt đầu từ khi lệnh giải phóng khoá đầu tiên. 21
Tại sao lại cần nghi thức khoá 2 giai đoạn ? § 22
Kỹ thuật khóa đơn giản (tt) T1 T2 T3 T4 Lock(A) Lock(B) Lock(B) Lock(A) Read(A) Read(B) Read(B) Read(A) Lock (B) Lock(A) B=B-50 Unlock(A) Read(B) Read(A) Write(B) Lock(B) B:= B + A Unlock(B) Unlock(B) Read(B) Write(B) A:= A+B Lock(A) Unlock(B) Unlock(A) Write(A) Read(A) Print (A+B) Unlock(B) Unlock(A) A:=A+50 Write(A) Unlock(A) Giao tác nào thoả nghi thức 2 giai đoạn ? 23
Kỹ thuật khóa đơn giản (tt) T1 T2 T3 T4 Lock(A) Lock(B) Lock(B) Lock(A) Read(A) Read(B) Read(B) Read(A) Lock (B) Lock(A) B=B-50 Unlock(A) Read(B) Read(A) Write(B) Lock(B) B:= B + A Unlock(B) Unlock(B) Read(B) Write(B) A:= A+B Lock(A) Unlock(B) Unlock(A) Write(A) Read(A) Print (A+B) Unlock(B) Unlock(A) A:=A+50 Write(A) Thỏa nghi thức khóa 2 giai Unlock(A) đoạn Không thỏa nghi thức khóa 2 giai đoạn 24
Kỹ thuật khóa đơn giản (tt) T1 T2 T1 T2 S S Read(A,t) Lock(A); Read(A,t) t:=t+100 t:=t+100; Write(A,t) Write(A,t) Lock(B); Unlock(A) Read(A,s) Lock(A); Read(A,s) s:=s*2 s:=s*2; Write(A,s) Write(A,s) Lock(B) Không phát khóa Read(B,t) Read(B,t); t:=t+100 được, phải chờ t:=t+100 Write(B,t); Unlock(B) đến lúc này Write(B,t) Lock(B); Ulock(A) Read(B,t) Read(B,t); t:=t*2 t:=t*2 Write(B,t); Unlock(B) Write(B,t) 25
Kỹ thuật khóa đơn giản (tt) § Vấn đề khoá chết (Dead lock): Hiện tượng chờ khi cần phát khóa có thể dẫn đến chờ lẫn nhau vĩnh viễn T1 T2 S Lock(A) Ngăn cản Read(A,t) Lock(B) Read(B,s) t:=t+100 Ngăn cản s:=s*2 Write(A,t) Write(B,s) Lock(B) Lock(A) 26
Kỹ thuật khoá đơn giản (tt) § Ngăn ngừa khoá chết: – Mọi giao tác phải xin khoá 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 thì phải giải giải phóng tất cả khoá được cấp trên các đơn vị dữ liệu. § Phát hiện khoá chết: – Xây dựng đồ thị chờ (Waiting graph):  Mỗi giao tác Ti là một node của đồ thị G  Nếu có giao tác Tj phát ra yêu cầu khoá đơn vị dữ liệu A đã bị khoá trước đó bởi Ti, thì vẽ cung có hướng từ Ti à Tj (Biểu diễn việc Tj phải chờ Ti)  Nếu G xuất hiện chu trình à Xảy ra tình trạng khoá chết 27
Nội dung trình bày § Các vấn đề của truy xuất đồng thời § Các kỹ thuật điều khiển đồng thời: – Kỹ thuật khoá  Khoá đơn giản  Khoá đọc ghi  Khoá đa hạt – Kỹ thuật nhãn thời gian  Nhãn thời gian toàn phần  Nhãn thời gian riêng phần  Nhãn thời gian nhiều phiên bản – Kỹ thuật lạc quan § Vấn đề khoá chết § Các vấn đề khác 28
Kỹ thuật khóa đọc ghi § Vấn đề tồn tại của 2PL theo kỹ thuật khoá đơn giản: – Có những tình huống mà Ti không thực sự cần phải ngăn cản một Tj truy xuất đơn vị dữ liệu của nó, nhưng theo 2PL vẫn phải ngăn cản – Không tối ưu về mặt tốc độ vì có những khoảng chờ không cần thiết, thậm chí gây nên deadlock § Do đó, bộ lập lịch cần các hành động: – Khóa đọc (Read lock, Shared lock)  Ký hiệu : RLock(A) hay rl(A) – Khóa ghi (Write lock, Exclusive lock)  Ký hiệu : WLock(A) hay wl(A) – Giải phóng khóa  Ký hiệu : Unlock(A) hay u(A) 29
Kỹ thuật khóa đọc ghi (tt) § Cho 1 đơn vị dữ liệu A bất kỳ – WLock(A)  Hoặc có 1 khóa ghi duy nhất lên A  Hoặc không có khóa ghi nào lên A – RLock(A)  Có thể có nhiều khóa đọc được thiết lập lên A § Ma trận tương thích: Yêu cầu khoá RLock(A) WLock(A) Trạng RLock(A) ✔ ✖ thái hiện hành WLock(A) ✖ ✖ ✔ Tương thích ✖ Không tương thích 30
Kỹ thuật khóa đọc ghi (tt) § Giao tác T muốn Write(A): – Yêu cầu WLock(A)  WLock(A) sẽ được chấp thuận nếu hiện không có khóa nào trên A  Từ đó sẽ không có giao tác nào khác nhận được WLock(A) hay RLock(A) cho đến khi T giải phóng khóa trên A § Giao tác muốn Read(A): – Yêu cầu RLock(A) hoặc WLock(A)  RLock(A) sẽ được chấp thuận nếu A không đang giữ một WLock nào  Từ đó sẽ không có giao tác nào khác nhận được WLock(A) cho đến khi T giải phóng khóa trên A. Nhưng không ngăn chặn các thao tác khác cùng xin Rlock(A) nên các giao tác không cần phải chờ nhau khi đọc A § Sau khi thao tác xong thì giao tác phải giải phóng khóa trên đơn vị dữ liệu A 31
Kỹ thuật khóa đọc ghi (tt) § Qui tắc – (1) Giao tác đúng đắn :  Đã có phát khóa thì sau đó phải có giải phóng khóa, giải phóng khóa chỉ có khi trước đó có phát khóa mà chưa giải phóng  Thao tác đọc chỉ được thực hiện sau khi phát khóa đọc hoặc ghi và trước khi giải phóng khóa ấy  Thao tác ghi chỉ được thực hiện sau khi phát khóa ghi và trước khi giải phóng khóa ghi ấy  Các thao tác đọc, ghi, phát khóa và giải phóng khóa đề cập trên đây là xét trong cùng một giao tác và trên cùng 1 đơn vị dữ liệu 32
Kỹ thuật khóa đọc ghi (tt) § Qui tắc – (2) - Lịch thao tác hợp lệ  Khi Ti đang giữ khóa đọc trên 1 đơn vị Dữ liệu A thì không một Tj nào khác được phép ghi trên A  Khi Ti đang giữ khóa ghi trên 1 đơn vị Dữ liệu A thì không một Tj nào khác được phép đọc hay ghi trên A 33
Kỹ thuật khóa đọc ghi (tt) § Qui tắc – (3) - Giao tác 2PL  Ngoại trừ trường hợp nâng cấp khóa, các trường hợp còn lại đều giống với nghi thức khóa hai giai đoạn  T : rli(A) wli(A) ui(A) Không có giải Không có phát phóng bất kỳ ra bất kỳ khóa khóa nào nào  Trường hợp nâng cấp khóa được giải phóng khóa đọc trong pha phát khóa  T : rli(A) . uli(A) .wli(A) ui(A) Chấp nhận giải phóng khóa đọc khi nâng cấp khóa § Định lý : – S thoả (1), (2) và (3) à S conlict-serializable 34
Ví dụ T T 1 2 1. Giao tác nào đúng đắn ? S1 RLock(A) 2. Lịch thao tác có hợp lệ hay không ? Read(A) 3. Giao tác nào không thoả nghi thức 2PL ? U(A) RLock(B) 4. S có khả tuần tự ? Read(B) U(B) WLock(A) Read(A) A:=A+B Write(A) U(A) WLock(B) Read(B) B:=B+A Write(B) U(B) 35
Ví dụ T T 1 2 1. Giao tác nào đúng đắn ? S1 RLock(A) 2. Lịch thao tác có hợp lệ hay không ? Read(A) 3. Giao tác nào không thoả nghi thức 2PL ? U(A) RLock(B) 4. S có khả tuần tự ? Read(B) U(B) WLock(A) Read(A) A:=A+B Write(A) U(A) WLock(B) Read(B) B:=B+A Write(B) U(B) 36
Ví dụ T1 T2 T3 T4 1. Giao tác nào đúng đắn ? S2 RL(A) 2. Lịch thao tác có hợp lệ hay không ? RL(A) 3. Giao tác nào không thoả nghi thức 2PL ? WL(B) U(A) 4. S có khả tuần tự ? WL(A) U(B) RL(B) U(A) RL(B) RL(A) U(B) WL(C) U(A) WL(B) U(B) U(B) U(C) 37
Ví dụ T1 T2 T3 T4 1. Giao tác nào đúng đắn ? S2 RL(A) 2. Lịch thao tác có hợp lệ hay không ? RL(A) 3. Giao tác nào không thoả nghi thức 2PL ? WL(B) U(A) 4. S có khả tuần tự ? WL(A) U(B) RL(B) U(A) RL(B) RL(A) U(B) WL(C) U(A) WL(B) U(B) U(B) U(C) 38
Kỹ thuật khóa đọc ghi (tt) § Vấn đề nâng cấp khoá của nhiều giao tác có thể dẫn đến deadlock T1 T2 S RLock(A) Read(A) RLock(A) Read(A) Không xin WLock(A) được lock Write(A) Không xin ↓ U(A) WLock(A) được lock Chờ Write(A) ↓ U(A) Chờ Nâng cấp khoá: Giao tác đầu tiên đọc dữ liệu và sao đó cũng ghi lên đơn vị dữ liệu đó. 39
Kỹ thuật khóa đọc ghi (tt) § Khóa cập nhật (update lock) – ULock(A) – Giao tác muốn read(A) và sau đó cũng muốn write(A)  Yêu cầu ULock(A)  ULock(A) được chấp thuận khi A tự do hoặc đang giữ RLock – Khi đó, không có giao tác nào nhận được RLock(A), WLock(A) hay ULock(A) – Ma trận tương thích Yêu cầu khoá RLock WLock ULock RLock ✔ ✖ ✔ Trạng thái ✖ ✖ ✖ hiện hành WLock ULock ✖ ✖ ✖ 40
Kỹ thuật khóa đọc ghi (tt) § Sử dụng khoá cập nhật thể tránh được deadlock T1 T2 S ULock(A) Read(A) ULock(A) Read(A) Denied !!! Write(A) U(A) ULock(A) Read(A) Write(A) U(A) 41
Nội dung trình bày § Các vấn đề của truy xuất đồng thời § Các kỹ thuật điều khiển đồng thời: – Kỹ thuật khoá  Khoá đơn giản  Khoá đọc ghi  Khoá đa hạt – Kỹ thuật nhãn thời gian  Nhãn thời gian toàn phần  Nhãn thời gian riêng phần  Nhãn thời gian nhiều phiên bản – Kỹ thuật lạc quan § Vấn đề khoá chết § Các vấn đề khác 42
Kỹ thuật khóa đa hạt § Xét ví dụ hệ thống ngân hàng – Quan hệ TàiKhoản(mãTK, sốDư) – Giao tác gửi tiền và rút tiền  Khóa relation – Các giao tác thay đổi giá trị của 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 (Y khác X) cũng phải chờ à vô lý, tốc độ xử lý đồng thời chậm  Khóa tuple hay disk block – 2 tài khoản ở 2 blocks khác nhau có thể được cập nhật cùng thời điểm – Xử lý đồng thời nhanh – Giao tác tính tổng số tiền của các tài khoản  Khóa relation?  Khóa tuple hay disk block? 43
Kỹ thuật khóa đa hạt (tt) § Phải quản lý khóa ở nhiều mức độ – Tính chất hạt (granularity) : Tính hạt càng tăng khi đơn vị dữ liệu bị khóa càng lớn – Tính đồng thời (concurrency) : Tính đồng thời càng tăng khi đơn vị dữ liệu bị khóa càng nhỏ – Tình hạt tăng thì tính đồng thời giảm và ngược lại à phải thỏa hiệp Tính hạt tăng Quan hệ (Relation) Khối (Block) Bộ (Tuple) Tính đồng thời tăng 44
Kỹ thuật khóa đa hạt (tt) § Phân cấp Dữ liệu – 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) – Một block gồm 1 hoặc nhiều tuples Quan hệ (Relation) Khối (Block) Khối (Block) Khối (Block) Bộ (Tuple) Bộ (Tuple) Bộ (Tuple) Bộ (Tuple) Bộ (Tuple) Bộ (Tuple) Bộ (Tuple) Bộ (Tuple) 45
Kỹ thuật khóa đa hạt (tt) § Gồm các khóa – Khóa thông thường  Shared lock: S  Exclusive lock: X – Khóa cảnh báo (warning lock)  Warning (intention to) shared lock: IS  Warning (intention to) exclusive lock: IX 46
Kỹ thuật khóa đa hạt (tt) § Ma trận tương thích trên cùng một node – Cho biết các khóa có thể cùng tồn tại trên 1 node dữ liệu IS IX S X IS ✔ ✔ ✔ ✖ IX ✔ ✔ ✖ ✖ S ✔ ✖ ✔ ✖ X ✖ ✖ ✖ ✖ 47
Kỹ thuật khóa đa hạt (tt) § Ma trận tương thích giữa node cha và node con – Cho biết các khóa có thể phát trên node con khi node cha đang có một khoá nào đó à Cho biết muốn phát 1 khóa trên node con thì trước đó phải phát khóa nào trên node cha Node cha đã khoá Node con có thể khoá bằng phương thức bằng các phương thức IS IS, S IX IS, S, IX, X S S, IS X Không có 48
Kỹ thuật khóa đa hạt (tt) § Quy tắc: – (1) Thỏa ma trận tương thích trên cùng một node – (2) Khóa nút gốc của cây trước – (3) Thỏa ma trận tương thích giữa node cha và node con – (4) Ti thỏa 2PL – (5) Ti có thể giải phóng nút Q khi không có nút con nào của Q bị khóa bởi Ti – (6) Trong trường hợp thêm mới hay xóa bỏ một node Q thì cha của Q phải được khóa bằng X trước à tránh Phantom 49
Bài tập § T2 có thể truy xuất f2.2 bằng khóa X được không? § T2 sẽ có những khóa gì? T1(IX) R1 t 1 t4 T (IX) 1 t2 t3 T (X) f f 1 2.1 2.2 f3.1 f3.2 50
Bài tập § T2 có thể truy xuất f2.2 bằng khóa X được không? § T2 sẽ có những khóa gì? T1(IX) T2(IX) R1 t 1 t4 T (IX) T (IX) 1 t2 2 t3 T (X) f f 1 2.1 2.2 f3.1 f3.2 T2(X) 51
Bài tập (tt) T1(IX) R1 t1 T1(X) t4 t2 T2(IX) t3 f f 2.1 2.2 f3.1 f3.2 T2(X) § T2 có thể truy xuất f2.2 bằng khóa X được không? § T2 sẽ có những khóa gì? 52
Bài tập (tt) T1(IS) R1 t1 t4 T1(S) t2 t3 f f 2.1 2.2 f3.1 f3.2 § T2 có thể truy xuất f3.1 bằng khóa X được không? § T2 sẽ có những khóa gì? 53
Bài tập (tt) T2(IX) T1(IS) R1 t1 t4 T1(S) t2 t3 T2(IX) f f 2.1 2.2 f3.1 f3.2 T2(X) § T2 có thể truy xuất f3.1 bằng khóa X được không? § T2 sẽ có những khóa gì? 54
Kỹ thuật khóa đa hạt (tt) T1 § Vấn đề select * from MãTK SốDư MãChiNhánh TaiKhoan where A-101 500 Mianus maCN=“Mianus” Tài T2 Khoản A-215 700 Mianus update TaiKhoan set A-102 400 Perryride soDu=400 where A-201 900 Mianus maCN=“Perryride” T13(IS) Tài Khoản T2(IX) T3 select sum(soDu) from TaiKhoan where maCN=“Minanus” Mianus Mianus Mianus Perryride T4 T13(S) TT (S) (S) T (X) 31 2 insert TaiKhoan valuse(A-201, 900, Mianus ) T3 có còn đúng không? 55
Nội dung trình bày § Các vấn đề của truy xuất đồng thời § Các kỹ thuật điều khiển đồng thời: – Kỹ thuật khoá  Khoá đơn giản  Khoá đọc ghi  Khoá đa hạt – Kỹ thuật nhãn thời gian  Nhãn thời gian toàn phần  Nhãn thời gian riêng phần  Nhãn thời gian nhiều phiên bản – Kỹ thuật xác nhận hợp lệ § Vấn đề khoá chết § Các vấn đề khác 56
Giới thiệu § Ý tưởng: – Mặc định cho rằng tất cả mọi thao tác của các giao tác dù diễn ra đồng thời cũng không gây mất nhất quán dữ liệu – Nếu lỡ có thao tác mang nguy cơ mất nhất quán dữ liệu à Hủy giao tác đó và chạy lại sau § Chọn một thứ tự thực hiện nào đó cho các giao tác bằng cách gán nhãn thời gian (timestamping) – Mỗi giao tác T sẽ được bộ lập lịch gán 1 nhãn thời gian, ký hiệu TS(T), nhãn này gán ngay lúc T bắt đầu bằng 1 trong 2 cách :  Đồng hồ máy tính  Bộ lập lịch tự đếm – Thứ tự của các nhãn tăng dần, Ti trễ hơn Tj thì TS(Ti) > TS(Tj) 57
Giới thiệu § Chiến lược cơ bản: – Nếu TS(Ti) < TS(Tj) thì lịch thao tác được phát sinh phải tương đương với lịch biểu tuần tự {Ti, Tj} 58
Nhãn thời gian toàn phần § Mỗi giao tác T khi phát sinh sẽ được gán 1 nhãn TS(T) ghi nhận lại thời điểm phát sinh của T § Mỗi đơn vị dữ liệu X cũng có 1 nhãn thời TS(X), nhãn này ghi lại TS(T) của giao tác T đã thao tác read/write thành công sau cùng lên X § Khi đến lượt giao tác T thao tác trên dữ liệu X, so sánh TS(T) và TS(X) – Nếu T muốn đọc X:  Nếu TS(T) ≥ TS(X) thì cho T đọc X và gán TS(X) = TS(T)  Ngược lại T bị hủy (abort) – Nếu T muốn ghi X:  Nếu TS(T) ≥ TS(X) thì cho T ghi X và gán TS(X) = TS(T)  Ngược lại T bị hủy (abort) 59
Nhãn thời gian toàn phần Read(T, X) Write(T, X) If TS(X) <= TS(T) If TS(X) <= TS(T) Read(X); //cho phép đọc X Write(X); //cho phép ghi TS(X):= TS(T); TS(X):= TS(T); Else Else Abort {T}; //hủy bỏ T Abort {T}; //hủy bỏ T 60
Ví dụ T1 T2 A B TS(T1)=100 TS(T2)=200 TS(A)=0 TS(B)=0 Read(A) TS(A)=100 TS(A) ≤ TS(T1) : T1 đọc được A Read(B) TS(B)=200 TS(B) ≤ TS(T2) : T2 đọc được B A=A*2 Write(A) TS(A)=100 TS(A) ≤ TS(T1) : T1 ghi lên A được B=B+20 Write(B) TS(B)=200 TS(B) ≤ TS(T2) : T2 ghi lên B được Read(B) TS(B) > TS(T1) : T1 không đọc được B T1 bị hủy, sau đó khởi động lại T1 với một nhãn thời gian mới 61
Nhãn thời gian toàn phần T1 T2 A T1 T2 A TS(T1)=100 TS(T2)=120 TS(A)=0 TS(T1)=100 TS(T2)=120 TS(A)=0 Read(A) TS(A)=100 Read(A) TS(A)=100 Read(A) TS(A)=120 Read(A) TS(A)=120 Write(A) TS(A)=120 Read(A) TS(A)=120 Write(A) Read(A) T1 bị huỷ và bắt đầu thực T1 bị huỷ và bắt đầu thực hiện với timestamp mới hiện với timestamp mới Mặc dù trong quản lý giao tác 2 hành động đọc/ghi có tác dụng rất khác nhau Sử dụng nhãn thời gian Không phân biệt tính chất của thao tác là đọc riêng phần hay ghi → T1 vẫn bị hủy và làm lại từ đầu với 1 timestamp mớI 62
Nội dung trình bày § Các vấn đề của truy xuất đồng thời § Các kỹ thuật điều khiển đồng thời: – Kỹ thuật khoá  Khoá đơn giản  Khoá đọc ghi  Khoá đa hạt – Kỹ thuật nhãn thời gian  Nhãn thời gian toàn phần  Nhãn thời gian riêng phần  Nhãn thời gian nhiều phiên bản – Kỹ thuật lạc quan § Vấn đề khoá chết § Các vấn đề khác 63
Nhãn thời gian riêng phần § Nhãn của đơn vị dữ liệu X được tách ra thành 2 loại: – RT(X) – read time of X  Ghi nhận TS(T) gần nhất (giao tác có nhãn thời gian lớn nhất) đọc X thành công – WT(X) – write time of X  Ghi nhận TS(T) gần nhất (giao tác có nhãn thời gian lớn nhất) ghi X thành công § Ngoài ra bộ lập lịch cũng quản lý trạng thái commit hay chưa của đơn vị dữ liệu X – C(X)= 1 nếu dữ liệu X đã được commit. Ngược lại C(X)=0 – Bộ lập lịch dựa vào hoạt động của các giao tác để gán nhãn C(X) lên các đơn vị dữ liệu. – Kỹ thuật này được sử dụng để tránh việc lỗi đọc phải dữ liệu rác. 64
Nhãn thời gian riêng phần § Công việc của bộ lập lịch: – Gán gắn các nhãn thời gian RT(X) và WT(X) và C(X) – Kiểm tra thao tác đọc/ghi xuất hiện khi nào để quyết định:  Chấp nhận yêu cầu  Trì hoãn giao tác  Huỹ bỏ giao tác  Bỏ qua hoạt động đó – Xử lý các tình huống:  Đọc quá trễ  Ghi quá trễ  Đọc dữ liệu rác  Quy tắc ghi Thomas 65
Nhãn thời gian riêng phần § Đọc quá trễ l T vào trước (TS(T) < TS(U)) muốn đọc X nhưng khi giá U ghi X T đọc X trị X hiện tại đã bị ghi bởi một giao tác khác vào sau T (TS(T) < WT(X) ) l T không nên đọc X do U ghi bởi vì T vào trước T bắt đầu U bắt đầu → Giải pháp: Hủy T 66
Nhãn thời gian riêng phần Ghi quá trễ § l T vào trước (TS(T) < TS(U)) và muốn ghi lên X, tuy nhiên X đã U đọc X bị đọc bởi một giao tác vào sau T ghi X T (WT(X) < TS(T) < RT(X) ) l T không nên ghi X do giao tác U đã đọc X. (U phải đọc giá trị do T ghi) T bắt đầu U bắt đầu → Giải pháp: Hủy T 67
Nhãn thời gian riêng phần § Đọc dữ liệu rác T ghi X U đọc X l T vào trước U và thực hiện việc ghi X trước. U vào sau và thực hiện việc đọc X. l Nhưng T hủy à giá trị X mà U đọc là giá trị rác T bắt đầu U bắt đầu T hủy à Giải pháp: U đọc X sau khi T commit hoặc sau khi T abort. 68
Nhãn thời gian riêng phần § Quy tắc ghi Thomas l T vào trước U vào sau nhưng khi T muốn ghi lên X thì U đã ghi lên U ghi X X trước (TS(T) < WT(X)) T ghi X l T nếu có ghi xong X cũng không làm được gì vì: § T không thể đọc X vì nếu đọc X thì sẽ dẫn đến đọc trễ § Các giao tác khác sau T và U T bắt đầu U bắt đầu thì muốn đọc giá trị X được ghi bởi U à Giải pháp: Bỏ qua thao thác ghi X của T [Quy tắc ghi Thomas] 69
Nhãn thời gian riêng phần § Vấn đề với quy tắc ghi Thomas l Trường hợp U ghi và sau đó bị U ghi X huỷ à giá trị được ghi bởi U đã T ghi X bị mất l Do T đã kết thúc à cần khôi phục lại giá trị X từ T mà lệnh ghi X đã bị bỏ qua T bắt đầu U bắt đầu T kết thúc U huỷ à Giải pháp: Khi T ghi X, nếu giao tác U đã commit thì bỏ qua T, hoặc đợi đến thời điểm U commit hoặc abort. 70
Nhãn thời gian riêng phần § Tóm lại khi có yêu cầu đọc và ghi từ giao tác T. Bộ lập lịch sẽ: – Đáp ứng yêu cầu – Hủy T và khởi tạo lại T với 1 timestamp mới  T rollback – Trì hoãn T, sau đó mới quyết định phải hủy T hoặc đáp ứng yêu cầu 71
Nhãn thời gian riêng phần § Quy tắc : – Nếu T cần đọc X  Nếu WT(X) ≤ TS(T) thì chờ cho X trở thành Dữ liệu đã Commit rồi cho T đọc X và gán RT(X) = MAX(RT(X), TS(T))  Ngược lại hủy T và khởi động lại T cới TS(T) mới (đọc quá trể) – Nếu T cần ghi X  Nếu RT(X) ≤ TS(T) – Nếu WT(X) ≤ TS(T) thì cho T ghi X và gán WT(X) = TS(T) – Ngược lại thì bỏ qua thao tác ghi này của T (không hủy T)  Ngược lại hủy T và khởi động lại T với TS(T) mới (ghi quá trễ) 72
Nhãn thời gian riêng phần (tt) Quy tắc: § If WT(X) <= TS(T) Read(X);//cho phép đọc X Read(T, X) RT(X):= max(RT(X),TS(T)); Else Rollback{T}; //hủy T và khởi tạo lại với TS mới If RT(X) <= TS(T) If WT(X) <= TS(T) Write(X);//cho phép ghi X Write(T, X) WT(X):= TS(T); Else Nếu X đã COMMIT à bỏ qua, ngược lại chờ cho đến khi giao tác thực hiện ghi trên X commit hoặc abort Else Rollback{T}; //hủy T và khởi tạo lại với TS mới 73
Ví dụ T1 T2 A B C RT(A)=0 RT(B)=0 RT(C)=0 TS(T1)=100 TS(T2)=200 WT(A)=0 WT(B)=0 WT(C)=0 RT(A)=100 WT(A) TS(T1) 7 Write(C) T1 không ghi lên C được Abort 74
Ví dụ (tt) T1 T2 T3 A B C RT=0 RT=0 RT=0 TS=200 TS=150 TS=175 WT=0 WT=0 WT=0 RT=200 Read(B) WT=0 RT=150 Read(A) WT=0 RT=175 Read(C) WT=0 RT=200 Write(B) WT=200 RT=150 Write(A) WT=200 Write(C) Write(A) Rollback Giá trị của A đã sao lưu bởi T1 → T3 không bị 75 rollback và không cần ghi A
Bài tập § Given the following sequence of events: – st1; st2; r1(A); r2(B); w2(A); w1(B) – st1; st2; st3; r1(A); r3(B); w1(C); r2(B); r2(C); w3(B); w2(A) § Task: Tell what happens as each event occurs for a timestamp based scheduler. 76
Ví dụ (tt) T1 T2 T3 T4 A RT=0 TS=150 TS=200 TS=175 TS=255 WT=0 RT=150 Read(A) WT=0 T3 bị hủy vì nó định RT=150 đọc giá trị A ghi bởi Write(A) WT=150 T2 (mà T2 lại có nhãn thời gian lớn hơn nó). RT=200 Read(A) WT=0 Giả sử T3 đọc giá trị A ghi bởi T1 thì T3 sẽ RT=200 Write(A) không bị hủy WT=200 Read(A) RT=255 Ý tưởng lưu giữ nhiều Read(A) WT=200 phiên bản của A Rollback 77
Nội dung trình bày § Các vấn đề của truy xuất đồng thời § Các kỹ thuật điều khiển đồng thời: – Kỹ thuật khoá  Khoá đơn giản  Khoá đọc ghi  Khoá đa hạt – Kỹ thuật nhãn thời gian  Nhãn thời gian toàn phần  Nhãn thời gian riêng phần  Nhãn thời gian nhiều phiên bản – Kỹ thuật xác nhận hợp lệ § Vấn đề khoá chết § Các vấn đề khác 78
Nhãn thời gian nhiều phiên bản § Ý tưởng – Cho phép thao tác read(A) của T3 thực hiện § Bên cạnh việc lưu trữ giá trị hiện hành của A, ta giữ lại các giá trị được sao lưu trước kia của A (phiên bản của A) § Giao tác T sẽ đọc được giá trị của A ở 1 phiên bản thích hợp nào đó 79
Nhãn thời gian nhiều phiên bản (tt) § Mỗi phiên bản của 1 đơn vị dữ liệu X có – RT(X)  Ghi nhận lại giao tác sau cùng đọc X thành công – WT(X)  Ghi nhận lại giao tác sau cùng ghi X thành công § Khi giao tác T phát ra yêu cầu thao tác lên X – Tìm 1 phiên bản thích hợp của X – Đảm bảo tính khả tuần tự § Một phiên bản mới của X sẽ được tạo khi hành động ghi X thành công 80
Nhãn thời gian nhiều phiên bản (tt) i=“số thứ tự phiên bản sau cùng nhất của X” § Quy tắc: While WT(Xi) > TS(T) i:=i-1;//lùi lại Read(Xi); Read(T, X) RT(Xi):= max(RT(Xi), TS(T)); i=“số thứ tự phiên bản sau cùng nhất của X” While WT(Xi) > TS(T) i:=i-1;//lùi lại If RT(Xi) > TS(T) Write(T, X) Rollback T//Hủy và khởi tạo TS mới Else Tạo phiên bản Xi+1; Write(Xi+1); RT(Xi+1) = 0;//chưa có ai đọc WT(X ) = TS(T); i+1 81
Ví dụ T1 T2 T3 T4 A0 A1 A2 RT=0 TS=150 TS=200 TS=175 TS=255 WT=0 RT=150 Read(A) WT=0 RT=0 Write(A) WT=150 RT=200 Read(A) WT=150 RT=0 Write(A) WT=200 RT=200 Read(A) WT=150 RT=255 Read(A) WT=200 82
Ví dụ (tt) T1 T2 A0 AB10 A2 B1 RT=0 RT=0 TS=100 TS=200 WT=0 WT=0 Read(A) RT=100 WT=0 Write(A) RT=0 RT=0 WT=200 WT=200 Write(B) RT=0 WT=200 Read(B) RT=100 WT=0 RT=0 Write(A) WT=100 83
Nhãn thời gian nhiều phiên bản (tt) § Nhận xét – Thao tác đọc  Giao tác T chỉ đọc giá trị của phiên bản do T hay những giao tác trước T cập nhật  T không đọc giá trị của các phiên bản do các giao tác sau T cập nhật → Thao tác đọc không bị rollback – Thao tác ghi  Thực hiện được thì chèn thêm phiên bản mới  Không thực hiện được thì rollback – Tốn nhiều chi phí tìm kiếm, tốn bộ nhớ – Nên giải phóng các phiên bản quá cũ không còn được các giao tác sử dụng 84
Tài liệu tham khảo § [5] Database systems: the complete book, Hector Garcia- Molina, Jeffrey D. Ullman, Jennifer Widom, Pearson Prentice Hall, 2009 – Chapter 18. Concurency Control 85
LOGO Q & A 86
Tóm tắt CHƯƠNG 3 § Các kỹ thuật điều khiển truy xuất đồng thời – Kỹ thuật khoá  Kỹ thuật khoá đơn giản  Kỹ thuật khoá đọc ghi  Nghi thức 2 giai đoạn  Khoá cập nhật  Các tình huống xảy ra deadlock, các loại deadlock  Khoá đa hạt – Kỹ thuật nhãn thời gian  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 87
Timestamp vs. Locking § Schedule allowed by locks but not timestamps § Schedule allowed by timestamps but not by locks: 88
Cascading Rollbacks § One transaction aborting can cause other transactions to abort. § T22 aborts ⇒ we have to rollback T23 and T24. § How to eliminate these cascading rollbacks? – Don't let transactions read “dirty” uncommitted data. 89
Strict Timestamp Based Concurrency Control § How to avoid cascading rollbacks? – Transactions should read only committed values. § Strict timestamp concurrency control protocol 90
SQL isolation levels § A transactions in SQL may be chosen to have one of four isolation levels: § ! READ UNCOMMITTED: ”No locks are obtained.” § ! READ COMMITTED: ”Read locks are immediately released – read values may change during the transaction.” § ! REPEATABLE READ: ”2PL but no lock when adding new tuples.” § ! SERIALIZABLE: ”2PL with lock when adding new tuples.” 91
Disadvantages of locking • Lock management overhead. • Deadlock detection/resolution. • Concurrency is signiicantly lowered, when congested nodes are locked. • To allow a transaction to abort itself when mistakes occur, locks can’t be released until the end of transaction, thus currency is signiicantly lowered • (Most Important) Conlicts are rare. (We might get better performance by not locking, and instead checking for conlicts at commit time.) 92
Optimism vs pessimism § ! Pessimistic concurrency is best in high- conlict situations: – ! Smallest number of aborts. – ! No wasted processing. § ! Optimistic concurrency control is best if conlicts are rare, e.g., if there are many read-only transactions. – ! Highest level of concurrency. – ! Hybrid solutions often used in practice. 93
Two-Phase Locking (2PL) . . . § Properties of the 2PL protocol – Generates conlict-serializable schedules – But schedules may cause cascading aborts ∗ If a transaction aborts after it releases a lock, it may cause other transactions that have accessed the unlocked data item to abort as well § Strict 2PL locking protocol – Holds the locks till the end of the transaction – Cascading aborts are avoided 94
Timestamp-based approach § Assumed Serial Schedule in Timestamp-based approach: – Conlict serializable schedule that is equivalent to a serial schedule in which the timestamp order of transactions is the order to execute them 95
Timestamp-based approach § Scheduler’s response to a T’s request – Grant the request – Abort and restart (roll back) T with a new timestamp – Delay T and later decide whether to abort T or to grant the request 96
THUẬT NGỮ § Bộ lập lịch § Bộ phận quản lý giao tác § Bảng khoá § Bộ phận quản lý đồng thời 97
LOGO HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU Chương 4: AN TOÀN VÀ AN NINH DỮ LIỆU GVLT: Nguyễn Trường Sơn 1
Nội dung trình bày § An toàn dữ liệu KHÔI PHỤC SAU SỰ CỐ – Phân loại sự cố – Nhật ký giao tác Từ khoá: – Điểm kiểm tra - database recovery - crash recovery – Undo loging – Redo loging – Undo / Redo loging § An ninh dữ liệu – Cơ chế phân quyền – Cơ chế mã hoá 2
Giới thiệu § Cơ sở dữ liệu luôn cần phải ở trạng thái nhất quán = đảm bảo tất cả các ràng buộc toàn vẹn (RBTV) § Nguyên nhân dẫn đến RBTV bị vi phạm: – Do chia sẽ dữ liệu (data sharing): Dữ liệu được chia sẽ cho nhiều giao tác cùng lúc Sử dụng các kỹ thuật quản lý giao tác và xử lý đồng thời – Do sự cố:  Lỗi lập trình của các giao tác  Lỗi lập trình của DBMS hoặc do hệ điều hành  Hư hỏng phần cứng & sự cố khác Sử dụng các kỹ thuật khôi phục sự cố 3
Các loại sự cố § Phân loại theo nguyên nhân: – Sự cố do nhập liệu sai – Errornous Data Entry – Sự cố trên thiết bị lưu trữ – Media failures – Sự cố giao tác – Transaction failures – Sự cố hệ thống – System failures § Phân loại theo tính chất: Mong muốn Sự cố Biết trước Không mong muốn Không biết trước 4
Sự cố do nhập liệu sai (Erroneous Data Entry) § Bao gồm: – Dữ liệu sai hiển nhiên: Là sự nhập sai dữ liệu mà máy tính có thể phát hiện được  Vd : Nhập thiếu 1 số trong dãy số điện thoại, nhập sai khóa ngoại, nhập chuỗi tràn, sai kiểu dữ liệu – Dữ liệu sai không hiển nhiên: Là sự nhập sai dữ liệu liên quan đến ngữ nghĩa mà máy tính khó có thể tự nó phát hiện được  Vd : Nhập sai 1 số trong dãy số điện thoại § Giải quyết: Hệ quản trị CSDL cung cấp các cơ chế cho phép phát hiện lỗi – Ràng buộc khóa chính, khóa ngoại – Ràng buộc miền giá trị – Trigger 5
Sự cố trên thiết bị lưu trữ (Media Failures) § Là những sự cố: – Là những sự cố gây nên việc mất hay không thể truy xuất dữ liệu ở bộ nhớ ngoài (ổ cứng, CD, băng từ )  Vd : Cháy nổ gây phá hủy thiết bị lưu trữ,  Vd : Đầu đọc của đĩa cứng hư, sector trên đĩa cứng hư, – Đây là loại sự cố nguy hiểm nhất, khó khôi phục trọn vẹn § Giải quyết: – Phải backup thường xuyên (toàn bộ hoặc chỉ phần thay đổi), chu kỳ không được quá thưa – Chạy nhiều bản CSDL song hành (1 bản chính – primary và nhiều bản phụ – minor) và thực hiện đồng bộ tức thì  Tốn thiết bị lưu trữ và đòi hỏi phần cứng rất mạnh  Kìm hãm tốc độ hệ thống  Bản minor phải đặt ở vị trí địa lý khác bản primary 6
Sự cố giao tác (Transaction Failures) § Sự cố làm cho 1 giao tác kết thúc không bình thường (không đến được lệnh commit hay lệnh rollback của chính nó) § Ví dụ – Chia cho không – Giao tác bị hủy – Dữ liệu nhập sai – Tràn số § Giải quyết : Khi giao tác T bị sự cố, DBMS sẽ – Hủy T và các giao tác bị quay lui dây chuyền theo nó – Tra lock-table và giải phóng các khóa mà các giao tác này đang giữ – Reset lại các giá trị mà các giao tác này đã ghi – Thực hiện lại tất cả các giao tác này 7
Sự cố hệ thống (System Failures) § Là những sự cố gây nên bởi – Lỗi phần cứng  Cúp điện  Hư bộ nhớ trong  Hư CPU – Lỗi phần mềm  Lỗi hệ điều hành  Lỗi DBMS § Giải quyết : Hệ quản trị CSDL cần cứu chữa và phục hồi dữ liệu – Nhật ký giao tác (transaction log) 8
Mục tiêu của khôi phục sự cố § Đưa dữ liệu về trạng thái sau cùng nhất trước khi xảy ra sự cố § Đảm bảo 2 tính chất của giao tác: – Nguyên tố (atomic) – Bền vững (durability) Query Transaction Log processor manager manager Buffer Recovery manager manager Data Log 9
Các thao tác đọc ghi dữ liệu trong DBMS 1 Input(X) 1 Chép DVDL X từ ổ đĩa sang vùng nhớ máy tính X (memory buffer) 2 Đọc đơn vị dữ liệu X vào t 3 (biến cục bộ của giao tác) Read(X,t) 2 Write(X,t) X 3 Ghi t vào đơn vị dữ liệu X t (memory buffer) Output(X) 4 Chép giá trị ĐVDL X từ Buffer Database 4 buffer xuống ổ đĩa máy tính Việc đọc / ghi dữ liệu trong DBMS thực chất là việc chuyển đổi các giá trị từ vào các không gian địa chỉ: Bộ nhớ ßà Ổ đĩa 10
Nội dung trình bày § An toàn dữ liệu – Phân loại sự cố – Nhật ký giao tác – Điểm kiểm tra  Điểm kiểm tra đơn giản  Điểm kiểm tra linh động – Undo loging – Redo loging – Undo / Redo loging § An ninh dữ liệu – Cơ chế phân quyền – Cơ chế mã hoá 11
Nhật ký giao tác § Nhật ký giao tác là một chuỗi các mẫu tin (log record) ghi lại các hành động của DBMS § Nhật ký là một tập tin tuần tự được lưu trữ trên bộ nhớ chính và được ghi xuống đĩa ngay khi có thể A = 8 16 B = 8 16 Data Actions Log Log Disk Memory Flush-log: là hành động chép những block mẫu tin nhật ký mới chưa được chép từ bộ nhớ vào ổ đĩa 12
Nhật ký giao tác (tt) § Một mẫu tin nhật ký có thể là: Ghi nhận giao tác T bắt đầu hoạt động Ghi nhận giao tác T đã hoàn tất Ghi nhận giao tác T bị hủy Ghi nhận giao tác T cập nhật lên đơn vị dữ liệu X Nhật ký giao tác được sử dụng trong các phương pháp khôi phục sự cố, mỗi kỹ thuật khôi phục sự cố khác nhau sẽ có một cách ghi nhật ký khác nhau và các cú pháp mẫu tin khác nhau. 13
Nhật ký giao tác (tt) § Khi sự cố hệ thống xảy ra: – DBMS sẽ tra cứu nhật ký giao tác để khôi phục lại trạng thái nhất quán của dữ liệu. § Để sửa chữa các sự cố: – Một vài giao tác sẽ phải thực hiện lại (redo)  Những giá trị mà giao tác này đã cập nhật xuống CSDL sẽ phải cập nhật lần nữa – Một vài giao tác không cần phải thực hiện lại (undo)  CSDL sẽ được khôi phục về lại trạng thái trước khi các giao tác này được thực hiện 14
Điểm kiểm tra (Check point) § Khi cần, DBMS không thể tra cứu toàn bộ nhật ký vì – Nhật ký tích lũy thông tin về tất cả các hành động của một giai đoạn rất dài – Quá trình tra cứu nhật ký à Phải quét hết tập tin nhật ký à Mất nhiều thời gian – Thực hiện lại các giao tác đã được ghi xuống đĩa làm cho việc khôi phục lặp lại à tốn thời gian vô ích. § Giải pháp: Dùng điểm kiểm tra (check point) – Nhật ký giao tác có thêm mẫu tin hay – Mẫu tin sẽ được ghi xuống nhật ký định kỳ vào thời điểm mà DBMS ghi tất cả những gì thay đổi của CSDL từ vùng đệm xuống đĩa 15
Điểm kiểm tra đơn giản § Khi đến điểm kiểm tra, DBMS sẽ 1. Tạm dừng tiếp nhận các giao tác mới 2. Đợi các giao tác đang thực hiện  Hoặc là hoàn tất (commit)  Hoặc là hủy bỏ (abort)  và ghi mẫu tin hay vào nhật ký 3. Tiến hành ghi dữ liệu và nhật ký từ vùng đệm xuống đĩa 4. Tạo 1 mẫu tin và ghi xuống đĩa 5. Trở về công việc bình thường (tiếp tục nhận các giao tác mới) 16
Điểm kiểm tra đơn giản (tt) § Khi có sự cố, DBMS dùng nhật ký để khôi phục : – Các giao tác ở phía trước điểm kiểm tra mới nhất là những giao tác đã kết thúc → không cần làm lại – Các giao tác ở phía sau điểm kiểm tra là những giao tác chưa thực hiện xong → cần khôi phục § Như vậy, BDMS sẽ : – Không phải duyệt hết nhật ký – Chỉ duyệt ngược từ cuối nhật ký đến điểm kiểm tra Nhật ký checkpoint Duyệt 17
Điểm kiểm tra linh động § Đặc điểm: – Mẫu tin trong Điểm kiểm tra đơn giản nay được chia thành 2 mẫu tin :  Mẫu tin : Bắt đầu checkpoint – T1, T2, , Tk là các giao tác đang dở dang khi bắt đầu checkpoint  Mẫu tin : Kết thúc checkpoint – Cho phép tiếp nhận các giao tác mới trong quá trình checkpoint 18
Điểm kiểm tra linh động (tt) § Khi đến điểm kiểm tra, DBMS sẽ 1. Tạm ngưng mọi hoạt động 2. Tạo và ghi mẫu tin  T1, T2, , Tk là những giao tác đang thực thi khi ấy 3. Chờ cho đến khi T1, T2, , Tk hoàn tất hay hủy bỏ 4. Trong khi ấy không ngăn các giao tác mới bắt đầu 5. Khi T1, T2, , Tk kết thúc, tạo mẫu tin và ghi xuống đĩa 19
Nội dung trình bày § An toàn dữ liệu – Phân loại sự cố – Nhật ký giao tác – Điểm kiểm tra – Undo loging – Redo loging – Undo / Redo loging § An ninh dữ liệu – Cơ chế phân quyền – Cơ chế mã hoá 20
Phương pháp Undo-Logging § Qui tắc – (1) Một thao tác cập nhật đơn vị dữ liệu X phát sinh ra 1 mẫu tin nhật ký ghi nhận lại giá trị cũ của X – (2) Trước khi X được cập nhật xuống đĩa, mẫu tin đã phải có trên đĩa. Phải ghi nhật ký xuống đĩa (lush log) trước khi thực hiện các câu lệnh OUTPUT – (3) Trước khi mẫu tin được ghi xuống đĩa, tất cả các cập nhật của T đã được phản ánh lên đĩa Mẫu tin phải sau các câu lệnh OUTPUT Flush-log: chép những block mẫu tin nhật ký mới chưa được chép từ bộ nhớ vào ổ đĩa 21
Ví dụ Bước Hành động t Mem A Mem B Disk A Disk B Mem Log 1 2 Read(A,t) 8 8 8 8 3 t:=t*2 16 8 8 8 4 Write(A,t) 16 16 8 8 5 Read(B,t) 8 16 8 8 8 6 t:=t*2 16 16 8 8 8 7 Write(B,t) 16 16 16 8 8 8 9 Flush log 10 Output(A) 16 16 16 16 8 11 Output(B) 16 16 16 16 16 12 Flush log Các hành động lush log, OUTPUT và cách ghi nhật ký đúng hay không ? 22
Ví dụ Bước Hành động t Mem A Mem B Disk A Disk B Mem Log 1 2 Read(A,t) 8 8 8 8 3 t:=t*2 16 8 8 8 4 Write(A,t) 16 16 8 8 5 Read(B,t) 8 16 8 8 8 6 t:=t*2 16 16 8 8 8 7 Write(B,t) 16 16 16 8 8 8 Flush log 9 Output(A) 16 16 16 16 8 10 Output(B) 16 16 16 16 16 11 12 Flush log Các hành động lush log, OUTPUT và cách ghi nhật ký đúng hay không ? 23
Phương pháp Undo-Logging (tt) § Quá trình khôi phục – (1) Gọi S là tập các giao tác chưa kết thúc  Có trong nhật ký nhưng  Không có hay trong nhật ký – (2) Với mỗi mẫu tin trong nhật ký (theo thứ tự cuối tập tin à đầu tập tin) à thực hiện ghi lại giá trị cũ cho ĐVDL X  Nếu Ti ∈ S thì - Write(X, v) - Output(X) – (3) Với mỗi Ti ∈ S  Ghi mẫu tin lên nhật ký 24
Phương pháp Undo-Logging (tt) § Khi có sự cố – T1 và T3 đã hoàn tất – T2 và T4 chưa kết thúc T4 T1 Khôi phục dữ liệu T Bỏ qua 2 T3 Sự cố 25
Ví dụ Bước Hành động t Mem A Mem B Disk A Disk B Mem Log 1 2 Read(A,t) 8 8 8 8 3 t:=t*2 16 8 8 8 4 Write(A,t) 16 16 8 8 5 Read(B,t) 8 16 8 8 8 6 t:=t*2 16 16 8 8 8 Sự cố 7 Write(B,t) 16 16 16 8 8 A và B không thay đổi nên không cần 8 Flush log khôi phục 9 Output(A) 16 16 16 16 8 Sự cố 10 Output(B) 16 16 16 16 16 Khôi phục A=8 và 11 B=8 12 Flush log Sự cố Không cần khôi phục A và B 26
Undo-Logging & Checkpoint § Giả sử nội dung nhật ký như sau: Thời điểm DBMS cần thực hiện Checkpoint § Cách ghi nhật ký: – Vì T1 và T2 đang thực thi nên chờ – Sau khi T1 và T2 hoàn tất hoặc hủy bỏ – Ghi mẫu tin lên nhật ký 27
Undo-Logging & Checkpoint (tt) § Ví dụ: –  T3 chưa kết thúc 2  Khôi phục F=30 –  Khôi phục E=25 –  Dừng  Ghi scan 28
Undo-Logging & Checkpoint (tt) § Phương pháp khôi phục Undo logging với Checkpoint đơn giản: – QUÉT nhật ký từ cuối à Tìm các giao tác chưa hoàn tất và khôi phục lại giá trị cho các ĐVDL đã bị thay đổi bởi các giao tác này. – Chỉ quét từ cuối nhật ký cho đến mẫu tin để tìm các giao tác chưa hoàn tất. Vì các giao tác trước đã chắc chắn hoàn tất. 29
Undo-Logging & Checkpoint (tt) Thời điểm DBMS cần thực hiện check point (Nonquiescent Checkpoint) § Vì T1 và T2 đang thực thi nên tạo § Trong khi chờ T1 và T2 kết thúc, DBMS vẫn tiếp nhận các giao tác mới § Sau khi T1 và T2 kết thúc, ghi lên nhật ký 30
Undo-Logging & Checkpoint (tt) § Trường hợp 1: Khôi phục với đầy đủ –  T3 chưa kết thúc  Khôi phục F=30 2 –  Những giao tác bắt đầu trước đã hoàn tất  T1 và T2 đã hoàn tất – 1  Khôi phục E=25 –  Dừng  Ghi scan 31
Undo-Logging & Checkpoint (tt) – § Trường hợp 2: Khôi phục  T3 chưa kết thúc khi thiếu  Khôi phục E=25 –  T1 bắt đầu trước và đã 1 hoàn tất –  T2 bắt đầu trước và chưa kết thúc  Khôi phục C=15 3 –  Chỉ có T1 và T2 bắt đầu trước đó –  Khôi phục B=10 –  Dừng, ghi abort(T3) và ghi scan 32 abort(T2)
Undo-Logging & Checkpoint (tt) § Trường hợp 3: Khôi phục khi thiếu 33
Undo-Logging & Checkpoint (tt) § Phương pháp khôi phục với Checkpoint linh động: – QUÉT nhật ký từ cuối về trước à Tìm các giao tác chưa hoàn tất và khôi phục lại giá trị cho các ĐVDL đã bị thay đổi bởi các giao tác này. – PHẠM VI QUÉT NHẬT KÝ:  Nếu quét từ cuối mà gặp mẫu tin trước à Các giao tác nằm trong mẫu tin đã hoàn tất à Chỉ cần quét từ cuối đến mẫu tin để tìm các giao tác chưa hoàn tất.  Nếu quét từ cuối mà gặp mẫu tin trước à sự cố xuất hiện trong khi thực hiện checkpoint à các giao tác nằm trong mẫu tin chưa hoàn tất hết à Phải quét từ sau về trước qua luôn cả mẫu tin để tìm các giao tác chưa hoàn tất. 34
Nội dung trình bày § An toàn dữ liệu – Phân loại sự cố – Nhật ký giao tác – Điểm kiểm tra – Undo loging – Redo loging – Undo / Redo loging § An ninh dữ liệu – Cơ chế phân quyền – Cơ chế mã hoá 35
Phương pháp Redo-Logging § Qui tắc: – Một thao tác T muốn cập nhật đơn vị dữ liệu X sẽ phát sinh ra 1 mẫu tin nhật ký  Mẫu tin của thao tác cập nhật chỉ ghi nhận lại giá trị mới  Cấu trúc mẫu tin với w là giá trị mới của X Khi thực hiện WRITE(X) thì phải ghi mẫu tin – Trước khi X được cập nhật xuống đĩa  Tất cả các mẫu tin nhật ký của các giao tác Ti cập nhật X đã phải có trên đĩa  Kể cả các mẫu tin hoàn tất của các Ti cũng đã phải được ghi xuống đĩa Các hành động và Flush log phải trước OUTPUT (X) 36
Ví dụ Bước Hành động t Mem A Mem B Disk A Disk B Mem Log 1 2 Read(A,t) 8 8 8 8 3 t:=t*2 16 8 8 8 4 Write(A,t) 16 16 8 8 5 Read(B,t) 8 16 8 8 8 6 t:=t*2 16 16 8 8 8 7 Write(B,t) 16 16 16 8 8 8 Flush log 9 Output(A) 16 16 16 16 8 10 Output(B) 16 16 16 16 16 11 12 Flush log Các hành động lush log, OUTPUT và cách ghi nhật ký đúng quy tắc hay không ? 37
Ví dụ Bước Hành động t Mem A Mem B Disk A Disk B Mem Log 1 2 Read(A,t) 8 8 8 8 3 t:=t*2 16 8 8 8 4 Write(A,t) 16 16 8 8 5 Read(B,t) 8 16 8 8 8 6 t:=t*2 16 16 8 8 8 7 Write(B,t) 16 16 16 8 8 8 9 Flush log 10 Output(A) 16 16 16 16 8 11 Output(B) 16 16 16 16 16 Các hành động lush log, OUTPUT và cách ghi nhật ký đúng hay không ? 38
Phương pháp Redo-Logging (tt) § Quá trình khôi phục: – Gọi S là tập các giao tác hoàn tất  Có mẫu tin trong nhật ký – Với mỗi mẫu tin trong nhật ký  Nếu Ti ∈ S thì – Write(X, w) (theo thứ tự đầu tập tin đến cuối tập tin) – Output(X) (theo thứ tự cuối tập tin đến đầu tập tin) – Với mỗi Tj ∉ S  Ghi mẫu tin lên nhật ký 39
Phương pháp Redo-Logging (tt) § Khi có sự cố – T1 và T3 đã hoàn tất – T2 và T4 chưa kết thúc T4 T1 Bỏ qua T Thực hiện 2 & abort lại T3 Sự cố 40
Ví dụ Bước Hành động t Mem A Mem B Disk A Disk B Mem Log 1 2 Read(A,t) 8 8 8 8 3 t:=t*2 16 8 8 8 4 Write(A,t) 16 16 8 8 5 Read(B,t) 8 16 8 8 8 6 t:=t*2 16 16 8 8 8 7 Write(B,t) 16 16 16 8 8 8 Xem như T chưa hoàn tất, A và B 9 Flush log không có thay đổi 10 Output(A) 16 16 16 16 8 Thực hiện lại T, 11 Output(B) 16 16 16 16 16 ghi A=16 và B=16 Thực hiện lại T, ghi A=16 và B=16 41
Redo-Logging & Checkpoint § Nhận xét – Phương pháp Redo thực hiện ghi dữ liệu xuống đĩa trễ so với thời điểm hoàn tất của các giao tác à đến điểm lưu trữ thì sẽ ghi tất cả các dữ liệu đang còn ở buffer của những giao tác đã hoàn tất vào đĩa. Thực hiện ghi ĐVDL đang ở trên buffer mà chưa được ghi xuống đĩa của những giao tác đã COMMIT khi mẫu tin được ghi xuống nhật ký. 42
Redo-Logging & Checkpoint (tt) QUY TẮC GHI CHECKPOINT § Đến điểm lưu trữ, DBMS – 1. Ghi mẫu tin với Ti, , Tk là những giao tác chưa hoàn tất và lush-log – 2. Thực hiện ghi ĐVDL đang ở trên buffer mà chưa được ghi xuống đĩa của những giao tác đã COMMIT khi mẫu tin được ghi xuống nhật ký. – 3. Ghi mẫu tin vào nhật ký và lush-log.  Lưu ý: Không cần đợi các giao tác hoàn tất Ti, , Tk hoặc huỷ bỏ 43
Redo-Logging & Checkpoint (tt) § Ví dụ 1 – T1 đã hoàn tất trước 1  Có thể đã được ghi xuống đĩa 1 Nếu chưa thì trước khi cũng được 2 ghi xuống đĩa – Sau  T2 đang thực thi  T3 bắt đầu 3 – Sau  T2 và T3 hoàn tất 44
Redo-Logging & Checkpoint (tt) § Ví dụ 1 – Tìm thấy 1 – Chỉ xét T2 và T3 –  Thực hiện lại T2  Ghi C=15 và B=10 2 –  Thực hiện lại T3  Ghi D=20 scan 45
Redo-Logging & Checkpoint (tt) § Ví dụ 1b 46
Redo-Logging & Checkpoint (tt) § Ví dụ 2 – T2 và T3 chưa hoàn tất  Không thực hiện lại 2 – T1 đã hoàn tất  Thực hiện lại T1  Ghi A=5 scan 47
Nhận xét ￭ Undo-logging ￭ Redo-logging – Khi giao tác kết thúc, dữ liệu – Phải giữ lại các cập nhật trên có thể được ghi xuống đĩa vùng đệm cho đến khi giao ngay lập tức tác hoàn tất và mẫu tin nhật – Truy xuất đĩa nhiều nhưng ký được ghi không chiếm dụng nhiều bộ xuống đĩa nhớ – Tốn nhiều bộ nhớ nhưng giảm tần suất truy xuất đĩa à Immediate modiication à Deferred modiication UNDO: GHI DỮ LIỆU REDO: GHI COMMIT XUỐNG ĐĨA TRƯỚC à GHI TRƯỚC à ĐƯA DỮ LIỆU COMMIT SAU LÊN ĐĨA SAU 48
Nội dung trình bày § An toàn dữ liệu – Phân loại sự cố – Nhật ký giao tác – Điểm kiểm tra – Undo loging – Redo loging – Undo / Redo loging § An ninh dữ liệu – Cơ chế phân quyền – Cơ chế mã hoá 49
Phương pháp Undo/Redo-Logging § Qui tắc: – (1) Khi một giao tác muốn ghi dữ liệu thì sẽ phát sinh ra một mẫu tin nhật ký tương ứng ghi nhận lại giá trị cũ và mới của ĐVDL X.  Cấu trúc mẫu tin: với v là giá trị cũ và w là giá trị mới – (2) Trước khi X được cập nhật xuống đĩa, các mẫu tin cập nhật đã phải có trên đĩa à Lệnh lush-log phải trước các lệnh OUTPUT – (3) Khi T hoàn tất, tạo mẫu tin trên nhật ký và ghi xuống đĩa 50
Ví dụ Bước Hành động t Mem A Mem B Disk A Disk B Mem Log 1 2 Read(A,t) 8 8 8 8 3 t:=t*2 16 8 8 8 4 Write(A,t) 16 16 8 8 5 Read(B,t) 8 16 8 8 8 6 t:=t*2 16 16 8 8 8 7 Write(B,t) 16 16 16 8 8 8 Flush log 9 Output(A) 16 16 16 16 8 10 11 Output(B) 16 16 16 16 16 51
Phương pháp Undo/Redo-Logging (tt) § Khôi phục: – (1) Khôi phục lại (undo) những giao tác chưa kết thúc  Theo thứ tự từ cuối nhật ký đến đầu nhật ký – (2) Thực hiện lại (redo) những giao tác đã hoàn tất  Theo thứ tự từ đầu nhật ký đến cuối nhật ký 52
Phương pháp Undo/Redo-Logging (tt) § Khi gặp sự cố – T1 và T3 đã hoàn tất – T2 và T4 chưa kết thúc T4 T1 Khôi T Thực hiện 2 phục lại T3 Sự cố 53
Ví dụ Bước Hành động t Mem A Mem B Disk A Disk B Mem Log 1 2 Read(A,t) 8 8 8 8 3 t:=t*2 16 8 8 8 4 Write(A,t) 16 16 8 8 5 Read(B,t) 8 16 8 8 8 6 t:=t*2 16 16 8 8 8 7 Write(B,t) 16 16 16 8 8 8 Flush log 9 Output(A) 16 16 16 16 8 T chưa kết thúc, khôi phục A=8 10 đã được ghi xuống 11 Output(B) 16 16 16 16 16 đĩa, thực hiện lại T, A=16 và B=16 54
Undo/Redo-Logging & Checkpoint § Khi đến điểm lưu trữ, DBMS – (1) Tạo mẫu tin và ghi xuống đĩa  Ti, , Tk là những giao tác đang thực thi – (2) Ghi xuống đĩa những dữ liệu đang nằm trên vùng đệm  Những đơn vị dữ liệu được cập nhật bởi các giao tác [Kể cả những giao tác đã COMMIT hay chưa COMMIT] – (3) Tạo mẫu tin trong nhật ký và ghi xuống đĩa 55
Undo/Redo-Logging & Checkpoint (tt) § Ví dụ 1 – T1 đã hoàn tất trước 1  Có thể đã được ghi xuống đĩa 1 Nếu chưa thì trước khi cũng được 2 ghi xuống đĩa – Giá trị B=10 đã được ghi xuống đĩa 56
Undo/Redo-Logging & Checkpoint (tt) § Ví dụ 1 – Tìm thấy 1  T1 không cần thực hiện lại 1 – Xét T2 và T3 –  Thực hiện lại T2 và ghi C=15 2  Không cần ghi B –  Thực hiện lại T3 và ghi D=20 scan 57
Undo/Redo-Logging & Checkpoint (tt) § Ví dụ 2 – Tìm thấy 1  T1 không cần thực hiện lại 1 – Xét T2 và T3 –  Thực hiện lại T2 và ghi C=15 2  Không cần ghi B – T3 chưa kết thúc  Khôi phục D=19 scan 58
Undo/Redo-Logging & Checkpoint (tt) § Ví dụ 3 – Tìm thấy 1  T1 không cần thực hiện lại 1 – Xét T2 và T3 –  Thực hiện lại T2 và ghi C=15 2  Không cần ghi B – T3 chưa kết thúc  Khôi phục D=19 và E=6 scan 59
Nội dung trình bày § An toàn dữ liệu – Phân loại sự cố – Nhật ký giao tác – Điểm kiểm tra – Undo loging – Redo loging – Undo / Redo loging § An ninh dữ liệu – Cơ chế phân quyền – Cơ chế mã hoá 60
An ninh Dữ liệu § Thực hiện hai bài toán : – Bài toán phân quyền  Quản lý tốt việc truy xuất Dữ liệu của các đối tượng người dùng hợp pháp à Bảo mật Dữ liệu  Thông qua 2 cơ chế – Cơ chế chứng thực – Cơ chế phân quyền » Quan điểm phân quyền cụ thể » Quan điểm phân cấp mức độ MẬT – Bài toán mã hóa  Ngăn chặm hiệu quả sự tấn công, xâm nhập của các đối tượng tin tặc à An ninh Dữ liệu 61
Cơ chế chứng thực § Mỗi người dùng DBMS được xác định bởi – Một tên đăng nhập – user name – Một mật mã đăng nhập – password § Thông tin về user name và password – Không được lưu trữ tường minh trong dữ liệu – User name và password của DBMS và của OS có thể tách bạch nhau hay dùng chung cho nhau là tùy hệ thống  Vd : Mixed-mode của Microsoft SQL Server 62