SQL - Convert non-null adjacency list to path

Question

I am working with some tables that represent a file system, and I need to select the full path of each folder as a flattened string.

The first table lists the details of each folder:

CREATE TABLE Folders(
    FolderID int IDENTITY(1,1) NOT NULL,
    [Name] nvarchar(255) NOT NULL)

The second table lists transitive closures of folder relationships:

CREATE TABLE FolderClosures(
    FolderClosuresID int IDENTITY(1,1) NOT NULL,
    AncestorFolderID int NOT NULL, --Foreign key to Folders.FolderID
    DescendantFolderID int NOT NULL --Foreign key to Folders.FolderID
    IsDirect bit NOT NULL)

For sample data, let's assume the following folders exist:

Documents/
Documents/Finance/
Documents/HumanResources/
Documents/HumanResources/Training/

These would be persisted in those tables as follows:

| FolderID | Name           |
+----------+----------------+
|        1 | Documents      |
|        2 | Finance        |
|        3 | HumanResources |
|        4 | Training       |

| FolderClosureID | AncestorFolderID | DescendantFolderID | IsDirect |
+-----------------+------------------+--------------------+----------+
|               1 |                1 |                  1 |        0 |
|               2 |                2 |                  2 |        0 |
|               3 |                1 |                  2 |        1 |
|               4 |                3 |                  3 |        0 |
|               5 |                1 |                  3 |        1 |
|               6 |                4 |                  4 |        0 |
|               7 |                1 |                  4 |        0 |
|               8 |                3 |                  4 |        1 |

Some details to note:

Every folder has an "identity row" in FolderClosures, where AncestorFolderID = DescendantFolderID AND IsDirect = 0.
Every folder that is not a top-level folder has exactly one row in FolderClosures where IsDirect = 1
FolderClosures can contain many rows per folder, where AncestorFolderID <> DescendantFolderID AND IsDirect = 0. Each of these represents a "grandparent" or more distant relationship.
Since no columns are nullable, no rows explicitly state that a given folder is a top-level folder. This can only be discerned by checking that there are no rows in FolderClosures where IsDirect = 1 AND DescendantFolderID = SomeID where SomeID is the ID of the folder in question.

I want to be able to run a query that returns this data:

| FolderID | Path                               |
+----------+------------------------------------+
|        1 | Documents/                         |
|        2 | Documents/Finance/                 |
|        3 | Documents/HumanResources/          |
|        4 | Documents/HumanResources/Training/ |

Folders may be nested at unlimited depth, but realistically probably only up to 10 levels. Queries may require returning paths for a few thousand folders.

I've found a lot of advice on creating this type of query when data is persisted as an adjacency list, but I haven't been able to find an answer for a transitive closure setup like this. The adjacency list solutions I've found rely on rows being persisted with nullable parent folder IDs, but that doesn't work here.

How can I get the desired output?

If it helps, I am using SQL Server 2016.

SQL - Convert non-null adjacency list to path

1 Answers