How to do intersection on a composition table

Question

I have a simple SQL relational model with a many to many relation. Here is the composition table

 ___________________________
| object1_id  | object2_id  |
|---------------------------|

I would like to know all the object1 that are common to a set of object2. My basic feeling is to do a request like this

SELECT c.object1_id FROM composition c WHERE c.object2_id = <given_id_1>
INTERSECT 
SELECT c.object1_id FROM composition c WHERE c.object2_id = <given_id_2>

And if I have N object2 in the set, I'll do N INTERSECT

SELECT c.object1_id FROM composition c WHERE c.object2_id = <given_id_1>
INTERSECT 
SELECT c.object1_id FROM composition c WHERE c.object2_id = <given_id_2>
...
INTERSECT 
SELECT c.object1_id FROM composition c WHERE c.object2_id = <given_id_N>

However, it doesn't look very optimized. Can you help me ? I am not really a SQL expert. I think I could use a JOIN to do that.

Sample

 ___________________________
| object1_id  | object2_id  |
|---------------------------|
|         10  |           1 |
|         11  |           1 |
|         10  |           2 |
|         12  |           2 |
|         10  |           3 |
|         11  |           3 |
|         13  |           3 |

Example

{ object2_id set } => { expected object1_id }
{ 1, 2 } => { 10 }
{ 1, 3 } => { 10, 11 }
{ 1, 2, 3 } => { 10 }

Mark Byers · Accepted Answer · 2012-03-19T18:26:34.743

In terms of performance your query looks OK. Have you measured it to see if there really is a problem?

If (object1_id, object2_id) is unique then you can write the query more concisely as follows:

SELECT object1_id
FROM composition
WHERE object2_id IN (id1, id2, ..., id6)
GROUP BY object1_id
HAVING COUNT(*) = 6

Note that the 6 is the number of provided IDs. This should be changed if a different number of IDs is provided. You would have to measure the actual performance on your dadta to see if this gives any speed increase.

If you can't assume uniqueness then this should work:

SELECT object1_id
FROM composition
WHERE object2_id IN (id1, id2, ..., id6)
GROUP BY object1_id
HAVING COUNT(DISTINCT object2_id) = 6

The most important thing though is to make sure you have appropriate indexes on your table! This is far more important than whether you write one query or the other.

thank you it help me a lot. Your query is really optmized for what I want to do, because my query complexity what O(N) and now it is O(1) (because I will have far more than 2 object to intersect). Thank you again — Baptiste Pernet, Mar 20 '12 at 09:18

score 1 · Answer 2 · answered Mar 19 '12 at 18:23

I believe this should work. It will find all composition 1's that also have a composition 2 that matches. Unless I am misunderstanding what you are looking for. If so, could you provide some sample data?

SELECT c1.object_id 
FROM Composition AS c1
WHERE EXISTS 
    (
        SELECT 1
        FROM Composition c2
        WHERE c2.object2_id = c1.object1_id
        --Add an AND to only look for a certain set of c2's
        --AND c2.object2_id IN (SET of object2id's)
    )

I added a sample and an example, I don't think your query work in my case, I don't need object2_id == object1_id. — Baptiste Pernet, Mar 20 '12 at 09:07

score 0 · Answer 3 · edited May 23 '17 at 12:11

0

I think this is a relational division question.

Analogy: find the supplier who supplies all parts.

object2_id is part_id

object1_id is supplier_id

The query is,

Find supplier_id values for suppliers who supply all parts in the set of part_id values { 1, 2, 3 }.

This is usually qualified with,

...suppliers who supply at least one part and...

otherwise all suppliers would supply the empty set of parts.

edited May 23 '17 at 12:11

Community

1
1

answered Mar 20 '12 at 10:05

onedaywhen

55,269
12
100
138

Could the person downvoting this answer please post their evidence of relational division not being able to solve the problem? The accepted answer looks to me like a classic division pattern but with a hard coded value for the cardinality for the divisor set i.e. will not scale. Thanks ;) – onedaywhen Apr 11 '12 at 06:19
Correct answer, but it isn't typically appreciated much, here in this arena, if you just name the concept and give a link. Maybe that was the reason. – Erwin Smout Apr 11 '12 at 19:08

How to do intersection on a composition table

3 Answers3

Linked