[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ộ.

− Cải tiến hiệu năng.
− Tính dễ mở rộng.
1.2 Khái niệm cơ sở dữ liệu phân tán
Ở mức phần cứng vật lý, những nhân tố chính phân biệt một hệ CSDLPT với một
hệ CSDL tập trung là:
− Có nhiều máy tính duợc gọi là trạm hay nút (node)
− Các trạm phải duợc kết nối bởi một kiểu mạng truyền thông nào dó dể truyền dữ
liệu và các lệnh giữa các trạm.
2 | 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.1 CSDL trung tâm trên một mạng
Hình 1.2 Môi truờng của hệ CSDLPT
Một hệ quản trị CSDLPT là một tập các phần mềm hệ thống bao gồm các phần
mềm quản trị các dữ liệu phân tán, các phần mềm quản trị truyền thông và các hệ quản
trị CSDL địa phương/cục bộ lưu trú trên mỗi trạm của hệ CSDLPT.
Ngoài chức năng của các hệ quản trị CSDL và của phần mềm quản trị truyền
thông, hệ quản trị CSDLPT còn có các chức năng đặc biệt sau:
− Quản lý một từ điển dữ liệu tổng thể lưu trữ thông tin liên quan đến các dữ liệu
phân tán.
− Định nghĩa các dữ liệu phân tán.
− Kiểm tra ngữ nghĩa của các dữ liệu phân tán.
− Định giá các câu truy vấn phân tán do người dùng đưa ra.
− Quản lý các giao tác phân tán.
− Bảo mật giao tác và dữ liệu.
3 | 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]
− Phục hồi CSDL phân tán, cung cấp khả năng phục hồi dữ liệu từ những trạm (site)
bị lỗi (sập).
− Quản trị nhân bản dữ liệu.
Một tính chất quan trọng của các CSDLPT là tính thuần nhất hay không thuần nhất.

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.

Tính tự trị của các trạm. Đây là mục tiêu cho phép mỗi trạm điều khiển và thao
tác dữ liệu địa phương của nó độc lập với các trạm khác. Do đó việc quản trị của
CSDLPT có thể hoàn toàn phi tập trung.
Tính mở rộng. Là khả năng mở rộng bằng việc đưa thêm các trạm mới vào mạng
với ảnh hưởng tối thiểu lên các CSDL cục bộ và các chương trình ứng dụng hiện có.
1.4 Kiến trúc của hệ quản trị cơ sở dữ liệu phân tán.
4 | 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]
Các hệ phân tán ngang hàng. Tổ chức vật lý trên mỗi máy có thể rất khác nhau,
do đó ta cần phải có một định nghĩa tổ chức dữ liệu vật lý cho mỗi trạm, mà chúng ta
gọi là lược đồ trong cục bộ (LIS). Hình ảnh về toàn thể CSDL được mô tả bởi lược đồ
khái niệm toàn cục (GCS), nó mô tả cấu trúc logic của dữ liệu ở mọi vị trí. Để xử lý
việc phân mảnh và nhân bản ta sử dụng lược đồ khái niệm cục bộ (LCS), mô tả tổ chức
logic của dữ liệu tại mỗi trạm. Do đó trong kiến trúc này lược đồ khái niệm toàn cục là
“hợp” của các lược đồ khái niệm cục bộ. Và các ứng dụng truy xuất dữ liệu thông qua
lược đồ ngoài (ES), được định nghĩa là một tầng nằm trên lược đồ khái niệm toàn cục.
Các khái niệm trên được mô tả trong hình 1.3.
Các thành phần cụ thể của một hệ CSDLPT. Ở đây hệ quản trị CSDLPT gồm 2
thành phần (mô tả trong Hình 1.4). Một thành phần xử lý mọi tương tác với người sử
dụng là Bộ xử lý tiếp nhận người dùng (User Processor), còn thành phần kia lo việc xử
lý dữ liệu (Data Processor).
Hình 1.3 Kiến trúc tham chiếu CSDLPT
Thành phần đầu tiên bao gồm:
5 | 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]
− Bộ giao tiếp người dùng (user interface handler) diễn dịch các lệnh của người sử
dụng, và định dạng dữ liệu để chuyển cho người sử dụng các kết quả.
− Bộ kiểm soát dữ liệu ngữ nghĩa (semantic data controller) sử dụng các ràng buộc
toàn vẹn (integrity constraints) và thông tin cấp phép, quyền hạn (authorization),
được định nghĩa như thành phần của lược đồ khái niệm toàn cục, để kiểm tra, xác

