University of British Columbia
Optimizations for model computation based on partial instantiation
Abstract
dc:descriptionVarious 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.
Degree
thesis:*- Name thesis:degree_name
- Master of Science - MSc
- Level thesis:degree_level
- master's
- Discipline thesis:degree_discipline
- Computer Science
- Grantor dc:publisher
- University of British Columbia
- Year dc:date
- 1994
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Tian, Xiaomei
Rights
dc:rights- Statement dc:rights
-
- 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.
- Language dc:language
- eng
Identifiers
dc:identifier.*- Handle dc:identifier
- http://hdl.handle.net/2429/5559