| Rule systems have seen an upsurge of interest in the past decade, as many in the academia and industry started to discover more applications for rules such as the Semantic Web, policy management, and program analysis. In response, high-level logic languages such as Flora-2 and SILK have been invented as tools for developing complex knowledge bases by knowledge engineers who are not programmers. The knowledge bases that are created by this type of users are typically complex and they stress the engine capabilities. Therefore, there are new challenges in order for logic engines to be able to process these knowledge bases, and this thesis focuses on two of them: non-termination analysis and cost-based optimization.;Non-termination analysis examines program execution history when the program is suspected to not terminate and informs the programmer about the exact reasons for this behavior. We study the problem of non-termination in tabled logic engines and propose a suite of algorithms, called non-Termination Analyzer or Terminyzer, which analyze forest logging traces of program execution and output sequences of tabled subgoal calls and their host rule ids that cause non-termination. Moreover, Terminyzer identifies the precise set of subgoals, together with their host rules, that recursively call one another and lead to non-termination. Terminyzer also attempts to automatically rectify non-terminating programs by heuristically fixing some causes of misbehavior.;Besides the non-termination problem, cost-based optimizations similar to those in Database systems are needed in order for rule systems to be practical in processing complex queries against large knowledge bases. To this end, this thesis proposes a Cost-based optimizer, called Costimizer, which first efficiently estimates predicate statistics and then applies them to greedily optimize rules and queries. Costimizer performs size estimation through an abstract evaluation of rules and it distinguishes itself from previous size estimation approaches by efficiently preserving argument dependencies.;Terminyzer and a prototype of Costimizer have been implemented for Flora-2 and SILK. Their effectiveness and practicability have been validated through extensive experimental studies. |
