Geordnete Bäume

Ich möchte verschiedene Kategorien mit beliebig vielen Unterkategorien
mit beliebiger Tiefe in einer Tabelle speichern und diese alphabetisch
sortiert ausgeben lassen, unabhängig davon, in welcher Reihenfolge sie
eingegeben worden sind.

Ausgabe:

A
-AA
-AB
--ABA
B
-BA
--BAA


Ich hab es zuerst mit dem Nested Sets Modell versucht, aber die
Sortierung bringt logischerweise alles durcheinander. Außerdem fand ich
die Ausgabe aller Bäume ohne Subqueries sehr uneffizient, da für jeden
Baum eine Wurzel-ID benötigt wird.

Rekursiv (mit parent-ids für übergeordnete Kategorien) möcht ich wegen
der Effizienz auch nicht arbeiten.

Mein Kollege hatte folgende Idee:

Tabelle kategorien:

id | kategorie | level
-------------------------------------
1 | Sport | 0
2 | Sport\Ballsport | 1
3 | Sport\Ballsport\Fußball | 2
4 | Sport\BallSport\Handball| 2

So könnte man alphabetisch sortieren und Bäume mit beliebiger Tiefe
erzeugen. Allerdings ist imho ziemlich viel Datenüberschuss vorhanden
und die Abfrage nach übergordneten Kategorien mit bspw. LIKE
Sport\Ballsport% gefällt mir auch nicht so richtig.

Gibt es da draußen irgendwo eine Datenstruktur, die meine Anforderungen
effizient erfüllt oder muss ich mir aus den genannten Lösungen einfach
das kleinste Übel aussuchen?

Gruß, Hendrik

Re: Geordnete Bäume

Hendrik Pilz schrieb:
> Ich möchte verschiedene Kategorien mit beliebig vielen Unterkategorien
> mit beliebiger Tiefe in einer Tabelle speichern und diese alphabetisch
> sortiert ausgeben lassen, unabhängig davon, in welcher Reihenfolge sie
> eingegeben worden sind.

Welches RDBMS? Für PostgreSQL hab ich für solche Zwecke bspw. das
ltree-Modul entdeckt. Oracle bringt AFAIK auch was eigenes mit,... Nur
für MySQL ist mir auch noch nichts anderes ein-/aufgefallen außer
NestedSets.

gruss, heli

Re: Geordnete Bäume

Hendrik Pilz wrote:
> Ich möchte verschiedene Kategorien mit beliebig vielen Unterkategorien
> mit beliebiger Tiefe in einer Tabelle speichern und diese alphabetisch
> sortiert ausgeben lassen, unabhängig davon, in welcher Reihenfolge sie
> eingegeben worden sind.
>
> Ausgabe:
>
> A
> -AA
> -AB
> --ABA
> B
> -BA
> --BAA
>
>
> Ich hab es zuerst mit dem Nested Sets Modell versucht, aber die
> Sortierung bringt logischerweise alles durcheinander.

und wenn du erst nach dem Level sortierst und dann erst nach dem Alphabet?

Bis denn dann
Stefan

>...
> Gruß, Hendrik

Re: Geordnete Bäume

Stefan Rybacki schrieb:

>> A
>> -AA
>> -AB
>> --ABA
>> B
>> -BA
>> --BAA
>>
>>
>> Ich hab es zuerst mit dem Nested Sets Modell versucht, aber die
>> Sortierung bringt logischerweise alles durcheinander.
>
>
> und wenn du erst nach dem Level sortierst und dann erst nach dem Alphabet?

Würde dann nicht:

A
B
-AA
-AB
-BA
--ABA
--BAA

rauskommen?

gruss, heli

Re: Geordnete Bäume

Helmut Chang wrote:
> Stefan Rybacki schrieb:
>
>>> A
>>> -AA
>>> -AB
>>> --ABA
>>> B
>>> -BA
>>> --BAA
>>>
>>>
>>> Ich hab es zuerst mit dem Nested Sets Modell versucht, aber die
>>> Sortierung bringt logischerweise alles durcheinander.
>>
>>
>>
>> und wenn du erst nach dem Level sortierst und dann erst nach dem
>> Alphabet?
>
>
> Würde dann nicht:
>
> A
> B
> -AA
> -AB
> -BA
> --ABA
> --BAA
>
> rauskommen?
>

