Bài tập tối ưu hoá câu đại số quan hệ năm 2024

Đặt vấn đề

Các ngôn ngữ bậc cao nói chung và ngôn ngữ con dữ liệu nói riêng khi thực hiện trong máy đều mất rất nhiều thời gian. Do đó, trườc khi thực hiện các câu lệnh thuộc các ngôn ngữ đó cần thiết phải biến đổi hợp lý về dạng tương đương, tức là dạng cho cùng một kết quả, để giảm thời gian tính toán. Việc làm đó được gọi là "tối ưu hóa" (Optimiztation). Việc tối ưu hóa không nhất thiết phải được tối ưu trên mọi khả năng có thể có của các cách cài đặt các câu hỏi. Có thể thỏa hiệp giữa thuật giải phức tạp, hoặc / và tốn kém không gian lưu trữ với việc tiết kiệm thời gian xử lý. Chúng ta biết rằng, CSDL có thể là rất lớn, hàng chục ngàn (như hệ quản lý cán bộ - công chức) hay hàng trăm ngàn (như việc quản lý các đối tượng chính sách - có công Cách mạng), hoặc hàng triệu bản ghi (như CSDL quản lý dân cư thành phố Hồ Chí Minh) v.v... Những bài toán này, nếu mỗi thao tác trên một bản ghi chúng ta tiết kiệm được q thời gian thì một câu truy vấn trên 1 bảng đã có thể tiết kiệm được 10n * q thời gian, ở đây n là số bản ghi của bảng. Chúng ta hãy thử tưởng tượng, với bảng lưu trữ các bản ghi có độ dài cố định về nhân khẩu, trong vòng 1 giây máy có thể xử lý cực nhanh 1000 bản ghi, thì để xử lý 4.850.000 nhân khẩu của bảng, máy phải tốn 4.850 giây! Quả là một thời gian khó có thể chấp nhận cho việc chờ đợi nhận kết quả của một câu lệnh truy vấn !

Nói chung, trong việc tối ưu hóa xử lý thông tin, người ta ưu tiên việc tối ưu hóa về thời gian hơn so với việc tối ưu hóa lưu trữ dữ liệu. Trong một số trường hợp, người ta còn phải "hy sinh" cả dạng chuẩn (Normal Form) để đạt tốc độ xử lý nhanh hơn. Trong ví dụ về hệ CSDL quản lý CBVC nêu tại mục 5.3 trong chương V, (ví dụ 5.3.4), mỗi khi cần xem xét đến hệ số lương của một CBVC người ta đều phải tham khảo qua bảng NGẠCH-BẬC-LƯƠNG thông qua phép kết tự nhiên với bảng CBVC trên các thuộc tính Ngạch và Bậc. Nếu trong danh sách CBVC chúng ta bổ sung cột Hệ-số-lương nữa thì dẫn tới việc trùng lắp (và dư thừa) thông tin - nguy cơ dẫn đến việc mất tính nhất quán dữ liệu - đồng thời không đảm bảo dạng chuẩn tốt cho bảng này và buộc phải bổ sung RBTV :

CBVC [Ngạch,Bậc, Hệ-số-lương] Í NGẠCH-BẬC-LƯƠNG [Ngạch,Bậc, Hệ-số-lương].

Bộ nhớ thứ cấp (băng từ, đĩa từ ...) của máy tính giờ đây không còn là vấn đề làm mọi người phải bận tâm khi xây dựng các hệ CSDL lớn. Dung lượng một đĩa cứng đã đạt tới hàng chục Giga bytes. Tuy nhiên vẫn có thể tồn tại nguy cơ thiếu không gian tính toán cho máy nếu không lưu tâm đến việc tối ưu hóa các câu hỏi trước khi đưa vào máy và yêu cầu máy thi hành. Một nguyên nhân dẫn tới điều này là việc thực hiện các phép kết nối và phép tích Đề-các của các quan hệ. Chúng ta đã biết, tích Đề-các (đã trình bày tại điểm 5.2.4, mục 5.2,) và các phép kết (q -Join, Natural Join, Equi Join, Outer Join - đã trình bày tại điểm 5.3.3 mục 5.3 và mục 5.4 của Chương V) đòi hỏi khá nhiều không gian lưu trữ và thời gian xử lý.

