实战 SQL：实现百度、高德等地图中的地铁换乘线路查询

不剪发的Tony老师 2023-03-28 原文

对于大多数人来说，SQL 意味着 SELECT、INSERT、UPDATE 和 DELETE。但实际上，SQL 能够实现的功能远远不止简单的增删改查。今天我们来介绍一个高级功能：通用表表达式（Common Table Expression）。CTE 可以提高复杂查询的性能和可读性，实现树状结构或者图数据的遍历。例如：

生成数字序列；
获取员工上下级的组织关系；
查询地铁、航班换乘线路；
社交网络图谱分析。

一般来说，我们只能通过应用程序或者存储过程实现这些复杂的功能，而且性能不高。但是有了 CTE，我们可以直接利用一个 SQL 语句完成以上功能。CTE 不仅强大而且通用，各种主流数据库都提供了支持。

通用表表达式	MySQL	Oracle	SQL Server	PostgreSQL	SQLite
简单 CTE	✔️	✔️	✔️	✔️	✔️
递归 CTE	✔️	✔️	✔️	✔️	✔️

我们通过几个实用案例，了解一下 CTE 的语法，同时介绍各种数据库中的实现差异。

简单 CTE

通用表表达式使用WITH关键字表示：

WITH t(n) AS (
  SELECT 4 --  -- Oracle
)
SELECT * FROM t;
n|
-|
4|

以上 WITH 子句相当于定义了一个语句级别的临时表 t(n)，在随后的 SELECT、INSERT、UPDATE 以及 DELETE 语句中都可以使用。如果是 Oracle，可以使用SELECT 2 FROM dual。

?WITH 子句定义了一个表达式，表达式的值是一个表，所以称为通用表表达式。CTE 和子查询类似，可以用于 SELECT、INSERT、UPDATE 以及 DELETE 语句。Oracle 中称之为子查询因子（subquery factoring）。

CTE 与子查询类似，只在当前语句中有效；不过一个语句中可以定义多个 CTE，而且 CTE 被定义之后可以多次引用：

WITH t1(n) AS (
  SELECT 4 -- FROM dual
),
t2(n) AS (
  SELECT n+1 FROM t1
)
SELECT t1.n, t2.n
  FROM t1 
 CROSS JOIN t2;
n|n|
-|-|
4|5|

第一个 CTE 名为 t1；第二个 CTE 名为 t2，引用了前面定义的 t1 ；每个 CTE 之间使用逗号进行分隔；最后的 SELECT 语句使用前面定义的 2 个 CTE 进行连接查询。这种使用 CTE 的方法和编程语言中的变量非常类似。

CTE 和视图、临时表或者子查询都有点类似，但是比它们的结构更加清晰；数据库对于 CTE 只需要执行一次，性能也会更好。不过，CTE 真正强大之处是允许在定义中调用自己，也就是递归调用。

生成数字序列

WITH子句还有一种递归形式，以下语句可以生成一个 1 到 10 的数字序列：

WITH RECURSIVE t(n) AS
(
  SELECT 1 -- 初始化
   UNION ALL
  SELECT n + 1 FROM t WHERE n < 10 -- 递归结束条件
)
SELECT n FROM t;
n |
--|
 1|
 2|
 3|
 4|
 5|
 6|
 7|
 8|
 9|
10|

其中，RECURSIVE表示递归，Oracle 和 SQL Server 中不需要该关键字。

递归 CTE 包含两部分，UNION ALL 上面的查询语句用于生成初始化数据；下面的查询语句用于递归，引用了它自身（ t ）。

运行初始化语句，生成数字 1；
第 1 次运行递归部分，此时 n 等于 1，返回数字 2（ n+1 ）；
第 2 次运行递归部分，此时 n 等于 2，返回数字 3（ n+1 ）；
第 9 次运行递归部分，此时 n 等于 9，返回数字 10（ n+1 ）；
第 10 次运行递归部分，此时 n 等于 10；由于查询不满足条件（ WHERE n < 10 ），不返回任何结果，并且递归结束；最后的查询语句返回 t 中的全部数据，也就是一个 1 到 10 的数字序列。

