CHƯƠNG 4: XỬ LÝ TRUY VẤN TRONG CSDL PHÂN TÁN NỘI DUNG 4.1 Giới thiệu về xử lý truy vấn 4.2 Xử lý truy vấn trong môi trường tập trung 4.3 Xử lý truy vấn trong môi trường phân tán 4.4 Tối ưu hoá truy vấn trong CSDL phân tán MỤC ĐÍCH •Giới thiệu một bức tranh tổng quát của bộ tối ưu hóa truy vấn trong môi trường tập trung và phân tán •Trình bày các quy trình xử lý truy vấn trong hệ thống phân tán 1 4.1 GIỚI THIỆU VỀ XỬ LÝ TRUY VẤN Mục đích của xử lý truy vấn: • Giảm thiểu thời gian xử lý • Giảm vùng nhớ trung gian • Giảm chi phí truyền thông giữa các trạm. Chức năng của xử lý truy vấn: • Biến đổi một truy vấn ở mức cao thành một truy vấn tương đương ở mức thấp hơn. • Phép biến đổi này phải đạt được cả về tính đúng đắn và hiệu quả • Mỗi cách biến đổi dẫn đến việc sử dụng tài nguyên máy tính khác nhau, nên vấn đề đặt ra là lựa chọn phương án nào dùng tài nguyên ít nhất.1 GIỚI THIỆU VỀ XỬ LÝ TRUY VẤN Các phương pháp xử lý truy vấn cơ bản • Phương pháp biến đổi đại số: Đơn giản hóa câu truy vấn nhờ các phép biến đổi đại số tương đương nhằm giảm thiểu thời gian thực hiện các phép toán, phương pháp này không quan tâm đến kích thước và cấu trúc dữ liệu • Phương pháp ước lượng chi phí: Xác định kích thước dữ liệu, thời gian thực hiện mỗi phép toán trong câu truy vấn. Phương pháp này phải xác định kích thước dữ liệu và chi phí thời gian thực hiện mỗi phép toán trong câu truy vấn 3 4.2 XỬ LÝ TRUY VẤN TRONG MÔI TRƯỜNG TẬP TRUNG 4.1 So sánh xử lý truy vấn tập trung và phân tán • Tập trung: Chọn một truy vấn đại số quan hệ tốt nhất trong số tất cả các truy vấn đại số tương đương.
Các chiến lược xử lý truy vấn có thể biểu diễn trong sự mở rộng của đại số quan hệ. • Phân tán Kế thừa chiến lươc xử lý truy vấn như môi trường tập trung Còn phải quan tâm thêm Các phép toán truyền dữ liệu giữa các trạm Chọn các trạm tốt nhất để xử lý dữ liệu Cách thức và biến đổi dữ liệu 4 Tè I ¦U h o¸ tru y vÊ n Trong m«i trê ng tËp trung Sơ đồ chung Câu truy v ấn KiÓm tra ng ÷ ph¸p Tè i u ho ¸ ®¹i s è quan hÖ Truy vÊn ®ó ng ng÷ ph¸p Truy vÊn ®¹i sè quan hÖ ®· tè i u KiÓm tra s ù hîp lÖ Chän c hiÕn lîc tè i u Truy vÊn SQL hîp lÖ KÕ ho ¹ch thùc hiÖn DÞc h truy vÊn T¹o s inh m· Truy vÊn ®¹i sè quan hÖ M· cña truy vÊn 5 Tè i ư u h o¸ truy vÊ n Tro ng m«i trê ng phân tán Câu truy vấn phân tán Lược đồ tổng Phân rã truy vấn thể Truy vấn đại số trên các quan hệ phân tán Trạm Lược đồ điều Định vị dữ liệu phân mảnh khiển Truy vấn mảnh Các thống kê Tối ưu hoá toàn cục trên các mảnh Truy vấn mảnh được tối ưu với các phép toán truyền thông Các trạm Tối ưu hoá cục bộ Lược đồ địa phương địa phương Các truy vấn cục bộ đã tối ưu 6 Sơ đồ phân lớp chung cho xử lý truy vấn phân tán 4.2 XỬ LÝ TRUY VẤN TRONG MÔI TRƯỜNG TẬP TRUNG 4.2 Chiến lược tối ưu trong CSDL tập trung Hai trong số những kỹ thuật tối ưu thông dụng nhất trong các hệ thống tập trung là các thuật toán INGRES và SYSTEM R. Tại sao phải nghiên cứu xử lý truy vấn tập trung? Để hiểu được các kỹ thuật tối ưu phân tán vì ba lí do: • Thứ nhất, câu truy vấn phân tán phải được dịch thành các câu truy vấn cục bộ, và được xử lí theo phương pháp tập trung. • Thứ hai, các kỹ thuật tối ưu hoá phân tán thường là các mở rộng của kỹ thuật tập trung.
• Cuối cùng, tối ưu hoá tập trung thường đơn giản.2 XỬ LÝ TRUY VẤN TRONG MÔI TRƯỜNG TẬP TRUNG Thuật toán INGRES Ý tưởng thuật toán: Thuật toán tổ hợp hai giai đoạn phân rã và tối ưu hoá. • Đầu tiên phân rã câu truy vấn dạng phép toán quan hệ thành các phần nhỏ hơn. Câu truy vấn được phân rã thành một chuỗi các truy vấn có một quan hệ chung duy nhất • Sau đó mỗi câu truy vấn đơn quan hệ được xử lí bởi một “thể xử lý truy vấn một biến” (one variable query processor-OVQP) 8 4.2 XỬ LÝ TRUY VẤN TRONG MÔI TRƯỜNG TẬP TRUNG OVQP tối ưu hoá việc truy xuất đến một quan hệ bằng cách dựa trên vị từ phương pháp truy xuất hữu hiệu nhất đến quan hệ đó Trước tiên OVQP sẽ thực hiện các phép toán đơn ngôi và giảm thiểu kích thước của các kết quả trung gian bằng các tách (detachment) và thay thế (substitution) Kí hiệu qi-1qi để chỉ câu truy vấn q được phân rã thành hai câu truy vấn con qi-1và qi, trong đó qi-1 được thực hiện trước và kết quả sẽ được qi sử dụng.2 XỬ LÝ TRUY VẤN TRONG MÔI TRƯỜNG TẬP TRUNG Phép tách: OVQP sử dụng để tách câu truy vấn q thành các truy vấn q’q” dựa trên một quan hệ chung là kết quả của q’. Nếu câu truy vấn q được biểu diễn bằng SQL có dạng: q: SELECT R2.An) Trong đó: A1 và A’1 là các thuộc tính của quan hệ R1, P1 là vị từ có chứa các thuộc tính của các quan hệ R1, R2,.
Một câu truy vấn như thế có thể phân rã thành hai câu truy vấn con, q’ theo sau là q” qua phép tách dựa trên quan hệ chung R1 như sau: q’: SELECT R1A1 INTO R’1 FROM R1 WHERE P1(R1.A1) Trong đó R’1 là một quan hệ tạm thời chứa các thông tin cần thiết để thực hiện tiếp tục câu truy vấn: q”:SELECT R2A2,. , Rn Ví dụ minh họa: xét CSDL của một công ty máy tính NHANVIEN (E) HOSO (G) MANV TENNV CHUCVU MANV MADA NHIEMVU THOIGIAN A1 Nam Phân tích HT A1 D1 Quản lý 12 A2 Trung Lập trình viên A2 D1 Phân tích 34 A3 Đông Phân tích HT A2 D2 Phân tích 6 A4 Bắc Phân tích HT A3 D3 Kỹ thuật 12 A5 Tây Lập trình viên A3 D4 Lập trình 10 A6 Hùng Kỹ sư điện A4 D2 Quản lý 6 A7 Dũng Phân tích HT A5 D2 Quản lý 20 A8 Chiến Thiết kế DL A6 D4 Kỹ thuật 36 A7 D3 Quản lý 48 A8 D3 Lập trình 15 DUAN (J) TLUONG (S) MADA TENDA NGANSACH CHUCVU LUONG D1 CSDL 20000 Kỹ sư điện 1000 D2 CÀI ĐẶT 12000 Phân tích HT 2500 D3 BẢO TRÌ 28000 Lập trình viên 3000 D4 PHÁT 25000 Thiết kế DL 4000 11 TRIỂN 4.2 XỬ LÝ TRUY VẤN TRONG MÔI TRƯỜNG TẬP TRUNG Để minh hoạ kỹ thuật tách chúng ta sử dụng CSDL trên cho câu truy vấn sau:“Cho biết tên của các nhân viên đang làm việc trong dự án có tên CSDL” Câu truy vấn này (q1) được diễn tả bằng SQL: q1: SELECT NHANVIEN.TENNV FROM NHANVIEN, HOSO, DUAN WHERE NHANVIEN.MANV AND HOSO.MADA AND TENDA = “CSDL” Câu truy vấn q1 được tách thành q11q’, trong đó TGIAN1 là quan hệ trung gian.MADA INTO TGIAN1 FROM DUAN WHERE TENDA = “CSDL” q’: SELECT NHANVIEN.TENNV FROM NHANVIEN, HOSO, TGIAN1 WHERE NHANVIEN.MANV 12 AND HOSO.2 XỬ LÝ TRUY VẤN TRONG MÔI TRƯỜNG TẬP TRUNG Các bước tách tiếp theo cho q’ có thể tạo ra: q12: SELECT HOSO.MANV INTO TGIAN2 FROM HOSO, TGIAN1 WHERE HOSO.MADA q13: SELECT NHANVIEN.TENNV FROM NHANVIEN, TGIAN2 WHERE NHANVIEN.MANV Truy vấn q1 đã được rút gọn thành chuỗi truy vấn q11q12q13. Truy vấn q11 là loại đơn quan hệ và có thể cho thực hiện bởi OVQP. Tuy nhiên các truy vấn q12 và q13 không phải loại đơn quan hệ và cũng không thể rút gọn hơn nữa bằng phép tách.
Các câu truy vấn đa quan hệ không thể tách tiếp được nữa (chẳng hạn q12 và q13) được gọi là bất khả giản (irreducible).2 XỬ LÝ TRUY VẤN TRONG MÔI TRƯỜNG TẬP TRUNG Các truy vấn bất khả giản được biến đổi thành câu truy vấn đơn quan hệ nhờ phép thế bộ (tuple substitution). Cho câu truy vấn n-quan hệ q, các bộ của một biến được thay bằng các giá trị của chúng, tạo ra được một tập các truy vấn (n-1) biến. Phép thế bộ được tiến hành như sau: Trước tiên chọn một quan hệ trong truy vấn q để thay thế. Gọi R1 là quan hệ đó.
Thế thì với mỗi bộ t1i trong R1, các thuộc tính được tham chiếu trong q được thay bằng các giá trị thật sự trong t1i, tạo ra một câu truy vấn q’ có (n-1) quan hệ. Vì vậy số câu truy vấn q’ được sinh ra bởi phép thế bộ là card(R1). Phép thế bộ có thể tóm tắt như sau: q(R1, R2,. , Rn) được thay bởi {q’(t1i, R2, R3,.
, Rn), t1i R1} Vì thế đối với mỗi bộ thu được, câu truy vấn con được xử lý đệ quy bằng phép thế nếu nó chưa bất khả giản.2 XỬ LÝ TRUY VẤN TRONG MÔI TRƯỜNG TẬP TRUNG Ví dụ minh họa: Xét tiếp câu truy vấn q13 q13: SELECT NHANVIEN.TENNV FROM NHANVIEN, TGIAN2 WHERE NHANVIEN.MANV Quan hệ được định nghĩa bởi biến TGIAN2 chạy trên thuộc tính duy nhất MANV. Giả sử rằng nó chỉ chứa hai bộ: <E1> và <E2>. Phép thế cho TGIAN2 tạo ra hai câu truy vấn con đơn quan hệ: q131: SELECT NHANVIEN.TENNV FROM NHANVIEN WHERE NHANVIEN.MANV = “E1” q132: SELECT NHANVIEN.TENNV FROM NHANVIEN WHERE NHANVIEN.MANV = “E2” Sau đó chúng có thể được OVQP quản lý và sử dụng.2 XỬ LÝ TRUY VẤN TRONG MÔI TRƯỜNG TẬP TRUNG Nhận xét: •Thuật toán tối ưu hoá INGRES (được gọi là INGRES - QOA) sẽ xử lý đệ qui cho đến khi không còn câu truy vấn đa quan hệ nào nữa. •Thuật toán có thể được áp dụng cho các phép chọn và các phép chiếu ngay khi có thể sử dụng kỹ thuật tách.
•Kết quả của câu truy vấn đơn quan hệ được lưu trong những cấu trúc dữ liệu có khả năng tối ưu hoá những câu truy vấn sau đó (như các nối) và sẽ được OVQP sử dụng. •Các câu truy vấn bất khả giản còn lại sau phép tách sẽ được sử lý bằng phép thế bộ. •Câu truy vấn bất khả giản, được kí hiệu là MRQ’. Quan hệ nhỏ nhất với lực lượng của nó đã được biết từ kết quả của câu truy vấn trước đó sẽ được chọn để thay thế.2 XỬ LÝ TRUY VẤN TRONG MÔI TRƯỜNG TẬP TRUNG Thuật toán INGRES- QOA Input: MRQ: câu truy vấn đa quan hệ (có n quan hệ) Output: Câu truy vấn tối ưu Begin Output If n=1 then Output run(MRQ) {thực hiện câu truy vấn một quan hệ} Else {Tách MRQ thành m tr.vấn một quan hệ và một tr.vấn đa quan hệ} ORQ1, .