ylfink@water.waterloo.edu (ylfink) (03/21/88)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
RECRUITING/DATABASES SEMINAR
- Thursday, March 24, 1988
Dr. Weining Zhang, of the University of Illinois at
Chicago, will speak on ``A Linearization of Non-linear
Recursive Programs in Logic Databases''.
TIME: 3:30 PM
ROOM: MC 6082
ABSTRACT
The efficiency of recursive query processing has been a
central issue of research on logic databases. Roughly
speaking, recursive rules can be classified into linear
rules and non-linear rules. Usually, evaluation
methods dedicated to process linear rules are more
efficient than those to process non-linear rules. We
observe that many syntactically non-linear recursive
rules are in fact semantically equivalent to linear
recursive rules. Thus, by transforming the former type
of rules into the latter type, we are able to use the
efficient evaluation methods. Our work is to
characterize the non-linear recursive rules which can
be converted into equivalent linear recursive rules. A
simple conversion method will be given to transform a
non-linear rule into a linear one. We will present a
necessary and sufficient condition for a simple doubly
recursive rule to be equivalent to a linear rule
obtained by the conversion. An extension of the
analysis to higher order recursive rules will also be
discussed.