Program Queries: Declarative Specifications for Program Properties

Program queries are an appealing way of writing properties of programs: using a declarative query language such as Datalog, program properties can be expressed concisely, paving the way for user-written correctness queries (for instance to enforce project-specific coding conventions)

The real challenge, however, lies in strategies for executing such queries efficiently. My recent work has been concerned with optimisations of Datalog programs to improve query times. One such optimisation is the magic sets transformation, a well-known optimising transformation from the databases community. We found that in order to apply magic sets effectively on automatically generated Datalog programs, however, a novel way of determining the best order in which to consider goals in a query was necessary. This led to very substantial performance improvements in running queries.

References

• Type Inference for Datalog and its Application to Query Optimisation (to appear in PODS 2008)
• Adding Magic to an Optimising Datalog Compiler (to appear in SIGMOD 2008)