只要是具有一定规律的数字序列都可以通过递归 CTE 生成，例如斐波那契数列。

遍历组织结构图

在公司的组织结构中，存在上下级的管理关系，如下图所示。

示例表和数据点此下载。如果我们想要知道某个员工从上至下的各级领导，可以使用递归 CTE 实现：

WITH RECURSIVE employee_path (emp_id, emp_name, path) AS
(
  SELECT emp_id, emp_name, CAST(emp_name AS CHAR(1000)) AS path
    FROM employee
   WHERE manager IS NULL
   UNION ALL
  SELECT e.emp_id, e.emp_name, CAST(CONCAT(ep.path, '->', e.emp_name) AS CHAR(1000))
    FROM employee_path ep
    JOIN employee e ON ep.emp_id = e.manager
)
SELECT * FROM employee_path WHERE emp_name = '黄忠';
emp_id|emp_name|path             |
------|--------|-----------------|
     5|黄忠    |刘备->诸葛亮->黄忠|

上面是 MySQL 中的语法。在 Oracle 以及 SQL Server 中需要将 CHAR(1000) 改为 VARCHAR(1000)，同时省略 RECURSIVE 关键字；在 PostgreSQL 中需要将 CAST 函数里的 CHAR(1000) 改为 VARCHAR(1000)；SQLite 没有提供 CONCAT 函数，使用连接操作符（||）即可。

其中，初始化查询用于查找没有 manager 的员工，也就是最上级的领导；递归查询通过将员工的 manager 和上级员工的 emp_id 进行关联，获取上下级管理关系；递归结束的条件就是没有找到任何数据。当然，我们也可以从下级往上级进行遍历。

其他具有这种层级关系的数据包括多层菜单、博客文章中的评论等。

查找地铁换乘线路

地铁、公交、航班等，包括社交网站上的关注，都是一种有向图数据结构。我们通常需要查找某一站点到另一站点的最短路径，利用递归 CTE 可以实现这类需求。示例数据中目前只有地铁 1 号线和 2 号线的数据，但是足够我们进行演示。

以下语句用于查找“王府井”到“积水潭”的换乘路线，使用 PostgreSQL 数据库实现：

WITH RECURSIVE paths (start_station, stop_station, stops, path) AS (
  SELECT station_name, next_station, 1, ARRAY[station_name::text, next_station::text]
    FROM bj_subway WHERE station_name = '王府井'
   UNION ALL
  SELECT p.start_station, e.next_station, stops + 1, p.path || ARRAY[e.next_station::text]
    FROM paths p
    JOIN bj_subway e
      ON p.stop_station = e.station_name AND NOT e.next_station = ANY(p.path)
)
SELECT * FROM paths WHERE stop_station ='积水潭';
start_station|stop_station|stops|path                                                                           |
-------------|------------|-----|-------------------------------------------------------------------------------|
王府井          |积水潭         |    8|{王府井,天安门东,天安门西,西单,复兴门,阜成门,车公庄,西直门,积水潭}                                         |
王府井          |积水潭         |    9|{王府井,东单,建国门,朝阳门,东四十条,东直门,雍和宫,安定门,鼓楼大街,积水潭}                                     |
王府井          |积水潭         |   13|{王府井,东单,建国门,北京站,崇文门,前门,和平门,宣武门,长椿街,复兴门,阜成门,车公庄,西直门,积水潭}                        |
王府井          |积水潭         |   18|{王府井,天安门东,天安门西,西单,复兴门,长椿街,宣武门,和平门,前门,崇文门,北京站,建国门,朝阳门,东四十条,东直门,雍和宫,安定门,鼓楼大街,积水潭}|

