Рекурсивные запросы с использованием Postgres

В таблице: flights (id,origin_apt, destination_apt, departure_time, arrival_time)
Мне нужно, построить маршруты для перелета с условием что может быть как прямой рейс из точки A в точку Z, так и с пересадками из точки A в точку B, затем из точки B в точку Z и так далее Максимальное число пересадок 5.
Я начал делать это с помощью запросов в Postgres, но мне удалось сделать только прямой рейс и с одной пересадкой
А вот осилить маршруты с 3-5 пересадками, мне не хватает знаний:
A -> Z
A -> B -> Z
A -> B -> C -> Z
A -> B -> C -> D -> Z
A -> B -> C -> D -> E -> Z
WITH RECURSIVE segs AS ( SELECT f0.id::text as flights , origin_apt, destination_apt , departure_time AS departure , arrival_time AS arrival , 1 as hops , (arrival_time - departure_time)::interval AS total_time , '00:00'::interval as waiting_time FROM flights f0 WHERE origin_apt = 'SVX' -- AND departure_time >= '2016-01-19' UNION ALL SELECT s.flights || '-->' || f1.id::text as flights , s.origin_apt, f1.destination_apt , s.departure AS departure , f1.arrival_time AS arrival , s.hops + 1 AS hops , s.total_time + (f1.arrival_time - f1.departure_time)::interval AS total_time , s.waiting_time + (f1.departure_time - s.arrival)::interval AS waiting_time FROM segs s JOIN flights f1 ON f1.origin_apt = s.destination_apt AND f1.departure_time >= s.arrival + '8 hour' -- ) SELECT * FROM segs WHERE destination_apt = 'PEK' -- AND waiting_time < '25 day'-- ORDER BY departure, waiting_time asc;
Пример данных:
CREATE TABLE flights ( id serial NOT NULL, origin_apt character varying, destination_apt character varying, departure_time timestamp without time zone, arrival_time timestamp without time zone, CONSTRAINT flights_pkey PRIMARY KEY (id) );
insert into flights VALUES (1,'GOJ','TAS','2016-01-04 06:00','2016-01-04 11:30'), (2,'GOJ','TAS','2016-01-11 06:00','2016-01-11 11:30'), ('3','GOJ','TAS','2016-01-18 06:00','2016-01-18 11:30'), ('4','GOJ','TAS','2016-01-25 06:00','2016-01-25 11:30'), ('5','GOJ','TAS','2016-02-01 06:00','2016-02-01 11:30'), ('6','GOJ','TAS','2016-02-08 06:00','2016-02-08 11:30'), ('7','GOJ','TAS','2016-02-15 06:00','2016-02-15 11:30'), ('8','GOJ','TAS','2016-02-22 06:00','2016-02-22 11:30'), ('9','GOJ','TAS','2016-02-29 06:00','2016-02-29 11:30'), ('10','GOJ','TAS','2016-03-07 06:00','2016-03-07 11:30'), ('11','GOJ','TAS','2016-03-14 06:00','2016-03-14 11:30'), ('12','GOJ','TAS','2016-03-21 06:00','2016-03-21 11:30'), ('13','GOJ','DYU','2016-01-02 03:40','2016-01-02 09:30'), ('14','GOJ','DYU','2016-01-09 03:40','2016-01-09 09:30'), ('15','GOJ','DYU','2016-01-16 03:40','2016-01-16 09:30'), ('16','GOJ','DYU','2016-01-23 03:40','2016-01-23 09:30'), ('17','GOJ','DYU','2016-01-30 03:40','2016-01-30 09:30'), ('18','GOJ','DYU','2016-02-06 03:40','2016-02-06 09:30'), ('19','GOJ','DYU','2016-02-13 03:40','2016-02-13 09:30'), ('20','GOJ','DYU','2016-02-20 03:40','2016-02-20 09:30'), ('21','GOJ','DYU','2016-02-27 03:40','2016-02-27 09:30'), ('22','GOJ','DYU','2016-03-05 03:40','2016-03-05 09:30'), ('23','GOJ','DYU','2016-03-12 03:40','2016-03-12 09:30'), ('24','GOJ','DYU','2016-03-19 03:40','2016-03-19 09:30'), ('25','GOJ','DYU','2016-03-26 03:40','2016-03-26 09:30'), ('26','TAS','PEK','2016-01-06 13:40','2016-01-06 22:00'), ('27','TAS','PEK','2016-01-13 13:40','2016-01-13 22:00'), ('28','TAS','PEK','2016-01-20 13:40','2016-01-20 22:00'), ('29','TAS','PEK','2016-01-27 13:40','2016-01-27 22:00'), ('30','TAS','PEK','2016-02-03 13:40','2016-02-03 22:00'), ('31','TAS','PEK','2016-02-10 13:40','2016-02-10 22:00'), ('32','TAS','PEK','2016-02-17 13:40','2016-02-17 22:00'), ('33','TAS','PEK','2016-02-24 13:40','2016-02-24 22:00'), ('34','TAS','PEK','2016-03-02 13:40','2016-03-02 22:00'), ('35','TAS','PEK','2016-03-09 13:40','2016-03-09 22:00'), ('36','TAS','PEK','2016-03-16 13:40','2016-03-16 22:00'), ('37','TAS','PEK','2016-03-23 13:40','2016-03-23 22:00'), ('38','PRG','PEK','2016-01-08 13:00','2016-01-09 05:55'), ('39','PRG','PEK','2016-01-15 13:00','2016-01-16 05:55'), ('40','PRG','PEK','2016-01-22 13:00','2016-01-23 05:55'), ('41','PRG','PEK','2016-01-29 13:00','2016-01-30 05:55'), ('42','PRG','PEK','2016-02-05 13:00','2016-02-06 05:55'), ('43','PRG','PEK','2016-02-12 13:00','2016-02-13 05:55'), ('44','PRG','PEK','2016-02-19 13:00','2016-02-20 05:55'), ('45','PRG','PEK','2016-02-26 13:00','2016-02-27 05:55'), ('46','PRG','PEK','2016-03-04 13:00','2016-03-05 05:55'), ('47','PRG','PEK','2016-03-11 13:00','2016-03-12 05:55'), ('48','PRG','PEK','2016-03-18 13:00','2016-03-19 05:55'), ('49','PRG','PEK','2016-03-25 13:00','2016-03-26 05:55'), ('50','PRG','PEK','2016-01-04 13:00','2016-01-05 06:00'), ('51','PRG','PEK','2016-01-11 13:00','2016-01-12 06:00'), ('52','PRG','PEK','2016-01-18 13:00','2016-01-19 06:00'), ('53','PRG','PEK','2016-01-25 13:00','2016-01-26 06:00'), ('54','PRG','PEK','2016-02-01 13:00','2016-02-02 06:00'), ('55','PRG','PEK','2016-02-08 13:00','2016-02-09 06:00'), ('56','PRG','PEK','2016-02-15 13:00','2016-02-16 06:00'), ('57','PRG','PEK','2016-02-22 13:00','2016-02-23 06:00'), ('58','PRG','PEK','2016-02-29 13:00','2016-03-01 06:00'), ('59','PRG','PEK','2016-03-07 13:00','2016-03-08 06:00'), ('60','PRG','PEK','2016-03-14 13:00','2016-03-15 06:00'), ('61','PRG','PEK','2016-03-21 13:00','2016-03-22 06:00'), ('62','GYD','PEK','2016-01-03 19:20','2016-01-04 06:20'), ('63','GYD','PEK','2016-01-10 19:20','2016-01-11 06:20'), ('64','GYD','PEK','2016-01-17 19:20','2016-01-18 06:20'), ('65','GYD','PEK','2016-01-24 19:20','2016-01-25 06:20'), ('66','GYD','PEK','2016-01-31 19:20','2016-02-01 06:20'), ('67','GYD','PEK','2016-02-07 19:20','2016-02-08 06:20'), ('68','GYD','PEK','2016-02-14 19:20','2016-02-15 06:20'), ('69','GYD','PEK','2016-02-21 19:20','2016-02-22 06:20'), ('70','GYD','PEK','2016-02-28 19:20','2016-02-29 06:20'), ('71','GYD','PEK','2016-03-06 19:20','2016-03-07 06:20'), ('72','GYD','PEK','2016-03-13 19:20','2016-03-14 06:20'), ('73','GYD','PEK','2016-03-20 19:20','2016-03-21 06:20'), ('74','GYD','PEK','2016-03-27 19:20','2016-03-28 06:20'), ('75','MUC','SVX','2016-01-16 10:40','2016-01-16 19:20'), ('76','MUC','SVX','2016-01-23 10:40','2016-01-23 19:20'), ('77','MUC','SVX','2016-01-30 10:40','2016-01-30 19:20'), ('78','MUC','SVX','2016-02-06 10:40','2016-02-06 19:20'), ('79','MUC','SVX','2016-02-13 10:40','2016-02-13 19:20'), ('80','MUC','SVX','2016-02-20 10:40','2016-02-20 19:20'), ('81','MUC','SVX','2016-02-27 10:40','2016-02-27 19:20'), ('82','MUC','SVX','2016-03-05 10:40','2016-03-05 19:20'), ('83','MUC','SVX','2016-03-12 10:40','2016-03-12 19:20'), ('84','MUC','SVX','2016-03-19 10:40','2016-03-19 19:20'), ('85','MUC','SVX','2016-03-26 10:40','2016-03-26 19:20'), ('86','PRG','SVX','2016-01-07 16:25','2016-01-08 00:40'), ('87','PRG','SVX','2016-01-14 16:25','2016-01-15 00:40'), ('88','PRG','SVX','2016-01-21 16:25','2016-01-22 00:40'), ('89','PRG','SVX','2016-01-28 16:25','2016-01-29 00:40'), ('90','PRG','SVX','2016-02-04 16:25','2016-02-05 00:40'), ('91','PRG','SVX','2016-02-11 16:25','2016-02-12 00:40'), ('92','PRG','SVX','2016-02-18 16:25','2016-02-19 00:40'), ('93','PRG','SVX','2016-02-25 16:25','2016-02-26 00:40'), ('94','PRG','SVX','2016-03-03 16:25','2016-03-04 00:40'), ('95','PRG','SVX','2016-03-10 16:25','2016-03-11 00:40'), ('96','PRG','SVX','2016-03-17 16:25','2016-03-18 00:40'), ('97','PRG','SVX','2016-03-24 16:25','2016-03-25 00:40'), ('98','PRG','SVX','2016-01-03 10:10','2016-01-03 18:15'), ('99','PRG','SVX','2016-01-10 10:10','2016-01-10 18:15'), ('100','PRG','SVX','2016-01-17 10:10','2016-01-17 18:15'), ('101','PRG','SVX','2016-01-24 10:10','2016-01-24 18:15'), ('102','PRG','SVX','2016-01-31 10:10','2016-01-31 18:15'), ('103','PRG','SVX','2016-02-07 10:10','2016-02-07 18:15'), ('104','PRG','SVX','2016-02-14 10:10','2016-02-14 18:15'), ('105','PRG','SVX','2016-02-21 10:10','2016-02-21 18:15'), ('106','PRG','SVX','2016-02-28 10:10','2016-02-28 18:15'), ('107','PRG','SVX','2016-03-06 10:10','2016-03-06 18:15'), ('108','PRG','SVX','2016-03-13 10:10','2016-03-13 18:15'), ('109','PRG','SVX','2016-03-20 10:10','2016-03-20 18:15'), ('110','PRG','SVX','2016-03-27 10:10','2016-03-27 18:15'), ('111','SVX','GYD','2016-01-07 17:00','2016-01-07 19:00'), ('112','SVX','GYD','2016-01-14 17:00','2016-01-14 19:00'), ('113','SVX','GYD','2016-01-21 17:00','2016-01-21 19:00'), ('114','SVX','GYD','2016-01-28 17:00','2016-01-28 19:00'), ('115','SVX','GYD','2016-02-04 17:00','2016-02-04 19:00'), ('116','SVX','GYD','2016-02-11 17:00','2016-02-11 19:00'), ('117','SVX','GYD','2016-02-18 17:00','2016-02-18 19:00'), ('118','SVX','GYD','2016-02-25 17:00','2016-02-25 19:00'), ('119','SVX','GYD','2016-03-03 17:00','2016-03-03 19:00'), ('120','SVX','GYD','2016-03-10 17:00','2016-03-10 19:00'), ('121','SVX','GYD','2016-03-17 17:00','2016-03-17 19:00'), ('122','SVX','GYD','2016-03-24 17:00','2016-03-24 19:00'), ('123','SVX','GYD','2016-01-02 17:00','2016-01-02 19:00'), ('124','SVX','GYD','2016-01-09 17:00','2016-01-09 19:00'), ('125','SVX','GYD','2016-01-16 17:00','2016-01-16 19:00'), ('126','SVX','GYD','2016-01-23 17:00','2016-01-23 19:00'), ('127','SVX','GYD','2016-01-30 17:00','2016-01-30 19:00'), ('128','SVX','GYD','2016-02-06 17:00','2016-02-06 19:00'), ('129','SVX','GYD','2016-02-13 17:00','2016-02-13 19:00'), ('130','SVX','GYD','2016-02-20 17:00','2016-02-20 19:00'), ('131','SVX','GYD','2016-02-27 17:00','2016-02-27 19:00'), ('132','SVX','GYD','2016-03-05 17:00','2016-03-05 19:00'), ('133','SVX','GYD','2016-03-12 17:00','2016-03-12 19:00'), ('134','SVX','GYD','2016-03-19 17:00','2016-03-19 19:00'), ('135','SVX','GYD','2016-03-26 17:00','2016-03-26 19:00'), ('136','SVX','DYU','2016-01-07 06:45','2016-01-07 09:55'), ('137','SVX','DYU','2016-01-14 06:45','2016-01-14 09:55'), ('138','SVX','DYU','2016-01-21 06:45','2016-01-21 09:55'), ('139','SVX','DYU','2016-01-28 06:45','2016-01-28 09:55'), ('140','SVX','DYU','2016-02-04 06:45','2016-02-04 09:55'), ('141','SVX','DYU','2016-02-11 06:45','2016-02-11 09:55'), ('142','SVX','DYU','2016-02-18 06:45','2016-02-18 09:55'), ('143','SVX','DYU','2016-02-25 06:45','2016-02-25 09:55'), ('144','SVX','DYU','2016-03-03 06:45','2016-03-03 09:55'), ('145','SVX','DYU','2016-03-10 06:45','2016-03-10 09:55'), ('146','SVX','DYU','2016-03-17 06:45','2016-03-17 09:55'), ('147','SVX','DYU','2016-03-24 06:45','2016-03-24 09:55'), ('148','SVX','DYU','2016-01-05 06:45','2016-01-05 09:55'), ('149','SVX','DYU','2016-01-12 06:45','2016-01-12 09:55'), ('150','SVX','DYU','2016-01-19 06:45','2016-01-19 09:55'), ('151','SVX','DYU','2016-01-26 06:45','2016-01-26 09:55'), ('152','SVX','DYU','2016-02-02 06:45','2016-02-02 09:55'), ('153','SVX','DYU','2016-02-09 06:45','2016-02-09 09:55'), ('154','SVX','DYU','2016-02-16 06:45','2016-02-16 09:55'), ('155','SVX','DYU','2016-02-23 06:45','2016-02-23 09:55'), ('156','SVX','DYU','2016-03-01 06:45','2016-03-01 09:55'), ('157','SVX','DYU','2016-03-08 06:45','2016-03-08 09:55'), ('158','SVX','DYU','2016-03-15 06:45','2016-03-15 09:55'), ('159','SVX','DYU','2016-03-22 06:45','2016-03-22 09:55'), ('160','SVX','DYU','2016-01-02 06:45','2016-01-02 09:55'), ('161','SVX','DYU','2016-01-09 06:45','2016-01-09 09:55'), ('162','SVX','DYU','2016-01-16 06:45','2016-01-16 09:55'), ('163','SVX','DYU','2016-01-23 06:45','2016-01-23 09:55'), ('164','SVX','DYU','2016-01-30 06:45','2016-01-30 09:55'), ('165','SVX','DYU','2016-02-06 06:45','2016-02-06 09:55'), ('166','SVX','DYU','2016-02-13 06:45','2016-02-13 09:55'), ('167','SVX','DYU','2016-02-20 06:45','2016-02-20 09:55'), ('168','SVX','DYU','2016-02-27 06:45','2016-02-27 09:55'), ('169','SVX','DYU','2016-03-05 06:45','2016-03-05 09:55'), ('170','SVX','DYU','2016-03-12 06:45','2016-03-12 09:55'), ('171','SVX','DYU','2016-03-19 06:45','2016-03-19 09:55'), ('172','SVX','DYU','2016-03-26 06:45','2016-03-26 09:55'), ('173','SVX','TAS','2016-01-04 07:40','2016-01-04 10:50'), ('174','SVX','TAS','2016-01-11 07:40','2016-01-11 10:50'), ('175','SVX','TAS','2016-01-18 07:40','2016-01-18 10:50'), ('176','SVX','TAS','2016-01-25 07:40','2016-01-25 10:50'), ('177','SVX','TAS','2016-02-01 07:40','2016-02-01 10:50'), ('178','SVX','TAS','2016-02-08 07:40','2016-02-08 10:50'), ('179','SVX','TAS','2016-02-15 07:40','2016-02-15 10:50'), ('180','SVX','TAS','2016-02-22 07:40','2016-02-22 10:50'), ('181','SVX','TAS','2016-02-29 07:40','2016-02-29 10:50'), ('182','SVX','TAS','2016-03-07 07:40','2016-03-07 10:50'), ('183','SVX','TAS','2016-03-14 07:40','2016-03-14 10:50'), ('184','SVX','TAS','2016-03-21 07:40','2016-03-21 10:50'), ('185','SVX','PEK','2016-01-07 19:45','2016-01-08 04:00'), ('186','SVX','PEK','2016-01-14 19:45','2016-01-15 04:00'), ('187','SVX','PEK','2016-01-21 19:45','2016-01-22 04:00'), ('188','SVX','PEK','2016-01-28 19:45','2016-01-29 04:00'), ('189','SVX','PEK','2016-02-04 19:45','2016-02-05 04:00'), ('190','SVX','PEK','2016-02-11 19:45','2016-02-12 04:00'), ('191','SVX','PEK','2016-02-18 19:45','2016-02-19 04:00'), ('192','SVX','PEK','2016-02-25 19:45','2016-02-26 04:00'), ('193','SVX','PEK','2016-03-03 19:45','2016-03-04 04:00'), ('194','SVX','PEK','2016-03-10 19:45','2016-03-11 04:00'), ('195','SVX','PEK','2016-03-17 19:45','2016-03-18 04:00'), ('196','SVX','PEK','2016-03-24 19:45','2016-03-25 04:00'), ('197','SVX','PEK','2016-01-05 19:45','2016-01-06 04:00'), ('198','SVX','PEK','2016-01-12 19:45','2016-01-13 04:00'), ('199','SVX','PEK','2016-01-19 19:45','2016-01-20 04:00'), ('200','SVX','PEK','2016-01-26 19:45','2016-01-27 04:00'), ('201','SVX','PEK','2016-02-02 19:45','2016-02-03 04:00'), ('202','SVX','PEK','2016-02-09 19:45','2016-02-10 04:00'), ('203','SVX','PEK','2016-02-16 19:45','2016-02-17 04:00'), ('204','SVX','PEK','2016-02-23 19:45','2016-02-24 04:00'), ('205','SVX','PEK','2016-03-01 19:45','2016-03-02 04:00'), ('206','SVX','PEK','2016-03-08 19:45','2016-03-09 04:00'), ('207','SVX','PEK','2016-03-15 19:45','2016-03-16 04:00'), ('208','SVX','PEK','2016-03-22 19:45','2016-03-23 04:00'), ('209','SVX','PEK','2016-01-08 19:45','2016-01-09 04:00'), ('210','SVX','PEK','2016-01-15 19:45','2016-01-16 04:00'), ('211','SVX','PEK','2016-01-22 19:45','2016-01-23 04:00'), ('212','SVX','PEK','2016-01-29 19:45','2016-01-30 04:00'), ('213','SVX','PEK','2016-02-05 19:45','2016-02-06 04:00'), ('214','SVX','PEK','2016-02-12 19:45','2016-02-13 04:00'), ('215','SVX','PEK','2016-02-19 19:45','2016-02-20 04:00'), ('216','SVX','PEK','2016-02-26 19:45','2016-02-27 04:00'), ('217','SVX','PEK','2016-03-04 19:45','2016-03-05 04:00'), ('218','SVX','PEK','2016-03-11 19:45','2016-03-12 04:00'), ('219','SVX','PEK','2016-03-18 19:45','2016-03-19 04:00'), ('220','SVX','PEK','2016-03-25 19:45','2016-03-26 04:00'), ('221','SVX','PEK','2016-01-03 19:45','2016-01-04 04:00'), ('222','SVX','PEK','2016-01-10 19:45','2016-01-11 04:00'), ('223','SVX','PEK','2016-01-17 19:45','2016-01-18 04:00'), ('224','SVX','PEK','2016-01-24 19:45','2016-01-25 04:00'), ('225','SVX','PEK','2016-01-31 19:45','2016-02-01 04:00'), ('226','SVX','PEK','2016-02-07 19:45','2016-02-08 04:00'), ('227','SVX','PEK','2016-02-14 19:45','2016-02-15 04:00'), ('228','SVX','PEK','2016-02-21 19:45','2016-02-22 04:00'), ('229','SVX','PEK','2016-02-28 19:45','2016-02-29 04:00'), ('230','SVX','PEK','2016-03-06 19:45','2016-03-07 04:00'), ('231','SVX','PEK','2016-03-13 19:45','2016-03-14 04:00'), ('232','SVX','PEK','2016-03-20 19:45','2016-03-21 04:00'), ('233','SVX','PEK','2016-03-27 19:45','2016-03-28 04:00')

