Erster Entwurf des
Retrievalteils des CSLIB-Systems mit
Anfragesprache und Suchmaschine

Von Holger Westphal 
(pumuckel@cs.tu-berlin.de)
11.12.1995

==========================================================================

ICH BITTE ZU ENTSCHULDIGEN:
Dieses Dokument wurde nicht ansprechend formatiert,
  o damit keiner auf die Idee kommt, darin Fehler zu korrigieren:-)
  o damit ich meine Zeit auf die Substanz statt auf die Form verwenden
    kann
  o damit es schneller verbreitet werden konnte.

ICH BITTE ZU BEACHTEN: 
Dieses Dokument enthaelt in keinem Fall explizite oder implizite
Spezifikationen irgendwelcher Schnittstellen, Formate oder
Funktionaliaeten.  Alles ist exemplarisch und ausschliesslich zur
Schaffung einer Verstaendigungsgrundlage gedacht.


CSLIB 2000 Simpel-Formular
==========================
Dieses Formular diene hier als Ausgangspunkt. Es ist nur die Suche nach
Dokumenten moeglich. Die Bedingung ist eingeschraenkt (flache Struktur,
nur auf Kontext des Dokuments bezogen, keine All-Quantifizierung, keine
'tastende', interaktive Suche, ...).  Es stellt einen Kompromiss
zwischen einem Anfrage-Sprache-Editor und einem Formular mit einem
einzigen Eingabe-Feld dar (als welches es allerdings auch verwendet
werden kann).

Das Formular ist grundsaetzlich so konzipiert, dass es mit HTML
realisierbar ist und stellt meinen persoenlichen Vorschlag fuer das
Minimal-Such-Formular des CSLIB 2000 Systems dar.

-------------------------------------------------------------------------------
Suche
  [X] Titel, [X] Produzenten, [X] Klassifikationscodes, [ ] Abstract,
  [ ] Erscheinungsjahr, ...
der Dokumente D aus dem Bestand [X] IFB, [ ] UB, [ ] BVBB, [ ] DBI ...,

wobei

              --------------------         -------------    -------------------
B1:          | ein Wort im Titel  | von D | beginnt mit |  | Programm          |
              ====================         =============    -------------------
      ----    --------------------         -------------    -------------------
B2:  |oder|  | ein Wort im Titel  | von D | matcht      |  | *[Mm]odula*       |
      ====    ====================         =============    -------------------
      ----    --------------------         -------------    -------------------
B3:  |und |  | Nachn eines Autors | von D | aehnlich    |  | Wirt              |
      ====    ====================         =============    -------------------
      ----    --------------------         -------------    -------------------
B4:  |und |  | Erscheinungsjahr   | von D | groesser    |  | 1990              |
      ====    ====================         =============    -------------------
      -----     --------------------
B5:  |nicht| D | ein Kongressband   |
      =====     ====================

und alle Textfelder in <X> CSLIB- < > ISO-8859-1-Kodierung sind,

<X> angeordnet nach Relevanz-Wahrscheinlichkeit entsprechend der
    Relevanz-Beschreibung, dass

             --------------------         -------------    -------------------
R1:         | Erscheinungsjahr   | von D | groesser    |  | 1990              |
             ====================         =============    -------------------
      ----   --------------------         -------------    -------------------
R2:  |und | | Wort im Abstract   | von D | synonym zu  |  | Einf&u:hrung      |,
      ====   ====================         =============    -------------------

< > sortiert

      ------------        ----------------------
S1:  |absteigend  | nach | Erscheinungsjahr     | von D.
      ============        ======================
                                    -----------
Liefere Ergebis bis spaetestens in | 2 Minuten | direkt und danach
                  ----------------- === =======
als [ ] Email an |                     |.
                  ----------- ---------           ----
Brich Suche nach | 5 Minuten | oder bei mehr als | 30 | Dokumenten ganz ab!
                  ===========                     ====
-------------------------------------------------------------------------------

Zeichenerklaerung:

[ ]   =  Toggle-Button, X = (vor)selektiert

< >   =  Radio-Button, X = (vor)selektiert

 --
|  |  =  Option-Menu, (vor)selektierter Item angezeigt
 ==
 --
|  |  =  Text-Input, eingegebener String angezeigt
 --

Bemerkungen:

o Die einzelnen Zeilen fuer die Bedingungen muessen nicht
  alle identisch sein, sondern sollten so angelegt sein, dass nur
  gueltige Kombination der Option-Menues auftreten. Es ist eine
  Voreinstellung zu waehlen, welche als besonderns haeufig angesehen
  wird.
o Damit der Anwender nicht die Syntax der Regulaeren Ausdruecke lernen
  muss, koennen spezielle 'matcht'-Zeilen vorgesehen werden, welche
  folgende Form haben:
               -----------  ---  ---------------  --  -----  -----  -----------
   ... matcht |bel Zeichen||   ||eins d. Zeichen||Mm||genau||odula||bel Zeichen|
               ===========  ---  ===============  --  =====  -----  ===========
  Problem: Platzmangel.

o Je nach implementierten Aehnlichkeitsmassen sollte der Menuepunkt
  'aehnlich' durch 'klingt aehnlich', 'schreibt sich aehnlich' ersetzt
  werden.
o Der Benutzer wird nicht vollkommen im Unklaren darueber gelassen, was
  er als Ergebnis bekommt, da das Formular (als Dokument gesehen) das Ergebnis
  spezifiziert.
