Unnecessary backtracking is a principal source of inefficiency in Prolog execution. In order
to avoid the overhead of the general backtracking mechanism, determinate programs should
be executed deterministically. Achieving this requires an automatic means of extracting determinacy.
We present a method in which determinacy is inferred from the success conditions
and the calling contexts of predicates. Unlike previous approaches that rely on cuts or use a
limited notion of test predicates, we propagate the conditions to detect determinacy, enabling
us to handle a much larger class of programs. Since the conditions are propagated explicitly,
the power of the method can be readily increased by increasing the expressiveness of these conditions.
Moreover, our approach provides a uniform treatment of calling contexts and success
conditions, and clearly spells out their roles in inferring determinacy. We also describe how determinacy
information can be combined with state-of-the-art indexing techniques to efficiently
realize the benefits of determinism.