đị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

E1 J.Doe Elect. Eng.
E2 M.Smith Syst. Anal.
E3 A. Lee Mech. Eng.
E4 J. Miller Programmer
E5 B.Casey Syst. Anal.
E6 L. Chu Elect. Eng.
E7 R. David Mech. Eng.
E8 J. Jones Syst. Anal.
7 | 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]
Bảng PROJ (project – dự án) gồm các thuộc tính PNO (mã số dự án); PNAME (tên dự
án); BUDGET (ngân sách dự án) và LOC (location – vị trí dự án).
PNO PNAME BUDGET LOC
P1 Instrumentation 150000 Montreal
P2 Database Develop 135000 New York
P3 CAD/CAM 250000 New York
P4 Maintenance 310000 Paris
Bảng ASG gồm các thuộc tính ENO (mã số nhân viên); PNO (mã số dự án); RESP
(responsibility – nhiệm vụ trong dự án) và DUR (duration – thời gian).
ENO PNO RESP DUR
E1 P1 Manager 12
E2 P1 Analyst 24
E2 P2 Analyst 6
E3 P3 Consultant 10
E3 P4 Engineer 48
E4 P2 Programmer 18
E5 P2 Manager 24
E6 P4 Manager 48
E7 P3 Engineer 36
E8 P3 Manager 40

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

Một phân mảnh dọc cho một quan hệ R sinh ra các mảnh R1,R2,…,Rr, mỗi mảnh
chứa một tập con thuộc tính của R và cả khóa của R. Mục đích của phân mảnh dọc là
phân hoạch một quan hệ thành một tập các quan hệ nhỏ hơn để nhiều ứng dụng chỉ cần
chạy trên một mảnh.
9 | 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.2 Minh họa phân mảnh dọc
Ví dụ: Quan hệ PROJ có thể được phân mảnh dọc thành hai quan hệ con: PROJ
1
chứa
thông tin về ngân sách các dự án; PROJ
2
chứa tên và vị trí dự án.
PROJ
1
PNO BUDGET
P1 150000
P2 135000
P3 250000
P4 310000
PROJ
2
PNAME LOC
Instrumentation Montreal
Database Develop New York
CAD/CAM New York
Maintenance Paris
2.4. Phân mảnh hỗn hợp
Trong đa số trường hợp, phân mảnh ngang hoặc phân mảnh dọc đơn giản cho một
lược đồ CSDL không đủ đáp ứng các yêu cầu từ các ứng dụng. Trong trường hợp đó,

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

chứa thông tin về ngân
sách các dự án trong PROJ
2
; PROJ
22
chứa tên và vị trí các dự án trong PROJ
2
; PROJ
31
chứa thông tin về ngân sách các dự án trong PROJ
3
; PROJ
32
chứa tên và vị trí các dự án
trong PROJ
3
; PROJ
41
chứa thông tin về ngân sách các dự án trong PROJ
4
; PROJ
42
chứa
tên và vị trí các dự án trong PROJ
4
.
PROJ
11
PNO BUDGET
P1 150000

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

