[SQL] Stamboom

[TheNephilim]

Kwam net weer een query tegen waarvan ik dacht, dat moet anders kunnen...

Namelijk de onderstaande query waar ik de stamboom van een paard weergeef. Nu haal ik doormiddel van JOINS steeds de ouders op, maar dat moet toch ook makkelijker kunnen.

SQL:

SELECT
  `f1`.`horse_id` AS `f1_horse_id`,
  `f1`.`horse_name` AS `f1_horse_name`,
  `fpa1`.`horse_id` AS `f1_has_parents`,

  `m1`.`horse_id` AS `m1_horse_id`,
  `m1`.`horse_name` AS `m1_horse_name`,
  `mpa1`.`horse_id` AS `m1_has_parents`
FROM
  `horse_parents` AS `hp1`
LEFT JOIN
  `horse` AS `f1`
ON
  (`f1`.`horse_id`=`hp1`.`father_id`)
LEFT JOIN
  `horse_parents` AS `fpa1`
ON
  (`fpa1`.`horse_id`=`hp1`.`father_id`)
LEFT JOIN
  `horse` AS `m1`
ON
  (`m1`.`horse_id`=`hp1`.`mother_id`)
LEFT JOIN
  `horse_parents` AS `mpa1`
ON
  (`mpa1`.`horse_id`=`hp1`.`mother_id`)
WHERE
  `hp1`.`horse_id`=1

Als ik nu verder wil, krijg ik een eindeloze querie, voor enkele generatie moet ik nu hard gaan kijken of ze bestaan. Is er geen constructie waarmee dit makkelijker kan?

Overigens maak ik gebruik van MySQL 5.1.46 en PHP 5.3.2

[lier]

Dit zal je recursief moeten oplossen...

Bekijk bijvoorbeeld deze resultaten.

[ Voor 58% gewijzigd door lier op 10-06-2010 10:49 ]

[truegrit]

Jazeker, die is er! Ze heten nested sets, en zijn bij uitstek geschikt voor hierarchische data zoals een stamboom. Lees onderstaande pagina even door om het principe er achter te begrijpen.

http://dev.mysql.com/tech...es/hierarchical-data.html

[TheNephilim]

Ga ik even lezen jongens bedankt!

Nog 1 ding, nu sla ik vader en moeder op als: paard_id (PK), moeder_id, vader_id. Is het handiger om dit te doen paard_id (PK), ouder_id (PK)..?

Dus per parent 1 record ipv 1 record per child?

@truegrit: Heb het voorbeeld in je link even geprobeerd, maar deze is niet wat ik zoek:

SQL:

SELECT 
  node.horse_id
FROM 
  horse_parents AS node,
  horse_parents AS parent
WHERE 
  node.horse_id BETWEEN parent.father_id AND parent.mother_id
AND 
  parent.horse_id = 1
ORDER BY 
  node.father_id

Ik heb geen id die tussen links & rechts past. Behalve dat moet hij eigenlijk ook andersom. Dus van paard 1 naar zijn ouders, van elke ouder weer naar de ouders. Ga nog even verder zoeken op het recursieve, het moet mogelijk zijn

[ Voor 55% gewijzigd door TheNephilim op 10-06-2010 11:06 ]

[Janoz]

Wat even belangrijk is om te beseffen is dat de nested set oplossing en de recursieve oplossing twee verschillende oplossingen zijn.

De documentatie op de mysql site is leuk, alleen is het een beetje lomp dat ze aan de ID een dubbele betekenis gegeven hebben. Nu wordt de vorm van de boom beperkt door de volgorde van toekennen van het ID. Je kunt beter een extra veld opnemen. Dit veld gebruik je dan voor de positie in de boom.

ECHTER

Je hebt hier niet te maken met een boom structuur zoals dat in de algoritmiek gebruikelijk is. In de algoritmiek betekend een boom structuur dat elke node maximaal 1 parent heeft. Bij een stamboom zijn dat er toch echt twee. Veel standaard boom oplossingen zijn dan ook niet toepasbaar op een stamboom.

