DE19954534A1

DE19954534A1 - Rückwärtsindexieren von Zeichenketten in einer relationalen Datenbank zum Suchen mit Joker

Info

Publication number: DE19954534A1
Application number: DE19954534A
Authority: DE
Inventors: Debora Jean Byrne; John Mark Mcconaughy; Shaw-Ben Shi; Chin-Long Shu; Trung Minh Tran
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1998-11-19
Filing date: 1999-11-12
Publication date: 2000-05-31
Also published as: JP2000163447A; US6199062B1

Abstract

Verfahren einer hierarchischen LDAP-Jokersuche in einem LDAP-Verzeichnisdienst mit einem Verwaltungssystem für eine relationale Datenbank (DBMS) als ein Externspeicher. Die relationale Datenbank enthält in der Regel einen Vorwärtsindex der Zeichenketten in der Datenbank. Das Verfahren generiert zunächst einen Rückwärtsindex der Zeichenketten in der relationalen Datenbank. In Abhängigkeit von der Position eines oder mehrerer Joker in der Kette werden der Vorwärtsindex, der Rückwärtsindex oder beide benutzt, um die relationale Datenbankabfrage zu generieren.

Description

DER ERFINDUNG ZUGRUNDELIEGENDER ALLGEMEINER STAND DER TECHNIK

Die vorliegende Erfindung betrifft im allgemeinen das Vor sehen von Verzeichnisdiensten in einer verteilten Rechner umgebung.

Ein Verzeichnisdienst ist der zentrale Punkt, wenn Netzwerk- Dienste, Sicherheits-Dienste und Applikationen eine inte grierte, verteilte Rechnerumgebung bilden. Typische Anwen dungen eines Verzeichnisdienstes können in verschiedene Kategorien klassifiziert werden. Ein "Benennungs-Dienst" (z. B. DNS und DCE Zellenverzeichnisdienst (CDS - Cell Directory Service)) benutzt das Verzeichnis als Quelle zum Auffinden einer Internet-Host-Adresse oder des Orts eines bestimmten Servers. Eine "Anwender-Registry" (z. B. Novell NDS) speichert Informationen über Anwender in einem System, das sich aus einer Anzahl verschalteter Maschinen zusammen setzt. Das zentrale Datenhaltungssystem für Anwenderinforma tionen ermöglicht es einem Systemadministrator, das verteilte System als Ein-Systemabbild zu verwalten. Wieder ein anderer Verzeichnis-Dienst ist ein "Weiße Seiten"- Nachschlagsystem, das einige e-Mail-Clients vorsehen, z. B. Netscape Communicator, Lotus Notes, Endora und dergleichen.

Mit den immer stärker zunehmenden Applikations- und System diensten, die eine zentrale Informationshaltung verlangen, wird die nächste Generation der Verzeichnisdienste voraus setzen, daß Systemadministratoren über Datenhaltungen ver fügen, die den Verwaltungsaufwand signifikant erleichtern können. Zusätzlich muß der künftige Verzeichnisdienst auch Endanwendern einen reichen Informationsdatenspeicher bieten, der es ihnen ermöglicht, auf Abteilungs- oder Firmenmit arbeiterdaten sowie Quelleninformationen, wie Namen und Standorte von Druckern, Kopiergeräten, und sonstige Umge bungsbetriebsmittel zuzugreifen. In einer Internet/Intranet- Umgebung wird es erforderlich sein, den sicheren Anwender zugriff auf solche Informationen bereitzustellen.

Zu diesem Zweck wurde das Lightweight Directory Access Protocol (LDAP) als offener IETF-Standard entwickelt, um Verzeichnisdienste für Applikationen von e-Mail-Systemen bis zu verteilten Systemverwaltungswerkzeugen zu bieten. LDAP ist ein sich entwickelndes Protokoll, das auf der Grundlage eines Client-Server-Modells beruht, in dem der Client eine TCP/IP-Verbindung zu einem LDAP-Server aufbaut, Anforderungen absendet und Antworten erhält. Das LDAP- Informationsmodell gründet sich insbesondere auf einen "Eintrag", der Informationen über irgendein Objekt enthält. Einträge werden in der Regel in einer spezifischen Baumstruktur organisiert, und jeder Eintrag setzt sich aus Attributen zusammen.

LDAP sieht eine Anzahl bekannter Funktionen vor, einschließ lich Abfrage (Suchen und Vergleichen), Aktualisieren, Echt heitsbestätigung und andere. Die Suchen- und Vergleichen- Operationen werden benutzt, um Informationen aus der Daten bank abzurufen. Für die Suchfunktion werden die Suchkriterien in einem Suchfilter spezifiziert. Der Suchfilter ist in der Regel ein Boolescher Ausdruck, der aus Kennzeichnern, einschließlich Attributname, Attributwert und Booleschen Operatoren UND, ODER und NICHT besteht. Anwender können den Filter benutzen, um komplexe Suchoperationen durchzuführen.

LDAP sieht dabei die Möglichkeit vor, daß eine Verzeichnis information wirksam abgefragt oder aktualisiert wird. Es bietet einen reichen Satz Suchmöglichkeiten, mit denen die Anwender komplexe Suchkriterien zusammenstellen können, um die gewünschten Informationen aus einem Externspeicher zu erhalten. In steigendem Maße war es erwünscht, eine rationale Datenbank zum Speichern von LDAP-Verzeichnisdaten zu benutzen. Repräsentative Datenbankimplementierungen sind DB/2, Oracle, Sybase, Informix und dergleichen. Wie allgemein bekannt, ist die Structured Query Language (SQL- Strukturierte Abfragesprache) die Standardsprache, die zum Zugriff auf solche Datenbänke benutzt wird.

LDAP-Einträge bestehen aus Attribut/Wert-Paaren. Innerhalb der relationalen Datenbanken (z. B. DB/2) wird eine gesonderte Tabelle für jedes der im LDAP-Schema zugelassenen Attribute erstellt. In dieser Tabelle werden die Attributwerte, zusammen mit einem Eintrags-ID (EID - Entry- ID), gespeichert, zu denen die Attributwert gehören. Wenn der Wert des Attributs kleiner ist als der Wert für eine indexierbare Spalte, dann wird ein Index auf der Grundlage des Attributwerts und des EID erzeugt. Wenn ferner ein Wert die maximale Länge für eine indexierbare Spalte überschreitet, wird eine zusätzliche Spalte erzeugt, die einen abgekürzten Wert enthält. Beim Generieren des Index (nachstehend als "Vorwärtsindex" bezeichnet aus Gründen, die noch ersichtlich werden) ist die Datenbank während der Suche beim Abrufen von Daten viel schneller.

