CHUONG 2

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ả.

2.3. Thuật toán tối ưu hóa cây đại số quan hệ 2.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ệ.

CHUONG  3

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.

3.2. Các tính chất của giao dịch

Để đảm bảo tính toàn vẹn của dữ liệu, hệ CSDL cầ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 CSDL 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 CSDL.

·        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 CSDL vẫn còn ngay cả khi xảy ra sự cố hệ thống.

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.

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ự.

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ự.

 CHUONG 4

4.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 đã hoà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.

4.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”.

·        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 đã hoà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.

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.

4.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.

•         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)

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.

4.2.2. Giao thức thứ tự nhãn thời gian (Timestamp – Ordering Protocol)

•         Giao dịch T muốn thực hiện write_item(X):

1.      Nếu Read_TS(X) > TS(T) hoặc 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 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)}.

CHUONG 5

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

< Ti start >

Giao dịch Ti đã khởi động.

< Ti, Xj, V1, V2 >

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.

< Ti commit >

Giao dịch Ti đã bàn giao.

< Ti abort >

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ì hoãn cơ sở dữ liệu (Deferred Database Modification):

Kỹ thuật cập nhật trì hoãn đảm bảo tính nguyên tử của giao dịch bằng cách ghi lại tất cả những sửa đổi cơ sở dữ liệu vào sổ ghi lộ trình (log), nhưng trì hoãn sự thực hiện tất cả các thao tác viết dữ liệu ra đĩa của giao dịch cho đến khi giao dịch bàn giao một phần (partially commits). Nhắc lại rằng: một giao dịch được gọi là bàn giao một phần khi hành động cuối cùng của nó được thực hiện xong. Kỹ thuật cập nhật trì hoãn được trình bày trong phần này giả thiết rằng các giao dịch được thực hiện một cách tuần tự.

Khi giao dịch bàn giao một phần, thông tin trên log kết hợp với giao dịch được sử dụng trong việc viết trì hoãn.

Sự thực thi của một giao dịch được tiến triển như sau:

·        Trước khi giao dịch Ti bắt đầu thực hiện, một mẫu tin < Ti start > được ghi ra sổ lộ trình.

·        Trước khi Ti thực hiện thao tác write(X), một mẫu tin < Ti, X, V2 > được ghi ra sổ lộ trình.

·        Cuối cùng, khi giao dịch Ti bàn giao một phần, mẫu tin < Ti commit > được ghi ra sổ lộ trình.

Khi giao dịch bàn giao một phần, các mẫu tin trong sổ lộ trình kết hợp với giao dịch sẽ được sử dụng để thực hiện việc ghi trì hoãn các hạng mục dữ liệu ra đĩa. Nhà thiết kế phải đảm bảo rằng, trước khi hoạt động ghi hạng mục dữ liệu diễn ra, các mẫu tin log đã được ghi thành công ra các thiết bị lưu trữ bền. Ngoài ra cũng cần để ý: kỹ thuật cập nhật trì hoãn chỉ cần ghi lại giá trị mới của hạng mục dữ liệu (V2) mà thôi.

Để minh hoạ, ta sử dụng ví dụ hệ thống ngân hàng đơn giản. Gọi T0 là giao dịch có nhiệm vụ chuyển $50 từ tài khoản A sang tài khoản B, T1 là giao dịch có nhiệm vụ rút $100 từ tài khoản C. Giả sử giá trị ban đầu của các tài khoản A, B, C là $1000, $2000 và $700. Hành động của T0 và T1 được mô tả như sau:

T0

T1

read(A); A:=A-50; write(A); read(B); B:=B+50; write(B)

read(C); C:=C-100; write(C)

Giả thiết các giao dịch được thực hiện tuần tự: T0 rồi tới T1. Một phần của sổ lộ trình ghi lại những thông tin liên quan đến hoạt động của hai giao dịch trên:

<T0 start> <T0 ,A, 950> <T0 ,B, 2050> <T0 commit> <T1 start> <T1 ,C, 600> <T1 commit>

Sau khi có sự cố xảy ra, hệ thống phục hồi sẽ tham khảo sổ lộ trình để chọn ra những giao dịch nào cần được Redo. Giao dịch Ti cần được làm lại khi và chỉ khi sổ nhật ký có chứa cả hai mẫu tin <Ti start> và <Ti commit>.

Thủ tục Redo(Ti) như sau:

Redo(Ti) đặt giá trị mới cho tất cả các hạng mục dữ liệu được cập nhật bởi giao dịch Ti. Các giá trị mới sẽ được tìm thấy trong sổ lộ trình (log).

Trở lại ví dụ vừa nêu, ta có bảng mô tả trạng thái của sổ ghi lộ trình và cơ sở dữ liệu như sau:

LOG

CƠ SỞ DỮ LIỆU