Ik zou de nested set oplossing dus volledig vergeten en je puur op de recursieve implementatie richten. Dat betekent inderdaad dat je een stuk meer queries op de database los moet laten.

[TheNephilim]

Klopt, die nested methode gaat sowieso niet werken omdat ik met 2 ipv 1 parent zit. Alleen kan ik recursive nog niks vinden wat werkt.

Maar het is dus recursive wel mogelijk om zonder elke generatie "hard" in je query te zetten toch alle generaties op te halen? Het is namelijk ook zo zonde om in PHP een while lusje te moeten gebruiken om alles op te halen.

Edit: Heb nu onderstaand, dit lijkt redelijke te werken, even verder uitwerken nog!

SQL:

SELECT 
  *
FROM
  `horse_parents` AS `c`
LEFT OUTER JOIN
  `horse_parents` AS `f`
ON
  (`f`.`horse_id`=`c`.`father_id`)
LEFT OUTER JOIN
  `horse_parents` AS `m`
ON
  (`m`.`horse_id`=`c`.`mother_id`)
WHERE
  `c`.`horse_id`=61

[ Voor 32% gewijzigd door TheNephilim op 10-06-2010 11:37 ]

[Janoz]

Dat while lusje is nu juist de recursieve oplossing.

[NMe]

Bernardo schreef op donderdag 10 juni 2010 @ 11:24:
Klopt, die nested methode gaat sowieso niet werken omdat ik met 2 ipv 1 parent zit. Alleen kan ik recursive nog niks vinden wat werkt.

Maar het is dus recursive wel mogelijk om zonder elke generatie "hard" in je query te zetten toch alle generaties op te halen? Het is namelijk ook zo zonde om in PHP een while lusje te moeten gebruiken om alles op te halen.

Zonde? Why? Gaat het echt duizenden lagen diep? Enkele tientallen queries kan je database echt wel hebben.

En om het verplichte linkje maar weer aan te halen:
Bomen in MySQL/PHP

[TheNephilim]

Oef, ik heb nog wat red bull nodig ofzo, zie door de bomen het bos niet meer. Maar het moet dus een PHP/MySQL oplossing worden

Ik ga je linkje even checken

[TheNephilim]

Ik kom er niet uit met je link. De voorbeelden gaan uit van 1 parent, en dat werkt niet. Het is eigenlijk heel simpel.

Het moet een array worden, met child als eerste dan 2 parents, die ook weer 2 parents hebben. Weet iemand hoe ik dit netjes in een array krijg? Ik kom er helemaal niet meer uit

[Janoz]

NMe schreef op donderdag 10 juni 2010 @ 11:37:
En om het verplichte linkje maar weer aan te halen:
Bomen in MySQL/PHP

Lees de draad voor je blaat!

Standaard boom linkjes zijn hier niet van toepassing aangezien dit topic niet over een zuivere boom datastructuur gaat.


----
@TS

Waarom wil je het perse in een array hebben? * Janoz snapt die arrayfetishismes van php-ers niet.

PHP:

class paard {
 var id;
 var naam;
 var vader;
 var moeder;
}

Klaar.

[ Voor 21% gewijzigd door Janoz op 10-06-2010 12:17 ]

[NMe]

Janoz schreef op donderdag 10 juni 2010 @ 12:13:
[...]

Lees de draad voor je blaat!

Standaard boom linkjes zijn hier niet van toepassing aangezien dit topic niet over een zuivere boom datastructuur gaat.

Dat maakt niet uit als je de stamboom van één enkel paard wil opvragen. Ik neem tenminste aan dat neven en nichten daar niet zo interessant bij zijn. Na die aanname is het een omgekeerde boom en dat kan wél met de standaardalgoritmiek.

@TS

Waarom wil je het perse in een array hebben? * Janoz snapt die arrayfetishismes van php-ers niet.

PHP:

class paard {
 var id;
 var naam;
 var vader;
 var moeder;
}

Klaar.

Gebruik je dan wel netjes public/private/protected in plaats van var?

[TheNephilim]

Ok, een array zou van mij niet hoeven. Een andere manier om het in onderstaande vorm te krijgen is ook goed.



