Volltextsuche im Kontext relationaler Datenbanken am Beispiel einer systeminternen DBMS- Komponente von MySQL

Inhaltsverzeichnis

1 Einführung
1.1 Volltextsuche in relationalen DBMS
1.2 Hauptziele der Arbeit

2 Grundkonzepte
2.1 Allgemeine Arbeitsweise einer Volltextsuchmaschine
2.1.1 Analyse und Indexierung
2.1.2 Suchanfragen
2.1.3 Ergebnisdarstellung
2.2 Volltextsuche im Kontext relationaler Datenbanken am Beispiel von MySQL
2.2.1 Volltextindizes
2.2.2 Struktur der Volltextindizes
2.2.3 Architektur von MySQL
2.2.4 Der Vorgang der Volltextindizierung
2.3 Unterscheidung system-interne und system-externe Volltextsuche
2.4 Typische Merkmale der Volltextsuche von MySQL
2.5 Detail-Fragestellung im Zusammenhang dieser Arbeit

3 Umsetzung und Implementierung
3.1 Ressourcen
3.1.1 Wikipedia DB
3.2 Das Experiment-Framework
3.2.1 Idee und Anforderungen
3.2.2 Systemaufbau und Abhängigkeit
3.2.3 Interessante Implementierungsdetails
3.3 Detail-Fragestellung im Zusammenhang dieser Arbeit

4 Experimente
4.1 Versuchsaufbau
4.1.1 Spezifikationen der verwendeten Laptops
4.2 Ergebnisse
4.2.1 Indexierung und Einfügeoperation
4.2.2 Natural - Search
4.2.3 Boolean-Search

5 Zusammenfassende Bewertung und Ausblick
5.1 Bewertung der funktionalen Systemmerkmale der MySQL-Komponente
5.2 Zusammenfassung und Bewertung der Experimentergebnisse
5.3 Ausblick

6 Anhang
6.1 Anpassungen und weitere Tools
6.1.1 Einstellungen bei MySQL
6.1.2 Anpassung der Wikipedia-Datenbank
6.1.3 Wörterpool
6.2 Funktion des Programms
6.2.1 Was macht mein Programm:
6.2.2 Weitere Volltextsuche hinzufügen
6.2.3 Anpassungsmöglichkeiten der Progammparameter über das GUI:
6.2.4 Anpassungsmöglichkeiten über Quellcode:
6.2.5 Implementierte Volltextsuchen: MySQL

7 Abbildungsverzeichnis

8 Tabellenverzeichnis

9 Quellen

1 Einführung

1.1 Volltextsuche in relationalen DBMS

Die Volltextsuche, welche Mitte der 70er Jahre aufkam, löste herkömmliche Suchmethoden in vielen Bereichen komplett ab. Denn mit ihr wurde es erstmals möglich, theoretisch jedes Dokument aufzufinden, das nur mindestens ein Wort der Suchanfrage enthält. So ist z.B. eine heutige Internetrecherche ohne das Verfahren der Volltextsuche undenkbar geworden. Für herkömmliche Suchverfahren wäre eine zeitaufwendige, händische Eingabe aller erforderlichen Schlüsselbegriffe, in diesem Fall jedes Wort einer Internetseite bzw. Dokuments, notwendig, um vergleichbare Resultate erzielen zu können. Wobei diese Resultate dann nur unter einem erheblichen Mehraufwand und einer längeren Suchzeit zu erreichen wären. Vergleichsweise hierzu führt die Volltextsuche, durch die Speicherung des aufbereiteten Textes und die Verwendung immer schnelleren Algorithmen, Suchanfragen effektiver und schneller durch.