o Die flache Struktur der und/oder/nicht-Operatoren ist aus informatischer
  Sicht etwas unbefriedigend. Es sind nicht alle boolschen Funktionen
  formulierbar, der (nicht so ganz ungeuebte) Benutzer 'schwimmt' etwas,
  was die Bindungstaerke der Operatoren angeht. Es ist fraglich, ob
  ein zusaetzliches Feld 'Prioritaet' oder 'Level' hier abhilfe schaffen
  kann oder nur noch mehr zur Verwirrung beitraegt.
o Das Beispiel ist insofern nicht realistisch, als dass zu viele
  Einschraenkungen angegeben sind, was hier allerdings der Demonstration
  eines Teils der Moeglichkeiten dient.
o Es kann gute Guende geben, ergaenzend wesentlich allgemeinere Kategorien
  zuzulassen, als im Beispiel angegeben wurden. Zum Beispiel koennte
  eine Kategorie 'Wort im ...' mit der Bedeutung 'Wort im Titel oder
  im Abstract oder im Namen eines Produzenten' sinnvoll sein, um dem
  Benutzer Entscheidungen zu ersparen.
o Eine 'intelligente' Erweiterung koennte das Vorschalten eines zweiten
  Formulars sein, welches in einem einzigen Eingabefeld die Eingabe einer
  Liste von (durch Leerzeichen getrennten) Strings gestattet, welche dann
  grob syntaktisch analysiert werden (ist es ein Integer, ein regulaerer
  Ausdruck?) und dann automatisch in 'passende' Felder eingetragen werden.
  Ergebnis ist dann ein vorbelegtes Formular (in der Art, wie oben angegeben),
  welches vom Benutzer modifiziert werden kann, falls es nicht der Intention
  entsprach. Die Qualitaet der automatischen Zuordnung kann weiter erhoeht
  werden, indem neben der rein syntaktischen Analyse auch Anfrageergebnisse
  aus der Datenbank hinzugezogen werden (z.B. tritt 'Mueller' nur als
  Nachname einer Person auf, 1990 nur als Erscheinungsjahr, 'C++' nur als
  Wort im Titel oder im Abstract).
o Mehr will ich dazu nicht sagen, weil ich sonst gleich die Oberflaeche
  implementiere.


Parsierung des Formulars
========================
Aufgabe des Oberflaechenprogrammierers ist die Parsierung des ausgefuellten
Formulars. In der Regel nimmt bereits das verwendete GUI einen Teil dieser
Arbeit ab.

Bei entsprechender Benennung der FORM-Elemente fuer das obige Beispiel
koennte man in etwa die folgende Datenstruktur (abstrakte Syntax) erhalten
(welche in ihrer Art nicht so weit von einer Belegung entsprechend dem
CGI-Interface eines WWW-Servers entfernt ist).

resultBaseClass = dokument			% implizit
environment.ifb = true
environment.ub = false
environment.bvbb = false
environment.dbi = false
resultIncludes.dokTitel = true
resultIncludes.dokProduzenten = true
resultIncludes.dokKlassifikationsCodes = true
resultIncludes.dokAbstract = false
resultIncludes.dokErscheinungsjahr = false
resultIncludes.dokId = true     		% implizit
condition[1].property = einWortImDokTitel
condition[1].predicate = beginntMit
condition[1].value = Program
operator[1][2] = or
condition[2].property = einWortImDokTitel
condition[2].predicate = regExMatch
condition[2].value = *[Mm]odula*
operator[2][3] = and
condition[3].property = nachnameEinesDokAutors
condition[3].predicate = soundexSimilar
condition[3].value = Wirt
operator[3][4] = and
condition[4].property = dokErscheinungsjahr
condition[4].predicate = greater
condition[4].value = 1990
operator[4][5] = andNot
condition[5].property = dokEinKongressband
textInEncoding = cslibEncoding
textOutEncoding = iso-8859-1-Encoding		% implizit
orderSpecification = ranking
relevance[1].property = dokErscheinungsjahr
relevance[1].predicate = greater
relevance[1].value = 1990
relevanceOperator[1][2] = and
relevance[2].property = einWortImDokAbstract
relevance[2].predicate = synonym
relevance[2].value = Einf&u:rung
sort[1].predicate = smaller
sort[1].function = dokErscheinungsjahr
directReplySecondsLimit = 120
emailReply = false
emailAddress =
overallSecondsLimit = 300
replyCountLimit = 30

Es ist offensichtlich, dass diese einfache Vorgehensweise nicht zur
Abbildung von geschachtelten Ausdruecken geeignet ist. Schwerwiegender
ist der Mangel, dass die Bindung der und/oder/nicht-Operatoren weder
klar noch beeinflussbar ist.
Ein Problem stellen auch Relationen zwischen Objekten dar (im Gegensatz zu
Relationen zwischen einem Dokument und einem Wert), da Objekte mitunter
selbst erst durch eine (komplexe) Anfrage identifiziert werden muessen (z.B.
Verweisrelation zwischen Dokumenten oder einem Dokument und einem Kongress).


Semantik der Anfrage
====================
Ist zwar die Uebereinstimmung bezueglich der Semantik der formulierten
Anfrage zwischen ungeuebtem Benutzer und Oberflaechenprogrammierer
durch die natuerlichsprachliche Spezifikation des Anfrageergebnisses
im Formular (trotz der diskutierten Maengel) bereits ausreichend,
sollte sie zwischen Oberflaechenprogrammierer und Programmierer der
Suchmaschine praezisiert werden, um Missverstaendnisse auszuschliessen.
Insbesondere sollte davon ausgegangen werden koennen, dass der Programmierer
der Suchmaschine das Formular gar nicht zu kennen braucht.

