Have you extended nested sets for hierarchical data modeling involving multiple parent nodes for a child node? What are your experiences?

Question

I am looking to use this concept in one of my upcoming project.

More info: Managing Hierarchical Data in MySQL.

Please share your experiences good or bad with examples.

I am adding more information to make it more broad:

I have child items that can have more than one parent (example: a user can belong to city and also a group called UserDefinedRegion), which the typical hierarchical models do not support, whether it is adjacency list or nested sets.

I am pasting the use case here for clarity:

---

Background: Currently the system has a fixed hierarchy in place which is State->County->City->User

1. Sales Manager logs in to the system and creates a new group which can by at the same level as City, or County.

2. Sales Manager logs in to the system and creates a new group which can be in between State and county or County and City.

3. Once the sales manager creates the groups, he should be able to view all the necessary reports rolled up the next day in his dashboard.

---

As you can see, second point can easily be accomplished by nested sets, but not the first point, which will introduce new parents nodes for the same child node.

So far the following solutions were proposed by stackOverflow users:

1. Network Node structure supported by Network Database.
2. Directed Acyclic graphs.

I am definitely looking for a RDBMS solution. It looks like not many have encountered multiple parent nodes in heirarchical data models in real life.

Piffle

Good question, I'd like to know that too. Mostly I just use strings formatted like "1.3.4" and then select using LIKE '1.3.%'. I find it more intuitive, but clearly this isn't optimal. – Travesty

I changed the title of your question because you certainly don't want to know how many have used hierarchical data modeling but you want ppl to share experiences with you in case they have. – Whacky

...and your question is pretty much a duplicate: #39301 – Whacky

Hi Tharkun, Actually this is second part of my own question #762978 I pretty much know that in my scenario, nested sets make sense. I want to reach out to community to see if there are any disadvantages with my choice. I also want to draw on other's experiences with using nested sets. I already picked up Joe Celko's book to gain more understanding. – Piffle

Either the heading or the description needs to get changed, you can't have multiple parents in the nested set model AFAIK. – Portuguese

ok, seems you just needed to make your point more clear. Interesting question... and tricky. – Whacky

definitely tricky, but feel that this could have already been solved by somebody – Piffle

Multiple parents means it's not a hierarchy but rather a directed graph. (presumably a directed acyclic graph) The answer given by @Portuguese is a pretty decent one. – Baguio

Answer 1

As you will probably be using stored procedures for some operations, make sure that they really perform well enough for your needs! This could be a problem if you use MySQL, in my experience.

Regarding the new requirement (multiple parents): You are now into much more problematic stuff when using a RDBMS, depending on what kind of queries you need to run against the data. I compared the RDBMS approach to using a graph database on this wiki page. If you are only interested in the RDBMS approach, take a look at A Model to Represent Directed Acyclic Graphs (DAG) on SQL Databases.

Portuguese

I am stuck with RDBMS as it is a legacy application and I am tasked with extending it to suit new requirements. I cannot isolate my heirarchy into a seperate graph database or a network database as le dorfier mentioned below. – Piffle

Answer 2

Your requirement for multiple parents immediately violates the fundamental nature of nested sets, as pointed out in your referenced article, so I'd say you're headed for trouble to start with. Since you'll be using a relational database, which (using it's core capabilties) will handle everything you've described so far, I think just working in that conceptual framework and polishing your skills will provide everything you need, without adding additional abstractions that (at least in this case) don't add any value.

If you still want to go there, I'd call this a networked node structure. Here's a reference.

Vanadinite

You are right, having multiple parents does violate the nested sets. Unfortunately that is a use case. Ability to let business users define custom groups (add new nodes in the heirarchy), which will eventually make a user not only tie to a city, but also a custom sales region. I was thining if I can extend nested set to accomodate this behavior. – Piffle

Isn't every city a child of a region? – Whacky

I'm having a hard time tracking your design process. Before there were relational databases there were network database products (acyclical graphs) and hierarchical databases; and one of the selling points about the relational model was that you didn't need to map your problem domain into anything else first; it gets too complicated. Can you describe your problem domain without trying to encapsulate it into a complete generalized abstraction first? Or directly to a relational abstraction? – Vanadinite

I am not sure what you are asking but we already have a database in place. We use MySQL. I am just summarizing the answers I received so far under my question description. Do not be confused by that. – Piffle