help with multi-path hierarchical data
-
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)
-
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/
-
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
-
I do apologize for the extraneous commas in the insert statements !
-
Mark-101232 (11/22/2011)
I think this is known as a directed graphIn 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 -
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.
-
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.
Viewing 7 posts - 1 through 6 (of 6 total)
You must be logged in to reply to this topic. Login to reply