ĐẠ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................................................................................................................... 1
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ............................................... 3
DANH MỤC CÁC HÌNH VẼ ..................................................................................... 4
LỜI MỞ ĐẦU ............................................................................................................. 5
Chương 1: KHÁI QUÁT VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN ..................................... 7
1.1. Cơ sở dữ liệu phân tán. ....................................................................................... 7

1.1.1. Định nghĩa .................................................................................................. 7
1.1.2. Ưu điểm...................................................................................................... 8
1.1.3. Nhược điểm ................................................................................................ 9
1.2. Đặc điểm của cơ sở dữ liệu phân tán ................................................................... 9
1.2.1. Chia sẻ tài nguyên ....................................................................................... 9
1.2.2. Tính mở ..................................................................................................... 10
1.2.3. Khả năng song song.................................................................................. 10
1.2.4. Khả năng mở rộng ..................................................................................... 10
1.2.5. Khả năng thứ lỗi ........................................................................................ 10
1.2.6. Tính trong suốt .......................................................................................... 11
1.2.7. Đảm bảo tin cậy và nhất quán .................................................................... 11
1.3. Kiến trúc cơ bản của CSDL phân tán ................................................................ 11
1.4. Hệ quản trị cơ sở dữ liệu phân tán ..................................................................... 12
1.4.1. Khái niệm ................................................................................................. 12
1.4.2. Kiến trúc hệ quản trị CSDL phân tán ........................................................ 13
1.5. Thiết kế cơ sở dữ liệu phân tán ......................................................................... 14
1.5.1. Các chiến lược phân tán dữ liệu ................................................................ 14
1.5.2. Phân mảnh dữ liệu .................................................................................... 14
1.5.2.1. Phương pháp phân mảnh ngang ............................................................. 15
1.5.2.2. Phương pháp phân mảnh dọc ................................................................. 23
1.5.2.3. Phương pháp phân mảnh hỗn hợp. ........................................................ 29
1.6. Kết luận............................................................................................................. 30
Chương 2: TỐI ƯU HÓA TRUY VẤN CƠ SỞ DỮ LIỆU PHÂN TÁN ................... 31
2.1. Vấn đề tối ưu hóa xử lý truy vấn ....................................................................... 31
2.2. Quá trình xử lý truy vấn .................................................................................... 34
2.2.1. Phân rã truy vấn ........................................................................................ 34
2.2.2. Cục bộ hóa dữ liệu phân tán ..................................................................... 41


2

2.2.2.1. Rút gọn cho phân mảnh ngang nguyên thủy ........................................... 41
2.2.2.2. Rút gọn cho phân mảnh dọc. .................................................................. 44
2.2.2.3. Rút gọn cho phân mảnh ngang dẫn xuất ................................................. 44
2.2.2.4. Rút gọn cho phân mảnh hỗn hợp............................................................. 46
2.2.3. Tối ưu hóa toàn cục .................................................................................. 47
2.2.3.1. Không gian tìm kiếm ............................................................................ 48
2.2.3.2. Chiến lược tìm kiếm ............................................................................. 49
2.2.3.3. Mô hình chi phí .................................................................................... 50
2.2.4. Tối ưu hóa cục bộ ..................................................................................... 54
2.3. Các thuật toán tối ưu hóa truy vấn phân tán ....................................................... 54
2.3.1. Thứ tự kết nối ........................................................................................... 55
2.3.2. Thuật toán INGRES phân tán.................................................................... 56
2.3.3. Thuật toán R* ........................................................................................... 60
2.3.4. Thuật toán DP-ACO ................................................................................. 63
2.4. Kết luận............................................................................................................. 67
Chương 3: CHƯƠNG TRÌNH CÀI ĐẶT THUẬT TOÁN TỐI ƯU HÓA TRUY
VẤN .......................................................................................................................... 67
3.1. Bài toán quản lý bệnh nhân ............................................................................... 67
3.2. Mô hình phân tán CSDL, công cụ, ngôn ngữ lập trình ....................................... 70
3.3. Thuật toán áp dụng ............................................................................................ 70
3.4. Kết quả thực nghiệm ......................................................................................... 70
3.5. Kết luận............................................................................................................. 73
KẾT LUẬN ............................................................................................................... 74
TÀI LIỆU THAM KHẢO ......................................................................................... 75


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)


Diễn giải
Tối ưu đàn kiến
Cơ sở dữ liệu
Bộ xử lý trung tâm
Hệ quản trị cơ sở dữ liệu

Hệ quản trị cơ sở dữ liệu phân tán

Quy hoạch động
Vào/Ra
Cây xử lý
Giới hạn không gian tìm kiếm


4
DANH MỤC CÁC HÌNH VẼ
Hình 1.1 Môi trường hệ CSDL phân tán ......................................................... ….8
Hình 1.2 Kiến trúc cơ bản của CSDL phân tán..................................................... 12
Hình 1.3: Mối quan hệ giữa các quan hệ bởi các đường nối .................................. 16
Hình 1.4: Ma trận tụ tương quan CA..................................................................... 26
Hình 1.5: Phân đoạn hỗn hợp ................................................................................ 29
Hình 1.6. Tái xây dựng phân đoạn hỗn hợp .......................................................... 30
Hình 2.1: Giải pháp A..............................................................................................32
Hình 2.2: Giải pháp B ........................................................................................... 32
Hình 2.3: Sơ đồ truy trình xử lý truy vấn .............................................................. 34
Hình 2.4: Đồ thị truy vấn và Đồ thị nối ................................................................. 37
Hình 2.5: Đồ thị truy vấn và Đồ thị nối với câu truy vấn sai ngữ nghĩa ................. 37
Hình 2.6: Cây đại số quan hệ ................................................................................ 39
Hình 2.7: Cây đại số quan hệ sau khi tái cấu trúc ................................................. 41

