# 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.