Open Collections

Optimizations for model computation based on partial instantiation

University of British Columbia

Various methods have been presented for efficiently evaluating deductive databases and logic programs. It has been shown that mixed integer programming methods can ef fectively support minimal model, stable model and well-founded model semantics for ground deductive databases. However, the “groundness” requirement is a huge draw back because the ground version of a logic program can be very large when compared to the original logic program. A novel approach, called partial instantiation, has been developed recently which, when integrated with mixed integer programming methods, can handle non-ground logic programs. The goal of this thesis is to explore how this integrated framework based on partial instantiation can be optimized. In particular, we have developed an incremental algorithm that minimizes repetitive computations for re ducing the size of a program. We have also developed several optimization techniques to further enhance the efficiency of our incremental algorithm, to further reduce the size of a logic program, and to avoid redundant node expansion in partial instantiation tree. Experimental results have shown that our algorithm and optimization techniques can bring about significant improvement in run-time performance. Last but not least, we have implemented the integrated framework of partial instantiation under UNIX envi ronment.

Thesis/Dissertation

application/pdf

2009-03-05

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/5559

Computer Science

University of British Columbia

UBCV

DSpace