ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
=====o0o=====
Đinh Thị Lan Phƣơng
TỐI ƢU TRUY VẤN CƠ SỞ DỮ LIỆU QUAN HỆ
VÀ CƠ SỞ DỮ LIỆU PHÂN TÁN
BẰNG PHƢƠNG PHÁP HEURISTIC LUẬN VĂN THẠC SĨ

1.2.3 Cách thức truy nhập CSDL 8
1.3 MÔ HÌNH DỮ LIỆU QUAN HỆ 9
1.3.2 Các phép toán trên quan hệ 10
1.3.3 Các dạng chuẩn của mô hình quan hệ 11
1.4 HỆ CƠ SỞ DỮ LIỆU PHÂN TÁN 13
1.4.1 Các khái niệm về cơ sở dữ liệu phân tán 13
1.4.2 Các mục tiêu của hệ quản trị cơ sở dữ liệu phân tán. 15
1.4.3 Kiến trúc hệ quản trị cơ sở dữ liệu phân tán 16
1.4.4 Phân đoạn, nhân bản và cấp phát dữ liệu 19
1.5 KẾT LUẬN CHƢƠNG 1 21
Chƣơng 2. TỔNG QUAN VỀ TỐI ƢU HOÁ TRUY VẤN 22
2.1 BÀI TOÁN TỐI ƢU HÓA TRUY VẤN 22
2.2 BỘ TỐI ƢU TRUY VẤN 23
2.2.1. Không gian tìm kiếm 24
2.2.2 Chiến lƣợc tìm kiếm 26
2.2.3 Mô hình chi phí 27
2.3 KẾT LUẬN CHƢƠNG 2 31
Chƣơng 3. MỘT SỐ PHƢƠNG PHÁP TỐI ƢU TRUY VẤN 32
3.1 MỘT SỐ PHƢƠNG PHÁP TỐI ƢU HOÁ TRUY VẤN TRONG MÔI
TRƢỜNG TẬP TRUNG 32
3.1.1 Thuật toán INGRES 32
3.1.2 Thuật toán System R 36
3.2 MỘT SỐ PHƢƠNG PHÁP TỐI ƢU HOÁ TRUY VẤN TRONG MÔI
TRƢỜNG PHÂN TÁN 41
3.2.1 Thuật toán INGRES phân tán 41 3
3.2.2 Thuật toán System R* 45
3.2.3 Thuật toán SDD-1 50

One Relation Query
Truy vấn đơn quan hệ
OVQP
One Variable Query Processor
Bộ xử lý truy vấn một biến
QEP
Query Excution Plan
Hoạch định thực thi truy vấn
QTCSDL
DataBase System
Quản trị cơ sở dữ liệu 5
MỞ ĐẦU
1. Đặt vấn đề
Trong thời đại của nền kinh tế tri thức mà chúng ta đang sống, mọi hoạt
động muốn đạt hiệu quả cao thì nhất thiết phải có đƣợc thông tin, tri thức cần
thiết một cách nhanh chóng và chính xác. Thông tin có thể có đƣợc ở mọi nơi,
và CSDL là một trong những nguồn cung cấp thông tin.
Vấn đề đặt ra là khối lƣợng thông tin lƣu trữ lớn song đòi hỏi việc xử lý
thông tin phải nhanh chóng và hiệu quả. Để lấy đƣợc thông tin cần thiết ta cần
thực hiện hàng loạt các thao tác trên CSDL thông qua các câu truy vấn. Từ câu
truy vấn ban đầu có thể thực hiện theo các phƣơng pháp khác nhau để có kết quả
song cần phải hạ thấp chi phí thực hiện truy vấn gọi là tối ƣu hoá truy vấn. Tuy
nhiên để có đƣợc phƣơng án tối ƣu nhất thì có thể chi phí cho quá trình tối ƣu
lại rất cao.
Xuất phát từ những đặc điểm chung và tính thời sự nêu trên, tôi đã chọn
đề tài nghiên cứu về tối ƣu hoá truy vấn và đi sâu vào tìm hiểu về phƣơng
pháp tối ƣu truy vấn bằng Heuristic mong đƣợc đóng góp một phần nhỏ bé trong

