1

I have built a function/query that returns [paths] as an adjacency list as shown below and it works well, however I am trying t figure out how to limit the results to only complete paths, not each iteration of depth(n).

for example, out of the following results shown below, only these are valid, FULL paths I want to return or filter:

S11>S11-LG>V613>V613_Close>B31A>B30>B30A>V30A1>V30A1_Close>B-GARNER>VB1>VB1_Close
S11>S11-LG>V613>V613_Close>B31A>B30>B30A>V30A1>V30A1_Close>B-GARNER>VB1>VB1_Open
S11>S11-LG>V613>V613_Close>B31A>B30>B30A>V30A1>V30A1_Close>B-GARNER>VB1>VB2
S11>S11-LG>V613>V613_Close>B31A>B30>B30A>V30A1>V30A1_Open>V30A2>V30A2_Close>S2-UG
S11>S11-LG>V613>V613_Close>B31A>B30>B30A>V30A1>V30A1_Open>V30A2>V30A2_Open>S1-UG

TEST

select * from fn_Get_SubTreePaths('S11', 11) order by DPath

results

S11>S11-LG
S11>S11-LG>V613
S11>S11-LG>V613>V613_Close
S11>S11-LG>V613>V613_Close>B31A
S11>S11-LG>V613>V613_Close>B31A>B30
S11>S11-LG>V613>V613_Close>B31A>B30>B30A
S11>S11-LG>V613>V613_Close>B31A>B30>B30A>V30A1
S11>S11-LG>V613>V613_Close>B31A>B30>B30A>V30A1>V30A1_Close
S11>S11-LG>V613>V613_Close>B31A>B30>B30A>V30A1>V30A1_Close>B-GARNER
S11>S11-LG>V613>V613_Close>B31A>B30>B30A>V30A1>V30A1_Close>B-GARNER>VB1
S11>S11-LG>V613>V613_Close>B31A>B30>B30A>V30A1>V30A1_Close>B-GARNER>VB1>VB1_Close
S11>S11-LG>V613>V613_Close>B31A>B30>B30A>V30A1>V30A1_Close>B-GARNER>VB1>VB1_Open
S11>S11-LG>V613>V613_Close>B31A>B30>B30A>V30A1>V30A1_Close>B-GARNER>VB1>VB2
S11>S11-LG>V613>V613_Close>B31A>B30>B30A>V30A1>V30A1_Open
S11>S11-LG>V613>V613_Close>B31A>B30>B30A>V30A1>V30A1_Open>V30A2
S11>S11-LG>V613>V613_Close>B31A>B30>B30A>V30A1>V30A1_Open>V30A2>V30A2_Close
S11>S11-LG>V613>V613_Close>B31A>B30>B30A>V30A1>V30A1_Open>V30A2>V30A2_Close>S2-UG
S11>S11-LG>V613>V613_Close>B31A>B30>B30A>V30A1>V30A1_Open>V30A2>V30A2_Open
S11>S11-LG>V613>V613_Close>B31A>B30>B30A>V30A1>V30A1_Open>V30A2>V30A2_Open>S1-UG

In other words - how can I determine only those paths which include the bottom-most item in the traversal / depth ?

Any help would be greatly appreciated! I am reading through Joe Celko's Trees and Hierarchies in SQL for Smarties - but have so far not wrapped my brain around how to limit the results correctly ...

Here is the code;

