Các thuật toán xử lý và tối ưu hoá truy vấn - Nhóm 4 Lớp KHMT 2010-2012
ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC KHOA HỌC
Đề tài:
CÁC THUẬT TOÁN XỬ LÝ
VÀ
TỐI ƯU HÓA TRUY VẤN
Giáo viên hướng dẫn: Nhóm học viên thực hiện:
TS. Hoàng Quang Trần Như Đăng Tuyên
Nguyễn Vũ Cát Trường
Nguyễn Thị Thanh Tâm
Trần Thị Thành
Lê Bá Minh Phong
HUẾ 11/2011
Các thuật toán xử lý và tối ưu hoá truy vấn - Nhóm 4 Lớp KHMT 2010-2012
TS. Hoàng Quang Trần Như Đăng Tuyên 1
A.MỞ ĐẦU 1
B. NỘI DUNG 4
1. Chuyển các câu truy vấn SQL sang đại số quan hệ 4
2. Các thuật toán cho việc sắp xếp ngoài 5
3. Các giải thuật đối với phép chọn (select) và phép nối (join) 7
4. Các giải thuật đối với phép chiếu (project) và các phép toán trên tập hợp 22
5. Sự thực hiện của các phép toán kết hợp và các phép nối ngoài 24
6. Sự kết hợp các phép toán bằng kỹ thuật đường ống 28
7. Tối ưu hóa câu truy vấn bằng heuristic 29
8. Sử dụng sự lựa chọn và ước lượng chi phí trong tối ưu hóa câu truy vấn 41
9. Tổng quan về tối ưu hoá truy vấn trong Oracle 54
10. Tối ưu hoá truy vấn ngữ nghĩa 55
C. BÀI TẬP 56
D. KẾT LUẬN 59
E. TÀI LIỆU THAM KHẢO 60

Các thuật toán xử lý và tối ưu hoá truy vấn - Nhóm 4 Lớp KHMT 2010-2012
Tiểu luận sẽ chỉ tập trung biểu diễn tối ưu hóa truy vấn trong ngữ cảnh của một
RDBMS. Một hệ quản trị cơ sở dữ liệu quan hệ phải định giá các chiến lược thực
hiện truy vấn khác một cách có hệ thống và chọn chiến lược khá hiệu quả hoặc
chiến lược tối ưu.
Mỗi DBMS có số thuật toán truy cập cơ sở dữ liệu chung thực hiện các phép
toán quan hệ như là SELECT hoặc JOIN hoặc kết hợp các phép toán này. Chỉ có
việc thực hiện các chiến lược mà có thể thực hiện bằng các thuật toán truy cập cơ
sở dữ liệu và áp dụng cho truy vấn riêng và thiết kế cơ sở dữ liệu vật lý riêng có
thể mô tả bằng module tối ưu hóa truy vấn.
Tổng quát nội dung tiểu luận như sau:
Phần 1: Các truy vấn SQL được chuyển sang các truy vấn đại số quan hệ và sau
đó được tối ưu hóa như thế nào. Từ phần 2 đến 6 giới thiệu các thuật toán đối với
2
Truy vấn trong ngôn ngữ bậc cao
Kiểm tra, phân tích cú pháp và làm cho hợp lệ
Dạng gần với truy vấn
Tối ưu hóa truy vấn
Thực hiện vẽ sơ đồ
Tạo mã truy vấn
Viết mã cho việc thực hiện truy vấn
Xử lý cơ sở dữ liệu hiện thời
Kết quả truy vấn
Hình 1. Các bước đặc trưng khi xử lí truy vấn mức cao
Các thuật toán xử lý và tối ưu hoá truy vấn - Nhóm 4 Lớp KHMT 2010-2012
việc thi hành các phép toán quan hệ. Sau đó, giới thiệu tổng quan về các chiến
lược tối ưu hóa truy vấn. Có hai kỹ thuật chính để thực hiện tối ưu hóa truy vấn.
Kỹ thuật đầu tiên dựa vào các qui tắc Heuristic (quy tắc mang tính kinh nghiệm)
nhằm sắp xếp các phép toán trong một chiến lược thực hiện truy vấn. Heuristic là
một qui tắc áp dụng tốt trong hầu hết các trường hợp nhưng không đảm bảo áp

