Bottom-up beats top-down for datalog

Jeffrey D. Ullman

1989 · 119 citations · 11 references

Concepts

Abstract

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.

References

11