Tối Ưu Hóa Độc Lập Của Một Đồ Thị Kết Nối Phân Tách

kết nối, và sau đó các bộ tương ứng với giá trị này sẽ được lấy ra. Trong thực tế, hiệu quả có được do việc thực hiện các phép kết nối mỗi-lần-một-bộ. Tuy nhiên, có sự khác biệt quan trọng giữa phương pháp này với cách tiếp cận phép nửa kết nối; trong khi cách làm đầu tiên chủ yếu được sử dụng để đồng bộ hoá việc xử lý các quan hệ trong và quan hệ ngoài và đòi hỏi nhiều lần truyền thông, thì cách làm sau khi được sử dụng để tiết kiệm các lần truyền thông và đòi hỏi nhiều xử lý cục bộ.

Về nguyên tắc, mỗi phương pháp truyền thông có thể được sử dụng trong ngữ cảnh của mỗi phương pháp kết nối, các khảo sát trong thực tế chỉ làm một số ít các kết hợp cho R*. Chẳng hạn, trong phương pháp vòng lặp lồng nhau, không cho phép truyền toàn bôn I, bởi vì I phải được quét card(O) lần, và điều này chỉ hiệu quả nếu có các phương pháp phương pháp truy xuất hiệu quả cho thuộc tính kết nối. Việc truyền quan hệ sẽ làm mất hiệu lực các phương pháp như thế. Điều này và các khảo sát tương tự giới hạn các trường hợp có thể có:

- Vòng lặp lồng nhau, “di chuyển toàn bộ quan hệ ngoài và không lưu trữ”. Chi phí là tổng của các chi phí kết nối cục bộ trong phương pháp này và lần truyền quan hệ ngoài O:

C1 = C(nested-loop) + Cmes  [card(O)  size(O)/m]

- Quét- trộn , ”di chuyển toàn bộ quan hệ ngoài và không lưu trữ”. Tương tự, chi phí là:

C2 = C(merge-scan) + Cmes [card(O)  size(O)/m]

- Vòng lặp lồng nhau, “quan hệ trong được lấy ra khi cần “. Trong trường hợp này, đôi với mỗi bộ của O, chúng ta gửi một yêu cầu cho I và NI bộ (tính trung bình) thoả mãn yêu cầu này sẽ được gửi trả về. Chúng ta có:

C3 = C(nested-loop) + Cmes  card(O)  (1+[NI  size(I)/m])

- Quét-trộn, ”quan hệ trong được lấy ra khi cần”. ở đây, chúng ta giả sử gửi một thông điệp yêu cầu từ O đến I đối với mỗi giá trị khác nhau của thuộc tính kết nối, và tất cả các bộ kết nối được của I đối với mỗi giá trị khác nhau của thuộc tính kết nối, và tất cả các bộ kết nối được của I sẽ được gửi trả về. Các giả sử này trái ngược với điều đã làm trong R*, mà một thông điệp sẽ được gửi đối với một bộ bất kỳ của O. Nếu A là thuộc tính kết nối của O, chúng ta có:

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

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

C4 = C(merge-scan) + Cmes  val(A/O/)  (1 + [NI  size(I)/m])

- Quét- trộn, “di chuyển toàn bộ quan hệ trong và lưu trữ trước khi sử dụng”. Trong trường hợp này, chúng ta mất thêm chi phí để lưu trữ và lấy quan hệ tại nơi xa:

C5 = C(merge-scan) + Cmes  [cad(I)  size(I)/m] + 2  Nin  C10

- Di chuyển cả hai quan hệ đến nơi thứ ba. Trong trường hợp này, các chi phí truyền thông là tổng chi phí của việc truyền tải cả hai quan hệ trong đến quan hệ ngoài

và quan hệ ngoài đến quan hệ trong; chi phí kết nối là C(merge-scan) hoặc C (nested- loop).

Bộ tối ưu R* liệt kê tất cả các chuỗi phép kết nối với tất cả các phương pháp kết nối có thể có và các phép kết nối được định vị tại mỗi nơi có thể có. Sau đó, nó xác định truy xuất ít tốn kém nhất cho một truy vấn đề. Quy hoạch động được áp dụng để làm tăng tốc độ tính toán, bởi vì việc tính toán chi phí thoả mãn các quy tắc có thể áp dụng được cho kỹ thuật này.