Eerder had ik dus 1 query, waarin voor elke generatie een join zat om te kijken of het paard wel ouders had. Nu wil ik gewoon een recursieve functie, die het 1e paard ophaald, vervolgens kijkt of deze ouders heeft en dan daarvan de ouders ophaalt. Mijn idee was inderdaad een array, zo als onderstaand:

PHP:

array(
  'horse_id' = array (
    'horse_id' = 1,
    'father' = array(
      'horse_id' = 2
       'father' = array(
      'horse_id' = 2
    ),
    'mother' = array(
      'horse_id' = 3
    )
    ),
    'mother' = array(
      'horse_id' = 3
    )
  )
);

[NMe]

Dat is dus, zoals ik al zei, een omgekeerde boom. Daar kun je gewoon de standaardalgoritmes voor pakken die in dit topic aangehaald zijn, wanneer je uitgaat van het paard dat je opzoekt als root node.

[TheNephilim]

@NME Je bedoeld het Tree Traversal idee? Heb hier al mee zitten klooien, maar je blijft het probleem van 1 parent houden en ik heb er 2.

@Janoz Dus volgens jou kan ik beter gewoon een functie maken die paard gegevens ophaalt, en bij elke plek waar een ouder moet staan, checken of het kind een ouder heeft en dan pas ophalen?

[ Voor 39% gewijzigd door TheNephilim op 10-06-2010 12:49 ]

[NMe]

Bernardo schreef op donderdag 10 juni 2010 @ 12:44:
@NME Je bedoeld het Tree Traversal idee? Heb hier al mee zitten klooien, maar je blijft het probleem van 1 parent houden en ik heb er 2.

Nee, ik bedoel letterljik dat je vanaf de jongste generatie naar boven zou werken.

Je vraagt een paard op, en daar zoek je de ouders van. En daar zoek je de ouders van. En daarvan. Zo wordt je tree steeds breder vanaf één enkel punt waar één paard staat: het paard dat jij opzoekt. Je hebt dus niet het probleem dat er altijd twee takken samenkomen in één omdat je de boom "omgedraaid" hebt; er gaan dus altijd twee takken weg uit één paard.

Nadeel daarvan is dat je op die manier niet broers en zussen, neven en nichten, enz. op kan vragen, maar ik heb niet het idee dat je die nodig hebt; althans, zo breng je je probleem niet.

[TheNephilim]

Klopt, zo moet het ... uit 1 paard komen 2 ouders en daaruit ook weer. De vraag is, hoe krijg ik dat netjes uit de database. Het is me tot zover niet gelukt. Je moet namelijk steeds 2x verder en dat ook weer geordend op kunnen slaan.

[NMe]

Bernardo schreef op donderdag 10 juni 2010 @ 12:56:
Klopt, zo moet het ... uit 1 paard komen 2 ouders en daaruit ook weer. De vraag is, hoe krijg ik dat netjes uit de database. Het is me tot zover niet gelukt. Je moet namelijk steeds 2x verder en dat ook weer geordend op kunnen slaan.

Dat staat dus, nogmaals, letterlijk uitgelegd in de link die ik hierboven gaf en waarschijnlijk ook in de andere links die voorbij kwamen. Heb je die al eens goed doorgenomen?

[Janoz]

NMe schreef op donderdag 10 juni 2010 @ 12:20:
[...]

Dat maakt niet uit als je de stamboom van één enkel paard wil opvragen. Ik neem tenminste aan dat neven en nichten daar niet zo interessant bij zijn. Na die aanname is het een omgekeerde boom en dat kan wél met de standaardalgoritmiek.

Ja, dat kan misschien wel, maar dat geld pas zodra je 1 paard opvraagt. Je linkt naar een pagina waarop een standaard boom in de database opgeslagen wordt. Dat is hier niet het geval. Hier heb je een graaf in de database (de broertjes en zusjes staan er ook bij) en pas nadat het er uit gehaald is wordt het daadwerkelijk een boom.

[TheNephilim]

