当前在线人数14693
首页 - 分类讨论区 - 电脑网络 - 数据库版 - 同主题阅读文章

此篇文章共收到打赏
0

  • 10
  • 20
  • 50
  • 100
您目前伪币余额:0
未名交友
[更多]
[更多]
SQL recursive CTE
[版面:数据库][首篇作者:TheMatrix] , 2018年12月31日12:46:44 ,629次阅读,10次回复
来APP回复,赚取更多伪币 关注本站公众号:
[分页:1 ]
TheMatrix
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 1 ]

发信人: TheMatrix (TheMatrix), 信区: Database
标  题: SQL recursive CTE
发信站: BBS 未名空间站 (Mon Dec 31 12:46:44 2018, 美东)

这几天仔细想了一下recursive CTE (SQL Server),觉得recursive CTE其实不是
programming意义上的recursive,实际上就是一个loop,while loop或者for loop。

从recursive CTE的结构上看也是这样:它必须有三个部分:初始query,union all 增
长query,还要有结束条件。结束条件就是增长部分不再增长了,就是结束了。这完全
对应了while loop或者for loop的结构。另外“union all”是结构中必须有的关键字
,它没有其他结构。

想了两个基本用例,觉得还是蛮有意思的。又不能贴代码了,只能贴两个图。

--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]


此主题相关图片如下:

[删除]

此主题相关图片如下:
[删除]

 
TheMatrix
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 2 ]

发信人: TheMatrix (TheMatrix), 信区: Database
标  题: Re: SQL recursive CTE
发信站: BBS 未名空间站 (Wed Jan  2 16:02:22 2019, 美东)

SQL query是挺有意思的,它有点functional programming的意思。为什么这么说呢?
因为一个query它首先要构造rowset,有了rowset,再做各种各样的变换,一次可以变
一点点,记为一个CTE,然后把这些一点点的变换串联起来,形成一个复杂的变换。这
正是functional programming的精髓。

然而SQL缺少现场定义的aggregate function的功能。如果用map-reduce来类比的话,
SQL相当于map的功能,它缺少reduce的功能,也就是把一个rowset塌缩为一个数据的功
能。另外反过来看,SQL也缺少现场定义explode函数的功能,也就是把一个比如字符串
数据膨胀为一个rowset的功能。

recursive CTE相当于有了循环,应该可以现场实现所有的reduce或explode的功能。

现场,我的意思是指,在同一个(复合)query中实现。

【 在 TheMatrix (TheMatrix) 的大作中提到: 】
: 这几天仔细想了一下recursive CTE (SQL Server),觉得recursive CTE其实不是
: programming意义上的recursive,实际上就是一个loop,while loop或者for loop。
: 从recursive CTE的结构上看也是这样:它必须有三个部分:初始query,union all 增
: 长query,还要有结束条件。结束条件就是增长部分不再增长了,就是结束了。这完全
: 对应了while loop或者for loop的结构。另外“union all”是结构中必须有的关键字
: ,它没有其他结构。
: 想了两个基本用例,觉得还是蛮有意思的。又不能贴代码了,只能贴两个图。




--
☆ 发自 iPhone 买买提 1.24.09
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 2607:fb90:9839:]

 
TheMatrix
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 3 ]

发信人: TheMatrix (TheMatrix), 信区: Database
标  题: Re: SQL recursive CTE
发信站: BBS 未名空间站 (Thu Jan  3 10:59:35 2019, 美东)

又思考了一下这个recursive CTE,从结构来看,它确实只是一个loop结构,但是从功
能来看,它也确实能实现recursive function才能实现的功能。这一点还是比较神奇的。

沉浸在细节中,我发现它之所以用普通loop的结构,就能实现只有recursive function
才能实现的功能,原因在于rowset。rowset有一种“全面展开”的功能,它把当前状态
的下一步的各种可能性“全面展开”了,再下一步,展开的更宽,再下一步,等等,就
是这么走下去。所以一个loop下来,各种可能的路径全在里面了。普通recursive
function里面需要的试探回溯之类的就不需要了。

这个确实很神奇啊。很多地方都能kandq这个模式:矢量计算,list processing,
stochastic process,平行宇宙。

【 在 TheMatrix (TheMatrix) 的大作中提到: 】
: 这几天仔细想了一下recursive CTE (SQL Server),觉得recursive CTE其实不是
: programming意义上的recursive,实际上就是一个loop,while loop或者for loop。
: 从recursive CTE的结构上看也是这样:它必须有三个部分:初始query,union all 增
: 长query,还要有结束条件。结束条件就是增长部分不再增长了,就是结束了。这完全
: 对应了while loop或者for loop的结构。另外“union all”是结构中必须有的关键字
: ,它没有其他结构。
: 想了两个基本用例,觉得还是蛮有意思的。又不能贴代码了,只能贴两个图。




