Quick tip: Using a SingleStoreDB Recursive CTE with London Underground data
Tags: singlestoredb, recursivecte, londonunderground, northernline
Published: 2023-01-19 18:49:52

## Abstract
SingleStoreDB now supports [Recursive CTEs](https://docs.singlestore.com/managed-service/en/reference/sql-reference/data-manipulation-language-dml/with--common-table-expressions-.html). In this short article, we'll see an example of a Recursive CTE to find routes between stations on the London Underground Northern Line and rank the routes according to distance.

The SQL code used in this article is available in a [GitHub Gist](https://gist.github.com/VeryFatBoy/5d1603d03a1a6ee1d63ecf3481de190f).

## Introduction
In a great [article](https://learnsql.com/blog/sql-recursive-cte/) about Recursive CTEs, there is an example of finding routes between different cities and ranking them according to distance. Let's apply that example to the London Underground. The London Underground network is extensive, and we'll focus our example on the Northern Line.

## Create a SingleStoreDB Cloud account
A [previous article](https://dev.to/veryfatboy/quick-tip-using-dbt-with-singlestoredb-161g) showed the steps required to create a free SingleStoreDB Cloud account. We'll use **RCTE Demo Group** as our Workspace Group Name and **rcte-demo** as our Workspace Name.

## Visualise the Northern Line
First, let's create a quick visualisation of the Northern Line. To do this, we can obtain the Station and Line data in GeoJSON format from an excellent [website](https://www.doogal.co.uk/TubeLine?name=Northern). We'll save the files as `northern_line_stations.geojson` and `northern_line_connections.geojson`, respectively.

Using [Deepnote](https://deepnote.com/), we'll create a Python notebook and upload the two GeoJSON files into a `data` directory.

First, we'll import `geopandas`:

```python
import geopandas as gpd
```

and now read the files:

```python
connections_df = gpd.GeoDataFrame.from_file(
  "data/northern_line_connections.geojson"
)

stations_df = gpd.GeoDataFrame.from_file(
  "data/northern_line_stations.geojson"
)
```

Next, we'll import `folium`:

```python
import folium

from folium import plugins
```

and now create a map:

```python
London = [51.509865, -0.118092]

m = folium.Map(location = London, tiles = "Stamen Terrain", zoom_start = 12)

folium.GeoJson(
  connections_df,
  name = "Northern Line",
  style_function = lambda feature: {
    "color" : "black",
    "weight" : 3
  }
).add_to(m)

folium.GeoJson(
  stations_df,
  name = "Northern Line Stations",
  popup = folium.GeoJsonPopup(fields = ["name"]),
  marker = folium.Marker(
    icon = folium.Icon(
    color = "black",
    icon = "train",
    icon_color = "white",
    prefix = "fa"
    )
  )
).add_to(m)

plugins.Fullscreen(
  position = "topright",
  title = "Fullscreen",
  title_cancel = "Exit",
  force_separate_button = True).add_to(m)
m
```

We can also save the map:

```python
m.save("northernline.html")
```

The zoomed-out map should be similar to Figure 1.

![Figure 1. Northern Line.](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6s0dao4nn1kwndyyrdzc.png)

<center>Figure 1. Northern Line.</center>

If we zoom in on the central area, we can see that at Kennington, there are two northbound branches (Charing Cross Branch on the left and City Branch on the right), as shown in Figure 2.

![Figure 2. Kennington.](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5n4um56oqu5pbykb9gzw.png)

<center>Figure 2. Kennington.</center>

Further north, these lines pass through Euston, as shown in Figure 3.

![Figure 3. Euston.](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/gnabofbmkoqfne71qfah.png)

<center>Figure 3. Euston.</center>

Therefore, we have two routes of different lengths from Kennington to Euston.

## Northern Line Inter-Station Distance
We need data on the distance between pairs of stations to determine the lengths of the two routes. Under the UK Freedom of Information Act and Transport for London's (TfL's) information access policy, the distance between pairs of stations was [provided](https://www.whatdotheyknow.com/request/station_to_station_journey_times) in a spreadsheet (`Inter Station Train Times.xls`) in 2013. The data are extensive and missing some changes to the Underground Network since 2013. However, we can extract the subset of the data for the Northbound Northern Line suitable for our example. This is available in a [GitHub Gist](https://gist.github.com/VeryFatBoy/5d1603d03a1a6ee1d63ecf3481de190f).

After executing our SQL code to create our table and insert the values, we'll modify the Recursive CTE example from the [article](https://learnsql.com/blog/sql-recursive-cte/) mentioned earlier, as follows:

```sql
WITH RECURSIVE possible_route AS (
    SELECT sr.station_to,
           CONCAT (sr.station_from, '->', sr.station_to) AS route,
           sr.distance
    FROM stations_route sr
    WHERE sr.station_from = 'MORDEN'
UNION ALL
    SELECT sr.station_to,
           CONCAT (pr.route, '->', sr.station_to) AS route,
           pr.distance + sr.distance
    FROM possible_route pr
INNER JOIN stations_route sr
    ON sr.station_from = pr.station_to
)
SELECT pr.route,
       pr.distance
FROM possible_route pr
WHERE pr.station_to = 'EUSTON'
ORDER BY pr.distance;
```

In our code, we want to find all routes from Morden (the most southern station on the Northern Line) to Euston. This will give us the following output:

```
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+
| route                                                                                                                                                                                                                                                                       | distance |
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+
| MORDEN->SOUTH WIMBLEDON->COLLIERS WOOD->TOOTING BROADWAY->TOOTING BEC->BALHAM->CLAPHAM SOUTH->CLAPHAM COMMON->CLAPHAM NORTH->STOCKWELL->OVAL->KENNINGTON->WATERLOO->EMBANKMENT->CHARING CROSS->LEICESTER SQUARE->TOTTENHAM COURT ROAD->GOODGE STREET->WARREN STREET->EUSTON |    17.39 |
| MORDEN->SOUTH WIMBLEDON->COLLIERS WOOD->TOOTING BROADWAY->TOOTING BEC->BALHAM->CLAPHAM SOUTH->CLAPHAM COMMON->CLAPHAM NORTH->STOCKWELL->OVAL->KENNINGTON->ELEPHANT & CASTLE->BOROUGH->LONDON BRIDGE->BANK->MOORGATE->OLD STREET->ANGEL->KINGS CROSS->EUSTON                 |    20.03 |
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+
```

Another interesting query is to find routes from Morden to Camden Town, as two branches of the Northern Line also meet there. Substituting EUSTON with CAMDEN TOWN in our Recursive CTE will give us the following output:

```
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+
| route                                                                                                                                                                                                                                                                                                         | distance |
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+
| MORDEN->SOUTH WIMBLEDON->COLLIERS WOOD->TOOTING BROADWAY->TOOTING BEC->BALHAM->CLAPHAM SOUTH->CLAPHAM COMMON->CLAPHAM NORTH->STOCKWELL->OVAL->KENNINGTON->WATERLOO->EMBANKMENT->CHARING CROSS->LEICESTER SQUARE->TOTTENHAM COURT ROAD->GOODGE STREET->WARREN STREET->EUSTON->MORNINGTON CRESCENT->CAMDEN TOWN |    18.85 |
| MORDEN->SOUTH WIMBLEDON->COLLIERS WOOD->TOOTING BROADWAY->TOOTING BEC->BALHAM->CLAPHAM SOUTH->CLAPHAM COMMON->CLAPHAM NORTH->STOCKWELL->OVAL->KENNINGTON->WATERLOO->EMBANKMENT->CHARING CROSS->LEICESTER SQUARE->TOTTENHAM COURT ROAD->GOODGE STREET->WARREN STREET->EUSTON->CAMDEN TOWN                      |    19.11 |
| MORDEN->SOUTH WIMBLEDON->COLLIERS WOOD->TOOTING BROADWAY->TOOTING BEC->BALHAM->CLAPHAM SOUTH->CLAPHAM COMMON->CLAPHAM NORTH->STOCKWELL->OVAL->KENNINGTON->ELEPHANT & CASTLE->BOROUGH->LONDON BRIDGE->BANK->MOORGATE->OLD STREET->ANGEL->KINGS CROSS->EUSTON->MORNINGTON CRESCENT->CAMDEN TOWN                 |    21.49 |
| MORDEN->SOUTH WIMBLEDON->COLLIERS WOOD->TOOTING BROADWAY->TOOTING BEC->BALHAM->CLAPHAM SOUTH->CLAPHAM COMMON->CLAPHAM NORTH->STOCKWELL->OVAL->KENNINGTON->ELEPHANT & CASTLE->BOROUGH->LONDON BRIDGE->BANK->MOORGATE->OLD STREET->ANGEL->KINGS CROSS->EUSTON->CAMDEN TOWN                                      |    21.75 |
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+
```

The results show the possible routes, which may also require changing trains.

## Summary
This short article showed an example of a Recursive CTE that could be applied to a practical, real-world problem. The [documentation](https://docs.singlestore.com/managed-service/en/reference/sql-reference/data-manipulation-language-dml/with--common-table-expressions-.html) contains further examples and discussion.