Left join conditions to convert permutation into combination of rows

I ha开发者_Go百科ve a table of plans e.g.

id | service_1 | service_2 | ...
---------------------------------
1  |   true    |  true     | ...
2  |   true    |  false    | ...
3  |   false   |  true     | ...

I am generating the permutation of rows by left joining the table on itself (any number of times).

SELECT t1.id, t2.id, t3.id
FROM plans AS t1 
LEFT JOIN plans AS t2
  ON t1.id != t2.id
  AND ...
LEFT JOIN plans AS t3
  ON t1.id != t2.id AND t2.id != t3.id AND t3.id != t1.id
  AND ...

How can I generate all the different combinations that provide service_1 and service_2 whilst avoiding duplication. The joining row cannot contain the same service e.g.

id | service_1 | service_2 | id | service_1 | service_2 |
---------------------------------------------------------
1  |   true    |  true     |NULL|    NULL   |    NULL   |
2  |   true    |  false    | 3  |    false  |    true   |

I am struggling with the join conditions for this approach. Also, is this fundamentally the wrong approach for solving this problem?

Possible ways I am trying to avoid duplication are:

• ordered sets (I am yet to get this working) e.g. t1.id < t2.id

• sort(array[t1.id,t2.id]) AS ids ... GROUP BY ids

Also, is this fundamentally the wrong approach for solving this problem?

I think so. This looks similar to the set packing problem and/or the set cover problem.

I don't think it would be feasible (or maybe even possible) to do this with a single query. You need as many joins as there are services to be covered, and a number of WHERE conditions a function of that number.

I think a naïve, brute-force approach with simple pruning may work here, since what you want is a list of all the possible combinations anyway. Or you could pre-compute all the valid combinations and store them in a large table.

Whatever you do, this looks like at least O(rows^cols) work to me.

Say you have the id's 1,2,3 4. SELECT * FROM plans A INNER JOIN plans B ON B.Id >= A.id will give you the following sets:

1,1
1,2
1,3
1,4
2,2
2,3
2,4
3,3
3,4
4,4

Which I believe is what you want - you have all 2 set combinations on the plans.

I don't think we have enough table structure/sample input/sample output. The following appears to answer the question for the limited case we're dealing with:

SELECT
    * /* TODO: Proper column list */
FROM
    plans t1
        left join
    plans t2
        on /* since SQL doesn't have a boolean, are the service columns bit? */
            (t1.service_1 = 0 or t2.service_1 = 0) and
            (t1.service_2 = 0 or t2.service_2 = 0)
WHERE
    (t1.service_1 = 1 or t2.service_1 = 1) and
    (t1.service_2 = 1 or t2.service_1 = 1)

Basically, we only satisfy the join where there is a "gap" on one side or the other (service_x = 0), but we require, overall, that there are no gaps.

Sorry if this seems rambling, or doesn't fit the bill. If you could add more samples to your question, and the actual table structure, I may be able to do better.