--
☆ 发自 iPhone 买买提 1.24.09
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 2607:fb90:b631:]

 
TheMatrix
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 4 ]

发信人: TheMatrix (TheMatrix), 信区: Database
标  题: Re: SQL recursive CTE
发信站: BBS 未名空间站 (Thu Jan  3 11:51:55 2019, 美东)

再出两个题,演示一下recursive CTE“全面展开”的功能。“跳马问题”和“八后问
题”。这两个问题是经典的递归问题。用python写了一下,见图。

跳马问题,是在一个5X5的棋盘上跳马,马初始位置在(0,0),马走日。找出全部走法,
使马能连续走遍棋盘上所有位置各一次。

八后问题,是在一个国际象棋棋盘上,摆八个皇后,使它们互相不能吃,列举所有的摆
法。棋盘是8X8,皇后可以横竖直走,也可以两个45度角斜走。



【 在 TheMatrix (TheMatrix) 的大作中提到: 】
: 又思考了一下这个recursive CTE,从结构来看,它确实只是一个loop结构,但是从功
: 能来看,它也确实能实现recursive function才能实现的功能。这一点还是比较神奇
的。
: 沉浸在细节中,我发现它之所以用普通loop的结构,就能实现只有recursive
function
: 才能实现的功能,原因在于rowset。rowset有一种“全面展开”的功能,它把当前状态
: 的下一步的各种可能性“全面展开”了,再下一步,展开的更宽,再下一步,等等,就
: 是这么走下去。所以一个loop下来,各种可能的路径全在里面了。普通recursive
: function里面需要的试探回溯之类的就不需要了。
: 这个确实很神奇啊。很多地方都能kandq这个模式:矢量计算,list processing,
: stochastic process,平行宇宙。




--
☆ 发自 iPhone 买买提 1.24.09
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 2607:fb90:b631:]


此主题相关图片如下:

[删除]

此主题相关图片如下:
[删除]

 
TheMatrix
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 5 ]

发信人: TheMatrix (TheMatrix), 信区: Database
标  题: Re: SQL recursive CTE
发信站: BBS 未名空间站 (Fri Jan  4 10:23:34 2019, 美东)

这个“全面展开”的功能真的很有启发。同样的方法,用python实现也是很简单,见图。

递归不需要了,一个loop解决问题。我知道有标准的方法把递归替换成loop,但是具体
是什么样的我也没想明白,现在看来,很可能就是这个样子的。

这个程序结构再深挖一点也可以。它可以看成是一个时间演化系统,多个sample点同时
演化,在统一的时钟步骤下往前走,可以分叉,可以消失。每次演化可以只依赖当前演
化front,也可以依赖历史。可以考察演化的不同时间的front,也可以考察任意定义的
section。这个模式比递归有意义啊。

【 在 TheMatrix (TheMatrix) 的大作中提到: 】
: 再出两个题,演示一下recursive CTE“全面展开”的功能。“跳马问题”和“八后问
: 题”。这两个问题是经典的递归问题。用python写了一下,见图。


--
☆ 发自 iPhone 买买提 1.24.09
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 2607:fb90:b644:]


此主题相关图片如下:

[删除]

此主题相关图片如下:
[删除]

 
TheMatrix
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 6 ]

发信人: TheMatrix (TheMatrix), 信区: Database
标  题: Re: SQL recursive CTE
发信站: BBS 未名空间站 (Fri Jan  4 14:16:24 2019, 美东)

string_aggregate和string_split,我的实现方法,用recursive CTE的。见图。

--
☆ 发自 iPhone 买买提 1.24.09
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 2607:fb90:b644:]


此主题相关图片如下:

[删除]

此主题相关图片如下:
[删除]

 
TheMatrix
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 7 ]

发信人: TheMatrix (TheMatrix), 信区: Database
标  题: Re: SQL recursive CTE
发信站: BBS 未名空间站 (Fri Jan  4 14:33:06 2019, 美东)

跳马问题和八后问题,我的实现方法,用recursive CTE的。见图。

跳马问题surprisingly easy,因为验证一步是否合法,用SQL写很容易。

