Title: Database Hierarchy Structure - Different Node Representation
Tags: mysql;database;database-design;hierarchical-data
Question: I am looking for some feedback/guidance on modeling a hierarchy structure within a relational database.  My requirement states that I need to have a tree structure, where every node within the tree can represent a different type of data.  For example:

Organization

Department 1

Employee 1
Employee 2
Office Equipment 1
Office Equipment 2


Department 1

Team 1


Office Equipment 3



In the example above, Organization, Department, Employee, Office Equipment, and Team could all be different tables within the database and have different properties associated with them.  Additionally, things like Office Equipment may not necessarily be required to be associated to a department - it could be associated to a Team or the Organization.
I have two ideas surrounding modeling this:
The first idea is to have a hierarchy table like below:
```
hierarchys
hierarchy_id (INT, NOT NULL)
parent_hierarchy_id (INT, NOT NULL)
organization_id (INT, NULL)
department_id (INT, NULL)
team_id (INT, NULL)
office_equipment (INT, NULL)
```
In the table above, each of the columns would be a nullable field with a foreign key reference to their respectable table.  The idea would be that only one column from every row would be populated.
My second idea is to have a single table like below:
```
hierarchys
hierarchy_id (INT, NOT NULL)
parent_hierarchy_id (INT, NOT NULL)
type (INT, NOT NULL)
```
In this case, the table above would manage the hierarchy structure, and each &quot;node table&quot; would have a hierarchy_id which would have a foreign key reference back to the hierarchy table (i.e. organizations would have a hierachy_id column). The type column would be a lookup to represent which type node is being represented (i.e. Organization, Employee, etc).
I see pros and cons in both approaches.
Some additional information:

I would like to keep in mind maintainability of this table - there will be additions, deletions, changes, etc.
I will have to display this data on an user interface, which will likely just display an icon to represent the node type, and the name.
I will have to preform some aggregations across the tree for different data requests.
This structure will be backed by a MySQL database.

Does anyone have an experience with a similar scenario?  I have searched quite a bit for information and guidance on this approach, but have not been able to find any information.  I have a feeling there is a specific term for what I am looking for that I am failing to use.
Thank you in advance for the community's help.


Here is the accepted answer: You may want to look into "nested sets".  This is a model for representing subsets of an ordered set by two limits, which we can call "left" and "right".  In this model,  (6,7) is a subset of (5,10) because it is "nested" inside of it.  If you use nested sets together with your design of having a separate table for the hierarchy, you'll end up with four columns in your hierarchy table:  leftID, rightID, ObjectID (an FK), and level.

There is a good description of the nested set model in Wikipedia, which you can view by clicking here.


Here is another answer: I have encountered similar situations throughout different projects, and the approach I've taken in those cases was very similar to your second solution.

I am also a bit biased towards how some Ruby on Rails gems do things, but you can easily figure out how you would implement these techniques with plain SQL and some application logic. So I'm giving you one alternative to your solution:

Using "Multi Table Inheritance" (Implemented in Heritage: https://github.com/dipth/Heritage). In this scenario you would have a ```Node``` table which forms the basis of your hierarchy with:

```Node (id, parent_node_id, heir_type, heir_id)
```

Where the heir_type is the name of the table holding the details for the node (e.g., Organization, Employee, team, etc.), and the heir_id is the id of the object in that table.

Then each type of node would have it's own table and it's own unique id. e.g.:

```Organization(id, name, address)
```

Having the rest of the tables independently from the hierarchy (i.e., strong entities) makes your model more flexible to new additions. Also having a separate table with its own unique id to handle the hierarchy makes it easier to render the hierarchy without having to deal with parent types etc. This model is also more flexible in the sense that one entity can be part of many different branches of the hierarchy (e.g., Employee 1 could be a member of Team 1 and Team 2 at the same time.)

Your solution has one mistake: The ```hierarchys``` is miss-spelled :P JK. The hierarchys table has no unique id. It looks like the unique id is a composite key ```(hierarchy_id, type)```. The ```parent_hierarchy_id``` does not capture the type of the parent and thus it may point to multiple nodes and many inconsistencies.

If you'd like me to elaborate more, let me know.


{'source': 'StackExchangeDataset', 'subset': 'stackoverflow.com', 'metadata': {'AnswerCount': 2, 'CommentCount': 0, 'ContentLicense': 'CC BY-SA 3.0', 'CreationDate': '2014:00:12/15/14', 'FavoriteCount': None, 'PostTypeId': 1, 'Tags': '<mysql><database><database-design><hierarchical-data>', 'Title': 'Database Hierarchy Structure - Different Node Representation', 'ViewCount': 558, 'id': 27485341, 'user_AboutMe': '', 'user_AccountId': 2532780.0, 'user_DisplayName': 'appex', 'user_Reputation': 23.0, 'user_Views': 5.0, 'user_id': 2200705.0}}