Algoritmo / estructura de datos para responder "¿qué recetas puedo hacer con este conjunto de ingredientes?"

Formalmente, sea s ( U , Q ) = { V | V ∈ U y V ⊆ Q } donde U , Q y V representan conjuntos, y U , más específicamente, representa un conjunto de conjuntos. Por el bien de ejemplo, U podría ser un conjunto de (conjuntos de) ingredientes requeridos para varias recetas en un libro de cocina con Q que representa el conjunto de ingredientes que tengo V que representa una receta que podría hacer con esos ingredientes. La consulta s ( U , Q) corresponde a la pregunta "¿Qué puedo hacer con estos ingredientes?"

Lo que estoy buscando es una representación de datos que indexe U de tal manera que admita consultas eficientes de s ( U , Q ) donde Q y todos los miembros de U generalmente serán pequeños en comparación con la unión de todos los miembros de U . Además, me gustaría poder actualizar eficientemente U (por ejemplo, agregar o eliminar una receta).

No puedo evitar pensar que este problema debe entenderse bien, pero no he podido encontrar un nombre o referencia para él. ¿Alguien sabe de una estrategia para resolver esto de manera eficiente o un lugar donde puedo leer más al respecto?

En lo que pensando en una solución, uno pensaba que tenía era construir un árbol de decisión para el conjunto T . En cada nodo del árbol, la pregunta "¿su lista de ingredientes contiene x ?" se pediría con x elegida para maximizar el número de miembros de U que se eliminan con la respuesta. A medida que U se actualiza, este árbol de decisión necesitaría ser reequilibrado para minimizar el número de preguntas requeridas para encontrar el resultado correcto. Otro pensamiento es representar a U con algo así como un 'octree' booleano n- dimensional (donde n es el número de ingredientes únicos).

Creo que "¿Qué recetas se pueden hacer con estos ingredientes?" puede responderse tomando el producto cartesiano de las (conjuntos de ingredientes necesarios para) las recetas en el libro de cocina con el conjunto de poder de los ingredientes que uno tiene y filtrando los pares ordenados resultantes para pares en los que ambos elementos son iguales, pero esto no es un solución eficiente, y lo que pregunto es cómo optimizar este tipo de operación; ¿Cómo se compondría esto en SQL de modo que fuera eficiente y qué hace SQL que permita que esto sea eficiente?

Aunque utilizo la ilustración de un libro de recetas y un conjunto de ingredientes, anticipo que la cantidad de 'recetas' y la cantidad de 'ingredientes' serán muy grandes (hasta cientos de miles cada una), aunque la cantidad de ingredientes en una receta dada y el número de ingredientes en un conjunto de ingredientes dado será relativamente pequeño (probablemente alrededor de 10-50 para una 'receta' típica y alrededor de 100 para un 'conjunto de ingredientes' típico). Además, la operación más común será la consulta s ( U , Q ), por lo que debería ser la más óptima. Sin embargo, esto también significa que un algoritmo de fuerza bruta que requiere verificar cada receta u operar sobre cada ingrediente sería indeseablemente lento por sí solo. Con almacenamiento en caché inteligente,

Para los números que diste, solo fuerza bruta.

Aquí hay un programa de JavaScript que el bruto lo fuerza para 10 ingredientes en el DB, 10 recetas en el DB, cada receta necesita 2 ingredientes, y tengo 5 ingredientes disponibles:

var i, j;
var numIngredients = 10;
var numRecipes = 10;
var numIngredientsPerRecipe = 2;
var numIngredientsInQuery = 5;

function containsAll(needles, haystack){ 
  var i, len;
  for(i = 0 , len = needles.length; i < len; i++){
      if(haystack.indexOf(needles[i]) == -1) {
          return false;
      }
  }
  return true;
}

// Set up a fake DB of recipes
var ingredients = [];
for (i = 0; i < numIngredients; i++) {
    ingredients.push(i);
}
console.log('Here are the ingredients:', ingredients);

var recipes = [];
for (i = 0; i < numRecipes; i++) {
    var neededIngredients = [];
    for (j = 0; j < numIngredientsPerRecipe; j++) {
        neededIngredients.push(Math.floor(Math.random() * numRecipes));
    }
    recipes.push({ recipeId: i, needed: neededIngredients});
}
console.log('Here are the recipes:', recipes);

// Set up a fake query
var ingredientsAvailable = [];
for (i = 0; i < numIngredientsInQuery; i++) {
    ingredientsAvailable.push(Math.floor(Math.random() * numRecipes));
}

console.log("Here's a query:", ingredientsAvailable);

//Time how long brute force takes
var start = Date.now();
var result = [];
for (i = 0; i < numRecipes; i++) {
    var candidateRecipe = recipes[i];
    if (containsAll(candidateRecipe.needed, ingredientsAvailable)) {
        result.push(candidateRecipe);
    }
}
var end = Date.now();
console.log('Found ' + result.length + ' recipes in ' + (end - start) + ' milliseconds.');
console.log(result);

Se ejecuta en 0 milisegundos. Elegí estos números pequeños para que puedas ejecutarlo tú mismo un par de veces y convencerte de que hace lo que quieres y está relativamente libre de errores.

Ahora cámbielo para que tengamos 1'000'000 ingredientes en el DB, 1'000'000 recetas en el DB, 50 ingredientes por receta y 100 ingredientes disponibles para mí. Es decir, valores que son todos iguales o mayores que el caso de uso más grande que proporcionó.

Se ejecuta en 125 milisegundos bajo nodejs, y esto es con la implementación más tonta sin ningún esfuerzo para optimizar.