Sql查询获取src到目标路径连接航班

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列开始，路径&结束，在第2列，我们转换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数组上的长度来限制连接的数量，但是一旦达到最大连接数，可能会更有效地停止递归队列中的迭代。最后一点：为了让事情变得简单，我使用了除最终目的地之外的路径，例如， {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'