Luận văn Nghiên cứu các đặc tính của phân mảnh dọc trong cơ sở dữ liệu phân tán và ứng dụng
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
VŨ XUÂN OANH
NGHIÊN CỨU CÁC ĐẶC TÍNH
CỦA PHÂN MẢNH DỌC TRONG CSDL PHÂN TÁN
VÀ ỨNG DỤNG
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
THÁI NGUYÊN, NĂM 2020
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
VŨ XUÂN OANH
NGHIÊN CỨU CÁC ĐẶC TÍNH
CỦA PHÂN MẢNH DỌC TRONG CSDL PHÂN TÁN
VÀ ỨNG DỤNG
Chuyên ngành: Khoa học máy tính
Mã số: 84 8 01 01
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
NGƯỜI HƯỚNG DẤN KHOA HỌC
TS. LÊ VĂN PHÙNG
THÁI NGUYÊN, NĂM 2020
i
LỜI CAM ĐOAN
Tôi xin cam đoan toàn bộ nội dung luận văn này là do tôi tự sưu tầm, tra
cứu thông tin trên mạng Internet, trong một số sách tham khảo để sắp xếp, hoàn
thiện cho phù hợp với nội dung yêu cầu của đề tài.
Đến nay, nội dung luận văn của tôi chưa từng được công bố hay xuất bản
dưới bất kỳ hình thức nào. Nếu sai tôi xin chịu hoàn toàn trách nhiệm.
Ngày 7 tháng 11 năm 2020
Tác giả
Vũ Xuân Oanh
ii
LỜI CẢM ƠN
Trong suốt quá trình học tập và thực hiện đề tài, em đã nhận được sự
giúp đỡ tận tình và những chỉ bảo ân cần của các Thày cô trong viện Công nghệ
thông tin – Viện khoa học và công nghệ Việt nam, các Thày cô trong trường
đại học Công nghệ Thông tin và Truyền thông, cùng các bạn bè đồng nghiệp.
Đặc biệt là sự giúp đỡ của TS Lê Văn Phùng, người thầy trực tiếp hướng dẫn,
đưa ra ý tưởng, định hướng, chỉnh sửa các kiến thức chuyên môn và tận tình
giúp đỡ em trong suốt quá trình nghiên cứu và thực hiện luận văn.
Qua đây cho phép em được bày tỏ lời cảm ơn tới tất cả các thầy cô giáo
ở Viện Công nghệ thông tin và Trường Đại học Công nghệ Thông tin và Truyền
thông, đã giảng dạy và tạo mọi điều kiện thuận lợi giúp đỡ chúng em trong quá
trình học tập, nghiên cứu.
Cuối cùng, tôi xin cảm ơn đến gia đình, các bạn bè đồng nghiệp đã chia
sẻ động viên giúp đỡ tôi về chuyên môn cũng như về mọi mặt trong cuộc sống,
đó là nguồn động viên khích lệ giúp tôi có nghị lực hơn để hoàn thành khoá
học.
Học viên
Vũ Xuân Oanh
iii
MỤC LỤC
LỜI CAM ĐOAN .............................................................................................i
LỜI CẢM ƠN..................................................................................................ii
MỤC LỤC.......................................................................................................iii
TRONG LUẬN VĂN ...................................................................................... v
LỜI MỞ ĐẦU.................................................................................................. 1
MẢNH .............................................................................................................. 1
2.3. Đặc tính bảo toàn phụ thuộc ................................................................. 20
bảo toàn phụ thuộc.................................................................................. 23
iv
không mất thông tin ................................................................................ 27
Lạng Sơn ................................................................................................. 37
3.2.1. Thuật toán sử dụng........................................................................ 38
3.2.2. Dữ liệu đầu vào............................................................................. 38
3.3. Môi trường thử nghiệm......................................................................... 40
v
DANH MỤC CÁC BẢNG VÀ CÁC HÌNH
TRONG LUẬN VĂN
logic................................................................................................................. 59
Hình 1.1. Minh họa về một DDBS.................................................................... 7
Hình 3.5. Giao diện trang chủ......................................................................... 51
Hình 3.6.Giao diện nhập liệu .......................................................................... 51
Hình 3.7. Giao diện tìm khóa.......................................................................... 52
1
LỜI MỞ ĐẦU
Cơ sở dữ liệu (CSDL) phân tán là một lĩnh vực được nghiên cứu từ
lâu, nhưng gần đây do sự phát triển nhanh chóng của công nghệ truyền tin
và mạng interrnet, cùng với xu thế toàn cầu hoá trong mọi lĩnh vực, đặc biệt
trong lĩnh vực phân tán dữ liệu và thiết kế, CSDL phân tán đã trở thành một
lĩnh vực thu hút nhiều sự quan tâm của các nhà nghiên cứu trong lĩnh vực
CNTT.
Khái niệm phân tán (hoặc phân mảnh) ở đây được hiểu là phân tán thông
tin và các thông tin đó được chứa trên các máy tính ở các vị trí khác nhau của
một hệ thống máy tính có liên hệ với nhau được gọi là mạng máy tính. Việc
phân mảnh sẽ làm tăng mức độ hoạt động đồng thời (song song) và như thế làm
tăng lưu lượng hoạt động của hệ thống.
Việc phân mảnh được tiến thành theo 2 cách ngang và dọc. Trong đó
việc chia dọc một quan hệ thành các quan hệ con chứa một tập con các thuộc
tính của quan hệ gốc được gọi là phân mảnh dọc. Việc phân mảnh dọc có nhiều
đặc trưng (đặc tính) quan trọng đã và đang được tập trung nghiên cứu ở trong
cũng như ngoài nước cả về mặt lý luận cũng như ứng dụng thực tiễn. Đặc biệt
trong lĩnh vực thiết kế, cho phép các vấn tin ảnh hưởng đến các quan hệ nhỏ
hơn, vì thế giảm bớt truy xuất và tiết kiệm bộ nhớ.
Phân mảnh dọc được nghiên cứu trong ngữ cảnh của các hệ CSDL cả tập
trung và phân tán. Tuy CSDL phân tán được phát triển từ CSDL tập trung
nhưng nó vẫn có những ứng dụng gía trị để thiết kế CSDL tập trung.
Với mong muốn nắm vững hơn các tri thức phục vụ công tác nghiên cứu
chuyên môn cũng như áp dụng vào đời sống kinh tế -xã hội cùng với sự gợi ý
của Thầy hướng dẫn, tôi đã lựa chọn đề tài "Nghiên cứu các đặc tính của phân
2
mảnh dọc trong CSDL phân tán và ứng dụng" để làm luận văn tốt nghiệp
thạc sĩ. Luận văn này tập trung vào việc nghiên cứu các đặc trưng của phân
mảnh dọc và áp dụng để thiết kế CSDL quản lý thông tin cung đường tỉnh Lạng
Sơn, nơi tôi đang sống và công tác.
3
Chương 1. TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN VÀ
PHÂN MẢNH
1.1. Những nét chung nhất về cơ sở dữ liệu phân tán
Cơ sở dữ liệu (CSDL) phân tán là một tập hợp các dữ liệu phục thuộc
logic lẫn nhau của cùng một hệ thống và được lưu trữ trên các trạm của một
mạng máy tính. CSDL phân tán làm tăng khả năng truy nhập tới CSDL lớn
trên mạng. Trong hệ thống đó mỗi máy tính quản lý một CSDL thành phần
được gọi là 1 node hoặc site.
Hệ quản trị CSDL phân tán (DBMS) là phần mềm quản trị CSDL, đảm
bảo trong suốt đối với người sử dụng và cho phép tính tự trị nghĩa là mỗi cơ
sở dữ liệu thành phần vẫn được quản trị độc lập và riêng biệt [5].
Định nghĩa này nhấn mạnh 2 khía cạnh quan trọng của CSDL phân tán:
1- Tính phân tán: thực tế dữ liệu không cư trú ở cùng một trạm, vì vậy
chúngta có thể phân biệt một CSDL phân tán với CSDL tập trung.
2- Sự tương quan logic: Các dữ liệu có một số tính chất ràng buộc lẫn
nhauvà như vậy có thể phân biệt CSDL phân tán với tập các CSDL địa phương
hoặc với các tệp ở các trạm khác nhau trên mạng.
3 - Các đặc trưng trong suốt của CSDL phân tán thể hiện ở chỗ:
+Trong suốt phân tán: Cho phép xử lý dữ liệu trên hệ CSDL phân tán giống
như đối với CSDL tập trung. Người sử dụng (NSD) không cần biết dữ liệu đã
được phân mảnh như thế nào, các bản sao dữ liệu để ở đâu, vị trí vật lý lưu trữ
dữ liệu ở đâu. Trong suốt phân tán thể hiện:
+ Trong suốt địa điểm: NSD không cần biết lưu trữ vật lý của dữ liệu ở
đâu, mà có quyền truy cập đến CSDL tại bất cứ nút nào trên mạng. Trong truy
vấn chỉ cần chỉ ra tên dữ liệu mà không cần chỉ ra vị trí. Các thao tác để lấy
hoặc cập nhật một dữ liệu từ xa được tự động thực hiện bởi hệ thống tại địa
điểm đưa ra yêu cầu. Tính trong suốt về vị trí rất hữu ích, nó cho phép người
4
dùng bỏ qua các bản sao dữ liệu đã tồn tại ở mỗi vị trí. Do đó có thể di chuyển
một bản sao dữ liệu từ một nút này đến một nút khác và cho phép tạo các bản
sao mới mà không ảnh hưởng tới các ứng dụng;
+ Trong suốt tên: Khi một đối tượng đã được đặt tên thì có thể truy nhập
chính xác không cần đặc tả thêm;
+ Trong suốt bản sao: Sự nhân bản là quá trình sao chép và duy trì dữ liệu
trong hệ CSDL phân tán. Cùng một dữ liệu (được lưu trữ vật lý tại một vị trí)
có thể sử dụng được trên nhiều vị trí khác nhau. Các bản sao có thể được lưu
trữ trên nhiều nút làm tăng hiệu suất, độ tin cậy và tính sẵn sàng của hệ thống.
Các ứng dụng có thể truy nhập dữ liệu tại các nút mà không cần phải truy cập
từ xa giảm truyền tải trên mạng lớn. Hệ thống cho phép tiếp tục thực hiện nếu
như các nút từ xa có sự cố. Trong suốt bản sao bảo đảm NSD không biết đó là
các bản sao vì dữ liệu luôn được cập nhật và đồng bộ với dữ liệu gốc.
- Trong suốt phân mảnh: Một quan hệ trong CSDL phân tán có thể phân
mảnh ngang hoặc phân mảnh dọc nghĩa là được tách thành các bộ dữ liệu hoặc
các quan hệ con và lưu trữ trên nhiều nút khác nhau. Trong suốt phân mảnh cho
phép NSD không cần biết có sự phân mảnh, các truy vấn dữ liệu vẫn được viết
như CSDL tập trung.
- Trong suốt giao dịch: CSDL phân tán cho phép một giao dịch có thể cập
nhật, sửa đổi dữ liệu trên các nút khác nhau.
- Trong suốt thất bại: Đảm bảo tại một nút của hệ thống bị hỏng thì hệ
thống vẫn làm việc bình thường (do cơ chế tạo bản sao hoặc làm việc trên các
nút không bị sự cố).
- Trong suốt thao tác: Cho phép các câu lệnh thao tác các dữ liệu đơn giản
để truy nhập được các CSDL tại nút cục bộ hoặc nút từ xa. Các thao tác xử lý
dữ liệu từ xa không phức tạp và đảm bảo vẫn giống như khi thao tác dữ liệu
trên hệ CSDL không phân tán.
5
- Trong suốt về tính không thuần nhất: Cho phép hỗn hợp nhiều hệ quản trị
CSDL khác nhau với các khả năng trao đổi dữ liệu, xử lý cập nhật dữ liệu, xử
lý giao tác phân tán trên toàn hệ thống.
4- Đối với CSDL tập trung, tính dư thừa hạn chế được càng nhiều càng tốt.
Trong khi đó, CSDL phân tán có tính dư thừa dữ liệu vì:
- Tính cục bộ của chương trình ứng dụng sẽ tăng nếu dữ liệu đặt ở nhiều
nơi mà chương trình ứng dụng cần.
- Khả năng sẵn sàng của hệ thống cao bởi vì khi có lỗi ở một nơi nào đó
trong hệ thống thì không ảnh hưởng đến hoạt động của chương trình ứng
dụng.
5. Trong CSDL phân tán, dữ liệu được chia ra thành nhiều phần nhỏ và chỉ
có một bản sao logic tổng thể duy nhất để tiện cho việc truy xuất dữ liệu; cấu
trúc truy xuất phức tạp không phải là công cụ chính để truy xuất hiệu quả (hiệu
quả theo nghĩa là thời gian tìm kiếm và chuyển dữ liệu nhỏ nhất, chi phí truyền
thông thấp nhất). Mỗi cách thức truy xuất CSDL phân tán được người lập trình
viết hoặc tạo ra bởi một bộ tối ưu. Cách viết và truy cập CSDL phân tán cũng
giống như viết chương trình duyệt trong CSDL tập trung. Công việc mà chương
trình duyệt này làm là xác định xem có thể truy cập đến được bao nhiêu CSDL
con.
6. Trong CSDL phân tán, vấn đề điều khiển giao tác tự trị có ý nghĩa quan
trọng. Giao tác tự trị là phương tiện đạt được sự toàn vẹn trong CSDL; Mặt
khác, vấn đề an toàn CSDL cũng phức tạp hơn vì còn liên quan đến mạng truyền
thông.
CSDL phân tán có một số ưu và nhược điểm sau:
6
1. Ưu điểm:
Tính hữu dụng cơ bản nhất của CSDL phân tán là dữ liệu của các CSDL
vật lý riêng biệt được tích hợp logic với nhau giúp NSD trên mạng có thể truy
nhập được. Nó có khả năng:
- Cho phép quản lý dữ liệu với nhiều mức trong suốt. Hệ quản trị CSDL
phân tán cung cấp khả năng trong suốt phân tán với ý nghĩa che giấu đặc tính
phân tán với NSD.
- Tăng độ tin cậy và khả năng sẵn sàng. Đối với CSDL tập trung thì CSDL
được đặt tại một nút nên khi có sự cố sẽ khó khôi phục và khó xử lý, bị ngừng
khả năng làm việc khi gặp sự cố. Đối với CSDL phân tán thì độ tin cậy ở đây
là hệ thống đang làm việc (không bị ngừng) tại thời điểm nào đó, tính sẵn sàng
của hệ thống vẫn tiếp tục làm việc. Khi dữ liệu và CSDL phân tán trên một vài
nút, một nút có thể gặp sự cố trong khi các nút khác vẫn có thể hoạt động hoặc
sử dụng các thành phần khác của CSDL. Chỉ trên các nút bị sự cố, dữ liệu và
ứng dụng không thể truy cập được. Để nâng cao độ tin cậy và tính sẵn sàng, có
thể áp dụng cơ chế tạo bản sao trên nhiều nút.
- Cải thiện hiệu năng, do dữ liệu của CSDL phân tán được đặt gần nơi xử
lý nên hiệu năng được cải thiện đáng kể.
- Cho phép thêm CSDL mới, tăng kích cỡ CSDL, thêm bộ xử lý, thêm các
CSDL thành phần trong CSDL phân tán.
2. Nhược điểm:
- Độ phức tạp thiết kế và cài đặt hệ thống tăng: Hệ quản trị CSDL phân tán
phải bổ sung thêm các chức năng như:
+ Theo dõi dấu vết dữ liệu;
+ Xử lý các truy vấn phân tán;
+ Quản lý giao dịch phân tán;
+ Phục hồi CSDL phân tán;
7
+ Quản lý các bản sao;
+ Quản lý thư mục - catalog phân tán.
- Khó điều khiển tính nhất quán về dữ liệu;
- Các phần mềm hệ thống đảm bảo quản trị, duy trì kết nối, trao đổi dữ liệu
trên mạng là rất khó khăn;.
- Bảo mật khó khăn.
Ở mức vật lý, những đặc trưng phân tán được thể hiện rõ:
- Có nhiều máy tính được gọi là các nút/trạm;
- Các nút này phải được kết nối bởi một kiểu mạng truyền thông để truyền
dữ liệu và những câu lệnh giữa các nút với nhau. Mỗi nút có thể truy nhập dữ
liệu ở các nút khác.
Khác với mô hình dữ liệu tập trung (tài nguyên tập trung tại một máy tính),
CSDL trong hệ thống CSDL phân tán được chứa trong nhiều máy tính (nút),
các máy tính này được nối với nhau qua các hệ thống truyền thông và chúng
không chia sẻ bộ nhớ chung cũng như không dùng chung đồng hồ. Các bộ xử
lý trong hệ thống phân tán có kích cỡ và chức năng khác nhau (chẳng hạn có
thể bao gồm các bộ vi xử lý, trạm làm việc, máy tính mini, hay các máy lớn
vạn năng).
Workstation 1
Workstation 2
Workstation 5
Mạng truyền số liệu
CSDL
CSDL
Workstation 4
Workstation 3
CSDL
CSDL
Hình 1.1. Minh họa về một DDBS
8
Chú ý rằng, nếu CSDL nằm tại một nút mạng thì hệ thống đó không phải
là DDBS:
Workstation 1
Workstation 2
Workstation 5
Workstation 4
Mạng truyền
dữ liệu
Workstation 3
Hình 1.2. CSDL tập trung, không phải là DDBS
1.2. Vấn đề phân mảnh trong cơ sở dữ liệu phân tán
Trong quá trình thiết kế, các quan hệ được phân mảnh thành các quan hệ
nhỏ hơn. Các câu hỏi có tương hỗ lẫn nhau được quan tâm gồm:
1. Tại sao lại cần phân mảnh?
2. Chúng ta nên phân mảnh như thế nào?
3. Chúng ta nên phân thành bao nhiêu mảnh?
4. Có cách nào để kiểm tra tính chính xác của sự phân mảnh?
5. Chúng ta nên cấp phát các mảnh như thế nào cho các nút?
6. Thông tin cần thiết cho phân mảnh và cấp phát là gì?
1.2.1. Lý do phân mảnh
Theo quan điểm phân tán dữ liệu, không phân mảnh giá trị dữ liệu. Trong
các hệ thống tệp phân tán, việc phân tán được thực hiện trên cơ sở toàn bộ các
tập tin.
Đối với phân mảnh, vấn đề quan trọng là đơn vị phân tán thích hợp. Một
quan hệ không phải là một đơn vị phù hợp. Vì sao vậy?. Lý do thứ nhất, việc
truy cập các ứng dụng tại các nút được xác định không phải trên toàn bộ quan
hệ mà chỉ trên các tập con của chúng. Lý do thứ hai, nếu các ứng dụng có các
9
khung nhìn đã xác định trên một quan hệ nhất định ở các nút khác nhau thì việc
phân mảnh giúp ích cho việc không phải truy cập dữ liệu từ xa, không gây ra
các rắc rối trong cập nhật và không gặp vấn đề giới hạn lưu trữ của kho. Lý do
cuối cùng, sự phân mảnh kéo theo khả năng truy vấn song song, do đó làm tăng
mức độ xử lý đồng thời.
Tuy vậy, việc phân mảnh cũng gây ra nhiều khó khăn. Nếu các ứng dụng
có các yêu cầu mâu thuẫn ngăn cản việc tách quan hệ thành các quan hệ con
riêng biệt, các ứng dụng mà quan điểm được xác định trên nhiều hơn một quan
hệ con có thể bị giảm hiệu suất. Chẳng hạn, việc lấy dữ liệu từ hai mảnh và kết
nối chúng là rất phức tạp. Cực tiểu hoá các liên kết đã phân tán là một bài toán
cơ bản về phân mảnh.
Vấn đề thứ hai liên quan đến kiểm soát ngữ nghĩa dữ liệu, đặc biệt là để
kiểm tra tính toàn vẹn. Do phân mảnh, các thuộc tính có thể bị phân bổ trong
các quan hệ con khác nhau tại các nút khác nhau.
1.2.2. Giải pháp phân mảnh
Mô hình quan hệ được biểu diễn ở dạng bảng, vì vậy vấn đề là tìm ra những
cách chia một bảng thành các bảng nhỏ hơn. Rõ ràng có hai lựa chọn: chia nó
theo chiều ngang (horizontal) hoặc theo chiều dọc (vertical).
1.2.3. Mức độ phân mảnh
Quyết định mức độ phân mảnh CSDL là một quyết định quan trọng ảnh
hưởng đến việc thực hiện truy vấn. Trên thực tế, các vấn đề liên quan đến lý
do phân mảnh là một tập con của các câu trả lời cho câu hỏi chúng ta đang
giải quyết ở đây. Mức độ phân mảnh đi từ một cực, nghĩa là không phân
mảnh, sang cực khác, để phân mảnh đến mức từng bộ (trong trường hợp phân
mảnh ngang) hoặc với mức mỗi thuộc tính (trong trường hợp phân mảnh
dọc).
10
Tất nhiên, sự phân mảnh có thể được lồng nhau. Nếu tổ hợp theo nhiều
kiểu, người ta sẽ nhận cách phân mảnh hỗn hợp. Mặc dù chúng ta không coi
phân mảnh hỗn hợp là một chiến lược phân mảnh nguyên thủy, nhiều phân
vùng thực tế có thể là hỗn hợp.
Chúng ta đã biết về các bất lợi của các đơn vị phân mảnh rất lớn và rất nhỏ.
Điều mà chúng ta cần là tìm ra mức độ phân mảnh phù hợp là sự thỏa hiệp giữa
hai thái cực. Mức độ như vậy chỉ có thể được xác định đối với các ứng dụng sẽ
hoạt động trên CSDL. Vấn đề là làm thế nào? Nói chung, các ứng dụng cần
phải được đặc trưng với một số tham số. Các mảnh riêng lẻ có thể được xác
định theo các giá trị của các tham số này. Trong phần sau chúng ta sẽ mô tả các
đặc tính này có thể được thực hiện như thế nào cho các kiểu phân mảnh đã lựa
chọn
1.2.4. Các quy tắc phân mảnh
Chúng ta sẽ thực thi ba quy tắc đồng thời sau trong quá trình phân mảnh để
bảo đảm rằng CSDL không bị thay đổi ngữ nghĩa trong quá trình phân mảnh
[5].
1. Tính đầy đủ (completeness). Nếu một quan hệ R bị phân mảnh thành n
quan hệ con FR = {R1, R2,. . . , Rn}, mỗi thuộc tính trong R cũng có thể được
tìm thấy trong một hoặc nhiều hơn các Ri. Đặc tính này bảo đảm rằng các dữ
liệu trong một quan hệ toàn cục được ánh xạ thành các quan hệ con mà không
bị tổn thất. Lưu ý rằng trong trường hợp phân mảnh ngang, người ta thường
nhắm đến một “bộ”, trong khi trong trường hợp phân mảnh theo chiều dọc,
nhắm đến một “thuộc tính”.
2. Tính tái thiết (reconstruction). Nếu một quan hệ R được phân mảnh
thành n mảnh FR = {R1, R2, . . . , Rn}, thì có thể xác định một toán tử quan hệ
sao cho: R =Ri, Ri FR
11
Toán tử sẽ khác nhau cho các dạng phân mảnh khác nhau (ngang hay
dọc); Tuy nhiên, điều quan trọng là nó có thể xác định được. Khả năng tái cấu
trúc lại quan hệ từ các mảnh của nó bảo đảm rằng các ràng buộc xác định trên
dữ liệu sẽ được duy trì.
3. Tính tách rời (disjointness). Nếu một quan hệ R được phân mảnh theo
chiều ngang thành n mảnh FR = {R1, R2,..., Rn} và bộ dữ liệu (bản ghi) tj nằm
trong Rj thì nó không nằm trong bất kỳ quan hệ con Rk khác (k ≠ j) để bảo đảm
các mảnh ngang là rời nhau. Nếu quan hệ R được phân mảnh theo chiều dọc,
thì các khóa chính của nó phải lặp lại trong tất cả các mảnh của nó (để tái thiết).
Do đó, trong trường hợp phân mảnh dọc, sự tách rời chỉ được xác định trên các
thuộc tính không phải là khóa chính của quan hệ.
1.2.5. Các chiến lược phân mảnh
Có hai chiến lược phân mảnh cơ bản: ngang và dọc. Từ đó, có thể mở rộng
thành chiến lược tích hợp phân mảnh kiểu lai ghép (hybrid) [5].
1. Phân mảnh ngang
Phân mảnh ngang phân rã một quan hệ bằng cách cắt khúc quan hệ đó. Do
đó mỗi khúc có một tập con giá trị của các bộ trong quan hệ. Như vậy, phân
mảnh ngang chính là việc chia quan hệ thành nhiều nhóm bộ. Kết quả của quá
trình phân mảnh ngang là các quan hệ con, số lượng quan hệ con phụ thuộc vào
điều kiện ràng buộc của các thuộc tính. Và các bộ trong các quan hệ con là tách
biệt nhau. Phân mảnh ngang thực chất là phép chọn quan hệ thỏa mãn một biểu
thức điều kiện cho trước.
Có hai kỹ thuật phân mảnh ngang: nguyên thủy (primary) và dẫn xuất
(derived). Phân mảnh ngang nguyên thủy của một quan hệ được thực hiện bằng
cách sử dụng các vị từ (predicate) được định nghĩa trên chính quan hệ đó. Còn
phân mảnh ngang dẫn xuất là sự phân rã quan hệ nhờ các vị từ được định nghĩa
trên quan hệ khác.
12
2. Phân mảnh dọc
Phân mảnh dọc (Vertical Fragmentation) một quan hệ R là việc phân mảnh
để tạo ra các mảnh con R1, R2,..., Rrmà mỗi mảnh con chứa một tập con các
thuộc tính của R cùng với khóa chính của R. Mục tiêu của phân mảnh dọc là
chia một quan hệ thành một tập các quan hệ nhỏhơn để nhiều ứng dụng có thể
thực hiện trên một mảnh. Như vậy, phân mảnh "tối ưu" là sinh ra một lược đồ
phân mảnh để giảm thiểu thời gian thực hiện của các ứng dụng chạy trên các
mảnh này.
Phân mảnh dọc cho phép các truy vấn với quan hệ nhỏ hơn, do đó dẫn đến
một số lượng nhỏ các truy cập đến nút.
13
Chương 2. CÁC ĐẶC TÍNH CỦA PHÂN MẢNH DỌC
2.1. Định hướng heuristic để phân mảnh dọc
Một phân mảnh dọc cho một quan hệ r (có R thuộc tính) sinh ra các mảnh
r1,r2,...rk, mỗi mảnh chứa một tập con thuộc tính của R và cả khóa của r. Mục
đích của phân mảnh dọc là phân hoạch một quan hệ thành tập các quan hệ nhỏ
hơn để nhiều ứng dụng có thể chỉ chạy trên 1 quan hệ. Trong ngữ cảnh này,
một phân mảnh “tối ưu” là một phân mảnh sinh ra một lược đồ phân mảnh cho
phép giảm tối đa thời gian thực thi các ứng dụng chạy trên các mảnh đó.
Phân mảnh dọc đã được nghiên cứu trong ngữ cảnh của các hệ CSDL tập
trung lẫn phân tán. Lý do chính trong ngữ cảnh tập trung là sử dụng nó làm một
công cụ thiết kế, cho phép các vấn tin ảnh hưởng đến các quan hệ nhỏ hơn, vì
thế giảm bớt số truy xuất và tiết kiệm bộ nhớ. Phân mảnh dọc tất nhiên phức
tạp hơn so với phân mảnh ngang vì do tổng số chọn lựa có thể có của phân
hoạch dọc rất lớn.
Để có được các lời giải tối ưu cho bài toán phân mảnh dọc thực sự rất khó
nên người ta đã đưa ra 2 loại heuristic cho phân mảnh dọc một quan hệ[8]:
1.Nhóm thuộc tính: bắt đầu bằng cách gán mỗi thuộc tính cho một mảnh,
và tại mỗi bước, nối một số mảnh lại cho đến khi thỏa mãn một tiêu chuẩn nào
đó. Kỹ thuật nhóm thuộc tính được Hammer and Niamir đề xuất lần đầu năm
1979 cho các CSDL tập trung và về sau được Sacca và Wiederhold dùng năm
1985 cho các CSDL phân tán.
2.Tách mảnh: bắt đầu bằng một quan hệ và quyết định cách phân mảnh
có lợi dựa trên hành vi truy xuất của các ứng dụng trên các thuộc tính. kỹ thuật
này được Hoffer and Severance thảo luận lần đầu tiên cho thiết kế CSDL tập
trung năm1975, sau đó được Navathe và các đồng tác giả mở rộng cho môi
trường phân tán năm 1984.
Tải về để xem bản đầy đủ
71 trang
11800
Free
Bạn đang xem 20 trang mẫu của tài liệu "Luận văn Nghiên cứu các đặc tính của phân mảnh dọc trong cơ sở dữ liệu phân tán và ứng dụng", để 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:
- luan_van_nghien_cuu_cac_dac_tinh_cua_phan_manh_doc_trong_co.pdf
