Case Study: Île-de-France Public Transit

This case study, extending the scenario introduced in [Senellart et al., 2018], applies ProvSQL to the real-world GTFS dataset for Île-de-France public transit. It demonstrates Boolean provenance at scale for wheelchair accessibility reasoning, then journeys with changes as a WITH RECURSIVE query over the whole network, whose rows the same query evaluates in several semirings: shortest travel time, accessibility, the equations of the recursion and the journeys they describe, the fastest journey itself, step by step, which of the metro and the train is faster, and the probability of reaching a station when parts of the network are disrupted.

Note

Unlike the other case studies, this one is not available in the ProvSQL Playground: it loads the large Île-de-France GTFS dataset, which is not bundled and must be fetched separately (see the Playground note). Run it against a local ProvSQL installation.

The Scenario

Île-de-France is the region around Paris. Its network combines the metro, inside Paris; the RER, express trains crossing the city and running out to the suburbs (lines A to E); suburban trains; trams; and buses, including the night buses (Noctilien, lines numbered N…).

The STIF GTFS dataset describes hundreds of transit routes and tens of thousands of stops, in GTFS, the General Transit Feed Specification: a set of CSV files whose columns the GTFS reference documents.

Starting from Luxembourg station, in the centre of Paris (served by RER B and several bus lines), you want to know:

which stops and lines are reachable without changing, and whether the journey is fully wheelchair-accessible: Boolean provenance answers this, a result token evaluating to true if and only if every record along the trip has the wheelchair flag set;
which stations are reachable at all, changing as often as needed, how long it takes, whether some journey is accessible, and how likely the journey remains when lines are disrupted: a recursive query over the network answers all four.

Warning

This case study requires external data files. The dataset is not bundled with ProvSQL due to its size (the compressed download is several hundred megabytes). Download instructions are in Setup below.

Setup

Download the GTFS data. Obtain the Île-de-France GTFS archive from data.gouv.fr (direct download: IDFM-gtfs.zip). Extract the archive; you will need the four text files routes.txt, stops.txt, trips.txt, and stop_times.txt.

Load the schema and data. Download setup.sql and run it from the directory containing the four GTFS files:

cd /path/to/gtfs-files
psql -d mydb -f /path/to/setup.sql

Loading the files, millions of rows of timetable among them, takes a couple of minutes. This creates four tables:

routes – transit lines (RER A, B, M1, bus 91…)
stops – individual stop points with GPS coordinates and a wheelchair_boarding flag
trips – individual scheduled journeys, each with a wheelchair_accessible flag
stop_times – arrival and departure times at each stop for each trip

The script also adds provenance tracking to trips and stops, and normalises their wheelchair columns to 1 (accessible) or 0. It also calls setup_search_path, which adds provsql to the database’s search_path: every new session calls ProvSQL’s functions without the provsql. prefix.

Note

The setup script already creates the most important indexes (on stop_id, trip_id, and parent station), which are essential for acceptable performance on this large dataset.

Step 1: Explore the Database

Inspect the four tables:

SELECT COUNT(*) FROM routes;
SELECT COUNT(*) FROM stops;
SELECT COUNT(*) FROM trips;
SELECT COUNT(*) FROM stop_times;

The stops table has two kinds of rows, told apart by location_type. A stop (location_type 0) is where a vehicle calls: a platform, or a bus stop; it is what stop_times refers to. A station (location_type 1) groups the stops of one place: each of its stops names it in its parent_station column. Luxembourg station thus groups its RER platforms and the bus stops around it. To find it and its stops:

SELECT * FROM stops WHERE stop_name = 'Luxembourg';

Two stations carry the name: IDFM:71161, Luxembourg in Paris, and IDFM:65716, a namesake elsewhere in the region. The queries below start from the first, and reach its trips through its stops.

Step 2: Provenance and Wheelchair Mapping

