help with multi-path hierarchical data

Question

Post reply

help with multi-path hierarchical data

bbaley

Old Hand

Points: 338
More actions
November 22, 2011 at 7:16 am

#247179

Hi All !
So I am experiencing a brainurism...
I know what I want, but not how to get it (not uncommon right?)
At any rate, please excuse my ignorance, I am looking for what I am sure has been done 1000 times before;
High level: imagine inputs and outputs, valves and pipes. any one valve or pipe can have multiple outputs or inputs.
So, the traditional child/parent tree does not work[?].
The idea is to be able to query a path, from (a) to (z), meaning starting at (a) and ending at (z) show me all path nodes.
The design goal is to not have to statically create a "record" for every path solution.
put another way, the query is "show me all paths(nodes) from (a) to (z)" where
each node can have multiple inputs and each node can have multiple outputs.
At any rate - I don't know what to call this!
I know a standard tree will not do, it is more of a web.
Any ideas ?
the result set should return:
path : G9, V9, D9, V1, S1, D1, B1, BIN100
path : G9, V9, D9, V1, S1, D1, B1, BIN101
path : G9, V9, D9, V1, S1, D1, B2, BIN200
path : G9, V9, D11, V2, S2, D2, B2, BIN201
path : G9, V9, D11, V2, S2, D2, B2, BIN202
path : etc...
for [all known paths]
when searching for paths with a start point of (G9) and endpoint of (BIN200)
the following paths are valid:
path : G9, V9, D9, V1, S2, D2, B2, BIN200
path : G9, V9, D9, V2, S2, D2, B2, BIN200
path : G9, V9, D11, V2, S2, D2, B2, BIN200
here is some sample data;
===========================================================
CREATE TABLE [dbo].[Devices](
[ID] [int] NOT NULL,
[DeviceName] [varchar](50) NOT NULL,
[DeviceType] [varchar](20) NOT NULL,
[Description] [varchar](255) NULL,
CONSTRAINT [PK_Devices] PRIMARY KEY CLUSTERED ([ID] ASC)
)
CREATE TABLE [dbo].[Connections](
[ID] [int] IDENTITY(1,1) NOT NULL,
[DeviceID] [int] NOT NULL,
[ConnectedDeviceID] [int] NOT NULL,
[ConnectionType] [char](1) NULL,
[IOType] [char](1) NULL,
CONSTRAINT [PK_Connections] PRIMARY KEY CLUSTERED ([ID] ASC)
)
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
insert into Devices(ID, DeviceName, DeviceType, Description), values(1,G9,DIVERTER,Garner )
insert into Devices(ID, DeviceName, DeviceType, Description), values(2,G11,DIVERTER,Garner)
insert into Devices(ID, DeviceName, DeviceType, Description), values(3,V9,DIVERTER,Valve)
insert into Devices(ID, DeviceName, DeviceType, Description), values(5,V11,DIVERTER,Valve)
insert into Devices(ID, DeviceName, DeviceType, Description), values(6,V1,DIVERTER,Valve)
insert into Devices(ID, DeviceName, DeviceType, Description), values(7,V2,DIVERTER,Valve)
insert into Devices(ID, DeviceName, DeviceType, Description), values(8,S1,DIVERTER,Scale)
insert into Devices(ID, DeviceName, DeviceType, Description), values(9,S2,DIVERTER,Scale)
insert into Devices(ID, DeviceName, DeviceType, Description), values(10,D9,DIVERTER,Distributor)
insert into Devices(ID, DeviceName, DeviceType, Description), values(11,D11,DIVERTER,Distributor)
insert into Devices(ID, DeviceName, DeviceType, Description), values(12,D1,DIVERTER,Distributor)
insert into Devices(ID, DeviceName, DeviceType, Description), values(13,D2,DIVERTER,Distributor)
insert into Devices(ID, DeviceName, DeviceType, Description), values(14,B1,MOVER,Belt)
insert into Devices(ID, DeviceName, DeviceType, Description), values(15,B2,MOVER,Belt)
insert into Devices(ID, DeviceName, DeviceType, Description), values(16,BIN100,STORAGE,Bin)
insert into Devices(ID, DeviceName, DeviceType, Description), values(17,BIN101,STORAGE,Bin)
insert into Devices(ID, DeviceName, DeviceType, Description), values(18,BIN102,STORAGE,Bin)
insert into Devices(ID, DeviceName, DeviceType, Description), values(19,BIN200,STORAGE,Bin)
insert into Devices(ID, DeviceName, DeviceType, Description), values(20,BIN201,STORAGE,Bin)
insert into Devices(ID, DeviceName, DeviceType, Description), values(21,BIN202,STORAGE,Bin)
---------------------------------------------------------------------------------------------------------------------------
insert into Connections(DeviceID, ConnectedDeviceID), values(1,3)
insert into Connections(DeviceID, ConnectedDeviceID), values(3,10)
insert into Connections(DeviceID, ConnectedDeviceID), values(10,16)
insert into Connections(DeviceID, ConnectedDeviceID), values(2,5)
insert into Connections(DeviceID, ConnectedDeviceID), values(5,11)
insert into Connections(DeviceID, ConnectedDeviceID), values(10,6)
insert into Connections(DeviceID, ConnectedDeviceID), values(6,8)
insert into Connections(DeviceID, ConnectedDeviceID), values(6,9)
insert into Connections(DeviceID, ConnectedDeviceID), values(11,7)
insert into Connections(DeviceID, ConnectedDeviceID), values(7,8)
insert into Connections(DeviceID, ConnectedDeviceID), values(7,9)
insert into Connections(DeviceID, ConnectedDeviceID), values(8,12)
insert into Connections(DeviceID, ConnectedDeviceID), values(9,13)
insert into Connections(DeviceID, ConnectedDeviceID), values(12,14)
insert into Connections(DeviceID, ConnectedDeviceID), values(12,15)
insert into Connections(DeviceID, ConnectedDeviceID), values(13,14)
insert into Connections(DeviceID, ConnectedDeviceID), values(13,15)
insert into Connections(DeviceID, ConnectedDeviceID), values(14,16)
insert into Connections(DeviceID, ConnectedDeviceID), values(14,17)
insert into Connections(DeviceID, ConnectedDeviceID), values(14,18)
insert into Connections(DeviceID, ConnectedDeviceID), values(15,19)
insert into Connections(DeviceID, ConnectedDeviceID), values(15,20)
insert into Connections(DeviceID, ConnectedDeviceID), values(15,21)

