ABSTRACT
The bottom-up evaluation of a datalog program gives a definite meaning to any program, and also provides a decision procedure for any query. To have a decision procedure means firstly that we can always tell whether a statement in datalog is a conclusion of a given program by testing whether it is present in the perfect model computed by the semi-naive bottom-up algorithm starting with the given EDB. Secondly, for an algorithm to be a decision procedure, it must always terminate. The semi-naive bottom-up algorithm for datalog always terminates.
