Language Constructs for a Datalog Compiler

Deductive databases promise that an important part of the application program can be developed in a declarative language, seamlessly integrated with the query language. The author is currently developing a Datalog-to-C++ compiler that implements the “Push” method for bottom-up evaluation. While such a compiler is certainly not a typical database application, our goal is to write a significant portion of it in an extended Datalog language. In this paper, we propose some extensions of the Datalog language that are needed for our application: (1) templates for declarative output, (2) arrays/tuples as a restricted form of structured terms, (3) a way to assign integer levels based on orders (e.g. for computing stratifications). All is done in a way such that termination is guaranteed. Termination is also considered for arithmetic computations.