What is the simplest way to get all the parents of a record using the id / parent_id model in mysql/php?

Question

I'm looking for the simplest way to recursively get all the parent elements from a database using the adjacency list / single table inheritance model (id, parent_id).

My select currently looks like this:

$sql = "SELECT
             e.id,
             TIME_FORMAT(e.start_time, '%H:%i') AS start_time,
             $title AS title,
             $description AS description,
             $type AS type,
             $place_name AS place_name,
             p.parent_id AS place_parent_id,
             p.city AS place_city,
             p.country AS place_country
         FROM event AS e
         LEFT JOIN place AS p ON p.id = e.place_id                          
         LEFT JOIN event_type AS et ON et.id = e.event_type_id
         WHERE e.day_id = '$day_id'
         AND e.private_flag = 0
         ORDER BY start_time";

Each event is linked to a place, and each place can be a child of another place (upto about 5 levels deep)

Is this possible in a single select with mysql?

At the moment I am thinking it could be a separate function which loops through the returned $events array, adding place_parent_X elements as it goes, but am not sure how to implement this.

Answer 1

It's not possible with the standard parent-child DB design.

However, you could use a nested set approach and do it in one query, though that will take quite a bit of work to get to that point.

Answer 2

Looks like the easiest is nested sets.

Answer 3

It's possible to do it in MySQL, but you'll need to create a function and use in in a query.

See this entry in my blog for detailed explanations:

• Hierarchical queries in MySQL

Here are the function and the query:

CREATE FUNCTION hierarchy_connect_by_parent_eq_prior_id(value INT) RETURNS INT
NOT DETERMINISTIC
READS SQL DATA
BEGIN
        DECLARE _id INT;
        DECLARE _parent INT;
        DECLARE _next INT;
        DECLARE CONTINUE HANDLER FOR NOT FOUND SET @id = NULL;

        SET _parent = @id;
        SET _id = -1;

        IF @id IS NULL THEN
                RETURN NULL;
        END IF;

        LOOP
                SELECT  MIN(id)
                INTO    @id
                FROM    place
                WHERE   parent = _parent
                        AND id > _id;
                IF @id IS NOT NULL OR _parent = @start_with THEN
                        SET @level = @level + 1;
                        RETURN @id;
                END IF;
                SET @level := @level - 1;
                SELECT  id, parent
                INTO    _id, _parent
                FROM    place
                WHERE   id = _parent;
        END LOOP;
END

SELECT  id, parent
FROM    (
        SELECT  hierarchy_connect_by_parent_eq_prior_id(id) AS id, @level AS level
        FROM    (
                SELECT  @start_with := 0,
                        @id := @start_with,
                        @level := 0
                ) vars, t_hierarchy
        WHERE   @id IS NOT NULL
        ) ho
JOIN    place hi
ON      hi.id = ho.id

The latter query will select all descendants of a given node (which you should set in the @start_with variable)

To find all ancestors of a given node you can use a simple query without functions:

SELECT  @r AS _id,
        @r := (
        SELECT  parent
        FROM    place
        WHERE   id = _id
        ) AS parent
FROM    (
        SELECT  @r := @node_id
        ) vars,
        place

This article in my blog described this query in more detail:

• Sorting lists

For both these solutions to work in reasonable time, you need to have the indexes on both id and parent.

Make sure your id is defined as a PRIMARY KEY and you have a seconday index on parent.