Đồ Thị Truy Vấn Và Đồ Thị Nối Ví Dụ 2.5: Xét Câu Truy Vấn

Ta có, các vị từ đơn giản:

p1: PC.MaNV = NV.MaNV p2: PC.MaDA=DA.MaDA

p3: TênDA=‟CAD/CAM‟ p4: CVụ =‟TP‟ p5: tgian >36 Ta có đồ thị truy vấn và đồ thị nối như Hình 2.4

Đồ thị truy vấn Đồ thị nối

Có thể bạn quan tâm!

Xem toàn bộ 103 trang tài liệu này.

Hình 2.4: Đồ thị truy vấn và Đồ thị nối Ví dụ 2.5: Xét câu truy vấn

Select TênNV From PC, NV,DA

Where PC.MaNV = NV.MaNV and TênDA=‟CAD/CAM‟ and CVụ =‟TP‟ and tgian >36

Ta có đồ thị truy vấn và đồ thị nối như Hình 2.5

thị truy vấn

Đồ Đồ thị nối

Hình 2.5: Đồ thị truy vấn và Đồ thị nối với câu truy vấn sai ngữ nghĩa

=> Đồ thị không liên thông. Điều này có nghĩa là câu truy vấn này sai ngữ nghĩa.

Nhận xét: Câu truy vấn sai ngữ nghĩa nếu đồ thị truy vấn của nó không liên thông: Một hoặc nhiều đồ thị con bị tách rời với đồ thị kết quả.

2.2.1.3. Loại bỏ dư thừa

Một câu truy vấn của người sử dụng thường được diễn tả trên một khung nhìn có thể được bổ sung thêm nhiều vị từ để có được sự tương ứng khung nhìn - quan hệ, bảo đảm được tính toàn vẹn ngữ nghĩa và bảo mật. Thế nhưng lượng từ hoá truy vấn đã được sửa đổi này có thể chứa các vị từ dư thừa, có thể phải khiến lặp lại một số công việc. Một cách làm đơn giản truy vấn là loại bỏ các vị từ thừa.

Loại bỏ vị từ dư thừa bằng quy tắc luỹ đẳng:

1. p ʌ p  p 6. p v True  True

2. p v p  p 7. p ʌ  p  False

3. p ʌ True  p 8. p v  p  True

4. p v False  p 9. p1 ʌ (p1v p2)  p1

5. p ʌ False  False 10. p1 v (p1 ʌ p2)  p1

Ví dụ 2.6: Xét câu truy vấn sau: Select CVụ

From NV

Where (Not (CVụ =‟TP‟) and (CVụ=‟TP‟ or CVụ=‟PP‟) and not (CVụ=‟PP‟)) or TênNV=‟Mai‟

Đặt:

p1: CVụ =‟TP‟ p2: CVụ=‟PP‟

p3: TênNV=‟Mai‟

Lượng từ hóa câu truy vấn trên, ta được: ( p1 ʌ (p1 v p2) ʌ  p2 ) v p3

áp dụng p ʌ (s v q)  (p ʌ s) v (p ʌ q): ( p1 ʌ ((p1 ʌ  p2 ) v (p2 ʌ  p2 ))) v p3 áp dụng quy tắc 3: ( p1 ʌ p1 ʌ  p2 ) v ( p1 ʌ p2 ʌ  p2 ) v p3

áp dụng quy tắc 7: (False  p2) v ( p1 ʌ False) v p3

áp dụng quy tắc 5: False v False v p3 = p3 Tức là: Select CVụ

From NV

where TênNV=‟Mai‟

2.2.1.4. Viết lại

Bước cuối cùng của phân rã câu truy vấn là viết lại câu truy vấn dưới dạng đại số quan hệ. Có thể được chia làm hai bước sau:

- Chuyển đổi câu truy vấn phép tính quan hệ sang đại số quan hệ.

- Xây dựng lại câu truy vấn đại số quan hệ để cải tiến hiệu năng.

Để cho dễ hiểu, thông thường người ta biểu diễn câu truy vấn đại số quan hệ bởi một cây đại số quan hệ. Một cây đại số quan hệ là một cây trong đó một nút lá biểu diễn một quan hệ trong cơ sở dữ liệu, còn một nút khác nút lá biểu diễn một quan hệ trung gian sinh bởi các phép toán đại số quan hệ. Chuỗi các thao tác từ các nút lá đến nút gốc biểu diễn cho kết quả của câu truy vấn.

Biến đổi một câu truy vấn phép tính quan hệ thành một cây đại số quan hệ được thực hiện như sau:

- Các nút lá tương ứng với các quan hệ trong mệnh đề FROM.

