single solution predicates and deductive DBs

[Don Smith]

Hello,

A while ago we discussed single-solution predicates on this list.     
Below are some references about work in the deductive database 
community on the similar topic of "choice operators."

In short, if you're looking for a respectable semantics for single
solution predicates, you can find one in these works.  One basic idea
is that in a program with negation there are often multiple, minimal 
models.   The semantics for a single-solution predicate is to
asymmetrically choose one of those models.

To illustrate, suppose you have a procedure

  p(a).
  p(b).

and you want to choose one solution arbitrarily. Rewrite the program
as

  p(X):- p_aux(X),not exists(Y, (Y\=X,p_aux(Y))).
  p_aux(a).
  p_aux(b).

This program has two minimal models. Choose one as your solution.

Asymmetry is beautiful!

    Don (dsmith at cs.waikato.ac.nz)
------------------------------------------------------------------
Domenico Sacca, Carlo Zaniolo:
Non-Determinism in Deductive Databases. DOOD 1991: 129-146

Gerge Greco, Carlo Zaniolo, Sumit Ganguly: Greedy by Choice. PODS 1992: 105-113

Luca Corciulo, Fosca Giannotti, Dino Pedreschi, Carlo Zaniolo:
Expressive Power of Non-Deterministic Operators for Logic-based Languages.
Workshop on Deductive Databases and Logic Programming 1994: 27-40

Programming with Non-determinism in Deductive Databases", Annals of Mathematics
     and Artificial Intelligence, to appear.  Zaniolo.

"Deterministic and Non-Deterministic Stable Models", Journal of Logic and
     Computation, to appear.  Zaniolo.