<T0 start> <T0 ,A, 950> < T0 ,B, 2050> <T0 commit> <T1 start>

<T1 ,C, 600> <T1 commit>

A=950; B=2050; C=600

Sau đây là một số tình huống mô phỏng:

·        Giả sử lỗi hệ thống xảy ra sau khi mẫu tin log cho hành động write(B) của giao dịch T0 vừa được ghi ra thiết bị lưu trữ bền. Khi hệ thống khởi động trở lại, sẽ không có hành động “thực hiện lại giao dịch” nào cần phải làm, do không có mẫu tin ghi commit nào xuất hiện trong sổ lộ trình. Nghĩa là giá trị của A,B và C vẫn giữ nguyên là $1000, $2000 và $700.

Giả sử lỗi hệ thống xảy ra sau khi mẫu tin log cho hành động write(C) của giao dịch T1 vừa được ghi ra thiết bị lưu trữ bền. Khi hệ thống hoạt động trở lại, thủ tục Redo(T0) sẽ được thực hiện do có sự xuất hiện của mẫu tin <T0 commit> trong sổ lộ trình. Sau khi thủ tục này được thực thi, giá trị của A và B sẽ là $950 và $2050.

5.3.2. Sửa đổi cơ sở dữ liệu 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). Hành động thay đổi nội dung dữ liệu tức thời của các giao dịch đang hoạt động được gọi là “những thay đổi chưa được bàn giao” (uncommitted modifications).

Sự thực thi của một giao dịch được tiến hành như sau:

·           Trước khi giao dịch Ti bắt đầu sự thực hiện, một mẫu tin <Ti start> được ghi ra sổ lộ trình.

·           Trước khi Ti thực hiện thao tác write(X), một mẫu tin <Ti, X, V1, V2> được ghi ra sổ lộ trình.

·           Cuối cùng, khi giao dịch Ti bàn giao một phần, mẫu tin <Ti commit> được ghi ra sổ lộ trình.

Cần phải đảm bảo rằng, trước khi hoạt động ghi hạng mục dữ liệu diễn ra, các mẫu tin log đã được ghi thành công ra các thiết bị lưu trữ bền. Ngoài ra, cũng cần chú ý là mẫu tin log cho hành động write(X) của giao dịch Ti, tức là mẫu tin <Ti, X, V1, V2> có chứa cả hai giá trị mới (V2) và cũ (V1) của hạng mục dữ liệu X.

Trở lại với ví dụ trong phần 5.3.1, ta có một phần của sổ lộ trình liên quan đến các hoạt động của T0 và T1 như sau:

<T0 start> <T0 , A, 1000, 950> <T0 , B, 2000, 2050> <T0 commit> <T1 start> <T1 , C, 700, 600> <T1 commit>

Bảng mô tả trạng thái của sổ ghi lộ trình và cơ sở dữ liệu như sau:

LOG

CƠ SỞ DỮ LIỆU

<T0 start> <T0 , A, 1000, 950> < T0 , B, 2000, 2050> <T0 commit> <T1 start> <T1 , C, 700, 600> <T1 commit>

A=950; B=2050; C=600

Kỹ thuật cập nhật tức thời sử dụng hai thủ tục khôi phục sau lỗi:

·           undo(Ti) đặt lại giá trị cũ cho tất cả các hạng mục dữ liệu được cập nhật bởi giao dịch Ti. Các giá trị cũ sẽ được tìm thấy trong sổ lộ trình (log).

·           redo(Ti) đặt giá trị mới cho tất cả các hạng mục dữ liệu được cập nhật bởi giao dịch Ti. Các giá trị mới sẽ được tìm thấy trong sổ lộ trình (log).

Sau khi lỗi xuất hiện, hệ thống phục hồi tham khảo sổ ghi để quyết định những giao dịch nào cần được làm lại (redo) và những giao dịch nào cần được huỷ bỏ (undo).

·           Giao dịch Ti cần được huỷ bỏ khi sổ ghi chứa mẫu tin <Ti start> nhưng không có mẫu tin <Ti commit>.

·           Giao dịch Ti cần được làm lại khi sổ ghi có chứa cả mẫu tin <Ti start> lẫn mẫu tin <Ti commit>.

Sau đây là một số tình huống mô phỏng:

ü        Giả sử lỗi hệ thống xảy ra sau khi mẫu tin log cho hành động write(B) của giao dịch T0 vừa được ghi ra thiết bị lưu trữ bền. Khi hệ thống khởi động trở lại, nó sẽ tìm thấy mẫu tin <T0 ­start> trong sổ ghi, nhưng không có mẫu tin <T0 ­commit> tương ứng. Do đó giao dịch T0 cần phải được huỷ bỏ. Nghĩa là thủ tục undo(T0) sẽ được gọi và giá trị của A,B và C vẫn giữ nguyên là $1000, $2000 và $700.

