[PHP/mySQL] Hierarchische structuur (array)

[radem205]

Beste tweakers,

Momenteel sta ik voor een lastige opgave (althans, voor mij). Namelijk;

Ik heb een tweetal tabellen (zie onderstaand voorbeeld):

Tabel: Levels

level_id	level_parent_id	level_name
0	null	Hoofdcategorie
1	0	Subcategorie 1
2	0	Subcategorie 2
3	2	Subcategorie 2 - 1
4	2	Subcategorie 2 - 2

Tabel: Items

item_id	item_name	level_id
1	Naam 1	0
2	Naam 2	3
3	Naam 3	4
4	Naam 4	1

Deze twee tabellen hebben, zoals je kan zien een relatie door middel van het 'level_id'.

Nu probeer ik in PHP hier een hierarchische (tree) structuur uit te krijgen, met als voorbeeld:

PHP:

<?php
array(
    0 => array(
        'level_name' => 'Hoofdcategorie',
        'items' => array(), // GEEN DIRECTE ONDERDERLIGGENDE ITEMS
        'children' => array(
                
            0 => array(
                'level_name' => 'Subcategorie 1',
                'items' => array(
                    0 => array(
                        'item_id' => 4,
                        'item_name' => 'Naam 4'
                    )
                )
            ),
            1 => array(
                'level_name' => 'Subcategorie 2',
                'items' => array(), // GEEN DIRECTE ONDERDERLIGGENDE ITEMS
                'children' => array(
                    0 => array(
                        'level_name' => 'Subcategorie 2 - 1',
                        'items' => array(
                            0 => array(
                                'item_id' => 2,
                                'item_name' => 'Naam 2'
                            )
                        )
                    ),
                    1 => array(
                        'level_name' => 'Subcategorie 2 - 2',
                        'items' => array(
                            0 => array(
                                'item_id' => 3,
                                'item_name' => 'Naam 3'
                            )
                        )
                    )
                )
            )
        )
    )
);
?>

De bovenstaande structuur heb ik handmatig opgezet, maar ik wil dit uiteraard automatisch laten verlopen op basis van de gegevens uit de database.

Het moeilijke voor mij zit 'm in het geval dat de tabel 'items' bepaald wat getoond moet worden. M.a.w.; op basis van een filter / zoekfunctie op de website wordt gezocht in de tabel 'items' en zullen de bijbehorende niveaus opgenomen moeten worden. Dus niet alleen het directe niveau waar het betreffende item ondervalt, maar ook de daarbovenliggende niveaus.

Ik heb het geprobeerd op te lossen met twee aparte sql queries, waarbij de eerste alle 'levels' ophaalt en de tweede alle items. Een tweede mogelijkheid is het maken van een recursieve functie, waarbij de 'tree' wordt opgebouwd (zie onderstaande functie). Dit werkt niet goed wanneer ik wil zoeken op specifieke items, waarbij ook alle bovenliggende niveaus zichtbaar moeten zijn.

code:

<?php
function buildTree(array &$elements, $parentId = 0) {
    $branch = array();

    foreach ($elements as $element) {
        if ($element['level_parent_id'] == $parentId) {
            
            $children = buildTree($elements, $element['level_id']);
            if ($children) {
                $element['children'] = $children;
            }
            $branch[$element['level_id']] = $element;
            unset($elements[$element['level_id']]);
        }
    }
    return $branch;
}
?>

Ik ben mij ervan bewust dat het allemaal wat vaag omschreven is, maar kunnen jullie mij in de goede richting helpen? Kant-en-klare code is niet nodig, maar ik loop momenteel vast en kom niet echt verder.

Alvast bedankt.

[Cartman!]

Ik denk dat je hier wellicht wat aan hebt: Crisp's blog: Formatting a multi-level menu using only one query

[4Real]

http://mikehillyer.com/ar...erarchical-data-in-mysql/

[radem205]

Bedankt voor de info.

De uitdaging zit 'm met name in het geval wanneer gezocht wordt op bijvoorbeeld item_name = 'naam 3' en alle bovenliggende niveau's zichtbaar moeten worden gemaakt (dus in dit geval 'Hoofdcategorie' -> 'Subcategorie 2' -> 'Subcategorie 2 - 2' ). Het resultaat van een zoekopdracht kunnen meerdere items bevatten (> 100).

