This exercise involves querying a database by means of SQL. It is meant to show you how to establish a connection with a database from a Java program and how to retrieve from it. You are given a database which contains a list of train services. For every service, its origin, destination, departure hour and, arrival hour. The target of your query is to find a route using the available services in the database with some given origin and destination and certain limitations such as a limited number of changes of trains, and bounds on the times of departure from the point of origin and arrival at the point of destination. 

This data has been sampled from the actual schedule of train services between cities in Britain. For the sake of simplicity, each city is assumed to have a single railway station. All times are given in the format hour.minute . The database lists services between Birmingham, London, Edinburgh, Manchester, York, Oxford, Newcastle, Leeds, Liverpool, Glasgow, Warwick, Colchester, Leicester and Sheffield. Many services have been deliberately omitted, to make changes in itineraries necessary.

The database is stored on the School's PostgreSQL server. Java programs can query it using a JDBC connection, and sending queries using psql commands. Some details of how the PostgreSQL server is organised are here, though you don't need to read that in order to complete these exercises. You might also find Alan Sexton's tutorial on JDBC and servlets useful.

The database consists of a single table called "trains" which looks like this:

   origin   | departure | destination |  arrival  
------------+-----------+-------------+-----------
 London     |  5.440000 | Birmingham  |  8.150000
 London     |  8.100000 | Birmingham  |  9.520000
 London     |  8.400000 | Birmingham  | 10.220000
 Manchester | 10.130000 | York        | 11.420000
 Manchester | 10.460000 | York        | 12.100000
 Manchester | 11.130000 | York        | 12.420000

This database is stored on the School's PostgrSQL server, called dbhost.cs.bham.ac.uk. You can view that database without using a Java program, as follows: type

psql -h dbhost -U yr2 -d trainsdb

\d

\d trains

select * from trains where origin='London';

In this exercise, we want to access the database from a Java program. Here is a very simple program fragment which queries the TRAINS relation from the trainsdb database, accessing it as user yr2 and citing the password 2ndyr. The code then prints out three places you can go to from London after 10:30:

    try { 
      // Load and register the driver for Postgresql
      Class.forName ("org.postgresql.Driver") ;
      // Establish a connection with the database
      Connection con = DriverManager.getConnection 
        ("jdbc:postgresql://dbhost/trainsdb","yr2","2ndyr") ;
      Statement stmt = con.createStatement ();
      ResultSet rs = stmt.executeQuery ( 
         "SELECT * FROM TRAINS WHERE (ORIGIN = 'London') AND "+
         "(DEPARTURE >= '10.30'::NUMERIC)" );
      int i=3;
      while (rs.next() && i>0) {
        i--;
        float depTime = rs.getFloat ("DEPARTURE");
        float arrTime = rs.getFloat ("ARRIVAL");
        String destination = rs.getString ("DESTINATION");
        System.out.println(
          "London ("+depTime+") to "+destination+" ("+arrTime+")");
      }
      rs.close();
      stmt.close();
      con.close();
    }

    catch (ClassNotFoundException e) {
      System.out.print ("org.postgresql.Driver not found");
      System.exit(1);
    }
    catch (SQLException  e) {
      System.out.println ("SQL Exception: "+e); 
      System.exit(1);
    }
  }

Your answers

You should submit your program using the procedures described here.

Setting things up on the computer

If you want to work from home, see the end of this handout for some hints about the SoCS firewall.

If you are using NetBeans, you must explicitly mount postgresql.jar in Netbeans.  In Windows it is:
J:\Java\postgresql.jar
and Linux:  
/bham/common/java/lib/postgresql.jar
(Netbeans does not use your CLASSPATH environment variable, that's whydoing setup Postgresql doesn't help.)

1. Accessing the database

Your first task is to write a program which accesses the database and provides a link from station A to station B, if one exists. For example:

java RouteFinder London Manchester 

London (6.00) to Manchester (9.02).

java RouteFinder1 Glasgow Sheffield

No direct route.

Hints

• Start by getting the example code above to work.
• In the example above, the SQL statement is a fixed string. In your program, it will have to be constructed by your Java program as it will depend on your user's command-line arguments.
• Look at the API documentation for ResultsSet and at this program in order to understand how to access the results of your database query.

2. Finding Routes to answer command-line queries

java RouteFinder2 <origin> <destination> <departure time> <arrival time> <maximum legs>

Your program should consult the database and respond by producing all the itineraries which satisfy the given restrictions. For example,

java RouteFinder2 London Sheffield 9.00 15.00 4

would produce:

London (9.55) to Manchester (12.36), Manchester (12.43) to Sheffield (13.35).
London (10.55) to Manchester (13.36), Manchester (13.43) to Sheffield (14.37).

Please use this format for your output.

You will have to think very carefully about the route finding algorithm you will use. If you program this naively, you'll find that your program produces incorrect results, and/or quickly runs out of memory or takes inordinately long. The lectures will discuss route finding in some detail. 

You can get part marks for this exercise if you only manage to do some of what is required, for example

