用于检索连接列车的SQL查询

Question

我有一个数据库，其中包含很多不同列车的列车时间。它看起来是这样的：

表1

Station_id站的班次 等

表2

工作站名称到达离开TrainNumber 等

我知道如何找回出发的时间定火车，但如果我想要检索包含几个基于用户选择的出发站的连接列车的旅行计划，我将如何进行到达站？如果有人想从伦敦到曼彻斯特，但没有直达列车旅行这条路线，所以他将不得不改变列车我利物浦。我将如何查询数据库以获得此结果？

我希望有人能帮助我，因为我无法找到解决方案。

Answer 1

确实，给出完全未知数据的问题的最佳解决方案超越了SQL的功能。也就是说，从理论上讲，最快的路线可能是搭乘数千列车变更，而且可能的组合总数远远超出了任何计算机处理的能力。但是在实践中，我认为可以肯定地说，一次列车变化较少的行程几乎总是比一次行程更多的行程更快，而且旅行者可能会选择较少的列车更换，因为总体行程略短一些避免了更换火车的麻烦以及由于延误而错过火车的危险。我不知道你的铁路系统是什么样的（甚至你来自哪里），但我猜测大多数旅程可以通过少量的列车更改完成，大概很少超过2个，对吗？

因此，大卫奥尼尔的解决方案基本上是正确的，但我认为他给出的查询有点困惑。他没有指定出发站，他似乎认为整个旅程中列车编号都保持不变，也许最重要的是，他将时间计算为旅行时间的总和。对旅客来说，重要的是离开和到达之间的总时间，而不仅仅是在火车上的时间。在火车上十分钟，在等待下一列火车的车站四小时，在第二列火车上另外十分钟，是四小时二十分钟，而不是二十分钟。哦，他似乎不能确保连接列车在第一列火车到达之前不会离开。如果另一列火车在你到达那里前十分钟离开，那么这个连接就没有什么用处了。

所以，我认为真正的查询会更喜欢这样的：

哦，你对什么样的表中描述似乎incompletet，所以原谅我，如果我只是创造我自己的表你就必须有数据去做这个。也就是说，你最好有：

Trip (train_number, departure_station_id, arrival_station_id, departure_time, arrival_time) 

Station (station_id, station_name) 

首先查询：寻找一个直接行程：

select t1.train_number, t1.arrival_time-t1.departure_time as time 
from trip t1 
where t1.departure_station_id=?station_from 
and t1.arrival_station_id=?station_to 
order by time 

如果变成了什么，有一列火车的变化再试一次：

select t1.train_number, t2.train_number, t2.arrival_time-t1.departure_time as time 
from trip t1 
join trip t2 on (t2.departure_station_id=t1.arrival_station_id 
and t2.departure_time>t1.arrival_time) 
where t1.departure_station_id=?station_from 
and t2.arrival_station_id=?station_to 
order by time 

如果仍然没有，请尝试两次列车更换：

select t1.train_number, t2.train_number, t3.train_number, t3.arrival_time-t1.departure_time as time 
from trip t1 
join trip t2 on (t2.departure_station_id=t1.arrival_station_id 
and t2.departure_time>t1.arrival_time) 
join trip t3 on (t3.departure_station_id=t2.arrival_station_id 
and t3.departure_time>t2.arrival_time) 
where t1.departure_station_id=?station_from 
and t3.arrival_station_id=?station_to 
order by time 

等

您可以将所有这些与UNION组合成一个查询，在较短的查询中填充额外列车号的空值。这样做的好处是，如果带有额外的列车改变的旅行真的很短，你会找到一个。但我怀疑这种情况很少发生。为了使工会能够发挥作用，每次查询都必须达到最大数量的更改 - 无论您准备如何允许 - 并且性能可能会很差。

我还没有尝试过这个，但我猜测，如果使用适当的索引，无变化的查询会闪电般快，一个变化会非常快，两个变化会开始变慢，超出这可能会是一个非常长的查询，因为可能的组合数量很大。请注意，这样一个简单的查询将包含荒谬的itineries。就像你想从伦敦去巴黎？我们可以试试伦敦到莫斯科，罗马到巴黎。或伦敦到格拉斯哥回到伦敦再到巴黎。当然这些会有很长的时间，而ORDER BY会将它们排序到底，但是它们会显示出可能必须消除的路线。你可以添加标准来消除自己回来的路线，但其他荒谬的旅行很难识别。

