Simplest Way to Do a Recursive Self-Join

Simplest way to do a recursive self-join?

WITH    q AS 
        (
        SELECT  *
        FROM    mytable
        WHERE   ParentID IS NULL -- this condition defines the ultimate ancestors in your chain, change it as appropriate
        UNION ALL
        SELECT  m.*
        FROM    mytable m
        JOIN    q
        ON      m.parentID = q.PersonID
        )
SELECT  *
FROM    q

By adding the ordering condition, you can preserve the tree order:

WITH    q AS 
        (
        SELECT  m.*, CAST(ROW_NUMBER() OVER (ORDER BY m.PersonId) AS VARCHAR(MAX)) COLLATE Latin1_General_BIN AS bc
        FROM    mytable m
        WHERE   ParentID IS NULL
        UNION ALL
        SELECT  m.*,  q.bc + '.' + CAST(ROW_NUMBER() OVER (PARTITION BY m.ParentID ORDER BY m.PersonID) AS VARCHAR(MAX)) COLLATE Latin1_General_BIN
        FROM    mytable m
        JOIN    q
        ON      m.parentID = q.PersonID
        )
SELECT  *
FROM    q
ORDER BY
        bc

By changing the ORDER BY condition you can change the ordering of the siblings.

SQL Server recursive self join

Recursive cte to the rescue....

Create and populate sample table (Please save us this step in your future questions):

DECLARE @T as table
(
    id int,
    name varchar(100),
    parent_id int
)

INSERT INTO @T VALUES
(1, 'A', NULL),
(2, 'A.1', 1),
(3, 'A.2', 1),
(4, 'A.1.1', 2),
(5, 'B', NULL),
(6, 'B.1', 5),
(7, 'B.1.1', 6),
(8, 'B.2', 5),
(9, 'A.1.1.1', 4),
(10, 'A.1.1.2', 4)

The cte:

;WITH CTE AS
(
    SELECT id, name, name as path, parent_id
    FROM @T 
    WHERE parent_id IS NULL
    UNION ALL
    SELECT t.id, t.name, cast(cte.path +','+ t.name as varchar(100)), t.parent_id
    FROM @T t
    INNER JOIN CTE ON t.parent_id = CTE.id
)

The query:

SELECT id, name, path
FROM CTE

Results:

id      name        path
1       A           A
5       B           B
6       B.1         B,B.1
8       B.2         B,B.2
7       B.1.1       B,B.1,B.1.1
2       A.1         A,A.1
3       A.2         A,A.2
4       A.1.1       A,A.1,A.1.1
9       A.1.1.1     A,A.1,A.1.1,A.1.1.1
10      A.1.1.2     A,A.1,A.1.1,A.1.1.2

See online demo on rextester

How to self JOIN recursively in SQL?

If you are using SQL Server 2005+, you can use common-table expressions

With Family As 
( 
Select s.ID, s.ParentSeriesId, 0 as Depth
From Series s
Where ID = @ParentID 
Union All 
Select s2.ID, s2.ParentSeriesId, Depth + 1
From Series s2
    Join Family 
        On Family.ID = s2.ParentSeriesId 
) 
Select *
From Family 

For more:

Recursive Queries Using Common Table Expressions

What is the best way to do a recursive SQL query on a self join field (as well as doing it through nhibernate?)

Using a recursive CTE, you can build the hierarchy. Filtering the top level query by your search criteria, you can get the results you're looking for.

DECLARE @id INT;
SET @id = 3;

WITH    Emp
          AS (SELECT    te.id
                      , te.Name
                      , te.ManagerId
                      , CAST(NULL AS VARCHAR(10)) AS ManagerName
              FROM      dbo.tblEmployee AS te
              -- Get entire heirarchy with the NULL ManagerId
              --WHERE     ManagerId IS NULL
              WHERE     te.id = @id
              UNION ALL
              SELECT    te2.id
                      , te2.Name
                      , e.id
                      , e.Name
              FROM      dbo.tblEmployee AS te2
              JOIN      Emp e
                        ON e.id = te2.ManagerId
             )
    SELECT  *
    FROM    Emp;

UPDATE:
For your comment about not including the record for the id passed, you can do two things:

The easiest way would be to add a where clause to the last select:

SELECT  *
FROM    Emp
WHERE emp.ID <> @id;

Alternatively, if you didn't need the ManagerName field to be populated for the top level of the hierarchy, you can what the first where clause in the CTE:

SELECT    te.id
, te.Name
, te.ManagerId
, CAST(NULL AS VARCHAR(10)) AS ManagerName
FROM      dbo.tblEmployee AS te
-- Get entire heirarchy with the NULL ManagerId
--WHERE     ManagerId IS NULL
--WHERE     te.id = @id
WHERE ManagerId = @id

recursive self join in data.table

Here's my attempt using your dataset.

It uses a while loop checking to see if there's any components that also are in the prodName field. The loop always needs to have the same fields so instead of adding a column for the recursive multipliers (i.e., 5*8*7 at the end), the iterative multipliers are integrated. That is, 5*8*7 becomes 5*56 at the end.

library(data.table)

a[, qty_multiplier := 1]
b <- copy(a)

while (b[component %in% prodName, .N] > 0) {
  b <- b[a
         , on = .(prodName = component)
         , .(prodName = i.prodName
             , component = ifelse(is.na(x.component), i.component, x.component)
             , qty = i.qty
             , qty_multiplier = ifelse(is.na(x.qty), 1, x.qty * qty_multiplier)
         )
         ]
}

b[prodName %like% 'prod', .(qty = sum(qty * qty_multiplier)), by = .(prodName, component)] 

   prodName component qty
1:    prod1         a  13
2:    prod1         b  14
3:    prod2         b   3
4:    prod3         b 284
5:    prod3         a 240
6:    prod3         d  45

Recursive SQL self join

You want a recursive CTE:

with e as (
      select cast(name as varchar(max)) as list, empId, 0 as level
      from employees
      where managerID is null
      union all
      select e.list + '>' + e2.name, e2.empId, level + 1
      from e join
           employees e2
           on e.empId = e2.managerId
     )
select e.*
from e
where not exists (select 1
                  from employees e2
                  where e2.managerId = e.empId
                 );

Recursive self join

I would simply run a short loop like this (sorry for invalid capitalization, coded from scratch):

public List<Int> GetAllManagers(int userID)
{
  var result = new List<int>();
  int index = 0;
  result.add(userID); // start with user (it will be removed later)
  while (index < result.count)
  {
    var moreData = from e in mycontext.EmployeeManagers
                    where e.UserId == result[index];
                     select e.ManagerId;
    foreach (int id in moreData)
      if (result.indexOf(id)==-1)
        result.add(id);
    index++;
  }
  result.delete(0);
  return result;
}

or recursevly

private void AddUniqueIds (List<int> elements, ref List<int> list)
{
  foreach (int id in elements)
    if (list.indexOf(id)==-1)
      list.add(id);
}
public List<int> GetAllManagers(int userID)
{
  var result = new List<int>();
  var moreData = from e in mycontext.EmployeeManagers
                 where e.UserId == result[index];
                 select e.ManagerId;

  foreach (int id in moreData)
    AddUniqueIds(result, GetAllManagers(id));

  return result;
}

---

Related Topics