# Return to Question

 4 deleted 13 characters in body edited Jun 13 '15 at 21:48 Robert Harvey♦ 172k4747 gold badges403403 silver badges611611 bronze badges Formally, let s(U, Q) = {V | V ∈ U and V ⊆ Q} where U, Q, and V all represent sets, and U, more specifically, represents a set of sets. For the sake of example, U might be a set of the (sets of) ingredients required for various recipes in a cookbook with Q representing the set of ingredients I have V representing a recipe I could make with those ingredients. The query s(U, Q) corresponds to the question "What all can I make with these ingredients?" What I'm looking for is a data representation that indexes U in such a way that it supports efficient queries of s(U, Q) where Q and all members of U will generally be small compared to the union of all the members of U. In addition, I'd like it to be able to efficiently update U (e.g., add or remove a recipe). I can't help but think that this problem must be well understood, but I haven't been able to find a name or reference for it. Does anyone know of a strategy for solving this efficiently or a place where I can read more about it? As far as thinking about a solution, one thought I had was to build a decision tree for the set U. At each node in the tree, the question "does your ingredient list contain x?" would be asked with x chosen to maximize the number of members of U that get eliminated by the answer. As U gets updated, this decision tree would need to be re-balanced to minimize the number of questions required to find the correct result. Another thought is to represent U with something like an n-dimensional boolean 'octree' (where n is the number of unique ingredients). I believe that "What recipes can be made with these ingredients?" can be answered by taking the cartesian product of the (sets of ingredients required for the) recipes in the cookbook with the powerset of the ingredients one has and filtering the resulting ordered pairs for pairs in which both elements are equal, but this is not an efficient solution, and what I'm asking about is how to optimize this kind of operation; how would one compose this in SQL such that it would be efficient and what does SQL do that allows this to be efficient? Edit: Although I use the illustration of a cookbook of recipes and a set of ingredients, I anticipate that the number of 'recipes' and the number of 'ingredients' will be very large (up to hundreds of thousands each), though the number of ingredients in a given recipe and the number of ingredients in a given ingredient set will be relatively small (probably around 10-50 for a typical 'recipe' and around 100 for a typical 'ingredient set'). Additionally, the most common operation will be the query s(U, Q), so it should be most optimal. This also means that a brute force algorithm that requires checking every recipe or operating over every ingredient would be undesirably slow on its own, however. With clever caching, I think this might not perform too badly, though. Formally, let s(U, Q) = {V | V ∈ U and V ⊆ Q} where U, Q, and V all represent sets, and U, more specifically, represents a set of sets. For the sake of example, U might be a set of the (sets of) ingredients required for various recipes in a cookbook with Q representing the set of ingredients I have V representing a recipe I could make with those ingredients. The query s(U, Q) corresponds to the question "What all can I make with these ingredients?" What I'm looking for is a data representation that indexes U in such a way that it supports efficient queries of s(U, Q) where Q and all members of U will generally be small compared to the union of all the members of U. In addition, I'd like it to be able to efficiently update U (e.g., add or remove a recipe). I can't help but think that this problem must be well understood, but I haven't been able to find a name or reference for it. Does anyone know of a strategy for solving this efficiently or a place where I can read more about it? As far as thinking about a solution, one thought I had was to build a decision tree for the set U. At each node in the tree, the question "does your ingredient list contain x?" would be asked with x chosen to maximize the number of members of U that get eliminated by the answer. As U gets updated, this decision tree would need to be re-balanced to minimize the number of questions required to find the correct result. Another thought is to represent U with something like an n-dimensional boolean 'octree' (where n is the number of unique ingredients). I believe that "What recipes can be made with these ingredients?" can be answered by taking the cartesian product of the (sets of ingredients required for the) recipes in the cookbook with the powerset of the ingredients one has and filtering the resulting ordered pairs for pairs in which both elements are equal, but this is not an efficient solution, and what I'm asking about is how to optimize this kind of operation; how would one compose this in SQL such that it would be efficient and what does SQL do that allows this to be efficient? Edit: Although I use the illustration of a cookbook of recipes and a set of ingredients, I anticipate that the number of 'recipes' and the number of 'ingredients' will be very large (up to hundreds of thousands each), though the number of ingredients in a given recipe and the number of ingredients in a given ingredient set will be relatively small (probably around 10-50 for a typical 'recipe' and around 100 for a typical 'ingredient set'). Additionally, the most common operation will be the query s(U, Q), so it should be most optimal. This also means that a brute force algorithm that requires checking every recipe or operating over every ingredient would be undesirably slow on its own, however. With clever caching, I think this might not perform too badly, though. Formally, let s(U, Q) = {V | V ∈ U and V ⊆ Q} where U, Q, and V all represent sets, and U, more specifically, represents a set of sets. For the sake of example, U might be a set of the (sets of) ingredients required for various recipes in a cookbook with Q representing the set of ingredients I have V representing a recipe I could make with those ingredients. The query s(U, Q) corresponds to the question "What all can I make with these ingredients?" What I'm looking for is a data representation that indexes U in such a way that it supports efficient queries of s(U, Q) where Q and all members of U will generally be small compared to the union of all the members of U. In addition, I'd like it to be able to efficiently update U (e.g., add or remove a recipe). I can't help but think that this problem must be well understood, but I haven't been able to find a name or reference for it. Does anyone know of a strategy for solving this efficiently or a place where I can read more about it? As far as thinking about a solution, one thought I had was to build a decision tree for the set U. At each node in the tree, the question "does your ingredient list contain x?" would be asked with x chosen to maximize the number of members of U that get eliminated by the answer. As U gets updated, this decision tree would need to be re-balanced to minimize the number of questions required to find the correct result. Another thought is to represent U with something like an n-dimensional boolean 'octree' (where n is the number of unique ingredients). I believe that "What recipes can be made with these ingredients?" can be answered by taking the cartesian product of the (sets of ingredients required for the) recipes in the cookbook with the powerset of the ingredients one has and filtering the resulting ordered pairs for pairs in which both elements are equal, but this is not an efficient solution, and what I'm asking about is how to optimize this kind of operation; how would one compose this in SQL such that it would be efficient and what does SQL do that allows this to be efficient? Although I use the illustration of a cookbook of recipes and a set of ingredients, I anticipate that the number of 'recipes' and the number of 'ingredients' will be very large (up to hundreds of thousands each), though the number of ingredients in a given recipe and the number of ingredients in a given ingredient set will be relatively small (probably around 10-50 for a typical 'recipe' and around 100 for a typical 'ingredient set'). Additionally, the most common operation will be the query s(U, Q), so it should be most optimal. This also means that a brute force algorithm that requires checking every recipe or operating over every ingredient would be undesirably slow on its own, however. With clever caching, I think this might not perform too badly, though. 3 added 791 characters in body edited Jun 13 '15 at 21:09 nben 6811 silver badge77 bronze badges Formally, let s(U, Q) = {V | V ∈ U and V ⊆ Q} where U, Q, and V all represent sets, and U, more specifically, represents a set of sets. For the sake of example, U might be a set of the (sets of) ingredients required for various recipes in a cookbook with Q representing the set of ingredients I have V representing a recipe I could make with those ingredients. The query s(U, Q) corresponds to the question "What all can I make with these ingredients?" What I'm looking for is a data representation that indexes U in such a way that it supports efficient queries of s(U, Q) where Q and all members of U will generally be small compared to the union of all the members of U. In addition, I'd like it to be able to efficiently update U (e.g., add or remove a recipe). I can't help but think that this problem must be well understood, but I haven't been able to find a name or reference for it. Does anyone know of a strategy for solving this efficiently or a place where I can read more about it? As far as thinking about a solution, one thought I had was to build a decision tree for the set U. At each node in the tree, the question "does your ingredient list contain x?" would be asked with x chosen to maximize the number of members of U that get eliminated by the answer. As U gets updated, this decision tree would need to be re-balanced to minimize the number of questions required to find the correct result. Another thought is to represent U with something like an n-dimensional boolean 'octree' (where n is the number of unique ingredients). I believe that "What recipes can be made with these ingredients?" can be answered by taking the cartesian product of the (sets of ingredients required for the) recipes in the cookbook with the powerset of the ingredients one has and filtering the resulting ordered pairs for pairs in which both elements are equal, but this is not an efficient solution, and what I'm asking about is how to optimize this kind of operation; how would one compose this in SQL such that it would be efficient and what does SQL do that allows this to be efficient? Edit: Although I use the illustration of a cookbook of recipes and a set of ingredients, I anticipate that the number of 'recipes' and the number of 'ingredients' will be very large (up to hundreds of thousands each), though the number of ingredients in a given recipe and the number of ingredients in a given ingredient set will be relatively small (probably around 10-50 for a typical 'recipe' and around 100 for a typical 'ingredient set'). Additionally, the most common operation will be the query s(U, Q), so it should be most optimal. This also means that a brute force algorithm that requires checking every recipe or operating over every ingredient would be undesirably slow on its own, however. With clever caching, I think this might not perform too badly, though. Formally, let s(U, Q) = {V | V ∈ U and V ⊆ Q} where U, Q, and V all represent sets, and U, more specifically, represents a set of sets. For the sake of example, U might be a set of the (sets of) ingredients required for various recipes in a cookbook with Q representing the set of ingredients I have V representing a recipe I could make with those ingredients. The query s(U, Q) corresponds to the question "What all can I make with these ingredients?" What I'm looking for is a data representation that indexes U in such a way that it supports efficient queries of s(U, Q) where Q and all members of U will generally be small compared to the union of all the members of U. In addition, I'd like it to be able to efficiently update U (e.g., add or remove a recipe). I can't help but think that this problem must be well understood, but I haven't been able to find a name or reference for it. Does anyone know of a strategy for solving this efficiently or a place where I can read more about it? As far as thinking about a solution, one thought I had was to build a decision tree for the set U. At each node in the tree, the question "does your ingredient list contain x?" would be asked with x chosen to maximize the number of members of U that get eliminated by the answer. As U gets updated, this decision tree would need to be re-balanced to minimize the number of questions required to find the correct result. Another thought is to represent U with something like an n-dimensional boolean 'octree' (where n is the number of unique ingredients). I believe that "What recipes can be made with these ingredients?" can be answered by taking the cartesian product of the (sets of ingredients required for the) recipes in the cookbook with the powerset of the ingredients one has and filtering the resulting ordered pairs for pairs in which both elements are equal, but this is not an efficient solution, and what I'm asking about is how to optimize this kind of operation; how would one compose this in SQL such that it would be efficient and what does SQL do that allows this to be efficient? Formally, let s(U, Q) = {V | V ∈ U and V ⊆ Q} where U, Q, and V all represent sets, and U, more specifically, represents a set of sets. For the sake of example, U might be a set of the (sets of) ingredients required for various recipes in a cookbook with Q representing the set of ingredients I have V representing a recipe I could make with those ingredients. The query s(U, Q) corresponds to the question "What all can I make with these ingredients?" What I'm looking for is a data representation that indexes U in such a way that it supports efficient queries of s(U, Q) where Q and all members of U will generally be small compared to the union of all the members of U. In addition, I'd like it to be able to efficiently update U (e.g., add or remove a recipe). I can't help but think that this problem must be well understood, but I haven't been able to find a name or reference for it. Does anyone know of a strategy for solving this efficiently or a place where I can read more about it? As far as thinking about a solution, one thought I had was to build a decision tree for the set U. At each node in the tree, the question "does your ingredient list contain x?" would be asked with x chosen to maximize the number of members of U that get eliminated by the answer. As U gets updated, this decision tree would need to be re-balanced to minimize the number of questions required to find the correct result. Another thought is to represent U with something like an n-dimensional boolean 'octree' (where n is the number of unique ingredients). I believe that "What recipes can be made with these ingredients?" can be answered by taking the cartesian product of the (sets of ingredients required for the) recipes in the cookbook with the powerset of the ingredients one has and filtering the resulting ordered pairs for pairs in which both elements are equal, but this is not an efficient solution, and what I'm asking about is how to optimize this kind of operation; how would one compose this in SQL such that it would be efficient and what does SQL do that allows this to be efficient? Edit: Although I use the illustration of a cookbook of recipes and a set of ingredients, I anticipate that the number of 'recipes' and the number of 'ingredients' will be very large (up to hundreds of thousands each), though the number of ingredients in a given recipe and the number of ingredients in a given ingredient set will be relatively small (probably around 10-50 for a typical 'recipe' and around 100 for a typical 'ingredient set'). Additionally, the most common operation will be the query s(U, Q), so it should be most optimal. This also means that a brute force algorithm that requires checking every recipe or operating over every ingredient would be undesirably slow on its own, however. With clever caching, I think this might not perform too badly, though. Tweeted twitter.com/#!/StackProgrammer/status/609827440148512769 occurred Jun 13 '15 at 20:59 2 added 545 characters in body edited Jun 13 '15 at 18:43 Robert Harvey♦ 172k4747 gold badges403403 silver badges611611 bronze badges Formally, let s(U, Q) = {V | V ∈ U and V ⊆ Q} where U, Q, and V all represent sets, and U, more specifically, represents a set of sets. For the sake of example, U might be a set of the (sets of) ingredients required for various recipes in a cookbook with Q representing the set of ingredients I have V representing a recipe I could make with those ingredients. The query s(U, Q) corresponds to the question "What all can I make with these ingredients?" What I'm looking for is a data representation that indexes U in such a way that it supports efficient queries of s(U, Q) where Q and all members of U will generally be small compared to the union of all the members of U. In addition, I'd like it to be able to efficiently update U (e.g., add or remove a recipe). I can't help but think that this problem must be well understood, but I haven't been able to find a name or reference for it. Does anyone know of a strategy for solving this efficiently or a place where I can read more about it? As far as thinking about a solution, one thought I had was to build a decision tree for the set U. At each node in the tree, the question "does your ingredient list contain x?" would be asked with x chosen to maximize the number of members of U that get eliminated by the answer. As U gets updated, this decision tree would need to be re-balanced to minimize the number of questions required to find the correct result. Another thought is to represent U with something like an n-dimensional boolean 'octree' (where n is the number of unique ingredients). I believe that "What recipes can be made with these ingredients?" can be answered by taking the cartesian product of the (sets of ingredients required for the) recipes in the cookbook with the powerset of the ingredients one has and filtering the resulting ordered pairs for pairs in which both elements are equal, but this is not an efficient solution, and what I'm asking about is how to optimize this kind of operation; how would one compose this in SQL such that it would be efficient and what does SQL do that allows this to be efficient? Formally, let s(U, Q) = {V | V ∈ U and V ⊆ Q} where U, Q, and V all represent sets, and U, more specifically, represents a set of sets. For the sake of example, U might be a set of the (sets of) ingredients required for various recipes in a cookbook with Q representing the set of ingredients I have V representing a recipe I could make with those ingredients. The query s(U, Q) corresponds to the question "What all can I make with these ingredients?" What I'm looking for is a data representation that indexes U in such a way that it supports efficient queries of s(U, Q) where Q and all members of U will generally be small compared to the union of all the members of U. In addition, I'd like it to be able to efficiently update U (e.g., add or remove a recipe). I can't help but think that this problem must be well understood, but I haven't been able to find a name or reference for it. Does anyone know of a strategy for solving this efficiently or a place where I can read more about it? As far as thinking about a solution, one thought I had was to build a decision tree for the set U. At each node in the tree, the question "does your ingredient list contain x?" would be asked with x chosen to maximize the number of members of U that get eliminated by the answer. As U gets updated, this decision tree would need to be re-balanced to minimize the number of questions required to find the correct result. Another thought is to represent U with something like an n-dimensional boolean 'octree' (where n is the number of unique ingredients). Formally, let s(U, Q) = {V | V ∈ U and V ⊆ Q} where U, Q, and V all represent sets, and U, more specifically, represents a set of sets. For the sake of example, U might be a set of the (sets of) ingredients required for various recipes in a cookbook with Q representing the set of ingredients I have V representing a recipe I could make with those ingredients. The query s(U, Q) corresponds to the question "What all can I make with these ingredients?" What I'm looking for is a data representation that indexes U in such a way that it supports efficient queries of s(U, Q) where Q and all members of U will generally be small compared to the union of all the members of U. In addition, I'd like it to be able to efficiently update U (e.g., add or remove a recipe). I can't help but think that this problem must be well understood, but I haven't been able to find a name or reference for it. Does anyone know of a strategy for solving this efficiently or a place where I can read more about it? As far as thinking about a solution, one thought I had was to build a decision tree for the set U. At each node in the tree, the question "does your ingredient list contain x?" would be asked with x chosen to maximize the number of members of U that get eliminated by the answer. As U gets updated, this decision tree would need to be re-balanced to minimize the number of questions required to find the correct result. Another thought is to represent U with something like an n-dimensional boolean 'octree' (where n is the number of unique ingredients). I believe that "What recipes can be made with these ingredients?" can be answered by taking the cartesian product of the (sets of ingredients required for the) recipes in the cookbook with the powerset of the ingredients one has and filtering the resulting ordered pairs for pairs in which both elements are equal, but this is not an efficient solution, and what I'm asking about is how to optimize this kind of operation; how would one compose this in SQL such that it would be efficient and what does SQL do that allows this to be efficient? 1 asked Jun 13 '15 at 14:35 nben 6811 silver badge77 bronze badges