Запрос SQL Server для поиска всех маршрутов из города A в город B с трансферами

Мне задавали этот вопрос во время интервью для позиции разработчика.

Задача: наличие маршрутов рейса, хранящихся в таблице SQL Server, написание запроса, в котором все маршруты из города A в город B без переноса, с одной или двумя передачами. Например, у вас есть маршруты:

| From         | To
----------------------
Los Angeles     London   
Los Angeles     New York
New York        London
Los Angeles     Seattle
Seattle         Paris
Paris           London

И вам нужно найти все маршруты с пересадками из Лос-Анджелеса в Лондон. Результат должен быть таким:

Route
------------------------
Los Angeles->London
Los Angeles->New York->London
Los Angeles->Seattle->Paris->London

Мое решение было этим

select [From] + '->' + [To] as [Route] from Routes where [From] = 'Los Angeles' and [To] = 'London'
union 
select r1.[From] + '->' + r1.[To] + '->' + r2.[To] as [Route] from Routes as r1 
join Routes as r2 on r1.[To] = r2.[From]
where r1.[From] = 'Los Angeles' and r2.[To] = 'London'
union 
select r1.[From] + '->' + r1.[To] + '->' + r2.[To] + '->' + r3.[To] as [Route] from Routes as r1 
join Routes as r2 on r1.[To] = r2.[From]
join Routes as r3 on r2.[To] = r3.[From]
where r1.[From] = 'Los Angeles' and r3.[To] = 'London'

Работает, но выглядит не очень хорошо, и если нам нужно найти маршруты с 3, 4, 5 или более передачами, нам нужно добавить новые союзы с более сложными выборами.

В этом конкретном примере это хорошо, потому что люди, как правило, не интересуются полетами с более чем 2 передачами. Но в целом я думаю, что этот запрос может выглядеть лучше. Возможно, кто-то может решить эту задачу с более общим запросом. Спасибо.

Ответ 1

Правильно, вы предоставили рабочее общее SQL-решение для всех RDB. Я вижу, что у вас был один намек - SQL Server. Он поддерживает рекурсивный CTE, который может быть использован для решения этой задачи.

with RoutesCTE as
(
    select CAST([From] + '->' + [To] as nvarchar(max)) as [Route]
          ,0 as TransfersCount
          ,[From]
          ,[To]
    from Routes

    union all

    select r.[Route] + '->' + r1.[To]
          ,TransfersCount + 1
          ,r.[From]
          ,r1.[To]
    from RoutesCTE r
        join Routes r1
            on r.[To] = r1.[From]
                and r1.[To] <> r.[From] 
                  and PATINDEX('%'+r1.[To]+'%', r.[Route]) = 0
)
select [Route]
from RoutesCTE 
where [From] = 'Los Angeles'
    and [To] = 'London'
    and TransfersCount <= 2

Итак, здесь у вас есть общее решение для SQL Server, и вы можете фильтровать их по количеству переводов.

Ответ 2

Лично... Я бы пошел с CTE в этом примере, но это также можно сделать с помощью динамического SQL, поскольку вы не знаете, сколько остановит какой-то человек, желающий пойти, сделать функцию и динамический SQL потяните его за вас и сделайте столько, сколько потребуется, теперь может быть больше форматирования и добавления этих стрелок и прочее... но похоже, что это работает так.

И вы можете выполнить @sql во временную таблицу и иметь другое условие для остановки London

if object_id('tempdb..#Test') is not null drop table #Test
create table #Test ([From] nvarchar(20), [To] nvarchar(20))

insert into #Test ([From], [To])
values 
('Log Angeles', 'London'),
('Log Angeles', 'New York'),
('New York', 'London'),
('Log Angeles', 'Seattle'),
('Seattle', 'Paris'),
('Paris', 'London')

declare @StopsCount int = 2
declare @beginingStop int = 2

declare @sqlHeader nvarchar(max) = 'select t' + cast(@StopsCount as nvarchar) + 
                               '.[From], t' + + cast(@StopsCount as nvarchar) + 
                               '.[To] '

declare @sqlQuery nvarchar(max) = 'from #Test t' + cast(@StopsCount as nvarchar)
while @StopsCount > 0
BEGIN

    set @StopsCount = @StopsCount - 1

    set @sqlQuery = @sqlQuery + ' left join #Test t' + cast(@StopsCount as nvarchar) +
                  ' on t' + cast(convert(int, (@StopsCount + 1)) as nvarchar) + '.[To]' +
                  ' = t' + cast(@StopsCount as nvarchar) + '.[From]'                      
    set @sqlHeader = @sqlHeader + ', t' + cast(@StopsCount as nvarchar) + '.[To]'
END

set @sqlQuery = @sqlHeader + @sqlQuery + ' where t' 
+ cast(@beginingStop as nvarchar) + '.[From] = ''Log Angeles'''

execute (@sqlQuery)

Ответ 3

Спасибо за хороший вопрос.

Этот ответ не для определенных RDBMS OP (not SQL Server), но я пишу специально для Oracle, с которым я знаком.

В запросе используется Иерархический запрос вместо рекурсивного CTE с LEVEL <= 3 равным TransfersCount <= 2 в SQL Server

WITH routes AS
(
    SELECT 'Los Angeles' from_place, 'London' to_place FROM DUAL UNION ALL
    SELECT 'Los Angeles', 'New York' FROM DUAL UNION ALL
    SELECT 'New York', 'London' FROM DUAL UNION ALL
    SELECT 'Los Angeles', 'Seattle' FROM DUAL UNION ALL
    SELECT 'Seattle', 'Paris' FROM DUAL UNION ALL
    SELECT 'Seattle', 'Los Angeles' FROM DUAL UNION ALL
    SELECT 'Paris', 'London' FROM DUAL 
)
SELECT SUBSTR(SYS_CONNECT_BY_PATH(from_place , '->'), 3) || '->' || to_place AS path
FROM routes
WHERE to_place = 'London'
START WITH from_place = 'Los Angeles'
CONNECT BY NOCYCLE  PRIOR to_place = from_place 
    AND to_place <> 'Los Angeles' 
    AND LEVEL <= 3 ;