2

I apologize for the vagueness of my question title, but I don't even know what to call what I'm trying to accomplish.

The best way to describe what I want is that I want to be able to chain a bunch of items together, and then (possibly) recursively find all the items that are part of any chains that contain the target item. For example, note item3 in the following chains: 

item1 => item2 => item3 => item4
item5 => item3 => item6  
item3 => item7 => item8  
item3 => item9 => item10  
item11 => item12 => item13 => item3

If a user were to do a search for item3, then I'd want all five chains above to be displayed. In other words, I want to be able to find all descendants and ancestors of item3, so that I can display the data in an HTML table (or whatever HTML structure works best).
The thing that makes this tricky is that (as shown above) any given item may have many descendants and many ancestors. As such, I'm not sure that regular recursion in MySQL would work.
I did have a look at both of the articles linked to in the top answer for the following SO thread, but I don't think that the suggested solutions will work for my desired data structure:
Mysql recursion?

Is there any way to structure this kind of data into a MySQL DB so that with fairly easy and lightweight queries (i.e., hopefully one query per item request), I can get the information and structure I'm looking for?
Thank you very much.

Community
  • 1
  • 1
HartleySan
  • 7,404
  • 14
  • 66
  • 119
  • What kind of structure do you have right now? – Starx Feb 24 '13 at 03:29
  • Can you tell what these items are and give some context? – arun Feb 24 '13 at 03:52
  • @Starx, I don't have any kind of structure, as I'm not sure what kind of structure is best. To be honest, what I want to achieve might not be practical with a DB. I was thinking about a structure similar to what's outlined in the articles linked to in the SO thread I linked to, but I'm thinking that those won't really work. – HartleySan Feb 24 '13 at 12:19
  • @arun, to be honest, I don't think the context really matters, but I wanted to make a DB of all the items in a particular game, and make it possible to easily look up how any given item is related to all connected items, as illustrated in my example above. – HartleySan Feb 24 '13 at 12:20

1 Answers1

0

I have a suggestion.

Store item in the following structure.

+---------+-----------+
|   id    |    item   |
+---------+-----------+
|   1     |   item3   |
+---------+-----------+

And add the link references in the following

+---------+-----------+------------+
|  itemid |  ancestor | descendant |
+---------+-----------+------------+
|  1      |  3        | 2          |
+---------+-----------+------------+
|  1      |  5        | 7          |
+---------+-----------+------------+

Create a index on all three columns. This will enable you to add same time as many times as it appears on a chain. Also you can query a particular item to find all its related links.

Starx
  • 77,474
  • 47
  • 185
  • 261
  • I thought about something along these lines as well, but if I were to do that, how would I be able to, for example, grab all the ancestors of the ancestors in one query if I don't know how many generations of ancestors there are? The same goes for the descendants. – HartleySan Feb 24 '13 at 12:23
  • I am no graph database expert, but if you are open, you can explore something like Neo4J or OrientDB. – arun Feb 24 '13 at 16:56