Viewing 7 posts - 1 through 6 (of 6 total)

You must be logged in to reply to this topic. Login to reply

Cadavre SSC-Forever Points: 41690 More actions · Answer 1

Fixed your sample data so that it actually works -

CREATE TABLE [dbo].[Devices](

[ID] [int] NOT NULL,

[DeviceName] [varchar](50) NOT NULL,

[DeviceType] [varchar](20) NOT NULL,

[Description] [varchar](255) NULL,

CONSTRAINT [PK_Devices] PRIMARY KEY CLUSTERED ([ID] ASC)

)

CREATE TABLE [dbo].[Connections](

[ID] [int] IDENTITY(1,1) NOT NULL,

[DeviceID] [int] NOT NULL,

[ConnectedDeviceID] [int] NOT NULL,

[ConnectionType] [char](1) NULL,

[IOType] [char](1) NULL,

CONSTRAINT [PK_Connections] PRIMARY KEY CLUSTERED ([ID] ASC)

)

INSERT INTO Devices (ID,DeviceName,DeviceType,Description)VALUES (1,'G9','DIVERTER','Garner')

INSERT INTO Devices (ID,DeviceName,DeviceType,Description)VALUES (2,'G11','DIVERTER','Garner')

INSERT INTO Devices (ID,DeviceName,DeviceType,Description)VALUES (3,'V9','DIVERTER','Valve')

INSERT INTO Devices (ID,DeviceName,DeviceType,Description)VALUES (5,'V11','DIVERTER','Valve')

