Database the Prolog way
Written by Mike James   
Friday, 24 September 2010
Article Index
Database the Prolog way
Compiling Prolog
A complete Prolog program

Using the compiler

After you have entered the list of clauses you use Compile,Compile Buffer in the editor. Provided this finds no errors it adds the compiled code into the runtime and you can interact with it using the main SWI Prolog window.

Switch from the editor to the main SWI Prolog window. Here you can type in "live queries" i.e. anything you type in will be immediately evaluated as true or false.

To indicate that you have finished a query you type a full stop.

For example, if you type in:

adjacent(paddington,warwick_avenue,
                            bakerloo,1).

the system will print back at you

true

Because this is a "fact" you have included in the database. If you type in

adjacent(paddington,warwick_avenue,
                            bakerloo,2).

it will return the result

false

because that fact is not in the database.

So far so good but not impressive.

Now try:

adjacent(paddington,warwick_avenue,X,T)

in this case the system comes back with:

X = bakerloo,
T = 1.

Now this should be more impressive. You have specified two "variables" X and T and the Prolog system has searched through the clauses to find values of X and T that make the query true. If it couldn't find such values then it simply fails and returns false. Yes - Prolog contains a built in search algorithm.  In fact the search algorithm is quite sophisticated and able to use rules and clauses to find values that satisfy complicated queries.

The question of how to get from one station to another is one such query.

 

To answer it you would have to know and be able to apply the simple rule that every human knows about connectivity -

If A is connected to B

and B is connected to C then

A is also connected to C

Using this rule you could scan through the database and build up chains of stations that were adjacent and that formed a route between the starting and finishing stations of your journey.

This is not something that most databases can manage easily but in Prolog you can state the connectivity rule as

connect(X,Y):-adjacent(X,Z,_,_),
                       connect(Z,Y).

This simply says that station X is connected to station Y if there exists a station adjacent to X that is connected to Y. If you add to this the rule. Where the comma between the two is read as And. The underscores simply mean that we don't care what the values of something are. Prolog will try to find values of X, Y and Z that make the clause true. If you enter the connect clause into the file and compile it you can try out the query:

connect(paddington,warwick_avenue).

Notice that the two stations are not directly connected but Prolog works out that they are connected by and intermediate and prints true. However if you try the same thing out with two stations that are directly connected then you will find it works out to false. The clause as written only defines stations that are connected by an intermediate and doesn't include directly connected stations. To include this case you need another clause:

connect(X,Y):-adjacent(X,Y,_,_).

which covers the special case when X and Y are adjacent stations then you virtually have a Prolog program to find a route between two stations.

Notice that there is more going on here than you might think. The Prolog program as written will discover that:

connect(edgware_road,maida_vale).

is true. Notice that to do this it has to find the chain

edgware_road->paddington->
         warwick_avenue->maida_vale

That is it has had to find two intermediate stations. Also notice that there is at least one route starting at edgware_road that doesn't lead to maida_vale. What this means is that Prolog not only has a simple search built in but a search which can backtrack when it initially goes the wrong way. 

If you ignore the data clauses that define how the stations are connected you have to admit that this is powerful stuff coming from just two Prolog instructions:

connect(X,Y):-adjacent(X,Z,_,_),
                          connect(Z,Y).
connect(X,Y):-adjacent(X,Y,_,_).

In practice all we need are some extra statements to keep track of the list of stations on the route but the rest is more or less fine detail and mechanics. But this simple demonstration shows the power of Prolog - it allows you to turn statements that concern the relationships between the data in the database into programs which access the data. In fact there is almost no distinction between the statement of a relationship and its use.

For example, it is obvious that if adjacent(X,Y) then it is also the case that adjacent(Y,X) so why bother entering both into the database. In Prolog you can state is obvious symmetry as

next(X,Y):-adjacent(X,Y,_,_).
next(X,Y):-adjacent(Y,X,_,_).

which can be read as saying that stations X and Y are next to each other if X is adjacent to Y or Y is adjacent to X. If you include this statement in a Prolog program then that is almost all you have to do. From then on questions about X being next to Y will be answered correctly even if you have only entered one of the two pieces of information about adjacency.

You can carry on adding rules that define how the data should be interpreted until you can answer very complex queries.

<ASIN:013138645X>

<ASIN:3540629718>

<ASIN:1432749366>

<ASIN:0262514451>

<ASIN:3540006788>



Last Updated ( Friday, 24 September 2010 )
 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.