all ideas welcome... interesting db foreign keys question - hierarchy database stuff

[eluser]september28[/eluser]
Hi there,

So i have a table called "links" which basically has 5 columns: id, ex1, ex2, user, date.

now ex1 and ex2 actually relate to the id of a record in another table (called "explanations"). Therefore "links" is simply a linking table between 2 records in the explanations table.

Now, I will try my best to explain what i want to do....

The user can add a link by identifying the 2 records in the explanations table, therefore if 2 records have ids of 23 and 45 then the links table will basically look like this:
ex1 = 23, ex2 = 45, user = 3, date = 07/05/09

now, Basically what i want my controller to do is find all of the links that a particular explanation is involved in so e.g. a user browses to explanation id 23. on the page are displayed the links that this explanation has (in this case only 45 but could be more). So far everything is easy - just take the explanation id that the user called and select in the links table based on ex1 OR ex2 = 23.

Now, here is the tricky bit, I then want my controller to take the linked explanation id (in this case 45) and then search the table for any links with 45 (minus of course the original one with 23). If it finds any, I want the process to be repeated again and again until no more links are found. so eg 45 might be linked to 12 and also 67, so then the process should be repeated with these numbers (12 and 67) until no more links are found. The reason That i want to do this is so that linking can grow exponentially (my application is like a dictionary where users can link meanings of words thus creating synonyms) therefore i am presuming that if 23 links with 45, then 23 should also link with whatever else 45 links with and so on.

Visually this takes the form of a spider diagram (it is a lot easier to visualise than to explain).

In the end, the controller function should then return an array for the view of all the links (so in this case [45,12,67 etc...]

Does anyone have any ideas how this could possibly be achieved or indeed whether i am making any sense at all?

Thanks in advance,

Dan

[eluser]n0xie[/eluser]
Of the top of my head I would use a tail recursive function that walks all tree paths. The theorie is something like this:

1. Get 1st resultset.
2. Add resultset to 'resultarray'.
--- recursion ---
3. Loop over each result. For every result add them to the resultarray if they are not already present
4. Goto 3 untill no 'new' results are found.
--- /recursion ---
5. return 'the resultarray'.

It depends a bit on how big it is going to get. I could see a LOT of queries if you do it my way...

[eluser]september28[/eluser]
Thanks n0xie, im guessing the average explanation would have probably about 15 to 20 links however i can see you point about being quite database intensive.

Does anyone know if there is a more efficient way of doing what i want to do in terms of database design? I mean i just guessed that i should have 2 db fields forthe links, but maybe it is best to do it another way?>?


Cheers,

Dan

[eluser]Dam1an[/eluser]
n0xies solution is the easy one, but as he said, can be VERY inefficient
Essentially, your data is heirachical, so maybe this will help give you some ideas.
There's also some threads on the forum about hierachical data, see if you can apply some of that to your situation

I know it must be doable, as if you imagine it as a tree, an item is linked to every node under it

Sorry I can't give any specific idea's on how, but my brain seems a bit dead right now

[eluser]september28[/eluser]
Ok guys,

I have just come up with a possible alternative... all suggestions welcome as ever!

I could create a table called link_groups and another one called link_lists or something like that.

the explanations table would be modified:
id, explanation, link_group_id, added_by, created_date etc... - the important thing to note here is the addition of the link_group_id field. If the record is not part of a link group, then link_group_id is NULL.

Now link_groups table has essentially 2 fields:
id, created_date.

link_lists has these fields:
id, link_groups_id, explanation_id

so basically each time a link is created between 2 different explanations, this happens:
(to create a link, the user specifies the 2 explanations to be linked, thus creating the variables $first_explanation_id and $second_explanation_id

later i will post up a flow diagram of what i intend to do because typing it out seems to cause more confusion.

It would be interesting to know how online dictionaries deal with synonyms...

Cheers,
Dan

[eluser]Dam1an[/eluser]
[quote author="september28" date="1241735270"]It would be interesting to know how online dictionaries deal with synonyms...[/quote]

I would assume online dictionaries would only go down a few levels at a time, in which case you could do it with a single query and a few joins