SQL Linear Recursion to Find Cheapest Airline Connections

By Ashutosh Malgaonkar

---

Table of Contents:

• I. The Problem Statement
• II. How the Data Looks
• III. Understanding the Problem with the Data
• IV. How Recursion is Implemented in PostgreSQL
• V. Solution Implementation

I. The Problem Statement

Company X employees are trying to find the cheapest flights to upcoming conferences.

When traveling long distances, direct flights between cities can often be more expensive than taking connecting flights through hub cities. By adding layovers, travelers can find more affordable options. However, for this challenge, we will assume that no traveler is willing to make more than two stops.

The flight data is stored in the following table structure:

• id – Unique identifier for each flight
• origin – The departure city
• destination – The arrival city
• cost – The cost of the flight

Your goal is to produce a trips table listing the cheapest possible flights between all origin-destination pairs, taking into account up to two layovers.

II. How the Data Looks

The flight data is structured as follows:

    CREATE TABLE flights (
        id SERIAL PRIMARY KEY,
        origin VARCHAR(50),
        destination VARCHAR(50),
        cost INT
    );
    

Sample data:

    INSERT INTO flights (origin, destination, cost) VALUES
    ('New York', 'Chicago', 150),
    ('Chicago', 'Los Angeles', 200),
    ('New York', 'Denver', 300),
    ('Denver', 'Los Angeles', 180),
    ('New York', 'Los Angeles', 500);
    

III. Understanding the Problem with the Data

Given this dataset, we aim to determine the cheapest routes between any two cities, considering direct and connecting flights. The challenge is to efficiently compute these paths using SQL recursion.

IV. How Recursion is Implemented in PostgreSQL

PostgreSQL supports Common Table Expressions (CTEs) that allow recursive queries. Here’s a simple recursion example that prints numbers from 1 to 10:

    WITH RECURSIVE count_to_ten(n) AS (
        SELECT 1
        UNION ALL
        SELECT n + 1 FROM count_to_ten WHERE n < 10
    )
    SELECT * FROM count_to_ten;
    

This demonstrates how recursion can generate sequences based on an initial value and a recursive step.

V. Solution Implementation

To find the cheapest flights using SQL recursion, we extend this principle to compute flight connections:

    WITH RECURSIVE flight_paths AS (
        SELECT id, origin, destination, cost, 0 AS stops FROM flights
        UNION ALL
        SELECT f.id, fp.origin, f.destination, fp.cost + f.cost, fp.stops + 1
        FROM flight_paths fp
        JOIN flights f ON fp.destination = f.origin
        WHERE fp.stops < 2
    )
    SELECT origin, destination, MIN(cost) AS cheapest_cost
    FROM flight_paths
    WHERE origin != destination
    GROUP BY origin, destination;
    

This recursive query works as follows:

• First, it selects all direct flights.
• Then, it recursively finds connecting flights while keeping track of the total cost and number of stops.
• Finally, it selects the minimum-cost paths for each origin-destination pair.

With this approach, we efficiently compute the cheapest airline connections using PostgreSQL recursion.

Conclusion

SQL recursion is a powerful tool for solving graph traversal problems like airline connections. By leveraging recursive CTEs, we efficiently compute the cheapest flights while limiting stops. This approach allows businesses to optimize travel costs effectively.