Re: double linked list

From: Mikito Harakiri <>
Date: Wed, 5 Feb 2003 10:40:38 -0800
Message-ID: <ZZc0a.13$>

"--CELKO--" <> wrote in message
> How about if I say the code to do tree manipulation with CONNECT BY is
> orders of magnitude slower, not Standard, not portable and quickly
> becomes a nightmare of nested subqueries to maintain? Once more, let
> me demonstrate my points with actual code. (If that dos not work,
> what will convince you that I have a valid position?)

Connect-By uses indexed nested loops. If both id and parent id columns are indexed, it is reasonably fast.

> The query "Show all subcomponents of part A1, including the
> substructure" can be handled by the following Oracle SQL statement:
> SELECT LEVEL AS pathlength, assemblyno, subassemblyno
> FROM Blueprint
> START WITH assemblyno = 'A1'
> CONNECT BY PRIOR subassemblyno = assemblyno;
> The CONNECT BY ... PRIOR clause provides traversal but not support for
> recursive aggregate functions. For example, it is not possible to sum
> the weights of all subcomponents of part A1 to find the weight of A1.
> The only recursive function supported by the CONNECT BY ... PRIOR
> clause is the LEVEL function.

Recursive Aggregate Functions aka Hierarchical Totals are prefectly possible with connect-by. Just use subqueries in the "select" list (Date's idea of expressing group-by with subqueries in the "select" list). select e1.ename,

(select sum(e2.sal) from emp e2

connect by e2.mgr = prior e2.empno

start with e2.empno = e1.empno)

from emp e1

I'm skeptical, however, about optimization of hierarchical total. For one thing, I'm not aware of any product that would be able to unnest subquery in the select list into "group by" query. Corrections are welcome.

> Another limitation of the CONNECT BY ... PRIOR clause is that it does
> not permit the use of joins. The reason for disallowing joins is that
> the order in which the rows are returned in the result is important.
> The parent nodes appear before their children, so you know that if the
> pathlength increases, these are children; if it does not, they are new
> nodes at a higher level.

Not true anymore for Oracle 9.

> This also means that an ORDER BY can destroy any meaning in the
> results. This means, moreover, that the CONNECT BY ... PRIOR result
> is not a true table, since a table by definition does not have an
> internal ordering. In addition, this means that it is not always
> possible to use the result of a CONNECT BY query in another query.

Connect-by ordering is no more a problem than the Standard SQL Order-By.

<exapmle with join workaround snipped>

> Another query that cannot be
> processed by direct use of the CONNECT BY ... PRIOR clause is one that
> displays all parent-child relationships at all levels. A technique to
> process this query is illustrated by the following SQL:
> SELECT DISTINCT PX.part_nbr, PX.pname, PY.part_nbr, PY.pname
> FROM Parts AS PX, Parts AS PY
> WHERE PY.part_nbr IN (SELECT Blueprint.subassemblyno
> FROM Blueprint
> START WITH assemblyno = PX.part_nbr
> CONNECT BY PRIOR subassemblyno = assemblyno)
> ORDER BY PX.part_nbr, PY.part_nbr;
> Again, the outer query includes a JOIN, which is not allowed with the
> CONNECT BY ... PRIOR clause. Note that the correlated subquery
> references PX.part_nbr.

What do you mean by "direct use"? This is SQL, a user is allowed to inline and nest subqueries.

Transitive closure query could be answered easily if we just drop "start with" clause.

SELECT Blueprint.subassemblyno,

instr(sys_connect_by_path(assemblyno,'/')||'/','/',2)-2)) FROM Blueprint
CONNECT BY PRIOR subassemblyno = assemblyno

> The basic problem is that CONNECT BY is a cursor (procedural code) and
> SQL is set-oriented. They don't work together very well

Where in the above examples did you see a cursor?

> I am trying to figure out "those not as technically proficient as
> me"?? I think that anyone can understand the nested sets or nested
> intervals model if they understand HTML or XML or work in a block
> structured language -- it is the same concept. It is all just
> "parentheses in disguise", not rocket science. I have not lost an
> audience when I teach it and several times programmers who were
> introduced to the technique for the first time came up with some stuff
> I had not thought of before -- they started drawing circles inside
> circles (i.e. set diagrams) instead of "boxes and arrows" (i.e.
> sequential travesals) and looked at their problems differently.

The appealing part of the transitive closure syntax -- being it Recursive With, or Connect By -- is that the hierarchical query doesn't use a particular labeling scheme. Certainly, you might insist that only one labeling scheme exists -- nested sets -- but we know otherwise. Here is incomplete list:

0. Materialized Path
1. Nested Sets.
2. <depth_first_order, depth> integer pair
3. Binary Rationals
4. Primary Number Decompositions

The hierarchical query that is locked into any of these scheme is implementation dependent! Received on Wed Feb 05 2003 - 19:40:38 CET

Original text of this message