Как найти стыковочные рейсы в пределах 1 таблицы?

Question

Я практикую SQL, и у меня есть стол с именем flights, в котором есть рейс id, origin, destination и cost поездки. Я хочу, чтобы можно было найти все самые дешевые рейсы, которые можно выполнить за две или менее остановки, а также указать, сколько остановок имеет каждый рейс, а также общую стоимость полета. Кроме того, если две поездки стоят одинаково, я хочу одну с наименьшим количеством остановок.

Вот таблица на db-fiddle: https://www.db-fiddle.com/f/mvvE24KAxnayR9fRmHChMw/1

Это это то, что я имею до сих пор, и это не завершено, так как мне не хватает количества остановок и некоторых рейсов. Я не уверен, как подсчитать количество остановок между рейсами или как получить все стыковочные рейсы.

Мне кажется, что это можно сделать без рекурсивного CTE, но я не уверен. Я также чувствую, что мой запрос очень грязный. Любая помощь будет полезна!

Спасибо!

Запрос:

WITH RECURSIVE connecting_flights AS (

  SELECT origin, destination, cost 
  FROM flights

  UNION ALL

  SELECT f.origin, f.destination, cf.cost
  FROM flights f
  INNER JOIN connecting_flights cf ON cf.origin = f.destination

), flight_data as (
    SELECT 
        DISTINCT flights.origin as original_flight
       , flights.destination as original_destination
       , flights.cost as flights_cost
       , cf.origin as cf_origin
       , cf.destination as cf_destination
       ,cf.cost as cf_cost
       , flights.cost + cf.cost as total_cost
    FROM flights
    LEFT JOIN connecting_flights cf ON cf.origin = flights.destination
    LEFT JOIN flights b ON b.origin = cf.origin
) 

SELECT
    original_flight
    , CASE 
        WHEN cf_destination IS NULL THEN original_destination
        ELSE cf_destination
     END as destination
   , CASE
       WHEN cf_destination IS NULL THEN flights_cost
       ELSE total_cost
    END as total
FROM flight_data
ORDER BY original_flight

Answer 1

Поскольку вы рассматриваете только до двух шагов, вы можете использовать union all:

select f.origin, f.destination, 0 steps, f.cost, f.origin || '->' || f.destination route
from flights f
union all
select f1.origin, f2.destination, 1, f1.cost + f2.cost, f1.origin || '->' || f1.destination || '->' || f2.destination route
from flights f1
inner join flights f2 on f1.destination = f2.origin
union all
select f1.origin, f3.destination, 2, f1.cost + f2.cost + f3.cost, f1.origin || '->' || f1.destination || '->' || f2.destination || '->' || f3.destination route
from flights f1
inner join flights f2 on f1.destination = f2.origin
inner join flights f3 on f2.destination = f3.origin
order by cost, steps

Результат:

| origin | destination | steps | cost | route              |
| ------ | ----------- | ----- | ---- | ------------------ |
| DFW    | MCO         | 0     | 100  | DFW->MCO           |
| SFO    | DFW         | 0     | 200  | SFO->DFW           |
| DFW    | JFK         | 0     | 200  | DFW->JFK           |
| SFO    | MCO         | 1     | 300  | SFO->DFW->MCO      |
| SFO    | MCO         | 0     | 400  | SFO->MCO           |
| SFO    | JFK         | 1     | 400  | SFO->DFW->JFK      |
| SFO    | JFK         | 0     | 500  | SFO->JFK           |
| JFK    | LHR         | 0     | 1000 | JFK->LHR           |
| DFW    | LHR         | 1     | 1200 | DFW->JFK->LHR      |
| SFO    | LHR         | 2     | 1400 | SFO->DFW->JFK->LHR |
| SFO    | LHR         | 1     | 1500 | SFO->JFK->LHR      |

Answer 2

это способ использования рекурсивной опции cte. Здесь вы можете выбрать root и пункт назначения и найти те, которые принимают наименьшее количество остановок и наименьшее количество денег

   with recursive cte
     as(select origin,destination,cast(destination as varchar(1000)) as str_path,origin as root,cost,0 as lvl 
         from flights
       union all
       select ua.origin,ua.destination,cast(concat(str_path,'-',ua.destination) as varchar(1000)),c.root,c.cost+ua.cost,c.lvl+1
         from cte c
         join flights ua
           on c.destination=ua.origin
          and c.str_path not like concat('%',ua.destination,'%')  
         )
  select * from cte  order by 4,2,cost asc 

+--------+-------------+-------------+------+------+-----+
| origin | destination |  str_path   | root | cost | lvl |
+--------+-------------+-------------+------+------+-----+
| DFW    | JFK         | JFK         | DFW  |  200 |   0 |
| JFK    | LHR         | JFK-LHR     | DFW  | 1200 |   1 |
| DFW    | MCO         | MCO         | DFW  |  100 |   0 |
| JFK    | LHR         | LHR         | JFK  | 1000 |   0 |
| SFO    | DFW         | DFW         | SFO  |  200 |   0 |
| DFW    | JFK         | DFW-JFK     | SFO  |  400 |   1 |
| SFO    | JFK         | JFK         | SFO  |  500 |   0 |
| JFK    | LHR         | DFW-JFK-LHR | SFO  | 1400 |   2 |
| JFK    | LHR         | JFK-LHR     | SFO  | 1500 |   1 |
| DFW    | MCO         | DFW-MCO     | SFO  |  300 |   1 |
| SFO    | MCO         | MCO         | SFO  |  400 |   0 |
+--------+-------------+-------------+------+------+-----+

db fiddle link

https://dbfiddle.uk/?rdbms=postgres_12&fiddle=2fc63555177972cb6c60e63d030fc9af

Answer 3

Я сам решил эту проблему, и Джордж, и Андроник дали мне идеи о том, как решить проблему.

В конце я хотел составить список рейсов, в которых отображаются только самые дешевые рейсы, исключая рейсы, которые стоят дороже.

WITH RECURSIVE connecting_flights AS (

  SELECT origin, destination, cost, 0 AS stops
  FROM flights

  UNION ALL

  SELECT cf.origin, f.destination, (cf.cost + f.cost) as cost, cf.stops + 1 AS stops
  FROM flights f
  INNER JOIN connecting_flights cf ON cf.destination = f.origin
  WHERE cf.stops <= 2 and cf.origin <> f.destination
  )

SELECT flights.origin, flights.destination, cf.stops, MIN(flights.cost) as total_cost
FROM connecting_flights AS flights
INNER JOIN connecting_flights AS cf ON cf.origin = flights.origin 
   AND cf.destination = flights.destination
GROUP BY flights.origin, flights.destination, cf.stops, cf.cost
HAVING MIN(flights.cost) = cf.cost
ORDER BY origin, destination;