HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
---------------------------------------

PHẠM VĂN TUÂN
TRUY VẤN TRONG CƠ SỞ DỮ LIỆU
PHÂN TÁN VÀ ỨNG DỤNG

Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số: 60. 48. 01( Khoa học máy tính)
TÓM TẮT LUẬN VĂN THẠC SĨ

HÀ NỘI – NĂM 2012


Luận văn được hoàn thành tại:
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

Người hướng dẫn khoa học: PGS. TS Lê Huy Thập

Phản biện 1:……………………………………
Phản biện 2:

…………………………………

Luận văn sẽ được bảo vệ trước Hội đồng chấm
luận văn thạc sĩ tại Học viện Công nghệ Bưu
chính Viễn thông
Vào lúc: ......giờ.....ngày.......tháng......năm .....

Có thể tìm hiểu luận văn tại:
- Thư viện của Học viện Công nghệ Bưu

2
toán liên quan đến vấn đề truy vấn và cài đặt thử nghiệm
thuật toán truy vấn phân tán.
3. Ý nghĩa khoa học
Trên cơ sở nghiên cứu về các mô hình CSDL phân
tán và các cơ chế truy vấn để xây dựng thuật toán truy vấn
tối ưu. Những kết quả dự kiến của luận văn sẽ góp phần vào
việc thiết kế CSDL phân tán phục vụ cho việc truy vấn hiệu
quả.


3

CHƯƠNG I: TỔNG QUAN
1.1 Giới thiệu chương
1.2.1 Nội dung
1.2.1 Giới thiệu về hệ quản trị cở sở dữ liệu phân tán
1.2.1.1 Khái niệm
Cơ sở dữ liệu phân tán là một tập hợp các dữ liệu phụ thuộc
logic 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 cậ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à một nute 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 và luôn được đảm bảo trong suốt đối với người
sử dụng và cho phép tính tự trị.
Định nghĩa này nhấn mạnh hai khía cạnh quan trong của cơ
sở dữ liệu phân tán.
- Tính phân tán

Đả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
1.2.1.4.4 Trong suốt thao tác
Cho phép các câu lệnh thao tác dữ liệu đơn giản để truy cập
được các cơ sở dữ liệu tại trạm cục bộ hoặc trạm từ xa.


5
1.2.1.4.5 Trong suốt về tính không thuần nhất
Cho phép tự động kết hợp nhiều hệ quản trị cơ sở dữ liệu
khác nhau với các khả năng trao đổi dữ liệu, xử lý cập nhật dữ liệu,
xử lý giao tác phân tán trên toàn bộ hệ thống.
1.2.1.4.6 Kiến trúc tham chiếu của cơ sở dữ liệu phân tán
- Lược đồ tổng thể
- Phân mảnh
- Lược đồ vị trí
- Lược đồ ánh xạ cục bộ
1.2.2 Các phương pháp phân mảnh
Phân mảnh là chia các bảng dữ liệu thành các bảng dữ liệu
con. Có ba kiểu phân mảnh một quan hệ tổng thể: Phân mảnh ngang,
phân mảng dọc và phân mảnh hỗn hợp.
Ba yêu cầu của phân mảnh:
- Điều kiện không mất thông tin
- Điều kiện xây dựng lại
- Điều kiện rời nhau
1.2.2.1 Phân mảnh ngang
Phân mảnh ngang là sự phân chia một quan hệ thành các tập
con các bộ, mỗi tập con được xác định bởi phép chọn với tân từ p
trên quan hệ tổng thể R: Ri = σ pi với pi là tân từ của Ri .Để có thể
khôi phục được R ta dùng phép hợp các quan hệ R = R1

tập trung
1.2.3.1 Nguyên lý chung của tối ưu hóa truy vấn
Một câu vấn tin bậc cao dạng SQL sẽ có rất nhiều câu vấn
tin dạng đại số quan hệ tương đương. Phương pháp để tìm ra được


