SQL Server查詢找到從城市A到城市B的所有轉接

Question

我在面試開發人員職位時被問到這個問題。

任務：將航班路線存儲在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次轉機的航班不感興趣。但總的來說，我認爲這個查詢可能會更好看。也許有人可以用更一般的查詢來解決這個任務。謝謝。

Answer 1

對，您爲所有RDB提供了一般工作的SQL解決方案。我看到你在這裏有一個提示 - 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的通用解決方案，您可以通過轉移過濾指望他們。

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

Answer 3

感謝您的好問題。

此答案不適用於OP的特定RDBMS（not SQL Server），但我爲我熟悉的Oracle編寫了特定的答案。

查詢的SQL Server使用層次查詢，而不是遞歸CTE的，與LEVEL <= 3等於TransfersCount <= 2

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 ;