Cho R (A1, A2, ..., An) và S (B1, B2, ..., Bm) là hai quan hệ định nghĩa trên 2 tập thuộc tính { A1, A2, ..., An } và { B1, B2, ..., Bm }. Nếu R có N1bộ giá trị và S có N2 bộ giá trị thì tích Đề-các sẽ cho kết quả là một bảng mới gồm m + n thuộc tính với N1 * N2 bộ giá trị. Chỉ cần mỗi quan hệ có 10 thuộc tính chứa số lượng bộ giá trị khá khiêm tốn, 1000 bộ, thì tích Đề-các đã tạo ra bảng trung gian có số thuộc tính là 20 và số lượng bộ giá trị là 1.000.000. Nếu mỗi field chỉ rộng 5 bytes thôi (mà trên thực tế thì rất ít có những quan hệ nhỉ như vậy) thì quan hệ trung gian này đã "ngốn" mất 1/10 Giga bytes ! Đương nhiên là, thời gian truy nhập CSDL và truy xuất đĩa từ để tạo ra ngần ấy bản ghi cũng không phải là ít. Sự bùng nổ số lượng và "bành trướng" kích thước (chiều dài) bản ghi này đặt chúng ta vào việc phải nghiên cứu để tối ưu câu hỏi trước khi đưa vào máy tính toán.

Chương này chủ yếu trình bày một vài phương pháp tối ưu hóa các biểu thức quan hệ, đặc biệt là xử lý biểu thức có liên quan tới phép kết nối và tích Đề-các. Sau đó sẽ trình bày chi tiết một phương pháp tối ưu hóa cho một lớp phổ cập các biểu thức quan hệ. Nguồn tài liệu tham khảo chủ yếu dựa trên các lý thuyết và ví dụ minh họa trong chương VI của PGS.PTS.Lê Tiến Vương [8].

Các nguyên tắc tổng quát để tối ưu hóa một câu hỏi.

Chúng ta hãy xét một ví dụ đơn giản sau đây :

Cho hai quan hệ R(A,B) với n bản ghi và S (C,D) với m bản ghi. Tích Đề-các của R và S là một quan hệ Q (A,B,C,D) có n * m bản ghi (Xem 5.2.4. Phép tích Đề-các của 2 quan hệ, mục 5,2, Chương V). Chúng ta có câu hỏi "Lấy giá trị của thuộc tính A sao cho B=C và D=50". Câu hỏi được viết lại dưới dạng ngôn ngữ đại số quan hệ như sau:

( ( R(A,B) x S(C,D) ) : (B=C D=50) ) [A]

Nếu đưa phép chọn D=50 vào bên trong phép tích Đề-các sẽ được:

(( R (A,B) x ( S(C,D) : (D = 50) ) ) : (B=C) ) [A]

và sau đó chuyển phép chọn B=C của tích Đề-các thành phép "kết nối bằng" chúng ta thu được:

Rõ ràng, phép tính cuối cùng sẽ đỡ tốn kém thời gian hơn rất nhiều.

-Cụ thể là: Chỉ chọn trên quan hệ S những bộ có giá trị D=50 thì số bộ lấy ra sẽ ít hơn toàn bộ số bộ của cả quan hệ trên S. Số bộ được chọn ra xong từ S mới đem kết nối với quan hệ R. Phép kết nối này chỉ chọn ra bộ nào thuộc R mà có giá trị tại B là bằng bộ có giá trị tại C thuộc S mới được lấy ra để kết lại với nhau. Điều đó hoàn toàn nhanh hơn là lấy tích Đề-các của R x S rồi mới chọn trong kết quả những bộ có giá trị tại B bằng giá trị tại C.

Việc biến đổi câu hỏi thành câu hỏi tương đương như ví dụ nêu trên là một minh họa cho việc giảm bớt thời gian trả lời câu hỏi bằng cách giảm bớt số lần cần truy nhập tới bộ nhớ thứ cấp dựa trên nguyên tắc thực hiện phép chọn càng sớm càng tốt. Trình tự thực hiện các phép tính sẽ đóng một vai trò quan trọng quá trình tổ chức câu hỏi.

10. D. Ullman [5] trong các kết quả nghiên cứu công bố lần đầu tiên của mình đã trình bày 6 chiến lược tổng quan cho việc tối ưu hóa câu hỏi như sau:

-. Thực hiện phép chọn càng sớm càng tốt.

Biến đổi câu hỏi để đưa phép chọn vào thực hiện trước nhằm làm giảm bớt kích cỡ của kết quả trung gian và do vậy chi phí phải trả cho việc truy nhập bộ nhớ thứ cấp cũng như lưu trữ của bộ nhớ chính sẻ nhỏ đi.

-Tổ hợp những phép chọn xác định với phép tích Đề-các thành phép kết nối.

Như đã biết, phép kết nối, đặc biệt là phép kết nối bằng (Equi Join) có thể được thực hiện ít tốn kém hơn nhiều so với phép tích Đề-các trên cùng các quan hệ. Nếu kết quả của tích Đề-các RxS là đối số của phép chọn và phép chọn liên quan tới các phép so sánh giữa các thuộc tính của R và S thì rõ ràng phép tích Đề-các là phép kết nối.