7
câu vắn tin đại số quan hệ có chi phí ít nhất, sau đó chuyển câu vấn
tin đại số đã tìm được đó trở lại dạng SQL, được gọi là “Sự tối ưu
hóa”.
1.2.3.2 Các chiến lược tối ưu cơ bản
Các chiến lược bao gồm
- Thực hiện phép chọn sớm nhất có thể

- Tổ hợp phép chọn xác định với phép tích Decartes thành
phép kết nối
- Tổ hợp dãy các phép toán một ngôi như phép chọn và phép
chiếu
- Tìm các biểu thức con chung trong một biểu thức
- Xử lý các tệp trước
- Đánh giá trước khi thực hiện phép toán
1.2.3.3 Phân rã câu truy vấn thành những câu truy vấn con
- Đồ thị nối các quan hệ
- Tách câu truy vấn thành các câu truy vấn con

- Dùng phép nửa kết nối để giảm kích thước quan hệ
- Phương pháp thay thế n – bộ
1.2.3.4 Thuật toán INGRES
Thuật toán: INGRES – QOA
Input: MVQ: Truy vấn đa biến với n biến


Endfor
V

CHOOSE – VARIABLE(MVQ’) { V được chọn cho

phép thế toàn bộ}
For mỗi bộ t

V do

Begin
MVQ’’

thay thế các giá trị cho t trong MVQ’

output

INGRES – QOA(MVQ’’) {gọi đệ quy}

output

output

output’{ hợp tất cả các kết quả}

end
Endif
END.
1.2.3.5 Thuật toán SYSTEM R

CHƯƠNG 2 : CÁC THUẬT TOÁN TỐI ƯU TRONG
HỆ CƠ SỞ DỮ LIỆU PHÂN TÁN

2.1 Giới thiệu chương
2.2 Nội dung
1. Phân rã câu truy vấn
a. Chuẩn hoá
b. Phân tích
c. Loại bỏ dư thừa
d. Viết lại
2. Định vị dữ liệu phân tán
a. Rút gọn phân mảnh ngang nguyên thuỷ
b. Rút gọn phân mảnh dọc
c. Rút gọn phân mảnh gián tiếp
d. Rút gọn phân mảnh hỗn hợp
3. Khái quát về xử lý câu truy vấn
a. Vấn đề xử lý truy vấn
b. Các mục tiêu của xử lý câu truy vấn
c. Các giai đoạn xử lý câu truy vấn
4. Tối ưu hoá các câu truy vấn phân tán
 Đầu vào bộ tối ưu hoá câu truy vấn
 Các thuật toán tối ưu hoá truy vấn trong môi trường phân tán
2.2.1 Thuật toán INGRES phân tán
Thuật toán : D- INGRES – QOA
Input : MVQ : Truy vấn đa biến với n biến


11
Output : output : Kết quả của truy vấn đa biến cuối cùng
BEGIN


SELECT _ RATEGY(MVQ’); (3.2)

{truyền các mảnh đã chọn tới các trạm đã chọn}
For mỗi cặp (F,S) trong Fragnemt – site – list do (3.3)
Chuyển đoạn F tới trạm S;
End – for
Run(MVQ’);
n

n-1;

(3.4)

End – while {đầu ra của thuật toán là kết quả của MVQ’
cuối cùng}


12
End. (D- INGRES - QOA)
Bước 1 : Xử lý địa phương tất cả các truy vấn một biến
(phép chọn và phép chiếu).
Bước 2: Thuật toán thu gọn được áp dụng cho truy vấn ban
đầu, tách các truy vấn không thể rút gọn và các truy vấn một biến ra.
Bỏ qua các truy vấn một biến vị đã xử lý ở bước 1
Bước 3: Áp dụng cho các câu truy vấn không thể rút gọn.
Bước 3.1: Chọn các truy vấn chưa được xử lý và liên quan
đến các mảnh nhỏ hơn.
Bước 3.2: Chọn chiến lược tốt nhất để xử lý truy vấn MVQ’
(truy vấn không thể rút gọn và có ít nhất hai biến). Chiến lược này


 ... 

Rin)

) 

Ri2

Ri3)

