[TÌM HIỂU MỘT SỐ THUẬT TOÁN PHÂN MẢNH TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN]
MỤC LỤC
1 | P a g e
[TÌM HIỂU MỘT SỐ THUẬT TOÁN PHÂN MẢNH TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN]
1. Tổng quan về cơ sở dữ liệu phân tán
1.1 Giới thiệu
Cơ sở dữ liệu phân tán (CSDLPT) là sự hợp nhất của hai cách tiếp cận xử lý dữ
liệu dường như đối lập nhau: công nghệ cơ sở dữ liệu (CSDL) và công nghệ mạng máy
tính. Một trong những mục đích, động cơ chính của việc sử dụng các hệ CSDL là việc
tích hợp các dữ liệu, giao tác của một xí nghiệp, tổ chức và cho phép truy xuất tập
trung, do vậy có thể điều khiển được các truy xuất đến dữ liệu đó. Còn công nghệ mạng
lại đi ngược lại với mọi nỗ lực tập trung hóa.
Mấu chốt của vấn đề là mục tiêu quan trọng của công nghệ CSDL là sự tích hợp
mà không phải là sự tập trung hóa, như vậy ta vẫn có thể có được sự tích hợp mà không
cần sự tập trung hóa và đó chính là mục tiêu của CSDLPT.
Chúng ta có thể định nghĩa một CSDLPT là một tập hợp nhiều CSDL có liên đới
logic và được phân bố trên một mạng máy tính. Vậy hệ quản trị CSDLPT được định
nghĩa là một hệ thống phần mềm cho phép quản lý các CSDLPT, và làm cho việc phân
tán trở nên trong suốt đối với người sử dụng.
Với các hệ CSDLPT chúng ta dễ dàng nhận thấy những ưu điểm tiềm năng như
sau:
− Quản trị dữ liệu phân tán với nhiều mức trong suốt khác nhau. Hệ quản trị CSDLPT
cung cấp khả năng trong suốt phân tán (distribution transparent) với ý nghĩa là che
dấu các chi tiết như dữ liệu được lưu trữ ở đâu trong hệ thống… Hệ quản trị CSDL
PT có thể cung cấp các khả năng trong suốt sau:
 Trong suốt phân tán, hay trong suôt mạng
 Trong suốt nhân bản
 Trong suốt phân mảnh
− Tăng tính tin cậy và tính sẵn sàng.
− Cho phép dùng chung dữ liệu trong khi vẫn duy trì được biện pháp điều khiển cục
bộ.

Một CSDLPT thuần nhất (homogeneous DDB) có được bằng cách chia một CSDL
thành một tập các CSDL cục bộ, mỗi CSDL cục bộ này được quản trị bởi cùng một hệ
quản trị CSDL. Một CSDLPT thuần nhất thường là kết quả của cách tiếp cận thiết kế
trên xuống, trong đó ta thiết kế một CSDLPT từ một CSDL tập trung.
Một CSDLPT không thuần nhất (heterogeneous DDB) là một CSDLPT có được
bằng cách tích hợp một tập các CSDL cục bộ (có thể được xây dựng từ các mô hình dữ
liệu khác nhau) được quản trị bởi các hệ quản trị CSDL khác nhau, thành một CSDL
duy nhất.
1.3 Mục tiêu của hệ quản trị cơ sở dữ liệu phân tán
Sự độc lập dữ liệu và trong suốt phân bố. Người dùng có thể không quan tâm đến
sự phân tán dữ liệu. Các thông tin này được lưu giữ trong từ điển dữ liệu (catalog), và
được hệ quản trị CSDLPT sử dụng để định vị dữ liệu. Đây là một dạng trong suốt cơ
bản cần có trong một hệ CSDLPT, nó liên quan đến tính độc lập dữ liệu (data
independence) và làm tăng khả năng thích ứng của các ứng dụng đối với những thay
đổi trong định nghĩa và tổ chức của dữ liệu và ngược lại. Khi đó không có sự khác biệt
nào giữa các ứng dụng chạy trên CSDL tập trung với ứng dụng chạytrên CSDLPT.
Trong suốt phân mảnh. Việc truy cập tới dữ liệu thường được xác định trên các
quan hệ con (thu được từ việc chia nhỏ các quan hệ gốc) được gọi là các mảnh
(fragment). Việc phân mảnh (ngang, dọc, hỗn hợp) làm tăng hiệu năng, tính sẵn sàng,
độ tin cậy của CSDLPT. Trong suốt phân mảnh che dấu sự phân đoạn đối với người
dùng.
Trong suốt nhân bản. Một giải pháp cho sự tin cậy dữ liệu là việc tạo ra dư thừa
dữ liệu dưới một hình thức nào đó. Mỗi mảnh dữ liệu được sao lưu thành hai hay nhiều
bản, mỗi bản được lưu trên một trạm khác nhau, được gọi là sự nhân bản. Nó giúp hệ
CSDLPT nâng cao hiệu năng, độ tin cậy và tính sẵn sàng. Tuy nhiên việc nhân bản sẽ
gây khó khăn cho việc cập nhật CSDL, và việc duy trì và quản lý các bản sao là phức
tạp và tốn kém. Việc trong suốt nhân bản là việc che dấu khiến người dùng chỉ nhìn
thấy các quan hệ không có nhân bản.
Tính trong suốt đối với hệ quản trị CSDL. Cho phép che dấu đối vói người dùng
việc các hệ quản trị CSDL cục bộ có thể khác nhau.