八后问题在递归这一步没有问题,但是在验证这一步有麻烦。因为验证一步合法,本身
就用到循环,而循环在SQL中就是recursive CTE,所以这需要两个recursive CTE嵌套
,而这是不允许的。所以我有两个版本,一个是把验证循环展开,相当于code
generation的做法。另一个必须借助于一个自定义函数。

--
☆ 发自 iPhone 买买提 1.24.09
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 2607:fb90:b644:]


此主题相关图片如下:

[删除]

此主题相关图片如下:
[删除]

此主题相关图片如下:
[删除]

 
TheMatrix
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 8 ]

发信人: TheMatrix (TheMatrix), 信区: Database
标  题: Re: SQL recursive CTE
发信站: BBS 未名空间站 (Fri Jan  4 17:10:23 2019, 美东)

这个全面展开的方法还不是把递归变成loop的标准方法,标准方法是用栈。用tree
search来看的话,全面展开相当于广度优先,递归方法是深度优先。从时间演化的角度
看,全面展开的方法是看所有path的front,而递归是看一条path,然后再看另一条,
一条一条之间的switch靠栈。

【 在 TheMatrix (TheMatrix) 的大作中提到: 】
: 这个“全面展开”的功能真的很有启发。同样的方法,用python实现也是很简单,见
图。
: 递归不需要了,一个loop解决问题。我知道有标准的方法把递归替换成loop,但是具体
: 是什么样的我也没想明白,现在看来,很可能就是这个样子的。
: 这个程序结构再深挖一点也可以。它可以看成是一个时间演化系统,多个sample点同时
: 演化,在统一的时钟步骤下往前走,可以分叉,可以消失。每次演化可以只依赖当前演
: 化front,也可以依赖历史。可以考察演化的不同时间的front,也可以考察任意定义的
: section。这个模式比递归有意义啊。




--
☆ 发自 iPhone 买买提 1.24.09
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 2607:fb90:b644:]

 
TheMatrix
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 9 ]

发信人: TheMatrix (TheMatrix), 信区: Database
标  题: Re: SQL recursive CTE
发信站: BBS 未名空间站 (Fri Jan  4 22:05:31 2019, 美东)

用stack把递归替换成loop要这么做:见图。

【 在 TheMatrix (TheMatrix) 的大作中提到: 】
: 这个全面展开的方法还不是把递归变成loop的标准方法,标准方法是用栈。用tree
: search来看的话,全面展开相当于广度优先,递归方法是深度优先。从时间演化的角度
: 看,全面展开的方法是看所有path的front,而递归是看一条path,然后再看另一条,
: 一条一条之间的switch靠栈。





--
☆ 发自 iPhone 买买提 1.24.09
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]


此主题相关图片如下:

[删除]

此主题相关图片如下:
[删除]

 
TheMatrix
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 10 ]

发信人: TheMatrix (TheMatrix), 信区: Database
标  题: Re: SQL recursive CTE
发信站: BBS 未名空间站 (Sat Jan  5 23:41:15 2019, 美东)

front的方法等价于队列,先进先出。递归的方法是个栈,后进先出。都是经典的东西。

【 在 TheMatrix (TheMatrix) 的大作中提到: 】
: 这个程序结构再深挖一点也可以。它可以看成是一个时间演化系统,多个sample点同时
: 演化,在统一的时钟步骤下往前走,可以分叉,可以消失。每次演化可以只依赖当前演
: 化front,也可以依赖历史。可以考察演化的不同时间的front,也可以考察任意定义的
: section。这个模式比递归有意义啊。




--
☆ 发自 iPhone 买买提 1.24.09
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]

 
TheMatrix
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 11 ]

发信人: TheMatrix (TheMatrix), 信区: Database
标  题: Re: SQL recursive CTE
发信站: BBS 未名空间站 (Mon Jan  7 10:27:45 2019, 美东)

用queue来做就是这样,见图。python里面没有类似pop的函数,所以先进先出要用一个
pointer。另外,什么需要放入queue里,这个可以考虑一下,可以极简可以冗余。队列
和栈是事件处理模式的基本数据结构。站在更一般的角度,事件处理或者消息处理的角
度看,这些处理模式就很自然了。

【 在 TheMatrix (TheMatrix) 的大作中提到: 】
: front的方法等价于队列,先进先出。递归的方法是个栈,后进先出。都是经典的东
西。




--
☆ 发自 iPhone 买买提 1.24.09
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]


此主题相关图片如下:

[删除]

[分页:1 ]
[快速返回] [ 进入数据库讨论区] [返回顶部]
回复文章
标题:
内 容:

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

友情链接


 

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

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