是否允许非线性递归？它是否利用指数？ [英] Is nonlinear recursion allowed? Does it leverage index?
问题描述
我想知道是否
与RECURSIVE MaryAncestor（anc，desc）AS
（（选择父级为anc，子级为desc FROM ParentOf WHERE desc =
" Mary"）
UNION
（SELECT A1.anc，A2.desc
来自MaryAncestor A1 ，MaryAncestor A2
WHERE A1.desc = A2.anc））
来自MaryAncestor的SELECT anc
在DB2中允许
第一名。如果允许，它可以在从Mary导航路径时利用连接索引
。节点到祖先根？
I wonder if
WITH RECURSIVE MaryAncestor(anc,desc) AS
( (SELECT parent as anc, child as desc FROM ParentOf WHERE desc =
"Mary")
UNION
(SELECT A1.anc, A2.desc
FROM MaryAncestor A1, MaryAncestor A2
WHERE A1.desc = A2.anc) )
SELECT anc FROM MaryAncestor
is allowed in DB2 in the first place. If allowed, can it leverage join index
when navigating path from "Mary" node to ancestor root?
推荐答案
Mikito，
我'我不确定我是否首先理解了这个问题。
我似乎无法看到你在树上导航的位置。
在DB2中递归必须使用UNION ALL。我不认为你可以使用递归公用表表达式两次使用
递归。
以下是我写它的方法：
使用MaryAncestor（anc，desc）AS
（（选择父级为anc，子级为desc
FROM ParentOf WHERE desc =" Mary" ）
UNION ALL
（SELECT P.anc，A.desc
来自MaryAncestor A，ParentOf P WHERE A.anc = P.desc ））
选择来自MaryAncestor的anc
（至少类似的东西......）
干杯< br $>
Serge
-
Serge Rielau
DB2 SQL编译器开发
IBM多伦多实验室
Mikito,
I''m not sure I understand the query in the first place.
I don''t seem to see where you navigate up the tree.
In DB2 recursion must use UNION ALL. I don''t think you can recurse using
the recursive common table expression twice.
Here is how I would write it:
WITH MaryAncestor(anc,desc) AS
( (SELECT parent as anc, child as desc
FROM ParentOf WHERE desc = "Mary")
UNION ALL
(SELECT P.anc, A.desc
FROM MaryAncestor A, ParentOf P WHERE A.anc = P.desc) )
SELECT anc FROM MaryAncestor
(something like that at least...)
Cheers
Serge
--
Serge Rielau
DB2 SQL Compiler Development
IBM Toronto Lab
来自
http://www-db.stanford.edu/~widom/cs...recursion.html
< quote>
非线性递归
SQL-99只需要支持linear递归：每个FROM最多只有一个递归定义关系的引用。
示例：祖先的非线性版本：
与RECURSIVE Ancestor（anc，desc）AS
（（选择父级为anc，子级为desc FROM ParentOf）
UNION
（SELECT A1.anc，A2.desc
来自Ancestor A1，Ancestor A2
WHERE A1.desc = A2.anc））
SELECT anc FROM Ancestor WHERE desc =Mary
a ..看起来更干净
b ..执行它的字面上比线性收敛到定点
版本
< / quote><搁置> XML仍然很糟糕< / aside>
我所做的只是手动推单表谓词desc =玛丽里面
视图定义。
现在我怀疑这句话执行它真正收敛到定点
比线性更快版本"从实际角度出发。是的，
我们可以更快地建立传递闭包，但这里的执行并不需要
完全传递闭包;只有从节点到根的路径。
看起来这里的理论和实践并不协调:-)
BTW，我正在比较连接和递归。是否有一个查询
可以在一个中表达而在另一个中不能表示？
" Serge Rielau" < SR ***** @ ca.eye-be-em.com>在消息中写道
news：c1 ********** @ hanover.torolab.ibm.com ...
From
http://www-db.stanford.edu/~widom/cs...recursion.html
<quote>
Nonlinear recursion
SQL-99 only requires support of "linear" recursion: each FROM has at most
one reference to a recursively-defined relation.
Example: Nonlinear version of Ancestor:
WITH RECURSIVE Ancestor(anc,desc) AS
( (SELECT parent as anc, child as desc FROM ParentOf)
UNION
(SELECT A1.anc, A2.desc
FROM Ancestor A1, Ancestor A2
WHERE A1.desc = A2.anc) )
SELECT anc FROM Ancestor WHERE desc = "Mary"
a.. Looks cleaner
b.. Executing it literally converges to fixed-point faster than linear
version
</quote><aside>XML still sucks</aside>
All I did was manually pushing single table predicate desc = "Mary" inside
view definition.
Now I doubt that statement "Executing it literally converges to fixed-point
faster than linear version" makes any sence from practical perspective. Yes,
we can build transitive closure faster, but the execution here doesn''t need
full transitive closure; only path from node to the root.
It looks like theory and practice aren''t in harmony here:-)
BTW, I''m comparing "connect by" and "recursive with". Is there a query that
can be expressed in the one and cannot in the other?
"Serge Rielau" <sr*****@ca.eye-be-em.com> wrote in message
news:c1**********@hanover.torolab.ibm.com...
Mikito，
<我不确定我是否首先理解了查询。
我似乎无法看到你在树上导航的位置。
在DB2递归中必须使用UNION ALL。我不认为你可以使用递归公用表表达式两次递归。
以下是我将如何写它：
与MaryAncestor（anc， desc）AS
（（选择父母为anc，孩子为desc
FROM ParentOf WHERE desc =" Mary"）
UNION ALL
（SELECT P.anc，A.desc
来自MaryAncestor A，ParentOf P WHERE A.anc = P.desc））
从MaryAncestor中选择一个
（至少这样的东西......）
干杯
Serge
-
Serge Rielau
DB2 SQL编译器开发
IBM多伦多实验室
Mikito,
I''m not sure I understand the query in the first place.
I don''t seem to see where you navigate up the tree.
In DB2 recursion must use UNION ALL. I don''t think you can recurse using
the recursive common table expression twice.
Here is how I would write it:
WITH MaryAncestor(anc,desc) AS
( (SELECT parent as anc, child as desc
FROM ParentOf WHERE desc = "Mary")
UNION ALL
(SELECT P.anc, A.desc
FROM MaryAncestor A, ParentOf P WHERE A.anc = P.desc) )
SELECT anc FROM MaryAncestor
(something like that at least...)
Cheers
Serge
--
Serge Rielau
DB2 SQL Compiler Development
IBM Toronto Lab
Mikito Harakiri写道：
Mikito Harakiri wrote:
BTW，我正在比较connect by和递归。是否存在可以在一个中表达而不能在另一个中表达的查询？
BTW, I''m comparing "connect by" and "recursive with". Is there a query that
can be expressed in the one and cannot in the other?
好问题。我记得Oracle新闻组中的一个帖子
得出的结论是标准版本功能更强大，但这几乎不是基于数学证明的
。
另请注意，O10g已经对连接进行了更改。
有一件事我可以自信地说：
重写另一个是另一个是一般都是非常重要的。
当你试图取消订单和等级时，事情变得越来越有趣了。> b $ b信息来自递归。
鉴于我从来没有用连接写任何东西我不能评论
连接失误。
干杯
Serge
-
Serge Rielau
DB2 SQL编译器开发
IBM多伦多实验室
Good question. I remember a thread in the Oracle newsgroup that
concluded that the standard version was more powerful, but that was
hardly based on a mathematical proof.
Also note that O10g has made changes to connect by.
There is one thing I can say with confidence:
Rewriting one as the other is in general non trivial.
Things are getting interesting when you try to tease order and level
information out of "recursive with".
Given that I never wrote anything using connect by I can''t comment where
connect by stumbles.
Cheers
Serge
--
Serge Rielau
DB2 SQL Compiler Development
IBM Toronto Lab
这篇关于是否允许非线性递归？它是否利用指数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
