Recursive sql problem

0 votes
asked Dec 18, 2008 by patrik

I have a problem that I would like have solved via a SQL query. This is going to be used as a PoC (proof of concept).

The problem:

Product offerings are made up of one or many product instances, a product instance can belong to many product offerings. This can be realised like this in a table:

PO | PI

-----

A | 10

A | 11

A | 12

B | 10

B | 11

C | 13

Now I would like to get back the product offer from a set of product instances. E.g. if we send in 10,11,13 the expected result back is B & C, and if we send in only 10 then the result should be NULL since no product offering is made up of only 10. Sending in 10,11,12 would result in A (not A & B since 12 is not a valid product offer in it self).

Prerequisites: The combination of product instances sent in can only result in one specific combination of product offerings, so there is only one solution to each query.

10 Answers

0 votes
answered Dec 18, 2008 by hamishmcn

I don't have a db in front of me, but off the top of my head you want the list of POs that don't have any PIs not in your input list, ie

select distinct po 
from tbl 
where po not in ( select po from tbl where pi not in (10,11,13) )

Edit: Here are the example other cases:
When input PI = 10,11,13 the inner select returns A so the outer select returns B, C
When input PI = 10 the inner select returns A,B,C so the outer select returns no rows
When input PI = 10,11,12 the inner select returns C so the outer select returns A,B

Edit: Adam has pointed out that this last case doesn't meet the requirement of only returning A (that'll teach me for rushing), so this isn't yet working code.

0 votes
answered Dec 18, 2008 by victor

well some pseudo code from the top of my head here:

select from table where PI = 10 or pi =11, etc

store the result in a temp table

select distinct PO and count(PI) from temp table.

now for each PO you can get the total available PI offerings. if the number of PIs available matches the count in the temp table, it means that you have all the PIs for that PO. add all the POs and you ave your result set.

0 votes
answered Dec 18, 2008 by vilx

IMHO impossible via pure SQL without some stored-procedure code. But... i'm not sure.

Added: On the other hand, I'm getting an idea about a recursive query (in MSSQL 2005 there is such a thing, which allows you to join a query with it's own results until there are no more rows returned) which might "gather" the correct answers by cross-joining the results of previous step with all products and then filtering out invalid combinations. You would however get all permutations of valid combinations and it would hardly be efficient. And the idea is pretty vague, so I can't guarantee that it can actually be implemented.

