Luận văn thạc sĩ nghiên cứu truy vấn trong cơ sở dữ liệu phân tán và ứng dụng làm đề tài luận văn tốt nghiệp của mìnht. Phạm vi nghiên cứu của đề tài Đề tài nghiên cứu về các vấn đề cơ bản của cơ sở dữ liệu phân tán, các nguyên lý chung, các kỹ thuật, các thuật.
AMBIENT/
Chủ đề:
Nội dung Text: Tóm tắt luận văn Thạc sĩ: Truy vấn trong cơ sở dữ liệu phân tán và ứng dụng
- 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
chính Viễn thông
- 1
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 vật 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à giả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 được
đặt ra. Đó chính là tiền đề để cơ sở dữ liệu phân tán ra đời.
Khi khối lượng thông tin phải xử lý ngày càng lớn,
phong phú và đa dạng thì vấn đề đặt ra là xử lý thông tin như
thế nào để giảm chi phí đến mức tối thiểu. Một trong các giải
pháp có khả năng khả thi là phải tối ưu hóa các câu lệnh khi
truy vấn dữ liệu nên tôi chọn nghiên cứu “ Truy vấn trong
cơ sở dữ liệu phân tán và ứng dụng” làm đề tài luận văn
tốt nghiệp của mình.
2. Phạm vi nghiên cứu của đề tài
Đề tài nghiên cứu về các vấn đề cơ bản của cơ sở dữ
liệu phân tán, các nguyên lý chung, các kỹ thuật, các thuật
- 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
- Sự tương quan logic
1.2.1.2 Những ưu điểm của cơ sở dữ liệu phân tán
- Cho phép quản lý dữ liệu với nhiều mức trong suốt
- Tăng độ tin cậy và khả năng sẵn sàng
- Cải thiện hiệu năng
- Dễ dàng mở rộng
- 4
1.2.1.3 Những nhược điểm của cơ sở dữ liệu phân tán
- Tăng độ phức tạp thiết kế và cài đặt hệ thống
- 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
1.2.1.4 Các đặc trưng trong suốt của cơ sơ dữ liệu phân tán
1.2.1.4.1 Trong suốt phân tán
- Cho phép xử lý dữ liệu trên hệ cơ sở dữ liệu phân tán như đối với
cơ sở dữ liệu tập trung.
- Trong suốt phân tán thể hiện:
+ Trong suốt địa điểm
+ Trong suốt tên
+ Trong suốt bản sao
+ Trong suốt phân mảnh
1.2.1.4.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 chữa dữ liệu trên các máy trạm khác nhau.
1.2.1.4.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
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 R2 …
Rn .
- 6
1.2.2.2 Phân mảnh ngang dẫn xuất
Phân mảnh ngang dẫn xuất là sự phân mảnh quan hệ con dựa
theo cách phân mảnh của quan hệ cha mẹ.
1.2.2.3 Phân mảnh dọc
Phân mảnh dọc là sự chia một quan hệ thành các quan hệ
con, cùng với tập thuộc tính khóa: Ri = Π{ATTRI} R, trong đó ATTRi là
tập con của thuộc tính của R, cùng với khóa của R.
Tiêu chuẩn cho sự phân mảnh dọc là đúng đắn:
- Điều kiện đầy đủ
- Điều kiện xây dựng lại
- Điều kiện rời nhau
1.2.2.4 Phân mảnh hỗn hợp
Là sự kết hợp cả phân mảnh dọc và phân mảnh ngang.
1.2.2.5 Nhân bản
- Nhân bản dữ liệu đầy đủ
- Không có nhân bản dữ liệu
- Nhân bản dữ liệu từng phần
1.2.2.6 Định vị
Là quá trình gán từng mảnh, từng bản sao của phân mảnh
cho một trạm cụ thể trong hệ thống phân tán.
1.2.3 Giới thiệu một số thuật toán cơ bản trong hệ cơ sở dữ liệu
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
Output: output: Kết quả thưc hiện
Begin
Output
- 8
If n =1 then
Output run(MVQ) { Thực hiện truy vấn một biến}
Else begin {tách MVQ thành m truy vấn một biến và một
truy vấn nhiều biến }
OVQ1,…, OVQm, MVQ’ MVQ
For I 1 to m do
Begin
Output’ run(OVQi) {Thực thi OVQi}
Output output output’ {hợp tất cả các kết quả }
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
Thuật toán: R – QOA
- 9
Input: QT: Cây truy vấn với n quan hệ
Output: output : kết quả thực hiện
Begin
For mỗi quan hệ Ri QT do
Begin
For mỗi đường truy cập APij to Ri do
xác định cost(APij)
endfor
best_ APi ở Pij với chi phí tối thiểu
endfor
for mỗi order(Ri1,Ri2,…,Rim) với i = 1,2 …,n! do
begin
build strategy(…(best APi1 .. Ri2 ) .. Ri3)
………Rin ) tính toán chi phí của chiến lược
endfor
output chiến lược với chi phí tối thiểu
End.{R- QOA}
1.3 Kết luận chương
- 10
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
For mỗi OVQi có thể tách ra in MVQ do {chạy tất cả các
truy vấn một biến}
Run(OVQi)
(1)
Endfor
MVQ’ _ list REDUCE(MVQ)
{thay thế MVQ bởi n truy vấn không thể rút gọn} (2)
While n 0 do {n – số truy vấn không thể rút gọn } (3)
Begin
{Chọn truy vấn không thể rút gọn liên quan đến các
mảnh nhỏ nhất }
MVQ’ select _ query(MVQ’_list); (3.1)
{Xác định các đoạn để truyền và trạm xử lý MVQ’}
Fragmen- site- list 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
được mô tả bởi một danh sách các cặp (F,S), trong đó F là một mảnh
để truyền tới trạm xử lý S.
Bước 3.3: Truyền tất cả các mảnh tới trạm xử lý chúng.
Bước 3.4: Thực hiện MVQ’. Nếu có các truy vấn con còn
lại, thuật toán quay lại bước 3 và thực hiện bước lặp tiếp theo, ngược
lại thuật toán kết thúc.
2.2.2 Thuật toán R*
Thuật toán : R* - QOA
Input : QT : Câu truy vấn
Output : strat : Chiến lược chi phí tối thiểu
BEGIN
For mỗi quan hệ Ri QT do
begin
for mỗi đường truy nhập APij to Ri do
- 13
Xác đinh cost(APij)
endfor
best_APi APij với chi phí tối thiểu ;
endfor
For mỗi thứ tự (Ri1,Ri2,...,Rin) với i = 1,2,...,n! Do
Begin
Xây dựng chiến lược (...(best APi1 )
Ri2 Ri3)
... Rin)
;
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
END. {R* - QOA}
Thuật toán này được diễn giải như sau: Bộ tối ưu hoá phải chọn thứ
tự kết nối, đường truy cập vào mỗi mảnh thẳng (chẳng hạn chỉ mục
nhóm, quét tuần tự,...). Các quyết định này dựa trên các thống kê và
thông tin đường truy nhập
2.2.3 Thuật toán SDD -1
Thuật toán SDD – 1 – QOA
- 14
Input : QG : Đồ thị truy vấn với n quan hệ, các thống kê của mỗi
quan hệ
Output : ES : Chiến lược thực hiện
BEGIN
ES local- operations(QG);
Sửa đổi các thống kê để phản ánh kết quả của xử lý địa
phương ;
BS {Tập các phép nửa kết nối có lợi };
For mỗi phép nửa kết nối SJ trong QG do
If cost(SJ) < benefit(SJ) then
BS BS SJ;
End-if
End-for
While BS do {Chọn các phép kết nối có lợi}
Begin
SJ most_benefit(BS) {SJ: semijoin có
benefit_cost lớn nhất}
BS BS – SJ; {Loại SJ khỏi BS}
ES ES + SJ;
Sửa đổi các thống kê để phản ánh kết quả của SJ thêm vào;
BS BS – các phép nửa kết nối không có lợi;
BS BS Các phép nửa kết nối có lợi mới;
End-while
- 15
{chọn trạm thực hiện}
AS(ES) chọn trạm i mà i chứa số lượng dữ liệu lớn nhất
sau tất cả các phép toán cục bộ;
ES ES sự truyền của các quan hệ trung gian tới
AS(ES);
{Tối ưu hoá sau}
For mỗi quan hệ Ri tại AS(ES) do
For mỗi phép nửa kết nối SJ của Ri và Rj do
If cost(ES) > cost(ES – SJ) then
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á chi phí truyền tất cả dữ liệu được yêu cầu tới nó và chọn trạm có
chi phí nhỏ nhất.
Giai đoạn tối ưu hoá sau: Loại bỏ những phép kết nối trong
chiến lược thực thi chỉ ảnh hưởng đến quan hệ được lưu trữ tại trạm
thực hiện.
2.3 Kết luận chương
- Sự phân rã : Dịch một câu truy vấn được diễn đạt trong một
ngôn ngữ bậc cao kiểu SQL thành một câu truy vấn tương đương
diễn đạt trong một biến thanis của đại số quan hệ.
- Sự cục bộ hoá: Là phép biến đổi theo lược đồ sắp đặt một
câu truy vấn phân tán thành một câu truy vấn tương đương được diễn
đạt trên các mảnh.
- Việc thực hiện thao tác của câu truy vấn đã được tối ưu hoá
để thu được kết quả.
- 17
CHƯƠNG 3 : ỨNG DỤNG
3.1 Giới thiệu chương
3.2 Nội dung
3.2.1 Giới thiệu công ty TNHH HOMETECH
3.2.2 Cơ sở dữ liệu hàng hóa tập trung của công ty TNHH
HOMETECH
Table : InternetSales
Tên cột Giải thích
Kiểu dữ liệu
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 Giá trên 1 đơn vị sản phẩm
DiscountAmount Float Lượng giảm giá
ProductStandardCosst Money Giá chuẩn của sản phẩm
TotalProductCost Money Tổng giá trị của phẩm
- 18
Table : Geography
Tên cột Kiểu dữ Giải thích
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ế
Table : Product
Tên cột Kiểu dữ Giải thích
liệu
ProductKey Int Khóa chính
ProductAlternateKey Nvarchar(25) Mã sản phẩm
EnglishProductName Nvarchar(50) Tên sản phẩm
StandardCost Money Giá chuẩn
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
EnglishDescription Nvarchar(400) Ghi chú thêm
StartDate Datetime Ngày nhập
EndDate Datetime Ngày kết thúc
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