5.3. Các truy vấn tổng quát

Trong phần này, chúng ta xét trường hợp tổng quát của các truy vấn với các phép kết nối và các phép hợp trong đồ thị tối ưu hoá. Chúng ta cho thấy phần mở rộng đi từ các truy vấn kết nối đến các truy vấn tổng quát là quan trọng, và rất nhiều chiến lược thực hiện khác nhau có thể sử dụng cho cùng một truy vấn tổng quát. Phép biến đổi cơ bản được sử dụng là tính giao hoán của phép kết nối và phép hợp (tức là tiêu chuẩn 5 trong chương trước) dùng để tạo ra các đồ thị kết nối phân tán. Chúng ta tập trung vào vấn đề của một phép kết nối đơn giữa các quan hệ được phân mảnh, các phép đa kết nối có thể được giải quyết bằng cách áp dụng liên tiếp các khảo sát dưới đây.

Việc xác định chiến lược thực hiện một phép hợp là điều dễ dàng, bởi chúng ta không quan tâm đến thứ tự của các bộ của các toán hạng được đưa vào trong quan hệ kết quả. Do đó, các lần truyền các mảnh không cục bộ đến các nơi (mà phép hợp được thực hiện) có thể được thực hiện một cách song song. Theo các yêu cầu truyền thông, phép hợp có trì hoãn tương ứng với lần truyền thông của mảnh lớn nhất, và chỉ là tổng của tất cả các chi phí truyền thông .

Tác dụng của việc giao hoán các phép kết nối và các phép hợp

Việc giao hoán các phép kết nối và các phép hợp được biểu diễn trong hình 5.4, có 3 đồ thị tối ưu hoá khác nhau của cùng một truy vấn. Trong hình 5.4 và trong tất cả các hình khác của phần này, các vòng tròn biểu diễn các mảnh của quan hệ R, và các hình vuông biểu diễn các mảnh của quan hệ S. Xét hai đồ thị tối ưu hoá đầu tiên của hình 5.4a và 5.4b. trong hình 5.4a, trước tiên các mảnh được kết nối với nhau và sau đó được tập hợp lại. Chúng ta gọi cách tiếp cận thứ nhất là phép kết nối không phân tán (nondistributed join) và cách tiếp cận thứ hai là phép phân tán (distributed join). Hai trường hợp này đặt ra nhiều vấn đề tối ưu hoá khác nhau:

a - Phép kết nối không phân tán: Vấn đề tối ưu hoá này thì đơn giản hơn, chỉ cần xách định cặp nơi (có thể dùng một nơi) mà tại đó các phép hợp được thực hiện. Nếu hai nơi khác nhau, thì truy vấn được rút gọn thành một truy vấn kết nối đơn giản giữa hai quan hệ mà nó có thể được tối ưu hoá như đã chỉ gia trong phần trước.

b - Phép kết nối phân tán: Vấn đề tối ưu hoá này thì khó hơn. Lưu ý rằng, trong hình 5.4b ta thấy đồ thị kết nối của phép kết nối giữa R và S ở bên trong nút bao

(hypernode) mà nút này biểu diễn phép hợp. Sử dụng các tiêu chuẩn về phân mảnh để loại bỏ các cạnh của đồ thị kết nối mà chúng tương ứng với các phép kết nối rỗng, như được chỉ ra trong chương 4 phần 4.2 mục 4. Khi xác định được đồ thị kết nối tối thiểu, việc bằng cách sử dụng các kỹ thuật đã được trình bầy trong phần trước. Cuối cùng, các kết quả kết nối được gửi đến cùng một nơi để thực hiện phép hợp. Đồ thị ưu hoá của hình 5.4b cho thấy phép kết nối phân tán. Tuy nhiên, cũng có thể thực hiện các phép hợp toàn phần (partial union) mà chúng liên quan tới các mảnh của chúng cùng một quan hệ, trước khi thực hiện phép kết nối. Một ví dụ được chỉ ra trong hình 5.4c.

Hình 5.4. Giao hoán phép kết nối và phép hợp

Trong việc xây dựng đồ thị tối ưu hoá G‟ của hình 5.4c, bắt đầu từ đồ thị tối ưu hoá G của hình 5.4c, áp dụng các quy tắc sau đây:

- Các mảnh dùng để thực hiện các phép hợp từng phần sẽ được bao quanh bởi 1 nút bao (trong ví dụ này, quy tắc này áp dụng cho {R1,R2} và {S2,S3}).

- Nếu hai mảnh Ri và Sj được nối với nhau bởi một cạnh trong G, thì các nút (bao)

mà chúng nằm trong cũng được nối với nhau bởi một cạnh trong G‟ (ví dụ, cạnh giữa R1 và S2 trong G tạo ra canh giữa (R1,R2) và (S2,S3) trong G).

Các đồ thị phân tách (partioned graph) là một thích hợp các đồ thị kết nối theo

quan điểm tối ưu hoá việc thực hiện chúng. Trong đồ thị kết nối phân tách, chúng ta có thể phân biệt các đồ thị con rời rạc. Mỗi đồ thị con như thế có thể được tối ưu hoá một cách độc lập. Đặc tính này độc lập với phương pháp được sử dụng để tính toán các hiệu xuất của truy vấn, và dựa vào các cơ sở lập luận sau đây:

- Tối ưu hoá các phép kết nối của các đồ thị con rời rạc có thể được thực hiện một cách độc lập.

- Phép hợp không bị ảnh hưởng bởi thứ tự của các toán hạng được tập hợp lại.

Ví dụ, trong hình 5.5a chúng ta co một đồ thị phân tách, vấn đề tối ưu hoá có thể được phân rã thành hai vấn đề bao gồm các mảnh (R1, R2, S1, S2) và (R3, S3). Trong hình 5.5b cho thấy một đồ thị tối ưu hoá cuối cùng có thể có truy vấn, bao gồm việc thực hiện các phép hợp từng phần của (R1, R2) và (S1, S2), các phép kết nối giữa chúng, phép kết nối giữa R3 và S3, và phép hợp cuối cùng của các kết quả.

Hình 5.5. Tối ưu hóa độc lập của một đồ thị kết nối phân tách

Điều thuận lợi của phép biến đổi từ đồ thị tối ưu hoá của hình 5.5a thành đồ thị tối ưu hoá của hình 5.5b phụ thuộc vào sự định vị và kích thước của các mảnh. Xét ví dụ sau đây: giả sử một mạng có ba nơi cho mảnh thứ i đặt tại thứ i, kết quả đặt tại nơi 1, các toán hạng và các kết quả của mỗi phép kết nối từng phần đều có cùng kích thước. Rất thuận tiện để thực hiện việc tập hợp từng thành phần tại nơi 1, phép kết nối giữa R3 và S3 tại nơi 3, và phép hợp cuối cùng tại nơi 1.

Các đặc tính ở trên cho phép xây dựng nhiều chiến lược bao gồm các phép hợp

từng phần đối với mỗi phần trong đồ thị kết nối; việc tìm ra chiến lược thực hiện tốt nhất cho một truy vấn cho trước đòi hỏi:

- Tạo ra tất cả các đồ thị tối ưu hoá truy vấn có thể có.

- Áp dụng các phương pháp truy vấn kết nối để tối ưu hoá các phép kết nối và cộng thêm các chi phí của phép hợp. Do đó mỗi đồ thị kết nối tương ứng với một chiến lược truy vấn tối ưu và một chi phí.

- Chọn chiến lược xử lý truy vấn tốt nhất trong các chiến lược, hình 5.6, có bốn cạnh khác nhau để tính toán chi phí cho một đồ thị kết nối đầy đủ của hai quan hệ R và S mà mỗi quan hệ có hai nhánh.

Hình 5.6. Các đồ thị tối ưu hoá khác nhau cho cùng một truy vấn

- Thực hiện phép kết nối phân tán. Vấn đề này chỉ thực hiện bốn phép kết nối của mình 5.6a và tập hợp các kết quả của chúng. Lưu ý rằng, tối ưu của bốn phép kết nối

không thể thực hiện riêng biệt. Bởi vì, chẳng hạn, nếu giảm kích thức của một trong các mảnh thì điều này có thể có ích cho ít nhất hai phép kết nối.

- Thực hiện phép hợp từng phần các mảnh của R. Vấn đề chỉ thực hiện hai phép kết nối, và được chỉ ra trong hình 5.6b.

- Thực hiện phép kết nối từng phần các mảnh của S. Vấn đề chỉ thực hiện hai phép kết nối, và được chỉ ra trong hình 5.6c.