1.1.1 Khái niệm
Đƣợc phát triển từ những năm 60, cho đến nay các hệ cơ sở dữ liệu (CSDL)
đƣợc tập trung nghiên cứu và phát triển ứng dụng rất mạnh. Khái niệm CSDL
cũng đã đƣợc định nghĩa dƣới nhiều góc độ khác nhau, ta có thể hiểu CSDL theo
khái niệm là một tập hợp dữ liệu của một tổ chức, xí nghiệp,… đƣợc lƣu trữ
trong máy tính, đƣợc nhiều ngƣời sử dụng và cách tổ chức của nó đƣợc chi phối
bằng một mô hình dữ liệu[5].
Một ngân hàng dữ liệu thƣờng là tập hợp các thông tin lƣu trữ trong máy
tính có liên quan đến một lĩnh vực khoa học, kinh tế hoặc văn hoá, thể thao theo
một cách đầy đủ nhất có thể có. Dữ liệu trong ngân hàng thực chất chỉ là một
kho dữ liệu trong khi đó một CSDL của một tổ chức hàm chứa cả các thông tin
liên quan đến việc bảo mật, cấu trúc lƣu trữ thông tin và sự chia sẻ tài nguyên.
1.1.2 Tiêu chuẩn của một cơ sở dữ liệu.
Một CSDL cần thoả mãn các tiêu chuẩn sau[1, 4, 6]:
1. Biểu diễn tốt thế giới thực: cung cấp một hình ảnh trung thực của thực tại.
Một CSDL trung thực cho phép ngƣời dùng có các thông tin thoả mãn việc sử
dụng và cập nhật.
2. Không dư thừa thông tin: mỗi thông tin đảm bảo không bị trùng lặp, chỉ có
mặt một lần trong CSDL do đó sự lựa chọn dữ liệu là duy nhất.
3. Tính độc lập của các chương trình đối với dữ liệu: tƣơng ứng với sự cần thiết
làm giảm giá thành bảo trì các chƣơng trình. Những thay đổi về cấu trúc của hệ
CSDL là do sự thay đổi của thế giới thực chứ không phải do một ứng dụng cụ
thể và nó cho phép nhiều ứng dụng cùng chia sẻ một bộ dữ liệu.
4. Tính an toàn và bí mật của dữ liệu: CSDL đƣợc đảm bảo chỉ những ngƣời có
trách nhiệm mới có thể truy cập đến các thông tin và sử dụng chúng. Ngoài ra
cũng cần có sự đảm bảo an toàn cho các vật mang thông tin chống lại mọi sự
huỷ hoại. 8


