Traversing from a leaf to one or more parent in the table

Question

Currently I have the following Model:

SELECT m.city_area_id AS city_area_id
FROM menus m
JOIN oc_category c ON (m.id = c.menu_id)
JOIN oc_category oc ON (oc.parent_id = c.category_id)
JOIN oc_product_to_category ptc ON
    ptc.category_id = oc.category_id AND
    ptc.product_id = $dish_id

The expected behavior of this Model is to find the city area ID given a dish.

It works this way:

1. Find our product's [our input] category ID through the table oc_product_to_category.
2. Using the category_id from this relationship, we head over to oc_category to find the parent_id of this particular product.

3. Once you've reached the top-most category ID, there would be a menu_id [the menu_id is 0 if it's not the top-most category_id, and the parent_id would also be 0 since there will be no more parents] for us to use.

4. Once we have the menu_id, we will be able to find this menu's city area ID.

The following is an example of a category_id row that has a parent_id. As you can tell, the menu_id is 0, and the parent_id is a non-zero value.

+-------------+-------+-----------+-----+--------+------------+--------+---------------------+---------------------+------------------+---------+
| category_id | image | parent_id | top | column | sort_order | status | date_added          | date_modified       | visible_official | menu_id |
+-------------+-------+-----------+-----+--------+------------+--------+---------------------+---------------------+------------------+---------+
|         784 | NULL  |       783 |   0 |      0 |          1 |      1 | 0000-00-00 00:00:00 | 0000-00-00 00:00:00 |                1 |       0 |
+-------------+-------+-----------+-----+--------+------------+--------+---------------------+---------------------+------------------+---------+

My issue:

My current SQL query works if for each category_id, there is only one parent_id level to traverse. So, for those products that have two parent category_ids [as opposed to one], my script would return an empty set.

My question is - how do I intelligently traverse from a leaf to the upmost parent no matter how many parents this particular category ID may have?

EDIT: Looks like my SQL row's formatting is all botched. I have no idea how to add a horizontal scrollbar to my code block =(

Answer 1

If I understand what you want to do, you're geting a particular set of row from ptc based on some criteria, e.g

SELECT ptc.*
  FROM oc_product_to_category ptc
 WHERE ptc.product_id = $dish_id

Then you want to get the related oc...

  JOIN oc_category oc 
    ON oc.category_id = ptc.category_id

And if that's not a top level oc, you want to get its parent...

  JOIN oc_category a1
    ON a1.category_id = oc.parent_id

And if that's not a top level, you want to get its parent...

  JOIN oc_category a2
    ON a2.category_id = a1.parent_id

And so on, until you get the top most parent.

One approach to doing this in a single query is to first determine the maximum possible depth of the tree, and then use outer join operations to return the parent of each level...

SELECT ptc.*
  FROM oc_product_to_category ptc
  JOIN oc_category a0
    ON a0.category_id = ptc.category_id
  LEFT JOIN oc_category a1 ON a1.category_id = oc.parent_id
  LEFT JOIN oc_category a2 ON a2.category_id = a1.parent_id
  LEFT JOIN oc_category a3 ON a3.category_id = a2.parent_id
  LEFT JOIN oc_category a4 ON a4.category_id = a3.parent_id
 WHERE ptc.product_id = $dish_id

The trick now is to determine which of those table references (a1, a2, a3, a4) returned the topmost level.

One way to do that is to use an expression that tests each of those levels, from the top down, to determine the highest level that returned a non-NULL value. For example:

       CASE
         WHEN a4.category_id IS NOT NULL THEN a4.menu_id
         WHEN a3.category_id IS NOT NULL THEN a3.menu_id
         WHEN a2.category_id IS NOT NULL THEN a2.menu_id
         WHEN a1.category_id IS NOT NULL THEN a1.menu_id
         WHEN a0.category_id IS NOT NULL THEN a0.menu_id
       END

You can use the result from that expression in the predicate for the join to the menus table

  LEFT JOIN menus m ON m.id = expr

So, the whole query might looks something like this:

SELECT m.city_area_id as city_area_id
FROM oc_product_to_category ptc
JOIN oc_category oc ON oc.category_id = ptc.category_id
LEFT JOIN oc_category a0 ON a0.category_id = oc.parent_id
LEFT JOIN oc_category a1 ON a1.category_id = a0.parent_id
LEFT JOIN oc_category a2 ON a2.category_id = a1.parent_id
LEFT JOIN oc_category a3 ON a3.category_id = a2.parent_id
LEFT JOIN oc_category a4 ON a4.category_id = a3.parent_id
LEFT JOIN menus m
    ON m.id =
        CASE
            WHEN a4.parent_id = 0 THEN a4.menu_id
            WHEN a3.parent_id = 0 THEN a3.menu_id
            WHEN a2.parent_id = 0 THEN a2.menu_id
            WHEN a1.parent_id = 0 THEN a1.menu_id
            WHEN a0.parent_id = 0 THEN a0.menu_id
        END
WHERE ptc.product_id = $dish_id

This example query will look only look for a topmost parent up to four levels above; if you're hierarchy has a greater depth than that, you'd need to extend this to more levels, following the same pattern...

  LEFT JOIN oc_category a5 ON a5.category_id = a4.parent_id
  LEFT JOIN oc_category a6 ON a6.category_id = a5.parent_id

And you'd need to extend the expression that return the menu_id to include checks whether a row was returned from those levels.

(In my implemtations, I typically use a NULL value for the parent_id column to indicate a topmost node. If your hierarchy is implemented differently, using a value of 0 for the parent_id, you may need to use a different expression to test for the topmost level, but the expression would follow the same pattern:

       CASE
         WHEN a4.parent_id = 0 THEN a4.menu_id
         WHEN a3.parent_id = 0 THEN a3.menu_id
         WHEN a2.parent_id = 0 THEN a2.menu_id
         WHEN a1.parent_id = 0 THEN a1.menu_id
         WHEN a0.parent_id = 0 THEN a0.menu_id
       END