Artículo: Metapredicate Optimization for Datalog Queries through Program Analysis
Some systems extend Datalog in order to allow the use of constructions in which several queries are composed to produce the set of resulting tuples. These constructions include outer joins, aggregate and grouping predicates, as well as, to some extent, negation. Typically, the result of such constructions depends on the subset of the tuples in the sets initially computed. In order to optimize for efficiency these compound queries, it would be interesting to determine in advance the subsets involved in the compound construct. Static analysis can be used at compile-time to infer an over-approximation of such subsets. Very precise abstract interpretation-based static analyzers have been developed for logic languages, and in particular the use of type domains allow to infer descriptive types for the arguments of a given predicate. Using the extensional description of the types inferred, the Datalog program can then be transformed to use the inferred subsets instead of the original queries. Here, we propose a source-to-source transformation of Datalog programs based on static analysis for optimizing queries involving outer join, negation, aggregate and grouping predicates. This approach has been tested in the DES system, using CiaoPP (a language preprocessor for Prolog) for inferring descriptive types. Some preliminary experiments show promising results.