Die Volltextsuche ist zwar kein klassischer Bestandteil relationaler Datenbanken, jedoch wird diese Funktionalität in heutiger Zeit in immer mehr Produkte integriert, um den Anforderungen des Benutzers gerecht zu werden. Mit dieser Funktionserweiterung der relationalen DBMS¹ können Volltextsuchen direkt auf eine bestehende relationale Datenbank angewandt werden. Auf eine externe Volltextsuchmaschine und eine dadurch möglicherweise notwendig werdende doppelte Datenhaltung für beide DBMS, kann somit verzichtet werden. So bietet die Volltextsuche in relationalen DBMS eine schnelle und flexible Lösung, um linguistische Suchvorgänge zu realisieren.

1.2 Hauptziele der Arbeit

Die Ziele der Arbeit bestehen darin,

a) eine Anwendung zu schreiben, welche es ermöglicht, die Leistungsfähigkeit der Volltextsuchkomponente des relationalen DBMS MySQL zu analysieren.
b) die, für die Analyse notwendigen, Resultate der Indexierungs- und Suchzeit in Abhängigkeit von verschiedenen Parametern, wie z.B. Datenbankgröße und Anzahl der übergebenen Suchwörter, zu ermitteln und auszuwerten.
c) die Anwendung so zu programmieren, dass ein späterer
Performanzvergleich mit weiteren Volltextsuchmaschinen unterstützt wird.

2 Grundkonzepte

2.1 Allgemeine Arbeitsweise einer Volltextsuchmaschine

Die Volltextsuchmaschine führt 3 grundlegende Vorgänge durch, wobei die Datenbasis im Voraus mit den nötigen Rohdaten gefüllt werden muss:

I. Analyse und Indexierung der Daten der Datenbasis,
II. Bearbeitung von Suchanfragen, sowie
III. Repräsentation der Ergebnisse.

Diese Arbeitschritte werde ich im Folgenden kurz erläutern.

2.1.1 Analyse und Indexierung

Alle Wörter, die in der Datenbasis vorkommen, werden in ein so genanntes Inverted-File abgelegt. Ein Inverted-File (invertierte Liste) stellt einen Index dar, der das schnelle Auffinden von Dokumenten ermöglicht, jedoch keine Nutzdaten enthält.

Je nach Suchmaschine werden manche Begriffe, dies sind die so genannten Stoppwörter, nicht in den Index mit aufgenommen. Stoppwörter sind sehr häufig vorkommende Wörter wie z.B. „ein" im Deutschen, denen keine Bedeutung zugemessen wird. Da sie sehr häufig vorkommen, kann mit diesem Vorgehen eine deutliche Verringerung der Indexgröße erreicht werden. Trotzdem verzichten immer mehr Suchmaschinen auf Stoppwörter, weil zum einen die Suchmaschinen immer performanter mit großen Indexen umgehen können und zum anderen für gewisse Anfragen auch Stoppwörter von großer Bedeutung sein können. Beispielsweise enthält der Ausdruck „sein oder nicht sein“ nur Stoppwörtern und würde bei vorhandener Stoppwortliste nicht mit in den Index aufgenommen werden [10].

Da sich das Grundkonzept des Volltextindex² nicht von dem des in MySQL angewandten Volltextindex’ unterscheidet, wird Näheres zum Volltextindex und zu dessen Aufbau erst im Kapitel „Volltextsuche im Kontext relationaler Datenbanken am Beispiel von MySQL“ (2.2.1 und 2.2.2) erläutert.

2.1.2 Suchanfragen

Die Suchmaschine versucht zu den übergebenen Suchbegriffen mittels des Index’ die relevanten Dokumente zu finden. Dazu wird nach Dokumentennummern gesucht, die in den Invertet-Files jedes einzelnen Suchbegriffs, vorkommen. Sind alle passenden Dokumente ermittelt, werden sie gemäß ihrer Relevanz sortiert. Beinhaltet ein Dokument das Suchwort mehrmals, so kommt das seinem Rang innerhalb der Ergebnisliste zugute.

2.1.3 Ergebnisdarstellung

Sind nun die passenden Seiten ermittelt, wird das Ergebnis zurückgeliefert. Dabei ist allen Suchmaschinen gleich, dass die Resultate nach Relevanz sortiert ausgegeben werden. Die Ermittlung der Relevanz und somit des Dokumentenrangs ist jedoch suchmaschinenspezifisch und hängt von dem gewählten Retrieval-Modell ab (siehe Kapitel 2.1.5)

