Trường Đại học Công Nghệ Thông Tin
Đại học quốc gia TP. Hồ Chí Minh
Thiết kế Cơ sở dữ liệu
phân tán
***
HV: Lương Chấn Viễn
MHV: CH1101155
Môn: Cơ sở dữ liệu nâng cao
GV: PGS.TS. Đỗ Phúc
MỤC LỤC
Quá trình thiết kế top-down
Các vấn đề của thiết kế phân tán
1. LÝ DO PHÂN MẢNH
2. CÁC KIỂU PHÂN MẢNH
3. TÍNH ĐÚNG ĐẮN CỦA PHÂN MẢNH
4. CÁC KIỂU CẤP PHÁT
Phương pháp phân mảnh
1. PHÂN MẢNH NGANG
2. PHÂN MẢNH DỌC
Chương trình DEMO
2
2
2
Việc thiết kế một hệ thống máy tính phân tán liên quan đến việc đưa quyết định về vị
trí đặt dữ liệu và chương trình trên các miền của một mạng máy tính, cũng như thiết
kế cả chính hệ thống mạng đó. Trong trường hợp hệ thống cần thiết kế là một hệ
quản trị cơ sở dữ liệu phân tán (distributed DBMSs), thì bài toán đặt ra là: việc phân
tán của hệ quản tri CSDL và phân tán của những chương trình ứng dụng chạy trên hệ
phân tán đó.
Việc tổ chức hệ thống phân tán có thể biểu diễn trên hệ trục toạ độ 3 chiều như sau:
1. Chiều biểu diễn về mức độ chia sẻ của dữ liệu

design) và thiết kế khái niệm (concept design). Việc thiết kế view nhằm định nghĩa
những giao diện tương tác với người dùng cuối. Trong khí đó, việc thiết kế khái niệm
xác định những loại thực thể (entity type) và quan hệ giữa những thực thể đó. Trong
thiết kế khái niệm gồm 2 phần: phân tích thực thể (entity analysis) và phân tích tính
năng (functional analysis) liên quan với nhau. Phân tích thực thể yêu cầu ta xác định
về cấu trúc thực thể như thuộc tính (attributes) và quan hệ giữa chúng với nhau. Phân
tích tính năng là để xác định nhưng chức năng cơ bản liên quan đến mô hình trên. 2
phần này cần được tham chiếu chéo với nhau một cách rõ ràng.
4
4
4
Liên hệ giữa việc thiết kế view với thiết kế khái niệm thể hiện thông qua việc tích
hợp view (view intergration). Chú ý rằng mô hình khái niệm không những phải có
khả năng tích hợp được với những ứng dụng hiện tại, mà ta còn phải xem xét đến
những ứng dụng được đưa ra sau này. Quá trình tích hợp viem cần bảo đảm rằng yêu
cầu về thực thể và quan hệ cho những view được bao phủ với sơ đồ khái niệm.
Không những những thông tin về dữ liệu thực thể và những ứng dụng chạy trên đó
được cung cấp, ta còn cần những số liệu thống kê về như tần suất sử dụng của ứng
dụng… Những quá trình trên tương ứng với việc thiết kế của một hệ CSDL tập trung.
Khi sơ đồ khái niệm toàn cục GCS (Global cemceptual schema) và thông tin về kiểu
mẫu truy cập được thu thập, bước tiếp theo ta tiến đến việc thiết kế phân tán
(Distributed Design). Mục tiêu của giai đoạn này, cũng chính là phần trình bày của
bài báo cáo, là thiết kế những sơ đồ khái niệm cục bộ LCSs (Local conceptual
schemas) bởi việc phân tán các thực thể trên các site của hệ thống phân tán.
Việc phân tán không chỉ dừng ở mức phân tán các quan hệ, mà còn chia nhỏ chúng ta
thành các “mảnh” (fragments) và phân tán những mảnh đó. Khi đó việc thiết kế gồm
2 bước: phân mảnh và bố trí các mảnh.
Bước cuối cùng của việc thiết kế là thiết kế vật lý (physical design) tức ánh xạ các sơ
đồ khái niệm cục bộ được tìm ra ở bước trước vào các thiết bị lưu trữ vật lý tương
ứng ở mỗi site.