;
tính toán chi phí chiến lược ;

endfor
strat

chiến lược với chi phí tối thiểu ;

For mỗi trạm k chứa một quan hệ liên quan trong QT do
Begin
LSk

chiến lược cục bộ (strategy, k);

Send(LSk, site k) { mỗi chiến lược cục bộ được tối
ưu hoá tại trạm k}

Endfor


SJ;

End-if
End-for
While BS

{Chọn các phép kết nối có lợi}

do

Begin
SJ

most_benefit(BS)

{SJ: semijoin có

benefit_cost lớn nhất}
BS

BS – SJ;

ES

ES + SJ;

{Loại SJ khỏi BS}

Sửa đổi các thống kê để phản ánh kết quả của SJ thêm vào;
BS

ES

ES – SJ;

End-if
End-for
End-for
End. {SDD -1- QOA}


Giai đoạn khởi đầu: sinh ra một tập những phép nửa kết nối

có lợi (BS), vào một chiến lược thực thi(ES) bao gồm các xử lý địa
phương.


Giai đoạn tiếp theo: Lặp lại lựa chọn ra các phép nửa kết nối

có lợi (SJi) từ BS, sửa đổi các thống kê cơ sở dữ liệu và BS. Sự sửa
đổi ảnh hưởng đến các thống kê của quan hệ R liên quan trong SJi và
phép nửa kết nối còn lại trong BS mà sử dụng quan hệ R. Vòng lặp
kết thúc khi tất cả các phép nửa kết nối được thêm vào ES sẽ là thứ
tự thực thi của chúng.


16


Giai đoạn chọn các trạm thực hiện: Với mỗi trạm đề cử đánh



Giải thích

ProductKey

Int

Khóa ngoại(bảng Product)

CustomerKey

Int

Khóa ngoại

SalesOrderNumber

Nvarchar(20)

Mã đơn đặt hang

OrderQuantity

Smallint

Chất lượng yêu cầu

UnitPrice

Money

liệu
GeographyKey

Int

Khóa chính

StateProvinceCode

Nvarchar(3)

Mã thành phố

StareProvinceName

Nvarchar(50)

Tên tỉnh, thành phố

CountryRegionName

Nvarchar(50)

Tên vùng

PostalCode

Nvarchar(15)

Mã vùng quốc tế


Color

Nvarchar(15)

Màu sắc

SafetyStockLevel

Smallint

Mức độ lưu trữ hang

ListPrice

Money

Giá ghi trên bao bì

Ze

Nvarchar(50)

Kích thước

Eight

Float

Cân nặng

liệu
CustomerKey

Int

Khóa chính

GeographyKey

Int

Khóa ngoại

FirstName

Nvarchar(50)

Tên

MiddleName

Nvarchar(50)

Tên đệm

LastName

Nvarchar(50)

Tên họ


Phone

Nvarchar(20)

Điện thoại

DateFirstPurchase

Datetime

Ngày đầu tiên mua
hàng

3.2.3 Phân mảnh cơ sở dữ liệu hàng hóa của công ty TNHH
HomeTech


20
3.2.4 Ứng dụng thuật toán INGRES để giải quyết bài toán truy
vấn cơ sở dữ liệu hàng hóa đã được phân mảnh
Các bảng

dữ

liệu gồm có Customer,

Geography,

InternetSales, Product.

21

Truy vấn với câu truy vấn sau :
Select

Customer.GeographyKey,

InternetSales.ProductKey,

Customer.FirstName,

InternetSales.TotalProductCost,

Product.EnglishProductName
From Customer, InternetSales, Product
Where internetSales.CustomerKey = Customer.CustomerKey And
Product.ProductKey

=

Customer.GeographyKey = 1

- Thời gian thực hiện là : 0,005s
- Số lượng bản ghi là : 2

InternetSales.ProductKey

and



R*,SDD-1 để có thể cho một đánh giá về mức độ phức tạp của các
thuật toán đó và khuyến cáo trong trường hợp nào nên dùng thuật
toán nào sẽ hiệu quả.