-Tổ hợp dãy các phép toán quan hệ một ngôi như các phép chọn và phép chiếu.

Một dãy các phép một ngôi như phép chọn hoặc phép chiếu mà kết quả của chúng phụ thuộc vào các bộ của một quan hệ độc lập thì có thể nhóm các phép đó lại.

-Tìm các biểu thức con chung trong một biểu thức.

Nếu kết quả của một biểu thức con chung (tức là biểu thức xuất hiện nhiều hơn một lần) là một quan hệ không lớn và nó có thể được đọc từ bộ nhớ thứ cấp với ít thời gian thì nên tính toán trước biểu thức đó chỉ một lần. Nếu biểu thức con chung có liên quan tới một phép kết nối thì trong trường hợp tổng quát không thể thay đổi được nó bằng cách "đẩy" phép chọn vào trong.

Điều đáng quan tâm là, các biểu thức con chung có tần số xuất hiện lớn thường được biểu diễn trong các VIEW (khung nhìn) của người sử dụng, bởi vì, để thực hiện các câu hỏi đó cần phải thay thế nó bằng một biểu thức cố định cho VIEW.

- Tiền xử lý các quan hệ / bảng (Table Preprocessing).

Có hai vấn đề quan trọng cần xử lý trước cho các quan hệ là sắp xếp trước các bộ giá trị theo thứ tự vật lý và sắp xếp lôgíc - tức là thiết lập các bảng chỉ mục (Index) cho các bản ghi. Khi đó việc thực hiện các phép toán có liên quan tới hai quan hệ (các phép toán hai ngôi) sẽ nhanh hơn rất nhiều.

- Đánh giá trước khi thực hiện tính toán.

