Recursion on many many tables, parent-to-child, to parents

Question

My boss gave me one table.

  Related_Items_Table

 Item |  Accessory 
 ---------------------
 TV |  Antennae 
 TV |  Power cord 
 TV |  Remote 
 Laptop |  Power cord 
 Laptop |  Carrying case 
 Camera |  Carrying case 
 Camera |  Lens 
 iPod |  Headphones

The best way to describe what my boss wants for results is to go through the process.

• The user searches for the TV.

• A TV is available, and TV accessories are Antennas, Power Cord & amp; Remote.

• Accessories Antennas, a power cord and a remote control are now used to search for other related items. The power cord is also a laptop accessory. Antenna and remote control are not accessories for any other element.

• The item Laptop is now used to find accessories for this item, which are the power cord and carrying case.

• Accessories The power cord and case are now used to search for other related items. The power cord does not find new items (we already know the power cord is connected to the TV and laptop). The case is also an accessory for the camera.

• The item "Camera" is now used to find accessories for this item, which are a portable case and lens.

• Carrying accessories and lenses are now used to search for other related materials. New items were not found in the case and lens (we already know that the carrying case is connected to the laptop).

• There are no new items to continue the search chain. The final list is back.

  Final list 

 Item |  Accessory 
 ---------------------
 TV |  Antennae 
 TV |  Power cord 
 TV |  Remote 
 Laptop |  Power cord 
 Laptop |  Carrying case 
 Camera |  Carrying case 
 Camera |  Lens 

What is the best way to deal with this problem? I'm not sure what the correct terminology would be for this, so maybe I missed it in my search. Any advice is appreciated.

Answer 1

It looks like your table is an undirected graph, and you need to go through this graph starting with a user search.

Consider using a width search algorithm (BFS) .

Each node visited is a result list that you need.

Answer 2

I would do something like this pesudocode:

insert into Final_List all the records that match the item in Related_Items_Table WHILE 1=1 BEGIN Insert into Final List select NextLevel.* from Related_Items_Table join Related_Items_Table NextLevel on Related_Items_Table.Accessory = NextLevel.Item where the nextlevel.item and nextlevel.accesory not already in Final List if @@Rowcount = 0 break END 

Answer 3

Brian Presler's pseudo-code is pretty close, with the exception of a few association issues. Here is what I think it looks like:

 -- The sample data from the problem. declare @SearchString varchar(32) = 'TV'; declare @RelatedItemsTable table ( [Item] varchar(32), [Accessory] varchar(32) ); insert @RelatedItemsTable values ('TV', 'Antennae'), ('TV', 'Power Cord'), ('TV', 'Remote'), ('Laptop', 'Power Cord'), ('Laptop', 'Carrying Case'), ('Camera', 'Carrying Case'), ('Camera', 'Lens'), ('iPod', 'Headphones'); -- This table will hold your results. declare @SearchResults table ( [Item] varchar(32), [Accessory] varchar(32) ); -- Base case: look for any item or accessory that matches the search string. -- I'm not sure whether you want to search items only or accessories also; -- adjust as needed. insert @SearchResults select * from @RelatedItemsTable where [Item] like @SearchString or [Accessory] like @SearchString; while @@rowcount > 0 begin -- The recursive case: look for new records where... insert @SearchResults select [New].[Item], [New].[Accessory] from @RelatedItemsTable [New] inner join @SearchResults [Old] on -- ... the new record is an item using the same kind of accessory as -- an existing item, or... [New].[Accessory] = [Old].[Accessory] or -- ... the new record is an accessory for the same kind of item as an -- existing accessory, and... [New].[Item] = [Old].[Item] where -- ... this record doesn't yet appear in the result set. not exists ( select 1 from @SearchResults [Existing] where [Existing].[Accessory] = [New].[Accessory] and [Existing].[Item] = [New].[Item] ); end; select * from @SearchResults; 

SQL Server has a mechanism for recursive queries - a recursive CTE - but I could not implement this example using one of these because I could not implement the NOT EXISTS part of the above query.

Answer 4

I could not do this with CTE, as I said. The reason why here is explained: CTE recursive CTE nodes interrupt several times

So this is the old way

 DECLARE @MyTable TABLE(Item NVARCHAR(50), Accessory NVARCHAR(50)) DECLARE @Result TABLE(Item NVARCHAR(50), Accessory NVARCHAR(50), LinkedItem NVARCHAR(50), Done int) INSERT INTO @MyTable VALUES ('TV', 'Antennae'), ('TV', 'Power Cord'), ('TV', 'Remote'), ('Laptop', 'Power Cord'), ('Laptop', 'Carrying Case'), ('Camera', 'Carrying Case'), ('Camera', 'Lens') DECLARE @NbIteration INT = 0 INSERT INTO @Result SELECT t.Item, t.Accessory, LinkedItem.Item, @NbIteration FROM @MyTable AS t LEFT JOIN @MyTable AS LinkedItem ON t.Accessory = LinkedItem.Accessory WHERE t.Item = 'TV' WHILE(@@ROWCOUNT > 0) BEGIN SELECT @NbIteration = @NbIteration + 1 INSERT INTO @Result SELECT t.Item, t.Accessory, LinkedItem.Item, @NbIteration FROM @Result AS r INNER JOIN @MyTable AS t ON r.LinkedItem = t.Item LEFT JOIN @MyTable AS LinkedItem ON t.Accessory = LinkedItem.Accessory WHERE r.Done = @NbIteration - 1 AND NOT EXISTS(SELECT TOP 1 1 FROM @Result AS Sub WHERE t.Item = Sub.Item) --don't go back to records already done END SELECT DISTINCT Item, Accessory FROM @Result 

Answer 5

If you don't mind using the GOTO statement for the loop you are trying to achieve, here is the solution:

 DECLARE @search VARCHAR(50) = 'TV' --Get initial resultset DECLARE @table TABLE (item VARCHAR(50), accessory VARCHAR(50)) INSERT INTO @table SELECT items.* FROM items WHERE item LIKE @search --declare the variables used for checking if we have any new results DECLARE @intCount INT = (SELECT COUNT(*) FROM @table) DECLARE @intNewCount INT = (SELECT COUNT(*) FROM @table) --The infamous GOTO label START: --Store the count of items SET @intCount = (SELECT COUNT(*) FROM @table) --Insert any matching rows for accessory = accessory, excluding ones already added INSERT INTO @table (item, accessory) SELECT item, accessory FROM items WHERE accessory IN (SELECT accessory FROM @table) AND NOT EXISTS(SELECT TOP 1 1 FROM @table t WHERE t.item = items.item AND t.accessory = items.accessory) --Now Insert any matching rows for item = item, excluding ones already added INSERT INTO @table (item, accessory) SELECT item, accessory FROM items WHERE item IN (SELECT item FROM @table) AND NOT EXISTS(SELECT TOP 1 1 FROM @table t WHERE t.item = items.item AND t.accessory = items.accessory) --Set the new count SET @intNewCount = (SELECT COUNT(*) FROM @table) --Check if there been any added during this iteration, if there are, repeat! IF @intCount <> @intNewCount GOTO START; --Finished SELECT * FROM @table 

I see that most of the other answers have a while loop, thought I would just mess it up :) Tested in SQL2008