DeAL TutorialChoice

Nondeterministic Reasoning: Choice

The set-oriented semantics of logic programs lead to the generation of all answers satisfying a given set of rules. In many practical situations, there is the need for picking an element out of a set of candidates in nondeterministic fashion. Interesting enough, choosing an element can be viewed as enforcing a functional dependency constraint.

Example: Say that, our university database contains facts describing professors and fact describing students. In fact, say that our toy database contains only the following facts:

student('Jim Black', ee, senior).

professor('Ohm', ee).
professor('Bell', ee).

Now, the rule is that the major of a student must match his/her advisor's major area of specialization. Then eligible advisors can be computed as follows:

eligadv(S, P) <- student(S, Major, Year), professor(P, Major).

This yields:

elig_adv('Jim Black', 'Ohm')
elig_adv('Jim Black', 'Bell')

But, since a student can only have one advisor, a choice goal will be used to force the selection of a unique advisor, out of the eligible advisors, for a student. Thus we obtain the following choice rule:

actualadv(S, P) <-  student(S, Major, Levl), professor(P, Major), choice((S),(P)).

The goal can also be viewed as enforcing a functional dependency (FD); thus, in elig_adv, the second column (professor name) is functionally dependent on the first one (student name).

The result of executing this rule is nondeterministic. It can either give a singleton relation containing either of the following two tuples:

elig_adv('Jim Black','Ohm')
elig_adv('Jim Black','Bell')

A rule (program) where the rules contain choice goals is called a choice rule (program).

The semantics of a choice program P can be defined by transforming into a program with negation, SV(P), called the stable version of P, which exhibits a multiplicity of total stable models, each obeying the FDs defined by the choice goals.

The use of choice is critical in many applications. For instance, the following nonrecursive rules can be used to determine whether there are more boys than girls in a database containing the unary relations boy and girl:

Example: Are there more boys than girls in our database?

match(Bname, Gname) <- boy(Bname), girl(Gname), choice((Bname),(Gname)), choice((Gname), (Bname)).
matchedboy(Bname) <- match(Bname, Gname).
moreboys <- boy(Bname), ~matchedboy(Bname).

The most significant applications of choice involve the use of choice in recursive predicates. For instance, the following program computes the spanning tree, starting from the source node, for a graph where an arc from node a to node b is represented by the database fact g(a,b):

Example: Computing a spanning tree

st(root,a).  
st(X, Y) <- st(_, X), g(X, Y), Y ~= a, choice((Y),(X)). 

In this example, the goal ensures that, in st, the end-node for the arc produced by the exit rule has an in-degree of one; likewise, the goal ensures that the end-nodes for the arcs generated by the recursive rule have an in-degree of one.

Example: Ordering a domain

ordered-d(root,root). 
ordered-d(X, Y) <- ordered-d(_, X), d(Y), choice((X),(Y)), choice((Y),(X)).

Example: The sum of the elements in d(X)

sumd(root, root, 0) <- d(_).
sumd(X, Y, SY) <- sumd(, X, SX), d(Y), choice((X),(Y)), choice((Y),(X)), SY = SX + Y.
totald(Sum) <- sumd(_, X, Sum), ~sumd(X, _, _).

If we eliminate the choice goal from this program we obtain a program that is stratified with respect to negation. Stratified choice programs always have stable models. Moreover, these stable models can be computed by strata, as any other stratified program.

The choice construct is significant for both nondeterministic and deterministic queries. A nondeterministic query is one where any answer out of a set is acceptable. For instance, in the previous example where an advisor was assigned to a student. The use of choice to compute a deterministic query is illustrated by the sum example - the sum of the elements of a set is independent from the order in which these are visited.


Last Updated 2014