Giáo trình Cơ sở dữ liệu - Trịnh Hoàng Nam

 hết được biên dịch 
thành biểu thức đại số quan hệ tương đương – được biểu diễn ở dạng cây biểu thức 
– và sau đây được tối ưu hóa. Trong nhiều trường hợp câu truy vấn SQL có cấu 
trúc phức tạp, bao gồm nhiều câu truy vấn đơn kết hợp lại với nhau. Chúng ta sẽ 
biểu diễn từng đoạn truy vấn đơn giản đó thành những biểu thức đại số quan hệ và 
biến đổi chúng về dạng đơn giản hơn nhưng cho ra cùng kết quả. Câu truy vấn đơn 
có thể bao gồm một phát biểu SELECT – FROM – WHERE, bao gồm cả mệnh đề 
ORDER BY, GROUP BY và HAVING. Tuy nhiên, đối với câu truy vấn lồng, các 
câu truy vấn cần phải được xử lý như những câu truy vấn đơn riêng rẽ. Ví dụ 9.1 
minh họa cho một câu truy vấn lồng như thế. 
VÍ DỤ 9.1: Biểu diễn câu truy vấn SQL bằng (các) biểu thức đại số quan hệ. 
Xét câu truy vấn SQL sau đây trong cơ sở dữ liệu COMPANY: 
Q1: SELECT EName 
 FROM EMPLOYEE 
 WHERE ESalary > ( SELECT MAX (ESalary) 
FROM EMPLOYEE 
WHERE DNum = 5) 
Câu truy vấn lồng này được biểu diễn bằng hai câu truy vấn đơn như sau: 
Q1a: SELECT MAX (ESalary) 
 FROM EMPLOYEE 
 WHERE DNum = 5 
Q1b: SELECT EName 
 FROM EMPLOYEE 
 WHERE ESalary > C 
Với C là kết quả trả về từ câu truy vấn Q1a. 
Hai biểu thức đại số quan hệ tương đương với hai câu truy vấn này lần lượt là: 
ℑMAX ESalary (σDNum=5(EMPLOYEE)) 
 Email: namth@buh.edu.vn 253 
piEName(σESalary>C(EMPLOYEE)) 
 
Tóm lại, một khi nói đến tối ưu hóa một câu truy vấn SQL, chúng ta tìm cách biểu 
diễn câu truy vấn đó về dạng biểu thức đại số quan hệ. Sau đó chúng ta tiến hành 
tối ưu hóa biểu thức đại số quan hệ này thông qua cây đại số quan hệ bằng các 
phương pháp tối ưu hóa thích hợp để nhận được một biểu thức được đánh giá là 
tốt hơn, nhưng cho ra cùng kết quả với biểu thức ban đầu. Cuối cùng, chúng ta 
biểu diễn biểu thức này bằng một câu truy vấn SQL. 
9.2 PHƯƠNG PHÁP ƯỚC LƯỢNG CÂY ĐẠI SỐ 
QUAN HỆ 
Như đã trình bày ở trên, để tối ưu hóa câu truy vấn, chúng ta tối ưu hóa biểu thức 
đại số quan hệ tương ứng với câu truy vấn đó. Đồng thời, mỗi biểu thức đại số 
quan hệ có thể biểu diễn được bởi một cây đại số quan hệ. Như vậy, chúng ta cần 
phải tối ưu hóa cây đại số quan hệ. 
Vấn đề đặt ra ở đây là dựa trên tiêu chuẩn nào để chúng ta xác định cây đại số 
quan hệ hiện có đã tối ưu hay chưa. Nói cách khác, chúng ta cần phải ước lượng 
chi phí thực hiện các phép tính trên cây đại số quan hệ để từ đó phát hiện ra được 
những sự điều chỉnh cần thiết để tiết kiệm được chi phí thực hiện. 
Chúng ta bắt đầu đánh giá cây biểu thức đại số quan hệ từ các phép toán ở mức 
phấp nhất (tức là các biểu thức tại đáy của cây). Các phép toán này có đầu vào là 
các quan hệ được lưu trữ vật lý trong cơ sở dữ liệu; đồng thời kết quả trả về của 
chúng được lưu trữ trong các quan hệ tạm. Tiếp theo, chúng ta có thể sử dụng các 
quan hệ tạm này làm đầu vào để thực hiện các phép toán ở mức trên tiếp theo 
trong cây biểu thức. Bây giờ đầu vào của phép toán có thể là các quan hệ tạm hoặc 
là các quan hệ được lưu trữ trong cơ sở dữ liệu. Chúng ta cứ tiếp tục như thế cho 
đến khi đạt đến đỉnh của cây biểu thức. 
 Email: namth@buh.edu.vn 254 
