zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ liệu

Thuật toán tối ưu hóa truy vấn trên cơ sở dữ liệu quan hệ

Chia sẻ: ViJakarta2711 ViJakarta2711 | Ngày: | Loại File: PDF | Số trang:6

Báo xấu

229
lượt xem 16
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong bài viết này tác giả tập trung thảo luận một phương pháp tối ưu hóa câu truy vấn bằng kỹ thuật heuristic nhằm nâng cao tốc độ truy xuất dữ liệu, giảm số bộ dữ liệu thừa, không gian lưu trữ dữ liệu trung gian trong bộ nhớ khi thực hiện một cây truy vấn.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Thuật toán tối ưu hóa truy vấn trên cơ sở dữ liệu quan hệ

Thông báo Khoa học và Công nghệ* Số 1-2013 126 THUẬT TOÁN TỐI ƯU HÓA TRUY VẤN TRÊN CƠ SỞ DỮ LIỆU QUAN HỆ ThS. Trần Thái Sơn Trung tâm Ngoại ngữ - Tin học, trường Đại học Xây dựng Miền trung Tóm tắt: Hầu hết tất cả các hệ quả trị cơ sở dữ liệu đều dùng ngôn ngữ truy vấn có cấu trúc SQL (Structure Query Language) để truy xuất dữ liệu, việc lựa chọn một biểu thức đại số quan hệ để thực thi một câu truy vấn là vấn đề cần thiết. Trong bài báo này tác giả tập trung thảo luận một phương pháp tối ưu hóa câu truy vấn bằng kỹ thuật heuristic nhằm nâng cao tốc độ truy xuất dữ liệu, giảm số bộ dữ liệu thừa, không gian lưu trữ dữ liệu trung gian trong bộ nhớ khi thực hiện một cây truy vấn Từ khóa: Truy vấn SQL, biểu thức đại số quan hệ, tối ưu hóa truy vấn. 1. Chuyển câu truy vấn SQL sang đại số rộng là: MAX HSLuong(SoPhong = quan hệ “KT05”(NHANVIEN)) SQL (Structure Query Language) là Trong đó  là phép kết hợp hàm của các ngôn ngữ truy vấn được sử dụng trong hầu hàm: SUM, AVERAGE, MAX, MIN, hết các hệ quản trị cơ sở dữ liệu. Quá trình COUNT… thực thi một câu truy vấn SQL, đầu tiên câu Khối truy vấn bên ngoài SELECT truy vấn được chuyển đổi sang một biểu HoLot, Ten, DiaChi FROM thức đại số quan hệ tương đương được biểu NHANVIEN WHERE được chuyển sang biểu diễn dưới dạng cấu trúc cây truy vấn, sau đó thức đại số quan hệ: tối ưu hóa. HoLot, Ten, DiaChi(HSLuog > Ví dụ 1: Xét câu truy vấn SQL trên c(NHANVIEN)), với C là kết quả trả về của lược đồ quan hệ NHANVIEN như sau: khối truy vấn bên trong MAX HSLuong(SoPhong NHANVIEN(MaNV, HoLot, Ten, = “KT05”(NHANVIEN)) NgaySinh, GioiTinh, Chucvu, DiaChi, Như vậy việc tối ưu hóa truy vấn là quá HSLuong, SoPhong) trình lựa chọn một biểu thức đại số cho câu SELECT HoLot, Ten, DiaChi truy vấn sao cho tốc độ truy xuất nhanh nhất FROM NHANVIEN và không dư thừa thông tin không cần thiết. WHERE HSLuong > ( SELECT 2. Tối ưu hóa câu truy vấn bằng phương MAX(HSLuong) pháp heuristic FROM Bài báo này tập trung thảo luận một kĩ NHANVIEN thuật tối ưu hóa câu truy vấn áp dụng các qui WHERE SoPhong = “KT05”); tắc heuristic để thay đổi quá trình thực thiện biểu thức đại số quan hệ bên trong của một Khối truy vấn bên trong SELECT truy vấn. Thông thường, ta sử dụng hình MAX(HSLuong) FROM NHANVIEN thức một cây truy vấn hoặc một cấu trúc dữ WHERE SoPhong = “KT05”) có thể được liệu đồ thị truy vấn để cải tiến quá trình tối chuyển sang biểu thức đại số quan hệ mở ưu. Từ một truy vấn mức cao đầu tiên tạo ra
Thông báo Khoa học và Công nghệ* Số 1-2013 127 các biểu thức đại số quan hệ, sau đó được tối SELECT P.SoDuAn, P.SoPhong, ưu theo các qui tắc heuristic. E.Ten, E.DiaChi, E.NgaySinh FROM DU AN AS P, PHONG 2.1. Cây truy vấn và đồ thị truy vấn BAN AS D, NHAN VIEN AS E Một cây truy vấn là một cấu trúc dữ liệu WHERE P.SoPhong = D.SoPBan AND dạng cây tương ứng với một biểu thức đại số D.MaQly = E. MaNV AND P.DiaChiDuAn quan hệ. Các quan hệ đầu vào của câu truy =”Stafford” ; vấn được biểu diễn là các nút lá của cây, các Hình 1(a) biểu diễn cây truy vấn của phép toán đại số quan hệ là các nút bên trong. truy vấn Q1, có ba quan hệ DU AN, Quá trình thực hiện cây truy vấn bao gồm PHONG BAN và NHAN VIEN được thể việc thực hiện một nút bên trong mỗi lần thực hiện bởi các nút lá P, D và E. Các phép đại hiện các toán hạng của biểu thức quan hệ, sau số quan hệ của biểu thức được biểu diễn bởi đó thay thế nút bên trong đó bởi quan hệ kết các nút bên trong cây. Khi cây truy vấn này quả của phép toán. Quá trình thực hiện kết được thực hiện, nút (1) phải bắt đầu thực thúc khi nút gốc được thực hiện và tạo ra hiện trước nút (2) bởi vì một số bộ kết quả quan hệ kết quả cho câu truy vấn. của phép (1) phải sẵn sàng trước khi chúng Ví dụ 2: Xét lược đồ cơ sở dữ liệu ta có thể bắt đầu thực hiện phép (2). Tương quan hệ như sau: tự, nút (2) phải bắt đầu thực hiện và tạo ra NHAN VIEN(MaNV, HoLot, Ten, các kết quả trước khi nút (3) có thể bắt đầu Ngaysinh, GioiTinh, ChucVu, DiaChi, thực hiện, … HSLuong, Sophong) PHONG BAN(SoPBan, TenPhongBan, DienThoai, MaQly, NgayBatDauQL) DIA CHI PBAN( SoPBan , Diachi,) DU AN( SoDuAn, TenDaAn, DiaChiDuAn, SoPhong) THAM GIA(SNV, SDA, SoNgayCong) THAN NHAN(MaNV, HoTenTN, Phai, NgaySinhTN, MoiQuanHe) Với truy vấn Q1: Cho biết số dự án, số phòng ban, tên, địa chỉ và ngày sinh người Hình 1(a): Cây truy vấn tương ứng với biểu quản lí phòng ban của mọi dự án nằm ở thức đại số quan hệ “Stafford”. Truy vấn Q1 tương ứng với biểu thức đại số quan hệ: SoDuAn, Sophong, Ten, DiaChi, NgaySinh(((DiaChiDuAn=’Stafford’ (DU AN)) Sophong=SoPBan (PHONG BAN)) MaQly = MaNV( NHAN VIEN)) Và tương ứng với câu lệnh SQL như sau: Hình 1(b): Cây truy vấn ban đầu ứng với SQL.
Thông báo Khoa học và Công nghệ* Số 1-2013 128 WHERE TenDuAn = ‘Aquarius’AND SoDuAn = SDA AND SNV = MaMV AND NgaySinh > #31/12/1977#; Các bước chuyển đổi một cây truy vấn trong suốt quá trình tối ưu hóa bằng cách sử dụng heuristic. Hình 1(c): Đồ thị truy vấn của Q1 Sự biểu diễn bằng đồ thị truy vấn không cho biết thứ tự thực hiện trên các phép toán, nó chỉ gồm một đồ thị đơn tương ứng với mỗi truy vấn. Một số kĩ thuật tối ưu hoá đã dựa vào các đồ thị truy vấn, nhưng hầu hết chưa đưa ra thứ tự thực hiện các phép toán trên cây, trong khi đó việc tối ưu hoá câu truy vấn cần phải chỉ ra thứ tự thực hiện của các phép. Hình 2 (a): Cây truy vấn ban đầu ứng 2.2. Tối ưu hoá cây truy vấn bằng với SQL. heuristic Thông thường, một câu truy vấn có thể được biểu diễn sang nhiều biểu thức đại số quan hệ khác nhau. Phân tích câu truy vấn sẽ tạo ra một cây truy vấn ban đầu chuẩn ứng với truy vấn SQL mà không sử dụng bất cứ sự tối ưu hoá nào. Việc tối ưu hoá bao gồm các qui tắc tương đương giữa các biểu thức đại số quan hệ mà có thể được áp dụng cho cây truy vấn Hình 2 (b): Chuyển các phép chọn ban đầu. Tối ưu hóa câu truy vấn bằng các xuống dưới cây truy vấn. qui tắc heuristic chính là sử dụng các biểu thức tương đương này để chuyển cây truy vấn ban đầu thành cây truy vấn cuối cùng đã tối ưu. Ví dụ 3: Xét truy vấn Q2: Tìm tên của tất cả các nhân viên sinh sau 1957, làm việc trong dự án có tên là ‘Aquarius’. Truy vấn này có thể viết lại bằng SQL như sau: SELECT Ten Hình 2 (c): Ưu tiên áp dụng các phép FROM NHAN VIEN, THAM GIA , DU chọn có giới hạn hơn. AN
Thông báo Khoa học và Công nghệ* Số 1-2013 129 dự án là một thuộc tính khoá của quan hệ DU AN, vì vậy phép chọn trên quan hệ DU AN sẽ lấy một bản ghi duy nhất. Chúng ta có thể cải tiến hơn nữa cây truy vấn bằng cách thay thế bất cứ phép tích Đề các nào mà theo sau là một điều kiện nối với một phép nối, như đã chỉ ra trong hình 2(d). Một sự cải tiến khác là chỉ giữ lại các thuộc tính cần cho các phép theo sau trong Hình 2 (d): Thay thế tích Đề Các và các quan hệ trung gian, ví dụ sử dụng các phép chọn bằng các phép nối. phép chiếu () trước trong cây truy vấn như đã chỉ ra trong hình 2(e). Điều này làm giảm các thuộc tính của các quan hệ trung gian, ngược lại các phép chọn làm giảm các bộ cần truy xuất. Có nhiều qui tắc để chuyển đổi các phép toán đại số quan hệ thành các biểu thức tương đương. Ở đây chúng ta quan tâm đến ý nghĩa của các phép toán và các quan hệ kết quả. Vì vậy, nếu hai quan hệ có cùng tập thuộc tính theo một thứ tự khác nhau nhưng Hình 2(e): Chuyển các phép chiếu xuống hai quan hệ trình bày cùng lượng thông tin dưới cây truy vấn. thì chúng ta xem đó là các quan hệ tương Cây truy vấn ban đầu đối với Q2 được đương. Phần này chúng ta giới thiệu một số chỉ ra trong hình 1(a). Quá trình thực hiện qui tắc chuyển đổi có ích trong việc tối ưu cây truy vấn này đầu tiên sẽ tạo ra một tập hóa câu truy. hợp các bộ dữ liệu rất lớn bao gồm tích Đề 1. Gộp dãy phép chọn:  C AND C2 AND …AND 1 các của các bộ dữ liệu đầu vào NHAN Cn(R)   C1 (  C2 (...( cn ( R ))...)) VIEN, THAM GIA và DU AN. Tuy nhiên truy vấn này chỉ cần một bản ghi từ quan hệ 2. Tính giao hoán của phép chọn: DU AN đối với tên dự án là ‘Aquarius’ và  C1 ( C2 ( R ))   C2 ( C1 ( R )) chỉ các bản ghi của NHAN VIEN có ngày 3. Gộp dãy phép chiếu: sinh sau 31/12/1977. Hình 2(b) chỉ ra một  List1(  List2(…(  Listn(R))…))   List1(R) cây truy vấn cải tiến mà đầu tiên là áp dụng 4. Tính giao hoán của phép chọn với phép các phép chọn để giảm số bộ xuất hiện trong chiếu: Nếu điều kiện chọn C chỉ bao gồm tích Đề Các. các thuộc tính A1, …,An trong danh sách Một sự cải tiến nữa đã đạt được là phép chiếu thì hai phép đó có thể giao hoán chuyển vị trí của các quan hệ NHAN VIEN với nhau: và DU AN trong cây, như đã chỉ ra trong  A1 , A2 ,..., An ( c ( R ))   c ( A1 , A2 ,..., An ( R )) hình 2(c). Điều này sử dụng thông tin mà số
Thông báo Khoa học và Công nghệ* Số 1-2013 130 5. Tính giao hoán của phép nối / tích Đề Các. tính giao hoán nhưng phép - (phép trừ) thì Phép cũng như phép  đều có tính giao không có tính giao hoán. hoán: R c S  S c R ; R  S  S  R 9. Tính kết hợp của các phép toán , ,  6. Tính giao hoán của phép chọn và phép nối và  là: (R  S)  T  R  (S  T) (hoặc tích Đề Các): Nếu tất cả các thuộc 10. Tính giao hoán của phép chọn với các tính trong điều kiện chọn C chỉ bao gồm các phép toán tập hợp: Phép  giao hoán với , thuộc tính của một trong hai quan hệ của  và – là:  C (R  S)  (  C (R))  (  C (S)) phép thì ta có:  C (R S)  (  C (R)) S 11. Tính giao hoán của phép chiếu với phép Như một sự lựa chọn, nếu điều kiện hợp: L(R  S)  (L(R))  (L(S)) chọn C có thể được viết lại là (c1 AND c2), ở 12. Chuyển một dãy các phép chọn, tích Đề đây c1 chỉ bao gồm các thuộc tính của R và Các (,) thành phép nối : Nếu điều kiện điều kiện c2 chỉ bao gồm các thuộc tính của C của một phép  mà theo sau là một phép  S, ta có:  C (R S)  (  C 1 (R)) (  C 2 (S)) tương ứng với một điều kiện nối, có thể 7. Tính giao hoán của phép chiếu và phép chuyển dãy (,) thành một phép như sau: nối (hoặc tích Đề Các: Giả sử rằng danh  C (R  S)  (R c S) sách phép chiếu là L ={A1, ..., An , B1, ..., Từ các qui tắc trên ta có thuật toán tối Bm}, ở đây A1, ..., An là các thuộc tính của ưu hóa truy vấn bằng phương pháp heuristic R và B1, ..., Bm là các thuộc tính của S. Nếu thực hiện như sau: điều kiện nối C chỉ bao gồm các thuộc tính Bước 1: Sử dụng qui tắc 1, phân rã bất cứ phép chọn nào có điều kiện hội thành một trong L thì ta có: L(R c S)  (A1, ..., An(R)) dãy các phép chọn, chuyển các phép chọn c (B1, ..., Bm(S)) xuống các nhánh khác của cây. Nếu điều kiện nối C chứa các thuộc Bước 2: Sử dụng qui tắc 2, 4, 6 và 10 tính không thuộc L thì các thuộc tính này tức là tính giao hoán của phép chọn với các phải được thêm vào danh sách phép chiếu và phép khác, chuyển mỗi phép chọn ở trên một phép chiếu cuối cùng cũng được thêm xuống phía dưới cây truy vấn khi có thể. vào. Ví dụ, nếu các thuộc tính An+1 , ..., Bước 3: Sử dụng qui tắc 5 và 9 chính An+k của R và Bm+1, ..., Bm+p của S được là tính giao hoán và kết hợp của các phép bao gồm trong điều kiện nối C nhưng không toán hai ngôi. Sắp xếp lại các nút lá, ưu tiên thuộc danh sách các thuộc tính chiếu L, thì các quan hệ tương ứng với phép chọn giới ta có: L(R c S)  L((A1, ..., An,An+1, ..., hạn nhất, phép đó tạo ra một quan hệ với số bộ ít nhất hoặc là quan hệ với kích thước nhỏ An+k(R)) c (B1, ..., Bm,Am+1, ..., Am+p(S))) nhất. Đối với phép  không có điều kiện C Bước 4: Sử dụng qui tắc 12, kết hợp nên qui tắc chuyển đổi đầu tiên luôn áp dụng một phép tích Đề Các với một phép chọn được bằng cách thay c bởi  . thành một phép nối, nếu điều kiện của phép 8. Tính giao hoán của các phép toán tập chọn tương ứng với điều kiện nối. hợp: Các phép tập hợp như  và  là có Bước 5: Sử dụng qui tắc 3, 4, 7, và 11 đó chính là dãy phép chiếu và tính giao hoán
Thông báo Khoa học và Công nghệ* Số 1-2013 131 của phép chiếu với các phép khác. Phân rã sắp xếp lại các nút lá của cây nhằm loại bỏ và chuyển các danh sách thuộc tính chiếu các tích Đề Các và điều chỉnh phần còn lại xuống phía dưới cây truy vấn đến mức có của cây một cách thích hợp. thể bằng cách tạo ra các phép chiếu mới khi 3. Kết luận cần thiết. Chỉ các thuộc tính cần trong kết Bài báo này đã đưa ra một cái nhìn quả truy vấn và trong các phép toán tiếp theo tổng quan về các kỹ thuật được sử dụng bởi trong cây truy vấn nên được giữ lại sau mỗi các hệ quản trị cơ sở dữ liêu trong việc xử lý phép chiếu. và tối ưu hóa các truy vấn mức cao. Phương Bước 6: Nhận ra các cây con trình bày pháp heuristic để tối ưu hóa câu truy vấn, sử các nhóm các phép toán có thể thực hiện dụng các quy tắc heuristic và các kỹ thuật bằng một thuật toán đơn. đại số để cải tiến hiệu quả quá trình hiện truy Heuristic chính là áp dụng các phép vấn. Thông qua đó chúng ta cũng chỉ ra rằng toán làm giảm kích thước của các kết quả một cây truy vấn thể hiện biểu thức đại số trung gian. Điều này bao gồm việc thực hiện quan hệ có thể được tối ưu hóa dựa theo các các phép chọn và phép chiếu trước có thể để qui tắc heuristic bằng cách tổ chức lại các giảm số bộ và giảm số thuộc tính. Thêm vào nút của cây và chuyển nó thành cây truy vấn đó, các phép chọn giới hạn nhất hoặc là các tương đương khác hiệu quả hơn để xử lý. phép đó tạo ra một quan hệ với số bộ ít nhất Các quy tắc chuyển đổi giữ vững tính tương hoặc là quan hệ với kích thước nhỏ nhất nên đương có thể được áp dụng cho một cây truy được thực hiện trước các toán tử tương tự vấn và sau đó giới thiệu các kế hoạch thực khác. Điều này được thực hiện bằng cách hiện truy vấn đối với các truy vấn SQL. TÀI LIỆU THAM KHẢO [1] PGS.TS, Vũ Đức Thi. 1997. “Cơ sở dữ liệu – Kiến thức và thực hành”. Nxb Khoa học Thống kê. [2] Trần Nguyên Phong. 2005. “Giáo trình thực hành SQL”, ĐHKH Huế. [3] Elmasri & Navathe. 2007. “Fundamentals of Database Systems”. [4] Ramakrishnan, R. and Gehrke. 2003. “Database Management Systems”, Third Edition, McGraw Hill.

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.