- Nút gốc được tạo ra như một phép chiếu chứa các thuộc tính kết quả. Trong SQL, nút gốc được tìm thấy trong mệnh đề SELECT.

- Điều kiện (mệnh đề WHERE trong SQL) được biến đổi thành dãy các phép toán đại số thích hợp (phép chọn, kết nối, phép hợp,…) đi từ nút lá tới gốc, có thể theo thứ tự xuất hiện của các vị từ và các toán tử.

Ví dụ 2.7: Xét câu truy vấn sau: “Tìm tên các nhân viên trừ J.Doe đã làm cho dự án CAD/CAM trong một hoặc hai năm”.

Biểu thức SQL là:

SELECT TênNV

FROM DA, PC, NV WHERE PC.MNV=NV.MNV

AND PC.MDA=DA.MDA

AND TênNV  “J.Doe”

AND DA.TênDA=”CAD/CAM”

TênNV

Thời gian=12  Thời gian=24

TênDA=”CAD/CAM”

TênNV ”J.Doe”

MDA

MNV

Chiếu

AND (Thời gian=12 OR Thời gian=24) Cây đại số quan hệ như Hình 2.6:

Chọn

Nối

Hình 2.6: Cây đại số quan hệ

Các quy tắc biến đổi cây đại số quan hệ:

Cho các quan hệ: R(A), A={A1, A2,…,An}; S(B), B={B1, B2,…,Bn} và T. Có thể nhận được các cây đại số quan hệ tương đương, áp dụng các quy tắc biến đổi sau:

1. Tính chất giao hoán của phép toán hai ngôi:

- Tích Đề các: R x S  S x R

- Kết nối: R S  S R

- Hợp của hai quan hệ: R  S  S  R.

- Quy tắc này không được áp dụng cho hiệu và kết nối nửa.

2. Tính kết hợp của các phép toán hai ngôi

- Tích Đề các: (R x S) x T  R x (S x T)

- Kết nối: (R S) T  R (S T)

3. Tính lũy đẳng của các phép toán đơn ngôi

Nếu R được định nghĩa trên tập thuộc tính A và A‟ A, A” A và A‟ A” thì A‟ A‟(A” (R)) A‟(R)

p1(A1)(p2(A2)(R)) p1(A1) p2(A2)(R)

trong đó pi là một vị từ được áp dụng cho thuộc tính Ai

4. Giao hoán, phép chọn với phép chiếu

Phép chọn và chiếu trên cùng một quan hệ có thể được giao hoán như sau: A1…An(p(Ap)(R)) A1…An(p(Ap)(A1…An,Ap(R)))

Chú ý rằng nếu Ap là phần tử của {A1, A2,…,An} thì phép chiếu cuối cùng trên {A1, A2,…,An} ở vế phải của hệ thức không có tác dụng.

5. Giao hoán, phép chọn với phép toán hai ngôi

- Phép chọn và tích Đề các: p(Ai)(R x S)  (p(Ai)(R)) x S

- Phép chọn và kết nối: p(Ai)(R p(Aj, Bk) S)  (p(Ai)(R)) p(Aj, Bk) S

- Phép chọn và hợp : p(Ai)(R  T) p(Ai)(R) p(Ai)(T)

6. Giao hoán, phép chiếu với phép toán hai ngôi

Nếu C=A‟ B‟, trong đó A‟ A, B‟ B, và A, B là các tập thuộc tính tương ứng của quan hệ R và S, chúng ta có

- C(R x S) A(R)B(S)

- C(R p(Ai, Bj) S) A(R) p(Ai, Bj) B(S)

- C(R  S) A(R) B(S)

Các quy tắc trên có thể được sử dụng để cấu trúc lại cây một cách có hệ thống nhằm loại bỏ các cây “xấu”. Một thuật toán tái cấu trúc đơn giản sử dụng heuristic trong đó có áp dụng các phép toán đơn ngôi (chọn/ chiếu) càng sớm càng tốt nhằm giảm bớt kích thước của quan hệ trung gian.

MDA, TenNV

MNV

MDA, MNV

MNV, TenNV

Tennv <> 'J.Doe'

Tái cấu trúc cây đại số quan hệ trong Ví dụ 2.7 sinh ra cây sau:

TênNV

MDA

TenDA=”CAD/CAM”

Thoigian=12Thoigian=24

Hình 2.7: Cây đại số quan hệ sau khi tái cấu trúc

Kết quả được xem là đạt chất lượng theo nghĩa là nó tránh truy xuất nhiều lần đến cùng một quan hệ và các phép toán chọn nhiều nhất được thực hiện trước tiên.

