Xử Lý Truy Vấn Đối Tượng Phân Tán

đến thông tin về phân bố dữ liệu. Các bước phân rã truy vấn là: chuẩn hóa, phân tích, loại bỏ dư thừa và viết lại truy vấn.

Chuẩn hóa là biến đổi câu truy vấn thành một dạng chuẩn để xử lý tiếp. Có hai dạng chuẩn là dạng chuẩn hội và dạng chuẩn tuyển chính tắc cơ bản:

Dạng chuẩn hội chính tắc là hội của các tuyển:

(𝑝11 ∨ 𝑝12 ⋁ … ∨ 𝑝1𝑛)⋀ … . ⋀(𝑞𝑚1 ∨ 𝑞𝑚2 ⋁ … ∨ 𝑞𝑚𝑛)

 Dạng chuẩn tuyển chính tắc là tuyển của các hội:

(𝑝11 ∧ 𝑝12 ∧ … ∧ 𝑝1𝑛) ∨ … .∨ (𝑞𝑚1 ∧ 𝑞𝑚2 ∧ … ∧ 𝑞𝑚𝑛)

Phân tích câu truy vấn cho phép bỏ các câu truy vấn đã chuẩn hóa nhưng không thể tiếp tục xử lý. Lý do chính để loại bỏ là do các câu truy vấn sai kiểu hoặc sai nghĩa. Một câu truy vấn gọi là sai kiểu nếu nó có một thuộc tính hoặc tên quan hệ chưa được khai báo trong lược đồ toàn cục, hoặc nếu nó áp dụng các phép toán cho các thuộc tính có kiểu không tương thích. Một câu truy vấn gọi là sai nghĩa nếu các thành phần của nó không tham gia vào việc tạo ra kết quả.

Loại bỏ dư thừa được thực hiện bằng cách giản ước lượng từ dư thừa theo các qui tắc.

Viết lại câu truy vấn bằng đại số quan hệ. Bước này chia thành hai bước nhỏ: biến đổi câu truy vấn từ phép tính quan hệ thành đại số quan hệ, và cấu trúc lại câu truy vấn đại số nhằm cải thiện hiệu năng. Chúng ta có thể xây dựng cây toán tử cho câu truy vấn đại số quan hệ, bằng cách áp dụng các qui tắc biến đổi cho phép tạo ra các cây tương đương. Để tìm được câu truy vấn tối ưu, người ta so sánh tất cả các cây dựa trên chi phí. Tuy nhiên số lượng các cây rất lớn nên thường sử dụng thuật toán heuristic trong đó có áp dụng phép toán một 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ác quan hệ trung gian.

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

• Thuật Toán Attrfrag Phân Mảnh Dựa Trên Tương Quan Thuộc Tính
• Phương Án Phân Mảnh Và Cấp Phát Sinh Ra Bởi Thuật Toán Fragallos‌
• Tối Ưu Hóa Biểu Thức Đường Dẫn Trong Cơ Sở Dữ Liệu Hướng Đối Tượng Phân Tán
• Thuật Toán Bloomopt Tối Ưu Hóa Truyền Dữ Liệu Trong Biểu Thức Đường Dẫn
• Tối Ưu Hóa Biểu Thức Đường Dẫn – Thuật Toán Pathexpopt
• Đánh Giá Độ Phức Tạp Và Cài Đặt Thuật Toán

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

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

Đầu vào của tầng hai là mộ t truy vấn đaị số trên quan hệ phân tán. Chứ c nă ng

chủ yếu của tầng này là cuc bộ hoá dữ liệ u truy vấn có sử duṇ g các thông tin dư

liệ u phân tán. Nghia

là tầng cuc

bộ hoá dữ liệ u chiu

trách nhiệ m dic̣ h câu truy vấn

đai

số quan hệ trên quan hệ toàn cuc

sang câu truy vấn đai

số quan hệ trên các

mảnh vậ t lý có sử dun

g các thông tin đươc

lưu trữ trong lươc

đồ phân mảnh. Nó

xác điṇ h mảnh quan hệ nào sẽ đươc

sử duṇ g trong truy vấn và chuyển đổi câu truy

vấn phân tán thành mộ t truy vấn trên mảnh cu ̣thể. Để tao mộ t truy vấn trên mảnh

đươc

thưc

hiệ n bở i hai bướ c:

 Một truy vấn phân tán đươc ánh xa ̣sang mộ t truy vấn trên mảnh bằng

việ c thay thế mỗi quan hệ phân tán bằng chương trình xây dưn

