How do I extend this query to find valid combinations of three items?

Question

I totally don't expect to get any answers here, but I'll try anyway.

So this came out of playing Skyrim. I wanted an easy way to look up what ingredients can be combined to make different potions/poisons so I made an Ingredient table that has an ID and a Name; an Effect table that has an ID, Name, Poison flag, and Potion flag (potion and poison are mutually exclusive); and a join table that has ID for ingredient and ID for effect.

So the way it works is every ingredient has 4 different effects, effects are repeated on mulitple ingredients. In the game you can combine 2 or 3 ingredients and the result is a potion or poison with all of the effects that are matching on at least 2 of the ingredients used. So if you use 3 ingredients and effect1 is on both ingredient1 and ingredient2 and effect2 is on both ingredient1 and ingredient3 your result will be a potion/poison that has both effect1 and effect2.

I was able to come up with a query on my own that will show every possible 2 ingredient combination that creates a potion with no poison effects. First I need to find every possible 2 ingredient combination that only has matching effects that are not "poison":

SELECT i1.UniqIngredient UniqIngredient1, i2.UniqIngredient UniqIngredient2
FROM Ingredient i1
CROSS JOIN Ingredient i2
INNER JOIN IngredientEffectJT jt1 ON i1.UniqIngredient = jt1.UniqIngredient
INNER JOIN IngredientEffectJT jt2 ON i2.UniqIngredient = jt2.UniqIngredient
INNER JOIN Effect e ON jt1.UniqEffect = e.UniqEffect AND jt2.UniqEffect = e.UniqEffect
WHERE i1.UniqIngredient < i2.UniqIngredient
GROUP BY i1.UniqIngredient, i2.UniqIngredient
HAVING SUM(e.Poison) = 0

Ingredient is cross joined with Ingredient to get every combination but because the order of the ingredients doesn't matter, I'd end up with double the results. That's why the WHERE checks i1.UniqIngredient < i2.UniqIngredient. I will only ever see each combination once and the lower ID of the 2 ingredients will always be in the 1st column. I join both ingredients to the same effect, because I only care about combinations that produce a result. Then I group them by the 2 ingredients and count up how many poison effects they share because I only want combinations that have 0 poison effects.

Then I use this result as a table that I join back to the Ingredient and Effect tables to get a list of every possible 2 ingredient combination that produces potions, and what effects each combination has:

SELECT i1.Name, i2.Name, e.Name
FROM (SELECT i1.UniqIngredient UniqIngredient1, i2.UniqIngredient UniqIngredient2
FROM Ingredient i1
CROSS JOIN Ingredient i2
INNER JOIN IngredientEffectJT jt1 ON i1.UniqIngredient = jt1.UniqIngredient
INNER JOIN IngredientEffectJT jt2 ON i2.UniqIngredient = jt2.UniqIngredient
INNER JOIN Effect e ON jt1.UniqEffect = e.UniqEffect AND jt2.UniqEffect = e.UniqEffect
WHERE i1.UniqIngredient < i2.UniqIngredient
GROUP BY i1.UniqIngredient, i2.UniqIngredient
HAVING SUM(e.Poison) = 0) il
INNER JOIN Ingredient i1 ON il.UniqIngredient1 = i1.UniqIngredient
INNER JOIN Ingredient i2 ON il.UniqIngredient2 = i2.UniqIngredient
INNER JOIN IngredientEffectJT jt1 ON i1.UniqIngredient = jt1.UniqIngredient
INNER JOIN IngredientEffectJT jt2 ON i2.UniqIngredient = jt2.UniqIngredient
INNER JOIN Effect e ON jt1.UniqEffect = e.UniqEffect AND jt2.UniqEffect = e.UniqEffect
ORDER BY i1.Name, i2.Name, e.Name

Using the same query I can find 2 ingredient poison combinations that have no potion effects just by changing the HAVING line to check e.Potion instead of e.Poison.

This is all fine and good, but when I want to introduce the 3rd ingredient that's where it gets tricky. I'm stumped. I can modify this query to check for 3 ingredients that all have the same effect, but that's not what I want. I want to find a 3rd ingredient that has a different effect in common with 1 of the ingredients.

Any help?

---

EDIT

---

