What will be covered ?

• Queries
• Backtracking: The Searching Mechanism

Example: From Ghezzi p 385
The transitive closure of rel.

1. relation(a,b).
2. relation(a,c).
3. relation(b,f).
4. relation(f,g).
5. closure(A,B) :- relation(A,B).
6. closure(A,B) :- relation(A,Z), closure(Z,B).

Try  -> trace.  in prolog to view the execution steps.
See Brassard&Bratley problem 8.18
The  code below will abreviate relation to rel and closure to clos.
This is very similar to code presented page 631, Scott.

---

Queries

• A functional program is defined by a set of functions.  Its execution is driven by evaluation of expressions.  
• A logic program is as a set of rules; its executions answer a given query.
• A query has the following form: t₁, t₂, ... t_k
Formal semantics :  t₁ AND t₂ AND ... t_k
Informally: Can we prove that   t₁ and t₂ and ... t_k  are true from the database of facts?
• Queries are also called goals and individual terms subgoals.
• The prolog runtime system will use the database of facts to deduce a goal.  If it is successful, it will return yes, otherwise no.
  Yes => Prolog can deduce some fact.
  No => a failure to deduce some fact.
  Rules cannot be used to deduce a negative facts.

• Queries with variables:
  ?- rel(X,f).
  X = b;
  false.
  means, set of all X such that <X,f> is in rel

  ?- rel(a,X).
  X = b;
  X = c;
  false.

  means, set of all X such that <a,X> is in rel

  ?- rel(a,X), rel(X,f).
  X = b;
  false.

  means, set of all X such that <a,X> is in rel AND <X,f> is in rel

  ---

• Adding more complicated rules:
   
  rel(a,b).
  rel(a,c).
  rel(b,f).
  rel(f,g).
  clos(A,B) :- rel(A,B).
  clos(A,B) :- rel(A,Z), clos(Z,B).
   
1) for all A,B,  <A,B> is in clos if <A,B> is in rel
    i.e. <A,B> is in the closure if <A,B> a relation
2)OR
    for all A,B in clos  if there exists an Z such that <A,Z> is in rel AND <Z,B> is in clos
    i.e. <A,B> is in the closure if the is a relation from A to some atom Z and then a closure from Z to B.

?- clos(b,X).
X = f ;
X = g ;
false.

?- clos(a,f).
true . 

---

Control in Prolog

A prolog program contains

Program evaluation strategy: characterized by two decisions: