Materialized Path im relationalen Modell

[jemand]

Hallo.

Ich habe bereits von Materialized Path gehört, um hierarchische Daten darzustellen. So ist dabei das Vorgehen.

ID;Mitarbeiter;Vorgesetzter
1;Müller;0
2;Maier;1
3;Walter;1.2
4;Krause;1.2
5;Rüdiger;1

Könnte man das im relationalen Modell nicht auch so darstellen?

ID;Mitarbeiter;PathID (FK zu Path-Tabelle)
1;Müller;null
2;Maier;1
3;Walter;2
4;Krause;2
5;Rüdiger;1

Path-Tabelle:
PathID;ParentID;Layer
1;1;1
2;1;1
2;2;2

In der Path-Tabelle werden also die Ebenen aller Paths (wie 1 oder 1.2) auf mehrere Zeilen gesplittet.

 

[Kampfgummibaerlie]

null ist nicht einmal ein Wert, der soviel verrät, wie "0"...

0 ist eine Information, null aber keine

=> nein ^^

 

[jemand]

Null oder 0 spielt für dieses Beispiel jetzt erstmal keine Rolle. Es geht mir nur ums Prinzip.
Und warum sollte das nicht (so gut) funktionieren? Ist doch genau das Gleiche, nur dass die Ebenen des Paths in einer Tabelle aufgesplittet sind.

 

[Kampfgummibaerlie]

ich kenne die Datenbankstruktur dahinter nicht, genauso wie ich als Vorgesetzten einen Integer nutzen würde, und nicht Dezimalzahlen.

Erzähl ein wenig mehr um alles rundherum, wo kommt es zum Einsatz, und so weiter...

Habe von Materialized Views bisher nicht wirklich eine Ahnung, kenne aber das prinzipielle Datenbanksystem von PostgreSQL recht gut.

 

[jemand]

Achso. Das mit den Vorgesetzten ist nur ein Beispiel.

Eine Möglichkeit, um hierarchische Daten darzustellen ist die Verwendung vom Parent eines Datensatzes.
Alternativ gibt es auch Materialized Paths (auch Lineage Column) als Möglichkeit, indem nicht (nur oder unbedingt) das Parent für ein Datensatz gespeichert wird, sondern der absolute Pfad - ähnlich wie bei Dateinamen.

Hierarchical data in MySQL: easy and fast

Wenn wir also das Vorgesetzten-Beispiel haben, ist folgendes damit gemeint.

ID;Mitarbeiter;Vorgesetzter
1;"Müller";"0"
2;"Maier";"1"
3;"Walter";"1.2"
4;"Krause";"1.2"
5;"Werner";"1.2.4"
6;"Friedrich";"1.2.4"
7;"Rüdiger";"1"

Müller befindet sich im Root-Verzeichnis (/).
Maier befindet sich im Verzeichnis /Müller, Walter und Krause unter /Müller/Maier, Werner und Friedrich unter /Müller/Maier/Krause und Rüdiger unter /Müller.

Ich wollte aber die String-Struktur unter "Vorgesetzter" in eine neue Tabelle splitten, weil man sonst kein einfaches Query erstellen könnte, um z.B. von "1.2" auf "Müller.Maier" zu kommen und ich es sowieso als unsauber halte für eine RDB.

Deswegen habe ich es so gemacht.

ID;Mitarbeiter;PathID (FK zu Path-Tabelle)
1;"Müller";null
2;"Maier";1
3;"Walter";2
4;"Krause";2
5;"Werner";3
6;"Friedrich";3
7;"Rüdiger";1

Path-Tabelle: (ParentID ist ein Index, steht jetzt zur besseren Veranschaulichung eben als String da)
PathID;ParentID;Layer
1;"Müller";1

2;"Müller";1
2;"Maier";2

3;"Müller",1
3;"Maier";2
3;"Krause";3

Ich hatte es schon ausprobiert und es funktioniert. Es ist ziemlich einfach zu implementieren und abzufragen und es wird wohl auch von der Laufzeit her besser sein als wenn ich die Hierarchie nur über Parents anordne und rekursiv bis zur höchsten Ebene muss, um den vollen Pfad rauszufinden. Allerdings macht mir hier die Redundanz große Sorgen.

 

[Kampfgummibaerlie]

gegen die Redundanz womöglich arrays nutzen?
(ich glaube, du meinst in dem fall die wiederholungen von den PathIDs mit redundanz)

 

[jemand]

Ich meine z.B., dass bei PathID=3 Müller und Maier dabeisteht (also alle Ebenen). Das ist eben der Nachteil bei dieser Variante ggü. der Parent-Variante, wo eben nur der direkte Parent angegeben wird und man dadurch viel Platz spart. Allerdings hat auch die Parent-Variante ihre Nachteile ggü. der Path-Variante.

Wie genau meinst du das mit den Arrays?

Danke

 

[Kampfgummibaerlie]

Man kann mehrere Werte in eine Spalte speichern, wie zB:

Zimmer, Gäste (Familienmitglieder, etc)
1, [1, 2, 3, 4, 5]

 

[jemand]

Aber kann man dann ein Query aufsetzen, der den Namen der einzelnen Elemente im Array findet?

Also: Statt: 1, [1, 2, ...] dann 1, [Gerda, Marleen, ...]

Geht sowas innerhalb eines Arrays?

 

[Kampfgummibaerlie]

habe mir die mühe gemacht, und das Ganze für dich geschrieben

Tabellen erstellen:

create table infos(id integer, text text);
create table directions(id int[]);

Inserts:

insert into infos(id, text) values (1, 'Ich');
insert into infos(id, text) values (2, 'bin');
insert into infos(id, text) values (3, 'Kampfgummibaerlie');
insert into infos(id, text) values (4, 'Fehler!');
insert into directions(ids) values ('{1, 2, 3}');

Abfrage:

select infos.text from infos, directions where directions.ids @> array[infos.id] order by infos.id;

Ergebnis:

       text
-------------------
 Ich
 bin
 Kampfgummibaerlie
(3 Zeilen)

Ich hoffe, du kannst mit dem was anfangen, wenn nicht, einfach weiterfragen

EDIT:
Ich denke, in etwa sowas möchtest du nutzen, wenn nicht, direkt ansagen, dass ich in die falsche Richtung arbeite ;D

 

[jemand]

Hey, danke Werde mir das morgen mal genauer ansehen.

 

[castorp]

Für Postgres gibt es eine exentsion die einen Datentyp zur Verfügung stellt, der letztendlich einen Materialized Path repräsentiert: F.21. ltree

Aber das - und auch die Verwendung eines Array - hat den gr0ßen Nachteil, dass man keine foreign keys mehr definieren kann.

Die Speicherung via "parent ID" (auch bekannt als "adjencancy model") ist sehr effizient und ermöglicht foreign keys (und man kann einen fehlenden Eintrag auch sauber mit NULL speichern). Nach meiner Erfahrung sind die rekursiven Abfragen ausreichend schnell. Ich habe eine Tabelle mit > 50 Millionen Datensätzen und lese typischerweise Bäume/Hierarchien mit hunderten oder auch tausenden von Elementen. Die Laufzeiten der Abfragen liegen dabei typischerweise unter 100 Millisekunden (meist sogar unter 10ms).
Langsam werden die nur, wenn man von mehr als einem Startelement ausgeht (also im nicht-rekursiven Teil der Abfrage mehr als ein Element selektiert).

es wird wohl auch von der Laufzeit her besser sein als wenn ich die Hierarchie nur über Parents anordne und rekursiv bis zur höchsten Ebene muss, um den vollen Pfad rauszufinden.

Vor allem bei Deinem Beispiel denke ich nicht, dass Du mit rekursiven Abfragen irgendwelche Probleme bekommst. Selbst in wirklich großen Firmen wird so eine Tabelle höchstens ein paar hundert Tausend Einträge haben.

Um die Hierarchie ausgehend vom Angestellten "Krause" auszulesen kannst Du diese Abfrage verwenden:

with recursive tree as (
  select *
  from mitarbeiter
  where name = 'Krause'
  union all
  select v.*
  from mitarbeiter v
    join tree m on m.vorgesetzter = v.id
)
select *
from tree;

Die Spalte "vorgesetzter" ist dabei ein foreign key auf die "id" Spalte:

create table mitarbeiter (id int primary key, name text not null, vorgesetzter int references mitarbeiter);
create index on mitabeiter (id, parent_id);
insert into mitarbeiter (id, name, vorgesetzter)
values
(1, 'Müller', null),
(2, 'Maier', 1),
(3, 'Walter', 2),
(4, 'Krause', 2),
(5, 'Rüdiger', 1);

Es ist ziemlich einfach zu implementieren und abzufragen

Aber Änderungen sind extrem aufwändig.

Stell Dir mal vor, Walter wird der Vorgesetzte von Krause. Mit dem obigen Modell ist das genau ein UPDATE Statement - unabhängig wie viele Angestellte "unterhalb" von Krause derzeit liegen. Mit dem materialized Path Modell musst Du deutlich mehr Datensätze aktualisieren und Du musst bei jedem Eintrag wissen wie der neue Pfad genau aussieht.

Ähnlich aufwändig ist es, wenn ein Mitarbeiter (der auch Vorgesetzter ist) die Firma verlässt. Mit dem obigen Modell ist das genau ein DELETE und ein UPDATE Befehl. Mit dem materialized path musst Du wieder durch alle Einträge gehen und für jeden den Pfad neu erstellen.

 

[dabadepdu]

Man könnte also noch argumentieren, dass natürgemäß statische oder sogar readonly Daten für dieses Verfahren gut geeignet sind, weil es eben keine Änderungen gibt. Etwa Stammbäume, Wege, usw., dann gibt es noch Mischwelten, wie vielleicht ein Produktkategoriensystem, das sich nur langsam ändert, aber keineswegs eindeutig ist, wo es also u.U. mehrere Pfade geben könnte.

