From Rules to Analysis Programs with Time and Space Guarantees

			     Y. Annie Liu
		 State Univ of New York at Stony Brook

While there are many special ways to specify analysis of complex data,
relational rules simplify and generalize them.  Such rules are used
explicitly or implicitly in business processes, biological analysis,
analysis of computer programs, and many other applications.
Programming each kind of analysis by hand is a daunting recurring
task, but doing the analysis using a general evaluator program on any
particular set of rules incurs a significant overhead and does not
provide good performance guarantees.  We have developed a method for
automatically generating efficient specialized programs for analysis
problems specified using Datalog, a general logic database query
language based on relational rules.  The method provides precise
guarantees for both the running time and space consumption for the
generated analysis programs.

This result is based on a general transformational method that makes
computation proceed in an iterative and incremental fashion, analogous
to integration by differentiation in calculus.  The method also
exploits sophisticated structures for storing and accessing complex
data.  Both time and space complexities of the generated programs are
optimal in a precisely defined sense.  We apply the method to a number
of analysis problems, some with improved time complexities and all
with greatly improved algorithm understanding and greatly simplified
complexity analysis.

(joint work with Scott Stoller)