Thạc Sĩ Xử lý dữ liệu và bài toán cấp phát

V


Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

MỞ ĐẦU
Ngày nay, công nghệ thông tin (CNTT) đã trở thành một nhân tố không thể thiếu
trong mọi lĩnh vực của đời sống xã hội. Sự bùng nổ nhu cầu xây dựng các hệ thống
thông tin, mà trước hết là các hệ thống thông tin quản lý đã thu hút sự quan tâm của
nhiều nhà khoa học. Các hệ thống cơ sở dữ liệu (CSDL) đã lần lượt xuất hiện. Các
hệ thống CSDL truyền thống được tập trung quản lý tại một trạm đơn lẻ, việc tính
toán, xử lý và lưu trữ các tập dữ liệu trở lên đơn giản và dễ dàng.
Khi nhu cầu thu thập, lưu trữ, xử lý và trao đổi thông tin ngày càng tăng, các hệ
thống xử lý tập trung đã bộc lộ nhiều nhược điểm như: Khó khăn trong việc tăng
khả năng lưu trữ thông tin, độ sẵn sàng phục vụ của CSDL không cao khi số người
sử dụng tăng, khả năng tính toán của các máy tính đơn lẻ đang dần tới giới hạn vật
lý, mô hình tổ chức lưu trữ và xử lý dữ liệu không phù hợp cho các tổ chức có hoạt
động rộng lớn, đa quốc gia. Những nhược điểm này đã được khắc phục khá nhiều
trong hệ thống phân tán. Những sản phẩm của hệ thống phân tán đã xuất hiện nhiều
trên thị trường và từng bước chứng minh tính ưu việt của nó hơn hẳn các hệ thống
tập trung truyền thống.
Với nhu cầu phát triển mạnh mẽ của công tác quản lý các hệ phân tán và cơ sở dữ
liệu phân tán để giải quyết các bài toán ”quản lý” phức tạp đang tồn tại trong các
ngành kinh tế, xã hội và an ninh quốc phòng, Nhằm hỗ trợ cho vấn đề nêu trên thì
việc tính toán, lập trình cấp phát và xử lý dữ liệu cũng phát triển theo. Đặc biệt, việc
phân mảnh các quan hệ trong CSDL và chuyển chúng đến các nút trên mạng cũng
như việc cập nhật thông tin (truy cập và truy xuất, .) đến các mảnh ở các vị trí phân
tán đã trở thành một chủ đề mới mẻ và được nhiều ngành khoa học, các bộ môn
chuyên ngành nghiên cứu, ứng dụng. Chính vì vậy, tôi đã lựa chọn đề tài:
“Xử lý dữ liệu và bài toán cấp phát” để nghiên cứu thực hiện.
Luận văn được trình bày trong 3 chương, có phần mở đầu, phần kết luận, phần
mục lục, phần tài liệu tham khảo. Các nội dung cơ bản của luận văn được trình bày
theo cấu trúc như sau: VI


Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

CHƯƠNG 1: TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN VÀ BÀI
TOÁN CẤP PHÁT.
1.1. Tổng quan về CSDL phân tán.
1.2. Bài toán cấp phát.
1.3. Kết luận chương.
CHƯƠNG 2: XỬ LÝ DỮ LIỆU VÀ BÀI TOÁN CẤP PHÁT.
2.1. Thuật toán phân mảnh cơ sở dữ liệu.
2.1.1. Phân mảnh ngang.
2.1.2. Phân mảnh dọc.
2.1.3. Phân mảnh hỗn hợp.
2.2. Tính toán hàm mục tiêu và ràng buộc tại node mạng.
2.2.1. Hàm mục tiêu.
2.2.2. Ràng buộc.
2.3. Bài toán cấp phát dạng QHTT.
2.4. Kết luận chương.
CHƯƠNG 3: CÀI ĐẶT VÀ ỨNG DỤNG TẠI CÔNG TY ĐẦU TƯ VÀ
THƯƠNG MẠI AN LỘC.
3.1. Khảo sát cơ sở dữ liệu của công ty đầu tư và thương mại An Lộc và đưa
ra yêu cầu của bài toán.
3.2. Xây dựng cơ sở dữ liệu phân tán.
3.3. Cài đặt và chạy chương trình cấp phát.
3.4. Kết luận chương.
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN CỦA ĐỀ TÀI. VII


Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/


