Select top-most folder in a hierarchy by given criteria in MySQL

Question

I'm using MySQL (5.7.20) to store a folder hierarchy. Each folder is stored together with all direct and indirect parents including the distance. As an example, the following folders

A
+- B
   + C
   + D

would be stored like this:

parent | child | dist
-------+-------+-----
A      | A     | 0
A      | B     | 1
A      | C     | 2
A      | D     | 2
B      | B     | 0
B      | C     | 1
B      | D     | 1
C      | C     | 0
D      | D     | 0

Additionally, there is another table that links a folder to one or many users, like this:

child | user
------+-----
A     | U1
B     | U1
C     | U2
D     | U2

What I'm now trying to achieve is to query this hierarchy by user in a way that only the highest matches in the hierarchy are returned.

So as in the example above, if I query for folders of user U1, I only want A as a result, because the second match B is a child of A. On the other hand, if I query for folders of user U2, the result should be C, D as both folders are on the same hierarchy level.

The closest query I could imagine was SELECT child, dist AS d FROM folders JOIN users ON folders.child = users.child GROUP BY folders.parent HAVING d = min(d); but unfortunately it is not giving the right results, as for example a query for user U1 would still give folders A,B as a result.

Does anyone have an idea how this could be done?

Answer 1

I think you want this. All the results from users table except those that have a parent in users:

SELECT u.user, u.child
FROM users AS u 
WHERE NOT EXISTS
      ( SELECT 1 
        FROM users AS u2
             JOIN folder AS f 
             ON f.parent = u2.child
        WHERE f.child = u.child
          AND f.dist > 0         -- this could be: AND f.parent <> f.child
          AND u2.user = u.user
      ) ;