Die Performance ist dann so eine Sache, zwar ist die Indizierung nicht möglich, vielleicht in einigen Fällen auch nicht notwendig, weil der gesamte Path ja auf einen Schlag alle Parentelemente bietet (ähnlich einem Index). Ich habe aber keine Erfahrungen mit dieser Speicherform. Anwendungsfälle mit Mengen im 2-stelligen Millionenbereich wären für mich jedenfalls schon high end. Hier böte sich zumindest bei einem tiefen Element die Situation, dass ich damit auch quasi Direktzugriff auf alle Parents habe. Das ist meist leider nicht der einzige Anwendungsfall, den man in Hirarchien bedienen muss.
Noch eine Perspektive bietet die Frage der Redundanz- die man eigentlich in einem normalisierten Modell vermeiden möchte-:
Einfache Formel: Redundanz bietet adhoc Performancevorteile, aber bedeutet enorm erhöhten Pflegeaufwand und die Gefahr- bei falscher Pflege- der Dateninkonsistenz.
Und dazu passend noch der Platz: Datenbankspeicherplatz ist m.E. vergleichsweise "billig" und eigentlich kein Kriterium mehr, jedenfalls ein deutlich geringeres, als logische Probleme/Pflegeaufwand, die sich durch Redundanz ergeben.

Mein Fazit: Wenn keine besonderen Gründe vorliegen, würde man keine "exotischen" Modellierungen einsetzen, sondern klassisch mit ParentID, zugehörigem FK und Index arbeiten. Ein Pfad könnte man daraus per Abfrage jederzeit generieren, wenn nötig, bspw. für bestimmte Optimierungsfragen, z.B. tagesaktuell oder so

 

[jemand]

Danke für eure Antworten.

Ich habe mich dazu entschieden, eine Parent-Struktur aufzustellen. Der Name im Zusammenspiel mit dem Parent ist UNIQUE, weil ich im selben Verzeichnis nicht mehrere Male den gleichen Namen will, in einem anderen Verzeichnis kann der Name wieder vorkommen.

Um den Pfad rauszubekommen, hatte ich auch das CTE aufgestellt.

WITH RECURSIVE cte AS(SELECT id, name, parent FROM Artikel WHERE name='Holzschrank' UNION ALL SELECT a.id, a.name, a.parent FROM Artikel a JOIN cte ON cte.parent = a.id) SELECT * FROM cte;

Ich bekomme folgende Struktur.

id;name;parent
9;Holzschrank;2
10;Holzschrank;6
2;Sonderangebote;1;
6;Top-Angebote;1
1;Schränke;null
1;Schränke;null

Jetzt wäre es allerdings toll, wenn ich aus dieser Struktur so etwas bekommen würde.

id;name;path;pathString
9;Holzschrank;[2,1];[Sonderangebote,Schränke]
10;Holzschrank;[6,1];[Topangebote,Schränke]

Der erste Gedanke war natürlich ein GROUP BY in Verbindung mit JSON_AGG, allerdings lässt sich nichts so gruppieren, dass man auf diese Form kommt.

Hat jemand einen Tipp, was man dafür anwenden müsste?

 

[Kampfgummibaerlie]

Soda, weil ich bei weitem zuviel Freizeit habe (auch um solche Uhrzeiten):

Tabelle erstellen:

create table artikel(id integer, name text, num integer);

Werte einfügen:

insert into artikel values (9, 'Holzschrank', 2);
insert into artikel values (10, 'Holzschrank', 6);
insert into artikel values (2, 'Sonderangebote', 1);
insert into artikel values (6, 'Top-Angebote', 1);
insert into artikel values (1, 'Schränke', null);
insert into artikel values (1, 'Schränke', null);
[/codde]

Schauen, ob alles darin ist:
[code]
select * from artikel;

Hier eine Abfrage:
(Ich komme, nicht wie du es wolltest auf 2 Datensätze, sondern auf 4, hoffe aber geholfen zu haben)

select string_agg(id::text, ', ') as ids, string_agg(name, ', ') as names,
string_agg(id::text, ', '), name as name from artikel group by name;

Am Rande:
Ich glaube die string_agg noch nie verwendet zu haben, also danke, dass ich das kennenlernen durfte

Wie kam ich dann darauf?
Google ist meine Macht :O

Bin etwas schüchtern, und möchte hier keinen Link zu fremdem Forum verlinken xD (anderes Forum, ist ein Thread dort aus 2008)

EDIT:
Würde aber im Allgemeinen eine solche "plumpe" Datenbankstruktur hinterfragen ...
Bin eher gewohnt, dass alles sein Eckchen hat, wo es einzeln änderbar ist.

EDIT2:
Die letzte selektierte Spalte in meiner Abfrage eigentlich unnötig, habe die nur eingefügt, weil ich irgendein Problem hatte mit aggregierte Spalten können nicht gruppiert werden, oder so...