Volltextsuche  im Kontext relationaler DBMS Inhaltsverzeichnis  

Inhaltsverzeichnis

1  Einführung  4

1.1  Volltextsuche in relationalen DBMS.  4

1.2  Hauptziele der Arbeit  5

2  Grundkonzepte  6

2.1  Allgemeine Arbeitsweise einer Volltextsuchmaschine  6

2.1.1  Analyse und Indexierung  6

2.1.2  Suchanfragen  7

2.1.3  Ergebnisdarstellung  7

2.2  Volltextsuche im Kontext relationaler Datenbanken am Beispiel von MySQL  

   8

2.2.1  Volltextindizes.  9

2.2.2  Struktur der Volltextindizes  10

2.2.3  Architektur von MySQL.  11

2.2.4  Der Vorgang der Volltextindizierung  17

2.3  Unterscheidung system-interne und system-externe Volltextsuche.  17

2.4  Typische Merkmale der Volltextsuche von MySQL.  21

2.5  Detail-Fragestellung im Zusammenhang dieser Arbeit  21

3  Umsetzung und Implementierung  23

3.1  Ressourcen.  23

3.1.1  Wikipedia DB  23

3.2  Das Experiment-Framework  23

3.2.1  Idee und Anforderungen  23

3.2.2  Systemaufbau und Abhängigkeit  24

3.2.3  Interessante Implementierungsdetails  24

3.3  Detail-Fragestellung im Zusammenhang dieser Arbeit  27

4  Experimente.  29

4.1  Versuchsaufbau.  29

4.1.1  Spezifikationen der verwendeten Laptops  29

4.2  Ergebnisse.  30

4.2.1  Indexierung und Einfügeoperation  30

Volltextsuche  im Kontext relationaler DBMS Inhaltsverzeichnis  

4.2.2  Natural - Search  36

4.2.3  Boolean-Search.  40

5  Zusammenfassende Bewertung und Ausblick  44

5.1  Bewertung der funktionalen Systemmerkmale der MySQL-Komponente  44

5.2  Zusammenfassung und Bewertung der Experimentergebnisse.  46

5.3  Ausblick  47

6  Anhang  49

6.1  Anpassungen und weitere Tools.  49

6.1.1  Einstellungen bei MySQL  49

6.1.2  Anpassung der Wikipedia-Datenbank.  50

6.1.3  Wörterpool  50

6.2  Funktion des Programms.  50

6.2.1  Was macht mein Programm:  50

6.2.2  Weitere Volltextsuche hinzufügen  52

6.2.3  Anpassungsmöglichkeiten der Progammparameter über das GUI:  52

6.2.4  Anpassungsmöglichkeiten über Quellcode:  54

6.2.5  Implementierte Volltextsuchen: MySQL.  55

7  Abbildungsverzeichnis  56

8  Tabellenverzeichnis  56

9  Quellen  57

Volltextsuche im Kontext relationaler DBMS 1. Einführung

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 DBMS: Datenbankmanagementsystem

Rebecca Konrad Seite 4 von 57 19.11.2009

Volltextsuche im Kontext relationaler DBMS 1. Einführung

1.2 Hauptziele der Arbeit

Die Ziele der Arbeit bestehen darin,

a) eine Anwendung zu schreiben, welche es ermöglicht, die

b) die, für die Analyse notwendigen, Resultate der Indexierungs- und

c) die Anwendung so zu programmieren, dass ein späterer

Rebecca Konrad Seite 5 von 57 19.11.2009

Volltextsuche im Kontext relationaler DBMS 2. Grundkonzepte

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:

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

Rebecca Konrad Seite 6 von 57 19.11.2009

Volltextsuche im Kontext relationaler DBMS 2. Grundkonzepte

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 Die Bezeichnungen Volltextindex ist ein Synonym für Inverted-File und ist im Folgenden als

äquivalent anzusehen.

Rebecca Konrad Seite 7 von 57 19.11.2009

Volltextsuche im Kontext relationaler DBMS 2. Grundkonzepte

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 SELECT doknr FROM table WHERE MATCH (spalte1, spalte2,...)

AGAINST (exprString [IN BOOLEAN MODE | WITH QUERY EXPANSION]) ausführen. Anstelle des exprString stehen dann die mit boole’schem OR verknüpften Terme [13]. Ein Beispiel dafür wäre:

SELECT doknr FROM telefonbuchTabelle WHERE MATCH (Vorname,

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

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

4 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

Volltextsuche im Kontext relationaler DBMS 2. Grundkonzepte

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 werden Fehler! 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.

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

wurde.

Rebecca Konrad Seite 9 von 57 19.11.2009

Volltextsuche im Kontext relationaler DBMS 2. Grundkonzepte

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

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

7 Volltextindizes enthalten mehr Informationen als die in der nebenstehenden Tabelle dargestellten.

Die Tabelle dient nur zu Demonstrationszwecken.

Rebecca Konrad Seite 10 von 57 19.11.2009

Volltextsuche im Kontext relationaler DBMS 2. Grundkonzepte

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

Beispiel-Indextabelle

Tabelle 2: Indextabelle erstellt aus Tabelle 1

- Die Keyword-Spalte enthält die einzelnen Tokens, die zum Zeitpunkt der Indizierung extrahiert wurden. Woraus ein Token besteht, wird durch die Wörtertrennung bestimmt.

- Die Spalten-ID entspricht dem Wert, der einer bestimmten volltextindizierten Tabelle und Spalte entspricht.

- Die Dokumenten-Id enthält jeweils den Wert, der einem bestimmten Volltextschlüsselwert in der volltextindizierten Tabelle zugeordnet ist.

- Die Positions-Spalte beinhaltet 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

Rebecca Konrad Seite 11 von 57 19.11.2009

Volltextsuche im Kontext relationaler DBMS 2. Grundkonzepte

sind für die Volltextsuche vor allem die Komponenten der Indexerstellung und der Abfrageverarbeitung von Bedeutung.

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:

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

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

Rebecca Konrad Seite 12 von 57 19.11.2009