g laị có

chứ a các phép toán đai

số quan hệ thao tác trên mảnh, goi

là chương

trình cuc bộ hoá.

 Truy vấn trên mảnh đươc

đơn giản hoá và xây dưn

g lai

để tao

ra mộ t

truy vấn khác tốt hơn. Quá trình đơn giản hoá và xây dưn

g lai

có thể

đươc

thưc

hiệ n dưa

theo cùng mộ t quy tắc đươc

sử dun

g trong tầng

phân rã.

Phân mảnh đươc

điṇ h nghia

bằng các quy tắc phân mảnh, các qui tắc này

đươc

biểu diên

như các phép toán quan hệ . Mộ t quan hệ toàn cuc

có thể đươc

xây

dưn

g laị bằng cách áp dun

g các quy tắc phân mảnh và dân

xuất mộ t chương trình

cuc

bộ hoá mà các toán haṇ g quan hệ là các mảnh. Để đơn giản, giả thiết không

xét các trường hơp các mảnh nhân bản.

Đối với mỗi kiểu phân mảnh, có những kỹ thuật rút gọn để tạo ra các câu truy vấn tối ưu và đơn giản hơn, ví dụ sau minh họa rút gọn cho phân mảnh dọc.

Ví dụ 3.2: Quan hệ NhanVien có thể được phân chia thành hai mảnh dọc, trong đó thuộc tính MaSoNV được nhân đôi.

𝑁ℎ𝑎𝑛𝑉𝑖𝑒𝑛1 = 𝜋𝑀𝑎𝑆𝑜𝑁𝑉,𝑇𝑒𝑛𝑁𝑉 (𝑁ℎ𝑎𝑛𝑉𝑖𝑒𝑛)

𝑁ℎ𝑎𝑛𝑉𝑖𝑒𝑛2 = 𝜋𝑀𝑎𝑆𝑜𝑁𝑉,𝐶ℎ𝑢𝑐𝐷𝑎𝑛ℎ(𝑁ℎ𝑎𝑛𝑉𝑖𝑒𝑛)

Chương trình cục bộ hóa là:

𝑁ℎ𝑎𝑛𝑉𝑖𝑒𝑛 = 𝑁ℎ𝑎𝑛𝑉𝑖𝑒𝑛1 ⋈𝑀𝑎𝑆𝑜𝑁𝑉 𝑁ℎ𝑎𝑛𝑉𝑖𝑒𝑛2

Các truy vấn trên các mảnh dọc có thể được rút gọn bằng cách xác định các quan hệ trung gian vô dụng và loại bỏ các cây con đã sinh ra chúng. Phép chiếu trên một mảnh dọc không có thuộc tính chung với các thuộc tính chiếu (trừ khóa của quan hệ) sinh ra các quan hệ vô dụng, mặc dù không phải là quan hệ rỗng. Cho trước quan hệ R được định nghĩa trên các thuộc tính A = {A1, …, An} và được

phân mảnh dọc thành Ri = A’(R) trong đó A’ A, ta thể phát biểu qui tắc sau:

D, K(Ri) là vô dụng nếu tập các thuộc tính chiếu D không thuộc A’. Áp dụng qui tắc này bằng cách sử dụng câu truy vấn:

SELECT TenNV

FROM NhanVien

TenNV

⋈MaSoNV

NhanVien1 NhanVien2

TenNV

NhanVien1

Truy vấn gốc

Truy vấn đã rút gọn

Hình 3.2: Rút gọn truy vấn

Câu truy vấn gốc tương đương trên NhanVien1 và NhanVien2. Bằng cách hoán vị phép chiếu với phép kết nối, chúng ta thấy rằng phép chiếu trên NhanVien2 là vô dụng vì TenNV không thuộc NhanVien2. Vì thế phép chiếu chỉ cần thực hiện trên NhanVien1, minh họa như Hình 3.2.

3.1.2.3. Tối ưu hóa truy vấn 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 dữ liệu. 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.Để chọn lựa được một chiến lược tối ưu nói chung, bộtối ưu 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.Đầu ra của bộ tối ưu là một kế hoạch đượ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 dữ liệu hỗ trợ việc thực hiện truy vấn trên các trạm. 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 một chiến lược gần tối ưu và tránh các chiến lược “tồi”.

