I. Đặt vấn đề và giới thiệu.

• Quá trình chuyển đổi truy vấn cho cùng 1 kết quả như nhau.
• Có nhiều giải pháp để chuyển đổi , mỗi giải pháp lại tiêu thụ tài nguyên máy tính khác nhau .
• Vấn đề đặt ra cần lựa chọn giải pháp sao cho tiêu thụ tài nguyên là tối thiểu.

1. Mục đích của truy vấn.

• Giảm vùng nhớ trung gian.
• Giảm chi phí truyền thông giữa các trạm.
• Sử dụng ít tài nguyên.

2. Các phương pháp xử lý.

a. 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 .
• Mục đích : nhằm giảm thiểu thời gian thực tế các phép toán.

b. Phương pháp ước lượng chi phí.

• Xác định kich thước dữ liệu, thời gian thực hiện mỗi phép toán trong câu truy vấn.

II. Xử lý truy vấn.

1. Thuật toán xử lý tập trung.

a. Thuật toán INGRES :

Ý tưởng : Thuật toán tổ hợp hai giai đoạn phân rã và tối ưu hoá. Phân rã :

• 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.

Tối ưu hóa :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” (OVQP). Thuật toán:

Input: 	MRQ: câu truy vấn đa quan hệ (có n quan hệ)
Output: 	Câu truy vấn tối ưu
Begin
   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, ..., ORQm, MRQ’← MRQ
       For i←1 to m 
       Output’ ← run(ORQi) 	  {thực hiện ORQi }
             	Output ← output + output’	{trộn tất cả các kết quả lại}	
       Endfor←
             R ← CHOOSE_ VARIABLE(MRQ’) {R được chọn cho phép thế bộ}  
       For mỗi bộ t thuộc R 
             MRQ” ← thay giá trị cho t trong MRQ’
             Output’ ← INGRES-QOA(MRQ”)   {gọi đệ qui}
             Output ← output + output’	{trộn tất cả các kết quả lại}	
       End for 
    End if
End. 

b. Thuật toán R*

Ý tưởng: Sử dụng cách tiếp cận biên dịch, trong đó thực hiện việc tìm kiếm vét cạn tất cả các chiến lược khác nhau để chọn ra được một chiến lược với chi phí thấp nhất.(Strat) Thuật toán:

Begin
     for mỗi quan hệ Ri thuộc QT do
     begin
             for mỗi đường truy cập APij  tới Ri do xác định cost (APij)
             end-for
                     best _ APi ← APij với chi phí nhỏ nhất
      end-for
      for mỗi thứ tự Ri1, Ri2,…, Rin với i =1,...,n! do xây dựng chiến lược tính chi phí của  chiến lược
      end-for
                 strat ← chiến lược với chi phí nhỏ nhất
      for mỗi trạm k có chứa quan hệ có mặt 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 hóa tại trạm k}
               end-for
End.

2. Thuật toán xử lý truy vấn phân tán.

Phân rã truy vấn.

Giai đoạn này chia làm bốn bước: chuẩn hoá, phân tích, loại bỏ dư thừa và viết lại. Bước 1: Chuẩn hoá: chuyển đổi truy vấn thành một dạng chuẩn để thuận lợi cho các xử lý tiếp theo. Có 2 dạng chuẩn :

• Dạng chuẩn hội là hội của những phép toán tuyển.
• Dạng chuẩn tuyển là tuyển của những phép toán hội.

Bước 2: Phân tích:

• Mục đích: Phát hiện ra những thành phần không đúng (sai kiểu hoặc sai ngữ nghĩa) và loại bỏ chúng sớm nhất nếu có thể.
• Truy vấn sai kiểu: nếu một thuộc tính bất kỳ hoặc tên quan hệ của nó không được định nghĩa trong lược đồ tổng thể, hoặc phép toán áp dụng cho các thuộc tính sai kiểu.

Bước 3: Loại bỏ dư thừa:

• Điều kiện trong các truy vấn có thể có chứa các vị từ dư thừa.
• Một đánh giá sơ sài về một điều kiện dư thừa có thể dẫn đến lặp lại một số công việc.
• Sự dư thừa vị từ và dư thừa công việc có thể được loại bỏ bằng cách làm đơn giản hoá các điều kiện thông qua các luật luỹ đẳng sau:

Bước 4: Viết lại: Bước này được chia làm hai bước con như sau:

• Biến đổi trực tiếp truy vấn phép tính sang đại số quan hệ.
• Cấu trúc lại truy vấn đại số quan hệ để cải thiện hiệu quả thực hiện.ại số quan hệ là một cây mà nút lá biểu diễn một quan hệ trong CSDL, các nút không lá là các quan hệ trung gian được sinh ra bởi các phép toán đại số quan hệ.

Đánh giá

• Trong hệ phân tán, truy vấn thu được từ giai đoạn phân rã và định vị dữ liệu có thể được thực hiện một cách đơn giản bằng việc thêm vào các thao tác truyền thông.
• Việc hoán vị thứ tự các phép toán trong một câu truy vấn có thể cung cấp nhiều chiến lược tương đương khác nhau.
• Bài toán xác định cây truy vấn tối ưu là NP-khó. Thông thường bộ tối ưu tìm tìm một chiến lược gần tối ưu và tránh các chiến lược “tồi”.
• Đầu ra của bộ tối ưu là một lịch trình được tối ưu bao gồm truy vấn đại số được xác định trên các mảnh và các phép toán truyền thông hỗ trợ việc thực hiện truy vấn trên các trạm.
• Để chọn lựa được một chiến lược tối ưu nói chung, bộ tối ưu còn phải xác định chi phí thực hiện câu truy vấn.
• Chi phí thực hiện là tổ hợp có trọng số của chi phí truyền thông, chi phí I/O và chi phí CPU.

III. Kết luận.

Xử lý truy vấ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ệ.

Xử lý truy vấn 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 truyền dữ liệu.

Tham khảo:

2011 Principles Of Distributed Database Systems ( 3rd Edition) ( M. Tamer Özsu, Patrick Valduriez)