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
(referencescity.city_id
,to_city
(referencescity.city_id
), calculated columnpath
=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 thecity
table. - Create a man-to-many table
route
betweenpath
andtown
which will have three columns:town_id
(referencestown.town_id
),path_id
(referencespath.path
) androute_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:
- Do you guys think this is a feasible model? Is there a better approach to this?
- In the
path
table, is it better to use aMD5
hash or create a multiple-column index onfrom_city
andto_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.
Best Answer
No.
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.