[mySQL] connectie query

[Verwijderd]

op hyves heb je zo'n leuk iets waarbij je kan zien via wie je een connectie hebt tot iemand, voorbeeld:

Profiel
Naam: Lisette
Leeftijd: 20
Connectie:
• Ludo > Suzanne > Jolijt > Lisette
• Ludo > Toon > Peter > Lisette
• Ludo > Anouk > Manuel > Lisette

ik heb allerlei dingen al geprobeerd, maar ik snap niet hoe ze dat doen, waarschijnlijk kan dit gewoon in 1 query, maar dat krijg ik niet voor elkaar.
M'n mySQL skillz beperken zich blijkbaar toch tot een minimum...

Ik heb gewoon een simpele table gemaakt:

persoon1	persoon2
1	2
1	3
1	5
2	6
2	7
5	9
6	8
6	9

Als persoon 1 dus op het profiel van persoon 9 zou zijn, dan zou er moeten staan:

Jouw connectie met 9 =
1 -> 2 -> 6 -> 9
en
1 -> 5 -> 9

weet iemand hoe ik zo'n query in elkaar moet zetten? moet ik gebruik maken van INNER JOINS, OUTER JOINS, LEFT JOINS enz enz...

[pistole]

Dit kan niet (naar mijn weten) zonder recursief te werk te gaan (en dus niet te doen in 1 query).

[Thralas]

Het lijkt ergens op het Dijkstra algoritme, alleen in dit geval gaat het niet om de kortste afstand, maar om een zo klein mogelijk aantal nodes? Niet echt iets wat me gemakkelijk te berekenen lijkt als je uitgaat van een database zoals Hyves

[Wolfboy]

@pistole, recursie is niet perse vereist hier, een iteratieve werking zou ook prima zijn (zoekwoorden: queue/stack)

Maar voor zover ik weet kan je dit idd niet met 1 mysql query oplossen.

[Verwijderd]

zouden ze die vrienden/relaties dan op een andere (uitgebreidere) manier opslaan in de db?

[Hydra]

Ik denk dat die mogelijkheid een van de grootste redenen is dat die site bij drukte zo retetraag is

Verwijderd schreef op dinsdag 27 december 2005 @ 14:00:
zouden ze die vrienden/relaties dan op een andere (uitgebreidere) manier opslaan in de db?

Nou, je kunt in princiepe voor iedereen alle 1e en 2e graads vrienden op kunnen slaan, maar dat betekent dat als je iemand toevoegt aan je lijst, alle mensen die jou als 1e graads vriend hebben ook geupdate moeten worden. En dat lijkt me niet erg performant Ik vermoed dat ze het gewoon via een serie selects doen iedere keer, verklaart wel waarom de site traag is.

[ Voor 74% gewijzigd door Hydra op 27-12-2005 14:05 ]

[Wolfboy]

