Bài giảng Cơ sơ dữ liệu phân tán: Phần 2 - ĐH Sư phạm kỹ thuật Nam Định

Tiếp nội dung phần 1, Bài giảng Cơ sơ dữ liệu phân tán: Phần 2 cung cấp cho người học những kiến thức như: Biến đổi truy vấn toàn cục thành các truy vấn mảnh; Tối ưu hóa các chiến lược truy xuất. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Cơ sơ dữ liệu phân tán: Phần 2 - ĐH Sư phạm kỹ thuật Nam Định Tập bài giảng Cơ sở dữ liệu phân tán Chương 4 BIẾN ĐỔI CÁC TRUY VẤN TOÀN CỤC THÀNH CÁC TRUY VẤN MẢNH Một thao tác truy xuất trong một ứng dụng có thể được biểu diễn như là một truyvấn tham chiếu đến các quan hệ toàn cục. DDBMS phải biến đổi truy vấn này thànhcác truy vấn đơn giản hơn mà chúng chỉ tham chiếu đến các mảnh. Chương này giảiquyết phép biến đổi này. Có nhiều cách khác nhau để biến đổi một truy vấn trên các quan hệ toàn cục đượcgọi là truy vấn toàn cục (global query) thành các truy vấn trên các mảnh được gọi làtruy vấn mảnh (fragment query). Các biến đổi khác nhau này tạo ra các truy vấn mảnhtương đương theo nghĩa chúng tạo ra cùng kết quả. Vì lí do này, chương này cũng giảiquyết các phép biến đổi tương đương (equivalence transformation), nghĩa là các quytắc có thể được áp dụng cho một truy vấn để viết truy vấn này thành một biểu thứctương đương. Các quy tắc tương đương được sử dụng để đơn giản hóa biểu thức truy vấn (queryexpression). Ví dụ xác định các biểu thức con chung và các phép toán được “phân tán”cho các mảnh. Tuy nhiên, điều nhấn mạnh trong chương này là tính đầy đủ(completeness) và tính đúng đắn (correctness) của phép biến đổi. Mục tiêu của chúngta là đưa ra một tập hợp các quy tắc biến đổi tương đương và bao quát tất cả các khíacạnh liên quan đến các phép biến đổi truy vấn. Các nội dung chính trong chương này: - Các kỹ thuật được sử dụng trong các hệ thống tập trung để biến đổi truy vấn.Trước tiên, chúng ta đưa ra cách biểu diễn truy vấn bằng cách sử dụng một cây truyvấn (query tree). Sau đó chúng ta đưa ra một cách tiếp cận về ngữ nghĩa cho các phépbiến đổi tương đương và cuối cùng cho thấy cách biến đổi một cây truy vấn thành mộtđồ thị truy vấn (query graph) để xác định các biểu thức con chung trong một truy vấn.Ở đây, chúng ta đưa ra nhiều nhắc nhở này bởi vì nó liên hệ chặt chẽ với những gì đitheo sau. Hơn nữa, các khía cạnh này trong các CSDL phân tán càng quan trọng hơnso với trong các CSDL tập trung và phép biến đổi truy vấn được đưa vào trong cácmôi trường phân tán. Các truy vấn toàn cục được biến đổi thế nào thành các truy vấn mảnh. Chúng tanêu ra một ánh xạ chuẩn tắc (canomical mapping) và cho thấy ánh xạ chuẩn tắc làđúng đắn. Sau đó, chúng ta sử dụng các phép biến đổi tương đương để biến đổi biểuthức chuẩn tắc (canomical mapping) của truy vấn. Cơ sở của các phép biến đổi này làáp dụng các phép toán đại số (algebraic operation). Chẳng hạn phép chiếu và phép 175 Tập bài giảng Cơ sở dữ liệu phân tánchọn, để làm giảm kích thước của các toán hạng của chúng càng nhiều càng tốt trênmỗi mảnh trước khi truyền dữ liệu giữa các nơi. Các truy vấn có liên quan đến cách đánh giá của việc gom nhóm từng phần: mệnhđề GROUP BY của lệnh SELECT và các hàm kết hợp (aggregate function). Chúng tamở rộng đại số quan hệ (relational algebra) để bao quát các vấn đề này, và sau đó nêura một số phép biến đổi tương đương áp dụng cho các phép toán mới. Cơ sở của cácphép toán này là phân tán việc xử lý đến các mảnh. Các truy vấn tham số (parametric query), nghĩa là các truy vấn này có chứa cácđiều kiện chọn bao gồm các tham số mà giá trị sẽ được xác định ở thời gian thực hiện.Các truy vấn là các thao tác truy xuất cơ bản tiêu biểu trong các ứng dụng tham số(parametric application) như được nêu ra trong chương 2. Chúng ta nêu ra các biệnpháp biến đổi tương đương có thể được sử dụng như thế nào để cải tiến tính hiệu quảcủa chúng.4.1. Các phép biến đổi tương đương dùng cho các truy vấn Một truy vấn quan hệ (relational query) có thể được biểu diễn bằng cách sử dụngcác ngôn ngữ khác nhau. Ở đây, chúng ra sử dụng đại số quan hệ và ngôn ngữ SQLcho mục đích này. Hầu hết các truy vấn SQL đều có thể đựơc biến đổi thành các biểuthức đại số quan hệ tương đương và ngược lại. Do đó, bất kỳ các ngôn ngữ nêu trên cóthể được sử dụng để biểu diễn ngữ nghĩa của truy vấn. Tuy nhiên, chúng ta có thế diễndịch một biểu thức quan hệ đại số (expression of relational algebra) không chỉ là sựđặc tả ngữ nghĩa của một truy vấn, mà còn là sự đặc tả của một chuỗi các phép toán)sequence of operations). Từ quan điểm này, hai biểu thức có cùng ngữ nghĩa có thể môtả hai chuỗi phép toán khác nhau. Ví dụ 4.1:  MANV, MAQL  MAP=1 (NV) và  MAP=1  MANV, MAQL (NV) là các biểu thức tương đương nhưng định nghĩa hai chuỗi phép toán khác nhau. Trong chương này, vì chúng ta quan tâm đến thứ tự thực hiện của các phép toán,bắt đầu từ việc sử dụng các biểu thức đại số quan hệ ban đầu và phân tích các phépbiến đổi tương đương của chúng.4.1.1. Cây toán tử của một truy vấn ...