SQL Server查询以查找具有转移的从城市A到城市B的所有路线 [英] SQL Server query to find all routes from city A to city B with transfers

问题描述

在采访开发人员职位时，我被问到了这个问题。

I was asked this question while interviewing for developer position.

任务：在SQL Server表中存储了飞行路线，该查询将查找一到两次无转移的从城市A到城市B的所有路线。例如，您有路线：

Task: Having flight routes stored in SQL Server table write query which will find all routes from city A to city B without transfer, with one or two transfers. For instance you have routes:

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

您需要查找从洛杉矶到伦敦的所有中转航线。结果应该是这样的

And you need to find all routes with transfers from Los Angeles to London. The result should be like this

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或更多次转移的路线，我们需要添加具有更复杂选择的新联合。

Works but looks not very good and if we need to find routes with 3, 4, 5 or more transfers we need to add new unions with more complex selects.

在这个特定示例中，这很好，因为人们通常对转乘次数超过2次的航班不感兴趣。但总的来说，我认为此查询看起来会更好。也许有人可以通过更一般的查询来解决此任务。谢谢。

For this particular example it’s good because the people as a rule are not interested in flights with more than 2 transfers. But in general I think this query can look better. Perhaps someone can solve this task with more general query. Thanks.

推荐答案

对，您为所有RDB提供了有效的常规SQL解决方案。我在这里看到您有一个提示-SQL Server。它支持可用于解决此任务的递归CTE。

Right, you provided working general SQL solution for all RDBs. I see you had here one hint – SQL Server. It supports recursive CTE which can be used to solve this task.

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

So, here you have general solution for SQL Server and you can filter them by transfers count.

这篇关于SQL Server查询以查找具有转移的从城市A到城市B的所有路线的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！