Re: Representing Tree strcuture in database

Tech Tip: Click here to run a free scan for Windows Errors and optimize PC performance

From: Tore Bostrup (newspost_at_bostrup.us)
Date: 04/04/04 

Date: Sun, 4 Apr 2004 11:41:44 -0400

There are basically three common models:

* Adjacency List model
Each row contains a column with a column containing the primary key of its
parent. Self-joins are used to obtain children of a parent.

* Nested Set model
Each row contains two columns - left and right - which contain the "outer
edges" of left and right columns in its subtree. This allows performing all
"whole subtree" operations with standard SQL Statements without the need for
a cursor. Think of it as collapsing the tree structure onto a line
underneath it, marking the edges of each node/subtree.

* Materialized Path model
Each row contains a column with a "path" that describes its position in the
tree structure.

The Adjacency List model - while maybe easier to grasp - does not allow
"whole subtree" operations without the use of a cursor. It is fine if you
are always simply looking at immediate parent/child relationships, or deal
with a small, fixed number of levels in the tree.

If your use is primarily for creating a treeview presentation, this is
probably a good choice.

The Nested Set model may seem a bit difficult at first - but once you grasp
it - it really isn't that hard. If you need to perform frequent or high
performance queries against subtrees (of unknown levels of depth), this is
the way to go. Modifications that affect the tree structure (inserting and
deleting rows, for instance), *may* require updating a significant number of
rows.

The Path model is less common, and somewhat de-normalized, but can be useful
when the tree structure has an unknown, but reasonably limited depth, and
"whole subtree" operations are required. This may be useful if the
repesentation matches something that uses a path structure anyway.

For more information, Google for [Trees in SQL], [Model Trees in SQL], [Path
Trees in SQL], [Nested Set Model], or [Adjacency List Model] and
combinations or variations of those.

HTH,
Tore.

"Lourdhu" <anonymous@discussions.microsoft.com> wrote in message
news:4834157A-70C4-4AA4-946E-13FB6AE83352@microsoft.com...
> hi all,
>
> can any one help me how to represent tree strcuture in relational
database in form of table(s) ?
>
>
> advanced thanks
> with regards

Relevant Pages

  • Re: Joe Celkos work with nested set models - update times??
    ... your upcoming book, but I can't wait until April to make the initial ... with a childless parent having ... > 3) Given a clustered index on the tree structure, ... > a tree structure in the adjacency list model (no cycles when the new ...
    (microsoft.public.sqlserver.programming)
  • Re: Joe Celkos work with nested set models - update times??
    ... This seems to be the downside to the nested set model. ... >1) Sibling are added to the right side of their parent, ... >3) Given a clustered index on the tree structure, ... >a tree structure in the adjacency list model (no cycles when the new ...
    (microsoft.public.sqlserver.programming)
  • Re: Searching in tree structures
    ... content is represented in a tree structure maintained in a database, ... tree and look at it's root node. ... The other solution is to, in addition to the parent node, also store ... the root node in the database. ...
    (comp.lang.php)
  • Creating Tree Structure from associative array
    ... I have an associative array, which contains parent and child relationships. ... I've searched the web for creating a tree structure from this and found a few good sites but doesnt help 100% perhaps someone can point me in the correct direction? ...
    (php.general)
  • Re: Database suggestion
    ... i.e. Can 11 have only one "parent" or multiple? ... If it can only have one parent, then I'd suggest using the structure ... tree structure is out of the window, so I'd suggest a simple string key, ... ...will INSERT new entries and UPDATE existing entries in one swoop. ...
    (comp.lang.php)