recursive CTE revisited

贴中不能有代码，只能附图，真是挺不方便的。

Recursive CTE有两点困惑，想清楚了隔一段时间又困惑了，今天再确认一遍。

（这里有个附图1）

这里有两点值得指出：

1. 说是recursive，实际上是一个循环。循环体中又用到了名字本身，但是应该理解为重命名，而不是理解为递归调用。重命名是比如：T=T+1，或者T=A(T)，这是重命名。
递归调用是这样的：
def function T(n) { ... T(n-1) ...}
当然所有的递归调用都可以改写为循环，所以SQL recursive CTE也可以完成真正递归
的功能。

2. 在UNION ALL第二部分中出现的CTE这个名字，到底是cumulative的结果还是
incremental的
table？这个是我每次都迷惑的地方。我又确认的一下，是incremental的table，就是
程序结构中那个T。这个可以写一个SQL确认一下，如图2。图中每一行
的first_value和last_value都相等，这说明在每一步的CTE中，都只有一行，也就是
incremental table，而不是cumulative的结果。

有了recursive CTE之后，Single SQL SELECT statement就应该是图灵完备的，当然这是指带WITH的SELECT statement。这个我以前不是很确定，现在我更确定了一些。我来“证明”一下。

首先图灵完备的意思，基本上是指输入任意的rowset，以可描述的算法可得到的任一输出rowset，都可以由single SELECT statement得到。

其次我们知道比如T-SQL这种，包含了控制结构语句的SQL语言是图灵完备的。再其次，我们还知道，通用程序语言，尤其是函数式程序语言，中的reduce函数，或者叫语句吧，可以完全替代循环这种控制结构。也就是说如果一个程序语言能够实现1，结果命名
，也就是顺序结构，2，分支结构，也就是if else，3，reduce函数，那么它就应该是
图灵完备的。

我就示意一下用recursive CTE如何实现reduce函数。

reduce函数的用法是这样的，它接受三个输入参数，第一个参数是一个二元函数，比如CONCAT，输入两个varchar，返回一个varchar。第二个参数是一个list，可以理解为一个rowset。第三个参数是一个初始值。它工作的原理是，首先把初始值当作结果，然后把这个结果和list中的元素依次做二元操作，也就是reduce的第一个参数函数，结果迭代回结果。

接下来假定，只用SQL built in的varchar函数，所能实现的二元varchar函数，作为
reduce的第一个参数，就足够实现任意操作。这个我不能完全说明，但是我觉得这是合假设。

那么假设我们有这么一个二元varchar函数，叫A。我们将用recursive CTE实现reduce(A, list, init)。

实现的方法是，先给list或者rowset里的record编号，也就是row_number。然后就是这个recursive CTE，它的第一部分，也就是union all之前的部分，是init rowset。它
的第二部分，也就是incremental的部分，每次只有一行，是当前结果（也是一行）和
输入list的下一行的join，有行号的话这是可以做到的。然后在这一行里用二元函数A。

【 在 TheMatrix (TheMatrix) 的大作中提到: 】
: 贴中不能有代码，只能附图，真是挺不方便的。
: Recursive CTE有两点困惑，想清楚了隔一段时间又困惑了，今天再确认一遍。
: （这里有个附图1）
: 这里有两点值得指出：
: 1. 说是recursive，实际上是一个循环。循环体中又用到了名字本身，但是应该理解为
: 重命名，而不是理解为递归调用。重命名是比如：T=T+1，或者T=A(T)，这是重命名。
: 递归调用是这样的：
: def function T(n) { ... T(n-1) ...}
: 当然所有的递归调用都可以改写为循环，所以SQL recursive CTE也可以完成真正递归
: 的功能。
: ...................