INSERT INTO Devices (ID,DeviceName,DeviceType,Description)VALUES (6,'V1','DIVERTER','Valve')

INSERT INTO Devices (ID,DeviceName,DeviceType,Description)VALUES (7,'V2','DIVERTER','Valve')

INSERT INTO Devices (ID,DeviceName,DeviceType,Description)VALUES (8,'S1','DIVERTER','Scale')

INSERT INTO Devices (ID,DeviceName,DeviceType,Description)VALUES (9,'S2','DIVERTER','Scale')

INSERT INTO Devices (ID,DeviceName,DeviceType,Description)VALUES (10,'D9','DIVERTER','Distributor')

INSERT INTO Devices (ID,DeviceName,DeviceType,Description)VALUES (11,'D11','DIVERTER','Distributor')

INSERT INTO Devices (ID,DeviceName,DeviceType,Description)VALUES (12,'D1','DIVERTER','Distributor')

INSERT INTO Devices (ID,DeviceName,DeviceType,Description)VALUES (13,'D2','DIVERTER','Distributor')

INSERT INTO Devices (ID,DeviceName,DeviceType,Description)VALUES (14,'B1','MOVER','Belt')

INSERT INTO Devices (ID,DeviceName,DeviceType,Description)VALUES (15,'B2','MOVER','Belt')

INSERT INTO Devices (ID,DeviceName,DeviceType,Description)VALUES (16,'BIN100','STORAGE','Bin')

INSERT INTO Devices (ID,DeviceName,DeviceType,Description)VALUES (17,'BIN101','STORAGE','Bin')

INSERT INTO Devices (ID,DeviceName,DeviceType,Description)VALUES (18,'BIN102','STORAGE','Bin')

INSERT INTO Devices (ID,DeviceName,DeviceType,Description)VALUES (19,'BIN200','STORAGE','Bin')

INSERT INTO Devices (ID,DeviceName,DeviceType,Description)VALUES (20,'BIN201','STORAGE','Bin')

INSERT INTO Devices (ID,DeviceName,DeviceType,Description)VALUES (21,'BIN202','STORAGE','Bin')

INSERT INTO Connections (DeviceID,ConnectedDeviceID)VALUES (1,3)

INSERT INTO Connections (DeviceID,ConnectedDeviceID)VALUES (3,10)

INSERT INTO Connections (DeviceID,ConnectedDeviceID)VALUES (10,16)

INSERT INTO Connections (DeviceID,ConnectedDeviceID)VALUES (2,5)

INSERT INTO Connections (DeviceID,ConnectedDeviceID)VALUES (5,11)

INSERT INTO Connections (DeviceID,ConnectedDeviceID)VALUES (10,6)

INSERT INTO Connections (DeviceID,ConnectedDeviceID)VALUES (6,8)

INSERT INTO Connections (DeviceID,ConnectedDeviceID)VALUES (6,9)

INSERT INTO Connections (DeviceID,ConnectedDeviceID)VALUES (11,7)

INSERT INTO Connections (DeviceID,ConnectedDeviceID)VALUES (7,8)

INSERT INTO Connections (DeviceID,ConnectedDeviceID)VALUES (7,9)

INSERT INTO Connections (DeviceID,ConnectedDeviceID)VALUES (8,12)

INSERT INTO Connections (DeviceID,ConnectedDeviceID)VALUES (9,13)

INSERT INTO Connections (DeviceID,ConnectedDeviceID)VALUES (12,14)

INSERT INTO Connections (DeviceID,ConnectedDeviceID)VALUES (12,15)

INSERT INTO Connections (DeviceID,ConnectedDeviceID)VALUES (13,14)

INSERT INTO Connections (DeviceID,ConnectedDeviceID)VALUES (13,15)

INSERT INTO Connections (DeviceID,ConnectedDeviceID)VALUES (14,16)

INSERT INTO Connections (DeviceID,ConnectedDeviceID)VALUES (14,17)

INSERT INTO Connections (DeviceID,ConnectedDeviceID)VALUES (14,18)

