Tối ưu hóa câu hỏi (tiếp theo)
Trong mục 8.2 đã trình bày các tư tưởng cơ bản để thực hiện tối ưu một biểu thức quan hệ. Trong phần này sẽ trình bày một lớp các câu truy vấn rất phổ dụng và đã được nhiều hệ thống cài đặt có hiệu quả. Vấn đề đặt ra là khi câu hỏi đã ...
Trong mục 8.2 đã trình bày các tư tưởng cơ bản để thực hiện tối ưu một biểu thức quan hệ. Trong phần này sẽ trình bày một lớp các câu truy vấn rất phổ dụng và đã được nhiều hệ thống cài đặt có hiệu quả. Vấn đề đặt ra là khi câu hỏi đã được biến đổi và tối ưu có tương đương với câu hỏi ban đầu hay không? Lớp câu hỏi sẽ quan sát bao gồm phép chiếu (Projection), phép chọn (Selection) và phép kết tự nhiên (Natural Join) có nghĩa là các biểu thức truy vấn chỉ bao gồm ba phép tính đó. Kết quả cài đặt của nhiều hệ thống (như trong System R) là hiệu quả nhưng không phải là tổng quát cho tất cả.
Như phần trên đã trình bày, trong các phép toán quan hệ thì phép tích Đề các, phép kết (Join) làm mất rất nhiều thời gian xử lý và tốn nhiều bộ nhớ. Vì vậy, nguyên tắc cơ bản của phần này là làm thế nào để biểu thức tối ưu cuối cùng (tương đương với biểu thức ban đầu) có số phép kết là tối thiểu. Do vậy, trong quá trình biến đỗi tương đương, điều quan trọng là loại bỏ được các phép kết không cần thiết.
Để tiện lợi cho quá trình biến đổi, cần làm quen với khái niệm "quan hệ vũ trụ" (universal relation), có thể hiểu một cách đơn giản đó là phép kết tự nhiên của tất cả các quan hệ trong CSDL thành một quan hệ chung.
Câu hỏi hội và bảng
Một câu hỏi hội (conjunctive query) là câu hỏi có dạng:
{a1 ... an½ ($ b1) ... ($ bm) ( p1 ... pk) }
trong đó pi, i =1, ..., k là một trong các dạng:
R(c1, c2, ..., cr), nghĩa là các bộ c1, c2, ..., cr thuộc quan hệ R; cj hoặc là các giá trị a, hoặc các giá trị b hoặc là một trực hằng (literal);
c q d trong đó c và d là các giá trị a hoặc b hoặc là trực hằng; q là một trong các phép so sánh <, £ , >, ³ . Chú ý rằng các phép = và ¹ là không được tính trong danh sách.
Thông thường, câu hỏi được biểu diễn đưới dạng bảng (tableau). Để mô tả khối lượng bảng, trước hết cần giả thiết rằng tập các thuộc tính của các quan hệ đang quan sát là như nhau. Các thuộc tính có cùng tên ở các quan hệ khác nhau đều có cùng một ý nghĩa và các thuộc tính có ý nghĩa khác nhau thì phải mang tên khác nhau.
Định nghĩa bảng
Bảng có thể được xem như một mảng hai chiều và thêm một số điều kiện ràng buộc. Hàng thứ nhất của bảng là danh sách tất cả các thuộc tính. Mỗi thuộc tính tương ứng với một cột của bảng. Hàng thứ hai gọi là hàng đích (summary) bao gồm các giá trị rỗng (blank), các ký hiệu phân biệt (distinguished symbols) và hằng. Ký hiệu phân biệt thường được ký hiệu bằng chữ cái a (thường) biểu diễn trong câu hỏi hội. Các hàng còn lại nhận các ký hiệu a hoặc trống hoặc b, với b là biến không phân biệt (nondistinguished variable) hoặc ký hiệu không phân biệt (nondisguished symbols). Các hàng này biểu diễn các hạng thức của câu hỏi hội dưới dạng R(c1, c2, ..., ck) tức là xác định các bộ trong từng quan hệ. Tại vị trí ci trong cột là tương ứng với thuộc tính thứ i của quan hệ, và sẽ là giá trị trống trong cột của bảng nếu không tương ứng với thuộc tính nào của lược đồ quan hệ R. Các tân từ c q d của câu hỏi hội được xem là các ràng buộc của bảng.
Chú ý bảng đòi hỏi rằng cùng một biến không được phép xuất hiện đồng thời trên hai cột khác nhau của bảng, còn biến phân biệt không xuất hiện ở hàng đích của cột đó.
Như vậy bảng có thể được diễn giải như một câu hỏi hội, tức là một ánh xạ từ các giá trị của các biến quan hệ lên quan hệ. Quan hệ kết quả là quan hệ trên tập thuộc tính với các ký hiệu phân biệt và hằng trên hàng đích.
Gọi T là một bảng và S là tập tất cả các ký hiệu xuất hiện trong T (tức là các biến và hằng). Một đánh giá r cho T liên quan với mỗi ký hiệu của S là một hằng, sao cho nếu một hằng c Ỵ S thì r (c) = c.r đối với hàng đích và các hàng khác của T có thể mở rộng như sau:
Gọi w0 là hàng đích của T, w1...wn là các hàng còn lại thì r (wi) là bộ nhận được nhờ thay thế r (v) cho mỗi biến v xuất hiện trong wi. Bảng được định nghĩa là ánh xạ từ các trạng thái vào các quan hệ trên một tập các thuộc tính. Vậy, nếu T là một bảng, I là một trạng thái thì T(I) là một quan hệ trên tập các thuộc tính mà các thuộc tính đó là những cột có giá trị khác trống trên hàng đích, sao cho
T(I) = {r (w0) với đánh giá r (wi) Ỵ I, 1 £ i £ n }.
Chú ý: Quy định rằng Ỉ là bảng rỗng. Bảng này biểu diễn ánh xạ mỗi trạng thái vào quan hệ rỗng.
Tính tương đương của bảng
Hai bảng T1 và T2 là tương đương, ký hiệu T1 º T2 nếu với mọi tình trạng I, T1(I) = T2(I). Nói rằng T1 chứa trong T2, viết tắt là T1 Í T2 nếu với mọi I, T1(I) Í T2(I). Lưu ý rằng điều kiện cần nhưng không đủ để cho T1 º T2 và T1 Í T2 là các quan hệ được xác định bởi T1 và T2 phải có cùng lược đồ đích (lược đồ đích là tập hợp các thuộc tính biễu diễn hàng đầu tiên của bảng).
Biểu diễn một biểu thức nhờ bảng
Trong phần này trình bày cách thức cấu trúc một bảng để biểu diễn một biểu thức quan hệ bằng các phép Chiếu, Chọn và Kết tự nhiên. Việc cấu trúc bảng trước hết tiến hành cho từng hạng thức của biểu thức, sau đó tổ hợp các bảng lại thành một bảng chung. Các quy tắc thiết lập bảng T cho biểu thức E được thể hiện đệ quy như sau:
(1) Nếu E là lược đồ quan hệ R thì bảng T đối với E chỉ có một hàng và hàng đích, trong đó:
(i) Nếu A Ỵ R thì tại cột cho thuộc tính A của T sẽ có cùng giá trị biến phân biệt cho cả hàng đích và hàng đó:
(ii) Nếu A R thì giá trị của cột tại hàng đích là trống và tại hàng là biến không phân biệt.
(2a) Giả sử biểu thức chọn E có dạng E1 : (A = C) và đã cấu trúc bảng T1 cho biểu thức E1.
(i) Nếu hàng đích của T1 có ký hiệu trống tại cột A thị T = Ỉ
(ii) Nếu có một hằng c ¹ c’ tại A của hàng đích, thì T = Ỉ nế c = c’ thì T = T1.
(iii) Nếu T1 có biến phân biệt a ở cột A của hàng đích thị bảng T đối với E được cấu trúc nhờ việc thay a bằng c tại mọi chỗ mà a xuất hiện trong T1 (tức là các giá trị a xuất hiện trong cột a của bảng T1).
(2b) Giả sử E là phép chiếu có dạng E1 [X] và T1 là bảng của E1. Cấu trúc bảng T cho E bằng cách xóa tất cả các ký hiệu xuất hiện tại hàng đích của tất cả các cột không xuất hiện trong T. Các biến phân biệt trong những cột này được thay bằng biến không phân biệt.
(2c) Giả sử E là biểu thức đại số quan hệ chứa phép kết tự nhiên có dạng E1 * E2 và T1, T2 là các bảng tương ứng của E1 và E2. Gọi S1 và S2 là các ký hiệu của T1 và T2. S1 và S2 có các tập hợp của biến không phân biệt rời nhau nhưng các biến phân biệt là trùng nhau trên các cột tương ứng của phép kết nối.
(i) Nếu T1 và T2 có một số cột trùng nhau nhưng giá trị của chúng tại hàng đích là những hằng số khác nhau T = Ỉ
(ii) Nếu các vị trí tương ứng trong các hàng đích không có các hằng phân biệt thì các hàng của bảng T cho E được bao gồm từ hợp của các hàng thuộc bảng T1 và T2.
Hàng đích của T có các cột của hai bảng, các cột chung nhận các giá trị:
(a) là hằng c nếu một trong hai bảng T1, T2 có hằng c tại cột tương ứng của hàng đích. Trong trường hợp này chúng ta sẽ thay thế mọi giá trị của các biến phân biệt trong cột bằng giá trị hằng c.
(b) là biến phân biệt a nếu không áp dụng được quy tắc (a) nhưng một trong hai giá trị của T1 và T2 tại cột tương ứng có giá trị là a ở hàng đích.
(c) là ký hiệu trống trong những trường hợp còn lại.
Chú ý: Trong trường hợp biểu thức E chứa phép chọn có dạng E1 : (A = B) với A và B tên hai thuộc tính, khi đó đồng nhất các giá trị biến phân biệt trong hàng đích của T cho cả hai cột A và B. Trong tài liệu này chỉ trình bày trường hợp phép chọn E1 : (A = c) với c là một hằng số.
Xét ví dụ: Cho A, B và C là các thuộc tính và giả sử rằng có biểu thức quan hệ:
( ( R(AB) * S(BC) ) : (B = 0) ) [AC]
Theo quy tắc (1) thiết bị lập bảng cho lược đồ R(AB) và lược đồ S(BC) như sau:
| R | A | B | S | B | C | |
| a1 | a2 | Và | a2 | a3 | ||
| a1 | a2 | a2 | a3 |
Theo quy tắc (2c) bảng cho phép kết tự nhiên R(AB) * S(BC) từ hai bảng trên:
| A | B | C |
| a1 | a2 | a3 |
| a1 | a2 | b1 |
| b2 | a2 | a3 |
Và cuối cùng, theo quy tắc (2b), bảng cho phép chọn rồi chiếu ((R(AB) * S(BC)) : (B=0)) [AC] là:
| A | B | C |
| a1 | a3 | |
| a1 | 0 | b1 |
| b2 | 0 | a3 |
Kiểm tra tính tương đương của bảng
Vấn đề đặt ra làm thế nào để tối thiểu hóa số hàng của một bảng mà vẩn tương đương với bảng xuất phát. Như trên đã nêu, cần thiết phải ánh xạ các hàng của bảng xuất phát lên một bảng khác có số hàng ít hơn (ví dụ T1 ® T2) sao cho T2 Í T1 với điều kiện:
Các bảng phải có cùng lược đồ đích (xác định trên cùng một tập thuộc tính) và có cùng biến phânbiệt trên cùng một vị trí của bảng.
Với mỗi phép gán quan hệ cho biến quan hệ tại các hàng của bảng, quan hệ sinh ra nhờ T1 phải là tập con của quan hệ sinh ra nhờ T2.
Để kiểm tra các bảng trong quá trình biến đổi liệu có tương đương với nhau không, trước hết cần thêm khái niệm ánh xạ hàng - hàng (Row - Row Mapping) được gọi là ánh xạ cuốn (Contaiment Mapping).
Gọi T1 và T2 là hai bảng với các tập ký hiệu tương ứng là S1 và S2. Một đồng cấu (Homomorphism) là một ánh xạ y : S1 ® S2 sao cho:
(i) Nếu c là một hàng số thì y (c) = c.
(ii) Nếu a là một biến phân biệt thì y (a) hoặc là biến phânbiệt hoặc là một hằng số xuất hiện trong cột tương ứng của hàng đích của T2.
(iii) Nếu w là một hàng của T1 thì y (W) là một hàng của T2.
Như vậy có thể ánh xạ các hàng của T2 lên các phần tử của một trạng thái I và vì thế đồng cấu y sẽ cho một ánh xạ từ các hàng của T1 lên I. Do đó T2 (I) Í T1(I) với mọi I, từ đó có T2 Í T1.
Ngược lại cũng hoàn toàn đúng, nếu T2 Í T1 suy ra được:
T2(I) Í T1(I).
Có thể hình thức hóa dưới định lý sau đây:
Định lý 8.1:
Gọi T 1 và T 2 là hai bảng với tập các ký hiệu tương ứng là S 1 và S 2 . T 2 Í T 1 khi và chỉ khi chúng có cùng lược đồ đích và có một đồng cấu y : S 1 ® S 2 .
Ánh xạ cuốn
Ánh xạ cuốn là ánh xạ từ các hàng của bảng này lên các hàng của bảng khác mà bảo toàn biến phân biệt và các hằng số nhưng không ánh xạ một ký hiệu lên hai ký hiệu phân biệt. Một cách hình thức có thể nói rằng, nếu T1, T2 là hai bảng, q là ánh xạ từ các hàng của T1 lên các hàng của T2, q được gọi là ánh xạ cuốn nếu:
(a) Với mỗi hàng i của T1, nếu hàng i có biến phân biệt ở cột A thì hàng q (i) của T2 cũng có biến phân biệt hoặc hằng số ở cột A.
(b) Nếu hàng i của T1 có hằng số c ở cột A thì hàng q (i) có c ở cột A.
(c) Nếu hàng i và j của T1 có cùng một biến không phân biệt ở cột A thì hàng q (i) và q (j) có cùng một ký hiệu ở cột đó. Ký hiệu có thể là hằng số, biến phân biệt hoặc biến không phân biệt. ( Chú ý rằng, vẫn có thể q (i) = q (j)). Từ đó có định lý sau:
Định lý 8.2 :
T2 Í T1 nếu và chỉ nếu chúng xác định trên cùng một lược đồ đích và tồn tại một ánh xạ cuốn q từ T1 lên T2.
Chứng minh: (Nếu) Gọi y : S1 ® S2 là ánh xạ ký hiệu - ký hiệu sao cho nếu ký hiệu d xuất hiện ở cột A của hàng r của T1 và ký hiệu d’ xuất hiện ở cột A của hàng q (r) của hàng T2 thì y (d) = d’. Ánh xạ y là phù hợp nhờ điều kiện (c). Điều kiện (i) - (iii) cho y dễ dàng suy trực tiếp. Thật vậy, (a) kéo theo (ii), (b) kéo theo (i) và (iii) được suy ra từ định nghĩa của y và q . Do vậy y là một đồng cấu. Theo định lý 8.1 thì T2 Í T1.
(Chỉ nếu): Từ định lý 8.1, có một đồng cấu y : S1 ® S2 thỏa (i) - (iii). Tồn tại ánh xạ từ các hàng của T2 thỏa (c) suy ra từ (iii), (i) và (ii). Từ kéo theo (a) và (b).
Ví dụ: Cho biểu thức (AB * BC)[AB], có bảng:
| A | B | C | ||
| a1 | a2 | |||
| T1 = | w1 | a1 | a2 | b1 |
| w2 | b2 | a2 | a3 |
Biểu thức AB trên các thuộc tính A, B và C có bảng:
| A | B | C | ||
| T2= | a1 | a2 | ||
| w3 | a1 | a2 | b1 |
Theo chiều xuôi, ánh xạ cả hai hàng w1 và w2 lên w3 là ánh xạ cuốn. Đồng cấu là:
| Trong T1 | Trong T2 |
| a1 | a1 |
| a2 | a2 |
| b1 | b1 |
| b2 | a1 |
| b3 | b1 |
Theo chiều ngược lại, ánh xạ w3 lên w1 và chúnh ta nhận thấy rõ ràng rằng ánh xạ là đúng.
Do vậy AB và (AB*AB) [ AB ] là tương đương.
Ví dụ:
E1 = AB * BC và E2 = (ABC) * ((BC) : (C=0 ))
Bảng tương ứng của E1, E2 là:
| A | B | C | A | B | C | ||
| a1 | a2 | a3 | a1 | a2 | 0 | ||
| T1 = w1 | a1 | a2 | b1 | T2 = w4 | a1 | a2 | 0 |
| w2 | a1 | b2 | a3 | W5 | b1 | a2 | 0 |
| w3 | b3 | a2 | a3 |
Do vậy T2 Í T1 vì có thể tạo một ánh xạ cuốn chuyển w1, w2 và w3 lên w4. Có thể chọn ánh xạ w3 lên w5 nếu muốn. Chiều ngược lại không tồn tại ánh xạ cuốn vì hằng số 0 không thể ánh xạ lên biến. Do đó T1 T2.
Từ đó có định lý sau đây.
Định lý 8.3:
Nếu T 1 và T 2 là hai bảng tương đương và không bảng nào trong hai bảng đó là tương đương với một bảng khác có số dòng ít hơn thì tồn tại một tương ứng 1-1 của các hàng thuộc T 1 đối với các hàng thuộc T2. Đó là ánh xạ cuốn cả hai chiều.
Tối thiểu hóa bảng
Cho T0 là bảng xuất phát. Tm là bảng tương đương với số hàng tối thiểu như có thể. Các hàng của bảng tương đương Tm phải là một tập con của các hàng thuộc T0 (kể cả việc đặt tên lại các ký hiệu). Có định lý sau đây:
Định lý 8.4 :
Nếu T 0 là một bảng, luôn có thể thiết lập được một bảng khác tương đương và có số hàng là tối thiểu được biến đổi từ T 0 nhờ xóa đi không hoặc một số hàng.
Hệ quả :
Mọi bảng với số hàng tối thiểu tương đương với bảng cho trước đều là một (kể cả việc đặt tên lại các ký hiệu)
Từ định lý 8.4 gợi ý một thủ tục tổng quát để tìm bảng tối thiểu. Trước hết tìm ánh xạ có thể để ánh xạ tất cả các hàng lên một tập con của các hàng. Cần chú ý xác định các ánh xạ hàng đích lên hàng đích (tức là đồng nhất trên các biến phân biệt) và bảo toàn các ràng buộc.
Vấn đề tìm ánh xạ để có số hàng ít nhất là một bài toán NP - đầy đủ nhưng số lượng hàng một bảng trong thực tế là nhỏ cho nến không phải luôn luôn là vấn đề thật khó khăn.