Việc đánh giá cây biểu thức được thực hiện thông qua quá trình ước lượng chi phí 
của từng phép toán chọn, chiếu và kết. Chi phí ở đây được hiểu là chi phí thực 
hiện các phép toán trong biểu thức và chi phí lưu trữ quan hệ tạm lên đĩa cứng để 
thực hiện các phép toán kế tiếp. Giả sử các bản ghi của quan hệ tạm được xếp vào 
một vùng đệm (có kích thước là ff), và khi vùng đệm bị đầy thì chúng sẽ được ghi 
lên đĩa. Khi đó chi phí của thao tác ghi lên đĩa tương đương với nf/ff, với nf là số 
các bộ trong quan hệ tạm cần lưu trữ. 
VÍ DỤ 9.2: Ước lượng chi phí thực hiện của một biểu thức đại số quan hệ. 
Xét cây biểu thức đại số quan hệ sau đây: 
Hình 9.1. Cây biểu thức đại số quan hệ. 
Để ước lượng chi phí của thao tác ghi lên đĩa, chúng ta cần tính tới kích thước của 
ba bảng tạm phát sinh trong quá trình thực hiện câu truy vấn. Đầu tiên đó là bảng 
tạm T1 chứa kết quả của phép chọn trên DEPARTMENT. Kế tiếp khi thực hiện 
phép kết tự nhiên giữa T1 với EMPLOYEE chúng ta có bảng tạm T2. Cuối cùng, 
bảng tạm T3 được tạo để chứa kết quả của phép chiếu trên T2. 
 
9.3 NGUYÊN TẮC TỐI ƯU HÓA BIỂU THỨC ĐẠI 
SỐ QUAN HỆ 
Trong các phép toán đại số quan hệ, phép nhân chéo và phép kết chi phí cao hơn 
so với các phép toán khác. Điều này có thể giải thích như sau. Về cơ bản phép kết 
là sự kết hợp giữa phép chọn từ kết quả của phép nhân chéo, mà trong chương 5 
chúng ta đã tính toán kết quả của phép nhân chéo quan hệ R1 có n1 thuộc tính, m1 
 Email: namth@buh.edu.vn 255 
bộ với quan hệ R2 có n2 thuộc tính, m2 bộ là một quan hệ R3 có n1+n2 thuộc tính và 
m1*m2 bộ. Quan hệ R3 được tạo ra bằng cách kết hợp từng bộ của R1 với từng bộ 
của R2. Như vậy, phép nhân chéo không chỉ gây tốn kém thì không gian lưu trữ mà 
còn rất mất thời gian. 
Để cải thiện chi phí thực hiện cũng như chi phí lưu trữ, các nguyên tắc sau đây 
giúp chúng ta tối ưu hóa câu truy vấn thông qua việc thay đổi trình tự thực hiện 
các phép toán trong biểu thức đại số quan hệ tương đương: 
Một cách khái quát, các nguyên tắc sau đây có thể giúp chúng ta tối ưu hóa câu 
truy vấn thông qua việc thay đổi trình tự thực hiện các phép toán: 
 Ưu tiên thực hiện các phép toán một ngôi nhằm giới hạn khối lượng dữ liệu 
trung gian được lưu trữ trong các bảng tạm, đồng thời cũng làm giảm chi 
phí đọc và ghi bảng tạm vào đĩa cứng. 
 Hạn chế việc thực hiện các phép nhân chéo giữa hai quan hệ với tất cả các 
thuộc tính của chúng. Hạn chế kích thước của các quan hệ tham gia phép 
nhân chéo bằng phép chọn và phép chiếu. 
 Phép kết bằng kết nối các bộ giữa hai quan hệ có giá trị bằng nhau tại các 
