Các thuật toán quản lý khóa chốt trong cơ sở dữ liệu phân tán

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

ĐỖ THỊ LỢI

CÁC THUẬT TOÁN QUẢN LÝ KHÓA CHỐT

TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Nguyên, 2018

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

ĐỖ THỊ LỢI

CÁC THUẬT TOÁN QUẢN LÝ KHÓA CHỐT

TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN

Chuyên ngành: Khoa học máy tính

Mã số: 84 80 101

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Người hướng dẫn khoa học: PGS TSKH Nguyễn Xuân Huy

Thái Nguyên, 2018

v

LỜI CAM ĐOAN

Tôi xin cam đoan kết quả tìm hiểu, nghiên cứu trong luận văn là của cá nhân

tôi. Các số liệu, kết quả nêu trong luận văn này là trung thực và chưa được công

bố trong bất kỳ công trình nào khác. Các trích dẫn số liệu và kết quả tham khảo

đều có xuất xứ rõ ràng và được trích dẫn hợp pháp.

Thái Nguyên, tháng 6 năm 2018

Tác giả luận văn

Đỗ Thị Lợi

vi

MỤC LỤC

LỜI CAM ĐOAN ................................................................................................. v

MỤC LỤC............................................................................................................vi

DANH MỤC CÁC HÌNH VẼ.............................................................................ix

LỜI CẢM ƠN....................................................................................................... x

MỞ ĐẦU ............................................................................................................... 1

1. Đặt vấn đề ...............................................................................................................1

2. Những đóng góp của luận văn...............................................................................2

3. Bố cục của luận văn................................................................................................2

CHƯƠNG I: TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN VÀ GIAO

TÁC........................................................................................................................ 4

1.1. Khái niệm về cơ sở dữ liệu phân tán:................................................................4

1.1.1 Đặc điểm của CSDL phân tán.......................................................................5

1.1.2. Đánh giá ưu, nhược điểm của CSDL phân tán: .........................................7

1.1.3 Các ràng buộc toàn vẹn trong cơ sở dữ liệu phân tán:...............................8

1.1.4. Loại hình phân tán trong luận văn .............................................................8

1.2. Bài toán truy nhập đồng thời giải quyết tranh chấp .......................................9

1.3. Phát biểu bài toán tổng hợp .............................................................................10

1.4. Giao tác (Transaction)......................................................................................11

1.4.1. Khái niệm.....................................................................................................11

1.4.3. Các thao tác của giao tác ............................................................................15

1.4.4. Các trạng thái của giao tác.........................................................................17

1.5. Lịch .....................................................................................................................17

1.5.1. Định nghĩa lịch: ..........................................................................................17

1.5.2. Lịch tuần tự (Serial schedule):...................................................................19

vii

1.5.3. Lịch khả tuần tự (serializable schedule):...................................................20

1.6. Khóa chốt ...............................................................................................................22

1.6.1. Khái niệm.........................................................................................................22

1.6.2. Khóa sống (Livelock) ......................................................................................26

1.6.3. Khóa gài (Deadlock)........................................................................................26

1.6.4. Nghi thức 2 pha...............................................................................................27

1.6.5. Mô hình khóa cơ bản ......................................................................................29

1.6.5.1. Mô hình đọc ghi đơn giản........................................................................30

1.6.5.2. Mô hình đọc và đọc & ghi.......................................................................31

CHƯƠNG II: CÁC THUẬT TOÁN QUẢN LÝ KHÓA................................ 33

TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN.......................................................... 33

2.1. Kiểm tra tính hợp lệ của giao tác.....................................................................33

2.2. Kiểm tra tính hợp lệ của lịch............................................................................38

2.3. Kiểm tra nghi thức 2 pha của giao tác ............................................................41

2.4. Kiểm tra tính khả tuần tự của lịch ..................................................................43

2.5. Lập lịch...............................................................................................................48

CHƯƠNG III: CÀI ĐẶT CHƯƠNG TRÌNH VÀ THỬ NGHIỆM.............. 52

3.1. Tổ chức dữ liệu ..................................................................................................52

3.2. Kịch bản chương trình......................................................................................54

3.3. Thử nghiệm chương trình ................................................................................56

3.3.1. Môi trường cài đặt.......................................................................................56

3.3.2. Mô hình hệ thống........................................................................................56

TÀI LIỆU THAM KHẢO ................................................................................. 68

viii

DANH MỤC CÁC KÍ HIỆU VÀ CHỮ VIẾT TẮT

1 CSDLPT Distributed database- Cở sở dữ liệu phân tán

2 CSDL Database- Cơ sở dữ liệu

3 PT Distributed- Phân tán

4 CNTT Information Technology- Công nghệ thông tin

5 MMT Internet- Mạng máy tính

6 // Chú thích

7 ++ Tăng biến đếm lên 1 đơn vị

8 -- Giảm biến đếm xuống 1 đơn vị

9 && Và hoặc Ender

10  Gán

11 [][] Ma trận

12 == Dấu bằng

ix

DANH MỤC CÁC HÌNH VẼ

Hình 3.1: Cấu trúc một file input của một giao tác cho kịch bản .................................53

Hình 3.2: Cấu trúc một file input của một lịch cho kịch bản........................................54

Hình 3.3: Giao diện chính của chương trình ................................................................57

Hình 3.4: Giao diện lập lịch từ các giao tác LOCK/ UNLOCK ...................................58

Hình 3.5: Giao diện xong lập lịch.................................................................................59

Hình 3.6: Giao diện phân tích lịch LOCK/ UNLOCK .................................................60

Hình 3.7: Giao diện xong phân tích lịch .......................................................................61

Hình 3.8: Giao diện phân tích lịch RLOCK & WLOCK/ UNLOCK.............................62

Hình 3.9: Giao diện xong phân tích lịch .......................................................................63

Hình 3.10: Giao diện lập lịch RLOCK & WLOK/ UNLOCK........................................64

Hình 3.11: Giao diện xong lập lịch ...............................................................................65