Đề tài Tối ưu các truy vấn đệ quy hướng đối tượng dựa trên mô hình chi phí cơ sở

TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 2(37).2010 26 TỐI ƯU CÁC TRUY VẤN ĐỆ QUY HƯỚNG ĐỐI TƯỢNG DỰA TRÊN MÔ HÌNH CHI PHÍ CƠ SỞ OPTIMIZATION OF OBJECT-ORIENTED RECURSIVE QUERIES BASED ON THE COST MODEL Trương Ngọc Châu Trường Đại học Bách khoa, Đại học Đà Nẵng TÓM TẮT Trong các lược đồ cơ sở dữ liệu hướng đối tượng thường xảy ra các quan hệ đệ quy giữa các lớp, nhằm mục đích làm tăng khả năng biểu diễn ngữ nghĩa của chúng, điều này làm phức tạp thêm vấn đề xử lý tối ưu các truy vấn nói chung và các truy vấn đệ quy nói riêng trên các đối tượng phức. Dựa vào các kết quả trong [5], bài báo tập trung nghiên cứu, phân tích và cải tiến các phương pháp tối ưu truy vấn đệ quy, như: tạo các cây xử lý truy vấn ứng với các nút vị từ; biến đổi các cây xử lý truy vấn dựa trên mô hình chi phí cơ sở, sử dụng chiến lược điều chỉnh chi phí, với tham số đầu vào là đồ thị truy vấn của truy vấn đệ quy hướng đối tượng tổng quát. ABSTRACT In the schemata of object-oriented database, recursive relations among classes often take place with the purpose of increasing the ability of performing their meaning. This causes more problems to the optimal processing of queries in general and recursive queries based on complicated objects in particular. Based on the results in [5], this article focuses on the study, analysis and improvement of a number of optimal methods for recursive queries such as creating trees of processing queries with the predicates performance at nodes; changing query- processing trees based on a model of the basic cost by using a strategy for controlling cost with an input querying graph of general recursive queries. 1. Giới thiệu Các mô hình dữ liệu hướng đối tượng được mở rộng với các quan hệ đệ quy nhằm mục đích làm tăng khả năng biểu diễn ngữ nghĩa, điều này làm phức tạp thêm vấn đề tối ưu các truy vấn nói chung và các truy vấn đệ quy nói riêng. Các tiếp cận tối ưu truy vấn đang tồn tại [2][3][8][10] để tối ưu hóa các truy vấn đệ quy không thể áp dụng được. R.S.G. Lanzelotte, P. Valduriez, M. Zait [5] đã đề xuất một cách tiếp cận tối ưu truy vấn đệ quy hướng đối tượng dựa trên một mô hình chi phí cơ sở, sử dụng các chiến lược điều chỉnh chi phí. Nguyên tắc chung khi tối ưu một truy vấn là biến đổi truy vấn này về một lược đồ thực thi, có tổng chi phí là thấp nhất. Cách tiếp cận thông thường, chủ yếu sử dụng các quy tắt viết lại truy vấn dựa trên lược đồ khái niệm [3][8][10] rất khó để đo được chi phí thực thi. Tiếp cận của nhóm tác giả R.S.G. Lanzelotte [5] dựa trên các thực thể vật lý, do đó chi phí của lược đồ thực thi truy vấn có thể được tính toán trực tiếp một cách dễ dàng dựa trên mô hình chi phí đã cho. TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 2(37).2010 27 Bài báo tập trung nghiên cứu và phân tích các chiến lược tối ưu dựa trên mô hình chi phí cơ sở, sử dụng các chiến lược điều chỉnh chi phí, với tham số đầu vào là các đồ thị truy vấn. Tiếp theo những kết quả trong [5], chúng tôi mở rộng các hành động tối ưu một cách tổng quát hơn, dựa trên câu truy vấn đệ quy hướng đối tượng tổng quát. 2. Một số khái niệm Ví dụ 1. Xét lược đồ cơ sở dữ liệu hướng đối tượng sau đây làm cơ sở cho các truy vấn được trình bày trong bài báo này. define class NGUOI: type tuple (hoTen: String; ngay Sinh: Date; hocVi: String;) end NGUOI define class BAIGIANG: type tuple (tenBaiGiang: String; giaoVien: GIAOVIEN; taiLieuTK: set(TAILIEU);) end BAIGIANG define class TAILIEU: type tuple (tenTaiLieu: String; tacGia: String; namXB: String;) end TAILIEU define class GIAOVIEN inherits NGUOI type tuple (thay: GIAOVIEN; baiGiang: set(BAIGIANG);) end GIAOVIEN Ngữ nghĩa của lược đồ khái niệm trong Ví dụ 1 được giải thích như sau: một giáo viên khi mới được nhận về giảng dạy tại một khoa ở một trường Đại học nào đó. Giáo viên này sẽ được khoa phân công soạn một số bài giảng trước khi tham gia giảng dạy. Các giáo viên được phân công soạn bài giảng, được khoa cử một thầy (thuộc tính thay trong lớp GIAOVIEN) có chuyên môn liên quan hướng dẫn. 2.1. Đồ thị truy vấn [5] Đồ thị truy vấn là một đồ thị có hướng bao gồm các thành phần sau: - Các nút vị từ: biểu diễn các vị từ trong câu truy vấn và được ký hiệu bởi các hình vuông, có một hoặc nhiều cung vào và một cung ra. Các cung vào và ra của một nút vị từ được gán nhãn cây, cây này bao gồm các biến hay các đối tượng. Nhãn cây tại cung ra của nút vị từ cho biết kiểu của nút vị từ tại đầu ra, để ký hiệu phép chiếu tại đầu ra, chúng ta tham chiếu các biến trong các nhãn cây của các cung vào. - Các tên nút: là các tên lớp hay quan hệ của lược đồ khái niệm. - Các cung có hướng nối các tên nút với các nút vị từ. 2.2. Truy vấn đệ quy Giả sử rằng lược đồ khái niệm được mở rộng với khái niệm khung nhìn (view) đệ quy R. Khi đó, một truy vấn đệ quy có thể được chia thành hai bước: cơ sở và đệ TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 2(37).2010 28 quy, có dạng tổng quát như sau: view R(d, i, j, v) includes (SELECT 1, a.i, a.j, v FROM a in T) Truy vấn Q1 tại bước cơ sở Union (SELECT d+1, b.i, c.j, v FROM b in R, c in T WHERE ) Truy vấn Q2 tại bước đệ quy Trong đó: - d cho biết độ sâu của đệ quy (thuộc tính này có thể không có mặt trong truy vấn); v có giá trị số và có thể thay đổi sau mỗi bước đệ quy, tùy thuộc vào cách mà nó được tính toán. - chứa biểu thức kết nối b.j = c.i - T là sưu tập chứa các đối tượng làm đầu vào cho truy vấn đệ quy - R là sưu tập chứa các đối tượng được trả về sau mỗi bước đệ quy và có cấu trúc tương tự như T. Ví dụ 2. Cho truy vấn đệ quy: “Cho biết họ tên giáo viên có thầy hướng dẫn liên quan ít nhất là 3 thế hệ, soạn các bài giảng đã tham khảo tài liệu của tác giả Nguyễn An”. view R(thay, giaovien, thehe) includes (SELECT [thay: a.thay, giaovien: a, thehe: 1] FROM a in GIAOVIEN) Bước cơ sở Union (SELECT [thay: r.thay, giaovien: b, thehe: add1(thehe)] FROM r in R, b in GIAOVIEN WHERE r.giaovien = b.thay) Bước đệ quy SELECT kq.hoTen FROM kq in R WHERE kq.thehe>=3 and kq.thay.baiGiang.taiLieuTK.tacGia = “Nguyễn An” Trả về kết quả Hình 1 là đồ thị truy vấn của truy vấn trong Ví dụ 2. Các nút vị từ P1 và P2 định nghĩa khung nhìn đệ quy R, khung nhìn này được xem như là bao đóng chuyển tiếp có dạng R = Q1∪ (R.Q2). Các thể hiện của R là hợp của các thể hiện ở đầu ra của các nút vị từ P1 và P2, nút vị từ P3 áp dụng cho truy vấn trên khung nhìn đệ quy. TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 2(37).2010 29 Hình 1. Đồ thị của truy vấn đệ quy 2.3. Lược đồ thực thi Chúng ta sử dụng cây xử lý truy vấn PT (Processing Tree) [5] để mô hình hóa lược đồ thực thi truy vấn. Ví dụ trong Hình 2 chỉ ra hai cây xử lý truy vấn của truy vấn ở Hình 1. Định nghĩa. Một nút N của PT, được ký hiệu N(child0, child1,..., childk-1) sao cho mỗi nút N hay các nút con của nó childi, 0 ≤ i ≤ k-1 hoặc là: - Một phép chiếu Proj, một phép chọn Selpred (k = 1), - Một kết nối ẩn IJatrrName, một kết nối hiển EJpred, một điểm bất động (Fix point) Fix, một phép hợp Union (k = 2), - Một kết nối ẩn thực hiện bởi một chỉ mục đường dẫn PIJpathIndex (k ≥ 2), - Một thực thể nguyên tử của lược đồ vật lý hoặc một tập tin tạm (k = 0). 2.4. Mô hình chi phí [4, 5, 6] Ký hiệu Ci là tên của quan hệ hay lớp, N là nút của PT, Ai là thuộc tính của Ci, P là vị từ. Ta có chi phí cho các phép toán cơ bản như sau: + access_cost(Ci): chi phí truy cập các thể hiện của Ci. + access_cost(Ci, P): chi phí truy cập các thể hiện của Ci thỏa mãn vị từ P. + access_cost(Ci, Ci+1): chi phí truy cập các thể hiện của Ci+1 được tham chiếu bởi một thể hiện của Ci thông qua thuộc tính Ai. + eval_cost(Ci, P): chi phí ước lượng vị từ P trên tất cả các đối tượng của Ci được lưu trữ trong một trang của Ci. P2 P1 x y thay x 1 giaoviethehe TRUE thay y GIAOVIEN R x thay y y = d thay g giaovie theh m thay d g giaovie add1 baiGiang d taiLieuTK tacGia i i = “Nguyễn An” and g >= 3 P3 d hoTen m KETQUA m thay x giaovienthehe TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 2(37).2010 30 - Các tham số dựa trên mô tả của lược đồ vật lý: |Ci| số các trang mà Ci được lưu trữ; ||Ci|| số các thể hiện của Ci; nblevels(I) số cấp của chỉ mục I; nbleaves(I) số các nút lá của chỉ mục I. Hình 2. Các cây xử lý cho truy vấn của Hình 1. - Các hàm: + nbpages(Ci, P): trả về số các trang đã truy cập, nghĩa là |Ci| đã được rút gọn bởi vị từ P. + nbtuples(Ci, P): trả về số đối tượng đã truy cập, nghĩa là ||Ci|| đã được rút gọn bởi vị từ P. Bảng 1. Các công thức tính chi phí cho các nút trong cây xử lý truy vấn Nút của PT Công thức chi phí Selselpred(C) access_cost(C, selpred) + nbpages(C, selpred)*eval_cost(C, selpred) EJpred(Ci, Cj) access_cost(Ci, pred) + nbtuples(Ci, pred)*(access_cost(Cj, pred) + nbpages(Cj, pred) * eval_cost(Cj, pred)) 1 1 Công thức này là hợp lệ nếu phép toán EJ được thực hiện bằng cách sử dụng thuật toán kết nối lặp lồng hay chỉ mục kết nối. R GIAOVIEN R EJthay = ∪ Fix Selthehe ≥ 3 IJthay PIJbaiGiang.taiLieuT KETQUA SeltacGia = ‘Nguyễn An’ IJgiaovien GIAOVIEN GIAOVIEN GIAOVIEN GIAOVIE N R T1 T2 T3 T4 T6 T5 (i) GIAOVIEN TAILIEU IJthay GIAOVIEN IJthay R’ GIAOVIEN PIJbaiGiang.taiLieuTK BAIGIANG TAILIEU SeltacGia = ‘Nguyễn GIAOVIEN EJthay = PIJbaiGiang.taiLieuTK BAIGIAN G SeltacGia = ‘Nguyễn ∪ Fi Selthehe ≥ 3 KETQUA R’ T7 T8 T9 T10 T11 T12 T13 T14 T15 (ii) TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 2(37).2010 31 IJAi(Ci, Cj) access_cost(Ci) + ||Ci|| * access_cost(Ci, Cj) PIJpathInd(C1,..., Cn) ||C1|| * (nblevels(pathInd) + nbleaves(pathInd)/||C1||)2 Fix(T, P) ∑ = n i 1 i))cost(Exp(T 3 Bảng 1 chỉ ra công thức tính chi phí của các nút trên PT đã giới thiệu trong 2.3. Cho N là nút gốc của PT, chi phí của PT được tính đệ quy theo công thức sau: cost(PT) = cost(N) + ∑ = k i 0 i )cost(child (childi là nút con thứ i của nút N trong PT) 3. Tối ưu các đồ thị truy vấn Cách tiếp cận trong [5] cho phép tối ưu từng bài toán con hay còn gọi là phần tử tối ưu một cách riêng biệt (một đường dẫn hay một nút vị từ SPJ), nhằm giảm bớt tính phức tạp của bài toán. 3.1. Tiếp cận tối ưu Tiếp cận đặt tả không gian tìm kiếm tối ưu và chiến lược tìm kiếm. Không gian tìm kiếm được đặt trưng bởi các hành động (action) tối ưu và phạm vi áp dụng. Chiến lược tìm kiếm chịu trách nhiệm điều chỉnh các hành động tối ưu. Thủ tục tối ưu optimize tổng quát như sau: optimize(Q){ rewrite(Q); for each (N, tree) ∈ Q translate(N, tree); for each SPJ(In, pred, out) ∈ Q | (∀N ∈ In) isaPT(N) Q := Q – {N ← SPJ(In, pred, out)} ∪ {N ← generatePT(SPJ(In, pred, out))}; repeat transformPT(Q) until saturation;} Bảng 2 tóm tắt các đặt trưng của các thủ tục đã kể đến trong thủ tục optimize. Bảng 2. Các thủ tục tối ưu Thủ tục Phần tử tối ưu Chiến lược Các nút của PT tạo ra rewrite toàn bộ đồ thị truy vấn Fix, Union translate một cung chi phí cơ sở IJ, PIJ 2 Chỉ mục đường dẫn pathInd được định nghĩa trên đường dẫn C1.A1...An-1, trong đó mỗi thuộc tính Ai có kiểu Ci+1 được định nghĩa trong lớp Ci. 3 n là số phép lặp để tìm ra điểm bất động đệ quy, Exp(Ti) ký hiệu phương trình điểm bất động Exp, có Ti như là đầu vào thay vì T, và Ti ký hiệu là kết quả mới được tạo ra tại bước i – 1. TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 2(37).2010 32 generatePT một nút vị từ chi phí cơ sở EJ, Sel transformPT toàn bộ PT chi phí cơ sở Các hành động kể đến trong các thủ tục được đặt tả thông qua các action, các action này thực hiện các phép biến đổi theo một quy tắc nào đó. action có chức năng nhận dạng và biến đổi các “mẫu” xuất hiện trong phạm vi của đồ thị truy vấn và có dạng: action: F | constraint → G trong đó, action là tên của hành động, F và G là các mẫu mô tả các thành phần của phần tử tối ưu mà action được áp dụng, constraint là ràng buộc kiểm tra điều kiện để áp dụng action. Khi action được áp dụng đến một số đối tượng O, nếu F đối sánh một số thành phần của O và ràng buộc constraint đúng, thì thành phần đã đối sánh bởi F trong O được thay bởi G. 3.2. Viết lại đồ thị truy vấn Mục đích để tìm ra điểm bất động đệ quy và tạo ra các nút Fix và Union không hiển thị trong đồ thị truy vấn. Viết lại đồ thị truy vấn được thực hiện bởi thủ tục rewrite sau: rewrite(Q){ repeat Union(Q) until saturation; repeat Fixpoint(Q) until saturation;} Các hành động Union và Fixpoint được áp dụng đến khi xác định được các toán tử Union và Fix dựa trên đồ thị truy vấn Q (saturation). Trong thủ tục này có hai hành động: - Hành động Union tạo ra toán tử Union xuất hiện trong đồ thị truy vấn Union: Q | (Name ← p1) ∈ Q ∧ (Name ← p2) ∈ Q → Q – {( Name ← p1), (Name ← p2)} ∪ {( Name ← Union(p1, p2))} - Hành động Fixpoint tìm ra điểm bất động của đệ quy và thêm vào toán tử Fix Fixpoint: Name | (Name ← p) ∈ Q ∧ fixpointRecursive(Name) → Fix(Name, p) Ràng buộc fixpointRecursive(Name) trả về giá trị đúng nếu cung (Name, tr) lặp lại trong đồ thị truy vấn, Name được xem như là điểm bất động của phương trình có dạng Name = Q(Name). 3.3. Biên dịch đến lược đồ vật lý Tối ưu chi phí cơ sở yêu cầu đồ thị truy vấn phải được biên dịch vào lược đồ vật lý. Mỗi cung (N, tr) của đồ thị truy vấn được biên dịch vào dãy gồm các nút IJ. Quá trình biên dịch được thực hiện bởi hành động như sau: translateArc: (N, tr) | type(N)=[..., Att:C,...] ∧ (Att, tr’, var) ∈ tr ∧ isaClass(C) → (IJAtt(N, C), tr’) TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 2(37).2010 33 Hành động collapse thu gọn dãy con các nút IJ vào nút PIJ (đường dẫn kết nối ẩn) nếu tồn tại một chỉ mục đường dẫn thích hợp. collapse: IJp1(IJp2(N1, N2), N3) | existPathIndex(p2.p1) → PIJp2.p1(N1, N2, N3) 3.4. Tạo các cây thực thi truy vấn ứng với các nút vị từ Sau khi thực hiện thủ tục generatePT, mỗi nút vị từ được thay thế trong đồ thị truy vấn bởi các nút EJ hoặc Sel để tạo thành cây xử lý PT hoàn chỉnh. Hành động sel(N, pred) (tương tự join) khai triển có hệ thống N dựa vào các vị từ trong pred để tạo ra các nút Sel (tương tự EJ). sel: (N, pred) | pred = and(selpred(N), pred’) → (Selselpred(N), pred’) Trong thành phần ràng buộc của hành động join, vị từ disjoint(N, Inner) là đúng nếu các thực thể nguyên thủy trong N và Inner là độc lập trong in, với in là tập các đầu vào của SPJ. join: (N, pred) | Inner ∈ In ∧ disjoint(N, Inner) ∧ pred = and(joinpred(N, Inner), pred’) → (EJjoinpred(N, Inner), pred’) Sau khi tối ưu các nút vị từ bởi generatePT, đồ thị truy vấn ở Hình 1 có được như Hình 2.(i). Tất cả các nút vị từ được tối ưu và được thay thế bởi các cây xử lý truy vấn tối ưu với một chi phí kết hợp. 3.5. Biến đổi các cây xử lý truy vấn : đẩy các phép toán tuyển chọn vào đệ quy Xét truy vấn đệ quy tổng quát được cho trong mục 2.2, ta có thể ước lượng sớm các điều kiện lọc đối tượng được sử dụng khi có mệnh đề “WHERE”, với điều kiện lọc liên quan đến các thuộc tính của R. Khi đồ thị truy vấn tồn tại chu trình thì đệ quy có thể lặp không xác định. Do đó, chúng ta nhấn mạnh việc sử dụng mệnh đề “WHERE”, bởi vì nó là cách duy nhất để bảo đảm truy vấn đệ quy dừng. Truy vấn chúng ta nghiên cứu có dạng: SELECT d, r.i, b.j, v FROM r in R, b in T WHERE ; Tương tự trong tối ưu hóa truy vấn quan hệ, trong đó các phép chọn và chiếu có thể được ước lượng sớm nhất có thể, sau đó mới đến phép kết nối, trong trường hợp này phép kết nối sẽ được thực hiện trên các sưu tập đối tượng có kích thước nhỏ hơn. Thủ tục transformPT trong [5] sau đây thực hiện đẩy các phép chọn (selection) và kết nối (join) vào đệ quy bằng cách sử dụng hành động filter. Sau đó tiếp tục cải tiến PT đã có bằng chiến lược tối ưu có tính ngẫu nhiên, ví dụ sau phép biến đổi này ta có Hình 2.(i) sẽ trở thành Hình 2.(ii). transformPT(PT) { newPT := PT; filter(newPT); newPT := randOptimize(newPT); TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 2(37).2010 34 if cost(newPT) < cost(PT) then PT := newPT;} Hành động filter thực hiện việc đẩy phép chọn vào đệ quy (tương tự đẩy phép kết vào đệ quy). Hạn chế của hành động này là chỉ đẩy các phép chọn và kết nối đồng thời vào bước cơ sở và đệ quy, và không nói rõ điều kiện ràng buộc khi đẩy các phép này. Để mở rộng và làm rõ hành động filter, chúng tôi phân biệt hai trường hợp có thể xảy ra trong biểu thức . Trường hợp đầu tiên được cho bởi điều kiện trên các thuộc tính i, j của R; trường hợp thứ hai được cho bởi điều kiện trên các thuộc tính v hoặc d mà chúng có giá trị thay đổi ở mỗi bước đệ quy. Từ hai trường hợp này chúng tôi xây dựng các action như sau: c filter1: Selpred(PT(Fix(Rec, Union(Base, PT’(Rec))))) | canPush1(pred, Rec) → Fix(Rec, Union(Selpred(PT(Base)), PT’(Rec)))) d filter2: Selpred(PT(Fix(Rec, Union(Base, PT’(Rec))))) | canPush2(pred, Rec) → Fix(Rec, Union(Base, PT’(Selpred(PT(Rec)))) e filter3: Selpred(PT(Fix(Rec, Union(Base, PT’(Rec))))) | canPush3(pred, Rec) → Fix(Rec, Union(Selpred(PT(Base)), PT’(Selpred(PT(Rec))))) Trong đó: kí hiệu PT(X) (hay PT’(X)) xem PT chứa X như một cây con, hay có thể xem nó như hàm chứa X; ràng buộc canPush là điều kiện để thực hiện việc đẩy phép chọn hoặc kết nối. Ứng với mỗi hành động filteri có một ràng buộc canPushi tương ứng, hành động đẩy phép chọn vào đệ quy được minh họa như Hình 3. - canPush1(pred, Rec): đẩy phép chọn vào bước cơ sở, nếu có một điều kiện trên thuộc tính i hoặc j, và i, j không tham gia vào điều kiện kết nối. - canPush2(pred, Rec): đẩy phép chọn vào bước đệ quy, nếu có một điều kiện trên d, độ sâu đệ quy d tăng tuyến tính tại mỗi bước lặp đệ quy là 1 đơn vị, nếu biểu thức lọc là “WHERE d ≤ k” thì biểu thức này sẽ giới hạn độ sâu đệ quy với số bước lặp tối đa là k. - canPush3(pred, Rec): đẩy phép chọn vào bước cơ sở và đệ quy, nếu có một điều kiện trên thuộc tính v và phụ thuộc vào cách mà v được tính toán, trong trường hợp tổng quát thì v có giá trị thay đổi sau mỗi bước đệ quy. Chúng ta tách biệt hai khả năng: v được tính toán đệ quy và v không được tính toán đệ quy khi nó là một thuộc tính có liên quan đến i hay j (ví dụ v là một thuộc tính tham chiếu của i hay j). R R ∪ Fi Base R R ∪ Fi Selp Base Selp Selp R R ∪ Fi Selp Base R R ∪ Fi Selp Base Truy vấn ban Hình 3. Các hành động đẩy phép chọn TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 2(37).2010 35 Vì phép chọn luôn chứa biểu thức đường dẫn và biểu thức đường dẫn này luôn tồn tại các kết nối ẩn. Do đó, khi đẩy phép chọn vào đệ quy sẽ kéo theo việc đẩy các kết nối ẩn vào theo. Một số các chọn lựa tối ưu dựa trên cơ sở các ràng buộc xác định, vì vậy việc thay đổi một thành phần của PT có thể kéo theo việc tối ưu lại nó. Do đó, thủ tục transformPT áp dụng một chiến lược tối ưu ngẫu nhiên đến PT đã lọc, nhằm biến đổi nó để rút gọn hơn nữa chi phí. Tiếp cận được trình bày trong bài báo cho phép chúng ta tìm ra các lời giải mà trong đó phép kết nối join và chọn selection được đẩy vào đệ quy. Một kết nối có tính chọn, vì vậy nó có thể được đẩy vào đệ quy. Trong mô hình chi phí, chúng ta có thể đánh giá những thuận lợi của phép biến đổi như thế. Ví dụ, chúng ta có truy vấn: “Cho biết những giáo viên tham gia soạn bài giảng có liên quan đến thầy hướng dẫn của giáo viên Trần Thuận”. Truy vấn này được trả lời bởi một kết nối giữa R và GIAOVIEN trên thuộc tính thay, nghĩa là, R.thay = GIAOVIEN.thay and GIAOVIEN.hoTen = “Trần Thuận”. Rõ ràng rằng kết nối này có tính chọn và nếu được đẩy vào đệ quy thì sẽ hạn chế sự tính toán đệ quy của R đến một vài yếu tố có liên quan. Ví dụ 3. Cây xử lý PT trong Hình 2.(i) được biến đổi thành cây xử lý PT trong Hình 2.(ii) bằng cách áp dụng các thủ tục trên. Tính tổng chi phí của PT trong Hình 2.(i) và Hình 2.(ii) dựa vào các chi phí cơ bản được cho trong Bảng 1, ta thấy chi phí trong Hình 2.(ii) thấp hơn Hình 2.(i). 4. Kết luận Trong bài này, chúng tôi đã nghiên cứu và phân tích một cách tiếp cận tổng quát để giải bài toán tối ưu các truy vấn đệ quy hướng đối tượng dựa trên mô hình chi phí cơ sở, sử dụng các chiến lược điều chỉnh chi phí. Trong tiếp cận này đã áp dụng các hành động tối ưu để xây dựng các lược đồ thực thi truy vấn với tham số đầu vào là đồ thị truy vấn, các lược đồ thực thi truy vấn được mô hình hóa bởi các cây xử lý truy vấn, các cây này gồm các thực thể vật lý, kết hợp các ước lược chi phí. Ưu điểm của cách tiếp cận này là các hành động tối ưu được biểu diễn qua các thực thể vật lý, do đó chúng ta có thể tính toán chi phí của nó một cách dễ dàng trên cơ sở của mô hình chi phí. TÀI LIỆU THAM KHẢO [1] F. Bancilhon, R, Ramakrishnan, An Amateur’s Introduction to Recursive Query Processing Strategies, SIGMOD 1986. [2] R. Krishnarnurty, C. Zauiolo, Optimization in a Logic Based Language for Knowledge and Data Intensive Applications, EDBT 1988. [3] HOÀNG BẢO HÙNG, Truy vấn và tối ưu hóa truy vấn trong cơ sở dữ liệu hướng đối tượng, Luận án tiến sĩ toán học, 2007. TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 2(37).2010 36 [4] R.S.G. Lanzelotte, P. Valduriez, Extending the Search Strategy in a Query Optimizer, VLDB 1991. [5] R.S.G. Lanzelotte, P. Valduriez, M. Zait, Optimization of Object-Oriented Recursive Queries using Cost-Contolled Strategies, ACM SIGMOD, June 1992, USA. [6] R.S.G. Lauzelotte, P. Valduriez, M. Ziane, J.P. Cheiney, Optimization of Nonrecursive Queries in 00 DBs, DOOD 1991. [7] D. Maier, J. Stein, Indexing in an Object-Oriented DBMS, Workshop on Object- Oriented Database Systems 1986. [8] Trigoni, Agathoniki, Semantic Optimization of OQL Queries, Technical Report, Number 547, University of Cambridge, Computer Laboratory, UCAM-CL-TR-547, ISSN 1476-2986, October, 2002. [9] P. Valduriez, Join Indices, ACM TODS, Vol. 12, N. 2, 1987. [10] Y. KORNATZKY, C. BEERI, Algebraic Optimization of Object-Oriented Query Languages. In Proc. ICDT, Paris, France, 1990.