Update: So after struggling with this for hours I have come up with a big, ugly, slow, hard to follow query (I actually don't even remember why I had to do that crazy join condition on the Effect table. But when I change it the whole query is 2x slower so it's actually faster the way I have it, though I don't know why...), that almost does what I want. This might just be as close as I can get, unless someone has any other ideas or sees a way to improve my new query.

SELECT DISTINCT il.Name1, il.Name2, il.Name3, e.Name
FROM
(SELECT DISTINCT i1.UniqIngredient Ingredient1, i1.Name Name1, i2.UniqIngredient Ingredient2, i2.Name Name2, i3.UniqIngredient Ingredient3, i3.Name Name3
FROM Ingredient i1
INNER JOIN Ingredient i2 ON i1.UniqIngredient < i2.UniqIngredient
INNER JOIN Ingredient i3 ON i2.UniqIngredient < i3.UniqIngredient
INNER JOIN IngredientEffectJT jt1 ON i1.UniqIngredient = jt1.UniqIngredient
INNER JOIN IngredientEffectJT jt2 ON i2.UniqIngredient = jt2.UniqIngredient
INNER JOIN IngredientEffectJT jt3 ON i3.UniqIngredient = jt3.UniqIngredient
INNER JOIN Effect e ON (jt1.UniqEffect = e.UniqEffect AND (jt2.UniqEffect = e.UniqEffect OR jt3.UniqEffect = e.UniqEffect)) OR (jt2.UniqEffect = e.UniqEffect AND jt3.UniqEffect = e.UniqEffect)
WHERE (EXISTS (SELECT 1
               FROM IngredientEffectJT jt1
               INNER JOIN IngredientEffectJT jt2 ON jt1.UniqEffect = jt2.UniqEffect
               WHERE jt1.UniqIngredient = i1.UniqIngredient 
               AND jt2.UniqIngredient = i2.UniqIngredient)
       AND (EXISTS (SELECT 1
                    FROM IngredientEffectJT jt1
                    INNER JOIN IngredientEffectJT jt3 ON jt1.UniqEffect = jt3.UniqEffect
                    WHERE jt1.UniqIngredient = i1.UniqIngredient 
                    AND jt3.UniqIngredient = i3.UniqIngredient)
         OR EXISTS (SELECT 1
                    FROM IngredientEffectJT jt2
                    INNER JOIN IngredientEffectJT jt3 ON jt2.UniqEffect = jt3.UniqEffect
                    WHERE jt2.UniqIngredient = i2.UniqIngredient 
                    AND jt3.UniqIngredient = i3.UniqIngredient)))
       OR (EXISTS (SELECT 1
                  FROM IngredientEffectJT jt1
                  INNER JOIN IngredientEffectJT jt3 ON jt1.UniqEffect = jt3.UniqEffect
                  WHERE jt1.UniqIngredient = i1.UniqIngredient 
                  AND jt3.UniqIngredient = i3.UniqIngredient)
      AND EXISTS (SELECT 1
                  FROM IngredientEffectJT jt2
                  INNER JOIN IngredientEffectJT jt3 ON jt2.UniqEffect = jt3.UniqEffect
                  WHERE jt2.UniqIngredient = i2.UniqIngredient 
                  AND jt3.UniqIngredient = i3.UniqIngredient))
GROUP BY i1.UniqIngredient, i1.Name, i2.UniqIngredient, i2.Name, i3.UniqIngredient, i3.Name
HAVING SUM(e.Poison) = 0) il
INNER JOIN IngredientEffectJT jt1 ON il.Ingredient1 = jt1.UniqIngredient
INNER JOIN IngredientEffectJT jt2 ON il.Ingredient2 = jt2.UniqIngredient
INNER JOIN IngredientEffectJT jt3 ON il.Ingredient3 = jt3.UniqIngredient
INNER JOIN Effect e ON (jt1.UniqEffect = e.UniqEffect AND (jt2.UniqEffect = e.UniqEffect OR jt3.UniqEffect = e.UniqEffect)) OR (jt2.UniqEffect = e.UniqEffect AND jt3.UniqEffect = e.UniqEffect)
ORDER BY il.Name1, il.Name2, il.Name3, e.Name

In the inner query:

FROM Ingredient i1
INNER JOIN Ingredient i2 ON i1.UniqIngredient < i2.UniqIngredient
INNER JOIN Ingredient i3 ON i2.UniqIngredient < i3.UniqIngredient

This creates every possible combination of 3 ingredients where order does not matter and nothing is repeated. Then the Joins to IngredientEffectJT and Effect... I actually don't remember what the crazy join on Effect is for. Looking at it, I thought it was to ensure an effect exists on at least 2 ingredients, but that's what the WHERE clause is doing. And simplifying that Effect join causes it to run significantly slower so...whatever.

Then the GROUP BY is there so I can count the number of matching poison effects. Since I had to group by the 3 ingredients, I lose the individual matching effects so then I need to rejoin all of those ingredients back to their effects and find the effects that match.

The problem with this query is that it will show combinations where all 3 ingredients have the same 1 effect. Those combinations are pointless because you can make the same thing by only using 2 of those 3 so it's kind of wasteful.

So, this is the best I could come up with. It's really slow so maybe I'll just save it to a new table to make it easier and faster to query again in the future.

Answer 1

Try this

declare @combos table (comboId int identity, ingredient1 int, ingredient2 int, ingredient3 int null)

--create table of all unique 2 and 3 ingredient combinations (unique potions)
insert int @combos (ingredient1, ingredient2, ingredient3)
select 
    distinct
    i1.ID,
    i2.ID,
    i3.ID
from
    ingredient i1
    inner join ingredient i2 on i1.ID < i2.ID
    left outer join ingredient i3 on i2.ID < i3.ID

--create table to hold mapping between unique combinations and ingredients
declare @combo_ingredient table (ComboId int, IngredientId int)

--insert into the mapping table
insert into @combo_ingredient (ComboId, IngredientId)
select ID, ingredient1 from @combos

insert into @combo_ingredient (ComboId, IngredientId)
select ID, ingredient1 from @combos

insert into @combo_ingredient (ComboId, IngredientId)
select ID, ingredient3 from @combos where ingredient3 is not null

--create table to hold mapping between unique combinations (potions) and the effects it will have
declare @combo_effect (comboId int, effectId int)

insert into @combo_effect (comboId, effectId)
select 
    c.ComboId, ec.EffectId
from
    @combo_ingredient c
    inner join effect_ingredient ec on c.IngredientId = ec.IngredientId
having
    count(*) > 1
group by 
    c.comboId, ec.EffectId

--remove combinations that include an ingredient that do not contribute to an effect
delete from @combo_effect ce
where ce.ComboId in (
    select 
        ci.ComboId 
    from 
        @combo_ingredient ci
        inner join effect_ingredient ei on ci.IngredientId = ei.IngredientId
        left outer join @combo_effect ce on ce.ComboId = ci.ComboId and ce.EffectId = ei.EffectId
    where 
        ce.ComboId is null
)

--you can then query combo_effect for whatever information you want
--all combos with no poison effects
select comboId from 
    @combo_effect ce 
    left outer join effect e on ce.effectId = e.effectId and e.PoisonFlag = 1
group by 
    comboId
having 
    Count(e.id) = 0