Assignment #1 (Solution Sketches)

Date Assigned: Friday, Jan. 23, 1998
Date Due: Friday, Feb. 6, 1998

```
query1(X,Y,Z) :- works(X,"First Bank Corporation", S), S>10000, lives(X,Y,Z). 

query2(X) :- manages(X,Y), lives(X,S,C), lives(Y,S,C).

query3(X) :- 

query4(X) :- manages(X,"Kathy").
qeury4(X) :- manages(X,Y), query4(Y).
```
While queries 1,2 and 3 could be expressed very succinctly in RDBMSs, the relational model is not expressive enough for expressing recursive queries like 4. This requires the logical model of database systems.
And PROLOG fails to work for the ancestor problem because it goes into an infinite loop trying to satisfy it, from the order in which we have given the clauses. This has to do (i) with the left recursive way in which the first clause is written and (ii) the depth-first nature of PROLOG's search strategy. A simple reordering of the terms will rectify the situation.
The first thing to note from this exercise is that we are trying to do some kind of non-monotonic inference. This process is referred to as abduction where given that the consequent of an implication is true, we wish to say with some degree of confidence that the antecedent is indeed also true. Notice that the other way is pure logic based deduction. This behavior is very useful for diagnostic expert systems, as mentioned in the question.
In a strange way, at least to some extent, PROLOG implements a non-monotonic kind of behavior (not really abductive). One reason is because of the "closed-world" assumption that makes it treat negation as failure. In other words, if it is not able to prove something, it certifies that it is false. For the given facts,
```
nostart(X) :- nogas(X).
nostart(pontiac).
```
If we make the query nogas(pontiac), we get the answer no, meaning that such a fact does not exist in the database. If we were to add the fact nogas(pontiac), then we will get an answer "yes" for the same query. The databse then will look like:
```
nostart(X) :- nogas(X).
nostart(pontiac).
nogas(pontiac).
```
Notice that now the second fact becomes redundant because it can be inferred from the first and the third. In this sense, PROLOG is safe to treat "negation as failure" as the extended database is closed under inference. That is, doing any new inference does not contradict old information. I must caution that these are really murky waters because it is not trivial to compute extensions to a database so that it remains closed under inference.
To do the kind of abductive reasoning that we are talking about, we need to resort to the inductive capabilities of a system like PROGOL. Notice that in a system like PROGOL, the process of rule induction follows the equation Induction = Abduction + Justification. In other words, abduction is used to construct a "plausible" hypothesis, then the system tries to justify the abduction by determining factors such as cover, degree-of-confidence before accepting them as intensional knowledge.
Here's a solution for the gcd exercise. It is self-explanatory.
Here's a very good solution by Vassilios Verykios.