Stop recursive incestuous child parent relationship in mysql

Question

I am programming in PHP / MySQL / Javascript. I have a list of parts which we want to link in a child / parent relationship with no limit on the amount of tiers.

When I am picking from a list of parts to add a child to a parent I limit the list of parts to exclude the parent itself, and any parts which are already children of that parent.

What I have discovered is that I also want to exclude the grandparents of the parent as otherwise we can get an incestuous relationship, which when I display the tree of parts will create an infinite loop.

Not only that but I cannot allow the child part to be a great grandparent of the parent or great great grandparent e.t.c.

Here is the SQL statement I use currently which I think could also be improved by using LEFT JOIN but I am not skillful enough with SQL at this point.

SELECT * 
FROM sch_part_general 
WHERE (sch_part_general.part_id <> $parentId) 
AND (sch_part_general.part_id NOT IN 
  (SELECT part_id FROM sch_part_mapping WHERE parent_id = $parentId)
)

sch_part_general is a multi column table with all the parts, with part_id as the primary key. sch_part_mapping is a two column mapping table with part_id (child) || parent_id (parent).

Could someone point me in the right direction with the SQL query? I am not keen on using a while loop to create the SQL statement as I think this will be quite inefficient but it is the only way I have considered might work so far.

Answer 1

MySQL doesn't have much (if any) support for hierarchical queries. If you want to stick to what is called theAdjacency List Model, all you can do is add a JOIN for each level you like to include. Needless to say this doesn't scale well.

On the other hand, if you can alter your Database Schema, I would suggest implementing the Nested Set Model.

A very good explantion of the Nested Set Model is presented in Mike Hillyer's blog

Limitations of the Adjacency List Model

Working with the adjacency list model in pure SQL can be difficult at best. Before being able to see the full path of a category we have to know the level at which it resides.

Nested Set Model

the concept of nested sets in SQL has been around for over a decade, and there is a lot of additional information available in books and on the Internet. In my opinion the most comprehensive source of information on managing hierarchical information is a book called Joe Celko’s Trees and Hierarchies in SQL for Smarties, written by a very respected author in the field of advanced SQL, Joe Celko.