Oh ja stimmt, mein Fehler. Wäre ja zu leicht gewesen. ;)

Bis denn dann
Stefan

> gruss, heli

Re: Geordnete Bäume

Hendrik Pilz haute in die Tasten:
> Mein Kollege hatte folgende Idee:
>
> Tabelle kategorien:
>
> id | kategorie | level
> -------------------------------------
> 1 | Sport | 0
> 2 | Sport\Ballsport | 1
> 3 | Sport\Ballsport\Fußball | 2
> 4 | Sport\BallSport\Handball| 2

ich mache das Ähnlich - jedoch in erweitertet Version, die dir eventuell
weiter hilft:

id | id_parent | kategorie | level | sortorder
---+-----------+-----------+-------+----------
1 | null | Sport | 0 | 1
2 | 1 | Ballsport | 1 | 2
3 | 2 | Fußball | 2 | 3
4 | 2 | Handball | 2 | 4

id_parent ist das Mutterelement eines Eintrags, sortorder die
Sortierreihenfolge innerhalb der Tabelle.
Wenn Du nun Einträge hinzufügst, änderst oder löschst, muss diese
Aufstellung einmal neu generiert werden. Jeden Eintrag kannst Du
beliebig platzieren, unabhängig von seiner alphhabetischen sortierung

Beim Abruf der Daten brauchst du lediglich ein "order by sortorder"
aufzurufen und alles ist in der richtigen reihenfolge. Wie tief du bist,
erkennst du dann am Wert in level.

HTH
Bas

Re: Geordnete Bäume

Sebastian Moderlak wrote:
> Hendrik Pilz haute in die Tasten:
>
>> Mein Kollege hatte folgende Idee:
>>
>> Tabelle kategorien:
>>
>> id | kategorie | level
>> -------------------------------------
>> 1 | Sport | 0
>> 2 | Sport\Ballsport | 1
>> 3 | Sport\Ballsport\Fußball | 2
>> 4 | Sport\BallSport\Handball| 2
>
>
> ich mache das Ähnlich - jedoch in erweitertet Version, die dir eventuell
> weiter hilft:
>
> id | id_parent | kategorie | level | sortorder
> ---+-----------+-----------+-------+----------
> 1 | null | Sport | 0 | 1
> 2 | 1 | Ballsport | 1 | 2
> 3 | 2 | Fußball | 2 | 3
> 4 | 2 | Handball | 2 | 4
>
> id_parent ist das Mutterelement eines Eintrags, sortorder die
> Sortierreihenfolge innerhalb der Tabelle.
> Wenn Du nun Einträge hinzufügst, änderst oder löschst, muss diese
> Aufstellung einmal neu generiert werden. Jeden Eintrag kannst Du
> beliebig platzieren, unabhängig von seiner alphhabetischen sortierung
>
> Beim Abruf der Daten brauchst du lediglich ein "order by sortorder"
> aufzurufen und alles ist in der richtigen reihenfolge. Wie tief du bist,
> erkennst du dann am Wert in level.
>
Arbeiten mit id_parent hat den Nachteil, dass ich nicht nach allem
suchen kann, was zur Kategorie Sport gehört (WHERE id=1 OR id_parent=1
-> Fußball und Handball wird nicht unter Sport gefunden).

Gruß, Hendrik

Re: Geordnete Bäume

