12494

Recursive/Hierarchical Query Using Postgres

The table: Flight (flight_num, src_city, dest_city, dep_time, arr_time, airfare, mileage)

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 <strong>multiple flights</strong>, 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?

Sample Data:

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

Answer1:

[this answer is based on Gordon's]

I changed arr_time and dep_time to TIME datatypes, which makes calculations easier. Also added result columns for total_time and waiting_time. <strong>Note</strong>: 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 );

And to the data:

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

Answer2:

You want to use a recursive CTE for this. However, you will have to make a decision about how many flights to include. The following (untested) query shows how to do this, limiting the number of flight segments to 5:

with recursive segs as ( select cast(f.flight_num as varchar(255)) as flight, src_city, dest_city, dept_time, arr_time, airfare, mileage, 1 as numsegs from flight f where src_city = <SRC_CITY> union all select cast(s.flight||'-->'||cast(f.flight_num as varchar(255)) as varchar(255)) as flight, s.src_city, f.dest_city, s.dept_time, f.arr_time, s.airfare + f.airfare as airfare, s.mileage + f.mileage as milage, s.numsegs + 1 from segs s join flight f on s.src_city = f.dest_city where s.numsegs < 5 ) select * from segs where dest_city = <DEST_CITY> order by airfare desc limit 1;

Answer3:

Something like this:

select * from (select flight_num, airfare from flight where src_city = ? and dest_city = ? union select f1.flight_num || f2.flight_num, f1.airfare+f2.airfare from flight f1, flight f2 where f1.src_city = ? and f2.dest_city = ? and f1.dest_city = f2.src_city union ... ) s order by airfare desc

I didn't test that as I'm leaving that for you so there might be subtle problems that require testing. This is clearly homework since no airline plans things this way. So I don't mind leaving you extra work.

Recommend

  • PostgreSQL: Iterate through a tables rows with for loop, retrieve column value based on current row
  • What do I put in date_default_timezone_set?
  • “Screen scrape” with Jsoup with element who has ID
  • Comparing Two JSON Objects
  • How to store and retrieve values using Ruby?
  • can not convert column type from object to str in python dataframe
  • d3.js How to draw stacked horziontal bars from array?
  • PHP - Setting inherited static property will also set it in other classes inheriting it
  • Mulit-Day All-Day Event
  • Put elements of a 1D vector into a 3D matrix using another matrix of positions
  • Add MathJax script to pages in Office 365 Sharepoint
  • I have accidentally uninstalled jack server while building Android AOSP
  • Filter Values of Current Week with XQuery
  • d3 onclick to get the specific path/bar reference
  • $this->db->insert_id(); returning 0 every time in codeigniter [duplicate]
  • ASP Net Core - Mixing External Identity Provider with Individual User Accounts for Audit Tracking
  • angularjs accessing ng-model from outside the $scope
  • Change subtype in Hibernate Inheritance
  • Relay Error when deleting: RelayMutationQuery: Invalid field name on fat query
  • Customize google placepicker colors for android
  • Add foreach value to Ajax
  • Error: java.util.Arrays$ArrayList cannot be cast to java.util.ArrayList
  • PostgreSQL primary key auto increment crashes in C++
  • Angular transclude in a directive containing a ng-template (generic Confirm Modal)
  • if I want to find what's referencing an object in SQL Server, is searching syscomments comprehe
  • Why is it still possible to insert a foreign key that doesn't exist?
  • R - Change list of ggplot objects into a list of grobs that grid.arrange will accept?
  • Insert Statement
  • Cannot style mat-tab without ::ng-deep and !important
  • Embedded Google Maps in Rails not responsive
  • AlertDialog style when using setView()
  • allocating memory to an array of string
  • Why querying a date BC is changed to AD in Java?
  • Database structure design with variable amounts of fields
  • Why value captured by reference in lambda is broken? [duplicate]
  • Convert array of 8 bytes to signed long in C++
  • Understanding cpu registers
  • Why joiner is not used after Sequence generator or Update statergy
  • Running Map reduces the dimensions of the matrices
  • UserPrincipal.Current returns apppool on IIS