DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 10 of 10

Thread: DB Design for hierarchial data

Hybrid View

  1. #1
    Hardy Cherry Guest

    DB Design for hierarchial data


    I am looking for suggestions on a db design for hierarchial data like an organization
    chart or a chart for a large company showing the top organization and all
    the subsidiaries. I need to account for an unknown number of levels. I
    need to find the top level parent from any place in the tree. And I need
    to be able to navigate up or down the hierarchy. Anyone have a design that
    does that they like?

  2. #2
    Craig Brown Guest

    Re: DB Design for hierarchial data


    Hardy Cherry,

    I would think that if you carried the "Parent" or next higher level on each
    record, you could navigate your way up, down or across the structure. The
    real parent row would just have a blank parent field.

    Craig Brown

    "Hardy Cherry" <hardy.cherry@gecapital.com> wrote:
    >
    >I am looking for suggestions on a db design for hierarchial data like an

    organization
    >chart or a chart for a large company showing the top organization and all
    >the subsidiaries. I need to account for an unknown number of levels. I
    >need to find the top level parent from any place in the tree. And I need
    >to be able to navigate up or down the hierarchy. Anyone have a design that
    >does that they like?



  3. #3
    Rob Guest

    Re: DB Design for hierarchial data


    How do you implement this though? Would one field (manager) refer to another
    field (employee) in the same database?

    table layout
    ------------
    EmployeeID
    EmployeeFirstName
    Manager <-- refer to another EmployeeID record??
    ------------

    Thanks,
    Rob



    "Craig Brown" <brown.c3@aetna.com> wrote:
    >
    >Hardy Cherry,
    >
    >I would think that if you carried the "Parent" or next higher level on each
    >record, you could navigate your way up, down or across the structure. The
    >real parent row would just have a blank parent field.
    >
    >Craig Brown
    >
    >"Hardy Cherry" <hardy.cherry@gecapital.com> wrote:
    >>
    >>I am looking for suggestions on a db design for hierarchial data like an

    >organization
    >>chart or a chart for a large company showing the top organization and all
    >>the subsidiaries. I need to account for an unknown number of levels.

    I
    >>need to find the top level parent from any place in the tree. And I need
    >>to be able to navigate up or down the hierarchy. Anyone have a design

    that
    >>does that they like?

    >



  4. #4
    Arthur Wood Guest

    Re: DB Design for hierarchial data


    Rob,
    Exactly. When you first create the record, Manager = 0. If this is the
    top of the Organization then Manager will remain 0. However, for those employees
    who report to A manager, their Manager field would be set to the ID of the
    Existing Employee record for thier manager.

    Take a look at the Employees table in the Northwind.mdb sample database that
    ships with Access. Here this is implemented in the ReportsTo field in the
    Employees table.


    Arthur Wood

    "Rob" <rob_wilbanks@yahoo.com> wrote:
    >
    >How do you implement this though? Would one field (manager) refer to another
    >field (employee) in the same database?
    >
    >table layout
    >------------
    >EmployeeID
    >EmployeeFirstName
    >Manager <-- refer to another EmployeeID record??
    >------------
    >
    >Thanks,
    >Rob
    >
    >
    >
    >"Craig Brown" <brown.c3@aetna.com> wrote:
    >>
    >>Hardy Cherry,
    >>
    >>I would think that if you carried the "Parent" or next higher level on

    each
    >>record, you could navigate your way up, down or across the structure.

    The
    >>real parent row would just have a blank parent field.
    >>
    >>Craig Brown
    >>
    >>"Hardy Cherry" <hardy.cherry@gecapital.com> wrote:
    >>>
    >>>I am looking for suggestions on a db design for hierarchial data like

    an
    >>organization
    >>>chart or a chart for a large company showing the top organization and

    all
    >>>the subsidiaries. I need to account for an unknown number of levels.


    >I
    >>>need to find the top level parent from any place in the tree. And I need
    >>>to be able to navigate up or down the hierarchy. Anyone have a design

    >that
    >>>does that they like?

    >>

    >



  5. #5
    Barry Guest

    Re: DB Design for hierarchial data


    "Hardy Cherry" <hardy.cherry@gecapital.com> wrote:
    >
    >I am looking for suggestions on a db design for hierarchial data like an

    organization
    >chart or a chart for a large company showing the top organization and all
    >the subsidiaries. I need to account for an unknown number of levels. I
    >need to find the top level parent from any place in the tree. And I need
    >to be able to navigate up or down the hierarchy. Anyone have a design that
    >does that they like?


    You could try:

    Parent_Company
    Holding_Company
    Subsidiary_Key

    Just think about the different business units, and lawyers the company has.
    Divide up the lawyers and the should be one Business Unit for every three
    lawyers,

    Make three instances for each Busines Unit, and you will have the database
    you want.

    Sorry for the metephores



  6. #6
    Dennis Guest

    Re: DB Design for hierarchial data


    Here's a specific example of the table:

    CREATE TABLE OrgChart (
    OrgID int NOT NULL ,
    Name] varchar (50) NOT NULL ,
    ParentID int NULL
    ) ON [PRIMARY]

    ALTER TABLE OrgChart WITH NOCHECK ADD
    CONSTRAINT PK_OrgChart PRIMARY KEY CLUSTERED
    ( OrgID ) ON [PRIMARY]

    ALTER TABLE OrgChart ADD
    CONSTRAINT FK_OrgChart_OrgChart FOREIGN KEY
    ( ParentID ) REFERENCES OrgChart ( OrgID )

    In data modeling terms, this is a "fishhook". The ParentID in one row references
    the OrgID in another. The top-level row has a NULL ParentID. You can add
    data to the table. Just make sure that you add rows from the top of the organization
    down so the ParentID values will be valid.

    Now you create a recursive stored procedure:

    CREATE PROCEDURE GetParent @StartID int, @TopID int OUTPUT, @TopName varchar(50)
    OUTPUT
    AS

    DECLARE @ParentID int

    SELECT @TopID = OrgID, @TopName = Name, @ParentID = ParentID
    FROM OrgChart
    WHERE OrgID = @StartID

    IF @ParentID IS NOT NULL
    EXECUTE GetParent @ParentID, @TopID OUTPUT, @TopName OUTPUT

    This stored procedure will call itself until it gets to the top of the hierarchy
    and ParentID is NULL.

    To use the stored procedure, use something like the following:

    DECLARE @ID int
    DECLARE @Name varchar(50)

    EXEC GetParent (SomeOrgIDValue), @ID output, @Name output

    PRINT @ID
    PRINT @Name

    You'll get the top-level ID and Name.

    There are enhancements that can be easily made for specific levels or relative
    level numbers.

    Dennis

    "Hardy Cherry" <hardy.cherry@gecapital.com> wrote:
    >
    >I am looking for suggestions on a db design for hierarchial data like an

    organization
    >chart or a chart for a large company showing the top organization and all
    >the subsidiaries. I need to account for an unknown number of levels. I
    >need to find the top level parent from any place in the tree. And I need
    >to be able to navigate up or down the hierarchy. Anyone have a design that
    >does that they like?



  7. #7
    Joel Scavone Guest

    Re: DB Design for hierarchial data


    This can get very complex.

    Joe Celko covers the issues in "SQL for Smarties"-- I recommend any SQL developer
    have it anyway.

    You need to associate a parentID with a childID in a very particular manner.
    If this is mission critical to you, and Celko doesn't help, email me and
    I'll let you know what we did.

    "Hardy Cherry" <hardy.cherry@gecapital.com> wrote:
    >
    >I am looking for suggestions on a db design for hierarchial data like an

    organization
    >chart or a chart for a large company showing the top organization and all
    >the subsidiaries. I need to account for an unknown number of levels. I
    >need to find the top level parent from any place in the tree. And I need
    >to be able to navigate up or down the hierarchy. Anyone have a design that
    >does that they like?



  8. #8
    Kristoffer Edvinsson Guest

    Re: DB Design for hierarchial data


    "Hardy Cherry" <hardy.cherry@gecapital.com> wrote:
    >
    >I am looking for suggestions on a db design for hierarchial data like an

    organization
    >chart or a chart for a large company showing the top organization and all
    >the subsidiaries. I need to account for an unknown number of levels. I
    >need to find the top level parent from any place in the tree. And I need
    >to be able to navigate up or down the hierarchy. Anyone have a design that
    >does that they like?


    Hi!

    I have read the previous responses to your question and have a somewhat different
    suggestion.

    Havin one field in a table be related to another field in the same table
    is not always as clear as one would like it to be, at least if you're not
    a DB expert. It's also a question of how you would like to model your data.
    Using the 'one-table' approach, you kind of associate the manager with the
    employee - a down-up kind of approach, if you get what I mean. Sometimes
    it is more logical to have an up-down relation (phrasing not used in strict
    relational DB meaning). To clarify: would you like the information about
    who is managing a certain employee to go with the employee managed, or do
    you prefer to model your data by who the manager manages? Get what I'm after?

    If you go for the second approach, you are going to need two tables:


    TABLE 1
    ----------------------
    TABLE NAME: employee
    ----------------------
    employee_id
    ----------------------


    TABLE 2
    ----------------------
    TABLE NAME: employee_managed_employees
    ----------------------
    manager_id
    managed_employee_id
    ----------------------


    In table 2, both fields refer to the employee_id field of table 1 with, I
    think, obvious meanings. The downsode of this approach however, is that you
    might face a relational-integrity or buisness-rule violation problem since
    it is possible for one employee to manage him/her-self. On the other hand,
    I definitely can think of circumstances under which this is desirable.

    Hope this helps
    /Kristoffer

  9. #9
    Pascal MESSAGER Guest

    Re: DB Design for hierarchial data


    What is the limit of recursion for sql server ? I'm afraid it's only 32 nested
    proc (see BOL)

    Pascal MESSAGER


    "Dennis" <DennisRehm@AppliedComputing.net> wrote:
    >
    >Here's a specific example of the table:
    >
    >CREATE TABLE OrgChart (
    > OrgID int NOT NULL ,
    > Name] varchar (50) NOT NULL ,
    > ParentID int NULL
    >) ON [PRIMARY]
    >
    >ALTER TABLE OrgChart WITH NOCHECK ADD
    > CONSTRAINT PK_OrgChart PRIMARY KEY CLUSTERED
    > ( OrgID ) ON [PRIMARY]
    >
    >ALTER TABLE OrgChart ADD
    > CONSTRAINT FK_OrgChart_OrgChart FOREIGN KEY
    > ( ParentID ) REFERENCES OrgChart ( OrgID )
    >
    >In data modeling terms, this is a "fishhook". The ParentID in one row references
    >the OrgID in another. The top-level row has a NULL ParentID. You can add
    >data to the table. Just make sure that you add rows from the top of the

    organization
    >down so the ParentID values will be valid.
    >
    >Now you create a recursive stored procedure:
    >
    >CREATE PROCEDURE GetParent @StartID int, @TopID int OUTPUT, @TopName varchar(50)
    >OUTPUT
    > AS
    >
    >DECLARE @ParentID int
    >
    >SELECT @TopID = OrgID, @TopName = Name, @ParentID = ParentID
    >FROM OrgChart
    >WHERE OrgID = @StartID
    >
    >IF @ParentID IS NOT NULL
    > EXECUTE GetParent @ParentID, @TopID OUTPUT, @TopName OUTPUT
    >
    >This stored procedure will call itself until it gets to the top of the hierarchy
    >and ParentID is NULL.
    >
    >To use the stored procedure, use something like the following:
    >
    >DECLARE @ID int
    >DECLARE @Name varchar(50)
    >
    >EXEC GetParent (SomeOrgIDValue), @ID output, @Name output
    >
    >PRINT @ID
    >PRINT @Name
    >
    >You'll get the top-level ID and Name.
    >
    >There are enhancements that can be easily made for specific levels or relative
    >level numbers.
    >
    >Dennis
    >



  10. #10
    Adrian Shaw Guest

    Re: DB Design for hierarchial data


    "Kristoffer Edvinsson" <kristoffer.edvinsson@swipnet.se> wrote:
    >
    >"Hardy Cherry" <hardy.cherry@gecapital.com> wrote:
    >>
    >>I am looking for suggestions on a db design for hierarchial data like an

    >organization
    >>chart or a chart for a large company showing the top organization and all
    >>the subsidiaries. I need to account for an unknown number of levels.

    I
    >>need to find the top level parent from any place in the tree. And I need
    >>to be able to navigate up or down the hierarchy. Anyone have a design

    that
    >>does that they like?

    >


    Well,

    There are several possibilities, two outlined in the other two responses.
    It is an interesting problem that relational databases do not handle very
    naturally. I came across this article by Steve Celko, DBMS Magazine (can't
    exactly remember when/where). Think of each node as a circle. Children of
    the node would be contained in that circle and the parent of the node would
    be contained in a larger circle. Think of this visual picture in terms of
    numerical ranges then we can construct a table to store information about
    each node:

    Table: tree


    id Description Left Right
    ---- ------------- ------- -------
    1 Root 1 10
    2 1st Gen 2 7
    3 2nd Gen 3 4
    4 2nd Gen 5 6
    5 1st Gen 8 9

    A node is defined as having a set values (its children), from 'left' to 'right'.
    The root node has the largest defined set, 1 through 10 because, in our model,
    it contains all the nodes. '1st Gen' nodes are sub sets of the root node,
    2-7 and 8-9. Notice that leaf nodes have the property that left+1=right
    and that no range limits are ever duplicated.

    This structure allows for nice, pretty queries. However, there is an ordering
    restriction imposed on the ranges that makes insertion into the tree less
    than pretty. (adding a child would cause all indices to shift)

    However, if it IS an org chart you are modelling, then additions and deletions
    will not be too common. I suppose that you could pull this data out of the
    database, handle it in some nice fashion in your application (using some
    nice tree API) and dump an update when changes are made. Notice that if you
    delete the second listed node, its children remain descendents of the root.
    Whereas if you use the adjacency list model (as a table with emp and boss
    fields) if you deleted an emp, all employees under him would be lost.

    Some sample queries from our table, tree:

    Get all descendents of a node, mynode:

    SELECT child.id
    FROM tree AS parent, tree AS child
    WHERE child.left between parent.left and parent.right
    AND parent.id = mynode

    Get the hierarchy level for each node:

    SELECT COUNT(parent.id) AS indentation, child.id
    FROM tree AS child, tree AS parent
    WHERE child.left BETWEEN parent.left AND parent.right
    GROUP BY child.id

    HAVE FUN

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center