知识卡片
递归查询与传递闭包
材料单场景(关系变量PP记录零件间的直接组成关系)需要递归求解传递闭包TC:
配对(px,py)出现在tc中,当且仅当它直接出现在pp中,或者存在某个pz使得(px,pz)
出现在pp中且(pz,py)出现在tc中(tc引用自身,是典型的递归定义)。这个定义有
一种等价的过程化/迭代实现:初始化TC:=PP,反复用TC UNION (PP和TC按PZ连接
再投影)更新TC,直到TC不再增长为止——直到到达一个”定点”(fixpoint),这种
用不动点迭代求解递归定义的思路,是关系代数处理层级/图结构数据的标准手法。
SQL的WITH RECURSIVE语法本质上是这套递归定义的直接翻译。但SQL在处理递归
查询时有一个容易被忽视的隐患:像Oracle的CONNECT BY那种实现方式,对
同一个终点存在多条不同路径时(比如从零件P1经P2或经P3都能到达P4),
会产生”看起来像重复行”、但实际携带着完全不同信息的结果行——两行(2,P4)分别
代表两条不同的路径,删除任何一行都会真的丢失信息,这和[[重复行无法分辨真伪]]里讨论的”无意义重复行”有本质区别,但表面上二者
在SQL结果集里看起来一模一样,这正是[[关系代数的闭包性质]]被违反的一个具体
案例——这样的结果集里不仅有重复行,行的顺序本身还携带着必须保留的路径信息,
彻底破坏了关系”元组无序”的基本性质。递归数据里若存在环(比如交通网络中的
往返航线),传递闭包本身不受影响,但过程化求解容易陷入死循环,简单的”排除
回到起点”式技巧不足以根治问题(仍可能出现绕远路的死循环路径),SQL标准为此
专门提供了CYCLE子句,用于标记已访问过的节点、在检测到重复访问时提前终止
递归。
结构图:
flowchart TD
A["传递闭包递归定义<br/>tc(px,py) ⟺ pp(px,py) 或<br/>∃pz: pp(px,pz)∧tc(pz,py)"] --> B["不动点迭代求解<br/>TC:=PP; 循环 TC∪=新增配对<br/>直到TC不再增长"]
B --> C["SQL WITH RECURSIVE<br/>= 递归定义的直接翻译"]
A --> D["多路径到达同一终点<br/>= 表面重复行, 实携带不同信息"]
D --> E["违反关系闭包性质<br/>删除/重排行都会丢失信息"]
A --> F["数据含环 (如往返航线)<br/>过程化求解可能死循环"]
F --> G["SQL CYCLE子句<br/>标记已访问节点提前终止"]
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- SQL和关系代数II:附加运算符 7.12 对于递归的说明 · 查看原书依据
SQL实际上就包含一个可在递归查询中用于此目有的特性——CYCLE子句。 CYCLE子句的细节比较复杂,此处不做阐述;简单地说,CYCLE子句提供了一种标记某节点(即数据行)已被访问过的方法,可以在有一次遇到已标记节点时停止递归。