create function [dbo].[fn_Get_SubTreePaths]( @Start varchar(20), @MaxLevels int)
returns table 
as
RETURN(
    WITH CTE AS (
    SELECT 
        c.DeviceID AS Start,
        CAST(d.DeviceName AS VARCHAR(2000)) AS Path, 
        c.ConnectedDeviceID, 
        1 AS Level
    FROM Connections c
    INNER JOIN Devices d ON d.ID=c.DeviceID
                        AND d.DeviceName=@Start
    UNION ALL
    SELECT 
        r.Start, 
        CAST(r.Path + '>'+ d.DeviceName AS VARCHAR(2000)), 
        --CAST(r.Path + ' -> ' + d.DeviceName + '-' + cast(r.SLevel as varchar) AS VARCHAR),
        c.ConnectedDeviceID, 
        Level = r.Level + 1
    FROM Connections c
    INNER JOIN Devices d ON d.ID=c.DeviceID
                        and d.DeviceName<>@Start
    INNER JOIN CTE r ON c.DeviceID=r.ConnectedDeviceID
      AND r.Level < @MaxLevels
    )

    SELECT 
      DISTINCT a.DPath
      FROM (
        SELECT c.Path + '>' + ISNULL(d.DeviceName,'?')  AS DPath
        FROM CTE c
        INNER JOIN Devices d ON d.ID=c.ConnectedDeviceID
        ) a    
    )                                  




CREATE TABLE [dbo].[Connections](
    [ID] [int] NOT NULL,
    [DeviceID] [int] NULL,
    [ConnectedDeviceID] [int] NULL
 CONSTRAINT [PK_Connections] PRIMARY KEY CLUSTERED 
(
    [ID] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]



CREATE TABLE [dbo].[Devices](
    [ID] [int] IDENTITY(1,1) NOT NULL,
    [DeviceName] [varchar](50) NULL
 CONSTRAINT [PK_Devices] PRIMARY KEY CLUSTERED 
(
    [ID] ASC
) WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]

And the view used by the CTE:

ALTER view [dbo].[vw_DeviceConnections] as
select 
  c.ID as ID,
  c.DeviceID as DeviceID,
  d.DeviceName,
  d.DeviceType,
  c.ConnectedDeviceID as ConnDeviceID,
  cd.DeviceName as ConnDeviceName,
  cd.DeviceType as ConnDeviceType
from Devices d  
inner join Connections c on
   d.id=c.DeviceID
inner join Devices cd on
   cd.id=c.ConnectedDeviceID  

2 Answers 2

2

See the answer working on SQLFiddle here.

Here's my strategy: Make your recursive CTE return the current node as well as the node before it. Then you can join that on itself and restrict it to rows whose last node is not used as the parent of another node.

Here's how your function would look (replace 'S11' and 15 with your parameters):

WITH CTE AS (
  SELECT
    d.ID AS Start,
    CAST(d.DeviceName AS VARCHAR(2000)) AS Path, 
    d.ID AS node,
    NULL AS parent,
    1 AS Level
  FROM Devices d
  WHERE d.DeviceName= 'S11'
UNION ALL
  SELECT 
    r.Start, 
    CAST(r.Path + '>'+ d.DeviceName AS VARCHAR(2000)), 
    d.ID as node,
    r.node as parent,
    r.Level + 1 as Level
  FROM CTE r
    INNER JOIN Connections c ON c.DeviceID = r.node
    INNER JOIN Devices d ON d.ID = c.ConnectedDeviceID
  WHERE r.Level < 15
),
Trimmed as (
  SELECT L.*
  FROM CTE L
    LEFT JOIN CTE R on L.node = R.parent
  WHERE R.parent IS NULL
)   
SELECT * FROM Trimmed

Let me know if you'd like clarification about how it works, I can try to explain it better.

1
  • Thank you Chad - I will use this as my solution: this "restrict it to rows whose last node is not used as the parent of another node." is perfect for what I need to do all within the primary query !
    – bbaley
    May 3, 2012 at 23:37
0

try next solution

select 
    *
from 
    fn_Get_SubTreePaths('S11', 11) f1
where
    (
        select
            count(*)
        from
            fn_Get_SubTreePaths('S11', 11) f2
        where
            charindex(f1.dPath, f2.dPath) > 0
    ) = 1

order by DPath
2
  • this works - it looks like you are limiting it to only the first occurrence of the path "up to that point" yes ?
    – bbaley
    May 3, 2012 at 23:34
  • My query takes one string (path) and search how many other strings it contain. If it return result 1 then it is final path. May 7, 2012 at 7:22

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.