I need to model the persistence of combinatorial information. For example, suppose that the combination of 3 attributes (A, B, and C) are used to reference a given product. Besides that, supposed that a given product can belong to different combinations of A, B and C. The queries will be used to constraint the possibilities of product selection based on user requirements. Here, I'm giving a simple example, but this system is intended to combine hundreds of tables with thousands of combinations.

For now I can think in two approachs: Model1:

| key search id | attribute 1 | attribute 2 | product id |
| 1             | value 1     | value 1     | 1          |
| 2             | value 1     | value 2     | 1          |
| 3             | value 2     | value 3     | 2          |
| 4             | value 2     | value 4     | 2          |
| 5             | value 3     | value 5     | 1          |


| key search id | product id  |
| 1             | 1           |
| 2             | 2           |
| 3             | 1           |

| key search id | attribute 1 |
| 1             | value 1     |
| 2             | value 2     |
| 3             | value 3     |

| key search id | attribute 1 |
| 1             | value 1     |
| 1             | value 2     |
| 2             | value 3     |
| 2             | value 4     |
| 3             | value 5     |

From model1, the queries and the modeling are simple, basically because I have only one table that store all possible combinations extensively. However, I have the combinatorial explosion problem because each line represents a valid combination. Indeed, if I add more variables and values, then it grows exponentially according to the valid combinations.

From model2 the queries and the modeling are more complex. However I don't need to store all possible combinations extensively, I can group valid combinations together (e.g. key search id 1 that group values of attribute 2). Besides that, the queries can also be solved more efficiently, as I can calculate the intersection between the IDs found for each attribute given the user requirements.

My question is, there exists a better modeling approach that can have the advantages of both modelings (simplicity and performance)? Or even, a specific database (or search engine) technology that better support this kind of problem?

  • consider introducing not just a product id but a variant id. Could be universal (i.e., unique in the system) or alternatively could be a variant relative to a given product id. Use the unique key for a particular variant as primary key for a table which will have a row for each variant 's attributes - that is, for the primary key it will associate an attribute and its value. – davidbak Jul 8 at 18:38

Every DBMS will have a hard limit on the number of columns a table can have. This will be large but it is finite. If your attribute list is huge this may be a consideration against model 1.

If all attributes must be provided for every search and all comparisons are "equals" model 1 can be efficiently indexed with a single index on all the attribute columns. If the table allows nulls, or attributes are optional in a search, or comparisons can be other than "equals" model 1 struggles. This is a well-known problem for relational databases. Ideally we could define a separate index for each attribute column and the server would compute the intersection of them, but real systems are poor at this. There are work-arounds which involve a certain amount of trial and error to get right.

With model 2 each attribute is its own table so can be indexed separately and it is likely the optimizer will use these indexes. The problem of optional run-time parameters remains. Likely SQL will be generated at run-time incurring optimization overhead for every query submitted. Further, if N search parameters are provided you're doing and N+1-way join. Optimizers tend to do progressively worse as N increases.

Where the balance between these lies will depend on the actual data distribution and also the workload. Of the two I'd tend toward model 1. Let's say there are 100 attributes, they are all integers and there are 1000 rows. That's 400kB (roughly) storage. Even with no good index the DBMS will be able to scan the table in milliseconds.

Other than relational approaches you could concatenate the attributes' values and use a text-search approach e.g. Elasticsearch. Since the comparison is of a list of search attribute values against a list of product attribute values I wonder if one of the "scientific" array-based DBMS would perform well? A graph-based approach, where each product attribute was a node, would be OK but likely no better than the relational equivalent.

| improve this answer | |

You need to properly model your domain. You are modeling products. You need to model both products and product-variants where a product-variant is a particular product with specific attributes.

Both products and product-variants are entities (identified with a primary key). First consider how you'd represent that a particular product had certain variants, for all products. Then consider how you'd represent a particular product-variant, for all product-variants.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.