Next: Clauses and bnd-to-is Up: Domains/Exclusions in Relation Previous: Domains/Exclusions in Relation

Facts and dom/exc Reductions

Starting with domains, the fact with a single-occurrence variable X,


likes(john,bnd[X,dom[ann,mary,susan]]).
is equivalent to the fact using the domain anonymously (regard ``X'' as ``_''):

likes(john,dom[ann,mary,susan]).

Both can be equivalently queried by (``%'' precedes comments)


likes(john,mary)  % success
likes(john,peggy) % failure
likes(john,Whom)  % success: Whom = dom[ann,mary,susan]
likes(john,dom[mary,peggy,susan])  % success
likes(john,bnd[Whom,dom[mary,peggy,susan]])
                  % success: Whom = dom[mary,susan]
likes(john,exc[mary,peggy])  % success
likes(john,bnd[Whom,exc[mary,peggy]])
                  % success: Whom = dom[ann,susan]

We can reduce the dom fact, obtaining the three `multiplied out' facts


likes(john,ann).
likes(john,mary).
likes(john,susan).
Note that the queries would be answered equivalently. However, `intensional' answers (delivering one closed dom structure) would become `extensional' answers (enumerating several constants); so the bnd/dom query, instead of binding Whom to dom[mary,susan], would first bind Whom to mary, and then, via backtracking, to susan.

If we let denote a clause with term at some position ( being the head, the first premise, ..., being 's operator/constructor, its first argument, ..., etc.) and a clause not having the term at any position, then a general algorithm can be defined recursively via an equation schema (treating queries as answer-head rules):

For example, matches the second equation via the instantiation , whose rhs's through the first equation lead to the three domless facts shown above.

Continuing with exclusions, the fact with a single-occurrence variable X,


likes(john,bnd[X,exc[mary,claire,linda]]).
is equivalent to the fact using the exclusion anonymously (since ``X'' is ``_''):

likes(john,exc[mary,claire,linda]).

Both can be interchangeably queried by


likes(john,mary)  % failure
likes(john,peggy) % success
likes(john,Whom)  % success: Whom = exc[mary,claire,linda]
likes(john,dom[mary,peggy,susan])  % success
likes(john,bnd[Whom,dom[mary,peggy,susan]])
                  % success: Whom = dom[peggy,susan]
likes(john,exc[mary,peggy])  % success
likes(john,bnd[Whom,exc[mary,peggy]])
                  % success: Whom = exc[peggy,mary,claire,linda]

If we have a `closed universe' of a finite number, say 8, of individuals, e.g. , we could reduce the exc fact, obtaining the five `complemented out' facts


likes(john,ann).
likes(john,john).
likes(john,peggy).
likes(john,susan).
likes(john,tina).
where the bnd/dom query would now first bind Whom to peggy, then, via backtracking, to susan. (These facts are also the multiplied out form of a dom fact.)

If the `non-Horn' extension of a (classic, strong) negation construct is available for facts, e.g. via false-valued functions in RELFUN, one could also approximate the exc fact in an `open universe', with infinite complements, by


likes(john,dom[mary,claire,linda]) :- ! & false.
likes(john,X).
Queries as shown above could now bind a second argument Whom to the dom by (successfully!) returning false, but would, e.g., also return a bindingless false for mary (rather than yielding unknown due to unification failure). The impurity of the cut-protected `catch-all' fact seems to favor our proposal to express such special cases of negation by the special-purpose construct exc directly in clause heads, permitting non-Horn clauses as ``Horn clauses + exclusions''.



Next: Clauses and bnd-to-is Up: Domains/Exclusions in Relation Previous: Domains/Exclusions in Relation


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