Repräsentation von Diskussionsthreads in SQL-Datenbanken

1. 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.

2. 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.

3. 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):

Message-ID From In-Reply-To ...
<20021021182732.GA6633@minsky.chello.at> "Harald R. Haberstroh" <Harald@XXX.at> NULL
<02102122202400.00672@chuck.teleweb.at> Alexander Hausner <alh@XXX.at> <20021021182732.GA6633@minsky.chello.at>
<20021021211728.GA8902@minsky.chello.at> "Harald R. Haberstroh" <Harald@XXX.at> <02102122202400.00672@chuck.teleweb.at>
<02102221293500.00360@chuck.teleweb.at> Alexander Hausner <alh@XXX.at> <20021021211728.GA8902@minsky.chello.at>
<20021022203911.GA14136@minsky.chello.at> "Harald R. Haberstroh" <Harald@XXX.at> <02102221293500.00360@chuck.teleweb.at>
<20021022221211.GC12301@teal.h.hjp.at> "Peter J. Holzer" <hjp-luga@XXX.at> <02102221293500.00360@chuck.teleweb.at>
...

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.

4. 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:

Message-ID From In-Reply-To Left Right ...
<20021021182732.GA6633@minsky.chello.at> "Harald R. Haberstroh" <Harald@XXX.at> NULL 1 12
<02102122202400.00672@chuck.teleweb.at> Alexander Hausner <alh@XXX.at> <20021021182732.GA6633@minsky.chello.at> 2 11
<20021021211728.GA8902@minsky.chello.at> "Harald R. Haberstroh" <Harald@XXX.at> <02102122202400.00672@chuck.teleweb.at> 3 10
<02102221293500.00360@chuck.teleweb.at> Alexander Hausner <alh@XXX.at> <20021021211728.GA8902@minsky.chello.at> 4 9
<20021022203911.GA14136@minsky.chello.at> "Harald R. Haberstroh" <Harald@XXX.at> <02102221293500.00360@chuck.teleweb.at> 5 6
<20021022221211.GC12301@teal.h.hjp.at> "Peter J. Holzer" <hjp-luga@XXX.at> <02102221293500.00360@chuck.teleweb.at> 7 8
...

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.
Message-ID From In-Reply-To Position ...
<20021021182732.GA6633@minsky.chello.at> "Harald R. Haberstroh" <Harald@XXX.at> NULL ()
<02102122202400.00672@chuck.teleweb.at> Alexander Hausner <alh@XXX.at> <20021021182732.GA6633@minsky.chello.at> (1)
<20021021211728.GA8902@minsky.chello.at> "Harald R. Haberstroh" <Harald@XXX.at> <02102122202400.00672@chuck.teleweb.at> (1 1)
<02102221293500.00360@chuck.teleweb.at> Alexander Hausner <alh@XXX.at> <20021021211728.GA8902@minsky.chello.at> (1 1 1)
<20021022203911.GA14136@minsky.chello.at> "Harald R. Haberstroh" <Harald@XXX.at> <02102221293500.00360@chuck.teleweb.at> (1 1 1 1)
<20021022221211.GC12301@teal.h.hjp.at> "Peter J. Holzer" <hjp-luga@XXX.at> <02102221293500.00360@chuck.teleweb.at> (1 1 1 2)
...

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.

4.1. Big-Endian Binärzahlen

Jede Zahl wird durch n Bytes in Big-Endian-Kodierung dargestellt. Die Zahl n hängt von der Anzahl der erwarteten Replies auf jede Message ab. 1 Byte erlaubt bis zu 256 Antworten, was für die meisten Diskussionen reichen dürfte (lange Diskussionen bilden i.A. eher lange Ketten von Argument und Gegenargument als dass viele Replies auf eine einzelne Message kommen), in Einzelfällen aber wohl überschritten werden kann. 2 oder 3 Bytes müssten praktisch immer ausreichen.

Die Sortierbarkeit als String ist durch die Big-Endian-Kodierung gewährleistet, die Tiefe im Baum ist proportional zur Länge des Strings.

Als reine Binär-Kodierung ist diese Kodierung nicht für VARCHAR-Felder geeignet. Als kleine Variation könnte man den String uuencoden, aber das ist nur bei n=3 sinnvoll.

Message-ID From In-Reply-To Position ...
<20021021182732.GA6633@minsky.chello.at> "Harald R. Haberstroh" <Harald@XXX.at> NULL
<02102122202400.00672@chuck.teleweb.at> Alexander Hausner <alh@XXX.at> <20021021182732.GA6633@minsky.chello.at> 01
<20021021211728.GA8902@minsky.chello.at> "Harald R. Haberstroh" <Harald@XXX.at> <02102122202400.00672@chuck.teleweb.at> 01 01
<02102221293500.00360@chuck.teleweb.at> Alexander Hausner <alh@XXX.at> <20021021211728.GA8902@minsky.chello.at> 01 01 01
<20021022203911.GA14136@minsky.chello.at> "Harald R. Haberstroh" <Harald@XXX.at> <02102221293500.00360@chuck.teleweb.at> 01 01 01 01
<20021022221211.GC12301@teal.h.hjp.at> "Peter J. Holzer" <hjp-luga@XXX.at> <02102221293500.00360@chuck.teleweb.at> 01 01 01 02
...

