Rekursive Funktion mit Datenbank

Mad Dog · 16.09.2011, 17:04

Hallo liebe Community,

ich hoffe ich bin hier richtig.
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

Sirke · 16.09.2011, 17:34

Ich würde sagen bis auf die Namen der Felder passt das zu 100%:
http://phpbar.de/w/Baumstruktur_aus_...Array_abbilden

mepeisen · 16.09.2011, 17:39

Zitat:

Zitat von Mad Dog

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

Und das nimmst du wo her? Also diese Annahme?
Da du mehr als einen Root hast, also nur einen Teilbaum aufbaust, kommst du da nicht um eine Rekursion herum. So wie du es beschrieben hast, hast du n-1 Abfragen (n = Anzahl Ebenen). Ich finde das durchaus OK.
Wichtig ist, dass du idealerweise wirklich mit einem IN alle bei vorherigen Durchlauf neu gefundenen Knoten als parent abfragst. Wenn du für jede PID einzeln abfragst, kommst du auf tausende Abfragen, was in der Tat langsam wird.

mepeisen · 16.09.2011, 17:44

Zitat:

Zitat von Sirke

Ich würde sagen bis auf die Namen der Felder passt das zu 100%:
http://phpbar.de/w/Baumstruktur_aus_...Array_abbilden

Warst zu schnell.

Passt nur dann, wenn er jedes mal den kompletten Baum aufbauen will.
So wie ich es verstanden habe, gehts ihm aber nur um den Teil zu Knoten XYZ. Dann immer die komplette Tabelle zu selektieren kann kontraproduktiv sein. Das ist aber eine Farge der Datenmenge. Für kleinere Datenmengen ist die verlinkte Lösung natürlich auch sinnvoll. ABER: Die verlinkte Lösung hat ne Lücke. Je nach Datenkonstellation kann es passieren, dass es sich Daten überschreibt. Beispiel-Daten:

PHP-Code:

  /**

  * gegeben sei eine Tabelle wie folgt:

  * 

  * id | parent | name

  * -------------------

  *  1 |      0 | A

  *  2 |      4 | Ba

  *  3 |      0 | C

  *  4 |      0 | B

  *  5 |      1 | Ab

  *  6 |      4 | Bb

  */

Mit dieser Konstellation passt am Ende dein Baum nimmer, weil du, angekommen bei ID 4, das zuvor schon gespeicherte Child (ID 2) kaputt machst.

Aber das kriegt man auch mit einer Sonderbehanldung hin...

Sirke · 16.09.2011, 18:12

Zitat:

Zitat von mepeisen

Mit dieser Konstellation passt am Ende dein Baum nimmer, weil du, angekommen bei ID 4, das zuvor schon gespeicherte Child (ID 2) kaputt machst.

Das müsste man ja bereits mit "ORDER BY parent,id" hinbekommen, wenn ich das jetzt richtig sehe, oder?!

Die Antwort habe ich als Lösung zu seinem Problem bzw seiner aktuellen Tabelle gepostet. Für sehr große Bäume würde ich "Nested Sets" als Lösung heranziehen, da man damit wirklich gezielt einzelne Teilbäume laden kann.

mepeisen · 16.09.2011, 18:29

Zitat:

Zitat von Sirke

Das müsste man ja bereits mit "ORDER BY parent,id" hinbekommen, wenn ich das jetzt richtig sehe, oder?!

Nicht wirklich. Gibt bestimmt ne Konstellation, wo das order by nimmer ausreicht. Davon abgesehen ist order by überflüssig. Einfacher ist es, die entsprechende Zuweisung etwas geschickter zu machen.

Zitat:

Zitat von Sirke

Die Antwort habe ich als Lösung zu seinem Problem bzw seiner aktuellen Tabelle gepostet. Für sehr große Bäume würde ich "Nested Sets" als Lösung heranziehen, da man damit wirklich gezielt einzelne Teilbäume laden kann.

Richtig, ja. Zumahl es hierzu die ein oder anderen Beispiele/Bibliotheken bereits gibt.

lcrash · 16.09.2011, 21:34

http://www.html.de/php/40963-rekursi...datenbank.html

G.Schuster · 16.09.2011, 23:53

Zitat:

Zitat von Mad Dog

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

Nested Set verwenden und auf Rekursion pfeifen.

Mad Dog · 19.09.2011, 12:48

Hallo,

lieder habe ich eine feste Tabellenstruktur gegeben und Nested Set lässt sich leider nicht anwenden.
Ich habe angefangen eine rekursive Funktion zu schreiben, jedoch bin ich auf ein kleines Problem gestoßen, dass ich nicht ganz nachvollziehen kann.

PHP-Code:

  function childss($parents, $database, $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[0] = $database->loadAssocList();

                    return $row;

                    if(empty($row[0])) {

                        unset($row[0]);

                    } else {   

                        $rows[] = $database->loadAssocList();               

                    }

                }

            }  

        }

        if(empty($rows)) {

            return $children;

        }

        if($level === 2) {

            return $children;

        }

        

        $children = array_merge($rows, $parents);  

        $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);                             

}

