[PHP + SQL] Hulp nodig met left right sql tree

[jozuf]

Hoi allemaal,

Ik zit een beetje vast met het maken van een left/right sql tree icm PHP en MySQL.
De database structuur (gesimplificeert hiervoor);

id | title | lft | rgt

De query om de boom op te halen in de juiste volgorde heb ik al werkend adhv een artikel van MySQL.
Nu moet ik alleen het nog voorelkaar krijgen in PHP om de tree om te zetten naar een multidimensionale array die een boom voorstelt.
Ik heb al lopen zoeken en zelf lopen proberen, mijn zoektocht vond ik wel wat oplossingen maar die zijn nogal intensief met queries (elk niveau 1 query) terwijl ik vermoed (redelijk zeker van ben, ooit wel is ergens werkend gezien tijden geleden) dat dit recursief opgelost kan worden met 1 enkele query waarbij gelijk alle nodes worden opgehaald in de juiste volgorde.
Ik kom er alleen niet uit en vroeg me af of jullie mij een klein beetje op gang kunnen helpen.

Ik wil gerust code plaatsen maar aangezien ik nog niet veel werkends heb in PHP (enkel de juiste opbouw voor de sql die de juiste resultset produceert) lijkt me dat weinig toevoegen.
Een abstracte aanpak voor dit probleem vind ik voldoende maar dit vind ik nog nergens.

Alvast bedankt!

[ Voor 3% gewijzigd door jozuf op 09-01-2010 16:26 ]

[kokx]

Wat jij wilt bereiken is dus het gebruiken van een NestedSet. Ik ben bekend met dit principe ja .

Het ophalen van data uit zo'n data tree is erg gemakkelijk. Een groot probleem is echter dat het erg intensief is om een element ergens in de tree toe te voegen. Aangezien je dan meteen de gehele tree moet updaten.

In dat artikel staat er een mooi voorbeeld van stored procedures. Ik raad je aan om daar eens goed naar te kijken, omdat dat hier goed van pas komt.

Ook is dit behoorlijk gevorderde logica, als je hier veel problemen mee hebt, raad ik je aan om gewoon een parent_id toe te voegen aan de velden. Hiermee kun je toch gewoon hetzelfde bereiken.

[cariolive23]

Hiermee kun je toch gewoon hetzelfde bereiken.

Dat levert weer andere beperkingen en uitdagingen op. Gewoon even doorbijten op de nested set en je hebt het probleem opgelost. Het artikel noemt de oplossingen reeds.

Recursieve queries zijn niet mogelijk in MySQL, dit moet je met een stored procedure nabootsen.

[jozuf]

Ik heb nu wat staan met een parentid constructie, werkt idd wel maar heb ik idd wat andere limitaties of tenminste zaken die wat complexer worden zoals het schuiven van nodes, verwijderen enzo.
Dus ik dacht laat ik deze constructie is een kans geven.

Met recursie doelde ik niet op SQL maar een php functie.
Ik heb de resultset dus al in de juiste volgorde en ziet er goed uit maar nu moet ik nog een php functie creeeren die die set omzet naar een multi dimensionale array die de boom voorsteld.
In het MySQL artikel worden wel oplossingen geboden maar dit sluit niet geheel aan bij wat ik zoek (ze doen zaken als indenting om het level weer te geven direct met sql, dat heb ik niet nodig).
Nested set idd, beter woord om zo nog wat meer op te gaan googlen Als iemand nog aanvullende info heeft graag! Pseudo code voor de aanpak zou ik ook erg kunnen waarderen

Bedankt iig alvast!

[ Voor 12% gewijzigd door jozuf op 09-01-2010 16:58 ]

[FireDrunk]

Waarom wil je perse de boomstructuur ook in MySQL? Je gaat er toch pas in PHP mee werken?
Kun je niet eerst de data uit MySQL halen en daarna in een tree stoppen? Dan zorg je er voor dat de tree gecached blijft, en niet elke pageview opgehaalt word (tenzij dat expliciet nodig is).

Je ontziet je MySQL server, en de ingewikkeldheid van je queries daalt ook nog eens... In PHP is een HashTree of een NestedTree prima te maken (het is immers C code...)

[jozuf]

@thijs_cramer:

wat vloog daar over mijn hoofd ?
Ik geloof niet dat ik ga beginnen met c code hiervoor
En ja je hebt gelijk wat betreft de performance hit maar dat kan ook wel op een andere manier gecached worden, denk ik zo zelf. Als dat al nodig zou zijn.
Performance is niet zo'n punt hier.

[ Voor 12% gewijzigd door jozuf op 09-01-2010 17:04 ]

[NMe]

Bomen in MySQL/PHP