Provenance has already been added to trips and stops by setup.sql: every row of a query over them carries the provenance of the trip and stop records it reads. Their wheelchair columns become the values of a provenance mapping, which associates each input token with a value. Each call below builds a mapping for one table; their union covers the tokens of both, and an index speeds up the lookups in this large mapping:

DROP TABLE IF EXISTS w_trips, w_stops, wheelchair;
SELECT create_provenance_mapping('w_trips', 'trips', 'wheelchair_accessible');
SELECT create_provenance_mapping('w_stops', 'stops', 'wheelchair_boarding');
CREATE TABLE wheelchair AS
  SELECT * FROM w_trips UNION SELECT * FROM w_stops;
CREATE INDEX ON wheelchair(provenance);

A result token evaluates to true (1) under sr_boolean if every contributing row has its wheelchair column set to 1. Inspect the mapping:

SELECT * FROM wheelchair LIMIT 10;

Step 3: Reachable Stops from Luxembourg

Find all stops reachable from Luxembourg on the same trip and later in the sequence – in other words, stops you can reach by boarding a vehicle at Luxembourg without changing:

SELECT DISTINCT s2.stop_name, r2.route_long_name
FROM stops s0
JOIN stops      s1 ON s1.parent_station = s0.stop_id
JOIN stop_times t1 ON s1.stop_id = t1.stop_id
JOIN stop_times t2 ON t1.trip_id = t2.trip_id
                  AND t1.stop_sequence < t2.stop_sequence
JOIN stops      s2 ON s2.stop_id = t2.stop_id
JOIN trips      u2 ON u2.trip_id = t2.trip_id
JOIN routes     r2 ON r2.route_id = u2.route_id
WHERE s0.stop_id = 'IDFM:71161'
ORDER BY r2.route_long_name, s2.stop_name;

This returns every (stop, line) pair reachable without changing, on RER B and on the bus lines through the station.

Step 4: Boolean Provenance – Full Wheelchair Accessibility

Add Boolean provenance evaluation to mark which results are fully wheelchair-accessible along every leg. Because the query returns one row per trip (each with its own provenance circuit), materialise the result first and then aggregate per destination:

CREATE TEMP TABLE from_luxembourg AS
  SELECT s2.stop_name,
         r2.route_long_name,
         sr_boolean(provenance(), 'wheelchair') AS accessible
  FROM stops s0
  JOIN stops      s1 ON s1.parent_station = s0.stop_id
  JOIN stop_times t1 ON s1.stop_id = t1.stop_id
  JOIN stop_times t2 ON t1.trip_id = t2.trip_id
                    AND t1.stop_sequence < t2.stop_sequence
  JOIN stops      s2 ON s2.stop_id = t2.stop_id
  JOIN trips      u2 ON u2.trip_id = t2.trip_id
  JOIN routes     r2 ON r2.route_id = u2.route_id
  WHERE s0.stop_id = 'IDFM:71161';

SELECT remove_provenance('from_luxembourg');

SELECT stop_name, route_long_name, bool_or(accessible) AS accessible
FROM from_luxembourg
GROUP BY stop_name, route_long_name
ORDER BY route_long_name, stop_name;

sr_boolean evaluates the provenance token of each row under the Boolean semiring, looking up each leaf token in the wheelchair table: true when every record the row reads (the station, its platform, the stop, the trip) has the wheelchair flag set, i.e., when that trip makes that journey accessibly. The table holds a row per trip and stop, hundreds of thousands of them, so this step takes a little while.

The materialised table still carries the provsql provenance column, so remove_provenance drops tracking first, and the final aggregation runs outside ProvSQL. bool_or asks whether some trip of the line reaches the stop accessibly from Luxembourg: one can wait for an accessible vehicle. bool_and would ask that every trip does; on this network, the two rarely differ.

Step 5: Inspect Individual Results with `sr_formula`

For a stop that is not fully accessible, use sr_formula to identify which specific trip or stop is responsible. Here we inspect the Musée du Louvre stop on bus line 27 as an example:

