Recursion On A Many To Many Table Parent To Child To Parent

Question

My boss has given me a single 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 walk through the process.

1. The user searches for TV.

2. TV is found and the accessories for TV are Antennae, Power Cord & Remote.

3. The accessories Antennae, Power Cord & Remote are now used to find other related items. Power Cord also an accessory for Laptop. Antennae & Remote are not accessories for any other item.

4. The item Laptop is now used to find that item's accessories, which are Power Cord & Carrying Case.

5. The accessories Power Cord & Carrying Case are now used to find other related items. Power Cord finds no new items (we already know Power Cord is associated with TV & Laptop). Carrying Case is also an accessory for Camera.

6. The item Camera is now used to find that item's accessories, which are Carrying Case & Lens.

7. The accessories Carrying Case & Lens are now used to find other related items. Carrying Case & Lens find no new items (we already know Carrying Case is associated with Laptop).

8. No new items are found to continue search chain. Final list returned.

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 handle this problem? I'm not sure what the correct terminology would be for this so perhaps I missed it in my searches. Any advice is appreciated.

Answer 1

It looks like your table presents a undirected graph and you need to traverse this graph starting from the Item user searched.

Consider using breadth-first search (BFS) algorithm.

Every visited node is a resulting list you need.

Answer 2

If you're not averse to using a GOTO statement for the looping you're trying to achieve, here's a 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's been any added during this iteration, if there are, repeat!
IF @intCount <> @intNewCount GOTO START;

--Finished
SELECT * FROM @table

I see most of the other answers have a while loop, thought I'd just mix it up :) Tested in SQL2008

Answer 3

I couldn't do it with CTE like I said. Reason why is explained here : Prevent recursive CTE visiting nodes multiple times

So here is an old fashion 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 4

Brian Pressler's pseudocode is pretty close, save for a couple of problems with the joins. Here's what I think this 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 does have a mechanism for recursive queries—the recursive CTE—but I wasn't able to implement this example using one of those because I couldn't implement the NOT EXISTS part of the above query.

Answer 5

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