• A program which only works in some cases
• A program which only prints out one itinerary instead of all of them
• Itineraries for which the times of trains don't match up

You can get full marks if your program can print out all itineraries satisfying the requirement. For extra credit, your program will not print out itineraries which are worse than other ones, for example:

• Itineraries which have an earlier departure time and a later arrival time than other available itineraries.
• Itineraries which have the same departure time, but a later arrival time than others.
• Itineraries which have the same arrival time, but an earlier departure time than others.
• Itineraries which which have the same departure and arrival times as others, but a greater (apparent) number of changes. Such itineraries may appear because the database may contain services which are in fact carried out by the same train. This means that some indicated changes may be  fictitious.

3. Using Dijkstra's algorithm

One measure of the efficiency of your program is how many database results it extracts in order to answer your query. Get your program for the previous part to print out this figure, by adding up the size of all the ResultSets that were returned. (For these figures to be meaningful, you should not cache legs you extract from the database.) The program we wrote RouteFinder2 implements a fairly naive algorithm which accumulates a set of ever longer paths until there are no more satisfying the constraints, as explained in the lectures. Our RouteFinder3, which implements Dijkstra's algorithm, is much more efficient than RouteFinder2, as demonstrated by the table below showing the number of database results returned:

Query	RouteFinder2	RouteFinder3
London Sheffield 9.00 15.00	1379	242
Sheffield Glasgow 9.00 16.00	1183	660
Colchester Edinburgh 12.00 20.00	4314	370

(Of course, the RouteFinder2 returns more results than that for RouteFinder3. RouteFinder2 can return all the results satisfying the user's constraints, while RouteFinder3 only produces the shortest one.)

In this part of the exercise, we are interested in efficiency. Implement Dijkstra's algorithm. Can you get lower numbers than those for RouteFinder3 in the table above?

4. Answering queries on the web

In order to run servlets on the School's machines, you will need to read "Developing and Running Servlets with Tomcat in SoCS" from the Support Team's documentation on Java servlets. (Indicentally, if you try to access this link from home, you will get the message "Access to this page is only available within the School of Computer Science". See "Working from home" for a workaround.) You can also look at Alan Sexton's tutorial on JDBC and servlets. In order to run servlets on your machine, you will need to install and run the servlet server Tomcat. You can find information on how to do this here.

The tutorials don't cover the issue of html forms very well. Here is an example html form using the GET method.  Here is a "Hello world, enter a parameter and I will display it" complete servlet written by one of the demonstrators. It avoids having to have an initial form; this servlet checks to see if a request was made, and if no request was made it just displays the form. If a request was made, it answers the request, and still displays the form afterwards.

Hints for working from home

One option is to install PostgreSQL and a Java servlet server (for part 4) on your machine. I haven't done this myself, so I can't help you.

Another option is to get your Java program to connect to the School's database server and servlet server. This probably only makes sense if you have a permanent internet connection from home, or a fixed-price dial-up connection. To make this work, you will need some technical information to overcome some restrictions imposed by the School's firewall. We advise you not to attempt this unless you are interested in understanding the technicalities, because it is quite complicated.

• To get JDBC to work with PostgreSQL, you must have org.postgresql.Driver in your path. If you don't, you get the error java.lang.ClassNotFoundException: org.postgresql.Driver

  At home, you can copy /bham/pd/packages/postgresql-current/share/java/postgresql.jar and make sure it is on your CLASSPATH. For example, put it in your current directory and use

  java -cp postgresql.jar:.  RouteFinder

  in unix, or

  java -classpath postgresql.jar; RouteFinder

  in Windows.
• The SoCS firewall will obstruct you accessing certain machines from outside the School, such as dbhost.cs.bham.ac.uk. You need to access port 5432 of this machine, because that is the port that PostgreSQL listens to. To work around the firewall, you can use ssh to connect port 5432 of your machine to port 5432 of dbhost, going via dipsy. To do this from a linux-based machine, simply type this on your home machine:

  ssh -L 5432:dbhost.cs.bham.ac.uk:5432 dipsy.cs.bham.ac.uk

  This is called tunnelling with ssh. To do it from a Windows machine, you need to install ssh on your computer and then set up the tunnel to dbhost's port 5432.  Look at this image to see the settings.

  Then you have to tell the Java program to access localhost, instead of dbhost, by changing the line in the source code. Alternatively, linux users could just alias dbhost to their home machine in /etc/hosts.

• If you want to read at home web pages which are only accessible from within the School, you can use the same trick with ssh. In this case, you want to tell your web browser to use webcache.cs.bham.ac.uk, port 3128, as the proxy. However, the SoCS firewall will stop you, so you have to use ssh to tunnel around it. Map port 3128 of your machine to port 3128 of webcache.cs.bham.ac.uk, again going via dipsy.cs.bham.ac.uk. Then tell your web browser to use localhost as proxy, port 3128.

Marking scheme

For students who have attempted Part 1

For students who have attempted Part 2 and possibly more