Bottom-up beats top-down for datalog
Jeffrey David Ullman · 1989
We show that for any safe datalog program P1 and any query Q (predicate of P1 with some bound arguments), there is another safe datalog program P2 that produces the answer to Q and takes no more time when evaluated by semi-naive evaluation than when P1 is evaluated topdown.