Database The Prolog Way

Page 1 of 3

Prolog - is it just a blast from the past only of interest to AI and strange language enthusiasts? Or could it just be the ultimate NoSQL database capable of things that are difficult to do without it. In this article we write a remarkably short Prolog program that can route find on London's Tube network.

AI isn't always concerned with grand schemes to create an artificial brain or something really impressive. Often its best achievements are doing things in clever ways that other approaches would find very difficult in a simple way.

You can think of this approach to AI as just advanced or clever computing.

Take for example the programing language Prolog.

You can consider this to be a language aimed at creating artificial intelligence or you can consider it to be a sophisticated database language. More NoSQL than most NoSQL approaches.

The advantage of thinking of it just like any other tool in your collection is that you might actually consider using it.

In this article we will use a free edition of Visual Prolog to solve a problem that could be solved by standard database techniques - but only with some difficulty and a lot of custom code.

But to start at the beginning....

I was constructing a database to store legal contracts relating to sales rights. This seemed easy until I reached the stage of dealing with the problem of coding the different sales territories that a contract could cover. There were exclusions, variations of rights, different groupings of countries to complicate matters.

The sort of query that the system should be able to handle was 'Can I sell this product in the USA?'

It didn't take long to see that a complete solution would mean teaching the application all about geography. In the end a restricted solution was found that involved a restricted use of agreed names for various regions of the world.

This has many disadvantages. If a new territorial grouping is mentioned in a contract, or if an existing grouping, the EU for example, changes then the programmer has to go in and make changes to the database and the range of queries that can be made is restricted.

Ideally, a database should be capable of storing data in a way that retains many of its real world characteristics and it should be capable of answering complicated and perhaps subtle questions.

You might think that this is a tall order but using Prolog in combination with a database has the capability of doing so much more than just SQL and a procedural language.

The Logic Of The Tube

Although Prolog is often thought of as a complex and difficult language it is can be conceptualised as a sort of database with the power of logical reasoning.

Not only can you set up traditional records composed of fields you can also define relationships and rules between records that can be used to 'reason' a way to an answer.

For example, in Prolog it would be very easy to define a record to store a sales contract in a form very close to the original paper document. You could then define rules that expressed the knowledge that we all  have about geography, for example, that the USA has 50 states and that they are Alabama, Alaska ..., that the UK. is in the EU and so on.

The power of this sort of system is that it then allows you to ask question in a natural style for the problem and get a reasonable answer.

For example, to answer the question 'can we sell this in the UK.?' the program would use the fact that the product can be sold in the EU and the rule that the UK is part of the EU to arrive at the answer 'Yes'.

The problem of teaching a database enough geography to answer regional questions isn't too difficult but it is rather too large a project to tackle in an article.

To give you some idea of the sorts of things that Prolog can do for database construction let's look at a simpler, but related problem, of finding a route on the London Underground from one station to another.

You can see a map of the "tube" at Transport For London so that you can follow the route station-by-station.

There are lots of Prolog implementations available but a good free ISO standard Prolog is SWIProlog . If you want to follow the steps of this tutorial then download it and install it before continuing or make use of the new live online Prolog environment that is currently in beta. The online in browser environment is good enough for all of the programs in this example. 

The application that we are creating is a simple route finder. That is, the user states the name of the starting station and the destination station and the computer prints a list of stations on the route including any changes of line that have to be made.

You could even add the extra condition that the route should be the shortest, cheapest, least congested etc. but for the sake of simplicity all that is required at the moment is a route any route..

If you think this problem is easy, after all millions of humans solve it every day, then I would ask you to think of how you would implement it using a traditional database or a program in a language of your choice. It is do able but it isn't easy. It involves writing quite a complex search.

In Prolog however the core of the solution occupies about five lines of instructions!

Even if you have never come across Prolog before, or even another computer language you should be able to get something of the flavour of the solution.

Begin Prolog

In Prolog you can write statements of fact using an abbreviated notation.

For example, you can write

son_of(mary,david)

to mean the son of Mary is David.

In Prolog this sort of statement is known as a 'clause'.

You should be able to see that this is very similar to a record consisting of two fields - mother's name and son's name and indeed the simple clause does play the role of a record in Prolog.

In the case of the Underground network problem the information to be stored concerns which stations are connected. The form of clause used to hold this information is

adjacent(station1,station2,line,time)

which records the fact that station1 is adjacent to station2 on tube line 'line' and it takes 'time' seconds to get from one to the other.

For example,

adjacent(Wembly_Park,Preston_Road,Metropolitan,4)

means that after Wembly Park Preston Road is the next stop on the Metropolitan line and it takes 4 minutes to get there - facts you can check using the tube map.

You should be able to see that it is possible to represent the entire underground system as a large collection of adjacent clauses. And to try things out start SWI Prolog or use the in browser editor and use the File, New command to create a new file called Route. Using the editor enter the following:

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

If you are using the online version type into the left hand window. You also need to remember to type the full stop at the end of each clause which acts as an end of clause marker.

So far we have very little that is new because the collection of adjacent clauses is equivalent to a database consisting of records with fields station1, station2, line, and time.

However if you compile this "knowledge base" you can already do some things that are beyond a simple database.

<ASIN:3540006788>

<ASIN:0262193388>

<ASIN:1904987176>

<ASIN:0262512270>

<ASIN:1852339381>