Reducing redundancy in data for storage in MySQL

I have a feeling this has already been answered, but I don't kn开发者_Go百科ow the correct terminology involved and couldn't find anything in my search.

I'm working on a product recommendation system. And I've got a database of items, and I'm running through and determining which items are similar. For example ItemID 1 is similar to 5, 7, and 8. The issue is the data being redundant. As I loop through the whole item set i'll wind up with something like this:

1 5,7,8

5 7,8,1

7 8,5,1

8 5,1,7

What is the best way to store this in MySQL, so I can query it and find the items related to either 1, 5, 7, or 8. In real life, there will be an uneven number of items in each set. I'm concerned with speed more than storage space, but it seems like there should probably be a happy medium, or if I'm lucky one that is fast, and saves space.

This is called a "graph data structure". The numbers (1,5,7,8) are the nodes. Each connection (1-5,1-7,1-8,5-7,etc.) are the edges.

http://en.wikipedia.org/wiki/Graph_(data_structure)

In MySQL, you should store the edges as one edge per row. If each edge connects in both directions, you should add each edge going in both directions (i.e. 1-5 and 5-1). I would setup the table something like this:

TABLE edges (
  id PRIMARY KEY AUTO_INC,
  from INT,
  to INT
)

You will want an index on (from), or possibly (from, to) depending. To find all objects related to the one you're looking at:

SELECT to FROM edges WHERE from = X;

A great many improvements could be made to this simple model, but it's a start.

Edit: Maybe some of those column names are key words. My bad.

Rather than one column for the item and another column for a list of what's similar, which results in each item having one row in the table, consider storing each (source, destination) pair in a separate row.

Instead of (1, {5,7,8}), (5, {7,8,1}) you would have (1, 5), (1, 7), (1, 8), (5, 7), (5, 8), (5, 1). Then to see which items are similar to item 8, you'd just select source where destination=8.

Chris is right and wrong at the same time. He's right in that it is a "graph data structure" but fails to mention that his approach would have you end up in several subqueries to find a graph.

Please do yourself a favor and have a look at the Nested Set model. You might want to head over to the MySQL manual to get you started.

Regards