Die Unterstützung des Suchens mit Jokern ist unbedingte Vor aussetzung beim Erzeugen einer durchsuchbaren Datenbank. Zwar beschleunigt die Anwendung des oben beschriebenen Index die meisten Suchen, jedoch zeigen Suchen, die mit einem "Joker" "*" (z. B. die Datenkette "*something") beginnen, bei weitem keine so gute Leistung innerhalb relationaler Datenbanken wie z. B. DB/2. In erster Linie geschieht das deswegen, weil solche Datenbanken b-Bäume zum Indexieren benutzen. In solchen bekannten Schemata gründet sich die B- Baumsuche auf die ersten Zeichen in der Suchkette. Wenn am Anfang der Kette ein Joker steht, hat die B-Baumsuche eine Schwierigkeit beim Finden eines Startpunkts. Daher ergibt sich, daß die Suche nicht wirksam durchgeführt werden kann.

Die vorliegende Erfindung befaßt sich mit dem Problem der ineffizienten Suche mit Joker in einer relationalen Daten bank.

Eine Hauptaufgabe der vorliegenden Erfindung ist es, ein Verfahren zum Suchen mit Joker in einer relationalen Datenbank unter Verwendung hierarchischer, filtergestützter Abfragen, wie z. B. LDAP, bereitzustellen.

Eine weitere Hauptaufgabe der vorliegenden Erfindung ist es, ein Jokersuchzeichen in eine Position zu zwingen, die optimal für einen bestimmten Datenbanksuchalgorithmus ist.

Noch eine bedeutsame Aufgabe der vorliegenden Erfindung ist das Vorsehen eines Mechanismus, der eine gegebene Zeichen kette (oder einen Teil derselben) umkehrt, um das Suchen mit Joker in einer relationalen Datenbank zu optimieren.

Noch eine weitere bedeutsame Aufgabe der vorliegenden Erfin dung ist das Abbilden einer gegebenen Zeichenkette mit einem Jokeroperator auf eine Zeichenkette, die aufgrund der gegebenen verfügbaren Datenbanksuchstrategie optimal gesucht werden kann.

Eine spezifischere Aufgabe der vorliegenden Erfindung ist das effektive Implementieren von LDAP SQL Suchabfragen mit Joker-Suchzeichen.

Diese und noch weitere Aufgaben der Erfindung werden be schrieben in einem Verfahren zum Suchen mit Joker in einer relationalen Datenbank, z. B. durch Benutzen hierarchischer, filtergestützter Suchabfragen. Das Verfahren beginnt mit dem Generieren eines Vorwärtsindex der Zeichenkette in der Datenbank. Das Verfahren generiert dann einen umgekehrten Index der Zeichenketten in der relationalen Datenbank. Der Rückwärtsindex generiert, vorzugsweise durch Spiegeln (d. i. Erzeugen eines Spiegelbildes), den Vorwärtsindex. Nach Ein gang einer hierarchischen, filtergestützten Suchabfrage mit einer Suchkette mit einem Joker, wird dann der Rückwärtsindex zum Generieren der entsprechenden relationalen Datenbankabfrage (z. B. in SQL) benutzt, wenn der Joker innerhalb der Suchkette an einer bestimmten Position steht. So ist z. B. die gegebene Position eine führende Position in der Suchkette. Als Alternative ist die gegebene Position an einer Zwischenposition in der Suchkette und die Anzahl der Zeichen, die nach dem Joker steht, ist größer als die Zeichenkette, die vor dem Joker steht. Wenn der Joker nicht in der gegebenen Position innerhalb der Suchkette steht, wird der Vorwärtsindex dazu benutzt, die relationale Datenbankabfrage zu generieren. In beiden Fällen wird dann die relationale Datenbankabfrage dazu benutzt, auf die relationale Datenbank zuzugreifen und Ergebnisse auszugeben.

In einer bevorzugten Ausführungsform ist die filtergestützte Abfrage eine Lightweight Directory Access Protocol (LDAP) Verzeichnisdienstabfrage, und die relationale Datenbank ist eine DB/2.

Gemäß einem weiteren Aspekt der vorliegenden Erfindung können sowohl Vorwärts- als auch Rückwärtsindexe benutzt werden, um Teile der gleichen Suchkette zu suchen. In diesem Verfahren des Suchens mit Joker werden zunächst die Vorwärts- und Rückwärtsindexe generiert. Bei Empfangen der hierarchischen, filtergestützten Abfrage, die die Suchkette mit dem Joker betrifft, wird bestimmt, ob der Vorwärtsindex, der Rückwärtsindex, oder beide Indizes benutzt werden sollen um die relationale Datenbankabfrage zu generieren. Die Bestimmung hängt in der Regel ab von der relativen Position des Jokers in der Suchkette. Als Ergebnis der Bestimmung wird dann die relationale Datenbankabfrage generiert. Wenn beide Indizes benutzt werden, wird in der Regel die Suche mit dem ersten Teil der Datenkette bis zum Joker mit Hilfe des Vorwärtsindex ausgeführt. Die Suche im restlichen Teil der Datenkette (hinter dem Joker) wird durchgeführt mit Hilfe des Rückwärtsindex im umgekehrten zweiten Teil.

So wird gemäß der vorliegenden Erfindung eine zusätzliche Spalte (identisch mit der indexierten Spalte) in der relationalen Datenbank erzeugt; die Daten dieser Spalte werden in umgekehrter Reihenfolge gespeichert, um das Erstellen einer SQL-Abfrage zu ermöglichen, die die Stärken der relationalen Datenbank benutzt. Alle eingehenden Suchen, die mit einem Joker beginnen, werden dann umgekehrt und der Rückwärtsindex wird anstatt des Vorwärtsindex benutzt.

Zusätzlich zum Behandeln des Szenarios, in dem der Joker am Anfang der Kette steht, wird der erfindungsgemäße Rück wärtsindex auch benutzt, um kompliziertere Szenarien zu ver arbeiten, z. B. einen Joker mitten in der Kette oder mehr als einen Joker in der Kette.

Vorzugsweise wird die Erfindung in einem Rechnerprogramm implementiert, das in einem Rechner zum Ausführen der Vor richtungsschritte abläuft. Der Vorwärtsindex und sein ent sprechender Rückwärtsindex werden vorzugsweise in der rela tionalen Datenbank gespeichert. Die Jokersuchmethode erleichtert das Implementieren einer zuverlässigen und skalierbaren Unternehmensverzeichnislösung, in der eine bevorzugte Ausführungsform das LDAP mit einem externen DB/2 Speicher ist.

