How do I Query an Adjacency relation (in SQL) to get a Leaf by providing a Path?

Question

Greetings, fellow coders!

I have this table that contains categories and subcategories (actually I don't, but let's stick to a classic example):

Id     ParentId     Name
1      NULL         A
2      1            B
3      2            C
4      3            D

5      NULL         B
6      5            D

Is there a way for me to get category "D" (id 4) by querying the table for the full path? (see pseudocode below)

SELECT * FROM Categories WHERE FullPath = "A/B/C/D"

// Result:
Id     ParentId     Name
4      3            D

I know that it's possible to use left joins to get the full path, but how do I write queries to get the leaf node by providing a path?

EDIT (Solution):

Help the help from both van and Eric, this is what I did:

with p as
(
    select
        c.*,
        cast(c.Name as varchar(1024)) as NamePath
    from
        Categories c
    where 
        ParentCategoryId is null
    union all
    select
        c.*,
        cast(p.NamePath + '/' + c.Name as varchar(1024)) as NamePath
    from
        Categories c
        inner join p on
            c.ParentCategoryId = p.CategoryId
)
select Id, Name
from p
where NamePath = 'A/B/C/D'

Thanks guys, both your answers were very helpful! I wish that I was able to mark them both as the solution.

This time I will simply go for the one with the leasts ammount of points (that is van).

Answer 1

Although not directly answering your question, if you have access to SQL Server 2008 you may want to consider using the Hierarchid data type.

Answer 2

I dont see the point of doing this as you already have built the path and know what "D" is. Cant you just split the pathe by '\' and use the last item to query on.

Answer 3

Here's the SQL Server (2005+) approach, using a Common Table Expression (CTE):

declare @leaf varchar(10)
declare @fullpath varchar(50)

set @leaf = 'D'
set @fullpath = '/A/B/C/D'

with p as
(
    select
        *,
        '/' + name as path
    from
        categories 
    where 
        leaf = @leaf
    union all
    select
        c.*,
        '/' + name + p.path as path
    from
        categories c
        inner join p on
            c.id = p.parentid
)

select
    *
from
    p
where
    path = @fullpath

Answer 4

With the help of CTE:

WITH CategoriesWithPath (id, parentid, name, path) AS
(
    SELECT  c.*, cast(c.name AS VARCHAR(1024)) AS "path"
    FROM    @Categories c
    WHERE   parentid is null
    UNION ALL
    SELECT  c.*, cast(p."path" + '/' + c.name AS VARCHAR(1024)) AS "path"
    FROM    @Categories c
    INNER JOIN CategoriesWithPath p ON c.parentid = p.id
)
SELECT  id, parentid, name 
FROM    CategoriesWithPath
WHERE   "path" = 'a/b/c/d'

But I would create a view using this CTA, so that you can easily just execute a SELECT from this view based on "path" filter.