Sơ Đồ Quy Trình Xử Lý Truy Vấn [4]

Trong trường hợp CSDL tập trung, việc chuyển đổi câu truy vấn sang các phép đại số quan hệ được tiến hành một cách thuận lợi. Chức năng chính của bộ xử lý tập trung là lựa chọn phép truy vấn đại số quan hệ tối ưu trong các phép đại số tương đương.

Trong môi trường phân tán, các phép đại số quan hệ không đủ để mô tả các giải pháp thực hiện. Nó phải được cung cấp thêm các thao tác để chuyển đổi dữ liệu giữa các vị trí. Việc lựa chọn thứ tự các thao tác đại số quan hệ, bộ xử lý truy vấn cũng phải lựa chọn các vị trí tốt nhất để xử lý dữ liệu và đường truyền thông mà dữ liệu sẽ lưu chuyển. Việc này sẽ làm tăng số các giải pháp lựa chọn cần lựa chọn trong số đó một giải pháp thực hiện. Vì vậy, việc xử lý phân tán càng trở nên khó khăn hơn.

Ví dụ 2.2: Ví dụ này minh họa tầm quan trọng của việc lựa chọn vị trí và cách truyền dữ liệu của một câu truy vấn đại số. Xét câu truy vấn của Ví dụ 2.1:

TênNV (NV MNV (Nhiệmvụ=”Quảnlý”(PC)))

Giả sử rằng các quan hệ NV và PC được phân mảnh ngang như sau:

NV1 = MNV  “E3”(NV) NV2 = MNV > “E3”(NV) PC1 = MNV  “E3”(PC) PC2 = MNV  “E3”(PC)

Các mảnh PC1, PC2, NV1, NV2 theo thứ tự được lưu tại các vị trí 1, 2, 3 và 4 và kết quả được lưu tại vị trí 5 như Hình 2.1 và Hình 2.2.

Vị trí 5

Kết quả = NV1  NV2

Vị trí 3

NV1‟

NV2‟

Vị trí 4

NV1‟= NV

MNVPC‟1

NV2‟= NV

MNVPC‟2

Vị trí 1

PC1‟

PC2‟

Vị trí 2

PC1‟= Nhiệm vụ=”Quản lý”PC1

PC2‟= Nhiệm vụ=”Quản lý”PC2

Hình 2.1: Giải pháp A

Vị trí 5

Kết quả = (NV1  NV2)

MNV Nhiệm vụ=”Quản lý”(PC1  PC2)

PC1

PC2

NV1

NV2

Vị trí 2

Vị trí 3

Hình 2.2: Giải pháp B

Vị trí 1

Vị trí 4

Mũi tên đi kèm ký hiệu quan hệ để chỉ hệ thống sẽ truyền quan hệ kết quả từ vị trí i đến vị trí j. Ví dụ trong chiến lược A, tại vị trí 1, sau khi thực hiện phép chọn trên quan hệ PC1 thỏa mãn biểu thức Nhiệm vụ = “Quản lý”, kết quả PC‟1 sẽ được truyền từ vị trí 1 sang vị trí 3 để tham gia phép kết nối với quan hệ NV1.

Hai giải pháp A và B thực hiện truy vấn là tương đương. Trong đó:

- Giải pháp A: Sử dụng hai quan hệ PC và NV được phân mảnh theo cùng một cách để thực hiện lựa chọn và kết nối các thao tác một cách song song các

phép chọn và kết nối.

- Giải pháp B: Tập trung tất cả các dữ liệu trong toán hạng tại vị trí kết quả trước khi xử lý truy vấn.

Để có thể đánh giá chi phí nguồn tài nguyên của hai giải pháp trên, ta ký hiệu:

- Chi phí để thao tác truy xuất nội bộ là một đơn vị, ký hiệu là tupacc.

- Chi phí để truyền nội bộ là 10 đơn vị, ký hiệu là tuptrans

- Giả sử lực lượng của quan hệ NV và PC là 400 và 1000 bản ghi.

- Giả sử có 20 quản lý trong quan hệ PC. Khi đó, tổng chi phí của giải pháp A là:

1. Tạo ra PC‟ bằng cách chọn trên PC cần (10+10)* tupacc

=	20
2. Truyền PC‟ đến vị trí của NV cần (10+10)*tuptrans	=	200
3. Tạo NV‟ bằng cách nối PC‟ và NV‟ cần (10+10)tupacc2	=	40
4. Truyền NV‟ đến vị trí nhận kết quả cần (10+10)*tuptrans	=	200
Tổng chi phí		460

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

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

Tổng chi phí cho giải pháp B có thể được tính như sau:

1. Truyền NV đến vị trí 5 cần 400*tuptrans = 4.000

2. Truyền PC đến vị trí 5 cần 1000*tuptrans =10.000

