当前在线人数16945
首页 - 分类讨论区 - 电脑网络 - 数据库版 -阅读文章
未名交友
[更多]
[更多]
文章阅读:Re: recursive CTE revisited
[同主题阅读] [版面: 数据库] [作者:TheMatrix] , 2019年12月25日18:57:36
TheMatrix
进入未名形象秀
我的博客
[上篇] [下篇] [同主题上篇] [同主题下篇]

发信人: TheMatrix (TheMatrix), 信区: Database
标  题: Re: recursive CTE revisited
发信站: BBS 未名空间站 (Wed Dec 25 18:57:36 2019, 美东)

有了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也可以完成真正递归
: 的功能。
: ...................







--
☆ 发自 iPhone 买买提 1.24.11
--
※ 修改:·TheMatrix 於 Dec 25 19:06:39 2019 修改本文·[FROM: 50.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]

[上篇] [下篇] [同主题上篇] [同主题下篇]
[转寄] [转贴] [回信给作者] [修改文章] [删除文章] [同主题阅读] [从此处展开] [返回版面] [快速返回] [收藏] [举报]
 
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996