Information Retrieval

Der Begriff Information Retrieval fasst die eben genannten 3 Bereiche einer Volltextsuche (Repräsentation, Speicherung, Organisation und Zugriff zu Information) zusammen [11]. Eines der zentralen Probleme von Information Retrieval Systemen ist die Vorhersage, ob und in welchem Maße ein Dokument relevant ist. Um diese Relevanz zu ermitteln, werden Retrieval-Modelle, wie z.B. das Boole’sches Retrieval-Modell, das Vektormodell oder das Probabilistische Modell angewandt [12].

2.2 Volltextsuche im Kontext relationaler Datenbanken am Beispiel von MySQL

MySQL ist ein relationales Datenbankmanagementsystem, welches als Open-Source-Software für verschiedene Betriebssysteme verfügbar ist und wegen der Performanz hauptsächlich in ANSI C/ANSI C++ implementiert ist [4]Fehler! Verweisquelle konnte nicht gefunden werden..

Seit Version 3 bietet MySQL eine im DBMS integrierte Volltextsuche an, mit welcher ein Volltextindex für eine oder mehrere Spalten einer MyISAM-Tabelle³ angelegt werden kann.

Im Gegensatz zu dem sonst üblichen LIKE-Prädikat⁴, das nur für Zeichenmuster verwendbar ist, bietet die Volltextsuche einen linguistischen Suchvorgang auf die Datenbankeinträge. Grundlage dafür ist, wie bei jeder Volltextsuche, dass der zu indizierende Text analysiert und dementsprechend indexiert wurde.

Die Suche auf einem MySQL–Volltextindex lässt sich allgemein mit

SELECTdoknrFROMtableWHERE MATCH (spalte1,spalte2,...)

AGAINST (exprString[IN BOOLEAN MODE | WITH QUERY EXPANSION]) ausführen. Anstelle desexprStringstehen dann die mit boole’schem OR verknüpften Terme [13].

Ein Beispiel dafür wäre:

SELECTdoknrFROMtelefonbuchTabelleWHERE MATCH (Vorname,Nachname,Ort) AGAINST (‘Hans Heilbronn’IN BOOLEAN MODE)

2.2.1 Volltextindizes

Ein Volltextindex ist ein token-basierter⁵ funktioneller Index (Inverted-File), der sich wesentlich von dem Erstellen anderer Indextypen unterscheidet. Statt einer Baum-Struktur, wird beim Volltextindex eine invertierte, gestapelte, komprimierte Indexstruktur basierend auf einzelnen Token aus dem zu indizierenden Text erstellt.

Der Vorgang der Erstellung und Verwaltung eines Volltextindexes wird als Indexauffüllung bezeichnet, wobei folgende Typen der Volltextindexauffüllung von MySQL unterstützt werdenFehler! Verweisquelle konnte nicht gefunden werden.:

1) Vollständige Auffüllung

Tritt in der Regel beim ersten Auffüllen eines Volltextindexes auf. Anschließend können die Indizes auch durch die beiden weiteren Auffüllungstypen gewartet werden. Wenn die vollständige Auffüllung für eine Tabelle angefordert wird, werden Indexeinträge für alle Zeilen in dieser Tabelle erstellt.

Soll der Volltextindex bei seiner Erstellung nicht aufgefüllt werden, muss dies in der CREATE FULLTEXT INDEX-Anweisung angeben werden. Der Index wird erst aufgefüllt, wenn der Benutzer den ALTER FULLTEXT INDEX-Befehl mit einer der Klauseln START FULL, INCREMENTAL oder UPDATE POPULATION ausführt [13].

2) Auffüllung mit Hilfe von Änderungsnachverfolgung

