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

I

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

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

TRƢỜNG ĐẠI HỌC CNTT VÀ TRUYỀN THÔNG

LẠI DƢƠNG QUANG

XƢ LÝ DỮ LIỆU VÀ BÀI TOÁN CẤP PHÁT

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

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

II

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

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

TRƢỜNG ĐẠI HỌC CNTT VÀ TRUYỀN THÔNG

LẠI DƢƠNG QUANG

XƢ LÝ DỮ LIỆU VÀ BÀI TOÁN CẤP PHÁT

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

Mã số: 60 48 01 01

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

GV hƣớng dẫn: PGS. NCVC. TS Lê Huy Thập

Thái Nguyên, 2015

III

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

LỜI CAM ĐOAN

Tôi cam đoan đây là công trình nghiên cứu do chính tôi thực hiện.

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

bố trong bất kỳ công trình nào khác.

Thái Nguyên, Ngày 10 tháng 4 năm 2015

Tác giả

Lại Dƣơng Quang

IV

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

LỜI CẢM ƠN

Trƣớc hết em xin trân trọng gửi lời cảm ơn đến toàn thể các thầy cô giáo Trƣờng

Đại học Công nghệ thông tin và Truyền thông Thái Nguyên đã dạy dỗ chúng em

trong suốt quá trình học tập chƣơng trình cao học tại trƣờng.

Đặc biệt em xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo PGS. NCVC. TS Lê

Huy Thập đã quan tâm, định hƣớng và đƣa ra những lời góp ý, chỉnh sửa quí báu

cho em trong quá trình làm luận văn tốt nghiệp

Thái Nguyên, Ngày 10 tháng 4 năm 2015

Học viên

Lại Dƣơng Quang

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