Finding a way to store a parent-child-grandson structure

Question

I need to maintain a structure where N parents will have 1 to N children, and each child will have 1 to N children. I would like to save this in db in a way that is relatively efficient and highly extensible without having to change the db schema.

Each parent must be unique, and N parents can have the same child. However, this child may have different children depending on the parent. (clear like dirt?)

It might be easier to describe how parentA can have a male child who has certain attributes (brown hair, brown eyes). the parent also has a male child, but this child has blond hair and blue eyes. I need to store each of these children (men and women) and each attribute (hair and eye color) in a normalized order and bind them in such a way that when I request a parent element, I get them and their child attributes.

I did a bit of work with tree structures and hierarchical structures in SQL, but it’s hard for me to understand this scenario to fit my performance and extensibility requirements. Children and related attributes will be added at regular (if not frequent) intervals. Thank you in advance. I know that clarification is needed.

Additional clarification

Well, it seems like another example might be required. Let me use the good old car example.

CarA and CarB have steering wheels, engines and tires. The CarA steering wheel has a radio control on it. CarB steering wheel no. CarA has a six-cylinder engine, and CarB has an eight-cylinder engine. I need to model the relationship between each car and each function with this attribute. Am I helping at all? -rb

Answer 1

if it is fixed on three levels, and they are conceptually different (as in the extended example), then I think you are confused with the idea of ​​trees where they are not needed. just use tables and relationships, as with any other problem.

• table for parents
• table for children (if they always have exactly two parents, parents can be fields, otherwise you also need a table for relationships).
• an attribute table and another for relations between many and many of them and children [or save them in the children table - see the comment from DForck42 below]

trees are needed where nodes at different levels are "one and the same." but they are not very suitable for sql, so I will not try to use them where they do not seem necessary.

---

update. from your comments below. I think that you say that children are divided into classes or types and that possible attributes depend on the type of child, but that the values ​​of these attributes depend on the parent.

in this case, you have a completely different problem, more similar to OO inheritance. the simplest solution that I see is that you can have a different table for each type of child. then each table has different columns for different attributes. child tables refer to parent tables.

so that you have a parent table with identifiers. then you may have a child table for "admin sites." each row of this child table will refer to the parent through an identifier and contain URL, CSS, etc. in the form of columns. another child type, such as the "database configuration page", will be in another table with a different set of attributes.

if you have common attributes, you can either repeat them in each table or have a "superclass" table.

Such solutions can be quite complex, and I suggest asking another question if you have a clearer explanation of what you want. there's a good explanation of the options here - http://www.sqlalchemy.org/docs/orm/inheritance.html (ignore the parts related to SQLAlchemy and just watch how they use tables differently to inheritance modeling).

Answer 2

As I read your question, you only need five tables.

-> Parent ParentId, Col1, Col2, Col3 -> Child ChildId, Col1, Col2, Col3 -> Grandchild GrandchildId, Col1, Col2, Col3 -> ParentToChild ParentId, ChildId -> ChildToGrandchild ChildId, GrandchildId 

All relations are stored here, and you will need to make restrictions for the required logic; with this implementation, NN relationships are possible for (Parent, Child) and (Child, Grandson).

Answer 3

Well, here is another approach. You only need two tables. The first is where you store all of your “objects” (no matter what they are) that make up your hierarchy:

 ObjectID | ObjectName | ... 

Second relationship table:

 RelID | ParentID | ChildID 

A relationship table may include a constraint that ensures that no object is a child of more than one parent, giving you integrity to a large extent for free.

Moving the table (s) to retrieve the hierarchy can now be difficult, but this can be done using a relatively simple stored procedure. There are two catches. Firstly, all your objects should have the same table and, therefore, the same unique identifiers (ideally). Secondly, how many recursion levels your database supports. In my experience, the 32 levels supported by SQL Server were more than sufficient, for example. However, crawling in code, rather than in the database, can lead to performance degradation.

There are other ways to approach this. If you find Google for database hierarchical data , you will find several, including official CS paper or two.

I have used this method in the past, and I find it simple and quite effective.

Answer 4

What happened to the following approach:

 create Table Persons { PersonID int Primary Key, Name varchar(100), MotherID int {Foreign Key}, FatherID int {Foreign Key} } create Table Attributes { PersonID int {Foreign Key}, AttributeName varchar(10), AttributeValue varchar(10) } 

You will receive all the attributes for the children of this person:

 Select Persons.Name, Attributes.AttributeName, Attributes.AttributeValue From Persons Left Join Atttributes On Persons.PersonID = Attributes.PersonID Where MotherID = @PersonID or FatherID = @PersonID