SQL查询将src获取到dest路径以连接航班

Question

我想解决一个问题，在该问题中，我希望找到src到目的地的飞行路线，包括转机航班，并在可能的情况下对所需时间进行排序。

我可以使用listagg之类的方式以某种方式将中间航班聚合为一个字符串吗？

我们可以将转乘航班的数量限制为一个数字和所花费的时间。

我现在有个开始，这让我转机

with  cap as (select 30 time_cap , 5 connect_cap), 
 connecting as 
    (select f1.src src1
          , f1.dest dest1
          , f1.stt st1
          , f1.endt end1
          , f2.src src2
          , f2.dest dest2
          , f2.stt st2
          , f2.endt end2
          , (f2.endt - f1.stt) as time 
     from flight f1 
     inner join flight f2 on f1.dest = f2.src 
     where f1.endt < f2.stt)

我的桌子现在看起来像这样

\d+ flight
                                  Table "public.flight"
 Column |            Type             | Modifiers | Storage  | Stats target | Description 
--------+-----------------------------+-----------+----------+--------------+-------------
 src    | character varying(20)       |           | extended |              | 
 dest   | character varying(20)       |           | extended |              | 
 stt    | timestamp without time zone |           | plain    |              | 
 endt   | timestamp without time zone |           | plain    |              |

这是一个面试问题，已经解决了。

可以在SQL查询中解决图形BFS的解决方案吗？

即使是无效的查询（伪代码-如果尝试也可以）或方法都可以。

在下面的查询中，我想在string_agg中找出一种方法，可以检查上一个目的地是否是我要去的目的地。

with flight as (select f1.src||'-'||f1.dest||','||f2.src||'-'||f2.dest route
                     , f1.src src1
                     , f1.dest dest1
                     , f1.stt st1
                     , f1.endt end1
                     , f2.src src2
                     , f2.dest dest2
                     , f2.stt st2
                     , f2.endt end2
                     , (f2.endt - f1.stt) as time 
                from flight f1 
                inner join flight f2 on f1.dest = f2.src 
                where f1.endt < f2.stt)

select string_agg(route,',') from flight ;

查询飞行的输出

  route  | src1 | dest1 |         st1         |        end1         | src2 | dest2 |         st2         |        end2         |   time   
---------+------+-------+---------------------+---------------------+------+-------+---------------------+---------------------+----------
 a-b,b-c | a    | b     | 2017-05-17 09:31:56 | 2017-05-17 14:31:56 | b    | c     | 2017-05-17 15:31:56 | 2017-05-17 16:31:56 | 07:00:00

Answer 1

可以使用特殊语法解决SQL中这些类型的树遍历问题WITH RECURSIVE。

为了测试解决方案，让我们用虚拟数据创建下表：

CREATE TABLE flight (
  src TEXT
, dest TEXT
, stt TIMESTAMP
, endt TIMESTAMP);

INSERT INTO flight VALUES 
('SIN', 'DAC', '2016-12-31 22:45:00', '2017-01-01 01:45:00'),
('DAC', 'SIN', '2017-01-01 16:30:00', '2017-01-01 21:30:00'),
('SIN', 'DAC', '2017-01-01 22:45:00', '2017-01-02 01:45:00'),
('DAC', 'DEL', '2017-01-01 10:00:00', '2017-01-01 11:30:00'),
('DEL', 'DAC', '2017-01-01 12:30:00', '2017-01-01 14:00:00'),
('DAC', 'CCU', '2017-01-01 10:30:00', '2017-01-01 11:15:00'),
('CCU', 'DAC', '2017-01-01 11:45:00', '2017-01-01 12:30:00'),
('SIN', 'DEL', '2017-01-01 11:00:00', '2017-01-01 15:00:00'),
('DEL', 'SIN', '2017-01-01 16:30:00', '2017-01-01 20:30:00'),
('CCU', 'DEL', '2017-01-01 12:00:00', '2017-01-01 12:45:00'),
('DEL', 'CCU', '2017-01-01 13:15:00', '2017-01-01 14:00:00');

递归CTE很难理解，因此我将逐步构建逻辑。

在递归CTE中，有两个部分。锚点子查询和递归子查询。首先执行锚子查询，然后执行递归子查询，直到返回空结果集。棘手的部分（至少对我而言）正在构造将执行从1个节点到下一个节点的遍历的联接。

锚和递归子查询使用UNION ALL（有时是UNION）合并并返回。

由于我们对飞行路线感兴趣，因此从以下开始的简单锚子查询将是：

SELECT src, ARRAY[src] path, dest FROM flight

上面的查询包含3列，分别是开始，路径和结束，在第二列中，我们将src字段从转换TEXT为TEXT[]。尽管并非严格要求这样做，但由于数组易于附加，因此它将大大简化其余步骤。