thuộc tính trùng tên. Do đó, chi phí thực hiện phép kết bằng sẽ thấp hơn 
nhiều so với chi phí thực hiện phép nhân chéo. 
 Do phép chọn và phép chiếu có tính chất giao hoán và kết hợp, do đó chúng 
ta có thể nhóm các phép chọn và phép chiếu liên tiếp thành một phép toán 
duy nhất nhằm giảm khối lượng dữ liệu trung gian. 
 Xác định các thành phần bị lặp lại trong câu truy vấn. Trong trường hợp sự 
lặp lại này khá thường xuyên, chúng ta nên lập câu truy vấn con để khai 
thác khả năng tính toán và lưu trữ một lần nhưng sử dụng nhiều lần sau đó. 
 Email: namth@buh.edu.vn 256 
 Tiền xử lý các bảng tham gia trong câu truy vấn nhằm giảm thiểu các sự kết 
nối không cần thiết bằng cách sắp xếp, tạo chỉ mục, tạo khung nhìn thích 
hợp,  
 Đánh giá sơ bộ chi phí thực hiện câu truy vấn theo những trình tự thực hiện 
khác nhau. Chi phí trong trường hợp này bao gồm: số phép toán thực hiện, 
chi phí thời gian, không gian lưu trữ,  
9.4 KỸ THUẬT TỐI ƯU HÓA BIỂU THỨC ĐẠI SỐ 
QUAN HỆ 
Các nguyên tắc tối ưu hóa được trình bày ở trên đều có chung một đặc điểm là 
biến đổi các biểu thức đại số về dạng có chi phí thực hiện thấp hơn. Sự biến đổi 
này chỉ thực sự được chấp nhận khi các biểu thức đại số cho ra quan hệ kết quả 
tương đương với nhau. Trong chương 4, chúng ta đã định nghĩa hai quan hệ tương 
đương là hai quan hệ có cùng tập thuộc tính, và quan hệ này là kết quả của sự thay 
đổi thứ tự các thuộc tính, hoặc thứ tự các bộ của quan hệ kia. 
Khi thực hiện các phép toán trong biểu thức đại số quan hệ, chúng ta phải quan 
tâm tới trình tự thực hiện các phép toán trong trường hợp không sử dụng dấu 
ngoặc đơn. Các phép toán một ngôi có thứ tự ưu tiên cao hơn so với các phép toán 
hai ngôi. 
Tối ưu hóa thực chất là xác định trình tự thực hiện các phép toán trong biểu thức 
đại số nhằm tiết kiệm chi phí thực hiện, không gian lưu trữ cũng như thời gian 
thực hiện nhưng không làm thay đổi kết quả trả về. Ba phép toán được sử dụng 
thường xuyên nhất trong biểu thức đại số là chọn, chiếu và kết. Phép chọn và phép 
chiếu cho ra quan hệ kết quả có kích thước nhỏ hơn quan hệ ban đầu. Trong khi 
đó, kết quả của phép chiếu là một quan hệ có kích thước lớn hơn rất nhiều so với 
các quan hệ tham gia. Dựa trên các tính chất này, chúng ta xây dựng các kỹ thuật 
tối ưu hóa và áp dụng chúng trong từng trường hợp cụ thể. 
 Email: namth@buh.edu.vn 257 
9.4.1. Các quy tắc biến đổi biểu thức đại số quan hệ 
Để bắt đầu, chúng ta thống nhất các ký hiệu được sử dụng trong biểu thức đại số 
quan hệ như sau: 
 F1, F2,  là các điều kiện 
 L1, L2,  là tập các thuộc tính 
 E1, E2,  là các biểu thức đại số quan hệ 
 σ là phép chọn 
 pi là phép chiếu 
 × là phép nhân chéo 
 ⋈F là phép kết có điều kiện 
 ⋈ là phép kết tự nhiên 
