Next: Full RELFUN Exemplified Up: DATAFUN as a Previous: Footed Rules and

Non-Determinism, DATALOG Relationalizing, and WAM Compilation

While free calls for the inversion of the area and density functions produce non-deterministic results, the area and density definitions themselves are deterministic. In RELFUN non-deterministic function definitions are also allowed, which return more than one value even for ground calls.

For instance, the subfield relation of the DATALOG example in subsection 2.1 could be extended non-deterministically, expanded by a transitive-closure version subclosure, and transcribed into a function definition, as in the following DATAFUN example:


subfield(engineering) :-& mechanics.
subfield(engineering) :-& architecture.
subfield(architecture) :-& bridgebuilding.
subclosure(Field) :-& subfield(Field).
subclosure(Field) :-& subclosure(subfield(Field)).
applicable(pharmacy,medicine).
applicable(computerscience,bridgebuilding).
applicable(computerscience,computerscience).
applicable(Tool,Field) :- applicable(Tool,subclosure(Field)).
In this knowledge base the ground call subfield(engineering) non-deterministically returns the values mechanics or architecture; finding a subfield path from engineering to bridgebuilding, applicable(computerscience,engineering) returns true. Note that the operator applicable itself is left a relation but its former Horn rule using a flat relational conjunction became a hornish rule that nests the (non-deterministic!) subclosure function into the recursive call. The original relational form could again be mimicked using an is-call, leading to

applicable(Tool,Field) :- Sub is subclosure(Field), applicable(Tool,Sub).
This flattening of the applicable definition exemplifies the first step of RELFUN's relationalize transformation leading from DATAFUN clauses to DATALOG clauses. The second step introduces extra arguments for values returned in an is-rhs or in the foot, where new first (not: last) arguments are used to cope with varying-arity DATAFUN (``|''-calls); denotative foots directly become the extra argument of the conclusion while evaluative foots generate a new variable (from _1, _2, ...) used as the extra argument of both the foot and the conclusion. Thus, the relationalized form of the above DATAFUN example is

subfield(mechanics,engineering).
subfield(architecture,engineering).
subfield(bridgebuilding,architecture).
subclosure(_1,Field) :- subfield(_1,Field).
subclosure(_2,Field) :- subfield(_1,Field), subclosure(_2,_1).
applicable(pharmacy,medicine).
applicable(computerscience,bridgebuilding).
applicable(computerscience,computerscience).
applicable(Tool,Field) :- subclosure(_1,Field), applicable(Tool,_1).
Besides this kind of RELFUN-to-PROLOG translation we have implemented a more direct WAM compilation of non-deterministic, non-ground functions [Bol90]: the WAM temporary register X1 (identical to the argument register A1) is also used for passing returned values, so that first-argument nestings need not be flattened because the caller directly finds the returned value of the first callee in argument register X1.



Next: Full RELFUN Exemplified Up: DATAFUN as a Previous: Footed Rules and


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