Skip to main content

Recursive Select - tree traversal

Walking a tree is not that big of a challenge. There are a few different variations in the SQL language but they are similar enough.

Given a schema that looks like:
create table tree( id int, parentid int, type int);
;with recursive    tree_cte (id, parentid, type) as (       select 1,0,0       union all       select, t.parentid, t.type         from tree t         inner join tree_cte tc on     )     select * from tree_cte tc     ;
SQL Server:
;with     tree_cte (id, parentid, type) as (       select id, parentid, type from (values(1,0,0) X(id, parentid, type, path))
       union all       select, t.parentid, t.type         from tree t         inner join tree_cte tc on     )     select * from tree_cte tc     ;
The differences are '+' instead of '||' and "recursive" and a little of the initiator SQL in the SQL Server version.

In a project I'm working on I need to create a graph of the entire tree, however, there are a few constraints. (a) the graph is huge so limit the graph as soon as possible; (b) only report full paths (no downline nodes); (c) a downline node can only be of type '1'. (NOTE: nodes of type 1 will not be separated by other node types.)

The original query returned:
Nothing special to see, it's the same as if I had selected everything:
select * from tree
Let's look at the individual paths:
;with recursive    tree_cte (id, parentid, type, path) as (       select 1,0,0,'1'       union all       select, t.parentid, t.type, tc.path || '.' || cast( as varchar)         from tree t         inner join tree_cte tc on     )     select * from tree_cte tc
With this output:
But according to my rules there are a few extra lines:
'+' when the node was the wrong type
'*' when the node was not a leaf node

This is the final code unless someone posts a recommendation... it is pretty simple:
;with recursive    tree_cte (id, parentid, type, path) as (       select 1,0,0,'1'       union all       select, t.parentid, t.type, tc.path || '.' || cast( as varchar)         from tree t         inner join tree_cte tc on         where t.type =1     )     select * from tree_cte tc     where not exists (select 1 from tree t where and type=1)
and it produced:
The differences being the where clause in the recursive SQL in the CTE and the conditional check in the outer select.
(1) where t.type =1
(2) where not exists (select 1 from tree t where and type=1)
(1) being some sort of a sentinel terminator for quick termination of the recursion instead of exhausting the data.
(2) when there is a mix of nodes where the non-desired nodes appear at different depths in the tree we need to make sure that the perceived leaf node is actually a leaf or the last of it's type.

Feels good to me. Now I have to put this into practice.


Popular posts from this blog

Entry level cost for CoreOS+Tectonic

CoreOS and Tectonic start their pricing at 10 servers. Managed CoreOS starts at $1000 per month for those first 10 servers and Tectonic is $5000 for the same 10 servers. Annualized that is $85K or at least one employee depending on your market. As a single employee company I'd rather hire the employee. Specially since I only have 3 servers.

The pricing is biased toward the largest servers with the largest capacities; my dual core 32GB i5 IntelNuc can never be mistaken for a 96-CPU dual or quad core DELL

If CoreOS does not figure out a different barrier of entry they are going to follow the Borland path to obscurity.

UPDATE 2017-10-30: With gratitude the CoreOS team has provided updated information on their pricing, however, I stand by my conclusion that the effective cost is lower when you deploy monster machines. The cost per node of my 1 CPU Intel NUC is the same as a 96 CPU server when you get beyond 10 nodes. I'll also reiterate that while my pricing notes are not currently…

Agile is still dead and has been since 1991

[updated 2011.09.30] yet another response to Agile is good.
When you have so much of you career invested in something like Agile, XP etc... it can be hard to see the forest for the trees. I had a consulting job in The Haag many years ago. IBM was the incumbent contractor at the customer site (a bank) but after 5 years on the job they had not written a single line of functioning code. In the office there were two teams of software people... both behind closed doors. The first team was the Data team and the second team was Functional. They rarely spoke and they never shared information. I was there for a week, introduced the client to OO and we had a functioning prototype. Smart people do smart things, You cannot make an underachiever exceptional by using Agile. Either they get "it" or they don't.
I just commented on a blog. I'm sure there is some validity to his post beyond observing that Agile Scrum is broken. It certainly is not what it was originally intended but for…

eGalax touch on default Ubuntu 14.04.2 LTS

I have not had success with the touch drivers as yet.  The touch works and evtest also seems to report events, however, I have noticed that the button click is not working and no matter what I do xinput refuses to configure the buttons correctly.  When I downgraded to ubuntu 10.04 LTS everything sort of worked... there must have been something in the kermel as 10.04 was in the 2.6 kernel and 4.04 is in the 3.x branch.

One thing ... all of the documentation pointed to the wrong website or one in Taiwanese. I was finally able to locate the drivers again: (it would have been nice if they provided the install instructions in text rather than PDF)
Please open the document "EETI_eGTouch_Programming_Guide" under the Guide directory, and follow the Guidline to install driver.
download the appropriate versionunzip the fileread the programming manual And from that I'm distilling to the following: execute the answer all of the questio…