gpt4 book ai didi

SQL查询以获取连接航类的src到dest路径

转载 作者:行者123 更新时间:2023-11-29 11:49:21 26 4
gpt4 key购买 nike

我想解决一个问题,我希望找到 src 到 dest 飞行路径,包括连接航类,并在可能的情况下按所需时间对其进行排序。

我可以使用 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)

我的 table 现在看起来像这样

\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

最佳答案

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 中有两个部分。 anchor 子查询和递归子查询。先执行 anchor 子查询,再执行递归子查询,直到返回空结果集。棘手的部分(至少对我而言)是构建将执行从 1 个节点到下一个节点的遍历的连接。

anchor 查询和递归子查询使用 UNION ALL 合并(或有时 UNION )并返回。

由于我们对航线感兴趣,因此可以从一个简单的锚定子查询开始:

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

上面的查询有 3 列开始、路径和结束,在第 2 列中,我们将 src 转换为来自 TEXT 的字段至 TEXT[] .虽然这不是严格需要的,但它会大大简化剩余的步骤,因为数组很容易附加到。

使用上面的 anchor 查询,我们现在可以定义我们的递归 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. 仅在到达(A-B) < 出发(B-C) 时才考虑转机航类 A-B 和 B-C 有效

对于这个例子,令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'

关于SQL查询以获取连接航类的src到dest路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46597366/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com