định xem các câu truy vấn có xử lý được hay không.
− Bộ tối ưu truy vấn toàn cục (Global query optimizer) xác định một chiến lược hoạt
động để giảm thiểu chi phí, và phiên dịch các câu truy vấn toàn cục thành câu truy
vấn cục bộ thông qua việc sử dụng các lược đồ toàn cục, khái niệm cục bộ và thư
mục toàn cục, ngoài ra còn chịu trách nhiệm tạo ra một chién lược thực thi tốt cho
các phép nối phân tán.
− Bộ theo dõi hoạt động toàn cục (Global execution Monitor) có trách nhiệm điều
phối việc thực hiện phân tán các yêu cầu của người dùng và cũng được gọi là bộ
quản lý giao dịch phân tán (Distributed transaction manager).
Thành phần thứ hai gồm:
− Bộ tối ưu truy vấn cục bộ (Local query processor) chịu trách nhiệm chọn ra một
đường truy xuất thích hợp nhất để truy xuất các dữ liệu.
− Bộ khôi phục cục bộ (Local recovery manager) đảm bảo cho các CSDL cục bộ duy
trì được tính nhất quán khi có sự cố xảy ra.
− Bộ hỗ trợ thực thi (Runtime support processor) truy xuất CSDL tùy vào các lệnh
trong lịch (schedule) do bộ tối ưu vấn tin sinh ra. Nó là giao diện với bộ điều hành
và chứa bộ quản lý vùng đệm CSDL (database buffer manager), chịu trách nhiệm
quản lý vùng đệm và quản lý việc truy xuất dữ liệu.
Một điểm lưu ý là hai thành phần này chỉ là phân chia về mặt tổ chức chứ không
phải bắt buộc phải cài đặt trên các trạm khác nhau. Tuy nhiên cũng có những gợi ý tách
biệt những trạm chỉ thực hiện truy vấn ra khỏi những hệ thống có đầy đủ chức năng, và
khi đó các trạm này chỉ cần có bộ xử lý tiếp nhận người dùng.
6 | P a g e
[TÌM HIỂU MỘT SỐ THUẬT TOÁN PHÂN MẢNH TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN]
Hình 1.4 Các thành phần của một hệ quản trị CSDLPT
2. Các kiểu phân mảnh trong cơ sở dữ liệu phân tán
2.1. Cơ sở dữ liệu mẫu
Bảng EMP (employee – nhân viên) gồm các thuộc tính ENO (employee number – mã
số nhân viên); ENAME (employee name – tên nhân viên); TITLE (chức vụ).
ENO ENAME TITLE

