使用Postgres的递归/层次查询

一尘不染

使用Postgres的递归/层次查询

sql

表： Flight (flight_num, src_city, dest_city, dep_time, arr_time, airfare,mileage)

我需要找到从任何给定的源城市到任何给定的目标城市无限制停留的最便宜的票价。问题是这可能涉及 多个航班 ，因此例如，如果我从蒙特利尔->堪萨斯城
出发，我可以从蒙特利尔->华盛顿出发，然后从华盛顿->堪萨斯城等等。我将如何使用Postgres查询生成此信息？

样本数据：

create table flight(
  flight_num BIGSERIAL PRIMARY KEY,
  source_city varchar,
  dest_city varchar,
  dep_time int,
  arr_time int,
  airfare int,
  mileage int
);


insert into flight VALUES
  (101,    'Montreal', 'NY',         0530,     0645,    180,      170),
  (102,    'Montreal', 'Washington',     0100,     0235,    100,      180),
  (103,    'NY',   'Chicago',        0800,     1000,    150,      300),
  (105,    'Washington', 'KansasCity',    0600,     0845,    200,      600),
  (106,    'Washington', 'NY',         1200,     1330,     50,       80),
  (107,    'Chicago',  'SLC',        1100,     1430,    220,      750),
  (110,    'KansasCity',  'Denver',         1400,     1525,    180,      300),
  (111,    'KansasCity',  'SLC',        1300,     1530,    200,      500),
  (112,    'SLC',    'SanFran',        1800,     1930,     85,      210),
  (113,    'SLC',    'LA',         1730,     1900,    185,      230),
  (115,    'Denver', 'SLC',        1500,     1600,     75,      300),
  (116,    'SanFran',  'LA',         2200,     2230,     50,       75),
  (118,    'LA',   'Seattle',        2000,     2100,    150,      450);

阅读 184

2021-05-30

共1个答案

一尘不染

[此答案基于戈登的]

我将arr_time和dep_time更改为TIME数据类型，这使计算更加容易。还添加了total_time和waiting_time的结果列。
注意：如果图形中可能存在任何循环，则需要避免循环（可能使用数组存储路径）

WITH RECURSIVE segs AS (
  SELECT f0.flight_num::text as flight
            , src_city, dest_city
            , dep_time AS departure
            , arr_time AS arrival
            , airfare, mileage
            , 1 as hops
            , (arr_time - dep_time)::interval AS total_time
            , '00:00'::interval as waiting_time
  FROM flight f0
  WHERE src_city = 'SLC' -- <SRC_CITY>
  UNION ALL
  SELECT s.flight || '-->' || f1.flight_num::text as flight
            , s.src_city, f1.dest_city
            , s.departure AS departure
            , f1.arr_time AS arrival
            , s.airfare + f1.airfare as airfare
            , s.mileage + f1.mileage as mileage
            , s.hops + 1 AS hops
            , s.total_time + (f1.arr_time - f1.dep_time)::interval AS total_time
            , s.waiting_time + (f1.dep_time - s.arrival)::interval AS waiting_time
  FROM segs s
     JOIN flight f1
       ON f1.src_city = s.dest_city
       AND f1.dep_time > s.arrival -- you can't leave until you are there
)
SELECT *
FROM segs
WHERE dest_city = 'LA' -- <DEST_CITY>
ORDER BY airfare desc
    ;

仅供参考：对表结构的更改：

create table flight
  ( flight_num BIGSERIAL PRIMARY KEY
  , src_city varchar
  , dest_city varchar
  , dep_time TIME
  , arr_time TIME
  , airfare INTEGER
  , mileage INTEGER
);

并向数据：

insert into flight VALUES
  (101,    'Montreal',          'NY',                   '05:30',     '06:45',    180,      170),
  (102,    'Montreal',          'Washington',           '01:00',     '02:35',    100,      180),
  (103,    'NY',                'Chicago',              '08:00',     '10:00',    150,      300),
  (105,    'Washington',        'KansasCity',           '06:00',     '08:45',    200,      600),
  (106,    'Washington',        'NY',                   '12:00',     '13:30',     50,       80),
  (107,    'Chicago',           'SLC',                  '11:00',     '14:30',    220,      750),
  (110,    'KansasCity',        'Denver',               '14:00',     '15:25',    180,      300),
  (111,    'KansasCity',        'SLC',                  '13:00',     '15:30',    200,      500),
  (112,    'SLC',               'SanFran',              '18:00',     '19:30',     85,      210),
  (113,    'SLC',               'LA',                   '17:30',     '19:00',    185,      230),
  (115,    'Denver',            'SLC',                  '15:00',     '16:00',     75,      300),
  (116,    'SanFran',           'LA',                   '22:00',     '22:30',     50,       75),
  (118,    'LA',                'Seattle',              '20:00',     '21:00',    150,      450);

2021-05-30