Next: REL RELFUN Functions Up: Determinism Transformation Previous: Restricting the Query

Transforming Relational Languages into LL

In this subsection, the determinism analysis and the transformation steps for deeply deterministic predicates are described.

For reasons of simplicity, only the following two kinds of deeply deterministic predicates are supported:

  1. functional predicates: predicates which for a given set of ground input arguments compute a ground set of output arguments, i.e. they always compute exactly one solution and never fail (total functions)
  2. test predicates: predicates which when called with all arguments ground either fail or succeed exactly once; these test predicates are used as guards

For a program , in which the predicates are defined, and a set of mode declarations , deeply deterministic functional or test predicates are detected by the following algorithm:

  1. :
    construct a set of candidates consisting of all predicates with at least one ground argument (if all arguments are ground, the predicate is assumed to be a test predicate, otherwise it is assumed to be a functional predicate)
  2. while do :
    repeat deleting all predicates in if in their definition a predicate in is used until no such predicate in exists
  3. try to transform all predicates in into LL (with the algorithms described in the following subsections); remove all predicates from which could not be thus transformed
  4. same as 2.

In the transformation steps, several intermediate representations are used:

The following REL example will be used to demonstrate the various transformations and intermediate representations. It consists of two deeply deterministic functional predicates:

This example was chosen for the following reasons:

  1. fac (the factorial function) is used to show how the algorithms work for a simple case.
  2. f is a rather artificial function using fac. It is used to show how the algorithms handle non-standard cases:

Next: REL RELFUN Functions Up: Determinism Transformation Previous: Restricting the Query

Harold Boley & Michael Sintek (