Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN
PHẠM THỊ THU HUYỀN
TỐI ƯU HÓA TRUY VẤN
TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. ĐOÀN VĂN BAN
Thái Nguyên - 2010
Thái Nguyên - 2010 -1-
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên MỤC LỤC
Trang phụ bìa
Lời cam đoan
Lời cám ơn
Mục lục i
Danh mục ký hiệu, các chữ viết tắt ii
Danh mục hình vẽ, ảnh chụp, đồ thị iii
PHẦN MỞ ĐẦU 1
1. Lý do chọn đề tài 1
2. Phạm vi nghiên cứu và ứng dụng 1
3. Ý nghĩa khoa học 1
4. Phƣơng pháp nghiên cứu 1
5. Các kết quả dự kiến đạt đƣợc 2
Chƣơng 1. CƠ SỞ DỮ LIỆU PHÂN TÁN
3
2.2.4. Các qui tắc liên quan đến phép chọn và phép chiếu 18
2.2.5. Thuật toán cải tiến cây biểu diễn biểu thức quan hệ
19
2.3 Phân rã câu truy vấn thành những câu truy vấn con 24
2.3.1 Đồ thị nối các quan hệ
24
2.3.2. Tách câu truy vấn thành các câu truy vấn con
25
2.3.3 Dùng phép nửa kết nối để giảm kích thước quan hệ
26
2.3.4 Phương pháp thay thế n-bộ 26
2.4 Các kỹ thuật tối ƣu hóa tập trung
27
2.4.1 Thuật toán INGRES
28
-2-
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 2.4.2 Thuật toán SYSTEM R
31
2.5 Kết luận 34
Chƣơng 3. TỐI ƢU HÓA TRUY VẤN PHÂN TÁN
35
3.1 Phân rã câu truy vấn
35
82
Chƣơng 4. CÀI ĐẶT VÀ THỬ NGHIỆM THUẬT TOÁN 85
4.1 Xác định thuật toán 85
4.2 Cài đặt thử nghiệm thuật toán tối ƣu truy vấn trong cơ sở dữ liệu phân
tán 85
4.2.1. Cấu trúc của CSDL
85
4.2.2. Xây dựng ứng dụng 88
4.3 Kết luận
95
KẾT LUẬN
96
TÀI LIỆU THAM KHẢO 97
-1-
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên PHẦN MỞ ĐẦU
1. Lý do chọn đề tài
Xã hội ngày càng phát triển kèm theo yêu cầu khối lượng thông tin cần xử
lý, lưu trữ tăng lên. Trên thực tế, các doanh nghiệp, các đơn vị và các tổ chức phải
phân bố trên một vùng rộng lớn về mặt địa lý, có thể dàn trải trên phạm vi nhiều
thành phố, hoặc toàn bộ quốc gia hay đến một vài quốc gia, thậm chí trên toàn
cầu. Do đó, dữ liệu không thể lưu trữ tập trung ở một địa điểm nhất định mà rải
khắp các địa điểm mà cơ quan, tổ chức hay doanh nghiệp đó hoạt động. Khi dữ liệu
không còn lưu trữ tập trung thì vấn đề làm thế nào để quản lý, tốc độ truy xuất dữ
liệu phục vụ cho công tác chuyên môn không bị ảnh hưởng, không bị gián đoạn
Chƣơng 1. CƠ SỞ DỮ LIỆU PHÂN TÁN
1.1. Khái niệm về hệ cơ sở dữ liệu phân tán
1.1.1. Khái niệm
Cơ sở dữ liệu phân tán [3] là một tập hợp các dữ liệu phục thuộc lôgic lẫn
nhau của cùng một hệ thống và được lưu trữ trên các trạm của một mạng máy tính.
Cơ sở dữ liệu phân tán làm tăng khả năng truy nhập tới cơ sở dữ liệu lớn trên mạng.
Trong hệ thống đó mỗi máy tính quản lý một cơ sở dữ liệu thành phần được gọi là 1
node hoặc site.
Hệ quản trị cơ sở dữ liệu phân tán (DBMS) là phần mềm quản trị cơ sở dữ
liệu, đảm bảo trong suốt đối với người sử dụng và cho phép tính tự trị nghĩa là mỗi
cơ sở dữ liệu thành phần vẫn được quản trị độc lập và riêng biệt.
Định nghĩa này nhấn mạnh hai khía cạnh quan trọng của cơ sở dữ liệu phân
tán
- Tính phân tán: Thực tế dữ liệu không cư trú ở cùng một trạm, vì vậy chúng
ta có thể phân biệt một cơ sở dữ liệu phân tán với cơ sở dữ liệu tập trung.
- Sự tương quan logic: Các dữ liệu có một số tính chất ràng buộc lẫn nhau và
như vậy có thể phân biệt cơ sở dữ liệu phân tán với tập các cơ sở dữ liệu địa
phương hoặc với các tệp ở các trạm khác nhau trên mạng.
1.1.2 Những ưu điểm của cơ sở dữ liệu phân tán
Lợi ích cơ bản nhất của cơ sở dữ liệu phân tán là dữ liệu của các cơ sở dữ
liệu vật lý riêng biệt được tích hợp logic với nhau làm cho nhiều người sử dụng trên
mạng có thể truy nhập được [6].
1. Cho phép quản lý dữ liệu với nhiều mức trong suốt
- Trong suốt mạng - phân tán: Hệ quản trị cơ sở dữ liệu phải được trong suốt
phân tán theo nghĩa làm cho người sử dụng không cần biết vị trí của dữ liệu và
không cần biết sự phức tạp truy cập qua mạng.
- Trong suốt bản sao
- Trong suốt phân đoạn
2. Tăng độ tin cậy và khả năng sẵn sàng
+ Quản lý giao dịch phân tán
+ Phục hồi cơ sở dữ liệu phân tán
+ Quản lý các bản sao
+ Quản lý thư mục - catalog phân tán
- Hệ thống phần cứng cũng phức tạp hơn vì cần có nhiều trạm và các trạm
phải được kết nối trên mạng.
- Các phần mềm hệ thống đảm bảo quản trị, duy trì kết nối, trao đổi dữ liệu
trên mạng.
- Bảo mật khó khăn.
Ở mức phần cứng vật lý, những nhân tố chính sau là để phân biệt một hệ cơ
-5-
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên sở dữ liệu phân tán với hệ cơ sở dữ liệu tập trung [6]:
- Có nhiều máy tính được gọi là các trạm hay các nút.
- Các trạm này phải được kết nối bởi một kiểu mạng truyền thông để truyền
dữ liệu và những câu lệnh giữa các trạm với nhau, như là ở hình 1.1
giảm truyền tải trên mạng lớn. Hệ thống cho phép tiếp tục thực hiện nếu như các
trạm từ xa có sự cố. Trong suốt bản sao đảm bảo user không biết đó là các bản sao
vì dữ liệu luôn được cập nhật và đồng bộ với dữ liệu gốc.
+ Trong suốt phân đoạn: Một quan hệ trong cơ sở dữ liệu phân tán có thể
phân đoạn ngang hoặc phân đoạn dọc nghĩa là được tách thành các bộ dữ liệu hoặc
các quan hệ con và lưu trữ trên nhiều trạm khác nhau. Trong suốt phân đoạn cho
phép người sử dụng không cần biết có sự phân đoạn, các truy vấn dữ liệu vẫn được
viết như cơ sở dữ liệu tập trung.
1.2.2 Trong suốt giao dịch
Cơ sở dữ liệu phân tán cho phép một giao dịch có thể cập nhật, sửa đổi dữ
liệu trên các trạm khác nhau. Để đảm bảo dữ liệu nhất quán trên toàn hệ thống, các
trạm trong giao dịch chỉ ủy thác khi tất cả các trạm đã ủy thác thành công hoặc roll
back khi một trạm bị thất bại.
1.2.3 Trong suốt thất bại
Đảm bảo tại một trạm của hệ thống bị hỏng thì hệ thống vẫn làm việc bình
thường (do cơ chế tạo bản sao hoặc làm việc trên các trạm không bị sự cố). Nếu
mạng hoặc hệ thống có sự cố trong khi ủy thác của giao dịch cơ sở dữ liệu phân tán
thì giao dịch đó được giải quyết tự động và trong suốt theo nghĩa khi mạng hoặc hệ
thống khôi phục thì tất các các trạm này hoặc là ủy thác hoặc là roll back lại giao
tác đó.
1.2.4 Trong suốt thao tác
Cho phép các câu lệnh thao các dữ liệu đơn giản để truy nhập được các cơ sở
-7-
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên dữ liệu tại trạm cục bộ hoặc trạm từ xa. Các thao tác xử lý dữ liệu từ xa không phức
tạp và vẫn đảm bảo vẫn giống như khi thao tác dữ liệu trên hệ cơ sở dữ liệu không
phân tán.
1.2.5 Trong suốt về tính không thuần nhất
Hình 1.2: Kiến trúc tham chiếu của cơ sở dữ liệu phân tán
1.4 Các kỹ thuật xây dựng cơ sở dữ liệu phân tán
- Kỹ thuật phân tách dữ liệu từ một cơ sở dữ liệu để lưu trữ trên các
trạm
khác nhau được gọi là phân đoạn.
- Sử dụng bản sao cho phép cùng một dữ liệu có thể được lưu trữ trên
nhiều hơn một trạm.
- Quá trình định vị các phân đoạn dữ liệu hoặc định vị các bản sao phân
đoạn lưu trữ dữ liệu trên các trạm khác nhau.
1.4.1 Phân đoạn
Sự phân đoạn là chia dữ liệu trong các bảng dữ liệu thành các bộ hoặc các
bảng dữ liệu con. Có ba kiểu phân đoạn một quan hệ tổng thể: Phân đoạn ngang,
phân đoạn dọc và phân đoạn hỗn hợp [8].
định vị
-9-
Ví dụ 1.1: Xét quan hệ tổng thể
NHACUNGCAP(SHNCC, TEN,THPHO)
Trong đó có các thuộc tính:
SHNCC: Số hiệu nhà cung cấp
TEN: Tên nhà cung cấp
THPHO: Thành phố
Ta tách quan hệ NHACUNGCAP thành hai quan hệ NCC
1
và NCC
2
thuộc hai chi nhánh „HN‟ và „HP‟. Ta có phân đoạn ngang:
NCC
1
=
THPHO=”HN”
NHACUNGCAP
NCC
2
=
THPHO=”HP”
NHACUNGCAP
Thoả mãn:
-
Điều kiện xây dựng lại: NHACUNGCAP = NCC
1
NCC
2
-
Điều kiện rời nhau thoả mãn vì: NCC
1
CUNGCAP
2
= CUNGCAP ⋉SHNCC=SHNCCNCC
2
Việc bố trí trên cùng một trạm của mỗi cặp đoạn (NCC
1
, CUNGCAP
1
) và
(NCC
2
, CUNGCAP
2
) cho phép cải tiến hiệu năng của phép kết nối các quan hệ
NHACUNGCAP và CUNGCAP vì có thể thực hiện song song bởi hai phép kết nối
(NCC
1
⋈ CUNGCAP
1
) và (NCC
2
⋈ CUNGCAP
2
).
- Điều kiện không mất thông tin của phân đoạn trên đòi hỏi không có
SHNCC nào trong quan hệ CUNGCAP mà lại không chứa trong quan hệ
NHACUNGCAP. Ở đây có ràng buộc toàn vẹn tham chiếu.
s CUNGCAP => phải pNHACUNGCAP mà p.SHNCC= s.SHNCC
p.SHNCC NCC
1
1
.SHNCC
=> p
2
NCC
2
p.SHNCC=p
2
.SHNCC
Mâu thuẫn vì SHNCC là khoá của NHACUNGCAP
1.4.1.3 Phân đoạn dọc
Phân đoạn dọc là sự chia một quan hệ thành tập con các bộ, mỗi tập
được xác định bởi một phép chiếu được áp dụng cho quan hệ: R
i
= П
ATTRi
R,
trong đó ATTR
i
là tập con các thuộc tính của R.
Tiêu chuẩn cho sự phân đoạn dọc là đúng đắn:
- Điều kiện đầy đủ: Nếu một thuộc tính xuất hiện trong một quan hệ tổng
thể thì nó cũng phải xuất hiện trong một đoạn dọc nào đó.
- Điều kiện xây dựng lại: Cần phải thêm vào mỗi đoạn khoá chính, do
đó
việc xây dựng lại được nhờ vào phép kết nối các đoạn dọc theo
các thuộc tính
chung.
-
Điều kiện rời nhau: ít nhất khoá phải được lặp lại trên tất cả các
1
⋈
SHNV=SHNV
П
SHNV, LUONG, THUE NV2
1.4.1.4 Phân đoạn hỗn hợp
Là sự kết hợp cả phân đoạn dọc và phân đoạn ngang.
Ví dụ 1.4: Xét quan hệ tổng thể
NHANVIEN(SHNV, TEN,LUONG, THUE, SHQL, SHPHONG)
Tách quan hệ NHANVIEN thành các quan hệ NV
1
, NV
2
, NV
3
, NV
4
NV
1
=
SHPHONG
10 SHNV, TEN, SHQL, SHPHONG NHANVIEN
NV
2
=
10<SHPHONG
20 SHNV, TEN, SHQL, SHPHONG NHANVIEN
NV
3
=
cây phân
đoạn
của quan hệ NHANVIEN. Nút gốc (quan hệ NHANVIEN) được
phân đoạn dọc thành hai phần; một phần tương ứng với một nút lá của cây (NV
4
),
phần còn lại được phân đoạn ngang, do vậy sinh ra ba nút lá khác, tương ứng với ba
phân đoạn: NV
1
, NV
2
, NV
3
.
1.4.2 Nhân bản dữ liệu
- Các chiến lược nhân bản dữ liệu:
1. Nhân bản dữ liệu đầy đủ: Toàn bộ cơ sở dữ liệu sẽ được tạo trên tất cả
mỗi trạm.
Ưu điểm: Điều này sẽ cải thiện tính sẵn sàng cao nhất vì nếu sự cố trên
trạm này thì vẫn có dữ liệu trên trạm khác và cải thiện hiệu năng lấy dữ liệu trên
mạng cho các truy vấn toàn bộ vì dữ liệu sẽ được lấy từ các trạm cục bộ.
Nhược điểm: Các thao tác cập nhập dữ liệu rất chậm vì phải copy, đồng
bộ dữ liệu cho mọi trạm. Kỹ thuật điểu khiển tương tranh và phục hồi sẽ phức tạp
hơn.
2. Không có nhân bản dữ liệu: Mỗi phân đoạn chỉ được lưu trữ trên một
trạm, phương án này còn được gọi là định vị không dư thừa dữ liệu.
Trong
trường hợp này các phân đoạn phải tách rời nhau để tránh lặp bản ghi giống nhau
cho các phân đoạn ngang và phân đoạn hỗn hợp.
-15-
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên Chƣơng 2. CÁC NGUYÊN LÝ CHUNG CỦA TỐI ƢU HÓA CÂU TRUY
VẤN PHÂN TÁN
Các ngôn ngữ hỏi bậc cao như SQUARE, SEQUEL, SQL, cho phép viết
nhiều câu truy vấn với sự quan tâm nhiều đến thời gian thực hiện, và thời gian thực
hiện đó có thể giảm đáng kể nếu bộ xử lý ngôn ngữ hỏi viết lại (bằng cách khác)
câu truy vấn trước khi thực hiện. Sự cải tiến như vậy thường gọi là "Sự tối ưu hoá",
mặc dù câu truy vấn được viết lại không cần tối ưu trên tất cả các cách cài đặt câu
truy vấn có thể. Chương này sẽ trình bày một số phương pháp tối ưu hóa các biểu
thức quan hệ, đặc biệt là xử lý biểu thức liên quan đến phép kết nối và tích
Decartes, xem xét các kỹ thuật điển hình INGRES và System R.
2.1. Các chiến lược tối ưu hóa cơ bản
Trong ngôn ngữ hỏi dựa trên đại số quan hệ, các truy vấn liên quan đến tích
Decartes và phép kết nối là rất tốn thời gian.
Ví dụ 2.1: Xét biểu thức AB × CD (AB là một quan hệ với các thuộc tính A, B); ta
đồng nhất hai quan hệ này với hai tệp dữ liệu. Để đưa ra giá trị của tích Decartes
này phải duyệt hết bản ghi của một quan hệ, chẳng hạn AB, ở vòng ngoài, với mỗi
bản ghi r của tệp AB, duyệt tệp CD ở vòng trong và nối r với mỗi bản ghi của tệp
CD. Giả sử quan hệ AB có n bản ghi, CD có m bản ghi thì tích Decartes AB × CD
có n × m bản ghi. Rõ ràng phép tính trên rất tốn kém về thời gian và ô nhớ.
Ullman J.D trong các kết quả nghiên cứu của mình đã trình bày 6 chiến lược
tổng quát cho việc tối ưu hóa câu truy vấn. ý tưởng tối ưu chia làm 2 nhóm: Nhóm 1
gồm các phép biến đổi đại số có liên quan hoặc không liên quan đến cách lưu trữ
các quan hệ, nhóm 2 gồm các chiến lược có lợi cho việc lưu trữ các quan hệ như
khoá, chỉ số. Các chiến lược thực hiện như sau [5]:
1. Thực hiện phép chọn sớm nhất có thể: Biến đổi câu truy vấn để đưa phép chọn
Hầu hết các chiến lược trên liên quan đến biến đổi biểu thức đại số. Một xử
lý câu truy vấn bắt đầu với việc xây dựng cây phân tích biểu thức đại số, trong đó
các nút biểu diễn toán tử đại số quan hệ và toán tử đặc biệt của ngôn ngữ. Ngôn
ngữ hỏi có thể là ngôn ngữ đại số quan hệ như SQUARE, SEQUEL, hoặc là một
ngôn ngữ phép tính quan hệ mà các biểu thức phép tính được chuyển thành biểu
thức đại số.
2.2.1 Các yêu cầu của phép biến đổi tối ưu hoá câu truy vấn
- Các phép biến đổi phải thực sự hữu hiệu đối với phần lớn các dạng câu
truy vấn hay một lớp các câu truy vấn thường dùng mà không phải 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 câu 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 truy vấn. Chi
-17-
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên phí cho xử lý câu truy vấn có rất nhiều yếu tố, tuy nhiên ta chỉ quan tâm đến một số
thông báo cơ bản nhất sau đây: số lần truy xuất khối nhớ giữa bộ nhớ trong và bộ
nhớ ngoài; số bản ghi cần phải xử lý ở thiết bị trung tâm; phần bộ nhớ để lưu trữ
các kết quả trung gian trong quá trình thực hiện câu truy vấn.
2.2.2 Biểu thức tương đương
Hai biểu thức E
1
và E
2
gọi là tương đương, ký hiệu E
1
E
1
, A
2
, ,A
n
; E
2
có các thuộc tính B
1
, ,B
m
. Gọi r
1
và r
2
là hai quan hệ tương
ứng của E
1
, E
2
. Khi đó giá trị của E
1
E
2
là tập các ánh xạ v từ A
1
, A
2
, ,A
n
Nếu biểu diễn E
2
E
1
theo kiểu này, nó hoàn toàn cho cùng một tập kết
quả. Do vậy hai biểu thức là tương đương.
Chú ý: Nếu xem quan hệ là tập các bộ thì phép kết nối, kết nối tự nhiên, tích
Decartes sẽ không giao hoán vì thứ tự các thuộc tính trong quan hệ kết quả bị thay
đổi.
Qui tắc kết hợp của phép kết nối và phép tích Decartes
Nếu E
1
, E
2
, E
3
là biểu thức quan hệ; p
1
, p
2
là biểu thức điều kiện thì:
(E
1
p1
E
2
)
p2
E
3
E
1
(E
2
E
3
)
-18-
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 2.2.4. Các qui tắc liên quan đến phép chọn và phép chiếu
Qui tắc hợp nhất của các phép chiếu: Dãy các phép chiếu có thể tổ hợp thành
một phép chiếu.
A1, ,An(B1, ,Bm(E))A1, ,An(E)
Với các thuộc tính A
1
, A
2
, , A
n
phải nằm trong tập các thuộc tính B
1
, B
2,
,B
m
Qui tắc giao hoán của phép chọn và tích Decartes
Nếu tất cả các thuộc tính của p là thuộc tính của E
1
thì:
p(E1 E2)p(E1) E2
Hệ quả: Nếu p = p
1
p
2
, p
1
chỉ liên quan tới các thuộc tính của E
1
, p
2
chỉ liên quan
tới thuộc tính E
2
, từ các qui tắc , , ta có:
p(E1 E2)p1(E1)p2(E2)
Nếu p
1
chỉ liên quan tới các thuộc tính E
1
, còn p
2
liên quan tới các thuộc
tính của cả E
1
-19-
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên Qui tắc giao hoán của phép chọn và phép hiệu tập hợp
p(E1 - E2) p(E1) - p(E2)
Theo qui tắc , nếu tên các thuộc tính của E
1
và E
2
là khác nhau thì cần thay thế
các thuộc tính trong p ở vế phải tương ứng các thuộc tính của E
1
.
Chú ý: Phép chọn
p
(E
2
)
là không cần thiết, có thể thay bởi E
2
. Tuy nhiên,
trong
nhiều trường hợp, việc thực hiện phép chọn
p
(E
2
)
thì phải thay A
1
, ,A
n
ở vế phải bởi các tên phù hợp.
2.2.5. Thuật toán cải tiến cây biểu diễn biểu thức quan hệ
Chúng ta có thể áp dụng các qui tắc trên để tối ưu các biểu thức quan
hệ.
Biểu thức "tối ưu" kết quả phải tuân theo các nguyên tắc trong mục 2.1,
mặc
dù các nguyên tắc không có nghĩa bảo đảm để tối ưu cho tất cả các biểu thức
tương đương [5].
Đầu ra của thuật toán này là một chương trình, bao gồm các bước như sau:
1. Áp dụng của một phép chọn hoặc một phép chiếu đơn giản
2. Áp dụng của một phép chọn và một phép chiếu, hoặc
3. Áp dụng của một tích Decartes, phép hợp hoặc phép hiệu tập hợp cho
hai biểu
thức mà trước đó các phép chọn và / hoặc các phép chiếu đã
được áp dụng cho
một hay hai hạng thức
Copyright: Tài liệu đại học ©