使用 Postgres 的递归/分层查询 [英] Recursive/Hierarchical Query Using Postgres

问题描述

表格:航班(flight_num, src_city, dest_city, dep_time, arr_time, airfare, mileage)

我需要找到从任何给定源城市到任何给定目的地城市的无限次停靠的最便宜票价.问题是这可能涉及多次航班，例如，如果我从蒙特利尔->堪萨斯城飞行，我可以从蒙特利尔->华盛顿然后从华盛顿->堪萨斯城等等.我将如何使用 Postgres 查询生成它?

I need to find the cheapest fare for unlimited stops from any given source city to any given destination city. The catch is that this can involve multiple flights, so for example if I'm flying from Montreal->KansasCity I can go from Montreal->Washington and then from Washington->KansasCity and so on. How would I go about generating this using a Postgres query?

样本数据:

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);

推荐答案

[此答案基于 Gordon 的]

[this answer is based on Gordon's]

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

I changed arr_time and dep_time to TIME datatypes, which makes calculations easier. Also added result columns for total_time and waiting_time. Note: if there are any loops possible in the graph, you will need to avoid them (possibly using an array to store the path)

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
    ;

仅供参考:表结构的变化:

FYI: the changes to the table structure:

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);

这篇关于使用 Postgres 的递归/分层查询的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！