Recursive query languages such as Datalog make "knowledge-base" systems highly expressive. However, such languages are difficult to compile into efficient code. This project will combine work on high level program transformations with techniques developed for logic databases to produce a Datalog compiler that will give cleaner and more efficient code than has been currently reported. In particular, transformations will be used that translate systems of fixed point equations into procedural programs that are further improved by finite differencing (a transformation that uncovers and implements critical invariants). The resulting code would then be amenable to more conventional optimization techniques. Two other related problems will be investigated, (1) to give the compiler the capability to analyze performance mechanically; and (2) to incrementally compute relations recursively defined in Datalog clauses.