SELECT s2.stop_name,
       sr_formula(provenance(), 'wheelchair') AS formula
FROM stops s0
JOIN stops      s1 ON s1.parent_station = s0.stop_id
JOIN stop_times t1 ON s1.stop_id = t1.stop_id
JOIN stop_times t2 ON t1.trip_id = t2.trip_id
                  AND t1.stop_sequence < t2.stop_sequence
JOIN stops      s2 ON s2.stop_id = t2.stop_id
JOIN trips      u2 ON u2.trip_id = t2.trip_id
JOIN routes     r2 ON r2.route_id = u2.route_id
WHERE s0.stop_id = 'IDFM:71161'
  AND r2.route_long_name = '27'
  AND s2.stop_name = 'Musée du Louvre'
LIMIT plain(1);

The formula shows which token carries a 0 wheelchair value, pinpointing the accessibility barrier:

stop_name       | formula
----------------+---------------
Musée du Louvre | 1 ⊗ 1 ⊗ 0 ⊗ 1

The four factors correspond to the four provenance-enabled table instances in the join: the Luxembourg station record (stops, 1), its platform record (stops, 1), the Musée du Louvre stop record (stops, 0), and the trip record (trips, 1). The 0 on the third factor pinpoints the specific Musée du Louvre stop served by line 27 as the accessibility barrier. Several stops are named Musée du Louvre in the dataset; the one served by line 27 has wheelchair_boarding = 0, as we can verify:

SELECT DISTINCT s2.stop_id, s2.wheelchair_boarding
FROM stops s0
JOIN stops      s1 ON s1.parent_station = s0.stop_id
JOIN stop_times t1 ON s1.stop_id = t1.stop_id
JOIN stop_times t2 ON t1.trip_id = t2.trip_id
                  AND t1.stop_sequence < t2.stop_sequence
JOIN stops      s2 ON s2.stop_id = t2.stop_id
JOIN trips      u2 ON u2.trip_id = t2.trip_id
JOIN routes     r2 ON r2.route_id = u2.route_id
WHERE s0.stop_id = 'IDFM:71161'
  AND r2.route_long_name = '27'
  AND s2.stop_name = 'Musée du Louvre';

Step 6: The Next Stop on Each Line (`LATERAL`)

Step 3 listed every reachable stop. A LATERAL subquery asks a more focused question – for each line through Luxembourg, what is the very next stop after it on that trip:

SELECT DISTINCT r.route_long_name,
       nxt.stop_name AS next_stop,
       sr_boolean(provenance(), 'wheelchair') AS accessible
FROM stops s0
JOIN stops      s1 ON s1.parent_station = s0.stop_id
JOIN stop_times t1 ON s1.stop_id = t1.stop_id
JOIN trips      u  ON u.trip_id = t1.trip_id
JOIN routes     r  ON r.route_id = u.route_id
JOIN LATERAL (
  SELECT s2.stop_name
  FROM stop_times t2
  JOIN stops      s2 ON s2.stop_id = t2.stop_id
  WHERE t2.trip_id = t1.trip_id
    AND t2.stop_sequence > t1.stop_sequence
  ORDER BY t2.stop_sequence
  LIMIT plain(1)
) nxt ON true
WHERE s0.stop_id = 'IDFM:71161'
ORDER BY r.route_long_name, nxt.stop_name;

The LATERAL subquery runs once per outer row and may reference its columns (t1.trip_id, t1.stop_sequence); the ORDER BY … LIMIT plain(1) keeps only the immediately following stop. stops and trips are provenance-tracked (the untracked stop_times and routes contribute certain provenance, as in an ordinary join), so each (line, next stop) row carries the lineage of the records that produced it, and sr_boolean reports whether the hop to the next stop is wheelchair-accessible.

