Báo cáo Đề tài Nghiên cứu một số vấn đề về truy vấn và tối ưu hóa truy vấn cơ sở dữ liệu phân tán trong hệ thống thông tin
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC THƯƠNG MẠI
ĐỀ TÀI NGHIÊN CỨU KHOA HỌC CẤP TRƯỜNG
NGHIÊN CỨU MỘT SỐ VẤN ĐỀ VỀ TRUY VẤN
VÀ TỐI ƯU HÓA TRUY VẤN CƠ SỞ DỮ LIỆU
PHÂN TÁN TRONG HỆ THỐNG THÔNG TIN
MÃ SỐ: CS-16-05
Chủ nhiệm đề tài: ThS. Cù Nguyên Giáp
Bộ môn: Tin Học
Hà Nội, năm 2017
1
MỤC LỤC
DANH MỤC HÌNH VẼ ..................................................................................................4
DANH MỤC TỪ VIẾT TẮT..........................................................................................5
1. Tính cấp thiết nghiên cứu của đề tài......................................................................6
2. Tổng quan về đề tài nghiên cứu ............................................................................6
3. Mục tiêu nghiên cứu..............................................................................................8
4. Đối tượng và phạm vi nghiên cứu.........................................................................9
5. Phương pháp nghiên cứu.......................................................................................9
6. Kết cấu báo cáo nghiên cứu ..................................................................................9
1. Khái niệm về hệ cơ sở dữ liệu phân tán ..............................................................11
1.1. Cơ sở dữ liệu phân tán .................................................................................11
1.2. Hệ quản trị cơ sở dữ liệu phân tán...............................................................12
2. Các đặc trưng của cơ sở dữ liệu phân tán............................................................13
2.1. Điều khiển tập trung.....................................................................................13
2.2. Độc lập dữ liệu .............................................................................................14
2.3. Giảm dư thừa dữ liệu....................................................................................14
2.4. Độ tin cậy qua các giao dịch phân tán.........................................................14
2.5. Cải tiến hiệu năng.........................................................................................14
2.6. Dễ dàng mở rộng hệ thống...........................................................................15
3. Kiến trúc cơ bản của cơ sở dữ liệu phân tán .......................................................15
3.1. Sơ đồ tổng thể ...............................................................................................15
3.2. Sơ đồ phân đoạn ...........................................................................................16
3.3. Sơ đồ định vị .................................................................................................16
3.4. Sơ đồ ánh xạ địa phương..............................................................................18
4. Các mô hình xử lý phân tán.................................................................................18
4.1. Mô hình xử lý Master - Slave........................................................................18
4.2. Các hệ phân tán ngang hàng........................................................................19
4.3. Môi trường đa tầng.......................................................................................20
DỮ LIỆU PHÂN TÁN..................................................................................................22
2. Giới thiệu về xử lý truy vấn ................................................................................22
3. Các giai đoạn trong xử lý truy vấn CSDLPT......................................................24
4.1. Ngôn ngữ (language)....................................................................................27
4.3. Thời gian tối ưu hóa (optimization timing) ..................................................27
2
4.4. Thống kê (statistics)......................................................................................28
5. Các kỹ thuật tối ưu hóa tập trung ........................................................................30
5.1. Thuật toán INGRES......................................................................................30
5.2. Thuật toán SYSTEM R ..................................................................................30
1. Phân rã câu truy vấn ............................................................................................32
1.1. Chuẩn hóa.....................................................................................................32
1.2. Phân tích.......................................................................................................33
1.3. Loại bỏ dư thừa ............................................................................................35
1.4. Viết lại...........................................................................................................36
2. Định vị dữ liệu phân tán......................................................................................37
2.1 Rút gọn phân mảnh ngang nguyên thủy...........................................................38
2.2 Rút gọn phân mảnh dọc ...................................................................................40
2.3 Rút gọn phân mảnh dẫn xuất ...........................................................................42
2.4 Rút gọn phân mảnh hỗn hợp............................................................................43
3. Tối ưu hóa các truy vấn phân tán ........................................................................44
3.1 Đầu vào bộ tối ưu hóa câu truy vấn ................................................................45
3.2 Thứ tự kết nối trên các truy vấn đoạn..............................................................47
4. Tối ưu hóa các truy vấn phân tán ........................................................................48
4.2 Thuật toán System R*.......................................................................................50
4.3 Thuật toán INGRES phân tán ..........................................................................52
5. Kết luận và hướng phát triển của đề tài...............................................................54
5.1 Kết luận............................................................................................................54
5.2 Hướng phát triển của đề tài.............................................................................54
TÀI LIỆU THAM KHẢO.............................................................................................56
3
DANH MỤC HÌNH VẼ
Hình 1: Sơ đồ tổng thể...................................................................................................16
Hình 2: Sơ đồ định vị ....................................................................................................18
Hình 3: Kiến trúc khách/chủ..........................................................................................19
Hình 4: Các hệ phân tán ngang hàng.............................................................................20
Hình 5: Môi trường đa tầng...........................................................................................20
Hình 6: Mô tả bộ xử lý truy vấn....................................................................................23
Hình 7: Mô tả các giai đoạn trong xử lý truy vấn .........................................................24
Hình 8: Mô hình tối ưu hóa truy vấn.............................................................................25
Hình 9: Đồ thị kết nối tương ứng ..................................................................................34
Hình 10: Đồ thị truy vấn không liên thông ...................................................................35
Hình 11: Ví dụ về cây đại số quan hệ............................................................................37
Hình 12: Rút gọn phân mảnh ngang với phép chọn......................................................39
Hình 13: Cây đại số quan hệ truy vấn gốc.....................................................................40
Hình 14: Rút gọn phân mảnh ngang với phép kết nối...................................................40
Hình 15: Rút gọn phân mảnh dọc..................................................................................41
Hình 16: Rút gọn phân mảnh dẫn xuất..........................................................................43
Hình 17: Rút gọn phân mảnh hỗn hợp ..........................................................................44
Hình 18: Truyền các toán hạng trong phép toán hai ngôi .............................................47
4
DANH MỤC TỪ VIẾT TẮT
1. DANH MỤC TỪ VIẾT TẮT TIẾNG VIỆT
STT
Từ viết tắt
CSDL
Cụm từ đầy đủ
1
2
3
4
5
6
7
Cơ sở dữ liệu
CSDLPT
CSDLTT
HQT CSDLPT
HQTCSDL
HTTT
Cơ sở dữ liệu phân tán
Cơ sở dữ liệu tập trung
Hệ quản trị cơ sở dữ liệu phân tán
Hệ quản trị cơ sở dữ liệu
Hệ thống thông tin
XLTV
Xử lý truy vấn
2. DANH MỤC TỪ VIẾT TẮT TIẾNG ANH
Nghĩa Tiếng Việt
Quản trị cơ sở dữ liệu
Truyền thông dữ liệu
Từ điển dữ liệu
STT Từ viết tắt
Cụm từ đầy đủ
Database management
Data communication
Data dictionary
1
2
3
4
5
6
7
DBM
DC
DD
Cơ sở dữ liệu phân tán
Lược đồ ngoài
DDB
ES
Distributed database
External Schema
Lược đồ khái niệm toàn cục
Lược đồ khái niệm cục bộ
GCS
LCS
Global Conceptual Schema
Local Conceptual Schema
5
CHƯƠNG 1. TỔNG QUAN NGHIÊN CỨU ĐỀ TÀI
1. Tính cấp thiết nghiên cứu của đề tài
Xã hội ngày càng phát triển kèm theo yêu cầu khối lượng thông tin cần xử lý, lưu
trữ trong các hệ thống thông tin (HTTT) tăng lên nhanh chóng. Dữ liệu lớn, cực lớn
lên tới hàng triệu bản ghi lại phải cập nhật chỉnh lý thường xuyên nên với mô hình cơ
sở dữ liệu tập trung (CSDLTT) sẽ gặp rất nhiều khó khăn về vấn đề tốc độ xử lý tại
máy chủ, băng thông đường truyền, ảnh hưởng đến tính sẵn sàng của hệ thống.
Bên cạnh đó, trên thực tế, các doanh nghiệp, các đơn vị và các tổ chức phải phân
bố trên một vùng rộng lớn về mặt địa lý, có thể dàn trải trên phạm vi nhiều thành phố,
toàn bộ quốc gia hay một vài quốc gia, thậm chí trên toàn cầu, nên việc lưu trữ, xử lý
dữ liệu tập trung không khả thi. Dữ liệu không thể lưu trữ tập trung ở một địa điểm
nhất định mà rải khắp các địa điểm mà cơ quan, tổ chức hay doanh nghiệp đó hoạt
động.
Khi dữ liệu không còn lưu trữ tập trung thì vấn đề làm thế nào để quản lý truy
xuất, tốc độ truy xuất dữ liệu phục vụ cho công tác chuyên môn không bị ảnh hưởng,
không bị gián đoạn là một vấn đề quan trọng được đặt ra. Đây chính là tiền đề để cơ sở
dữ liệu phân tán (CSDLPT) ra đời. Trong các hệ thống sử dụng CSDLPT dữ liệu thực
sự được lưu trữ trên nhiều trạm riêng biệt, tuy nhiên, việc quản lý khai thác lại được
xây dựng sao cho người sử dụng có thể truy vấn dữ liệu như một CSDLTT.
Khi khối lượng thông tin phải xử lý ngày càng lớn, phong phú và đa dạng thì vấn
đề đặt ra là cần xử lý thông tin như thế nào để giảm chi phí đến mức tối thiểu. Một
trong các giải pháp có tính khả thi là phải tối ưu hoá các câu lệnh khi truy vấn dữ liệu.
Tối ưu hóa câu lệnh truy vấn trên CSDLPT đòi hỏi nhiều kỹ thuật phức tạp hơn khi tối
ưu hóa truy vấn trên CSDL thông thường, do cơ sở dữ liệu được lưu trữ rời rạc.
Từ tình hình thực tế và nhu cầu đó, việc nghiên cứu về truy vấn và tối ưu hóa
truy vấn trong CSDLPT là một điều vô cùng cần thiết, có tính ứng dụng cao trong các
doanh nghiệp. Vì vậy tôi chọn đề tài “Nghiên cứu một số vấn đề về truy vấn và tối ưu
hóa truy vấn cơ sở dữ liệu phân tán trong hệ thống thông tin” để nghiên cứu. Đề tài
hướng đến việc hệ thống hóa các vấn đề trong xây dựng câu truy vấn và tối ưu hóa các
câu truy vấn trong môi trường đặc trưng của CSDLPT.
2. Tổng quan về đề tài nghiên cứu
Hiện nay, quản lý, xử lý và khai thác thông tin, dữ liệu là một lĩnh vực thu hút sự
quan tâm, đầu tư nghiên cứu và triển khai mạnh mẽ ở các nước tiên tiến về CNTT,
nhất là khi ngành công nghiệp nội dung số đang nổi lên như một lĩnh vực kinh doanh
có lợi nhuận cao. Các công nghệ liên quan đến công nghệ dữ liệu (data engineering),
tìm kiếm thông tin (information retrieval), xử lý dữ liệu (data procesing), CSDL lưới
(Grid Database)… được nghiên cứu rộng rãi tại các chuyên ngành liên quan đến
CNTT tại các trường đại học lớn trên thế giới. Các chương trình này đã và đang được
hỗ trợ bởi một ngành công nghiệp khổng lồ để đưa các thành tựu mới về công nghệ
trong các lĩnh vực này vào ứng dụng một cách nhanh chóng. Các chính phủ của các
6
nước tiên tiến coi việc phát triển, nắm bắt và ứng dụng các thành tựu mới trong các
ngành công nghệ này là công tác sống còn trong việc phát triển các hạ tầng thông tin
và phục vụ lợi ích quốc gia và phát triển kinh tế.
Do đó, một số hiệp hội của các nhà nghiên cứu và phát triển các công nghệ, ứng
dụng quản lý thông tin và dữ liệu đã ra đời và có ảnh hưởng lớn trên thế giới. Nổi tiếng
nhất là SIGMOD thuộc ACM và Data Engineering của IEEE, cả hai đều thuộc Mỹ
nhưng được công nhận rộng rãi trên toàn thế giới. Tại một số nước tiên tiến khác cũng
tổ chức các phân hội địa phương của các hiệp hội này. Ðiều này chứng tỏ tầm ảnh
hưởng của các tổ chức này trong ngành xử lý dữ liệu trên thế giới. Ngoài ra các nước
cũng có các tổ chức quốc gia riêng về công nghệ xử lý dữ liệu. Ví dụ, tại Nhật Bản có
SIGMOD-Japan và Tổ chức xử lý thông tin Japan (Japan InformationProcessing
Society). Các tổ chức này hiện nay đều hỗ trợ mạnh các công nghệ xử lý dữ liệu lớn
(big data) trong đó có vấn đề nghiên cứu về CSDLPT.
Theo [1], trong hệ thống cơ sở dữ liệu phân tán, sự lưu trữ và dư thừa dữ liệu
phân tán có tiện ích là để phục hồi lỗi, nhưng cũng vì thế nó làm cho quá trình xử lý
truy vấn phân tán phức tạp hơn tại cùng một thời điểm. Vì vậy, trong các nhánh nghiên
cứu về CSDLPT, nghiên cứu về tối ưu hóa và xử lý truy vấn là một trong những công
nghệ quan trọng nhất. Trong nghiên cứu này, tác giả sử dụng toán tử bán kết hợp nhằm
cải thiện hiệu suất của các truy vấn và giảm thời gian tìm kiếm.
Tác giả Lin Zhou đã mô tả ngắn gọn các khái niệm tương ứng và đặc điểm của hệ
thống cơ sở dữ liệu phân tán, tóm tắt những mục tiêu tối ưu hóa truy vấn cơ sở dữ liệu
phân tán và phân tích các quá trình tối ưu hóa truy vấn dựa trên toán tử bán kết hợp với
các ứng dụng thực tế cùng với thuật toán cổ điển SDD-1 nhằm thực hiện tối ưu hóa
truy vấn trong cơ sở dữ liệu phân tán.
Theo Pawandeep Kaur [2] thì tối ưu hóa truy vấn là quá trình sử dụng phương án
tốt nhất cho truy vấn để cải thiện hiệu suất của các truy vấn. Tối ưu hóa truy vấn trong
cơ sở dữ liệu phân tán khó khăn hơn rất nhiều so với cơ sở dữ liệu tập trung. Truy vấn
trong cơ sở dữ liệu phân tán bị ảnh hưởng bởi các yếu tố như phương pháp chèn dữ
liệu vào máy chủ từ xa và cách thời gian phản hồi giữa các máy chủ. Thời gian trả lời
của các truy vấn phụ thuộc vào thời gian truyền và tốc độ xử lý của các máy cục bộ.
Trong đó, vai trò của việc xây dựng một mô hình ước lượng chi phí của truy vấn phù
hợp là rất quan trọng. Mô hình phù hợp sẽ tạo nên tảng để ước lượng chi phí cho các
phương thức tối ưu hóa truy vấn khác nhau và lựa chọn phương án tốt nhất.
Trong [3], Shyam Padia đã chứng minh tường minh răng vấn đề tối ưu hóa truy
vấn trong cơ sở dữ liệu phân tán quy mô lớn là bài toán NP - khó trong tự nhiên và rất
khó để giải quyết. Các bài toán thuộc lớp NP-khó, ví dụ như bài toán tối ưu hó truy
vấn, sự phức tạp của bộ tối ưu hóa tăng phi tuyến khi số lượng các quan hệ và số lượng
các mối ràng buộc trong một truy vấn tăng lên. Nghiên cứu đã tìm hiểu và giới thiệu
một số các các chiến lược tối ưu hóa khác nhau và các nghiên cứu cho thấy rằng hiệu
suất tối ưu hóa truy vấn phân tán được cải thiện khi sử dụng thuât toán đàn kiến được
tích hợp trong các thuật toán tối ưu hóa.
7
Tại Việt nam, trong một thời gian dài, tầm quan trọng của các HTTT có mức tự
động hóa cao không được đánh giá đúng mức trong quản lý nhà nước và phát triển
kinh tế, kinh doanh. Việc nghiên cứu về CSDL trong một thời gian dài tập trung vào lý
thuyết CSDL như nghiên cứu về mô hình CSDL dùng các công cụ toán học. Trong
lĩnh vực ứng dụng, mặc dù có không ít các dự án xây dựng các CSDL nhưng lĩnh vực
này chưa được nghiên cứu đánh giá một cách tổng thể, sử dụng còn ở mức chưa khai
thác hết tất cả các tính năng của các công nghệ CSDL hiện đại. Giữa lý thuyết và ứng
dụng là một khoảng cách lớn.
Theo Đào Ngọc Sơn [4], hệ thống phân tán là một hệ thống cơ sở dữ liệu phức
tạp, đòi hỏi việc tổ chức cơ sở hạ tầng vật lý và mô hình kết nối mạng phức tạp. Việc
tìm hiểu và tối ưu hóa truy vấn trong CSDLPT có ý nghĩa quan trọng quyết định đến
hiệu năng hệ thống, làm hệ thống cơ sở dữ liệu phân tán mang những lợi ích giống như
cơ sở dữ liệu tập trung và phát huy những ưu thế cơ sở dữ liệu phân tán mang lại.
Công trình đã trình bày các nguyên lý chung để tối ưu hóa bao gồm: Các chiến lược tối
ưu tổng quát, các kỹ thuật tối ưu hóa cơ bản, các biến đổi đại số,… và giới thiệu các
thuật toán tối ưu hóa trong cơ sở dữ liệu phân tán, dựa vào mô hình chi phí hoặc thời
gian đáp ứng hệ thống, các thuật toán INGRES phân tán, Thuật toán System R*, thuật
toán SDD-1 và thuật toán AHY. Bên cạnh đó tác giả cũng đã cài đặt thử nghiệm thuật
toán System R* phân tán trong một hệ thống CSDLPT mô phỏng.
Đề tài nghiên cứu của Phạm Thị Thu Huyền [5] đã trình bày các vấn đề cơ bản
của cơ sở dữ liệu phân tán, cơ sở dữ liệu tập trung, các kỹ thuật tối ưu hóa truy vấn tập
trung và phân tán. Qua đó cài đặt thử nghiệm một thuật toán SDD-1 để tối ưu truy vấn
phân tán trong một hệ thống CSDLPT đơn giản.
Qua các nghiên cứu trên thế giới và tại Việt nam, chúng ta có thể nhận thấy việc
nghiên cứu về CSDLPT và tối ưu hóa truy vấn trên cơ sở dữ liệu này là rất quan trọng.
Các nghiên cứu trên thế giới đã đi sâu vào các khía cạnh kỹ thuật đơn giản cũng như
phức tạp trong việc phân tích câu truy vấn và tối ưu hóa xử lý câu truy vấn. Các nghiên
cứu ở Việt nam cũng đã từng bước thực hiện việc cài đặt và thử nghiệm các thuật toán
ứng dụng trong tối ưu hóa các truy vấn một cách rời rạc. Do đó, trong nghiên cứu này,
tác giả thực hiện việc trình bày một cách có hệ thống các vấn đề liên quan đến
CSDLPT và tổng hợp các thuật toán phổ biến đại diện cho các cách tiếp cận khác
nhau trong việc tối ưu hóa câu truy vấn dành cho CSDLPT.
3. Mục tiêu nghiên cứu
Tối ưu hóa truy vấn trong CSDLPT là một lĩnh vực rất rộng, trong phạm vi của
đề tài này, tác giả sử dụng một cách tiếp cận có tính ứng dụng cao. Trong đó mục tiêu
chính trong nghiên cứu bao gồm:
- Hệ thống hóa các nghiên cứu, và lý thuyết về các vấn đề cơ bản của cơ sở dữ
liệu phân tán, các nguyên lý chung, các kỹ thuật và các thuật toán liên quan đến
truy vấn và tối ưu hóa truy vấn trong hệ thống thông tin.
- Giới thiệu chi tiết các thuật toán chính được sử dụng trong tối ưu hóa CSDLPT.
8
- Báo cáo đề tài có thể làm tài liệu tham khảo cho việc viết giáo trình các môn:
Cơ sở dữ liệu 2; Phân tích thiết kế hệ thống thông tin và là tài liệu tham khảo các
học phần: Phân tích thiết kế hệ thống thông tin; Hệ thống thông tin quản lý.
4. Đối tượng và phạm vi nghiên cứu
Đối tượng nghiên cứu: Các vấn đề về cơ sở dữ liệu phân tán, các nguyên lý
chung, các kỹ thuật, các thuật toán liên quan đến vấn đề tối ưu hoá truy vấn cơ sở dữ
liệu phân tán trong hệ thống thông tin.
Phạm vi nghiên cứu: Đề tài tập trung nghiên cứu về truy vấn và một số các kỹ
thuật tối ưu hóa truy vấn trong cơ sở dữ liệu phân tán.
5. Phương pháp nghiên cứu
Đề tài đã sử dụng phương pháp nghiên cứu tài liệu về lý thuyết cơ sở dữ liệu
phân tán, các kỹ thuật truy vấn trong các sách chuyên ngành, bài báo đã công bố tại
các tạp chí chuyên ngành uy tín, nhằm đưa ra một số các kiến thức tổng quan xử lý
truy vấn cơ sở dữ liệu phân tán.
Phương pháp thu thập dữ liệu: sử dụng phương pháp thống kê, so sánh nhằm nêu
ra được những sự khác biệt giữa vấn đề xử lý truy vấn trong cơ sở dữ liệu tập trung và
cơ sở dữ liệu phân tán.
Mặt khác, đề tài cũng kết hợp nghiên cứu giữa lý thuyết và thực nghiệm để có thể
phân tích một số các ví dụ minh họa giữa các thao tác khi xử lý tối ưu hóa truy vấn cơ
sở dữ liệu phân tán trong hệ thống thông tin.
6. Kết cấu báo cáo nghiên cứu
Về nội dung và bố cục, ngoài các phần như: mục lục, danh mục hình vẽ, danh
mục từ viết tắt và tài liệu tham khảo, phụ lục, báo cáo được trình bày gồm 5 chương:
Chương 1: Tổng quan nghiên cứu đề tài
Chương này sẽ trình bày sơ lược về tổng quan đề tài nghiên cứu: tính cấp thiết,
tình hình nghiên cứu về đề tài ở trong và ngoài nước, mục tiêu nghiên cứu, đối tượng,
phạm vi nghiên cứu, và các phương pháp nghiên cứu khi tìm hiểu về vấn đề truy vấn
và tối ưu hóa truy vấn cơ sở dữ liệu phân tán trong hệ thống thông tin.
Chương 2: Tổng quan về cơ sở dữ liệu phân tán
Nội dung chương này sẽ trình bày một cách tổng quan nhất về CSDL phân tán,
bao gồm các khái niệm, đặc trưng và kiến trúc của cơ sở dữ liệu phân tán đồng thời nội
dung của chương này cũng giới thiệu thêm một số các mô hình xử lý phân tán trong hệ
thống thông tin.
Chương 3: Các nguyên lý chung của tối ưu hóa truy vấn cơ sở dữ liệu phân
tán
Trong chương này sẽ giới thiệu về nguyên lý xử lý truy vấn, các chiến lược tối
ưu hóa truy vấn cơ bản, một số các phép biến đổi đại số và các kỹ thuật tối ưu hóa tập
trung làm nền tảng cho tối ưu hóa trong CSDLPT.
9
Chương 4: Tối ưu hóa truy vấn phân tán
Nội dung chương này sẽ đề cập đến vấn đề tối ưu hóa truy vấn như cách phân rã
câu truy vấn, phương pháp định vị dữ liệu phân tán và các chiến lược và các thuật toán
để tối ưu hóa truy vấn phân tán. Đồng thời trong chương này cũng đưa ra nững hạn
chế còn tồn tại trong nghiên cứu và đặt ra các hướng phát triển nghiên cứu trong tương
lai.
10
CHƯƠNG 2: TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU PHÂN
TÁN
1. Khái niệm về hệ cơ sở dữ liệu phân tán
1.1. Cơ sở dữ liệu phân tán
Trong các Hệ thống thông tin (HTTT) xử lý tập trung, hệ cơ sở dữ liệu phát triển
từ mô hình xử lý dữ liệu mà trong đó mỗi hệ thống ứng dụng định nghĩa một hay nhiều
tệp dữ liệu riêng, các dữ liệu được ánh xạ sang mô hình định nghĩa và được quản lý tập
trung. Mô hình này dẫn đến sự độc lập dữ liệu, nói cách khác, các ứng dụng có sự bất
biến tương đối về cấu trúc lưu trữ và chiến lược truy cập dữ liệu.
Tuy nhiên, trong các hệ xử lý phân tán, các thành phần của hệ xử lý phân tán
nằm độc lập về mặt vật lý, có sự liên kết tương đối lỏng lẻo thông qua các hệ thống
mạng kết nối, do đó “hệ dữ liệu phân tán” được coi như công cụ làm cho quá trình xử
lý dữ liệu phân tán dễ dàng và hiệu quả hơn. Cơ sở dữ liệu phân tán được phát triển
như là một tất yếu trong mô hình xử lý thông tin này.
Cơ sở dữ liệu phân tán: Là một tập hợp nhiều cơ sở dữ liệu có liên đới logic và
được phân bố rải rác trên nhiều máy trong một mạng máy tính.
Trong mô hình cơ sở dữ liệu phân tán, bản thân cơ sở dữ liệu có ở trên nhiều máy
tính khác nhau. Như vậy, đặc trưng nổi bật nhất của cơ sở dữ liệu phân tán là các
CSDL được phân bố trên nhiều máy tính khác nhau trong một mạng máy tính và có
liên đới về mặt logic. Tuy nhiên, việc làm rõ thế nào là một CSDLPT có liên đới logic
và một tập hợp các CSDL rời rạc vẫn còn tương đối khó khăn. Hiện tại, vẫn chưa tồn
tại một định nghĩa rõ ràng về các liên đới logic trong CSDLPT, nhưng một định nghĩa
được chấp nhận phổ biến như sau:
Liên đới logic: Toàn bộ dữ liệu của CSDLPT có một số các thuộc tính ràng buộc
chúng với nhau, điều này giúp chúng ta có thể phân biệt một CSDL phân tán với một
tập hợp CSDL cục bộ hoặc các tập tin lưu trữ tại các vị trí khác nhau trong một mạng
máy tính.
Hệ CSDL phân tán không đơn thuần là tập hợp các tệp dữ liệu đơn lẻ phân bố rời
rạc trong mạng máy tính. Để hình thành một hệ CSDL phân tán, cần có một cấu trúc
giao diện chung giữa các tệp dữ liệu này để có thể xây dựng một cơ chế truy cập lẫn
nhau giữa các tệp dữ liệu.
Ví dụ: CSDL quan hệ thường được tổ chức và biểu diễn dưới dạng các bảng.
Việc phân mảnh một quan hệ thành nhiều quan hệ con khác nhau để lưu trữ trên nhiều
máy trạm trong một mạng máy tính thường được thực hiện theo cách phân mảnh theo
chiều dọc hoặc theo chiều ngang.
Cụ thể: cho quan hệ PROJ = {PNO, BUDGET, PNAME, LOG}; quan hệ PROJ
có thể tách thành hai quan hệ PROJ1 = {PNO, BUDGET} và quan hệ PROJ2 = {PNO,
PNAME, LOG} và hai quan hệ này có thể được lưu trữ ở hai máy trạm khác nhau.
11
Giả sử quan hệ PROJ có dữ liệu như sau.
PNO
P1
P2
P3
P4
BUDGET PNAME
LOG
150000 Instrumentation
350000 Database development
Montreal
New York
New York
Paris
CAD/CAM
250000
139000 Maintenance
Khi đó: PROJ1 = 휋푃푁푂,퐵푈퐷퐺퐸푇(푃푅푂퐽) và có kết quả tương ứng là
PNO
P1
P2
P3
P4
BUDGET
150000
350000
250000
139000
Đồng thời: PROJ2 = 휋푃푁푂,푃푁퐴푀퐸,퐿푂퐺(푃푅푂퐽) và có kết quả tương ứng là
PNO
P1
P2
P3
P4
PNAME
Instrumentation
Database development
CAD/CAM
LOG
Montreal
New York
New York
Paris
Maintenance
Vậy trong CSDLPT quan hệ PROJ sẽ được lưu trữ dưới dạng hai quan hệ PROJ1
và PROJ2.
Cùng với sự phát triển của các cấu trúc tổ chức kinh tế xã hội, trong đó các cơ
quan tổ chức thường hoạt động phân tán trong một phạm vi rộng, tầm quốc gia hoặc
toàn cầu, các thiết kế và cài đặt hệ CSDL phân tán là phù hợp và đáp ứng mọi nhu cầu
truy xuất dữ liệu. Sự phát triển mạnh của công nghệ phần cứng, mạng truyền thông
cũng đảm bảo cho các hệ thống sử dụng hệ CSDL phân tán có tính tin cậy và tính sẵn
sàng cao, giảm chi phí truyền thông và đảm bảo hiệu suất công việc.
1.2. Hệ quản trị cơ sở dữ liệu phân tán
Hệ quản trị CSDL là một tập hợp các chương trình cho phép người dùng định
nghĩa, tạo lập, bảo trì các CSDL và cung cấp các truy cập có điều khiển đến các CSDL
này. Mục đích chính của một hệ CSDL là cung cấp cho người dùng một cách nhìn trừu
tượng về dữ liệu. Điều đó có nghĩa là hệ thống che dấu những chi tiết phức tạp về cách
thức dữ liệu được lưu trữ và bảo trì. Hệ CSDL phân tán cũng đòi hỏi một Hệ quản trị
CSDL phân tán có những đặc điểm riêng biệt.
Hệ quản trị cơ sở dữ liệu phân tán: Hệ quản trị CSDL phân tán cung cấp công
cụ như tạo lập và quản lý CSDL phân tán. Hệ quản trị CSDL phân tán có chức năng
hỗ trợ việc tạo và bảo trì CSDL phân tán, chúng có các thành phần tương tự như một
hệ quản trị CSDL tập trung và các thành phần hỗ trợ trong việc chuyển tải dữ liệu đến
các trạm và ngược lại.
12
Các thành phần sau đây đòi hỏi một Hệ quản trị CSDL phân tán thương mại phải
có:
- Quản trị dữ liệu (database management): DBM
- Truyền thông dữ liệu (data communication): DC
- Từ điển dữ liệu (data dictionary): DD dùng để mô tả thông tin về sự phân tán
của dữ liệu trên mạng.
- Cơ sở dữ liệu phân tán (distributed database): DDB
Hệ quản trị CSDL phân tán sử dụng nhiều kiến trúc lưu trữ phân tán khác nhau,
có thể phân thành một số loại chính như sau:
Cơ sở dữ liệu phân tán thuần nhất:
Một CSDLPT được coi là thuần nhất nếu thỏa mãn tính chất sau: tất cả các nút
(các máy tính trạm của một mạng máy tính dùng để lưu trữ toàn bộ CSDLPT) cùng sử
dụng một loại hệ quản trị CSDL.
CSDLPT thuần nhất thường được xây dựng bằng cách chia một CSDL thành một
tập CSDL cục bộ. Phương phức xử lý trong CSDLPT thuần nhất thuận lợi cho việc
tăng trưởng, mở rộng CSDL và cho phép nâng cao hiệu năng xử lý của toàn hệ thống.
Cơ sở dữ liệu phân tán hỗn tạp:
Ngược lại với CSDLPT thuần nhất, trong CSDLPT hỗn tạp, các nút có thể thực
hiện trên các hệ quản trị CSDL khác nhau. CSDLPT hỗn tạp thường xảy ra khi CSDL
mới được xây dựng từ tập hợp các nút mạng đã cài đặt CSDL riêng. Khi đó, thay vì
xây dựng lại các CSDL cục bộ, hệ thống mới được xây dựng bằng cách tích hợp luôn
các CSDL cục bộ đã có.
2. Các đặc trưng của cơ sở dữ liệu phân tán
CSDL phân tán không đơn giản là sự thực hiện phân tán của các CSDL tập trung,
bởi vì chúng cho phép thiết kế các đặc trưng khác với CSDL tập trung truyền thống.
Các đặc điểm tiêu biểu của CSDL truyền thống gồm: Điều khiển tập trung, độc lập dữ
liệu, giảm dư thừa dữ liệu, biệt lập và bảo mật dữ liệu. Những đặc điểm này trong
CSDLPT có sự thay đổi đáng kể, tạo ra một hướng đi mới trong việc xây dựng các
HTTT trên CSDLPT.
2.1. Điều khiển tập trung
Trong CSDL tập trung: Khả năng điều khiển tập trung trên toàn nguồn tài nguyên
thông tin của tổ chức, được xem là động cơ mạnh nhất cho việc ra đời CSDL. Chúng
được phát triển như là sự tiến hoá của hệ thống thông tin mà trong đó mỗi ứng dụng có
các tập tin riêng của nó.
Trong CSDL phân tán: Ý niệm về điều khiển tập trung ít được nhấn mạnh hơn,
điều này phụ thuộc vào kiến trúc của CSDL phân tán. Kiến trúc của CSDLPT được
trình bay chi tiết hơn ở phần tiếp theo, tuy nhiên ở đây, chúng ta có thể nhận định các
13
CSDLPT được xây dựng dựa vào kiến trúc client/server đặc biệt là kiến trúc multi-
client/single-server sẽ có mức độ điều khiển tập trung cao hơn các kiến trúc khác, ví
dụ như kiến trúc CSDLPT ngang hàng (peer-to-peer).
2.2. Độc lập dữ liệu
Trong CSDL phân tán, độc lập dữ liệu cũng quan trọng giống như trong CSDL
truyền thống. Tuy nhiên, một khía cạnh mới được thêm vào trong ý niệm của độc lập
dữ liệu là trong suốt phân tán. Với trong suốt phân tán chúng ta hiểu rằng các chương
trình ứng dụng có thể sử dụng CSDL như là nó không được tổ chức phân tán. Vì thế sự
chính xác của chương trình không bị ảnh hưởng bởi việc dịch chuyển dữ liệu từ trạm
này đến trạm khác, tuy nhiên tốc độ thực hiện của chúng bị ảnh hưởng.
Trong CSDLPT, việc trong suốt phân tán sẽ dựa trên các phương pháp để làm ẩn
các kỹ thuật rời rạc hóa dữ liệu được sử dụng. Do đó, trong suốt CSDLPT được chia
thành các vấn đề nhỏ hơn, bao gồm: trong suốt phân đoạn, trong suốt về vị trí, trong
suốt ánh xạ địa phương, trong suốt nhân bản.Các kỹ thuật trong suốt CSDLPT không
phải là trọng tâm trong nghiên cứu này, nên tác giả không trình bày một các cụ thể
trong báo cáo. Các kỹ thuật này có thể được tìm thấy trong các tài liệu tham khảo đi
kèm với báo cáo.
2.3. Giảm dư thừa dữ liệu
Trong CSDL truyền thống, dữ liệu dư thừa được giảm đến mức tối thiểu bởi hai
lý do: Sự không tương thích giữa nhiều bản sao của cùng một tập dữ liệu. Tiết kiệm
không gian lưu trữ bằng cách loại bỏ các dư thừa. Việc giảm dư thừa dữ liệu có thể đạt
được bằng cách chia sẻ dữ liệu cho phép nhiều ứng dụng truy cập cùng các bản tin và
bản ghi.
Trong CSDL phân tán, việc giảm dư thừa phức tạp hơn vì ngoài hai lý do trên
còn nhiều lý do để giảm dư thừa như: Hoạt động của các trình ứng dụng có thể được
tăng lên khi dữ liệu được sao lại tất cả các vị trí nơi trình ứng dụng cần nó. Tính
thường trực của hệ thống sẽ tăng lên bởi vì khi có lỗi xảy ra ở một trạm nào đó sẽ
không dừng việc thực hiện các ứng dụng của trạm khác nếu dữ liệu đã được sao chép
lại.
2.4. Độ tin cậy qua các giao dịch phân tán
Hệ quản trị CSDL phân tán cải thiện độ tin cậy qua các giao dịch phân tán vì các
thành phần được nhân bản hạn chế được các vị trí lỗi riêng lẻ. Lỗi của trạm riêng, hoặc
lỗi của truyền thông làm cho một hoặc nhiều trạm mất liên lạc, không đủ để phá vỡ
toàn bộ hệ thống. Trong trường hợp CSDL phân tán, điều này nghĩa là một số dữ liệu
không thể truy nhập được, nhưng nếu biết cách hỗ trợ cho các giao dịch phân tán và
các giao thức ứng dụng thì người sử dụng vẫn có thể truy nhập được tới phần khác
trong CSDL phân tán.
2.5. Cải tiến hiệu năng
Hiệu năng của CSDL phân tán được nâng cao dựa trên hai đặc điểm:
14
Hệ quản trị CSDL PT có khả năng phân mảnh DSDL khái niệm và cho phép cụ
bộ hóa dữ liệu. Phương hthức này có hai ưu điểm nổi bật. Thứ nhất, mỗi trạm chỉ xử lý
một phần CSDL, sự tranh chấp về CPU và các dịch vụ vào/ra không nghiêm trọng như
trong hệ CSDL tập trung. Thứ hai, tính cụ bộ làm giảm trễ truy nhập từ xa thường gặp
trên các mạng diện rộng.
Tính song song của các hệ thống phân tán có thể được khai thác để thực hiện
song song liên truy vấn và truy vấn nội bộ. Liên truy vấn song song là khả năng thực
hiện nhiều truy vấn tại cùng thời điểm, còn nội truy vấn song song là phương pháp
tách một truy vấn đơn thành các truy vấn von và mỗi truy vấn con được thực hiện tại
các trạm khác nhau, truy nhập các phần khác nhau của CSDL phân tán.
2.6. Dễ dàng mở rộng hệ thống
Trong môi trường phân tán khả năng mở rộng kích thước dữ liệu được thực hiện
rất dễ dàng và hiếm khi cần sửa đổi trong các hệ thống lớn. Việc mở rộng thường có
thể được thực hiện bằng cách tăng khả năng lưu trữ và xử lý của mạng. Trong một Hệ
CSDL cũng không thể gia tăng năng lực lưu trữ và xử lý một cách tuyến tính, vì điều
này phụ thuộc vào “chi phí” phân tán; chi phí liên quan đến năng lực tính toán và thời
gian truyền tải dữ liệu cần thiết khi xử lý phân tán. Tuy nhiên, khả năng mở rộng của
CSDL phân tán vẫn lớn hơn rất nhiều so với CSDL tập trung, và có tính kinh tế cao
hơn.
3. Kiến trúc cơ bản của cơ sở dữ liệu phân tán
3.1. Sơ đồ tổng thể
Sơ đồ này xác định tất cả các dữ liệu sẽ được lưu trữ trong CSDL phân tán. Sơ đồ
tổng thể có thể được định nghĩa một cách chính xác theo cách như trong CSDL không
phân tán. Ở đây sẽ sử dụng mô hình quan hệ để hình thành nên sơ đồ này. Sử dụng mô
hình này, sơ đồ tổng thể bao gồm định nghĩa của một tập các quan hệ tổng thể.
15
Lược đồ toàn cục
Lược đồ phân đoạn
Lược đồ định vị
Sơ đồ ánh xạ địa
Sơ đồ ánh xạ địa
phương 1
phương 2
HQTCSDL (DBMS) tại
vị trí 1
HQTCSDL (DBMS) tại
vị trí 2
CSDL địa phương tại
CSDL địa phương tại
vị trí 1
vị trí 2
Hình 1: Sơ đồ tổng thể
3.2. Sơ đồ phân đoạn
Mỗi quan hệ tổng thể có thể chia thành một vài phần nhỏ hơn không giao nhau
được gọi là đoạn (fragments). Có nhiều cách khác nhau để thực hiện việc phân chia
này. Sơ đồ tổng thể mô tả các ánh xạ giữa các quan hệ tổng thể và các đoạn được định
nghĩa trong sơ đồ phân đoạn. Ánh xạ này là một- nhiều. Có thể có nhiều đoạn liên kết
tới một quan hệ tổng thể, nhưng mỗi đoạn chỉ liên kết tới nhiều nhất là một quan hệ
tổng thể. Các đoạn được chỉ ra bằng tên của quan hệ tổng thể cùng với tên của chỉ mục
đoạn.
3.3. Sơ đồ định vị
Các đoạn là các phần logic của một quan hệ tổng thể được định vị trên một hoặc
nhiều vị trí vật lý trên mạng. Sơ đồ định vị xác định đoạn nào ở các trạm nào. Lưu ý
rằng, kiểu ánh xạ được định nghĩa trong sơ đồ định vị quyết định CSDL phân tán là dư
thừa hay không. Tất cả các đoạn liên kết với cùng một quan hệ tổng thể R và được
định vị tại cùng một trạm j cấu thành ảnh vật lý của quan hệ tổng thể R tại trạm j. Bởi
vậy, có thể ánh xạ một-một giữa một ảnh vật lý và một cặp (quan hệ tổng thể, trạm).
Các ảnh vật lý có thể được chỉ ra bằng tên của một quan hệ tổng thể và một chỉ mục
trạm.
16
17
Ví dụ: ký hiệu Ri chỉ tới đoạn thứ i của quan hệ tổng thể R (hình 2).
Ký hiệu Rj là ảnh vật lý của quan hệ tổng thể R tại trạm j (hình 2).
Hình 2: Sơ đồ định vị
3.4. Sơ đồ ánh xạ địa phương
Do ba mức trên của lược đồ hoàn toàn độc lập với mô hình quản trị dữ liệu của
các HQT CSDL địa phương, nên ở mức thấp hơn, các mô hình vật lý cần được ánh xạ
thành các đối tượng được quản lý và thực hiện bởi các HQT CSDL địa phương.
Sơ đồ ánh xạ địa phương: Ánh xạ các ảnh vật lý tới các đối tượng được các hệ
quản trị CSDL địa phương thao tác tại các trạm. Ánh xạ này phụ thuộc vào các hệ
quản trị CSDL địa phương. Do vậy, trong một hệ thống không đồng nhất, phải có các
kiểu ánh xạ địa phương khác nhau tại các trạm khác nhau.
4. Các mô hình xử lý phân tán
Quá trình thiết kế một CSDL bắt đầu với một sự phân tích những thông tin nào
của thế giới thực CSDL phải lưu trữ và các mối quan hệ giữa các thành phần của
những thông tin này. Thông thường, cấu trúc của CSDL được đặc tả bởi một ngôn ngữ
đặc biệt hay một tập các ký hiệu thích hợp để biểu thị một thiết kế CSDL.
4.1. Mô hình xử lý Master - Slave
Các hệ quản trị CSDL Client/Server cung cấp kiến trúc hai lớp chức năng Server
và chức năng Client, nhằm tạo ra sự dễ dàng trong việc quản lý tính phức tạp của các
hệ quản trị CSDL hiện đại và tính phức tạp của việc phân tán dữ liệu.
Server thực hiện hầu hết các công việc quản lý dữ liệu. Nghĩa là tất cả mọi xử lý
và tối ưu hoá truy vấn, quản lý giao dịch và quản lý lưu trữ đều được thực hiện trên
Server. Client, ngoài ứng dụng và giao diện người sử dụng, có một module hệ quản trị
CSDL Client trách nhiệm quản lý dữ liệu và khóa giao dịch được gửi đến Client.
Client và Server trao đổi với nhau bởi các câu lệnh SQL. Cụ thể hơn, Client chuyển
truy vấn SQL đến Sever, Server sẽ thực hiện và trả lại kết quả cho Client.
18
Loại kiến trúc Client/Server đơn giản chỉ có một Server được truy nhập bởi nhiều
Client, gọi là đa Client-đơn Server. Việc quản lý dữ liệu không khác so với CSDL tập
trung. CSDL chỉ được lưu trên Server và có phần mềm quản lý nó. Tuy nhiên, sự khác
biệt quan trọng so với các hệ thống tập trung là cách thực thi giao dịch và quản lý bộ
nhớ Cache.
Loại kiến trúc có nhiều Server trong hệ thống được gọi là đa Client- đa Server.
Có hai chiến lược quản lý: hoặc Client quản lý kết nối của nó tới Server hoặc Client
chỉ biết Server chủ của nó và liên lạc với các Server khác qua Server chủ khi có yêu
cầu. Chiến lược thứ nhất làm đơn giản cho các Server, nhưng lại gắn thêm nhiều trách
nhiệm cho các máy Client. Điều này dẫn đến một hệ thống được gọi là hệ máy khách
tự phục vụ. Mặt khác, với chiến lược thứ hai, tập trung vào chức năng quản lý dữ liệu
tại Server. Vì vậy, tính trong suốt của truy nhập dữ liệu được cung cấp tại giao diện
Server.
Hình 3: Kiến trúc khách/chủ
4.2. Các hệ phân tán ngang hàng
Trong các hệ ngang hàng, tổ chức dữ liệu vật lý và tổ chức lưu trữ trên các máy
khác nhau có thể khác nhau. Điều này có nghĩa là cần phải có một định nghĩa nội tại
riêng cho mỗi vị trí, được, gọi là lược đồ nội tại cục bộ LIS (Local Internal Schema).
Lược đồ khái niệm toàn cục mô tả cấu trúc logic của dữ liệu ở mọi vị trí.
Dữ liệu trong một CSDL phân tán thường được phân mảnh và nhân bản trên các
vị trí khác nhau. Vì vậy cần phải mô tả tổ chức lưu trữ dữ liệu vật lý trên mọi vị trí.
Cần bổ sung thêm tầng thứ cấp trong kiến trúc cơ sở dữ liệu 3 mức, đó là lược đồ khái
niệm cục bộ LCS (Local Conceptual Schema). Vì vậy lược đồ khái niệm toàn cục GCS
(Global Conceptual Schema) là hợp của các lược đồ khái niệm cục bộ. Mức trên cùng
19
là khung nhìn dữ liệu của người sử dụng, lược đồ ngoài ES (External Schema). Người
sử dụng khác nhau có cách nhìn dữ liệu cũng khác nhau. Như vậy kiến trúc của hệ cơ
sở dữ liệu phân tán có 3 mức: Có nhiều khung nhìn dữ liệu khác nhau trong mức lược
đồ ngoài, nhưng chỉ có duy nhất một mô hình khái niệm toàn cục và có nhiều mô hình
khái niệm cục bộ, ứng với lược đồ trong cục bộ trên mỗi vị trí.
Hình 4: Các hệ phân tán ngang hàng
4.3. Môi trường đa tầng
Trong môi trường tính toán đa tầng, khả năng xử lý hợp tác và xử lý phân tán
được đưa vào, tạo ra mô hình tính toán phân cấp. Trong mô hình này, tài nguyên tính
toán được phân bố theo chiều dọc.
Tầng thứ 2 thường bao gồm một máy chủ LAN mạnh đóng vai trò trung gian.
Máy chủ mạnh này vừa là một client của một máy tính lớn vừa là server cho các máy
trạm làm việc và các máy tính cá nhân nằm ở tầng thứ 3.
Hình 5: Môi trường đa tầng
20
Tải về để xem bản đầy đủ
57 trang
26/03/2022
4320
Bạn đang xem 20 trang mẫu của tài liệu "Báo cáo Đề tài Nghiên cứu một số vấn đề về truy vấn và tối ưu hóa truy vấn cơ sở dữ liệu phân tán trong hệ thống thông tin", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bao_cao_de_tai_nghien_cuu_mot_so_van_de_ve_truy_van_va_toi_u.pdf
