Challenging recursive T-SQL query

Question

Here is my scenario. Let's say I have two tables "Car" and "CarPart". The car consist of many parts and each part can belong to multiple cars. One complication in my case is that each part gets a new PartID, even if it's the same part name, but it simply belongs to a different car. This is something I have no control over, so just bear with me. Here is the script to set things up.

IF OBJECT_ID('Car') IS NOT NULL DROP TABLE Car
CREATE TABLE Car (
CarID INT,
CarName VARCHAR(16)
)

IF OBJECT_ID('CarPart') IS NOT NULL DROP TABLE CarPart
CREATE TABLE CarPart (
PartID INT,
PartName VARCHAR(16),
CarID INT
)

INSERT INTO Car
VALUES (1, 'Chevy'),
    (2, 'Ford'),
    (3, 'Toyota'),
    (4, 'Honda'),
    (5, 'Nissan'),
    (6, 'Hugo')

INSERT INTO CarPart 
VALUES  (110, 'Engine', 1),
  (120, 'Engine', 2),
  (210, 'Door', 1),
  (220, 'Door', 3),
  (310, 'Seat', 4),
  (320, 'Seat', 5),
  (410, 'Window', 3),
  (510, 'Wheel', 2),
  (420, 'Window', 6)

As you can see, the part "Engine" belongs to both "Chevy" and "Ford" and is listed twice with different IDs. Once again, this is a design limitation I have to live with.

Here is what I need to accomplis: given a car, I need to find all of the parts for this car and all of the other cars that these parts belong to. I have to continue finding parts and cars in a recursive manner until I reach the end of the chain. The logic can be outlined as follows: @StartCar --> Parts of a @StartCar --> Other parts by the same name --> get Id's of those "other" parts --> Get cars which "own" those parts --> start over and repeat until the end of the chain is reached.

To solve my problem, I tried this query:

DECLARE @StartCar VARCHAR(16) = 'Chevy'

;WITH cte (CarName, PartName)
AS
(
SELECT c.CarName,
       cp.PartName
FROM CarPart cp
JOIN Car c ON cp.CarID = c.CarID
WHERE c.CarName = @StartCar
UNION ALL
SELECT c.CarName,
       cp.PartName
FROM CarPart cp
JOIN Car c ON cp.CarID = c.CarID
JOIN cte cte ON cp.PartName = cte.PartName
)
SELECT CarName, PartName
FROM cte

However, it gets into an infinite loop and terminates. I would expect see the output similar to this:

CarName PartName
Chevy Engine
Chevy Door
Ford Engine
Ford Wheel
Toyota Door
Toyota Window
Hugo Window

I appreciante any pointers.

Thank you!

Answer 1

You are basically traversing a graph that's not acyclic, so you must explicitly avoid cycles. One way is to keep track of the path in the graph. Here's code that should work. You could use SQL Server's HIERARCHYID data type to hold the paths, also.

I chose to make the CTE a table of cars instead of a table of parts. Your rule never results in some, but not all, parts for a specific car, so this seemed simpler.

WITH cte(CarID,hier) AS (
  SELECT CarID, CAST('/'+LTRIM(CarID)+'/' AS varchar(max))
  FROM Car
  WHERE CarName = @StartCar

  UNION ALL

  SELECT c2.CarID, hier+LTRIM(c2.CarID)+'/'
  FROM Car AS c
  JOIN cte ON cte.CarID = c.CarID
  JOIN CarPart AS c1 ON c.CarID = c1.CarID
  JOIN CarPart AS c2 ON c2.PartName = c1.PartName
  WHERE hier NOT LIKE '%/'+LTRIM(c2.CarID)+'/%'
)

SELECT
  c.CarName, cp.PartName
FROM Car AS c
JOIN CarPart AS cp ON cp.CarID = c.CarID
JOIN cte on cte.CarID = c.CarID

Answer 2

SQL Fiddle

Query 1:

declare @t table (
  car_name varchar(100), 
  part_name varchar(100)
  )

declare @car int = 3

insert @t
select c.CarName, p.PartName
from Car c join CarPart p on c.CarID = p.CarID
where c.CarID = @car


while exists(
  select c.CarName, p.PartName
  from Car c join CarPart p on c.CarID = p.CarID
  where c.CarName in (
    select c.CarName
    from Car c join CarPart p on c.CarID = p.CarID
    where p.PartName in (select part_name from @t)
      and c.CarName not in (select car_name from @t)
    )
) 
insert @t
  select c.CarName, p.PartName
  from Car c join CarPart p on c.CarID = p.CarID
  where c.CarName in (
    select c.CarName
    from Car c join CarPart p on c.CarID = p.CarID
    where p.PartName in (select part_name from @t)
      and c.CarName not in (select car_name from @t)
    )

select * from @t

Results:

| CAR_NAME | PART_NAME |
------------------------
|   Toyota |      Door |
|   Toyota |    Window |
|    Chevy |    Engine |
|    Chevy |      Door |
|     Hugo |    Window |
|     Ford |    Engine |
|     Ford |     Wheel |