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 的通用解决方案，您可以按传输计数过滤它们。