Die obigen Ausführungen haben einige der einschlägigeren Aufgaben und Merkmale der vorliegenden Erfindung überschlagsweise dargestellt. Diese Aufgaben und Merkmale müssen so verstanden werden, daß sie nur illustrativ für einige der stärker hervorragenden Merkmale und Applikationen der Erfindung gelten. Viele weitere günstige Ergebnisse lassen sich durch Anwenden der geoffenbarten Erfindung auf andere Weise oder Verändern der Erfindung erzielen, wie noch beschrieben wird. Dementsprechend lassen sich weitere Aufgaben und ein volleres Verständnis der Erfindung anhand der nachfolgenden detaillierten Beschreibung der bevorzugten Ausführungsform erzielen.

Für ein volleres Verständnis der vorliegenden Erfindung und deren Vorteile muß Bezug auf die folgende detaillierte Beschreibung anhand der begleitenden Zeichnungen genommen werden; in diesen ist

Fig. 1 eine repräsentative LDAP-Verzeichnisdienst-Implemen tierung;

Fig. 2 ist ein vereinfachtes LDAP-Verzeichnis;

Fig. 3 ist ein Flußdiagramm einer LDAP-Verzeichnissitzung;

Fig. 4 zeigt eine repräsentative LDAP-Verzeichnisdienst- Implementierung mit einem externen Speicher einer relatio nalen Datenbank;

Fig. 5 ist eine vereinfachte Darstellung einer Suchkette, die vom Jokersuchmechanismus der vorliegenden Erfindung manipuliert wurde;

Fig. 6 ist eine Darstellung einer Suchkette mit einem Joker am Anfang, und der resultierenden Suchkette, die von der vorliegenden Erfindung generiert wurde;

Fig. 7 ist eine Darstellung einer Suchkette mit einem Joker dazwischen, und einem Suchkettentyp, der von der erfindungs gemäßen Methode generiert wurde.

Fig. 8 zeigt die Suchkette aus Fig. 7 und illustriert einen zweiten Suchkettentyp, der von der erfindungsgemäßen Methode generiert wurde.

Fig. 9 ist ein vereinfachtes Flußdiagramm des erfindungs gemäßen Verfahrens zum Suchen mit einem Joker in einem LDAP- Verzeichnisdienst mit einem externen Speicher eines relatio nalen Datenbankverwaltungssystems.

In Fig. 1 wird ein Blockdiagramm eines repräsentativen LDAP- Verzeichnisdienstes gezeigt, in dem die vorliegende Erfindung implementiert werden kann. Wie wohlbekannt ist, ist LDAP das Lightweight Directory Access Protokoll, und dieses Protokoll wurde auf dem Stand der Technik z. B. implementiert, z. B. als Vorderende zum X.500 Verzeichnisdienst oder als eigenständiger Verzeichnisdienst. Gemäß dem Protokoll stellt eine Client-Maschine 10 eine TCP/IP-Verbindung mit einem LDAP-Server 12 her, schickt eine Anforderung ab und erhält Antworten. Der LDAP-Server 12 unterstützt ein Verzeichnis 21, wie in vereinfachter Form in Fig. 2 illustriert wird. Sowohl die Clientmaschine als auch die Severmaschine beinhalten ferner eine Verzeichnis- "Runtime"-(Laufzeit)-Komponente 25 zum Implementieren der Verzeichnisdienstoperationen, wie nachstehend beschrieben wird. Das Verzeichnis 21 gründet sich auf das Konzept eines Eintrags ("Entry"), der Informationen über irgendein Objekt (z. B. eine Person) enthält. Einträge setzen sich zusammen aus Attributen 29, die einen Typ und einen oder mehrere Werte umfassen. Jedes Attribut 29 hat eine bestimmte Syntax, die festlegt, was für eine Art Werte im Attribut zulässig sind (z. B. ASCII-Zeichen, .jpeg file usw.) und wie diese Werte bei einer bestimmten Verzeichnisoperation gebunden sind.

Der Verzeichnisbaum ist in einer vorgegebenen Art und Weise organisiert, wobei jeder Eintrag relativ zu seinen Geschwi stereinträgen mit einem "relativ eindeutigen Namen" (RDN - Relative Distinguished Name) unverwechselbar benannt wird. Ein RDN enthält mindestens einen eindeutigen Attributwert aus dem Eintrag, und höchstens ein Wert je Attribut wird im RDN benutzt. Gemäß dem Protokoll enthält ein global eindeutiger Name für einen Eintrag, der als "eindeutiger Name" (DN - Distinguished Name) bezeichnet wird, eine Verkettung der RDN-Sequenz aus einem gegebenen Eintrag zur Baumwurzel.

Die LDAP-Suche kann auf einen einzigen Eintrag (Basisebenen suche), auf die Kinder eines Eintrags (Ein-Ebenensuche) oder einen ganzen Unterbaum (Unterbaumsuche) angewandt werden. Somit ist der "Geltungsbereich" (Scope), der von der LDAP- Suche unterstützt wird: Basis, Ein-Ebene und Unterbaum. LDAP unterstützt nicht Suche nach beliebigen Baumebenen und Pfadaufzählung.

LDAP beinhaltet eine Applikationsprogrammier-Schnittstelle (API - Application Programming Interface) wie in "The C LDAP Application Program Interface", IETF Working Draft, 29. Juli 1997 beschrieben, die hier durch Querverweis angezogen wird. Eine Applikation auf einer gegebenen Client-Maschine benutzt die LDAP-API zum Bewirken einer Verzeichnisdienst-"Sitzung" (Session) gemäß dem Flußdiagramm in Fig. 3. In Schritt 40 wird eine LDAP-Sitzung mit einem Vorgabe-LDAP-Server initia lisiert. In Schritt 42 gibt eine API-Funktion ldap_init() ein Bearbeitungsprogramm an den Client zurück und dieses Bearbeitungsprogramm kann gleichzeitig geöffnete Mehrfachverbindungen zulassen. Im Schritt 44 ermächtigt der Client den LDAP-Server, daß er z. B. eine API-Funktion ldap_bind() benutzt. In Schritt 46 werden eine oder mehrere LDAP-Operationen durchgeführt. Zum Beispiel kann die API- Funktion ldap_search() benutzt werden, um eine gegebene Verzeichnissuche durchzuführen. Im Schritt 48 gibt der LDAP- Server die Ergebnisse der Verzeichnissuche, z. B. ein oder mehrere Datenbankelemente, die die Suchkriterien erfüllen, zurück. Dann wird die Sitzung in Schritt 50 mit der API- Funktion ldap_unbind() geschlossen, die dann benutzt wird, um die Verbindung zu schließen.

