Hi,

In the literature for nested sets, a commonly described operation is:
given a node, find the path from the root to this node. I wish to find
the most efficient way to do the inverse operation -- given a path,
find the node. Is there a more efficient way of doing this than the
naive approach of walking the path oneself (i.e. multiple queries to
the database)?

Thanks,
Hamish

On 22 Apr, 01:48, Hamish <ham... (AT) gmail (DOT) com> wrote:
I assume you are looking for a leaf node in a set of nodes? If the
tree is consistent it should be sufficient to find the node with min
(rgt) or max(lft) among those nodes.


/Lennart

"Hamish" <hamish (AT) gmail (DOT) com> wrote

If you build your nested sets in the traditional way, the criterion "where
rgt = lft +1" will select leaf nodes, and only leaf nodes.
If the path you have been given is a set of nodes with only one leaf, this
criterion will select it.

On Apr 22, 8:02*pm, "Walter Mitty" <wami... (AT) verizon (DOT) net> wrote:
Sorry, I didn't explain myself at all well. Let me try again.

Given a path of node labels, which may not be unique and which may not
end at a leaf node, what is the most efficient way of arriving at the
last node in the path?

E.g. the node for '/usr/local/bin' in a filesystem containing '/usr/
bin' and '/usr/local/bin/git'

(Also, I'm hoping to use Dan Hazel's rational numbers keying method
(http://arxiv.org/pdf/0806.3115v1), so I can't assume that leaves have
rgt=lft+1.)

Thanks,
Hamish