9
bản ghi mà chỉ cần đọc một phần thông tin tối thiểu đủ để xác định xem
đó có phải là bản ghi cần hay không.
2. Tổ chức truy nhập trực tiếp: Cho phép truy nhập trực tiếp đến các đơn vị
thông tin cần tìm mà không cần đọc lần lƣợt từ đầu. Để truy nhập phải
tuân theo phƣơng pháp đã xác định khi tổ chức lƣu trữ. Có hai loại tổ
chức truy nhập là tệp trực tiếp và tệp có chỉ số. Ta phải sử dụng một phần
thông tin của bản ghi làm khoá của bản ghi đó. Qua đặc trƣng của khoá
cho phép xác định chính xác bản ghi cần tìm.
3. Truy nhập ngẫu nhiên: Kiểu tổ chức này lƣu trữ các bản ghi tại địa chỉ
theo một khoá nào đó. Ta thƣờng dùng một thuật toán, một hàm ngẫu
nhiên để tính toán ra địa chỉ của bản ghi. Hàm địa chỉ đƣợc xây dựng theo
nhiều phƣơng pháp khác nhau nhƣ phƣơng pháp tính địa chỉ tuyến tính,
phƣơng pháp dùng hàm mã cắt v.v…
1.3 MÔ HÌNH DỮ LIỆU QUAN HỆ
Mô hình dữ liệu là tập hợp các khái niệm dùng để biểu diễn các cấu trúc của
CSDL. Cấu trúc của một CSDL bao gồm các kiểu dữ liệu, các mối liên kết và
các ràng buộc phải tuân theo trên các dữ liệu. Nhiều mô hình còn có thêm tập
hợp các phép toán cơ bản để đặc tả các thao tác trên CSDL.
Mô hình quan hệ đƣợc Ted Codd đƣa ra vào những năm 1970 và đƣợc sử
dụng rất rộng rãi bởi tính đơn giản và cơ sở toán học của nó.
1.3.1 Khái niệm về quan hệ
Một lƣợc đồ quan hệ R, kí hiệu là R(A
1
, A
2,
…,A
n
) đƣợc tạo nên từ một
10
1.3.2 Các phép toán trên quan hệ
Có năm phép toán cơ bản và năm phép toán khác có thể đƣợc định nghĩa
theo năm phép toán cơ bản này. Đó là phép chọn, phép chiếu, phép hợp, phép
trừ và phép tích Descartes. Các phép toán bổ sung có thể là: giao, nối, nối tự
nhiên, nối nửa và phép chia.
Phép chọn trên quan hệ R với vị từ p là tập tất cả các bộ t của R thoả p:
)}(/{t )( tpRR
p



Phép chiếu của quan hệ R trên tập các thuộc tính X của quan hệ R, là một
quan hệ trên tập thuộc tính X, đƣợc xây dựng bằng cách loại bỏ trong quan hệ R
những thuộc tính không nằm trong X.

}|][{t)( RtXR
X


Phép hợp. Hợp của hai quan hệ R và S, là tập tất cả các bộ thuộc R hoặc
thuộc S hoặc thuộc cả hai. Các bộ trùng lặp bị loại bỏ.
R  S= {t| tR hoặc t  S }
Phép trừ: Hiệu của hai quan hệ R và S là tập tất cả các bộ của R không
thuộc S
R-S = {t| tR và t S }
Tích Descartes. Tích Descartes của hai quan hệ R bậc n và S bậc m có kết
quả là tập các (n+m) bộ sao cho mỗi bộ này có n thành phần đầu thuộc R và m

Nối - . Phép nối là một dẫn xuất của tích Descartes. Có nhiều kiểu nối, và
kiểu nối tổng quát là nối  hay đơn giản là nối. Với F là vị từ nối:
R

F
S = 
F
(R x S) 11
Nối tự nhiên. Giả sử hai quan hệ R và S có tập thuộc tính chung là X. Phép
nối tự nhiên của hai quan hệ R và S là quan hệ trên tập thuộc tính của R và tập Y
các thuộc tính của S không nằm trong X
R

S = {(u,v)|uR  v = s[Y] sS s[X] = u[X]}
Nối nửa của hai quan hệ R và S theo vị từ p cho kết quả là:
R <
p
S =
X
(R

P
S ) với X là tập các thuộc tính của R
Phép chia. Chia quan hệ R bậc n cho quan hệ S bậc m (trong đó n>m và m
 0) là tập các bộ t trên bộ n-m thuộc tính sao cho với mọi bộ uS thì (t,u) R
RS = 
A‟

Yêu cầu của chuẩn hoá là không làm mất mát thông tin khi thay một quan
hệ này bằng các quan hệ khác. Nếu chúng ta có thể nối các quan hệ kết quả để
tạo thành quan hệ ban đầu, thì quá trình phân rã đó gọi là phân rã không mất
thông tin.
Một yêu cầu khác đối với quá trình chuẩn hoá là bảo toàn phụ thuộc. Phân
rã đƣợc gọi là bảo toàn phụ thuộc nếu đảm bảo rằng từng phụ thuộc hàm sẽ
đƣợc biểu hiện trong các quan hệ riêng rẽ sau khi tách.
Định nghĩa dạng chuẩn 1 (1 NF): Một lƣợc đồ quan hệ R đƣợc gọi là ở
dạng chuẩn 1 nếu và chỉ nếu toàn bộ các miền thuộc tính có mặt trong R đều chỉ
chứa các giá trị nguyên tố [1].
Nhƣ vậy 1NF không cho phép quan hệ có các thuộc tính đa trị hoặc có các
nhóm thuộc tính đa trị.
Định nghĩa dạng chuẩn 2 (2 NF): Một lƣợc đồ quan hệ ở dạng chuẩn 2NF
nếu nó đã ở dạng chuẩn 1NF và nếu mỗi thuộc tính không khoá của R phụ thuộc
hàm đầy đủ vào mỗi một khoá [1].
Dạng không chuẩn hóa
Dạng chuẩn thứ hai (2NF)
Dạng chuẩn thứ nhất (1NF)
Dạng chuẩn thứ ba (3NF) 13
Định nghĩa dạng chuẩn 3 (3 NF): Một lƣợc đồ quan hệ R ở dạng chuẩn
3NF nếu nó đã ở dạng chuẩn 2NF và nếu mỗi thuộc tính không khoá của R là
không phụ thuộc hàm bắc cầu vào mỗi một khoá [1].
Định nghĩa dạng chuẩn BCNF: Một lƣợc đồ quan hệ R với tập các phụ
thuộc hàm đƣợc gọi là ở dạng chuẩn BCNF nếu X A thoả mãn trên R, A X

Trạm 5

Trạm 4

Trạm 3

Trạm 2
Hình 1- Cơ sở dữ liệu trung tâm trên một mạng
Các trạm phải đƣợc kết nối bởi một kiểu mạng truyền thông nào đó để truyền dữ
liệu.
Một hệ quản trị CSDL phân tán là một tập các phần mềm hệ thống bao
gồm các phần mềm quản trị các dữ liệu phân tán, các phần mềm quản trị truyền
thông và các hệ quản trị CSDL địa phƣơng/cục bộ lƣu trú trên mỗi trạm của hệ
CSDL phân tán.

Ngoài các chức năng của các hệ quản trị CSDL tập trung và của phần mềm

Trạm 1 Trạm 5

Trạm 4

Trạm 3

Trạm 2

Sự độc lập dữ liệu và trong suốt phân tán. Ngƣời dùng có thể không quan
tâm đến sự phân tán dữ liệu. Các thông tin này đƣợc lƣu trữ trong từ điển dữ
liệu, và đƣợc hệ quản trị CSDL phân tán sử dụng để định vị dữ liệu. Đây là một
dạng trong suốt cơ bản cần có trong CSDL phân tán, nó liên quan đến tính độc
lập dữ liệu và làm tăng khả năng thích ứng của các ứng dụng đối với những thay
đổi trong định nghĩa và tổ chức của dữ liệu và ngƣợc lại. Khi đó không có sự 16
khác biệt nào giữa các ứng dụng chạy trên CSDL tập trung với ứng dụng chạy
trên CSDL phân tán.
Trong suốt phân đoạn. Việc truy cập tới dữ liệu đƣợc xác định trên các
quan hệ con (thu đƣợc từ việc chia nhỏ quan hệ gốc) đƣợc gọi là các đoạn
(fragment). Việc phân đoạn làm tăng hiệu năng, tính sẵn sàng, độ tin cậy của
CSDL phân tán. Trong suốt phân đoạn che dấu sự phân đoạn đối với ngƣời
dùng.
Trong suốt nhân bản. Một giải pháp cho sự tin cậy dữ liệu là việc tạo ra dƣ
thừa dữ liệu dƣới một hình thức nào đó. Mỗi đoạn dữ liệu đƣợc sao lƣu thành
hai hay nhiều bản, mỗi bản đƣợc lƣu trên một trạm khác nhau, đƣợc gọi là sự
nhân bản. Nó giúp hệ CSDL phân tán nâng cao hiệu năng, độ tin cậy và tính sẵn
sàng. Tuy nhiên việc nhân bản sẽ gây khó khăn cho việc cập nhật CSDL, và việc
duy trì và quản lý các bản sao là phức tạp và tốn kém. Việc trong suốt nhân bản
là việc che dấu khiến ngƣời dùng chỉ nhìn thấy các quan hệ không có nhân bản.
Tính trong suốt đối với hệ quản trị CSDL phân tán cho phép che dấu đối
với ngƣời dùng việc các hệ quản trị CSDL cục bộ có thể khác nhau.
Tính tự trị của các trạm. Đây là mục tiêu cho phép mỗi trạm điều khiển và
thao tác dữ liệu địa phƣơng của nó độc lập với các trạm khác. Do đó việc quản
trị của CSDL phân tán có thể hoàn toàn không tập trung.
Tính mở rộng. Là khả năng mở rộng bằng việc đƣa thêm các trạm mới vào
mạng với ảnh hƣởng tối thiểu lên các CSDL cục bộ và các chƣơng trình ứng

LCS
2
GCS
LCS
1
ES
2
LIS
1
LIS
n
ES
1
ES
n
LIS
2
LCS
n
Hình 3- Kiến trúc tham chiếu Cơ sở dữ liệu phân tán
ES-lƣợc đồ ngoài (External Schema)
GCS-lƣợc đồ khái niệm toàn cục (Global Conceptual
Schema)
LCS-lƣợc đồ khái niệm cục bộ (Local
Conceptual Schema)
LIS-lƣợc đồ trong cục bộ (Local Internal
Schema) 18

Ngƣời sử dụng
Bộ kiểm soát dữ
liệu ngữ nghĩa
Bộ tối ƣu truy
vấn toàn cục
Bộ theo dõi hoạt
động toàn cục
Lƣợc đồ khái niệm
toàn cục
Bộ giao tiếp
ngƣời dùng
Thƣ mục/Từ
điển toàn cục
Lƣợc đồ ngoài
Bộ hỗ trợ thực thi
Bộ khôi phục cục
bộ
Bộ tối ƣu hoá
truy vấn cục bộ
Lƣợc đồ khái niệm
cục bộ
Lƣợc đồ trong cục
bộ

Nhật ký hệ thống
Bộ xử lý dữ liệu
(data processor)
Bộ tiếp nhận
ngƣời dùng
(user processor)

cũng phải thực hiện truy tìm dữ liệu trên nhiều trạm khác nhau.
Việc phân đoạn của một quan hệ phải đƣợc xác định bởi ngƣời quản trị
CSDL, và phải tuân thủ ba quy tắc: không mất mát thông tin, khôi phục lại đƣợc
và không trùng lặp (chỉ áp dụng cho phân đoạn ngang). 20
Các kiểu phân đoạn: Phân đoạn ngang: Phân đoạn ngang là sự phân chia một quan hệ thành các
tập các bộ con, mỗi tập con đƣợc xác định bởi phép chọn áp dụng cho quan hệ
(phân đoạn ngang nguyên thuỷ):
R
i
= 
Fi
(R), 1 i  z trong đó F
i
là vị từ chọn trên quan hệ R
Hay đƣợc xác định bởi phép nối nửa của một quan hệ với mỗi đoạn ngang
của một quan hệ khác (phân đoạn ngang dẫn xuất):
R
i
Phân đoạn ngang
Phân đoạn dọc
Phân đoạn hỗn hợp
Hình 5 - Các kiểu phân đoạn 21
Mức thấp nhất là không nhân bản, mỗi một đoạn chỉ lƣu trữ tại một vị trí.
Mức hay sử dụng nhất là nhân bản từng phần.
Mỗi đoạn – hay mỗi bản sao của phân đoạn - phải đƣợc cấp phát vào một
trạm cụ thể nào đó trong hệ thống phân tán. Quá trình đó đƣợc gọi là cấp phát
dữ liệu. Việc chọn vị trí để cấp phát và mức độ nhân bản phụ thuộc vào hiệu
suất và khả năng sẵn sàng của hệ thống cũng nhƣ phụ thuộc vào loại và tần suất
các giao dịch của mỗi vị trí. Ví dụ, nếu nhƣ yêu cầu tính sẵn sàng cao, cùng một
giao dịch có thể đƣợc thực hiện tại bất kỳ vị trí nào và các giao dịch chủ yếu là
truy xuất dữ liệu, thì việc nhân bản toàn bộ CSDL là một lựa chọn tốt. Tuy nhiên
việc tìm phƣơng án tối ƣu, hay ít nhất là một phƣơng án tốt cho việc phân bố dữ
liệu phân tán là bài toán khó.
Cho một tập các đoạn F = {F
1
,F
2
,…,F
n
 và một mạng bao gồm các nút
S={S
1
,S

Về khái niệm, tối ƣu hoá truy vấn nhằm chọn ra một chiến lƣợc tốt nhất
trong không gian các chiến lƣợc thực thi [10].
Chiến lƣợc đƣợc chọn phải hạ thấp tối đa hàm chi phí bao gồm thời gian xử
lý của CPU, thời gian truy nhập dữ liệu đối với CSDL tập trung và trong CSDL
phân tán cần xét thêm chi phí truyền dữ liệu.
Truy vấn cần tối ƣu giả thiết đƣợc diễn tả bằng đại số quan hệ trên các
CSDL có thể là các đoạn trong CSDL phân tán.
Trong CSDL tập trung, chiến lƣợc thực thi truy vấn có thể đƣợc diễn tả
chính xác bằng mở rộng của đại số quan hệ và chọn ra câu truy vấn đại số tốt
nhất trong số các câu truy vấn tƣơng đƣơng. Đây là bài toán khó khi số lƣợng
các quan hệ lớn nên nói chung thƣờng đƣợc rút lại ở yêu cầu chọn đƣợc một lời
giải gần tối ƣu.
Trong CSDL phân tán, đại số quan hệ chƣa đủ để diễn tả các chiến lƣợc
thực thi. Bên cạnh việc chọn thứ tự cho các phép toán đại số quan hệ cần phải
chọn các vị trí tốt nhất để xử lý dữ liệu. Vì thế không gian lời giải các chiến
lƣợc thực thi tăng lên làm cho việc xử lý phân tán phức tạp hơn. Kết quả của quá
trình tối ƣu hóa trong môi trƣờng phân tán là câu truy vấn đại số đƣợc đặc tả
theo các đoạn và các phép toán truyền dữ liệu hỗ trợ cho việc thực thi truy vấn
qua các vị trí.
Các yêu cầu của phép biến đổi tƣơng đƣơng :
- Các phép biến đổi phải thực sự hữu ích đối với phần lớn các dạng truy
vấn hay một lớp các truy vấn thƣờng dùng mà không cần chi phí quá nhiều để
thực hiện quá trình biến đổi đó.
- Các phép biến đổi phải bảo toàn kết quả của truy vấn trƣớc và sau khi
biến đổi, có nghĩa là hai biểu thức trƣớc và sau khi biến đổi phải cho cùng một
kết quả khi thay các lƣợc đồ trong biểu thức bởi các thể hiện cụ thể.
- Các phép biến đổi phải làm giảm chi phí thực hiện câu hỏi. 23

không gian tìm kiếm lớn có thể mất nhiều thời gian có khi còn lớn hơn cả thời
gian thực thi thực sự.
Ví dụ 2.1: Với CSDL gồm các quan hệ :
NHANVIEN(MSNV, TENNV, NNGH)
MUCLUONG(NNGH, LUONG)
DUAN(MSDA, TENDA, NSDA, DDDA)
PHANCONG(MSNV, MSDA, NVU, TGIAN)

Tạo ra không gian
tìm kiếm
Chiến lƣợc tìm
kiếm
QEP tốt nhất
QEP tƣơng đƣơng
Câu truy vấn
Quy tắc biến đổi
Mô hình chi phí
Hình 6 - Quá trình tối ưu hoá truy vấn 25
Xét câu truy vấn sau :
SELECT TENNV
FROM NHANVIEN, PHANCONG, DUAN
WHERE NHANVIEN.MSNV=PHANCONG.MSNV
AND PHANCONG.MSDA=DUAN.MSDA

Để thực hiện truy vấn, ta có thể xây dựng các cây nối tƣơng đƣơng nhƣ :
PHANCONG

PHANCONG
DU AN
(3)

9
PHANCONG
X
NHANVIEN DU AN
(4)
Hình 7 - Các cây nối tương đương

MSNV, MSDA

MSNV
MSDA
X


MSDA

PHAN CONG
PHAN CONG