Helmut Chang wrote:
> Hendrik Pilz schrieb:
>
>> Ich möchte verschiedene Kategorien mit beliebig vielen Unterkategorien
>> mit beliebiger Tiefe in einer Tabelle speichern und diese alphabetisch
>> sortiert ausgeben lassen, unabhängig davon, in welcher Reihenfolge sie
>> eingegeben worden sind.
>
>
> Welches RDBMS? Für PostgreSQL hab ich für solche Zwecke bspw. das
> ltree-Modul entdeckt. Oracle bringt AFAIK auch was eigenes mit,... Nur
> für MySQL ist mir auch noch nichts anderes ein-/aufgefallen außer
> NestedSets.
>
Tja, ich arbeite leider mit MySQL :(

Wie sieht es mit der Abbildung des Kategoriebaums in einem Array aus?
Ist das zu empfehlen oder eher nicht?

Gruß, Hendrik

Re: Geordnete Bäume

> Arbeiten mit id_parent hat den Nachteil, dass ich nicht nach allem
> suchen kann, was zur Kategorie Sport gehört (WHERE id=1 OR id_parent=1
> -> Fußball und Handball wird nicht unter Sport gefunden).
Sicherlich macht es aber noch weniger Sinn die Bezeichner redundant im
Namen abzuspeichern.

Wie wäre es denn mit einer seperaten Methode, die, wenn nach einer
Kategorie gesucht wird, alle id's der unterkategorien ermittelt, diese
dann in in form von 2,3,4 zurückgibt und Du Deine Query damit fütterst:
where id_parent in (2,3,4)
??

grüße
Bas

Re: Geordnete Bäume

Sebastian Moderlak wrote:
>> Arbeiten mit id_parent hat den Nachteil, dass ich nicht nach allem
>> suchen kann, was zur Kategorie Sport gehört (WHERE id=1 OR id_parent=1
>> -> Fußball und Handball wird nicht unter Sport gefunden).
>
> Sicherlich macht es aber noch weniger Sinn die Bezeichner redundant im
> Namen abzuspeichern.
>
> Wie wäre es denn mit einer seperaten Methode, die, wenn nach einer
> Kategorie gesucht wird, alle id's der unterkategorien ermittelt, diese
> dann in in form von 2,3,4 zurückgibt und Du Deine Query damit fütterst:
> where id_parent in (2,3,4)
> ??
>
Wäre eine Möglichkeit, aber da wären wir wieder bei der Rekursion, die
ich eigentlich vermeiden wollte. Da wäre das Speichern der kompletten
Kategorie-Bezeichner afaik performanter, zur Not kann man ja noch einen
Volltext-Index setzen.

Gruß, Hendrik

Re: Geordnete Bäume

Hendrik Pilz schrieb:

> Wie sieht es mit der Abbildung des Kategoriebaums in einem Array aus?
> Ist das zu empfehlen oder eher nicht?

Verstehe ich jetzt nicht... Wo willst du ein Array haben? Meinst du:
auslesen, Speicherung in PHP in einem Array und dann sortieren?

gruss, heli

Re: Geordnete Bäume

Helmut Chang wrote:
> Hendrik Pilz schrieb:
>
>> Wie sieht es mit der Abbildung des Kategoriebaums in einem Array aus?
>> Ist das zu empfehlen oder eher nicht?
>
>
> Verstehe ich jetzt nicht... Wo willst du ein Array haben? Meinst du:
> auslesen, Speicherung in PHP in einem Array und dann sortieren?
>
Ja, wobei ich den Array serialisieren und in eine Datei oder in die
Datenbank schreiben will. So oft wird ja der Kategoriebaum nicht
geändert, wenn er erst einmal fertig ist. Bei jedem Änderungsvorgang
würd ich den Array dann neu schreiben und serialisieren.

Gruß, Hendrik

Re: Geordnete Bäume

Hendrik Pilz schrieb:
> Helmut Chang wrote:
>
>> Hendrik Pilz schrieb:
>>
>>> Wie sieht es mit der Abbildung des Kategoriebaums in einem Array aus?
>>> Ist das zu empfehlen oder eher nicht?
>>
>>
>>
>> Verstehe ich jetzt nicht... Wo willst du ein Array haben? Meinst du:
>> auslesen, Speicherung in PHP in einem Array und dann sortieren?
>>
> Ja, wobei ich den Array serialisieren und in eine Datei oder in die
> Datenbank schreiben will. So oft wird ja der Kategoriebaum nicht
> geändert, wenn er erst einmal fertig ist. Bei jedem Änderungsvorgang
> würd ich den Array dann neu schreiben und serialisieren.

Wenn er so oft nicht geändert wird, dann sorge doch dafür, dass die
Nodes beim INSERT an der richtigen Stelle eingefügt werden. Beim UPDATE
des Sortierkriteriums hingegen wirds schwieriger. Darüber hast du
allerdings nichts gesagt.

gruss, heli