Die Aufgabe des Oberflaechenprogrammierers besteht also weiter darin,
gegenueber der Suchmaschine klar auszudruecken, welches Ergebnis sie nun
genau berechnen soll. Damit besteht die Aufgabe letztendlich darin, dem
ausgefuellten Formular ueber das Ergebnis seiner Parsierung (siehe oben)
eine Semantik zuzuordnen. Diese Semantik umfasst allerdings mindestens
zwei Teile: (1) den Aufbau des Ergebnisdokuments betreffend (2) den
Auftrag an die Suchmaschine betreffend. Wie (1) geloest wird, interessiert
die Suchmaschine ueberhaupt nicht (und soll es auch nicht).
Bei der Loesung von (2) kann die Semantik (2a) basierend auf der Syntax des
geparsten Formulars natuerlichsprachlich zwischen Oberflaechenprogrammierer
und Programmierer der Suchmaschine erfolgen (2b) mithilfe einer auf die
Suchmaschine ausgerichteten Meta-Sprache (hier die Anfragesprache).

Loesung (2a) wuerde die Implementierung einer allgemeinen Suchmaschine
behindern und laesst Probleme mit sich aendernen Schnittstellen erwarten.
Loesung (2b) wuerde eine Zwischenuebersetzung in die
Meta-Sprache erfordern, welche vom Oberflaechenprogrammierer zu leisten
waere, da die Suchmachine von einer Oberflaeche unabhaengig bleiben
soll und eben die Meta-Sprache zur Kommunikation zwischen Suchmaschine
und Oberflaeche dient.

Eine Interpretation der Formular-Syntax koennte in der (erst ansatzweise
spezifizierten) Anfragesprache wie folgt ausgedrueckt werden:

import 'CSLIB.IFB-Bestand'.
ranklist of (titel:	dokTitelIso8859_1(D),
             prods:	dokProduzentenNamenListeIso8859_1(D),
             codes:	dokUBKlassifikationsCodesIso8859_1(D),
             id:	dokId(D),
             dokument:	D)
  where	D in dokument,
	(TW in woerterImDokTitel(D), TW in regExAbleitungen(`'Programm*');
	 TW in woerterImDokTitel(D), TW in regExAbleitungen(`'*[Mm]odula*')),
	A in dokAutoren(D), personNachname(A) in soundexSimilarStrings(`'Wirt'),
	dokErscheinungsjahr(D) > 1990,
	not D in kongressband
  ranked by
	X @ dokErscheinungsjahr(dokument(X)) >~ 1990,
	    AW in~ woerterImDokAbstract(dokument(X)),
	    AW in~ wortSynonyme(`'Einf&u:hrung').

Bemerkungen:
o Um jetzt nicht in die Spezifikation der Anfragesprache verfallen zu
  muessen, empfehle ich, die Anfrage mit dem Suchformular (oben) und dem
  Ergebnis (unten) zu vergleichen, um die Semantik intuitiv zu verstehen.
o Man beachte, dass die Operatoren aus dem Formular als Anwendung von links
  nach rechts (von oben nach unten) interpretiert wurden und (entprechend
  der Definition der Anfragesprache) ueberfluessige Klammern entfernt wurden.
  Das Oder wird durch den ';'-Operator ausgedrueckt.
o Zur Darstellung von Mengen- und Zeitlimitierungen sind zur Zeit
  keine Konzepte vorgesehen.
o Zur Implementierung der 'ranked by'-Klausel fehlt bis jetzt noch
  die Wahl einer entsprechenden Theorie (Fuzzy-Retrieval oder
  probabilistisches Retrieval) und selbst bei Wahl der Theorie noch
  die komplette Implementierung einschliesslich Gewinnung der notwendigen
  Daten. Aus diesem Grund wird die Realisierbarkeit innerhalb des
  Projekts eher pessimistisch bewertet.
o Die Semantik der in der Anfrage verwendeten (komplexen) Funktionen wird
  Teil der Dokumentation der Anfragesprache sein muessen. Im allgemeinen
  wird sich die Semantik aus den die Funktion definierenden Regeln ergeben,
  sodass nur die Definition und die Semantik der primitiven Funktionen
  bekanntgegeben werden braucht. Die Entwickler der Anfragesprache/Suchmaschine
  werden sich anfangs auf die Implementierung jener Funktionen beschraenken,
  welche zum Betrieb eines (zu spezifizierenden) Minimal-Suchformulars
  unbedingt notwendig sind.
o Die Anfragesprache und damit auch das Interface zur Suchmaschine
  sollte stets abwaertskompatibel sein. Dies laesst sich solange einfach
  erreichen, wie die Erweiterung der Anfragesprache nur ueber die
  Implementierung neuer Funktionen erfolgt, aber diese ansonsten keine
  grundlegenden Aenderungen erfaehrt (d.h. z.B. nicht zu verbergende
  Aenderungen des Datenmodells, Aenderungen am Typsystem, Konstrukte mit
  spezieller Semantik).
o In der Beispielanfrage ist erkennbar, dass Funktionen mit sehr langen
  Namen verwendet wurden. Dies soll den in den beiden vorstehenden Punkten
  diskutierten Zielen dienen. Auf diese Weise kann man sich auf die
  Implementierung der unbedingt notwendigen Funktionen konzentrieren
  und braucht die interne Realisierung nicht nach aussen zu tragen.
  Spaeter kann man dann immer noch primitivere Funktionen exportieren,
  aus denen sich der Anwender selbst komplexere Funktionen zusammenstellen
  kann. Die Einbeziehung von Typinformationen in die Funktionsnamen entbindet
  auch vorlaeufig von der effizienten Implementierung einer auf Typinferenz
  beruhenden statischen Bindung. Ausserdem hat dies den Vorteil, dass die
  Semantik der Funktionsaufrufe ohne eine Analyse des Kontextes ermittelbar
  ist.