3. Các phép toán đại số quan hệ dùng trong thuật toán phân mảnh
3.1 Phép chọn
Phép chọn sinh ra một tập con của quan hệ đã cho. Tập con này chứa tất cả các bộ
thỏa một công thức nào đó (một điều kiện). Chúng ta biểu thị một phép chọn từ một
quan hệ R là:
σ
F
(R)
trong đó R là quan hệ và F là một công thức.
Công thức trong phép chọn được gọi là vị từ chọn (selection predicate) và là một
công thức nguyên tử với các toán hạng có dạng A θ c, trong đó A là một thuộc tính của
R và θ là một trong các toán tử so sánh số học <, >, =, ≠, ≤ và ≥. Các toán hạng này có
thể được nối lại bằng các nối tử logic ˄, ˅ và ¬. Hơn nữa vị từ chọn không chứa bất kỳ
một lượng từ nào.
Ví dụ: Xét quan hệ EMP. Kết quả chọn các bộ của các kỹ sư điện (electrical engineer)
như sau:
σ
TITLE=’Elect. Eng.’
(EMP)
ENO ENAME TITLE
E1 J.Doe Elect. Eng.
E6 L. Chu Elect. Eng.
12 | 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]
3.2 Phép chiếu
Phép chiếu sinh ra một tập con theo chiều dọc của một quan hệ. Kết quả chiếu chỉ
chứa các thuộc tính của quan hệ gốc được chiếu. Vì thế ngôi của kết quả luôn nhỏ hơn
hay bằng ngôi của quan hệ gốc.
Phép chiếu quan hệ R trên các thuộc tính A và B được biểu thị như sau:
π

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

E1 J.Doe Elect. Eng. Elect. Eng. 40000
E1 J.Doe Elect. Eng. Syst. Anal. 34000
E1 J.Doe Elect. Eng. Mech. Eng. 27000
E1 J.Doe Elect. Eng. Programmer 24000
E2 M.Smith Syst. Anal. Elect. Eng. 40000
E2 M.Smith Syst. Anal. Syst. Anal. 34000
E2 M.Smith Syst. Anal. Mech. Eng. 27000
E2 M.Smith Syst. Anal. Programmer 24000
… … … … …
… … … … …
… … … … …
… … … … …
E8 J. Jones Syst. Anal. Elect. Eng. 40000
E8 J. Jones Syst. Anal. Syst. Anal. 34000
E8 J. Jones Syst. Anal. Mech. Eng. 27000
13 | 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]
E8 J. Jones Syst. Anal. Programmer 24000
3.4 Phép nối-θ
Là một dẫn xuất của tích Descartes. Có rất nhiều kiểu nối và kiểu nối tổng quát
nhất là nối-θ, hay đơn giản là nối. Nối-θ của hai quan hệ R và S được biểu thị bằng:
R
F
S = σ
F
(RxS)
trong đó F là một vị từ nối (xác định tương tự như vị từ chọn).
Ví dụ: Nối-θ của hai quan hệ EMP và PAY trên vị từ nối EMP.TITLE=PAY.TITLE
được thể hiện như sau:
EMP

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

)=PAY
member(L
1
)=EMP
− Thông tin định lượng về CSDL là lực lượng (cardinality) của mỗi quan hệ R,
được ký hiệu là card(R).
4.1.2 Thông tin về ứng dụng
− Vị từ đơn giản (simple predicate): Cho quan hệ R(A
1
, A
2
, … , A
n
), trong đó A
i
là một thuộc tính được định nghĩa trên một miền biến thiên D
i
, một vị từ đơn
giản p
j
được định nghĩa trên R có dạng:
P
j
: A
i
θ Value
trong đó θ thuộc{=,<,≠,≤,>,≥} và Value được chọn từ miền biến thiên của A
i
.
Với quan hệ R, chúng ta định nghĩa Pr = {p

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

| m
i
= ˄
pj
∈
Pr
p
j
* }, 1≤ j≤ m , 1≤ i ≤ z, với p
j
* = p
j
hay p
j
* = ¬( p
j
).
Ví dụ: Các vị từ hội sơ cấp
m
1
: PNAME="Maintenance" ˄ BUDGET≤200000
m
2
: NOT(PNAME="Maintenance") ˄ BUDGET≤200000
m
3
: PNAME= "Maintenance" ˄ NOT(BUDGET≤200000)
m
4
: NOT(PNAME="Maintenance") ˄ NOT(BUDGET≤200000)

