Use table alias in another query to traverse a tree

Question

I have the following query:

select * from (
   select p1.c as child, p1.p as parent, 1 as height
   from parent as p1
   where (p1.c=3 or p1.c=8);

   union

   select p2.c as child, p2.c as parent, 2 as height
   from parent as p2 
   where (p1.child=3 or p1.child=8) and p1.parent = p2.child;
)

The schema is:

CREATE TABLE parent(p int, c int);

I'm trying to find a path from the child to the root. [Edit] And append the number of edges we have to traverse.
The goal is to join the child's parent with its parent, something like:

(8, 2, 1)
(8, 5, 2) -> 8 is the lowest child, 2 is its parent, and 5 it's 2 parent.

Some sample data:

How can I use the reference for the first query p1 inside the second query that will form p2? After that I should have;

(8,2,1)
(3,12,1)
(3,10,2)
(8,5,2)

Thus I already will know what to do to complete what I want.

If using Oracle, look up CONNECT BY, and maybe mix in a LISTAGG. — Bob, Jul 08 '14 at 03:15
The examples look fine to me. The third column is the "height", the distance between the nodes. The first column is the "child", the second column is the "parent" (height 1), or "grandparent" (height 2). — spencer7593, Jul 08 '14 at 03:16
Is your tree limited to three levels like in the example or are you looking for a general solution for n levels? — Erwin Brandstetter, Jul 08 '14 at 04:22

score 4 · Answer 1 · edited Jun 20 '20 at 09:12

Question asked

You cannot reference a table alias from one subquery in another query on the same level (or in another leg of a UNION query). A table alias is only visible in the query itself and subqueries of it.
You could reference output columns of a subquery on the same query level with a LATERAL JOIN. Example:
Find most common elements in array with a group by

Solution for small maximum number of levels

For only a handful of levels (if you know the maximum), you can use a simple query:

LEFT JOIN to n-1 instances of the table itself
Use COALESCE and a CASE statement to pin down the root and hight,

SELECT p1.c AS child, COALESCE(p3.p, p2.p, p1.p) AS parent
      ,CASE
          WHEN p3.p IS NOT NULL THEN 3
          WHEN p2.p IS NOT NULL THEN 2
          ELSE 1
       END AS height
FROM   parent p1
LEFT   JOIN parent p2 ON p2.c = p1.p
LEFT   JOIN parent p3 ON p3.c = p2.p
WHERE  p1.c IN (3, 8)
ORDER  BY p1.c;

This is standard SQL and should work in all 4 RDBMS you tagged.

Generic solution for arbitrary number of levels

Use a recursive CTE like @Ken already advised.

In the recursive leg keep the child for every row, only advance the parent.
In the outer SELECT, only keep a the row with the greatest height per child.

WITH RECURSIVE cte AS (
   SELECT c AS child, p AS parent, 1 AS height
   FROM   parent
   WHERE  c IN (3, 8)

   UNION ALL

   SELECT c.child, p.p AS parent, c.height + 1
   FROM   cte    c
   JOIN   parent p ON p.c = c.parent
   -- WHERE  c.height < 10  -- to safeguard against endless loops if necessary
   )
SELECT DISTINCT ON (child) *
FROM   cte
ORDER  BY child, height DESC;

DISTINCT ON is specific to Postgres. Explanation:
Select first row in each GROUP BY group?

The rest would work in a similar fashion in Oracle and even SQLite, but not in MySQL which doesn't support CTEs.

SQL Fiddle demonstrating both.

score 2 · Answer 2 · answered Jul 08 '14 at 03:12

In Postgres, I would recommend looking at a WITH RECURSIVE CTE:

http://www.postgresql.org/docs/9.3/static/queries-with.html

It's perfect for modeling tree-like structures such as parent-child relationships, be it an entire tree, a subtree, etc.

There are many examples in the Postgres doc, including for dealing with tree-like structures specifically, which should apply to your case (albeit with some adaptation of your query to fit the WITH RECURSIVE mold).

score 2 · Answer 3 · answered Jul 08 '14 at 03:12

It's not possible to reference a table alias from the first SELECT in the second SELECT (following a UNION or UNION ALL set operator. You can in a correlated subquery, but that has to be within the context of the same SELECT.)

Also, you need to ditch the semicolons within the statement; MySQL is going to see that as the end of the statement.

For MySQL, you're definitely got a workable approach to solving this problem, using separate queries for each "height", and combining the results with a UNION set operator. Likely, you want to use a UNION ALL set operator for performance. (If you don't need the extra step of identifying and removing duplicates. Also, it's not necessary to use an inline view.

SELECT p1.c  AS child
     , p1.p  AS parent
     , 1     AS height
  FROM parent p1
 WHERE p1.c IN (3,8)
 UNION ALL
SELECT p1.c  AS child
     , p2.p  AS parent
     , 2     AS height
  FROM parent p1
  JOIN parent p2
    ON p2.c = p1.p
 WHERE p1.c IN (3,8)

Just to demonstrate how this can be extended to a height of 3, adding another JOIN to the same table, with alias of p3.

 UNION ALL
SELECT p1.c  AS child
     , p3.p  AS parent
     , 3     AS height
  FROM parent p1
  JOIN parent p2 ON p2.c = p1.p
  JOIN parent p3 ON p3.c = p2.p
 WHERE p1.c IN (3,8)

NOTE

Originally, I only noticed this was tagged for MySQL.

With Oracle, you could make use of the recursive CONNECT BY form of SELECT, to get an equivalent result without a UNION.

Use table alias in another query to traverse a tree

3 Answers3

Question asked

Solution for small maximum number of levels

Generic solution for arbitrary number of levels

Linked