Path: news.easynews.com!core-easynews!newsfeed2.easynews.com!easynews.com!easynews!newsfeed.news2me.com!canoe.uoregon.edu!logbridge.uoregon.edu!newsfeed.stanford.edu!postnews1.google.com!not-for-mail
From: mikharakiri@yahoo.com (Mikito Harakiri)
Newsgroups: comp.databases.ibm-db2,comp.databases.theory
Subject: is DB2 recursive query semantics inflationary?
Date: 5 Jun 2003 16:18:36 -0700
Organization: http://groups.google.com/
Lines: 102
Message-ID: <bdf69bdf.0306051518.46204a92@posting.google.com>
NNTP-Posting-Host: 148.87.1.171
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: posting.google.com 1054855116 15703 127.0.0.1 (5 Jun 2003 23:18:36 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: 5 Jun 2003 23:18:36 GMT
Xref: core-easynews comp.databases.ibm-db2:78183 comp.databases.theory:26686
X-Received-Date: Thu, 05 Jun 2003 16:23:33 MST (news.easynews.com)

Graeme Birchall's "DB2 Cookbook" says:

<quote p.210>
WITH PARENT (PKEY, CKEY) AS (SELECT PKEY, CKEY 
FROM HIERARCHY 
WHERE PKEY = 'AAA' 
UNION ALL 
SELECT C.PKEY, C.CKEY 
FROM HIERARCHY C 
,PARENT P 
WHERE P.CKEY = C.PKEY 
) 
SELECT PKEY, CKEY 
FROM PARENT;

ANSWER
========= PROCESSING
PKEY CKEY SEQUENCE
---- ---- ==========
AAA BBB < 1st pass
AAA CCC   ""
AAA DDD   ""
CCC EEE < 2nd pass
DDD FFF   ""
DDD EEE < 3rd pass
FFF GGG < 4th pass

Figure 580, SQL that does Recursion

The above statement is best described by decomposing it into its
individual components, and
then following of sequence of events that occur:
• The WITH statement at the top defines a temporary table called
PARENT.
• The upper part of the UNION ALL is only invoked once. It does an
initial population of
the PARENT table with the three rows that have an immediate parent key
of AAA .
• The lower part of the UNION ALL is run recursively until there are
no more matches to
the join. In the join, the current child value in the temporary PARENT
table is joined to
related parent values in the DATA table. Matching rows are placed at
the front of the
temporary PARENT table. This recursive processing will stop when all
of the rows in the
PARENT table have been joined to the DATA table.
• The SELECT phrase at the bottom of the statement sends the contents
of the PARENT
table back to the user's program.
</quote>

Is it correct recursive sql execution description? First, I would
assume that recursive processing engine is not aware of the join
inside recursive view definition. Moreover, in the next chapter Graeme
gives recursive example that generates natural number sequence and
doesn't have such join.

My runtime interpretation of recursive SQL is:

ANSWER
========= PROCESSING
PKEY CKEY SEQUENCE
---- ---- ==========
AAA BBB < 1st step
AAA CCC   ""
AAA DDD   ""

AAA BBB < 2nd step
AAA CCC   ""
AAA DDD   ""
CCC EEE   ""
DDD FFF   ""
DDD EEE   "" 

AAA BBB < 3rd step
AAA CCC   ""
AAA DDD   ""
CCC EEE   ""
DDD FFF   ""
DDD EEE   "" 
FFF GGG   "" 

That's right: recursive view means that given temporary table state
T(N) at the step N we calculate T(N+1) as

T(N+1) =
SELECT PKEY, CKEY 
FROM HIERARCHY 
WHERE PKEY = 'AAA' 
UNION ALL 
SELECT C.PKEY, C.CKEY 
FROM HIERARCHY C 
,T(N) P 
WHERE P.CKEY = C.PKEY

which means that temporary table is totally rewritten at each step
rather than incrementally inflated as Graeme suggests.

Am I missing some kind of optimization that reduces my execution to
Graeme's? (My guess would be that not every kind of recursive union
view would allow such transformation.)