DANH MỤC HÌNH ẢNH
Hình 1.1: Hệ đa bộ xử lý có bộ nhớ chung 3
Hình 1.2: Hệ đa bộ xử lý có shared disk 3
Hình 1.3: Hệ đa bộ xử lý sở hữu cá nhân 3
Hình 1.4: CSDL được phân tán trên mạng 4
Hình 1.5: Phân mảnh hỗn hợp và tái thiết phân mảnh hỗn hợp . 11
Hình 2.1: Phân mảnh hỗn hợp 37
Hình 2.2: Truyền dữ liệu cho câu vấn tin . 40
Hình 3.1: Giao diện ban đầu của bài toán 55
Hình 3.2: Giao diện sau khi tiến hành chọn số lượng máy trạm . 56
Hình 3.3: Giao diện của quá trình chọn số lượng mảnh cơ sở dữ liệu . 57
Hình 3.4: Giao diện của quá trình chọn các mảnh cơ sở dữ liệu . 58
Hình 3.5: Giao diện sau quá trình lựa chọn các mảnh cơ sở dữ liệu . 59
Hình 3.6: Giao diện lựa chọn các tham số từ file .txt có sẵn . 60
Hình 3.7: Giao diện sau quá trình nhập các tham số . 61
Hình 3.8: Bảng kết quả của quá trình cấp phát 62
VIII


Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/


DANH MỤC BẢNG BIỂU
Bảng 2.1: Quan hệ DuAn 25
Bảng 2.2: Quan hệ TraLuong . 26
Bảng 2.3: Mảnh dữ liệu (quan hệ) TraLuong 1 26
Bảng 2.4: Mảnh dữ liệu (quan hệ) TraLuong 2 27
Bảng 2.5: Phân hoạch ngang cho quan hệ DuAn: DuAn H1 , DuAn H3 , DuAn H4 ,
DuAn H6 29
Bảng 3.1: Một số bản ghi của quan hệ Giao_Dich tiến hành phân mảnh ngang 51
Bảng 3.2: Bảng dữ liệu (quan hệ) của mảnh F 1 . 52
Bảng 3.3: Bảng dữ liệu (quan hệ) của mảnh F 2 53
Bảng 3.4: Bảng dữ liệu (quan hệ) của mảnh F 3 . 53
Bảng 3.5: Bảng dữ liệu (quan hệ) của mảnh F 4 . 53
Bảng 3.6: Bảng dữ liệu (quan hệ) của mảnh F 5 . 53
Bảng 3.7: Bảng dữ liệu (quan hệ) của mảnh F 6 . 53 IX


Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/


DANH MỤC CÁC THUẬT NGỮ VIẾT TẮT
Thuật ngữ Tên viết tắt
Cơ sở dữ liệu phân tán CSDLPT
Cơ sở dữ liệu CSDL
Dữ liệu DL
Quy hoạch tuyến tính QHTT


X


Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

MỤC LỤC

LỜI CAM ĐOAN I
LỜI CẢM ƠN . II
MỞ ĐẦU III
DANH MỤC HÌNH ẢNH . V
DANH MỤC BẢNG BIỂU . VI
DANH MỤC CÁC THUẬT NGỮ VIẾT TẮT .VII
MỤC LỤC . VIII
CHƯƠNG 1: TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU VÀ BÀI TOÁN CẤP PHÁT . 1
1.1. Tổng quan về CSDL phân tán 1
1.1.1. Xử lý phân tán 1
1.1.2. Hệ cơ sở dữ liệu phân tán và hệ quản trị cơ sở dữ liệu phân tán . 4
1.1.3. Một số yêu cầu của hệ cơ sở dữ liệu phân tán . 5
1.1.4. Các đặc điểm của hệ CSDL phân tán . 13
1.1.5. Kiến trúc hệ quản trị cơ sở dữ liệu phân 14
1.2. Bài toán cấp phát . 16
1.2.1. Giới thiệu về bài toán cấp phát 16
1.2.2. Mô tả bài toán cấp phát 20
1.2.3. Hàm mục tiêu (hàm chi phí) 20
1.2.4. Các ràng buộc . 21
1.3. Kết luận chương 22
CHƯƠNG 2: XỬ LÝ DỮ LIỆU VÀ BÀI TOÁN CẤP PHÁT . 22
2.1. Thuật toán phân mảnh cơ sở dữ liệu . 22
2.1.1. Thuật toán phân mảnh ngang nguyên thủy 22 XI


Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