查询结果显示有 4 条路线，如果选择最短路线就是第一条。其中的 path 字段是个数组，用于存储走过的站点；最后的 NOT e.next_station = ANY(p.path) 条件用于避免反复经过同一个站点，因为地铁线路是一个双向图。

我们还可以进一步计算换乘次数，实现最少换乘路线；如果在表中增加一些字段，记录每两个站点之间的时间和换乘时间，还可以计算最快捷路线。

其他数据库没有提供数组类型，但是可以使用其他方法实现，以下是 MySQL 中的实现：

WITH RECURSIVE paths (start_station, stop_station, stops, path) AS (
  SELECT station_name, next_station, 1, CAST(CONCAT(station_name , ',', next_station) AS CHAR(1000))
    FROM bj_subway WHERE station_name = '王府井'
   UNION ALL
  SELECT p.start_station, e.next_station, stops + 1, CONCAT_WS(',', p.path, e.next_station)
    FROM paths p
    JOIN bj_subway e
      ON p.stop_station = e.station_name AND (INSTR(p.path, e.next_station) = 0)
)
SELECT * FROM paths WHERE stop_station ='积水潭';

我们使用了逗号分隔符的字符串模拟数组的效果，这种方法也适用于其他数据库。你用哪种数据库，有没有提供这种功能？

定期更新数据库领域相关文章，欢迎关注❤️、点赞?、转发?！

高德图中积水潭 station SELECT sql 数据库 oracle mysql 递归查询MySQL

有关实战 SQL：实现百度、高德等地图中的地铁换乘线路查询的更多相关文章