WHERE Salary > ( SELECT MAX(Salary)
FROM EMPLOYEE
WHERE Dno = 5);
Câu truy vấn này bao gồm một truy vấn con lồng và vì vậy sẽ được phân tích
thành hai khối. Khối bên trong là:
( SELECT MAX(Salary)
FROM EMPLOYEE
WHERE Dno = 5);
Và khối ngoài là
SELECT Lname, Fname
FROM EMPLOYEE
WHERE Salary > C
4
Các thuật toán xử lý và tối ưu hoá truy vấn - Nhóm 4 Lớp KHMT 2010-2012
Trong đó C biểu diễn kết quả trả về từ khối trong. Khối trong có thể được
chuyển sang biểu thức đại số quan hệ mở rộng
ℑ
MAX

Salary
(σ
Dno=5
(EMPLOYEE))
Trong đó ℑ là phép kết hợp hàm (AGGREGATE FUNCTION: SUM,
AVERAGE, MAXIMUM, MINIMUM, COUNT)
Và block ngoài sang biểu thức
Л
Lname,Fname
(σ
Salary>c

B
; {kích thước của vùng đệm trong các khối }
m ←[(j/k)];
{Phần sắp xếp}
While (i<=m)
do {
đọc k blocks tiếp theo của file vào bộ đệm hoặc nếu có ít hơn k các
khối còn lại thì đọc vào các khối còn lại;
sắp xếp các bản ghi trong bộ đệm và ghi như là một file con tạm thời;
i ←i + 1;
}
{Phần trộn: trộn các file con cho đến khi chỉ còn lại một file}
Set i ←1;
p ←[log
k-1
m] {p là số lần đối với phần trộn}
j ←m;
While (i<=p)
Do {
n ←1;
q ←[(j/(k-1)] {số file con để ghi trong lần này}
While (n<=q)
Do {
Đọc k-1 file con tiếp theo hoặc các file con còn lại (từ lần trước)
một khối tại một thời điểm;
Trộn và ghi như file con mới một khối tại một thời điểm.
n← n+1;
}
j←q;
i←i+1;

R
, và số lần thực hiện trộn là
 
))(log
RdM
n
.
Trong ví dụ trên, d
M
=4 do đó 205 runs đã sắp ban đầu sẽ được trộn thành 52 tại
cuối cùng của những lần đầu tiên, rồi nó được trộn thành 13, rồi 4, rồi 1 run, điều
đó có nghĩa là cần 4 lần. Tối thiểu d
M
cho trường hợp tốt nhất của thuật toán, đó là:
(2*b) + (2*(b*log
2
b)))
Trong đó:
(2*b) biểu diễn số khối truy cập đối với đoạn sắp xếp, vì mỗi khối của tệp được
truy xuất 2 lần: một cho việc đọc vào bộ nhớ và một cho việc ghi các bản ghi này
lên đĩa sau khi sắp xếp.
(2*(b*log
2
b))) biểu diễn số truy xuất khối trong giai đoạn trộn, giả sử trường
hợp xấu nhất d
M
=2 .
Tổng quát, log được tính dựa trên d
M
và biểu thức đối với số khối truy cập trở

khả năng chọn các bản ghi từ file. Các giải thuật này cũng được biết như là duyệt
file, bởi vì chúng duyệt hết các bản ghi của file để tìm kiếm và lấy các bản ghi thỏa
mãn điều kiện chọn. Nếu giải thuật tìm kiếm có sử dụng chỉ mục thì tìm kiến theo
chỉ mục được gọi là index scan (phép duyệt theo chỉ mục). Các phương thức tìm
sau đây (từ S1 đến S6) là các ví dụ về một số thuật toán tìm kiếm mà có thể được
sử dụng để thực hiện phép chọn:
S1- Tìm kiếm tuyến tính (Linear search). Duyệt từng bản ghi trong file, và
kiểm tra giá trị thuộc tính của nó có thỏa mãn điều kiện chọn hay không.
S2- Tìm kiếm nhị phân (Binary search). Nếu điều kiện chọn gồm một so sánh
bằng trên thuộc tính khóa trên file được sắp xếp, tìm kiếm nhị phân có thể hiệu quả
8
Các thuật toán xử lý và tối ưu hoá truy vấn - Nhóm 4 Lớp KHMT 2010-2012
hơn tìm kiếm tuyến tính. Một ví dụ là OP1 khi Ssn là thuộc tính sắp xếp đối với
file EMPLOYEE.
S3- Sử dụng chỉ mục sơ cấp (hoặc hash key). Nếu điều kiện chọn bao gồm so
sánh bằng trên một thuộc tính khóa với một chỉ mục sơ cấp (hoặc hash key) – ví
dụ như, Ssn = ‘123456789’ trong OP1- sử dụng chỉ mục sơ cấp để lấy bản ghi.
Lưu ý rằng điều kiện này truy tìm bản ghi đơn.
S4- Sử dụng chỉ mục sơ cấp để lấy nhiều bản ghi. Nếu điều kiện so sánh là <,
>=, < hoặc <= trên trường khóa với chỉ mục sơ cấp. Ví dụ như, Dnumber>5 trong
OP2 – sử dụng chỉ mục để tìm các bản ghi thỏa mãn điều kiện bằng tương ứng
(Dnumber=5) sau đó lấy tất cả các bản ghi tiếp theo trong file (đã sắp xếp). Đối
với điều kiện Dnumber<5, lấy hết tất cả các bản ghi có trước.
S5- Sử dụng chỉ mục bó cụm để lấy nhiều bản ghi. Nếu điều kiện chọn gồm
một so sánh bằng trên thuộc tính không khóa với một chỉ mục cụm. Ví dụ như,
Dno=5 trong OP3 – sử dụng chỉ mục để lấy tất cả các bản ghi thỏa mãn điều kiện.
S6- sử dụng chỉ mục thứ cấp (B
+_
tree) trên so sánh bằng. Phương pháp tìm
kiếm này có thể được sử dụng để truy tìm bản ghi đơn nếu trường chỉ mục là một

các chỉ mục bao gồm các con trỏ bản ghi (thường là con trỏ khối) thì mỗi chỉ mục
có thể được dùng để truy lục tập các con trỏ bản ghi thỏa mãn điều kiện riêng biệt.
Sự giao nhau của các tập con trỏ bản ghi này chính là các con trỏ bản ghi thỏa mãn
điều kiện liên kết, sau đó chúng được sử dụng để truy lục các bản ghi một cách
trực tiếp. Nếu chỉ một số các điều kiện có chỉ mục thứ cấp thì mỗi bản ghi đã truy
lục được tiếp tục kiểm tra nhằm xác định xem nó có thỏa mãn các điều kiện còn lại
hay không.
Bất cứ khi nào một điều kiện đơn chỉ định sự chọn lựa (như OP1, OP2 hoặc
OP3) thì chúng ta có thể chỉ cần kiểm tra xem có hay không một đường dẫn truy
cập tồn tại trên thuộc tính bao hàm trong điều kiện đó. Nếu một đường dẫn truy
cập tồn tại thì phương pháp tương ứng với đường dẫn truy cập được sử dụng; trái
lại, phương pháp tìm kiếm tuyến tính có thể được sử dụng. Tối ưu hóa câu truy vấn
đối với phép toán SELECT chủ yếu là cần cho các điều kiện chọn kết hợp bất cứ
khi nào có nhiều hơn một thuộc tính trong điều kiện có đường dẫn truy cập. Bộ tối
ưu hóa sẽ chọn đường dẫn truy cập sao cho truy lục ít bản ghi nhất, theo cách hiệu
quả nhất bằng cách ước lượng các chi phí khác nhau và chọn ra phương pháp có
chi phí ước lượng thấp nhất.
10
Các thuật toán xử lý và tối ưu hoá truy vấn - Nhóm 4 Lớp KHMT 2010-2012
Khi bộ tối ưu đang chọn giữa nhiều điều kiện đơn giản trong một điều kiện
chọn liên kết thì nó thường xem xét độ chọn lọc (selectivity) của mỗi điều kiện. Độ
chọn lọc được định nghĩa là tỉ lệ giữa số bản ghi (các bộ) thõa điều kiện với tổng
số bản ghi (các bộ) trong tệp (quan hệ) nên đó là một số giữa 0 và 1 (0 nghĩa là
không có bản ghi nào thỏa mãn điều kiện và 1 nghĩa là tất cả bản ghi đều thõa điều
kiện. Mặc dù các độ chọn lọc chính xác của tất cả điều kiện có thể không có giá trị
nhưng ước lượng các độ chọn lọc thường được lưu giữ trong danh mục của DBMS
và được sử dụng bởi bộ tối ưu hóa. Ví dụ, đối với điều kiện bằng trên một thuộc
tính khóa của quan hệ r(R), s=1/|r(R)|, trong đó |r(R)| là số bộ trong quan hệ r(R).
Đối với điều kiện bằng trên một thuộc tính với i giá trị riêng biệt, s có thể được
ước lượng bởi (|r(R)|/i)/|r(R)| hoặc 1/i, giả sử rằng các bản ghi được phân phối giữa

này chúng ta chỉ trình bày các kỹ thuật thực hiện phép nối hai chiều (dựa vào lược
đồ quan hệ Hình 2), xét thuật toán đối với phép nối có dạng:
R
A=B
S
Trong đó, A và B lần lượt là các thuộc tính tương thích miền (domain-
compatible) của R và S. Các phương pháp thảo luận ở đây có thể được mở rộng
thành các dạng phép nối tổng quát hơn. Chúng ta minh họa bốn kỹ thuật phổ biến
nhất để thực hiện một phép nối, sử dụng các phép nối sau:
OP6: EMPLOYEE
Dno=Dnumber
DEPARTMENT
OP7: DEPARTMENT
Mgr_Ssn=Ssn
EMPLOYEE
Các phương pháp thực hiện phép nối.
J1. Nested–loop join (phép nối vòng lặp lồng nhau). Đối với mỗi bản ghi t
trong R (vòng lặp ngoài), truy lục mỗi bản ghi s từ S (vòng lặp trong) và kiểm tra
xem hai bản ghi có thõa mãn điều kiện nối t[A]=s[B] hay không?
J2- Single – loop join (phép nối vòng lặp đơn) (sử dụng một cấu trúc truy xuất
để truy lục các bản ghi phù hợp). Giả sử một chỉ mục (hoặc khóa băm) tồn tại đối
với thuộc tính nối B của S, tại một thời điểm (vòng lặp đơn) truy lục một bản ghi t
trong R và sau đó sử dụng cấu trúc truy cập để truy lục trực tiếp tất cả các bản ghi
phù hợp s từ S thỏa mãn s[B] = t[A].
J3- Sort-merge join (phép nối sắp xếp trộn). Nếu các bản ghi của R và S được
sắp xếp vật lý theo giá trị của các thuộc tính nối A và B thì chúng ta có thể thực
12
Các thuật toán xử lý và tối ưu hoá truy vấn - Nhóm 4 Lớp KHMT 2010-2012
hiện phép nối bằng cách hiệu quả nhất có thể. Cả hai tệp được duyệt đồng thời
theo thứ tự của các thuộc tính nối, kết nối các bản ghi có cùng giá trị đối với thuộc

đưa bộ kết hợp <R(i), S(j)> vào T;
(*đưa ra các bộ khác phù hợp R(i), nếu có*)
set l

j+1;
while (l ≤ m) and (R(i)[A]=S(l)[B]) do
{ đưa ra bộ kết hợp <R(i), S(l)> vào T;
set l

l+1
13
Các thuật toán xử lý và tối ưu hoá truy vấn - Nhóm 4 Lớp KHMT 2010-2012
}
(*đưa ra các bộ khác phù hợp S(j), nếu có*)
Set k

i+1;
while (k ≤ n) and (R(k)[A]= S(j)[B]) do
{ đưa các bộ kết hợp <R(k),S(j)> vào T;
set k

k + 1
}
set i

k, j

l
}
}

1, j

1;
While (i ≤ n) and ( j≤ m) do
{ if R(i) > S(i) then
14
Các thuật toán xử lý và tối ưu hoá truy vấn - Nhóm 4 Lớp KHMT 2010-2012
{ đưa S(j) vào T
Set j

j+ 1
}
Elseif R(i) < S(j) then
{ đưa R(i) vào T;
set i

i+ 1
}
Else set j

j+1 (* R(i) = S(j), vì vậy chúng ta bỏ qua một trong các
bộ trùng lặp*)
}
If (i ≤ n) then thêm các bộ từ R(i) đến R(n) vào T;
If (j ≤ m) then thêm các bộ từ S(j) đến R(m) vào T;
(d) Sắp xếp các bộ trong R và S bằng cách sử dụng cùng các thộc tính sắp
xếp duy nhất.
Set i

1, j

15
Các thuật toán xử lý và tối ưu hoá truy vấn - Nhóm 4 Lớp KHMT 2010-2012
{ đưa R(j) vào T; (*R(i) không phù hợp với S(j), vì vậy đưa
ra R(i)*)
Set i

i+1
}
Else set i

i+1, j

j+1
}
If (i ≤ n) then thêm các bộ từ R(i) đến R(n) vào T;
Hình 4: Thực hiện phép JOIN,PROJECT, UNION, INTERSECTION và SET
DIFFERENCE bằng cách sử dụng Sort-merge, trong đó R có n bộ và S có m bộ
(a) Thực hiện phép T

R
A=B
S
(b) Thực hiện phép T

Л
<attribute list>
(R)
(c) Thực hiện phép T

R

B
=7 blocks (các bộ đệm). Để minh họa, giả sử
rằng tệp DEPARTMENT gồm có r
D
= 50 bản ghi lưu trữ trong b
D
= 10 khối đĩa và
tệp EMPLOYEE gồm có r
E
= 6000 bản ghi lưu trữ trong b
E
= 2000 khối đĩa. Nó
thuận tiện để đọc nhiều khối từ tệp vào bộ nhớ tại một thời điểm từ tệp và các bản
ghi của tệp được sử dụng cho vòng lặp ngoài (tức là, n
B
- 2 khối). Sau đó thuật toán
có thể đọc một khối tại một thời điểm đối với tệp dùng làm vòng lặp trong và sử
dụng các bản ghi của nó để dò tìm (tìm kiếm) các khối vòng lặp ngoài trong bộ
nhớ để kết nối các bản ghi phù hợp. Điều này làm giảm tổng số truy cập khối. Cần
thêm một khối bộ đệm để chứa các bản ghi kết quả sau khi chúng được nối và nội
dung của khối bộ đệm này được bổ sung vào tệp kết quả (tệp trên đĩa chứa kết quả
phép nối) bất cứ khi nào nó (khối bộ đệm) bị đầy. Sau đó khối bộ đệm này được sử
dụng lại để lưu giữ thêm các bản ghi kết quả.
Trong phép nối vòng lặp lồng nhau (nested-loop join), có sự khác biệt khi chọn
tệp nào dùng làm vòng lặp ngoài và tệp nào dùng làm vòng lặp trong. Nếu
EMPLOYEE được dùng cho vòng lặp ngoài thì mỗi khối của EMPLOYEE được
đọc một lần và toàn bộ tệp DEPARTEMENT (mỗi khối) được đọc một lần vào
mỗi thời điểm chúng ta đọc (n
B
-2) khối tệp từ EMPLOYEE vào bộ nhớ đệm.

thì tổng số truy cập khối là:
b
D
+ ( b
D
/(n
B
- 2) * b
E
) = 10 + ( 10/5 * 2000) = 4010 truy cập khối.
Thuật toán nối sử dụng một bộ đệm để lưu giữ các bản ghi đã nối kết của tệp kết
quả. Mỗi lần bộ đệm bị đầy thì nó được ghi vào đĩa và được sử dụng lại.
Nếu tệp kết quả của phép nối có b
RES
khối đĩa thì mỗi khối được ghi một lần,
vì vậy thêm b
RES
truy cập khối vào công thức có trước nhằm ước lượng tổng chi
phí của phép nối. Như ví dụ cho thấy nên sử dụng tệp có số khối ít hơn làm tệp
vòng lặp ngoài trong phép nối vòng lặp lồng nhau.
Một hệ số khác có ảnh hưởng đến việc thực hiện phép nối, đặc biệt là phương
pháp vòng lặp đơn (single-loop) J2, là tỉ lệ phần trăm các bản ghi trong tệp sẽ được
nối với các bản ghi trong tệp khác. Chúng ta gọi đây là hệ số chọn nối (the join
selection factor) của tệp với chú ý đến điều kiện nối bằng (equijoin) với tệp khác.
Hệ số này phụ thuộc vào điều kiện nối bằng riêng biệt giữa hai tệp. Để minh họa
điều này, xét toán OP7 nối mỗi bản ghi DEPARTMENT với bản ghi EMPLOYEE.
Ở đây, mỗi bản ghi DEPARTMENT (có 50 bản ghi như vậy trong ví dụ) muốn
được nối với một bản ghi EMPLOYEE đơn, nhưng nhiều bản ghi EMPLOYEE sẽ
không được nối.
Giả sử rằng các chỉ mục thứ cấp tồn tại trên cả hai thuộc tính Ssn của

+1)) = 10 + (50*5) = 260 truy cập khối
Tùy chọn thứ 2 hiệu quả hơn vì hệ số chọn nối của DEPARTMENT với sự
chú ý đến điều kiện nối Ssn = Mgr_ssn là 1, ngược lại hệ số chọn nối của
EMPLOYEE với sự chú ý đến cùng điều kiện nối là (50/6000) hoặc 0.008. Với
phương pháp J2, hoặc tệp nhỏ hơn hoặc tệp có sự phù hợp đối với mọi bản ghi (tức
là, tệp có hệ số chọn nối cao) sẽ được sử dụng trong vòng lặp nối (ngoài). Cũng có
thể tạo một chỉ mục riêng đối với việc thực hiện phép nối nếu nó chưa tồn tại.
Phép nối sắp xếp-trộn (Sort-merge join) J3 khá hiệu quả nếu cả hai tệp được
sắp xếp bởi thuộc tính nối của chúng. Chỉ một lần thực hiện đơn qua mỗi tệp. Do
đó số khối truy cập bằng với tổng số khối trong cả hai tệp. Đối với phương pháp
này, cả hai OP6 và OP7 có thể cần b
E
+ b
D
= 2000 + 10 = 2010 truy cập khối. Tuy
nhiên, cả hai tệp phải được sắp thứ tự theo các thuộc tính nối; nếu một hoặc cả hai
tệp không sắp thứ tự thì chúng có thể được sắp xếp riêng đối với việc thực hiện
phép nối. Nếu chúng ta ước lượng chi phí sắp xếp một tệp ngoài bằng (b*log
2
b)
truy cập khối và nếu cả hai tệp cần được sắp xếp thì tổng chi phí một phép nối sắp
xếp-trộn có thể được ước lượng bằng (b
E
+ b
D
+ b
E*
log
2
b

,…R
M
và S
thành M phần S
1
, S
2
,…S
M
. Tính chất (property) của mỗi cặp phân chia tương ứng
R
i
, S
i
là các bản ghi trong R
i
chỉ cần được nối với các bản ghi trong S
i
và ngược lại.
Tính chất này được bảo đảm bằng việc sử dụng cùng hàm băm để phân chia cả hai
tệp trên các thuộc tính nối của chúng. Số bộ nhớ đệm tối thiểu cần cho giai đoạn
phân chia là M+1. Mỗi tệp R và S được phân chia tách biệt nhau. Đối với mỗi
phần phân chia, một bộ nhớ đệm đơn (có kích thước là một khối đĩa) được cấp
phát để lưu trữ các bản ghi băm đến phân chia này. Bất cứ khi nào bộ nhớ đệm cho
một phân chia bị đầy thì dữ liệu chứa trong nó được bổ sung vào một tệp con trên
đĩa (disk subfile) lưu trữ phần phân chia này. Giai đoạn phân chia có hai lần lặp.
Sau lần lặp thứ nhất, tệp R được phân chia thành các tệp con R
1
, R
2

ghi vào tệp kết quả. Để cải tiến hiệu quả việc dò tìm trong bộ nhớ, thường sử dụng
một bảng băm trong bộ nhớ để lưu trữ các bản ghi trong phần phân chia R
i
bằng
cách sử dụng một hàm băm khác với hàm băm phân chia.
Chúng ta có thể xấp xỉ chi phí của phép nối băm phân chia này bằng 3*(b
R
+b
S
)
+ b
RES
do mỗi bản ghi được đọc một lần và ghi lại vào đĩa một lần trong suốt giai
20
Các thuật toán xử lý và tối ưu hoá truy vấn - Nhóm 4 Lớp KHMT 2010-2012
đoạn phân chia. Trong giai đoạn nối (dò tìm), mỗi bản ghi được đọc để thực hiện
phép nối. Khó khăn chính của thuật toán này là bảo đảm rằng hàm băm phân chia
là không thay đổi, nghĩa là các kích cỡ phần phân chia gần bằng nhau. Nếu hàm
phân chia bị lệch (thay đổi) thì một số phần phân chia có thể quá lớn để vừa với
không gian bộ nhớ khả dụng đối với giai đoạn nối thứ hai.
Lưu ý rằng, nếu không gian bộ nhớ đệm n
B
> (b
R
+2), trong đó b
R
là số khối của
tệp nhỏ hơn trong hai tệp đang được nối (giả sử là R) thì không có lí do gì để thực
hiện phân chia vì trong trường hợp này, phép nối có thể được thực hiện hoàn toàn
trong bộ nhớ bằng cách sử dụng một số biến thể của phép nối vòng lặp lồng nhau

bộ đệm khả dụng như vậy và hàm băm được sử
dụng là h(K) = K mod M sao cho M phần phân chia được tạo, trong đó M < n
B
.
Để minh họa, giả sử chúng ta đang thực hiện phép nối OP6. Trong lần thực hiện
đầu tiên của giai đoạn phân chia, khi thuật toán nối băm hỗn hợp đang phân chia
tệp nhỏ hơn trong hai tệp (DEPARTMENT trong OP6), thuật toán chia không gian
21
Các thuật toán xử lý và tối ưu hoá truy vấn - Nhóm 4 Lớp KHMT 2010-2012
bộ đệm thành M phần sao cho tất cả các khối của phần phân chia đầu tiên của
DEPARTMENT hoàn toàn nằm trong bộ nhớ chính. Với mỗi phần phân chia khác,
chỉ một bộ đệm đơn trong bộ nhớ (có kích thước là một khối đĩa) được cấp phát;
phần còn lại của sự phân chia được ghi vào đĩa như phép nối băm phân chia thông
thường. Do đó, vào cuối của lần thực hiện đầu tiên của giai đoạn phân chia, phần
phân chia đầu tiên của DEPARTMENT nằm hoàn toàn trong bộ nhớ chính, trái lại
mỗi phần phân chia khác của DEPARTMENT nằm trong một tệp con của đĩa.
Đối với lần thực hiện thứ hai của giai đoạn phân chia, các bản ghi của tệp thứ
hai đang được nối (tệp lớn hơn, EMPLOYEE trong OP6) bị phân chia. Nếu một
bản ghi băm tới phần phân chia đầu tiên thì nó được nối với bảng ghi phù hợp
trong DEPARTMENT và các bản ghi đã nối được ghi vào bộ đệm kết quả (và cuối
cùng ghi vào đĩa). Nếu một bản ghi EMPLOYEE băm đến một phần phân chia
khác với phần đầu tiên thì nó được phân chia bình thường. Vì vậy, vào cuối lần
thực hiện thứ hai của giai đoạn phân chia, tất cả các bản ghi băm đến phần đầu tiên
đã được nối. Bây giờ có M-1 cặp phân chia trên đĩa. Vì vậy, trong suốt giai đoạn
nối hoặc dò tìm lần hai, cần M-1 lần lặp thay vì M lần. Mục đích là nối nhiều bản
ghi trong suốt giai đoạn phân chia nhằm tiết kiệm chi phí lưu trữ các bản ghi đó
vào lại đĩa và đọc chúng lần thứ hai trong giai đoạn nối.
4. Các giải thuật đối với phép chiếu (project) và các phép toán
trên tập hợp.
Phép chiếu

qua mỗi quan hệ là đủ để đưa ra kết quả. Ví dụ như chúng ta có thể thực hiện phép
hợp,
SR ∪
, bằng cách cũng một lúc duyệt và trộn 2 file đã sắp xếp, và chỉ khi bộ
giống nhau tồn tại trong hai quan hệ, chỉ một được giữ lại trong kết quả trộn. Đối
với phép giao,
SR ∩
, chúng ta chỉ giữ lại trong kết quả trộn các bộ có mặt trong
cả hai quan hệ. Hình 15.3 (c) đến (e) phác thảo sự thực hiện của 3 phép toán bằng
cách sắp xếp và trộn. Chi tiết không chứa trong 3 thuật toán này.
Băm có thể được sử dụng để thực hiện hợp giao và trừ. Một bảng được phân
chia và các phép toán khác được dùng để dò tìm phần chia thích hợp. Ví dụ như để
thực hiện
SR ∪
, đầu tiên băm (phân chia) các bản ghi của R, sau đó băm (do tìm)
các bản ghi của S, nhưng không chèn các bản sao bản ghi vào các bucket. Để thực
hiện
SR ∩
, đầu tiên chia các bản ghi của R thành file băm. Sau đó trong khi băm
mỗi bản ghi của S, tìm và kiểm tra khi bản ghi giống nhau từ R được tìm thấy
trong bucket, và khi thêm bản ghi vào file kết quả. Thực hiện R-S, đầu tiên băm
các bản ghi của R đến các bucket file băm. Trong khi băm (dò tìm) mỗi bản ghi
của S, khi một bản ghi giống nhau được tìm thấy trong bucket thì loại bỏ bản ghi
đó khỏi bucket.
23