Home > Archive > Software Engineering > May 2006 > Mapping Hierarchical data to relational data structure
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Mapping Hierarchical data to relational data structure
|
|
|
| Hi folks,
I'll give an example of what I'm looking for.
Imagine the MSDN (MS Tech Site) website, it has a "Treeview" control that
maps directly a hierarchical website map.
Imagine the same feature mapped to a hierarchical index - an index that is
used to maintain string literals from several applications.
i.e.
GROUP-A
-LEAF-1 - some application string 1
-LEAF-2 - some application string 2
-------GROUP-1A
-LEAFNODE-3 - some application string 3
---------------GROUP-2A
-LEAFNODE-4
GROUP-B
etc...
Using XML it is very simple to create (and maintain) such a data structure,
unfortunatly I would like to use a Relational DB :-/
My proposed method involves the following schema using two tables
T_GROUPS
==========
GROUP_Id (sequence)
GROUP_Name
GROUP_Parent (link to Group_Id)
T_NODES
=======
NODE_Id (sequence)
NODE_Name
NODE_Content
GROUP_Id (many Node_Id's to 1 Group_id)
But this seems kinda clumsy. Is there a more elegant way of dong the above
- must be able to add/delete/edit new groups and leafnodes without changing
the DB schema.
(I want to be able to bind the data to a treeview)
Any thoughts?
| |
| davout 2006-05-08, 4:05 am |
| A lot of hierarchical systems presume an orderly tree, like....
Continent
|--- Country
|--- Region
|--- City
An orderly tree assues the echerlons as shown below alwasy appear in that
order, but the real world isn't necessarily as neat and tidy as this.
Personally I think it's necessary to keep the tree content discrete from the
tree structure. Also you have to allow for the fact that some child nodes
can have multiple parents, and that a hierarchy can have mutiple top level
nodes.
The messy hierarchy is the opposite of an orderly, and allows nodes of any
type to appear at any level.
hier_node
============
NodeId (sequence)
ParentNodeId (the 'NodeID' of the parent or '-1' if its a top level node)
DataType (a code to represent entity type - country, region, city)
DataID (the entity id)
You can use a select 'union' retrieval to retrieve data from all of the
contributing entity tables.
"Adie" <adie@oh-XXXX.com> wrote in message
news:dd2dj9okahsp$.dlg@oh-XXXX.com...
> Hi folks,
>
> I'll give an example of what I'm looking for.
>
> Imagine the MSDN (MS Tech Site) website, it has a "Treeview" control that
> maps directly a hierarchical website map.
>
> Imagine the same feature mapped to a hierarchical index - an index that is
> used to maintain string literals from several applications.
>
> i.e.
>
> GROUP-A
> -LEAF-1 - some application string 1
> -LEAF-2 - some application string 2
> -------GROUP-1A
> -LEAFNODE-3 - some application string 3
> ---------------GROUP-2A
> -LEAFNODE-4
> GROUP-B
> etc...
>
> Using XML it is very simple to create (and maintain) such a data
> structure,
> unfortunatly I would like to use a Relational DB :-/
>
> My proposed method involves the following schema using two tables
>
> T_GROUPS
> ==========
> GROUP_Id (sequence)
> GROUP_Name
> GROUP_Parent (link to Group_Id)
>
> T_NODES
> =======
> NODE_Id (sequence)
> NODE_Name
> NODE_Content
> GROUP_Id (many Node_Id's to 1 Group_id)
>
> But this seems kinda clumsy. Is there a more elegant way of dong the above
> - must be able to add/delete/edit new groups and leafnodes without
> changing
> the DB schema.
>
> (I want to be able to bind the data to a treeview)
>
> Any thoughts?
| |
| H. S. Lahman 2006-05-10, 7:03 pm |
| Responding to Adie...
> Hi folks,
>
> I'll give an example of what I'm looking for.
>
> Imagine the MSDN (MS Tech Site) website, it has a "Treeview" control that
> maps directly a hierarchical website map.
>
> Imagine the same feature mapped to a hierarchical index - an index that is
> used to maintain string literals from several applications.
>
> i.e.
>
> GROUP-A
> -LEAF-1 - some application string 1
> -LEAF-2 - some application string 2
> -------GROUP-1A
> -LEAFNODE-3 - some application string 3
> ---------------GROUP-2A
> -LEAFNODE-4
> GROUP-B
> etc...
>
> Using XML it is very simple to create (and maintain) such a data structure,
> unfortunatly I would like to use a Relational DB :-/
Any hierarchy can be described as simply:
0..1 child of
[Node] --------------+
| 0..* |
| parent of | R1
| |
+-----------------+
IOW, it is just a matter of constructing relationships. Substitute Node
-> Group as a table name and all you need to do is assign the
referential attributes correctly.
In your case things are somewhat more complicated because additional
entries are associated with each Group. But that can easily be
accommodated in the RDB schema:
[Node]
| *
| contains
|
| R2 <<ordered>>
|
| 1 0..1 child of
[Group] -------------+
| 0..* |
| parent of | R1
| |
+-----------------+
That is pretty much what you already described below. It is pretty
standard...
>
> My proposed method involves the following schema using two tables
>
> T_GROUPS
> ==========
> GROUP_Id (sequence)
> GROUP_Name
> GROUP_Parent (link to Group_Id)
This is the main tree. The Parent referential attribute provides
sufficient linking for an RDB. However, you need some way to find the
root T_GROUP tuple without an expensive search. Typically that is done
by defining a table for the whole tree, T_TREE:
T_TREE
==============
TREE_Name
GROUP_root (link to GROUP_Id for the root group)
The T_TREE table would contain only one tuple unless you intend to
define multiple XML trees.
>
> T_NODES
> =======
> NODE_Id (sequence)
> NODE_Name
> NODE_Content
> GROUP_Id (many Node_Id's to 1 Group_id)
>
> But this seems kinda clumsy. Is there a more elegant way of dong the above
> - must be able to add/delete/edit new groups and leafnodes without changing
> the DB schema.
Why clumsy? It is actually a pretty elegant way to represent a complex
structure so that the structure is easily modified. Adding and deleting
groups and nodes is just a matter of adding/removing tuples and
tinkering with referential attribute values. No schema changes are
required.
The only thing that is clumsy is that it is difficult to write a query
to to do the navigation because of the reflexive relationship. That is,
SQL isn't very good at "walking" structures like this in a single query.
So there is an RDB performance issue around reading one tuple at a
time. But since this is your datastructure you can get cute with the
Group and Node IDs. For example, if you assign GroupID as sequential
numbers and NodeID as {GroupID, relative entry number}, then you can
probably read the whole table as a dataset and "walk" it efficiently
yourself.
[Note the the notion of T_TREE is actually much more useful at the
application level because one can assign responsibilities for navigating
the tree to that object. That would include add/delete/edit access.
IOW, Tree is the helper class for navigation.]
*************
There is nothing wrong with me that could
not be cured by a capful of Drano.
H. S. Lahman
hsl@pathfindermda.com
Pathfinder Solutions -- Put MDA to Work
http://www.pathfindermda.com
blog: http://pathfinderpeople.blogs.com/hslahman
Pathfinder is hiring:
http://www.pathfindermda.com/about_us/careers_pos3.php.
(888)OOA-PATH
|
|
|
|
|