How to SELECT immediate children and ancestors all in the same query

Question

I'm working with a tree structure in MySQL that is respresented using the nested sets model.

I'm hoping some of you sql experts can help me with building a SELECT query.

I would like to be able to match a set of nodes using LIKE. For each node that is matched, I also need a comma-delimmited list of the ancestors of that node, and a comma-delimmited list of the immediate children of that node.

I'm not really sure where to start with this - if such a thing is even possible in a single query. (Currently I am accomplishing this with a query inside a loop.) What I'm hoping for is a result set that might look something like this....

Starting with the string "qu" and querying the Table "Body" I get...

Node      | Parent Nodes               | Immediate Children
Quads       Leg, Lower Body, Muslces     Vastus Lateralus, Vastus Medialis, Rectus Femoris
Obliques    Core, Trunk, Muscles         Inner obliques, outer obliques

Any suggestions on how to accomplish this without looping queries would be much appreciated.

Answer 1

In one query? I wouldn't bother. The SQL would be horrendous, and probably not even that efficient. Split each bit up into logical smaller queries: first find all the matching nodes, then for each of those, the extra info you need.

Answer 2

I'm not 100% sure what you want but if I understand correctly you could achieve this using a normalized database schema and subqueries.

For example:

Table "nodes" Table "node_parents"

The "nodes" table would store all nodes, and "node_parents" would map relationships between different nodes.

So when you select LIKE a certain node you could grab all its parents and children from node_parents.

You could grab the extra info using joins or subqueries.

Answer 3

While I agree with nickf that this is bad and dirty, it's still fun, so here goes:

SELECT     base.left_id, base.ancestors, 
           GROUP_CONCAT(children.left_id) children
FROM       (
            SELECT     base.left_id
            ,          GROUP_CONCAT(ancestors.left_id) ancestors
            FROM       nested_set   base
            LEFT JOIN  nested_set   ancestors
            ON         base.left_id     BETWEEN ancestors.left_id 
                                            AND ancestors.right_id
            WHERE      base.name  LIKE '%criteria%'
            GROUP BY   base.left_id
           ) base                                    
LEFT JOIN  nested_set   children
ON         children.left_id BETWEEN base.left_id 
                                AND base.right_id
LEFT JOIN  nested_set   inbetween
ON         inbetween.left_id BETWEEN base.left_id 
                                AND base.right_id
AND        children.left_id  BETWEEN inbetween.left_id 
                                AND inbetween.right_id     
WHERE      inbetween.left_id IS NULL
GROUP BY   base.left_id

Basically, the trick is to solve it in two steps: first, solve the ancestors problem, and squash the ancestors to a list with, then, use this result to solve it for the children.

The ancestors part is relatively easy, it is the subquery in the from clause in my solution. The children is a bit harder. It works by taking all descendents, and then requiring that there do not exist any nodes between the base node and the descendents, which basically restricts the descendents to only the children.

There are other variations to this strategy to solve this - for example you can do the children first, and solve the ancestors using a subquery in the SELECT list.

Answer 4

This question is a lot harder then I anticipated in your other post, but I disagree with the first posters answer.

I am quite confident that it is possible with a single query.

You need to use SUBQUERIES and selects. Have you ever looked at the really good demo on the mySQL website about Adjacency List Model.

Because you can LIKE for the "Node" you can then use Sub queries for your SQL query to get all of the parents and parent. One of my queries which I did something like this on was absolutely massive! But it worked.

Take a look : http://dev.mysql.com/tech-resources/articles/hierarchical-data.html

This is just a little code snippet which shows how the immediate children is found.

SELECT node.name, (COUNT(parent.name) - (sub_tree.depth + 1)) AS depth
FROM nested_category AS node,
    nested_category AS parent,
    nested_category AS sub_parent,
    (
        SELECT node.name, (COUNT(parent.name) - 1) AS depth
        FROM nested_category AS node,
        nested_category AS parent
        WHERE node.lft BETWEEN parent.lft AND parent.rgt
        AND node.name = 'PORTABLE ELECTRONICS'
        GROUP BY node.name
        ORDER BY node.lft
    )AS sub_tree
WHERE node.lft BETWEEN parent.lft AND parent.rgt
    AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt
    AND sub_parent.name = sub_tree.name
GROUP BY node.name
HAVING depth <= 1
ORDER BY node.lft