Without plain, ORDER BY … LIMIT 1 would be read in every possible world: each later stop would be a candidate, conditioned on no earlier stop being present. Here a token stands for an accessible record, so this would ask for the next accessible stop, another question, and a costly one: each row would carry a condition over all the later stops of its trip, for every trip through Luxembourg, and the query does not finish in reasonable time. Every stop exists, so which stop comes next is a plain fact of the timetable: LIMIT plain(1) keeps the next stop of the actual data, with the provenance its row has in the full result. ProvSQL emits a WARNING about this LIMIT in a subquery, since that provenance does not say that the stop is the next one; here, the answer means what it says. See ORDER BY, LIMIT and OFFSET for the general rule.

Step 7: The Network as a Table

Steps 3 to 6 stayed on one vehicle. To change lines, describe the network itself: one row per pair of consecutive stations on a line, with the average scheduled time between them and whether some trip makes that hop accessibly. This is plain SQL over the timetable, a long computation that needs no provenance: turn the rewriting off with provsql.active while it runs, rather than tracking the provenance of millions of rows for nothing.

SET provsql.active = off;
DROP TABLE IF EXISTS hop_minutes, hop_access, hop_name, hop_one, hop;
DROP VIEW IF EXISTS trip_hops, calls;

First, every call of a trip at a stop, with its line, the station of the stop, its arrival time in seconds since midnight, and whether both the trip and the stop are accessible:

CREATE TEMP VIEW calls AS
  SELECT st.trip_id, st.stop_sequence, r.route_short_name AS line,
         r.route_type,
         coalesce(nullif(s.parent_station, ''), s.stop_id) AS station,
         split_part(st.arrival_time, ':', 1)::int * 3600
           + split_part(st.arrival_time, ':', 2)::int * 60
           + split_part(st.arrival_time, ':', 3)::int AS arrival,
         t.wheelchair_accessible = 1 AND s.wheelchair_boarding = 1
           AS accessible
  FROM stop_times st
  JOIN trips t  ON t.trip_id = st.trip_id
  JOIN routes r ON r.route_id = t.route_id
  JOIN stops s  ON s.stop_id = st.stop_id;

Then every hop of a trip, a call and the next call of the same trip, which the window function lead reads in the order of the trip. Its time runs from arrival to arrival, so that it counts the stop at the station, still on board; the hop is accessible when both its calls are:

CREATE TEMP VIEW trip_hops AS
  SELECT line, route_type, station AS from_station,
         lead(station) OVER w AS to_station,
         (lead(arrival) OVER w - arrival) / 60.0 AS minutes,
         accessible AND lead(accessible) OVER w AS accessible
  FROM calls
  WINDOW w AS (PARTITION BY trip_id ORDER BY stop_sequence);

Finally, one row per hop of a line, over all its trips: the average time, and whether some trip makes it accessibly. Bus schedules give times to the minute, so a single trip often shows a hop as 0 or 1 minute; the average evens this rounding out. The last call of a trip has no next one, and a hop with no scheduled time is left out:

CREATE TABLE hop AS
  SELECT from_station, to_station, line, route_type,
         round(avg(minutes), 1)::float8 AS minutes,
         bool_or(accessible)::int AS accessible
  FROM trip_hops
  WHERE to_station IS NOT NULL AND to_station <> from_station
  GROUP BY from_station, to_station, line, route_type
  HAVING avg(minutes) IS NOT NULL;
RESET provsql.active;

The table has tens of thousands of rows and takes up to a minute to build, over the millions of rows of stop_times. Since the rewriting was off, its rows carry no provenance at all: the link with the tokens of trips and stops is lost, and accessible is just a copied value, no longer a formula over the trips and stops it came from. add_provenance makes hop a base relation of its own, each hop with a fresh token, which the queries below combine like those of any other input; map these tokens to the times and accessibility of their hops:

SELECT add_provenance('hop');
SELECT create_provenance_mapping('hop_minutes', 'hop', 'minutes');
SELECT create_provenance_mapping('hop_access', 'hop', 'accessible');

Step 8: Every Station Reachable from Luxembourg

