如何查找1table以内的中转航班？

Question

我正在练习 SQL，我有一个名为 flights 的 table，航班为 id、origin、destination，以及行程的 cost。我希望能够找到所有可以在两站或更少站内完成的最便宜的航班，同时还显示每个航班有多少站以及航班的总费用。另外，如果两次旅行的费用相同，那么我想要停靠次数最少的一次。

这是 db-fiddle 上的 table：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 选项的方法。在这里你可以选择根和目的地，找出那些停站最少，钱最少的

   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

最后我自己解决了这个问题，George 和 Andronicus 都给了我解决问题的想法。

最后，我想制作一个航班列表，只显示最便宜的航班，不包括更贵的航班。

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;

如何查找1table以内的中转航班？

How to find connecting flights within 1 table?

sql

database

postgresql

recursion

common-table-expression