Một số cải tiến đối với phép biến đổi ma tập để tối ưu hóa câu truy vấn trên chương trình datalog

TẠP CHÍ KHOA HỌC, Đại học Huế, Số 14, 2002 MỘT SỐ CẢI TIẾN ĐỐI VỚI PHÉP BIẾN ĐỔI MA TẬP ĐỂ TỐI ƯU HÓA CÂU TRUY VẤN TRÊN CHƯƠNG TRÌNH DATALOG Lê Mạnh Thạnh, Trương Công Tuấn Trường Đại học Khoa học, Đại học Huế 1. MỞ ĐẦU Phép biến đổi ma tập được đánh giá là một trong những kỹ thuật tối ưu câu truy vấn rất có hiệu quả trong cơ sở dữ liệu suy diễn. Lý do quan trọng đối với sự thành công của kỹ thuật này là sự kết hợp được các ưu điểm của kỹ thuật ước lượng trên xuống (top-down) và dưới lên (bottom-up), từ đó giảm thiểu được số các sự kiện cần tính và tìm kiếm trên cơ sở dữ liệu. Tính lôi cuốn của kỹ thuật ma tập được thể hiện ở tính hiệu quả của nó ([3, 4, 5]). Tuy nhiên, phép biến đổi ma tập chưa hẳn là một chiến lược định giá câu truy vấn tốt nhất. Bài báo tập trung thảo luận một số vấn đề liên quan đến phép biến đổi ma tập và đề xuất một số cải tiến nhằm nâng cao hiệu quả của nó trong việc tối ưu câu truy vấn trên chương trình Datalog. 2. MỘT SỐ KHÁI NIỆM CƠ SỞ Trong khuôn khổ một bài báo, chúng tôi chỉ trình bày tóm tắt một số khái niệm cơ sở của phép biến đổi ma tập. Để có các chi tiết đầy đủ hơn cũng như một số khái niệm khác của cơ sở dữ liệu suy diễn có thể xem trong [1, 5]. 2.1 Tô điểm (Adornment): Tô điểm là cách chú thích trên các vị từ để cung cấp thông tin về các vị từ sẽ được sử dụng như thế nào trong quá trình định giá câu truy vấn. Ta có một số định nghĩa: (i) Một đối của một đích con trong quy tắc r được gọi là buộc nếu trong suốt quá trình định giá câu truy vấn, mọi đích được tạo ra từ đích con này có giá trị hằng ở vị trí của đối này. Ngược lại, đối được gọi là tự do. (ii) Một tô điểm của vị từ p(t1,t2,...,tk) là một dãy các ký tự b và f có chiều dài k. Nếu ký hiệu thứ i của tô điểm là b thì đối thứ i của p là buộc, nếu ký hiệu thứ i của tô điểm là f thì đối thứ i của p là tự do. Chỉ có các vị từ IDB là được tô điểm. (iii) Cho quy tắc p ¬ q1Ùq2Ù...Ùqn và w là tô điểm của vị từ p, tô điểm ai của các đích con được xác định như sau: Nếu ti,j là hằng hoặc biến đã xuất hiện trong đích con qk trước đó (k < i) hoặc trong một vị trí buộc của p thì ai[j] =b, ngoài ra thì ai[j] =f (với ai[j] là ký hiệu ở vị trí thứ j của tô điểm). (iv) Cho chương trình P, chương trình tô điểm của P, ký hiệu là Pad, gồm các quy tắc được tô điểm của mọi quy tắc trong P. (v) Tô điểm a của câu truy vấn p(t1,...,tn) được xác định bởi: a[i] = b nếu ti là hằng và a[i] = f nếu ngược lại. 2.2 Truyền thông tin sang ngang (Sideway Information Passing): Phép biến đổi ma tập được thực hiện theo một chiến lược truyền thông tin sang ngang chọn trước, chiến lược này chỉ ra cách thức để các trị buộc trong đầu quy tắc được truyền đến thân, thứ tự mà các đích con trong thân sẽ được tính và cách thức để các trị buộc này truyền sang ngang giữa các đích con trong thân quy tắc. Định nghĩa 2.2.1 Một chiến lược truyền thông tin sang ngang đối với quy tắc r và tô điểm a của đầu quy tắc r, ký hiệu Sips(r,a), là một đồ thị có hướng được gán nhãn. Các cạnh có dạng N{q} với N là tập các vị từ trong chương trình, S là tập các biến và q là một vị từ. Các cạnh và nhãn chỉ định cách thức thông tin được truyền giữa các đích con. Các cạnh của đồ thị chỉ ra một thứ tự để các đích con được ước lượng, các nhãn chỉ định thông tin được truyền sang ngang từ đích con này đến đích con khác. Ví dụ 2.1 Xem quy tắc sau: (r): p(X,Y) ¬ q(X,Z) Ù s(Z,Y) Giả sử đối X của vị từ p bị buộc bởi hằng 1, lúc đó Sips(r,a) được biểu diễn như sau: X=1 X=1,Z p q s Quy tắc r được tô điểm thành quy tắc: pbf(X,Y) ¬ qbf(X,Z) Ù sbf(Z,Y) 2.3 Phép biến đổi ma tập ([4]): Phép biến đổi ma tập được thực hiện qua hai giai đoạn: Giai đoạn 1: Thực hiện việc tô điểm chương trình: Biến đổi chương trình Datalog P ban đầu thành chương trình có tô điểm Pad theo một chiến lược truyền thông tin sang đã chọn trước. Giai đoạn 2: Biến đổi chương trình Pad thành chương trình mới, ký hiệu MPad, được thực hiện như sau: 1. Đối với mỗi vị từ p với đối là trong chương trình Pad ,tạo ra một vị từ mới mag_p() với là đối bị buộc của vị từ p. 2. Đối với mỗi quy tắc r trong Pad: p() ¬ q1() Ù ... Ù qn() ta sửa đổi thành một quy tắc trong MPad : p() ¬ mag_p() Ù q1() Ù ... Ù qn() 3. Đối với mỗi quy tắc r trong Pad : p() ¬ q1() Ù ... Ù qn() và với mọi vị từ IDB qi, 1£i£ n ta thêm vào MPad các quy tắc magic: mag_qi() ¬ mag_p() Ù q1() Ù ... Ù qi-1() 4. Câu truy vấn q() được chuyển thành sự kiện “hạt nhân” mag_q(), trong đó là tập các hằng tương ứng với các đối bị buộc của câu truy vấn. Định lý 2.3.1 ([4]) Cho chương trình Datalog P và câu truy vấn q. Dùng phép biến đổi ma tập để biến đổi chương trình P và câu truy vấn q thành chương trình MPad. Chương trình này sẽ tương đương với P theo nghĩa khi ước lượng MPad sẽ cho ra cùng kết quả của câu truy vấn q. 3. MỘT SỐ VẤN ĐỀ LIÊN QUAN ĐẾN PHÉP BIẾN ĐỔI MA TẬP Trong phần này chúng tôi tập trung thảo luận một số vấn đề liên quan đến kỹ thuật ma tập và đề xuất các giải pháp nhằm nâng cao tính hiệu quả của nó trong quá trình định giá câu truy vấn. 3.1 Hạn chế tính toán dư thừa trên chương trình viết lại bởi phép biến đổi ma tập Khi kết thúc giai đoạn hai của phép biến đổi ma tập, ta nhận được một chương trình mới và việc tìm kiếm lời giải của chương trình viết lại này thường được thực hiện bởi các thuật toán ước lượng dưới lên, chẳng hạn thuật toán nửa ngây thơ (semi-naive) ([5]), thuật toán này cho phép ngăn chặn việc tính toán lại các sự kiện đã được tính ở bước trước. Tuy nhiên, nó không ngăn chặn được việc dẫn xuất ra các vị từ magic dư thừa. Giữa các vị từ magic tô điểm, mặc dầu không có quan hệ về cú pháp nhưng về mặt ngữ nghĩa, một vị từ magic tô điểm có thể chứa các vị từ magic tô điểm khác. Vấn đề ở đây chính là sử dụng các thông tin trong các tô điểm để xác định xem một vị từ magic có chứa vị từ magic khác hay không. Việc kiểm tra quan hệ giữa các vị từ magic có thể thu hẹp thành việc kiểm tra giữa các vị từ tương ứng của chúng. Điều này được thực hiện qua thuật toán sau đây: Thuật toán kiểm tra quan hệ giữa các vị từ magic được tô điểm: Vào: Giả sử mag_) và mag_ là hai vị từ magic lần lượt có tô điểm là a và b. Ra: Cho kết quả vị từ mag_ có chứa vị từ mag_hay không. Phương pháp: Bước 1: Biến đổi các vị từ mag_ thành hạng thức p1(), trong đó x bao gồm các hằng trong tương ứng với ký tự 'b' và các biến phân biệt tương ứng với ký tự 'f'. Tương tự, biến đổi vị từ mag_thành hạng thức p2(). Bước 2: Nếu tồn tại hợp nhất tử tổng quát nhất (mgu - most general unifier) q của p1() và p2() sao cho p1q chính là p2 thì kết luận vị từ mag_ chứa vị từ mag_, ngược lại thì mag_ không chứa vị từ mag_. Mệnh đề 3.1.1 Thuật toán này là đúng đắn. Chứng minh: Rõ ràng nếu tồn tại mgu q của p1() và p2() sao cho p1()q =p2() thì p1() chứa p2(), điều này có nghĩa mag_ chứa mag_. Để ý rằng phép hợp nhất trở nên đơn giản hơn nhiều nếu một trong hai vị từ cần hợp nhất là nguyên tố nền. Trong trường hợp này thì phép hợp nhất thu hẹp thành phép đối sánh hạng thức. Ví dụ 3.1.1 Xét hai vị từ mag_pbff(a) và mag_pbbf(a,b). Ta có mag_pbff(a) tương ứng với đích ?p(a,X,Y) và mag_pbbf(a,b) tương ứng với đích ?p(a,b,Z), mặc khác hợp nhất tử tổng quát nhất q của p(a,X,Y) và p(a,b,Z) là {X/b,Y/Z} và p(a,X,Y)q = p(a,b,Z). Vì vậy mag_pbff(a) chứa mag_pbbf(a,b). Ví dụ 3.1.2 Xét chương trình Datalog P bao gồm các quy tắc: r1 : anc(X,Y) ¬ par(X,Y) r2 : anc(X,Y) ¬ par(X,Z) Ù anc(Z,Y) Trong đó: par là vị từ EDB, anc là vị từ IDB. Giả sử quan hệ đối với vị từ EDB par gồm các bộ (a,b), (b,c), (c,d). Câu truy vấn ?-anc(X,d). Sử dụng chiến lược truyền thông tin từ trái sang phải, sau giai đoạn 1 của phép biến đổi ma tập ta nhận được chương trình tô điểm Pad sau đây: ar1 : ancfb(X,Y) ¬ par(X,Y) ar2 : ancfb(X,Y) ¬ ancfb(Z,Y) Ù par(X,Z) ar3 : ancbb(Z,Y) ¬ par(X,Y) ar4 : ancbb(X,Y) ¬ ancbb(Z,Y) Ù par(X,Z) Đích truy vấn có tô điểm: ?- ancfb(X,d) Sau giai đoạn 2 của phép biến đổi ma tập, ta nhận được chương trình MPad: mar1 : ancfb(X,Y) ¬ mag_ancfb(Y) Ù par(X,Y) mar2 : ancfb(X,Y) ¬ mag_ancfb(Y) Ù par(X,Z) Ù ancbb(Z,Y) mar3 : mag_ancbb(Z,Y) ¬ mag_ancfb(Y) Ù par(X,Z) (a,b), (b,c), (c,d) mar4 : ancbb(X,Y) ¬ mag_ancbb(X,Y) Ù par(X,Y) mar5 : ancbb(X,Y) ¬ mag_ancbb(X,Y) Ù par(X,Z) Ù ancbb(Z,Y) mar6 : mag_ancbb(Z,Y) ¬ mag_ancbb(X,Y) Ù par(X,Z) mar7 : mag_ancfb(d) Áp dụng thuật toán nửa ngây thơ cho chương trình MPad này, ta nhận được: Bước 1: mag_ancfb(d) được tạo ra. Bước 2: ancfb(c,d), mag_ancbb(b,d), mag_ancbb(c,d), mag_ancbb(d,d) được thêm vào. Bước 3: ancbb(c,d) được thêm vào. Bước 4: ancbb(b,d), ancfb(b,d) được thêm vào. Bước 5: ancfb(a,d) được thêm vào. Bước 6: Kết thúc, ta nhận được lời giải câu truy vấn (c,d), (b,d), (a,d). Rõ ràng các vị từ mag_ancbb(b,d), mag_ancbb(c,d), mag_ancbb(d,d) được tạo ra ở bước 2 là chứa trong vị từ magic biểu diễn câu truy vấn ban đầu mag_ancfb(d), vì vậy chúng là dư thừa và không cần phải tính. Tóm lại, tính toán dư thừa trong các thuật toán định giá câu truy vấn trên chương trình viết lại bởi phép biến đổi ma tập sẽ tránh được bằng cách kết hợp thêm thuật toán kiểm tra vị từ magic được tạo ra ở mỗi bước có chứa trong vị từ magic đã tạo ra ở bước trước hay không, nếu có thì ta loại bỏ nó. Ta có một vài nhận xét liên quan đến phép biến đổi ma tập: Trong phép biến đổi ma tập, một chiến lược truyền thông tin được dùng xuyên suốt quá trình ước lượng câu truy vấn. Việc ước lượng chương trình viết lại bởi phép biến đổi ma tập đã không xem xét số các sự kiện được phát sinh trong quá trình định giá truy vấn, tức là số các sự kiện được tạo ra trong mỗi bước lặp. Trong phần tiếp theo sau đây, chúng ta sẽ xem xét các vấn đề này. 3.2 Định giá câu truy vấn bằng cách kết hợp các chiến lược truyền thông tin sang ngang Trên tập các quy tắc của chương trình đã cho có thể tồn tại nhiều chiến lược truyền thông tin khác nhau. Vì vậy một câu hỏi tự nhiên là liệu có thể kết hợp hiệu quả của các chiến lược này để thực hiện việc tối ưu câu truy vấn hay không? Ta hãy xem ví dụ sau đây: Ví dụ 3.2.1 Xét chương trình Datalog P đã cho trong ví dụ 3.1.2. và câu truy vấn ?anc(a,b). Đối với ví dụ này, hai chiến lược truyền thông tin có thể được chọn để thực hiện việc tô điểm chương trình là từ trái sang phải và từ phải sang trái. Việc kết hợp hai chiến lược này sẽ dẫn đến hai quá trình định giá câu truy vấn ?anc(a,Z) và ?anc(Z,b) cho đến khi tất cả lời giải được tìm thấy đối với ?anc(a,Z) hoặc ?anc(Z,b). Việc chọn ra một chiến lược truyền thông tin "tốt" trong mỗi bước lặp có thể giảm bớt các sự kiện dư thừa được phát sinh và đạt được hiệu quả tối ưu, điều này thường không thể nhận được bởi phép biến đổi ma tập dựa trên cơ sở chiến lược truyền thông tin được chọn trước. Các quy tắc ban đầu chỉ nên được xem xét lại sau khi một số khá lớn các sự kiện được phát sinh. Trong trường hợp này rõ ràng chiến lược truyền thông tin được chọn sẽ dựa vào kích thước nhỏ nhất của các quan hệ được tạo ra tại thời điểm đó. Ta có thuật toán sau: Thuật toán ma tập có kết hợp các chiến lược truyền thông tin sang ngang: Bước 1: Áp dụng phép biến đổi ma tập để biến đổi chương trình P theo tất cả các chiến lược truyền thông tin chấp nhận được, kết quả nhận được một tập các chương trình tô điểm theo các chiến lược này. Bước 2: Áp dụng các thuật toán lặp kiểu dưới lên Naive, Semi-naive ([5]) trên các chương trình tô điểm được tạo ra ở bước 1, trong đó ở mỗi bước lặp, một chiến lược truyền thông tin sẽ được chọn dựa vào kích thước nhỏ nhất của các quan hệ được tạo ra tại thời điểm đó, Tính hiệu quả của thuật toán này được thể hiện ở việc kết hợp được các chiến lược truyền thông tin khác nhau trong từng bước lặp, từ đó giảm được chi phí tính toán đối với các phép toán nối trong thân quy tắc trong quá trình ước lượng chương trình. Mệnh đề 3.2.1 Thuật toán này hội tụ và hiệu quả hơn so với các thuật toán lặp dưới lên Naive, Semi-Naive đã được đề xuất trong [5]. Chứng minh: Các chương trình tô điểm được tạo ra trong bước 1 của thuật toán là tương đương với chương trình ban đầu (định lý 2.3.1) theo nghĩa chúng cho ra cùng kết quả của câu truy vấn, mặt khác các thuật toán dưới lên Naive, Semi-Naive là hội tụ ([5]), từ đó suy ra tính hội tụ của thuật toán này. Thuật toán đã đề xuất chắc chắn hiệu quả hơn các thuật toán dưới lên Naive, Semi-Naive trong [5], bởi vì trong mỗi bước lặp đều có xem xét số các bộ của các quan hệ được tạo ra tại thời điểm đó và chiến lược truyền thông tin ở bước tiếp theo được chọn dựa vào kích thước nhỏ nhất của các quan hệ đó. Ví dụ 3.2.2 Xét trở lại chương trình Datalog (P) ở ví dụ 3.1.1. với câu truy vấn là ?anc(a,Y). Hai chiến lược truyền thông tin có thể được chọn để ước lượng các đích con trong thân quy tắc của anc là từ trái sang phải và từ phải sang trái. Dùng chiến lược trái sang phải ta nhận được tập các quy tắc sau: ancbf(X,Y) ¬ mag_ancbf(X) Ù par(X,Y) ancbf(X,Y) ¬ mag_ancbf(X) Ù par(X,Z) Ù anc(Z,Y) mag_ancbf(Z) ¬ mag_ancbf(X) Ù par(X,Z) Dùng chiến lược phải sang trái ta nhận được tập các quy tắc sau: ancbf(X,Y) ¬ mag_ancbf(X) Ù par(X,Y) ancbf(X,Y) ¬ mag_ancbf(X) Ù anc(Z,Y) Ù par(X,Z) mag_ancff ¬ mag_ancbf(X) ancff(X,Y) ¬ mag_ancff Ù par(X,Y) ancff(X,Y) ¬ mag_ancff Ù anc(Z,Y) Ù par(X,Z) Hai chiến lược này dẫn đến các tập truy vấn con Q1 = {mag_ancbf} và Q2 = {mag_ancbf , mag_ancff}. Trong Q2 truy vấn con mag_ancff chứa truy vấn con mag_ancbf. Như vậy việc chọn chiến lược Sip từ phải sang trái để ước lượng các đích con dẫn đến quá trình câu truy vấn ?anc(X,Y) và kiểm tra a có thuộc X không? Tuy nhiên, để ý rằng mag_ancff chứa mag_ancbf, vì vậy chiến lược từ trái sang phải là tốt hơn chiến lược từ phải sang trái. 4. KẾT LUẬN Bài báo đã tập trung thảo luận một số vấn đề liên quan đến việc tối ưu hoá câu truy vấn trên chương trình Datalog bằng phép biến đổi ma tập. Chúng tôi đã đề xuất cách thức nhận ra các sự kiện dư thừa trong quá trình ước lượng và việc kết hợp các chiến lược truyền thông tin trong mỗi bước lặp. Các giải pháp đưa ra nhằm mục đích làm tăng tính hiệu quả của phép biến đổi ma tập, đồng thời điều này cũng là một thể hiện tốt về tính hiệu quả tương đối của một phương pháp. TÀI LIỆU THAM KHẢO S. Ceri, G. Gottlob, L.Tanca. Logic Programming and Databases, Springer-Verlag Berlin Heidelberg (1990). Lê Mạnh Thạnh, Trương Công Tuấn. Một số phương pháp ước lượng câu truy vấn trong cơ sở dữ liệu suy diễn, Tạp chí Khoa học Đại học Huế, số 7(2001) 49-59. Lê Mạnh Thạnh, Trương Công Tuấn. Phân tích một số phương pháp xử lý vòng lặp vô hạn trong quá trình ước lượng câu truy vấn đối với chương trình Datalog, Tạp chí Tin học và Điều khiển học, tập 17, số 4(2001) 87-96. R. Ramakrishnan. Magic Templates: A Spellbinding Approach to Logic Programs, Journal of Logic Progamming 11 (1991) 189-216. J.D. Ullman. Principles of Database and Knowledge - Base Systems, Volume I and II, Computer Science Press (1989). TÓM TẮT Trong các phương pháp định giá câu truy vấn trên cơ sở dữ liệu suy diễn, phép biến đổi ma tập (magic sets transformation) được xem là một kỹ thuật tối ưu câu truy vấn tốt nhờ vào tính hiệu quả của nó, tuy nhiên kỹ thuật ma tập chưa hẵn là một chiến lược tối ưu truy vấn tốt nhất. Bài báo này tập trung thảo luận một số vấn đề liên quan đến phép biến đổi ma tập và đề xuất một số cải tiến nhằm nâng cao hiệu quả của nó. SOME IMPROVEMENTS OF MAGIC-SETS TRANSFORMATION IN OPTIMIZING QUERIES FOR DATALOG PROGRAMS Le Manh Thanh, Truong Cong Tuan College of Sciences, Hue University SUMMARY One of the major tasks of deductive databases is query answering, many query evaluation methods have been proposed. Among these, the magic-sets transformation was a general query optimization technique in deductive databases. However, magic-sets technique may not be the best query optimization strategy. In this paper, we discuss some problems of magic sets and propose some improvements of magic-sets technique that allow efficient bottom-up computation of answers.