Note

Recursive queries (WITH RECURSIVE), used from this step on, require PostgreSQL ≥ 15.

A journey with changes is a path in this network: a recursive query follows the hops from Luxembourg, a line change being just another hop out of the same station:

WITH RECURSIVE reach(station) AS (
    SELECT 'IDFM:71161'::text
  UNION
    SELECT h.to_station FROM reach r JOIN hop h ON h.from_station = r.station)
SELECT count(*) FROM reach;

The whole network, in a few seconds. The network is full of cycles (every line runs both ways), so a station has infinitely many derivations: ProvSQL records the provenance of each row as one unknown of a system of equations over the rows of the cycle, which every evaluation then solves (see Recursive Queries).

Step 9: How Long, and Is There an Accessible Journey?

The same query, evaluated in two semirings. In the tropical semiring of sr_tropical, alternatives take the minimum and a journey the sum of its hops: the shortest travel time. In the Boolean semiring of sr_boolean, over the accessible column: whether some journey uses accessible hops only. A VALUES list names a few destinations; it has no provenance of its own:

WITH RECURSIVE reach(station) AS (
    SELECT 'IDFM:71161'::text
  UNION
    SELECT h.to_station FROM reach r JOIN hop h ON h.from_station = r.station)
SELECT d.name,
       round(sr_tropical(provenance(), 'hop_minutes',
                         nonnegative => true)::numeric, 1) AS minutes,
       sr_boolean(provenance(), 'hop_access') AS accessible
FROM reach r
JOIN (VALUES ('IDFM:474151', 'Châtelet - Les Halles'),
             ('IDFM:71410', 'Gare du Nord'),
             ('IDFM:71517', 'La Défense'),
             ('IDFM:73721', 'Versailles Château Rive Gauche'),
             ('IDFM:73699', 'Aéroport CDG (Terminal 2)'),
             ('IDFM:68385', 'Marne-la-Vallée - Chessy'))
       AS d(station, name)
  USING (station)
ORDER BY minutes;

Châtelet - Les Halles, two stops away on RER B, comes first; the airport and Chessy, at the far ends of the network, last.

These are times on board only, well below what a traveller would see. In this network, changing lines is instant, and a train is always there to board: a journey is free to hop from line to line at every station, and the fastest ones do, catching a bus or a night bus for a single stop when it saves a minute. Real journeys add, at every change, the walk between platforms, sometimes several minutes in a large station, and, at every boarding, the wait for the next departure. The dataset has what it takes to account for both: the departure times are in stop_times, and a file this case study does not load, transfers.txt, gives the minimum time to change between two stops (another, pathways.txt, even gives the walks from the entrances of a station, with their stairs). A model using them would have a node per station and line, with change hops between them, or, to count the waits, a node per departure; the queries stay the same recursion over a larger table.

Each semiring solves the equations by the method its properties allow. The Boolean semiring, and the tropical one over the nonnegative costs that nonnegative => true declares, are absorptive (a cycle never improves a journey) and selective (an alternative is one of the two), which makes Dijkstra’s algorithm correct; without nonnegative, a cost might be negative and a cycle could lower it, and the equations are solved by Gaussian elimination instead, for the same values here.

Step 10: Not Every Semiring Has an Answer

Counting the derivations of a station in the counting semiring:

SELECT create_provenance_mapping('hop_one', 'hop', '1');

WITH RECURSIVE reach(station) AS (
    SELECT 'IDFM:71161'::text
  UNION
    SELECT h.to_station FROM reach r JOIN hop h ON h.from_station = r.station)
SELECT sr_counting(provenance(), 'hop_one')
FROM reach WHERE station = 'IDFM:474151';

is refused: going round a cycle any number of times gives infinitely many derivations, which no integer counts.

Step 11: The Equations of a Recursion