@Cartman: Dit komt redelijk overeen met het voorbeeld wat ik mijn startpost aanhaalde. Het probleem hierbij is dat ik bovenstaande hier niet mee kan bereiken (althans, niet dat ik weet).

@4Real: Bedankt voor de link. Interessant artikel, alleen is het lastig om dit in mijn situatie toe te passen.

De data in de database is afkomstig uit een Excelbestand, met onderstaande structuur (hier is helaas niets aan te wijzigen):

Naam:	Start:	Eind:	Bovenliggend niveau:
Hoofdcategorie	-	-
Subcategorie 1	-	-	Hoofdcategorie
Subcategorie 2	-	-	Hoofdcategorie
Subcategorie 2 - 1	-	-	Subcategorie 2
Subcategorie 2 - 2	-	-	Subcategorie 2
Naam 1	20-04-2015	24-04-2015	Hoofdcategorie
Naam 2	20-04-2015	24-04-2015	Subcategorie 2 - 1
Naam 3	20-04-2015	24-04-2015	Subcategorie 2 - 2
Naam 4	20-04-2015	24-04-2015	Subcategorie 1

Ik kan uiteraard nog wat doen aan de structuur in de database.

Heeft iemand een idee hoe ik dit kan aanpakken? Als de link van 4real wel toepasbaar is, dan hoor ik het graag. Dan ga ik hier dieper induiken.


Edit:

Ik heb het voor elkaar om volgens het Nested Set principe (zie link van 4Real) een complete lijst van niveaus te krijgen (zie onderstaande sql code).

code:

SELECT 
        CONCAT( REPEAT(' ', COUNT(parent.level_name) - 1), node.level_name) AS name
    FROM 
        levels AS node,
        levels AS parent
    WHERE 
        node.level_lft BETWEEN parent.level_lft AND parent.level_rgt
    GROUP BY 
        node.level_name
    ORDER BY 
        node.level_lft;

Nu staan er in de tabel 'items' nog meer velden waarop gezocht moet kunnen worden. Een voorbeeld van een veld is 'verantwoordelijke'. Wanneer op dit veld gezocht wordt moeten alle items uit de tabel 'items' die voldoen aan de criteria getoond worden met de bovenliggende niveaus.
Dit krijg ik nog niet voor elkaar met onderstaande code. Deze code toont alleen de niveaus die direct toegewezen zijn aan 'persoon X'.

code:

SELECT 
        CONCAT( REPEAT(' ', COUNT(parent.level_name) - 1), node.level_name) AS name
    FROM 
        levels AS node,
        levels AS parent,
        items AS item
    WHERE 
        node.level_lft BETWEEN parent.level_lft AND parent.level_rgt
    AND 
        item.level_id = node.level_id
    AND 
        item.verantwoordelijk = 'persoon X'
    GROUP BY 
        node.level_name
    ORDER BY 
        node.level_lft;

Weet iemand hoe ik ervoor kan zorgen dat op basis van het Nested Set-principe alle items die voldoen aan een zoekcriteria met bijbehorende bovenliggende niveaus getoond kunnen worden?

[ Voor 28% gewijzigd door radem205 op 29-04-2015 10:30 ]

[radem205]

Ok, het is mij inmiddels gelukt om hetgeen te bereiken wat ik wil. Alleen zit ik nog met een performance issue, wat ik graag geoptimaliseerd wil hebben.

Ik heb onderstaande tabellen (ter illustratie):

Levels: (o.b.v. Nested Sets)

level_id	level_lft	level_rgt	level_name
1	2	145	Categorie 1
2	3	12	Subcategorie 1

Taken: (deze tabel bevat meer kolommen waarop gezocht kan worden)

item_id	level_id	item_verantwoordelijk
1	2	persoon X
2	2	persoon X
3	1	persoon Y

Nu wil ik aan de hand van een zoekopdracht in de tabel 'Taken', de juiste niveaus weergeven met de bijbehorende taken.

Als voorbeeld:

Zoekopdracht: item_verantwoordelijk = 'persoon X'

- Categorie 1
---- Subcategorie 1
------ Item_id 1
------ Item_id 2