Bảng PAY gồm các thuộc tính TITLE (chức vụ); SAL (salary – lương).
TITLE SAL
Elect. Eng. 40000
Syst. Anal. 34000
Mech. Eng. 27000
Programmer 24000
2.2. Phân mảnh ngang
Phân mảnh ngang là phân mảnh chia một quan hệ theo các bộ, mỗi mảnh là một
tập con của quan hệ.
8 | P a g e
[TÌM HIỂU MỘT SỐ THUẬT TOÁN PHÂN MẢNH TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN]
Hình 2.1 Minh họa phân mảnh ngang
Ví dụ: Quan hệ PROJ có thể được chia thành hai quan hệ con là PROJ
1
chứa các thông
tin về các dự án có ngân sách dưới 200000 đô la; quan hệ con PROJ
2
lưu các thông tin
về các dự án có ngân sách lớn hơn 200000 đô la.
PROJ
1
PNO PNAME BUDGET LOC
P1 Instrumentation 150000 Montreal
P2 Database Develop 135000 New York
PROJ
2
PNO PNAME BUDGET LOC
P3 CAD/CAM 250000 New York
P4 Maintenance 310000 Paris
2.3. Phân mảnh dọc

phân mảnh dọc có thể được thực hiện sau một phân mảnh ngang hoặc ngược lại, sinh ra
một lối phân hoạch có cấu trúc cây. Bởi vì hai chiến lược này được áp dụng lần lượt,
chọn lựa này được gọi là phân mảnh hỗn hợp.
10 | P a g e
[TÌM HIỂU MỘT SỐ THUẬT TOÁN PHÂN MẢNH TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN]
Hình 2.3 Minh họa phân mảnh hỗn hợp
Ví dụ: Quan hệ PROJ có thể phân hoạch thành 4 mảnh ngang: PROJ
1
chứa thông tin về
dự án ở Montreal và có ngân sách nhỏ hơn hoặc bằng 200000 đô la; PROJ
2
chứa thông
tin về dự án ở New York và có ngân sách nhỏ hơn hoặc bằng 200000 đô la; PROJ
3
chứa
thông tin về dự án ở New York và có ngân sách lớn hơn 200000 đô la và PROJ
4
chứa
thông tin về dự án ở Paris và có ngân sách lớn hơn 200000 đô la. Mỗi mảnh ngang lại
được phân thành 2 mảnh dọc: PROJ
11
chứa thông tin về ngân sách các dự án trong
PROJ
1
; PROJ
12
chứa tên và vị trí các dự án trong PROJ
1
; PROJ
21

PROJ
12
PNO PNAME LOC
P1 Instrumentation Montreal
PROJ
21
PNO BUDGET
P2 135000
11 | P a g e
[TÌM HIỂU MỘT SỐ THUẬT TOÁN PHÂN MẢNH TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN]
PROJ
22
PNO PNAME LOC
P2 Database Develop New York
PROJ
31
PNO BUDGET
P3 250000
PROJ
32
PNO PNAME LOC
P3 CAD/CAM New York
PROJ
41
PNO BUDGET
P4 310000
PROJ
42
PNO PNAME LOC
P4 Maintenance Paris

A,B
(R)
Chú ý rằng kết quả chiếu có thể chứa các bộ giống nhau. Trong trường hợp đó,
các bộ trùng lặp có thể được xóa khỏi quan hệ kết quả. Chúng ta có thể cho phép chiếu
loại bỏ trùng lặp hoặc không.
Ví dụ: Chiếu quan hệ PROJ trên các thuộc tính PNO và BUDGET cho kết quả như sau:
π
PNO,BUDGET
(PROJ)
PNO BUDGET
P1 150000
P2 135000
P3 250000
P4 310000
3.3 Tích Descartes
Tích Descartes của 2 quan hệ k
1
ngôi R và quan hệ k
2
ngôi S là tập các (k
1
+k
2
) bộ,
với mỗi bộ là kết quả nối một bộ của R với một bộ của S, được thực hiện cho tất cả các
bộ của R và S. Tích Descartes của R và S được viết là RxS.
Ví dụ: Xét các quan hệ EMP và PAY. Tích Descartes EMP x PAY được thể hiện trong
bảng sau:
EMP x PAY
ENO ENAME EMP.TITLE PAY.TITLE SAL

