Repräsentation von Diskussionsthreads in SQL-Datenbanken

Abstract

Diskussionen in Newsgroups und Mailinglisten werden üblicherweise als Baum dargestellt. Jede Message (außer der Ursprungsmessage des Threads) ist Antwort auf genau einen Vorgängerartikel.

Eine naive Abbildung dieser Struktur auf eine relationale Datenbank würde mittels des Reply-To-Feldes jede Messge mit ihrer Vorgängerin verknüpfen. Da SQL aber keine Möglichkeit bietet, so gebildete Bäume abzugehen, ist diese Implementation ineffizient.

Dieser Artikel stellt eine alternative, effizientere Methode vor und schlägt einige Möglichkeiten ihrer praktischen Umsetzung vor.

Messages und Threads

Diskussionen in Newsgroups und Mailinglisten bestehen aus einzelnen Messages. Jede Message ist durch eine Message-Id eindeutig bezeichnet. Eine Menge zusammengehöriger Messages bezeichnet man als Thread.

Für die »Zusammengehörigkeit« gibt es unterschiedliche Konventionen:

• [RFC1036] spezifiert einen Header References:

  This field lists the Message-ID's of any messages prompting the submission of this message. It is required for all follow-up messages, and forbidden when a new subject is raised.

• [RFC822] spezifiert einen Header In-Reply-To für den gleichen Zweck

  The contents of this field identify previous correspon- dence which this message answers.

  und einen Header References für other correspondence.

• [RFC2822] dokumentiert die derzeit übliche Praxis, im In-Reply-To-Header die unmittelbare Vorgänger-Message zu erwähnen, im References-Header dagegen alle Vorgänger-Messages bis zur Wurzel des Baums. Außerdem weist er darauf hin, dass eine Message mehrere Vorgänger haben kann (die alle im In-Reply-To-Header erwähnt werden sollen): In diesem Fall bildet der Thread natürlich keinen Baum mehr, sondern einen DAG, und der References-Header hat zu entfallen.

• Darüber hinaus wird häufig der Subject-Header verwendet, wenn weder ein In-Reply-To-Header noch ein samp>References-Header vorhanden sind. In diesem Fall ist die exakte Position im Thread natürlich nicht bekannt.

Für den Rest dieses Artikels nehmen wir an, dass aus der Anwendung einer dieser Konventionen (oder der Kombination mehrerer) bereits ein eindeutiger Thread-Baum gebildet wurde.

Verweis auf die Vorgänger-Message

Eine naheliegende Implementation besteht darin, einfach mit jeder Message die Vorgängerin (samp>In-Reply-To-Header, wenn nicht vorhanden, kann er aus der Position im Thread erzeugt werden):

Ausgehend von der Ausgangsmessage kann man dann den Thread rekonstrieren indem man jeweils die unmittelbaren Antworten auf diese Message ermittelt:

select * from messages where in_reply_to=?

und dieses Verfahren rekursiv fortsetzt.

Es ist leicht zu sehen, dass dies zu einer großen Anzahl von Queries führt: Um alle 5 Replies dieses Threads zu ermitteln, sind 4 Queries nötig, und 2 weitere, um zu ermitteln, dass es keine weiteren gibt.

Manche SQL-Dialekte (z.B. Oracle[Oracle]) bieten Konstrukte an, um einen Baum mit einer einzigen Query abzufragen:

select * from messages start with message_id=? connect by in_reply_to = prior message_id

Damit wäre das Problem gelöst, aber leider ist das nicht Standard-SQL und damit für datenbank-unabhängige Applikationen nicht zu gebrauchen (Tatsächlich ist Oracle die einzige mir bekannte Datenbank, die hierarchical queries erlaubt).

Daher wird im folgenden eine alternative Methode vorgeschlagen.

Kodierung der Position im Thread als Folge von Zahlen

Dieser Ansatz wurde von der Darstellung von Bäumen als "nested sets"[Celko1999] inspiriert:

Bei den "nested sets" wird jeder Knoten im Baum als Intervall natürlicher Zahlen dargestellt, wobei jedes Nachkomme ein Subintervall darstellt. Obiger Thread würde also wie folgt dargestellt:

Das erlaubt eine einfache Abfrage aller Nachfahren in sortierter Reihenfolge, der Anzahl der Nachfahren, und aller Vorgänger eines Knotens. Das Einfügen und Löschen eines neuen Knotens ist aufwändig (die Hälfte aller Knoten muss modifiziert werden), und es ist auch nicht leicht möglich, die Tiefe eines Knotens im Baum herauszufinden (was für die graphische Darstellung des Threads wichtig wäre).

Daher wird die Position der Message im Thread wie folgt kodiert:

• Die Wurzel jedes Threads wird mit der leeren Zahlenfolge bezeichnet: ().
• Die Antworten auf eine Message werden durchnummeriert und mit der Zahlenfolge der Vorgängermessage plus ihrer eigenen Nummer kodiert. Die unmittelbaren Antworten auf die Wurzel haben also die Bezeichnungen (1), (2), (3), ... die Antworten auf (1) die Bezwichnungen (1 1), (1 2), (1 3), u.s.w.

Dies erlaubt erlaubt eine einfache Abfrage aller Nachfahren in sortierter Reihenfolge, des unmittelbaren Vorgängers, und auch Tiefe im Baum ist unmittelbar ersichtlich. Ebenso ist das einfügen einer neuen Message trivial.

Leider kennt SQL keinen Datentyp "Zahlenfolge", so dass dieser auf einen anderen Typ variabler Länge abgebildet werden muss. Die Typen VARCHAR und BLOB bieten sich hier an.

Welchen Typ man nimmt, hängt von der Datenbank ab, da unterschiedliche Datenbanken unterschiedliche Einschränkungen machen:

• VARCHAR ist häufig relativ kurz (255 Zeichen), außerdem sind manche Zeichen nicht erlaubt (z.B. NUL oder Spaces am Ende des Felds). Die Sortierreihenfolge hängt außerdem von der Locale ab.
• BLOBs hingegen können häufig nicht direkt abgefragt werden oder nicht in einem Index verwendet werden.

Daher werden im folgenden mehrere Kodierungsmöglichkeiten vorgeschlagen, die entweder für BLOBs oder VARCHARs geeignet sind.

Literatur

[Celko1999]

Joe Celko's SQL for Smarties: Advanced SQL Programming Second Edition
Joe Celko
The Morgan Kaufmann Series in Data Management Systems, Jim Gray, Series Editor
October 1999
576 pages
Paper
$44.95
ISBN 1-55860-576-2

[Oracle]

Oracle8i SQL Reference
Release 3 (8.1.7)
Part Number A85397-01

[RFC822]

RFC 822 - Standard for the format of ARPA Internet text messages
D. Crocker
Aug-13-1982

[RFC1036]

RFC 1036 - Standard for interchange of USENET messages
M.R. Horton, R. Adams
Dec-01-1987

[RFC2279]

RFC2 2279 - UTF-8, a transformation format of ISO 10646
F. Yergeau
January 1998

[RFC2822]

RFC 2822 - Internet Message Format
P. Resnick, Ed.
April 2001