Ответ

Ваш запрос уже может выбирать любые вложенности рекурсии. Ваши исходные данные для тестов не содержат подходящих маршрутов, что бы запрос мог выдать больше стыковок. При добавлении записи insert into flights VALUES(234,'DYU','PRG','2016-02-18 09:00','2016-02-18 15:30') ваш запрос сразу начинает находить еще кучу вариантов, к сожалению очень многие с повторным пролетом через Кольцово. Так что запрос надо ограничивать, не позволяя выбирать маршруты в которых один и тот же АП встречается более одного раза. Примерно так:
WITH RECURSIVE segs AS ( SELECT f0.id::text as flights ,'/'||origin_apt||'/'||destination_apt||'/' as route -- <-- Добавил полный маршрут , origin_apt, destination_apt , departure_time AS departure , arrival_time AS arrival , 1 as hops , (arrival_time - departure_time)::interval AS total_time , '00:00'::interval as waiting_time FROM flights f0 WHERE origin_apt = 'SVX' -- AND departure_time >= '2016-01-19' UNION ALL SELECT s.flights || '-->' || f1.id::text as flights ,s.route||f1.destination_apt||'/' -- <-- добавляем АП посадки в маршрут , s.origin_apt, f1.destination_apt , s.departure AS departure , f1.arrival_time AS arrival , s.hops + 1 AS hops , s.total_time + (f1.arrival_time - f1.departure_time)::interval AS total_time , s.waiting_time + (f1.departure_time - s.arrival)::interval AS waiting_time FROM segs s JOIN flights f1 ON f1.origin_apt = s.destination_apt AND f1.departure_time >= s.arrival + '8 hour' -- AND NOT s.route like '%/'||f1.destination_apt||'/%' -- <-- АП назначения не в полном маршруте AND s.hops < 5 ) SELECT * FROM segs WHERE destination_apt = 'PEK' -- AND waiting_time < '25 day'-- ORDER BY departure, waiting_time asc;