EMP.TITLE=PAY.TITLE
PAY
ENO ENAME TITLE SAL
E1 J.Doe Elect. Eng. 40000
E2 M.Smith Syst. Anal. 34000
E3 A. Lee Mech. Eng. 27000
E4 J. Miller Programmer 24000
E5 B.Casey Syst. Anal. 34000
E6 L. Chu Elect. Eng. 40000
E7 R. David Mech. Eng. 27000
E8 J. Jones Syst. Anal. 34000
Ví dụ trên minh họa một trường hợp đặc biệt của nối-θ được gọi là nối bằng.
Trong trường hợp này, công thức F chỉ chứa đẳng thức (=) làm toán tử so sánh.
Chú ý: Nối tự nhiên là một nối bằng của hai quan hệ trên một thuộc tính cụ thể, đặc
biệt là trên các thuộc tính có cùng một miền biến thiên.
4. Thuật toán phân mảnh ngang
4.1 Yêu cầu thông tin
4.1.1 Thông tin về cơ sở dữ liệu
− Mối liên hệ giữa các quan hệ được biểu diễn bằng một đồ thị nối. Quan hệ
nằm tại đuôi của đường nối gọi là quan hệ chủ nhân (owner), quan hệ tại đầu
đường nối (đầu mũi tên) gọi là thành viên (member).
14 | P a g e
[TÌM HIỂU MỘT SỐ THUẬT TOÁN PHÂN MẢNH TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN]
Hình 4.1 Biểu diễn mối liên hệ giữa các quan hệ bằng các đường nối
Cho đường nối L
1
của hình 4.1, các hàm owner và member có các giá trị như
sau:
owner(L
1

1
, p
2
, …, p
m
}.
Ví dụ: các vị từ đơn giản:
PNAME = "Maintenance"
BUDGET ≤ 200000
− Vị từ hội sơ cấp (minterm predicate): Là hội của các vị từ đơn giản. Cho R và
Pr = {p
1
, p
2
, …, p
m
}. Tập các vị từ hội sơ cấp M
i
= {m
1
,m
2
,…, m
r
} được định
nghĩa là:
M
i
={m
i

− Độ tuyển hội sơ cấp (minterm selectivity): Số các bộ (tuple) của quan hệ được
câu truy vấn truy cập. Câu truy vấn được chỉ định bằng minterm predicate m
i
.
ký hiệu độ tuyển hội sơ cấp m
i
là sel(m
i
).
Ví dụ:
Độ tuyển hội của vị từ hội sơ cấp m
1
: TITLE=”Elect. Eng.” ˄
SAL≤30000 là 0 bởi vì không có bộ nào trong PAY thỏa vị từ này.
Độ tuyển hội của vị từ hội sơ cấp m
2
: TITLE=”Elect. Eng.” ˄
SAL>30000 là 1 bởi vì có 1 bộ trong PAY thỏa vị từ này.
− Tần số truy xuất (access frequency): Tần số ứng dụng truy xuất dữ liệu. Nếu
Q={q
1
, q
2
, …, q
q
} là tập các câu vấn tin, acc(q
i
) biểu thị cho tần số truy xuất
của qi trong một khoảng thời gian đã cho. Ta cũng có thể xác định tần số truy
xuất cho một vị từ hội sơ cấp là acc(m

về một mảnh hội sơ cấp nào đó được định nghĩa theo Pr đều bằng nhau.
− Tính cực tiểu (minimality) của vị từ đơn giản: Nếu tất cả các vị từ của tập Pr đều có
liên đới thì Pr là cực tiểu.
− Tính liên đới (relevant): Gọi m
i
và m
j
là hai vị từ hội sơ cấp đồng nhất về định
nghĩa, ngoại trừ mi chứa vị từ đơn giản p
i
ở dạng tự nhiên còn m
j
chứa p
i
ở dạng
phủ định ¬p
i
. Gọi f
i
và f
j
là hai mảnh tương ứng được định nghĩa theo m
i
và m
j
. Thế
thì p
i
là có liên đới nếu và chỉ nếu:
− 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

là mảnh hội sơ cấp theo p
i
}
Do
Begin
Tìm một p
j
∈
Pr sao cho p
j
phân hoạch một mảnh f
k
của Pr’ theo quy tắc 1
Pr’

Pr’
∪
p
j
Pr

Pr – p
j
F

F
∪
f
i
If p


∈
Pr’
For mỗi m
i
∈
M do
If m
i
mâu thuẫn với I then
M

M – m
i
End-if
End-for
End. {PHORIZONTAL}
4.3 Phân mảnh ngang dẫn xuất
− Định nghĩa: Phân mảnh ngang dẫn xuất được định nghĩa dựa trên một quan hệ
thành viên của một đường nối dựa theo phép toán chọn trên quan hệ chủ nhân của
đường nối đó. Đường nối giữa quan hệ chủ nhân và thành viên được định nghĩa là
một nối bằng (equijoin), nối bằng có thể cài đặt nhờ các nối nửa (semijoin). Cho
trước một đường nối L, trong đó owner(L)=S và member(L)=R, các mảnh ngang
dẫn xuất của R được định nghĩa là:
R
i
= R S
i
, 1≤i≤w
trong đó w là số lượng các mảnh được định nghĩa trên R, và S

2
: SAL < 27000
Kết quả chương trình cho ta 3 mảnh:
PAY
1
TITLE SAL
Elect. Eng. 40000
Syst. Anal. 34000
PAY
2
TITLE SAL
Programmer 24000
PAY
3
TITLE SAL
Mech. Eng. 27000
19 | P a g e
[TÌM HIỂU MỘT SỐ THUẬT TOÁN PHÂN MẢNH TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN]
5.3 Phân mảnh ngang nguyên thủy trên quan hệ PROJ
Các vị từ đơn giản nhập vào cho chương trình:
p
1
: LOC = “Montreal”
p
2
: LOC = “New York”
p
3
: LOC = “Paris”
p

6.1.1 Giá trị sử dụng thuộc tính (attribute usage value)
Yêu cầu dữ liệu chính có liên quan đến các ứng dụng là tần số truy xuất của
chúng. gọi Q={q
1
, q
2
,…,q
q
} là tập các vấn tin của người dùng (các ứng dụng) sẽ chạy
trên quan hệ R(A
1
, A
2
,…,A
n
). Thế thì với mỗi câu vấn tin qi và mỗi thuộc tính A
j
,
chúng ta sẽ đưa ra một giá trị sử dụng thuộc tính, ký hiệu use(q
i
, A
j
) được định nghĩa
như sau:
1 nếu thuộc tính A
j
được vấn tin q
i
tham chiếu
use(q

(q
k
)acc
l
(q
k
)
use(q
k
, A
i
)=1 ∧ use(q
k
, A
j
)=1 ∀R
l
trong đó ref
l
(q
k
) là số truy xuất đến các thuộc tính (A
i
, A
j
) cho mỗi ứng dụng q
k
tại vị
trí R
l

Xuất: CA - ma trận ái lực tụ;
Begin
{Khởi gán: cần nhớ rằng AA là một ma trận n x n}
CA(
•
, 1)
←
AA(
•
, 1)
CA(
•
, 2)
←
AA(
•
, 2)
Index
←
3
while index <= n do {chọn vị trí “tốt nhất” cho thuộc tính AA
index
}
begin
for i :=1 to index-1 by 1 do
tính cont(A
i-1
, A
index
, A

end-while
Sắp thứ tự các hàng theo thứ tự tương đối của cột.
end. {BEA}
6.3 Thuật toán phân hoạch
22 | P a g e
[TÌM HIỂU MỘT SỐ THUẬT TOÁN PHÂN MẢNH TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN]
Thuật toán PARTITION
Nhập: CA: ma trận ái lực tụ; R: quan hệ; ref: ma trận sử dụng thuộc tính;
acc: ma trận tần số truy xuất;
Xuất: F: tập các mảnh;
Begin
{xác định giá trị z cho cột thứ nhất}
{các chỉ mục trong phương trình chi phí chỉ ra điểm tách}
tính CTQ
n-1
tính CBQ
n-1
tính COQ
n-1
best
←
CTQ
n-1
*CBQ
n-1
– (COQ
n-1
)
2
do {xác định cách phân hoạch tốt nhất}

23 | P a g e
[TÌM HIỂU MỘT SỐ THUẬT TOÁN PHÂN MẢNH TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN]
Xây dựng lại ma trận theo vị trí xê dịch
R
1

←∏
TA
(R)
∪
K {K là tập thuộc tính khoá chính của R}
R
2

←∏
BA
(R)
∪
K
F
←
{R
1
, R
2
}
End. {PARTITION}
7. Chương trình minh họa thuật toán phân mảnh dọc
7.1 Giao diện chương trình
Chương trình có các chức năng sau:

3
=BUDGET; A
4
=LOC
- Nhập các giá trị cho ma trận tần số truy cập
25 | P a g e