Database - store tree like data when nodes have multiple parents

[krwell]

I'm attempting to build a small data application but I'm running into problems on how to store some data. I have some heirarchical data that doesn't fit to the true heirarchical data standards because some nodes have multiple parents. Any ideas on how to do this?

 

[notfred]

And you're trying to store this in a heirarchical database, or a relational database, or something else like an XML file?

 

[KB]

how many generations of nodes are you using in this tree?
If just two levels? That is database terms is a many-to-many relationship. In your case a child node can have one-to-many parents, and a parent can have one-to-many children. Thus you would have tables for the parent nodes, then a second table for child nodes, then a third table for the relationships. Search google for many-to-many for examples.

If more than 2 levels, then I would probebly store it in xml. You could store it in a database using a column for the level and a self-referencing key to the same table to show the parent, but that would get confusing.

 

[krwell]

I'm storing this in a relational database and these will be about up to 8 levels deep.

 

[EagleKeeper]

Originally posted by: krwell
I'm storing this in a relational database and these will be about up to 8 levels deep.

Have a table that has two three fields.

First field is the primary node
Second field is for any parent nodes.
Third field is for any child nodes.

Data relating to the relationship can be in additional fields and/or index into another table.

The combination of the three fields provides a unique record index.

Using this logic, you can find out who the parents of a given node are and what children exist for that given node.

 

[kamper]

Originally posted by: EagleKeeper
Have a table that has two three fields.

First field is the primary node
Second field is for any parent nodes.
Third field is for any child nodes.

Two problems with that:
-putting multiple values in a single field is not a good thing
-duplicating the data about parent/child relationship is a bad idea. What if record A thinks it's the parent of record B but record B doesn't think it's a child of record A?

My suggestion is that you look at this more like a directed graph than a hierarchy, if that's appropriate. Have a table with all the info you need in it but with no information about relationships. Have a second table with two fields called "parent" and "child" and make them foreign keys back to the primary key of the main table. The one problem I see with that is that there's no guarantee against loops, but that's a pretty hard thing to do with a relational database anyway, I think.

 

[EagleKeeper]

Originally posted by: kamper

Originally posted by: EagleKeeper
Have a table that has two three fields.

First field is the primary node
Second field is for any parent nodes.
Third field is for any child nodes.

Two problems with that:
-putting multiple values in a single field is not a good thing
-duplicating the data about parent/child relationship is a bad idea. What if record A thinks it's the parent of record B but record B doesn't think it's a child of record A?

My suggestion is that you look at this more like a directed graph than a hierarchy, if that's appropriate. Have a table with all the info you need in it but with no information about relationships. Have a second table with two fields called "parent" and "child" and make them foreign keys back to the primary key of the main table. The one problem I see with that is that there's no guarantee against loops, but that's a pretty hard thing to do with a relational database anyway, I think.

As you agree, there is no way to prevent an incest relationship or a denial of relationship between the two relatives.

The people impilmenting the database will have to make sure that the rules are follwed by the user or the implimentation.

What you are talking about foriegn keys seems to be juut a differnt sysntax/implimention of my schema option. You end up with 3 keys to create a single unique record. Where that data for that record is stored should become irrelevant.

 

[kamper]

Originally posted by: EagleKeeper
As you agree, there is no way to prevent an incest relationship or a denial of relationship between the two relatives.

Incest no, but denial of relationship is a nobrainer. You either allow nodes to dicate who their parents are or who their children are but not both. Duplicating information is one of the first things every programmer should learn not to do.

The people impilmenting the database will have to make sure that the rules are follwed by the user or the implimentation.

What you are talking about foriegn keys seems to be juut a differnt sysntax/implimention of my schema option. You end up with 3 keys to create a single unique record. Where that data for that record is stored should become irrelevant.

No, it's quite different. The parent/child relationships have nothing to do with primary keys and I don't see why you want to make it part of the key. Where the data for the relationship is stored is very relevant because many-to-one relationships should not be modeled in a single table.