Intern werden alle Zeilen aufgezeichnet, die in einer Tabelle geändert wurden. Diese Änderungen werden an den Volltextindex weitergegeben und können dann, je nach Einstellung, automatisch oder manuell gestartet werden.

Der Vorteil bei dieser Methode ist, dass die zeitaufwändige und rechenintensive Aktualisierung des Indexes auf einen günstigen Zeitpunkt gelegt werden kann.

3) Inkrementelle, auf Timestamps basierende Auffüllung

Bei der inkrementellen Auffüllung wird der Volltextindex bezüglich der Zeilen, die seit der letzten Auffüllung oder während des letzten Auffüllungsvorgangs hinzugefügt, gelöscht oder geändert wurden, aktualisiert. Voraussetzung für die inkrementelle Auffüllung ist, dass die indizierte Tabelle eine Spalte vom timestamp-Datentyp⁶ aufweist. Ist keine timestamp-Spalte vorhanden, würde eine vollständige Auffüllung durchgeführt werden.

Am Ende einer Auffüllung wird ein neuer timestamp-Wert aufgezeichnet. Dieser Wert entspricht dem größten aufgetretenen timestamp-Wert und wird verwendet, wenn eine nachfolgende inkrementelle Auffüllung gestartet wird.

2.2.2 Struktur der Volltextindizes

Folgendes Beispiel, soll die Struktur eines Volltextindex veranschaulichen [13].

Beispiel-Tabelle⁷

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 1: Benutzer-Tabelle mit Beispieldaten

Wenn für die Titelspalte unter Berücksichtigung der Stoppwörter ein Volltextindex erstellt wird, entsteht (sehr vereinfacht) folgende interne Indextabelle (invertet File):

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2: Indextabelle erstellt aus Tabelle 1

- DieKeyword-Spalte enthält die einzelnen Tokens, die zum Zeitpunkt der Indizierung extrahiert wurden. Woraus ein Token besteht, wird durch die Wörtertrennung bestimmt.
- DieSpalten-IDentspricht dem Wert, der einer bestimmten volltextindizierten Tabelle und Spalte entspricht.
- DieDokumenten-Identhält jeweils den Wert, der einem bestimmten Volltextschlüsselwert in der volltextindizierten Tabelle zugeordnet ist.
- DiePositions-Spaltebeinhaltet den relativen Wortoffset des Tokens innerhalb des Dokuments.

2.2.3 Architektur von MySQL

Damit man die Verarbeitung einer Volltextsuchabfrage nachvollzogen werden kann, werde ich im Folgenden die Architektur von MySQL darstellen. Hierbei sind für die Volltextsuche vor allem die Komponenten der Indexerstellung und der Abfrageverarbeitung von Bedeutung.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Architektur von MySQL [13] mit Veränderungen bei der Umrandung

Auf höchster Abstraktionsebene lässt sich die MySQL Architektur als 3-Schichten-Modell⁸ darstellen:

1. Anwendungsebene(blaue Umrandung)
2. logische Ebene(rote Umrandung)
3. physikalische Ebene(grüne Umrandung)

Jede dieser Ebenen enthält mehrere Komponenten, von denen ich die Wichtigsten in den folgenden Abschnitten kurz beschreiben werde. Hierbei beziehe ich mich auf die Quellen [13] und [20].

1. Anwendungsebene

Über eine Schnittstelle wird der Zugriff von der Anwendungsebene zum MySQL DBMS ermöglichen. Es gibt drei mögliche Benutzergruppen, die auf das MySQL DBMS zugreifen. Dies sind die Administratoren, die Programmierer (clients) und die Endbenutzer (query users).

- DieAdministratorensind für die Erstellung und Wartung der Datenbank zuständig und benutzen hierfür die Programmierschnittstelle und Dienstprogramme, wie z.B. MySQLAdmin, um auf die Struktur der Datenbank zugreifen zu können.
- DerProgrammiererkann mit Hilfe einer Programmiersprache (Php, JDBC und Weitere) über eine Schnittstelle mit der bestehenden Datenbank kommunizieren.
- DerEndanwendergibt seine Anfragen, in der von dem Programmierer vorgegebenen Form an, so dass eine Kommunikation zur Datenbank hergestellt und das Resultat ermittelt werden kann.