0 votes
answered Dec 18, 2008 by charles-bretana
  Select Distinct PO
   From Table T
   -- Next eliminates POs that contain other PIs
   Where Not Exists 
       (Select * From Table 
        Where PO = T.PO
            And PI Not In (10, 11, 12))
     -- And this eliminates POs that do not contain all the PIs
     And Not Exists 
        (Select Distinct PI From Table  
         Where PI In (10, 11, 12)
           Except 
         Select Distinct PI From Table  
         Where PO = T.PO

or, if your database does not implement EXCEPT...

   Select Distinct PO
   From Table T
   -- Next predicate eliminates POs that contain other PIs
   Where Not Exists 
       (Select * From Table 
        Where PO = T.PO
            And PI Not In (10, 11, 12))
     -- And this eliminates POs that do not contain ALL the PIs
     And Not Exists 
         (Select Distinct PI From Table A
          Where PI In (10, 11, 12)
             And Not Exists
                 (Select Distinct PI From Table 
                  Where PO = T.PO 
                     And PdI = A.PI))                 
0 votes
answered Dec 18, 2008 by l15a

You will need a count of the items in your list, i.e. @list_count. Figure out which Offerings have Instances that aren't in the list. Select all Offerings that aren't in that list and do have Instances in the list:

select P0,count(*) c from table where P0 not in (
select P0 from table where P1 not in (@list)
) and P1 in (@list) group by P0

I would store that in a temp table and select * records where c = @list_count

0 votes
answered Dec 18, 2008 by fake-jim

Edit: Whilst I think mine works fine, Adam's answer is without a doubt more elegant and more efficient - I'll just leave mine here for posterity!

Apologies since I know this has been tagged as an Oracle issue since I started playing. This is some SQL2008 code which I think works for all the stated cases....

declare @test table
(
    [PI] int
)
insert @test values (10), (11), (13)

declare @testCount int
select @testCount = COUNT(*) from @test

;with PO_WITH_COUNTS as 
(
        select  PO_FULL.PO, COUNT(PO_FULL.[PI]) PI_Count
        from    ProductOffering PO_FULL
        left
        join    (
                select  PO_QUALIFYING.PO, PO_QUALIFYING.[PI]
                from    ProductOffering PO_QUALIFYING
                where   PO_QUALIFYING.[PI] in (select [PI] from @test)
                ) AS QUALIFYING
                on      QUALIFYING.PO = PO_FULL.PO
                and     QUALIFYING.[PI] = PO_FULL.[PI]
        group by
                PO_FULL.PO
        having  COUNT(PO_FULL.[PI]) = COUNT(QUALIFYING.[PI])
)
select  PO_OUTER.PO
from    PO_WITH_COUNTS PO_OUTER 
cross 
join    PO_WITH_COUNTS PO_INNER
where   PO_OUTER.PI_Count = @testCount
or      PO_OUTER.PO <> PO_INNER.PO
group by
        PO_OUTER.PO, PO_OUTER.PI_Count
having  PO_OUTER.PI_Count = @testCount 
or      PO_OUTER.PI_Count + SUM(PO_INNER.PI_Count) = @testCount

Not sure if Oracle has CTEs but could just state the inner query as two derived tables. The cross join in the outer query lets us find combinations of offerings that have all the valid items. I know that this will only work based on the statement in the question that the data is such that there is only 1 valid combination for each requested set, Without that it's even more complicated as counts are not enough to remove combinations that have duplicate products in them.

0 votes
answered Dec 18, 2008 by adam-bellaire

Okay, I think I have it. This meets the constraints you provided. There might be a way to simplify this further, but it ate my brain a little:

select distinct PO 
from POPI x 
where 
  PO not in (
    select PO 
    from POPI 
    where PI not in (10,11,12)
  ) 
  and PI not in (
    select PI 
    from POPI 
    where PO != x.PO 
      and PO not in (
        select PO 
        from POPI 
        where PI not in (10,11,12)
      )
  );

This yields only results who fill the given set which are disjoint with all other results, which I think is what you were asking for. For the test examples given:

  • Providing 10,11,12 yields A
  • Providing 10,11,13 yields B,C
0 votes
answered Dec 18, 2008 by noah

I tested this under 4 sets of values and they all returned a correct result. This uses a function that I use in SQL to generate a table from a string of parameters separated by semicolons.

DECLARE @tbl TABLE (
    po varchar(10),
    pii int)

INSERT INTO @tbl
SELECT 'A', 10
UNION ALL
SELECT 'A', 11
UNION ALL
SELECT 'A', 12
UNION ALL
SELECT 'B', 10
UNION ALL
SELECT 'B', 11
UNION ALL
SELECT 'C', 13

DECLARE @value varchar(100)
SET @value = '10;11;12;'
--SET @value = '11;10;'
--SET @value = '13;'
--SET @value = '10;'

SELECT DISTINCT po
FROM @tbl a
INNER JOIN fMultiValParam (@value) p ON
a.pii = p.paramid
WHERE a.po NOT IN (
    SELECT t.po
    FROM @tbl t
    LEFT OUTER JOIN (SELECT *
            FROM @tbl tt
            INNER JOIN fMultiValParam (@value) p ON
            tt.pii = p.paramid) tt ON
    t.pii = tt.pii
    AND t.po = tt.po
    WHERE tt.po IS NULL)

here's the function

CREATE    FUNCTION [dbo].[fMultiValParam]
(@Param varchar(5000))
RETURNS @tblParam TABLE (ParamID varchar(40))
AS
BEGIN

IF (@Param IS NULL OR LEN(@Param) < 2)
BEGIN
    RETURN
END

DECLARE @len INT
DECLARE @index INT
DECLARE @nextindex INT

SET @len = DATALENGTH(@Param)
SET @index = 0
SET @nextindex = 0

WHILE (@index < @len)
BEGIN
    SET @Nextindex = CHARINDEX(';', @Param, @index)

    INSERT INTO @tblParam
    SELECT SUBSTRING(@Param, @index, @nextindex - @index)

    SET @index = @nextindex + 1

END
RETURN
END
0 votes
answered Dec 18, 2008 by acoustickitty

Try this:

SELECT DISTINCT COALESCE ( offer, NULL )
FROM products
WHERE instance IN ( @instancelist )
0 votes
answered Dec 18, 2008 by tuinstoel

Is it possible that a customers asks for a product more than once?

For example: he/she asks an offering for 10,10,11,11,12?

If this is possible than solutions like

select ... from ... where pi in (10,10,11,11,12)

will not work.

Because 'pi in (10,10,11,11,12)' is the same as 'pi in (10,11,12)'.

A solution for 10,10,11,11,12 is A&B.

Welcome to Q&A, where you can ask questions and receive answers from other members of the community.
Website Online Counter

...