1

Initial scenario

My software uses a tree data structure, and I store it in SQL. I use the abstraction called Adjacency List which consists of each row storing ID and ParentID.

ID is Primary Key and ParentID is a Foreign Key to the same table.

The problem

I want to "convert" my SQL abstraction to Path Enumeration. It consists of each row storing ID and a varchar field storing the path of the IDs, from the root to the current row. For example, the Path field of the row with ID = 6 in this tree:

Tree

Would be /1/2/4/6/. More details here, by the name Lineage Column.

Question

How do I build a column Path from an existing database that only has ID and ParentID?

Jeremy Caney
  • 7,102
  • 69
  • 48
  • 77
Lucas Reis
  • 743
  • 11
  • 21
  • 1
    I strongly recommend against this. Combining multiple values into a single field is a strong sql-anti-pattern. Without knowing your needs I couldn't be certain, but perhaps converting your adjacency-list to a closure-table or nested-sets would be more useful to you? Neither of which breach the atomicity of a relational data structure. *(Also, we'd need to know which RDBMS you're using. Some support recursion, some do it in 'unique' ways, some don't at all.)* – MatBailie Apr 29 '14 at 15:21
  • 1
    @MatBailie, we just need the to retrieve an object and its descendants, and we only delete entire subtrees. I also prefer the _Closure Table_ abstraction, but I was a lost vote! ;) – Lucas Reis Apr 29 '14 at 15:29
  • @LucasReid - As described you're getting an object and its (Asc)endents rather that its (Desc)endents. Also, we still need to know the RDBMS. – MatBailie Apr 29 '14 at 15:31
  • I'll try to convince my team once again to use the Closure Tables. I'll leave this answer here just for curiosity purposes. – Lucas Reis Apr 29 '14 at 15:36
  • 1
    Adding a `depth` field to each row in the closure table also allows for retrieving the path in-order if that is necessary. – MatBailie Apr 29 '14 at 15:41
  • It's worth noting that this problem also pertains to developers looking to convert an adjacency list to a materialized path. This should be obvious, but I'm pointing it out for SEO purposes. – Jeremy Caney Sep 01 '20 at 18:48

2 Answers2

2

SQL Server 2005 onwards should support the following:

WITH
  recursed_tree AS
(
  SELECT
    IDObject,
    concat('/', cast(IDObject as varchar(100)))   AS Path
  FROM
    tbObject
  WHERE
    ParentID IS NULL

  UNION ALL

  SELECT
    next.IDObject,
    concat(prev.Path, '/', cast(next.IDObject as varchar(100)))   AS Path
  FROM
    recursed_tree   AS prev
  INNER JOIN
    tbObject        AS next
       ON prev.IDObject = next.ParentID
)

SELECT
  *
FROM
  recursed_tree
MatBailie
  • 83,401
  • 18
  • 103
  • 137
0

I came up with this SQL Server query:

[ tbObjectHierarchy has a FK and PK called IDObject and a varchar called Path ]

declare @T  as table (IDObject int, Path varchar(500))
declare @T2 as table (IDObject int, Path varchar(500))

insert into tbObjectHierarchy(IDObject, Path)
select o.IDObject, concat('/', cast(o.IDObject as varchar(100)), '/') as Path
from tbObject as o 
where o.ParentID is null

insert into @T (IDObject, Path)
select o.IDObject, concat(h.Path, cast(o.IDObject as varchar(100)), '/') as Path
from tbObject as o
inner join tbObjectHierarchy as h
on o.ParentID = h.IDObject

while exists (select top 1 * from @T)
begin
    insert into tbObjectHierarchy (IDObject, Path)
    select t.IDObject, t.Path
    from @T as t

    delete from @T2

    insert into @T2
    select o.IDObject, concat(t.Path, cast(o.IDObject as varchar(100)), '/') as Path
    from tbObject as o
    inner join @T as t
    on o.ParentID = t.IDObject

    delete from @T

    insert into @T
    select * from @T2
end
Lucas Reis
  • 743
  • 11
  • 21
  • This is clearly TSQL then. Is it version 2005 onwards? Using a recursive CTE would likely be much simpler and quicker. – MatBailie Apr 29 '14 at 15:29