− Độ 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

i
).
4.2 Phân mảnh ngang nguyên thủy
− Định nghĩa: Cho quan hệ R, các mảnh ngang của R
i
là:
R
i
= σ
Fi
(R), 1≤ i ≤ z
15 | 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]
trong đó F
i
là công thức chọn được sử dụng để có được mảnh R
i
. Chú ý rằng nếu F
i
có dạng chuẩn hội, nó là một vị từ hội sơ cấp.
Một mảnh ngang R
i
của quan hệ R có chứa tất cả các bộ R thỏa vị từ hội sơ cấp
m
i
. Vì vậy cho một tập các vị từ hội sơ cấp M, số lượng các mảnh ngang cũng bằng
số lượng các vị từ hội sơ cấp. Tập các mảnh ngang này cũng thường được gọi là các
mảnh hội sơ cấp (minterm fragment).
− Tính đầy đủ (completeness) của vị từ đơn giản: 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.
− 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

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 COM_MIN (thuật toán lặp sinh ra một tập đầy đủ và cực tiểu các vị từ
Pr’ khi cho một tập các vị từ đơn giản Pr)
COM_MIN
Nhập: R: quan hệ; Pr: tập các vị từ đơn giản
Xuất: Pr’: tập các vị từ đơn giản đầy đủ và cực tiểu
Declare
F: tập các mảnh hội sơ cấp
Begin
Tìm một vị từ p
i
∈
Pr sao cho p
i
phân hoạch R theo quy tắc 1
Pr’

p
i
Pr

Pr – p
i
F

f
i
{f
i

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

k

∈
Pr’, một vị từ không có liên đới then
Begin
Pr’

Pr’ – p
k
F

F – f
k
End
End-if
End-begin
Until Pr’ đầy đủ
End. {COM_MIN}
− Thuật toán PHORIZONTAL (thuật toán phân mảnh ngang nguyên thủy)
16 | 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]
Nhập: R: quan hệ; Pr: tập các vị từ đơn giản
Xuất: 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 p
i


∈
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

i
= σ
Fi
(S) với F
i
là
công thức định nghĩa mảnh ngang nguyên thủy S
i
.
− Muốn thực hiện phân mảnh ngang dẫn xuất, ta cần 3 nguyên liệu (input): tập các
phân hoạch của quan hệ chủ nhân, quan hệ thành viên, và tập các vị từ nối nửa giữa
chủ nhân và thành viên.
5. Chương trình minh họa thuật toán phân mảnh ngang nguyên thủy
5.1 Giao diện chương trình
17 | 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]
Chương trình gồm các chức năng:
- Nhập dữ liệu mẫu từ một tập tin chứa các quan hệ tạo sẵn (chẳng hạn như access).
- Chọn một bảng dữ liệu để tiến hành phân mảnh.
- Khai báo các vị từ đơn giản từ bảng đã chọn.
- Tiến hành phân mảnh ngang nguyên thủy cho quan hệ.
- Có thể thực hiện phân mảnh ngang nguyên thủy trên các quan hệ khác.
5.2 Phân mảnh ngang nguyên thủy trên quan hệ PAY
18 | 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]
Các vị từ đơn giản nhập vào cho chương trình:
p
1
: SAL > 27000
p

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

4
: BUDGET > 15000
p
5
: BUDGET < 15000
Kết quả chương trình cho ta 4 mảnh:
PROJ
1
PNO PNAME BUDGET LOC
P1 Instrumentation 150000 Montreal
PROJ
2
PNO PNAME BUDGET LOC
P3 CAD/CAM 250000 New York
PROJ
3
PNO PNAME BUDGET LOC
20 | 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]
P4 Maintenance 310000 Paris
PROJ
4
PNO PNAME BUDGET LOC
P2 Database Develop 135000 New York
5.4 Hạn chế của chương trình
- Chưa cho phép nhập các số liệu tự do ngoài số liệu có trong bảng dữ liệu cung cấp
sẵn.
- Chỉ mới cung cấp các toán tử =, >, <.
6. Thuật toán phân mảnh dọc
6.1 Yêu cầu thông tin

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