Quy tắc 1: Giao hoán phép kết và phép nhân chéo 
Nếu E1 và E2 là hai biểu thức đại số quan hệ và F là điều kiện trên các thuộc 
tính của E1 và E2: 
(R1): E1 ⋈F E2 = E2 ⋈F E1 
(R2): E1 ⋈ E2 = E2 ⋈ E1 
(R3): E1 × E2 = E2 × E1 
Hình 9.2. Biểu diễn quy tắc (1) bằng cây biểu thức. 
Quy tắc 2: Kết hợp phép kết và phép nhân chéo 
Nếu E1, E2 và E3 là các biểu thức đại số quan hệ, F1 là điều kiện trên các thuộc 
tính của E1 và E2, F2 là điều kiện trên các thuộc tính của E2 và E3 
 Email: namth@buh.edu.vn 258 
(R4): (E1 ⋈F1 E2) ⋈F2 E3 = E1 ⋈F1 (E2 ⋈F2 E3) 
(R5): (E1 ⋈ E2) ⋈ E3 = E1 ⋈ (E2 ⋈ E3) 
(R6): (E1 × E2) × E3 = E1 × (E2 × E3) 
Hình 9.3. Biểu diễn quy tắc (2) bằng cây biểu thức. 
Quy tắc 3: Thay thế nhiều phép chiếu liên tiếp bằng một phép chiếu duy nhất 
Nếu E là biểu thức đại số quan hệ và L1, L2 là hai tập thuộc tính của E, L1 ⊆ L2 
(R7): piL2(piL1(E)) = piL2(E) 
Hình 9.4. Biểu diễn quy tắc (3) bằng cây biểu thức. 
Quy tắc 4: Thay thế nhiều phép chọn liên tiếp bằng một phép chọn duy nhất 
Nếu E là biểu thức đại số quan hệ và F, F1, F2, , Fn là các điều kiện trên tập 
thuộc tính của E, F = F1 ∧ F2 ∧  ∧ Fn 
(R8): σF1(σF2(σF1(E))) = σ F1 ∧ F2 ∧  ∧ Fn (E) = σF(E) 
 Email: namth@buh.edu.vn 259 
Hình 9.5. Biểu diễn quy tắc (4) bằng cây biểu thức. 
Quy tắc 5: Giao hoán các phép chọn 
Nếu E là biểu thức đại số quan hệ và F1, F2 là hai điều kiện trên tập thuộc tính 
của E: 
(R9): σF1(σF2(E)) = σF2(σF1(E)) 
Hình 9.6. Biểu diễn quy tắc (5) bằng cây biểu thức. 
Quy tắc 6: Giao hoán phép chọn và phép chiếu 
Nếu E là biểu thức đại số quan hệ và F là điều kiện trên tập thuộc tính L của E: 
(R10): piL(σF(E)) = σF(piL(E)) 
Nếu E là biểu thức đại số quan hệ, L1, L2 là hai tập thuộc tính của E (L2 ⊆ L1), 
F là điều kiện trên tập thuộc tính L1 
(R11): piL2(σF(E)) = piL2(σF(piL1(E))) 
Hình 9.7. Biểu diễn quy tắc (6) bằng cây biểu thức. 
 Email: namth@buh.edu.vn 260 
Quy tắc 7: Giao hoán phép chọn và phép nhân chéo 
Nếu E1, E2 là hai biểu thức đại số quan hệ và F là điều kiện trên tập thuộc tính 
L của E1: 
(R12): σF(E1 × E2) = σF(E1) × E2 
Nếu E1, E2 là hai biểu thức đại số quan hệ, F = F1 ∧ F2, với F1 là điều kiện trên 
tập thuộc tính L1 của E1, F2 là điều kiện trên tập thuộc tính L2 của E2: 
(R13): σF(E1 × E2) = σF1 ∧ F2(E1 × E2) = σF1(E1) × σF2(E2) 
Hình 9.8. Biểu diễn quy tắc (7) bằng cây biểu thức. 
Quy tắc 8: Giao hoán phép chọn và phép hợp 
Nếu E1, E2 là hai biểu thức đại số quan hệ có cùng lược đồ và F là điều kiện 
trên các thuộc tính của hai biểu thức này: 
(R14): σF(E1 ∪ E2) = σF(E1) ∪ σF(E2) 
Hình 9.9. Biểu diễn quy tắc (8) bằng cây biểu thức. 
Quy tắc 9: Giao hoán phép chọn và phép trừ 
Nếu E1, E2 là hai biểu thức đại số quan hệ có cùng lược đồ và F là điều kiện 
trên các thuộc tính của hai biểu thức này: 
 Email: namth@buh.edu.vn 261 