Mỗi khi cần chọn trình tự thực hiện các phép toán trong biểu thức, hoặc chọn một trong hai đối số của một phép hai ngôi, thì cần tính toán xem chí phí (Cost) thực hiện các phép tính đó (thường tính theo số phép toán, thời gian, hoặc/và dung lượng bộ nhớ cần thiết so với kích thước của các quan hệ, từ đó xác định được chi phí tổng thể phải trả cho các cách khác nhau khi thực hiện các câu hỏi.

Dựa vào các nguyên tắc nêu trên, chúng ta sẽ biến đổi câu truy vấn thành câu hỏi tương đương tối ưu hơn, để việc thực hiện có chi phí xử lý ít hơn. Nhưng trước khi có thể "tối ưu hóa" các biểu thức, cần làm rõ khái niệm khi nào thì hai biểu thức được gọi là tương đương. Trong phần sau sẽ cho biết một cách hình thức khái niệm tương đương.

Biểu thức tương đương.

Trước hết, xem xét lại khái niệm về định nghĩa quan hệ đã được sử dụng trong các chương 2 và 3 để thấy sự tương đương của các quan hệ dựa theo định nghĩa. Với các định nghĩa khác nhau chúng cho các tính chất toán học cũng khác nhau. Nếu quan niệm quan hệ là một tập hợp các bộ (k - bộ) với k cố định, khi đó hai quan hệ là tương đương khi và chỉ khi chúng có cùng một tập các bộ. Với quan niệm quan hệ là tập các ánh xạ từ tập tên thuộc tính vào tập giá trị, thì khi đó hai quan hệ là bằng nhau nếu chúng có cùng một tập ánh xạ. Định nghĩa thứ nhất có thể biến đổi sang định nghĩa thứ hai bằng cách thay đổi tên thuộc tính thành tên các cột trong bảng và, ngược lại đổi từ định nghĩa thứ hai sang định nghĩa thứ nhất bằng cách cố định thứ tự cho các thuộc tính. Sau đây sẽ sử dụng định nghĩa thứ hai, nghĩa là, quan hệ là một tập ánh xạ từ tập thuộc tính vào tập các giá trị. Một ngôn ngữ truy vấn hiện hữu luôn luôn đòi hỏi phải biết tên của các cột trong một quan hệ. Do đó, tên các thuộc tính trong một quan hệ phải là một biến trong một biểu thức và cũng thể hiện ở kết quả của biểu thức.

+ Biểu thức trong ngôn ngữ đại số quan hệ có các hạng thức là biến quan hệ (relation variables) R1,...., Rn; các quan hệ hằng (constant relation), được xác định như là một ánh xạ từ các k-bộ của các quan hệ (r1, ..., rk) trong đó ri là quan hệ trên lược đồ ri và thay thế ri vào Ri khi đánh giá biểu thức. Hai biểu thức E1 và E2 được gọi là tương đương (Equivalent), viết tắt là E1 º E2, nếu chúng biểu diễn cùng một ánh xạ, nghĩa là, nếu chúng ta thay thế cùng các quan hệ cho tên các lược đồ tương ứng ở hai biểu thức E1 và E2, thì chúng sẽ cho ra cùng một kết quả.

Với định nghĩa tương đương này chúng ta có một phép chuyển dịch đại số thông thường sau đây:

Các quy tắc liên quan tới phép kết và tích Đề-các.

Œ Quy tắc giao hoán của phép kết nối và tích Đề-các

Nếu E1 và E2 là hai biểu thức quan hệ và F là điều kiện trên các thuộc tính của E1 và E2 thì:

// Tính giao hoán của kết

E1 * E2 º E1 * E2 // Tính giao hoán của kết bằng

E1 x E2 º E1 x E2 // Tính giao hoán của tích Đề-các.

Chúng ta chứng minh quy tắc giao hoán của phép kết nối. Giả sử E1 có các thuộc tính A1, ..., An; E2 có các thuộc tính B1, ..., Bm và các thuộc tính A, B không nhất thiết phải là phân biệt. Gọi r1 và r2 là hai quan hệ tương ứng của E1và E2. Giá trị của E1 E2 là tập các ánh xạ a từ A1 ... An, B1 ... Bm vào tập giá trị sao cho các ánh xạ m 1 Ỵ r1 và m 2 Ỵ r2 thỏa mãn điều kiện:

a [Ai] = m 1[Ai], i = 1,2,...,n

a [Bi] = m 1[Bi], i = 1,2,...,m

và điều kiện F là đúng khi thay a [C] cho mỗi thuộc tính C trong F.

Nếu biểu diễn E2 E1 cũng như trên, chúng ta dễ dàng nhận thấy hai phép kết trên cho chính xác cùng một tập kết quả. Do vậy hai biểu thức là tương đương.

Chú ý: Nếu quan niệm quan hệ là tập các bộ (có thứ tự thuộc tính cố định) thì phép q -kết, kết tự nhiên và tích Đề-các không thể giao hoán được vì thứ tự các thuộc tính trong quan hệ kết quả bị thay đổi.

- Quy tắc kết hợp của phép kết nối và tích Đề-các.

Nếu E1, E2 và E3 là các biểu thức quan hệ: F1, F2 là điều kiện thì:

(E1 * E2) * E3 E1 * (E2 * E3)

(E1 * E2) x E3 E1 x (E2 x E3)

Việc kiểm tra tính tương đương của các quy tắc trên khá dễ dàng.

Các quy tắc liên quan tới phép chọn và phép chiếu

Dãy các phép chiếu có thể tổ hợp lại thành một phép chiếu, biểu diễn theo các trường hợp sau:

Ž Dãy các phép chiếu

(E [B1B2 ... Bm]) [A1A2 ... An] E [A1 ... An]

Ở đây, các thuộc tính A1, ..., An phải nằm trong tập các thuộc tính B1, ..., Bm. Ngữ nghĩa của việc biến đổi tương đương này là: Nếu thực hiện một phép chiếu biểu thức quan hệ E trên tập các thuộc tính B, rồi sau đó thực hiện tiếp phép chiếu trên tập con các thuộc tính A Ì B của quan hệ vừa tìm được, thì kết quả của dãy phép chiếu này hoàn toàn tương đương với một phép chiếu biểu thức quan hệ E trên tập thuộc tính A.

Tương tự, dãy các phép chọn có thể tổ hợp thành một phép chọn để kiểm tra tất cả các điều kiện cùng một lúc và được biểu diễn như sau:

- Dãy các phép chọn:

( ((E : (f1)) : f2) : ... ) : fn E : (f1 f2 ... fn)

Ngữ nghĩa: Việc lần lượt thực hiện các phép chọn trên quan hệ kết quả của một phép chọn trước đó đối với biểu thức quan hệ E là tương đương với việc chọn trên E các bộ giá trị thỏa mãn đồng thời tất cả các điều kiện chọn f1, f2 ... fn.

- Giao hoán phép chọn và phép chiếu:

(E [A1... An] : (f))(E : (f)) [A1 ... An]

Một cách tổng quát hơn, nếu điều kiện chọn f liên quan tới các thuộc tính B1, ... Bm mà không nằm trong tập thuộc tính A1, ... An thì:

(E [A1 ... An]) : (f) (E [A1 ... An B1 ... Bm ]) : (f)) [A1 ... An]

-Giao hoán phép chọn và tích Đề-các:

Nếu tất cả các thuộc tính của F là thuộc tính của E1 thì:

(E1 x E2) : (f) (E1 : (f)) x E2