i
, A
j
) =
0 trong trường hợp ngược lại
Các véctơ use(q
i
, •) cho mỗi ứng dụng rất dễ định nghĩa nếu nhà thiết kế biết
được các ứng dụng sẽ chạy trên CSDL.
6.1.2 Ma trận ái lực thuộc tính (AA – attribute affinity matrix)
Giá trị sử dụng thuộc tính không đủ để làm cơ sở cho việc tách và phân mảnh.
Điều này là do chúng không biểu thị cho độ lớn của tần số ứng dụng. Số đo tần số có
thể được chứa trong định nghĩa về số đo ái lực thuộc tính aff(A
i
, A
j
), biểu thị cho cầu
nối (bond) giữa hai thuộc tính của một quan hệ theo cách chúng được các ứng dụng
truy xuất.
Số đo ái lực giữa hai thuộc tính A
i
, A
j
được định nghĩa là:
aff(A
i
, A
j
)= ∑ ∑ ref
l

(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

và acc
l
(q
k
) là số đo tần số truy xuất ứng dụng q
k
đến các thuộc tính A
i
, A
j
tại vị trí
21 | 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]
l. Chúng ta cần lưu ý rằng trong công thức tính aff (A
i
, A
j
) chỉ xuất hiện các ứng dụng q
mà cả A
i
và A
j
đều sử dụng.
Kết quả của tính toán này là một ma trận đối xứng n x n, mỗi phần tử của nó là
một số đo được định nghĩa ở trên. Chúng ta gọi nó là ma trận ái lực thuộc tính (AA)
(attribute affinity matrix).
6.2 Thuật toán tụ nhóm
Thuật toán năng lượng nối BEA
Thuật toán BEA
Nhập: AA - ma trận ái lực thuộc tính;

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

i
)
Tính cont(A
index-1
,A
index
, A
index+1
); { điều kiện biên}
Loc
←
nơi đặt, được cho bởi giá trị cont lớn nhất
for i: = index downto Loc do {xáo trộn hai ma trận}
CA(
•
, j)
←
CA(
•
, j-1)
CA(
•
, loc)
←
AA(
•
, index)
Index
←
index+1

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}

begin
for i from n-2 to 1 by -1 do
begin
tính CTQ
i
tính CBQ
i
tính COQ
i
z
←
CTQ
i
*CBQ
i
– (COQ
i
)
2
if z > best then
begin
best
←
z
ghi nhận điểm tách bên vào trong hành động xê dịch
end-if
end-for
gọi SHIFT(CA)
end-begin
until không thể thực hiện SHIFT được nữa

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:

- Nhập các giá trị về số thuộc tính của quan hệ, số truy vấn, số vị trí.
- Nhập các giá trị cho ma trận sử dụng thuộc tính.
- Nhập các giá trị cho ma trận tần số truy cập.
- Tính ma trận ái lực thuộc tính AA.
- Tính ma trận ái lực gom cụm CA.
- Thực hiện phân mảnh dọc dựa trên ma trận AA và ma trận CA.
7.2 Phân mảnh dọc trên quan hệ PROJ
- Nhập các giá trị cho ma trận về giá trị sử dụng thuộc tính
24 | 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]
Ma trận bao gồm các thông tin sau
• Bốn ứng dụng:
q
1
: Tìm ngân sách của một dự án, cho biết mã số dự án
q
2
: Tìm tên và ngân sách của tất cả mọi dự án
q
3
: Tìm tên của các dự án được thực hiện tại một thành phố đã cho
q
4
: Tìm tổng ngân sách dự án cho mỗi thành phố
• Quan hệ PROJ có bốn thuộc tính được ký hiệu như sau:
A
1
=PNO; A
2
=PNAME; A

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