Zoals het in het artikel staat zou ik ipv horse_id (PK), father_id, mother_id naar horse_id (PK), parent_id (PK) moeten. Dan kan ik het verhaaltje met left & right gebruiken. Dat zou overigens wel zonde zijn, dan moet ik namelijk mijn DB structuur aanpassen. Praktisch voor de stamboom in dit geval, maar verder totaal niet.

[Janoz]

Je moet je door NME niet op het verkeerde been laten zetten. Aan je database moet je helemaal niks veranderen omdat een stamboom niet voldoet aan wat in de IT wordt gezien als een boom structuur. Waar je je vooral op moet richten is de structuur die je in je php maakt zodra je de stamboom van 1 paard uit de database haalt. Dat is inderdaad wel een boom structuur.

[NMe]

Janoz schreef op donderdag 10 juni 2010 @ 13:25:
[...]

Ja, dat kan misschien wel, maar dat geld pas zodra je 1 paard opvraagt. Je linkt naar een pagina waarop een standaard boom in de database opgeslagen wordt. Dat is hier niet het geval. Hier heb je een graaf in de database (de broertjes en zusjes staan er ook bij) en pas nadat het er uit gehaald is wordt het daadwerkelijk een boom.

Ik zeg natuurlijk nergens dat het tweede voorbeeld van die link gebruikt moet worden, het eerste is namelijk met een minieme aanpassing wel bruikbaar. Maar goed, ik heb het inderdaad wat onderschat.

[TheNephilim]

Allen bedankt voor de reacties en hulp! Ik ga het voorlopig gewoon even oplossen op de simpele manier, een functie en per generatie een check of daar nog ouders zijn.

Mocht ik een werkende oplossing gevonden hebben, post ik die natuurlijk

[Mischa_NL]

Hoeveel records betreft dit? Anders zou je misschien eens kunnen kijken naar een oplossing xml?
BV: boomstructuur in xml, met daarin ID's die verwijzen naar database-items.

[Janoz]

En op wat voor manier levert dat ook maar iets van een voordeel op tov de huidige oplossing?

[NMe]

Janoz schreef op vrijdag 11 juni 2010 @ 15:58:
En op wat voor manier levert dat ook maar iets van een voordeel op tov de huidige oplossing?

Mwah, je zou de node op kunnen zoeken die je nodig hebt en daar zo vaak als nodig is steeds parents van op blijven vragen. Vervolgens heb je alle ID's en hoef je maar één query te doen om alle voorouders op te vragen.

Maar goed, dat voordeel is zó marginaal dat het niet bepaald de keuze voor een uitbreiding via XML rechtvaardigt.

[Janoz]

* Janoz wijst nogmaals op een marginaal eigenschapje van de data van de topicstarter. Hoeveel parents heeft hij ook alweer?

Ben benieuwd welke exotische XML extensie meer dan 1 parent ondersteund

[Mischa_NL]

Janoz schreef op vrijdag 11 juni 2010 @ 18:18:
* Janoz wijst nogmaals op een marginaal eigenschapje van de data van de topicstarter. Hoeveel parents heeft hij ook alweer?

Ben benieuwd welke exotische XML extensie meer dan 1 parent ondersteund

You got me there. Niet bij nagedacht. Ook geen oplossing dus.

[NMe]

Janoz schreef op vrijdag 11 juni 2010 @ 18:18:
* Janoz wijst nogmaals op een marginaal eigenschapje van de data van de topicstarter. Hoeveel parents heeft hij ook alweer?

Ben benieuwd welke exotische XML extensie meer dan 1 parent ondersteund

Zelfde oplossing als wat ik eerder roep in een ander smaakje: omgekeerd modelleren en waarden dubbel opslaan. Non-oplossing, maar 't kan.

[Freee!!]

NMe schreef op vrijdag 11 juni 2010 @ 21:28:
[...]
Zelfde oplossing als wat ik eerder roep in een ander smaakje: omgekeerd modelleren en waarden dubbel opslaan. Non-oplossing, maar 't kan.

Werkt goed, totdat je erachter komt dat meerdere voorouders van je paard een voorouder delen. Standaard probleem bij stambomen is inteelt. Teveel daarvan is niet goed, maar het is soms heel handig om bepaalde gewenste eigenschappen te versterken.