Bài giảng Cơ sở dữ liệu - Nguyễn Quỳnh Chi

Học viện Công nghệ Bưu Chính Viễn thông- Khoa Công nghệ thông tin I 
Hà nội 5/2010 
CƠ SỞ DỮ LIỆU 
BÀI GIẢNG 
DÀNH CHO SINH VIÊN CÔNG NGHỆ 
THÔNG TIN 
NGUYỄN QUỲNH CHI 
Học viện Công nghệ Bưu Chính Viễn thông- Khoa Công nghệ thông tin I 
Hà nội 5/2010 
GIỚI THIỆU 
Học phần Cơ sở dữ liệu cung cấp các kiến thức để sinh viên nắm được các mức trừu tượng hóa 
cơ sở dữ liệu, các mô hình cơ sở dữ liệu, các ngôn ngữ biểu diễn và xử lý dữ liệu, lý thuyết về 
cơ sở dữ liệu quan hệ, quy trình thiết kế một hệ thống cơ sở dữ liệu, các quá trình chuẩn hoá, 
truy vấn dữ liệu. Đồng thời, học phần cũng cung cấp cho sinh viên những kỹ năng để áp dụng 
những lý thuyết để thiết kế một cơ sở dữ liệu trong thực tế và xây dựng ứng dụng cơ sở dữ liệu 
dựa trên một hệ quản trị cơ sở dữ liệu có sẵn. 
Đối tượng chính của bài giảng này là sinh viên ngành Công nghệ thông tin hệ đại học, hệ cao 
đẳng hoặc sinh viên của các ngành khác cũng có thể dùng tài liệu này để tham khảo nhưng khối 
lượng sẽ được lược bỏ đi một phần tuỳ vào từng ngành và hệ đào tạo. 
Sinh viên cần hoàn thành các môn học: Toán rời rạc, Nhập môn logic, Cấu trúc dữ liệu và giải 
thuật trước khi tham gia học môn học này. 
Đây là một môn học tính điểm trung bình sau khi kết thúc cuối kỳ học, trong đó kiểm tra cuối 
kỳ chiếm 70%, bài tập lớn làm theo nhóm (khoảng 3 hoặc 4 người/nhóm) chiếm 20%, quá trình 
tham dự trên lớp chiếm 10%. 
Tổng số gồm 4 đơn vị học trình trong đó 48 tiết lý thuyết giảng trên lớp, 6 tiết cho việc giảng 
viên giải đáp thắc mắc về bài tập và bài tập lớn và 6 tiết cuối cùng dùng để sinh viên thuyết 
trình bài tập lớn trên lớp và trao đổi với giảng viên. 
Yêu cầu đọc sách để chuẩn bị bài và làm bài tập lớn theo hướng dẫn của giảng viên trước mỗi 
buổi tham gia lớp học. Nói chung sinh viên được khích đặt các câu hỏi và phát biểu ý kiến 
riêng với những vấn đề đặt ra trong quá trình nghe giảng trên lớp, tránh thái độ thụ động ngồi 
nghe. 
Nội dung của môn học sẽ được trình bày trong 16 bài học với nội dung được thể hiện trong 
mục lục của bài giảng. 
Học viện Công nghệ Bưu Chính Viễn thông- Khoa Công nghệ thông tin I 
Hà nội 5/2010 
MỤC LỤC 
GIỚI THIỆU ................................................................................................................................................ 1 
MỤC LỤC .................................................................................................................................................... 3 
Bài 1: Khái niệm chung về cơ sở dữ liệu-phần 1 ..................................................................................... 11 
Khái niệm về cơ sở dữ liệu .................................................................................................................. 11 
Khái niệm về hệ quản trị cơ sở dữ liệu ............................................................................................... 11 
Các hệ thống cơ sở dữ liệu truyền thống ........................................................................................... 12 
Tổng quan các thành phần của một hệ quản trị cơ sở dữ liệu .......................................................... 14 
Kiến trúc của một hệ quản trị cơ sở dữ liệu ....................................................................................... 15 
Khái niệm dữ liệu và thông tin ............................................................................................................. 16 
Dữ liệu phái sinh và dữ liệu vật lý ................................................................................................... 17 
Bài 2: Khái niệm chung về cơ sở dữ liệu-phần 2..................................................................................... 19 
Sự cần thiết của việc thiết kế cơ sở dữ liệu ....................................................................................... 19 
Các vai trò cần thiết trong một môi trường cơ sở dữ liệu ............................................................. 19 
Các ưu điểm của hệ quản trị cơ sở dữ liệu ................................................................................... 20 
Mô hình trừu tượng 3 lớp ................................................................................................................... 20 
Mức bên ngoài .................................................................................................................................. 21 
Mức khái niệm.................................................................................................................................. 22 
Mức trừu tượng bên trong .............................................................................................................. 22 
Mức trừu tượng vật lý ..................................................................................................................... 22 
Khái niệm lược đồ, ánh xạ và thể hiện của cơ sở dữ liệu .............................................................. 22 
Sự độc lập dữ liệu ............................................................................................................................ 24 
Các ngôn ngữ cơ sở dữ liệu ................................................................................................................. 25 
Học viện Công nghệ Bưu Chính Viễn thông- Khoa Công nghệ thông tin I 
Hà nội 5/2010 
Ngôn ngữ định nghĩa dữ liệu ........................................................................................................... 25 
Ngôn ngữ thao tác dữ liệu ............................................................................................................... 26 
Ngôn ngữ truy vấn ........................................................................................................................... 26 
Các ngôn ngữ thế hệ thứ tư ............................................................................................................ 26 
Bài 3: Các mô hình dữ liệu ........................................................................................................................ 27 
Giới thiệu chung ................................................................................................................................... 27 
Quá trình thiết kế một cơ sở dữ liệu .................................................................................................. 28 
Bước 1. Phân tích yêu cầu của bài toán ........................................................................................... 28 
Bước 2. Thiết kế cơ sở dữ liệu mức khái niệm .............................................................................. 28 
Bước 3. Thiết kế cơ sở dữ liệu ở mức logic ................................................................................... 28 
Bước 4. Cải thiện các lược đồ ......................................................................................................... 29 
Bước 5. Thiết kế cơ sở dữ liệu vật lý .............................................................................................. 29 
Bước 6.Thiết kế an toàn bảo mật cho hệ thống ............................................................................. 29 
Mô hình thực thể liên kết .................................................................................................................... 29 
Các ký pháp cho mô hình E-R được thể hiện trong hình vẽ dưới đây ............................................ 31 
Một ví dụ về lược đồ E-R (ERD) được thể hiện trong hình vẽ dưới đây ........................................ 33 
Một ví dụ khác về lược đồ E-R- phức tạp hơn ................................................................................ 33 
Các thuộc tính trong mô hình E-R ..................................................................................................... 33 
Các liên kết trong mô hình E-R ......................................................................................................... 34 
Các ràng buộc ánh xạ lực lượng liên kết (mapping cardinality) trong mô hình E-R ........................ 35 
Các ràng buộc tham gia trong mô hình E-R ...................................................................................... 37 
Khóa của một tập thực thể .............................................................................................................. 37 
Tập các mối quan hệ ........................................................................................................................ 38 
Một số vấn đề cần quan tâm khi thiết kế mô hình E-R ...................................................................... 39 
Học viện Công nghệ Bưu Chính Viễn thông- Khoa Công nghệ thông tin I 
Hà nội 5/2010 
Ảnh hưởng của ràng buộc ánh xạ lực lượng liên kết lên các khóa ................................................ 39 
Vấn đề đặt vị trí cho các thuộc tính của mối quan hệ ..................................................................... 41 
Các vấn đề thiết kế khác cần xem xét ............................................................................................. 43 
Vấn đề tập thực thể hay các thuộc tính .......................................................................................... 43 
Việc coi một đối tượng là một tập thực thể hay tập mối quan hệ ................................................ 44 
Việc coi một đối tượng là tập thực thể yếu hay tập thực thể mạnh ............................................. 45 
Bài 5: Giới thiệu về mô hình hóa dữ liệu-phần 2 .................................................................................... 47 
Mô hình thực thể liên kết mở rộng ..................................................................................................... 47 
Cụ thể hóa (Specializations) ............................................................................................................. 47 
Tổng quát hóa ................................................................................................................................... 48 
Sự kế thừa thuộc tính ...................................................................................................................... 49 
Các ràng buộc trên việc tổng quát hóa ............................................................................................ 50 
Tích hợp ............................................................................................................................................ 52 
Các mối quan hệ nhiều ngôi. ............................................................................................................ 54 
Lược đồ E-R với các chỉ thị vai trò .................................................................................................... 56 
Giới thiệu về ngôn ngữ tạo mô hình thống nhất UML ........................................................................ 56 
Sự liên quan giữa lược đồ lớp của UML và lược đồ E-R ................................................................. 56 
Ràng buộc toàn vẹn tham chiếu .......................................................................................................... 58 
Bài 6: Mô hình dữ liệu quan hệ ................................................................................................................ 60 
Mô hình dữ liệu quan hệ ...................................................................................................................... 60 
Quan hệ là gì? ................................................................................................................................... 62 
Các lược đồ quan hệ và Các thể hiện của quan hệ ......................................................................... 63 
Thiết kế logic .................................................................................................................................... 64 
Việc ánh xạ mô hình thực thể liên kết sang mô hình quan hệ ............................................................ 65 
Học viện Công nghệ Bưu Chính Viễn thông- Khoa Công nghệ thông tin I 
Hà nội 5/2010 
Bước 1: dùng cho việc ánh xạ các thực thể thông thường (thực thể khỏe) .................................. 65 
Bước 2: Ánh xạ các thực thể yếu .................................................................................................... 67 
Bước 3: Ánh xạ các quan hệ hai ngôi ............................................................................................... 68 
Bước 4: Ánh xạ các thực thể liên kết (hay thực thể kết hợp) ........................................................ 70 
Bước 5: Ánh xạ các quan hệ một ngôi (đệ quy) .............................................................................. 72 
Bước 6: Ánh xạ các quan hệ nhiều ngôi .......................................................................................... 73 
Bước 7: Ánh xạ các mối liên kết lớp cha/lớp con ........................................................................... 75 
Bài 7 Ngôn ngữ truy vấn ........................................................................................................................... 79 
Ngôn ngữ đại số quan hệ ..................................................................................................................... 79 
Năm phép toán cơ bản của đại số quan hệ .................................................................................... 80 
Phép chọn ......................................................................................................................................... 80 
Phép chiếu ........................................................................................................................................ 81 
Phép hợp .......................................................................................................................................... 82 
Phép trừ ............................................................................................................................................ 83 
Phép tích đề các ................................................................................................................................ 84 
Biểu thức đại số quan hệ ................................................................................................................. 85 
Bài 8 Ngôn ngữ truy vấn quan hệ - phần 2 .............................................................................................. 89 
Các toán tử bổ sung trong đại số quan hệ ........................................................................................... 89 
Phép giao .......................................................................................................................................... 90 
Phép kết nối ...................................................................................................................................... 91 
Phép kết nối ngoài ............................................................................................................................ 93 
Phép nửa kết nối .......................................................................................................... ... của các 
đường truy nhập, chỉ mục, v.v... Thuật toán tìm kiếm cho các phép chọn là một trong hai loại 
sau đây 
- duyệt toàn bộ bảng chỉ mục: tìm kiếm được thực hiện trực tiếp từ một cấu trúc chỉ mục 
- duyệt toàn bộ tệp dữ liệu: các bản ghi được lựa chọn trực tiếp từ một cấu trúc tệp 
FS1-Thuật toán duyệt tệp dữ liệu theo kiểu tìm kiếm tuần tự: các tệp heap thường được tìm 
kiếm với một thuật toán tìm kiếm tuần tự. 
FS2-Thuật toán duyệt tệp dữ liệu theo kiểu tìm kiếm nhị phân: các tệp tuần tự thường được tìm 
với thuật toán tìm kiếm nhị phân hoặc thuật toán nhảy. 
IS3-Thuật toán dùng chỉ mục chính hoặc tù khoá bảng băm để lấy ra một bản ghi đơn: trong 
các trường hợp tìm kiếm có điều kiện so sánh bằng đối với một thuộc tính khoá mà chỉ mục của 
thuộc tính khoá đó đã được tạo ra (hoặc từ khoá bảng băm được sử dụng) 
IS4-Thuật toán dùng chỉ mục chính hoặc tù khoá bảng băm để lấy ra nhiều bản ghi: trong các 
trường hợp tìm kiếm có điều kiện so sánh không bằng (, >=) đối với một thuộc tính 
khoá mà chỉ mục của thuộc tính khoá đó đã được tạo ra. Chỉ mục chính này được sử dụng để 
tìm thấy bản ghi thoả mãn điều kiện bằng sau đó dựa trên bản ghi đó, tất cả các bản ghi lớn hơn 
hoặc nhỏ hơn sẽ được lấy ra từ tệp được sắp xếp. 
IS5-Thuật toán dùng chỉ mục theo cụm để lấy ra nhiều bản ghi: trong các trường hợp tìm kiếm 
có điều kiện so sánh bằng đối với một thuộc tính không khoá mà chỉ mục theo cụm (chỉ mục 
thứ cấp) của thuộc tính đó đã được tạo ra. Chỉ mục theo cụm này được sử dụng để tìm thấy tất 
cả các bản ghi thoả mãn điều kiện chọn. 
IS6-Thuật toán dùng chỉ mục thứ cấp, cây nhị phân B+: một điều kiện chọn với một phép so 
sánh bằng, một chỉ mục thứ cấp có thể được sử dụng để lấy ra một bản ghi đơn nếu trường chỉ 
mục đó là một khoá hoặc lấy ra nhiều bản ghi nếu trường chỉ mục đó không phải là khoa. Các 
chỉ mục thứ cấp cũng có thể được sử dụng cho bất kể các toán tử so sánh nào, không chỉ phép 
so sánh bằng. 
Thuật toán cho các phép chọn kết hợp 
Các phép chọn kết hợp (conjunctive selections) là các phép chọn có điều kiện chọn bao gồm 
nhiều điều kiện đơn thực hiện phép toán logic AND với nhau. 
Học viện Công nghệ Bưu Chính Viễn thông- Khoa Công nghệ thông tin I 
Hà nội 5/2010 
Đối với các điều kiện chọn đơn giản, việc tối ưu về cơ bản có nghĩa là bạn kiểm tra sự tồn tại 
của một đường dẫn truy nhập nào đó cho một thuộc tính liên quan trong một biểu thức điều 
kiện và sử dụng nó nếu sẵn có, trái lại một tìm kiếm tuần tự được thực hiện 
Tối ưu truy vấn cho phép chọn rất có ích cho các điều kiện kết hợp khi nhiều hơn một thuộc 
tính tham gia có một đường dẫn truy nhập. Một bộ tối ưu nên chọn đường dẫn truy nhập mà có 
thể lấy ra số lượng bản ghi ít nhất theo một cách thức hiệu quả nhất. 
Vấn đề quan tâm nhất khi chọn trong số nhiều điều kiện đơn giản của một biểu thức điều kiện 
kết hợp là độ lựa chọn của mỗi điều kiện 
Độ lựa chọn được định nghĩa = số lượng bản ghi thoả mãn điều kiện/số bản ghi trong quan hệ. 
Độ lựa chọn càng nhỏ thì càng ít bộ của một quan hệ thoả mãn điều kiện. Vì vậy, bộ tối ưu nên 
sắp lịch thực thi sao cho độ lựa chọn nhỏ nhất được dùng đầu tiên, tiếp theo là các giá trị độ lựa 
chọn càng ngày càng cao hơn sao cho điều kiện cuối cùng được sử dụng có giá trị độ lựa chọn 
là cao nhất. 
Thông thường, các giá trị độ lựa chọn cho tất cả các điều kiện là không sẵn có. Tuy nhiên, hệ 
quản trị cơ sở dữ liệu sẽ duy trì việc ước lượng cho hầu hết trong số chúng chứ không phải tất 
cả các loại điều kiện và những ước lượng này sẽ được dùng bởi bộ tối ưu. 
Ví dụ 
- Độ lựa chọn của một điều kiện bằng của một thuộc tính khía của một quan hệ r(R) là 
- Độ lựa chọn của một điều kiện bằng trên một thuộc tính với n giá trị khác nhau có thể 
được ước lượng bởi 
Giả sử rằng các bản ghi phân phối đều đối với n giá trị khác nhau, một tổng |r(R)|/n bản 
ghi đều thoả mãn một điều kiện bằng trên thuộc tính này. 
IS7-Thuật toán lựa chọn kết hợp: nếu một thuộc tính liên quan tới một điều kiện đơn trong 
lựa chọn kết hợp có một đường dẫn truy nhập cho phép việc sử dụng bất kỳ thuật toán FS2 tới 
IS6, thì sử dụng điều kiện này để lấy các bản ghi sau đó kiểm tra xem liệu mỗi bản ghi được lấy 
ra có thoả mãn các điều kiện đơn còn lại trong điều kiên kết hợp hay không. 
nRr
n
Rr
1
)(
)(
=






)(
1
Rr
Học viện Công nghệ Bưu Chính Viễn thông- Khoa Công nghệ thông tin I 
Hà nội 5/2010 
IS8-Thuật toán lựa chọn kết hợp sử dụng một chỉ mục ghép: nếu hai hoặc nhiều thuộc tính liên 
quan tới điều kiện bằng và một chỉ mục ghép (hoặc cấu trúc băm) cho tổ hợp các trường này 
tồn tại- sử dụng chỉ mục ghép một cách trực tiếp. 
IS9-Thuật toán lựa chọn kết hợp bằng phép giao của các con trỏ tới bản ghi: Nếu chỉ mục thứ 
cấp có sẵn trên bất kỳ một hoặc tất cả các thuộc tính liên quan trong phép so sánh bằng (giả sử 
rằng các chỉ mục sử dụng con trỏ trỏ tới bản ghi chứ không sử dụng các con trỏ trỏ tới các khối 
bản ghi), thì mỗi chỉ mục được dùng để lấy ra các con trỏ bản ghi thoả mãn các điều kiện đơn 
giản. Giao của các con trỏ bản ghi này la tập các bộ thoả mãn điều kiện kết hợp. 
Thuật toán cho các phép kết nối 
Phép kết nối và những biến thể cua nó là các phép toán tốn nhiều thời gian thực hiện nhất trong 
quá trình xử lý truy vấn. Hầu hết các phép kết nối mà ta thường gặp trong các hệ thống thực tế 
hoặc là phép kết nối tự nhiên và các kết nối bằng (điều kiện kết nối là các phép so sánh bằng). 
Các phép kết nối liên quan tới hai quan hệ được gọi là phép kết nối hai ngôi (hai chiều) trong 
khi các phép kết nối liên quan tới nhiều hơn hai quan hệ được gọi là kết nối nhiều ngôi (nhiều 
chiều). 
Trong khi có một vài chiến lược khác nhau có thể được áp dụng để xử lý các phép kết nối hai 
ngôi, số lượng các chiến lược tiềm năng cho xử lý nhiều ngôi tăng lên một cách nhanh chóng. 
Trước hết ta xem xét các chiến lược xử lý cho kết nối hai ngôi, sau đó chuyển sang xem xét 
chiến lược cho phép kết nối nhiều ngôi. 
Chúng ta sẽ giả sử rằng hai quan hệ được kết nối với nhau có tên là R và S, trong đó R chứa 
một thuộc tính tên là A và S chứa một thuộc tính tên là B, hai quan hệ này là khả hợp. 
Tại thời điểm này, chúng ta chỉ quan tâm tới chiến lược cho kết nối tự nhiên hoặc kết nối bằng 
liên quan tới hai thuộc tính A và B này. Chú ý rằng một kết nối tự nhiên chỉ xảy ra trên thuộc 
tính A và B khi ta đổi tên một hoặc cả hai thuộc tính sao cho chúng có trùng tên với nhau trước 
khi phép kết nối tự nhiên được tiến hành. Chú ý thêm nữa là nếu thuộc tính A và B là các thuộc 
tính khả kết nối duy nhất của hai quan hệ R và S thì phép toán kết nối bằng với điều kiện A=B 
cho kết quả giống như phép kết nối tự nhiên R*S. 
J1-Thuật toán vòng lặp lồng nhau: một kỹ thuật brute force trong đó mỗi bản ghi t ∈ R cho 
vòng lặp bên ngoài kết hợp với mỗi bản ghi s∈S của vòng lặp bên trong và kiểm tra xem liệu 
hai bản ghi này có thoả mãn điều kiện kết nối, tương đương với t.A=S.B? 
J2-Thuật toán sử dụng vòng lặp đơn với một cấu trúc truy nhập: Nếu một chỉ mục hoặc khoá 
bảng băm tồn tại cho một trong hai thuộc tính của phép kết nối, ví dụ là B ∈ S, lấy ra mỗi bản 
Học viện Công nghệ Bưu Chính Viễn thông- Khoa Công nghệ thông tin I 
Hà nội 5/2010 
ghi t ∈ R trong một lân và sư dụng cấu trúc truy nhập để trực tiếp lấy ra tất cả các bản ghi s ∈ S 
thoả mãn t.A=s.B. 
J3-Thuật toán kết nối dùng sắp xếp và trộn: nếu các bản ghi của R và S đều được sắp xếp một 
vật lý theo giá trị của thuộc tính A và B thì phép kết nối có thể được xử lý theo một chiến lược 
rất hiệu quả. Cả hai quan hệ được duyệt theo trật tự của các thuộc tính kết nối, lấy ra những bản 
ghi phù hợp có cùng giá trị của A và B. Theo cách thức này thì mỗi quan hệ chỉ được duyệt một 
lần duy nhất. 
J4-Thuật toán sử dụng kết nối và băm: trong kỹ thuật này, các bản ghi của cả hai quan hệ R và 
S được băm sử dụng chung một hàm băm (trên các thuộc tính kết nối) tới cùng một tệp băm. 
Một bước duyệt toàn bộ quan hệ nhỏ sẽ băm các bảng ghi của nó tới tệp băm. Một phép duyệt 
qua quan hệ còn lại sẽ băm các bản ghi của nó tới cùng khối băm như quan hệ trước để kết hợp 
tất cả các bản ghi giống nhau. 
Tạo chuỗi ống xử lý (pipelining) các phép toán 
Việc tối ưu hoá các truy vấn có thể có hiệu quả bằng cách giảm số lượng các qua hệ trung gian, 
những quan hệ kết quả được sinh ra khi thực thi một chuỗi các truy vấn. 
Việc giảm số lượng các quan hệ trung gian này được thực hiện bằng cách kết hợp một số các 
phép toán quan hệ thành một ống xử lý liên hoàn các phép toán. Phương pháp này đôi khi cũng 
được coi như một tiến trình xử lý chuỗi. 
Việc kết hợp các phép toán trong một ống xử lý liên hoàn loại bỏ được một số chi phí như đọc 
và ghi các quan hệ trung gian, nhưng không loại bỏ được tất cả các chi phí đọc và ghi liên quan 
tới các phép toán và không loại bỏ được các xử lý cần thiết. 
Xét một ví dụ về việc tạo ống xử lý liên hoàn này, chúng ta xét đến hai quan hệ R và S, thực 
hiện phép chiếu trên một tập các thuộc tính sau khi kết nối với nhau. Trong đại số quan hệ truy 
vấn này được thể hiện là π
(a, b, c)
(R * S) trong đó a, b, c là ba thuộc tính cần quan tâm. 
Hai phép toán này có thể được thực thi như sau 
- thực hiện phép kết nối R và S, lưu kết quả lại thành một bảng trung gian T1 [T1=R*S] 
- chiếu lên tập các thuộc tính cần từ bảng T1 [kết quả= π
(a, b, c)
(T1)] 
Trong ống liên hoàn thực hiện truy vấn này, không có quan hệ trung gian T1 được sinh ra. 
Thay vào đó, ngay khi một bộ của phép kết nối giữa R và S được sinh ra, nó lập tức được 
chuyển ngay cho phép chiếu để xử lý. Kết quả cuối cùng được tạo ra một cách trực tiếp. Trong 
Học viện Công nghệ Bưu Chính Viễn thông- Khoa Công nghệ thông tin I 
Hà nội 5/2010 
cách thực hiện trong ống liên hoàn, các kết quả được sinh ra thậm chí trước khi toàn bộ phép 
kết nối được xử lý. 
Hai chiến lược cơ bản có thể được sử dụng cho các phép toán dùng ống liên hoàn 
- Tạo ống liên hoàn theo hướng yêu cầu: Hệ quả là dữ liệu sẽ được đưa lên cây truy vấn 
khi các phép toán yêu cầu dữ liệu để thực hiện 
- Tạo ống liên hoàn theo hướng tạo sản phẩm: hệ quả là dữ liệu đượ đẩy lên cây truy vấn 
khi các phép toán ở mức thấp hơn sinh ra dữ liệu, cái sẽ được dùng cho các phép toán ở 
mức cao hơn trong cây truy vấn. 
Một ví dụ về tạo ống liên hoàn theo hướng yêu cầu được thể hiện ở hình vẽ sau 
Một ví dụ về việc tạo xử lý liên hoàn theo hướng yêu cầu: thể hiện trong hình vẽ dưới đây 
Một ví dụ về tạo xử lý liên hoàn hướng sản phẩm được thể hiện trong hình vẽ sau đây 
Học viện Công nghệ Bưu Chính Viễn thông- Khoa Công nghệ thông tin I 
Hà nội 5/2010 
Sử dụng các thuật toán thông minh trong tối ưu hóa truy vấn 
Bộ phân tích cú pháp của các ngôn ngữ truy vấn bậc cao tạo ra cách biểu diễn bên trong của 
câu truy vấn mà được tối ưu dựa trên các luật thoongminh. 
Các hàm dịch vụ truy nhập mà thực thi các nhóm phép toán cùng nhau dựa trên các đường truy 
nhập có sẵn cho các quan hê liên quan được bộ tối ưu truy vấn lựa chọn. Một trong những luật 
thông minh chính là áp dụng các phép chiếu và phép chọn càng sớm càng tốt. Luật này rất có 
ích bởi vì kích cỡ của các quan hệ liên quan tới các phép toán kết nối tiếp theo (hoặc các phép 
toán nhi phân khác) càng nhỏ thì càng tốt. Phép chiếu và phép chọn có tác dụng làm giảm kích 
cỡ của các toán hạng trong các phép toán kết nối. 
Nhìn chung, về cơ bản thì các bộ tối ưu hóa truy vấn sẽ tạo ra một vài cách biểu diễn truy vấn 
khác nhau sau đó lựa chọn trong số đó một cách tốt nhất. 
Khi một biểu diễn truy vấn được tạo ra, bạn phải đảm bảo rằng nó là một biểu thức tương 
đương với biểu thức truy vấn trong thực tế. 
Cuối cùng, bộ tối ưu hóa truy vấn phải tuân thủ các luật chuyển đổi sẵn cơ bản để đảm bảo tính 
tương đương giữa các biểu thức biểu diễn truy vấn. 
Mức độ thông tin sẵn có đối với bộ tối ưu sẽ ảnh hưởng tới hiệu quả của cơ chế tạo ra biểu diễn 
tương đương này. 
Học viện Công nghệ Bưu Chính Viễn thông- Khoa Công nghệ thông tin I 
Hà nội 5/2010 
- ở mức độ thấp nhất-tức là chỉ biết tên của các quan hệ thì luật chuyển đổi tương 
đương như sau 
o R ∩ R ≡ R 
o πX (R ∪ S) ≡ πX (R) ∪ πX (S) 
o σA=B AND B=C AND A=C (R) ≡ σA=B AND B=C (R) 
- Mức độ cao hơn là thông tin về lược đồ quan hệ có sẵn 
o Cho R(A,B), S(B,C) với r(R) và s(S) thì σA=a (R * S) ≡ σA=a(R) * S 
- Nếu thông tin về ràng buộc có sẵn, chúng sẽ cung cấp thậm chí nhiều thông tin và 
khả năng thay đổi hơn 
o Nếu bạn biết rằng R(A,B,C,D) với r(R) và bạn cũng biết rằng r thỏa mãn 
B→C, thì πA,B (r) * πB,C (r) ≡ πA,B,C (r) 
Nhìn chung có rất nhiều sự tương đương tồn tại và bộ tối ưu có thể sử dụng chúng càng nhiều 
càng tốt. Ví dụ: r ∪ r ≡ r, r ∩ r ≡ r, r − r ≡ ∅. 
Các luật liên quan tới lực lượng của một quan hệ cũng có thể được sử dụng để tối ưu hóa thực 
thi các truy vấn. Ví dụ xem xét sự khác nhau giữa R*S và S*R 
- Giả sử rằng R bao gồm 3 bộ và S có 5 bộ. mỗi bộ của R dài 10 bytes và mỗi bộ của 
S dài 100 byte. 
- Với trường hợp R*S: một lần duyệt toàn bộ R sinh ra 3 x 10 bytes=30 bytes. Ba lần 
duyệt qua S (mỗi lần cho một bộ được tạo ra từ R) sinh ra 15 bộ x 100 bytes= 1500 
bytes. Vậy tổng số = 1530 bytes 
- Với trường hợp S*R: một lần duyệt toàn bộ S sinh ra 5 x 100 bytes=500 bytes. Năm 
lần duyệt qua R (mỗi lần cho một bộ được tạo ra từ S) sinh ra 15 bộ x 10 bytes= 150 
bytes. Vậy tổng số = 650 bytes 
- Rõ ràng S*R là cách thực hiện tốt hơn R*S 
Tiếp đến chúng ta xem xét tới việc ước lượng chi phí khi tối ưu truy vấn 
Việc ước lượng chi phí thường được sử dụng chỉ cho mã nguồn thực thi truy vấn đóng gói, các 
truy vấn được biên dịch mà sẽ được thực hiện lặp đi lặp lại. 
Thời gian và công sức cần thiết cho loại phân tích này không được tính như việc thực thi truy 
vấn một lần đơn giản. 
Kỹ thuật ước lượng chi phí cần quan tâm tới chi phí thực thi một truy vấn từ bốn khía cạnh 
khác nhau sau: 
Học viện Công nghệ Bưu Chính Viễn thông- Khoa Công nghệ thông tin I 
Hà nội 5/2010 
- Chi phí truy nhập tới các bộ phận lưu trữ thứ cấp: cần quan tâm tới tất cả các chi phí 
tìm kiếm, đọc dữ liệu và ghi vào bộ lưu trữ thứ cấp. 
- Chi phí lưu trữ: cần quan tâm tới chi phí lưu trữ các tệp dữ liệu trung gian được tạo 
ra bởi các chiến lược thực thi được lựa chọn. 
- Chi phí tính toán: cần quan tâm tới việc sắp xếp, trộn, tính toán trên các thuộc tính 
(nằm ở các điều kiện của phép chọn và phép chiếu) 
- Chi phí truyền thông: trong một môi trường phân tán, loại chi phí này bao gồm chi 
phí vận chuyển các truy vấn và/hoặc các kết quả của nó tới vị trí ban đầu. 
Việc tối ưu truy vấn theo ngữ nghĩa: Kỹ thuật này sử dụng ngữ nghĩa của một cơ sở dữ liệu và 
nhiều ràng buộc áp dụng để thay đổi các truy vấn về mặt ngữ nghĩa thành các truy vấn có hiệu 
quả hơn. Ví dụ, giả sử một người sử dụng sinh ra một truy vấn sau 
- πs# (σqty > 100 (SPJ)) {liệt kê mã nhà cung cấp của những nhà cung cấp vận chuyển ít 
nhất một linh kiện sản phẩm với số lượng lớn hơn 100} 
- Nếu một ràng buộc tồn tại phát biểu là: tất cả dữ liệu liên quan tới số lượng <=75 thì 
bộ tối ưu có thể thông báo với hệ thống là truy vấn không cần thực thi và kết quả 
đơn giản trả về tập rỗng.