1. Trang Chủ
  2. Cơ sở dữ liệu
  3. 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

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! 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 truy vấ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ành các truy vấn đơ

Thể loại Tài liệu miễn phí Cơ sở dữ liệu

Số trang 119

Ngày tạo 10/2/2021 12:26:05 PM +00:00

Loại tệp PDF

Kích thước 2.18 M

Tên tệp

Tải Bài giảng Cơ sơ dữ liệu phân tán: Phần 2 - ĐH Sư p... (.pdf)

Xem mẫu

  1. 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 truy vấ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ành cá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ải quyế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 đƣợc gọ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ảnh tƣơ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ải quyết các phép biến đổi tƣơng đƣơng (equivalence transformation), nghĩa là các quy tắ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ức tƣơ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 (query expression). 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úng ta 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ía cạ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 truy vấ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ép biế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ì đi theo 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ơn so với trong các CSDL tập trung và phép biến đổi truy vấn đƣợc đƣa vào trong các mô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 ta nê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ểu thứ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
  2. Tập bài giảng Cơ sở dữ liệu phân tán chọ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ên mỗ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 ta mở rộng đại số quan hệ (relational algebra) để bao quát các vấn đề này, và sau đó nêu ra 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ác phé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ện phá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ụng các ngôn ngữ khác nhau. Ở đây, chúng ra sử dụng đại số quan hệ và ngôn ngữ SQL cho 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ểu thứ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ễn dị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ép biến đổi tƣơng đƣơng của chúng. 4.1.1. Cây toán tử của một truy vấn 1) Mục đích: - Dùng để biểu diễn các truy vấn - Giúp theo dõi các thao tác trên biểu thức - Xác định một thứ tự bộ phận mà trong đó các phép toán phải đƣợc thực hiện cho ra kết quả của truy vấn. 2) Cấu tạo cây: 176
  3. Tập bài giảng Cơ sở dữ liệu phân tán - Nút lá: chứa các quan hệ toàn cục - Các nút trung gian và nút gốc: biểu diễn + phép toán một ngôi (unary operation) + phép toán hai ngôi (binary operation) Ví dụ 4.2: Xét hệ thống quản lý kinh doanh của một công ty trong ví dụ 2.13 và có một ứng dụng: Đƣa ra mã của nhà cung cấp đã cung cấp hàng mà có địa chỉ ở Nam Định. Truy vấn Q1 tƣơng ứng với biểu thức đại số quan hệ: Q1:  MANCC (  DC= “Nam Định” (NCC >< MANCC = MANCC KD)) Cây toán tử của truy vấn Q1: Cây toán tử của một biểu thức đại số quan hệ có thể đƣợc xem nhƣ một cây phân tích cú pháp (pharse tree) của chính biểu thức đó, giả sử có văn phạm sau đây: R  identifier R  (R) R  un_op R un_op   F  A bin_op    -   F    
  4. Tập bài giảng Cơ sở dữ liệu phân tán Hai biểu thức đại số quan hệ E1 và E2 là tƣơng đƣơng, kí hiệu E1  E2 hoặc E1  E2 nếu thay thế cùng các quan hệ cho các tên giống nhau trong hai biểu thức thì ta có các kết quả tƣơng đƣơng. Các phép biến đổi tƣơng đƣơng đƣợc xây dựng từ các biểu thức đơn giản (các biểu thức có hai hoặc ba quan hệ toán hạng) và đƣợc phân loại theo loại toán tử. 3) Các tính chất của các phép toán đại số quan hệ: Cho U là phép một ngôi và B là phép hai ngôi. - Tính giao hoán (commutativity) của các phép toán một ngôi: U1(U2(R))  U2(U1(R)) - Tính giao hoán của các phép toán hạng của các phép toán hai ngôi: RBSSBR - Tính kết hợp (associativity) của các phép toán hai ngôi: R B (S B T)  (R B S) B T - Tính lũy đẳng (idempotence) của các phép toán một ngôi: U (R)  U1(U2 (R)) trong đó U1, U2 thuộc cùng loại phép toán. - Tính phân phối (distributivity) của các phép toán một ngôi đối với các phép toán hai ngôi U(R B S)  U(R) B U(S) - Tính rút thừa số (factorization) của các phép toán một ngôi (phép biến đổi này ngƣợc với tính phân phối): U(R) B U(S)  U(R B S) 4) Các phép biến đổi tƣơng đƣơng Từ các tính chất trên của các phép toán đại số quan hệ, chúng ta có thể liệt kê các phép biến đổi tƣơng đƣơng sau đây, còn đƣợc gọi là quy tắc đạo sinh (generation rule) mà chúng cho thấy phần mô tả bên vế phải đƣợc suy diễn nhƣ thế nào từ phần mô tả bên vế trái. Các quy tắc đạo sinh không đƣợc thể hiện khi các phần mô tả của vế trái và vế phải giống nhau. 1- Hai phép chọn kề nhau -  F1 ( F 2 ( R))   F 2 ( F1 ( R)) -  F1  F 2 R    F1 F 2 R  2 - Hai phép chiếu kề nhau  X 1  X 2 R    X 1 (R) với X1  X2 3 - Phép chiếu kề với phép chọn -  X  F R    F  X R  ; nếu Attr(F)  X 178
  5. Tập bài giảng Cơ sở dữ liệu phân tán -  X ( F ( R))   X ( F  X  Attr( F ) ( R))) 4 - Phép hợp kề với phép chọn  F  R  S    F ( R)   F ( S ) 5 - Phép kết nối kề với phép chọn -  F R  S    F R   S ; nếu Attr(F)  Attr(R) -  F1 F 2 R  S    F1 R    F 2 (S ) ; nếu Attr(F1)  Attr(R) và Attr(F2)  Attr(S)) -  F R  S    F 2 ( F1 R   S ) ; nếu F = F1  F2 và Attr(F1)  Attr(R) và Attr(F2)  Attr(R)  Attr(S)) 6 - Phép tích Đề- Các kề với phép chọn -  F R  S    F ( R)  S ; nếu Attr(F)  Attr(R) -  F1 F 2 R  S    F1 R    F 2 (S ) ; nếu Attr(F1)  Attr(R) và Attr(F2)  Attr(S) -  F R  S    F 2 ( F1 R   S ) ; nếu F = F1  F2 và Attr(F1)  Attr(R) và Attr(F2)  (R)  Attr(S) 7 - Phép giao kề với phép chọn -  F R  S    F ( R)   F (S ) -  F1 F 2 R  S    F1 ( R)   F 2 (S ) ; nếu Attr(F1)  Attr(R) và Attr(F2)  Attr(S) 8 - Phép trừ kề với phép chọn  F  R  S    F ( R)   F ( S ) 9 - Phép trừ kề với phép chiếu  X ( R  S )   X ( R)   X (S ) 10 - Phép hợp kề với phép chiếu  X ( R  S )   X ( R)   X ( S ) 11 - Phép kết nối kề với phép chiếu -  X R  S    X R   S ; nếu Attr(FR)  X (Attr(FR) là các thuộc tính trong R của phép kết nối và X  Attr(R) -  X 1 X 2 R  S    X 1R    X 2 (S ) ; nếu Attr(F)  X1  X2 và X1  Attr(R) và X2  Attr(S) (Attr(F) là các thuộc tính trong R và S của phép kết nối). 12 - Phép tích Đề- Các kề với phép chiếu  X 1 X 2 R  S    X 1 R    X 2 (S ) ; 179
  6. Tập bài giảng Cơ sở dữ liệu phân tán nếu X1 Attr(R) và X2  Attr(S) 13 - Các phép hợp, giao, tích Đề- Các và kết nối - (R  S)  T  (R  T)  S - (R  S)  T  (R  T)  S - (R  S)  T  (R  T)  S - R  F1 S   F 2 T  R  F 2 T   F1 S ; nếu Attr(F2)  Attr(R)  Attr(T) và Attr(F1)  Attr(R)  Attr(S) 14 - Phép kết nối đi sau phép hợp R  S   T  R  T   S  T  15 - Phép giao đi sau phép hợp R  S   T  R  T   S  T  16 - Phép hiệu đi sau phép hợp R  S   T  R  T   S  T  17 - Phép hiệu đi trƣớc phép hợp R  S  T   R  S  T  R  T  S  R  S   R  T  5) Các tiêu chuẩn áp dụng các phép biến đổi tƣơng đƣơng để đơn giản hóa việc thực hiện các truy vấn Các phép toán hai ngôi và đặc biệt là các phép kết nối là các phép toán tốn kém nhất trong các hệ thống CSDL. Do đó cần phải giảm kích thƣớc của các toán hạng của các phép toán hai ngôi trƣớc khi thực hiện chúng bằng cách sử dụng các phép biến đổi tƣơng đƣơng. Tiêu chuẩn 1: Sử dụng tích lũy đẳng của phép chọn và phép chiếu để tạo ra các phép chọn và các phép chiếu thích hợp đối với mỗi quan hệ toán hạng. Tiêu chuẩn 2: Đẩy các phép chọn và các phép chiếu xuống phía dƣới cây nếu có thể đƣợc. Khi một phép chiếu di chuyển xuống dƣới qua một phép kết nối thì các thuộc tính trong điều kiện kết nối phải có trong tập thuộc tính chiếu của phép này. Trong các CSDL phân tán, các tiêu chuẩn này còn quan trọng hơn: các phép toán hai ngôi đòi hỏi so sánh các toán hạng mà chúng có thể đƣợc đặt tại các nơi khác nhau. Truyền dữ liệu là một trong các thành phần chính của các chi phí và các trì hoãn gắn liền với việc thực hiện truy vấn. Do đó, việc làm giảm kích thƣớc của các toán hạng của các phép toán hai ngôi là một điều quan tâm chính. Ví dụ 4.3: Xét truy vấn Q1 trong ví dụ 4.2. Áp dụng hai tiêu chuẩn trên, ta biến đổi truy vấn Q1 nhƣ sau: - Phép chọn đƣợc phân phối đối với phép kết nối. Do đó, phép chọn đƣợc áp dụng trực tiếp cho quan hệ NCC. 180
  7. Tập bài giảng Cơ sở dữ liệu phân tán - Hai phép chiếu mới đƣợc tạo ra và đƣợc phân phối đối với phép kết nối. Khi một phép chiếu di chuyển xuống dƣới quan một phép kết nối thì các thuộc tính trong điều kiện kết nối phải có trong tập thuộc tính chiếu của phép này. 4.1.3. Đồ thị toán tử và xác đinh biểu thức con chung Một vấn đề quan trọng việc áp dụng các phép biến đổi cho một biểu thức cho một biểu thức truy vấn là tìm ra các biểu thức con chung (common subexpresion) của nó. Rõ ràng, điều này sẽ tiết kiệm thời gian thực hiện của một truy vấn nếu các biểu thức con chung chỉ đƣợc định trị một lần. Phƣơng pháp xác định biểu thức con chung là biến đổi cây toán tử thành một đồ thị toán tử. 1) Các bƣớc biến đổi cây toán tử thành đồ thị toán tử: Bƣớc 1: Gộp các nút lá giống nhau của cây tức là các quan hệ toán hạng giống nhau. Bƣớc 2: Gộp các nút trung gian khác của cây tƣơng ứng với cùng các phép toán và có cùng các toán hạng. 2) Các đặc tính đƣợc dùng để đơn giản hóa một cây toán tử (1) R  R  R (2) R  R  R (3) R - R   (4) R  F(R)  F(R) (5) R  F(R)  R (6) R - F(R)    F(R) (7) F1(R)  F2(R)  F1  F2(R) (8) F1(R)  F2(R)  F1  F2(R) (9) F1(R) - F2(R)  F1   F2(R) Ví dụ 4.4: Đƣa ra tên của các nhân viên làm việc trong một phòng ban có mã quản lí là 100 nhƣng họ không đƣợc lĩnh lƣơng nhiều hơn 2000. 181
  8. Tập bài giảng Cơ sở dữ liệu phân tán Ta có biểu thức của truy vấn: - NV1 = NV >< NV.MAPPH.MAP (σMAQL100 PH) - NV2 = σLUONG2000  NV  >< NV.MAPPH.MAP σ MAQL100  PH  - TENNV  NV1  NV2  Vì phép kết nối giữa các quan hệ là phép kết nối bằng nền các biểu thức truy vấn có thể đƣợc viết lại nhƣ sau: - NV1 = NV  (σMAQL100 PH) - NV2 = σLUONG2000  NV   σMAQL100  PH  - TENNV  NV1  NV2  Ta có cây toán tử tƣơng ứng với biểu thức Bƣớc 1: Gộp các nút lá tƣơng ứng với các quan hệ NV và PH + Đặt thừa số là phép chọn trên LUONG đối với phép kết nối bằng cách di chuyển phép chọn lên phía trên + Gộp các nút tƣơng ứng với phép chọn trên MAQL ta đƣợc các nút tƣơng ứng với phép kết nối Ta có đƣợc cây toán tử nhƣ sau: Ta đƣợc biểu thức con tƣơng ứng với cây toán tử trên là 182
  9. Tập bài giảng Cơ sở dữ liệu phân tán NV1= NV  (σMAQL100DEPT) Bƣớc 2: Áp dụng đặc tính thứ 6: NV1 - σLUONG 2000  NV1    LUONG  2000(NV1), ta rút gọn cây toán tử thành cây nhƣ sau: Ta đƣợc biểu thức con tƣơng ứng với cây toán tử trên  TENNV σLUONG  2000  NV  (σMAQL100 PH)   Bƣớc 3: Áp dụng phép biến đổi tƣơng đƣơng (2)  TENNV σLUONG  2000  NV  (σMAQL100 PH)      TENNV MAP,TENNV σLUONG  2000 (NV  (σMAQL100 PH))  Áp dụng phép biến đổi tƣơng đƣơng (5)  TENNV   MAP, TENNV  σLUONG 2000 (NV)  σMAQL100 (PH)  Áp dụng phép biến đổi tƣơng đƣơng (12)  TENNV   MAP, TENNV  σLUONG  2000 (NV    MAP  σMAQL100PH  Ta đƣợc cây toán tử nhƣ sau: 183
  10. Tập bài giảng Cơ sở dữ liệu phân tán 4.2. Biến đổi truy vấn toàn cục thành các truy vấn mảnh 4.2.1 Biểu thức chuẩn tắc của một truy vấn mảnh 1) Biểu thức chuẩn tắc Biểu thức chuẩn tắc (canonical expression) của một biểu thức đại số trên lƣợc đồ toàn cục là biểu thức mà mỗi tên quan hệ toàn cục xuất trong nó đƣợc thay thế bởi biểu thức đại số tái tạo các quan hệ toàn cục từ các mảnh. Ví dụ 4.5: Xét lƣợc đồ phân mảnh của quan hệ toàn cục PH trong ví dụ 2.13 PH1=  MAP 10(PH) PH2=  MAP >10 AND MAP < 20 (PH) PH3=  MAP  20 (PH) Cho truy vấn Q2: MAP = 1(PH) Biểu thức chuẩn tắc MAP = 1(PH1  PH2  PH3) 2) Cây toán tử trên lƣợc đồ phân mảnh Biến đổi một cây toán tử trên lƣợc đồ toàn cục thành một cây toán tử trên lƣợc đồ phân mảnh bằng cách thay thế các nút lá của cây toán tử trên lƣợc đồ toàn cục bởi các biểu thức tái tạo tƣơng ứng của lƣợc đồ phân mảnh. 3) Tối ƣu hóa biểu thức chuẩn tắc - Sử dụng các phép biến đổi tƣơng đƣơng. - Sử dụng tính phân phối của phép chọn và phép chiếu đối với phép hợp và phép kết nối để phân phối việc xử lý đến các mảnh. Ví dụ 4.6: Xét truy vấn Q1 trong ví dụ 4.3 với truy vấn Q1 và biểu thức tái tạo quan hệ toàn cục NCC và PH NCC= NCC1  NCC2 KD= KD1  KD2 Vì phép kết nối là phép kết nối bằng nên cây toán tử có thể đƣợc biểu diễn nhƣ sau: 184
  11. Tập bài giảng Cơ sở dữ liệu phân tán Cây toán tử đƣợc của truy vấn Q1 đƣợc biểu diễn trong thành cây toán tử của biểu thức chuẩn tắc của truy vấn Q1 nhƣ sau: Áp dụng phép biến đổi tƣơng đƣơng (4) và (11), ta đƣợc cây toán tử nhƣ sau: 4.2.2. Đại số quan hệ định tính 1) Khái niệm: Một quan hệ định tính là một quan hệ đƣợc mở rộng bởi một vị từ định tính. Vị từ định tính có thể đƣợc xem là một đặc tính ngữ nghĩa (intensional property) của tất cả các bộ của quan hệ. Ký hiệu một quan hệ định tính (qualified relation) là một cặp [R:qr ] Trong đó: - Một quan hệ đƣợc gọi là thân (body) của quan hệ định tính - qr là một vị từ đƣợc gọi là vị từ định tính (qualification) của quan hệ định tính. 185
  12. Tập bài giảng Cơ sở dữ liệu phân tán Các mảnh ngang là các ví dụ tiêu biểu của các quan hệ định tính, trong đó vị từ định tính tƣơng ứng với vị từ phân mảnh. Ví dụ 4.7: Xét lƣợc đồ phân mảnh trong ví dụ 2.13, ta có các quan hệ định tính [PH1: MAP  10]; [PH2: MAP >10 AND MAP < 20]. [NCC1: DC = „Miền Bắc‟]; [NCC2: DC = „Miền Nam‟]. [KD1: KD.MANCC = NCC.MANCC  NCC. DC = „Miền Bắc‟] [KD2: KD.MANCC = NCC.MANCC  NCC. DC = „Miền Nam‟] Vị từ định tính của một quan hệ không cần phải đƣợc định trị trên các bộ của quan hệ. Tuy nhiên, nếu vị từ định tính đƣợc định trị thì vị từ định tính phải đúng. Cụ thể, một vị từ định tính không thể đƣợc định trị khi chúng ta không địng trị đƣợc một số thuộc tính trong biểu thức của vị từ định tính. Đại số các quan hệ định tính là sự mở rộng của đại số quan hệ, trong đó sử dụng các quan hệ định tính nhƣ là các toán hạng. Rõ ràng, đại số này đòi hỏi việc thao tác trên các điều kiện định tính cũng nhƣ trên các quan hệ. 2) Các quy tắc Các quy tắc sau đây xác định kết quả của việc áp dụng các phép toán đại số quan hệ cho các quan hệ định tính: a) Quy tắc 1: F [R: qR]  [F R: F AND qR] Quy tắc này phát biểu rằng việc áp dụng một phép chọn F cho một quan hệ định tính [R: qR] tạo ra một quan hệ định tính có quan hệ F R là thân của nó và vị từ F AND qR là vị từ định tính của nó. Việc mở rộng vị từ định tính F AND qR sau khi chọn phản ánh rằng F và qR đều đƣợc thỏa mãn trên tất cả các bộ đƣợc chọn. b) Quy tắc 2: A [R: qR]  A [R: qR] Vị từ định tính của kết quả của một phép chiếu vẫn không thay đổi, ngay cả khi phép chiếu loại bổ một số thuộc tính dùng để định trị vị từ định tính. Lý do là các vị từ định tính mang thông tin ngữ nghĩa (intensional information). Do đó, điều này vẫn đúng khi loại bỏ các thuộc tính đƣợc dùng đẻ biểu diễn vị từ định tính, mà không loại bỏ chính định vị từ định tính c) Quy tắc 3: [R: qR]  [S: qS]  [R  S: qR AND qS] Việc mở rộng vị từ định tính qR AND qS là trực quan. Lƣu ý rằng hai vị từ định tính áp dụng riêng cho các thuộc tính của R  S. d) Quy tắc 4: [R: qR] - [S: qS]  [R - S: qR] Việc mở rộng phép hiệu là hơi trực quan. Khi chúng ta loại bỏ các bộ của quan hệ S có trong quan hệ R, vì từ định tính của kết quả vẫn giống với vị từ định tính của R. Điều không đúng khi thay thế nó thành qr AND NOT qs, bởi vì có thể các bộ của R 186
  13. Tập bài giảng Cơ sở dữ liệu phân tán không thỏa mãn qR AND NOT qS, nhƣng nó có trong kết quả bởi vì S không chứa các bộ này. Tuy nhiên, vấn đề sau đây đƣợc đặt ra với quy tắc 4: Xét phép giao của hệ số quan hệ truyền thống, đƣợc định nghĩa là R  S = R - (R - S). Từ định nghĩa, dễ dàng thấy rằng phép giao có tính giao hoán, nghĩa là: RS= SR Nếu chúng ta áp dụng định nghĩa của đại số mở rộng, chúng ta đi đến 1 kết quả đáng ngạc nhiên: [R: qR]  [S: qS]  [R: qR] - ([R: qR] - [S: qS])  [R: qR] - [R - S: qR]  [R (R - S): qR]  [R  S:qR] (4.2.a) [S: qS]  [R: qR]  [S: qS] - ([S: qS] - [R: qR]  [S: qS] - [S - R: qS]  [S- (S - R): qS] - [R: qR]  [S  R: qS] (4.2b) Trên thực tế, kết quả mà chúng ta muốn tìm là. [R  S: qR AND qS] Bởi vì các bộ của phép giao là những bộ thuộc cả hai quan hệ thỏa mãn cả hai qr và qs. Lƣu ý rằng, qr AND qs bao hàm cả hai qr và qs. Do đó, các kết quả (4.2a) và (4.2b) là không sai, nhƣng dĩ nhiên một số thông tin bị mất. e) Quy tắc 5: [R: qR]  [S: qS]  [R  S: qR OR qS] Phép hợp đƣợc mở rộng bằng cách lấy OR của các vị từ định tính. Cho trƣớc các quy tắc trên, chúng ta thấy các phép toán đại số đƣợc suy đoán nhƣ thế nào, chẳng hạn phép kết nối và phép nửa kết nối. Chúng ta có thêm hai quy tắc f) Quy tắc 6: [R: qR]  [S: qS]  [R  F S: qR AND qS AND F] Chứng minh quy tắc 6 (nên nhớ rằng phép kết nối đựơc suy dẫn từ việc sử dụng phép chọn và tích Descarters). [R: qR]  [S: qS]  F ([R: qR]  [S: qS]  F [R  S: qR AND qS]  F (R  S): qR AND qS AND F]  [R:  F S: qR AND qS AND F] g) Quy tắc 7: [R: qR]   F [S: qS]  [R   F S: qR AND qS AND F] Chứng minh quy tắc 7 (nên nhớ rằng phép nửa kết nối đƣợc suy dẫn từ việc sử dụng phép chiếu và phép kết nối) [R: qR]   F [S: qS]  Atlr(R)([R: qR]  F [S: qS])  Atlr(R)[R  F S: qR AND qS AND F]  [Atlr(R)(R  F S): qR AND qS AND F]  187
  14. Tập bài giảng Cơ sở dữ liệu phân tán [R:   F S: qR AND qS AND F] Chứng minh hai quy tắc này sẽ cho chúng ta thấy cách thao tác các quan hệ định tính nhƣ thế nào. 3) Tính tƣơng đƣơng của hai quan hệ định tính Hai quan hệ định tính là tƣơng đƣơng nếu các thân của chúng là các quan hệ tƣơng đƣơng và các vị từ định tính của chúng biểu diễn cùng hàm chân trị. Nghĩa là, nếu chúng ta áp dụng cả hai vị từ định tính cho cùng một bộ thì chúng ta có cùng một chân trị Hệ quả: Tất cả các phép biến đổi tƣơng của đại số quan hệ vẫn còn đúng với các đại số quan hệ định tính. 4) Các phép biến đổi tƣơng đƣơng để xác định một truy vấn là rỗng Chúng ta sử dụng các vị từ định tính để loại bỏ các mảnh không liên quan đến truy vấn. Xét vị từ định tính đƣợc tạo ra sau một phép chọn hoặc một phép chiếu. Trong những trƣờng hợp này, vị từ định tính sẽ có dạng chuẩn giao các vị từ (conjunction of predicates). Vị từ định tính này có thể bị mâu thuẫn. Một ví dụ về một vị từ định tính mâu thuẫn là MAP =1 AND MAP= 5. Các quan hệ định tính với các vị từ định tính mâu thuẫn về thực chất là rỗng. Điều nhận biết này là có ích hơn so với việc phát hiện ra kết quả của một biểu thức là rỗng khi thực hiện truy vấn. Trên thực tế, sự mâu thuẫn là rút giảm các đặc tính ngữ nghĩa (intensional propety) của các mảnh, và có thể sử dụng trong lúc biên dịch truy vấn. Bằng cách sử dụng các vị từ định tính ở trên, đại số quan hệ định tính sẽ cho các kết quả nhất quan mà các vị từ định tính của các toán hạng của nó đƣợc cho một cách đúng đắn và sẽ không biết trƣớc kết quả nhƣ thế nào nếu các vị từ định tính là không đúng. Vì chúng ta áp dụng đại số này cho các mảnh của các quan hệ, điều cảnh báo này cho thấy các vị từ định tính của các mảnh cần phải đƣợc cho trƣớc một cách chính xác. Ví dụ 4.8: Các biểu thức con dẫn đến quan hệ rỗng là:  DC = „Miền Nam‟ [NCC1: DC = „Miền Bắc‟] [PH1: MAP < 10]  MAP = MAP[NV3: MAP > 20] Việc nhận biết một trong các biểu thức con của một truy vấn thực chất là rỗng sẽ dẫn đến các phép đơn giản hóa đáng kể của cây truy vấn. Việc nhận biết một trong các biểu thức con của một truy vấn thực chất là rỗng sẽ dẫn đến các phép đơn giản hóa đáng kể của cây truy vấn. Các phép biến đổi tƣơng sau đây là có ích, trong đó R có thể đựơc xem là một quan hệ thông thƣờng hoặc một quan hệ định tính: 188
  15. Tập bài giảng Cơ sở dữ liệu phân tán ()   A()   RR RR R-R -R R  F    R  F       F R  Trong đó, R là một quan hệ thông thƣờng hoặc một quan hệ định tính. Việc nhận biết một trong các biểu thức con của một truy vấn thực chất là rỗng sẽ dẫn đến các phép đơn giản hóa đáng kể của cây truy vấn. 5) Các tiêu chuẩn để đơn giản hóa các biểu thức trên một lƣợc đồ phân mảnh: Tiêu chuẩn 1: Sử dụng tích lũy đẳng của phép chọn và phép chiếu để tạo ra các phép chọn và các phép chiếu thích hợp đối với mỗi quan hệ toán hạng. Tiêu chuẩn 2: Đẩy các phép chọn và các phép chiếu xuống phía dƣới cây nếu có thể đƣợc. Tiêu chuẩn 3: Rút gọn với phép chọn - Đẩy các phép chọn xuống phía các nút lá của cây - Thực hiện chúng bằng cách dùng đại số quan hệ định tính - Thay thế kết quả của phép chọn bởi quan hệ rỗng nếu vị từ định tính của kết quả bị mâu thuẫn. Tiêu chuẩn 4: Sử dụng đại số quan hệ định tính để định trị vị từ định tính của các toán hạng của các phép kết nối. Thay thế cây con (bao gồm phép kết nối và các toán hạng của nó) bằng quan hệ rỗng nếu vị từ định tính của kết quả của phép kết nối bị mâu thuẫn. Tiêu chuẩn 5: Để phân tán các phép kết nối xuất hiện trong một truy vấn toàn cục, các phép hợp (biểu diễn việc tập hợp các mảnh) phải đƣợc đẩy lên phía trên các phép kết mà chúng ta muốn phân phối. Năm tiêu chuẩn trên đƣợc dùng để đơn giản hóa các quan hệ đƣợc phân mảnh ngang đơn giản các phép kết nối giữa các quan hệ đƣợc phân mảnh ngang. 4.2.3. Đơn giản hóa các quan hệ đƣợc phân mảnh ngang Các bước đơn giản hóa: Bƣớc 1: Tìm dạng chuẩn tắc của truy vấn Bƣớc 2: Đẩy phép chọn xuống phía các nút lá của cây 189
  16. Tập bài giảng Cơ sở dữ liệu phân tán Bƣớc 3: Rút gọn với phép chọn bằng cách loại bỏ phần chứa phép chọn sinh ra quan hệ rỗng Cho quan hệ R đƣợc phân mảnh ngang chính thành R1, R2, ..., Rn, trong đó Ri=  pi (R), pi là vị từ chọn Quy tắc rút gọn phép chọn  p (Ri)= nếu  u  R: (pi(u)pj(u)) j Trong đó: + pi, pj là các vị từ chọn + u là một bộ của R + p(u): vị từ p đúng với u Ví dụ 4.9: Xét hệ thống quản lý kinh doanh của một công ty với lƣợc đồ phân mảnh trong ví dụ 2.13. Hãy đơn giản hoá câu truy vấn trên các mảnh: Select * From PH Where MAP=1 Ta có biểu thức đại số quan hệ tƣơng ứng: Q3: MAP = 1(PH) Bƣớc 1: Dạng chuẩn tắc của truy vấn Q3 MAP = 1(PH1  PH2  PH3) Bƣớc 2: Đẩy phép chọn hƣớng xuống các nút lá bằng cách phân phối nó đối với phép hợp. Bƣớc 3: Rút gọn với phép chọn MAP = 1(PH2) =   u  PH: (p2(u)pj(u)) 190
  17. Tập bài giảng Cơ sở dữ liệu phân tán p2(u): 10 20 pj(u): MAP = 1 Bƣớc 4: Đơn giản phép hợp 4.2.4. Đơn giản hóa các phép kết nối giữa các quan hệ đƣợc phân mảnh ngang chính Các bƣớc đơn giản hóa: Bƣớc 1: Tìm dạng chuẩn tắc của truy vấn theo hai giải pháp sau Giải pháp 1: R  F S = ( Ri)  F ( Sj), nếu có nhiều mảnh đƣợc kết nối với nhau Giải pháp 2: R  F S =  (Ri  F Sj), nếu có một số cặp mảnh đƣợc kết nối với nhau Bƣớc 2: Đẩy phép hợp lên phía các phép kết nối ( Ri)  F ( Sj)=  (Ri  F Sj) Bƣớc 3: Rút gọn với phép nối bằng cách loại bỏ phần đƣợc tạo bởi phép kết nối sinh ra quan hệ rỗng. Cho quan hệ R đƣợc phân mảnh ngang chính thành R1, R2, ..., Rn, trong đó Ri=  pi (R), pi là vị từ chọn Quy tắc rút gọn phép nối Ri  F Rj =  nếu u  Ri, v  Rj: (pi(u)pj(v)) Trong đó pi, pj là các vị từ chọn u là một bộ của Ri, v là một bộ của Rj p(u): vị từ p đúng với u 191
  18. Tập bài giảng Cơ sở dữ liệu phân tán Chú ý: Nếu phép kết nối là phép kết nối bằng thì sử dụng kí hiệu *. Ví dụ 4.10: Xét hệ thống quản lý kinh doanh của một công ty với lƣợc đồ phân mảnh trong ví dụ 2.13. Hãy đơn giản hoá câu truy vấn trên các mảnh: Select * Form KD, NCC Where KD.MANCC= NCC.MANCC Ta có biểu thức đại số quan hệ tƣơng ứng: Q4: KD * NCC Các bƣớc đơn giản hóa: Bƣớc 1: Dạng chuẩn tắc của truy vấn Q4 (KD1 KD2) * (NCC1NCC2) Bƣớc 2: Đẩy phép hợp lên phía các phép kết nối Bƣớc 3: Rút gọn với phép nối KD1 * NCC2 =  KD2 * NCC1 =  4.2.5. Đơn giản hóa cho phân mảnh ngang dẫn xuất Các bƣớc đơn giản hóa: 192
  19. Tập bài giảng Cơ sở dữ liệu phân tán Bƣớc 1: Tìm dạng chuẩn tắc của truy vấn Bƣớc 2: Đẩy phép chọn xuống phía dƣới các nút lá của cây Bƣớc 3: Rút gọn phép chọn, đơn giản phép hợp Bƣớc 4: Đẩy phép hợp lên phía các phép kết nối ( Ri)  F ( Sj)=  (Ri  F Sj) Bƣớc 5: Rút gọn với phép nối, đơn giản phép hợp Ví dụ 4.11: Xét hệ thống quản lý kinh doanh của một công ty với lƣợc đồ phân mảnh trong ví dụ 2.13. Hãy đơn giản hoá câu truy vấn trên các mảnh: Select * Form NCC, KD Where NCC.MANCC = KD.MANCC and DC=”Miền Bắc” Ta có biểu thức đại số quan hệ tƣơng ứng: Q5: NCC * DC=”Miền Bắc” KD  KD *  DC=”Miền Bắc” NCC Các bƣớc đơn giản hóa: Bƣớc 1: Dạng chuẩn tắc của truy vấn Q5 (KD1 KD2)*  DC=”Miền Bắc” (NCC1  NCC2 ) Bƣớc 2: Đẩy phép chọn xuống phía dƣới Bƣớc 3: Rút gọn với phép chọn, đơn giản phép hợp  DC=”Miền Bắc” (NCC2)=  193
  20. Tập bài giảng Cơ sở dữ liệu phân tán Bƣớc 4: Đẩy phép hợp lên phía các phép kết nối Bƣớc 5: Rút gọn với phép nối, đơn giản phép hợp KD2*  DC=”Miền Bắc” (NCC1) =  4.2.6. Đơn giản hóa các quan hệ đƣợc phân mảnh dọc Các bƣớc đơn giản hóa: Bƣớc 1: Tìm dạng chuẩn tắc của truy vấn Bƣớc 2: Đẩy phép chiếu xuống phía dƣới các nút lá của cây Bƣớc 3: Rút gọn phép chiếu bằng cách loại bỏ các phép chiếu trên một mảnh dọc sinh ra quan hệ vô dụng, mặc dù không phải là quan hệ rỗng. Cho quan hệ R đƣợc đƣợc phân thành các mảnh R1, R2, …Rn K là khóa của R Ri = Π X(R), trong đó X  Attr(R) Quy tắc rút gọn phép chiếu Π Y, K(Ri)=vô dụng nếu tập thuộc tính chiếu Y  X Bƣớc 4: Đơn giản phép kết nối 194
nguon tai.lieu . vn
Tin học văn phòng Đồ họa - Thiết kế - Flash Quản trị Web Cơ sở dữ liệu Quản trị mạng Kỹ thuật lập trình Hệ điều hành Phần cứng An ninh - Bảo mật Chứng chỉ quốc tế Thủ thuật máy tính Điện - Điện tử Kinh tế học Hoá học Xã hội học Môi trường