id: 06104248
dt: a
an: 06104248
au: Liang, Senlin
ti: Non-termination analysis and cost-based query optimization of logic
    programs.
so: Krötzsch, Markus (ed.) et al., Web reasoning and rule systems. 6th
    international conference, RR 2012, Vienna, Austria, September 10‒12,
    2012. Proceedings. Berlin: Springer (ISBN 978-3-642-33202-9/pbk).
    Lecture Notes in Computer Science 7497, 284-290 (2012).
py: 2012
pu: Berlin: Springer
la: EN
cc: 
ut: non-termination analysis; termination analysis; forest logging; tabling;
    subgoal abstraction; derived predicate statistics; cost estimation;
    query optimization; logic programming; rule-based systems
ci: 
li: doi:10.1007/978-3-642-33203-6_33
ab: Summary: There have been many studies in termination analysis of logic
    programming but little has been done on analyzing non-termination of
    logic programs, which is even more important in our opinion.
    Non-termination analysis examines program execution history when
    non-termination is suspected and informs the programmer of
    non-termination causes and possible ways to fix them. In the first part
    of this thesis, we study the problem of non-termination in tabled logic
    engines with subgoal abstraction, such as XSB, and propose a suite of
    algorithms, called non-Termination analyzer, Terminyzer, for automatic
    detection and explanation of non-termination. The second part of this
    thesis focuses on cost-based query optimization. Database query
    optimizers rely on data statistics in selecting query execution plans
    and rule-based systems can greatly benefit from such optimizations as
    well. To this end, one first needs to collect data statistics for base
    and propagate them to derived predicates. However, there are two
    difficulties: dependencies among arguments and recursion. To address
    these problems, we implement a Cost-based query optimizer, Costimizer,
    which consists of a cost estimator and an optimizing unit. The
    optimizing unit performs a greedy search optimization based on
    predicate statistics computed by the cost estimator. We validate the
    effectiveness of Costimizer on both size estimation and query
    optimization through experimental studies.
rv: