Next: Transforming Relational Languages Up: Determinism Transformation Previous: Determinism in Relational

## Restricting the Query Set

As was shown in the previous subsection, determinism analysis requires to consider not only the clauses of a single predicate but also the whole program and a set of queries. This gives rise to two problems:

1. usually the set of all queries is not known for a program
2. the set of all queries is infinite in most cases

These problems can be solved in the following ways:

1. The set of all possible queries is not supplied by the user but determined by global analysis. In this case, only very few restrictions of the query set can be found: predicates with numerical or other type restricted builtins are used to determine the types of some variables which are then propagated through the whole program by abstract interpretation. The (usually infinite) set of possible queries is then represented by a finite set of type restrictions.
2. The user declares types and/or modes for some or all predicates. Modes specify whether an argument is always free, bound, or ground when a predicate is called. These types and modes are then propagated by abstract interpretation to obtain a finite set of type and mode restrictions for as many predicates as possible.

In this work, a simplified version of the second solution was chosen: since PROLOG is (usually) untyped, only mode declarations are considered. A mode analyzer, e.g. the one described in [\protect\citeauthoryearKrause1991], can then be used to refine the set of mode descriptions, thus further restricting the query set.

In the following, a set of mode descriptions, either only declared by the user or refined with a mode analyzer, is assumed to be present. Only two modes are used: ground, which is denoted by , and any (i.e. unrestricted), which is denoted by . For a predicate , the mode declaration is of the form with .

Next: Transforming Relational Languages Up: Determinism Transformation Previous: Determinism in Relational

Harold Boley & Michael Sintek (sintek@dfki.uni-kl.de)