Ik denk dat je er daar wel mee uit komt. Dit artikel heeft mij in elk geval een tijd geleden de ogen geopend.

[jozuf]

@NMe:

die had ik ook zelf al doorgenomen maar doet het niet zo als ik verwacht.
Dat is degene die een query doet voor elk niveau.

Toch bedankt maar volgens mij moet het beter kunnen
Een query voor elk niveau is een beetje te gek, dan ga ik wel terug naar parent_id waarbij ik dat niet nodig had.
Volgens mij moet ik het ff laten liggen, geen haast Ms dat ik dan iets kan bedenken.

En voor iedereen die zicht afvraagt waarom? Gewoon omdat ik dit wil kunnen, beetje bijleren en omdat het in mijn ogen de beste aanpak is voor het probleem. Waarbij performance niet een erg grote rol speelt (maar het moet ook weer niet te gek worden, het is wel gewoon een request geen cronjob ofzo) maar zaken als flexibiliteit wel. Met de parentId constructie zit je al snel vast, zeker al gaat het om diepere/complexere bomen waarmee je ook CRUD wilt doen (Create,read,update,delete)

[ Voor 61% gewijzigd door jozuf op 09-01-2010 17:14 ]

[NMe]

Waarom geef je enerzijds aan dat performance geen issue is, maar wil je anderzijds wél alles in één query ophalen? En ook: waarom zou je de boom desnoods niet kunnen bouwen in PHP na het ophalen van alle records? Waarom moet dat in je database?

[jozuf]

Voor de duidelijkheid ik wil het niet in de database opbouwen.

Ik wil het in PHP opbouwen, het lukt me alleen nog niet. Hoe je het in de database op moet bouwen staat in het mysql artikel uitgelegd.

Ik zeg enerzijds performance is geen issue want het draait op mijn homeserver die wel wat kan hebben, geen shared host ofzo. Anderzijds blijft het toch een request en ik wil niet eerst 10 seconde wachten totdat alle queries gevuurd zijn om het menu op te bouwen + de tijd die nodig is om de request op te halen.
Een ander argument voor mij is dat ik flexibiliteit wil in het beheren van de boom wat in deze constructie gemakkelijker zou moeten gaan dan in een parent id boom.

En als laatste wil ik gewoon altijd trots zijn op mijn werk en het best mogelijke neerzetten. En misschien een beetje bijleren.
Het gaat om het menu van mijn serverconsole. Deze moet beheerd kunnen worden, verschoven etc .
Het meeste van die logica staat al gebouwd op parentId maar het is niet alles om daar mee te werken.
Alhoewel b.v. een item invoegen in een left/right boom een grotere hit is dan bij parentId is het wel gemakkelijker te creeëren in SQL.
De boom zal het meest uitgelezen worden, de performance van toevoegen/verplaatsen etc. van nodes is van ondergeschikt belang.

En ook nog het feit dat het aan me knaagt dat dit moet kunnen worden opgelost met recursie in php (en 1 query) maar dat ik er frustrerend genoeg op het moment niet erg uitkom.

[ Voor 36% gewijzigd door jozuf op 09-01-2010 17:31 ]

[UltimateB]

Hmm, heb even geen code bij de hand maar geloof dat wij gebruik maken van een subquery die the dept ophaalt. Combineer dat met een ORDER BY rgt (of was het left :x) en je hebt de tree in volgorde met dept. Dan is het niet zo heel lastig meer om dit in PHP de gebruiken. Het ophalen van een pad naar de root node is volgens mij ook genoemt in het artikel dat NMe noemde.

[Raynman]

Ik vond het al knap dat iedereen zo goed begreep wat je wilde, want ik vond de probleemstelling niet zo duidelijk. Kun je anders nog een simpel voorbeeld geven van wat je precies wilt doen?

@UltimateB: die query staat in het artikel (link uit TS) en waarschijnlijk bedoelt jozuf dat met "De query om de boom op te halen in de juiste volgorde heb ik al werkend", maar dat hoor ik graag nog even van hem. (Lijkt me dan inderdaad niet zo moeilijk meer.)

[ Voor 41% gewijzigd door Raynman op 09-01-2010 17:36 ]

[jozuf]

ja klopt met "De query om de boom op te halen in de juiste volgorde heb ik al werkend"
bedoelde ik dat ik de resultset al in de juiste volgorde aangeleverd krijg in PHP. dus nummer 1 is root
nummer 2 is het eerste menu item waarna vervolgens de subitems komen van nummer 2 dan komt nummer 3 met zijn subitems en de subitems van de subitems etc.