使用上面的锚点查询，我们现在可以定义递归cte。

WITH RECURSIVE flight_paths (src, path, dest) AS (
SELECT
  src
, ARRAY[src]
, dest 
FROM flight
UNION ALL
SELECT
  fp.src
, fp.path || f.src -- appends another 'flight source'
, f.dest -- updates the dest to the new dest
FROM flight f
JOIN flight_paths fp ON f.src = fp.dest 
-- this is the join that links the tree nodes
WHERE NOT f.src = ANY(fp.path) 
-- this condition prevents infinite recursion by not visiting nodes that have already been visited.
) SELECT * FROM flight_paths
-- finally, we can select from the flight_paths recursive cte

上面的代码返回了136行我的测试数据。前15行如下所示：

src path        dest
SIN {SIN}       DAC
DAC {DAC}       SIN
SIN {SIN}       DAC
DAC {DAC}       DEL
DEL {DEL}       DAC
DAC {DAC}       CCU
CCU {CCU}       DAC
SIN {SIN}       DEL
DEL {DEL}       SIN
CCU {CCU}       DEL
DEL {DEL}       CCU
DEL {DEL,CCU}   DAC
DAC {DAC,CCU}   DAC
DEL {DEL,CCU}   DEL
DAC {DAC,CCU}   DEL
DEL {DEL,CCU}   DEL
DAC {DAC,CCU}   DEL

这 是树遍历的设置 ，是编写递归cte的最难部分。现在，遍历已建立，我们可以修改上面的内容，以便：

1. 我们从源头开始，到目的地结束
2. 到达目的地时停止迭代
3. 仅在到达（AB）<离开（BC）时才认为转机航班AB和BC有效

在此示例中，让src := SIN＆dest := CCU

WITH RECURSIVE flight_paths (src, path, dest, stt, endt) AS (
SELECT
  src
, ARRAY[src]
, dest 
, stt
, endt
FROM flight
UNION ALL
SELECT
  fp.src
, fp.path || f.src
, f.dest 
, fp.stt
, f.endt -- update endt to the new endt
FROM flight f
JOIN flight_paths fp ON f.src = fp.dest 
WHERE NOT f.src = ANY(fp.path) 
  AND NOT 'CCU' = ANY(fp.path) 
  -- (2) this new predicate stop iteration when the destination is reached
  AND f.stt > fp.endt
  -- (3) this new predicate only proceeds the iteration if the connecting flights are valid
) 
SELECT * 
FROM flight_paths
WHERE src = 'SIN' AND dest = 'CCU'
-- (1) specify the start & end

这给出了2条可能的路线，以第一个航班的出发时间为列stt，最后一个航班的到达时间为endt：

src path            dest    stt                 endt
SIN {SIN,DAC}       CCU     2016-12-31 22:45:00 2017-01-01 11:15:00
SIN {SIN,DAC,DEL}   CCU     2016-12-31 22:45:00 2017-01-01 14:00:00

现在可以非常轻松地优化结果集。例如，可以将最终查询修改为仅返回中午之前到达目的地的航班，如下所示：

SELECT * 
FROM flight_paths
WHERE src = 'SIN' AND dest = 'CCU' 
  AND endt::time < '12:00:00'::time

从这一点开始，在递归cte中添加计算飞行时间和连接时间的列，然后过滤适合两次谓词的飞行，这也是相当容易的。希望我已经为您提供了足够的详细信息以生成这两种变体。

您也可以通过过滤path数组的长度来限制连接数，尽管一旦达到最大连接数，在递归cte中停止迭代可能会更有效。

最后一点：为了使事情变得简单，我使用了除最终目的地之外的路径，例如，{SIN, DAC, DEL}而不是航班序列{SIN-DAC, DAC-DEL, DEL-CCU}（ 或停靠站{DAC, DEL}），但是我们可以很容易地获得这些表示形式，如下所示：

WITH RECURSIVE flight_paths (src, flights, path, dest, stt, endt) AS (
SELECT
  src
, ARRAY[src || '-' || dest]
, ARRAY[src]
, dest 
, stt
, endt
FROM flight
UNION ALL
SELECT
  fp.src
, fp.flights || (f.src || '-' || f.dest)
, fp.path || f.src
, f.dest
, fp.stt
, f.endt
FROM flight f
JOIN flight_paths fp ON f.src = fp.dest 
WHERE NOT f.src = ANY(fp.path) 
  AND NOT 'CCU' = ANY(fp.path) 
  AND f.stt > fp.endt
) 
SELECT flights, stt, endt, path[2:] stopovers
FROM flight_paths
WHERE src = 'SIN' AND dest = 'CCU'