tương ứng với các mảnh.
2.2 CÁC KIỂU PHÂN MẢNH
Có hai cách phân mảnh: phân mảnh theo chiều ngang, phân mảnh theo chiều dọc.
Ví dụ: Xét CSDL như sau:
6
6
6
Ta có thể tách theo chiều nganh quan hệ PROJ thành 2 quan hệ PROJ
1
chứa các
thông tin về dự án có kinh phí dưới 200000 USD, và PROJ
2
chứa các thông tin về dự
án có kinh phí lớn hơn 200000 USD.
Hay tách quan hệ PROJ theo chiều dọc (giữ nguyên thuộc tính khoác) thành 2 quan
hệ PROJ
1
chứa các thông tin về kinh phí dự án, và PROJ
2
chứa các thông tin về tên
và vị trí dự án.
7
7
7
Ngoài ra, ta có thể lồng ghép nhiều phân mảnh trên 1 quan hệ. Nếu lồng ghép 2 kiểu
phân mảnh khác nhau thì ta gọi là phân mảnh hỗn hợp (hybrid fragmentation).
2.3 TÍNH ĐÚNG ĐẮN CỦA PHÂN MẢNH
TÍNH ĐẦY ĐỦ (COMPLETENESS)
Cho quan hệ bất kỳ. Giả sử được phân mảnh thành các mảnh . Khi đó tính đầy đủ
yêu cầu mỗi mục dữ liệu trong có thể tìm thấy trong 1 mảnh trong các mảnh của .

quan hệ dựa trên vị từ định nghĩa theo một quan hệ khác. Trước khi thực hiện phân
mảnh, chúng ta cần thu thập thông tin cần thiết.
3.1.1 YÊU CẦU THÔNG TIN
THÔNG TIN VỀ CSDL
Thông tin này bao gồm lược đồ khái niệm toàn cục.Trong trường hợp này, ta chú ý
đến các liên kết giữa các quan hệ, đặc biệt là phép nối. Trong mô hình thực thể quan
hệ, các liên kết này biểu diễn bởi mũi tên từ quan hệ đến quan hệ
trong đó gọi là owner, gọi là member: , .
Ví dụ: liên kết có và .
THÔNG TIN VỀ ỨNG DỤNG
Yêu cầu thông tin của ứng dụng gồm cả thông tin định tính lẫn định lượng. Thông tin
định tính định hướng cho việc phân mảnh, trong khi thông tin định lượng được sử
dụng chủ yếu trong mô hình cấp phát. Những thông tin định tính cơ bản gồm các vị
từ được câu truy vấn của người dùng.
9
9
9
Cho quan hệ trong đó là các thuộc tính của quan hệ. Một vị từ đơn có dạng
trong đó toán tử , và với là miền xác định của . Ví dụ: PNAME=”Maintenance”,
BUGET ≤ 200.000.
Các câu truy vấn thường xây dựng từ các vị từ đơn giản bởi các toán tử Boolean. Ở
đây, ta gọi một vị từ là vị từ hội sơ cấp (minterm predicate), nếu vị từ có thể xây
dựng dựa trên phép hội của các vị từ đơn giản. Bởi vì ta luôn có thể biến đổi một biểu
thức bool thành dạng chuẩn hội (conjuctive normal form) nên việc sử dụng vị từ hội
sơ cấp trong thuật toán thiết kế không làm mất tính tổng quát.
Cho tập các vị từ đơn cho trước , ta định nghĩa tập các vị từ hội tối tiểu (minterm
predicates) là:
Trong đó .
Ví dụ:
: PNAME=”Maintencance”