Kennelijk is het dan niet meer zo moeilijk maar ik kom er maar niet echt op.
Sorry voor de onduidelijkheid, ik wist niet zo goed hoe ik het allemaal goed moest uitleggen, wat denk ik komt doordat ik het zelf ook nog maar net een beetje begin te begrijpen.

Dus als het dan niet zo moeilijk meer is kan iemand zich wagen aan een stukje psuedo met recursie (of niet maar iig wel) gebaseerd op 1 query (zie hieronder evt.) er vanuit gaande dat die resultset in de juiste volgorde word aangeleverd?

voor geintereseerde evt hier nog de query die ik hiervoor wil gaan gebruiken. Hij heeft nog een beetje legacy aanboord voor de voorgaande parentid constructie nu in gebruik.

code:

   SELECT menu_items.id,     
          menu_items.name,
          menu_items.url,
          menu_items.target_blank,
          menu.parent_id,
          menu.position,
          menu.lft,
          menu.rgt,
          icons.name AS icon
     FROM (SELECT node.id, node.parent_id,
                  node.position,
                  node.menu_items_id,
                  node.icons_id,
                  node.users_id,
                  node.display,
                  node.lft,
                  node.rgt
             FROM menu as node,
                  menu as parent
            WHERE node.lft BETWEEN parent.id AND parent.rgt
              AND parent.id = 1
         ORDER BY node.lft) AS menu
LEFT JOIN menu_items
       ON menu_items.id = menu.menu_items_id
LEFT JOIN icons
       ON icons.id = menu.icons_id
    WHERE users_id = " . $_SESSION['id'] . "
      AND (display = '" . ($mobileBrowser ? 'mobile' : 'normal') . "' OR display = 'both')

---EDIT----

op basis van bovenstaande query wil ik dus een multi dimensionale array opbouwen in php met een structuur als;
$menu[rootitem]
$menu[rootitem][menuitem]
$menu[rootitem][menuitem][subitem]
en evt dit in herhaling voor diepere takken dus;
$menu[rootitem][menuitem][subitem][subitem] etc,.

rootitem mag weggelaten worden in de php array aangezien het menu niet zozeer een rootitem heeft maar wel nodig is binnen de tabel om de sql logica juist te laten werken.

[ Voor 93% gewijzigd door jozuf op 09-01-2010 18:02 ]

[Soultaker]

Dat is niet echt een multidimensionale array in de traditionele betekenis van het woord. Maar je wil dus een boomstructuur creëren in PHP. Daar heb je die left en right indices helemaal niet voor nodig (al zou je 't er mee kunnen doen als je geen id en parent_id had). Je kunt simpelweg met een platte array van nodes beginnen, en dan elke node onder de juiste parent hangen.

Voorbeeldje:

PHP:

$nodes = array(
    1 => array(parent_id => NULL, name => 'Root' ),
    2 => array(parent_id =>    1, name => 'Item1' ),
    3 => array(parent_id =>    1, name => 'Item2' ),
    4 => array(parent_id =>    2, name => 'SubItem 1.1' ),
    5 => array(parent_id =>    2, name => 'SubItem 1.2' ),
    6 => array(parent_id =>    3, name => 'SubItem 2.1' ),
    7 => array(parent_id =>    3, name => 'SubItem 2.1' ) );

$root = 1;
foreach ($nodes as $id => & $node)
{
    $node[children] = array();
    if ($id != $root) $nodes[$node[parent_id]][children][] = & $nodes[$id];
}

$tree = $nodes[$root];

De boom recursief doorlopen kan dan bijvoorbeeld zo:

PHP:

function print_tree(& $node, $depth = 0)
{
    echo str_repeat(' ', 4*$depth), $node[name], "\n";
    foreach($node[children] as & $node) print_tree($node, $depth + 1);      
}
print_tree($tree);

Uitvoer:

Root
    Item1
        SubItem 1.1
        SubItem 1.2
    Item2
        SubItem 2.1
        SubItem 2.1

[jozuf]

Soultaker's oplossing sloot niet aan bij hoe de resultset is opgebouwd, uiteindelijk zelf uitgevogeld;

PHP:

        $menu = $this->getSubTree(fetchAll($query));
        return $menu[0]['children'];
    }
    
    private function getSubTree(&$nodes, $prevNodeRgt = false){
        while($node = current($nodes)){ 
            if((!$prevNodeRgt ? $node['rgt'] : $prevNodeRgt) < $node['rgt']) return $tree;

            next($nodes);

            //Has children?   
            if($node['rgt'] - $node['lft'] > 1) $node['children'] = $this->getSubTree($nodes, $node['rgt']);    

            $tree[] = $node;        
        }
        return $tree; 
    }

wat mij betreft kan deze dicht.

[ Voor 21% gewijzigd door jozuf op 13-01-2010 19:57 ]