Es kann erwünscht sein, LDAP-Verzeichnisdaten in einem Externspeicher abzuspeichern. Fig. 4 illustriert repräsenta tive LDAP-Verzeichnisdienst-Implementierungen, die für diesen Zweck ein Verwaltungssystem für eine relationale Datenbank (RDBMS - Relational Database Management System) benutzen. Das System illustriert einen möglichen LDAP- Verzeichnisdienst, in dem die vorliegende Erfindung implementiert werden kann. Der Fachmann erkennt natürlich, daß sich die Erfindung nicht auf einen LDAP- Verzeichnisdienst beschränkt, der mit einem DB/2- Externspeicher bestückt ist. Die Prinzipien der vorliegenden Erfindung können auch in anderen Verzeichnisdienst-Typen (z. B. X.500) praktiziert werden und andere Verwaltungssysteme für relationale Datenbanken (z. B. X.500, Oracle, Sybase, Informix usw.) als Externspeicher benutzen. In Fig. 4 kann ein LDAP-Client 34 sich mit einer Anzahl vernetzter Datenbanken 38a-38n über einen LDAP-Server 36 zusammenschließen. Die Datenbanken 38a-38n enthalten die Verzeichnisinformationen. Jedoch aus der Sicht des Anwenders speichert der LDAP-Server 36 alle Informationen ab, ohne die Datenbank 38 zu kennen, in der die Daten tatsächlich abgelegt sind. Mit dieser Konfiguration ist der LDAP-Server 36 frei von der Aufgabe der Verwaltung der physikalischen Datenspeicherung und kann Informationen aus einer Vielzahl von Datenbankservern 38 abrufen, die zusammenarbeiten, um einen riesigen Datenspeicher zu bilden.

Der Fachmann erkennt hier, daß die in Fig. 4 gezeigten Systemarchitekturen nicht als einschränkend für die vorlie gende Erfindung verstanden werden dürfen. Die Technik der Erfindung kann zum Durchsuchen jeder beliebigen relationalen Datenbank unter Verwendung jedes beliebigen Abfragetyps benutzt werden (und nicht nur hierarchische, auf Filter gegründete Datenbankabfragen). Wenn die Erfindung in einem LDAP-Verzeichnisdienst mit einem relationalen Datenbank-Ver waltungssystem (DBMS) als Externspeicher implementiert ist, bedient sich der Dienst verschiedener LDAP-Tabellen strukturen. Weitere Einzelheiten über diese Strukturen (sowie die SQL SELECT Aussagen, die von den LDAP/DB/2- Suchroutinen benutzt werden) sind in US-Anmeldung 09/050, 503 mit dem Titel "A Fast And Efficient Method To Support Hierarchical LDAP Searches with Relational Tables", erteilt an den Inhaber der vorliegenden Anmeldung, vorgesehen, und werden hier durch Querverweis angezogen.

Fig. 5 illustriert eine Suchkette 60 mit einer Anzahl Schriftzeichenpositionen 62. An jeder Schriftzeichenposition kann ein Jokersuchzeichen stehen, das in der Regel durch ein Sternchen ("*") ausgedrückt wird. Im vorliegenden Beispiel sitzt der Joker 64 irgendwo innerhalb der Suchkette 60. Daher enthält ein erster Teil (d. i. eine Teilkette) 66 der Suchkette die Schriftzeichen vor dem Joker 64, und ein zweiter Teil 68 der Suchkette enthält die Schriftzeichen hinter dem Joker. Dieses Beispiel wird ausschließlich zur Erleichterung der Beschreibung der hier benutzten Nomenklatur beim Diskutieren einer Suchkette benutzt. Die Suchkette kann auch mehrere Joker enthalten.

