Giáo trình Cơ sở dữ liệu nâng cao

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 toà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 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 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 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 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 toán của biểu thức đại số quan hệ sao cho các phép toán một ngôi được thực hiện trước các phép toán hai ngôi, do các phép toá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 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 hoá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 hoán của phép kết nối : o Tính chất giao hoá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  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 hoá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 toán tối ƣu hóa cây đại số quan hệ 3.3.1. Thuật toá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 toá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 toán một ngôi xuống dưới các phép toá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 toá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. 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ỏ hoàn toà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 toà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 toà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 hoà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 đã hoà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ể 34 ngăn cản sự hoàn tất của giao dịch. Nếu không có sự cố, tất cả các giao dịch đều hoà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 hoà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 hoà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 toà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. 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 toá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 toán: o Xây dựng đồ thị phụ thuộc G:  Nút: là các giao dịch. 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ự. 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 toá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 T2  T1  T3  T4 T4  T2  T3  T1 T4  T3  T1  T2 T1 T2 T3 T4 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);