ruby - ECONNRESET (Whois::ConnectionError) - 尝试在 Ruby 中查询 Whois 时出错 - 2
我正在用Ruby编写一个简单的程序来检查域列表是否被占用。基本上它循环遍历列表，并使用以下函数进行检查。require'rubygems'require'whois'defcheck_domain(domain)c=Whois::Client.newc.query("google.com").available?end程序不断出错(即使我在google.com中进行硬编码)，并打印以下消息。鉴于该程序非常简单，我已经没有什么想法了-有什么建议吗？/Library/Ruby/Gems/1.8/gems/whois-2.0.2/lib/whois/server/adapters/base.
ruby - 如何根据特征实现 FactoryGirl 的条件行为 - 2
我有一个用户工厂。我希望默认情况下确认用户。但是鉴于unconfirmed特征，我不希望它们被确认。虽然我有一个基于实现细节而不是抽象的工作实现，但我想知道如何正确地做到这一点。factory:userdoafter(:create)do|user,evaluator|#unwantedimplementationdetailshereunlessFactoryGirl.factories[:user].defined_traits.map(&:name).include?(:unconfirmed)user.confirm!endendtrait:unconfirmeddoenden
ruby-on-rails - 在 Rails 和 ActiveRecord 中查询时忽略某些字段 - 2
我知道我可以指定某些字段来使用pluck查询数据库。ids=Item.where('due_at但是我想知道，是否有一种方法可以指定我想避免从数据库查询的某些字段。某种反拔？posts=Post.where(published:true).do_not_lookup(:enormous_field) 最佳答案 Model#attribute_names应该返回列/属性数组。您可以排除其中一些并传递给pluck或select方法。像这样:posts=Post.where(published:true).select(Post.attr
华为OD机试用Python实现 -【明明的随机数】 2023Q1A - 2
华为OD机试题本篇题目：明明的随机数题目输入描述输出描述：示例1输入输出说明代码编写思路最近更新的博客华为od2023|什么是华为od，od薪资待遇，od机试题清单华为OD机试真题大全，用Python解华为机试题|机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为o
基于C#实现简易绘图工具【100010177】 - 2
C#实现简易绘图工具一.引言实验目的:通过制作窗体应用程序(C#画图软件),熟悉基本的窗体设计过程以及控件设计,事件处理等,熟悉使用C#的winform窗体进行绘图的基本步骤,对于面向对象编程有更加深刻的体会.Tutorial任务设计一个具有基本功能的画图软件**·包括简单的新建文件,保存,重新绘图等功能**·实现一些基本图形的绘制,包括铅笔和基本形状等,学习橡皮工具的创建**·设计一个合理舒适的UI界面**注明:你可能需要先了解一些关于winform窗体应用程序绘图的基本知识,以及关于GDI+类和结构的知识二.实验环境Windows系统下的visualstudio2017C#窗体应用程序三.
MIMO-OFDM无线通信技术及MATLAB实现（1）无线信道：传播和衰落 - 2
MIMO技术的优缺点优点通过下面三个增益来总体概括：阵列增益。阵列增益是指由于接收机通过对接收信号的相干合并而活得的平均SNR的提高。在发射机不知道信道信息的情况下，MIMO系统可以获得的阵列增益与接收天线数成正比复用增益。在采用空间复用方案的MIMO系统中，可以获得复用增益，即信道容量成倍增加。信道容量的增加与min(Nt,Nr)成正比分集增益。在采用空间分集方案的MIMO系统中，可以获得分集增益，即可靠性性能的改善。分集增益用独立衰落支路数来描述，即分集指数。在使用了空时编码的MIMO系统中，由于接收天线或发射天线之间的间距较远，可认为它们各自的大尺度衰落是相互独立的，因此分布式MIMO
微信小程序开发入门与实战（Behaviors使用） - 2
@作者:SYFStrive @博客首页:HomePage📜：微信小程序📌：个人社区（欢迎大佬们加入）👉：社区链接🔗📌：觉得文章不错可以点点关注👉：专栏连接🔗💃：感谢支持,学累了可以先看小段由小胖给大家带来的街舞👉微信小程序（🔥）目录自定义组件-behaviors 1、什么是behaviors 2、behaviors的工作方式 3、创建behavior 4、导入并使用behavior 5、behavior中所有可用的节点 6、同名字段的覆盖和组合规则总结最后自定义组件-behaviors 1、什么是behaviorsbehaviors是小程序中，用于实现
【Java入门】使用Java实现文件夹的遍历 - 2
遍历文件夹我们通常是使用递归进行操作，这种方式比较简单，也比较容易理解。本文为大家介绍另一种不使用递归的方式，由于没有使用递归，只用到了循环和集合，所以效率更高一些！一、使用递归遍历文件夹整体思路1、使用File封装初始目录，2、打印这个目录3、获取这个目录下所有的子文件和子目录的数组。4、遍历这个数组，取出每个File对象4-1、如果File是否是一个文件，打印4-2、否则就是一个目录，递归调用代码实现publicclassSearchFile{publicstaticvoidmain(String[]args){//初始目录Filedir=newFile("d:/Dev");Datebeg
Hive SQL 五大经典面试题 - 2
目录第1题连续问题分析：解法：第2题分组问题分析：解法：第3题间隔连续问题分析：解法：第4题打折日期交叉问题分析：解法：第5题同时在线问题分析：解法：第1题连续问题如下数据为蚂蚁森林中用户领取的减少碳排放量iddtlowcarbon10012021-12-1212310022021-12-124510012021-12-134310012021-12-134510012021-12-132310022021-12-144510012021-12-1423010022021-12-154510012021-12-1523.......找出连续3天及以上减少碳排放量在100以上的用户分析：遇到这类
sql - 查询忽略时间戳日期的时间范围 - 2
我正在尝试查询我的Rails数据库(Postgres)中的购买表，我想查询时间范围。例如，我想知道在所有日期的下午2点到3点之间进行了多少次购买。此表中有一个created_at列，但我不知道如何在不搜索特定日期的情况下完成此操作。我试过:Purchases.where("created_atBETWEEN?and?",Time.now-1.hour,Time.now)但这最终只会搜索今天与那些时间的日期。最佳答案您需要使用PostgreSQL'sdate_part/extractfunction从created_at中提取小时