o In der Beispielanfrage wurden die zuvor diskutierten Strategien nicht
  konsequent umgesetzt. Die Konjunktion in der zweiten Zeile der where-Klausel
  koennte durch folgendes (syntaktisch gueltiges) Praedikat ersetzt werden:

  D in 'Dokumente mit Wort im Titel, das eine RegEx Ableitung von'(`'Programm*')

  Die (interne) Definition der komplexen Funktion waere dann durch die
  zweite Zeile der Beispielanfrage gegeben oder kann auch gleich durch noch
  primitivere Funktionen ausgedrueckt werden.
  Auf diese Weise waere die Uebersetzung der abstrakten Formularsyntax in
  die Anfrage nicht besonders schwierig und die Uebersetzung der Anfrage
  in die Primitiven der Suchmaschine koennte speziell optimiert werden.
o Ich hoffe, es ist deutlich geworden ist, dass die Anfragesprache das Problem
  der Bedienung eines WWW-Formulars bei geeigneter Definition von
  Funktionen als Spezialfall enthaelt und keine andere Syntax als die
  der Anfragesprache fuer die Kommunikation zwischen Oberflaeche und
  Suchmaschine notwendig ist. Die Entwickler der Anfragesprache
  und Suchmaschine koennen relativ schnell die anwendungsbezogene
  Einsetzbarkeit der Schnittstelle zwischen WWW-Formular und Suchmaschine
  angehen, ohne die parallele Entwicklung einer komplexeren und
  abwaertskompatiblen Anfragesprache langfristig aufgeben zu muessen.


Ergebnis der Anfrage
====================
Das Ergebnis der Anfrage kann folgendermassen repraesentiert werden:

(status: 'ok',
 type: list( tuple( relevance: float,
		    data: tuple( titel: iso8859_1EncodedString,
		  		 prods: list( iso8859_1EncodedString ),
				 codes: set( iso8859_1EncodedString ),
				 id: int,
				 dokument: objectReference))),
 value:
  [(0.34,
    ('Programmieren in Modula 2', ['Niklaus Wirth'], {'53q444','53u345'}, 4711,
     `dokument(4711))),
   (0.29,
    ('Programming in Modula 2', ['Niklaus Wirth'], {'53q444','53u345'}, 4713,
     `dokument(4713))),
   ...
  ]
)

Bemerkungen:
o Die Repraesentation des Anfrageergebnisses als komplexer 'Wert',
  ueberwindet den viel zitierten 'Impedance Mismatch', der im Zusammenhang
  der Kopplung zwischen einer Programmiersprache und einem Datenbanksystem
  auftritt. Aus der Sicht des Anwendungsprogrammierers ist die Anfrage
  ein Funktionsaufruf mit einem komplexen Argument (Anfrage), der einen
  komplexen Wert (Anfrageergebnis) liefert, auf dem mit den gewohnten
  Methoden weitergearbeitet werden kann.
o Es macht deshalb sehr viel Sinn,
  die Typsysteme von Programmiersprache und Anfragesprache direkt
  zu koppeln (d.h. zu jedem Typ der Anfragesprache gibt es einem
  Typ in der Programmiersprache, auch wenn beide Systeme nicht auf der
  selben Sprache basieren oder auf unterschiedlichen Rechnern laufen).
  Es ist dann moeglich, die Konvertierung und Konstruktion der Datenstruktur
  zu automatisieren, sodass der Programmierer nichts mehr davon merkt.
  Fuer jedes Paar von Programmiersystemen ist dies nur einmal zu
  implementieren (Hinweise: Remote Procedures, Dual Compilation,
  Proxy-Implementierung in der Objective C Library).
o Der Aufbau der das Anfrageergebnis praesentierenden Oberflaeche erfolgt
  durch Anwendung iterativer oder rekursiver Prozeduren auf das
  Anfrageergebnis (z.B. einer erzeugenden, attributierten Grammatik).
o Wird das Ergebnis als Hypertext praesentiert, waere es interessant,
  verschiedene Daten mit Hyperlinks zu versehen (z.B. vom Autornamen zu
  einer Seite, welche weitere Angaben ueber den Autor enthaelt oder
  vom Klassifikationscode zu einer Seite, welche dessen Beschreibung
  und Stellung in der Systematik enthaelt.) Fuer diesen Fall
  muessen zusaetzlich Objekt-Referenzen in das Ergebnis aufgenommen werden,
  auf welche sich nachfolgende Anfragen beziehen koennen.
  (Verlockend waere die Moeglichkeit, solche Hypertexte automatisch
  aus dem Schema bzw. aus dem Typ eines Anfrageergebnisses erzeugen zu
  koennen.)
  Sinnvoller als diese statische 'Erweiterung der Anfrage durch navigierenden
  Zugriff' waere vermutlich, wie bereits von der WWW-Gruppe vorgestellt,
  es dem Benutzer zu ermoeglichen, aus Komponenten des Anfrageergebnisses
  neue Anfragen bilden zu koennen.
o Das Konzept der Objekt-Referenzen (OID's) ist noch Gegenstand der
  Entwicklung. Grundsaetzlich ist jedoch von einem Wert-basierten
  (value based) Anfrageergebnis auszughen, da es mehrfache Interaktionen
  mit der Suchmaschine erspart. Der Preis ist allerdings u.U. die
  Notwendigkeit, relativ umfangreiche Ergebniswerte zwischenspeichern
  zu muessen. Als Ergaenzung dazu besteht prinzipiell die Moeglichkeit,
  Anfragen selbst als Ergebniswerte zuzulassen. In diesem Fall wuerde
  man z.B. statt einer Menge von Werten eine Anfrage erhalten, welche
  (der Suchmaschine zur Auswertung uebergeben) dann diese Menge von Werten
  ergeben wuerde. Dies kann dann von Vorteil sein, wenn der Benutzer
  selbst entscheiden kann (indem er z.B. Hyperlinks verfolgt), welche
  Teile des Ergebnisses ihn im Detail weiter interessieren.
  In wieweit diese beiden Konzepte (OID's und Anfragen als Werte)
  zusammenfallen, ist mir theoretisch noch nicht ganz klar.
  Jedoch treten in diesem Zusammenhang viele neue Probleme auf: Konsistenz,
  Transaktionen, Lebensdauer von Objekten, Garbage Collection.


Aufbau der Suchmaschine
=======================
Fuer mich gibt es genau eine Suchmaschine! Input: Anfrage, Output: Ergebnis.

Es macht deshalb wenig Sinn, Suchmaschine und Anfragesprache
voneinander zu trennen. Die Anfragesprache ist Teil der Schnittstelle
der Suchmaschine 'nach oben'. Das eigentlich 'Maschinelle' an der
Suchmaschine ist die Menge ihrer Primitiven bzw. ihr Laufzeitsystem.
Die Primitiven der Suchmaschine bilden ihre Schnittstelle 'nach
unten', und dass bedeutet hier zur Datenbank und zu verschiedenen
Algorithmen und Prozeduren, welche Datenobjekte Selektieren, Indexieren,
Konvertieren, Zerlegen, Zusammensetzen, Vergleichen usw.

Zwischen diesen beiden Schnittstellen der Suchmaschine befindet sich
der Compiler der Anfragesprache. Er kann weder isoliert von der
Schnittstelle 'nach oben' noch von der Schnittstelle 'nach unten'
betrachtet werden. Aufgabe des Compilers ist es, an der Schnittstelle
'nach oben' von der Schnittstelle 'nach unten' abstrahieren zu koennen.
Ist die Anfragesprache weitgehend deklarativ (oder logisch semantisch),
abstrahiert man hier gleichzeitig von dem WIE, indem man nur das
WAS spezifiziert. Letzteres effizient und korrekt umzusetzen ist
letztendlich die eigentliche Herausforderung bei der Entwicklung
des Compilers (und bildet gleichzeitig das zentrale Risiko).

Ergebnis der Compilation einer Anfrage ist ein Programm (oder ein
algebraischer Ausdruck) (moeglichst in einer direkt interpretierbaren
oder ausfuehrbaren Form), welches unter ausschliesslichem Rueckgriff auf
die Primitiven der Suchmaschine und auf einige wenige Kontrollstrukturen
(Fallunterscheidung, Schleifen, Backtracking, Rekursion) und primitive
Konzepte (Applikation, Variablenbindung) das Ergebnis berechnet.
Die Sprache, in welcher das Programm abgefasst ist, sollte die 
Maechtigkeit einer Turingmaschinen besitzen.

Das Erreichen dieses Ziels ist besonders einfach, wenn diese Zielsprache
gleich der Sprache ist, in der der Compiler geschrieben ist und fuer diese
Sprache ein Interpreter (wahlweise mit schnellem Compiler) existiert und
kein Unterschied zwischen den Datenobjekten dieser Sprache und der
(internen) Repraesentation von Programmen in dieser Sprache besteht.
Leider erfuellen nicht viele Sprachen diese Eigenschaften (z.B. PROLOG, LISP).
Ansonsten ist naemlich zusaetzlich ein Interpreter fuer diese
Sprache vorzusehen, welcher eine Datenstruktur in der Sprache, in welcher der
Compiler geschrieben ist, interpretiert. (Compilation auf Maschinensprache
verbieten meistens Effizienzgruende, wenn das Programm nur einmal
ausgefuehrt wird, was bei Ad-Hoc-Anfragen aber gerade der Normalfall ist.
Deshalb sind Sprachen, die auf abstrakten Maschinen basieren, zumindest
fuer einen Prototyp, vorzuziehen.)

Alternativ koennte man auch das Programm, welches das Anfrageergebnis
berechnet, als die Suchmaschine bezeichnen (eine hochspezialisierte Maschine,
welche nur zum Zweck der Erfuellung eines einzigen Informationswunschen
konstruiert wurde). In diesem Fall waere dann der Compiler ein
Suchmaschinen-Generator und das Gesamtsystem eine Suchmaschinen-Farm
(die Suchmaschinen erzeugt, versorgt, ausbeutet und terminiert:-).


Primitiven der Suchmaschine
===========================
Um die allgemeine Betrachtung aus dem vorhergehenden Abschnitt zu
konkretisieren, nenne ich jetzt die aus meiner Sicht wichtigsten
Primitiven der Suchmaschine fuer das CSLIB-System, um deren Implementierung
wir nicht herumkommen werden.

SQL-Anbindung
-------------
Moeglichkeit der Absetzung dynamisch generierter SQL-Kommandos an die
Informix-Datenbank und Konvertierung der Ergebnisse in Datenstrukturen
der Implementierungssprache. Aus Effizienzgruenden sollte eine
Deskriptor-Verwaltung existieren, um parametrisierte SQL-Kommandos
mehrfach mit unterschiedlichen Argumenten aufrufen zu koennen.
(Wahlweise koennte auch auf Datenbankprozeduren zurueckgegriffen werden,
was aber fuer Prozeduren, die zur Beantwortung einer Anfrage zwar
mehrfach, danach aber nie wieder benoetigt werden, unguenstig erscheint.)
Man beachte, dass die Moeglichkeit von dynamischen SQL-Kommandos den
Fall von Kommandos, die bereits vor der Kompilation feststehen, umfasst.
(Auch wenn hier nun Datenbankprozeduren wieder besser geeignet waeren;
ihre Verwendung aber nicht ausgeschlossen wird.)

Wichtig bei der Schnittstelle ist, dass sie die Typen der Parameter
bekommt und auswerten kann, da diese Typen, im Gegensatz zum
Ergebnistyp, nicht vom Datenbanksystem ermittelt werden koennen!
(Eigentlich ein schlimmer Bug. Siehe Implementierung von isqlperl.)

Zu beruecksichtigen ist, dass mehrere Cursor gleichzeitig geoeffnet
sein duerfen (d.h. geschachtelte SQL-Aufrufe moeglich sind).

Vorschlag fuer die Schnittstelle (in PROLOG):
  informix_sql_select(
             <Id>,
		% Wiederverwendung des Statement-Deskriptors ist so einfacher
             <Liste zu bindender Variablen>,
		% korrespondiert zu Audruecken in SELECT-Klausel
             <Liste der Prolog-Typen der zu bindenden Variablen>,
		% korrespondiert zu Audruecken in SELECT-Klausel
             <Liste der gebundenen SQL-Variablen>,
		% korrespondiert zu Reihenfolge der SQL-Variablen
             <Liste der SQL-Typen der gebundenen SQL-Variablen>,
		% korrespondiert zu Reihenfolge der SQL-Variablen
             <Liste der gebundenen Text-Variablen>,
		% Modifikationen des Kommandos, die nicht per SQL-Variablen
		% moeglich sind (Rettungsanker)
             <Textuelle Form des SQL-Kommandos>
		% kann Text-Variablen enthalten, ansonsten SQL-Syntax).
  Beispiel der Anwendung:

    % Code ist UB-Klassifikationscode zu Dokument mit DokId.
    % DokId muss gebunden sein, Code darf nicht? gebunden sein.
    % Mehrfach erfuellbar.
    dokIdUBcode_bf(+DokId,-Code) :-
      sql_select(dokIdIFBcode_bf_1,[Code],[atom],[DokId],[int],[],
                 ['select a1.code',
                  ' from dm_klassifikation a1, dok_klassifikation a2',
                  ' where a2.dokument = ? and',
                  '       a1.klassifikation = a2.klassifikation']).

    % Ermittle Liste aller Klassifikationscodes fuer das Dokument mit Id 4711
    ?-findall(Code, dokIdUBcode_bf(4711,Code),CodeListe), write(CodeListe), nl.

Probleme: Freigabe der an die Id gebundenen Deskriptoren und Cursor,
Fehlerbehandlung.

SQL-Schnittstelle fuer jedes weitere Datenbanksystem, welches unterstuetzt
werden soll (z.B. Postgres).

Umlaut-Konvertierung
--------------------
Seien alle Textdaten in der Datenbank im Zeichensatz 'cslibEncoding' kodiert.
Fuer jeden externen Zeichensatz ist eine Konvertierungsfunktion von und
nach 'cslibEncoding' vorzusehen.

Vorschlag fuer die Schnittstelle einer generischen Konvertierungsfunktion
(PROLOG):

 % String Dest ist die bestmoegliche Umkodierung von String Source im
 % Kodierungssystem SourceEncoding nach DestEncoding.
 translateEncoding(+SourceEncoding,+DestEncoding,+Source,-Dest) :-
   % ... Implementierung in C

 % Wandle einen String aus der Datenbank nach Latin-1
 ?-translateEncoding(cslibEncoding,iso8859_1_Encoding,
     "Gr&u:&sse von Herrn Amp&e!re", S), write(S), nl.
 
Neben den rein darstellungsbezogenen Konvertierungen sind vermutlich auch
solche fuer Zwecke der Sortierung notwendig.

 ?-translateEncoding(cslibEncoding, 'RAKsortierwert', "Gr&u:&sse", "Gruesse").
 yes.

Sortierung
----------
Wir gehen zunaechst davon aus, dass Anfrageergebnisse nur klein sind und
sortieren im Speicher. Es gibt (zumindest in SWI-Prolog) ein
Key-Sort-Praedikat, welches Nested-Multi-Level-Sorting nach einem
Schluessel gestattet. Um das Praedikat direkt nutzen zu koennen, muesste
zuerst der 'Sortier-Schluessel' fuer jeden Wert aus der Menge der zu
sortierenden Werte berechnet werden. (Problem: Das Sortier-Praedikat
scheint nicht waehlbar zu sein.)

?-keysort([(1,c)-v1c,(2,a)-v2a,(1,b)-v1b],
          [(1,b)-v1b,(1,c)-v1c,(2,a)-v2a]).
yes.

Erweiterung der regulaeren Ausdruecke der Datenbank, Textretrieval
------------------------------------------------------------------
Die regulaeren Ausdruecke von Informix sind beschraenkt.
Will man diese erweitern, ist es ratsam, wenigstens jene Teilausdruecke,
welche die Datenbank unterstuetzt, direkt in die SQL-Kommandos
einzubauen und den 'Rest' im Speicher zu testen.

Dazu benoetigen wir ein Praedikat, welches diesen Test im Speicher
ausfuehrt:

% String S matcht den regulaeren Ausdruck RegEx. S muss gebunden sein,
% d.h. es werden nicht alle (moeglicherweise beliebig viele) Ableitungen
% ermittelt. Das Praedikat verwaltet eine (kleine) Menge von vorkompilierten
% Ausdruecken, d.h. es versucht zuerst immer eine kompilierte Version von
% RegEx zu finden, bevor es den Ausdruck kompiliert.
  regExMatch(+RegEx,+S) :-
    % ... Rueckgriff auf (C-)Bibliothek

?-regExMatch("[Mm]odula.*","Modula 2").
yes.

Die Zerlegung der regulaeren Ausdruecke gehoert zum Compiler und nicht
zu den Primitiven, da sie zu komplexen Bedingungen fuehren kann.
Beispiel einer Zerlegung:

S in regExAbleitungen(`'[D]aten(bank|autobahn)(en)?') <<=
  (sqlInformixMatches(S,"[D]atenbank*");
   sqlInformixMatches(S,"[D]atenautobahn*")),
  regExMatch(".*(en)?",S).

Man beachte die unterschiedliche Semantik des '*'-Operators (einmal
als Muster, einmal als Quantor).
Die Transformation ist nur anzuwenden, wenn S an den Wert eines
Attributs einer Informix-Tabelle gebunden ist.

Am einfachsten waere es natuerlich, zunaechst nur Informix-Ausdruecke
zuzulassen, also die fuer den maechtigeren, aber nicht? ANSI-konformen
'Matches'-Operator (aber bitte irgendwie aufwaertskompatibel!).

Die Einfuehrung hoeherer Konzepte (z.B. Wortmasken) halte ich vorlaeufig
fuer nicht so essentiell. Auch die Verfeinerung bzgl. Zeichenmasken
werden vermutlich nur wenige benutzen. Eine spezielle Syntax fuer
regulaere Ausdruecke (wie in IQL-T) halte ich zwar fuer etwas 'sperrig'
(siehe auch Bemerkungen zum Formular oben), waere aber in Hinblick auf
spaetere Erweiterungen vielleicht sinnvoll. (Ich werde mir was einfallen
lassen, was in die Richtung geht: Eine Zeichnenmaske ist eine
Konkatenation von string-wertigen Ausdruecken.)

Falls wir tatsaechlich Volltexte haben sollten, laesst sich einiges
ueber (zu standardisierende) Trennzeichen fuer Absaetze
usw. realisieren. Die Moeglichkeit der Adressierung von groesseren
Texteinheiten erwarte ich fuer das Projekt eh nicht mehr (Namen, Titel,
komplette Abstracts werden das einzige sein; zur Gliederung von
Dokumenten wuerde sich eine Instanz von SGML anbieten, was einigermassen
zukunftssicher waere.)


Beispiel einer Uebersetzung
===========================
Um der Suchmaschine (bzw. der Suchmaschinen-Farm) etwas von Ihrer
Mysthik zu nehmen, hier ein Beispiel fuer das Ergebnis einer Uebersetzung.
Jene Leser, welche PROLOG kennen, sind hier wieder etwas im Vorteil.

Folgende Direktive bewirkt die Ausgabe des Ergebnisses der Anfrage,
welches intern als 'result1' identifiziert wird, auf einem Stream, der mit
einem Perl-Prozess verbunden ist.

Die Anfrage bedeutet:
  Menge der Titel, Ids und Klassifikationscodes der Dokumente, deren Titel
  'Modula' oder 'modula' enthalten.

?-doQuery(result1,(
    setof of (titel:	dokTitelIso8859_1(D),
              codes:	dokUBKlassifikationsCodesIso8859_1(D),
              id:	dokId(D))
      where D in dokument,
  	    dokTitelText(D) in regExAbleitungen(`'*[Mm]odula*')),
    perlStream).

Hierzu werden folgende Praedikate als definiert vorausgesetzt:

doQuery(+Id,+Query,+Stream) :-
  compileQuery(Id,Query,Duplicates,ResultType),
  writeResult(Id,Stream,Duplicates,ResultType),
  cleanUpResult(Id).

writeResult(+Id,+Stream,+noDuplicateEliminationNeeded,+set(T)) :-
  findall(Tuple,apply(Id,[Tuple]),Result), % laesst sich noch optimieren, da
  writeResultAsSet(Stream,set(T),Result).  % keine Duplikate

compileQuery(+Id,+Query,-Duplicates,-ResultType) :-
  % ... magic, magic

compileQuery erzeugt folgendes Programm (Uebersetzung der Anfrage), welches
auf die Primitiven der Suchmaschine zurueckgreift.

result1((Titel,Codes,DokId)) :-
  sql_select(result1_1,[Ti,DokId],[string,int],[],[],[],
             ['select ti.text, dok.id',
              ' from dok_titel ti, dok_dokument dok,',
              ' where ti.dokument = dok.dokument and',
              '       ti.text matches "*[Mm]odula*"']),
  translateEncoding(cslibEncoding,iso8859_1_Encoding,Ti,Titel),
  findall(C,dokUBKlassifikationsCodesIso8859_1_bf(DokId,C),Codes).

Folgende Praedikate werden vom Compiler als anwendungsabhaengige
Primitiven betrachtet (d.h. sie sind atomar und koennen nicht weiter
optimiert werden).

dokUBKlassifikationsCodesIso8859_1_bf(+DokId,-Code) :-
  dokIdUbcode_bf(Id,Co), 	% bereits oben definiert
  translateEncoding(cslibEncoding,iso8859_1_Encoding,Co,Code).


Semantik der Datenbank, Datenbestand und Indexe
===============================================
Die Datenbank ist sozusagen das Futterreservoir fuer die Suchmaschine:-).

Ich gehoere zwar zu den wenigen Gluecklichen, die an der Entwicklung des
Datenmodells beteiligt waren, kann aber zum Datenbestand z.Z. relativ
wenig sagen. Dies liegt daran, dass ich an der Implementierung des
Datenmodells und an der Erfassung bzw. Konvertierung von Daten
nicht unmittelbar beteiligt bin. Ich weiss jedoch, dass verschiedene
Probleme in diesem Zusammenhang aufgetreten sind:

  o Die Qualitaet (Kodierung, Feldtrennung) der verfuegbaren Daten
    (insbesondere Fakyr) bleibt weit hinter den Moeglichkeiten des
    Datenmodells zurueck.
  o Qualitativ hochwertige Daten, welche dem Modell einigermassen
    gerecht werden, sind (auch aufgrund fehlender Erfassungshilfsmittel)
    rar und werden vermutlich auch rar bleiben.

Grundsaetzlich sind wir also mit dem Problem von Daten unterschiedlicher
Guete konfrontiert. Aus der Sicht einer Retrieval-Komponente ist das
natuerlich der blanke Horror. Prinzipiell kann dies naemlich nur heissen,
dass sich das Retrievalmodell am schwaechsten Glied zu orientieren hat,
wenn es homogen sein soll. Wuerde ein heterogenes Retrieval-Modell
realisiert, wird die Akzeptanz des Benutzers gegen Null gehen.

Ich sehe folgende Loesungsmoeglichkeiten:
  1. Ermittlung und Implementierung des maximalen, minimalen Retrieval-Modells
     (d.h. Attribute, die nicht alle Dokumente haben, oder bei denen die
      Semantik stark variiert, sind nicht anfragbar). Auf die
     Diskussion von Nullwerten will ich hier verzichten.
  2. Halbautomatische, intelligente und intellektuelle (manuelle) Erhoehung
     der Qualitaet der 'schwachen' Daten und dann weiter bei 1,3 oder 4.
     (Wie ist Ulrike bei den Daten fuer das 'Donald'-Formular vorgegangen?)
  3. Entwicklung verschiedener Retrieval-Teilmodelle, die den
     jeweils umfassenden Datenbestand mit steigenden Anforderungen immer
     kleiner werden lassen (fuer den Benutzer aeusserst entmutigend).
  4. Aufgabe des Ziels, den IFB-Bestand aufgrund der Fakyrdaten
     zu integrieren und Entwicklung eines maximalen Retrieval-Modells
     auf dem maximalen Datenmodell aber leider vergleichweise winzigem 
     (und/oder noch auszubauendem) Datenbestand. Ziel ist es also, ein
     'leeres' System abzuliefern, welches dann einem Anwender uebergeben
     wird.
  5. Aufgabe des Ziels der Implementierung eines Prototypen
     und Produktion von Papier, welches den Prototypen beschreibt.
  6. Indexierung der Fakyr-Daten mit free-WAIS-sf, WWW-Interface
     sf-gate, fertig!.

Wir werden uns fuer eine der durch diese Wege skizzierten Grundrichtungen
entscheiden muessen, da wir uns sonst 'verzetteln'.

Ich weiss von der Datenbankgruppe, dass sie die Implementierung eines
'Wort-Indexes' plant. Ich weiss auch grob, wie dieser aussehen soll.
Die Semantik dieses Indexes und auch der uebrigen Daten muss von den
Entwicklern der Suchmaschine hundertprozentig verstanden sein, damit
sie ueberhaupt irgendetwas implementieren koennen. Sie koennen mit den
Entwicklern der Oberflaeche solange nicht die Semantik einer einzigen
Funktion vereinbaren, wie sie nicht wissen, ob und wie sie diese
implementieren koennen, und ob sie deren Semantik vor dem Datenbestand
ueberhaupt garantieren koennen.

An dieser Stelle kommt nun genau das zum Tragen, was meiner in der
Einleitung erwaehnten Praeferenz fuer die Richtung von der Datenbank
'aufwaerts' zugrundeliegt. Ich wuensche mir deshalb eine Praesentation
der Datenbankgruppe, worauf ich im letzten Abschnitt zurueckkomme.

Abschliessende Bemerkungen und Vorgehensweise
=============================================
Ich denke, es mangelt nicht an Teilaufgaben. Ich habe versucht, einige
davon im einzelnen ein wenig zu praezisieren.
Aus meiner Sicht ergibt sich folgende Vorgehensweise bei der Zusammenarbeit
der Projektgruppen:

  1. Information ueber die Semantik der Datenbank, des Datenbestandes und
     dessen Indexe anhand von Beispieldaten und Dokumentation durch die
     Datenbankgruppe.
  2. Entscheidung fuer einen der Loesungswege aus dem vorigen Abschnitt.
  2a.Entscheidung, ob ein, und wenn ja, welches String-Aehnlichkeitsmass
     auf welchen Daten implementiert wird, in Zusammenarbeit mit 'Gruppe'
     Delta.
  3. Spezifikation einer Menge von Funktionen zwischen
     WWW-Gruppe und Gruppe 'Anfragesprache und Suchmaschine'.
  4. Verbindliche Spezifikation der Anfragesprache 'Level 0' durch Gruppe
     'Anfragesprache' und eines Standard-Interfaces, Klaerung, ob
     Suchmaschine als Server oder als Prozess angelegt wird.
  5. Entscheidung der Gruppe 'Anfragesprache und Suchmaschine'
     fuer eine (hoechstens zwei) Implementierungssprache(n).
     (Ich habe kein Geheimnis aus meiner Entscheidung gemacht:-)
  6. Implementierung von Suchmaschine, Anfragesprache, Perl-Interface,
     begleitet von Tests mit der WWW-Gruppe.
  7. ...

Ich bin zunehmend der Meinung, dass, falls das CSLIB 2000 Projekt aus
irgendeinem Grunde scheitern sollte, dies an dem Gebrauch ungeeigneter
Werkzeuge liegt (was auch immer das bedeuten mag:-)