Chi phí của một chiến lược thực hiện phân tán có thể được biểu diễn hoặc theo tổng chi phí hoặc theo thời gian trả lời.

 Tổng chi phí là tổng của tất cả các thành phần chi phí, bao gồm chi phí truyền thông, chi phí I/O và chi phí CPU.

 Thời gian trả lời truy vấn là thời gian được tính từ khi bắt đầu xử lý đến khi hoàn thành truy vấn.

Công thức xác định tổng chi phí [4]:

Tổng chi phí: Là tổng của tất cả các chi phí CCPU, CI/O. CMSG Total_cost= CCPU * #instr + CI/O * #I/OS + CMSG * #msgs + CTR *#bytes (3.1) Trong đó:

 Total_cost: tổng chi phí

 CCPU: chi phí của một lệnh CPU

 CI/O: chi phí của một xuất/nhập đĩa

 CMSG: chi phí của việc khởi đầu và nhận một thông báo.

 CTR: chi phí truyền một đơn vị dữ liệu từ trạm này đến tram khác.

 #instr: tổng tất cả các lệnh CPU ở các trạm

 #I/OS: số lần xuất/nhập đĩa

 #msgs: số thông báo

 #bytes: tổng kích thước của tất cả các thông báo. Trong công thức trên:

 Hai thành phần chi phí đầu (CCPU, CI/O) là chi phí địa phương.

 Hai thành phần chi phí sau (CMSG, CTR) là chi phí truyền thông.

Công thức cho sự xác định thời gian trả lời [4]:

Response_time = CCPU * seq_#inst +CI/O * seq_#I/OS+ CMSG * seq_#msgs +

+ CTR* seq_#bytes (3.2)

Trong đó các tham số CCPU, CI/O, CMSG, CTR, #instr, #I/Os, #msgs, #bytes như trên, ngoài ra:

 Response_time: thời gian trả lời truy vấn

 seq_#x (x có thể là số lệnh của CPU, I/O, số thông báo, số byte) là số lớn nhất của x khi thực hiện truy vấn một cách tuần tự

Yếu tố chính ảnh hưởng đến hiệu suất của một chiến lược thực thi là kích thước của các quan hệ trung gian sinh ra trong quá trình thực hiện. Khi phép toán tiếp theo đặt tại một trạm khác, quan hệ trung gian phải được truyền qua mạng. Do đó để tối thiểu hoá khối lượng dữ liệu truyền đi, điều cần quan tâm là đánh giá kích thước kết quả trung gian của các phép toán đại số quan hệ. Đánh giá này dựa trên các thông tin thống kê về các quan hệ cơ sở và các công thức ước tính lực lượng của kết quả các phép toán quan hệ.

Để xây dựng các thuật toán tối ưu hóa truy vấn phân tán, chúng ta cần tìm hiểu các kỹ thuật tối ưu trong các hệ thống tập trung vì ba lý do. Thứ nhất, câu truy vấn phân tán phải được dịch thành các câu truy vấn cục bộ, và được xử lý theo những phương pháp tối ưu hóa trong môi trường tập trung. Thứ hai, các kỹ thuật tối ưu hóa phân tán thường là mở rộng của các kỹ thuật tối ưu hóa tập trung. Cuối cùng tối ưu hóa tập trung thông thường đơn giản hơn, công việc hạ thấp chi phí truyền dữ liệu làm cho vấn đề tối ưu hóa phân tán trở nên phức tạp hơn.

Hai kỹ thuật tối ưu hóa tập trung thông dụng nhất là thuật toán INGRES [54] và thuật toán của SYSTEM R [48]. Hai thuật toán này được mở rộng trong môi trường phân tán thành thuật toán INGRES phân tán [23] và R* [47], ngoài ra còn có thuật toán SDD-1 [15], thuật toán AHY [30].

3.2. Xử lý truy vấn đối tượng phân tán

3.2.1. Giới thiệu

Phần lớn các bộ xử lý truy vấn đã được đề xuất đều dùng các kỹ thuật tối ưu hóa đã được phát triển cho các hệ thống quan hệ. Tuy nhiên, có một số vấn đề khiến cho việc xử lý và tối ưu hóa truy vấn trong môi trường đối tượng phức tạp hơn, đó là [4]:

1. Khác với ngôn ngữ truy vấn quan hệ chỉ hoạt động trên một kiểu duy nhất là quan hệ, các hệ đối tượng có các hệ thống kiểu phong phú hơn nhiều. Kết