Từ đó dễ dàng suy ra rằng, nếu F có dạng f = f1 L f2 trong đó f1 chỉ liên quan tới các thuộc tính của E1; f2 chỉ liên quan tới các thuộc tính của E2 , thì có thể sử dụng các luật Œ và ‘ để có:

(E1 x E2) : (f) (E1 : (f1)) x (E2 : (f2))

Hơn nữa nếu f1 chỉ liên quan tới các thuộc tính của E1, nhưng f2 liên quan tới các thuộc tính của cả E1 và E2 thì:

(E1 x E2) : (f) ((E1 : (f1)) x E2) : (f2)

-Giao hoán phép chọn và một phép hợp:

Nếu có biểu thức E = E1 E2; có thể giả thiết thêm rằng, các thuộc tính của E1 và E2 có cùng tên như của E hoặc ít nhất mỗi thuộc tính của E là phù hợp với một thuộc tính duy nhất của E1 và một thuộc tính duy nhất của E2 . Khi đó:

(E1 E2) : (f) (E1 : (f))(E2 : (f))

Nếu tên các thuộc tính của E1 và hoặc E2 khác với tên thuộc tính của E thì trong f ở vế phải của công thức trên cần thay đổi để sử dụng tên cho phù hợp.

-Giao hoán phép chọn và một phép hiệu tập hợp

(E1 - E2) : (f) (E1 : (f)) - (E2 : (f))

Như đã nêu trong luật ’ , nếu tên các thuộc tính của E1 vàE2 là khác nhau thì cần thay thế các thuộc tính trong f ở vế phải biểu thức tương đương tương ứng với E1. Chú ý rằng, phép chọn (E2 : (f)) có thể là không cần thiết. Trong nhiều trường hợp, việc thực hiện phép chọn (E2 : (f)) trước sẽ có hiệu quả hơn là tính toán trực tiếp với E2 vì kích cỡ quan hệ lúc đó sẽ bé đi rất nhiều.

Các quy tắc nêu trên nói chung là đẩy phép chọn xuống trước phép kết nối vì phép kết nối thường thực hiện lâu như phép tích Đề Các. Quy tắc đẩy phép chọn xuống trước phép kết nối suy ra từ quy tắc và ‘ . Quy tắc đẩy phép chiếu xuống trước phép tích Đề-các hoặc phép hợp cũng tương tự như quy tắc ‘ và ’ . Chú ý là không có phương pháp tổng quát cho việc đẩy phép chiếu xuống trước phép hiệu các tập hợp.

-Giao hoán một phép chiếu với một phép tích Đề-các:

Gọi E1, E2 là hai biểu thức quan hệ, A1 ... An là tập các thuộc tính trong đó B1, ... Bm là các thuộc tính của E1, các thuộc tính còn lại C1, ..., Ck thuộc E2. Khi đó:

(E1 x E2) [A1 ... An] E1 [B1 ... Bm] x E2 [C1 ... Ck]

-Giao hoán một phép chiếu với một phép hợp:

(E1 E2) [A1 ... An] E1[A1 ... An] E2[A1 ... An]

Như đã nêu trong luật ’ , nếu tên các thuộc tính của E1 và / hoặc E2 là khác với các thuộc tính trong E1 E2 thì cần thay A1 ... An bên vế phải bằng các tên phù hợp.

Ví dụ về một thuật toán tối ưu hóa biểu thức quan hệ.

Tới đây có thể áp dụng các quy tắc nêu trong mục 8.2 để có thể tối ưu hóa các biểu thức quan hệ. Biểu thức "tối ưu" kết quả phải tuân theo các nguyên tắc đã nêu ở phần 8.1 mặc dù rằng các nguyên tắc đó không có nghĩa là bảo đảm để tối ưu cho mọi trường hợp tương đương.

Lưu ý rằng, luôn luôn đẩy phép chọn và phép chiếu xuống mức càng sâu càng tốt trong cây biểu diễn biểu thức quan hệ nhằm tạo nên một dãy các phép chọn cũng như phép chiếu để từ đó có thể tổ chức thành một phép chọn theo sau một phép chiếu. Nhóm các phép chọn và phép chiếu lại trong một nhóm để thực hiện trước các phép tính hai ngôi như phép hợp, tích Đề-các, hiệu tập hợp v.v...

Có một số trường hợp đặc biệt xảy ra khi một phép tính hai ngôi có các hạng thức chứa phép chọn và / hoặc phép chiếu được áp dụng đối với lá của cây biểu diễn biểu thức. Khi đó cần xem xét cẩn thận tác động của phép tính hai ngôi vì một số trường hợp cần phải liên kết phép chọn hoặc phép chiếu với phép hai ngôi đó.