玩得开心！

Answer 2

我对表2中的信息有些不确定。就目前而言，我假设表2中同时包含出发时间和目的地站（dest_station_name）

select t1.station_name, t2.station_name, t3.station_name, 
    t4.station_name, t5.station_name, 
    sum(t2.arrival - t1.departure + /*the rest of them */) as total_time from table2 t1 
join table2 t2 on t1.dest_station_name = t2.station_name 
    and t1.train_number = t2.train_number 
join table2 t3 on t2.dest_station_name = t3.station_name 
    and t2.train_number = t3.train_number 
join table2 t4 on t3.dest_station_name = t4.station_name 
    and t3.train_number = t4.train_number 
join table2 t5 on t4.dest_station_name = t5.station_name 
    and t4.train_number = t5.train_number 
where t5.station_name = :goal_station 
order by total_time desc; 

既然你不知道提前多少跳你要带你”你可能想写一系列这些，每个都有不同数量的火车跳。运行1跳并查找没有返回的数据。它没有返回，运行2跳查询。如果没有返回，请运行3跳查询，等等。

编辑格式

注：正如其他的答案和评论指出：这不能用于保证最短路径。这可以用来找到跳数最少的路径。例如，我写的技巧会建议从纽约到华盛顿特区，从纽约到洛杉矶再到华盛顿，即使纽约到特伦顿新泽西州到兰彻斯特PA到华盛顿特区都可以。

Answer 3

这不能简化为简单的SQL查询。或者一个复杂的问题:)

你想解决Shortest Path Problem。

您将需要建立一个使用您的站点作为顶点的图形，以及代表从一个站到另一个站的可能旅程的顶点之间的路径（请注意，您将有许多从一个节点到另一个节点的路径，以出发时间为键）。每条路径的重量是其（旅程）持续时间。

然后，您可以使用维基百科链接建议的算法之一解决最短路径问题，同时要记住，您必须增加在站N等待的成本，直到列车到站N + 1的出发时间。

听起来像一个有趣的黑客！

Answer 4

我怀疑你偶然发现了一个可能没有任何实际答案的特殊难题。这可能无法用一个甚至几个查询。假设用户选择站A到站B作为旅程。

1. 查找所有以A开始并以B结尾的列车。如果找到任何列车，您可以停车。
2. 如果没有找到所有从A开始的列车。
3. 对于每个S1，S2，...，Sn的车站，列车始于A结束时查询列车，起始列车从Sx到B.如果您发现一列火车然后停下来。但是，如果不是，你必须重复。在这一点上，你必须小心，你最终不会陷入循环。这就是你找到的列车 - E，那么E - ˚F则F - A.

您可能需要使用递归函数像这样（注意，这是不完全经过深思熟虑）：

journey(A, B) 
     if A = B then return empty journey else 
     query for trains that go from A to B, if found return the one step journey 
     else 
      query for all trains that start at A 
      for each endpoint of trains that start at A => E 
       rest = journey(E, B) 
      return A-E+rest 

Answer 5

我不认为你真的需要一个最短路径解决方案。

通常网站知道最多两个城市间的火车路线。反正通常没有更多。 如果用户想要使用其他路线，那么你有一个“旅行通过”字段。

所以你只需将路线连接成一条。

Answer 6

我想要解决这个问题的方法，你需要实现某种搜索算法 - 它不会用简单的查询来解决。您应该在结构中加载您的列车时间，然后查找从A到B的所有可能连接。

当在给定参数中找到所有可能的路线（可以说您知道计划行程的日期）时，应该对它们进行排序通过几个标准 - 如最短的旅程，最快的旅程，最便宜的旅程 - 如果您存储机票费用信息，最少的火车开关数量等等，然后显示最有利的结果。

听起来像一个有趣的项目工作了一段时间。你可能会给我一个关于周末新爱好项目的想法;）