2. Logische Ebene

Die logische Ebene lässt sich unterteilen in den

I. Query Prozessor, zu welchem die Komponenten „SQL-Interface“, „Parser“, „Optimizer“ und „Caches / Buffers“ der Abbildung 1 zählen.
II. Connection Pool
III. Recover- und Log-Management(in der Abbildung 1 “Managment Service & Utilities” genannt).
IV. Speichermaschinen(in der Abbildung 1 „Storage Engines“ genannt).

I. Query Prozessor

a) SQL-Interface

Wenn Anfragen vom Client eintreffen, ist es die Aufgabe des DML9-Precompilers die relevanten SQL-Statements zu extrahieren. Anfragen eines Administrators an die MySQL Datenbank, werden von der DDL¹⁰ kompiliert. Dieser Compiler ermöglicht die direkte Kommunikation mit dem MySQL-Server und somit mit der Datenbank.

b) Parser

Nachdem die relevanten SQL Anteile extrahiert wurden, kann die Anfrage geparst werden. Was bedeutet, dass eine Baumstruktur, bestehend aus allen Teilanfragen, erstellt wird.

Diese Baumstruktur kann im Anschluss auf korrekte SQL Syntax und Semantik überprüft werden, so dass nur valide SQL-Anfragen weiterverarbeitet werden.

c) Optimizer

Nach einer Überprüfung, ob der Client dazu berechtigt ist auf die angegebene Datenbank zuzugreifen, kann eine Optimierung der Anfrage durchgeführt werden. Diese Optimierung führt zu einer schnellstmöglichen Ausführung der Anfrage.

Der MySQL-Anfrageoptimierer verwendet, wann immer möglich, Indizes, wobei er den restriktivsten Index jeweils bevorzugt. Denn durch die bevorzugte Verwendung des restriktivsten Index’, können schon zu Beginn und bei jedem weiteren Durchlauf möglichst viele Tupel ausgeschlossen werden, was wiederum zu einer schnelleren Verarbeitung der Anfrage führt.

[...]

---

¹ DBMS: Datenbankmanagementsystem

² Die Bezeichnungen Volltextindex ist ein Synonym für Inverted-File und ist im Folgenden als äquivalent anzusehen.

³ MyISAM (My Indexed Sequential Access Method) ist der Standard-Tabellentyp von MySQL. MyISAM zeichnet sich durch hohe Effizienz im Vergleich zu anderen von MySQL unterstützten Tabellentypen aus und unterstützt eine leistungsfähige Volltextsuche. MyISAM unterstützt allerdings im Unterschied zu z.B. InnoDB keine Transaktionen oder referenzielle Integrität.

⁴ Durch das LIKE-Prädikat kann ein Spaltenwert mit einem „Muster“ verglichen werden. Das LIKE-Prädikat ist TRUE, wenn der Datenwert dem Muster entspricht.

Rebecca Konrad Seite 8 von 57 19.11.2009

⁵ Ein Token ist ein Wort oder eine Zeichenfolge, das bzw. die von der Wörtertrennung identifiziert wurde.

⁶ Ein Zeitstempel (engl.: timestamp) ist ein Wert in einem definierten Format, der einem Ereignis einen Zeitpunkt zuordnet. Der Zweck eines Zeitstempels ist es, für Menschen oder Computer deutlich zu machen, wann welche Ereignisse eintraten.

⁷ Volltextindizes enthalten mehr Informationen als die in der nebenstehenden Tabelle dargestellten. Die Tabelle dient nur zu Demonstrationszwecken.

⁸ Weitere Informationen zum Schichtenmodell unter http://de.wikipedia.org/wiki/Schichtenmodell

⁹ Data Manipulation Language siehe [4].

¹⁰ Data Definition Language siehe [4].