How to design a bus station query database schema?

Question

We have bus station data, and we want to build an application which will provide the line/multiple line for a given start station and the end station.

For example user try to get a bus line suggestion from station1 to station2.

If there is a bus line which can cover both station1 and station2, this line should be returned. The result may look like this:

Step1: station1 -- station2

If there is no direct bus line between station1 and station2, then the application should try to find the exchange plan,for example, the result may look like this:

Step1: station1 -- exchangestation

Step2: exchangestation -- station2

Now we have the data, but we do not know how to design the data model in the database, how to create the schema to make the query efficient?

=============================================

Update:

For example, I have four bus lines(actually two) each with a different color:

l1: A-B-C-D
l2: D-B-A (in fact, the l2 is the reverse of l1 except the l2 will skip station `C`.
l3: E-B-D-F
l4: F-D-B-E(reverse of l3) 

Now if we want to save these information in the database to query the bus line plan for given one station to another, then how many tables do we need, and what should be put into each table ?

Answer 1

I think you need to build another table that defines all the routes in is as combinations of other routes. Then you query this table and join to the actual routes to get the geometry.

If the query is for 'from station' to 'to station' and each section has a 'from station and 'to station'. But you want to include routes that take in multiple sections, you could have another table 'routes' that has something like:

• 'route name', 'route ID', 'from station', 'to station'

you also need your original sections table, something like:

• 'section name', 'section ID', etc...

and I think that you need another join table like:

• 'route ID', 'section ID'

and that table stores the one to many relationship between the routes and sections tables, so, for your example above, you have two rows in the join table, one for each step. The querying is done on the route table, for from and to stations. Data returned, if spatial, is details from the route table and spatial data from the section table. Maybe you add up times from each section or whatever.

Does that make sense?

Answer 2

You probably should pick a tool for that and follow the schema the tool forces (for example pgRouting).

If you want to do it without a table you only need two tables really to store the vertices and the nodes.

The trick is your image shows a spatial approach while in fact you need a temporal one (image pending). The bus doesn't go from node A to node B. The bus goes from node A@12:00 to node B@12:10.

So we create a node for every station + a node for every departure time from each station. Each node has 3 one-way links going out from it:

• link to the bus destination (A@12:00 - B@12:10 cost: 10 minutes)
• link to the next bus leaving from this station (A@12:00 - A@12:30 cost:30 minutes)
• link to the base node (A@12:00 to A cost:0 minutes)

Now to find the connection from point A to point C we pick the earliest matching point at station A and find our way from there to the base node for station C.

Nodes:

id|station|time
---------------
1 |A      |NULL
2 |B      |NULL
3 |A      |12:00
4 |B      |12:10

vertices

id|start_node|end_node|line|cost
---------------------------
1 |3         |4       |l1  |10
2 |3         |1       |NULL|0
3 |4         |2       |NULL|0

Answer 3

Here is a working example using javascript and data from OpenStreetMap. The data model may be useful.