Recursive sql problem

Question

Hi, 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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

  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))

Answer 5

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

Answer 6

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.

Answer 7

Hi,

If we redefine a bit a problem:

Lets have a customer table with product instances:

crete table cust_pi (
pi varchar(5),
customer varchar(5));

And a "product_catalogue" table:

CREATE TABLE PI_PO_TEST
   ("PO" VARCHAR2(5 CHAR),
   "PI" VARCHAR2(5 CHAR)
           );

Lets fill it with some sample data:

insert into CUST_PI (PI, CUSTOMER)
values ('11', '1');
insert into CUST_PI (PI, CUSTOMER)
values ('10', '1');
insert into CUST_PI (PI, CUSTOMER)
values ('12', '1');
insert into CUST_PI (PI, CUSTOMER)
values ('13', '1');
insert into CUST_PI (PI, CUSTOMER)
values ('14', '1');
insert into PI_PO_TEST (PO, PI)
values ('A', '10');
insert into PI_PO_TEST (PO, PI)
values ('A', '11');
insert into PI_PO_TEST (PO, PI)
values ('A', '12');
insert into PI_PO_TEST (PO, PI)
values ('A', '13');
insert into PI_PO_TEST (PO, PI)
values ('B', '14');
insert into PI_PO_TEST (PO, PI)
values ('C', '11');
insert into PI_PO_TEST (PO, PI)
values ('C', '12');
insert into PI_PO_TEST (PO, PI)
values ('D', '15');
insert into PI_PO_TEST (PO, PI)
values ('D', '14');

Then my first shoot solution is like this:

select po1 po /* select all product offerings that match the product definition 
                (i.e. have the same number of product instances per offering as 
                in product catalogue */
  from (select po po1, count(c.pi) k1
          from cust_pi c, pi_po_test t
         where c.pi = t.pi
           and customer = 1
         group by po) t1,
       (select po po2, count(*) k2 from pi_po_test group by po) t2
 where k1 = k2
   and po1 = po2
minus /* add those, that are contained within others */
select slave
  from (select po2 master, po1 slave
  /* this query returns, that if you have po "master" slave should be removed from result, 
     as it is contained within*/
          from (select t1.po po1, t2.po po2, count(t1.po) k1
                  from pi_po_test t1, pi_po_test t2
                 where t1.pi = t2.pi
                 group by t1.po, t2.po) t1,
               (select po, count(po) k2 from pi_po_test group by po) t2
         where t1.po2 = t2.po
           and k1 < k2)
 where master in
 /* repeated query from begining. This could be done better :-) */
       (select po1 po
          from (select po po1, count(c.pi) k1
                  from cust_pi c, pi_po_test t
                 where c.pi = t.pi
                   and customer = 1
                 group by po) t1,
               (select po po2, count(*) k2 from pi_po_test group by po) t2
         where k1 = k2
           and po1 = po2)

All of that was done on Oracle, so your mileage may vary

Answer 8

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

Answer 9

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

Answer 10

SELECT DISTINCT COALESCE ( offer, NULL ) FROM products WHERE instance IN ( @instancelist )

Answer 11

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.