Kết quả đầu ra (Output) của thuật toán là một chương trình bao gồm các bước như sau:

-Áp dụng của một phép chọn hoặc một phép chiếu đơn giản.

-Áp dụng của một phép chọn và một phép chiếu hoặc

- Áp dụng của một tích Đề-các, phép hợp hoặc phép hiệu tập hợp cho hai hạng thức mà trước đó các phép chọn hoặc các phép chiếu đã được áp dụng cho một hoặc cả hai hạng thức.

Hãy xét một CSDL quản lý thư viện bao gồm các quan hệ sau đây:

-. SÁCH (Tên-sách, Tác-giả, Nhà_XB, Mã-sách): là quan hệ về các loại sách trong thư viện.

-NHÀ-XUẤT-BẢN (Nhà_XB, Địa-chỉ, Thành-phố): quan hệ về nhà xuất bản.

-ĐỘC-GIẢ (Tên-ĐG, Đchỉ-ĐG, Tphố-ĐG, Số-thẻ) : quan hệ về độc giả

- MƯỢN-SÁCH (Số-thẻ, Mã-sách, Ngày-mượn): quan hệ sổ theo dõi mượn.

Để lưu trữ thông tin về sách có thể giả thiết thêm rằng có một khung nhìn (VIEW) theo dõi các sách được mượn, TD-MƯỢN, bao gồm một số thông tin bổ sung về sách được mượn, là kết quả của kết nối tự nhiên của quan hệ SÁCH, ĐỘC-GIẢ và MƯỢN-SÁCH, chẳng hạn được xác định qua biểu thức quan hệ:

((SÁCH x ĐỘC-GIẢ x MƯỢN-SÁCH) : (f)) [{S}]

Ở đây:

f ::= (ĐỘC-GIẢ.Số-thẻ = MƯỢN-SÁCH.Số-thẻ) (SÁCH.Mã-sách = MƯỢN-SÁCH.Mã-sách).

và S là tập các thuộc tính:

S = { Tên-sách, Tác-giả, Nhà_XB, SÁCH.Mã-sách, Tên_ĐG, Đchỉ-ĐG, Tphố-ĐG, ĐỘC-GIẢ.Số-thẻ, Ngày-mượn }.

-Câu hỏi: Cho danh sách những cuốn sách đã cho mượn trước ngày 27/03/1999. Biểu thức quan hệ được viết như sau:

(TD-MƯỢN : (Ngày-mượn < 27/03/1999) ) [ Tên-sách ]

Hình cây của biểu thức trên được biểu diễn bằng hình 8.1. Xin lưu ý là, các phép toán nằm ở phiá dưới là các phép toán được thược hiện trước các phép toán ở phiá trên của cây.

Hình 8.1: Biểu diễn cây của biểu thức hỏi

Thay thế các giá trị f và S vào biểu thức hỏi có được cây biểu diễn của biểu thức quan hệ như trong hình 8.1

-Bước thứ nhất của tối ưu là tách phép chọn f thành hai phép chọn với điều kiện:

SÁCH.Mã-sách = MƯỢN-SÁCH.Mã-sách

và

MƯỢN-SÁCH.Số-thẻ = ĐỘC-GIẢ.Số-thẻ

Bây giờ chúng ta có 3 phép chọn. Cần "đẩy" chúng xuống mức thấp hơn chừng nào còn có thể được.

Phép chọn với điều kiện Ngày-mượn < 27/03/1999 được đẩy xuống dưới phép chiếu và hai phép chọn kia bằng cách áp dụng các quy tắc (hoặc luật) và . Phép chọn đầu được áp dụng cho tích Đề-các ((MƯỢN-SÁCH x ĐỘC-GIẢ) x SÁCH). Vì thuộc tính Ngày-mượn trong phép chọn chỉ có ở quan hệ MƯỢN-SÁCH nên có thể thay thế:

((MƯỢN-SÁCH x ĐỘC-GIẢ) x SÁCH) : (Ngày-mượn < 27/03/1999)

bằng biểu thức:

((MƯỢN-SÁCH x ĐỘC-GIẢ) : (Ngày-mượn < 27/03/1999)) x SÁCH)

và tiếp tục đẩy xuống nữa, cuối cùng ta được biểu thức:

(((MƯỢN-SÁCH : (Ngày-mượn < 27/03/1999)) x ĐỘC-GIẢ) x SÁCH)

Như vậy đã đẩy được phép chọn theo ngày mượn sách này xuống sâu như có thể.

Bây giờ tiếp tục đẩy phép chọn với điều kiện

Như vậy đã đẩy được phép chọn theo ngày mượn sách này xuống sâu như có thể.

