Recursive select that selects rows based own plus childrens values-CodePudding

I need to select rows in a table like this:

Select all rows in the table where both conditions are met:

Condition 1: the value column should not match with any value in table v
Condition 2: no decendent (on any level, ie: child or sub child, sub- sub- child etc) has a value that matches with any value in table v

Table v looks like this:

Expected result from example table. Should [row] be selected/returned?

a1: No - condition 2
a2: No - condition 2
a3: No - condition 1
a4: No - condition 1
a5: Yes - (value does not match in v and no decendents that match in v)
a6: Yes - (value does not match in v and no decendents that match in v)
a7: Yes - (value does not match in v and no decendents that match in v)
a8: Yes - (value does not match in v and no decendents that match in v)

Here is an sqlfiddle where the tables are set up together with a recursive function that shows all rows and their level in the tree, but that I don't know how to procede with:

For the sake of the discussion let's add another row which lead rows with id a8 and a9 to be "NO" since it is child of a9 and has value from the second table

INSERT INTO a
    ([id], [parentId], [value])
VALUES
    ('a10', 'a9', 35)
GO

test 2 Result set (fits expected)

CodePudding user response：

This got somewhat complicated, but I created a CTE where there is a record that contains a Path for every combination of ancestor and descendant (transitive closure). Then, I create a second CTE where I extract the parent id from the beginning of Path and the descendant id from the end of Path and look up the descendant's value. Then, finally, I query the second CTE and use NOT EXISTS to filter the rows.

 WITH tree
    AS 
    ( 
  
        SELECT a.id, a.parentId, a.value,
                CAST('/'   a.id as varchar(1000)) as Path
        FROM a 
      
        UNION ALL

        SELECT a.id, a.parentId, a.value,
                CAST(t.Path   '/'   a.id as varchar(1000)) as Path
        FROM a
        INNER JOIN tree t
            ON Path LIKE '%/'   a.parentId
    ),
    DT
      AS
      (
        SELECT t.Path,
          RIGHT(LEFT(t.Path,3),2) as parent_id,
          RIGHT(t.Path,2) as descendant_id,
          (SELECT q.[value]
           FROM a q
           WHERE q.id = RIGHT(t.Path,2)
          ) as [descendant_value]

        FROM tree t
      )
   SELECT *
   FROM DT dt_outer
   WHERE NOT EXISTS (SELECT 1 FROM DT dt_inner WHERE dt_inner.parent_id = dt_outer.parent_id AND
     dt_inner.descendant_value IN (SELECT [value] FROM v))
   ORDER BY 2,3

I left the result set with duplicates to get a clearer picture of what's going on. You can finish up with a DISTINCT parent_id to get the unique ids.

SQL Fiddle