1

I need to create a data model for routing data between points. For example, path between two cities which will include the two start and destination cities, way points (like smaller towns along the way), total distance between the two cities (distances between routing points do not need to be modelled though it would be good if that can be done too).

My current idea is like below.

  • Create one table containing the cities: city. Columns: city_id (primary key), city_name, etc.
  • Create a many-to-many table path with 4 columns: from_city (references city.city_id, to_city (references city.city_id), calculated column path = MD5(CONCAT(from_city, to_city)), distance to store the total distance for the route.
  • Create a table to store route points called town similar to the city table.
  • Create a man-to-many table route between path and town which will have three columns: town_id (references town.town_id), path_id (references path.path) and route_position which will be a value 1-n which will indicate the position of the route point in the actual path. For example, first route point will have number 1, second 2 and so on.

Questions:

  1. Do you guys think this is a feasible model? Is there a better approach to this?
  2. In the path table, is it better to use a MD5 hash or create a multiple-column index on from_city and to_city?

EDIT:

To give some context, I'm currently using a graph database to store this data and have a user-defined function that uses A* search to find the shortest path between points. Problem is as the graph gets denser, this computation becomes too slow. So, I think a lookup-based approach would be faster.

NO WAR WITH RUSSIA
  • 54,954
  • 34
  • 200
  • 411
kovac
  • 167
  • 1
  • 2
  • 9
  • 1) I do not see the need to divide cities and towns into different tables. 2) Paths "from CityA to CityB" and "from CityB to CityA" are two different records in `path` table, is it? 3) It's possible more than 1 path "from CityA to CityB" - how You'll store them? – Akina May 23 '18 at 05:08
  • There is only one path between two cities. Yeah currently the cities and towns are in the same table. – kovac May 23 '18 at 06:17
  • *There is only one path between two cities* Direct and reverse paths follow the same cities? Nevertheless I recommend creating two records for them... – Akina May 23 '18 at 06:28
  • 1
    Don't bother with the MD5; the composite key makes a lot more sense. – Rick James Jun 02 '18 at 01:51

1 Answers1

1

Do you guys think this is a feasible model?

No.

Is there a better approach to this?

Yes. Use PostgreSQL, and PostGIS. Instead of storing towns, store your points as WGS84 coordinates. You can use PostGIS to resolve the towns or addresses to WGS84 coordinates. You can connect them self and find the shortest path, or... you can use load the OSM data and have a Google Maps-like product.

See also,

MariaDB has a graph backend OQGRAPH that may also assist you, but I wouldn't touch it with a 10 foot pole. Database Administrators has one question on it. Outside I've jokes, I've never seen it mentioned.

NO WAR WITH RUSSIA
  • 54,954
  • 34
  • 200
  • 411
  • Thanks for the feedback. I added an edit to my question regarding shortest path. If I wanted a specific path, will the spatial approach still work? For example, if there are barriers between towns that need to be accounted for, hence the distance may be larger since the path will go around the barrier? – kovac May 23 '18 at 02:47
  • Yes. Dijkstra’s Shortest path handles all of that. You can literally use the same alogirthm to find the least-cost caloric path too https://pdfs.semanticscholar.org/9a0e/8984ee9d728eb4a92f8f5430d2d84ad0dd4b.pdf You will of course have to provide the route around the obstacle for it to use in the calculation – NO WAR WITH RUSSIA May 23 '18 at 02:50
  • Hmm, we did use Dijkstra initially and it was slow in a dense connected graph. Then we implemented an optimised A* search which performed far better than Dijkstra but even that is getting too slow. However, the `LineString` data type with the spatial function for length could help me. – kovac May 23 '18 at 02:56
  • Also supports A* https://docs.pgrouting.org/2.0/en/src/astar/doc/index.html – NO WAR WITH RUSSIA May 23 '18 at 03:06