3. Tạo ra PC‟ bằng cách chọn trên PC cần 1000*tupacc = 1.000

4. Nối NVvà PC cần 400*20*tupacc = 8.000

Tổng chi phí là 23.000

Như vậy, chi phí để thực hiện giải pháp A thấp hơn chi phí thực hiện giải pháp B.

Tối ưu hóa truy vấn là một vấn đề quan trọng trong việc xử lý truy vấn. Có nhiều phép biến đổi một truy vấn mức cao trên CSDL phân tán thành nhiều giải pháp thực hiện dưới dạng ngôn ngữ mức thấp, nhưng trong đó chỉ có một giải pháp thực hiện có hiệu quả, tối ưu về chi phí sử dụng tài nguyên của mạng, bao gồm chi phí sử dụng bộ nhớ, thời gian xử lý và thời gian truyền dữ liệu.

Chỉ số đánh giá chi phí sử dụng tài nguyên mạng hoặc là tổng thời gian xử lý

các thao tác truy vấn tại các vị trí khác nhau và việc truyền dữ liệu giữa các vị trí hoặc đánh giá theo chỉ số thời gian đáp ứng của truy vấn là tổng thời gian thực hiện truy vấn. Các thao tác có thể được thực hiện đồng thời song song tại các vị trí khác nhau, vì vậy thời gian đáp ứng có thể nhỏ hơn tổng chi phí. Chi phí truyền thông là một trong các nhân tố quan trọng và được quan tâm trong CSDL phân tán.

2.2. Quá trình xử lý truy vấn

Quá trình xử lý truy vấn bao gồm 4 tầng: Phân rã truy vấn, cục bộ hóa dữ liệu, tối ưu hóa toàn cục và tối ưu hóa cục bộ (xem Hình 2.3) [4].

Phân rã truy vấn và cục bộ hóa dữ liệu tương ứng với việc viết lại truy vấn. Chức năng của ba tầng đầu tiên được thực hiện tại một vị trí tập trung và sử dụng các thông tin toàn cục, còn chức năng của tầng thứ 4 được thực hiện ở vị trí cục bộ.

Các vị trí cục bộ

Tối ưu hóa cục bộ

Lược đồ cục bộ

Truy vấn cục bộ đã tối ưu

Phân rã truy vấn

Lược đồ toàn cục

Truy vấn dạng đại số trên các quan hệ phân tán

Cục bộ hóa dữ liệu

Lược đồ mảnh

Truy vấn theo mảnh

Tối ưu hóa toàn cục

Số liệu trên các mảnh

Truy vấn theo mảnh đã tối ưu.

Với các phép toán truyền

Vị trí điều khiển

Hình 2.3: Sơ đồ quy trình xử lý truy vấn [4]

2.2.1. Phân rã truy vấn

Phân rã truy vấn là giai đoạn đầu tiên của quá trình xử lý câu truy vấn, thực hiện việc biến đổi câu truy vấn ở dạng ngôn ngữ bậc cao thành câu truy vấn ngôn ngữ bậc thấp thực thi cho kết quả tương đương. Đặc trưng của giai đoạn này, khi biến đổi không sử dụng các thông tin về dữ liệu đã được phân tán trên các vị trí.

Vì thế, phân rã truy vấn đều giống nhau trong cả hệ thống tập trung và phân tán, câu truy vấn sẽ đúng về ngữ nghĩa và đạt chất lượng theo nghĩa là đã loại bỏ các hành động không cần thiết. Phân rã truy vấn bao gồm bốn bước liên tiếp: Chuẩn hoá, phân tích, loại bỏ dư thừa, viết lại câu truy vấn.

- Chuẩn hóa: Các câu truy vấn bằng các phép tính quan hệ được viết lại dưới dạng chuẩn tắc thích hợp cho các bước tiếp theo. Sự chuẩn hóa một câu truy vấn bao gồm đặt các lượng tử và lượng tử hóa truy vấn bằng cách áp dụng độ ưu tiên các toán tử logic.

- Phân tích: Câu truy vấn đã chuẩn hóa được phân tích về mặt ngữ nghĩa nhằm loại bỏ các câu truy vấn sai càng sớm càng tốt. Tìm ra truy vấn sai chỉ tồn tại với một tập con các phép tính quan hệ. Thông thường sử dụng một loại đồ thị để nắm bắt ngữ nghĩa của câu truy vấn.

- Loại bỏ dư thừa: Câu truy vấn đúng được đơn giản hóa bằng cách loại bỏ các phụ thuộc dư thừa. Truy vấn dư thừa chỉ xuất hiện khi một truy vấn là kết quả của việc biến đổi hệ thống được áp dụng cho truy vấn của người sử dụng.

- Xây dựng lại câu truy vấn: Câu truy vấn phép tính quan hệ được xây dựng lại dưới dạng truy vấn đại số quan hệ bằng các quy tắc biến đổi.