Hình 2.8: Câu truy vấn gốc ................................................................................... 42
Hình 2.9: Câu truy vấn đã rút gọn ........................................................................ 42
Hình 2.10: Rút gọn phân mảnh ngang .................................................................. 43
Hình 2.11. Rút gọn phân mảnh dọc ...................................................................... 44
Hình 2.12: Rút gọn cho phân mảnh ngang dẫn xuất ............................................. 46
Hình 2.13: Rút gọn phân mảnh hỗn hợp ................................................................ 47
Hình 2.14: Bộ tối ưu truy vấn ............................................................................... 48
Hình 2.15: Các cây nối ......................................................................................... 49
Hình 2.16: Hình dáng của một số cây nối ............................................................. 49
Hình 2.17: Đồ thị minh họa tổng chi phí và thời gian trả lời ..........................51
Hình 2.18:Truyền các toán hạng trong phép toán hai ngôi.............................55
Hình 2.19: Đồ thị nối của truy vấn phân tán .......................................................... 56
Hình 2.20: Đồ thị nối của truy vấn q1 ................................................................... 62
Hình 2.21: Các thứ tự kết nối ................................................................................ 63
Hình 2.22: Quá trình quyết định đường đi của đàn kiến ........................................ 64
Hình 3.1: Mối quan hệ giữa các bảng dữ liệu ........................................................ 70
Hình 3.2: Kết quả thực hiện câu truy vấn tại trạm 1 .............................................. 71
Hình 3.3: Kết quả thực hiện câu truy vấn tại trạm 2 .............................................. 71
Hình 3.4: Kết quả thực hiện câu truy vấn tại trạm 3 .............................................. 72
Hình 3.5: Kết quả thực hiện câu truy vấn tại trạm 1 .............................................. 72
Hình 3.6: Kết quả thực hiện câu truy vấn tại trạm 2 .............................................. 73


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.


8
Trạm 1

Trạm 2

DB

Mạng truyền thông

DB


DB

DB

Trạm 4

Trạm 3

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


Lược đồ ánh xạ cục bộ 2

DBMS của vị trí 1

DBMS của vị trí 2

CSDL cục bộ tại vị trí 1

Các vị trí khác…

CSDL cục bộ tại vị trí 2

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 Ri (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.
a) 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.


16
CT
Chức vụ, Lương
DA

L1

NV

MNV, tênNV, chức vụ
L2

MDA, tênDA, ngân sách, địa điểm

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
TênDA
Ngân sách
Địa điểm
P1
Thiết bị đo đạc
150000
Hưng Yên
P2
Phát triển dữ liệu
135000
Hà Nội
P3
CAD/CAM
250000
Hà Nội

P4
Bảo dưỡng
310000
Huế
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:
DA1 = σĐịa điểm = “Hưng Yên” (DA)
DA2 = σĐịa điểm = “Hà Nội” (DA)


17
DA3 = σĐịa điểm = “Huế” (DA)
DA1
MDA
TênDA
P1
Thiết bị đo đạc

Ngân sách
150000

Địa điểm
Hưng Yên

DA2
MDA
P2
P3

TênDA

Phát triển dữ liệu
CAD/CAM

Ngân sách
135000
250000

Địa điểm
Hà Nội
Hà Nội

DA3
MDA
P4

TênDA
Thiết bị đo đạc

Ngân sách
310000

Địa điểm
Huế

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’ = {p1, 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


21

vẫn là các mảnh. Kết quả phân mảnh nguyên thuỷ cho DA là tạo ra sáu mảnh FDA =
{DA1, DA2, DA3, DA4, DA5, DA6}, ở đây có hai mảnh rỗng là {DA2, DA5}
DA1
MDA
TênDA
Ngân sách
Địa điểm
P1

Thiết bị đo đạc

150000

Hưng Yên

Ngân sách

Địa điểm

Phát triển dữ liệu

135000

Hà Nội

TênDA

Ngân sách

Địa điểm


CAD/CAM

250000

Hà Nội

TênDA

Ngân sách

Địa điểm

Bảo dưỡng

310000

Huế

DA3
MDA
P2

TênDA

DA4
MDA
P3
DA6
MDA

P4

c) Phân mảnh ngang dẫn xuất
Phân mảnh ngang dẫn xuất được định nghĩa trên một quan hệ thành viên của
đường nối dựa theo phép toán chọn trên quan hệ đích của đường nối đó.
Như vậy, nếu cho trước một đường nối L, trong đó owner (L) = S và member(L)
= R, và các mảnh ngang dẫn xuất của R được định nghĩa là:
Ri = R Si , 1 ≤ i ≤ w
Trong đó, w là số lượng các mảnh được định nghĩa trên R, và Si = Fi(S) với Fi là
công thức định nghĩa mảnh ngang nguyên thuỷ Si
Ví dụ 1.6: Xét đường nối
NV
CT
MNV TênNV
Chức vụ
E1
E2
E3
E4
E5
E6
E7
E8

Hà
Hùng
Trung
Dũng
Hoa
Tuấn

Quân
Hương

Kỹ sư điện
Phân tích hệ thống
Kỹ sư cơ khí
Lập trình viên
Phân tích hệ thống
Kỹ sư điện
Kỹ sư cơ khí
Phân tích hệ thống

Chức vụ, Lương
L1
NV
MNV, TênNV, Chức vụ

Ta có thể nhóm các kỹ sư thành hai nhóm tùy theo lương: Nhóm có lương từ