4.2. UTF-8 Kodierung

UTF-8[RFC2279] wurde zur Kodierung von Multi-Byte-Character-Sätzen, insbesondere ISO-10646 entwickelt. Es bietet folgende Eigenschaften:

  • Bis zu 48 Bit lange Zahlen können dargestellt werden.
  • Kleinere Zahlen belegen weniger Bytes, insbesondere belegen die Zahlen 0-127 genau ein Byte.
  • Mit Ausnahme der Zahl 0 selbst wird keine Zahl auf eine Bytefolge, die eine 0 enthält, abgebildet.
  • Sortierbarkeit durch byteweises sortieren ist gewährleistet.

Diese Kodierung kann auf vielen, aber nicht allen, Datenbanken in einem VARCHAR-Feld abgelegt werden, allerdings ist die Kodierung und Dekodierung etwas aufwendiger (aber in vielen Programmiersprachen bereits als Library-Funktion vorhanden).

Die Kodierung ist im typischen Fall kompakt (1 Byte pro Ebene), ohne die Zahl der Replies künstlich zu begrenzen.

Probleme können Datenbanken bereiten, die selbst Charset-Konversionen durchführen: In einer Oracle-Datenbank z.B. ist diese Kodierung nur möglich, wenn Client und Datenbank garantiert das gleiche charset verwenden, und wenn möglich sollte dies auf UTF8 sein.

(Die Tabelle sieht hier in diesem einfachen Fall gleich aus wie bei der Biärkodierung)

4.3. ASCII-Kodierung

Die letzte Kodierung, die ich hier vorstellen möchte, ist eigentlich die erste, die mir eingefallen ist - ich habe sie im Oktober 2001 in einem Prototypen für einen Message-Server implementiert. Hier stelle ich aber eine leicht verbesserte Version vor:

Diese Kodierung verwendet nur druckbare ASCII-Zeichen, genauer gesagt nur »/«, Groß- und Kleinbuchstaben. Sie ist daher weniger kompakt, sollte aber mit jeder Datenbank problemlos implementierbar sein.

  • Die leere Folge wird durch einen Slash kodiert.
  • Zahlen werden durch einen Slash getrennt.
  • Jede Zahl wird als Gleitkommazahl in Basis 26 dargestellt, wobei der Exponent in Kleinbuchstaben und die Mantisse in Großbuchstaben kodiert wird. 0 bis 25 werden somit als »A« bis »Z« kodiert, 26 bis 675 als »aAA« ,,, »aAB« ,,. »aZZ«, dann folgen »bAAA«, »cAAAA« bis »zZZZZZZZZZZZZZZZZZZZZZZZZZZZ« was 160059109085386090080713531498405298175 dezimal entspricht und selbst für die verworrendsten Threads ausreichen sollte :-)

Die Sortierung muss roher ASCII-Sortierung entsprechen ("/" vor Großbuchstaben, Großbuchstaben vor Kleinbuchstaben), aber das sollte sich überall erreichen lassen.

Die Kodierung braucht im Normalfall 2 Zeichen pro Ebene. Bei langen Threads und Datenbanken mit kurzen Strings kann das ein Problem werden - nach dem 127sten Reply ist Schluss.

Die Position ist menschenlesbar, die Tiefe im Thread enspricht der Anzahl der Slashes (man kann so z.B. einen Threadbaum in HTML durch ein einfaches Substitute erzeugen).

Message-ID From In-Reply-To Position ...
<20021021182732.GA6633@minsky.chello.at> "Harald R. Haberstroh" <Harald@XXX.at> NULL /
<02102122202400.00672@chuck.teleweb.at> Alexander Hausner <alh@XXX.at> <20021021182732.GA6633@minsky.chello.at> /A/
<20021021211728.GA8902@minsky.chello.at> "Harald R. Haberstroh" <Harald@XXX.at> <02102122202400.00672@chuck.teleweb.at> /A/A/
<02102221293500.00360@chuck.teleweb.at> Alexander Hausner <alh@XXX.at> <20021021211728.GA8902@minsky.chello.at> /A/A/A/
<20021022203911.GA14136@minsky.chello.at> "Harald R. Haberstroh" <Harald@XXX.at> <02102221293500.00360@chuck.teleweb.at> /A/A/A/A/
<20021022221211.GC12301@teal.h.hjp.at> "Peter J. Holzer" <hjp-luga@XXX.at> <02102221293500.00360@chuck.teleweb.at> /A/A/A/B/
...

5. 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
Abstract
Messages und Threads
Verweis auf die Vorgänger-Message
Kodierung der Position im Thread als Folge von Zahlen
Big-Endian Binärzahlen
UTF-8 Kodierung
ASCII-Kodierung
Literatur