- Thực hiện phép hợp các mảnh, sau đó thực hiện phép kết nối của chúng; điều này tương ứng với việc thực hiện không phân tán của phép kết nối, được chỉ ra trong hình 5.6d.

CÂU HỎI VÀ BÀI TẬP

I. Câu hỏi lý thuyết

1) Nêu khái niệm cơ sở dữ liệu phân tán và các khía cạnh quan trọng của một cơ sở dữ liệu phân tán

2) Cho ví dụ và giải thích về một hệ thống sử dụng thiết kế và cài đặt cơ sở dữ liệu phân tán

3) Nêu mục đích của việc sử dụng cơ sở dữ liệu phân tán

4) Vẽ mô hình kiến trúc tham chiếu cơ sở dữ liệu phân tán

5) Giải thích các thành phần trong mô hình kiến trúc

6) Nêu các kiểu kiến trúc tham chiếu cho hệ quản trị cơ sở dữ liệu phân tán

7) Nêu các đặc điểm chính của cơ sở dữ liệu phân tán

8) Nêu các thành phần và phần mềm tiêu biểu cần thiết để xây dựng một cơ sở dữ liệu phân tán

9) Nêu các loại hệ quản trị cơ sở dữ liệu phân tán

10) Nêu các loại phân mảnh dữ liệu

11) Nêu điều kiện đúng đắn để phân mảnh ngang

12) Cho ví dụ về điều kiện đúng đắn để phân mảnh ngang

13) Nêu điều kiện đúng đắn để phân mảnh dọc

14) Cho ví dụ về điều kiện đúng đắn để phân mảnh dọc

15) Nêu các loại phân mảnh dọc

16) Nêu khái niệm phân mảnh hỗn hợp; Cho ví dụ

17) Nêu các mức trong suốt phân tán

18) Nêu các phương pháp truy xuất cơ sở dữ liệu phân tán

19) Nêu các phương pháp truy xuất cơ sở dữ diệu với tính trong suốt phân mảnh

20) Nêu khái niệm cây phân mảnh; Cho ví dụ

21) Nêu khái niệm cây cập nhật; Cho ví dụ

22) Nêu các bước truy xuất CSDL với mỗi giá trị

23) Nêu các bước truy xuất CSDL sau khi nhập vào tất cả các giá trị

24) Nêu các bước truy xuất CSDL trước khi nhập vào các giá trị

25) Nêu các mục tiêu của thiết kế phân tán dữ liệu

26) Nêu các loại thông tin dùng để thiết kế phân tán

27) Nêu các chiến lược tiếp cận để thiết kế CSDL phân tán

28) Vẽ và giải thích sơ đồ của chiến lược thiết kế từ trên xuống

29) Nêu các yêu cầu thông tin khi thiết kế phân mảnh ngang

30) Cho ví dụ thông tin về cơ sở dữ liệu khi thiết kế phân mảnh ngang

31) Nêu các bước thiết kế một cơ sở dữ liệu phân tán

32) Nêu khái niệm, cách biểu diễn, vị từ định tính của phân mảnh ngang chính

33) Cho ví dụ về một quan hệ toàn cục được phân mảnh ngang chính

34) Nêu khái niệm, cách biểu diễn, vị từ định tính của phân mảnh ngang dẫn xuất

35) Cho ví dụ về một quan hệ toàn cục được phân mảnh ngang dẫn xuất

36) Nêu khái niệm, cách biểu diễn phân mảnh dọc

37) Cho ví dụ về một quan hệ toàn cục được phân mảnh dọc

38) Nêu các khái niệm: vị từ đơn giản, tập vị từ đơn giản, vị từ giao tối thiểu, tập vị từ giao tối thiểu, vị từ thích hợp, tập vị từ đầy đủ, tập vị từ tối thiểu

39) Nêu quy tắc 1, fi của Pr‟

40) Trình bày giải thuật COM_MIN để tìm tập các vị từ đơn giản là đầy đủ và tối thiểu

41) Trình bày giải thuật PHORIZONTAL để tìm tập các vị từ giao tối thiểu.

42) Nêu phương pháp thiết kế phân mảnh ngang chính theo cách tiếp cận từ trên xuống

43) Nêu phương pháp thiết kế phân mảnh ngang dẫn xuất theo cách tiếp cận từ trên xuống

