Tối ưu hóa cơ sở dữ liệu phân tán 04
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.26 MB, 88 trang )
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN THỊ THƠ MÂY
TỐI ƯU HÓA CƠ SỞ DỮ LIỆU PHÂN TÁN
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
HÀ NỘI – 2015
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN THỊ THƠ MÂY
TỐI ƯU HÓA CƠ SỞ DỮ LIỆU PHÂN TÁN
Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60480104
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. ĐOÀN VĂN BAN
HÀ NỘI – 2015
LỜI CAM ĐOAN
Tôi xin cam đoan, kết quả của luận văn hoàn toàn là kết quả của tự bản thân tôi
tìm hiểu, nghiên cứu. Các tài liệu tham khảo được trích dẫn và chú thích đầy đủ.
Tác giả
Nguyễn Thị Thơ Mây
LỜI CẢM ƠN
Lời đầu tiên, em xin chân thành cảm ơn PGS.TS Đoàn Văn Ban, người đã trực
tiếp hướng dẫn, giúp đỡ và tạo mọi điều kiện thuận lợi cho em từ lúc tìm hiểu, định
hướng cũng như tìm kiếm tài liệu trong lĩnh vực cơ sở dữ liệu phân tán cho đến lúc hoàn
thành luận văn.
Em xin gửi lời cám ơn sâu sắc đến tất cả các thầy cô giáo đã dạy dỗ và truyền đạt
những kiến thức, kinh nghiệm quý báu cho chúng em trong suốt hai năm cao học ở
trường Đại học Công nghệ - Đại học Quốc gia Hà nội.
Cuối cùng, em xin cảm ơn tất cả bạn bè, người thân và đồng nghiệp đã khích lệ,
động viên, đóng góp ý kiến và giúp đỡ để em hoàn thành luận văn này.
Hà nội, ngày ….., tháng ….., năm 2015
1
MỤC LỤC
MỤC LỤC...................................................................................................................
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ...............................................
DANH MỤC CÁC HÌNH VẼ .....................................................................................
LỜI MỞ ĐẦU .............................................................................................................
Chương 1: KHÁI QUÁT VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN .....................................
1.1.
Cơ sở dữ liệu phân tán. ..................................................................................
1.1.1. Định nghĩa ............................................................................................
1.1.2. Ưu điểm ...............................................................................................
1.1.3. Nhược điểm ..........................................................................................
1.2.
Đặc điểm của cơ sở dữ liệu phân tán .............................................................
1.2.1. Chia sẻ tài nguyên ................................................................................
1.2.2. Tính mở ................................................................................................
1.2.3. Khả năng song song..............................................................................
1.2.4. Khả năng mở rộng ................................................................................
1.2.5. Khả năng thứ lỗi ...................................................................................
1.2.6. Tính trong suốt .....................................................................................
1.2.7. Đảm bảo tin cậy và nhất quán ..............................................................
1.3.
Kiến trúc cơ bản của CSDL phân tán .............................................................
1.4.
Hệ quản trị cơ sở dữ liệu phân tán .................................................................
1.4.1. Khái niệm .............................................................................................
1.4.2. Kiến trúc hệ quản trị CSDL phân tán ...................................................
1.5.
Thiết kế cơ sở dữ liệu phân tán ......................................................................
1.5.1. Các chiến lược phân tán dữ liệu ...........................................................
1.5.2. Phân mảnh dữ liệu ................................................................................
1.5.2.1. Phương pháp phân mảnh ngang ........................................................
1.5.2.2. Phương pháp phân mảnh dọc ............................................................
1.5.2.3. Phương pháp phân mảnh hỗn hợp. ....................................................
1.6.
Kết luận ..........................................................................................................
Chương 2: TỐI ƯU HÓA TRUY VẤN CƠ SỞ DỮ LIỆU PHÂN TÁN ...................
2.1.
Vấn đề tối ưu hóa xử lý truy vấn ...................................................................
2.2.
Quá trình xử lý truy vấn .................................................................................
2.2.1. Phân rã truy vấn ...................................................................................
2.2.2. Cục bộ hóa dữ liệu phân tán ................................................................
2
2.2.2.1. Rút gọn cho phân mảnh ngang nguyên thủy .....................................
2.2.2.2. Rút gọn cho phân mảnh dọc. .............................................................
2.2.2.3. Rút gọn cho phân mảnh ngang dẫn xuất ...........................................
2.2.2.4. Rút gọn cho phân mảnh hỗn hợp ......................................................
2.2.3. Tối ưu hóa toàn cục ..............................................................................
2.2.3.1. Không gian tìm kiếm .......................................................................
2.2.3.2. Chiến lược tìm kiếm .........................................................................
2.2.3.3. Mô hình chi phí ................................................................................
2.2.4. Tối ưu hóa cục bộ .................................................................................
2.3.
Các thuật toán tối ưu hóa truy vấn phân tán ..................................................
2.3.1. Thứ tự kết nối .......................................................................................
2.3.2. Thuật toán INGRES phân tán ..............................................................
2.3.3. Thuật toán R* .......................................................................................
2.3.4. Thuật toán DP-ACO .............................................................................
2.4.
Kết luận ..........................................................................................................
Chương 3: CHƯƠNG TRÌNH CÀI ĐẶT THUẬT TOÁN TỐI ƯU HÓA TRUY
VẤN..........................................................................................................................
3.1.
Bài toán quản lý bệnh nhân ............................................................................
3.2.
Mô hình phân tán CSDL, công cụ, ngôn ngữ lập trình ..................................
3.3.
Thuật toán áp dụng .........................................................................................
3.4.
Kết quả thực nghiệm ......................................................................................
3.5.
Kết luận ..........................................................................................................
KẾT LUẬN...............................................................................................................
TÀI LIỆU THAM KHẢO .........................................................................................
3
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
STT
1
2
3
4
5
6
7
8
9
Ký hiệu
ACO
(Ant Colony Optimization)
CSDL
CPU
(Central Processing Unit )
DBMS
(Database Management System)
DDBMS
(Distributed Database Management
System)
DP
(Dynamic Programming)
I/O
(Input/Output)
PT
(Processing tree)
SSL
(Search Space Limit)
4
DANH MỤC CÁC HÌNH VẼ
Hình 1.1 Môi trường hệ CSDL phân tán .........................................................
Hình 1.2 Kiến trúc cơ bản của CSDL phân tán.....................................................
Hình 1.3: Mối quan hệ giữa các quan hệ bởi các đường nối ..................................
Hình 1.4: Ma trận tụ tương quan CA .....................................................................
Hình 1.5: Phân đoạn hỗn hợp ................................................................................
Hình 1.6. Tái xây dựng phân đoạn hỗn hợp ..........................................................
Hình 2.1: Giải pháp A..............................................................................................
Hình 2.2: Giải pháp B ...........................................................................................
Hình 2.3: Sơ đồ truy trình xử lý truy vấn ..............................................................
Hình 2.4: Đồ thị truy vấn và Đồ thị nối .................................................................
Hình 2.5: Đồ thị truy vấn và Đồ thị nối với câu truy vấn sai ngữ nghĩa .................
Hình 2.6: Cây đại số quan hệ ................................................................................
Hình 2.7: Cây đại số quan hệ sau khi tái cấu trúc .................................................
Hình 2.8: Câu truy vấn gốc ...................................................................................
Hình 2.9: Câu truy vấn đã rút gọn ........................................................................
Hình 2.10: Rút gọn phân mảnh ngang ..................................................................
Hình 2.11. Rút gọn phân mảnh dọc ......................................................................
Hình 2.12: Rút gọn cho phân mảnh ngang dẫn xuất .............................................
Hình 2.13: Rút gọn phân mảnh hỗn hợp ................................................................
Hình 2.14: Bộ tối ưu truy vấn ...............................................................................
Hình 2.15: Các cây nối .........................................................................................
Hình 2.16: Hình dáng của một số cây nối .............................................................
Hình 2.17: Đồ thị minh họa tổng chi phí và thời gian trả lời ..........................
Hình 2.18:Truyền các toán hạng trong phép toán hai ngôi.............................
Hình 2.19: Đồ thị nối của truy vấn phân tán ..........................................................
Hình 2.20: Đồ thị nối của truy vấn q1 ...................................................................
Hình 2.21: Các thứ tự kết nối ................................................................................
Hình 2.22: Quá trình quyết định đường đi của đàn kiến ........................................
Hình 3.1: Mối quan hệ giữa các bảng dữ liệu ........................................................
Hình 3.2: Kết quả thực hiện câu truy vấn tại trạm 1 ..............................................
Hình 3.3: Kết quả thực hiện câu truy vấn tại trạm 2 ..............................................
Hình 3.4: Kết quả thực hiện câu truy vấn tại trạm 3 ..............................................
Hình 3.5: Kết quả thực hiện câu truy vấn tại trạm 1 ..............................................
Hình 3.6: Kết quả thực hiện câu truy vấn tại trạm 2 ..............................................
5
LỜI MỞ ĐẦU
Ngày nay, cùng với sự phát triển nhanh chóng của công nghệ thông tin, các ứng
dụng cơ sở dữ liệu đã thâm nhập vào mọi hoạt động kinh tế xã hội, quản lý nhà nước và
đem lại hiệu quả vô cùng to lớn, góp phần tăng năng suất lao động, đơn giản trong quản
lý và cải cách nền hành chính. Xã hội ngày càng phát triển, yêu cầu khối lượng thông tin
cần lưu trữ, xử lý ngày càng tăng. Trên thực tế, các doanh nghiệp, các đơn vị, cơ quan,
tổ chức phân bố trên một vùng rộng lớn về mặt địa lý, có thể là trên phạm vi nhiều thành
phố hoặc toàn bộ quốc gia hay một vài quốc gia, thậm chí trên toàn cầu. Do đó, 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ý, tốc độ truy xuất dữ liệu phục vụ cho xử lý công việc
không bị ảnh hưởng, không bị gián đoạn được đặt ra. Cơ sở dữ liệu phân tán ra đời đã
giải quyết được những yêu cầu đó.
Cơ sở dữ liệu là một trong những lĩnh vực được quan tâm nhiều trong công nghệ
thông tin. Việc nghiên cứu CSDL đã và đang phát triển ngày càng phong phú, đa dạng.
Cho đến nay, đã có hàng loạt các vấn đề về CSDL được nghiên cứu, giải quyết. CSDL
phân tán nói riêng và các hệ phân tán nói chung là một lĩnh vực nghiên cứu không mới,
nhưng gần đây cùng với sự phát triển nhanh chóng và mạnh mẽ của công nghệ truyền
thông, mạng Internet và đặc biệt là xu thế phát triển của thương mại điện tử, thì 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
cũng như các nhà sản xuất phần mềm.
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à 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 hóa các câu lệnh khi truy vấn dữ liệu. Nghiên cứu
về tối ưu hóa truy vấn trong cơ sở dữ liệu phân tán là cần thiết để khai thác có hiệu quả
dữ liệu phân tán. Do đó, tôi chọn nghiên cứu đề tài “Tối ưu hóa cơ sở dữ liệu phân tán”
làm luận văn tốt nghiệp.
Mục tiêu của luận văn là nghiên cứu các phương pháp thiết kế cơ sở dữ liệu phân
tán, các kỹ thuật tối ưu hóa câu truy vấn trong cơ sở dữ liệu phân tán, cài đặt thử nghiệm
một số thuật toán tối ưu hóa câu truy vấn trong cơ sở dữ liệu phân tán, từ đó đưa ra nhận
xét, đánh giá ưu điểm, nhược điểm của từng thuật toán tối ưu để có lựa chọn phù hợp
với từng bài toán thực tế.
Với mục tiêu của luận văn như vậy, bố cục của luận văn gồm: phần mở đầu, ba
chương nội dung và phần kết luận.
Chương 1: Khái quát về cơ sở dữ liệu phân tán. Giới thiệu tổng quan về cơ sở dữ
liệu phân tán, phân biệt cơ sở dữ liệu tập trung với cơ sở dữ liệu phân tán để thấy được
sự khác biệt của hai cơ sở dữ liệu này và lợi ích của cơ sở dữ liệu phân tán; Tìm hiểu
các phương pháp thiết kế cơ sở dữ liệu phân tán, tập trung nghiên cứu các kỹ thuật phân
mảnh: phân mảnh ngang, phân mảnh dọc và phân mảnh hỗn hợp.
6
Chương 2: Tối ưu hóa truy vấn cơ sở dữ liệu phân tán. Trong chương này sẽ trình
bày chi tiết các bước trong quy trình xử lý câu truy vấn; trình bày các thuật toán tối ưu
hóa câu truy vấn cơ sở dữ liệu phân tán như: INGRES phân tán, R*, DP-ACO.
Chương 3: Cài đặt thử nghiệm thuật toán: Trình bày mô hình cài đặt hệ thống. Cài
đặt thuật toán INGRES phân tán, R* và so sánh, đánh giá kết quả thực nghiệm cho bài
toán tối ưu hóa truy vấn. Cuối cùng là kết luận và hướng phát triển của đề tài.
Nội dung cơ bản của luận văn đã được trình bày, thảo luận tại seminar khoa học
ở Bộ môn Hệ thống thông tin, khoa Công nghệ Thông tin, trường Đại học Công nghệ Đại học Quốc gia Hà Nội.
7
Chương 1
KHÁI QUÁT VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN
1.1. Cơ sở dữ liệu phân tán
1.1.1. Định nghĩa
Một cơ sở dữ liệu (CSDL) phân tán là một tập dữ liệu có quan hệ logic với nhau,
được phân bố trên các máy tính của một mạng máy tính [11].
-
Tính chất phân tán: Toàn bộ dữ liệu của CSDL phân tán không nằm ở một nơi
mà nằm trên nhiều trạm thuộc mạng máy tính.
Quan hệ logic: Trong CSDL phân tán, dữ liệu có một số đặc tính liên kết với
nhau như tính kết nối, mối quan hệ logic, đ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 nằm tại các vị trí khác nhau
trong một mạng máy tính.
Trong hệ thống cơ sở dữ liệu phân tán gồm nhiều trạm, mỗi trạm có thể khai thác
các giao tác truy nhập dữ liệu trên nhiều trạm khác.
Ví dụ: Với một ngân hàng có 3 chi nhánh đặt ở các vị trí khác nhau. Tại mỗi chi
nhánh có một máy tính điều khiển một số máy kế toán cuối cùng (Teller terminal). Mỗi
máy tính với cơ sở dữ liệu thống kê cục bộ của nó tại mỗi chi nhánh được đặt ở một vị
trí của cơ sở dữ liệu phân tán. Các máy tính được nối với nhau bởi một mạng truyền
thông.
Ở mức phần cứng vật lý, những nhân tố chính sau là để phân biệt một hệ cơ sở dữ
liệu phân tán với hệ cơ sở dữ liệu tập trung:
Có nhiều máy tính được gọi là các trạm hay các nút.
Các trạm 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 trạm với nhau, như Hình 1.1.
Trong mô hình dữ liệu tập trung, tài nguyên tập trung tại một máy tính. Trong hệ
thống cơ sở dữ liệu phân tán, cơ sở dữ liệu được chứa trong nhiều máy tính, các máy
tính này được nối với nhau qua các hệ thống truyền thông, 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). Trong hệ thống cơ sở dữ liệu phân tán
gồm nhiều trạm thì mỗi trạm có thể truy nhập dữ liệu ở các trạm khác.
DB
DB
Mạng truyền thông
8
DB
Trạm 1
DB
Trạm 4
Hình 1.1 Môi trường hệ CSDL phân tán
1.1.2. Ưu điểm
Lợi ích cơ bản nhất của cơ sở dữ liệu phân tán là dữ liệu của các cơ sở dữ liệu vật
lý riêng biệt được tích hợp logic với nhau làm cho nhiều người sử dụng trên mạng có
thể truy nhập được.
Cho phép quản lý dữ liệu theo nhiều mức trong suốt: Hệ quản trị cơ sở dữ liệu
phải được trong suốt phân tán theo nghĩa làm cho người sử dụng không cần biết vị trí
của dữ liệu và không cần biết sự phức tạp truy cập qua mạng.
Tăng độ tin cậy và khả năng sẵn sàng: Độ tin cậy là khả năng hệ thống đang làm
việc (không bị ngừng) tại một thời điểm nào đó, tính sẵn sàng là khả năng hệ thống tiếp
tục làm việc trong một khoảng thời gian nào đó. Khi cơ sở dữ liệu phân tán trên một vài
trạm, một trạm có thể có sự cố trong khi các trạm khác vẫn có thể hoạt động hoặc sử
dụng các thành phần khác của cơ sở dữ liệu, chỉ trên trạm 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 trạm [2].
Cải thiện hiệu năng: Một hệ quản trị cơ sở dữ liệu phân tán, phân mảnh cơ sở dữ
liệu có thể làm cho dữ liệu được lưu trữ tại gần nơi sử dụng nhất. Dữ liệu được lưu trữ
cục bộ làm giảm cạnh tranh CPU, giảm các phục vụ I/O và giảm tương tranh truy nhập
trên mạng. Dữ liệu được phân tán tại các trạm nên dung lượng dữ liệu cục bộ sẽ nhỏ
hơn, các xử lý giao tác và truy vấn cục bộ sẽ được thực hiện tốt hơn. Hơn nữa, trên mỗi
trạm có ít các giao tác hơn số giao tác trên cơ sở dữ liệu tập trung, vì vậy cũng tăng hiệu
suất hệ thống. Tính song song trong các hệ CSDL phân tán có thể nâng cao được hiệu
quả truy nhập. Tính chất này có thể lợi dụng để xử lý song song các câu truy vấn. Có hai
dạng:
Câu truy vấn đồng thời phát sinh tại các trạm khác nhau.
Câu truy vấn có thể được phân rã thành những câu truy vấn con được thực hiện
song song trên các trạm khác nhau.
Tổ chức dữ liệu phân tán kinh tế hơn so với tổ chức dữ liệu tập trung. Chi phí cho
một hệ máy tính nhỏ rẻ hơn nhiều so với chi phí của một máy tính lớn khi triển
9
khai cùng một mục đích ứng dụng. Chi phí truyền thông cũng ít hơn do việc cục bộ hóa
dữ liệu.
Dễ dàng mở rộng: Việc thêm cơ sở dữ liệu mới, tăng kích cỡ cơ sở dữ liệu hoặc
thêm bộ xử lý trong môi trường phân tán là dễ hơn vì cũng chỉ như là thêm các cơ sở dữ
liệu thành phần.
1.1.3. Nhược điểm
Bên cạnh những ưu điểm đã trình bày phần trên, CSDL phân tán có một số nhược
điểm sau:
Độ phức tạp thiết kế và cài đặt hệ thống tăng: Hệ quản trị cơ sở dữ liệu 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 cơ sở dữ liệu phân tán
+ Quản lý các bản sao
+ Quản lý thư mục - catalog phân tán
Tăng chi phí: Độ phức tạp tăng đồng nghĩa với chi phí cho việc mua sắm và bảo
trì cho hệ quản trị CSDL phân tán tăng so với CSDL tập trung. Hơn nữa, hệ quản trị
CSDL phân tán còn yêu cầu thêm phần cứng để thiết lập mạng liên kết giữa các trạm
làm cho chi phí truyền thông liên tục phát sinh. Ngoài ra, còn có thêm chi phí lao động
để quản lý và duy trì các CSDL cục bộ và hệ thống mạng.
Bảo mật khó khăn: Trong hệ thống tập trung, việc truy cập dữ liệu có thể được
kiểm soát dễ dàng. Tuy nhiên, trong hệ quản trị CSDL phân tán không chỉ việc truy cập
dữ liệu lặp ở nhiều vị trí được kiểm soát mà bản thân mạng cũng phải đảm bảo an toàn.
Kiểm soát tính toàn vẹn khó khăn hơn: CSDL toàn vẹn đề cập đến độ tin cậy và
tính nhất quán của dữ liệu được lưu trữ. Tính toàn vẹn thường được thể hiện trong các
điều kiện ràng buộc. Thực hiện các ràng buộc này thường yêu cầu truy cập lượng lớn
dữ liệu định nghĩa các ràng buộc. Trong hệ quản trị CSDL phân tán, chi phí truyền
thông và chi phí xử lý để thực thi các ràng buộc toàn vẹn cao hơn trong hệ thống tập
trung.
1.2. Đặc điểm của cơ sở dữ liệu phân tán
1.2.1. Chia sẻ tài nguyên
Việc chia sẻ tài nguyên của hệ phân tán được thực hiện thông qua mạng truyền
thông. Để chia sẻ tài nguyên một cách có hiệu quả thì mỗi tài nguyên cần được quản lý
bởi một chương trình có giao diện truyền thông, các tài nguyên có thể được truy cập,
cập nhật một cách tin cậy và nhất quán. Quản lý tài nguyên ở đây là lập kế hoạch dự
phòng, đặt tên cho các lớp tài nguyên, cho phép tài nguyên được truy cập từ nơi này đến
nơi khác, ánh xạ lên tài nguyên vào địa chỉ truyền thông, ...
10
1.2.2. Tính mở
Tính mở của hệ thống máy tính là dễ dàng mở rộng phần cứng (thêm các thiết bị
ngoại vi, bộ nhớ, các giao diện truyền thông, ...) và các phần mềm (các mô hình hệ điều
hành, các giao thức truyền tin, các dịch vụ chung tài nguyên, ...)
Một hệ phân tán có tính mở là hệ có thể được tạo ra từ nhiều loại phần cứng và
phần mềm của nhiều nhà cung cấp khác nhau theo một tiêu chuẩn chung.
Tính mở của hệ phân tán được xem xét theo mức độ bổ sung các dịch vụ dùng
chung tài nguyên mà không phá hỏng hay nhân đôi các dịch vụ đang tồn tại. Tính mở
được hoàn thiện bằng cách xác định hay phân định rõ các giao diện chính của một hệ và
làm cho nó tương thích với các nhà phát triển phần mềm.
Tính mở của hệ phân tán dựa trên việc cung cấp cơ chế truyền thông giữa các tiến
trình và công khai các giao diện dùng để truy cập các tài nguyên chung.
1.2.3. Khả năng song song
Hệ phân tán hoạt động trên một mạng truyền thông có nhiều máy tính, mỗi máy có
thể có một hay nhiều CPU. Trong cùng một thời điểm nếu có N tiến trình cùng tồn tại, ta
nói chúng thực hiện đồng thời. Việc thực hiện tiến trình theo cơ chế phân chia thời gian
(một CPU) hay song song (nhiều CPU).
Khả năng làm việc song song trong hệ phân tán được thực hiện do:
Nhiều người sử dụng đồng thời đưa ra các lệnh hay tương tác với các chương
trình ứng dụng.
Nhiều tiến trình Server chạy đồng thời, mỗi tiến trình đáp ứng các yêu cầu từ các
tiến trình Client khác.
1.2.4. Khả năng mở rộng
Hệ phân tán có khả năng hoạt động tốt và hiệu quả ở nhiều mức khác nhau. Một hệ
phân tán nhỏ nhất có thể hoạt động chỉ cần hai trạm làm việc và một File Server. Các hệ
lớn hơn có thể có hàng nghìn máy tính.
Khả năng mở rộng được đặc trưng bởi tính không thay đổi phần mềm hệ thống và
phần mềm ứng dụng khi hệ được mở rộng. Điều này chỉ đạt được mức độ nào đó với hệ
phân tán hiện tại. Yêu cầu việc mở rộng không chỉ là sự mở rộng về phần cứng, về
mạng mà trải trên các khía cạnh khi thiết kế hệ phân tán.
1.2.5. Khả năng thứ lỗi
Việc thiết kế khả năng thứ lỗi của các hệ thống máy tính dựa trên hai giải pháp:
Dùng khả năng thay thế để đảm bảo sự hoạt động liên tục và hiệu quả.
Dùng các chương trình hồi phục khi xảy ra sự cố.
Xây dựng một hệ thống có thể khắc phục sự cố theo cách thứ nhất thì nối hai máy
tính với nhau để thực hiện cùng một chương trình, một trong hai máy chạy ở chế độ
Standby. Giải pháp này tốn kém vì phải nhân đôi phần cứng của hệ thống. Một giải pháp
để giảm chi phí là các Server riêng lẻ được cung cấp các ứng dụng quan trọng để có thể
thay thế nhau khi có sự cố xuất hiện. Khi không có sự cố các Server hoạt động
11
bình thường, khi có sự cố trên một Server nào đó, các ứng dụng Clien tự chuyển hướng
sang các Server còn lại.
Cách hai thì các phần mềm hồi phục được thiết kế sao cho trạng thái dữ liệu hiện
thời (trạng thái trước khi xảy ra sự cố) có thể được khôi phục khi lỗi được phát hiện.
Các hệ phân tán cung cấp khả năng sẵn sàng cao để đối phó với các trường hợp
hỏng phần cứng.
1.2.6. Tính trong suốt
Tính trong suốt của một hệ phân tán được hiểu là việc che khuất đi các thành phần
riêng biệt của hệ thống đối với người sử dụng và những người lập trình ứng dụng.
Tính trong suốt về vị trí: Người sử dụng không cần biết vị trí vật lý của dữ liệu.
Người sử dụng có quyền truy cập đến cơ sở dữ liệu nằm tại bất kỳ vị trí nào. Các thao
tác truy xuất, cập nhật dữ liệu tại một điểm dữ liệu ở xa được tự động thực hiện bởi hệ
thống tại điểm đưa ra yêu cầu, người sử dụng không cần biết đến sự phân tán của cơ sở
dữ liệu trên mạng.
Tính trong suốt trong việc sử dụng: Việc chuyển đổi một phần hay toàn bộ cơ sở
dữ liệu do thay đổi về tổ chức hay quản lý không ảnh hưởng tới thao tác người sử dụng.
Tính trong suốt của việc phân chia: Nếu dữ liệu được phân chia do tăng tải thì
không ảnh hưởng tới người sử dụng.
Tính trong suốt của sự trùng lặp dữ liệu: Nếu dữ liệu trùng lặp để giảm chi phí
truyền thông với cơ sở dữ liệu hoặc nâng cao độ tin cậy, người sử dụng không cần biết
điều đó.
1.2.7. Đảm bảo tin cậy và nhất quán
Hệ thống yêu cầu độ tin cậy cao: Sự bí mật của dữ liệu phải được bảo vệ, các chức
năng khôi phục hư hỏng phải được đảm bảo. Ngoài ra, yêu cầu của hệ thống về tính nhất
quán cũng rất quan trọng, thể hiện trong việc không được có mâu thuẫn trong nội dung
dữ liệu.
1.3. Kiến trúc cơ bản của CSDL phân tán
Mô hình kiến trúc CSDL phân tán gồm: Lược đồ tổng thể, lược đồ phân mảnh,
lược đồ định vị và lược đồ ánh xạ cục bộ (xem Hình 1.2).
Lược đồ tổng thể: Định nghĩa tất cả các dữ liệu sẽ được lưu trữ trong CSDL
phân tán. Trong mô hình quan hệ, lược đồ tổng thể bao gồm định nghĩa của các tập
quan hệ tổng thể.
Lược đồ phân mảnh: Mỗi quan hệ tổng thể có thể chia thành một vài phần tách
biệt nhau được gọi là mảnh (fragments). Có nhiều cách khác nhau để thực hiện việc
phân chia này. Ánh xạ (một - nhiều) giữa lược đồ tổng thể và các mảnh được định nghĩa
trong lược đồ phân mảnh.
Lược đồ định vị: Các mảnh là các phần logic của quan hệ tổng thể được
định vị
12
vật lý trên một hoặc nhiều vị trí trên mạng. Lược đồ định vị định nghĩa mảnh nào định
vị tại các vị trí nào. Kiểu ánh xạ được định nghĩa trong lược đồ định vị quyết định
CSDL phân tán là dư thừa hay không.
Lược đồ ánh xạ cục bộ: Ánh xạ các ảnh vật lý và các đối tượng được lưu trữ tại
một trạm (tất cả các mảnh của một quan hệ tổng thể trên cùng một vị trí tạo ra một ảnh
vật lý)
Lược đồ tổng thể
Lược đồ phân mảnh
Lược đồ định vị
Lược đồ ánh xạ cục bộ 1
DBMS của vị trí 1
CSDL cục bộ tại vị trí 1
Hình 1.2 Kiến trúc cơ bản của CSDL phân tán
1.4. Hệ quản trị cơ sở dữ liệu phân tán
1.4.1. Khái niệm
Hệ quản trị CSDL phân tán (DDBMS) là một hệ thống phần mềm cho phép quản
lý các CSDL phân tán (tạo lập và điều khiển các truy nhập cho các hệ CSDL phân tán)
và làm cho việc phân tán trở nên trong suốt với người sử dụng [11].
Đặc tính trong suốt muốn nói đến sự tách biệt về ngữ nghĩa ở cấp độ cao của một
hệ thống với các vấn đề cài đặt ở cấp độ thấp. Sự phân tán dữ liệu được che dấu với
người sử dụng làm cho người sử dụng truy nhập vào CSDL phân tán như hệ CSDL tập
trung. Sự thay đổi việc quản trị không ảnh hưởng tới người sử dụng.
Hệ quản trị CSDL phân tán gồm một tập các phần mềm (chương trình) sau đây:
Chương trình quản trị dữ liệu phân tán.
Chương trình quản trị việc truyền thông dữ liệu.
Chương trình quản trị các CSDL cục bộ.
Chương trình quản trị từ điển dữ liệu: Thông tin về sự phân tán dữ liệu
trên
mạng.
Hệ quản trị cơ sở dữ liệu phân tán được phân làm hai loại:
13
Hệ quản trị cơ sở dữ liệu phân tán đồng nhất: Là hệ quản trị cơ sở dữ liệu mà tất
cả các nút sử dụng cùng một loại hệ quản trị cơ sở dữ liệu.
Hệ quản trị cơ sở dữ liệu phân tán không đồng nhất: Là hệ quản trị cơ sở dữ liệu
mà có ít nhất một nút không cùng loại hệ quản trị cơ sở dữ liệu với hệ quản trị cơ sở dữ
liệu ở các nút còn lại.
1.4.2. Kiến trúc hệ quản trị CSDL phân tán
1.4.2.1. Các hệ Client/Server
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 phân tán dữ liệu.
Server thực hiện các công việc quản lý dữ liệu. Nghĩa là tất cả xử lý và tối ưu hóa
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ị Client 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ằng
câu lệnh SQL. Cụ thể, Client chuyển truy vấn SQL đến Server, Server sẽ thực hiện và
trả kết quả lại cho Client.
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 – một 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 [2].
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.
Mô hình CSDL logic Client/Server là duy nhất. Mô hình mức vật lý của nó có thể
phân tán. Vì vậy, phân biệt giữa Client/Server và ngang hàng không phải ở mức độ
trong suốt được cung cấp cho người sử dụng và cho ứng dụng mà ở mô hình kiến trúc
được dùng để nhận ra mức độ trong suốt.
1.4.2.2. Các hệ phân tán ngang hàng
Mô hình Client/Server phân biệt Client (nơi yêu cầu dịch vụ) và Server (nơi phục
vụ các yêu cầu). Nhưng trong mô hình xử lý ngang hàng, các hệ thống tham gia có vai
trò như nhau. Chúng có thể vừa yêu cầu dịch vụ từ một hệ thống khác hoặc vừa trở
thành nơi cung cấp dịch vụ. Một cách lý tưởng, mô hình tính toán ngang hàng cung cấp
cho xử lý hợp tác giữa các ứng dụng có thể nằm trên các phần cứng hoặc hệ điều hành
khác nhau. Mục đích của môi trường xử lý ngang hàng là để hỗ trợ các CSDL
14
được nối mạng. Như vậy, người sử dụng DBMS sẽ có thể truy cập tới nhiều CSDL
không đồng nhất [2].
1.5. Thiết kế cơ sở dữ liệu phân tán
1.5.1. Các chiến lược phân tán dữ liệu
Có 3 chiến lược phân tán dữ liệu cơ bản: Sao lặp dữ liệu, phân mảnh dữ liệu và
phương pháp hỗn hợp.
Sao lặp dữ liệu:
CSDL được nhân thành nhiều bản từng phần hoặc đầy đủ và được đặt ở nhiều
trạm trên mạng.
Nếu bản sao của CSDL được lưu trữ trên tất cả các máy trạm của hệ thống, ta có
trường hợp sao lặp đầy đủ.
Hiện nay có nhiều kỹ thuật mới cho phép tạo bản sao không đầy đủ, phù hợp với
yêu cầu dữ liệu ở từng trạm và một bản đầy đủ được quản lý ở server.
Sau một khoảng thời gian nhất định các bản sao được đồng bộ với bản chính
bằng một ứng dụng nào đó.
Ưu điểm:
+
Tăng độ tin cậy: Khi xảy ra sự cố trên một trạm trong hệ thống thì vẫn còn dữ
liệu tại các trạm khác hoặc khi một trạm trong hệ thống bị hỏng thì trạm khác có thể thay
thế, không ảnh hưởng đến toàn bộ hệ thống.
+
Tăng hiệu năng truy vấn dữ liệu trên mạng với các truy vấn toàn cục vì dữ liệu sẽ
được lấy từ các trạm cục bộ.
+
Tránh việc kiểm tra toàn vẹn dữ liệu phức tạp.
+
Giảm liên thông mạng.
- Nhược điểm:
+
Tăng chi phí: Việc tạo ra các bản sao dữ liệu và lưu trữ trên các trạm của hệ
thống sẽ tăng chi phí cho các bộ lưu trữ.
+
Các thao tác cập nhật dữ liệu chậm vì phải sao chép, đồng bộ dữ liệu cho các
trạm. Điều này làm mất đi tính thời gian thực của dữ liệu.
+
Tăng độ phức tạp trong việc bảo trì toàn vẹn.
Phân mảnh dữ liệu: CSDL được chia thành các mảnh nhỏ liên kết với nhau
(không trùng lặp). Mỗi mảnh dữ liệu được đưa đến các trạm thích hợp để sử dụng.
Phương pháp hỗn hợp: Kết hợp phương pháp phân mảnh và sao lặp dữ
liệu.
1.5.2. Phân mảnh dữ liệu
Sự phân mảnh là chia dữ liệu trong các bảng dữ liệu thành các bộ hoặc các bảng dữ
liệu con. Có ba kiểu phân mảnh một quan hệ tổng thể: Phân mảnh ngang, phân mảnh
dọc và phân mảnh hỗn hợp [7].
Một sự phân mảnh là đúng đắn nếu thoả mãn ba điều kiện sau:
Tính đầy đủ: Tất cả dữ liệu của quan hệ tổng thể phải được ánh xạ tới các mảnh,
có nghĩa là mỗi phần tử dữ liệu thuộc quan hệ tổng thể phải thuộc một hay nhiều mảnh
của nó.
15
- Tính phục hồi: Luôn có thể xây dựng lại được quan hệ tổng thể từ các mảnh đã
có.
-
Tính tách biệt: Nếu quan hệ R được phân mảnh ngang thành các mảnh R i (i=1, 2,
…, n) và mục dữ liệu dj nằm trong một mảnh Ri thì nó sẽ không nằm trong mảnh Rk
(k≠i), đảm bảo các mảnh phân mảnh rời nhau. Trong trường hợp phân mảnh dọc, khóa
chính của quan hệ phải được lặp lại trong tất cả các mảnh. Vì vậy, tính tách biệt trong
phân mảnh dọc được hiểu không liên quan đến khóa chính của quan hệ.
1.5.2.1. Phương pháp phân mảnh ngang
Phân mảnh ngang là việc chia quan hệ thành nhiều các 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. 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 loại phân mảnh ngang:
+
Phân mảnh ngang nguyên thủy: Là phân mảnh ngang được thực hiện trên các vị
từ của chính quan hệ đó.
+
Phân mảnh ngang dẫn xuất: Là phân rã một quan hệ dựa trên các vị từ của quan
hệ khác.
b)
Thông tin cần thiết của phân mảnh ngang
Thông tin về CSDL: Thông tin về CSDL là lược đồ toàn cục, quan hệ gốc và các
quan hệ con. Trong ngữ cảnh này, cần biết được các quan hệ sẽ kết nối với nhau bằng
phép nối hay bằng phép tính khác. Với mục đích phân mảnh dẫn xuất, các vị từ được
định nghĩa trên quan hệ khác, ta thường dùng mô hình thực thể liên kết vì trong mô hình
này các mối liên hệ được biểu diễn bằng các đường nối có hướng (các cung) giữa các
quan hệ có liên hệ với nhau qua một nối. Trong mô hình quan hệ thực thể, các mối liên
hệ giữa các đối tượng CSDL được mô tả rõ ràng. Nhìn chung, mối quan hệ giữa các đối
tượng trong CSDL thường mô tả bằng các mối quan hệ một - một, một – nhiều và quan
hệ nhiều – nhiều.
Ví dụ 1.1: Trong Hình 1.3, mỗi một chức vụ có nhiều nhân viên giữ chức vụ đó.
Đây là mối quan hệ một – nhiều được biểu diễn bằng một đường nối có hướng L1 trỏ từ
quan hệ CT (Chi trả) đến NV (nhân viên), mối quan hệ nhiều – nhiều được trỏ từ các
quan hệ NV (nhân viên) và DA (dự án) đến quan hệ PC (phân công) được biểu diễn bằng
hai đường nối L2 và L3.
Quan hệ tại điểm cuối của đường nối được gọi là quan hệ chủ (quan hệ đích) và
các quan hệ tại điểm đầu được gọi là các quan hệ thành viên (quan hệ nguồn). Ánh xạ
Owner và Member từ tập đường nối tới tập quan hệ. Khi cho trước một đường nối, hàm
sẽ trả về quan hệ đích hay quan hệ nguồn của đường nối. Ví dụ trong Hình 1.3: Owner
(L1) = CT và Member (L1) = NV.
CT
Chức vụ, Lương
NV
MNV, tênNV, chức vụ
L2
L3
PC
MNV, MDA, nhiệm vụ, thời gian
Hình 1.3: Mối quan hệ giữa các quan hệ bởi các đường nối.
Ký hiệu lực lượng của mỗi quan hệ R là Card(R).
Thông tin về ứng dụng: Để thực hiện được phân mảnh, cần phải có thông tin định
tính và thông tin định lượng. Thông tin định tính hướng dẫn cho hoạt động phân mảnh,
thông tin định lượng chủ yếu sử dụng trong các mô hình cấp phát.
Thông tin định tính cơ bản gồm các vị từ dùng trong câu truy vấn.
Thông tin định lượng về ứng dụng cần phải có hai tập dữ liệu:
+ Độ tuyển hội sơ cấp (Minterm Selectivity): Số các bộ của quan hệ sẽ được chọn
theo vị từ hội sơ cấp cho trước, ký hiệu chọn của hội sơ cấp m là sel(m).
+ Tần số ứng dụng người dùng truy cập dữ liệu.
+ Tần số truy nhập hội sơ cấp là tần số truy nhập của hội sơ cấp m, ký hiệu là
acc(m).
b) Phân mảnh ngang nguyên thủy
Phân mảnh ngang nguyên thuỷ được định nghĩa bằng một phép toán chọn trên các
quan hệ đích của một lược đồ của CSDL. Vì thế, cho biết quan hệ R, các mảnh ngang
của R là các Ri: Ri = σFi (R), 1 ≤ i ≤ n. Trong đó, Fi là biểu thức đại số quan hệ. Nếu Fi
có dạng chuẩn hội thì nó là vị từ hội sơ cấp (mi).
Ví dụ 1.2: Xét quan hệ DA
MDA
P1
P2
P3
P4
Ta có thể định nghĩa các mảnh ngang dựa vào vị trí dự án. Khi đó các mảnh thu
được được trình bày như sau:
DA = σ
1
Địa điểm = “Hưng Yên”
(DA)
DA = σ
2
Địa điểm = “Hà Nội”
(DA)
17
DA = σ
3
Địa điểm = “Huế”
(DA)
DA1
MDA
P1
DA2
MDA
P2
P3
DA3
MDA
P4
Phân mảnh ngang Ri của quan hệ R có chứa tất cả các bộ của R thỏa mãn một vị từ
hội sơ cấp mi. Vì vậy, cho một tập M các vị từ hội sơ cấp, số lượng phân mảnh ngang
của quan hệ R bằng số lượng vị từ hội sơ cấp. Tập các mảnh ngang được gọi là tập các
mảnh hội sơ cấp. Định nghĩa phân mảnh ngang phụ thuộc vào vị từ hội sơ cấp, vì vậy,
cần phải xác định các vị từ đơn giản tạo ra vị từ hội sơ cấp.
Một đặc tính quan trọng của các vị từ đơn giản là tính đầy đủ và tính cực tiểu.
Tập các vị từ đơn giản Pr được gọi là đầy đủ nếu và chỉ nếu xác suất mỗi ứng
dụng truy xuất đến một bộ bất kỳ thuộc về một mảnh hội sơ cấp nào đó được định nghĩa
theo Pr đều bằng nhau.
Ví dụ 1.3: Xét quan hệ phân mảnh DA được đưa ra trong Ví dụ 1.2. Nếu tập ứng
dụng Pr = {Địa điểm = ”Hưng Yên”, Địa điểm = ”Hà Nội ”, Địa điểm = ”Huế”, Ngân
sách 200000} thì Pr không đầy đủ vì có một số bộ của DA không được truy xuất bởi vị
từ Ngân sách 200000. Để tập vị từ này đầy đủ, cần phải xét thêm vị từ Ngân sách
> 200000 vào Pr. Vậy Pr = {Địa điểm = ”Hưng Yên”, Địa điểm = ”Hà Nội”, Địa điểm =
”Huế”, Ngân sách 200000 , Ngân sách > 200000} là đầy đủ bởi vì mỗi bộ được truy xuất
bởi đúng hai vị từ p của Pr. Nếu bớt đi một vị từ bất kỳ trong Pr thì tập còn lại không đầy
đủ.
Cần phải đảm bảo tính đầy đủ vì các mảnh thu được theo tập vị từ đầy đủ sẽ nhất
quán về mặt logic do tất cả chúng đều thoả vị từ hội sơ cấp. Chúng cũng đồng nhất và
đầy đủ về mặt thống kê theo cách mà ứng dụng truy xuất chúng. Vì thế, sẽ dùng một tập
hợp gồm các vị từ đầy đủ làm cơ sở của phân mảnh ngang nguyên thủy.
Đặc tính thứ hai của tập các vị từ là tính cực tiểu. Vị từ đơn giản phải có liên đới
trong việc xác định một mảnh. Một vị từ không tham gia vào một phân mảnh nào thì có
thể coi vị từ đó là thừa. Nếu tất cả các vị từ của Pr đều có liên đới thì Pr là cực tiểu.
18
Ví dụ 1.4: Tập Pr được định nghĩa trong Ví dụ 1.3 là đầy đủ và cực tiểu. Tuy nhiên
nếu thêm vị từ TênDA = ”thiết bị đo đạc” vào Pr, tập kết quả sẽ không còn cực tiểu bởi
vì vị từ mới thêm vào không có liên đới ứng với Pr. Vị từ mới thêm vào không chia thêm
mảnh nào trong các mảnh đã được tạo ra.
Khái niệm đầy đủ gắn chặt với mục tiêu của bài toán. Số vị từ phải đầy đủ theo yêu
cầu của bài toán thì mới thực hiện được những vấn đề đặt ra của bài toán. Khái niệm cực
tiểu liên quan đến vấn đề tối ưu của bộ nhớ, tối ưu của các thao tác trên tập các câu truy
vấn. Vậy khi cho trước một tập vị từ Pr để xét tính cực tiểu ta có thể kiểm tra bằng cách
bỏ những vị từ thừa để có tập vị từ Pr’ là cực tiểu và Pr’ cũng là tập đầy đủ với Pr.
Thuật toán COM_MIN: Cho phép tìm tập các vị từ đầy đủ và cực tiểu Pr’ từ Pr.
Quy tắc 1: Quy tắc cơ bản về tính đầy đủ và cực tiểu, nó khẳng định rằng một quan
hệ hoặc một mảnh được phân hoạch thành ít nhất hai phần và chúng được truy xuất khác
nhau bởi ít nhất một ứng dụng.
Thuật toán 1.1 COM_MIN
Input: R: Quan hệ; Pr: Tập các vị từ đơn giản;
Output: Pr’: Tập các vị từ cực tiểu và đầy đủ;
{F: Tập các mảnh hội sơ cấp}
Begin
Pr’ = ; F = ;
For each vị từ p Pr
if p phân hoạch R theo Quy tắc 1 then
Begin
Pr’: = Pr’ p;
Pr: = Pr – p;
F: = F fi; {fi là mảnh hội sơ cấp theo pi }
End; {Các vị từ có phân mảnh R đã được chuyển vào Pr’}
Repeat
For each p Pr
if p phân hoạch một mảnh fk của Pr’ theo quy tắc 1 then
Begin
Pr’: = Pr’ p;
Pr: = Pr – p;
F: = F p;
End;
Until Pr’ đầy đủ {Không còn p nào phân mảnh fk của Pr’}
For each p Pr’
if p’ mà p <=> p’ then
Begin
19
Pr’:= Pr’-p;
F:= F - f;
End;
End. {COM_MIN}
Thuật toán bắt đầu bằng cách tìm một vị từ có liên đới và phân hoạch quan hệ đã
cho. Vòng lặp Repeat - Until thêm các vị từ có phân hoạch các mảnh vào tập này, đảm
bảo tính đầy đủ của Pr’. Đoạn cuối kiểm tra tính cực tiểu của Pr’. Vì thế, cuối cùng ta có
tập Pr’ là cực tiểu và đầy đủ.
Bước hai của việc thiết kế phân mảnh nguyên thủy là suy dẫn ra tập các vị từ hội
sơ cấp có thể được định nghĩa trên các vị từ trong tập Pr’. Các vị từ hội sơ cấp này xác
định các mảnh cấp phát.
Bước ba của quá trình thiết kế là loại bỏ một số mảnh vô nghĩa. Điều này được
thực hiện bằng cách xác định những vị từ mâu thuẫn với tập các phép kéo theo I. Chẳng
hạn nếu Pr’ = {p1, p2}, trong đó:
p1: att = value_1
p2: att = value_2
Và miền biến thiên của att là {value_1, value_2}, rõ ràng I chứa hai phép kéo theo
với khẳng định:
I1: (att = value_1)
(att = value_2)
I2: (att = value_1)
(att = value_2)
Bốn vị từ hội sơ cấp được định nghĩa theo Pr’ như sau:
m1: (att = value_1)
(att = value_2)
m2: (att = value_1)
(att = value_2)
m3: (att = value_1)
(att = value_2)
m4: (att = value_1)
(att = value_2)
Trong trường hợp này các vị từ hội sơ cấp m1, m4 mâu thuẫn với các phép kéo theo
I và vì thế bị loại ra khỏi M.
Thuật toán phân mảnh ngang nguyên thủy được trình bày trong thuật toán 1.2.
Thuật toán 1.2 PHORIZONTAL
Input: R: Quan hệ; Pr: Tập các vị từ đơn giản;
Output: M: Tập các vị từ hội sơ cấp;
Begin
Pr’:= COM_MIN(R, Pr);
Xác định tập M các vị từ hội sơ cấp;
Xác định tập I các phép kéo theo giữa các pi Pr’;
For each mi M do
Begin
IF mi mâu thuẫn với I then
M := M-mi ;
End
20
End. {PHORIZONTAL}
Ví dụ 1.5: Xét quan hệ DA. Giả sử có hai ứng dụng: Ứng dụng đầu tiên được đưa
ra tại ba vị trí và cần tìm tên và ngân sách của các dự án khi cho biết vị trí. Câu truy vấn
được viết theo cú pháp SQL là:
SELECT TênDA, Ngân sách
FROM
DA
WHERE địa điểm=giá trị
Đối với ứng dụng này, các vị từ đơn giản có thể được dùng là:
p1: Địa điểm = ”Hưng Yên”
p2: Địa điểm = ”Hà Nội”
p3: Địa điểm = ”Huế”
Ứng dụng thứ hai là những dự án có ngân sách dưới 200.000 đô la được quản lý tại
một vị trí, còn những dự án có ngân sách lớn hơn được quản lý tại một vị trí thứ hai. Vì
thế các vị từ đơn giản phải được sử dụng để phân mảnh theo ứng dụng thứ hai là:
p4: ngân sách ≤ 200000
p5: ngân sách > 200000
Nếu kiểm tra bằng thuật toán COM_MIN, tập Pr’ = {p 1, p2, p3, p4, p5} rõ ràng đầy
đủ và cực tiểu.
Dựa trên Pr’, có thể định nghĩa sáu vị từ hội sơ cấp sau đây tạo ra M:
m1: (Địa điểm =”Hưng Yên”)
(ngân sách ≤ 200000)
m2: (Địa điểm =”Hưng Yên”)
(ngân sách > 200000)
m3: (Địa điểm =”Hà Nội”)
(ngân sách ≤ 200000)
m4: (Địa điểm =”Hà Nội”)
(ngân sách > 200000)
m5: (Địa điểm =”Huế”)
(ngân sách ≤ 200000)
m6: (Địa điểm =”Huế”) (ngân sách > 200000)
Đây không phải là các vị từ hội sơ cấp duy nhất có thể được tạo ra. Chẳng hạn vẫn
có thể định nghĩa các vị từ:
p1 p2 p3 p4 p5
Tuy nhiên các phép kéo hiển nhiên là:
I1: p1
p2
p3
I2: p2
p1
p3
I3: p3
p1
p2
I4: p4
p5
I5: p5
p4
I6: p4
p5
I7: p5 p4
Cho phép loại bỏ những vị từ hội sơ cấp này và còn lại m1 đến m6.
Một số mảnh được định nghĩa theo M = {m1,…,m6} có thể rỗng nhưng chúng
