Giáo trình xử lý dữ liệu phân tán | Đại học Thái Nguyên

lOMoAR cPSD| 45349271 CHƯƠNG I
TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN
Với việc phân bố ngày càng rộng rãi của các công ty, xí nghiệp, dữ liệu bài toán là rất lớn
và không tập trung ược. Các CSDL thuộc thế hệ một và hai không giải quyết ược các bài toán
trong môi trường mới không tập trung mà phân tán, song song với các dữ liệu và hệ thống không
thuần nhất, thế hệ thứ ba của hệ quản trị CSDL ra ời vào những năm 80 trong ó có CSDL phân
tán ể áp ứng những nhu cầu mới.
1.1. Xử lý phân tán và hệ thống xử lý phân tán
Ngay từ các máy tính thế hệ thứ hai, ơn vị xử lý trung tâm CPU và các chức năng xuất
nhập (Input/Output function) ã ược tách riêng những vẫn an quyện vào nhau. Sự tách biệt và an
quyện này có thể ược xem như một dạng xử lý phân tán. Tuy nhiên, cũng cần nhận ra rằng iều
mà chúng ta xem là xử lý phân tán ở ây không phải là hình thức phân bố chức năng trên một hệ thống ơn bộ xử lý.
Một thuật ngữ ã gây nhiều nhầm lẫn sẽ rất khó ịnh nghĩa chính xác. Có một số cố gắng
nhằm ịnh nghĩa việc xử lý phân tán có nghĩa là gì, và hầu như mỗi nhà nghiên cứu ều ưa ra nhột
ịnh nghĩa riêng. Định nghĩa cho một hệ thống tính toán phân tán khẳng ịnh rằng ó là một số các
bộ phận xử lý tự vận hành (không nhất thiết phải cùng chủng loại) ược liên kết bởi một mạng
máy tính và cùng thực hiện các tác vụ mà chúng ược phân công. "Các bộ phận xử lý" muốn nói
ến trong ịnh nghĩa này là các thiết bị tính toán có thể chạy ược một chương trình trên chính nó.
Câu hỏi cơ bản ược ặt ra là: Những gì ược phân tán? Một trong những iều có thể ược phân
tán là thiết bị xử lý. Thực tế, ịnh nghĩa về hệ thống tính toán phân tán ược trình bày ở trên ã
ngầm giả sử rằng các bộ phận xử lý ược phân tán. Một kiểu phân tán nữa là chức năng. Nhiều
chức năng của hệ thống máy tính có thể ược chuyển giao cho các thành phần phần cứng và phần
mềm. Kiểu thứ ba là theo dữ liệu. Dữ liệu ược dùng bởi một số ứng dụng có thể ược phân tán
cho một số vị trí xử lý. Cuối cung là quyền iều khiển cũng có thể phân tán. Quyền iều khiến
việc thực hiện một số tác vụ có thể ược phân tán thay vì ược thực hiện bởi một hệ thống máy
tính. Từ góc ộ của hệ CSDL phân tán, những kiểu phân tán này ều cần thiết và quan trọng.
Một câu hỏi hợp lý khác ược ặt ra là: Tại sao chúng ta lại thực hiện phân tán? Nhiều câu trả lời
kinh iển cho câu hỏi này ã chỉ ra rằng việc xử lý phân tán là nhằm thích ứng tốt hơn với việc
phân bố ngày càng rộng rãi của các công ty, ồng thời một hệ thống như thế phải có ộ tin cậy
cao hơn và khả năng áp ứng tốt hơn. Quan trọng hơn, nhiều ứng dụng hiện tại của công nghệ
máy tính ược phân tán như một hệ quả tất yếu. Thương mại iện tử trên Internet, các ứng dụng a 1 lOMoAR cPSD| 45349271
phương tiện như việc cung cấp tin tức theo yêu cầu, các kỹ thuật chẩn oán hình ảnh trong y
khoa hoặc các hệ thống iều khiển sản xuất ều minh họa cho những ứng dụng phân tán.
Tuy nhiên từ góc ộ tổng thể hơn, chúng ta có thể khẳng ịnh rằng lý do cơ bản của việc
xử lý phân tán là do nó có thể giải quyết tốt hơn các bài toán lớn và phức tạp mà chúng ta gặp
phải hiện nay bằng cách sử dụng một biến thể của qui tắc "chia ể trị" ã ược biết từ lâu. Nếu việc
hỗ trợ bằng phần mềm cần cho vấn ề xử lý phân tán phát triển ược, thì có thể giải các bài toán
này một cách ơn giản là chia nhỏ chúng ra và gán chúng cho các nhóm phần mềm ược chạy trên
các máy tính khác nhau, tạo ra một hệ thống chạy trên nhiều bộ phận xử lý nhưng có thể hoạt
ộng hiệu quả nhằm thực thi một tác vụ chung nào ó.
Từ quan iểm kinh tế, cách tiếp cận này có hai ưu iểm cơ bản. Trước tiên việc tính toán
phân tán cung cấp một phương pháp kinh tế nhằm tận dụng ược sức mạnh tính toán bằng cách
sử dụng nhiều bộ phận xử lý một cách tối ưu. Nó òi hỏi phải nghiên cứu về các hệ thống phân
tán như ã ược ịnh nghĩa trước ây, và cả những hệ thống xử lý song song, là phần không thuộc
phạm vi của giáo trình này. Lý do kinh tế thứ hai ó là, bằng việc giải quyết bài toán theo từng
nhóm hoạt ộng khá ộc lập, chúng ta có thể kiểm soát ược chi phí phát triển phần mềm, Thực sự
chúng ta ều biết rằng chi phí phần mềm ã tăng ngược lại với chi phí của phần cứng.
Các hệ CSDL phân tán cũng có thể ược xem xét trong khuôn khổ của bộ khung này và
ược xử lý như những công cụ có thể làm cho việc xử lý phân tán dễ dàng và hiệu quả hơn.
Chúng ta có thể phác họa tính chất tương ồng giữa những gì mà các hệ | CSDL phân tán có thể
hỗ trợ cho việc xử lý dữ liệu với những gì mà công nghệ CSDL ã cung cấp. Chẳng nghi ngờ gì
nữa, việc phát triển các hệ CSDL phân tán a mục ích, dễ áp dụng và có hiệu quả sẽ giúp rất
nhiều cho việc phát triển các phần mềm phân tán.
1.2. Hệ CSDL phân tán
1.1.1. Định nghĩa CSDL phân tán
Một CSDL phân tán là một tập hợp nhiều CSDL có liên ới logic và ược phân bố rải rác
trên nhiều máy trong một mạng máy tính
Tính chất phân tán: Toàn bộ dữ liệu của CSDL phân tán không ược lưu trữ ở một nơi mà
cư trú trên nhiều máy trạm thuộc mạng máy tính, iều này giúp chúng ta phân biệt CSDL phân
tán với CSDL tập trung ơn lẻ.
Tương quan logic: Toàn bộ dữ liệu của một CSDL phân tán có một số các thuộc tính ràng
buộc chúng với nhau, iều này giúp chúng ta có thể phân biệt một CSDL phân tán với một tập
hợp CSDL cục bộ hoặc các tệp cư trú tại các vị trí khác nhau trong một mạng máy tính. 2 lOMoAR cPSD| 45349271
Hình 1.1. Môi trường hệ cơ sở dữ liệu phân tán
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ể thực hiện các giao
tác truy nhập dữ liệu trên nhiều trạm khác.
Ví dụ 1.1: 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ê ịa phương 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.
1.1.2. Định nghĩa hệ quản trị CSDL phân tán
Hệ quản trị CSDL phân tán (Distributed Database Management System-DBMS) ược ịnh
nghĩa là một hệ thống phần mềm cho phép quản lý các hệ CSDL (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.
Đặc tính vô hình 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 1 tập các phần mềm (chương trình) sau: •
Các chương trình quản trị các dữ liệu phân tán •
Chứa các chương trình ể quản trị việc truyền thông dữ liệu Các chương trình ể
quản trị các CSDL ịa phương. •
Các chương trình quản trị từ iển dữ liệu.
Để tạo ra một hệ CSDL phân tán (Distributed Database System-DDBS) các tập tin không
chỉ có liên ới logic chúng còn phải có cấu trúc và ược truy xuất qua một giao diện chung.
Môi trường hệ CSDL phân tán là môi trường trong ó dữ liệu ược phân tán trên một số vị trí. 3 lOMoAR cPSD| 45349271
Hình 1.2. Hệ a bộ xử lý có bộ nhớ chung
Một hệ CSDL phân tán (DDBS) không phải là một tập hợp các tập tin ược lưu riêng rẽ
tại mỗi nút của một mạng máy tính. Để tạo ra một hệ CSDL phân tán, các tập tin không chỉ có
liên ới logic nhưng chúng còn phải có cấu trúc và ược truy xuất qua một giao diện chung. Hiện
nay, ang có nhiều nỗ lực cung cấp các ặc thù chức năng của DBMS trên các dữ liệu bản cấu
trúc, ược lưu trong các tập tin trên Internet. Với hiện thực ó, òi hỏi ở trên dường như khắt khe
một cách không cần thiết. Tuy nhiên việc cung cấp một truy xuất "tựa DBMS" ến dữ liệu khác
với một hệ CSDL phân tán.
Đôi khi chúng ta giả thiết rằng việc phân bố vật lý của các dữ liệu không phải là vấn ề
quyết ịnh. Đưa ra quan iểm này có thể tạo thoải mái khi gán cho hai CSDL hiện hữu trên cùng
một hệ thống máy tính là một CSDL phân tán. Tuy nhiên việc phân bố vật lý của các dữ liệu
vẫn hết sức quan trọng. Nó làm nảy sinh những vấn ề không hề gặp phải khi dữ liệu ược lưu
trên cùng một máy tính. Phân bố vật lý không nhất thiết là các hệ thống máy tính phải tách biệt
nhau về mặt ịa lý, thực sự chúng có thể trong cùng một phòng. Nó chỉ khẳng ịnh một iều là việc
giao tiếp giữa chúng ược thực hiện trên một mạng thay vì qua bộ nhớ chung, với mạng ược xem
là tài nguyên dùng chung duy nhất.
Điều này lại dẫn ến một vấn ề khác. Định nghĩa trên cũng loại bỏ các hệ thống a bộ xử
lý ra khỏi nhóm các hệ CSDL phân tán. Một hệ a bộ xử lý nói chung ược xem như một hệ thống
có hai hoặc nhiều bộ xử lý cùng dùng chung một dạng bộ nhớ nào ó, hoặc là bộ nhớ chính và
khi ó ược gọi là có bộ nhớ chung hay kết chặt (Hình 1.2), hoặc dùng chung bộ nhớ thứ cấp và
khi ó ược gọi là có ĩa chung (shared disk) hay kết hờ (loosely coupled) (Hình 1.3). 4 lOMoAR cPSD| 45349271
Hình 1.3. Hệ a bộ xử lý có ĩa chung
Trong ngữ cảnh này, chúng ta cần phân biệt giữa kiến trúc sở hữu tập thể và kiến trúc
sở hữu cá nhân. Mô hình thứ nhất cho phép mỗi bộ xử lý truy xuất ược mọi tài nguyên (bộ nhớ
chính, bộ nhớ thứ cấp, các thiết bị ngoại vi) trong hệ thống và như thế bao quát cả mô hình ược
mô tả ở trên. Dùng chung bộ nhớ cho phép các bộ xử lý giao tiếp với nhau mà không cần phải
trao ổi các thông báo. Kiến trúc sở hữu cá nhân (Hình 1.4) là kiến trúc nhà trong ó mỗi bộ xử
lý có riêng bộ nhớ chính, bộ nhớ thứ cấp và các thiết bị ngoại vi, trao ổi với các bộ xử lý khác
qua các kênh truyền tốc ộ cao. Tuy nhiên có nhiều khác biệt giữa các tương tác trong kiến trúc
a bộ xử lý và các tương tác kém rất thường gặp trong môi trường tính toán phân tán. Sự khác
biệt cơ bản là thể thức hoạt ộng. Thiết kế một hệ thống a bộ xử lý khá ối xứng bao gồm một số
bộ xử lý và các thành phần bộ nhớ ồng nhất, ược iều khiển bởi một hoặc nhiều bản sao của cùng
một hệ iều hành, chịu trách nhiệm kiểm soát chặt chẽ việc phân công tác vụ cho mỗi bộ xử lý.
Trong môi trường tính toán phân tán, iều này không úng do tỉnh a chủng của các hệ iều hành cũng như phần cứng. 5 lOMoAR cPSD| 45349271
Hình 1.4. Hệ a bộ xử lý sở hữu cá nhân
Ngoài ra một hệ CSDL phân tán không phải là hệ thống mà trong ó, dù có sự hiện diện
của một mạng máy tính, CSDL lại chỉ nằm tại một nút của mạng. (Hình 1.6). Trong trường hợp
này, vấn ề quản trị CSDL không khác với việc quản trị CSDL trong môi trường tập trung. CSDL
này ược quản lý tập trung tại một hệ thống máy tính (Trạm 2 trong Hình 1.5) và tất cả mọi yêu
cầu ều ược chuyển ến vị trí ó. Điều cần xem xét duy nhất là sự chậm trễ khi truyền dữ liệu. Hiển
nhiên là sự tồn tại của mạng máy tính hoặc một tập các tập tin không ủ ể tạo ra một hệ CSDL
phân tán. Điều mà chúng ta quan tâm là một môi trường trong ó dữ liệu ược phân tán trên nó số vị trí (Hình 1.6).
Hình 1.5. CSDL trung tâm trên một mạng
Hình 1.6. Môi trường của hệ CSDL phân tán 6 lOMoAR cPSD| 45349271
1.3. Các ặc iểm của cơ sở dữ liệu phân tán
1.3.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, ... 1.3.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 với iều kiện là các thành phần này phải theo một tiêu chuẩn chung.
Tính mở của hệ phân tán ược xem như là 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.3.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ó
1 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 hai tình huống sau: -
Nhiều người sử dụng ồng thời ra các lệnh hay các tương tác với các chương trình ƯD -
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.3.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 tới hàng nghìn máy tính. 7 lOMoAR cPSD| 45349271
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 mở rộng không chỉ là sự mở rộng về phần cứng, về mạng mà nó trải trên các khía cạnh khi thiết kế hệ phân tán.
1.3.5. Khả năng thứ lỗi
Việc thiết kế khả năng thứ lỗi dựa trên hai giải pháp cơ bản sau:
- 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ì người ta 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
(không tải hay chờ). 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 phí tổn 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ó các sự cố các Server hoạt ộng 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 sai hỏng phần cứng.
1.3.6. Tính trong suốt
Tính trong suốt ược hiểu như là việc che khuất i các thành phần riêng biệt của hệ ố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 tới ến cơ sở dữ liệu nằm bất kỳ tại vị trí nào. Các thao tác lấy, 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 của 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, nó không ược
ảnh hưởng tới người sử dụng.
Tính trong suốt của sự trùng lặp: 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 ến iều ó.
1.3.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 8 lOMoAR cPSD| 45349271
quan trọng trong thể hiện: không ược có mâu thuẫn trong nội dung dữ liệu. Khi các thuộc tính
dữ liệu là khác nhau thì các thao tác vẫn phải nhất quán.
Xuất phát từ yêu cầu thực tế về tổ chức và kinh tế: Trong thực tế nhiều tổ chức là không
tập trung, dữ liệu ngày càng lớn và phục vụ cho a người dùng nằm phân tán, vì vậy cơ sở dữ
liệu phân tán là con ường thích hợp với cấu trúc tự nhiên của các tổ chức ó. Đây là một trong
những yếu tố quan trọng thức ẩy việc phát triển cơ sở dữ liệu phân tán.
Sự liên kết các cơ sở dữ liệu ịa phương ang tồn tại: cơ sở dữ liệu phân tán là giải pháp tự
nhiên khi có các cơ sở dữ liệu ang tồn tại và sự cần thiết xây dựng một ứng dụng toàn cục.
Trong trường hợp này cơ sở dữ liệu phân tán ược tạo từ dưới lên dựa trên nền tảng cơ sở dữ liệu
ang tồn tại. Tiến trình này òi hỏi cấu trúc lại các cơ sở dữ liệu cục bộ ở một mức nhất ịnh. Dù
sao, những sửa ổi này vẫn là nhỏ hơn rất nhiều so với việc tạo lập một cở sở dữ liệu tập trung hoàn toàn mới.
Làm giảm tổng chi phí tìm kiếm: Việc phân tán dữ liệu cho phép các nhóm làm việc cục
bộ có thể kiểm soát ược toàn bộ dữ liệu của họ. Tuy vậy, tại cùng thời iểm người sử dụng có thể
truy cập ến dữ liệu ở xa nếu cần thiết. Tại các vị trí cục bộ, thiết bị phần cứng có thể chọn sao
cho phù hợp với công việc xử lý dữ liệu cục bộ tại iểm ó.
Sự phát triển mở rộng: Các tổ chức có thể phát triển mở rộng bằng cách thêm các ơn vị
mới, vừa có tính tự trị, vừa có quan hệ tương ối với các ơn vị tổ chức khác. Khi ó giải pháp cơ
sở dữ liệu phân tán hỗ trợ một sự mở rộng uyển chuyển với một mức ộ ảnh hưởng tối thiểu tới các ơn vị ang tồn tại
Trả lời truy vấn nhanh: Hầu hết các yêu cầu truy vấn dữ liệu từ người sử dụng tại bất kỳ
vị trí cục bộ nào ều thoả mãn dữ liệu ngay tại thời iểm ó.
Độ tin cậy và khả năng sử dụng nâng cao: nếu có một thành phần nào ó của hệ thống bị
hỏng, hệ thống vẫn có thể duy trì hoạt ộng.
Khả năng phục hồi nhanh chóng: Việc truy nhập dữ liệu không phụ thuộc vào một máy
hay một ường nối trên mạng. Nếu có bất kỳ một lỗi nào hệ thống có thể tự ộng chọn ường lại qua các ường nối khác.
1.4. Các hệ khách/ ại lý
Các hệ quản trị CSDL khách / ại lý xuất hiện vào ầu những năm 90 và có ảnh hưởng rất
lớn ến công nghệ DBMS và phương thức xử lý tính toán. Ý tưởng tổng quát hết sức ơn giản:
phân biệt các chức năng cần ược cung cấp và chia những chức năng này thành hai lớp: chức
năng ại lý (server function) và chức năng khách hàng (client function). Nó cung cấp kiến trúc
hai cấp, tạo dễ dàng cho việc quản lý mức ộ phức tạp của các DBMS hiện ại và ộ phức tạp của
việc phân tán dữ liệu. 9 lOMoAR cPSD| 45349271
Đại lý thực hiện phần lớn công việc quản lý dữ liệu. Điều này có nghĩa là tất cả mọi việc
xử lý và tối ưu hoá vấn tin, quản lý giao dịch và quản lý thiết bị lưu trữ ược thực hiện tại ại lý.
Khách hàng, ngoài ứng dụng và giao diện sẽ có modun DBMS khách chịu trách nhiệm quản lý
dữ liệu ược gửi ến cho bên khách và ôi khi việc quản lý các khoá chốt giao dịch cũng có thể
giao cho nó. Kiến trúc ược mô tả bởi hình dưới rất thông dụng trong các hệ thống quan hệ, ở ó
việc giao tiếp giữa khách và ại lý nằm tại mức câu lệnh SQL. Nói cách khác, khách hàng sẽ
chuyển các câu vấn tin SQL cho ại lý mà không tìm hiểu và tối ưu hoá chúng. Đại lý thực hiện
hầu hết công việc và trả quan hệ kết quả về cho khách hàng.
Có một số loại kiến trúc khách/ ại lý khác nhau. Loại ơn giản nhất là trường hợp có một
ại lý ược nhiều khách hàng truy xuất. Chúng ta gọi loại này là nhiều khách một ại lý. Một kiến
trúc khách/ ại lý phức tạp hơn là kiến trúc có nhiều ại lý trong hệ thống ( ược gọi là nhiều khách
nhiều ại lý). Trong trường hợp này chúng ta có hai chiến lược quản lý: hoặc mỗi khách hàng tự
quản lý nối kết của nó với ại lý hoặc mỗi khách hàng chỉ biết ại lý “ruột” của nó và giao tiếp
với các ại lý khác qua ại lý ó khi cần. Lối tiếp cận thứ nhất làm ơn giản cho các chương trình ại
lý nhưng lại ặt gánh nặng lên các máy khách cùng với nhiều trách nhiệm khác. Điều này dẫn ến
tình huống ược gọi là các hệ thống khách tự phục vụ. Lối tiếp cận sau tập trung chức năng quản
lý dữ liệu tại ại lý. Vì thế sự vô hình của truy xuất dữ liệu ược cung cấp qua giao diện của ại lý.
Từ góc ộ tính logíc cả dữ liệu, DBMS khách/ ại lý cung cấp cùng một hình ảnh dữ liệu
như các hệ ngang hàng sẽ ược thảo luận ở phần tiếp theo. Nghĩa là chúng cho người sử dụng
thấy một hình ảnh về một CSDL logic duy nhất, còn tại mức vật lý nó có thể phân tán. Vì thế
sự phân biệt chủ yếu giữa các hệ khách/ ại lý và ngang hàng không phải ở mức vô hình ược
cung cấp cho người dùng và cho ứng dụng mà ở mô hình kiến trúc ược dùng ể nhận ra mức ộ
vô hình này. 1.5. Các hệ phân tán ngang hàng
Mô hình khách/ ại lý phân biệt khách và ại lý. Nhưng mô hình xử lý ngang hàng, các hệ
thống tham gia có vai trò như nhau. Chúng có thể yêu cầu vừa 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 ượ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.
CÂU HỎI CUỐI CHƯƠNG
1. Hãy phát biểu ịnh nghĩa cơ sở dữ liệu phân tán và giải thích ịnh nghĩa?
2. Anh (chị) hiểu như thế nào về Hệ Quản trị cơ sở dữ liệu phân tán? 10 lOMoAR cPSD| 45349271
3. So sánh sự giống nhau và khác nhau giữa cơ sở dữ liệu phân tán và cơ sở dữ liệu tập trung?
4. Hãy trình bày các ặc iểm của cơ sở dữ liệu phân tán?
5. Hãy trình bày hệ khách/ ại lý và hệ phân tán ngang hàng. 11 lOMoAR cPSD| 45349271 CHƯƠNG II
THIẾT KẾ CƠ SỞ DỮ LIỆU PHÂN TÁN
2.1. Các chiến lược thiết kế 12 lOMoAR cPSD| 45349271
Hình 2.1. Quá trình thiết kế từ trên xuống
2.1.1. Quá trình thiết kế từ trên xuống (top-down)
Phân tích yêu cầu: nhằm ịnh nghĩa môi trường hệ thống và thu thập các nhu cầu về dữ liệu
và nhu cầu xử lý của tất cả mọi người có sử dụng CSDL
Thiết kế khung nhìn: ịnh nghĩa các giao- diện cho người sử dụng cuối
Thiết kế khái niệm: xem xét tổng thể xí nghiệp nhằm xác ịnh các loại thực thể và mối liên
hệ giữa các thực thể.
Thiết kế phân tán: chia các quan hệ thành nhiều quan hệ nhỏ hơn gọi là phân mảnh và cấp
phát chúng cho các vị trí.
Thiết kế vật lý: ánh xạ lược ồ khái niệm cục bộ sang các thiết bị lưu trữ vật lý có sẵn tại các vị trí tương ứng.
2.1.2. Quá trình thiết kế từ dưới lên (bottom-up)
Thiết kế từ trên xuống thích hợp với những CSDL ược thiết kế từ ầu. Tuy nhiên chúng ta
cũng hay gặp trong thực tế là ã có sẵn một số CSDL, nhiệm vụ thiết kế là phải tích hợp chúng
thành một CSDL. Tiếp cận từ dưới lên sẽ thích hợp cho tình huống này. Khởi iểm của thiết kế
từ dưới lên là các lược ồ khái niệm cục bộ. Quá trình này sẽ bao gồm việc tích hợp các lược ồ
cục bộ thành khái niệm lược ồ toàn cục.
2.2. Phân mảnh dữ liệu
2.2.1. Lý do phân mảnh
Khung nhìn của các ứng dụng thường chỉ là một tập con của quan hệ. Vì thế ơn vị truy
xuất không phải là toàn bộ quan hệ nhưng chỉ là các tập con của quan hệ. Kết quả là xem tập
con của quan hệ là ơn vị phân tán sẽ là iều thích hợp duy nhất.
Việc phân rã một quan hệ thành nhiều mảnh, mỗi mảnh ược xử lý như một ơn vị, sẽ cho
phép thực hiện nhiều giao dịch ồng thời. Ngoài ra việc phân mảnh các quan hệ sẽ cho phép thực
hiện song song một câu vấn tin bằng cách chia nó ra thành một tập các câu vấn tin con hoạt tác
trên các mảnh. Vì thế việc phân mảnh sẽ làm tăng mức ộ hoạt ộng ồng thời và như thế làm tăng
lưu lượng hoạt ộng của hệ thống.
2.2.2.Các quy tắc phân mảnh úng ắn
Chúng ta sẽ tuân thủ ba quy tắc trong khi phân mảnh mà chúng bảo ảm rằng CSDL sẽ
không có thay ổi nào về ngữ nghĩa khi phân mảnh. a) Tính ầy ủ
Nếu một thể hiện quan hệ R ược phân rã thành các mảnh R1, R2,…,Rn, thì mỗi mục dữ
liệu có thể gặp trong R cũng có thể gặp một trong nhiều mảnh Ri. Đặc tính này giống như tính
chất phân rã nối không mất thông tin trong chuẩn hoá, cũng quan trọng trong phân mảnh bởi vì
nó bảo ảm rằng dữ liệu trong quan hệ R ược ánh xạ vào các mảnh và không bị mất. Chú ý rằng 13 lOMoAR cPSD| 45349271
trong trường hợp phân mảnh ngang “mục dữ liệu” muốn nói ến là một bộ, còn trong trường hợp
phân mảnh dọc, nó muốn nói ến một thuộc tính. b) Tính tái thiết ược
Nếu một thể hiện quan hệ R ược phân rã thành các mảnh R1, R2,…,Rn, thì cần phải ịnh
nghĩa một toán tử quan hệ sao cho R= Ri, Ri Fr
Toán tử thay ổi tuỳ theo từng loại phân mảnh, tuy nhiên iều quan trọng là phải xác ịnh
ược nó. Khả năng tái thiết một quan hệ từ các mảnh của nó bảo ảm rằng các ràng buộc ược ịnh
nghĩa trên dữ liệu dưới dạng các phụ thuộc sẽ ược bảo toàn. c) Tính tách biệt
Nếu quan hệ R ược phân rã ngang thành các mảnh R1, R2,…,Rn, và mục dữ liệu di nằm
trong mảnh Rj, thì nó sẽ không nằm trong mảnh Rk khác ( k≠j ). Tiêu chuẩn này ảm bảo các
mảnh ngang sẽ tách biệt (rời nhau). Nếu quan hệ ược phân rã dọc, các thuộc tính khoá chính
phải ược lặp lại trong mỗi mảnh. Vì thế trong trường hợp phân mảnh dọc, tính tách biệt chỉ ược
ịnh nghĩa trên các trường không phải là khoá chính của một quan hệ.
2.2.3 Các yêu cầu thông tin
Một iều cần lưu ý trong việc thiết kế phân tán là quá nhiều yếu tố có ảnh hưởng ến một
thiết kế tối ưu. tổ chức logic của CSDL, vị trí các ứng dụng, ặc tính truy xuất của các ứng dụng
ến CSDL, và các ặc tính của hệ thống máy tính tại mỗi vị trí ều có ảnh hưởng ến các quyết ịnh
phân tán. Điều này khiến cho việc diễn ạt bài toán phân tán trở nên hết sức phức tạp.
Các thông tin cần cho thiết kế phân tán có thể chia thành bốn loại: - Thông tin CSDL - Thông tin ứng dụng - Thông tin về mạng
- Thông tin về hệ thống máy tính
Hai loại sau có bản chất hoàn toàn ịnh lượng và ược sử dụng trong các mô hình cấp phát
chứ không phải trong các thuật toán phân mảnh
2.3. Phân mảnh ngang
Trong phần này, chúng ta bàn ến các khái niệm liên quan ến phân mảnh ngang (phân tán
ngang). Có hai chiến lược phân mảnh ngang cơ bản:
Phân mảnh nguyên thuỷ của một quan hệ ược thực hiện dựa trên các vị từ ược ịnh nghĩa trên quan hệ ó.
Phân mảnh ngang dẫn xuất là phân mảnh một quan hệ dựa vào các vị từ ược ịnh trên một quan hệ khác.
2.3.1. Các kiểu phân mảnh ngang
Phân mảnh ngang chia một quan hệ r theo các bộ, vì vậy mỗi mảnh là một tập con các bộ t của quan hệ R. 14 lOMoAR cPSD| 45349271
Phân mảnh nguyên thuỷ của một quan hệ ược thực hiện dựa trên các vị từ ược ịnh nghĩa
trên quan hệ ó. Ngược lại phân mảnh ngang dẫn xuất là phân mảnh một quan hệ dựa vào các vị
từ ược ịnh trên một quan hệ khác. Như vậy trong phân mảnh ngang tập các vị từ óng vai trò quan trọng.
Phần này sẽ xem xét các thuật toán thực hiện các kiểu phân mảnh ngang. Trước tiên chúng
ta nêu các thông tin cần thiết ể thực hiện phân mảnh ngang. 2.3.2. Yêu cầu thông tin của phân mảnh ngang
a. Thông tin về cơ sở dữ liệu
Thông tin về CSDL muốn nói ến là lược ồ toàn cục và quan hệ gốc, các quan hệ con. Trong
ngữ cảnh này, chúng ta cần biết ược các quan hệ sẽ kết lạ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 hệ, 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. Ví dụ 2.1:
Hình 2.2. Biểu diễn mối liên hệ giữa các quan hệ nhờ các ường nối
Hình 2.2 trình bày một cách biểu diễn các ường nối giữa các quan hệ. chú ý rằng hướng
của ường nối cho biết mối liên hệ một -nhiều. Chẳng hạn với mỗi chức vụ có nhiều nhân viên
giữ chức vụ ó, vì thế chúng ta sẽ vẽ một ường nối từ quan hệ CHI_TRA (Chi trả) hướng ến
NHAN_VIEN (Nhân viên). Đồng thời mối liên hệ nhiều- nhiều giữa NHAN_VIEN và DU_AN
(Dự án) ược biểu diễn bằng hai ường nối ến quan hệ THAM_GIA (Tham gia).
Quan hệ nằm tại ầu (không mũi tên) của ường nối ược gọi là chủ nhân (owner) của ường
nối và quan hệ tại cuối ường nối ( ầu mũi tên) gọi là thành viên (member). Ví dụ 2.2: 15 lOMoAR cPSD| 45349271
Cho ường nối L1 của hình 2.2, các hàm owner và member có các giá trị sau: Owner( L1 ) = CHI_TRA Member (L1) = NHAN_VIEN
Thông tin ịnh lượng cần có về CSDL là lực lượng của mỗi quan hệ R, ó là số bộ có trong
R, ược ký hiệu là card (R) b. Thông tin về ứng dụng
Để phân tán ngoài thông tin ịnh lượng ta còn cần thông tin ịnh tính cơ bản gồm các vị từ
ược dùng trong các câu vấn tin. Lượng thông tin này phụ thuộc bài toán cụ thể.
Nếu không thể phân tích ược hết tất cả các ứng dụng ể xác ịnh những vị từ này thì ít nhất
cũng phải nghiên cứu ược các ứng dụng” quan trọng” nhất.
Vậy chúng ta xác ịnh các vị từ ơn giản (simple predicate). Cho quan hệ R ( A1, A2,…, An
), trong ó Ai là một thuộc tính ược ịnh nghĩa trên một miền biến thiên D(Ai) hay Di..
Một vị từ ơn giản P ược ịnh nghĩa trên R có dạng: P: Ai θ Value
Trong ó θ {=,<,≠, ≤, >, ≥} và value ược chọn từ miền
biến thiên của Ai (value Di).
Như vậy, cho trước lược ồ R, các miền trị Di chúng ta có thể xác ịnh ược tập tất cả các vị
từ ơn giản Pr trên R.
Vậy Pr ={P: Ai θ Value }. Tuy nhiên trong thực tế ta chỉ cần những tập con thực sự của Pr .
Ví dụ 2.3: Cho quan hệ DU_AN như sau:
P1 : TenDA = “thiết bị iều khiển” P2 : NganSach ≤ 200000 Là các vị từ ơn giản..
Chúng ta sẽ sử dụng ký hiệu Pri ể biểu thị tập tất cả các vị từ ơn giản ược ịnh nghĩa trên
quan hệ Ri. Các phần tử của Pri ược ký hiệu là pij.
Các vị từ ơn giản thường rất dễ xử lý, các câu vấn tin thường chứa nhiều vị từ phức tạp
hơn, là tổ hợp của các vị từ ơn giản. Một tổ hợp cần ặc biệt chú ý, ược gọi là vị từ hội sơ cấp
(minterm predicate), ó là hội (conjunction) của các vị từ ơn giản. Bởi vì chúng ta luôn có thể
biến ổi một biểu thức Boole thành dạng chuẩn hội, việc sử dụng vị từ hội sơ cấp trong một thuật
toán thiết kế không làm mất i tính tổng quát.
Cho một tập Pri = {pi1, pi2, …, pim } là các vị từ ơn giản trên quan hệ Ri, tập các vị từ hội
sơ cấp Mi={mi1, mi2, …, miz } ược ịnh nghĩa là: Mi={mij | mij=Λ p*ik} với 1 ≤ k ≤ m, 1 ≤ j ≤ z
Trong ó p*ik=pik hoặc p*ik= ¬pik . Vì thế mỗi vị từ ơn giản có thể xuất hiện trong vị từ hội
sơ cấp dưới dạng tự nhiên hoặc dạng phủ ịnh. 16 lOMoAR cPSD| 45349271
Ví dụ 2.4: Xét quan hệ CHI_TRA: Chức vụ Lương Kỹ sư iện 40000 Phân tích hệ thống 34000 Kỹ sư cơ khí 27000 Lập trình 24000
Dưới ây là một số vị từ ơn giản có thể ịnh nghĩa ược trên quan hệ CHI_TRA. p1:
Chức vụ =” Kỹ sư iện” p2: Chức vụ =” Phân tích hệ thống ” p3:
Chức vụ =” Kỹ sư cơ khí ” p4: Chức vụ =” Lập trình ” p5:
Lương ≤ 30000 p6: Lương > 30000
Các vị từ hội sơ cấp ược ịnh nghĩa dựa trên các vị từ ơn giản này:
m1: Chức vụ=” Kỹ sư iện ”Λ Lương ≤ 30000 m2: Chức
vụ =” Kỹ sư iện ”Λ Lương > 30000 m3: ¬ (chức vụ=”
Kỹ sư iện ”) Λ Lương ≤ 30000 m4: ¬ (chức vụ=” Kỹ sư
iện ”) Λ Lương> 30000 m5: chức vụ=” Lập trình ”Λ
Lương ≤ 30000 m6: chức vụ=” Lập trình ”Λ Lương > 30000 Chú ý:
+ Phép lấy phủ ịnh không phải lúc nào cũng thực hiện ược. Ví dụ: xét hai vị từ ơn giản sau:
Cận_dưới ≤ A; A Cận_trên. Tức là thuộc tính A có miền trị nằm trong cận dưới và cận trên,
khi ó phần bù của chúng là: ¬ (Cận_dưới ≤ A); ¬ (A Cận_trên) không xác ịnh ược.
Giá trị của A trong các phủ ịnh này ã ra khỏi miền trị của A.
Hoặc hai vị từ ơn giản trên có thể ược viết lại là:
Cận_dưới ≤ A Cận_trên có phần bù là: ¬ (Cận_dưới ≤ A ≤ Cận_trên) không ịnh nghĩa
ược. Vì vậy khi nghiên cứu những vẫn ề này ta chỉ xem xét các vị từ ẳng thức ơn giản => Không
phải tất cả các vị từ hội sơ cấp ều có thể ịnh nghĩa ược. Một số trong chúng có thể vô nghĩa ối
với ngữ nghĩa của quan hệ CHI_TRA. Ngoài ra cần chú ý rằng m3 có thể ược viết lại như sau:
m3: chức vụ ≠ “Kỹ sư iện ” Λ Lương ≤ 30000
Theo những thông tin ịnh tính về các ứng dụng, ta cần biết hai tập dữ liệu.
1/ Độ tuyển hội sơ cấp: số lượng các bộ của quan hệ sẽ ược truy xuất bởi câu vấn tin ược ặc tả
theo một vị từ hội sơ cấp ã cho. chảng hạn ộ tuyển của m1 trong Thí dụ 1.6 là zero bởi vì không 17 lOMoAR cPSD| 45349271
có bộ nào trong CT thỏa vị từ này. Độ tuyển của m2 là 1. Chúng ta sẽ ký hiệu ộ tuyển của một
hội sơ cấp mi là sel (mi).
2/ Tần số truy xuất: tần số ứng dụng truy xuất dữ liệu. Nếu Q={q1, q2,....,qq} là tập các câu vấn
tin, acc (qi) biểu thị cho tần số truy xuất của qi trong một khoảng thời gian ã cho. Chú ý rằng
mỗi hội sơ cấp là một câu vấn tin. Chúng ta ký hiệu tần số truy xuất của một hội sơ cấp là acc(mi)
2.3.3. Phân mảnh ngang nguyên thuỷ
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ủ nhân 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 ≤ z.
Trong ó Fi là công thức chọn ược sử dụng ể có ược mảnh Ri. Chú ý rằng nếu Fi có dạng
chuẩn hội, nó là một vị từ hội sơ cấp (mj).
Ví dụ 2.5: Xét quan hệ DU_AN Mã DA TênDA Ngân sách Địa iểm P1 Thiết bị o ạc 150000 Montreal P2 Phát triển dữ liệu 135000 New York P3 CAD/CAM 250000 New York P4 Bảo dưỡng 310000 Paris
Chúng 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:
DU_AN 1 =σĐịa iểm=”Montreal” (DU_AN)
DU_AN 2 =σĐịa iểm=”New York” (DU_AN)
DU_AN 3 =σĐịa iểm=”Paris” (DU_AN) DU_AN 1 Mã DA TênDA Ngân sách Địa iểm P1 Thiết bị o ạc 150000 Montreal DU_AN 2 Mã DA TênDA Ngân sách Địa iểm 18 lOMoAR cPSD| 45349271 P2 Phát triển dữ liệu 135000 New York P3 CAD/CAM 250000 New York DU_AN 3 Mã DA TênDA Ngân Địa iểm sách P4 Bảo dưỡng 310000 Paris
Bây giờ chúng ta có thể ịnh nghĩa một mảnh ngang chặt chẽ và rõ ràng hơn
Mảnh ngang Ri của quan hệ R có chứa tất cả các bộ R thỏa vị từ hội sơ cấp mi 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ụ 2.6: Xét quan hệ phân mảnh DU_AN ược ưa ra trong ví dụ 2.5. Nếu tập ứng dụng Pr={Địa
iểm=”Montreal”, Địa iểm=”New York ”, Địa iểm=”Paris”, Ngân sách 200000 } thì Pr không
ầy ủ vì có một số bộ của DU_AN không ược truy xuất bởi vị từ Ngân sách 200000. Để cho
tập vị từ này ầy ủ, chúng ta cần phải xét thêm vị từ Ngân sách > 200000 vào Pr. Vậy Pr={Địa
iểm=”Montreal”, Địa iểm=”New York ”, Địa iểm=”Paris”, 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. Tất nhiên nếu ta bớt i
một vị từ bất kỳ trong Pr thì tập còn lại không ầy ủ.
Lý do cần phải ảm bảo tính ầy ủ là 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ế chúng ta 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. Đây là một ặc tính cảm tính. 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.
Ví dụ 2.7: Tập Pr ược ịnh nghĩa trong ví dụ 2.6 là ầy ủ và cực tiểu. Tuy nhiên nếu chúng ta thêm
vị từ TenDA =”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. 19 lOMoAR cPSD| 45349271
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 chúng ta 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 vấn tin. Vậy khi cho trước
một tập vị từ Pr ể xét tính cực tiểu chúng ta có thể kiểm tra bằng cách vứt bỏ những vị từ thừa
ể có tập vị từ Pr’ là cực tiểu và tức nhiên 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. Chúng ta tạm quy ước:
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 2.1 COM_MIN
Input : R: quan hệ; Pr: tậpcác vị từ ơn giản; Output:
Pr’: tập các vị từ cực tiểu và ầy ủ; Declare
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 p; {fi là mảnh hội sơ cấp theo pi }
End; {Chúng ta ã chuyển các vị từ có phân mảnh R 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 20