Dit heb ik inmiddels bereikt met een drietal queries, om zo alle bovenliggende niveaus en de niveaudiepte te kunnen bepalen.

PHP:

<?php

// BEPAAL DE PARENTS VAN DE TAKEN

$sql_spec = $db->prepare("
    
    SELECT 
        parent.level_id, 
        MAX(parent.level_name) AS level_name
    FROM schedule_level AS node ,
            schedule_level AS parent,
            (
                SELECT
                    item_id,
                    level_id
                FROM
                    schedule_item
                AND
                    item_verantwoordelijk = 'Persoon X'
            ) AS item
    WHERE 
        node.level_lft BETWEEN parent.level_lft AND parent.level_rgt
    AND 
        node.level_id = item.level_id
    GROUP BY 
        parent.level_id
    ORDER BY 
        node.level_lft
        
");

if($sql_spec->execute()) {

    $items_control = $sql_spec->fetchAll(PDO::FETCH_ASSOC);
    
    $control = array();
    
    foreach($items_control AS $cont) {
    
        $control[$cont['level_id']] = $cont;
    
    }
    
}

// GEEF ALLE NIVEAUS MET BIJBEHORENDE DEPTH

$sql = $db->prepare("
    
    SELECT 
            node.level_id, 
            node.level_name, 
            (COUNT(parent.level_id) - 1) AS depth
    FROM schedule_level AS node,
                    schedule_level AS parent
    WHERE 
            node.level_lft BETWEEN parent.level_lft AND parent.level_rgt
    GROUP BY 
            node.level_id
    ORDER BY 
            node.level_lft

");

if($sql->execute()) {

    $data = $sql->fetchAll(PDO::FETCH_ASSOC);
    
    $levels = array();
    
    foreach($data AS $d) {
        
        if(array_key_exists($d['level_id'], $control))
            $levels[$d['level_id']] = $d;
    
    }


}

// ZOEK ALLE TAKEN DIE VOLDOEN AAN DE ZOEKOPDRACHT

$sql_items = $db->prepare("
    
    SELECT
        level_id,
        item_id,
        item_verantwoordelijk
    FROM    
        schedule_item
    WHERE
        item_verantwoordelijk = 'Persoon X'
");

if($sql_items->execute()) {

    $items = $sql_items->fetchAll(PDO::FETCH_ASSOC);
        
    foreach($items AS $item) {
    
        $levels[$item['level_id']]['items'][] = $item;
    
    }


}

?>

Problemen / performanceverlies:
- Het grote nadeel aan deze code is dat bij een complexe zoekopdracht tweemaal (in de eerste en laatste query) een complexe (sub)query uitgevoerd moet worden.
- Het lukt mij niet om de eerste 2 queries te combineren.

Hebben jullie advies om de bovenstaande code te versimpelen / verbeteren?

Graag niet letten op het ontbreken van controles. Dit is een stukje code die ik gebruik om te testen.

[Verwijderd]

Je kan met een UNION ALL de twee tabellen relatief gemakkelijk combineren, alleen denk ik niet dat performance-wise veel voordeel zult ervaren. Ik weet niet hoeveel records je hebt en of je bijvoorbeeld altijd alle depths wil weten. Je zou een extra HAVING COUNT kunnen toevoegen bijvoorbeeld.
Verder weet ik ook niet hoe vaak je deze data wil retrieven? Kijk eens naar Memcached of Redis om results te cache-en.

[bobdetweaker]

OP, heb je je al verdiept in closure tables? Het implementeren en beheren van closure tables is zeer gemakkelijk en de poespas die nodig is bij het verplaatsen van een node met zijn children erbij naar een andere parent node is minimaal.

Neem eens een kijkje naar de volgende dingen en beoordeel zelf:

- http://www.slideshare.net...els-for-hierarchical-data
- https://www.percona.com/b...ubtrees-in-closure-table/

Ik heb zelf in meerdere projecten met jouw structuur gewerkt en altijd spijt gehad dat ik niet eerder ben overgestapt naar closure tables. Als je wat voorbeelden wilt zien kan ik wel wat uittypen. Ook kan ik je mogelijk wat methods uit een van mijn services laten zien om je een beeld te geven.

Veel succes!