Rekursive Funktion mit Datenbank

[Mad Dog]

Hallo liebe Community,

ich stehe hier vor einem "Problem".

Ich habe eine Tabelle mit Kategorien. Jede Kategorie hat einen eindeutige ID, eine Parent_ID und einen Namen. Die Parent_ID verweisst, wie der Name schon sagt, auf die Elternkategorie. Jetzt ist es so, das ich eine Oberkategorie gegeben habe (Oberkategorien haben eine Parent_ID von 0, d.h. sie haben keine Elternkategorien).

Jetzt sollen alle Unterkategorien ausgelesen werden aus der Datenbank. Das Ergebnis soll ein Array sein, mit allen Unterkategorien von der Oberkategorie. Eine Kategorie kann nur eine Unterkategorie, aber auch rein theoretisch auch 1000 Unterkategorien haben.

Leider unterstützt MySQL kein SQL Statement mit einem "WITH", also keine rekursive Abfrage auf der Serverseite, was z.B. in Oracle kein Problem darstellt.

Meine nächste Idee wäre eine rekursive Funktion gewesen, welche die Kategorien selectiert, die die Oberkategorie als Eltern haben (in einem Array gespeichert). Danach wird die selbe Funktion wieder aufgerufen, diesmal wird das Array durchlaufen und geschaut ob die da drinne enthaltenen Kategorien bei Kategorien in der Datenbank als Eltern auftretten, wenn ja wird diese Kategorien oder auch mehrere in das array hinzugefügt.
Sollte es keine weitere Unterkategorie mehr geben, wird diese Kategorie in dem Array dementsprechend markiert um "ünnötige" Queries an die Datenbank zu verhindern.

Mir kommt das ganze nur irgendwie so vor, als ob es am Ende eine sehr langsame Funktion sein wird.

Habt ihr entsprechende Verbesserungsvorschläge oder gar komplett andere Ansätze?

Hier nochmal das Layout der Tabelle:

ID | PID | Name
1 0 a
2 1 b
3 1 c
4 2 d
5 3 e
6 0 f
7 0 g
8 6 h
9 7 i
10 9 j

Wäre a die Oberkategorie, sollte das Array am Ende die Kategorien 2,3,4 und 5 enthalten.
Ich hoffe ich habe mich verständlich ausgedrückt.

Mit freundlichen Grüßen,

Mad Dog

 

[NetAktiv]

Also wenn ich das richtig verstehe, dann willst du bei einem Punkt in einer Baum-Hierarchie starten und alle Unterpunkte als (flache 1-dimensionales) Array, also letztendlich als Liste, ausgeben? Wenn das richtig ist, dann wäre dein Ansatz als rekursiver Aufruf sicher gut.

 

[crash]

Nested Sets ansehen.

 

[T!P-TOP]

@TE: ich weiß zwar nicht, ob du bereits das Ganze umgesetzt hast, ich stand jedenfalls vor einer ähnlichen Aufgabe. In meinem CMS gibts ich in der neuen Version unter anderem die Möglichkeit, Menüs zu erstellen. Die Menu-Links eines Menüs kann man dabei unendlich tief verschachteln. Habs mit Rekursion gelöst und bin mit einem Query ausgekommen:

id	parent_link_id	name
1	0	html
2	1	listen
3	2	ol
4	2	ul
5	4	foo
6	4	bar
7	2	dl
8	1	überschrift
9	8	h1
10	8	h2
11	8	h3
12	8	h4

<?php
/* $this->menuLinks ist das array welches die datensätze für die menü-links beinhaltet */
getMenuStructur($this->menuLinks);

function getMenuStructur($menuLinks, $parent_link_id = 0) 
{
    $newUl = false;

    foreach($menuLinks as $menuLink) {
        if ($menuLink['parent_link_id'] == $parent_link_id) {
            $newUl = true;
            break;
        }
    }

    if ($newUl) echo '<ul>';

    foreach($menuLinks as $menuLink) {
        if ($menuLink['parent_link_id'] == $parent_link_id) {
            echo '<li>';
            echo $menuLink['name'];
            getMenuStructur($menuLinks, $menuLink['id']);
            echo '</li>';
        }
    }

    if ($newUl) echo '</ul>';
} 
?>

Ausgabe:

html

• listen
  • ol
  • ul
    • foo
    • bar
  • dl
• überschrift
  • h1
  • h3
  • h3
  • h4

 

[Mad Dog]

Hallo

danke für die Antworten.
Jetzt stehe ich wieder vor einem sehr komischen Problem:

function childss($parents, $database, $level = 1) {
if($level === 1) {
foreach($parents as $parentvalue) {
$count = count($parentvalue);
for($i = 0; $i < $count; $i++) {
$pids[] = $parentvalue[$i]['id'];
if($parentvalue[$i]['all'] != 1) {
$query = 'SELECT `id`, `parent_id`, `title` FROM #__categories WHERE parent_id = '.intval($parentvalue[$i]['id']);
$database->setQuery($query);
$row[] = $database->loadAssocList();
if(empty($row[0])) {
unset($row[0]);
} else {
$rows[] = $database->loadAssocList();
$checkedpid[] = intval($parentvalue[$i]['id']);
}
}
}
}

if(empty($rows)) {
return $children;
}

$rows = array_merge($rows, $parents);
$children = $rows;
$count = count($children);
for($i = 0; $i < $count; $i++) {
$count2 = count($children[$i]);
for($j = 0; $j < $count2; $j++) {
if(!in_array($children[$i][$j]['id'], $pids)) {
$children[$i][$j]['level'] = $level;
$children[$i][$j]['all'] = 0;
} else {
$children[$i][$j]['all'] = 1;
}
}
}
$level = $level + 1;
childss($children, $database, $level);
} else {
return 'test';
}
}

Dies ist die Funktion. Klappt fast alles. Würde ich return $children am Ende einfügen, würde ich das korrekte Array erhalten.
Jedoch erhalte ich so wie die Funktion oben ist nur ein "NULL" zurück und ich versteh nicht so ganz wieso.

childss($children, $database, $level) sollte ja eigentlich dazu führen, dass die Funktion sich selbst aufruft und da $level 2 ist (jedenfalls bevor die Funktion sich selbst aufruft) sollte eigentlich 'test' returned werden. Aus irgendeinem Grund ist dem nicht so.

Habt ihr ne Ahnung woran das liegen kann?

@T!P-TOP: Wie sieht den die Funktion aus, die die Datensätze aus der Datenbank ausliest?

 

[mermshaus]

Hier geht's weiter: Rekursive Funktion mit Datenbank - php.de

(Code-Tags wären auch generell nicht schlecht.)

Edit: Hach ja, der Thread ist von Beginn an ein Crossposting gewesen. Wie nett, wie nett.

 

[T!P-TOP]

@T!P-TOP: Wie sieht den die Funktion aus, die die Datensätze aus der Datenbank ausliest?

    public function getMenuLinks($menuId)
    {
        $sql = "SELECT `id`, `parent_link_id`, `name` "
             . "FROM `webrex_menus_links` "
             . "WHERE `menu_id` = '".$this->db->escape($menuId)."'";
        
        $result = $this->db->query($sql);
        
        return $result;    
    }

Diese Model-Methode ruft der controller auf und gibt das array an ein Template-View Objekt weiter. Das View Script greift dann einfach auf dieses Array zu und der Rest ist ja in der Funktion ersichtlich, die in meinem letzten Post zu finden war.