Re: Using Materialized Path to create a paths table

From: David Cressey <dcressey_at_verizon.net>
Date: Thu, 25 May 2006 13:51:01 GMT
Message-ID: <9Didg.1582$au4.87_at_trndny08>


"Matthew Brealey" <thelawnet_at_gmail.com> wrote in message news:1148564515.778519.28270_at_y43g2000cwc.googlegroups.com...
> I wonder if anyone has any thoughts on using the materialized path as
> an intermediate step to create a kind of paths table to represent a
> tree hierarchy
>
> Here are some records
>
> EmployeeId ParentEmployeeId MaterializedPath
> 1 <null> 1.
> 2 1 1.1.
> 3 1 1.2.
> 4 2 1.1.1
>
> etc.
>
> To find the descendants of a node using the materialized path is quite
> low-cost: an index on MaterializedPath would be usable with the
> following query
>
> select
> Descendant.EmployeeId
> from Employee as Ancestor
> inner join Employee as Descendant on Descendant.MaterializedPath like
> Ancestor.MaterializedPath + '%'
> where Ancestor.EmployeeId = 1
>
> To find the ancestors however with the following query
>
> select
> Ancestor.EmployeeId
> from Employee as Descendant
> inner join Employee as Ancestor on Descendant.MaterializedPath like
> Ancestor.MaterializedPath + '%'
> where Descendant.EmployeeId = 4
>
> requires a table scan.
>
> This is very expensive for any non-trivial number of nodes where you
> need to find a node's ancestors.
>
> But if you treat the MaterializedPath as an intermediate result, it is
> a trival to use it to build a denormalized EmployeeAncestor table,
> which for the set of data above would be as follows
>
> EmployeeId AncestorEmployeeId
> 1 1
> 2 1
> 2 2
> 3 1
> 3 2
> 4 1
> 4 2
> 4 4
>
> I.e. there is one record for each of each node's ancestors (including
> the node itself)
>
> This table is easy to maintain using the same trigger tha maintains the
> MaterializedPath (although not so easy if you did not maintain the
> MaterializedPath itself)
>
> The advantage is that it becomes very much cheaper to calculate the
> ancestors of a node:
>
> select
> Ancestor.EmployeeId
> from
> EmployeeAncestor Descendant
> inner join Employee Ancestor on Ancestor.EmployeeId =
> Descendant.AncestorEmployeeId
> where Descendant.EmployeeId = 4
>
> The query to find descendant is similar:
>
> select
> Descendant.EmployeeId
> from
> Employee Ancestor
> inner join EmployeeAncestor Descendant on Descendant.AncestorEmployeeId
> = Ancestor.EmployeeId
> where Ancestor.EmployeeId = 1
>
> So it seems to me that the materialized path is not actually a good
> thing to use to find ancestor/descendant relationships of itself, but
> by using it to create a simple ancestor node-type table, you can get
> slightly better performance for finding descendants, and vastly better
> performance results for ancestors.
>
> Any comments?
>

I'd like to see this compared to the nested sets technique. Received on Thu May 25 2006 - 15:51:01 CEST

Original text of this message