Re: double linked list

"--CELKO--" <71062.1056_at_compuserve.com> wrote in message news:c0d87ec0.0302051638.36d87f46_at_posting.google.com...
> >> What do you mean by "direct use"? This is SQL, a user is allowed to
> inline and nest subqueries. <<
>
> But you want to avoid them in favor of simple, "flat" joins whenever
> possible. They hurt performance and maintainability.

OK.

> >> Where in the above examples did you see a cursor? <<
>
> It's there, but it is hidden in the syntax. The fact that I have to
> proceed from one row to another in a particular order means I am doing
> sequential processing. Do you know of a parallel algorithm for ue
> with the adjacency list model of a tree?

Suppose we have relation

Links
start end
---- ---
1 2
2 3

and it's transitive closure

TC
start end
---- ---
1 2
2 3
1 3

It's not important whether TC is built on the fly (for example, with "recursive with" construct), or incrementally maintained. Then the hierarchical queries against TC relation

select count(1) from TC
where start = 2

• the total number of descendants of the node #2, and

select count(1) from TC
where end = 2

• the node level

and others are as easy as the queries against the Nested Sets model.

To be fair, if you have a "cursor" objection against "connect by", it should apply to "recursive with" as well, right?

> >> 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. <<
>
> Granted, but you also lose the ability to order the children, to
> separate the tree structure from the nodes (organizational chart
> versus personnel)

I don't follow here.

Since adjacency list model applies to DAGs, which are more general case then trees, we must be careful about separating graph nodes and edges. Otherwise, there would be nulls like this

Links
parent_id id
-------- ---

null     1
1        2
2        3

and a lot of confusion. (For example: Was that query against the nodes, or against the links?)

> >> The hierarchical query that is locked into any of these scheme is
> implementation dependent! <<
>
> Unh? All of the methods on your list use Standard SQL, and have no
> implementation dependent features (well, other than precision and
> scale of numbers) or vendor extensions. There are trade-offs with
> each; the amount of math needed for a query in the ones that depend on
> numeric pairs, the storage for a path enumeration string and the
> seartch time, etc.

Once again, it is implementation dependent in the sence that the user is locked into a particular labeling schema. He would have to completely rewrite his queries if he decides to change labeling. On contrary, there only one adjacency list model.

> The big advantage of the adjacency list model is that it is fast and
> easy to insert new rows.

It is more general too.

> But summary data is much harder to obtain,

Not if transitive closure is known.

> and constraints to preserve the tree structure are more complex (most
> programmers do not bother to write the needed constraints!! Arrgh!).
> Simple deletion of a row splits the tree apart, so you need code to
> reconstruct it. Protection from cycles requires either procedural
> code or table level check clauses (not yet found in many products).
> Following a path requires cursors - hidden or explicit.
>
> Done right, the adjacency list is harder than people think.

That might be correct. However, until Herarchy Theory in the Relational Model is mostly undeveloped I prefer not to dismiss alternative solutions easily. Received on Thu Feb 06 2003 - 02:36:46 CET