# How to filter multiple many to many relationship based on multiple tags?

I've a scheme of two main tables: `problem` and `tag` and a relation (which is a many to many connector) table: `problem_tags` which excerpt of them is like:

Problem table:

``````----+------------------------------------+--------
id |                name                | rating
----+------------------------------------+--------
1 | Special Permutation                |   1600
2 | Binary String Reconstruction       |   1500
3 | Special Elements                   |   1500
4 | Alice, Bob and Candies             |   1300
5 | K-th Not Divisible by n            |   1200
6 | Same Parity Summands               |   1200
7 | Sum of Round Numbers               |    800
8 | Skier                              |   1400
9 | Square?                            |    900
``````

Tag table:

`````` id |           name
----+---------------------------
1 | constructive algorithms
2 | dfs and similar
3 | math
4 | brute force
5 | implementation
6 | two pointers
7 | binary search
8 | data structures
``````

Problem tags table:

`````` problem_id | tag_id
------------+--------
1 |      1
2 |      1
2 |      2
2 |      3
3 |      4
3 |      5
3 |      6
4 |      5
5 |      3
5 |      7
``````

My question is how can I filter out problems based on multiple tags, i.e. all problems that are tagged math and binary search and brute force; or all problems that are tagged math but not constructive algorithms; or for a more complex one all problems that are only tagged with math and implementation and nothing else?

Currently I've come up with something like this:

1. Find all problem's ids that are tagged math (joining tag and problem_tags table)
2. Find all problem's ids that are tagged binary search
3. Find all problem's ids that are tagged brute force
4. Get intersection of all above ids
5. Select problems where their ids is in the above intersection

But my solution lacks when it reaches the second example (only tagged with selected tags) and I think it's not the most optimal and SQL-ish way for doing it.

I had just asked that on a different forum. The best solution for a 3rd Normal Form schema design was to select all that is needed in the linking table and compare the Cardinality (count) of the matching results.

The other forum was for Oracle. The answer you seek is the PostgreSQL version of this post: https://community.oracle.com/message/15613817#15613817

``````-- copy paste from original post
-- Oracle version
select *
from my_recipes rp
where rp.recipe_id  in
(
select tg.recipe_id
from my_recipe_tags tg
where tg.tag_id in    (
-- expands string '1:2:3' into a table w/ 3 row
select to_number(regexp_substr(:p_search_tags,'[^:]+', 1, level) )
from  dual
connect by regexp_substr(:p_search_tags, '[^:]+', 1, level) is not null
)
group by tg.recipe_id
-- counts cardinality of Tags in search
having count(*) = regexp_count(:p_search_tags, '[^:]+')
) ;
``````

Untested (needs to be fixed)

``````select *
from PROBLEMS p
where p.id in (
select pt.problem_id
from PROBLEM_TAGS pt
join TAGS t on pt.tag_id = t.tag_id
where t.name in ('math','binary search', 'brute force') -- should be from a CTE
group by pt.problem_id
having count(*) = 3 -- count(*) from CTE
)
``````

For the 2nd version, add `AND p.id NOT IN` clause.

For the 3rd version add a filter that ensures `pt.problem_id` has the exact cardinality of the queried tags.

``````and p.id in (
select pt.problem_id
from PROBLEM_TAGS pt
group by pt.problem_id
having count(*) = 2 -- you have two tags for 3rd one
-- you should pull Cardinality from CTE also
)
``````
• I'm not that much of an expert in `SQL` so I'll appreciate if you could map your solution to my asked schema. – Masked Man May 20 '20 at 22:33
• @MaskedMan - I need the `CREATE TABLE` and `INSERT` statements to test. If you can set the schema up on db fiddle, I can ensure the SQL statements actually work. Edit your original post and add the link, please. thanks. – Michael Kutz May 20 '20 at 22:58
• I think it's the solution that I'm looking for but 2 issues here, First: what is the purpose of `having count(*) = 3` after the `group by` part, could you explain it a bit? cause when I changed it, the result set changed, I have some guesses but not sure. Second: in the second code snippet in `join TAGS t on pt.tag_id = t.tag_id` change the `t.tag_id` to `t.id` as `Tag` table has `id` and not `tag_id` ;). – Masked Man May 21 '20 at 0:22
• I'll appreciate if you answer my previous comment. – Masked Man May 21 '20 at 23:46
• @MaskedMan - `3` is the Cardinality of the Tags you are querying. It should be something like `( select count(*) from list_of_must_have_tags )`. I don't know PostgreSQL syntax that well to demonstrate that concept. Having a link to DB Fiddle would be helpful. ;) – Michael Kutz May 22 '20 at 12:57