Bây giờ tiếp tục đẩy phép chọn với điều kiện SÁCH.Mã-sách = MƯỢN-SÁCH.Mã-sách. xuống mức thấp nhất nếu có thể. Không thể đẩy phép chọn này xuống dưới tích Đề-các vì nó liên quan tới một thuộc tính của quan hệ SÁCH và một thuộc tính thuộc quan hệ MƯỢN-SÁCH. Do vậy phép chọn:

: MƯỢN-SÁCH.Số-thẻ = ĐỘC-GIẢ.Số-thẻ

Số-thẻ

có thể đẩy xuống để áp dụng cho tích Đê-các:

(MƯỢN-SÁCH x ĐỘC-GIẢ) : ( : (Ngày-mượn < 27/03/1999)

Chú ý rằng MƯỢN-SÁCH.Số-thẻ là tên một thuộc tính của phép chọn:

MƯỢN-SÁCH : (Ngày-mượn < 27/03/1999).

-Bước tiếp theo: Tổ hợp hai phép chiếu thành một phép chiếu là [Tên-sách] nhờ luật Ž . Kết quả được cho như trong hình 8.2. Sau đó áp dụng quy tắc mở rộng thay thế:

:(MƯỢN-SÁCH.Số-thẻ = ĐỘC-GIẢ.Số-thẻSố-thẻ) và chiếu [Tên_sách]

nhờ dãy phép toán:

[Tên-sách, SÁCH.Mã_sách, MƯỢN-SÁCH.mã-sách ] (1)

:(SÁCH.Mã_sách = MƯỢN-SÁCH.Mã-sách) (2)

rồi chiếu để lấy tên sách:

[Tên-sách] (3)

Áp dụng quy tắc ” để thay thế biểu thức đầu tiên, biểu thức số (1), của phép chiếu nhờ phép chiếu:

[Tên-sáchTên-sách, SÁCH.Mã_sách]

để áp dụng cho quan hệ SÁCHvà [MƯỢN-SÁCH.mã-sách] áp dụng cho hạng thức phiá trái của tích Đề-các trong hình 8.2.

Phép chiếu cuối và phép chọn có thể áp dụng quy tắc mở rộng � để có dãy:

[ áp dụng cho hạng thức phiá trái của tích Đề-các trong hình 8.2.

Phép chiếu cuối và phép chọn có thể áp dụng quy tắc mở rộng � để có dãy:

[MƯỢN-SÁCH.Mã_sáchMã_sách, MƯỢN-SÁCH.Số-thẻSố-thẻ, ĐỘC-GIẢ.Số-thẻ] (5)

: (MƯỢN-SÁCH.Số-thẻ = ĐỘC-GIẢ.Số-thẻ) (6)

[MƯỢN-SÁCH.Mã_sách]Mã_sách] (7)

Phép chiếu đầu, số (5), được phân tách chuyển xuống tích Đề-các nhờ quy tắc ” .

Một phần phép chiếu ĐỘC-GIẢ.Số-thẻ xuống hạng thức ĐỘC-GIẢ vì là thuộc tính của quan hệ này.

Hình 8.2 Cây với tổ hợp phép chọn và phép chiếu

Phần còn lại là phép chiếu để lấy 3 thuộc tính:

[ MƯỢN-SÁCH.Mã_sách, MƯỢN-SÁCH.Số-thẻSố-thẻ, Ngày-mượn ]

được đẩy xuống hạng thức thứ MƯỢN-SÁCH. Các thuộc tính không phù hợp sẽ bị loại bỏ. Biểu diễn cây cuối cùng của biểu thức như trong hình 8.3.

Nhóm các phép tính bằng đường mũi tên gián đoạn. Mỗi tích Đề-các được tổ hợp với phép chọn để tạo thành một phép kết nối bằng nhau (Equi Join) rất có hiệu quả. Đặc biệt phép chọn trên quan hệ MƯỢN-SÁCH và phép chiếu của ĐỘC-GIẢ để lấy thuộc tính Số-thẻ ở phía dưới là đủ để tổ hợp với tích Đề-các. Thứ tự thực hiện của cây biểu thức trong các hình 8.3, 8.2 và 8.3 là từ dưới lên: Nhóm các phép toán nằm ở phía dưới được thực hiện trước các phép toán ở phiá trên.

Hình 8.3 Cây kết quả biểu diễn việc phân nhóm các biểu thức.

Một thuật toán để tối ưu hóa câu hỏi trong ngôn ngữ ĐSQH

Ví dụ trên cho ta một minh họa về việc chuyển đổi một câu hỏi bằng ngôn ngữ Đại số quan hệ về dạng tương đương tốt hơn (hay tối ưu hơn). Phương pháp trên tập trung chủ yếu vào các phép chiếu, phép chọn và tích Đề-các, với mục đích làm sao "đẩy" được phép chọn và phép chiếu xuống mức thấp nhất, tức là thi hành các phép toán này càng sớm càng tốt, nếu có thể. Tiếp theo, kết hợp các phép chọn với tích Đề-các thành phép kết tự nhiên để làm giảm các kết quả trung gian. Cốt lõi của vấn đề tối ưu hóa chính là việc làm giảm thiểu lưu trữ trung gian và từ đó làm tăng nhanh tốc độ xử lý câu hỏi.

Tuy nhiên, để thực hiện được các quá trình tối ưu hóa như trên, chúng ta cần lưu ý tới thứ tự thực hiện các phép toán để có thể "đẩy" các phép toán xuống các mức hợp lý cần thiết. Bảng dưới đây cho phép chúng ta cách thực hiện các phép biến đổi tương đương đối với các phép Hội (Union), Trừ (Minus), Giao (Intersect), Tích Đề-các (Cartesian), Chia (Division), Chiếu (Projection) và Chọn (Selection).

-(B1). Kết tự nhiên tương đương vớ dãy phép tích Đề-các, phép chọn và phép chiếu:

Q1 (A,B) * Q2 (B,C) (Q1 x Q2 : (Q1[B]=Q2[B])) [A,B,C]

-(B2). Phép theta kết tương đương với dãy phép tích Đề-các và phép chọn với điều kiện theta:

Q1(A,B) Q2(C,D) (Q1 x Q2) : (Bq D)

-(B3). Phép giao (Intersect) tương đương với phần bù (Complement) của hội hai phần bù của 2 quan hệ:

Q1 Ç Q2(( Q1) ( Q2)) và (B4)

-(B4). Phép bù của một quan hệ tương đương với tích Đề-các của các phép chiếu trên từng thuộc tính của quan hệ trừ đi các bộ giá trị đã có trong thể hiện của quan hệ:

Q(X1, X2,¼ Xn) (Q[X1] x Q[X2] x ¼ x Q[Xn]) - Q(X1,¼ Xn)

-(B5). Thương của 2 quan hệ tương đương với hiệu của các quan hệ trung gian sau:

Q1(A,B) ¸ Q2(A) = Q1[B] - ((Q1[B] x Q2[A] - Q1(A,B)) [B]

Áp dụng các cách biến đổi tương đương trên, kết hợp với các quy tắc "đẩy" và kết hợp như đã trình bày trong mục 8.2, chúng ta đưa ra thuật toán tổng quát để tối ưu hóa các câu hỏi trong ngôn ngữ đại số quan hệ.

-Thuật toán:

Đầu vào (Input): Sơ đồ cú pháp câu hỏi bằng ngôn ngữ đại số quan hệ.

Đầu ra (Output): Sơ đồ cú pháp tối ưu.

-Bước 1. Áp dụng các phép biến đổi tương đương nêu trong bảng (B1) đến (B5) trên.

-Bước 2. Áp dụng luật biến đổi dãy các phép chọn tương đương: tách phép chọn thành các phép chọn con.

-Bước 3. Đối với mỗi phép chọn, áp dụng các luật ,‘ ,’ và “ nhằm đẩy các phép toán chọn đó xuống càng sâu càng tốt.

-Bước 4. Đối với mỗi phép chiếu, áp dụng các quy tắc Ž ,” và nhằm đẩy các phép toán chiếu đó xuống càng sâu càng tốt.

-Bước 5.

-Tập trung các phép chọn nhằm áp dụng luật

-Áp dụng luật Ž để loại bỏ bớt các phép chiếu vô ích.

-Tập trung các phép chọn với tích Đề-các, nếu được, để chuyển thành pheép kết tự nhiên hay theta kết bằng cách áp dụng các luật Ž và ‘ .

+Nhận xét:

- Thuật giải nêu trên chủ yếu nhằm giảm khối lượng dữ liệu trung gian chứ không chỉ ra thứ tự thực hiện các phép kết. Ví dụ:

(Q1 (A,B) * Q2 (B,C)) * Q3(A,C)

(Q1 (A,B) * Q3 (A,C)) * Q2(B,C)

-Thuật giải này không cho chúng ta một kết quả tối ưu mà nó chỉ đưa ra một giải pháp tôét.

- Các phép biến đổi chỉ dựa trên các phép toán cơ bản là Hội (Union), Trừ (Minus), Giao (Intersect), Tích Đề-các (Cartesian), Chia (Division), Chiếu (Projection) và Chọn (Selection) mà chúng ta còn có thể thực hiện các phép biến đổi dựa trên các phép toán khác nữa.