44) Nêu khái niệm phép kết nối phân tán; Cho ví dụ.

45) Nêu khái niệm và các loại đồ thị kết nối

46) Nêu định nghĩa: Giá trị sử dụng thuộc tính, ma trận sử dụng thuộc tính

47) Nêu các chiến lược thiết kế phân mảnh ngang dẫn xuất

48) Nêu các yêu cầu thông tin của phân mảnh dọc

49) Trình bày giải thuật gom tụ

50) Trình bày giải thuật phân tách

51) Trình bày bài toán định vị

52) Trình bày các yêu cầu thông tin cho bài toán định vị

53) Trình bày mô hình định vị

54) Nêu định nghĩa cây toán tử của một truy vấn, cách xây dựng cây toán từ

55) Trình bày các phép biến đổi tương đương

56) Nêu định nghĩa biểu thức chuẩn tắc của một truy vấn mảnh; Cho ví dụ.

57) Nêu các bước đơn giản hóa các quan hệ được phân mảnh ngang chính

58) Nêu các bước đơ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; Cho ví dụ.

59) Nêu các bước đơn giản hóa cho phân mảnh ngang dẫn xuất

60) Nêu các bước đơn giản hóa cho phân mảnh dọc

61) Nêu các vấn đề của tối ưu hóa truy vấn

62) Nêu các mục tiêu của tối ưu hóa truy vấn

63) Nêu mô hình mới của các truy vấn

64) Nêu các tầm quan trọng của tối ưu hóa truy vấn trong cơ sở dữ liệu phân tán

65) Nêu cách Sử dụng các chương trình nửa kết nối cho các truy vấn kết nối

66) Nêu cách xác định các chương trình nửa kết nối trong SDD-1

67) Nêu các xác định các chương trình nửa kết nối bằng các giải thuật Apers, Hevner và Yao

68) Nêu cách xử lý truy vấn bằng cách sử dụng các phép nối

II. Câu hỏi trắc nghiệm

1. Cơ sở dữ liệu phân tán là sự:

A. Hợp nhất lý thuyết cơ sở dữ liệu và công nghệ mạng máy tính.

B. Hợp nhất công nghệ viễn thông và tin học.

C. Tích hợp công nghệ tin học và cơ sở dữ liệu.

2. Khái niệm hệ cơ sở dữ liệu phân tán bao gồm khái niệm về:

A. Cơ sở dữ liệu phân tán và công nghệ mạng máy tính.

B. Cơ sở dữ liệu tập trung và tối ưu hoá câu hỏi

C. Cơ sở dữ liệu phân tán và hệ quản trị cơ sở dữ liệu phân tán.

3. Cơ sở dữ liệu phân tán là:

A. Một tập các cơ sở dữ liệu có quan hệ với nhau về mặt logic và được phân tán trên một mạng máy tính.

B. Một tập các cơ sở dữ liệu được phân tán trên một mạng máy tính.

C. Một tập các cơ sở dữ liệu được cài đặt lưu trữ trên các máy chủ.

4. Hệ quản trị cơ sở dữ liệu phân tán là:

A. Hệ thống phần mềm quản trị cơ sở dữ liệu phân tán và làm cho sự phân tán đó là trong suốt đối với người sử dụng.

B. Hệ thống phần mềm điều khiển truy nhập cơ sở dữ liệu phân tán .

C. Hệ thống phần mềm thực hiện các phép lưu trữ và tìm kiếm dữ liệu trên mạng máy tính.

5. Đặc trưng của cơ sở dữ liệu phân tán là:

A. Dữ liệu được phân tán trên mạng máy tính và có quan hệ logic. với nhau

B. Tập các file dữ liệu được lưu trữ trên các thiết bị nhớ của mạng máy tính.

C. Tập các file dữ liệu có quan hệ với nhau về mặt logic

6. Độc lập dữ liệu được hiểu là:

A. Tổ chức lưu trữ dữ liệu là trong suốt đối với người sử dụng dụng.

B. Các chương trình ứng dụng không phụ thuộc vào tổ chức lưu trữ dữ liệu.

C. Tổ chức lưu trữ dữ liệu trên các máy chủ của mạng

7. Đặc trưng về độc lập dữ liệu trong các hệ cơ sở dữ liệu phân tán là:

A. Sự trong suốt phân tán

B. Các ứng dụng được phân tán.