DAG vs. Baum

Ich überlege, ob die Datenstruktur “Baum” nicht vielleicht einer der größeren Fehler der Informatik war. Fast alles reales, was man in einem Baum abspeichert, ist eigentlich ein DAG.

Zur Erläuterung: Ein Baum ist eine Datenstruktur bestehend aus Knoten, in denen jeder Knoten einen oder keinen Vorgänger hat (genauer ist dies ein Wald. Bei einem Baum hat genau ein Knoten keinen Vorgänger). Umgekehrt hat jeder Knoten keine bis beliebig viele Kinder, nämlich genau die, deren Vorgänger der Knoten selbst ist. Kreise sind explizit verboten.

Das bekannteste Beispiel ist das Dateisystem auf einem Computer: Jede Datei liegt in einem Ordner. Der liegt wieder in einem anderen und so weiter, bis hin zu einem der auf dem Laufwerk liegt, das wiederum den Anfang darstellt. Maillisten und einige Arten von Foren und Kommentarsystemen funktionieren ähnlich: Jeder Post ist eine Antwort auf exakt einen vorigen und wird eine Ebene tiefer angezeigt. Baumstrukturen gibt es aber schon länger als es Informatik überhaupt gibt: Das ganze Feld der Taxonomie oder auch die Sprachforschung, die alles in verschiedene Familien und Unterfamilien und so weiter unterteilt, sind genau das.

Bäume lassen sich durch Algorithmen schön und einfach behandeln, z.B. um alle Kinder zu finden. Über Pfadangaben kann ein einzelnes Element eindeutig identifiziert werden.

Es gibt nur ein Problem damit: So funktioniert die Realität nicht. Im Normalfall haben Sachen mehrere Vorgänger. Ein klassisches Beispiel: In welchen Ordner passt diese Datei? In Diskussionen möchte man manchmal auf mehrere Posts, die ähnliche Punkte machen, gleichzeitig antworten. Sprachen gehören nicht zu einer Familie, sondernd haben Einflüsse von vielen andere gleichzeitig.

Um darum herumzukommen, muss man sich für einen Vorgänger explizit entscheiden, oder das Objekt aufteilen (was bei Antworten in Online-Diskussionen gut geht, bei Dateien nur fallweise möglich ist, und zum Beispiel bei der Klassifizierung von Autotypen völlig versagt). In beiden Fällen gehen bestehende semantische Beziehungen verloren.

Die Antwort darauf heißt DAG für Directed Acyclic Graph. Die Regeln sind fast die gleichen wie für einen Baum, nur dass hier ein Knoten mehrere Vorgänger haben kann. Ein Beispiel: iTunes und ähnliche Programme erlauben es zum Beispiel, dass ein Lied in vielen Wiedergabelisten gleichzeitig ist.

DAGs repräsentieren all die Beispiele, die ich genannt habe, auf natürliche Art und Weise. Damit kann eine Datei auch in zwei Ordnern liegen. Da ein Baum ein Spezialfall eines DAGs ist, können bestehende Strukturen auch problemlos darin abgebildet werden.

In der Realität haben viele Systeme im Prinzip Hacks, um DAG-Strukturen zu erstellen. Dank Hardlinks sind Dateisysteme de-facto schon lange DAGs, es wird nur gut versteckt. Symlinks, Aliase und die Windows .LNK-Dateien stellen “Vorgänger zweiter Klasse” da, durch welche die Beziehungen expliziert neu erzeugt werden.

Heutzutage werden klassische hierarchische Strukturen massiv durch Tag-Systeme abgelöst, bei denen eine Datei, Blog-post oder so beliebig viele Tags haben kann. Diese Struktur ist einfach nur ein sehr kurzer DAG. Im Prinzip ist das auch schon ein Lösungsansatz, aber da ich keine Beziehungen zwischen Tags als solchen herstellen kann, und so ein System in manchen Fällen (z.B. Diskussionen) überhaupt nicht geht, würde ich das aber nicht als vollwertigen Ersatz betrachten.

Aus technischer Sicht ist ein DAG wesentlich schwieriger. Zum Beispiel ist ein Baum immer Planar, was heißt das man ihn ohne weiteres ohne sich kreuzende Linien darstellen kann, was bei einem DAG nicht zwingend gegeben ist. Eine Aufzählung aller Elemente ist schwieriger wenn nichts doppelt sein soll. Objekte lassen sich möglicherweise über mehrere völlig unterschiedliche Pfade finden. Das ist natürlich auch genau der Punkt, aber die Frage “bezeichnen die zwei Pfade das selbe Objekt” lässt sich nicht beantworten ohne in den DAG selbst hineinzuschauen (während sie für Bäume trivial ist).

Vor allem aber kenne ich noch keine wirklich gute UI um DAGs darzustellen und zu manipulieren. Beispielsweise ist die Alternative zur Baumstruktur in Online-Foren nicht etwa ein DAG, sondernd eine einfache Liste die nach der Zeit geordnet ist. Beziehungen müssen durch die Inhalte der Texte manuell angezeigt werden.

(All das betrifft natürlich nicht die Anwendung von Bäumen zur effizienteren Verwaltung wo der Nutzer sie nicht sieht, z.B. in Suchindizes, Heaps und anderen Fällen.)

Was meint ihr? Ich habe hier wegen zu viel Spam die Kommentare hier fürs erste abgeschaltet, aber ich bin bei Twitter unter [@zcochrane][1] erreichbar.

Geschrieben am 11. März 2014 um 11:33

0 Kommentare

    New comments can no longer be posted because it got to annoying to fight all the spam.