KALANTARI@RED.RUTGERS.EDU.UUCP (02/16/87)
RUTGERS COMPUTER SCIENCE AND RUTCOR COLLOQUIUM SCHEDULE - SPRING 1987
Computer Science Department Colloquium :
Here is summary of speakers:
Date(Feb), Time, Place(Hill), Speaker Title
18, 9:50 ,705, Raghu Ramakrishnan,EVALUATING DATA INTENSIVE LOGIC PROGRAMS
18, 4:30, 525, Allan Borodin,Parallel Complexity of Algebraic Problems
19, 2:50, 705, Victor Pan, Parallel Nested Dissection for Path Algebra
Computations
20, 2:50, 705, Ben Cohen, "Knowledge-Based CAD-CAM Software Integration."
DATE : Wednesday, February 18
SPEAKER: Raghu Ramakrishnan
AFFILIATION: University of Texas at Austin
TITLE: EVALUATING DATA INTENSIVE LOGIC PROGRAMS
TIME: 9:50
PLACE: Hill 705
ABSTRACT
There has been considerable interest recently in the problem of
evaluating @u[logic queries] against relational databases. The
evaluation methods that we consider rely upon @i[bottom-up fixpoint
computation], which, unlike Prolog's depth-first strategy, is
@i[complete]. These methods also take advantage of efficient database
join techniques. The major criticism of such methods is that they do
not fully utilize the constants in the query to restrict the search
space, and thus perform unnecessary computation. Such constants are
used by Prolog through a process of @i[sideways information passing],
since variable bindings generated in solving a goal restrict the
search space in solving subsequent goals.
We define @i[sideways information passing] formally. Given a program,
we show that any sideways information passing strategy may be
implemented by rewriting the program and evaluating the rewritten
program bottom-up, thus answering the above criticism. We describe
several rewriting algorithms, generalizing some of the bottom-up
methods described in the literature - Magic Sets, Counting, and their
variants - to work with arbitrary logic programs. We also present the
results of a performance analysis which provides some insight about
the relative cost of these methods.