Methods for evaluating queries to Horn knowledge bases in first-order logic

Bazy wiedzy typu Horna są uogólnieniem dedukcyjnych baz danych Datalogu bez ograniczeń o zakresie zmiennych i z możliwością korzystania z symboli funkcyjnych. Baza wiedzy typu Horn składa się z pozytywnego programu w logice definiującego predykaty intensjonalne i instancji ekstensjonalnych predykatów. Niniejsza rozprawa dotyczy efektywnych metod obliczania zapytań do baz wiedzy typu Horna. Omówiona jest również metoda obliczania zapytań do stratyfikowanych baz wiedzy. Problematyka ta nie była do tej pory tak dobrze zbadana, jak przetwarzanie zapytań dla dedukcyjnych baz danych czy teoria i techniki programowania w logice. W pierwszej części rozprawy formułujemy sieci zapytań-podzapytań i omawiamy konstrukcję bazującej na takich sieciach metody obliczania zapytań do baz wiedzy typu Horna, o następujących dobrych własnościach: zastosowane podejście jest zorientowane na cel; każde podzapytanie jest przetwarzane tylko raz; każda krotka uzupełniająca jest przesyłana tylko raz, o ile jest to pożądane; operacje są wykonywane zbiorowo; każda strategia sterowania może być używana. Intencją tej metody jest zwiększenie efektywności przetwarzania zapytań poprzez wyeliminowanie zbędnych obliczeń, ułatwienie stosowania zaawansowanych strategii sterowania oraz zredukowanie liczby odczytów i zapisów dyskowych. Ogólna taka metoda jest nazwana QSQN. Jest ona poprawna i pełna oraz ma złożoność wielomianową względem danych ekstensjonalnych, o ile głębokość zagnieżdżenia termów jest ograniczona. W dalszej części rozprawy przedstawiona jest technika włączania eliminacji rekurencji ogonowej do sieci zapytań-podzapytań i uzyskana w ten sposób metoda obliczania zapytań QSQN-TRE dla baz wiedzy typu Horna. Celem takiej eliminacji jest redukcja zachowywania wyników pośrednich podczas przetwarzania zapytań z rekurencją ogonową. Udowodniono, że metoda QSQN-TRE jest poprawna i pełna oraz ma złożoność wielomianową względem danych ekstensjonalnych, o ile głębokość zagnieżdżenia termów jest ograniczona. Jako rozszerzenie metody QSQN-TRE została opracowana również inna metoda obliczania zapytań o nazwie QSQN-rTRE, która pozwala wyeliminować nie tylko predykaty ogonowo rekurencyjne, ale również predykaty intensjonalne, występujące na końcu ciała pewnej klauzuli programu.Opracowane zostały również sieci zapytań-podzapytań i odpowiednia metoda o nazwie QSQN-STR do obliczania zapytań do stratyfikowanych baz wiedzy. Takie bazy wiedzy umożliwiają użycie bezpiecznych literałów negatywnych w ciałach klauzul programu. Metody QSQN, QSQN-TRE i QSQN-rTRE zostały zaimplementowane z trzema zaproponowanymi strategiami sterowania DAR, DFS i IDFS. Przeprowadzone zostały eksperymenty mające na celu porównanie tych metod (używających strategii sterowania IDFS) z innymi znanymi metodami obliczania zapytań, takimi jak Magic-Sets i QSQR. Omówione zostały również wyniki eksperymentów działania metody QSQN-STR ze strategią sterowania IDFS2 będącą zmodyfikowaną wersją IDFS. Wyniki przeprowadzonych eksperymentów potwierdzają skuteczność i przydatność opracowanych metod obliczania zapytań.

Horn knowledge bases are extensions of Datalog deductive databases without the range-restrictedness and function-free conditions. A Horn knowledge base consists of a positive logic program for defining intensional predicates and an instance of extensional predicates. This dissertation concentrates on developing efficient methods for evaluating queries to Horn knowledge bases. In addition, a method for evaluating queries to stratified knowledge bases is also investigated. This topic has not been well studied as query processing for Datalog-like deductive databases or the theory and techniques of logic programming.We begin with formulating query-subquery nets and use them to create the first framework for developing algorithms for evaluating queries to Horn knowledge bases with the following good properties: the approach is goal-directed; each subquery is processed only once; each supplement tuple, if desired, is transferred only once; operations are done set-at-a-time; and any control strategy can be used. Our intention is to increase efficiency of query processing by eliminating redundant computation, increasing adjustability (i.e., easiness in adopting advanced control strategies) and reducing the number of accesses to the secondary storage. The framework forms a generic evaluation method called QSQN. It is sound and complete, and has polynomial time data complexity when the term-depth bound is fixed. Next, we incorporate tail-recursion elimination into query-subquery nets in order to formulate the QSQN-TRE evaluation method for Horn knowledge bases. The aim is to reduce materializing the intermediate results during the processing of a query with tail-recursion. We prove the soundness and completeness of the proposed method and show that, when the term-depth bound is fixed, the method has polynomial time data complexity. We then extend QSQN-TRE to obtain another evaluation method called QSQN-rTRE, which can eliminate not only tail-recursive predicates but also intensional predicates that appear rightmost in the bodies of the program clauses.We also incorporate stratified negation into query-subquery nets to obtain a method called QSQN-STR for evaluating queries to stratified knowledge bases.We propose the control strategies DAR, DFS, IDFS and implement the methods QSQN, QSQN-TRE, QSQN-rTRE together with these strategies. Then, we carry out experiments to obtain a comparison between these methods (using the IDFS control strategy) and the other well-known evaluation methods such as Magic-Sets and QSQR. We also report experimental results of QSQN-STR using a control strategy called IDFS2, which is a modified version of IDFS. The experimental results confirm the efficiency and usefulness of the proposed evaluation methods.