INSERT INTO Connections (DeviceID,ConnectedDeviceID)VALUES (15,19)

INSERT INTO Connections (DeviceID,ConnectedDeviceID)VALUES (15,20)

INSERT INTO Connections (DeviceID,ConnectedDeviceID)VALUES (15,21)

Forever trying to learn
My blog - http://www.cadavre.co.uk/
For better, quicker answers on T-SQL questions, click on the following...http://www.sqlservercentral.com/articles/Best+Practices/61537/
For better, quicker answers on SQL Server performance related questions, click on the following...http://www.sqlservercentral.com/articles/SQLServerCentral/66909/

Mark Cowne One Orange Chip Points: 26952 More actions · Answer 2

I think this is known as a directed graph

DECLARE @Start VARCHAR(50)

DECLARE @End VARCHAR(50)

DECLARE @MaxLevels INT

SET @Start='G9'

SET @End='BIN200'

SET @MaxLevels=7;

WITH CTE AS (

SELECT c.DeviceID AS Start,CAST(d.DeviceName AS VARCHAR(1000)) 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(1000)), c.ConnectedDeviceID, r.Level + 1

FROM Connections c

INNER JOIN Devices d ON d.ID=c.DeviceID

AND d.DeviceName<>@End

INNER JOIN CTE r ON c.DeviceID=r.ConnectedDeviceID

-- Ignore node if it has appeared before

AND ','+r.Path+',' NOT LIKE '%,'+d.DeviceName+',%'

AND r.Level<@MaxLevels)

SELECT c.Path + ','+ d.DeviceName AS Path

FROM CTE c

INNER JOIN Devices d ON d.ID=c.ConnectedDeviceID

AND d.DeviceName=@End;

____________________________________________________

Deja View - The strange feeling that somewhere, sometime you've optimised this query before

How to get the best help on a forum

http://www.sqlservercentral.com/articles/Best+Practices/61537

bbaley Old Hand Points: 338 More actions · Answer 3

I do apologize for the extraneous commas in the insert statements !

drew.allen SSC Guru Points: 76985 More actions · Answer 4

Mark-101232 (11/22/2011)
I think this is known as a directed graph

In order for the recursive CTEs to work, it actually needs to be a directed acyclic graph, i.e., it can't have any loops in the graph. The simplest loop is a is connected to b and b is connected to a. It's not clear whether there is anything in place to ensure that the directed graph is acyclic.

Drew

J. Drew Allen
Business Intelligence Analyst
Philadelphia, PA

bbaley Old Hand Points: 338 More actions · Answer 5

Drew - my thoughts were to limit the query results a unique path, where no one node appears more than twice to keep this from happening.

That being said, the data representing the paths would not be circular or acyclic.

RowanCollum SSC Veteran Points: 224 More actions · Answer 6

If I understand the expected results correctly, the following would be a possible solution using an rCTE:

declare @StartDevice varchar(32) ,@EndDevice varchar(32);

select @StartDevice = 'G9' ,@EndDevice = 'BIN200';

;with cte as

(

select top 1 c.ID ,c.DeviceID ,c.ConnectedDeviceID ,cast(d.DeviceName as nvarchar(max)) as DevicePath

from Devices d ,Connections c

where d.DeviceName = @StartDevice and c.DeviceID = d.ID

order by c.ID

union all

select top 100 percent c.ID ,c.DeviceID ,c.ConnectedDeviceID ,k.DevicePath + ', ' + d.DeviceName

from cte k ,Connections c ,Devices d

where c.DeviceID = k.ConnectedDeviceID and d.ID = c.DeviceID

order by c.ID

)

select 'path : ' + k.DevicePath + ', ' + d.DeviceName

from cte k ,Devices d

where d.ID = k.ConnectedDeviceID

and not exists (select 'X' from Connections where DeviceID = k.ConnectedDeviceID)

-- and d.DeviceName = @EndDevice

order by k.ID

NOTE: With the sample data provided, 'D11' would not be included in a 'G9' path.