quả của các phép toán đại số đối tượng thường là các tập đối tượng (hoặc sưu tập) mà chúng có thể thuộc những kiểu khác nhau. Nếu ngôn ngữ đối tượng là đóng đối với những toán tử đại số thì tập các đối tượng đa chủng này có thể làm toán hạng cho những toán tử khác. Điều này đòi hỏi phải phát triển các lược đồ suy diễn kiểu chi tiết để xác định những phương thức nào có thể áp dụng được cho tất cả các đối tượng trong một tập như thế. Hơn nữa các đại số đối tượng thường thực hiện trên các kiểu sưu tập có ý nghĩa khác nhau, đặt thêm những yêu cầu cho các lược đồ suy diễn kiểu.

2. Việc đóng gói các phương thức và dữ liệu trong đối tượng làm nảy sinh hai vấn đề quan trọng. Trước tiên là đánh giá chi phí thực hiện các phương thức khó khăn hơn nhiều so với tính toán chi phí truy xuất một thuộc tính theo đường truy xuất. Thứ hai là việc đóng gói làm nảy sinh các vấn đề liên quan đến khả năng truy cập các thông tin lưu trữ của bộ xử lý truy vấn.

3. Các đối tượng thường có cấu trúc phức tạp, qua đó trạng thái của một đối tượng lại tham chiếu đến một đối tượng khác. Truy xuất các đối tượng như thế phải chứa cả biểu thức đường dẫn. Tối ưu hóa biểu thức đường dẫn là vấn đề chủ chốt trong các ngôn ngữ truy vấn đối tượng. Hơn nữa các đối tượng thuộc các kiểu có liên hệ với nhau thông phân cấp kế thừa. Tối ưu hóa việc truy xuất các đối tượng thông qua phân cấp kế thừa cũng là một bài toán phức tạp.

Một số kiến trúc bộ xử lý truy vấn được đề xuất trong các hệ quản trị CSDL đối tượng: Bộ xử lý truy vấn trong Open OODB [53] gồm có một mô tơ thực thi truy vấn chứa các cài đặt hiệu quả của các thao tác quét, quét chỉ mục, kết nối băm lai và tổng hợp đối tượng phức hợp. Bộ xử lý truy vấn trong dự án EPOP [42] chia không gian tìm kiếm thành các vùng và cần xử lý di chuyển từ vùng này đến vùng khác.

Để thảo luận các vấn đề liên quan đến xử lý truy vấn trong môi trường đối tượng, chúng ta sẽ sử dụng ngôn ngữ truy vấn đối tượng OQL (Object Query Language) là cơ sở. OQL là ngôn ngữ truy vấn CSDL hướng đối tượng đã đề xuất trong ODMG-93 [22].

3.2.2. Các kỹ thuật tối ưu hóa truy vấn đối tượng

Tiếp theo, chúng ta xem xét các khác biệt trong xử lý truy vấn của mô hình đối tượng so với mô hình quan hệ.

3.2.2.1. Tối ưu hóa đại số

Ưu điểm chính của tối ưu hóa đại số là một biểu thức truy vấn đại số có thể được biến đổi bằng cách dùng các tính chất đại số chuẩn như tính bắc cầu, tính giao hoán và tính phân phối. Trong quá trình xử lý, người ta lọai bỏ đi những phương án có thời gian thực thi kém hiệu quả.

Các qui tắc biến đổi phụ thuộc rất nhiều vào từng đại số đối tượng cụ thể vì chúng được định nghĩa riêng biệt cho mỗi đối tượng và cho các tổ hợp của chúng. Các vấn đề tổng quát của việc định nghĩa các qui tắc biến đổi và sự thao tác các biểu thức đại số hoàn toàn tương tự như trong các hệ thống quan hệ nhưng có một khác biệt quan trọng. Các biểu thức truy vấn quan hệ được định nghĩa trên các quan hệ phẳng, còn các truy vấn đối tượng được định nghĩa trên các lớp mà chúng có mối liên hệ kiểu con hoặc hợp phần với nhau. Vì thế chúng ta có thể dùng ngữ nghĩa của những mối liên hệ này trong các bộ tối ưu hóa truy vấn đối tượng để có thêm những biến đối khác.

Ví dụ xét ba toán tử đại số đối tượng là hợp (), giao ( ) và chọn (select, kí hiệu 𝑃𝜎𝐹 < 𝑄1 … . 𝑄𝑘 >), trong đó hợp và giao có ngữ nghĩa như trong lý thuyết tập hợp thông thường, select chọn các đối tượng từ một tập P bằng cách dùng tập các đối tượng Q1…Qk làm tham số. Kết quả của những toán tử này cũng là một