sr_formula shows the equations themselves, and sr_regex their solution, as a regular expression over the hops. On the whole network they are far too long to read; here they are restricted to RER B between Luxembourg and its two neighbours. Label every metro and RER hop (route_type 1 and 2) with its line and stations. plain(NULL::stops) reads the station names without their provenance, so that provenance() is the token of the hop alone, and the stops’ own tokens stay out of the result as well:

CREATE TABLE hop_name AS
  SELECT provenance(), h.line || ': ' || f.stop_name || ' → ' || t.stop_name
           AS value
  FROM hop h JOIN plain(NULL::stops) f ON f.stop_id = h.from_station
             JOIN plain(NULL::stops) t ON t.stop_id = h.to_station
  WHERE h.route_type IN (1, 2);

WITH RECURSIVE reach(station) AS (
    SELECT 'IDFM:71161'::text
  UNION
    SELECT h.to_station FROM reach r JOIN hop h ON h.from_station = r.station
    WHERE h.line = 'B'
      AND h.to_station IN ('IDFM:71161', 'IDFM:71106', 'IDFM:73620'))
SELECT s.stop_name, sr_formula(provenance(), 'hop_name'),
       sr_regex(provenance(), 'hop_name')
FROM reach r JOIN plain(NULL::stops) s ON s.stop_id = r.station;

For Port Royal, the equations are:

x₂ where x₁ = x₃ ⊗ B: Luxembourg → Saint-Michel Notre-Dame,
         x₂ = x₃ ⊗ B: Luxembourg → Port Royal,
         x₃ = 𝟙 ⊕ (x₂ ⊗ B: Port Royal → Luxembourg)
                ⊕ (x₁ ⊗ B: Saint-Michel Notre-Dame → Luxembourg)

One unknown per station, numbered as in the circuit Studio draws: Luxembourg (x₃) holds from the start (𝟙) or by coming back from either neighbour, and each neighbour by a hop from Luxembourg. The regular expression lists the journeys themselves, any number of round trips from Luxembourg (*, with | between the two neighbours), then the hop to Port Royal:

(B: Luxembourg → Port Royal · B: Port Royal → Luxembourg
 | B: Luxembourg → Saint-Michel Notre-Dame
   · B: Saint-Michel Notre-Dame → Luxembourg)*
· B: Luxembourg → Port Royal

Unlike the other semirings so far, the concatenation · of sr_regex does not commute, and follows the order of the query: reach comes first in the recursive FROM clause, so that each journey reads in the order it is made.

Step 12: The Fastest Journey Itself

sr_tropical gives the shortest travel time, not the journey that takes it. sr_tropical_paths gives both: the least cost, from a first mapping, and the journeys of that cost, as a regular expression over the labels of a second one, alternatives of the same cost joined by |. With the labels of Step 11, look for La Défense, on metro and RER only:

WITH RECURSIVE reach(station) AS (
    SELECT 'IDFM:71161'::text
  UNION
    SELECT h.to_station FROM reach r JOIN hop h ON h.from_station = r.station
    WHERE h.route_type IN (1, 2))
SELECT (sr_tropical_paths(provenance(), 'hop_minutes', 'hop_name')).*
FROM reach WHERE station = 'IDFM:71517';

The fastest journey takes RER B to Châtelet - Les Halles, and changes there to RER A:

B: Luxembourg → Saint-Michel Notre-Dame
· B: Saint-Michel Notre-Dame → Châtelet - Les Halles
· A: Châtelet - Les Halles → Auber · A: Auber → Charles de Gaulle - Étoile
· A: Charles de Gaulle - Étoile → La Défense

Step 13: One Journey, Step by Step

Two journeys may take the same time. From Luxembourg to La Motte-Picquet - Grenelle, the fastest journeys part at Gare Montparnasse, for metro 6 over four stops or metro 13 then 10 over three. Depending on the version of the dataset loaded, both may take the same time, and sr_tropical_paths then lists both:

WITH RECURSIVE reach(station) AS (
    SELECT 'IDFM:71161'::text
  UNION
    SELECT h.to_station FROM reach r JOIN hop h ON h.from_station = r.station
    WHERE h.route_type IN (1, 2))
SELECT (sr_tropical_paths(provenance(), 'hop_minutes', 'hop_name')).paths
FROM reach WHERE station = 'IDFM:71199';

B: Luxembourg → Port Royal · B: Port Royal → Denfert-Rochereau
· 6: Denfert-Rochereau → Raspail · 4: Raspail → Vavin
· 4: Vavin → Gare Montparnasse
· (6: Gare Montparnasse → Pasteur · 6: Pasteur → Sèvres-Lecourbe
   · 6: Sèvres-Lecourbe → Cambronne
   · 6: Cambronne → La Motte-Picquet - Grenelle
 | 13: Gare Montparnasse → Duroc · 10: Duroc → Ségur
   · 10: Ségur → La Motte-Picquet - Grenelle)

sr_best_path takes the same two mappings and keeps one journey of least time, the one with the fewest hops (then the first in alphabetical order of its hops), here through Duroc. It returns its hops as an array, in the order they are made, which unnest turns into an itinerary. To visit Provins, a medieval town in the east of the region:

WITH RECURSIVE reach(station) AS (
    SELECT 'IDFM:71161'::text
  UNION
    SELECT h.to_station FROM reach r JOIN hop h ON h.from_station = r.station
    WHERE h.route_type IN (1, 2))
SELECT round(j.cost::numeric, 1) AS minutes, step, hop
FROM (SELECT (sr_best_path(provenance(), 'hop_minutes', 'hop_name')).*
      FROM reach WHERE station = 'IDFM:62139') j,
     unnest(j.path) WITH ORDINALITY AS u(hop, step)
ORDER BY step;

 minutes | step |                         hop
---------+------+------------------------------------------------------
3 |    1 | B: Luxembourg → Saint-Michel Notre-Dame
3 |    2 | B: Saint-Michel Notre-Dame → Châtelet - Les Halles
3 |    3 | B: Châtelet - Les Halles → Gare du Nord
3 |    4 | 4: Gare du Nord → Gare de l'Est
3 |    5 | TER: Gare de l'Est → Longueville
3 |    6 | P: Longueville → Sainte-Colombe Septveilles
3 |    7 | P: Sainte-Colombe Septveilles → Champbenoist Poigny
3 |    8 | P: Champbenoist Poigny → Provins

Over the whole network, buses included, journeys of the same time are the rule rather than the exception, and the regular expression of sr_tropical_paths grows long, where sr_best_path still returns one journey.

Step 14: Metro or Train?

From Gare de Lyon, which of the other railway terminals of Paris are faster to reach by metro than by train (the RER and the suburban trains, route_type 2)? Each kind of journey is a recursive query, and EXCEPT takes the train journeys away from the metro ones:

WITH RECURSIVE
  metro(station) AS (
      SELECT 'IDFM:73626'::text
    UNION
      SELECT h.to_station FROM metro m JOIN hop h ON h.from_station = m.station
      WHERE h.route_type = 1),
  train(station) AS (
      SELECT 'IDFM:73626'::text
    UNION
      SELECT h.to_station FROM train t JOIN hop h ON h.from_station = t.station
      WHERE h.route_type = 2)
SELECT d.name, round(j.cost::numeric, 1) AS minutes, cardinality(j.path) AS hops
FROM (SELECT station,
             (sr_best_path(provenance(), 'hop_minutes', 'hop_name')).*
      FROM (SELECT station FROM metro EXCEPT SELECT station FROM train) t) j
JOIN (VALUES ('IDFM:71135', 'Gare d''Austerlitz'),
             ('IDFM:71359', 'Gare de l''Est'),
             ('IDFM:71410', 'Gare du Nord'),
             ('IDFM:71139', 'Gare Montparnasse'),
             ('IDFM:71370', 'Gare Saint-Lazare'))
       AS d(station, name)
  USING (station)