(R15): σF(E1 – E2) = σF(E1) – σF(E2) 
Hình 9.10. Biểu diễn quy tắc (9) bằng cây biểu thức. 
Quy tắc 10: Giao hoán phép chọn và phép kết tự nhiên 
Nếu E1, E2 là hai biểu thức đại số quan hệ và F là điều kiện trên các thuộc tính 
chung của hai biểu thức này: 
(R16): σF(E1 ⋈ E2) = σF(E1) ⋈ σF(E2) 
Hình 9.11. Biểu diễn quy tắc (10) bằng cây biểu thức. 
Quy tắc 11: Giao hoán phép chiếu và phép nhân chéo 
Nếu E1, E2 là hai biểu thức đại số quan hệ, L1, L2 lần lượt là tập các thuộc tính 
của E1 và E2: 
(R17): piL1, L2(E1 × E2) = piL1(E1) × piL2(E2) 
Hình 9.12. Biểu diễn quy tắc (11) bằng cây biểu thức. 
Quy tắc 12: Giao hoán phép chiếu và phép hợp 
Nếu E1, E2 là hai biểu thức đại số quan hệ có cùng tập thuộc tính L: 
(R18): piL(E1 ∪ E2) = piL(E1) ∪ piL(E2) 
 Email: namth@buh.edu.vn 262 
Hình 9.13. Biểu diễn quy tắc (12) bằng cây biểu thức. 
Quy tắc 13: kết hợp phép giao và phép hợp 
Nếu E1, E2 và E3 là các biểu thức đại số quan hệ có tính khả hợp: 
(R19): (E1 ∪ E2) ∪ E3= E1 ∪ (E2 ∪ E3) 
Hình 9.14. Biểu diễn quy tắc (13) bằng cây biểu thức. 
9.4.2. Thuật toán tối ưu hóa biểu thức đại số quan hệ 
Với mục tiêu tối ưu hóa biểu thức đại số quan hệ thông qua việc biến đổi biểu thức 
này bằng cách áp dụng các quy tắc tối ưu hóa trình bày ở phần trên, chúng ta xây 
dựng một trình tự để thực hiện các phép toán trong biểu thức. Trình tự này được 
thể hiện chi tiết trong giải thuật 9.1 được trình bày dưới đây. Tuy nhiên, khi sử 
dụng thuật toán này để tối ưu hóa biểu thức đại số quan hệ, chúng ta cần lưu ý một 
số vấn đề sau đây: 
 Thuật toán tập trung chủ yếu vào nhiệm vụ làm giảm bớt khối lượng dữ liệu 
trung gian chứ không giúp xác định trình tự thực hiện các phép kết. 
 Thuật toán cung cấp một phương án để chúng ta lựa chọn khi thực thi cây 
truy vấn, đây chưa phải là phương án tốt nhất. 
 Các phép biến đổi còn có thể được thực hiện dựa trên tập hợp đầy đủ các 
phép toán đại số quan hệ chứ không chỉ gói gọn vào các phép toán được 
trình bày. 
 Email: namth@buh.edu.vn 263 
 Tối ưu hóa biểu thức đại số quan hệ chỉ là một phần trong chiến lược tối ưu 
hóa câu truy vấn, vì ngoài trình tự thực hiện các phép toán trong biểu thức, 
chúng ta còn có thể tối ưu hóa câu truy vấn bằng các thao tác tiền xử lý dữ 
liệu. Vấn đề này vượt ra khỏi phạm vi của giáo trình cho nên chúng tôi 
không đi sâu vào chi tiết. 
THUẬT TOÁN 9.1: Tối ưu hóa biểu thức đại số quan hệ. 
Đầu vào: Biểu thức đại số quan hệ cần tối ưu (biểu diễn bởi cây biểu thức) 
Đầu ra: Biểu thức đại số quan hệ tối ưu (biểu diễn bởi cây biểu thức) 
Thuật toán: 
Bước 1: Áp dụng quy tắc R4 tách phép chọn phức tạp thành một chuỗi các 
phép chọn liên tiếp. Đối với mỗi phép chọn, tiếp tục áp dụng các quy tắc từ 
R4 đến R11 nhằm đẩy các phép chọn xuống càng sâu càng tốt 
Bước 2: Đối với mỗi phép chiếu, áp dụng các quy tắc R3, R6, R8, R12 để 
chiếu quan hệ trên những thuộc tính cần sử dụng và đẩy các phép chiếu 
xuống càng sâu càng tốt. 
Bước 3: Tổ hợp phép nhân chéo với phép chọn thành phép kết có điều kiện 
Bước 4: Nhận diện các cây con mà các phép toán của nó thực hiện theo 
đường không rẽ nhánh và thực thi chúng. 
 
