Sql to find record in a hierarchical chain

[macroapa]

Hi, lets say I have a table with 2 fields:

myTable
Field 1 - ref
Field 2 - parentRef

Now in the structure there could be numerous chains until you get to
the top of the hieratchy (where the ref field = parentRef field).

ie

ref parentRef
111 222
222 333
333 444
444 444

so in this 444 is top of the chain (there will be many other records
as well that are nothing to with 444 and are part of their own
hierarchy). So how do I easily relate 111 to 444. Ie how do i find
the ultimate top parent for a given 'ref' field.

Hope anyone can give me some pointers (and the above makes sense!!!)

Thanks.

 

[macroapa]

Hi, lets say I have a table with 2 fields:

myTable
Field 1 - ref
Field 2 - parentRef

Now in the structure there could be numerous chains until you get to
the top of the hieratchy (where the ref field = parentRef field).

ie

ref    parentRef
111  222
222  333
333  444
444  444

so in this 444 is top of the chain (there will be many other records
as well that are nothing to with 444 and are part of their own
hierarchy).  So how do I easily relate 111 to 444.  Ie how do i find
the ultimate top parent for a given 'ref' field.

Hope anyone can give me some pointers (and the above makes sense!!!)

Thanks.

Ps I should say that the number of chains in the hierarchy can be
different.

 

[Dorian]

That's a very tricky one.
I have a similar setup which I maintain via a tree view. However, my design
has a maximum of 3 levels.
If you have a maximum number of levels, you can write a query that
'flattens' the table, so you get:
parent1 child1 child2 child3
parent2 child1 child2 etc. etc.
with every possible chain in a separate row.
In my application, every time the tree view is changed I automatically
regenerate the 'flat' the table and from then on always use the flattened
table. The other table is only used in maintaining the tree view.
-- Dorian
"Give someone a fish and they eat for a day; teach someone to fish and they
eat for a lifetime".

 

[macroapa]

hmmm, yep. Problem I've got is that the number of child's could be
unlimited in theory. I may just have to build the flattened one for
say 20 and hope for the best.

 

[Sylvain Lafontaine]

WIth this design, you must either walk the tree or use a combination of left
join if the number of hierarchical levels is not to high.

Usually, the best solution for this kind of problem is to add a field in the
same table or into another one to flatten the hierarchy. For example, if
you add the separator . :

ref parentRef Hierarchy
111 222 .444.333.222.111.
222 333 .444.333.222.
333 444 .444.333.
444 444 .444.

Notice that I've added the separator both at the beginning and at the end of
the new field; in order to facilate the construction of searching terms.
This way, you can not only find which is the ultimate parent of any field
but for example, you can easily find things such as who are all the children
of any given node.

The drawback of this method is that you need some more or less complicated
code to adjust the hierarchy when you are bringing changes. The easiest way
is often to simply rebuild it completely each time.

The usual way of doing this is first to store Null instead of 444 when you
are at the top:

444 Null

This is not really necessary but it's a convention. After initialising the
process by setting the field Hierarchy to Null for every record, you can
start the trees by updating all records where the ParentId is null - or
where the ParentId is the same as the TableID as in your case. Second, you
process every record which have a ParendId where the Hierarchy field is not
Null; this build the second level. All you have to do is to add the
Hierarchy value of the Parent to each of its child. (By convention, a child
is a direct child: directly on the first level below and excluding all the
other descendants further below like a grand-child, a grand-grand-child,
etc. while a descendant is a "child" at any level below.). After that, you
keep going until your table is full.

--
Sylvain Lafontaine, ing.
MVP - Windows Live Platform
Blog/web site: http://coding-paparazzi.sylvainlafontaine.com
Independent consultant and remote programming for Access and SQL-Server
(French)

 

[Dorian]

Good luck.
I used a separate query for each level and then a UNION query to join them
all together.
-- Dorian
"Give someone a fish and they eat for a day; teach someone to fish and they
eat for a lifetime".