Wenn ich die Funktion nun aufrufe, liefert sie mir NULL als Rückgabewert. Ich habe zur Kontrolle die If-Abfrage $level === 2 eingebaut, um zu prüfen ob die Funktion sich überhaupt selbst aufruft.
Dies ist leider nicht so und ich versteh nicht wieso.

Könnt ihr mir da weiterhelfen?

Mfg

mad dog

nikosch · 19.09.2011, 12:51

Weil ein return die Funktion beendet.

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Thema bewerten
Thema bewerten:

Ähnliche Themen
Thema	Autor	Forum	Antworten	Letzter Beitrag
Hilfe: datenbank mappen und kopieren	MIB	Datenbanken	29	15.02.2012 21:55
[Erledigt] Funktion zur Ausgabe eines Datensatzes meiner Datenbank	AtriX_Fabsy	Datenbanken	11	06.05.2009 19:35
Datenbankabfrage Max mit funktion	tiego	PHP Tipps 2009	4	08.04.2009 21:09
Bilder aus Datenbank / <img>-Tags automatisch generieren	Teela	PHP Tipps 2009	2	14.03.2009 17:40
[Erledigt] Array innerhalb einer Funktion	Marko_Schulze	PHP Tipps 2008	8	02.12.2008 18:58
Wert einer Funktion an andere Funktion übergeben	Secondary	PHP Tipps 2008	14	27.08.2008 10:36
PHP-GTK Tutorial		Beitragsarchiv	9	02.11.2005 21:07
[Erledigt] mysql datenbank anlegen...aber WIE???		PHP Tipps 2005-2	0	05.08.2005 19:33
mysql datenbank anlegen...aber WIE???		Datenbanken	0	05.08.2005 19:32
mysql datenbank anlegen...aber WIE???		Datenbanken	0	05.08.2005 19:31
[Erledigt] mysql datenbank anlegen...aber WIE???		Datenbanken	0	05.08.2005 19:31
[Erledigt] mysql datenbank anlegen...aber WIE???		Datenbanken	0	05.08.2005 19:29
mysql datenbank anlegen...aber WIE???		Datenbanken	0	05.08.2005 19:29
[Erledigt] Wie kann ich beliebig viele Werte an eine Funktion übergeben		PHP Tipps 2005	11	25.01.2005 10:44
[Erledigt] Funktion in funktion nicht möglich?		PHP-Fortgeschrittene	4	28.11.2004 00:14

16.09.2011, 17:04
Mad Dog Neuer Benutzer Registriert seit: 18.11.2008 Beiträge: 8	Rekursive Funktion mit Datenbank Hallo liebe Community, ich hoffe ich bin hier richtig. 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


Mister Ad PHP Code Flüsterer Registriert seit: 21.08.2005 Beiträge: 4682 PHP-Kenntnisse: Fortgeschritten

16.09.2011, 17:34
Sirke Erfahrener Benutzer Registriert seit: 04.07.2003 Beiträge: 359 PHP-Kenntnisse: Fortgeschritten	Ich würde sagen bis auf die Namen der Felder passt das zu 100%: http://phpbar.de/w/Baumstruktur_aus_...Array_abbilden

16.09.2011, 21:34
lcrash Erfahrener Benutzer Registriert seit: 11.04.2011 Beiträge: 260 PHP-Kenntnisse: Fortgeschritten	http://www.html.de/php/40963-rekursi...datenbank.html

19.09.2011, 12:48
Mad Dog Neuer Benutzer Registriert seit: 18.11.2008 Beiträge: 8	Hallo, lieder habe ich eine feste Tabellenstruktur gegeben und Nested Set lässt sich leider nicht anwenden. Ich habe angefangen eine rekursive Funktion zu schreiben, jedoch bin ich auf ein kleines Problem gestoßen, dass ich nicht ganz nachvollziehen kann. PHP-Code: function childss($parents, $database, $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[0] = $database->loadAssocList(); return $row; if(empty($row[0])) { unset($row[0]); } else { $rows[] = $database->loadAssocList(); } } } } if(empty($rows)) { return $children; } if($level === 2) { return $children; } $children = array_merge($rows, $parents); $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); } Wenn ich die Funktion nun aufrufe, liefert sie mir NULL als Rückgabewert. Ich habe zur Kontrolle die If-Abfrage $level === 2 eingebaut, um zu prüfen ob die Funktion sich überhaupt selbst aufruft. Dies ist leider nicht so und ich versteh nicht wieso. Könnt ihr mir da weiterhelfen? Mfg mad dog

19.09.2011, 12:51
nikosch moderatives Dielektrikum Registriert seit: 21.05.2008 Beiträge: 35.987 PHP-Kenntnisse: Fortgeschritten	Weil ein return die Funktion beendet. __________________ -- One pixel is still too big. Please make it smaller. ASAP. Initiative Mittelstand. Die wichtigste Gestaltungsregel im Screendesign ist Pi mal Daumen des Arbeitgebers. --