ORDER BY minutes;

       name        | minutes  | hops
-------------------+----------+------
 Gare d'Austerlitz |      5.9 |    3
 Gare Saint-Lazare |      8.4 |    4
 Gare de l'Est     |     10.3 |    7
 Gare Montparnasse |     12.0 |    8
 Gare du Nord      | Infinity |

All five are reached both ways, so that plain SQL would return none of them. In sr_best_path, the difference of two journeys is the first one where it is better than the second (faster or, as fast, with fewer hops, then first in alphabetical order of its hops), and nothing otherwise: the metro wins to four of the terminals, with the journey that does, while the train is faster to Gare du Nord (RER A then B, through Châtelet - Les Halles), which has no journey left.

Step 15: A Day of Rail Disruptions

Suppose each rail hop runs with probability 0.95, and each bus hop with probability 0.9:

SELECT set_prob(provenance(),
                CASE WHEN route_type = 3 THEN 0.9 ELSE 0.95 END)
FROM hop;

(The query returns one empty row per hop.)

The probability of still reaching a station is a network-reliability problem, hard in general. An exact answer would expand the equations into a Boolean circuit of billions of gates, and is refused:

WITH RECURSIVE reach(station) AS (
    SELECT 'IDFM:71161'::text
  UNION
    SELECT h.to_station FROM reach r JOIN hop h ON h.from_station = r.station)
SELECT probability_evaluate(provenance())
FROM reach WHERE station = 'IDFM:73699';

An approximation with an additive guarantee (see Choosing a guarantee, not a method) samples instead, solving the equations in each sampled world. With the buses, every destination is reached in practically every world; on the rail network alone, the ends of the branches show:

WITH RECURSIVE reach(station) AS (
    SELECT 'IDFM:71161'::text
  UNION
    SELECT h.to_station FROM reach r JOIN hop h ON h.from_station = r.station
    WHERE h.route_type <> 3)
SELECT d.name,
       round(probability_evaluate(provenance(), 'additive',
                                  'eps=0.01,delta=0.05')::numeric, 3) AS p
FROM reach r
JOIN (VALUES ('IDFM:474151', 'Châtelet - Les Halles'),
             ('IDFM:71517', 'La Défense'),
             ('IDFM:73721', 'Versailles Château Rive Gauche'),
             ('IDFM:73699', 'Aéroport CDG (Terminal 2)'),
             ('IDFM:68385', 'Marne-la-Vallée - Chessy'))
       AS d(station, name)
  USING (station)
ORDER BY p DESC;

The centre of the network, with many alternatives, stays almost certain to be reached; Chessy, at the end of a branch of RER A, depends on every hop of that branch, and is markedly less likely. Each estimate is within 0.01 of the true probability with probability 95%.

These estimates assume that every hop runs or not independently of all the others. In practice, the hops of the same line are correlated: a signal failure or a strike stops a whole stretch of a line at once, and an express train and the stopping service between the same stations, two alternatives here, share the same track. Such correlations would lower these probabilities a lot.

Case Study: Île-de-France Public Transit

The Scenario

Setup

Step 1: Explore the Database

Step 2: Provenance and Wheelchair Mapping

Step 3: Reachable Stops from Luxembourg

Step 4: Boolean Provenance – Full Wheelchair Accessibility

Step 5: Inspect Individual Results with sr_formula

Step 6: The Next Stop on Each Line (LATERAL)

Step 7: The Network as a Table

Step 8: Every Station Reachable from Luxembourg

Step 9: How Long, and Is There an Accessible Journey?

Step 10: Not Every Semiring Has an Answer

Step 11: The Equations of a Recursion

Step 12: The Fastest Journey Itself

Step 13: One Journey, Step by Step

Step 14: Metro or Train?

Step 15: A Day of Rail Disruptions

Step 5: Inspect Individual Results with `sr_formula`

Step 6: The Next Stop on Each Line (`LATERAL`)