Để minh họa cho việc áp dụng thuật toán tối ưu hóa biểu thức đại số quan hệ nói 
trên, chúng ta lần lượt xét một ví dụ liên quan đến cơ sở dữ liệu COMPANY được 
sử dụng trong giáo trình này. 
VÍ DỤ 9.3: Tối ưu hóa biểu thức đại số quan hệ. 
Xét biểu thức đại số quan hệ sau đây : 
piEname, ESalary, supervisorSSN, DName (σDnumber = DNum(EMPLOYEE × DEPARTMENT)) 
 Email: namth@buh.edu.vn 264 
Hình 9.15. Cây biểu thức cần được tối ưu hóa. 
Áp dụng thuật toán 9.1 để tối ưu hóa biểu thức đại số quan hệ theo trình tự sau 
đây: 
Bước 1: Không áp dụng, vì không có các phép chọn liên tiếp. 
Bước 2: 
(1) Áp dụng quy tắc (4) để giao hoán phép chọn và phép chiếu: 
Hình 9.16. Áp dụng quy tắc (4) để biến đổi cây biểu thức. 
 (2) Áp dụng quy tắc (12) để giao hoán phép chiếu và phép nhân chéo 
Hình 9.17. Áp dụng quy tắc (12) để biến đổi cây biểu thức. 
Bước 3: Kết hợp phép chọn và phép nhân chéo thành phép kết có điều kiện: 
 Email: namth@buh.edu.vn 265 
Hình 9.18. Kết hợp phép chọn và phép nhân chéo. 
Bước 4: Thực thi các phép toán. 
 
9.5 TỐI ƯU HÓA BẰNG KHUNG NHÌN 
Như đã trình bày ở trên, câu truy vấn thực chất là một dãy các phép toán được 
thực thi liên tiếp, quan hệ kết quả của phép toán trước là đầu vào của phép toán 
sau. Các quan hệ kết quả này nói chung được lưu trữ trong không gian tạm và tự 
động bị xóa đi sau khi biểu thức được thực thi. Đôi khi chúng ta có nhu cầu lưu trữ 
toàn bộ dữ liệu và kết quả tính toán để sử dụng lại mỗi khi có nhu cầu. Khung nhìn 
(view) là một công cụ tỏ ra rất hữu dụng trong những trường hợp như thế nếu 
chúng ta sử dụng khung nhìn như là một công cụ lưu trữ quan hệ kết quả của câu 
truy vấn. Ví dụ sau đây cho biết cách thức tạo khung nhìn View trong SQL. 
VÍ DỤ 9.4: Tối ưu hóa bằng khung nhìn. 
Tạo khung nhìn V1 lưu kết quả của câu truy vấn: Liệt kê số nhân viên, tổng số giờ 
làm việc của mỗi dự án: 
CREATE VIEW V1 AS 
SELECT PNum, COUNT(*), SUM(workHours) 
FROM WORKSON 
GROUP BY PNum 
Rõ ràng, khi có nhu cầu truy vấn liên quan đến số liệu thống kê cho từng dự án, 
khung nhìn này giúp tiết kiệm chi phí cũng như thời gian thực hiện câu truy vấn. 
 Email: namth@buh.edu.vn 266 
Hình 9.19. Cây biểu thức của khung nhìn V1. 
 