Wenn gemäß die vorliegende Erfindung, wie in Fig. 6 gezeigt, der Joker 64 in der ersten Position der Suchkette 60 steht, wird die Suchkette (vorzugsweise zur Gänze) umgekehrt, wie unter Bezugszeichen 60' gezeigt wird, um den Suchprozeß zu erleichtern. Wenn ferner der Joker 64 irgendwo im Inneren der Suchkette steht, sind zwei Lösungen zum Durchsuchen der Kette möglich. Im Beispiel der Fig. 7 ist die Anzahl der Schriftzeichen in der Teilkette 66 (dem vorderen Teil) kleiner als die Anzahl der Schriftzeichen in der Teilkette 68 (dem hinteren Teil); daraus ergibt sich, daß es erwünscht ist, die gesamte Kette umzukehren, wie durch Bezugszeichen 60' gezeigt wird, um die Suchwirksamkeit zu erhöhen. Fig. 8 zeigt eine alternative Technik, in der die vordere Teilkette 66 in Vorwärtsrichtung beibehalten wird, während die hintere Teilkette 68 umgekehrt wird. Wie man sieht, setzt diese letztere Technik den Joker 64 an das hintere Ende der neuen zusammengesetzten Suchkette 60'''. Auf diese Weise wird eine Suche x₁x₂x₃, gefolgt von einer Suche x₈x₇x₆x₅* durchgeführt.

Durch Zwingen des Jokers in die letzte Zeichenposition (oder wenigstens möglichst nahe an diese Position) wird die zusammengesetzte Suche effizienter durchgeführt, wenn eine relationale Datenbank als Außenspeicher benutzt wird.

Jetzt wird der Prozeß zum Generieren der umgekehrten Zeichenketten beschrieben. Wie oben angemerkt wurde, bestehen die LDAP-Einträge aus Attribut-Wertepaaren. In der relationalen Datenbank (z. B. DB/2) wird für jedes der Attribute, die im LDAP-Schema zulässig sind, eine gesonderte Tabelle erstellt. Innerhalb dieser Tabelle werden die Attributwerte gespeichert, zusammen mit einem Eintrag-ID (EID - Entry ID), zu dem die Attributwerte gehören. Wenn der Attributwert kleiner ist als der Wert für eine indexierbare Spalte, dann wird ein Index auf der Grundlage des Attributwertes und des EID erzeugt. Wenn ferner der Wert die maximale Länge für eine indexierbare Spalte überschreitet, wird eine zusätzliche Spalte erstellt, die einen abgekürzten Wert enthält. Diese Spalte mit dem abgekürzten Wert wird dann auf der Grundlage des Werts im EID indexiert. Dieser Index wird hier Vorwärtsindex genannt. Erfindungsgemäß wird der Vorwärtsindex in einen Rückwärtsindex gespiegelt, um das Suchen mit dem Joker zu ermöglichen.

Insbesondere, sieht in LDA-Schema-Dateien ein gegebener Anwender (z. B. der Verzeichnis-Administrator) Attributnamen und -merkmale vor. Die nachstehende Tabelle illustriert ver schiedene Attributdefinitionen, die als Ausfallsschema vorgesehen sind:

Die erste Spalte sagt aus, daß ein Attribut definiert wird. Die zweite Spalte gibt den Namen des Attributs. Die dritte Spalte schreibt die Syntax für dieses Attribut vor. Die vierte Spalte spezifiziert den innerhalb der relationalen Datenbank zu benutzenden Tabellennamen. Laut Vereinbarung können in DB/2 Tabellennamen nicht länger als 18 Schrift zeichen sein; damit ist es nicht immer zulässig, einfach den Attributnamen zu benutzen. Die fünfte Spalte spezifiziert die maximale Länge für den Attributwert, und die letzt Spalte spezifiziert die Attributzugriffsklasse, die bei der Zugriffssteuerung benutzt wird. Diese Information bleibt im Speicher während das Programm innerhalb der sogenannten Attributdefinitionsstruktur abläuft.

Wenn der DB/2-Server zum erstenmal anläuft, werden die Tabellen erstellt, wobei jeweils eine Tabelle je Attribut erstellt wird, das in den Schemadateien gefunden wird. Somit führt z. B. die Definition von "cn" zu der folgenden Attributtabelle:

Zusätzlich wird auf dieser Tabelle ein Index erstellt, der die Werte wie folgt wiedergibt: (EID,CN). Wie wohlbekannt ist, ist DB/2 in der Lage, Spalten bis zu 240 Schriftzeichen zu indexieren. In diesem repräsentativen Beispiel wird daher für cn keine abgekürzte Spalte geschaffen. Die Wertespalte innerhalb der Tabelle bekommt vorzugsweise den gleichen Namen wie der Tabellenname in allen Fällen. Nehmen wir ein anderes Beispiel, die Definition von "Member" würde zu einer Attributtabelle wie folgt führen:

Der für diese Tabelle erzeugte Index wäre das Paar: (EID,MEMBER_T). Im vorliegenden Beispiel wird eine abgekürzte Spalte erzeugt, weil der Wert für das Mitgliedattribut bis zu 1000 Zeichen betragen kann. Dieser Wert ist länger als eine zulässige indexierbare Spalte in DB/2. Vorzugsweise wird der Name der abgekürzten Indexspalte durch Anhängen von _T an den Spaltennamen gebildet. Wenn nötig, wird der Spaltenname selbst abgekürzt, um einen Namen unter der Grenze der DB/2-Spaltennamenlänge zu erzeugen. Gemäß vorliegender Erfindung wird eine zusätzliche Spalte hinzugefügt, um Suchen zu verbessern, die mit einem Joker beginnen (oder sonstwie einen Joker enthalten). Vorzugsweise sind die Inhalte dieser Spalte das Spiegelbild derjenigen, die in der vorwärts-indexierten Spalte stehen. So ist z. B. für die Tabellen-CN der obigen Beschreibung die vorwärts indexierte Spalte die cn-Spalte. Im Beispiel der MEMBER- Tabelle ist die vorwärts-indexierte Spalte die Spalte MEMBER_T. Wie man noch sehen wird, generieren die entstehen den Daten einen sogenannten Rückwärtsindex, der zum Ermög lichen der oben beschriebenen, und in den Fig. 6-8 illu strierten Jokersuchstrategien benutzt wird.

Beim Erstellen der Tabellen wird die zusätzliche Spalte vor zugsweise in allen Tabellen erstellt, die keine Binärwerte in ihren Attributen enthalten. Tabellen mit Binärattributen sind klar identifizierbar durch "bin" in der Syntaxspalte der Attributdefinition. In den Beschreibungsstrukturen der speicherresidenten Attribute wird ein Feld freigehalten, das den Namen der indexierten Spalte identifiziert. Um das Hinzufügen zusätzlicher Daten zu der Struktur zu vermeiden, ist die rückwärts-indexierte Spalte vorzugsweise identisch mit der indexierten Spalte, erhält jedoch das Präfix "R". Diese Spalte wird dann erzeugt. Die beiden obigen Tabellen sehen jetzt so aus:

Diese Tabelle enthält einen Vorwärtsindex in (EID,CN) und einen Rückwärtsindex in (EID,RCN).

Diese Tabelle beinhaltet einen Vorwärtsindex in (EID,MEMBER_T) und einen Rückwärtsindex in (EID,RMEMBER_T). Die oben beschriebene Technik sieht eine einfache Methode vor, um innerhalb des Code auf die Rückwärtsspalten zugreifen zu können ohne in der Datenstruktur zusätzlichen Speicherraum zu brauchen. Um das "R" dem Namen der Rückwärtsspalte voranstellen zu können, kann es erwünscht, oder in einigen Fällen auch notwendig sein, einen weiteren Buchstaben vom Spaltennamen abzuschneiden. Man betrachte z. B. die folgende Attributdefinition und die ihr zugewiesene Tabellenstruktur:

Der Name "REGISTEREDADDRESS" (im vorliegenden repräsentativen Beispiel) hat ein Zeichen weniger als die zulässige Länge. Somit werden in der bevorzugten Implementierung des erfindungsgemäßen Schemas (für diesen Datenbanktyp) und um Platz für die Werte R und _T zu machen, zwei Zeichen vom Namen abgeschnitten, um die Basis für den indexierten Spaltennamen zu schaffen. Das _T wird angehängt für den abgekürzten Vorwärtsindex. Das R wird vorne angehängt und das _T wird hinten angehängt für den abgekürzten Rückwärtsindex. Das selbe Verfahren wird durchgeführt beim Schaffen der Namen für Spalten in Tabellen, wo kein abgekürzter Wert benötigt wird. Der Unterschied ist, daß der Originalname der Spalte um einen Platz kürzer gehalten wird als der maximal zulässige Wert, so daß vorne ein "R" angehängt werden kann.

Bei Eingang einer Hinzufügungsanforderung wird der Attribut wert in die Wertespalte (d. h. in die Spalte, die mit dem Tabellennamen übereinstimmt) eingesetzt. Falls erforderlich, wird ein abgekürzter Wert in der abgekürzten Spalte gespei chert. Zusätzlich wird der indexierte Wert umgekehrt und in der indexierten Umkehrspalte (bzw. abgekürzten Spalte) gespeichert. Zum Beispiel sieht eine repräsentative Tabelle beim Hinzufügen der Attributwerte CN: Smith und CN, aus wie folgt: John Smith, zusammen mit einem Eintrag mit einem EID 4:

Betrachten wir die folgende beispielhafte Suche anhand einer Suchkette "*sm*". In diesem Beispiel wird eine SQL-Abfrage, wie SELECT EID FROM CN WHERE CN LIKE?, benutzt mit ? = sm*. Ohne den Rückwärtsindex ist diese Abfrage die gleiche Abfrage wie für die Suche nach der Zeichenkette "smith". Mit dem Rückwärtsindex jedoch heißt die Abfrage jetzt; SELECT EID FROM CN WHERE RCN LIKE? ESCAPE '\', mit ? = htims*". Wie man sieht, liegt jetzt der Joker am Ende der Schriftzeichensuchkette. Diese Abfrage benutzt den Vorteil einer Operation, in der DB/2 eine sehr gute Leistung aufweist, nämlich eine Suche mit einem Joker am Ende.

Joker werden ebenso häufig in der Mitte einer Suchkette benutzt wie am Anfang oder am Ende. Die vorliegende Erfindung sieht daher einen Mechanismus zur Verstärkung des Suchen mit Jokern unter Verwendung des Rückwärtsindex in solchen Szenarien vor. Insbesondere wird die Rückwärtsindexspalte in diesen Fällen benutzt, um die Leistungsergebnisse zu verbessern. Fig. 9 illustriert ein vereinfachtes Flußdiagramm des Jokersuchmechanismus der vorliegenden Erfindung, in dem potentiell sowohl der Vorwärtsindex als auch der Rückwärtsindex verschiedenen Teilen der gleichen Suchkette zugewiesen werden. Die Routine beginnt in Schritt 80 durch Erstellen des Vorwärtsindex und des Rückwärtsindex. Dieser Prozeß wurde bereits oben in Einzelheiten beschrieben und illustriert. Der Fachmann erkennt, daß der Rückwärtsindex kontinuierlich aktualisiert wird, wenn neue Zeichenketteneinträge im Vorwärtsindex erstellt werden. In Schritt 82 fährt die Routine einen Test um festzustellen, ob eine LDAP-Abfrage vom LDAP- Verzeichnisdienst her eingegangen ist. Wenn nicht, läuft die Routine zyklisch durch. Wenn aber das Resultat des Tests im Schritt 82 positiv ist, geht die Routine zu Schritt 84 über (unter der Annahme der Existenz eines Jokers in der Such kette), um festzustellen, ob der Joker am Anfang der Such kette steht. Wenn ja, verzweigt die Routine zu Schritt 86 und generiert (unter Verwendung des Rückwärtsindex) eine umgekehrte Suchkette. Die umgekehrte Suchkette wird dann benutzt, um die Abfrage in der relationalen Datenbank in Schritt 88 zu generieren. Wenn jedoch der Ausgang des Tests in Schritt 84 anzeigt, daß das erste Zeichen kein Joker ist, geht die Routine zu Schritt 90 über, um die Anzahl der Zeichen vor dem Joker und die Anzahl der Zeichen hinter dem Joker zu zählen.

Im Schritt 92 wird ein Test durchgeführt, um festzustellen, ob die Anzahl der Zeichen hinter dem Joker größer ist als die Anzahl der Zeichen vor dem Joker. Wen die Anzahl der Zeichen hinter dem Joker größer ist als die Anzahl der Zeichen vor dem Joker kann keine optimale Suche durchgeführt werden (weil der Joker näher zum Anfang der Suchkette steht). Wenn also das Ergebnis des Tests in Schritt 92 positiv ist, geht die Routine zu Schritt 94 über und kehrt den hinteren Teil der Kette (einschließlich des Jokers) um, um den Joker ans Ende zu setzen. Dann kehrt die Routine wieder zu Schritt 88 zurück, in dem die zusammengesetzte Kette zum Generieren der Datenbankabfrage benutzt wird. Wenn das Ergebnis des Tests in Schritt 92 jedoch negativ ist, ist die vordere Teilkette größer und damit ist der Rückwärtsindex nicht nötig. (Er kann aber auf die hintere Teilkette angewandt werden, falls gewünscht). Dann kehrt die Routine wieder zu Schritt 88 zurück, wie bereits beschrieben. Das schließt die Verarbeitung ab.

Zeigen wir hier ein konkretes Beispiel; betrachten wir dazu eine Zeichenkette wie "some*thing" (mit einem Joker in der Mitte). Wie oben bereits gesagt, lassen sich hier zwei unterschiedliche Verfahren mit dem Rückwärtsindex anwenden.

Erstens, der Rückwärtsindex wird zusammen mit dem normalen Vorwärtsindex benutzt. Und zwar wird die Suche am ersten Teil der Kette bis zum Joker mit dem Vorwärtsindex durchgeführt. Am restlichen Teil der Zeichenkette (hinter dem Joker) wird die Suche am umgekehrten zweiten Teil mit dem Rückwärtsindex durchgeführt. In diesem illustrativen Beispiel sieht die Suche für diese Technik aus wie folgt: SELECT EID FROM CN WHERE CN LIKE? ESCAPE '\' AND RCN LIKE? ESCAPE '\'. Die erste Parametermarke (?) ist "some*" und die zweite Parametermarke ist "gniht*".

Der Rückwärtsindex ist auch nützlich, wenn der Joker nahe einem bestimmten Ende der Kette sitzt, wie z. B. "so*mething" oder "somethi*ng". Da die typische B-Baumsuche-Implemen tierung die vorne stehenden Zeichen in der Kette benutzt, zeigt die zweite Suche (somethi*ng) eine viel besserer Leistung als die erste Suche (so*mething), weil die zweite Suche eine Kette mit viel mehr vorne stehenden Zeichen betrifft. Die vorliegende Erfindung nutzt diese Eigenschaft durch Verwenden des Rückwärtsindex, um eine Abfrage in einer relationalen Datenbank zu generieren, wenn der Joker an einer gegebenen Position in der Suchkette steht. Wie oben angemerkt, wenn die gegebene Position eine vordere Position in der Suchkette ist, wird der Rückwärtsindex benutzt. Auch wenn die gegebene Position ferner eine mittlere Position in der Suchkette ist und die Anzahl der Zeichen hinter dem Joker größer ist als die Anzahl der Zeichen vor dem Joker, wird die Rückwärtskette benutzt.

Der Fachmann erkennt hier, daß die erfindungsgemäße Lösung erweitert werden kann, wenn mehrere Joker in der Kette vor kommen. In einem solchen Fall wird die Kettenlänge bis zum ersten Joker, und die Länge vom letzten Joker bis zum Ende gemessen. Dann kann eine einfache Suche gefahren werden.

Wenn die Länge der Kette bis zu ersten Jokerzeichen länger ist als die Länge vom letzten Joker bis zum Ende, dann wird der Vorwärtsindex benutzt. Wenn aber die Länge vom letzten Joker bis zum Kettenende länger ist als die Länge bis zum ersten Joker, dann wird die Rückwärtssuche benutzt. Zum Beispiel würde eine Suche an "so*mething*likethis" eine Rückwärtssuche benutzen, während eine Suche an "something*like*this" eine Vorwärtssuche benutzen würde.

Die vorliegende Erfindung macht sich somit die Eigenschaft der B-Baumsuche zunutze, in der das Suchen mit hinten stehenden Jokern eine erhöhte Leistung erbringt. Also verbessert sich die Leistung einer Abfrage mit der Suchkette "so*mething" durch die Anwendung der zu "gnihtem*os" umge kehrten Rückwärtsindexspalte. Gemäß der vorliegenden Erfin dung wird eine viel längere vorne stehende Zeichenkette generiert (sieben Zeichen anstatt zwei), und bewirkt damit, daß die B-Baumsuche durch die vorhandene relationale Datenbank viel schneller und effektiver abläuft.

Das Kombinieren des Vorwärts- und Rückwärtsindex ermöglicht das Anwenden der vorliegenden Erfindung mit ausgezeichneter Leistung zum Auffinden von Teilkettenübereinstimmungen ohne den großen Speicherraumbedarf, der bei anderen Techniken auf dem Stand der Technik erforderlich ist. So generiert z. B. der bekannte Netscape-Verzeichnisserver alle Teilkettenkomponenten einer festen Länge und indexiert sie. Leistungstests zeigen, daß die vorliegende Erfindung die Jokerteilkettensuche wesentlich verbessert (in verschiedenen Fällen bis zu 500%) durch Wettbewerbsfähigmachen der Jokersuche gegenüber anderen LDAP-Implementierungen im gewerblichen Bereich. Die hier dargestellte erfindungsgemäße Technik kann auf jeder beliebige handelsübliche relationale Datenbank und LDAP-Serverimplementierung auf B-Baumgrundlage (wie der Netscape LDAP-Server) angewandt werden.

Der Fachmann erkennt hier, daß die vorliegende Erfindung den Joker in einer Suchkette in eine Position zwingt, so daß sie sich die besonderen Stärken des Suchalgorithmus zunutze macht, der zum Zugriff auf die Datenbank angewandt wird. Somit kann die vorliegende Erfindung verallgemeinert werden, daß jede geeignete Technik angewandt werden kann, um einen oder mehrerer Joker in Positionen zu zwingen, die für den besonderen Suchalgorithmus optimal sind, der zum Zugriff auf die interessierenden gespeicherten Daten benutzt wird.

Insbesondere bearbeitet die erfindungsgemäße Methode bei Eingang einer Abfrage, die eine Suchkette mit einem Joker aufweist, die Suchkette durch Zwingen des Joker in eine optimale Suchposition als Funktion des Algorithmus, der zum Durchsuchen der Datenbank benutzt wird. Die bearbeitete Suchkette wird dann zum Zugriff auf die Datenbank benutzt.

Wie oben angemerkt kann die Erfindung in jedem hierarchischen Verzeichnisdienst implementiert werden, in dem ein Verwaltungssystem einer relationalen Datenbank (RDBMS - Relational Database Management System) benutzt wird, um eine Externspeicherfunktion vorzusehen. So können z. B. die Prinzipien der vorliegenden Erfindung in einem X.500 Verzeichnisdienst oder in noch zu entwickelnden LDAP- Implementierungen verwirklicht werden. Die erfindungsgemäß generierte SQL-Abfrage wird benutzt, um auf die relationale Datenbank zuzugreifen, und die Ergebnisse werden dann als Antwort auf diese Abfrage erhalten. Die Erfindung kann auch mit einem relationalen Datenbank-Verwaltungssystem implementiert werden, das zusätzlich zu einem Verzeichnisdienst implementiert ist. Der Fachmann erkennt, daß die Erfindung auf jedes relationale Datenbank- Verwaltungssystem (RDBMS) anwendbar ist und nicht nur auf DB/2. So kann zum Beispiel die relationale Datenbank ein Oracle, Sybase oder jeder andere von Dritten gelieferte externe Speicher sein.

Ferner wurde zwar die bevorzugte Ausführungsform im Kontext mit dem Generieren einer Abfrage in Structured Query Language (SQL) beschrieben, jedoch sollte die erfindungsgemäße Technik breit angelegt sein, um sich auf jede relationale Datenbank-Abfragesprache erweitern zu lassen. Auch kann die erfindungsgemäße Technik durch eine Datenbankabfrage getrieben werden und nicht nur durch eine LDAP-Abfrage, wie in der bevorzugten Ausführungsform beschrieben.

Eine der bevorzugten Ausführungsformen der Routinen der vor liegende Erfindung ist als Anweisungssatz (Rechner programmcode) in einem Code-Modul in einem Speicher mit wahlfreiem Zugriff eines Rechners resident bzw. läßt sich in diesen herunterladen.

Claims

1. Ein Verfahren zum Jokerdurchsuchen einer relationalen Datenbank unter Verwendung hierarchischer, filter basierter Abfragen, enthaltend die folgenden Schritte:
Generieren eines Zeichenketten-Rückwärtsindex in der relationalen Datenbank;
bei Eingang einer hierarchischen, filter-basierten Abfrage, die eine Suchkette mit einem Joker enthält, Anwenden des Rückwärtsindex zum Generieren einer relationalen Datenbank-Abfrage, wenn der Joker in einer gegebenen Position in der Suchkette steht; und
Anwenden der relationalen Datenbank-Abfrage, um auf die relationale Datenbank zuzugreifen.

2. Das Verfahren gemäß Anspruch 1, in dem die gegebene Position eine führende Position in der Suchkette ist.

3. Das Verfahren gemäß Anspruch 1, in dem die gegebene Position eine Zwischenposition in der Suchkette ist und die Anzahl der Zeichen hinter dem Joker größer als die Anzahl der Zeichen vor dem Joker ist.

4. Das Verfahren gemäß Anspruch 1, das ferner den folgenden Schritt aufweist: Anwenden eines Vorwärtsindex zum Generieren einer relationalen Datenbankabfrage, wenn der Joker nicht an einer gegebenen Position innerhalb der Suchkette steht.

5. Das Verfahren gemäß Anspruch 4, in dem die gegebene Position eine Zwischenposition in der Suchkette ist und die Anzahl der Zeichen hinter dem Joker kleiner als die Anzahl der Zeichen vor dem Joker ist.

6. Das Verfahren gemäß Anspruch 1, in dem der Rückwärtsindex durch Erzeugen eines Spiegelbildes des Vorwärtsindex generiert wird.

7. Das Verfahren gemäß Anspruch 1, in dem die filter- basierte Abfrage eine Lightweight Directory Access Protocol (LDAP) Verzeichnisdienstabfrage ist.

8. Ein Verfahren zum Jokerdurchsuchen einer relationalen Datenbank unter Verwendung hierarchischer, filter basierter Abfragen, enthaltend die folgenden Schritte:
Generieren eines Vorwärtsindex von Zeichenketten in der relationalen Datenbank;
Generieren eines Rückwärtsindex durch Spiegeln des Vor wärtsindex;
bei Eingang einer hierarchischen, filter-basierten Abfrage, die eine Suchkette mit mindestens einem Joker enthält, Bestimmen ob der Vorwärtsindex, der Rückwärts index, oder beide Indexe zum Generieren einer relatio nalen Datenbankabfrage verwendet werden sollen;
als Ergebnis dieser Bestimmung, Generieren der relatio nalen Datenbank-Abfrage; und
Anwenden der relationalen Datenbank-Abfrage, um auf die relationale Datenbank Zugriff zu nehmen.

9. Das Verfahren gemäß Anspruch 8, in dem der Rückwärtsindex auf die Suchkette angewandt wird, um die relationale Datenbank-Abfrage zu generieren.

10. Das Verfahren gemäß Anspruch 8, in dem der Vorwärtsindex auf einen ersten Teil der Suchkette, und der Rückwärtsindex auf einen zweiten Teil der Suchkette angewandt wird, um die relationale Datenbankabfrage zu generieren.

11. Das Verfahren gemäß Anspruch 10, in dem der Joker an einer Zwischenposition in der Suchkette steht und die Anzahl der Zeichen vor dem Joker größer ist als die Anzahl der Zeichen hinter dem Joker.

12. Das Verfahren gemäß Anspruch 8, in dem die Suchkette zwei oder mehr Joker enthält.

13. Ein Verfahren zum Durchsuchen einer relationalen Daten bank von einem Lightweight Directory Access Protocol (LDAP) Verzeichnisdienst, der filter-basierte Abfragen generiert, wobei die relationale Datenbank einen Vor wärtsindex aus Zeichenketten und einen Rückwärtsindex, der das Spiegelbild des Vorwärtsindex ist, abgespeichert enthält, und das Verfahren die folgenden Schritte umfaßt:
bei Eingang einer LDAP-Abfrage, die eine Suchkette mit einem Joker enthält, Benutzen des Vorwärtsindex, des Rückwärtsindex, oder beider Indexe, zum Generieren einer relationalen Datenbankabfrage in Abhängigkeit von der Position des mindestens einen Jokers in der Suchkette; und
Benutzen der relationalen Datenbankabfrage, um auf die relationale Datenbank Zugriff zu nehmen.

14. Ein Rechnerprogrammerzeugnis in maschinell lesbaren Medien zum Durchsuchen einer relationalen Datenbank unter Verwendung hierarchischer, filter-basierter Abfragen, enthaltend:
Mittel zum Generieren eines Zeichenketten- Rückwärtsindex in der relationalen Datenbank; und
auf den Eingang einer hierarchischen, filter-basierten Abfrage ansprechende Mittel, die eine Suchkette mit einem Joker aufweisen, zum Anwenden des Rückwärtsindex zum Generieren einer relationalen Datenbankabfrage, wenn der Joker an einer bestimmten Position in der Suchkette steht.

15. Das Rechnerprogrammerzeugnis gemäß Anspruch 14, in dem die gegebene Position eine führende Position in der Suchkette ist.

16. Das Rechnerprogrammerzeugnis gemäß Anspruch 14, in dem die gegebene Position eine Zwischenposition in der Suchkette ist und die Anzahl der Zeichen hinter dem Joker größer als die Anzahl der Zeichen vor dem Joker ist.

17. Das Rechnerprogrammerzeugnis gemäß Anspruch 14, in dem die filter-basierte Abfrage eine Lightweight Directory Access Protocol (LDAP) Verzeichnisdienstabfrage ist.

18. Ein Rechnerprogrammerzeugnis in maschinell lesbaren Medien zum Durchsuchen einer relationalen Datenbank unter Verwendung hierarchischer, filter-basierter Abfragen, enthaltend:
Mittel zum Generieren eines Rückwärtsindex durch Spiegeln eines Zeichenketten-Vorwärtsindex in der relationalen Datenbank; und
auf den Eingang einer hierarchischen, filter-basierten Abfrage ansprechende Mittel, die eine Suchkette mit mindestens einem Joker aufweisen, zum Anwenden des Vorwärtsindex, des Rückwärtsindex, oder beider Indexe zum Generieren einer relationalen Datenbankabfrage.

19. Ein Verzeichnisdienst, enthaltend:
Ein Verzeichnis, das als Namenshierarchie organisiert ist, mit einer Vielzahl von Einträgen, die jeweils von einem unverwechselbaren Identifikator repräsentiert werden;
einem Verwaltungssystem einer relationalen Datenbank mit einem Externspeicher zum Abspeichern der Verzeichnisdaten;
Mittel zum Durchsuchen des Verzeichnisses, enthaltend:
Mittel zum Generieren eines Rückwärtsindex durch Spiegeln eines Zeichenketten-Vorwärtsindex in der relationalen Datenbank; und
auf den Eingang einer hierarchischen, filter-basierten Abfrage ansprechende Mittel, die eine Suchkette mit mindestens einem Joker aufweisen, zum Anwenden des Vor wärtsindex, des Rückwärtsindex, oder beider Indexe zum Generieren einer relationalen Datenbankabfrage.

20. Der Verzeichnisdienst gemäß Anspruch 19, in dem das Verzeichnis mit dem Lightweight Directory Access Protocol (LDAP) konform ist.

21. In einem Verzeichnisdienst mit einem Verzeichnis, das als Namenshierarchie organisiert ist, einschließlich einer Vielzahl von Einträgen, die jeder durch einen unverwechselbaren Identifikator repräsentiert werden, eine Verbesserung, die enthält:
ein Verwaltungssystem für eine relationale Datenbank mit einem Externspeicher zum Abspeichern von Verzeichnisdaten;
Mittel zum Durchsuchen des Verzeichnisses, umfassend:
Mittel zum Generieren eines Rückwärtsindex durch Spiegeln eines Zeichenketten-Vorwärtsindex in der relationalen Datenbank; und
auf den Eingang einer hierarchischen, filter-basierten Abfrage ansprechende Mittel, die eine Suchkette mit mindestens einem Joker aufweisen, zum Anwenden des Vor wärtsindex, des Rückwärtsindex, oder beider Indexe zum Generieren einer relationalen Datenbankabfrage.

22. Der Verzeichnisdienst gemäß Anspruch 21, in dem das Verzeichnis mit dem Lightweight Directory Access Protocol (LDAP) konform ist.

23. Ein Verfahren zum Jokerdurchsuchen einer Datenbank unter Verwendung einer Datenbankabfrage, enthaltend die folgenden Schritte:
Bei Eingang einer Abfrage, enthaltend eine Suchkette mit einem Joker, Bearbeiten der Suchkette, um den Joker in eine optimale Suchposition zu zwingen, als Funktion eines Algorithmus, der zum Durchsuchen der Datenbank verwendet wird;
Generieren einer Datenbankabfrage aus der bearbeiteten Suchkette; und
Verwenden der Datenbankabfrage um auf die Datenbank Zugriff zu nehmen.