Logic databases

Introduction

Now we look at logical databases. Logic programs used this way are extentions to the relational database model. Facts are used to define relations, such as father(Father,Child), while rules can be used to define operations, such as selection and projection, of the relational algebra.

The first thing we need to do (and which we will do from now on) is to give the relation scheme for each relation. In other words, we want to specify (part of) the intended interpretation for each relation. (We also need to specify what we intend by the relation itself.) For example, if we want to define the predicate employ/2, we might give the relation scheme employ(Employer,Employee) to indicate that the first argument of the relation employ is the employer of the second argument of the relation, the employee.

Rules can be used to defined new relations. Suppose we have the following database of facts:

% male(Person)
male(john).
male(bob).
male(wolfgang).
male(frank).
male(billy).
male(bill).

% female(Person)
female(sally).
female(ardelia).
female(susan).
female(nancy).
female(beverley).
female(genvieve).

% parent(Parent,Child)
parent(wolfgang,sally).
parent(wolfgang,susan).
parent(wolfgang,bob).

parent(ardelia,sally).
parent(ardelia,susan).
parent(ardelia,bob).

parent(nancy,beverley).

parent(frank,beverley).

parent(bill,wolfgang).
parent(bill,nancy).

parent(genvieve,wolfgang).
parent(genvieve,nancy).

We can define the predicate mother/2 to capture the motherhood relationship,

mother(Mother,Child) <- female(Mother), parent(Mother, Child).

If we try to define capture the sibling relationship, we run into a difficulty:

sibling(Person1,Person2) <- parent(Parent,Person1),
parent(Parent,Person2).

sibling(Person1,Person2) <- parent(Parent,Person1),
parent(Parent,Person2), Person1 =/=  Person2.

Recursive rules

For example, suppose that we have the following facts about how nodes a, b, c, d, e, and f are connected.

% connected(N,M) is true if node N is connected to node M
connected(a,b).
connected(b,c).
connected(c,d).
connected(c,e).
connected(c,f).
connected(d,f).

Then we can define a predicate linked/2 which is true of two nodes if there is a sequence of connections starting at the first node, and finishing with the second node, with link the two nodes together.

% linked(X,Y) is true if sequence of connections, starting at node
% X and finishing at node Y, which together define a path from X to Y

linked(X,Y) <-connected(X,Z), linked(Z,Y).

The first clause of the definition of the predicate linked/2 is the base case of the recursion: the simplest way in which there is a path between two nodes is if they are directly connected to each other.

The second clause of the definition is the recursive case, which expresses that another for two nodes X and Y to be linked is if there is some node Z, to which X is connected, which is linked (N.B. recursion) to Y.

Recursive procedure "design secrets"

1. You must have a base case and a recursive step.
2. The condition for using the base case must be satisfiable (e.g., round-off errors might make the condition x=y unsatisfiable, so it might be better to test whether |x-y| <= eps, for some small number eps.)
3. The recursive step must break the problem down into smaller (or simpler) pieces, and it must move you closer to the base case. It is also important that the recursive step moves closer to the base case in such a way that the condition for the base case will be satisfied (e.g., if the condition for the base case is that x=0, and the recursive step decreases x by 2, then the condition for the base case will not be met whenever x is odd.)

Answering a ground query

Example

How would we answer the (ground) query linked(a,c)?

Choose a rule

from the program which has the predicate linked/2 as its head. Suppose we choose the rule linked(X,Y) <-connected(X,Y).

Modus Ponens

says to deduce an appropriate ground instance of the body of the rule, i.e. connected(a,c). This is called (REDUCTION)

Fail

as this is not a logical consequence of the given logic program: there is no rule which we can use to deduce this.

Choose a rule

again from the program which has the predicate linked/2 as its head. Suppose that this time we choose linked(X,Y) <-connected(X,Z), linked(Z,Y).

Modus Ponens

says to deduce an appropriate ground instance of the body of the rule, i.e. connected(a,b), linked(b,c). (Note that there is a choice required; here we have magically chosen the correct instance.)

Choose a goal

to prove from the conjunctive query connected(a,b), linked(b,c) (this conjunctive query, the thing which we still need to deduce, is called the RESOLVENT).

etc ...

continue until the resolvent is empty (i.e. there are no more goals to deduce).

structured data

book(theArtOfProlog,
     leon,
     sterling,
     mit_press,
     2,
     1994).

publisher(Title,Publisher) <-
     book(Title,_,_,Publisher,_,_).

We can use the versatility afforded us by the structure of terms (recall that terms are the only data structure in logic programming) to structure our data:

book(title(theArtOfProlog),
     author(first(leon),last(sterling)),
     publisher(mit_press),
     copyright(edition(2),year(1994)).

publisher(Title,Publisher) <-
     book(Title,_,Publisher,_).

Return now to the example above. Suppose that we not only want to know whether two nodes are linked or not, but that we also want to know the possible paths between the nodes. (If you are at UBC and want to go to Richmond centre, it doesn't help much simply to know that you can get from UBC to Richmond centre, you also want to know which buses will take you there.)

Let's define the predicate path/3 as follows.

% path(X,Y,P) is true if X and Y are linked (as defined previously)
% and P is a representation of the path which links X and Y.

path(X,Y,cn(X,P)) <-connected(X,Z), path(Z,Y,P).

Here is how this works:

| ?- path(a,b,P).

P = cn(a,b) ? ;

no
| ?- path(a,c,P).

P = cn(a,cn(b,c)) ? ;

no
| ?- path(f,a,P).

no
| ?- path(a,f,P).

P = cn(a,cn(b,cn(c,f))) ? ;

P = cn(a,cn(b,cn(c,cn(d,f)))) ? ;

no