Sau khi khung nhìn được tạo ra, chúng ta có thể thực hiện các câu truy vấn có sử 
dụng khung nhìn như là một quan hệ lưu trữ khác trong CSDL. Các bảng dữ liệu 
xuất hiện trong lệnh tạo khung nhìn được gọi là bảng cơ sở của khung nhìn. Trong 
phạm vi giáo trình, chúng ta không đi sâu vào nghiên cứu khung nhìn và các vấn 
đề liên quan, chúng ta chỉ giới hạn vào việc định nghĩa và sử dụng khung nhìn như 
là một công cụ hỗ trợ tối ưu hóa câu truy vấn. 
Giả sử chúng ta có khung nhìn V được định nghĩa từ phép kết nối R ⋈ S. Chúng ta 
có thể sử dụng khung nhìn V này để giảm chi phí thực hiện câu truy vấn R ⋈ S ⋈ 
T. Cụ thể, câu truy vấn này có thể được viết lại là R ⋈ T. Ví dụ sau đây minh họa 
các sử dụng khung nhìn để tối ưu hóa câu truy vấn. 
VÍ DỤ 9.5: Thực hiện câu truy vấn (biểu diễn bằng cây biểu thức). 
Cho biết số nhân viên tham gia từng dự án do phòng số 1 quản lý. 
Cách 1: Không sử dụng khung nhìn, cây biểu thức có dạng như hình 9.19. 
Hình 9.20. Cây biểu thức tương ứng khi không sử dụng khung nhìn. 
Cách 2: Sử dụng khung nhìn V1, cây biểu thức có dạng như hình 9.20. 
 Email: namth@buh.edu.vn 267 
Hình 9.21. Cây biểu thức tương ứng khi không sử dụng khung nhìn. 
Rõ ràng, với việc sử dụng V1, chi phí thực hiện câu truy vấn đã giảm đi đáng kể. 
Ghi chú: Chúng ta còn có thể biến đổi biểu thức này bằng cách áp dụng các quy 
tắc được trình bày ở mục 9.3. 
 
9.6 TÓM TẮT 
Trong các hệ quản trị cơ sở dữ liệu hiện nay, đa người dùng là một đặc trưng quan 
trọng không thể bỏ qua. Theo đó, tại một thời điểm, có thể có rất nhiều câu truy 
vấn được thực thi trên cơ sở dữ liệu. Vấn đề đặt ra là làm thế nào để hệ quản trị cơ 
sở dữ liệu đáp ứng các yêu cầu đó một cách nhanh nhất có thể. Một trong những 
giải pháp được lựa chọn đó là tối ưu hóa câu truy vấn. Trong nhiều trường hợp, 
người sử dụng chủ động thực hiện công việc tối ưu hóa này trước khi cài đặt câu 
truy vấn và yêu cầu hệ quản trị cơ sở dữ liệu thực thi. 
Để tối ưu hóa câu truy vấn chúng ta sử dụng biểu thức đại số quan hệ tương ứng 
với câu truy vấn đó. Chúng ta dựa trên kích thước không gian lưu trữ tạm thời 
trong quá trình thực thi phép toán để ước lượng chi phí của biểu thức đại số quan 
hệ. Bản chất của quá trình tối ưu hóa là tìm cách biến đổi biểu thức hiện có để đạt 
được một biểu thức khác cho kết quả tương tự nhưng có chi phí thấp hơn. Quá 
trình tối ưu được sự hỗ trợ của hàng loạt các quy tắc biến đổi tương đương dựa 
trên ba phép toán cơ bản: chọn, chiếu và nhân chéo. 
 Email: namth@buh.edu.vn 268 
Tiếp theo, chúng tôi giới thiệu một quá trình bốn bước nhằm tối ưu hóa một biểu 
thức đại số quan hệ. Quá trình này thực chất là trình tự áp dụng các quy tắc biến 
đổi tương đương đã nêu ở trên nhằm tạo ra một biểu thức có thể không đơn giản 
hơn, nhưng chi phí thấp hơn so với biểu thức ban đầu. 
Cuối cùng, vì câu truy vấn là một dãy tuần tự gồm nhiều phép toán, kết quả của 
phép toán trước là đầu vào của phép toán sau, chúng ta có thể lưu trữ quan hệ kết 
quả đó trong các khung nhìn khác nhau và sử dụng lại chúng mỗi khi cần thiết. 
Việc sử dụng khung nhìn như thế không chỉ giúp rút ngắn thời gian thực hiện truy 
vấn mà còn góp phần vào việc tối ưu hóa câu truy vấn.