Precise complexity analysis for efficient Datalog queries

Given a set of Datalog rules, facts, and a query, answers to the query can be inferred bottom-up starting with the facts or top-down starting with the query. For efficiently answering the query, top-down evaluation is extended with tabling that stores the results of the subqueries encountered, and bottom-up evaluation is done on rules transformed based on demand from the query. This paper describes precise time and space complexity analysis for efficiently answering Datalog queries, and precise relationships between top-down evaluation with tabling and bottom-up evaluation driven by demand. We first present a systematic method for precisely calculating the worst-case time and space complexities of top-down evaluation with tabling. We then describe a method for transforming the rules for efficiently answering queries using bottom-up evaluation of the transformed rules; the method is akin to the magic set transformation, but is simpler and produces simpler rules that yield exponentially smaller space in the number of arguments of predicates. Next, we establish precise relationships between top-down evaluation with tabling and bottom-up evaluation of rules transformed based on demand. Finally, we support our analyses and comparisons through experiments on benchmarks from OpenRuleBench.