Je zou het gewoon in een aparte tabel kunnen opslaan om de load wat lager te houden (dus bij elke update aan de vrienden/relaties tabel die tabel ook updaten.

Mja, of dat nou een goede oplossing is...

[Verwijderd]

ja het schijnt wel zo te zijn dat hyves een flink leger aan servers heeft staan (nog meer dan tweakers zelfs )

eerst vroeg ik me dus af waarom ze zoveel servers nodig hadden, maar nu snap ik het

maargoed, blijft een lastig probleem dus...

[Verwijderd]

Als je de restrictie toevoegt dat je tot op een bepaalde diepte (zeg x) zoekt, is de vraag niet meer zo moeilijk. Je joint de tabellen x keer met elkaar zodat je een boom krijgt van diepte x. Het enige waar je dan nog op moet checken is of de persoon die je zoekt in de boom voorkomt.

Aangenomen dat je 2 tabellen hebt:
Persoon (PID, Naam, enz) en IsVriendje(PID1, PID2) wordt de query zoiets:
SELECT *
FROM PERSOON
LEFT JOIN IsVriendje as vriendje1 ON persoon.pid = vriendje1.pid1
LEFT JOIN IsVriendje as vriendje2 ON vriendje1.pid2 = vriendje2.pid1
...
...
WHERE persoon.pid=<persoon_id> AND (vriendje1.pid2=<persoon2_id> OR vriendje2.pid2 =<persoon2_id OR ... OR ...)

[Verwijderd]

Verwijderd schreef op dinsdag 27 december 2005 @ 14:35:
Als je de restrictie toevoegt dat je tot op een bepaalde diepte (zeg x) zoekt, is de vraag niet meer zo moeilijk. Je joint de tabellen x keer met elkaar zodat je een boom krijgt van diepte x. Het enige waar je dan nog op moet checken is of de persoon die je zoekt in de boom voorkomt.

Aangenomen dat je 2 tabellen hebt:
Persoon (PID, Naam, enz) en IsVriendje(PID1, PID2) wordt de query zoiets:
SELECT *
FROM PERSOON
LEFT JOIN IsVriendje as vriendje1 ON persoon.pid = vriendje1.pid1
LEFT JOIN IsVriendje as vriendje2 ON vriendje1.pid2 = vriendje2.pid1
...
...
WHERE persoon.pid=<persoon_id> AND (vriendje1.pid2=<persoon2_id> OR vriendje2.pid2 =<persoon2_id OR ... OR ...)

ja het is inderdaad maar tot een bepaalde diepte, (derdegraads vrienden ofzo)

ik ga ff aan de slag hiermee, thnx.

[Woy]

Ik denk dat je het zowiezo beter niet in een SQL query kunt doen. Het probleem is zowiezo een graven probleem.
Je zou eens moeten dus moeten zoeken naar algoritmes die dit probleem oplossen voor een willekeurige graaf. Dan moet je kijken of dat algoritme nog enigsinds bruikbaar is door middel van queries. Als het met queries niet rendabel is kun je mischien de complete ( of een slim gekozen sub-set ) graaf in je geheugen opbouwen en dan zo'n algoritme er op los laten.

Maar zoals al gezegd. Als je een database met veel personen erin hebt zal het waarshijnlijk niet eenvoudig zijn om dit performant voor elkaar te krijgen.

[edit]
ok als het maar tot derdegraads diepte is dan is het probleem al een stuk eenvoudiger. Maar nog steeds denk ik dat het een vrij lastig probleem is als je een grote dataset hebt. Ik kan me herinneren dat ik ooit gelezen had dat als je 6 of 7 stappen diep ging dat je dan zo'n beetje een link had naar de complete wereld. Weet trouwens niet meer waar ik dat gelezen heb.

[ Voor 25% gewijzigd door Woy op 27-12-2005 15:39 ]

[Verwijderd]

Zolang de diepte (zie mijn vorige post) niet te groot wordt (zeg 3 of 4), dan valt de performance nog wel mee. Jouw oplossing (subgraaf in geheugen laden) stuit op problemen. Je kan niet zomaar een geschikte deelgraaf vinden waar je een zoekalgoritme op los kan laten. Je zou er nog wel voor kunnen kiezen om eerst de gehele table in het geheugen te laden en daar dan een zoekalgoritme op los te laten. Je zou dan breadth-first kunnen zoeken naar een pad tussen je 2 nodes en doet dan in wezen hetzelfde als de MySQL-oplossing. Waarom zou je dat dan in PHP sneller doen als in MySQL? Lijkt me onzinnig...

edit:
Whoops, ik zie je edit nu pas. In geval van een diepte van 6 of 7 zou je weleens gelijk kunnen hebben. Interessant om zoiets eens te benchmarken in een reallife-omgeving.

[ Voor 14% gewijzigd door Verwijderd op 27-12-2005 15:44 ]

[Woy]

Als je een beperkte diepte hebt kun je nog redelijk met joins uit de voeten. Maar als je ook dieper wilt gaan gaan je dataset natuurlijk exponentieel groeien. Dan is het efficienter om het gewoon in graaf te doen aangezien je dan elke node maar een keer in je geheugen laadt.

Verder is het denk haast onmogenlijk om voor diepere relaties alle mogenlijkheden op te zoeken. Er zijn dan bijna oneindig veel routes die je kan doen. Ik bedoel als je van rotterdam naar amsterdam wilt kun je ook via alle andere plaatsen in nederland rijden

[Hydra]

Verwijderd schreef op dinsdag 27 december 2005 @ 15:42:
Zolang de diepte (zie mijn vorige post) niet te groot wordt (zeg 3 of 4), dan valt de performance nog wel mee. Jouw oplossing (subgraaf in geheugen laden) stuit op problemen. Je kan niet zomaar een geschikte deelgraaf vinden waar je een zoekalgoritme op los kan laten. Je zou er nog wel voor kunnen kiezen om eerst de gehele table in het geheugen te laden en daar dan een zoekalgoritme op los te laten. Je zou dan breadth-first kunnen zoeken naar een pad tussen je 2 nodes en doet dan in wezen hetzelfde als de MySQL-oplossing. Waarom zou je dat dan in PHP sneller doen als in MySQL? Lijkt me onzinnig...

Hyves werkt alleen met vrienden en vrienden van vrienden, niet dieper dan dat. Je kunt dan voor elke pagina die je bezoekt kunnen kijken of zijn vrienden en vrienden-van-vrienden in jouw lijst voorkomen. Je wilt in dit geval echt de RDBMs niet te zwaar belasten, de applicatie hoeft alleen maar de intersectie van de twee lijsten te berekenen. Basically is het een intersection van 2 SELECT-in-SELECT queries.

rwb schreef op dinsdag 27 december 2005 @ 15:53:
Als je een beperkte diepte hebt kun je nog redelijk met joins uit de voeten. Maar als je ook dieper wilt gaan gaan je dataset natuurlijk exponentieel groeien. Dan is het efficienter om het gewoon in graaf te doen aangezien je dan elke node maar een keer in je geheugen laadt.

Het zou me niks verbazen als ze overgaan van een pure MySQL oplossing (als dat nu nog het geval is) naar een hybride oplossing waarbij een eigengemaakte graph-engine die paden oplevert.

Verder is het denk haast onmogenlijk om voor diepere relaties alle mogenlijkheden op te zoeken. Er zijn dan bijna oneindig veel routes die je kan doen. Ik bedoel als je van rotterdam naar amsterdam wilt kun je ook via alle andere plaatsen in nederland rijden

Volgens mij is iedereen slechts 6 stappen van ieder ander verwijderd ofzo

[ Voor 30% gewijzigd door Hydra op 27-12-2005 16:30 ]

[Woy]

Hydra schreef op dinsdag 27 december 2005 @ 16:25:
[...]
Het zou me niks verbazen als ze overgaan van een pure MySQL oplossing (als dat nu nog het geval is) naar een hybride oplossing waarbij een eigengemaakte graph-engine die paden oplevert.

Dat is idd waar ik ook op aan stuurde.

Volgens mij is iedereen slechts 6 stappen van ieder ander verwijderd ofzo

Ja idd zoals ik ergens hierboven ook al zei dacht ik ook dat iedereen binnen 6 of 7 stappen met elkaar verbonden is op de wereld. Maar je kan natuurlijk via verschillende paden ergens komen. Daarom zei ik ook dat alle mogenlijke paden nogal lastig is. Als je het beperkt tot 6 stappen valt het nog wel te overzien opzich aangezien je een pad na 6 stappen al af kan schrijven en ik er vanuit ga dat je niet alle mensen/relaties van de wereld in je database hebt zitten.

[Hydra]

rwb schreef op dinsdag 27 december 2005 @ 18:00:
Ja idd zoals ik ergens hierboven ook al zei dacht ik ook dat iedereen binnen 6 of 7 stappen met elkaar verbonden is op de wereld. Maar je kan natuurlijk via verschillende paden ergens komen. Daarom zei ik ook dat alle mogenlijke paden nogal lastig is. Als je het beperkt tot 6 stappen valt het nog wel te overzien opzich aangezien je een pad na 6 stappen al af kan schrijven en ik er vanuit ga dat je niet alle mensen/relaties van de wereld in je database hebt zitten.

Ik denk dat dat al snel niet meer gaat werken kwa performance. Juist als je geografisch gezien een kleine groep hebt zullen alle mensen mekaar 'kennen' binnen 6 stappen. Dit betekent dat je voor elke persoon de volledige lijst terug gaat krijgen. Daarnaast ga je voor elke persoon die je tegenkomt breadth-first alle paden uitrekenen.In een MySQL database wil je dat helemaal niet

[Bosmonster]

rwb schreef op dinsdag 27 december 2005 @ 15:36:
Ik kan me herinneren dat ik ooit gelezen had dat als je 6 of 7 stappen diep ging dat je dan zo'n beetje een link had naar de complete wereld. Weet trouwens niet meer waar ik dat gelezen heb.

Ik kan me ook herinneren gelezen te hebben dat die _theorie_ in de praktijk bullshit is

[ Voor 3% gewijzigd door Bosmonster op 28-12-2005 12:42 ]

[arieleks]

Bosmonster schreef op woensdag 28 december 2005 @ 12:42:
[...]

Ik kan me ook herinneren gelezen te hebben dat die _theorie_ in de praktijk bullshit is

Offtopic: 't Is toch ook gewoon om te laten zien hoe kleine dingen heel snel heel groot kunnen worden?

[Woy]

Bosmonster schreef op woensdag 28 december 2005 @ 12:42:
[...]

Ik kan me ook herinneren gelezen te hebben dat die _theorie_ in de praktijk bullshit is

hehe, ja dat zal vast wel ja. Maar toch denk ik dat het in de westerse wereld aardig snel opschiet. In afrika in afgelegen dorpen enzo zal het idd niet zo snel gaan.