ü        Giả sử lỗi hệ thống xảy ra sau khi mẫu tin log cho hành động write(C) của giao dịch T1 vừa được ghi ra thiết bị lưu trữ bền. Khi hệ thống hoạt động trở lại, hai thủ tục redo(T0) và undo(T1) sẽ được thực hiện. Do có sự xuất hiện của các mẫu tin <T0 start>, <T0 commit>, <T1 start> trong sổ lộ trình. Sau khi hai thủ tục này được thực thi, giá trị của A, B, C sẽ là $950,ì $2050 và $700.

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.

Tóm lược các khái niệm cơ bản:

·        Trang (page):cơ sở dữ liệu được lưu vào thiết bị lưu trữ không phai thành nhiều khối có kích thước cố định. Người ta gọi những khối này là trang (page).

·        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 ...

Ý 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 tác vụ 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.1: Bảng trang

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)      Xoá 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:

1.        Đả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.

2.        Xuất bảng trang hiện hành ra đĩa (không được viết đè lên trang bóng).

3.        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.

Nếu sự cố xảy ra trước khi hoà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 hoà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ả. Ví dụ trong hình 5.2 dưới đây mô phỏng lại trạng thái của các bảng trang hiện hành và bảng trang bóng khi giao dịch thực hiện thao tác ghi lên trang thứ tư của cơ sở dữ liệu có 10 trang.

Hình 5.2: Current Page và Shadow Page sau khi thực thiện thao tác ghi.

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 trên sổ ghi:

·        Không mất thời gian ghi ra các log record.

·        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:

·        Tổng 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 kỹ thuật dựa vào sổ ghi, chỉ cần xuất ra các log record, mà thông thường, các log record này vừa đủ chứa trong một khối.

·        Sự phân mảnh dữ liệu: Kỹ thuật phân trang bóng lại đổi vị trí của trang khi trang này bị sửa đổi. Điều này dẫn đến tính gom cụm dữ liệu không còn, hoặc phải dùng các giải pháp gom cụm lại rất mất thời gian.

·        Phải thu nhặt rác. Mỗi khi giao dịch bàn giao, các trang chứa giá trị dữ liệu cũ đã bị sửa đổi bởi giao dịch sẽ trở thành không truy xuất được. Vì chúng không thuộc danh sách các trang tự do nhưng cũng không chứa dữ liệu hữu dụng. Ta gọi chúng là “rác”. Cần thiết phải định kỳ tìm kiếm và thêm các trang rác vào trong danh sách các trang tự do. Hành động này được gọi là “thu nhặt rác”.

·        Ngoài ra, kỹ thuật phân trang bóng sẽ gặp nhiều khó khăn hơn kỹ thuật dựa vào sổ ghi khi cần được tinh chỉnh để đáp ứng cho 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 lắm.

CHUONG 6

6.2. Kiến trúc hệ quản trị CSDL phân tán

Trước tiên việc phân tán dữ liệu được thực hiện trên cơ sở cấp phát các tập tin cho các nút trên một mạng máy tính. Các nút mạng thường nằm ở các vị trí địa lý khác nhau trải rộng trên một diện tích lớn. Do vậy để tối ưu việc khai thác thông tin thì dữ liệu không thể để tập trung mà phải phân tán trên các nút của mạng.

Hơn nữa một quan hệ không phải là một đơn vị truy xuất dữ liệu tốt nhất. Ví dụ như, nếu ứng dụng được thực hiện trên một bộ phận nhỏ các dữ liệu của quan hệ mà quan hệ đó nằm tại các vị trí khác nhau thì có thể gây ra những truy xuất thừa và hơn thế việc nhân bản các quan hệ làm tốn không gian bộ nhớ. Do vậy phân rã một quan hệ thành nhiều mảnh, mỗi mảnh được xử lý như một đơn vị sẽ cho phép thực hiện nhiều giao dịch đồng thời. Một câu truy vấn ban đầu có thể được chia ra thành một tập các truy vấn con, các truy vấn này có thể được thực hiện song song trên các mảnh sẽ giúp cải thiện tốc độ hoạt động của hệ thống.

Tuy nhiên chúng ta cũng sẽ gặp những rắc rối của việc phân mảnh, ví dụ nếu các ứng dụng có những xung đột sẽ ngăn cản hoặc gây khó khăn cho việc truy xuất dữ liệu. Phân rã các mảnh nói chung làm tăng chi phí trong việc truy xuất dữ liệu. Một vấn đề nữa liên quan đến việc kiểm soát ngữ nghĩa và tính toàn vẹn dữ liệu

6.3.1. Phân mảnh ngang

Phân đoạn ngang của 1 qh R la 1 nhóm các bộ trong R thỏa mãn 1 số tính chất nào đó

Ri= Sci(R), ci la điều kiện phân đoạn ngang