›
›

Bài giảng Cơ sở dữ liệu nâng cao

pdf 60 trang vanle 1780
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cơ sở dữ liệu nâng cao", để 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:

  • pdfbai_giang_co_so_du_lieu_nang_cao.pdf

Nội dung text: Bài giảng Cơ sở dữ liệu nâng cao

  1. TRƢỜNG ĐẠI HỌC HÀNG HẢI KHOA CƠNG NGHỆ THƠNG TIN BỘ MƠN HỆ THỐNG THƠNG TIN BÀI GIẢNG CƠ SỞ DỮ LIỆU NÂNG CAO TÊN HỌC PHẦN : CƠ SỞ DỮ LIỆU NÂNG CAO MÃ HỌC PHẦN : 17406 TRÌNH ĐỘ ĐÀO TẠO : ĐẠI HỌC CHÍNH QUY DÙNG CHO SV NGÀNH: CƠNG NGHỆ THƠNG TIN HẢI PHÕNG – 2011
  2. 2 MỤC LỤC CHƢƠNG 1: LƢU TRỮ VÀ TỔ CHỨC TỆP TIN 6 1.1. Tổng quan về phƣơng tiện lƣu trữ 6 1.2. Tổ chức tệp tin 7 1.2.1. Bản ghi với độ dài cố định (Fixed – Length Records) 7 1.2.2. Bản ghi với độ dài thay đổi (Variable – Length Records) 9 1.3. Tổ chức các bản ghi trong tệp tin 11 1.3.1. Tổ chức tệp tin Heap 11 1.3.2. Tổ chức tệp tin tuần tự 11 1.3.3. Tổ chức tệp tin băm 12 1.4. Câu hỏi ơn tập chƣơng 1 14 CHƢƠNG 2: LẬP CHỈ MỤC VÀ BĂM 15 2.1. Các khái niệm cơ bản 15 2.2. Các chỉ mục cĩ thứ tự 15 2.2.1. Chỉ mục chính (Primary Indexes) 15 2.2.2. Chỉ mục cụm (Clustering Indexes) 17 2.2.3. Chỉ mục phụ (Secondary Indexes) 17 2.3. Chỉ mục cây B+ 19 2.3.1. Tĩm lược về cây tìm kiếm 19 2.3.2. Chỉ mục B – Tree 20 2.3.3. Chỉ mục B+ – Tree 21 2.4. Băm tĩnh và băm động 23 2.4.1. Băm tĩnh (Static Hashing) 23 2.4.2. Băm động (Dynamic Hashing) 24 2.5. Câu hỏi ơn tập chƣơng 2 26 CHƢƠNG 3: TỐI ƢU HĨA TRUY VẤN 28 3.1. Giới thiệu 28 3.2. Các phép biến đổi tƣơng đƣơng 28 3.3. Thuật tốn tối ƣu hĩa cây đại số quan hệ 30 3.3.1. Thuật tốn 30 3.3.2. Ví dụ 30 3.4. Câu hỏi ơn tập chƣơng 3 32 CHƢƠNG 4: GIAO DỊCH TRONG CƠ SỞ DỮ LIỆU 33 4.1. Giới thiệu 33
  3. 3 4.2. Các tính chất và trạng thái của giao dịch 33 4.2.1. Tính chất của giao dịch 33 4.2.2. Trạng thái của giao dịch 33 4.3. Lịch biểu 34 4.3.1. Khái niệm lịch biểu 34 4.3.2. Tính khả tuần tự của lịch biểu 35 4.4. Thuật tốn kiểm tra tính khả tuần tự của lịch biểu 35 4.5. Câu hỏi ơn tập chƣơng 4 37 CHƢƠNG 5: ĐIỀU KHIỂN ĐỒNG THỜI VÀ KHƠI PHỤC HỆ THỐNG 38 5.1. Các giao thức dựa vào khĩa 38 5.1.1. Mơ hình khĩa nhị phân 38 5.1.2. Mơ hình khĩa đọc – ghi (chia sẻ – độc quyền) 38 5.1.3. Giao thức khĩa 2 pha 40 5.1.4. Deadlock 41 5.2. Giao thức thứ tự nhãn thời gian (Timestamp – Ordering protocol) 43 5.2.1. Nhãn thời gian (Timestamp) 43 5.2.2. Giao thức thứ tự nhãn thời gian (Timestamp – Ordering Protocol) 43 5.3. Phục hồi hệ thống dựa vào nhật ký giao dịch (Log-based) 44 5.3.1. Cập nhật trì hỗn cơ sở dữ liệu (Deferred Database Modification) 44 5.3.2. Cập nhật tức thời (Immediate Database Modification) 45 5.4. Kỹ thuật phân trang bĩng (Shadow Paging) 46 5.5. Câu hỏi ơn tập chƣơng 5 49 MỘT SỐ ĐỀ THI MẪU 50
  4. 4 Tên học phần: Cơ sở dữ liệu nâng cao Loại học phần: 2 Bộ mơn phụ trách giảng dạy: Hệ thống Thơng tin Khoa phụ trách: CNTT. Mã học phần: 17406 Tổng số TC: 2 Tổng số tiết Lý thuyết Thực hành/Xemina Tự học Bài tập lớn Đồ án mơn học 45 30 15 0 khơng khơng Học phần học trƣớc: Cơ sở dữ liệu. Học phần tiên quyết: Cơ sở dữ liệu. Học phần song song: Khơng yêu cầu. Mục tiêu của học phần: Cung cấp cho sinh viên những kiến thức nâng cao về cơ sở dữ liệu quan hệ. Nội dung chủ yếu: Các vấn đề nâng cao về cơ sở dữ liệu quan hệ: Lưu trữ và tổ chức tệp tin; Lập chỉ mục và băm; Tối ưu hĩa truy vấn; Quản lý giao dịch trong cơ sở dữ liệu; Điều khiển tương tranh; Phục hồi hệ thống. Nội dung chi tiết: PHÂN PHỐI SỐ TIẾT TÊN CHƢƠNG MỤC TS LT TH BT KT Chƣơng 1: Lƣu trữ và tổ chức tệp tin 2 2 1.1. Tổng quan về phương tiện lưu trữ 1.2. Tổ chức tệp tin 1.3. Tổ chức các bản ghi trong tệp tin Chƣơng 2: Lập chỉ mục và băm 12 6 5 1 2.1. Các khái niệm cơ bản 2.2. Các chỉ mục cĩ thứ tự 2.3. Chỉ mục cây B+ 2.4. Băm tĩnh 2.5. Băm động Chƣơng 3: Tối ƣu hĩa truy vấn 7 6 1 3.1. Giới thiệu 3.2. Các phép biến đổi tương đương 3.4. Thuật tốn tối ưu hĩa cây đại số quan hệ Chƣơng 4: Giao dịch trong cơ sở dữ liệu (Transactions) 12 6 5 1 4.1. Giới thiệu 4.2. Các tính chất của giao dịch
  5. 5 PHÂN PHỐI SỐ TIẾT TÊN CHƢƠNG MỤC TS LT TH BT KT 4.3. Các trạng thái của giao dịch 4.4. Lịch biểu (Schedule) 4.5. Tính khả tuần tự của lịch biểu (Serializability) 4.6. Thuật tốn kiểm tra tính khả tuần tự của lịch biểu Chƣơng 5: Điều khiển đồng thời và khơi phục hệ thống 12 7 5 5.1. Các giao thức dựa vào khĩa (Lock-based) 5.2. Giao thức thứ tự nhãn thời gian 5.3. Phục hồi hệ thống dựa vào nhật ký giao dịch (Log-based) 5.4. Kỹ thuật phân trang bĩng (Shadow Paging) Nhiệm vụ của sinh viên: Tham dự các buổi học lý thuyết và thực hành, làm các bài tập được giao, làm các bài thi giữa học phần và bài thi kết thúc học phần theo đúng quy định. Tài liệu học tập: 1. Avi Silberschatz, Henry F. Korth, S. Sudarshan, Database System Concepts, 6th ed, McGraw-Hill. Hình thức và tiêu chuẩn đánh giá sinh viên: Hình thức thi: tự luận hoặc trắc nghiệm. Tiêu chuẩn đánh giá sinh viên: căn cứ vào sự tham gia học tập của sinh viên trong các buổi học lý thuyết và thực hành, kết quả làm các bài tập được giao, kết quả của các bài thi giữa học phần và bài thi kết thúc học phần. Thang điểm: Thang điểm chữ A, B, C, D, F. Điểm đánh giá học phần: Z = 0,3X + 0,7Y. Bài giảng này là tài liệu chính thức và thống nhất của Bộ mơn Hệ thống Thơng tin, Khoa Cơng nghệ Thơng tin và được dùng để giảng dạy cho sinh viên. Ngày phê duyệt: __/__/___ Trƣởng Bộ mơn Ngƣời biên soạn
  6. 6 CHƢƠNG 1: LƢU TRỮ VÀ TỔ CHỨC TỆP TIN 1.1.Tổng quan về phƣơng tiện lƣu trữ Cĩ một vài kiểu lưu trữ dữ liệu tồn tại trong hầu hết các hệ thống máy tính. Các thiết bị lưu trữ này được phân loại theo tốc độ truy cập dữ liệu, giá trên một đơn vị dữ liệu và độ tin cậy của thiết bị: Cache: Là thiết bị lưu trữ nhanh nhất và cũng cĩ giá đắt nhất. Bộ nhớ cache tương đối nhỏ, được quản lý bởi phần cứng của hệ thống máy tính. Main Memory: Dung lượng cĩ thể lên tới vài Gigabytes trên máy tính cá nhân và hàng trăm Gigabytes trên các máy Server. Tuy nhiên vẫn là quá nhỏ để lưu tồn bộ cơ sở dữ liệu. Dữ liệu lưu trữ trên Main Memory sẽ mất khi mất nguồn hay lỗi hệ thống. Flash Memory: Khác với Main Memory, dữ liệu lưu trên thiết bị lưu trữ loại này vẫn cịn ngay cả khi mất nguồn hay lỗi hệ thống. Flash Memory cĩ giá thấp hơn Main Memory, thường sử dụng rộng rãi để lưu trữ dữ liệu trên các thiết bị như camera, máy nghe nhạc, điện thoại, USB, Magnetic – disk storage: Là phương tiện chủ yếu lưu trữ dữ liệu lâu dài, thường tồn bộ cơ sở dữ liệu được lưu trữ trên đĩa từ. Để xử lý dữ liệu trên đĩa từ, dữ liệu phải được chuyển sang bộ nhớ chính (Main Memory). Hiện nay, dung lượng của đĩa từ cĩ thể từ vài chục Gigabytes đến hàng Terabyte. Optical storage: Các đĩa CD (Compact Disk) với dung lượng khoảng 700 Megabytes là dạng phổ biến nhất của các thiết bị lưu trữ loại này. Và khoảng 4.7 đến 8.5 Gigabytes với đĩa DVD (Digital Video Disk). Đĩa hai mặt cĩ dung lượng lên tới 17 Gigabytes. Tape storage: Là thiết bị chủ yếu dùng để sao lưu dữ liệu. Thiết bị lưu trữ loại này cĩ giá rẻ hơn đĩa từ nhưng tốc độ truy xuất chậm do phải đọc tuần tự. Khả năng lưu trữ của băng từ là rất lớn (40 – 300 Gigabytes). Các thiết bị lưu trữ được tổ chức như hình sau phân cấp theo tốc độ và giá cả: Ở mức cao là các thiết bị lưu trữ cĩ khả năng truy xuất nhanh hơn nhưng cĩ giá đắt hơn.
  7. 7 Hình 1.1: Phân cấp các thiết bị lưu trữ 1.2. Tổ chức tệp tin 1.2.1. Bản ghi với độ dài cố định (Fixed – Length Records) Xem xét các bản ghi trong file instructor, mỗi bản ghi được định nghĩa như sau: Giả sử mỗi ký tự chiếm một byte và kiểu numeric(8, 2) chiếm 8 bytes như vậy một bản ghi instructor sẽ cĩ độ dài là 53 byte. Một cách tiếp cận đơn giản để lưu trữ các bản ghi này là dùng 53 byte đầu tiên lưu bản ghi đầu tiên, 53 byte tiếp theo cho bản ghi thứ hai, Hình 1.2: File chứa các bản ghi Instructor Tuy nhiên với các tiếp cận này sẽ cĩ hai vấn đề nảy sinh: Nếu kích thước của một khối khơng chia hết cho 53 thì một số bản ghi sẽ vượt quá một khối đĩa, nghĩa là một bản ghi cĩ thể nằm trong hai khối đĩa. Như vậy cĩ thể phải truy xuất tới hai khối đĩa để đọc hay ghi một bản ghi.
  8. 8 Khĩ khăn khi xĩa một bản ghi với cấu trúc lưu trữ kiểu này. Khoảng trống bị chiếm bởi bản ghi đã xĩa hoặc là phải được lấp đầy bởi bản ghi khác hoặc là phải được đánh dấu xĩa. Để giải quyết vấn đề đầu tiên, chúng ta chỉ lưu mỗi bản ghi trong một khối. Phần khoảng trống dư lại ở cuối khối sẽ bị bỏ quả. Với vấn đề thứ hai, khi một bản ghi bị xĩa và để lại khoảng trống trên khối đĩa, ta cĩ thể giải quyết bằng một số cách như sau: Dịch chuyển các bản ghi sau bản ghi bị xĩa về trước: Hình 1.3: File Instructor trong hình 1.2 sau khi đã xĩa bản ghi thứ 3 và dịch chuyển các bản ghi sau về trước Với cách tiếp cận này thì khoảng khơng gian cịn trống luơn ở cuối khối, tuy nhiên nhược điểm của nĩ là phải dịch chuyển một lượng lớn bản ghi để thực hiện thao tác xĩa. Một cách tiếp cận đơn giản hơn là di chuyển bản ghi cuối cùng: Hình 1.4: File Instructor trong hình 1.2 sau khi đã xĩa bản ghi thứ 3 và dịch chuyển bản ghi cuối cùng Sử dụng phương pháp đánh dấu các bản ghi bị xĩa: Thực tế ta khơng mong muốn phải di chuyển các bản ghi khi thực hiện thao tác xĩa, hơn nữa những thao tác thêm một bản ghi được thực hiện thường xuyên hơn những thao tác xĩa. Do vậy, một cách tiếp cận hợp lý hơn là đánh dấu vị trí các bản ghi bị xĩa và chờ thao tác thêm bản ghi tiếp theo sẽ sử dụng lại khoảng khơng gian bị trống đĩ.
  9. 9 Một phương pháp đơn giản để đánh dấu các bản ghi bị xĩa là sử dụng một số byte ở phần đầu của tệp tin (ta gọi là file header) để lưu địa chỉ của bản ghi đầu tiên bị xĩa, rồi sử dụng bản ghi đầu tiên bị xĩa để lưu địa chỉ của bản ghi thứ hai bị xĩa, Như vậy ta sẽ cĩ một danh sách các bản ghi được đánh dấu xĩa. Hình 1.5: File Instructor trong hình 1.2 với các bản ghi 1, 4, 6 đã đánh dấu xĩa Khi thêm mới một bản ghi, ta sử dụng con trỏ đầu danh sách được chứa trong file header để xác định danh sách, nếu danh sách khơng rỗng ta xen bản ghi mới vào nơi được trỏ bởi con trỏ đầu danh sách nếu khơng ta xen bản ghi mới vào cuối file. Ta thấy rằng với cấu trúc bản ghi cĩ độ dài cố định việc cài đặt các thao tác thêm hay xĩa bản ghi là đơn giản do khoảng khơng gian để lại bởi bản ghi bị xĩa cũng vừa bằng khoảng khơng gian cần thiết cho bản ghi thêm vào. Nhưng nếu cho phép bản ghi cĩ độ dài thay đổi thì vấn đề trở nên phức tạp hơn nhiều. 1.2.2. Bản ghi với độ dài thay đổi (Variable – Length Records) Lưu trữ nhiều kiểu bản ghi trong một tệp tin. Các kiểu bản ghi với độ dài thay đổi trên một hay nhiều thuộc tính. Các kiểu bản ghi cho phép các trường được lặp lại, như mảng hay tập hợp. Biểu diễn một bản ghi với các thuộc tính cĩ độ dài thay đổi thường gồm hai phần. Phần đầu chứa các thuộc tính cĩ độ dài cố định và phần sau là các thuộc tính với độ dài thay đổi. Các thuộc tính với độ dài cố định như các giá trị số, ngày tháng, hoặc các xâu với độ dài cố định. Các thuộc tính với độ dài thay đổi như các thuộc tính kiểu varchar được biểu diễn với một cặp (offset, length), trong đĩ offset cho biết vị trí bắt đầu của dữ liệu và length là độ dài (số byte) dữ liệu. Ví dụ với một bản ghi instructor thì các thuộc tính: ID, name và dept_name là các xâu với độ dài thay đổi, và thuộc tính salary là kiểu số với độ dài cố định. Giả sử mỗi giá trị offset và length được lưu trữ trong hai byte và kiểu số được lưu trong 8 byte:
  10. 10 Hình 1.6: Biểu diễn bản ghi cĩ độ dài thay đổi Với các thuộc tính trong bản ghi cĩ giá trị null, ta sử dụng cấu trúc null bitmap để đánh dấu các giá trị null. Với bản ghi instructor cĩ bốn thuộc tính: ID, name, dept_name và salary, nếu thuộc tính salary nhận giá trị null thì bít thứ tư của bitmap được gán là 1 và giá trị trong các byte từ 12 đến 19 bị bỏ qua. Do bản ghi instructor chỉ cĩ bốn thuộc tính nên chỉ cần một byte để lưu thơng tin về null bitmap. Trong một số cách biểu diễn, null bitmap được lưu trử ở phần đầu của bản ghi. Cách biểu diễn này rất hữu dụng khi số lượng thuộc tính trong một bản ghi, và số lướng thuộc tính null là lớn. Trên đây đã trình bày vấn đề tổ chức các thuộc tính cĩ độ dài thay đổi trong một bản ghi. Sau đây ta xem xét vấn đề lưu các bản ghi độ dài thay đổi trong một khối. Cấu trúc slotted – page thường được sử dụng để lưu trữ các bản ghi với độ dài thay đổi trong khối đĩa: Hình 1.7: Cấu trúc Slotted – page Phần đầu mỗi khối (Block Header) chứa thơng tin về: Số lượng bản ghi. Phần cuối khoảng khơng gian trống trong khối. Mảng chứa vị trí và kích thước mỗi bản ghi. Các bản ghi được lưu trữ liên tiếp trong khối và bắt đầu từ cuối khối. Khoảng khơi gian trống trong khối là liên tiếp nhau và nằm giữa mục cuối cùng trong mảng header và và bản ghi đầu tiên. Khi một bản ghi được thêm vào khối, nĩ sẽ được lưu ở phần cuối cùng trong khơng gian trống của khối, sau đĩ một mục chứa vị trí và kích thước của bản ghi đĩ sẽ được thêm vào phần Block Header. Nếu một bản ghi bị xĩa, khoảng khơng gian chứa nĩ sẽ được giải phĩng và mục thơng tin về bản ghi đĩ trong phần Block Header sẽ được xĩa (ví dụ kích thước được gán bằng -1). Sau đĩ các
  11. 11 bản ghi trước bản ghi bị xĩa sẽ được dịch chuyển về cuối để đảm bảo phần khơng gian trống trong khối luơn nằm giữa Block Header và bản ghi đầu tiên. SQL hỗ trợ các kiểu blob và clob cho các trường hợp mà kích thước dữ liệu cần lưu trữ lớn hơn kích thước của khối đĩa như: ảnh, các tệp tin audio, video, Các kiểu này lưu trữ các đối tượng nhị phân và các chuỗi ký tự lớn. Các đối tượng này sẽ được lưu trữ trong các tệp tin đặc biệt và sử dụng cấu trúc cây B+ sẽ được trình bày trong chương sau. 1.3. Tổ chức các bản ghi trong tệp tin Ở phần trước ta đã xem xét làm thế nào để biểu diễn các mẩu tin trong một cấu trúc file. Một quan hệ là một tập các bản ghi. Với một tập các bản ghi, vấn đề là làm sao để tổ chức chúng trong một file. Cĩ một vài cách tổ chức các bản ghi trong file như sau: Tổ chức tệp tin Heap: Một bản ghi được lưu ở bất kỳ đâu trong file. Khơng cĩ thứ tự của các bản ghi. Thơng thường một file lưu một quan hệ. Tổ chức tệp tin tuần tự: Các bản ghi được tổ chức tuần tự theo giá trị của một khĩa tìm kiếm (search key) trong mỗi bản ghi. Tổ chức tệp tin băm: Sử dụng một hàm băm tính tốn trên một số thuộc tính của bản ghi và dùng kết quả để đĩ để xác định khối đĩa mà bản ghi được lưu trữ. 1.3.1. Tổ chức tệp tin Heap Là kiểu tổ chức file đơn giản nhất, các bản ghi khơng được sắp xếp thứ tự. Việc thêm mới một bản ghi là đơn giản: Tìm khối đĩa cuối cùng của file, sao chép khối đĩa vào bộ đệm, thêm mới bản ghi rồi ghi lại vào đĩa. Địa chỉ của khối đĩa cuối cùng được cập nhật lại vào file header. Do các bản ghi trong file khơng được sắp xếp theo thứ tự nên khi tìm kiếm phải sử dụng phương pháp tìm kiếm tuần tự: Đọc lần lượt từng khối đĩa vào bộ nhớ chính rồi tiến hành tìm kiếm các bản ghi. Như vậy nếu file gồm b khối đĩa thì thời gian tìm kiếm trung bình sẽ là n/2. 1.3.2. Tổ chức tệp tin tuần tự Tổ chức file tuần tự được thiết kế để xử lý hiệu quả các bản ghi theo thứ tự được sắp dựa trên một khố tìm kiếm nào đĩ. Một khĩa tìm kiếm là một hay một nhĩm thuộc tính bất kỳ, khơng nhất thiết phải là khĩa chính hay siêu khĩa. Ta sử dụng kỹ thuật con trỏ để truy xuất nhanh chĩng tới bản ghi theo thứ tự khố tìm kiếm. Con trỏ trong mỗi bản ghi sẽ trỏ tới bản ghi tiếp theo trong thứ tự khố tìm kiếm. Hình 1.8 cho thấy tổ chức file tuần tự của các bản ghi instructor với khĩa tìm kiếm là thuộc tính ID. Tổ chức file tuần tự cho phép đọc các bản ghi theo thứ tự được sắp thuận lợi cho mục đích hiển thị cũng như cho các thuật tốn xử lý truy vấn (query – processing algorithms). Tuy vậy, kho khăn gặp phải khi tổ chức file tuần tự là việc duy trì thứ tự vật lý của các bản ghi trong file khi xảy ra các thao tác thêm, xĩa bản ghi. Ta cĩ thể quản lý thao tác xĩa nhờ việc sử dụng kỹ thuật con trỏ như đã trình bày ở phần trên. Với phép chèn một bản ghi, ta áp dụng các quy tắc sau:
  12. 12 Xác định vị trí bản ghi trước bản ghi được thêm vào theo thứ tự của khĩa tìm kiếm. Nếu cĩ bản ghi trống (để lại do phép xĩa) trong cùng khối với bản ghi vừa xác định thì đặt bản ghi mới vào khơng gian trống đĩ, nếu khơng chèn bản ghi mới vào khối tràn (overflow block). Sau đĩ điều chỉnh lại con trỏ của các bản ghi liên quan cho đúng với thứ tự của khĩa tìm kiếm. Hình 1.9 chỉ ra file trong hình 10.10 sau khi chèn thêm bản ghi (32222, Verdi, Music, 48000). Hình 1.8: File tuần tự chứa các bản ghi Instructor Hình 1.9: File tuần tự sau khi thêm bản ghi vào khối tràn 1.3.3. Tổ chức tệp tin băm Phương pháp tổ chức file dạng này cho phép truy cập nhanh tới bản ghi cần tìm. Điều kiện tìm kiếm phải là điều kiện bằng trên một thuộc tính, gọi là thuộc tính băm (hash attribute, hash field) của file. Thơng thường thuộc tính đem băm cũng là khĩa. Ý tưởng của phương pháp này là sử
  13. 13 dụng một hàm h nhận giá trị đầu vào là giá trị băm và cho ra kết quả là địa chỉ của khối đĩa chứa bản ghi cần tìm. Ưu điểm của phương pháp tổ chức file dạng này là cho phép thực hiện các thao tác nhanh, tuy vậy việc xây dựng hàm băm là khĩ khăn vì phải đảm bảo dễ tính tốn và phân phối đều các bản ghi.
  14. 14 1.4. Câu hỏi ơn tập chƣơng 1 1.4.1. Trình bày tổng quan về các phương tiện lưu trữ 1.4.2. Trình bày các phương pháp tổ chức tệp tin cơ sở dữ liệu 1.4.3. Trình bày các phương pháp tổ chức bản ghi trong tệp tin 1.4.4. Chỉ ra cấu trúc của file trong hình 1.5 sau mỗi thao tác dưới đây: Thêm bản ghi (24556, Turnamian, Finance, 98000) Xĩa bản ghi 2 Thêm bản ghi (34556, Thompson, Music, 67000) 1.4.5. Xét bản ghi trong file Employee (ID, Name, Dept_ID, Age, Address) trong đĩ: ID, Dept_ID là kiểu numberic (8, 2) độ dài cố định, lưu trong 8 byte Name là kiểu varchar(30) độ dài thay đổi lưu, mỗi ký tự, lưu trong 1 byte Age là kiểu số tinyint độ dài cố định, lưu trong 1 byte Address là kiểu varchar (50) độ dài thay đổi, mỗi ký tự lưu trong 1 byte Hãy biểu diễn bản ghi sau trong cấu trúc bản ghi với độ dài thay đổi: 1002, Nimzowitsch, 102, 60, Russian 1105, Lindan, 111, NULL, China
  15. 15 CHƢƠNG 2: LẬP CHỈ MỤC VÀ BĂM 2.1. Các khái niệm cơ bản Ở chương trước ta đã tìm hiểu về cách thức tổ chức các bản ghi trong file. Mỗi phương pháp đều cĩ những ưu, nhược điểm nhất định. Chương này sẽ trình bày một số kỹ thuật lập chỉ mục cho phép truy cập hiệu quả tới bản ghi cần tìm dựa vào một giá trị tìm kiếm. Cĩ nhiều kỹ thuật lập chỉ mục và khơng cĩ kỹ thuật nào là tốt nhất. Ta sẽ xem xét các kỹ thuật này thơng qua các tiêu chí: Kiểu truy xuất: Kiểu tìm kiếm mà kỹ thuật lập chỉ mục hỗ trợ: Tìm kiếm với một giá trị cụ thể hay tìm kiếm với các giá trị trong một khoảng giới hạn. Thời gian truy xuất: Thời gian cần thiết để truy xuất tới một hay một số bản ghi. Thời gian thêm mới một bản ghi: Thời gian cần thiết để thêm mới một bản ghi, bao gồm thời gian thêm bản ghi vào đúng vị trí trong file và thời gian cập nhật lại cấu trúc chỉ mục. Thời gian xĩa bản ghi: Thơi gian cần thiết để xĩa bản ghi, bao gồm thời gian để tìm, xĩa bản ghi và thời gian cập nhật lại cấu trúc chỉ mục. Thường ta muốn trong một file cĩ thể cĩ nhiều hơn một chỉ mục. Chẳng hạn, ta muốn tìm kiếm một quyển sách theo nhiều tiêu chí: tác giả, tên sách, chủ đề, Thuộc tính hay một nhĩm thuộc tính dùng để tìm kiếm các bản ghi trong file gọi là khĩa tìm kiếm (search key – Khái niệm này khác với khái niệm khĩa chính, khĩa ứng cử hay siêu khĩa). 2.2. Các chỉ mục cĩ thứ tự 2.2.1. Chỉ mục chính (Primary Indexes) Là chỉ mục được thiết lập trên trường khĩa chính của file được sắp xếp thứ tự theo khĩa chính. File chỉ mục là một file cĩ thứ tự gồm hai trường với các bản ghi cĩ độ dài cố định. Một bản ghi trong file chỉ mục, gồm hai phần: [Ki, Pi] trong đĩ Ki là giá trị tương ứng với giá trị trên trường khĩa đã sắp thứ tự, Pi chứa địa chỉ khối chứa bản ghi cĩ khĩa Ki của file dữ liệu. Với chỉ mục chính: số bản ghi trong file chỉ mục bằng số khối trong file dữ liệu. Hình sau minh họa cấu trúc file chỉ mục chính thiết lập trên trường khĩa (Name) cĩ sắp thứ tự trong file Employee:
  16. 16 Hình 2.1: Chỉ mục chính thiết lập trên trường khĩa cĩ thứ tự Tìm kiếm với điều kiện trên trường khĩa: Search (K) Xác định bản ghi thứ i của file chỉ mục thỏa mãn: Ki ≤ K < Ki+1. Dựa vào con trỏ Pi trong file chỉ mục đọc khối đĩa chứa bản ghi cần tìm vào bộ đệm và tiến hành tìm kiếm bản ghi. Xét một file dữ liệu cĩ thứ tự với 30000 bản ghi với độ dài cố định là 100 byte và tổ chức theo kiểu khơng kéo dài (unspanned) được lưu trên đĩa với kích thước khối đĩa là 1024 byte. Như vậy một khối đĩa lưu được bfr = 1024 / 100 = 10 bản ghi. Do vậy, số khối cần để lưu file dữ liệu là: b = 30000 / 10 = 3000 khối đĩa. Để tìm kiếm một bản ghi cĩ trường khĩa là K ta sử dụng phương pháp tìm kiếm nhị phân mất: log2 (b) = log2 (3000) = 12. Giả sử tạo file chỉ mục chính cĩ số bản ghi bằng số khối trong file dữ liệu. Mỗi bản ghi gồm 2 trường: trường khĩa kích thước 9 byte, kích thước con trỏ là 6 byte thì một bản ghi trong file chỉ mục cĩ độ dài 15 byte. Mỗi khối đĩa sẽ lưu
  17. 17 được bfri = 1024 / 15 = 68 bản ghi của file chỉ mục. Do vậy để lưu file chỉ mục cần bi = 30000 / 68 = 45 khối đĩa. Khi đĩ muốn tìm bản ghi cĩ giá trị khĩa K cần: log2 (45) + 1 (truy cập file dữ liệu) = 7. Như vậy rõ ràng nếu cĩ file chỉ mục thì việc tìm kiếm trên trường khĩa sẽ nhanh hơn nhiều lần. 2.2.2. Chỉ mục cụm (Clustering Indexes) Nếu các bản ghi trong file dữ liệu được sắp sếp thứ tự trên trường khơng khĩa (khơng cĩ giá trị duy nhất cho mỗi bản ghi), ta cĩ thể tạo ra một kiểu chỉ mục khác – gọi là chỉ mục cụm – để tăng tốc độ truy xuất tới các bản ghi với điều kiện trên trường khơng khĩa. Hình 2.2: Chỉ mục cụm trên trường khơng khĩa (DeptNumber) cĩ sắp thứ tự 2.2.3. Chỉ mục phụ (Secondary Indexes) Chỉ mục phụ cung cấp một phương thức để truy cập nhanh tới file dữ liệu trên trường khơng được sắp thứ tự. Chỉ mục phụ cĩ thể áp dụng trên trường khĩa ứng cử (cĩ giá trị duy nhất với mỗi bản ghi trong file dữ liệu) hoặc trên trường khơng khĩa (cĩ giá trị giống nhau với những bản ghi khác nhau trong file dữ liệu). Nếu chỉ mục được thiết lập trên trường khĩa khơng được sắp xếp thì mỗi bản ghi trên file dữ liệu sẽ cĩ tương ứng một bản ghi trong file chỉ mục (Khác với chỉ mục chính: Số bản ghi trong file chỉ mục chính chỉ bằng số khối cần để lưu trữ file dữ liệu). Do vậy chỉ mục phụ cần nhiều khơng gian lưu trữ và thời gian tìm kiếm hơn so với chỉ mục chính.
  18. 18 Hình 2.3: Chỉ mục phụ trên trường khĩa khơng sắp thứ tự Giả sử cĩ một file dữ liệu với r = 30000 bản ghi. Các bản ghi cĩ kích thước cố định R = 100 byte. Lưu trên đĩa với kích thước khối đĩa là B = 1024 byte. Khi đĩ file dữ liệu sẽ được lưu trong 3000 khối. Khi cần tìm kiếm trên một trường khơng sắp thứ tự: Nếu khơng cĩ file chỉ mục phụ: Thực hiện tìm kiếm tuần tự trung bình cần 3000 / 2 = 1500 lần truy cập khối. Nếu tạo một file chỉ mục phụ trên trường cần tìm kiếm kích thước 9 byte, kích thước con trỏ là 6 byte, khi đĩ kích thước một bản ghi trong file chỉ mục phụ là 15 byte. Như vậy một khối đĩa sẽ lưu được 1024 / 15 = 68 bản ghi của file chỉ mục phụ. Do chỉ mục được xây dựng trên trường khĩa khơng được sắp thứ tự nên số bản ghi trong file chỉ mục bằng số bản ghi trong file dữ liệu (như hình trên). Do vậy số khối cần để lưu file chỉ mục phụ là: 30000 / 68 = 442 khối. Như vậy để tìm kiếm cần: log2 (442) + 1 (lần truy cập khối đĩa trên file dữ liệu) = 10 lần truy cập khối đĩa.
  19. 19 Như vậy file chỉ mục phụ là giải pháp hiệu quả để giảm thời gian tìm kiếm trên trường khĩa khơng được sắp xếp. Ta cũng cĩ thể tạo chỉ mục phụ trên trường khơng khĩa. Khi đĩ sẽ cĩ nhiều bản ghi trên file dữ liệu cĩ cùng giá trị trên trường cần tạo chỉ mục. Khi đĩ giải pháp thơng dụng là tạo thêm một file trung gian (giữa file chỉ mục phụ với file dữ liệu) để xử lý các bản ghi cĩ giá trị trùng nhau trên trường tìm kiếm. Hình 2.4: Chỉ mục phụ trên trường khơng khĩa khơng sắp thứ tự 2.3. Chỉ mục cây B+ 2.3.1. Tĩm lược về cây tìm kiếm Cây là một khái niệm trong cấu trúc dữ liệu. Cây được tạo thành từ các nút; Mỗi nút trong cây (trừ nút gốc) đều cĩ một nút cha và cĩ thể cĩ hoặc khơng cĩ nút con. Một nút khơng cĩ nút con nào gọi là nút lá. Mức của nút gốc là 0. Mức của nút con = Mức của nút cha + 1.
  20. 20 Cây tìm kiếm bậc p là một cây mà mỗi nút chứa nhiều nhất p – 1 giá trị tìm kiếm và p con trỏ theo thứ tự: với q ≤ p. Mỗi con trỏ Pi trỏ tới một nút con hoặc khơng trỏ tới nút nào (Null Pointer). Cĩ hai ràng buộc trên cây: Trong mỗi nút: K1 , P2, , , Pq-1, ; Trong đĩ: q ≤ p. Pi là một tree pointer – trỏ tới một nút khác trong cây. Pri là một con trỏ dữ liệu (data pointer – trỏ tới bản ghi cĩ giá trị trên trường khĩa tìm kiếm là Ki, hoặc trỏ tới khối đĩa chứa bản ghi đĩ).
  21. 21 Hình 2.6: Một nút trong B – tree với q-1 giá trị tìm kiếm Trong mỗi nút trong: K1 ; Trong đĩ: q ≤ p. Pi là một tree pointer – trỏ tới một nút khác trong cây:
  22. 22 Trong mỗi nút trong: K1 , , , ; Trong đĩ: q ≤ p. Pri là một con trỏ dữ liệu (data pointer – trỏ tới bản ghi cĩ giá trị trên trường khĩa tìm kiếm là Ki, hoặc trỏ tới khối đĩa chứa bản ghi đĩ). Pnext là một tree pointer – trỏ đến nút lá tiếp theo trong cây. Trong mỗi nút lá: K1 < K2 < < Kq-1, q ≤ p. Mỗi nút lá cĩ ít nhất p/2 giá trị. Tất cả các nút lá đều cĩ cùng mức. Hình sau minh họa B+ – Tree với p = 3: sau khi chèn: 8, 5, 1, 7, 3, 12, 9, 6 Hình 2.8: B+ – tree bậc 3
  23. 23 2.4. Băm tĩnh và băm động 2.4.1. Băm tĩnh (Static Hashing) Nhược điểm của tổ chức file tuần tự là phải truy cập tới cấu trúc file chỉ mục để xác định vị trí của bản ghi dữ liệu, hoặc phải thực hiện tìm kiếm nhị phân. Khi kích thước file lớn thì kỹ thuật này vẫn sử dụng nhiều thao tác vào ra. Tổ chức file sử dụng kỹ thuật hàm băm sẽ giúp tránh được việc truy xuất tới file chỉ mục. Trong kỹ thuật tổ chức file sử dụng hàm băm, ta sử dụng thuật ngữ bucket để chỉ một đơn vị lưu trữ, nĩ cĩ thể lớn hơn hay nhỏ hơn kích thước khối đĩa (disk block) và cĩ thể lưu được một số bản ghi của file dữ liệu. Gọi K là tập các giá trị khĩa tìm kiếm, B là tập các địa chỉ của các bucket. Hàm băm h là hàm ánh xạ một giá trị từ K sang B. Bản ghi với khĩa tìm kiếm là Ki sẽ được thêm vào bucket cĩ địa chỉ h(Ki). Để tìm kiếm bản ghi với khĩa tìm kiếm Ki, ta thực hiện tìm kiếm ở bucket h(Ki). Hàm băm khơng chỉ ứng dụng trong việc tổ chức file mà cịn cĩ ứng dụng trong việc tạo chỉ mục. Khi tạo chỉ mục băm ta áp dụng hàm băm trên trường khĩa tìm kiếm để xác định địa chỉ của bucket sau đĩ lưu giá trị khĩa tìm kiếm cùng con trỏ tới bản ghi dữ liệu vào bucket đĩ. Hình sau minh họa chỉ mục băm thứ cấp (secondary hash index) trên file instructor với khĩa tìm kiếm là ID. Hàm băm trong trường hợp này tính tổng các chữ số của ID đem chia lấy dư cho 8. Hình 2.9: Chỉ mục băm với khĩa tìm kiếm là ID trên file Instrutor
  24. 24 2.4.2. Băm động (Dynamic Hashing) Với kỹ thuật băm tĩnh, tập các địa chỉ bucket là cố định nên sẽ gặp khĩ khăn khi kích thước của file dữ liệu tăng lên theo thời gian. Để giải quyết vấn đề này, một kỹ thuật gọi là băm động được đề xuất. Kỹ thuật băm động là kỹ thuật cho phép sửa đổi hàm băm để phù hợp với sự tăng hoặc giảm của file cơ sở dữ liệu. Sau đây ta sẽ xem xét một dạng băm động gọi là hàm băm cĩ thể mở rộng (Extendable hashing). Chọn một hàm băm h với các tính chất đều, ngẫu nhiên và cĩ miền giá trị lớn, ví dụ một số nguyên 32 bit. Tại một thời điểm ta chỉ sử dụng gd bít để đánh địa chỉ bucket. Giá trị gd này gọi là độ sâu tồn cục (global depth) dùng để xác định địa chỉ của bucket từ giá trị h(K) của khĩa tìm kiếm K. Ví dụ với gd = 2 thì cần dùng 2 bít sau cùng của h(K) để xác định địa chỉ của bucket. Gắn với mỗi bucket là một số ld gọi là độ sâu cục bộ (local depth) - số bit tối thiểu cĩ thể phân biệt các mục trong bucket đĩ. Hình dưới đây minh họa cấu trúc của hàm băm cĩ thể mở rộng với gd = 2 và các ld = 2: Hình 2.10: Hàm băm cĩ thể mở rộng Khi muốn tìm một mục dữ liệu với giá trị khĩa tìm kiếm là K ta làm như sau: Tính giá trị của băm h(K). Biểu diễn h(K) dưới dạng nhị phân Sử dụng gd bít thấp của h(K) để xác định bucket tương ứng. Xác định vị trí của h(K) trong bucket tìm được và theo con trỏ dữ liệu tới bản ghi dữ liệu cần tìm. Để đơn giản cho việc minh họa, xét hàm băm h(K) = K mod 1000. Lúc này muốn tìm bản ghi với khĩa tìm kiếm K = 5 ta làm như sau: Tính h(K) = K mod 1000 = 5. Biểu diễn 5 dưới dạng nhị phân: 101. Sử dụng gd = 2 bít thấp của h(K): 01 xác định được bucket tương ứng là Bucket B. Tìm vị trí của 5 trong bucket B và theo con trỏ dữ liệu tới vị trí bản ghi cần tìm trong file dữ liệu.
  25. 25 Khi muốn thêm một giá trị h(K) ta làm như sau: Thực hiện tìm kiếm như trên để xác định bucket tương ứng: Nếu bucket chưa đầy thì chèn h(K) vào bucket đĩ. Nếu bucket đầy thì thực hiện tách bucket đĩ ra làm hai và tăng gd lên 1. Hình sau minh họa kết quả sau khi thêm một giá trị h(K) = 13: Hình 2.11: Cấu trúc hàm băm trong hình 2.10 sau khi thêm h(K) = 13 Hình sau minh họa kết quả sau khi thêm một giá trị h(K) = 20 (Bucket đầy Thực hiện tách): Hình 2.12: Cấu trúc hàm băm trong hình 2.11 sau khi thêm h(K) = 20
  26. 26 2.5. Câu hỏi ơn tập chƣơng 2 2.5.1. Trình bày cấu trúc file chỉ mục chính 2.5.2. Trình bày cấu trúc file chỉ mục cụm 2.5.3. Trình bày cấu trúc file chỉ mục phụ 2.5.4. Trình bày về cấu trúc B – tree 2.5.5. Trình bày về cấu trúc B+ – tree 2.5.6. Trình bày kỹ thuật băm tĩnh, băm động 2.5.7. Xem lại cú pháp tạo chỉ mục trong SQL 2.5.8. Xét một file dữ liệu với các thơng tin sau: File cĩ 50000 bản ghi Các bản ghi cĩ độ dài cố định 100 byte tổ chức theo kiểu khơng kéo dài Trường khĩa chính cĩ kích thước 9 byte File được lưu trên đĩa cĩ kích thước khối đĩa là 512 byte Hãy so sánh số lần truy xuất khối đĩa khi thực hiện tìm kiếm trên trường khĩa chính trong các trường hợp sau: File khơng sắp thứ tự File được sắp thứ tự trên trường khĩa chính File được sắp thứ tự trên trường khĩa chính và cĩ file chỉ mục chính với kích thước con trỏ là 6 byte 2.5.9. Xét một file dữ liệu với các thơng tin như phần 2.6.7. Hãy so sánh số lần truy xuất khối đĩa khi thực hiện tìm kiếm trên trường khĩa ứng cử K trong các trường hợp sau: File khơng sắp thứ tự trên trường khĩa ứng cử K File khơng được sắp thứ tự trên trường khĩa ứng cử K nhưng cĩ file chỉ mục thiết lập trên trường khĩa ứng cử K 2.5.10. Cho B – tree ban đầu rỗng và tập khĩa chèn vào theo thứ tự sau: 2, 3, 5, 7, 11, 17, 19, 23, 29, 31. Hãy biểu diễn B – tree bậc: 4 6 8 2.5.11. Hãy biểu diễn lại B – tree ở phần 2.6.9 sau mỗi thao tác: Insert 9 Delete 10 Insert 8 Delete 23 Delete 19
  27. 27 2.5.12. Làm lại yêu cầu như phần 2.6.9 và 2.6.10 với cấu trúc B+ – tree 2.5.13. Giả sử cĩ một cấu trúc hàm băm cĩ thể mở rộng (Extendable Hashing) trên file chứa các bản ghi với trường khĩa tìm kiếm K như sau: 2, 3, 5, 7, 11, 17, 19, 23, 29, 31. Hãy chỉ ra cấu trúc của hàm băm cho file này nếu hàm băm là: h(x) = x mod 8 và mỗi buket cĩ thể chứa được 3 bản ghi. 2.5.14. Chỉ ra cấu trúc hàm băm cĩ thể mở rộng ở phần 2.6.12 sau mỗi thao tác dưới đây: Delete 11 Delete 31 Insert 1 Insert 15
  28. 28 CHƢƠNG 3: TỐI ƢU HĨA TRUY VẤN 3.1. Giới thiệu Trong chương này chúng ta sẽ nghiên cứu một kỹ thuật tối ưu hĩa vấn tin cơ bản. Khi diễn tả truy vấn bằng một ngơn ngữ khai báo, như ngơn ngữ vấn tin quan hệ, hệ thống cơ sở dữ liệu rất khĩ thực thi nhanh chĩng. Với nhiều cách cài đặt một câu vấn tin, giai đoạn tối ưu hĩa phải chọn ra được một cách cài đặt tốt nhất. Quá trình xử lý một truy vấn: Bước 1: o Bộ quét: Truy vấn được bằng một biểu thức. Bộ quét sẽ duyệt truy vấn để biết truy vấn được viết bằng ngơn ngữ nào. o Bộ kiểm tra: Kiểm tra cú pháp của truy vấn xem cĩ hợp lệ hay khơng. o Xác nhận tính hợp lệ (các quan hệ, thuộc tính sử dụng trong truy vấn đã được khai báo hay chưa? Sau bước 1 truy vấn sẽ được biểu diễn bằng một biểu thức đại số quan hệ) Bước 2: o Bộ tối ưu: Tìm ra phương pháp thực hiện tối ưu cho truy vấn. o Sau bước này sẽ cho ra một biểu thức đại số quan hệ với chi phí thực hiện nhỏ nhất. Bước 3: o Bộ tạo mã sẽ tạo ra chương trình bằng ngơn ngữ trong để thực hiện truy vấn. o Thực thi chương trình để lấy về kết quả. 3.2. Các phép biến đổi tƣơng đƣơng Các truy vấn được viết bằng các ngơn ngữ bậc cao, ví dụ SQL, sau bước 1 của quá trình xử lý truy vấn, truy vấn được biểu diễn bằng biểu thức đại số quan hệ. Ví dụ:  SELECT * FROM R ↔ E(R) WHERE E  SELECT A1, A2, , Ai FROM R ↔ F (R)  SELECT * FROM R, S ↔ WHERE F Tối ưu bằng biến đổi biểu thức đại số quan hệ: Biến đổi thứ tự thực hiện các phép tốn của biểu thức đại số quan hệ sao cho các phép tốn một ngơi được thực hiện trước các phép tốn hai ngơi, do các phép tốn chiếu, chọn thì cĩ chi phí nhỏ hơn so với các phép kết nối, tích đề các.
  29. 29 Một số phép biến đổi tương đương: o Tách điều kiện trong phép chọn: o Tính chất giao hốn của phép chọn: o Dãy các phép chiếu liên tiếp: o Phép chọn – phép tích đề các và phép kết nối : . . o Tính chất giao hốn của phép kết nối : o Tính chất giao hốn của phép kết nối tự nhiên: o Tính chất kết hợp của phép kết nối tự nhiên: o Tính chất kết hợp của phép kết nối : . , nếu các thuộc tính trong chỉ thuộc và . o Phép chọn và phép kết nối : . , nếu các thuộc tính trong 0 chỉ thuộc . . nếu các thuộc tính trong chỉ thuộc , các thuộc tính trong 2 chỉ thuộc . o Phép chiếu và phép kết nối : . , nếu:  Các thuộc tính trong chỉ thuộc .  Các thuộc tính trong chỉ thuộc .  Các thuộc tính trong đều cĩ trong và . .  Các thuộc tính trong chỉ thuộc .  Các thuộc tính trong chỉ thuộc .  Các thuộc tính trong chỉ cĩ trong , liên quan đến nhưng khơng thuộc .
  30. 30  Các thuộc tính trong chỉ cĩ trong , liên quan đến nhưng khơng thuộc . o Phép hợp – Phép giao và phép trừ . Tính chất giao hốn:   . Tính chất kết hợp:   . Tính chất phân phối của phép chọn qua phép hợp – giao – trừ:   . Tính chất phân phối của phép chiếu qua phép hợp: 3.3. Thuật tốn tối ƣu hĩa cây đại số quan hệ 3.3.1. Thuật tốn Bước 1: Biểu diễn truy vấn dưới dạng cây với lá là các quan hệ, đỉnh trong là các phép tốn đại số quan hệ. Bước 2: Áp dụng các phép biến đổi tương đương đẩy các phép tốn một ngơi xuống dưới các phép tốn hai ngơi. Bước 3: Thêm vào các phép chiếu để giảm bớt kích thước của các quan hệ. 3.3.2. Ví dụ Xét hai bảng nhân viên và đơn vị sau: NhanVien (MaNV, MasoDV, HoTen, NgaySinh, GioiTinh, Luong) DonVi(MaDV, TenDV) Truy vấn đưa ra họ tên của các nhân viên nữ ở đơn vị cĩ tên là „PhongDaoTao‟:
  31. 32 3.4. Câu hỏi ơn tập chƣơng 3 3.4.1. Trình bày các bước trong quá trình xử lý truy vấn. 3.4.2. Trình bày các phép biến đổi tương đương. 3.4.3. Trình bày thuật tốn tối ưu hĩa cây đại số quan hệ. 3.4.4. Cho hai bảng nhân viên và đơn vị sau: NhanVien (MaNV, MasoDV, HoTen, NgaySinh, GioiTinh, Luong) DonVi(MaDV, TenDV) Hãy viết biểu thức đại số quan hệ thực hiện truy vấn sau: Đưa ra họ tên của các nhân viên nữ ở đơn vị cĩ tên là „PhongDaoTao‟.Tối ưu hĩa truy vấn trên sử dụng phương pháp biến đổi đại số quan hệ. 3.4.5. Cho các quan hệ: o DonVi(MDV, TenDV, MaNQL, DiaDiem) o DuAn (MaDA, TenDA, KinhPhi, MaDV) Truy vấn nào dưới đây đã tối ưu? Q1. Q2. Q3. Q4.
  32. 33 CHƢƠNG 4: GIAO DỊCH TRONG CƠ SỞ DỮ LIỆU 4.1.Giới thiệu Thuật ngữ giao dịch (Transaction) đề cập tới một tập hợp các lệnh tạo thành một đơn vị làm việc logic, hoặc nĩ được thực hiện một cách đầy đủ hoặc bị hủy bỏ hồn tồn. Ví dụ 3.1: Chuyển tiền từ tài khoản A sang tài khoản B là một giao dịch: Kiểm tra tiền trong tài khoản A (cĩ X khơng?). A = A – X. B = B + X. Thường giao dịch được tạo ra bởi các chương trình người dùng được viết trong ngơn ngữ xử lý dữ liệu bậc cao hoặc ngơn ngữ lập trình (vd: SQL, C++, Java). Mục dữ liệu (data item) là đơn vị dữ liệu trong CSDL. Bản chất, kích thước của các mục dữ liệu do nhà thiết kế chọn. Chúng được lựa chọn sao cho việc truy xuất dữ liệu đạt hiệu quả nhất. Ví dụ trong mơ hình dữ liệu quan hệ, ta cĩ thể chọn mục dữ liệu là: các quan hệ, các bộ, hay các thành phần của bộ. Kích thước của các mục dữ liệu mà hệ thống sử dụng gọi là độ mịn của hệ thống (granularity). Bộ lập lịch (Scheduler) là một thành phần của hệ thống CSDL chịu trách nhiệm tạo ra một lịch biểu (thứ tự thực hiện) các thao tác trong các giao dịch. 4.2.Các tính chất và trạng thái của giao dịch 4.2.1. Tính chất của giao dịch Để đảm bảo tính tồn vẹn của dữ liệu, hệ cơ sở dữ liệucần duy trì các tính chất sau của giao dịch: Tính nguyên tử (Atomicity): Hoặc tồn bộ các thao tác của giao dịch được phản ánh đúng đắn trong cơ sở dữ liệu hoặc khơng cĩ gì cả. Tính nhất quán (Consistency): Sự thực hiện của một giao dịch phải bảo đảm tính nhất quán của cơ sở dữ liệu. Tính cơ lập (Isolation): Nhiều giao dịch cĩ thể thực thi đồng thời nhưng mỗi giao dịch khơng cần biết đến các giao dịch khác đang thực hiện đồng thời. Các kết quả trung gian của giao dịch phải được che giấu trước các giao dịch khác. Tính lâu bền (Durability): Sau khi giao dịch hồn thành, các thay đổi đã được tạo ra đối với cơ sở dữ liệu vẫn cịn ngay cả khi xảy ra sự cố hệ thống. 4.2.2. Trạng thái của giao dịch Khi giao dịch bắt đầu thực hiện nĩ vào trạng thái active và cĩ thể thực hiện thao tác đọc, ghi các mục dữ liệu.Khi kết thúc thao tác cuối cùng giao dịch đạt tới trạng thái partially committed. Tại thời điểm này, giao dịch đã hồn thành sự thực hiện của nĩ, nhưng nĩ vẫn cĩ thể bị bỏ dở do các thay đổi cĩ thể vẫn lưu tạm thời trong bộ nhớ chính và như thế một sự cố phần cứng vẫn cĩ thể
  33. 34 ngăn cản sự hồn tất của giao dịch. Nếu khơng cĩ sự cố, tất cả các giao dịch đều hồn tất thành cơng (tất cả các thao tác trong giao dịch đều được phản ánh trong cơ sở dữ liệu), khi đĩ giao dịch được “bàn giao” (commited).Tuy nhiên, trong thực tế một giao dịch cĩ thể khơng hồn tất sự thực hiện của nĩ.Giao dịch như vậy được gọi là bị bỏ dở (abort).Để đảm bảo được tính nguyên tử, một giao dịch bị bỏ dở khơng được phép làm ảnh hưởng tới trạng thái của cơ sở dữ liệu.Như vậy, tất cả thay đổi được tạo ra trước đĩ phải bị huỷ bỏ (rollback). Active: Giao dịch sẽ đi vào trạng thái Active khi bắt đầu và trạng thái này sẽ được duy trì trong khi giao dịch đang thực hiện. Partially Committed: Sau khi thao tác cuối cùng trong giao dịch được thực hiện. Failed: Sau khi phát hiện rằng sự thực hiện khơng thể tiếp tục được nữa. Aborted: Sau khi rollback và cơ sở dữ liệuđã phục hồi lại trạng thái của nĩ trước khi khởi động giao dịch. Committed: Giao dịch hồn tất thành cơng(tất cả các thao tác được phản ánh đầy đủ trong cơ sở dữ liệu). Sơ đồ trạng thái tương ứng với một giao dịch như sau: Hình 4.1: Các trạng thái của giao dịch 4.3.Lịch biểu 4.3.1. Khái niệm lịch biểu Lịch biểu: Là một dãy (cĩ thứ tự) các thao tác của một tập các giao dịch mà trong đĩ thứ tự của các thao tác trong mỗi giao dịch được bảo tồn. Ví dụ 3.2: Xét hai giao dịch chuyển tiền: 10$ từ tài khoản A sang tài khoản B 20$ từ tài khoản B sang tài khoản C.
  34. 35 Hình 4.2: Lịch biểu 4.3.2. Tính khả tuần tự của lịch biểu Lịch biểu tuần tự (Serial Schedule): Là lịch biểu mà trong mỗi giao dịch các thao tác được thực hiện kế tiếp nhau, khơng cĩ thao tác của giao dịch khác xen vào (Thực hiện lần lượt, hết giao dịch này đến giao dịch khác). Khơng thể cĩ đụng độ trong một lịch biểu tuần tự. Với một tập S gồm n giao dịch {T1, T2, , Tn} sẽ cĩ n! lịch biểu tuần tự. Hình 3.3 là một ví dụ về lịch biểu tuần tự của hai giao dịch T1 và T2. Hình 4.3: Lịch biểu tuần tự Lịch biểu gọi là khả tuần tự (Serializable): nếu nĩ tương đương với một lịch biểu tuần tự. Tương đương theo nghĩa cho ra cùng một trạng thái CSDL sau khi kết thúc việc thực hiện lịch biểu). Lịch biểu bất khả tuần tự nếu nĩ khơng tương đương với một lịch biểu tuần tự. 4.4.Thuật tốn kiểm tra tính khả tuần tự của lịch biểu Input: S {T1, T2, , Tn} Output: S khả tuần tự hay k? Thuật tốn: o Xây dựng đồ thị phụ thuộc G: . Nút: là các giao dịch.
  35. 36 . Cung Ti Tj: o Nếu G khơng cĩ chu trình thì lịch biểu S là khả tuần tự, ngược lại lịch biểu S là bất khả tuần tự. Ví dụ: Lịch biểu S của hai giao dịch T1, T2 và đồ thị phụ thuộc G của S: Hình 3.4: Ví dụ kiểm tra tính khả tuần tự của lịch biểu Trong ví dụ này ta thấy đồ thị G cĩ chu trình, do vậy lịch biểu S là bất khả tuần tự.
  36. 37 4.5.Câu hỏi ơn tập chƣơng 4 4.5.1. Trình bày khái niệm về giao dịch. Cho ví dụ. 4.5.2. Trình bày bốn tính chất của giao dịch. 4.5.3. Trình bày khái niệm lịch biểu. Cho ví dụ. 4.5.4. Trình bày các khái niệm lịch biểu tuần tự, lịch biểu bất tuần tự vàlịch biểu khả tuần tự. Cho ví dụ. 4.5.5. Trình bày thuật tốn kiểm tra tính khả tuần tự của lịch biểu 4.5.6. Lịch biểu nào dưới đây là khả tuần tự? R2(Y), R1(X), R1(Y), R3(X), W3(X), W2(Y), W1(X) R2(Y), R1(X), R1(Y), R3(Z), W3(Z), W2(Y), W1(X) R2(Y), R1(X), R1(Y), R3(X), W2(Y), W1(X), W3(X) R1(X), R1(Y), R3(X), R2(Y), W2(Y), W1(X), W3(X) 4.5.7. Cho đồ thị phụ thuộc của lịch biểu S. Lịch biểu nào dưới đây là lịch biểu tuần tự tương đương với S: T1 T2 T3 T4 T1 T2 T2 T1 T3 T4 T4 T2 T3 T1 T4 T3 T1 T2 T3 T4
  37. 38 CHƢƠNG 5: ĐIỀU KHIỂN ĐỒNG THỜI VÀ KHƠI PHỤC HỆ THỐNG 5.1. Các giao thức dựa vào khĩa 5.1.1. Mơ hình khĩa nhị phân Một khĩa nhị phân (Binary Lock) cĩ hai trạng thái (giá trị): Locked và Unlocked (1 hoặc 0). Lock(X): Khĩa trên mục dữ liệu X. Lock(X) = 1 nghĩa là mục dữ liệu X đã bị khĩa bởi một giao dịch; Các giao dịch khác nếu cĩ yêu cầu truy cập mục dữ liệu này sẽ phải đợi đến khi Lock(X) = 0. Hai thao tác lock_item, unlock_item được sử dụng với khĩa nhị phân. o lock_item(X); B: if LOCK(X)=0 (*item is unlocked*) then LOCK(X) 1 (*lock the item*) else begin wait (until LOCK(X)=0 and the lock manager wakes up the transaction); go to B; end; o unlock_item(X); LOCK(X) 0 (*unlock the item*) if any transactions are waiting then wakeup one of the waiting transations; Trong mơ hình khĩa nhị phân, mọi giao dịch phải tuân theo các luật sau: o Một giao dịch phải thực hiện lock_item(X) trước các thao tác read_item(X), write_item(X). o Một giao dịch phải thực hiện unlock_item(X) sau khi đã hồn tất các thao tác read_item(X), write_item(X). o Một giao dịch khơng được thực hiện lock_item(X) nếu nĩ đang giữ khĩa trên X (Hold the lock). o Một giao dịch khơng được thực hiện unlock_item(X) nếu nĩ khơng giữ khĩa trên X. 5.1.2. Mơ hình khĩa đọc – ghi (chia sẻ – độc quyền) Cho phép nhiều hơn một giao dịch cĩ thể truy cập trên cùng một mục giữ liệu X nếu các giao dịch đĩ chỉ đọc dữ liệu. Nếu một giao dịch muốn thực hiện ghi trên mục dữ liệu X, nĩ phải cĩ độc quyền truy cập trên X. Một khĩa trên mục dữ liệu X: LOCK(X) cĩ 3 trạng thái: “read – locked” (“share – locked”), “write – locked” (“exclusive – locked”) và “unlocked”.
  38. 39 Các thao tác: read_lock, write_lock, unlock được sử dụng với khĩa đọc – ghi. Trong mơ hình khĩa đọc – ghi, một bản ghi trong bảng khĩa (Lock Table) gồm 4 trường: Data item name LOCK No_of_reads Locking Transactions o Data item name: Tên mục dữ liệu. o LOCK: read_locked hoặc write_locked. o Nếu LOCK là write_locked: Locking transactions là một giao dịch duy nhất đang giữ khĩa ghi trên mục dữ liệu. o Nếu LOCK là read_locked: Locking transactions là một danh sách các giao dịch giữ khĩa đọc trên mục dữ liệu. No_of_reads: Số lượng các giao dịch đang giữ khĩa đọc trên X. Trong mơ hình khĩa đọc – ghi, mọi giao dịch phải tuân theo các luật sau: o Một giao dịch phải thực hiện read_lock(X) hoặc write_lock(X) trước khi read_item(X). o Một giao dịch phải thực hiện write_lock(X) trước khi write_item(X). o Một giao dịch phải thực hiện unlock_item(X) sau khi đã hồn tất các thao tác read_item(X), write_item(X). o Một giao dịch khơng được thực hiện read_lock(X) nếu nĩ đang giữ khĩa đọc, hoặc ghi trên X (Hold the lock).1 o Một giao dịch khơng được thực hiện write_lock(X) nếu nĩ đang giữ một khĩa đọc trên X.1 o Một giao dịch khơng được thực hiện unlock_item(X) nếu nĩ khơng giữ khĩa trên X. Hình 4.1 dưới đây chỉ ra quá trình xử lý yêu cầu khĩa trong mơ hình khĩa chia sẻ - độc quyền. Hình 5.1: Xử lý yêu cầu khĩa trong mơ hình khĩa chia sẻ – độc quyền 1Các luật này cĩ thể được nới lỏng.
  39. 40 5.1.3. Giao thức khĩa 2 pha Giao thức khĩa hai pha (Two – phase locking protocol – 2PLP) là một giao thức đảm bảo tính khả tuần tự.Một giao dịch T được gọi là tuân theo giao thức khĩa hai pha nếu trong T tất cả các yêu cầu khĩa (read_lock, write_lock) được đưa ra trước yêu cầu mở khĩa (unlock). Với giao thức này, các giao dịch được chia thành hai pha: o Pha tăng trưởng: (expanding or growing phase): Trong pha này giao dịch được phép khĩa (read_lock, write_lock) trên các mục dữ liệu nhưng khơng được phép mở khĩa (unlock) bất cứ một mục dữ liệu nào. o Pha thu lại (shrinking phase): Trong pha này, giao dịch được phép mở khĩa trên các mục dữ liệu nhưng khơng được phép khĩa thêm bất kỳ một mục dữ liệu nào. Hình 5.2: Giao thức khĩa 2 pha Ví dụ: Hình 5.3: Giao dịch T1 và T2 khơng tuân theo 2PLP Giao dịch T1’ và T2’ tuân theo 2PLP Các biến thể của giao thức khĩa 2 pha: o Conservative 2PLP: Yêu cầu giao dịch phải khĩa tất cả các mục dữ liệu cần truy cập trước khi thực thi giao dịch, bằng cách đưa ra các tập: read-set và write-set. (Giao thức này cĩ khả năng ngăn ngừa deadlock – trình bày trong các slide kế tiếp)
  40. 41 o Strict 2PLP: Yêu cầu giao dịch khơng được giải phĩng bất kỳ khĩa độc quyền nào (exclusive lock) cho đến khi commit hoặc abort. o Rigorous 2PLP: Yêu cầu giao dịch khơng được giải phĩng bất kỳ khĩa nào cho đến khi commit hoặc abort. Hình 5.4: Giao thức khĩa 2 pha và các biến thể 5.1.4. Deadlock Deadlock là hiện tượng xảy ra khi mỗi giao dịch T trong một tập S (gồm hai hay nhiều giao dịch) đợi một số mục bị khĩa bởi các giao dịch khác trong S. Ví dụ: Hai giao dịch đang trong trạng thái Deadlock: T1 T2 read_lock(Y) read_item(Y) read_lock(X) read_item(X) write_lock(X) write_lock(Y) Trong ví dụ này giao dịch T1 đang đợi khĩa ghi trên mục dữ liệu X nhưng X lại đang bị khĩa bởi giao dịch T2; cịn giao dịch T2 đang đợi khĩa ghi trên mục dữ liệu Y nhưng Y lại đang bị khĩa bởi giao dịch T1.Hai giao dịch này đợi lẫn nhau và ta gọi hiện tượng này là Deadlock. 5.1.4.1. Các chiến lược ngăn cản Deadlock Một chiến lược được sử dụng để giải quyết vấn đề Deadlock là sử dụng các giao thức cĩ khả năng ngăn cản Deadlock (Deadlock prevention protocol).Tuy nhiên các giao thức này ít được sử dụng trong thực tế. Conservative two – phase locking là giao thức được sử dụng để ngăn cản Deadlock.Giao thức này yêu cầu giao dịch phải khĩa tất cả các mục dữ liệu cần truy cập trước khi thực thi giao dịch.Nếu một yêu cầu khĩa nào đĩ khơng được đáp ứng thì tất cả yêu cầu khĩa cịn lại sẽ bị bỏ qua,
  41. 42 giao dịch sẽ phải đợi và thử lại ở lần sau. Tuy nhiên, giao thức này lại giới hạn việc thực thi đồng thời các giao dịch. Một số chiến lược khác để ngăn cản Deadlock là quyết định làm gì với các giao dịch liên quan trong tình huống Deadlock: cĩ thể là chặn lại và bắt phải chờ đợi, hoặc bỏ qua. Những chiến lược này sử dụng khái niệm nhãn thời gian của giao dịch (Transaction Timestamp). Nhãn thời gian của một giao dịch T (Ký hiệu TS(T)) là một định danh duy nhất được gán cho T khi T bắt đầu. Nếu giao dịch T1 bắt đầu trước giao dịch T2 thì TS(T1) < TS(T2). Hai chiến lược ngăn ngừa cản Dealock sử dụng nhãn thời gian là Wait – Die và Wound – Wait. Giả sử giao dịch Ti cố gắng khĩa mục dữ liệu X nhưng khơng thể vì X đang bị khĩa bởi Tj với một khĩa xung đột (Conflicting lock)2. Khi đĩ: Với Wait – Die: Nếu TS(Ti) < TS(Tj) thì Ti được phép đợi (wait); ngược lại bỏ qua Ti (Ti die) và khởi động lại Ti sau với cùng nhãn thời gian. Với Wound – Wait: Nếu TS(Ti) < TS(Tj) thì bỏ qua Tj (Ti wound Tj) và khởi động lại Tj sau với cùng nhãn thời gian; ngược lại Ti phải đợi (wait). Một nhĩm các giao thức ngăn cản Deadlock mà khơng dùng tới nhãn thời gian là no waiting (NW) và cautious waiting (CW). Với NW, nếu một giao dịch khơng nhận được khĩa nĩ sẽ lập tức bị bỏ qua và khởi động lại sau một khoảng thời gian trễ mà khơng cần kiểm tra Deadlock cĩ thật sự xảy ra hay khơng, như vậy NW cĩ thể bỏ qua các giao dịch khơng cần thiết (các giao dịch khơng gây ra Deadlock). Để giảm số lượng các giao dịch bị bỏ qua khơng cần thiết CW được đề xuất.Giả sử Ti cố gắng khĩa mục dữ liệu X nhưng khơng được bởi X đang bị khĩa bởi Tj với một khĩa xung đột. Với Cautious Waiting: Nếu Tj khơng bị chặn (Khơng đợi khĩa một mục dữ liệu) thì Ti sẽ được phép đợi; ngược lại Ti sẽ bị bỏ qua. 5.1.4.2. Chiến lược phát hiện Deadlock Chiến lược này tỏ ra hiệu quả khi các giao dịch là ngắn và mỗi giao dịch chỉ yêu cầu khĩa một vài mục dữ liệu. Ý tưởng của chiến lược này là xây dựng và duy trì một đồ thị đợi (Wait – for – graph): o Một nút tương ứng với một active transaction. o Ti cố gắng khĩa mục X nhưng khơng thể do X đang bị khĩa bởi Tj với một khĩa xung đột: Tạo một cung từ Ti đến Tj; Khi Tj loại bỏ khĩa xung đột thì xĩa cung tương ứng đi. o Đồ thị cĩ chu trình Deadlock xảy ra. Khi đĩ một số giao dịch gây ra Deadlock sẽ bị loại bỏ. 2Hai khĩa được gọi là xung đột nếu tồn tại một khĩa là khĩa ghi (Write lock).
  42. 43 Hình 5.5: Wait – for – graph 5.1.4.3. Starvation Starvation: Là hiện tượng một giao dịch khơng được thực hiện trong một thời gian dài trong khi các giao dịch khác vẫn thực hiện bình thường. Starvation cĩ thể xảy ra do: o Chiến lược chờ đợi khĩa khơng cơng bằng. Giải pháp cho vấn đề này là đưa ra một chiến lược chờ đợi cơng bằng như sử dụng hàng đợi “đến trước phục vụ trước” (first – come – first – served queue), hoặc tăng độ ưu tiên của các giao dịch chờ đợi lâu. o Thuật tốn chọn các giao dịch để bỏ qua (victim selection) khơng tốt: Chọn lặp lại một giao dịch để bỏ qua. 5.2. Giao thức thứ tự nhãn thời gian (Timestamp – Ordering protocol) 5.2.1. Nhãn thời gian (Timestamp) Ta kết hợp với mỗi giao dịch Ti trong hệ thống với một nhãn thời gian cố định. Nhãn thời gian của giao dịch Ti, kí hiệuTS(Ti). Nhãn thời gian này được gán bởi hệ CSDL khi giao dịch Ti bắt đầu thực hiện.Giả sử một giao dịch Ti đã được gán nhãn thời gian TS(Ti) và một giao dịch mới Tj đi vào hệ thống, khi đĩ TS(Ti) TS(T) hoặc Write_TS(X) > TS(T) thì bỏ qua và rollback.
  43. 44 2. Nếu điều kiện 1 khơng thỏa mãn, cho phép T write_item(X) và gán lại: Write_TS(X) = TS(T). Giao dịch T muốn thực hiện read_item(X): 1. Nếu Write_TS(X) >TS(T) thì bỏ qua và rollback. 2. Nếu điều kiện 1 khơng thỏa mãn, cho phép T read_item(X) và gán lại: Read_TS(X) = Max{Read_TS(X), TS(T)}. 5.3.Phục hồi hệ thống dựa vào nhật ký giao dịch (Log-based) Một cấu trúc thường được dùng để ghi lại những thay đổi trên cơ sở dữ liệu là sổ ghi lộ trình (log). Log là một dãy các mẩu tin lộ trình (log records). Một thao tác cập nhật trên cơ sở dữ liệu sẽ được ghi nhận bằng một log record. Một log record kiểu mẫu chứa các trường sau: Định danh giao dịch ( transaction identifier ): định danh duy nhất của giao dịch thực hiện hoạt động write. Định danh hạng mục dữ liệu ( Data-item identifier ): định danh duy nhất của hạng mục dữ liệu được viết ( thường là vị trí của hạng mục dữ liệu trên đĩa ). Giá trị cũ ( Old value ): giá trị của hạng mục dữ liệu trước thao tác write. Giá trị mới ( New value ): giá trị hạng mục dữ liệu sẽ cĩ sau khi write. Cĩ một vài log record đặc biệt mang các ý nghĩa riêng. Bảng sau đây chỉ ra một số loại log record và ý nghĩa của chúng: LOẠI LOG RECORD Ý NGHĨA Giao dịch Ti đã khởi động. Giao dịch Ti đã thực hiện thao tác ghi trên hạng mục dữ liệu Xj, Xj cĩ giá trị V1 trước khi ghi và nhận giá trị V2 sau khi ghi. Giao dịch Ti đã bàn giao. Giao dịch Ti đã huỷ bỏ. Giao dịch muốn thực hiện một thao tác ghi, trước tiên phải tạo ra một log record cho thao tác ghi đĩ (trong log file), trước khi giao dịch thay đổi cơ sở dữ liệu. Như vậy, hệ thống cĩ cơ sở để huỷ bỏ (undo) một thay đổi đã được làm trên cơ sở dữ liệu bằng cách sử dụng trường Old-value trong log record.Log phải được lưu trong những thiết bị lưu trữ bền. Mỗi một log record mới ngầm định sẽ được thêm vào cuối tập tin log. 5.3.1. Cập nhật trì hỗn cơ sở dữ liệu (Deferred Database Modification) Tư tưởng chính của ký thuật cập nhật trì hỗn là trì hỗn việc cập nhật thực sự vào csdl cho đến khi giao dịch đạt tới trạng thái commit. Một giao dịch khơng thể thay đổi csdl trên đĩa cho đến khi nĩ đạt tới trạng thái commit. Một giao dịch khơng thể đạt tới trạng thái commit cho đến khi tất cả các thao tác cập nhật của nĩ được ghi lại trên file log (WAL: write – ahead logging).
  44. 45 Các thao tác CSDL sẽ khơng được cập nhật cho đến khi giao dịch hồn tất nên khơng cần các thao tác UNDO. Cĩ thể phải REDO trong trường hợp hệ thống lỗi sau khi giao dịch đã hồn tất nhưng trước khi tất cả các thay đổi được ghi vào cơ sở dữ liệu.Giao dịch Ti cần được REDO nếu trong file log chứa cả hai bản ghi: và . Cũng vì vậy mà kỹ thuật phục hồi này cịn được gọi là NO – UNDO/ REDO recovery algorithm. Bảng sau chỉ ra các loại bản ghi được tạo ra trong file log: Thao tác của giao dịch Bản ghi trong file Log Giao dịch Ti bắt đầu Ti,Start Ti Write(X) Ti, X, New_Value Giao dịch Ti hồn tất Ti, Commit Ví dụ: Xét ba mục dữ liệu A, B, C với các giá trị ban đầu lần lượt là 1000, 2000, 700 và hai giao dịch T1, T2: T0: Read(A) Bản ghi trong file log A = A – 50 T0,Start Write(A) T0, A, 950 Read(B) T0, B, 2050 B = B + 50 T0, Commit Write(B) T1, Start T1, C, 600 T1: Read(C) T1, Commit C = C – 100 Write(C) Sau đây là một số tình huống xảy ra và hành động của hệ thống phục hồi sử dụng kỹ thuật cập nhật trì hỗn cơ sở dữ liệu: Giá trị các mục dữ liệu Tình huống Hệ thống phục hồi A B C Lỗi sau khi T0 vừa thực hiện thao tác Khơng làm gì. 1000 2000 700 write B. Lỗi sau khi T1 thực hiện Write(C). REDO(T0) 950 2050 700 5.3.2. Cập nhật tức thời (Immediate Database Modification) Kỹ thuật cập nhật tức thời cho phép các thao tác sửa đổi cơ sở dữ liệu cĩ quyền xuất dữ liệu tức thời ra đĩa trong khi giao dịch vẫn cịn ở trong trạng thái hoạt động (active state). Trong kỹ thuật này khi giao dịch thực hiện thao tác ghi, cơ sở dữ liệu sẽ được cập nhật tức thời mà khơng cần đợi đến khi giao dịch đạt tới trạng thái commit.Các thao tác cập nhật vẫn phải được ghi lại trong file log trước khi ghi lại trong csdl.
  45. 46 Bảng sau chỉ ra các loại bản ghi được tạo ra trong file log: Thao tác của giao dịch Bản ghi trong file Log Giao dịch Ti bắt đầu Ti, Start Ti Write(X) Ti, X, Old_Value, New_Value Giao dịch Ti hồn tất Ti,Commit 5.4.Kỹ thuật phân trang bĩng (Shadow Paging) Kỹ thuật “Phân trang bĩng” cũng là kỹ thuật cho phép phục hồi sau lỗi, nhưng ý tưởng thực hiện khác với các kỹ thuật dựa trên sổ ghi lộ trình vừa trình bày ở phần trên. Bảng trang và ý nghĩa của nĩ: Khái niệm trang đã nĩi được mượn từ lý thuyết về Hệ điều hành. Cách quản lý trang cũng được thừa kế từ đĩ. Giả sử rằng cơ sở dữ liệu được phân thành n trang và sự phân bố trên đĩa của chúng cĩ thể khơng theo một thứ tự cụ thể nào cả. Tuy nhiên, phải cĩ cách để tìm ra nhanh một trang.Người ta dùng bảng trang cho mục đích này.Bảng trang cĩ n đầu vào (entry).Mỗi đầu vào ứng với một trang. Một đầu vào chứa một con trỏ, trỏ đến một trang trên đĩa. Đầu vào đầu tiên chỉ đến trang đầu tiên của cơ sở dữ liệu, đầu vào thứ hai chỉ đến trang thứ hai Hình 5.6: Bảng trang Ý tưởng then chốt của kỹ thuật “Phân trang bĩng” là người ta sẽ duy trì hai bảng trang trong suốt chu kỳ sống của giao dịch, một bảng trang gọi là “bảng trang hiện hành” (current page table), bảng trang cịn lại gọi là “bảng trang bĩng” (shadow page table). Khi giao dịch khởi động, hai bảng trang này giống nhau.Bảng trang bĩng sẽ khơng thay đổi suốt quá trình hoạt động của giao dịch. Bảng trang hiện hành sẽ bị thay đổi mỗi khi giao dịch thực hiện tác vụ write. Tất cả các thao tác
  46. 47 input và output đều sử dụng bảng trang hiện hành để định vị các trang trong đĩa. Điểm quan trọng khác là nên lưu bảng trang bĩng vào thiết bị lưu trữ bền. Hình 5.7: Current Page và Shadow Page Giả sử giao dịch thực hiện tác vụ write(X) và hạng mục dữ liệu X được chứa trong trang thứ i. Tác vụ write được thực thi như sau: 1. Nếu trang thứ i chưa cĩ trong bộ nhớ chính, thực hiện input(X). 2. Nếu đây là lệnh ghi được thực hiện lần đầu tiên trên trang thứ i bởi giao dịch, sửa đổi bảng trang hiện hành như sau: a) Tìm một trang chưa được dùng trên đĩa. b) Xố trang vừa được tìm xong ở bước 2.a khỏi danh sách các khung trang tự do. c) Sửa lại bảng trang hiện hành sao cho đầu vào thứ i trỏ đến trang mới vừa tìm được trong bước 2.a. d) Gán giá trị xi cho X trong trang đệm (buffer page). Để bàn giao một giao dịch, cần làm các bước sau: B1. Đảm bảo rằng tất cả các trang đệm trong bộ nhớ chính đã được giao dịch sửa đổi phải được xuất ra đĩa. B2. Xuất bảng trang hiện hành ra đĩa (khơng được ghi đè lên trang bĩng). B3. Xuất địa chỉ đĩa của bảng trang hiện hành ra vị trí cố định trong thiết bị lưu trữ bền. Vị trí này chính là nơi chứa địa chỉ của bảng trang bĩng. Hành động này sẽ ghi đè lên địa chỉ của bảng trang bĩng cũ. Như vậy, bảng trang hiện hành sẽ trở thành bảng trang bĩng và giao dịch được bàn giao.
  47. 48 Nếu sự cố xảy ra trước khi hồn thành bước thứ 3, hệ thống sẽ trở về trạng thái trước khi giao dịch được thực hiện.Nếu sự cố xảy ra sau khi bước thứ 3 hồn thành, hiệu quả của giao dịch được bảo tồn; khơng cần thực hiện thao tác redo nào cả. Kỹ thuật phân trang bĩng cĩ một số điểm lợi hơn so với các kỹ thuật dựa vào file log: o Khơng mất thời gian ghi các log record. o Khơi phục sau sự cố nhanh hơn, do khơng cần các thao tác undo hoặc redo. Tuy nhiên kỹ thuật phân trang bĩng lại cĩ nhiều nhược điểm: o Tốn chi phí bàn giao, xuất nhiều khối ra đĩa: các khối dữ liệu hiện tại, bảng trang hiện hành, địa chỉ của bảng trang hiện hành. Trong khi kỹ thuật dựa vào file log chỉ cần xuất ra các log record. o Gây ra hiện tượng phân mảnh dữ liệu: Do kỹ thuật phân trang bĩng đổi vị trí của trang khi trang này bị sửa đổi. o Ngồi ra, kỹ thuật phân trang bĩng sẽ gặp nhiều khĩ khăn khi cần đáp ứng yêu cầu phục vụ song song cho nhiều giao dịch. Vì những lý do trên, kỹ thuật phân trang bĩng khơng được sử dụng rộng rãi.
  48. 49 5.5. Câu hỏi ơn tập chƣơng 5 5.5.1. Trình bày mơ hình khĩa nhị phân. 5.5.2. Trình bày các luật trong mơ hình khĩa nhị phân. 5.5.3. Trình bày mơ hình khĩa đọc – ghi. 5.5.4. Trình bày các luật trong mơ hình khĩa đọc – ghi. 5.5.5. Trình bày mơ hình khĩa 2 pha. 5.5.6. Trình bày về các biến thể của giao thức khĩa hai pha. 5.5.7. Trình bày hiện tượng Deadlock. 5.5.8. Trình bày các chiến lược ngăn cản và phát hiện Deadlock. 5.5.9. Trình bày về giao thức thứ tự nhãn thời gian. 5.5.10. Phân biệt hai kỹ thuật cập nhật trì hỗn và cập nhật tức thời. 5.5.11. Trình bày kỹ thuật Shadow Paging. 5.5.12. Cho hai giao dịch sau: T1: read(A); read(B); if A = 0 then B := B + 1 write(B). T2: read(B); read(A); if B = 0 then A := A + 1; write(A). Thêm các lệnh lock và unlock vào hai giao dịch trên để đảm bảo chúng tuân theo giao thức khĩa hai pha. Việc thực thi hai giao dịch trên cĩ thể sinh ra deadlock khơng?
  49. 50 MỘT SỐ ĐỀ THI MẪU
  50. 51 Trƣờng Đại Học Hàng Hải Việt Nam Khoa Cơng nghệ Thơng tin BỘ MƠN HỆ THỐNG THƠNG TIN THI KẾT THƯC HỌC PHẦN Tên học phần: CƠ SỞ DỮ LIỆU NÂNG CAO Đề thi số: Ký duyệt đề: Năm học: x Thời gian: 60 phút x Thang điểm: 100 PHẦN I – TRẮC NGHIỆM (30 ĐIỂM) Câu 1: (10 điểm) Cho các quan hệ: o Khoa (MKhoa, TenKhoa, DiaDiem) o Lop (MaLop, TenLop, SiSo, MaKhoa) và truy vấn Q: Hiển thị TenLop của các lớp cĩ SiSo > 50 và thuộc khoa „Kinh Tế‟. Hỏi biểu thức đại số quan hệ nào dưới đây đã tối ưu? A. B. C. D. Câu 2: (10 điểm) Cho đồ thị phụ thuộc của lịch biểu S. T1 T2 Lịch biểu nào dưới đây là lịch biểu tuần tự tương đương với S: A. T1 T2 T3 T4 B. T2 T1 T3 T4 T3 T4 C. T4 T2 T3 T1 D. T4 T3 T1 T2 Câu 3: (10 điểm) Lịch biểu nào dưới đây là khả tuần tự: A. R1(X), R2(Y), R1(Y), W1(X), R3(Y), W2(Y), W3(Y) B. R1(X), R2(Y), R1(Y), W1(X), R3(Z), W2(Y), W3(Z)
  51. 52 C. R1(X), R2(Z), R1(Y), W1(X), R3(Z), W2(Z), W3(Z) D. R1(Z), R2(Z), R1(Y), W1(Z), R3(Y), W2(Z), W3(Y) PHẦN II – TỰ LUẬN (70 ĐIỂM) Câu 4: (30 điểm) Cho các quan hệ sau: LoaiHang (MaLH, TenLH, MoTa) HangHoa (MaHH, TenHH, HinhThuc, SoLuong, MaLH) và truy vấn Q: Lập danh sách gồm MaHH, TenHH của các mặt hàng cĩ số lượng >100 và thuộc loại hàng „Mỹ phẩm‟. a. Viết biểu thức đại số quan hệ thực hiện truy vấn Q. b. Sử dụng phương pháp tối ưu Heuristic để tối ưu hĩa Q. Câu 5: (40 điểm) Cho các quan hệ tồn cục: Khoa (MaKhoa, TenKhoa, DiaDiem) Lop (MaLop, TenLop, SiSo, MaKhoa) Giả sử Khoa và Lop được phân đoạn ngang theo MaKhoa =1 và MaKhoa = 2 thành Khoa1, Khoa2, Lop1, Lop2. a. Viết biểu thức đại số quan hệ của các đoạn trên. b. Viết biểu thức xây dựng lại của 2 quan hệ tồn cục Khoa, Lop. c. Hãy viết truy vấn tồn cục QTC: Lập danh sách gồm TenLop, TenKhoa của các lớp cĩ MaKhoa = 2. d. Chuyển truy vấn QTC ở câu c thành truy vấn đoạn. HẾT Lưu ý: - Khơng sửa, xĩa đề thi, nộp lại đề sau khi thi
  52. 53 Trƣờng Đại Học Hàng Hải Việt Nam Khoa Cơng nghệ Thơng tin BỘ MƠN HỆ THỐNG THƠNG TIN THI KẾT THƯC HỌC PHẦN Tên học phần: CƠ SỞ DỮ LIỆU NÂNG CAO Đề thi số: Ký duyệt đề: Năm học: x Thời gian: 60 phút x Thang điểm: 100 PHẦN I – TRẮC NGHIỆM (30 ĐIỂM) Câu 1: (10 điểm) Cho các quan hệ: o Khoa (MKH, TenKH, DiaDiem, MaCNK) o Lop (MaLH, TenLH, SiSo, MaKH) và truy vấn Q: Hiển thị MaLH, TenLH, SiSo của các lớp thuộc khoa „CNT‟. Hỏi biểu thức đại số quan hệ nào dưới đây đã tối ưu? A. B. C. D. Câu 2: (10 điểm) Cho đồ thị phụ thuộc của lịch biểu S. T1 T2 Lịch biểu nào dưới đây là lịch biểu tuần tự tương đương với S? A. T4 T1 T2 T3 B. T4 T3 T2 T1 C. T3 T1 T4 T2 T3 T4 D. T4 T3 T1 T2 Câu 3: (10 điểm) Lịch biểu nào dưới đây là khả tuần tự? A. R1(X), R1(Y), R3(Z), R2(Y), W3(Z), W2(Y), W1(X)
  53. 54 B. R2(Y), R1(X), R1(Y), R3(X), W3(X), W2(Y), W1(X) C. R3(X), R2(Y), R1(X), R1(Y), W2(Y), W1(Y), W3(X) D. R1(X), R1(Y), R3(X), R2(Y), W2(Y), W1(Y), W3(X) PHẦN II – TỰ LUẬN (70 ĐIỂM) Câu 4: (30 điểm) Cho các quan hệ sau: HoaDon (MaHD, MaKH, NgayLap) ChiTiet (MaHD, MaHang, SoLuong, GiaBan, ChietKhau) và truy vấn Q: Lập danh sách gồm MaHang, SoLuong của các mặt hàng bán vào ngày „29/04/2011‟. a. Viết biểu thức đại số quan hệ thực hiện truy vấn Q. b. Sử dụng phương pháp tối ưu Heuristic để tối ưu hĩa Q. Câu 5: (40 điểm) Cho các quan hệ tồn cục: KhoHang (MaKH, TenKH, ViTri) LoaiHang (MaLH, TenLH, MoTa, MaKH) Giả sử KhoHang, LoaiHang được phân đoạn ngang theo MaKH =1 và MaKH = 2 thành KhoHang1, KhoHang2, LoaiHang1, LoaiHang2. a. Viết biểu thức đại số quan hệ của các đoạn trên. b. Viết biểu thức xây dựng lại của 2 quan hệ tồn cục DonVi, NhanVien. c. Hãy viết truy vấn tồn cục QTC: Lập danh sách gồm TenLH, ViTri của loại hàng cĩ MaLH=‟LH01‟ và ở kho hàng cĩ MaKH = 2. d. Chuyển truy vấn QTC ở câu c thành truy vấn đoạn. HẾT Lưu ý: - Khơng sửa, xĩa đề thi, nộp lại đề sau khi thi
  54. 55 Trƣờng Đại Học Hàng Hải Việt Nam Khoa Cơng nghệ Thơng tin BỘ MƠN HỆ THỐNG THƠNG TIN THI KẾT THƯC HỌC PHẦN Tên học phần: CƠ SỞ DỮ LIỆU NÂNG CAO Đề thi số: Ký duyệt đề: Năm học: x Thời gian: 60 phút x Thang điểm: 100 PHẦN I – TRẮC NGHIỆM (30 ĐIỂM) Câu 1: (10 điểm) Cho các quan hệ: o LoaiHang (MLH, TenLH, MoTa) o Hang (MaHH, TenHH, HinhThuc, SoLuong, MaLH) và truy vấn Q: Hiển thị TenHH của các mặt hàng cĩ SoLuong <10 và thuộc loại hàng „Điện Tử‟. Hỏi biểu thức đại số quan hệ nào dưới đây đã tối ưu? A. B. C. D. Câu 2: (10 điểm) Cho đồ thị phụ thuộc của lịch biểu S. T1 T2 Lịch biểu nào dưới đây là lịch biểu tuần tự tương đương với S: A. T3 T1 T2 T4 B. T3 T2 T1 T4 T3 T4 C. T4 T2 T3 T1 D. T4 T3 T1 T2 Câu 3: (10 điểm) Lịch biểu nào dưới đây là khả tuần tự: A. R1(X), R2(Y), R1(Y), W2(Y), R3(Y), W1(X), W3(Y)
  55. 56 B. R1(X), R2(Y), R1(Y), R3(Y), W1(X), W3(Y), W2(Y) C. R1(X), R2(Y), R1(Y), R3(Y), W3(Y), W2(Y), W1(X) D. R1(Y), R3(Y), R1(X), R2(Y), W3(Y), W2(Y), W1(X) PHẦN II – TỰ LUẬN (70 ĐIỂM) Câu 4: (30 điểm) Cho các quan hệ sau: Khoa (MKhoa, TenKhoa, DiaDiem) Lop (MaLop, TenLop, SiSo, MaKhoa) và truy vấn Q: Lập danh sách gồm MaLop, TenLop của các lớp cĩ sĩ số nhỏ hơn 30 và thuộc khoa „Điện tự động‟. a. Viết biểu thức đại số quan hệ thực hiện truy vấn Q. b. Sử dụng phương pháp tối ưu Heuristic để tối ưu hĩa Q. Câu 5: (40 điểm) Cho các quan hệ tồn cục: DonVi (MaDV, TenDV, DiaDiem) NhanVien (MaNV, HoTen, NgaySinh, GioiTinh, Luong, MaDV) Giả sử DonVi và NhanVien được phân đoạn ngang theo MaDV = 1 và MaDV = 2 thành DonVi1, DonVi2, NhanVien1, NhanVien2. a. Viết biểu thức đại số quan hệ của các đoạn trên. b. Viết biểu thức xây dựng lại của 2 quan hệ tồn cục DonVi, NhanVien. c. Hãy viết truy vấn tồn cục QTC: Lập danh sách gồm HoTen, TenDV của các nhân viên thuộc đơn vị cĩ MaDV = 1. d. Chuyển truy vấn QTC ở câu c thành truy vấn đoạn. HẾT Lưu ý: - Khơng sửa, xĩa đề thi, nộp lại đề sau khi thi
  56. 57 Trƣờng Đại Học Hàng Hải Việt Nam Khoa Cơng nghệ Thơng tin BỘ MƠN HỆ THỐNG THƠNG TIN THI KẾT THƯC HỌC PHẦN Tên học phần: CƠ SỞ DỮ LIỆU NÂNG CAO Đề thi số: Ký duyệt đề: Năm học: x Thời gian: 60 phút x Thang điểm: 100 PHẦN I – TRẮC NGHIỆM (30 ĐIỂM) Câu 1: (10 điểm) Cho các quan hệ: o SinhVien (MSV, TenSV, NgaySinh, DiaChi, MaLop) o KetQua (MaSV, MaMH, Diem) và truy vấn Q: Hiển thị MaMH, Diem của sinh viên „Trần Huyền‟. Hỏi biểu thức đại số quan hệ nào dưới đây đã tối ưu? A. B. C. D. Câu 2: (10 điểm) Cho đồ thị phụ thuộc của lịch biểu S. T1 T2 Lịch biểu nào dưới đây là lịch biểu tuần tự tương đương với S? A. T2 T4 T1 T3 B. T4 T3 T2 T1 C. T2 T1 T4 T3 T3 T4 D. T4 T3 T1 T2 Câu 3: (10 điểm) Lịch biểu nào dưới đây là khả tuần tự? A. R1(X), R1(Z), R3(Z), R2(Y), W3(Z), W2(Y), W1(Z)
  57. 58 B. R1(X), R2(Y), R1(Y), R3(X), W3(X), W1(X), W2(Y) C. R3(Z), R2(Y), R1(X), R1(Y), W1(X), W3(Z), W2(Y) D. R3(X), R1(X), R1(Y), R2(Y), W2(Y), W1(Y), W3(X) PHẦN II – TỰ LUẬN (70 ĐIỂM) Câu 4: (30 điểm) Cho các quan hệ sau: DonVi(MDV, TenDV, MaNQL, DiaDiem) DuAn (MaDA, TenDA, KinhPhi, MaDV) và truy vấn Q: Hiển thị TenDA của các dự án cĩ KinhPhi > 100000 và do đơn vị cĩ TenDV = „XD1‟ quản lý. a. Viết biểu thức đại số quan hệ thực hiện truy vấn Q. b. Sử dụng phương pháp tối ưu Heuristic để tối ưu hĩa Q. Câu 5: (40 điểm) Cho quan hệ NhanVien (MaNV, TenNV, DiaChi, Luong, PhuCap, MaNQL, MaPB) và thơng tin phân đoạn như sau: NhanVien được phân đoạn dọc thành: o NV1 chứa các thơng tin: MaNV, TenNV, DiaChi, MaNQL, MaPB o NV2 chứa các thơng tin: MaNV, Luong, PhuCap NV1 được phân đoạn ngang thành: o NV11: Những nhân viên cĩ MaPB < 5. o NV12: Những nhân viên cĩ MaPB 5. a. Viết biểu thức đại số quan hệ của các đoạn trên. Viết biểu thức xây dựng lại của 2 quan hệ tồn cục NhanVien. b. Hãy viết truy vấn tồn cục QTC: Lập danh sách gồm TenNV, Luong, PhuCap của các nhân viên cĩ MaPB = 8. Chuyển truy vấn QTC ở câu c thành truy vấn đoạn. HẾT Lưu ý: - Khơng sửa, xĩa đề thi, nộp lại đề sau khi thi
  58. 59 Trƣờng Đại Học Hàng Hải Việt Nam Khoa Cơng nghệ Thơng tin BỘ MƠN HỆ THỐNG THƠNG TIN THI KẾT THƯC HỌC PHẦN Tên học phần: CƠ SỞ DỮ LIỆU NÂNG CAO Đề thi số: Ký duyệt đề: Năm học: x Thời gian: 60 phút x Thang điểm: 100 PHẦN I – TRẮC NGHIỆM (30 ĐIỂM) Câu 1: (10 điểm) Cho các quan hệ: o DonVi (MDV, TenDV, DiaDiem) o NhanVien (MaNV, HoTen, NgaySinh, GioiTinh, Luong, MaDV) và truy vấn Q: Hiển thị HoTen của các nhân viên nữ thuộc đơn vị „PKD‟. Hỏi biểu thức đại số quan hệ nào dưới đây đã tối ưu? A. B. C. D. Câu 2: (10 điểm) Cho đồ thị phụ thuộc của lịch biểu S. Lịch biểu nào dưới đây là lịch biểu tuần T1 T2 tự tương đương với S: A. T3 T1 T2 T4 B. T3 T2 T1 T4 C. T3 T1 T4 T2 T3 T4 D. T4 T3 T1 T2 Câu 3: (10 điểm) Lịch biểu nào dưới đây là khả tuần tự: A. R2(X), R1(X), R1(Y), R3(Z), W3(Z), W2(X), W1(X) B. R1(Y), R2(X), R1(X), R3(Z), W3(Z), W2(X), W1(X)
  59. 60 C. R1(Z), R2(X), R1(Y), W2(X), R3(Z), W1(Y), W3(Z) D. R1(Y), R2(X), R1(X), R3(Z), W1(X), W3(Z), W2(X) PHẦN II – TỰ LUẬN (70 ĐIỂM) Câu 4: (30 điểm) Cho các quan hệ sau: DonHang (MaDH, MaNV, MaNhaCC, NgayLap, TongTien) ChiTiet (MaDH, MaHang, SoLuong, DonGia, ChietKhau) và truy vấn Q: Lập danh sách gồm MaHang, SoLuong của các mặt hàng cĩ DonGia > 90000 trong đơn hàng cĩ NgayLap = „29/04/2011‟. a. Viết biểu thức đại số quan hệ thực hiện truy vấn Q. b. Sử dụng phương pháp tối ưu Heuristic để tối ưu hĩa Q. Câu 5: (40 điểm) Cho các quan hệ tồn cục: DonVi(MaDV, TenDV, MaNQL) DuAn (MaDA, TenDA, KinhPhi, MaDV) Giả sử DonVi và DuAn được phân đoạn ngang theo MaDV = 1 và MaDV = 2 thành DonVi1, DonVi2, DuAn1, DuAn2. a. Viết biểu thức đại số quan hệ của các đoạn trên. b. Viết biểu thức xây dựng lại của 2 quan hệ tồn cục DonVi, DuAn. c. Hãy viết truy vấn tồn cục QTC: Lập danh sách gồm TenDA, TenDV của các dự án cĩ KinhPhi > 900000 và do đơn vị cĩ MaDV = 1 quản lý. d. Chuyển truy vấn QTC ở câu c thành truy vấn đoạn. HẾT Lưu ý: - Khơng sửa, xĩa đề thi, nộp lại đề sau khi thi