tập các đối tượng. Dưới đây là một số qui tắc biến đổi có thể được áp dụng khi tối ưu hóa nhằm thu được các biểu thức truy vấn tương đương (để ngắn gọn dùng kí hiệu QSet biểu thị cho Q1 … Qk, RSet có ý nghĩa tương tự).

(𝑃𝜎𝐹1 < 𝑄𝑆𝑒𝑡 >)𝜎𝐹2 < 𝑅𝑆𝑒𝑡 >⇔ (𝑃𝜎𝐹2 < 𝑅𝑆𝑒𝑡 >)𝜎𝐹1 < 𝑄𝑆𝑒𝑡 >(3.3) (𝑃 ∪ 𝑄)𝜎𝐹 < 𝑅𝑆𝑒𝑡 >⇔ (𝑃𝜎𝐹 < 𝑅𝑆𝑒𝑡 >) ∪ (𝑄𝜎𝐹 < 𝑅𝑆𝑒𝑡 >) (3.4) (𝑃𝜎𝐹1 < 𝑄𝑆𝑒𝑡 >)𝜎𝐹2 < 𝑅𝑆𝑒𝑡 >⇔ (𝑃𝜎𝐹1 < 𝑄𝑆𝑒𝑡 >) ∩ (𝑃𝜎𝐹2 < 𝑅𝑆𝑒𝑡 >) (3.5)

Qui tắc đầu tiên biểu hiện tính chất giao hoán của select, quy tắc thứ hai diễn tả rằng select phân phối trên phép hợp. Qui tắc thứ ba là một đồng nhất thức

biểu thị rằng select chỉ hạn chế đầu vào của nó và trả về một tập con của tham số thứ nhất.

Hai qui tắc đầu hoàn toàn tổng quát ở chỗ chúng biểu thị cho các hệ thức tương đương kế thừa từ lý thuyết tập hợp. Qui tắc thứ ba là một biến đổi đặc biệt cho một toán tử đại số đối tượng cụ thể, được định nghĩa với một ngữ nghĩa cụ thể.

Trên không gian tìm kiếm và các qui tắc biến đổi, các thuật toán liệt kê được sử dụng để xác định biểu thức có chi phí thấp nhất. Bản chất tổ hợp của các thuật toán liệt kê có lẽ quan trọng hơn trong các hệ quản trị CSDL đối tượng so với CSDL quan hệ. Người ta cho rằng nếu số lượng kết nối trong một truy vấn vượt quá mười thì chiến lược tìm kiếm sẽ không khả thi. Trong các trường hợp như vậy, các thuật toán tìm kiếm ngẫu nhiên có thể được chọn lựa nhằm hạn chế vùng không gian tìm kiếm. Các nghiên cứu về các thuật toán tìm kiếm ngẫu nhiên trong ngữ cảnh CSDL hướng đối tượng là không có. Các chiến lược tổng quát có lẽ không thay đổi được nhưng việc điều chỉnh tham số và định nghĩa không gian các lời giải chấp nhận được cần phải thay đổi.

Một vấn đề cần xem xét ở đây là hàm chi phí. Hàm chi phí có thể định nghĩa một cách đệ qui dựa trên cây xử lý đại số. Nếu cấu trúc nội tại của các đối tượng không thể thấy được bởi bộ tối ưu hóa truy vấn, chi phí của mỗi nút (biểu diễn một phép toán đại sô) phải được định nghĩa. Một cách để định nghĩa nó là yêu cầu các đối tượng “bộc lộ” chi phí của chúng như thành phần giao diện. Chi phí của một thao tác có thể là một phương thức được định nghĩa trên một thao tác được cài đặt như một hàm của (a) thuật toán thực thi và (b) sưu tập mà chúng thực hiện trên đó. Trong cả hai trường hợp một hàm chi phí trừu tượng hơn cho các hành vi được đặc tả vào lúc định nghĩa kiểu để từ đó bộ tối ưu hóa truy vấn có thể tính được chi phí của toàn bộ cây xử lý.

3.2.2.2. Biểu thức đường dẫn

Phần lớn các ngôn ngữ truy vấn đều cho phép dùng các truy vấn với các vị từ chứa các điều kiện về cách truy xuất đối tượng dọc theo các chuỗi tham chiếu. Những chuỗi tham chiếu này gọi là biểu thức đường dẫn (path expression). Ví dụ nếu x là một đối tượng của kiểu xe hơi được định nghĩa trong ví dụ 1.2, biểu thức