2.2.1.1. Chuẩn hóa câu truy vấn

Mục đích của chuẩn hoá (normalization) là biến đổi câu truy vấn thành một dạng chuẩn để xử lý tiếp. Chuẩn hoá một truy vấn nói chung gồm có đặt các lượng từ và lượng từ hoá vấn tin bằng cách áp dụng độ ưu tiên của các toán tử logic.

Với các ngôn ngữ quan hệ như SQL, biến đổi quan trọng nhất là lượng từ hoá vấn tin (mệnh đề Where), có thể đó là một vị từ phi lượng từ với độ phức tạp nào đó với tất cả các lượng từ cần thiết ( hoặc ) được đặt phía trước. Có hai dạng chuẩn có thể cho vị từ, một có thứ bậc cao cho AND () và loại còn lại cho OR ().

- Dạng chuẩn hội là hội (vị từ ) của các tuyển vị từ (các vị từ ): (p11  p12 …. p1n)  ….. (pm1 pm2 …. pmn)

Trong đó pij là một vị từ đơn giản (nguyên tố).

- Ngược lại, một lượng từ hoá ở dạng chuẩn tuyển như sau: (p11  p12 …. p1n)  …. (pm1 pm2 …. pmn)

Trong dạng chuẩn tắc tuyển, câu truy vấn có thể được xử lý như các câu truy

vấn con hội độc lập, được nối bằng phép hợp (tương ứng với các tuyển mệnh đề). Dạng chuẩn tuyển ít được dùng vì dẫn đến các vị từ nối và chọn trùng nhau.

Dạng chuẩn hội hay dùng trong thực tế.

Ví dụ 2.3: Tìm tên các nhân viên đang làm việc ở dự án P1 trong 12 tháng hoặc 24 tháng.

Câu truy vấn được diễn tả bằng SQL như sau: SELECT TênNV

FROM NV, PC

WHERE NV.MNV = PC.MNV AND PC.MDA = “P1”

AND Thời gian =12 OR Thời gian =24

Lượng từ hoá ở dạng chuẩn hội là:

NV.MNV = PC.MNV  PC.MDA = “P1”  (Thời gian = 12  Thời gian = 24) Lượng từ hoá ở dạng chuẩn tuyển là:

(NV.MNV = PC.MNV  PC.MDA = ”P1”  Thời gian = 12) 

(NV.MNV = PC.MNV  PC.MDA = ”P1”  Thời gian = 24)

Ở dạng sau, xử lý hai hội độc lập có thể là một công việc thừa nếu các biểu thức con chung không được loại bỏ.

2.2.1.2. Phân tích câu truy vấn

Phân tích câu truy vấn cho phép loại bỏ các câu truy vấn đã chuẩn hoá nhưng không thể tiếp tục xử lý được hoặc không cần thiết, do chúng sai kiểu hoặc sai ngữ nghĩa.

- Một câu truy vấn gọi là sai kiểu nếu 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 áp dụng cho các thuộc tính có

kiểu không thích hợp. Ví dụ:

Select MaDA From TenNV >200

Câu truy vấn trên sai kiểu do TenNV có kiểu chuỗi (String) không thể so sánh với kiểu số (200) được.

- Một câu truy vấn gọi là sai ngữ 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ả.

Nếu các truy vấn không chứa các tuyển và phủ định ta có thể dùng đồ thị truy vấn. Truy vấn chứa phép chọn, nối, chiếu.

- Biểu diễn bằng đồ thị truy vấn:

+ Một nút biểu thị quan hệ kết quả

+ Các nút khác biểu thị cho quan hệ toán hạng

+ Đường nối giữa hai nút không phải là quan hệ kết quả biểu thị cho phép kết nối

+ Đường mà nút đích là kết quả sẽ biểu thị cho phép chiếu.

+ Các nút không phải là kết quả sẽ được gán nhãn là một vị từ chọn hoặc vị từ tự kết nối (chính nó).

- Đồ thị nối: Một đồ thị con quan trọng của đồ thị truy vấn, chỉ có các nối.

Ví dụ 2.4: Cho các quan hệ sau:

PC (MaNV, MaDA, NVụ, Tgian) NV (MaNV, TênNV, CVụ)

DA (MaDA, TênDA, Kphí, Đđiểm)

Câu truy vấn “Tìm tên, nhiệm vụ các của những người có Cvụ = ‟TP‟ đã làm việc ở dự án „CAD/CAM‟ trong hơn 3 năm” được viết dưới dạng SQL như sau:

Select TênNV

From PC, NV,DA

Where PC.MaNV = NV.MaNV and PC.MaDA = DA.MaDA

and TênDA = ‟CAD/CAM‟ and CVụ = ‟TP‟ and tgian > 36