Database The Prolog Way
Written by Mike James   
Wednesday, 10 December 2014
Article Index
Database The Prolog Way
Compiling Prolog
A complete Prolog program

Some Queries

If you are using the downloaded compiler 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.

If you are using the online version you don't have to compile anything as it is done for you. To interact with the "data" you simply type into the query window which is at the bottom right. 

Switch from the editor to the main/query 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 display

true

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

swish2

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.

Searching For Unknowns

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

This isn't quite all we need because connect is defined recursively and we need a case to stop the recursion. Two stations are obviously connected if they are immediately adjacent:

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

This rule defines the simplest meaning of connected. 

Prolog will try to find values of X, Y and Z that make the clause true. If you enter the connect clauses into the database you can try out the query:

connect(paddington,maida_vale).

Notice that the two stations are not directly connected but Prolog works out that they are connected by and intermediate and prints true. You will also notice that it prints false as well in the online version. This is because it also reports results of searches that fail. 

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

connect(edgware_road,nottinghill_gate).

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

edgware_road->paddington->bayswater->nottinghill_gate

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. The online version gives you information on these "back tracked" searches. 

That is Prolog contains a complete search algorithm with "back tracking". That is if you are searching for a set of values X, Y and Z to make a clause true Prolog with try a value for X and Y and then try all values of Z. If it finds a value of Z that makes the clause true then the search stops. If it doesn't it backtracks and changes the value of Y and starts the search on Z again. This continues until all values of Y have been tried when it backtracks again to X and tries the whole search over with a new value of X. This is why Prolog is so good a finding values that satisfy a set of conditions - it comes with a built in sophisticated search.  

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. 

 

The Full Tube

The next example is a complete Prolog program that  will not only tell you whether one station is connected to another, but will give you the route and tell you if and where you have to change.

It can only handle one change of line and it doesn't attempt to find the best route in terms of time but it would be very easy to extend the program to include these features.

Of course this is more complicated than the simple example given earlier but not that much more complicated and given what it does it's remarkably simple.

What we need is a clause like route(X,Y,F) where X and Y are the two stations and F is the route between them to be found.  The database for the task consists of the list of adjacent clauses as given earlier that define the part of the underground system that the program works with. As you can see this is fairly limited but if you have a map of the underground you can extend it as you much as you like. Notice that the time between stations isn't actually used in this program, but it is included so that the program can be extended to include time considerations without invalidating the database.

adjacent(edgware_road,paddington,district,1).
adjacent(paddington,bayswater,district,1).
adjacent(bayswater,nottinghill_gate,district,1).
adjacent(paddington,warwick_avenue,bakerloo,1).
adjacent(warwick_avenue,maida_vale,bakerloo,1).

You can add extra stations to make the database more interesting.

<ASIN:013138645X>

<ASIN:3540629718>

<ASIN:1432749366>

<ASIN:0262514451>

<ASIN:3540006788>



Last Updated ( Wednesday, 10 December 2014 )
 
 

   
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.