2.2.2. Cục bộ hóa dữ liệu phân tán

Cục bộ hóa dữ liệu chịu trách nhiệm dịch câu truy vấn đại số trên quan hệ toàn cục sang câu truy vấn đại số quan hệ trên các mảnh vật lý. Cục bộ hóa có sử dụng các thông tin được lưu trong một lược đồ phân mảnh.

Tầng này xác định xem những mảnh nào cần cho câu truy vấn và biến đổi câu

truy vấn phân tán thành câu truy vấn trên các mảnh. Tạo ra câu truy vấn trên mảnh được thực hiện qua hai bước:

- Truy vấn phân tán được ánh xạ thành truy vấn trên mảnh bằng cách thay thế mỗi quan hệ phân tán bằng chương trình xây dựng lại có chứa các phép toán đại số quan hệ thao tác trên mảnh, gọi là chương trình cục bộ hóa

- Truy vấn trên mảnh được đơn giản hoá và xây dựng lại để tạo ra một truy vấn khác tốt hơn. Quá trình đơn giản hoá và xây dựng lại có thể được thực hiện theo những quy tắc được sử dụng trong tầng phân rã.

2.2.2.1. Rút gọn cho phân mảnh ngang nguyên thủy

Phân mảnh ngang phân tán một quan hệ dựa trên các vị từ chọn. Ví dụ quan hệ NV (MaNV, TenNV, CVụ) được phân mảnh ngang thành:

- NV1 = MaNV  „E3‟(NV)

- NV2 = ‟‟E3‟ < MaNV  „E6‟(NV)

- NV3 = MaNV > „E6‟(NV)

Khi đó, chương trình cục bộ hóa cho quan hệ phân mảnh ngang là hợp các mảnh: NV = NV1  NV2  NV3

Vì vậy, dạng truy vấn gốc được xác định trên NV sẽ thu được bằng cách thay

NV bởi (NV1  NV2  NV3). Như vậy, để giảm các thao tác truy vấn trên quan hệ đã được phân mảnh ngang, trước hết phải xác định rõ cần thao tác trên mảnh nào và sau đó xây dựng lại cây con, xem xét loại bỏ các quan hệ rỗng. Phân mảnh ngang sẽ được sử dụng để làm đơn giản hóa các phép chọn và phép kết nối.

Rút gọn phép chọn: Chọn trên các mảnh có lượng từ mâu thuẫn với lượng từ hoá của quy tắc phân mảnh sẽ sinh ra quan hệ rỗng, ta loại bỏ chúng. Cho một quan hệ R được phân mảnh theo chiều ngang là Rj = pj (R), j = 1...n, quy tắc này có thể biểu diễn một cách hình thức như sau:

pj (Rj) =  nếu x thuộc R :  ( pi(x) ʌ pj(x)) Trong đó: pi, pj là các vị từ chọn, x là một bộ.

Ví dụ 2.8: Xét các phân mảnh ngang NV1, NV2, NV3 ở trên.

Vị từ MaNV = "E1" mâu thuẫn với các vị từ của mảnh NV2 và NV3, nghĩa là không có bộ nào thỏa mãn vì từ MaNV = "E1".

Xét câu truy vấn sau: Select MaNV

From NV

Where MaNV=‟E5‟

MaNV

MaNV=‟E5‟



MaNV

MaNV=‟E5‟

Áp dụng cách tiếp cận thô sơ để cục bộ hóa NV từ NV1, NV2 và NV3 cho câu truy vấn gốc trong Hình 2.8 bằng cách hoán vị phép chọn và phép hợp. Dễ dàng nhận thấy vị từ chọn mâu thuẫn với NV1 và NV3. Câu truy vấn đã rút gọn chỉ ứng dụng có một mảnh NV2 như trong Hình 2.9

NV1

NV2

NV3

NV2

Hình 2.8: Câu truy vấn gốc Hình 2.9: Câu truy vấn đã rút gọn Rút gọn với phép kết nối: Phép kết nối thực hiện trên các phân mảnh ngang

có thể đơn giản khi kết nối dựa theo các thuộc tính kết nối, bằng cách phân phối kết nối trên các hợp và sau đó loại bỏ các kết nối không tác dụng. Việc phân phối các kết nối trên phép hợp được phát biểu như sau:

(R1  R2) S = (R1 S)  (R2 S)

Trong đó Ri là các mảnh của R và S là một quan hệ.

Bằng phép biến đổi này, các phép hợp có thể được di chuyển lên trên cây toán tử để tất cả các phép kết nối có thể có các mảnh đều được lộ ra. Các phép nối