định phân mảnh, nếu nó ảnh hưởng đến việc mảnh bị phân thành và thì phải có ít
nhất một ứng dụng truy xuất đến và có xác suất khác nhau.
Nếu tất cả các vị từ trong đều có liên ứng thì là tối tiểu.
Qui tắc 1: Một quan hệ hoặc một mảnh được phân hoạch thành ít nhất hai phần khác
nhau và được ít nhất một ứng dụng truy cập các bộ ới xác suất khác nhau.
THUẬT TOÁN COM_MIN
Input: quan hệ , tập các vị từ đơn
Output: tập các vị từ đơn đầy đủ và tối tiểu
Khởi tạo:
- Tìm sao cho phân hoạch theo quy tắc 1.
-
-
-
Lặp
- Tìm sao cho phân hoạch theo quy tắc 1
-
-
- Nếu không liên ứng thì loại ra khỏi
Cho đến khi đầy đủ
Tiếp theo ta suy ra tập các vị từ hội sơ cấp định nghĩa bởi tập vừa tìm được.
THUẬT TOÁN PHORIZONTAL
Input: quan hệ , tập các vị từ đơn đầy đủ và tối tiểu
Output: tập các vị từ hội tối tiểu .
Xác định tập các vị từ hội tối tiểu
Xác định tập các phép kéo theo giữa các vị từ đơn .
Khử các minterm mẫu thuẫn ra khỏi .
3.1.3 PHÂN MẢNH NGANG ĐƯỢC SUY
11
11
11

Khi đó ta có thể xây dựng ma trận ái lực mà mỗi phần tử ở dòng cột là .
3.2.2 THUẬT TOÁN GOM NHÓM
Nhiệm vụ cơ bản trong việc xây dựng thuật toán phân mảnh dọc là tìm cách nào đó
để nhóm các thuộc tính của quan hệ dựa trên ma trận ái lực. Ta cần tìm hoán vị các
hàng và cột ma trận ái lực để tạo thành ma trận CA (clustered affinity matrix) sao cho
số đo ái lực toàn cục AM (global affinity measure) là lớn nhất. Ta định nghĩa:
12
12
12
Vì ma trận ái lực đối xứng nên
Và ta có thể viết thành
Ta định nghĩa:
Khi đó ta có thể viết
Ta xem là một hàm . Với một thứ tự các thuộc tính tính như sau:
Khi đó ta có thể viết
Nếu ta thêm cột vào giữa và thì
Khi đó ta gọi lượng đóng góp tịnh (net contribution) khi thêm vào vị trí giữa và là
Khi đó ta cần tìm vị trí chèn sao cho .
THUẬT TOÁN BEA
Input: ma trận affinity .
Output: ma trận
Khởi tạo: cố định 2 cột bất kỳ từ vào .
Với mỗi cột còn lại
- Tìm vị trí sao cho là lớn nhất
- Chèn vào vị trí
Xem ví vụ ở phần chương trình demo.
3.2.3 THUẬT TOÁN PHÂN HOẠCH
Mục đích của việc phân mãnh dọc là tìm những tập thuộc tính được truy xuất cùng
nhau bởi các ứng dụng. Ta có thể tách các thuộc tính thành tập con. Ở đây, ta chỉ xét
việc tách thành 2 tập con.

15
15
Trong đó phần nhập dữ liệu đầu vào yêu cầu nhập số lượng các thuộc tính của quan
hệ , số lượng các câu lệnh truy vấn và số các site của hệ thống phân tán. Chương
trình quy ước các thuộc tính của quan hệ của là và các câu truy vấn . Yêu cầu về
thông tin ứng dụng còn có ma trận và ma trận ACC. Do trong thuật toán BEA lúc
khởi tạo cố định 2 cột tương ứng với 2 thuộc tính và , vì thế, người dùng có thể chọn
2 thuộc tính tương ứng với 2 cột cố định ban đầu.
Phần trình bày lời giải sẽ trả trình bày gồm các phần:
- yêu cầu thông tin: viết lại ma trân và ma trận từ dữ liệu đầu vào cũng như
tính tổng tần suất truy cập trên các site của truy vấn . Ở đây quy ước .
- Xây dựng ma trận với các phần tử . Người dùng có thể xem các phép tính
cụ thể bằng cách nhấn vào “cụ thể”.
- Quá trình xây dựng ma trận gom cụm bằng thuật toán BEA. Chương trình
trình bày mỗi bước chèn cột vào ma trận trước đó cũng như các net
Solve
Solve
4
4
3
1 0 1 0
0 1 1 0
0 1 0 1
0 0 1 1
15 20 10
5 0 0
25 25 25
3 0 0
Chọn 2 cột thuộc tính ban đầu:
A1