Next: Footed Rules and Up: DATAFUN as a Previous: DATAFUN as a

Footed Facts and Non-Ground Functions

Let us consider the database example in [WPP77], containing the following DATALOG facts about country areas (given in thousands of square miles):


area(china,3380).
area(india,1139).
area(ussr, 8708).
area(usa,  3609).
Although these binary relations would permit requests like area(Cntry,8708), their normal use direction is of the kind area(ussr,Area): the large value range of possible areas makes it unlikely that a user ask for a country with a precisely given thousands-of-square-miles area such as 8708 (the problem would become even more noticeable if the exact areas were stored, perhaps as real numbers, with rounding problems etc.) Therefore, in our opinion this `historical' DATALOG example should be rewritten functionally, as already implied in [GM84]. For this we extract the second argument from the DATALOG facts and use it as the so-called foot after a ``:-&''-infix:

area(china) :-& 3380.
area(india) :-& 1139.
area(ussr)  :-& 8708.
area(usa)   :-& 3609.
The resulting special DATAFUN clauses are called footed facts, here used for the pointwise definition of the RELFUN function area mapping from country names to natural numbers. The definition emphasizes the natural area use direction, as in area(ussr), a function call returning the value 8708.

The main advantage of distinguishing an `output' argument of a relation as the returned value of a corresponding function is the possibility of nested calls such as


+(area(china),area(india),area(usa))
where the parenthesized inner applications are (not passive structures but) active function calls that return their values to the ternary + use (cf. subsection 2.2); for reasons of conciseness, program analysis, and variable elimination this is preferable to flat relational conjunctions such as

area(china,A1), area(india,A2), area(usa,A3), +(Area,A1,A2,A3)
The main disadvantage lies in the issue of inverted calls, which are easier and sometimes more logically complete for `usage-neutral' relations: a functional non-termination problem is illustrated in [Fri84]. However, RELFUN's inversion method for functions appears quite natural, and for its DATAFUN subset completeness problems do not arise. A generalized form of PROLOG's is-primitive is employed to unify the values of a free function call with the value to be used as the argument of the inverse function, where a call is free if all its (actual!) arguments are different free variables. More generally, DATAFUN (RELFUN) permits non-ground function calls which like DATALOG (PROLOG) goals may contain repeated logical variables (non-ground terms).

As a simple example with just one free variable consider 8708 is area(Cntry), the inverse function call corresponding to the above-discussed relational inversion area(Cntry,8708). Independently from the context (e.g., in an is-rhs) the free call area(Cntry) non-deterministically returns the values 3380, 1139, 8708, or 3609, at the same time binding Cntry to china, india, ussr, or usa, respectively, in the textual order of the area footed facts in the knowledge base. Within the above is-call only the third of the returned values unifies with the left-hand side (lhs), so the inversion correctly binds Cntry to ussr.

Other operators such as the exponentiation relation may be hardly or impossibly inverted, which again suggests to rewrite them as `directed' functions, leading from non-ground facts like


exp(X,0,1).
exp(X,1,X).
to non-ground footed facts like

exp(X,0) :-& 1.
exp(X,1) :-& X.
Here, the first clause has a ground foot, 1, while the second one has a non-ground foot, X (in DATAFUN this must be a variable). Non-ground foots can yield both ground and non-ground values, as in exp(2,1), returning 2, and exp(Y,1), returning Y, respectively.



Next: Footed Rules and Up: DATAFUN as a Previous: DATAFUN as a


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