2.1.2. Phân mảnh dọc . 30
2.1.3. Phân mảnh hỗn hợp 38
2.2. Tính toán hàm mục tiêu và ràng buộc tại node mạng . 39
2.2.1. Hàm mục tiêu . 39
2.2.2. Ràng buộc 44
2.3. Bài toán cấp phát dạng QHTT 45
2.4. Kết luận chương 49
CHƯƠNG 3: CÀI ĐẶT VÀ ỨNG DỤNG TẠI CÔNG TY ĐẦU TƯ VÀ THƯƠNG
MẠI AN LỘC 50
3.1. Khảo sát cơ sở dữ liệu của công ty đầu tư và thương mại An Lộc và
đưa ra yêu cầu của bài toán . 50
3.1.1. Mô tả hệ thống . 50
3.1.2. Yêu cầu của bài toán 51
3.2. Xây dựng cơ sở dữ liệu phân tán 52
3.3. Cài đặt và chạy chương trình cấp phát 58
3.4. Kết luận chương 66
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 67
TÀI LIỆU THAM KHẢO . 68
1


Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

CHƯƠNG 1: TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU VÀ BÀI
TOÁN CẤP PHÁT
1.1. Tổng quan về CSDL phân tán
Nguyên lý cơ bản của các hệ cơ sở dữ liệu phân tán (CSDLPT) được xây dựng
dựa trên sự hợp nhất của hai hướng tiếp cận lý thuyết các hệ cơ sở dữ liệu (CSDL)
và công nghệ mạng máy tính.
Động lực thúc đẩy sự phát triển mạnh mẽ của CSDLPT, nhu cầu tích hợp đa
dạng các loại dữ liệu (DL) nhằm cung cấp nhiều loại hình dịch vụ cho người sử
dụng. Thêm vào đó, với mục tiêu chia sẻ tài nguyên, khai thác, nâng cao khả năng
tích hợp và trao đổi tài nguyên mạng cũng thúc đẩy quá trình sử dụng các hệ thống
phân tán.
Nhu cầu thu thập, lưu trữ, xử lý và trao đổi thông tin ngày càng tăng, các hệ
thống xử lý tập trung đã bộc lộ những nhược điểm sau: [14][13]
- Tăng khả năng lưu trữ thông tin là khó khăn, bởi bị giới hạn tối đa của
thiết bị nhớ.
- Độ sẵn sàng phục vụ của CSDL không cao khi số người sử dụng tăng.
- Khả năng tính toán của các máy tính đơn lẻ đang dần tới giới hạn vật lý.
- Mô hình tổ chức lưu trữ, xử lý dữ liệu tập trung không phù hợp cho
những tổ chức kinh tế, xã hội có hoạt động rộng lớn, đa quốc gia.
1.1.1. Xử lý phân tán
Hệ xử lý phân tán hay còn gọi là hệ thống tính toán phân tán đó là một hệ thống
bao gồm một số đơn vị xử lý tự vận hành được liên kết thành mạng và hợp đồng
thực hiện các nhiệm vụ mà chúng được phân công. Các đơn vị xử lý có thể thực
hiện được các chương trình tiền định trên đó.
Những đối tượng được phân tán:
- Các thiết bị xử lý, các chức năng xử lý: Các chức năng của hệ thống có
thể được chuyển giao cho các thành phần hệ thống. 2


Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

- Dữ liệu: Dữ liệu được dùng bởi một số ứng dụng có thể được phân tán
tới một số vị trí xử lý.
- Quyền điều khiển: Quyền điều khiển một số nhiệm vụ cũng được phân
tán.
Phân loại các hệ thống phân tán:
Chúng ta có thể phân loại các hệ thống phân tán theo các tiêu chí sau đây
- Mức độ kết nối;
- Sự liên đới giữa các thành phần;
- Cấu trúc tương giao;
- Sự đồng bộ giữa các thành phần.
Tại sao phải phân tán:
- Nhằm thích ứng tốt hơn với việc phân bố rộng rãi của các công ty, xí
nghiệp.
- Nhiều ứng dụng công nghệ hiện đại cần được phân tán.
Lý do của việc xử lý phân tán:
Để thực hiện tốt hơn các bài toán lớn và phức tạp mà chúng gặp phải hiện nay
bằng cách sử dụng quy tắc ”Chia để trị”.
Các ưu điểm cơ bản của xử lý phân tán:
- Tận dụng được sức mạnh tính toán xử lý song song bằng cách sử dụng
nhiều bộ xử lý đồng thời.
- Giải quyết bài toán theo từng nhóm hoạt động độc lập nên có thể kiểm
soát được chi phí phát triển phần mềm.
- Các hệ cơ sở dữ liệu phấn tán cũng có thể được xem xét để phân tán
nhằm mục đích xử lý hiệu quả hơn.
Một số hệ thống xử lý hay được dùng: