GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
CHƯƠNG 6. XỬ LÝ VÀ TỐI ƯU CÂU TRUY VẤN
Mục đích
Trình bày các bước xử lý câu truy vấn, tối ưu logic câu truy vấn và tối ưu vật lý
câu truy vấn.
Yêu cầu
Sinh viên nắm các kỹ thuật cơ bản của tối ưu câu truy vấn và vận dụng được
trong khi thực hiện truy vấn dữ liệu trên SQL Server và có ý thức tối ưu trong quá
trình câu truy vấn dữ liệu cũng như trong khai phá dữ liệu.
1. Quá trình xử lý và tối ưu câu truy vấn.
Khi nhận được một câu hỏi của người dùng, bộ xử lí câu hỏi trước hết kiểm tra xem
câu hỏi có được viết đúng cú pháp hay không, các quan hệ và các thuộc tính trong câu hỏi
có trong CSDL hay không. Tiếp đó, nếu câu hỏi được chấp nhận, một phương án thực thi
(execution plan) cho câu hỏi được phát sinh.
Một phương án thực thi câu hỏi xác định một dãy các bước cho việc định giá câu hỏi,
trong đó mỗi bước ứng với một phép toán của đại số quan hệ cùng với chú giải về phương
pháp được dùng để định giá phép toán đó. Chẳng hạn, phép kết nối có thể được định giá
bằng các phương pháp lặp lồng, sắp xếp trộn, kết nối băm…
Mục đích của tối ưu hóa câu hỏi là tìm một phương án thực thi trong số tất cả các
phương án tương đương (theo nghĩa luôn cho cùng một kết quả), có thể có, được định giá
với chi phí nhỏ nhất. Trong hệ CSDL tập trung, chi phí cho việc định giá một câu hỏi là
tổng của chi phí nhỏ nhất. Trong hệ CSDL tập trung, chi phí cho việc định giá một câu hỏi
là tổng của chi phí I/O và chi phí CPU. Chi phí I/O (Vào/ra) do việc truyền dữ liệu giữa bộ
nhớ chính và bộ nhớ thứ cấp (thường là đĩa từ) vì trong phần lớn các ứng dụng, dữ liệu
thường quá lớn và không thể chứa hết trong bộ nhớ chính. Với phần lớn các thao tác
CSDL, chi phí I/O là chi phí có tính chi phối. Để giảm chi phí I/O thường phải sử dụng các
cấu trúc dữ liệu đặc biệt, như các cây B
+
chẳng hạn.
Hình 1 dưới đây chỉ rõ các bước khác nhau của việc xử lí một câu hỏi được viết
trong một ngôn ngữ hỏi bậc cao, chẳng hạn SQL.

NTD – Khoa Tin – ĐHSP Huế
1
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
Hình 1
NTD – Khoa Tin – ĐHSP Huế
SQL Query
Parse query
Select logical
query plan
Select physical
plan
Execute plan
Query expression tree
Logical query plan tree
Physical query plan tree
Query optimization
Convert
Query
Parse
Apply laws
Estimate
result sizes
Consider
physical plans
Estimate costs
Pick the best
Execute
Answer
Parse tree
Logical query plan

Improve logical query plan
Logical query plan + sizes
{P1, P2, … }
{(P1, C1), (P2,C2) … }
Pi
statistic
s
2
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
Nói chung, số các phương án thực thi tương đương đối với một câu hỏi cho trước là
rất lớn và phụ thuộc vào số m các phép toán (thao tác) trong câu hỏi và số k các phương
pháp khác nhau có thể được dùng để định giá mỗi một phép toán đó. Khi đó, số các
phương án thực thi có thể lên tới (m!).k.m. Tập tất cả các phương án thực thi tương đương
là không gian tìm kiếm cho tối ưu hóa câu hỏi.
Vì vậy, bài toán tìm phương án thực thi tối ưu (tốt nhất) là một bài toán rất khó, tốn
rất nhiều thời gian, đòi hỏi phải biết thông tin về các tệp được cài đặt ra sao, thậm chí cần
biết cả nội dung của các tệp. Đó là những thông tin thường không có sẵn đầy đủ trong thư
mục của hệ quản trị cơ sở dữ liệu (hệ QTCSDL).
Do đó, tối ưu hóa câu hỏi trong nhiều trường hợp được hiểu là tìm một phương án
thực thi câu hỏi tương đối hiệu quả, gần với tối ưu.
Xét ví dụ sau, cho hai lược đồ quan hệ R(AB) và S(CD). Giả sử ta có yêu cầu sau:
“Đưa ra thuộc tính A của các bộ thoả mãn điều kiện B=C và D=100”.
Câu hỏi được viết dưới dạng ngôn ngữ đại số quan hệ như sau:
π
A
(σ
B=C and D=100
(R
×
S))

Nếu đưa phép chọn D=100 vào bên trong phép tích Đề - các, sẽ được:
π
A
(σ
B=C
(R
×
σ
D=100
(S)))
và sau đó chuyển phép chọn σ
B=C
của tích Đề - các thành phép kết nối bằng sẽ được:
)((
100
SR
D
CB
A =
=
σπ

Có thể còn nhiều cách khác nữa, như vậy, một câu hỏi có thể có nhiều cách thực
hiện.
Vấn đề đặt ra ở đây là: Cần phải thao tác ra sao để giảm chi phí thời gian xử lý câu
hỏi, đặc biệt cần thiết nhất là giảm đến mức có thể các truy xuất ngoài (tức là thao tác với
bộ nhớ thứ cấp như băng đĩa từ).
Rõ ràng phép tính cuối cùng đỡ tốn kém thời gian hơn rất nhiều. Cụ thể chỉ chọn trên
quan hệ S những bộ có giá trị
100

=
D
thì số bộ lấy ra sẽ ít hơn toàn bộ số bộ của cả quạn
hệ S. Số bộ được chọn ra xong từ S mới đem kết nối với quan hệ trên R. Phép kết nối này
chỉ chọn ra bộ nào thuộc R mà có giá trị tại B bằng bộ có giá trị tại C mới được lấy ra. Như
vậy chi phí thực hiện sẽ tốt hơn lấy tích Đề - các của
SR ×
, rồi mới chọn trong kết quả
những bộ có giá trị tại B bằng giá trị tại C.
Qua ví dụ đơn giản trên đủ để cho thấy tối ưu hóa là cần thiết.
Quá trình tối ưu hóa câu hỏi thường được chia làm hai pha: tối ưu hóa logic và tối ưu
hóa vật lí. Tối ưu hóa logic cho phép viết lại câu hỏi dưới dạng chuẩn tắc đơn giản và được
tối ưu hóa về mặt logic, cóc nghĩa không tính tới các chi phí truy cập dữ liệu. Tối ưu hóa
vật lí thực hiện chọn các thuật toán tốt nhất cho các toán tử mức thấp có tính tới kích thước
dữ liệu và các đường truy cập sẵn có.
Tối ưu hóa logic được thực hiện ở mức của đại số quan hệ, trong khi tối ưu hóa vật lí
cho phép, nói riêng, thiết lập các chú giải. Tối ưu hóa vật lí cần tới một mô hình chi phí để
NTD – Khoa Tin – ĐHSP Huế
3
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
ước lượng chi phí của mỗi phương án thực thi nhằm chọn được phương án tối ưu hay gần
tối ưu.
Phần còn lại của chương được tổ chức như sau:
Mục 2: Trình bày về các mục tiêu của tối ưu hóa.
Mục 3. Dành cho việc nghiên cứu các phương pháp chính của tối ưu hóa logic nhằm
tìm câu hỏi đơn giản nhất tương đương với câu hỏi đã cho và sử dụng một phương pháp
heuristic cấu trúc lại cây đại số để xây dựng một dạng chuẩn tắc.
Mục 4. Nghiên cứu các thuật toán khác nhau truy cập vật lí tới dữ liệu bao gồm phép
chọn, phép chiếu, phép kết nối.
Mục 5. Mô tả mô hình chi phí.

Cuối cùng là tóm lược chương.
Một số phần trong chương này được trích dẫn trong [1].
2. Các mục tiêu của tối ưu hóa
2.1. Câu hỏi tĩnh và câu hỏi động
Trước hết bộ tối ưu hóa cần phân biệt được hai loại câu hỏi này.
Câu hỏi tĩnh (Static query): là câu hỏi SQL thường được tích hợp vào một chương
trình ứng dụng trong đó mã lệnh thực hiện nó đã biết được cố định, thường được thực hiện
nhiều lần. Loại câu hỏi này đáng được tối ưu hóa vì việc tối ưu hóa được thực hiện chỉ
một lần khi biên dịch chương trình có chứa câu hỏi, để sau đó nó được thực hiện hàng
nghìn, hàng vạn lần. Câu hỏi SQL có thể được tham số hóa, các giá trị hằng được truyền
bởi các biến của chương trình. Vì vậy, bộ tối ưu hóa phải có khả năng tối ưu hóa các câu
hỏi được tham số hóa, chẳng hạn một tân từ như SO_LUONG = $x, trong đó x là một biến
chương trình.
Câu hỏi động (Dynamic query): là câu hỏi SQL thường được thiết lập theo kiểu
tương tác (trực tuyến) với mã không biết trước, thường chỉ được thực hiện một lần. Với
loại câu hỏi này, không nên tốn quá nhiều thời gian vào việc tìm phương án thực thi tối ưu
hoặc gần tối ưu vì câu hỏi chỉ thực hiện một lần vì thời gian để xử lí một câu hỏi như vậy
sẽ là tổng của thời gian tìm một phương án tối ưu và thời gian thực thi phương án.
2.2. Phân tích câu hỏi
Như đã được chỉ rõ trong hình 1, thoạt đầu câu hỏi được phân tích về mặt cú pháp,
kiểm tra tên các quan hệ và các thuộc tính trong câu hỏi có trong lược đồ CSDL không,
phân tích tính đúng đắn của điều kiện trong câu hỏi. Tiếp đến, câu hỏi được biến đổi về
dạng chuẩn tắc, dạng chuẩn hội hay chuẩn tuyển.
Từ câu hỏi đã được phân tích, phần lớn các hệ thống tạo sinh ra một cây phép toán
của đại số quan hệ (chiếu, chọn, kết nối, hợp, hiệu, giao), có thể được mở rộng với các
phép toán gộp và các phép sắp xếp, được gọi là cây đại số hay cây quan hệ (đôi khi còn
gọi là cây xử lí (processing tree)).
Như vậy, cây đại số là cây nhị phân biểu diễn một câu hỏi trong đó các nút lá biểu
diễn các quan hệ, các nút trung gian biểu diễn các phép toán của đại số quan hệ, nút gốc
biểu diễn kết quả của câu hỏi, còn các cung biểu diễn các dòng dữ liệu giữa các phép toán.

NTD – Khoa Tin – ĐHSP Huế
4
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
Cây đại số quan hệ cũng tương tự như cây nhị phân biểu diễn biểu thức mà các bạn đã học
ở phần cấu trúc cây nhị phân trong môn học Cấu trúc dữ liệu và Giải thuật.
Từ cây đại số, có thể tạo sinh một phương án thực thi bằng cách đi dọc theo cây, từ
lá tới gốc. Một phép toán có thể được thực hiện theo kiểu hướng tập (set oriented
execution) bao gồm việc tính tập tất cả các bộ của các quan hệ đầu vào của một toán từ
trước khi định giá toán tử đó.
Như vậy, nếu phép toán O
1
không dùng các kết quả của phép toán O
2
thì các phép
toán O
1
và O
2
có thể được thực hiện song song. Kiểu thực hiện này có thể thích hợp cho
những thuật toán có khả năng làm việc hiệu quả trên các tập (trên cơ sở của phép sắp xếp
chẳng hạn).
Một phép toán cũng có thể được thực hiện theo kiểu từng bộ một hay kiểu đường ống
(pipeline execution). Cụ thể là khởi động phép toán sớm nhất có thể, ngay khi đã có một bộ
cho ít nhất một toán hạng.
Đối với phép toán một ngôi, chỉ cần có một bộ là đủ. Như vậy, có thể thực hiện hai
phép chọn liên tiếp theo kiểu đường ống, có nghĩa là bắt đầu thực hiện phép chọn thứ hai
ngay khi có một bộ (hay một trang gồm một số bộ) được sinh bởi phép chọn thứ nhất.
Các phép toán hai ngôi, như phép hiệu r – s chẳng hạn, chỉ có thể bắt đầu sau khi đã
tính được đầy đủ toán hạng s. Như vậy, kiểu đường ống chỉ có khả năng thực hiện một
toán hạng.

2.3. Các chức năng của bộ tối ưu hóa
Bộ tối ưu hóa có mục tiêu là tìm ra một phương án thực thi được tối ưu hóa.
Có thể định nghĩa một phương án thực thi là một chương trình (có thể song song),
các phép toán sơ cấp phải thực hiện để định giá câu trả lời cho một câu hỏi, thường được
thực hiện làm hai giai đoạn: viết lại (rewriting) và lên phương án (planning).
Viết lại là giai đoạn của tối ưu hóa bao gồm biến đổi câu hỏi về mặt logic để có được
một biểu diễn chuẩn tắc. Giai đoạn này chứa đựng khía cạnh ngữ nghĩa trong đó có thể tính
tới các ràng buộc toàn vẹn và khía cạnh cú pháp, đưa các điều kiện trong câu hỏi về dạng
chuẩn (hội hay chuyển) và gán cho các toán tử đại số một thứ tự cố định.
Lên phương án là giai đoạn của tối ưu hóa bao gồm cả việc sắp xếp lại các toán tử
đại số (đã được thực hiện ở giai đoạn viết lại), chọn các thuật toán và kiểu thực hiện
(hướng tập hay đường ống).
Như vậy giai đoạn viết lại tạo ra một cây logic, còn giai đoạn lên phương án sẽ bổ
sung các chú giải để có một phương án thực thi.
Đương nhiên, ta tìm cách tối ưu hóa thời gian trả lời, có nghĩa làm cực tiểu thời gian
cần thiết cho việc thực thi câu hỏi. Vấn là tạo sinh một cây tối ưu và chọn những thuật toán
tốt nhất để thực hiện mỗi toán tử và cây đại số xét trong toàn thể. Muốn vậy, phải tối ưu
hóa đồng thời:
- Số các vào/ra
- Sự song song giữa các toán tử.
- Thời gian tính cần thiết (thời gian CPU)
NTD – Khoa Tin – ĐHSP Huế
5
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
Việc tối ưu hóa được thực hiện phụ thuộc nói riêng vào thứ tự các phép toán trong
cây đại số được dùng các thuật toán được giữ lại. Do đó, điều quan trọng là thiết lập được
các quy tắc cho phép từ cây ban đầu phát sinh ra tất cả các phương án có thể, để sau đó
chọn được phương án với chi phí nhỏ nhất. Thực sự là các cây rất lớn, nên ta thường phải
định nghĩa các quy tắc heuristic để xác định một cây gần tối ưu.
3. Tối ưu hóa logic hay phép viết lại

Phép viết lại cho phép thu được một biểu diễn chuẩn tắc của câu hỏi, dưới dạng một
cây đại số trong đó các phép toán được sắp thứ tự và các điều kiện được viết dưới dạng
chuẩn.
Phép viết lại có thể bao gồm phép viết lại ngữ nghĩa và phép viết lại cú pháp.
3.1. Phân tích và viết lại ngữ nghĩa
Loại phân tích này nhằm xác định tính đúng đắn của câu hỏi, tìm các câu hỏi tương
đương trên cơ sở thao tác trên điều kiện của câu hỏi này nhờ vào các ràng buộc toàn vẹn.
Để thực hiện việc phân tích ngữ nghĩa của câu hỏi, có thể dùng đồ thị liên kết các
quan hệ (Relation connection graph), đồ thị các kết nối, đồ thị liên kết các thuộc tính
(Attribute connection graph).
Đồ thị liên kết các quan hệ là đồ thị trong đó:
1. Một đỉnh được kết hợp với mỗi xuất hiện của một quan hệ.
2. Một phép kết nối được biểu diễn bởi một cung giữ hai nút biểu diễn các quan hệ
được kết nối.
3. Một phép chọn được biểu diễn bởi một khuyên của nút ứng với quan hệ trên đó
phép chọn được áp dụng.
4. Phép chiếu cuối cùng được biểu diễn bởi một cung từ nút quan hệ tới một nút đặc
biệt là nút kết quả.
Đồ thị các kết nối là đồ thị liên kết các quan hệ trong đó chỉ giữ lại các nút và các
cung biểu diễn các phép kết nối giữa chúng.
Đồ thị liên kết các thuộc tính là đồ thị trong đó:
1. Một đỉnh được kết hợp với mỗi thuộc tính hay một hằng được tham chiếu (hay dẫn
trỏ).
2. Một phép kết nối được biểu diễn bởi một cung giữa các thuộc tính tham gia.
3. Một phép chọn được biểu diễn bởi một cung giữa một thuộc tính và một hằng.
Đồ thị liên kết các thuộc tính cho phép phát hiện các điều kiện trong câu hỏi có chứa
mâu thuẫn, nếu có chứa một chu trình không được thỏa mãn bởi các hằng. Nó cũng cho
phép phát hiện các câu hỏi tương đương với câu hỏi đã cho nhờ tính bắc cầu.
Hai hình vẽ dưới đây theo thứ tự các đồ thị liên kết các quan hệ và đồ thị liên kết các
thuộc tính của câu hỏi được nói ở ví dụ ở trên có biểu diễn bằng SQL như sau.

SELECT A
FROM R, S
WHERE R.B=S.C AND S.D=100
NTD – Khoa Tin – ĐHSP Huế
6
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
Bây giờ ta nói về tính đúng đắn của một câu hỏi. Có thể phân biệt hai loại câu hỏi
không đúng đắn sau:
1. Một câu hỏi có thể được phát biểu không chỉnh vì trong câu hỏi có chứa những
phần vô ích: người viết câu hỏi rõ ràng đã quên một phép kết nối trong câu hỏi.
2. Một câu hỏi có thể chứa đựng một mâu thuẫn không có bộ nào thỏa được, như với
câu hỏi “Tìm số hiệu nhà cung cấp có cung cấp mặt hàng P2 với số lượng lớn hơn 40 và
nhỏ hơn 20”.
Sau đây là hai kết quả quan trọng cho phép loại bỏ các câu hỏi không đúng đắn,
trong trường hợp các câu hỏi hội (không có phép hay là) với các toán tử so sánh =, <, >, ≤,
≥.
a. Một câu hỏi thường là được phát biểu không chỉnh nếu đồ thị liên kết các quan hệ
của nó không liên thông [4]. Thực vậy, mọi đồ thị con không được nối với nút kết quả sẽ
không tham gia vào kết quả đó.
b. Một câu hỏi là mâu thuẫn nếu đồ thị liên kết các thuộc tính của nó được bổ sung
thêm các cung so sánh giữa các hằng tạo ra một chu trình không thỏa được [4]. Thực vậy,
khi đó không có bộ nào có thể thỏa được những tân từ của chu trình, kiểu như
SO_LUONG < 20 và SO_LUONG>40.
Nhớ rằng không phải các kỹ sư lập trình ra câu hỏi truy vấn mà là các người sử dụng
nghiệp dư mới là người truy vấn dữ liệu và kỹ sư lập trình có nhiệm vụ phân tích câu hỏi
ấy trước khi cho thực thi!
Trong các phần sau chúng ta sẽ thấy vai trò của các đồ thị nói trên trong quá trình cài
đặt tối ưu câu truy vấn là rất lớn.
3.1.1. Các câu hỏi tương đương do bắc cầu.
Trước hết ta cho một định nghĩa chính xác về các câu hỏi tương đương (Equivalent

queries).
Định nghĩa
NTD – Khoa Tin – ĐHSP Huế
R S
S.D=100
R.B=S.C
k
q
A
7
R.
B
S.
D
10
0
=
R.
B
R.
B
S.
C
=
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
Hai câu hỏi là tương đương nếu và chỉ nếu chúng cho cùng kết quả với mọi thể hiện
(ngoại diên) có thể của cơ sở dữ liệu.
Từ việc nghiên cứu đồ thị liên kết các thuộc tính có thể phát hiện ra các câu hỏi
tương đương.
Thực vậy, mọi cặp thuộc tính (A

i
, B
j
) được nối với nhau bằng một đường đi từ A
i
tới
B
j
mà trên mọi cạnh của đường đi đều có nhãn đẳng thức, thì do tính bắc cầu, phải có A
i
=
B
j.
Khi đó chẳng hạn trong đồ thị liên kết ban đầu, nếu thay đồ thị con ta sẽ thu được
một câu hỏi tương đương.
6.3.1.2. Các câu hỏi tương đương được suy từ các ràng buộc toàn vẹn.
Một cách khác để tạo sinh các câu hỏi tương đương là sử dụng các ràng buộc toàn
vẹn [2,3]. Bài toán được đặt ra như sau.
Cho câu hỏi thỏa điều kiện Q và một tập các ràng buộc toàn vẹn I
1
, I
2
,…I
n
.
Nếu Q mâu thuẫn với một trong các ràng buộc I
i
, câu hỏi có câu trả lời là rỗng.
Ngược lại, chỉ cần định giá điều kiện Q’ (đơn giản hơn Q) sao cho:
I

1
∧ I
2
∧… ∧I
n
∧ Q’→Q
(Các kiến thức về biểu diễn tri thức trong Trí tuệ nhân tạo giúp bạn về Q’ đơn giản
hơn Q, I
1
∧ I
2
∧… ∧I
n
∧ Q’→Q … là gì).
Ta minh họa các phép biến đổi ngữ nghĩa qua một số ví dụ đơn giản.
Xét cơ sở dữ liệu về việc cung cấp hàng hóa, gồm 3 quan hệ sau:
S(S#, SNAME, CITY, STATUS)
P(P#, PNAME, COLOR, ADDR, WEIGHT)
SP(S#, P#, QTY)
Với S#, P# lần lượt là mã số của nhà cung cấp hàng hóa và hàng hóa.
SNAME, PNAME lần lược là tên nhà cung cấp và tên mặt hàng.
CITY là địa chỉ của nhà cung cấp và ADDR là địa chỉ lưu trữ của mặt hàng.
Trước hết hãy xét biểu thức sau:
Π
P#
(SP

S)
Phép kết nối ở đây là phép kết nối tự nhiên trên thuộc tính S# là thuộc tính chung của
hai quan hệ S và SP. Mặt khác vì S# là một khóa ngoại của quan hệ SP và là khóa của quan

hệ S, suy ra mọi bộ của quan hệ SP đều kết nối với một bộ nào đó của quan hệ S và sẽ
đóng góp một giá trị của S# vào kết quả cuối cùng. Nói cách khác, nhờ vào ràng buộc toàn
vẹn ta thấy trong biểu thức trên, phép kết nối là không cần thiết và biểu thức đã cho tương
đương với biểu thức.
Π
P#
(SP)
Giả sử rằng CSDL cung cấp hàng hóa của ta thỏa ràng buộc “mọi mặt hàng màu đỏ
phải được lưu trữ ở Huế”. Khi đó một câu hỏi khác phức tạp như: “Tìm các nhà cung cấp
chỉ cung cấp các mặt hàng màu đỏ và có địa chỉ là thành phố của ít nhất một mặt hàng
NTD – Khoa Tin – ĐHSP Huế
8
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
được anh ta cung cấp” có thể được biến đổi thành một câu hỏi tương đương đơn giản hơn:
“Tìm các nhà cung cấp ở Huế chỉ cung cấp các mặt hàng màu đỏ”.
Gần đây, tối ưu hóa ngữ nghĩa được phát triển trong ngữ cảnh của các hệ CSDL
hướng đối tượng và sematic web. Các ràng buộc tương đương, kéo theo, tính duy nhất của
khóa, ràng buộc bao hàm đặc biệt hữu ích để biến đổi và làm đơn giản các câu hỏi.
3.2. Viết lại cú pháp và cấu trúc lại cây đại số
Đây là các kỹ thuật cơ sở nhằm biến đổi cây đại số và thay đổi thứ tự thưc hiện các
phép toán, dựa trên tính giao hóan và kết hợp của các phép toán đại số quan hệ.
3.2.1. Biểu thức tương đương
Trong phần này ta xem quan hệ như là tập các ánh xạ từ tập các thuộc tính U lên
miền giá trị D (xem lại phần các định nghĩa CSDL quan hệ - chương mô hình CSDL quan
hệ).
Lúc đó một biểu thức đại số quan hệ có các hạng thức là biến quan hệ R
1
, R
2
, ,R

n
,
các quan hệ hằng được xác định từ k - bộ của các quan hệ (r
1
,r
2
, ,r
n
) trong đó r
i
là quan hệ
trên lược đồ R
i
và thay thế r
i
vào R
i
khi đánh giá biểu thức.
Hai biểu thức E
1
và E
2
được gọi là tương đương viết tắt là E
1
≡E
2
nếu chúng biểu
diễn cùng một ánh xạ, nghĩa là nếu thay thế cùng các quan hệ cho tên các lược đồ tương
ứng ở hai biểu thức cho ra cùng một kết quả.
Với cách hiểu tương đương trên ta đưa ra một số qui tắc chuyển dịch đại số quan hệ

thông thường sau đây.
3.2.2. Các qui tắc liên quan tới phép kết nối và phép tích Đề-các
(1) Quy tắc giao hoán của phép nối và phép tích Đề - các
Với E
1
và E
2
là hai biểu thức quan hệ và F là biểu thức điều kiện
1221
EEEE
FF

≡
1221
EEEE ∗≡∗
1221
EEEE ×≡×
Lưu ý: Nếu hiểu quan hệ là tập các bộ thì phép kết nối, phép tích Đề-các, phép kết
nối tự nhiên không có tính giao hoá, vì thứ tự thuộc tính trong quan hệ kết quả bị thay đổi.
(2) Quy tắc kết hợp của phép kết nối và phép tích Đề - các
)E(EEE)E(E
3
F
2
F
13
F
2
F
1

2121

≡
)()(
321321
EEEEEE
∗∗≡∗∗
)()(
321321
EEEEEE
××≡××
Các qui tắc liên quan đến phép chọn và chiếu
(3) Dãy các phép chiếu
Nếu dãy các thuộc tính A
1
, ,A
n
nằm trong dãy các thuộc tính B
1
, ,B
m
thì:
)())((
21
21
21
EE
n
m
n

AAA
BBB
AAA
⋅⋅⋅
⋅⋅⋅
⋅⋅⋅
Π≡ΠΠ
NTD – Khoa Tin – ĐHSP Huế
9
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
(4) Dãy các phép chọn
)())((
2121
Ε≡Ε
∧
FFFF
σσσ
(5) Giao hoán phép chọn và phép chiếu
))(())((
1
221
EE
FAAAAAAF
nn
σσ
⋅⋅⋅⋅⋅⋅
Π≡Π
Nếu F chỉ liên quan đến các thuộc tính B
1
, ,B

m
không nằm trong A
1
, ,A
n
thì:
))(())((
1
221
1 21
EE
FAAABmBAAAFAnAA
nn
σσ
⋅⋅⋅⋅⋅⋅
Π≡ΠΠ
(6) Giao hoán phép chọn và phép tích Đề - các
Nếu tất cả các thuộc tính trong F là các thuộc tính của E
1
thì:
2121
)()( EEEE
FF
×≡×
σσ
Nếu F = F
1
∧ F
2
, với F

1
chỉ liên quan với E
1
và F
2
liên quan với E
2
, ta có
)()()(
212
211
EEEE
FFF
σσσ
×≡×
Nếu F
1
chỉ liên quan với E
1
, còn F
2
liên quan cả với E
1
và E
2
thì
))(()(
2121
12
EEEE

FFF
×≡×
σσσ
(7) Giao hoán phép chọn và một phép hợp
)()()(
2121
EEEE
FFF
σσσ
∪≡∪
(8) Giao hoán phép chọn và một phép hiệu
)()()(
2121
EEEE
FFF
σσσ
−≡−
(9) Giao hoán giữa phép chọn và kết nối tự nhiên
)(*)()*(
2121
EEEE
FFF
σσσ
≡
(10) Giao hoán một phép chiếu và một phép tích Đề các
A
1
, ,A
n
là tập thuộc tính bao gồm B

1
, ,B
m
của E
1
và C
1
, ,C
k
của E
2
thì
)()()(
2121
111
EEEE
kmn
CCBBAA ⋅⋅⋅⋅⋅⋅⋅⋅⋅
Π×Π≡×Π
(11) Giao hoán một phép chiếu với một phép hợp
)()()(
2121
11
1
EEEE
nn
n
AAAA
AA
⋅⋅⋅⋅⋅⋅

⋅⋅⋅
Π∪Π≡∪Π
Lưu ý rằng phép chọn với phép giao; phép chiếu với phép hiệu lại không có tính giao
hoán, hãy cho một phản ví du.
Phép chứng minh của các qui tắc trên có thể tham khảo trong [5]
3.2.3. Tối ưu hóa trên cơ sở đại số
Sau đây là 6 chiến lược tối ưu hoá câu hỏi tổng quát [5].
- Thực hiện phép chọn càng sớm càng tốt.
Việc làm này nhằm làm giảm số bộ tham gia vào biểu thức, vì vậy làm giảm đi kích
cỡ của kết quả trung gian, nên chi phí truy cập bộ nhớ, cũng như lưu trữ cũng ít đi.
- Tổ hợp một số phép chọn với tích Đề - các thành phép kết nối.
NTD – Khoa Tin – ĐHSP Huế
10
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
Vì phép kết nối, nhất là kết nối bằng chi phí thực hiện "rẻ" hơn phép tích Đề-các.
- Tổ hợp các chuỗi phép toán một ngôi như phép chọn và chiếu.
Nhằm làm giảm đi số phép toán.
- Tìm các biểu thức con chung trong một biểu thức
Nếu kết quả của một biểu thức con chung (biểu thức xuất hiện nhiều lần) là một quan
hệ không lớn và có thể đọc nó từ bộ nhớ thứ cấp với ít thời gian thì nên tính toán biểu thức
đó trước. Thường là đưa các kết quả của các biểu thức con chung đó thành một view.
Nhờ các biểu thức con chung này ta có thể phân rã câu hỏi thành các câu hỏi con đơn
giản hơn, vấn đề này sẽ được bàn trong phần tiếp theo.
- Xử lý các tệp trước
Hai vấn đề xử lý quan trọng cần thực hiện trước khi thực hiện các câu hỏi, cũng như
bất cứ công việc khai thác dữ liệu nào là: sắp xếp trước và thiết lập các tệp chỉ số cho các
tệp dữ liệu. Lúc này rõ ràng việc thực hiện các câu hỏi sẽ dễ dàng, nhanh chóng hơn.
- Đánh giá trước khi thực hiện tính toán
Khi lựa chọn trình tự thực hiện các phép tính trong một biểu thức, hoặc lựa chọn
một trong hai đối số của phép tính hai ngôi cần tính toán xem chi phí thực hiện các phép

tính đó (số phép tính, thời gian, dung tích bộ nhớ ) từ đó có được chi phí tổng quát cho
cách thực hiện câu hỏi. Chẳng hạn nên thực hiện các phép kết nối có kết quả hẹp nhất
trước trong một dãy các phép kết nối.
Cụ thể, chúng ta có thể áp dụng các qui tắc đã nêu ở phần trên để đưa ra một trình tự
có tính heuristic nhằm tối ưu hóa các biểu thức quan hệ.
Bước 1: Sử dụng quy tắc 4) để tách một phép chọn
)(
1
E
n
FF ⋅⋅⋅∧
σ
thành chuỗi các phép
chọn
)))(((
1
⋅⋅⋅⋅⋅⋅ E
n
FF
σσ
Bước 2: Đối với mỗi phép chọn, sử dụng các quy tắc từ (4) đến (9) để di chuyển
phép chọn xuống càng thấp càng tốt.
Bước 3: Đối với mỗi phép chiếu, sử dụng các quy tắc (3), (10), (11) và quy tắc (5)
suy rộng để di chuyển phép chiếu xuống càng thấp càng tốt.
Bước 4: Sử dụng các quy tắc (3), (4) và (5) để tổ hợp các phép chọn và các phép
chiếu thành một phép chọn, một phép chiếu , hoặc một phép chọn được một phép chiếu
theo sau.
Bước 5. Nhóm các phép chiếu tuần tự , giữ các thuộc tính, bỏ đi các phép chiếu
không cần thiết như chiếu A
i

với ∀i.
Thí dụ
Xét CSDL quản lý tư liệu với các quan hệ sau:
BOOKS(TITLE, AUTHOR, PNAME,LC_NO): quan hệ sách
PUBLISHERS(NAME, PADDR, PCITY, CARD_NO): quan hệ nhà xuất bản.
NTD – Khoa Tin – ĐHSP Huế
11
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
BORROWERS(NAME, ADDR, CITY, CARD_NO): quan hệ độc giả.
LOANS(CARD_NO, LC_NO, DATE): quan hệ sổ mượn
Trong đó các thuộc tính là:
PNAME: Tên nhà sản xuất.
LC_NO: Số thư viện.
PADDR:Địa chỉ của nhà sản xuất.
PCITY: Thành phố nơi có nhà sản xuất
CARD_NO: Số thẻ của độc giả
ADDR: Địa chỉ độc giả DATE
CITY: Thành phố nơi độc giả ở
DATE: Ngày mượn sách
Để lưu trữ thông tin về sách, có thể giả thiết thêm rằng, có một khung nhìn XLOANS
bao gồm một số thông tin bổ sung về sách được mượn. XLOANS là kết nối tự nhiên của
quan hệ BOOKS,BORROWERS , và LOANS và nó có thể được định nghĩa là:
))(( BOOKSBORROWERSLOANS
FS
××
σπ
Trong đó:
)_._.()_._.( NOLCLOANSNOLCBOOKSNOCARDLOANSNOCARDBORROWERSF
=∧==


Còn S là danh sách các thuộc tính trong khung nhìn:
TITLE, AUTHOR, PNAME, LC-NO, NAME, ADDR, CITY, CARD_NO, DATE
Cần đưa ra một danh sách những cuốn sách đã được mượn trước ngày 08/03/02 bằng
cách đặt một câu vấn tin:
))((
2002.03.08
XLOANS
DATETITLE <
σπ
Sau khi thay thế XLOANS biểu thức trên có cây biểu diễn như trong hình sau:

×
↓
↓
↓
↓
=∧=
<
)_._.()_._.(
,_.,,,,_,,,
2002.03.08
NOCARDLOANSNOCARDBORROWERSNOLCLOANSNOLCBOOKS
DATENOCARDBORROWERSCITYADDRNAMENOLCBOOKSAUTHORTITLE
DATE
TITLE
σ
π
σ
π



NTD – Khoa Tin – ĐHSP Huế
12
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
BOOKS

×


BORROWERS
LOANS
Nguyên tắc tối ưu hóa là tách phép chọn F thành hai phép phép chọn với các điều
kiện tương ứng:
BOOKS.LC_NO=LOANS.LC_NO và
BORROWERS.CARD_NO=LOANS.CARD_NO
Sau đó chúng ta di chuyển ba phép chọn càng xuống thấp càng tốt. Phép chọn
))((
2002.03.08
BOOKSBORROWERSLOANS
DATE
××
<
σ
có thể thay bằng:
(
BOOKSBORROWERSLOANS
DATE
××
<
))(

2002.03.08
σ
)
Bây giờ chúng ta di chuyển phép chọn này xuống dưới đến mức “tối đa” Phép chọn
theo điều kiện BOOKS.LC_NO = LOANS.LC_NO không thể di chuyển xuống bên dưới
tích Đề - các bởi vì nó chứa một thuộc tính của BOOKS còn thuộc tính kia không phải của
BOOKS. Tuy nhiên phép chọn theo BORROWERS.CARD_NO = LOANS.CARD_NO có
thể di chuyển xuống dưới để áp dụng vào tích:
BORROWERSLOANS
DATE
×
<
)(
2002.03.08
σ
Chú ý rằng LOANS.CARD_NO là tên của một thuộc tính trong:
)(
2002.03.08
LOANS
DATE<
σ
.
Bởi vì nó là thuộc tính của LOANS và kết quả chọn cũng sử dụng các thuộc tính đó.
Kế tiếp chúng ta có thể tổ hợp hai phép chiếu thành một là
TITLE
π
nhờ qui tắc (3).
Cây kết quả như sau:

TITLE

π

↓

NOLCLOANSNOLCBOOKS
−=−

σ

↓

×



BOOKS


NOLCLOANSNOCARDBORROWERS _._.
=
σ


×

BORROWERS


2002.03.08
<

DATE
σ

LOANS

NTD – Khoa Tin – ĐHSP Huế
13
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
Sau đó nhờ qui tắc (5) mở rộng chúng ta có thể thay
TITLE
π
và
NOLCLOANSNOLCBOOKS
−=−

σ
bằng chuỗi sau:

TITLE
π

NOLCLOANSNOLCBOOKS _
=−
σ

NOLCLOANSNOLCBOOKSTITLE _.,.,
−
π
Chúng ta áp dụng qui tắc (10) để thay phép chiếu cuối cùng bằng:


NOLCLOANSNOLCBOOKSTITLE _.,.,
−
π
Để áp dụng cho BOOKS và
NOLCLOANS _.
π
thì áp dụng cho toán hạng bên trái của tích
Đề - các bên trên cây kết quả trên.
Phép chiếu sau tương tác với phép chọn bên dưới nó nhờ qui tắc (5) mở rộng tạo ra
chuỗi:

NOLCLOANS
−
.
π

NOCARDLOANSNOCARDBORROWERS
−=−

σ


NOCARDLOANSNOCARDBORROWERSNOLCLOAN −−− .,.,.
π
Phép chiếu cuối cùng được chuyển cho tích Đề - các nhờ qui tắc (10) và chuyển một
phần cho phép chọn
2002.03.08
<
DATE
σ

nhờ qui tắc (5) mở rộng.Sau đó chúng ta phát hiện
rằng trong biểu thức:
DATENOCARDLOANSNOLCLOANS ,.,.
−−
π
Phép chiếu này không cần thiết bởi vì tất cả các thuộc tính của LOANS đều được sử
dụng. Do đó chúng ta loại bỏ phép chiếu này.Cây kết quả cuối cùng được trình bày như
sau:

TITLE
π

↓


NOLCLOANSNOLCBOOKS
−=−

σ

↓

×

TITLENOLCBOOKS ,.
−
π

NOLCLOANS
−

.
π
NTD – Khoa Tin – ĐHSP Huế
14
BOOKS
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn

↓

×


NOCARDBORROWERS
−
.
π


NOLCLOANS _.
π


BORROWERS

2002.03.08
<
DATE
σ

LOANS

3.3. Sắp thự tự các phép toán trên cơ sở phân tách câu hỏi
Phép phân tách câu hỏi dựa trên phân tách và thay thế bộ cho phép sắp xếp các phép
toán lại theo thứ tự: chọn, nửa nối, kết nối.
Phép tách nhằm lấy đi một thành phần của một câu hỏi có đúng 1 biến chung với
phần còn lại của câu hỏi.
Phép thay thế bộ thay thế một trong số các biến của câu hỏi, mỗi lần một bộ.
Phép tách được ưu tiên thực hiện trước phép thế bộ.
Xét ví dụ sau, để quản lí hàng hóa trong việc vận chuyển bằng tàu hỏa, ta có cơ sở dữ
liệu gồm hai quan hệ:
TAU (TTU_TAU, TTU_TOA)
TOA(TTU_TOA, KIEUTOA,TLU_TOA, NLU_TOA, TITR, GA)
Trong đó
TTU_TAU: thứ tự tàu
TTU_TOA: thứ tự toa
TLU_TOA: trọng lượng toa
NLU_TOA: năng lực toa
TITR : tình trạng
GA: Ga tàu mà toa đó đỗ
Giả sử có yêu cầu: “Hãy đưa ra danh sách các kiểu toa của đoàn tàu có thứ tự tàu
4002”, với câu lệnh truy vấn trong SQL như sau:
Select KIEUTOA
From TAU,TOA
Where (TOA.TTU_TOA =TAU.TTU_TOA) and (TAU.TTU_TAU=4002).
Có thể tách câu vấn tin trên thành hai câu vấn tin con và thực hiện chúng theo trình
tự như trình bày dưới đây:
Selec * INTO T1
NTD – Khoa Tin – ĐHSP Huế
15
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
From TAU

Where TAU.TTU_TAU= 4002
Và:
Selec KIEUTOA
From TOA
Where TOA.TTU_TOA= T1.TTU_TOA
Dưới đây sẽ trình bày một cách tổng quát vấn đề và sẽ nghiên cứu vì sao có thể tạo ra
được các câu hỏi con như trên.
Trong SQL các câu hỏi thường gặp là câu hỏi có dạng tổng quát:
Select A
1
, ,A
n
From R
1
, ,R
n
Where F
1
and F
2

Với F
1
, F
2
là các mệnh đề chọn hoặc mệnh đề kết nối.
Một câu hỏi là tách được với một biến (quan hệ) tách X
m
, nếu có thể biểu diễn dưới
dạng:

Select A
1
, A
2
, A
n
From R
1
, R
2
, ,R
n

Where F
1
(X
1
, ,X
m
) and F
2
(X
m
,X
m+1
, ,X
n
)
Như vậy để một câu hỏi có thể tách được, danh sách các biến trong biểu thức điều
kiện trong mệnh đề WHERE có thể biểu diễn dưới dạng and của hai biểu thức điều kiện

đều có chứa biến X
m
, những biến còn lại chỉ có mặt nhiều nhất là một lần ở trong hai biểu
thức thành phần.
Sử dụng các khái niệm đồ thị liên kết quan hệ và đồ thị liên kết thuộc tính, để biểu
diễn câu hỏi, ta có thể nhận ra các thành phần có thể tách được của các câu hỏi.
Ví dụ: Xét CSDL quản lý đường sắt, gồm các quan hệ sau:
Quan hệ đường:DUONG (TTU_DG, GA)
Quan hệ tàu: TAU (TTU_TAU, TTU_TOA)
Quan hệ hiện trạng: HTR (TTU_TAU, TTU_DG, TTU_NG)
Ở đây:
TTU_TOA: Thứ tự TOA; TTU_DG: Thứ tự đường; GA: Tên ga; TTU_TAU: Thứ
tự tàu; TTU_NG: Ngày khởi hành.
Với câu hỏi: Hãy cho danh sách các toa khởi hành từ ga HUẾ vào ngày 05.01.02.
Q
0
Selec TTU_TOA
NTD – Khoa Tin – ĐHSP Huế
16
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
From DUONG, TAU, HTR
Where (DUONG.GA = “HUE" )
And (HTR.TTU_NG = ‘05.01.02’)
And (DUONG.TTU_DG = HTR.TTU_DG)
And (HTR.TTU_TAU = TAU.TTU_TAU)
Câu hỏi trên có thể tách thành thành bốn câu hỏi con Q
1
, Q
2
, Q

3
, Q
4
.
Q
1
Select TTU-TAU,TTU-DG INTO T
1
From HTR
Where HTR.TTU-NG =”05.01.02”
Q
2

Select TTU-DG INTO T
2
From DUONG
Where DUONG.GA=”HUE”
Q
3
Select TTU-DG,T
1
.TTU-TAU INTO T
3
From T
1
, T
2
Where T
1
.TTU-DG=T

2
.TTU-DG
Q
4
Select TTU-TOA
From TAU, T
3

Where TAU.TTU-TAU= T
3
.TTU-TAU
Bạn hãy vẽ đồ thị liên kết quan hệ và liên kết thuộc tính cho câu hỏi Q
0
để nhận ra kỹ
thuật tách câu hỏi trên.
Các câu hỏi Q
1
, Q
2
có thể thực hiện một cách độc lập và theo một thứ tự bất kỳ, thâm
chí có thể song song. Điều này thực sự có lợi nếu cơ sở dữ liệu được xử lý trên các Server
có thể thực hiện song song hay trên các máy trạm trong thời gian máy trạm rỗi.
Nhận xét:
Nguyên tắc của phép tách là chia đồ thi đồ thị nối thành các đồ thị con riêng biệt
được nối với nhau bởi một cầu (một cung được gọi là cầu, nếu loại nó ra đồ thị thì số miền
liên thông của đồ thị sẽ tăng lên một) và mỗi đồ thị con tương ứng với một câu hỏi con có
thể được tách.
Trong phép tách trên, câu hỏi Q
3
và Q

4
là không tách nữa, nhưng có thể làm gọn hơn
nhờ phép thay thế bộ. Ví dụ giả sử các tàu thỏa các điều kiện chọn trong T
3
chỉ có các
TTU-TAU có bao gồm các giá trị {TN1, TN3, TN5} thì Q
4
có thể viết lại dạng sau :
NTD – Khoa Tin – ĐHSP Huế
17
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
Q
4
Select TTU-TOA
From TAU
Where (TAU.TTU-TAU=’TN1’)or (TAU.TTU-TAU=’TN3’)or
(TAU.TTU-TAU=’TN5’).
3.4. Dùng phép nửa nối để giảm kích thước của quan hệ
Nhắc lại định nghĩa phép nửa nối.
Định nghĩa: Cho hai quan hệ r xây dựng trên R(U1)và s trên S(U2). Phép nửa nối
của r và s, ký hiệu là r < s là một quan hệ trên lược đồ R gồm các bộ của phép kết nối tự
nhiên r*s chiếu lên R.
Tức là: r < s = {t: t∈
sr ∗
.R}
Hơn nữa ta thấy: r < s= r *(s.R∩S).
Như vậy nếu muốn liên kết hai quan hệ r, s nhưng quan hệ kết quả chỉ cần giữ lại các
thuộc tính của r. Ta chỉ cần sử dụng phép nửa nối giữa r và s, chứ không cần đến phép nối.
Vì như vậy sẽ làm giảm đi kích thước các quan hệ tham gia vào phép kết nối nhằm tăng tốc
độ thực hiện.

Ví dụ
Ta có CSDL quản lý việc sản xuất và uống rượu gồm các sau:
Uống(Ten, NR,SL) với Ten: Tên người uống; NR: Số hiệu rượu; SL: Số lượng.
Sảnxuất( SX, TênSX, Vùng) với SX: Mã người sản xuất; TenSX: Tên người sản
xuất; Vùng: khu vực sản xuất rượu.
Rượu(NR, tên rượu, năm, độ) với năm: Năm sản xuất
Hàng(NR, SX).
Giả sử có câu hỏi:"Tìm tên người uống rượu sản xuất tại vùng Đá Bạc vào năm 2000,
độ rượu nhỏ hơn 45 độ".
Với SQL câu trả lời sẽ như sau:
SELECT Uống.Tên
FROM Uống, Sảnxuất, rượu, hàng
WHERE (Rượu.Năm=2000) and (Rượu.độ<45) and (Sản
xuất.Vùng='Đá Bạc') and
(Sản xuất.SX=Hàng.SX) and (Rượu.NR=Hàng.NR) and
(Hàng.NR=Uống.NR).
Câu hỏi trên có thể thay thế cho tối ưu hơn như sau:
Bước 1: Hạn chế
SELECT Rượu.NR INTO T1
NTD – Khoa Tin – ĐHSP Huế
18
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
WHERE (Rượu.Độ<45) and (Rượu.Năm=2000)
Và
SELECT Sản xuất.SX INTO T2
WHERE (Sản xuất. Vùng='Đá Bạc')
Sau khi tách câu hỏi như trên, lúc này câu hỏi ban đầu sẽ là
SELECT Uống.Tên
FROM Uống, T1, T2, Hàng
WHERE (T2.SX=Hàng.SX) and (T1.NR=Hàng.NR) and

(Hàng.NR=Uống.NR).
Nếu sử dụng phép nửa nối ta có:
Bước 2: Sử dụng nửa nối
SELECT Hàng.NR, Hàng.SX INTO T3
FROM Hàng, T1
WHERE Hàng.NR=T1.NR
Và câu hỏi ban đầu sẽ được viết lại là
SELECT Uống.Tên
FROM Uống, T2, T3
WHERE (T2.SX=T3.SX) and (T3.NR=Uống.NR)
Sau đó câu hỏi này được tách thành
SELECT T3.NR INTO T4
FROM T3, T2
WHERE (T3.SX=T2.SX)
Và
SELECT Uống.Tên INTO T5
FROM Uống, T4
WHERE (Uống.NR=T4.NR)
Kết quả cuối cùng được đưa vào T5.
Phép phân tách, thay thế bộ và sử dụng nửa nối là một heuristic sắp thứ tự các toán
tử tinh tế hơn nhằm thực hiện trước tiên các phép chọn, tiếp đó là sắp thứ tự các phép kết
nối để làm xuất hiện những phép nửa kết nối có thể. Sở dĩ làm như vậy, vì các phép nửa
kết nối thường có tác dụng thu nhỏ kích thước các quan hệ, nên có hy vọng sẽ thu nhỏ kích
thước các quan hệ trung gian và số các thao tác vào/ra. Và như vậy, so với heuristic cấu
trúc lại cây đại số, trong đó hoàn toàn không có sắp thứ tự các phép kết nối, thì chiến lược
phân tách câu hỏi được xem là tốt hơn.
NTD – Khoa Tin – ĐHSP Huế
19
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
Vấn đề thực sự chính là sắp thứ tự các phép kết nối và tổng quát hơn là phép hai

ngôi. Phép viết lại là một tiếp cận cũng đã có tính tới ít nhiều việc sắp thứ tự các phép toán
mà không cần tới ước lượng kích thước kết quả của các phép kết nối. Cách tiếp cận đó rõ
ràng không đủ để thu được một phương án thực thi với chi phí nhỏ nhất vì nó không cho
phép sắp thứ tự các toán tử một cách tối ưu cũng như không cho phép chọn các thuật toán
tối ưu cho mỗi phép toán.
4. Các toán tử vật lí.
Trước khi nói tới tối ưu hóa vật lí, cần phải hiểu về các thuật toán truy cập các bảng
(quan hệ). Các thuật toán này thực hiện các toán tử của đại số quan hệ và là trung tâm của
mô tơ trong hệ quản trị CSDL chịu trách nhiệm thực thi các phương. Dưới đây, chúng ta
tập trung vào các phép chọn, chiếu và phép kết nối.
4.1. Các thống kê của CSDL.
Để thảo luận về các kĩ thuật định giá các phép toán quan hệ, cần phải dùng đến
những thống kê của CSDL được lưu giữ trong thư mục hệ thống. Để minh họa, chúng ta
tóm tắt một số thống kê chính được lưu giữ trong hai sản phẩm thương mại: DB2 và
Ingres.
Sau đây là một vài thống kê chính có trong DB2.
Với mỗi bảng (quan hệ) cơ sở:
- Số bộ (lực lượng) của bảng.
- Số trang được chiếm giữ bởi bảng.
- Phần của “không gian bảng” (table space) được chiếm giữ bởi bảng đó.
Với mỗi cột của bảng cơ sở:
- Số các giá trị phân biệt trong cột.
- Giá trị lớn thứ hai trong cột.
- Giá trị nhỏ thứ hai trong cột.
- Chỉ với các cột có chỉ mục, mười giá trị xuất hiện nhiều nhất trong cột và
số lần xuất hiện của chúng.
Với mỗi chỉ mục:
- Một chỉ dẫn cho biết đó là một “chỉ mục dồn cụm” (clustering index) hay
không (tức chỉ mục được dùng để dồn cụm vật lí đặt cạnh nhau trên đĩa đối với các
dữ liệu có quan hệ logic với nhau).

- Nếu là chỉ mục dồn cụm, phần của bảng chỉ mục vẫn còn trong dãy dồn
cụm.
- Số các trang là trong chỉ mục đó.
- Số các mức trong chỉ mục.
Đối với hệ Ingres, các thống kê chính được lưu giữ gồm:
* Đối với mỗi bảng cơ sở:
- Số bộ của bảng.
- Số các trang sơ cấp cho bảng.
NTD – Khoa Tin – ĐHSP Huế
20
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
- Số các trang tràn cho bảng.
* Với mỗi cột của bảng cơ sở:
- Số các giá trị phân biệt trong cột.
- Giá trị cực đại, cực tiểu, trung bình trong cột.
- Các giá trị hiện có trong cột và số lần xuất hiện của chúng.
Chú ý là các thống kê nói trên không được cập nhật mỗi khi CSDL được cập nhật vì
làm như vậy sẽ rất công phu và tốn kém. Thực sự là những thống kê này sẽ được cập nhật
có chọn lọc bằng một chương trình tiện ích của hệ thống theo yêu cầu của người quản trị
CSDL. Đối với hệ DB2, đó là tiện ích RUNSTAS, còn đối với hệ Ingres, là tiện ích
OPTIMIZEDB.
Cho R và S là hai quan hệ có số bộ theo thứ tự là n và m. Gọi N và M là kích thước,
tính theo trang, theo thứ tự của R và S. Trong sự phân tích, ta quan tâm tới hai loại chi phí:
chi phí I/O và chi phí CPU. Tổng chi phí cho định giá một phép toán hay cho một phương
án thực thi là một tổng có trọgn số của chi phí I/O và chi phí CPU. Chi phí I/O thường là
chi phí có tính chi phối (vượt trội). Để định giá chi phí CPU, ta dùng số các phép so sánh
và/hay số các bộ cần tìm. Có hai phương pháp được dùng để định giá cho phí I/O.
Phương pháp thứ nhất dùng tổng số trang được đọc hay viết. Phương pháp này có
nhược điểm là không phân biệt I/O đối với trang ngẫu nhiên và trang tuần tự. Phương pháp
thứ hai dùng số các thao tác I/O được khởi đầu. Một thao tác I/O có thể đọc/ghi nhiều

trang. Chẳng hạn sự khác nhau giữa một thao tác I/O đọc/ghi 10 trang với thao tác I/O
đọc/ghi 500 trang.
Trong môi trường nhiều người dùng, thường khó biết được số thực sự các thao tác
I/O. Chẳng hạn, hãy xét X trang dữ liệu được lưu trữ trong không gian nhớ liên tiếp (tuần
tự). Khi đó X trang này có thể được đọc vào bằng một thao tác I/O nếu đó là yêu cầu I/O
duy nhất và bộ nhớ đệm đủ lớn để lưu giữ chúng. Tuy nhiên cũng vẫn X trang đó, có thể
đọc vào, sử dụng nhiều thao tác I/O khi có nhiều yêu cầu I/O đồng thời (tương tranh). Ví
dụ vừa nêu cũng minh họa rằng, trong môi trường đa người dùng, khó có thể biết được số
I/O cho trang ngẫu nhiên. Thực vậy, nếu X trang trên có thể được đọc bởi một thao tác I/O
thì chỉ cần một trang ngẫu nhiên I/O. Tuy nhiên, nếu cần tới nhiều thao tác I/O thì phải tốn
nhiều trang ngẫu nhiên I/O.
Như vậy cả hai phương án đều có thể dẫn tới sự không chính xác. Ta sẽ dùng phương
pháp thứ nhất để tiến hành phân tích, trừ khi phương pháp thứ hai có tác động rõ rệt tới
chiến lược xử lí, và trong trường hợp đó, ta sẽ dùng cả hai phương pháp.
Trong việc phân tích chi phí I/O, để đơn giản, ta sẽ bỏ qua chi phí của việc đưa ra kết
quả của một định giá, vì mục đích của việc phân tích chi phí là để tìm ra một phương án
thực thi hiệu quả nhất. Còn kích thước của kết quả cuối cùng không phụ thuộc vào chiến
lược được sử dụng, nên việc bỏ qua chi phí của việc đưa ra kết quả không ảnh hưởng gì tới
việc tìm chiến lược hiệu quả nhất.
4.2. Định giá phép chọn.
NTD – Khoa Tin – ĐHSP Huế
21
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
Xét phép chọn σ
Aopa
(R), trong đó A là một thuộc tính, a là một hằng thuộc Dom (A),
op ∈{=, ≠, <, ≤, >, ≥)
Nếu op là ≠ thì hầu hết các bộ của R sẽ thỏa điều kiện chọn, và trong trường hợp này,
quét toàn bộ quan hệ dường như là cách tốt nhất để định giá phép chọn hơn là dùng bất kì
cấu trúc chỉ mục nào. Dưới đây ta sẽ giả sử rằng op không là ≠.

Chi phí của việc định giá một phép chọn liên quan chặt chẽ với số bộ R thỏa điều
kiện chọn.
Định nghĩa (Hệ số chọn).
Hệ số chọn của “A op a” trên R, kí hiệu là S
A opa
(R) là số phần trăm các bộ của R
thỏa điều kiện chọn “A op a”
Rõ ràng 0≤ S
A opa
(R)≤1. Hệ số chọn đối với một điều kiện bất kì có thể được ước
lượng trên cơ sở một số thống kê đã biết và một vài giả thiết về sự phân bố dữ liệu của các
giá trị trong cột A của R. Ngoài n là số bộ của R, những thống kê này, như đã biết, bao
gồm dist (A), số các giá trị phân biệt của A trong R; min (A), giá trị nhỏ nhất của A trong
R; max (A), giá trị lớn nhất của A trong R. Một giả thiết thường dùng là xem các giá trị
của A thỏa sự phân bố đều giữa min (A) và max(A). Dựa vào các thống kê nói trên và giả
thiết về sự phân bố đều, có thể dễ dàng ước lượng được S
A opa
(R).
Chẳng hạn S
A = a
(R) có thể được ước lượng là 1/dist(A); còn S
A > a
(R) được ước lượng
là (max(A) – a)/(max(A) – min(A)).
Vì những giá trị thực sự trong cột A có thể sai lệch đáng kể với sự phân bố đều, các
hệ số chọn được ước lượng trên cơ sở của giả thiết đó có thể là không tốt. Để giải quyết
vấn đề này, nhiều hệ CSDL duy trì các thống kê chi tiết về các giá trị của mỗi thuộc tính.
Các thống kê đó điển hình ở dạng của một histogram (biểu đồ). Ý tưởng cơ bản là phân
hoạch các giá trị của A thành các tập con rời nhau và lưu trữ các thống kê tóm lược của
mỗi tập con sao cho phân bố thực các giá trị của A có thể được xấp xỉ tốt hơn.

Gọi k là số bộ của R thỏa điều kiện “A op a”. Khi đó k được ước lượng là n. S
A opa
(R). Chi phí cho việc định giá phép chọn σ
A opa
(R) được phân tích như sau:
Trường hợp 1: Đường truy cập nhanh không có sẵn hoặc không dùng. Có hai trường
hợp nhỏ.
a. Các bộ của quan hệ được lưu trữ theo các giá trị đã được sắp của A. Trong trường
hợp này, có thể dùng thuật toán tìm kiếm nhị phân. Chi phí CPU sẽ là O(logn + k), còn chi
phí I/O sẽ là O(logN + [k/n.N]), trong đó N là số trang cần thiết để lưu giữ các bộ của R,
còn [k/n.N] là số trang cần để lưu giữ k bộ thỏa điều kiện chọn.
b. Các bộ không được lưu trữ theo các giá trị được sắp xếp của A. Trong trường hợp
này, cần phải quét tuần tự tất cả các bộ của R. Chi phí CPU là O(n), còn chi phí I/O là
O(N).
Trường hợp 2: Có sử dụng đường truy cập nhanh. Có hai trường hợp nhỏ.
a. Các bộ của quan hệ được lưu trữ theo các giá trị được sắp của A. Đây là trường
hợp khi đường truy cập nhanh là chỉ mục được dồn cụm. Vì tất cả cá bộ được chọn được
lưu trữ cùng nhau và phải mất một số không đổi các bước (như đã được chỉ rõ trong phần
NTD – Khoa Tin – ĐHSP Huế
22
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
“Tổ chức vật lí của CSDL”, một B
+
cây thường có độ cao không quá 3 hay 4 mức) để tìm
bộ được chọn thứ nhất khi sử dụng đường truy cập nhanh, chi phí CPU sẽ là O(k), còn chi
phí CPU là O([k/n.N]).
b. Các bộ không được lưu trữ theo các giá trị được sắp của A. Đây là trường hợp khi
đường truy câp nhanh là một chỉ mục không dồn cục. Vì mỗi bộ được chọn có thể tìm
được sau một số không đổi các phép so sánh khi dùng chỉ mục, chi phí CPU sẽ là O(n).
4.3. Định giá phép chiếu.

Xét phép chiếu Π
A1, A2 , At
(R) trong đó A
1
, A
2
,….A
t
là các thuộc tính của R.
Trường hợp 1: Các hàng dư (giống nhau) được giữ nguyên. Như đã biết, trong SQL,
các hàng dư chỉ được lấy khi dùng câu select distinct. Trong trường hợp này, phép chiếu
được định giá bằng cách quét đọc mỗi bộ một lần. Do đó chi phí CPU là O
(n)
còn chi phí
I/O là O(N).
Trường hơp 2: Các hàng dư được lấy đi. Việc định giá được thực hiện làm ba bước.
Bước 1: Quan hệ được quét đọc và phép chiếu có giữ các bộ dư được tính.
Bước 2: Kết quả của bước thứ nhất được sắp xếp, và như vậy các bộ dư phải xuất
hiện trong các vị trí kề nhau.
Bước 3: Kết quả của bước thứ hai được quét đọc và các bộ dư được lấy đi.
Chi phí CPU được chi phối bởi quá trình sắp xếp và chi phí là O(nlogn). Chi phí I/O
được chi phối bởi hai bước đầu. Với bước một, chi phí I/O và O(N). Bước hai nhìn chung
đòi hỏi một phép sắp xếp ngoài vì bộ nhớ không thể chứa hết tất cả các dữ liệu cần được
sắp xếp.Gọi W là kích thước kết quả của bước một:
W = n.(Σ length (A
i
))/kích thước trang.
Khi đó chi phí I/O cho bước thứ hai là O(W.logW). (6.1)
4.4. Định giá phép kết nối.
Trong số những phép toán của đại số quan hệ hay được dùng nhất (chọn, chiếu, kết

nối) phép kết nối là phép toán tốn kém nhất và cũng được nghiên cứu nhiều nhất. Trong
mục này, sẽ giới thiệu một số thuật toán quen biết để định giá phép kết nối. Để đơn giản,
ta chỉ xét phép kết nối “bằng” của hai quan hệ R và S dạng R

R.A=S.B
S, trong đó n và m
theo thứ tự là số bộ của R và S, còn N và M là kích thước tính theo trang của chúng.
Không giảm tổng quát, giả thiết là quan hệ nhỏ hơn, có nghĩa M ≤ N.
4.4.1. Kết nối chu trình lồng nhau.
Thuật toán này tiến hành so sánh mỗi bộ của R trực tiếp với mọi bộ của S để tìm các
bộ sánh hợp:
for mỗi bộ x trong R do
for mỗi bộ y trong S do
if x[A] = y [B] then return
(x,y)
Theo sự cài đặt trên, R được dùng trong chu trình ngoài và được gọi là quan hệ
ngoài, và tương tự, S được gọi là quan hệ trong.
NTD – Khoa Tin – ĐHSP Huế
23
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
Như sẽ thấy, việc chọn quan hệ nào làm quan hệ ngoài/trong là có ý nghĩa đối với
việc tối ưu hóa chi phí I/O, nếu mục tiêu tối ưu là làm cực tiểu số trang I/O. Với thuật toán
này, chi phí CPU luôn là O(n.m). (6.2)
Để định giá chi phí I/O, thuật toán trên cần sửa đổi như sau để thể hiện rõ sự làm
việc theo trang. Gọi K là kích thước (theo trang) của bộ nhớ đệm sẵn có cho phép kết nối.
Rõ ràng, cần có K ≥ 3 vì bộ nhớ đệm cần giữ ít nhất một trang cho mỗi quan hệ R và S, và
một trang để tích lũy kết quả. Trong sự phân tích dưới đây, K được dùng để kí hiệu số
trang của bộ nhớ đệm hiện có cho hai quan hệ kết nối, không tính trang của bộ nhớ đệm
cho kết quả ra.
Trước hết xét trường hợp đặc biệt với K = 2. Khi R là quan hệ ngoài và S là quan hệ

trong, ta có thuật toán được sửa đổi như sau:
for mỗi trang P của R do
for mỗi trang Q của S do
for mỗi bộ x trong P do
for mỗi bộ y trong Q do
if x[A] = y [B] then return (x,y)
Thuật toán này quét quan hệ trong một lần với mỗi trang của quan hệ ngoài. Có
nghĩa nếu quan hệ trong được quét từ trang đầu tới trang cuối cho lần lặp đang xét, thì nó
sẽ được quét từ trang cuối tới trang đầu cho lần lặp tiếp theo. Kết quả là, trang cuối của S
vừa được so sánh với trang hiện hành của R, sẽ trở thành trang đầu tiên của S được so sánh
với trang tiếp theo của R. Theo cách đó trang này của S không phải đọc lại vào bộ nhớ
chính, tiết kiệm một trang I/O. Kĩ thuật này được gọi là quét qua lại (rocking scan). Với
thuật toán cải tiến này, chi phí I/O là:
N + M + (N-1).(M-1) = N.M+1 (6.3)
Với trường hợp đặc biệt này, dễ thấy là nếu S là quan hệ ngoài và R là quan hệ trong,
chi phí I/O là không đổi.
Bây giờ ta xét trường hợp tổng quát khi K là một số nguyên dương bất kì lớn hơn 2.
Không giảm tổng quát, giả sử K<N+M, vì nếu ngược lại, cả R và S đều được giữ trọng
trong bộ nhớ đệm và chi phí I/O khi đó sẽ là M + N.
Giả sử R sử dụng K
1
trang nhớ đệm, còn S sử dụng K
2
trang nhớ đệm, với K
1
+ K
2
=
K, K
1

≤ N và K
2
≤ M. Khi R là quan hệ ngoài và S là quan hệ trong, ta có thuật toán sau:
for mỗi K
1
trang P của R do
for mỗi K
2
trang Q của S do
for mỗi bộ x trong P do
for mỗi bộ y trong Q do
if x[A] = y [B] then return (x,y)
Vì R chỉ phải đọc một lần; với K
1
trang đầu tiên của R, phải đọc toàn bộ quan hệ S,
và với mỗi K
1
trang tiếp sau của R (có tất cả (N/K
1
 - 1) những nhóm K
1
trang của R như
vậy), chỉ phải đọc M – K
2
trang của S, do có cùng kĩ thuật quét qua lại. Chi phí I/O là:
NTD – Khoa Tin – ĐHSP Huế
24
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
N + M + ([N/K
1

] 1) ).(M – K
2
) (6.4)
Có thể chứng minh rằng biểu thức (6.4) đạt cực tiểu khi K
1
= min {N, K – 1}. Cụ thể
là, quan hệ ngoài có thể dùng một số trang đệm nhiều theo sự cần thiết (chỉ cần không quá
N trang đệm).
Phân tích tương tự như trên, có thể chứng minh rằng, khi S là quan hệ ngoài, chi phí
I/O sẽ là: M + N + ([M/K
2
] – 1).(N-K
1
) (6.5)
Và biểu thức (6.5) đạt cực tiểu khi K
2
= min{M,K – 1}.
Còn có thể chứng minh được rằng, khi bỏ qua hàm trần, cực tiểu đạt được bởi biểu
thức (6.4) không bé hơn cực tiểu đạt được bởi biểu thức (6.5).
Chẳng hạn, xét trường hợp khi N = 20, M = 10, và K = 15. Trong trường hợp này,
biểu thức (6.4) đạt cực tiểu khi K
1
= 14 và chi phí I/O xấp xỉ (bỏ qua hàm trần) bằng 34;
còn biểu thức (6.5) đạt cực tiểu khi K
2
= 10 và chi phí là 30. Chú ý là khi có tính tới hàm
trần, kết quả không phải bao giờ cũng đúng.
Chẳng hạn với N = 20, M = 10, và K = 5 thì cực tiểu đạt được bởi biểu thức (6.4) và
66, trong cực tiểu đạt được bởi biểu thức (6.5) là 68.
Phân tích trên đã được tiến hành trên cơ sở số trang I/O là độ do chi phí I/O. Có thể

tóm tắt như sau:
Nếu tiêu chuẩn tối ưu hóa là làm cực tiểu số trang I/O thì dùng quan hệ nhỏ hơn làm
quan hệ ngoài, và để cho quan hệ ngoài sử dụng số trang đệm nhiều theo sự cần thiết, tức
bằng với min {M, K – 1}.
Tuy nhiên, nếu tiêu chuẩn tối ưu hóa là làm cực tiểu số thao tác I/O lúc ban đầu (lúc
khởi đầu) thì có thể dùng một chiến lược cấp phát bộ nhớ đệm khác như sau. Chú ý là mỗi
thao tác I/O có thể đọc K
1
trang của R hay K
2
trang của S. Do đó, R có thể được đọc vào
với [N/K
1
] thao tác I/O. Tương tự, S có thể được đọc vào với [M/K
2
] thao tác I/O. Khi R
được dùng làm quan hệ ngoài, R cần được đọc vào một lần; với K
1
trang đầu của R, S cần
được quét vào một lần; với mỗi một trong số ([N/K
1
] – 1) nhóm K
1
trang của R, sẽ tiết
kiệm được một thao tác I/O khi đọc S theo kĩ thuật quét qua lại. Do đó, khi R được dùng
làm quan hệ ngoài, số các thao tác I/O cần thiết là:
[N/K
1
] + [M/K
2

] + ([N/K
2
] – 1). (M[M/K
2
] – 1) = [N/K
1
].[M/K
2
] + 1 (6.6)
Có thể chứng minh được rằng, khi bỏ qua các hàm trần, biểu thức (6.6) đạt cực tiểu
khi K
1
= K
2
= K/2. Nói cách khác, để làm cực tiểu số các thao tác I/O, R và S cần dùng một
số trang nhớ đệm như nhau. Từ biểu thức (6.6) cũng dễ thấy là nếu tiêu chuẩn tối ưu hóa là
làm cực tiểu số thao tác I/O thì việc dùng R hay S làm quan hệ ngoài là như nhau.
4.4.2. Kết nối sắp xếp trộn.
Thuật toán kết nối này gồm hai bước:
1. Sắp xếp hai quan hệ (theo thứ tự tăng chẳng hạn) của các thuộc tính kết nối, cụ thể
là sắp xếp R trên A và sắp xếp S trên B, nếu như chúng chưa được sắp xếp.
2. Thực hiện một phép kết nối trộn (kết nối hợp nhất). Trước hết ta xét trường hợp
khi các giá trị của ít nhất một trong hai thuộc tính kết nối là phân biệt. Đây là trường hợp
thường gặp vì phần lớn các phép kết nối được thực hiện giữa các thuộc tính có mối quan hệ
NTD – Khoa Tin – ĐHSP Huế
25