DANH MỤC TÀI LIỆU
Luận văn: tìm kiếm trong chương trình nguồn các lệnh SQL và sau đó chuyển sang AQL để hỗ trợ tối ưu hóa vấn tin
1
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
---------------------------------------
Phm Quỳnh Điệp
THUẬT TOÁN CHUYN CÂU SQL TỪ
CHƯƠNG TRÌNH NGUỒN SANG AQL
Chuyên ngành: Khoa học máy tính
số: 60.48.01
NGƯI HƯỚNG DẪN KHOA HỌC :
PGS. TS. Lê Huy Thập
LUẬN VĂN THẠC SĨ KỸ THUẬT
HÀ NỘI - 2012
2
LỜI M ĐẦU
Câu truy vấn đã được tối ưu sẽ nâng cao hiệu quả nếu nó thỏa mãn một số
tiêu chuẩn cho trước nào đó. Một s phương pháp phân tích tối ưu hóa các câu
truy vấn dạng SQL và AQL đã được một số tác giả trong và ngi nước nghiên cứu.
Mt sthuật toán cũng đã được công bố. Tuy nhiên tất cđu dựa trên githuyết
các câu vấn tin dng SQL được lấy trực tiếp từ một chương trình nguồn hay nời
lập trình viết khi lập trình và tối ưu hóa một cách thủ công. Một vấn đề đặt ra là mt
chương trình nguồn dạng tuần tự mà trong đó nhiều lệnh SQL thể thỏa mãn
điều kiện song song a và chđược song song a và ti ưu hóa bởi phương pháp
song song tđộng. Điều đó gây nhiều bất cập trong ứng dụng. Việc tìm kiếm trong
chương trình nguồn các lệnh SQL và sau đó chuyển sang AQL đhỗ trợ tối ưua
vấn tin là mt vấn đề thời sự và cần thiết. Trong khuôn khổ của lun văn các vấn đ
sẽ lần lượt trình bày trong các chương.
Chương 1, strình bày các kiến thức cơ bn về một số phần mềm tìm kiếm,
tổng quan cơ sở dữ liệu (CSDL) phân tán, u vấn tin SQL, AQL và cây vấn tin,
quá trình tối ưu hóa và ngôn ng lập trình Java.
Chương 2, sẽ trình bày các thuật toán tìm câu vấn tin SQL, tạo câu vấn tin
AQL và cây toán tử.
Chương 3, y dựng chương trình demo tìm các câu vn tin SQL t một
chương trình nguồn rồi sau đó chuyển các câu SQL này sang câu vấn tin AQL.
3
Chương 1: TỔNG QUAN
1.1. Các phn mềm tìm kiếm cơ bản
Các phần mm tìm kiếm là “chìa khóa” quan trng để giúp bạn tìm thy
thông tin c thể mà bn cần trong vô số những dữ liệu trên mạng toàn cu.
Các công cụ tìm kiếm dựa trên chương trình tự động
Những ng cụ tìm kiếm tự động, d Google sẽ tạo ra những danh sách
của họ tđộng. Các chương trình tđộng như crawler hay spider sbắt đầu làm
việc, sau đó mọi người thể tìm kiếm thông qua những gì các chương trình t
động dò m được.
1.1.1. Google search:
1.1.2. Yahoo search
1.1.3. Một số lệnh tìm kiếm trong các ngôn ngữ lập trình bậc cao
1.2. Tổng quan CSDL phân tán
Những năm của thp k 70, máy tính đã đủ khnăng y dựng hthống
tin h sở dữ liệu. Một mặt đã hình thành phát triển các hình thuyết
cho h sở dữ liệu và mặt khác những nguồn phát trin hthống ứng dụng ngày
càng nhiều kinh nghim. Hthống thông tin nh thành trên sở kết nối các
máy tính khác nhau.
Những năm gần đây, hcơ sở dữ liệu phân tán được phát trin dựa trên cơ sở
dữ liệu và mng máy tính. Cơ sở dữ liệu phân tán gồm nhiềusở dữ liệu tích hợp
lại với nhau thông qua mạng máy tính để trao đổi dliệu, thông tin... Cơ sở dữ liệu
được tổ chức lưu trữ những vị trí khác nhau trong mng y tính và chương
trình ng dụng làm việc trên cơ sở truy cập dữ liệu ở những điểm khác nhau đó.
Vấn đề hoàn toàn mới là xây dng và cài đặt một cơ sở dữ liệu phân tán. Cần
giải quyết vấn đề xây dng cài đặt cơ sở dliệu phân tán cụ thể như vấn đề thiết
kế phân tán, thiết kế cơ sở dữ liệu...
1.2.1. Khái nim về cơ sở dữ liệu phân tán
4
1.2.2. Lợi điểm của cơ sở dữ liệu phân tán
1.3. Câu vấn tin SQL, AQL và cây vấn tin
1.3.1. Câu vấn tin SQL (Structured Query Language)
Đây một loại ngôn ngcon dliệu quan hệ được xác nhn lầ rất mạnh.
Phép toán cơ bn trong SQL là phép ánh xạ, được mô tả về pháp như khối
SELECT - FROM - WHERE.
Mệnh đề SELECT nghĩa là chọn các thuộc nh ra, hay còn gi là thuộc tính
kết quả, nếu không chỉ ra thuộc nh thì dùng du * có nghĩa là tt ccác thuộc nh
của quan h đang được ch ra sau mnh đề FROM. Mệnh đề FROM đchỉ ra quan
hệ cn cho việc xử lý. Sau mệnh đWHERE là mt biểu thức điều kiện lọc dliu
(hay còn gọi là biểu thức logic).
1.3.2. Ngôn ng truy vấn đại số (AQL)
Gọi r là quan h trên tp thuộc nh R={ A1,….,An}. Ta luôn githiết rằng
quan hệ r là tập hữu hạn các bộ. Đối với các phép hợp ( ký hiệu ) phép giao (ký
hiu ), phép tr(ký hiệu -) hai quan hệ tham gia phải kh hợp
1.3.2.1. Phép hợp: hiu:
Hp ca hai quan h r s ký hiu là r s là tp các b hp thuc r hoc
thuc s hoc thuc r ln thuc s:
r s = { t: t r hoc t s hoc t r và t s }
1.3.2.2. Phép giao: Ký hiu:
Giao ca hai quan hệ r và s ký hiệu là rs là tp các bộ phải vừa thuộc r phải
vừa thuộc s:
r s = {t: t r vàt s}
1.3.2. 3. Phép trừ: hiu: -
1.3.2.5. Phép chiếu (Projection)
1.3.2.6. Phép chn (Selection)
5
1.3.2.7. Phép kết nối (Join)
1.3.2.8. Phép chia
1.3.2.9. Các ví d về tìm kiếm bằng đại số qua h
1.3.3. Cây vn tin
y vấn tin làm nhiệm vụ giải thích phương án thi hành một câu SQL: Cho
biết thứ tự thực hin mỗi phép toán, phương pháp tính toán mỗi toán t. Mi t
củay là mt hay nhiều phép toán đại số quan hệ, mỗi nút lá là một quan hệ cơ sở.
Phn ghi ctrên mỗi nút mô tả cách thức thực hiện toán tử gì trên đó..
1.4. Sắp sếp lại phép nối và viết lại câu vấn tin
1.4.1. Sắp sếp lại phép nối
1.4.2. Viết lại câu vấn tin
1.5. Quá trình tối ưu hóa
Ti ưu a vấn tin phân n là phương pháp lựa chọn phương án thực hiện
câu vn tin (QEP Query Executtion Plan) phân n tt nhất theo nghĩa chi phí
thp nhất trong số các phương án có khả năng được thực hiện bởi th vấn tin.
Chi phí thực hiện được diễn tả bởi hàm chi phí, thường được xem là hàm
mục tiêu. Nó bao gồm chi phí xuất nhập, chi phí xử lý tại các CPU và chi phí truyền
thông tin. Một đơn giản h điển hình của các thtối ưu h vấn tin phân tán ban
đu là b qua chi phí xlý cục bộ (chi phí xut nhập và chi phí CPU) bằng cách giả
thiết rằng chi phí truyền dữ liệu chiếm ưu thế. Dữ liệu vào của thể tối ưu hóa vấn tin
các s liệu thống kê của các mnh và các công thức đánh giá lực lượng của các
quan htrung gian được tạo ra. Trong chương này chúng ta tập trung chủ yếu vào
vấn đsắp tht các phép nối trong câu vấn tin phân n vì: Phép ni thường là
phép toán giảm dữ liệu trung gian, và các câu vn tin ,chứa nối, chọn và chiếu
thưng là loại vấn tin hay gặp nht. Hơn nữa chúng ta ddàng tổng quát a thuật
toán cơ bản này cho các câu vấn tin có các phép toán hai ngôi như phép hợp.
1.6. Giới thiệu về ngôn ngJava
1.6.1. Khái nim
6
Java c như “Gia-va”) mt ngôn ngữ lập trình dạng lập trình hướng đối
ợng (OOP). Khác với phần lớn ngôn ngữ lập trình thông thường, thay vì biên dịch
mã ngun thành mã máy hoặc thông dịch mã nguồn khi chạy, Java được thiết kế đ
bn dịch mã nguồn thành bytecode, bytecode sau đó sđược môi trường thực thi
(runtime environment) chy. Bằng cách này, Java thưng chạy nhanh hơn những
ngôn ngữ lập trình thông dịch khác n Python, Perl, PHP,…
pháp Java được vay ợn nhiều tC & C++ nhưng có pháp ớng
đối tượng đơn giản hơn và ít tính năng xử lý cấp thp hơn.
1.6.2. Lịch sử hình thành ngôn ngữ Java
1.6.3. Một s đặc điểm nổi bật của ngôn ngữ lập trình Java
1.6.3.2 Thông dịch:
1.6.3.3 Độc lập nền:
1.6.3.4 ớng đối tượng:
1.6.3.5 Đa nhiệm đa luồng (MultiTasking Multithreading):
1.6.3.5 Kh chuyển (portable):
1.6.3.6 Htrợ mạnh cho việc phát triển ứng dụng:
1.7. Kết luận chương
Chương 1 trìnhy những kiến thức cơ bản về cớ sở dữ liệu phân tán, câu
vấn tin SQL, câu vn tin AQL và cây vấn tin, sắp sếp lại phép nối và viết lại câu
vấn tin, quá trình ti ưu hóa và ngôn ngữ lập trình Java.
Trên đây là cơ sở lý thuyết nn tảng cho qua trình tối ưu hóa vấn tin. Chương
2 sẽ trình bày các thuật toán tìm câu vấn tin SQL từ chương trình nguồn, chuyển
câu vấn tin SQL sang câu vấn tin AQL và thuật toán vẽ cây toán tử.
thông tin tài liệu
Câu truy vấn đã được tối ưu sẽ nâng cao hiệu quả nếu nó thỏa mãn một số tiêu chuẩn cho trước nào đó. Một số phương pháp phân tích và tối ưu hóa các câu truy vấn dạng SQL và AQL đã được một số tác giả trong và ngoài nước nghiên cứu. Một số thuật toán cũng đã được công bố. Tuy nhiên tất cả đều dựa trên giả thuyết các câu vấn tin dạng SQL được lấy trực tiếp từ một chương trình nguồn hay người lập trình viết khi lập trình và tối ưu hóa một cách thủ công. Một vấn đề đặt ra là một chương trình nguồn dạng tuần tự mà trong đó có nhiều lệnh SQL có thể thỏa mãn điều kiện song song hóa và chỉ được song song hóa và tối ưu hóa bởi phương pháp song song tự động. Điều đó gây nhiều bất cập trong ứng dụng. Việc tìm kiếm trong chương trình nguồn các lệnh SQL và sau đó chuyển sang AQL để hỗ trợ tối ưu hóa vấn tin là một vấn đề thời sự và cần thiết.
Mở rộng để xem thêm
tài liệu giúp tôi
Nếu bạn không tìm thấy tài liệu mình cần có thể gửi yêu cầu ở đây để chúng tôi tìm giúp bạn!
xem nhiều trong tuần
yêu cầu tài liệu
Giúp bạn tìm tài liệu chưa có

LÝ THUYẾT TOÁN


×