DE60030735T2

DE60030735T2 - Voraussage der realisierbarkeit eines verbindungsweges

Info

Publication number: DE60030735T2
Application number: DE60030735T
Authority: DE
Inventors: Yaniv Morgan Hill GVILY; Shai Los Gatos AGASSI
Original assignee: SAP Portals Israel Ltd
Current assignee: SAP Portals Israel Ltd
Priority date: 1999-07-02
Filing date: 2000-06-29
Publication date: 2007-09-13
Anticipated expiration: 2020-06-30
Also published as: EP1203320A1; JP2006172491A; DE60030735D1; EP1203320A4; US6502094B1; ATE339730T1; CA2377581C; WO2001003009A1; JP2009116898A; JP4272656B2; EP1203320B1; IL147283A0; JP2003504727A; AU6065800A; JP5065309B2; USRE45752E1; CA2377581A1

Description

HINTERGRUND DER ERFINDUNG
Die vorliegende Erfindung bezieht sich allgemein auf Systeme und Verfahren zum Vorhersagen des Erfolges von Anfragen in Informationssystemen, die aus Objekten und Verbindungen zwischen den Objekten bestehen. Insbesondere bezieht sich die vorliegende Erfindung auf Systeme und Verfahren zum Vorhersagen, ob eine Instanz mit einem Objekt in Verbindung steht, ohne eine tatsächliche Anfrage durchzuführen.
Da Informationssysteme und besonders Datenbanksysteme immer weiter wachsen (z. B. in den Terabytebereich hinein), werden auch die Kosten der effizienten Abfrage der Datenbanken größer. Es ist nicht ungewöhnlich, dass ein Benutzer mit einer komplexen Anfrage auf eine Datenbank trifft und nach langen Minuten des Wartens nur "keine passenden Einträge gefunden" erhält. Diese leeren Anfragen nehmen wertvolle Serverressourcen ein, ohne irgendwelche nützlichen Ergebnisse zu liefern.
Während das Web an Popularität gewinnt, hat die Zahl von Benutzern, die gleichzeitig auf solche Informationssysteme zugreifen oder treffen können, drastisch zugenommen. Manche Websites erhalten Millionen von Treffern pro Tag. Es ist von zunehmender Bedeutung geworden, in der Lage zu sein, leere Anfragen zu erkennen und sie herauszufiltern, bevor sie wertvolle Ressourcen in Anspruch nehmen.
Einige der Probleme in Verbindung mit der Vorhersage, ob eine Anfrage keine Einträge liefern wird, schließen die Bestimmung ein, wie man im Voraus weiß, ob eine Instanz mit einem Objekt verknüpft ist (mit anderen Worten, ob es irgendwelche Instanzen dieses Objektes gibt, die mit der ursprünglichen Instanz in Verbindung stehen), und wie dies gemacht werden kann, ohne mit Laufzeit auf das Informationssystem oder die Datenbank zuzugreifen. Ein weiteres Problem ist es, alle Objekte aufzulisten, mit denen eine bestimmte Instanz in Verbindung steht.
Einige derzeit auf dem Fachgebiet bekannte Datenbanken unterstützen eine Art Abfragekosten-Analyse und -Vorhersage. Basierend auf Tabellen-, Index- und Verbindungsindexgrößen ist die Datenbank imstande, die Zeit zu schätzen, die zum Ablauf der Anfrage benötigt wird. Ein intelligenter Benutzerrechner wird Anfragen, die zu lange dauern, abbrechen. Das gibt dem Benutzer die Wahl, eine Anfrage basierend auf ihren Kosten abzubrechen, während diese Erfindung dem Benutzer ermöglicht, eine Anfrage basierend auf ihrem vorhergesagten Ergebnis abzubrechen.
Viele Datenbanken unterhalten auch Instanz-Instanz-Indextabellen. Wenn zwei Tabellen durch eine Fremdschlüssel/Primärschlüssel-Beziehung verknüpft sind, dann unterhält die Datenbank typischerweise einen B-Baumindex, der einen Schlüssel aufweist, welches der Fremdschlüssel ist, und Blätter einschließt, die eine Zahl enthalten, die auf die Indexdatei des Primärschlüssels hinweist. Dies gestattet der Datenbank, alle Primärschlüssel, mit denen spezifische Fremdschlüssel in Verbindung stehen, schnell zu finden. Ein Problem bei diesen B-Baumindices ist jedoch, dass sie dazu ausgelegt sind, eine Anfrage zu beantworten, nicht das Abfrage-Ergebnis vorherzusagen, bevor die Anfrage laufen gelassen wird. Außerdem werden diese Tabellen typischerweise für unmittelbar benachbarte Objekte unterhalten (d. h., wo eine direkte Verbindung existiert).
Das US-Patent Nr. 5,848,424, erteilt am 8. Dezember 1998 an Scheinkman et al., offenbart eine Datennavigation-Schnittstelle mit Navigation als Funktion ziehbarer Elemente und Ablegeziele. Die Schnittstelle basiert auf einem Zieh-und-Ablage-Paradigma, wodurch der Benutzer ein ziehbares Element verziehen und über einem Ablegezielelement ablegen kann, um eine Anfrage zu erzeugen. Das System ermöglicht dem Benutzer ein leichtes Generieren willkürlicher Ad-hoc-Anfragen, die zum Zeitpunkt der Erzeugung der Datenbank nicht zwangsläufig vorhergesehen werden. Es basiert auf einer Datenbankbeschreibung oder Matrix, wo Objekt-Objekt-Verknüpfungen gespeichert sind; jeder Eintrag in der Matrix steht stellvertretend für eine Art der Verbindung zwischen zwei Klassen von Objekten, wobei eine Klasse der Spalte des Eintrags entspricht, während die andere Klasse der Zeile des Eintrags entspricht. Das Vorhandensein eines Eintrags in der Matrix, d. h. das Vorhandensein eines Bits am Kreuzungspunkt einer Zeile und einer Spalte der Matrix, steht stellvertretend für eine Verbindung von einem Objekt zu einem anderen Objekt. Selbst wenn eine Objekt-Objekt-Verknüpfung existiert, garantiert dies jedoch nicht, dass eine Instanz des ersten Objektes existiert, die mit dem zweiten Objekt in Verbindung steht, geschweige denn, dass es bestimmt, ob spezifische Instanzen existieren. Tatsächlich können beide Objekte ganz ohne Instanzen sein, und doch wird die Datenbankbeschreibung eine Verbindung zwischen ihnen zeigen.
Derartige Systeme sind in dem Hyper-Relational Server [Hyperverknüpfungsserver] im Besitz und erfunden von TopTier Software, San Jose, Kalifornien verkörpert. Mit einem TopTier Hyper-Relational Server kann ein Benutzer entgegen den auf der Web-Hypertext-Metapher basierenden Systemen willkürlich Ad-hoc-Anfragen generieren. Dieses System liefert eine Lösung für das Bedürfnis, einem Benutzer die leichte Generierung willkürlicher Anfragen zu ermöglichen; es liefert keine Lösung für die oben aufgeführten Probleme, insbesondere das Problem, die Ergebnisse einer Anfrage vorherzusagen.
Was daher benötigt wird, ist ein System und Verfahren zum Vorhersagen, ob eine Anfrage eines Informationssystems eine leere Menge ergeben wird, ohne die Anfrage tatsächlich laufen lassen zu müssen.
Das US-Patent Nr. 5,761,654 offenbart ein Verfahren unter Einbeziehung einer Datenstruktur (Verbindungsbaum), die als Bildschirmmaske einer Abfrage-Anweisung dient und als Abfragediagramm graphisch angezeigt werden kann. "Die Abfragediagramm-Datenstruktur kann beim Abstimmen der SQL-Anweisung verwendet werden, so dass bei Analyse und Ausführung der Anweisung durch ein Datenbank-Suchprogramm Filterbedingungen in der Anweisung bei der frühest praktikablen Gelegenheit ausgeführt werden." Demgemäß lehrt US 5,761,654 ein Verfahren der effizienten Durchführung einer Anfrage durch organisiertes Durchforsten einer Verbindungsbaum-Datenstruktur.
Das Verfahren von US 5,761,654 zielt darauf ab, die Anfrage unter Verwendung der Tabelle mit der besten Trennschärfe (Lauftabelle) zu beginnen, um die meisten Zeilen in einem früheren Stadium der Anfrage zu eliminieren und den Abfrageprozess daher effizienter zu machen. Die Trennschärfe gibt die Wahrscheinlichkeit der Rückholung einer Zeile bei einem bestimmten Auswahlfilter an.
WO 97/11432 offenbart eine Verfahrenstechnik zur effizienten Verbindung mehrfacher großer Tabellen in einem Datenbanksystem mit einem Prozessor unter Verwendung eines kleinen Hauptspeichers. Die Verfahrenstechnik verwendet einen Verbindungsindex und minimiert die Anzahl von Ein-Ausgabe-Operationen bei gleichzeitiger Maximierung der Verwendung des kleinen Hauptspeichers durch einen Pufferzuordnungsprozess. Die Verfahrenstechnik teilt verfügbaren Hauptspeicher in Pufferspeicher auf und weist den Pufferspeichern Bedingungen zu, um sicherzustellen, dass jeder Pufferspeicher im Verbindungsergebnis eine weitgehend gleiche Datenmenge erhält. Die Verfahrenstechnik verarbeitet dann jede Eingabetabelle. Die Ausgabe wird mit einem Fragment für jede Eingabetabelle vertikal fragmentiert, was ferner die Einzelverarbeitung jeder Eingabetabelle erlaubt. WO 97/11432 offenbart auch ein Verfahren zur Erzeugung eines Verbindungsindex, falls nicht vorhanden.
O'Neil P. et al: "Multi-table joins through bitmapped join indices", Sigmod Record, Association for Computing Machinery, New York, USA, Vol. 24, Nr. 3, S. 8–11, offenbart ein Verfahren, das Mehrtabellenverbindungen durch Verwendung zeilenweise gesteuerter Verbindungsindices ermöglicht. Das Verfahren verwendet Verbindungsindices mit komprimierten Bitmap-Darstellungen, die es Aussagen, die Spalten von Beschreibungstabellen beschränken, ermöglichen, eine Antwortmenge (oder Schmelzmenge) in einer zentralen Detailtabelle (z. B. einer Auftragstabelle – wo eine Auftragszeile einen einzelnen Kauf enthält) zu bestimmen; das Verfahren verwendet unterschiedliche Aussagen über unterschiedliche Beschreibungstabellen (z. B. Kunden, Produkte und (Verkaufs-)Agenten) in Kombination, um die Detailtabelle durch komprimierte Bitmap-Darstellungen von Verbindungsindices zu beschränken und vervollständigt leicht die Verbindung der umfassend beschränkten Detailtabellenzeilen zurück zu den Beschreibungstabellen.
ASHANY R: "APPLICATION OF SPARSE MATRIX TECHNIQUES TO SEARCH, RETRIEVAL, CLASSIFICATION AND RELATIONSHIP ANALYSIS IN LARGE DATA BASE SYSTEMS-SPARCOM", Ergebnisse der internationalen Konferenz über sehr große Datenbanken; Westberlin, 13.–15. September 1978, New York, I.E.E.E., USA, 13. September 1978, Vol. CONF. 4, offenbart ein Informationssystem, das Objekte (im Beispiel gemäß 1 Spalten einer Tabelle mit den Überschriften "Verbrechen", "Waffentyp", "Orte", "Geschlecht", "Augenfarbe", "Sprachen") und Instanzen der Objekte (in 1 die Namen von Leuten, die Verbrechen begangen haben) umfasst. Das Dokument offenbart auch Beziehungen zwischen zumindest einigen der Objekte und den Instanzen der Objekte (in 1 z. B. hat "John" ein "Verbrechen" an einem "Ort" begangen) und eine Instanz-Objekt-Bitmap, die angibt, ob Instanzen von Objekten mit anderen Objekten verknüpft sind (die Tabelle gemäß 1 zeigt beispielsweise deutlich, dass es eine Reihe von Objekten ("Verbrechen", "Orte", "Geschlecht" etc.) gibt, die mit der Instanz des Objektes "John" verknüpft sind).
Gravano L, Garcia-Molina H, Tomasic A: "Precision and recall of GIOSS for database discovery", Parallel and Distributed Information Systems, 1994, Ergebnisse der dritten internationalen Konferenz in Austin, Texas, USA, 28.–30. Sept. 1994, Los Alamitos, Kalifornien, USA, IEEE Comput. Soc, 1994-09-28 offenbart ein System, das als Reaktion auf eine Benutzeranfrage relevante Datenbanken zur Suche vorschlagen kann. Die Anfrage des Benutzers durchläuft zwei Schritte: zuerst wird die Anfrage einem Server vorgelegt, um eine Reihe vielversprechender Datenbanken zur Suche auszuwählen. Während des zweiten Schritts wird die Anfrage tatsächlich an den gewählten Datenbanken ausgewertet. Der Server ist angeordnet, um basierend auf Worthäufigkeitsinformationen für jede Datenbank einen Hinweis darauf zu geben, welche Datenbanken für die Anfrage des Benutzers nützlich sein könnten. Diese Information gibt für jede Datenbank und jedes Stichwort in dem Datenbank-vokabular an, wie viele Dokumente für jeden Feldbezeichner an dieser Datenbank das Stichwort tatsächlich enthalten.
Das Dokument gibt auch ein Beispiel, wo eine Computer-Wissenschaftsbibliothek berichten könnte, dass "Knuth" (Stichwort) als Verfasser (Feldbezeichner) in 180 Dokumenten vorkommt, das Stichwort "Computer" im Titel von 25.548 Dokumenten usw. Solche als Ergebnis einer Anfrage erhaltenen Informationen sind viel weniger als die von einem Vollindex retournierten Informationen, weil es nur notwendig ist, die Häufigkeit für jedes Stichwort/Feldbezeichnungspaar festzuhalten, nicht die Identitäten der Dokumente, die es enthalten.
ZUSAMMENFASSUNG DER ERFINDUNG
Die vorliegende Erfindung bezieht sich auf Verfahren und Vorrichtungen zum Generieren einer Instanz-Objekt-Bitmap und Verwenden der Instanz-Objekt-Bitmap zur Vorhersage, ob eine Anfrage ein Ergebnis liefern wird.
Gemäß einem Aspekt der vorliegenden Erfindung wird in einem Informationssystem, das Objekte, Instanzen der Objekte und Beziehungen zwischen zumindest einigen der Objekte und den Instanzen der Objekte umfasst, ein Verfahren der Vorhersage bereitgestellt, ob eine Anfrage ein Ergebnis liefern wird, wobei das Verfahren die Schritte umfasst:

– Bereitstellen einer Instanz-Objekt-Bitmap, die anzeigt, ob Instanzen von Objekten mit anderen Objekten verknüpft sind;
– Zugreifen auf die Bitmap zum Bestimmen, ob die Anfrage ein Ergebnis liefern wird; und
– Unterrichten eines Benutzers, dass die Anfrage das Ergebnis liefern wird; und dadurch gekennzeichnet ist, dass der Schritt Bereitstellen einer Instanz-Objekt-Bitmap das Generieren der Instanz-Objekt-Bitmap durch Berechnen von Wegen von Instanzen zu benachbarten Objekten durch Bestimmen eines Weges von einer Instanz in einem Objekt zu einer Instanz in einem benachbarten Objekt und Berechnen eines Weges von einer Instanz zu einem nicht benachbarten Objekt durch Mischen eines Weges von einer Instanz in einem ersten Objekt zu einer Instanz in einem zweiten Objekt mit einem berechneten Weg von der Instanz in dem zweiten Objekt zu dem nicht benachbarten Objekt umfasst.

Gemäß einem anderen Aspekt der vorliegenden Erfindung wird ein Informationssystem bereitgestellt, das dem oben erwähnten Verfahren entspricht und im angehängten Anspruch 5 definiert ist.
Der Schritt Berechnen eines Weges von einer Instanz zu einem nicht benachbarten Objekt kann wiederholt werden, bis Wege von Instanzen zu entfernten Objekten bestimmt werden. In Übereinstimmung mit einer Ausführungsform der Erfindung können die Längen der Wege von Instanzen zu entfernten Objekten auf eine vorbestimmte Länge begrenzt sein. Zum Beispiel kann eine maximale Weglänge von 5 verwendet werden.
In Übereinstimmung mit einer Ausführungsform der vorliegenden Erfindung kann die Instanz-Objekt-Bitmap mit dem TopTier Hyper-Relational Server verwendet werden, um zu bestimmen, ob das Ziehen eines ziehbaren Elementes auf ein Ablegeziel ein Abfrage-Ergebnis liefern wird.
In Übereinstimmung mit einer anderen Ausführungsform der vorliegenden Erfindung kann die Instanz-Objekt-Bitmap leicht zum Erzeugen einer Objekt-Objekt-Wahrscheinlichkeitsmatrix verwendet werden, die dazu verwendet werden kann, die Wahrscheinlichkeit einer sich auf ein anderes Objekt beziehenden beliebigen Instanz zu bestimmen. Demzufolge kann anstelle der Verwendung der gewöhnlich größeren Bitmap, um unzweideutig vorherzusagen, ob eine Anfrage ein Ergebnis liefern wird, die Wahrscheinlichkeitsmatrix verwendet werden, um die Chance abzuschätzen, dass eine solche Anfrage ein Ergebnis liefern wird.
Ein umfassenderes Verständnis der vorliegenden Erfindung kann durch Bezugnahme auf die detaillierte Beschreibung bevorzugter Ausführungsformen und Ansprüche bei Betrachtung in Verbindung mit den Figuren gewonnen werden, worin gleiche Bezugszeichen sich in allen Figuren auf gleichartige Gegenstände beziehen.
KURZBESCHREIBUNG DER ZEICHNUNGEN
1 ist ein Blockdiagramm, das die Beziehung verschiedener Objekte und Instanzen der Objekte zeigt;
2 ist eine Darstellung einer Webseite, die zeigt, wie die Webseite anzeigt, dass Beziehungen zwischen einer Instanz und anderen Objekten existieren;
3 ist eine andere Darstellung einer Webseite, die zeigt, wie die Webseite anzeigt, dass Verbindungen zwischen einer Instanz und anderen Objekten existieren oder nicht existieren;
4 ist ein Blockdiagramm, das die Verbindungen verschiedener Objekte zeigt;
5 ist ein Flussdiagramm eines Verfahrens zum Berechnen einer Instanz-Objekt-Bitmap und Vorhersagen der Ergebnisse von Anfragen unter Verwendung derselben; und
6 ist ein Blockdiagramm, das die Beziehung verschiedener Objekte und Instanzen der Objekte zeigt.
BESCHREIBUNG DER SPEZIFISCHEN AUSFÜHRUNGSFORMEN
Diese Erfindung stellt die Vorhersage der Ergebnisse von Anfragen in Informationssystemen bereit, die aus Objekten und Verbindungen bestehen. Sie stellt auch Verfahren und Vorrichtungen zum Erkennen und Herausfiltern von Anfragen bereit, die keine Einträge liefern werden (d. h. eine leere Menge). Die vorliegende Erfindung kann mit relationalen, objektorientierten oder anderen geeigneten Datenbanken verwendet werden, ohne sie auf irgendeine Weise zu verändern.
In der übrigen Beschreibung ist die Erfindung unter Verwendung einer OLTP-Datenbank beschrieben; es sollte jedoch klar sein, dass die Erfindung nicht auf derartige Datenbanken begrenzt ist, sondern auf jede beliebige Art von System zutreffen kann, das aus Objekten, Instanzen und Verbindungen zwischen ihnen besteht. Es wird dabei beispielsweise an Verbindungen zwischen OLTP-Objekten und Instanzen, OLAP-Objekten und Instanzen, Webkomponenten oder Objekten und/oder Dokumentenbestandteile oder Objekte gedacht, um nur einige wenige zu nennen. In solchen Systemen besteht jedes der Objekte typischerweise aus mehreren Instanzen.
Eine Ausführungsform der vorliegenden Erfindung generiert und verwendet vorzugsweise eine Instanz-Objekt-Bitmap einer Datenbank. Sie funktioniert durch Unterhalten eines Bitvektors für jede Instanz jedes Objektes in dem System. Der Bitvektor steht stellvertretend für das Vorhandensein einer Verbindung von der Instanz zu allen anderen Klassen oder Objekten. In Übereinstimmung mit einer Ausführungsform der vorliegenden Erfindung wird der Vektor oder die Bitmap "offline" berechnet, bevor eine Anfrage generiert wird. Wenn eine Abfrage angefordert wird, kann in Laufzeit kostengünstig auf den Vektor oder die Bitmap zugegriffen werden, was es möglich macht, die Ergebnisse der Anfrage in viel weniger Laufzeit vorherzusagen als zur Ausführung der Abfrage tatsächlich notwendig wäre.
Die Erfindung stellt auch ein Verfahren zum Berechnen einer Instanz-Objekt-Bitmap bereit. Wie nachstehend detaillierter erörtert, ist die Rechenzeit zum Berechnen oder Generieren der Bitmap O(N), wobei N die Gesamtanzahl von Instanzen in dem System ist.
Die Instanz-Objekt-Bitmap einer Datenbank sowie die Verwendung dieser Instanz-Objekt-Bitmap wird nun detaillierter beschrieben. Im folgenden Beispiel beziehen sich die Großbuchstaben A, B etc. auf Objekte oder Klassen in einer Datenbank. Eine Instanz einer Klasse oder eines Objektes ist mit einem Index nach dem Großbuchstaben notiert. So bezeichnet A_i eine Instanz in Klasse A. Außerdem soll A→B eine Verbindung zwischen Klassen oder Objekten A und B bezeichnen. In einem TopTier Hyper-Relational Server des im US-Patent Nr. 5,848,424 offenbarten Typs ist die Art solcher Klasse-Klasse-Verbindungen in der Datenbankbeschreibung gespeichert.
A_i→B soll eine Verbindung zwischen einer Instanz in A zu Objekt B bezeichnen; A_i→B_j soll ferner bedeuten, dass aus den Instanzen A_i die Instanzen B_j werden, wenn die Verbindung A→B angewendet wird. Schließlich soll der Doppelpfeil →→ einen indirekten Verbindungsweg bedeuten.
Unter Bezugnahme auf 1 ist nun ein Blockdiagramm dargestellt, das die Beziehung verschiedener Objekte und Instanzen in einer Musterdatenbank zeigt. Der Einfachheit halber stellt dieses bestimmte Beispiel nur vier Objekte oder Klassen A–D bereit. Wie dargestellt, existieren Klasse-Klasse- oder Objekt-Objekt-Verknüpfungen von A zu B, von B zu C und von C zu D. Musterinstanzen jedes Objektes sind unter jedem Objekt gezeigt. In dem Beispiel gemäß 1 ist nur eine Instanz A₁ von Objekt A dargestellt, während acht Instanzen D₁ bis D₈ von Objekt D dargestellt sind. Das Beispiel in 1 zeigt nur einige Instanzen der Objekte A–D, für die eine Instanz-Instanz-Verbindung existiert. Mit anderen Worten, in der Datenbank können andere Instanzen A₂ bis A_n von Objekt A, andere Instanzen D₉ bis D_m von Objekt D etc. vorhanden sein. Auch andere Instanz-Instanz-Verbindungen können existieren, sind aber der Einfachheit halber nicht gezeigt.
Angenommen, ein Benutzer möchte alle Instanzen von D abfragen, mit denen A₁ in Verbindung steht. Typischerweise muss eine Anfrage erfolgen, um jedes B_i zu erhalten, mit dem A₁ in Verbindung steht. Dann muss für jedes der resultierenden B_i eine neue Abfrage ausgeführt werden, um eine Menge C_i,k zu bekommen, mit denen B_i in Verbindung steht. Diese müssen dann besonders gemischt werden, um eine Menge C_k zu liefern. Der Vorgang muss dann noch einmal wiederholt werden, um eine besondere Reihe D_j zu bekommen, auf die sich die Instanzen C_k beziehen. Mit anderen Worten, die indirekte Verbindung von A₁ zu den Instanzen D_j des Objektes D gleicht Verbindungen von Instanz A₁ zu Instanzen B_i, von Instanzen B_i zu Instanzen C_k und von Instanzen C_k zu Instanzen D_j. A1→→Dj = A1→B1 & Bi→Ck & Ck→Dj
Die Größenordnung des Berechnens einer derartigen Verbindung ist die Anzahl von Instanzen zur Leistung der Länge des Weges. Für das gesamte Schema – für jede mögliche Verbindung – gleicht die Rechenzeit der Gesamtzahl von Instanzen zur Leistung der Anzahl von Objekten (stellvertretend für die Länge der Wege) mal die Anzahl von Objekten (für jede unterschiedliche Quelle). Aufgrund der Tatsache, dass Doppeleinträge retourniert werden können, ist der Speicherplatzbedarf sogar noch größer. Die Rechenzeit beträgt somit: O(V·NV)
Bei Verwendung der hinlänglich bekannten mathematischen Buchstabenbezeichnung O(x) ist V die Anzahl von Objekten, und N = Σ_i=1...V|V_i| ist die Gesamtzahl von Instanzen.
Überdies können für diese Rechenart viele Male mehrfache Datenbankzugriffe benötigt werden. Typischerweise ist Datenbankzeit eine wertvolle und knappe Ressource. Während die Datenbank arbeitet, müssen alle Benutzer warten, auch derjenige, der die Anfrage laufen lässt. In dem obigen Beispiel sind zumindest drei Zugriffe zum Berechnen einer einzigen Instanz erforderlich.
Die vorliegende Erfindung hilft demzufolge, Laufzeitberechnungen zu verhindern, die kein Ergebnis liefern. Sie tut dies durch Vorsehen einer Instanz-Objekt-Bitmap der Datenbank, die verwendet wird, um vorherzusagen, ob eine Anfrage irgendwelche Einträge liefern wird. Die Bitmap kann ein Bitvektor für jede Instanz jedes Objektes in dem System sein; der Bitvektor steht dabei stellvertretend für das Vorhandensein einer Verbindung von der Instanz zu einigen oder allen anderen Klassen oder Objekten in dem System. In dem Beispiel gemäß 1, z. B. A₁, würde die Instanz-Objekt-Bitmap anzeigen:

– das Vorhandensein oder Nichtvorhandensein einer Verbindung von der Instanz A_i zum Objekt B;
– das Vorhandensein oder Nichtvorhandensein einer Verbindung von der Instanz A_i zum Objekt C; und
– das Vorhandensein oder Nichtvorhandensein einer Verbindung von der Instanz A_i zum Objekt D.

Die Instanz-Objekt-Bitmap macht es möglich, effizient und rasch zu berechnen, ob ein Ergebnis auf eine Anfrage vorhanden ist. In dem Beispiel gemäß 1 macht die Konsultation des Bitmapvektors für die Instanz A₁ klar, dass ein Weg von der Instanz A₁ zum Objekt D existiert und daher, dass die Abfrage aller Instanzen von D, mit denen A₁ verbunden ist, zumindest ein Ergebnis bringen wird. Der Zugriff auf die Instanz-Objekt-Bitmap ist in einem Bruchteil einer Sekunde möglich und ist bedeutend schneller als die Abfrage tatsächlich vollständig durchzuführen. Für alle anderen Instanzen A_i (i ≠ 1) wird die Bitmap anzeigen, dass es keine Verbindung zu irgendeinem der Objekte B–D gibt.
Die Erfindung macht es somit möglich, das Ergebnis einer Anfrage vorherzusagen oder, noch genauer, vorherzusagen, ob eine gestellte Anfrage ein Ergebnis liefern wird oder nicht. Dies erlaubt einem Benutzer oder einem von einem Benutzer laufen gelassenen Client-Programm, Anfragen auszuwählen oder Anfragen abzubrechen, die kein Ergebnis liefern werden, bevor irgendein Datenbankzugriff durchgeführt wird.
Die Instanz-Objekt-Bitmap kann nicht nur beantworten, ob eine Verbindung existiert, sondern als Nebenprodukt auch in Laufzeit alle realisierbaren Verbindungen für eine gegebene Instanz aufzählen. In diesem Zusammenhang sind realisierbare Verbindungen diejenigen Verbindungen, die ein Ergebnis liefern werden. Ein mit dieser Technologie ausgestattetes System kann den Benutzer durch Navigation in eine relationale oder andere Datenbankumgebung führen, wobei es nur Wege vorschlägt oder zulässt, die tatsächlich ein Ergebnis liefern werden. Diese Fähigkeit kann mit dem TopTier Hyper-Relational Server oder jeder anderen Datenbankzugriff-Technologie verwendet werden. Zum Beispiel kann im Falle des TopTier Hyper-Relational Servers das System so konfiguriert sein, dass jedes Mal, wenn ein Benutzer ein Element in der Schnittstelle zieht und über ein Ablegeziel bringt, das Ziel markiert wird, um anzuzeigen, dass die Anfrage tatsächlich ein Ergebnis liefern wird. Dies hilft dem Benutzer, in der Schnittstelle zu navigieren, indem der Benutzer informiert wird, wenn er ein Element auf ein Ablegeziel fallen lässt, das kein Abfrage-Ergebnis liefern wird, und verhindert somit, dass der Benutzer mit einer solchen Anfrage Zeit verschwendet. Natürlich können auch andere Verfahren zur Beratung des Benutzers in Betracht gezogen werden, ob die Anfrage ein Ergebnis liefern wird oder nicht.
In Übereinstimmung mit einer anderen Ausführungsform der vorliegenden Erfindung ist das System und Verfahren der vorliegenden Erfindung dann imstande, alle Objekte aufzulisten, mit denen eine bestimmte Instanz in Verbindung steht. Demgemäß ist es dann möglich, einem Benutzer diejenigen realisierbaren Anfragen aufzuzählen, die ein Ergebnis liefern werden, womit eine geführte Navigation durch bestimmte Daten unter Beweis gestellt wird. Dies kann durch Abtasten einer Vektorbitmap auf eine gegebene Instanz und Anzeigen einer Liste derjenigen Objekte erfolgen, zu denen eine Verbindung von der gegebenen Instanz aus existiert. Wie einem Fachmann auf diesem Gebiet verständlich sein wird, kann die Liste dem Benutzer in vielerlei Formen vorgelegt werden. 2 und 3 zeigen beispielsweise eine Art, einem Benutzer diese Information vorzulegen. 2 stellt eine Webseite 200 dar, die eine Vielzahl von Instanzen 202 und eine Vielzahl von Objekten oder Ablegezielen 204 auflistet. Im Beispiel von 2 wird die Instanz 202-3 gerade zu Ablegezielen 204 hinübergezogen. Die Prüfzeichen 206 neben den Ablegezielen oder Objekten 204 deuten an, dass eine Beziehung zwischen der Instanz 202-3 und den Objekten oder Ablegezielen existiert, und somit das Ablegen der Instanz 202-3 auf ein beliebiges der Objekte 204 ein Abfrage-Ergebnis liefern wird. Wenn keine Beziehung zwischen einer Instanz und einem Objekt existiert, wird ein 'X' 208 verwendet, um dem Benutzer zu zeigen, dass es keine Beziehung gibt (siehe 3). Wie in 3 dargestellt, weist die Instanz 202-4 eine Verbindung mit den Objekten 204-3, 204-4 und 204-5 auf, wie durch die Prüfzeichen 206 gekennzeichnet, hat aber keine Verbindung mit den Objekten 204-1, 204-2, 204-6, 204-7, 204-8 oder 204-9, wie durch 'X' 208 gekennzeichnet.
Gemäß noch einer anderen Ausführungsform der vorliegenden Erfindung kann die Verbindungsbitmap nur für Wege unter einer vorbestimmten Länge gespeichert sein. Dies reduziert nämlich die Offline-Rechenzeit der Bitmap und verursacht unter normalen Umständen keinerlei Problem für den Benutzer. In der Tat hat es den Anschein, dass Wege mit erhöhter Länge in den meisten relationalen Datenbanken gewöhnlich von geringerer Bedeutung sind. In Übereinstimmung mit einer Ausführungsform der vorliegenden Erfindung ist die vorbestimmte Anzahl von Weglängen fünf. Demzufolge ist in diesem Fall eine Verbindung nur in der Instanz-Objekt-Bitmap gespeichert, wenn der Weg von der Instanz zum letzten Objekt kürzer als oder gleich wie fünf Objekte ist.
Die Instanz-Objekt-Bitmap der vorliegenden Erfindung kann in vielerlei Formen verkörpert sein. Wie oben beschrieben, kann sie als Vektor gespeichert sein (P_i, i = 1 ... V), wobei P_i stellvertretend für das Vorhandensein eines Weges von der Instanz zum Objekt Nummer i steht. In diesem Fall entspricht die Größe eines Vektors der Anzahl möglicher Wege von der Instanz zu anderen Objekten. In Übereinstimmung mit anderen Ausführungsformen der vorliegenden Erfindung kann die Instanz-Objekt-Bitmap auch als Matrix oder in irgendeiner anderen geeigneten Form gespeichert sein.
Die Instanz-Objekt-Bitmap der vorliegenden Erfindung ist grundsätzlich sehr verschieden von bestehenden Instanz-Instanz-Indextabellen. Wie oben erörtert, kann die vorliegende Erfindung zur Vorhersage verwendet werden, ob ein Ergebnis vorliegt, während eine Instanz-Instanz-Indextabelle typischerweise verwendet wird, um die Antwort auf eine Anfrage zu liefern. In dem Beispiel gemäß 1 würde eine Instanz-Instanz-Tabelle anzeigen, dass die Instanz A₁ von Objekt A mit Instanzen B₁ und B₂ von Objekt B verknüpft ist. Dies macht es möglich, auf die Frage "wie ist Instanz A₁ mit Objekt B verknüpft" die Antwort B₁ und B₂ bereitzustellen. Die Instanz-Objekt-Bitmap der vorliegenden Erfindung macht es möglich vorherzusagen, dass eine Antwort auf die Anfrage existiert, stellt die Antwort aber nicht bereit. Unter der Annahme, dass die Instanz-Objekt-Bitmap der vorliegenden Erfindung typischerweise weniger Informationen liefert als eine Instanz-Instanz-Indextabelle des Standes der Technik, ist die Instanz-Objekt-Bitmap der vorliegenden Erfindung typischerweise viel kleiner als eine Instanz-Instanz-Indextabelle und nimmt somit viel weniger Arbeitsspeicher und/oder Speicherraum ein. Zum Beispiel zeigt die Instanz-Instanz-Indextabelle des Standes der Technik in dem oben gegebenen Beispiel an, dass eine Verbindung zwischen A₁ und B₁ sowie eine Verbindung zwischen A₁ und B₂ existiert. Die Instanz-Objekt-Bitmap der vorliegenden Erfindung zeigt jedoch nur an, dass eine Verbindung von A₁ zum Objekt B existiert, gibt aber nicht im Einzelnen an, was dies für Verbindungen sind.
Nun wird die Berechnung oder Generierung der Instanz-Objekt-Bitmap beschrieben.
Insbesondere kann die Bitmap der vorliegenden Erfindung unter Verwendung verschiedener Verfahren berechnet werden. In Übereinstimmung mit einer Ausführungsform der vorliegenden Erfindung kann die Bitmap berechnet werden, indem einfach Anfragen laufen gelassen werden, um sämtliche Instanzen-Objekt-Verbindungen zu bestimmen. Wie oben erörtert, entspricht die notwendige Laufzeit für alle Anfragen jedoch O(V·N^V), was einen beträchtlichen Zeitaufwand darstellt.
Demzufolge gibt es in Übereinstimmung mit einer anderen Ausführungsform der vorliegenden Erfindung ein Verfahren zur Vereinfachung und Beschleunigung der Berechnung der Instanz-Objekt-Bitmap. In Übereinstimmung mit dieser Ausführungsform der vorliegenden Erfindung wird ein Algorithmus zur "Offline"-Berechnung der Instanz-Objekt-Bitmap vorgelegt, der bedeutend schneller abläuft als sein Online-Gegenstück. Daher ist die notwendige Rechenzeit zum Erstellen der Instanz-Objekt-Bitmap eher verkürzt, was Laufzeit spart. In diesem Zusammenhang bedeutet "offline" nur, dass die Bitmap vor ihrer Verwendung zur Vorhersage der Ergebnisse von Anfragen berechnet wird. Einem Fachmann auf diesem Gebiet wird verständlich sein, dass das System während des Generierens der Bitmap auch zu anderen Zwecken laufen kann.
In Übereinstimmung mit einer Ausführungsform der vorliegenden Erfindung wird die Instanz-Objekt-Bitmap durch Suffixergänzung generiert. Die Suffixergänzung basiert auf der Beobachtung, dass es zur Berechnung eines indirekten Verbindungsweges A_i→→D von der Instanz A_i zum Objekt D möglich ist, zuerst B_j→→D zu berechnen, dann A_i→B_j und die beiden am Ende zu mischen. Dieses Verfahren erlaubt dem Algorithmus Wege, die bereits berechnet wurden, zur Berechnung längerer Wege erneut zu verwenden.
Unter Bezugnahme auf 4 wird nun ein Beispiel der Suffixergänzung beschrieben. 4 ist ein Blockdiagramm, das die Verbindungen verschiedener Objekte zeigt. In der Ausführungsform gemäß 4 sind fünf Objekte A–E mit vier Verbindungen dazwischen vorgesehen. Die vier Verbindungen bestehen von A zu B, von B zu C, von C zu D und von E zu B. In diesem Beispiel dient die Berechnung des indirekten Verbindungsweges B_j→→D von Instanzen B_j zum Objekt D als vorberechnetes Suffix zur Berechnung sowohl der indirekten Verbindungswege A_i→→D von den Instanzen A_i zum Objekt D als auch des indirekten Verbindungsweges E_m→→D von den Instanzen E_m zum Objekt D. Auf diese Weise kann die komplette Menge von Instanz-Objekt-Verbindungen in einer Größenordnung der Anzahl von Instanzen berechnet werden.
Eine Ausführungsform eines Verfahren zur Berechnung einer Instanz-Objekt-Bitmap wird nun noch näher erläutert. Zuerst werden für jede Instanz in dem Informationssystem benachbarte Objekte bestimmt. Dies kann beispielsweise unter Verwendung einer Instanz-Instanz-Indextabelle des auf dem Fachgebiet bekannten Typs geschehen, oder es können Anfragen zum Bestimmen dieser Verbindungen verwendet werden.
Beim nächsten Schritt werden Instanz-Objekt-Verbindungswege mit einer Länge von zwei berechnet. Dies kann unter Verwendung der im vorhergehenden Schritt berechneten Instanz-Nachbarobjekt-Verbindungswege geschehen. Diese vorberechneten Verbindungswege werden dann als Suffixe zur Berechnung längerer Verbindungswege verwendet. Derselbe Schritt kann so viele Male wie notwendig wiederholt werden, um Instanz-Objekt-Verbindungswege mit größeren Längen zu generieren. Jedes Mal wenn der Schritt wiederholt wird, werden neue Instanz-Objekt-Verbindungswege hinzugefügt, wobei jeder neue Weg eine Länge aufweist, die um ein Objekt länger ist als die Länge der im vorhergehenden Schritt berechneten Verbindungswege. Im Beispiel gemäß 4 weisen die Instanz-Objekt-Verbindungswege von den Instanzen B_j zu D beispielsweise eine Länge von zwei auf. Diese Wege können dann verwendet werden, um Instanz-Objekt-Verbindungswege von den Instanzen A_i zum Objekt D und von den Instanzen E_m zum Objekt D zu berechnen; diese Verbindungswege weisen eine Länge von drei auf.
Bei jedem Schritt ist die Rechenzeit von der Größenordnung der Anzahl von Instanzen. Schlimmstenfalls können sämtliche Instanzen als Ausgangspunkt eines Instanz-Objekt-Verbindungsweges verwendet werden. Demzufolge beträgt die Rechenzeit für den kompletten Prozess dann O(N), wobei N = Σ_i=1...V|V_i| die Gesamtzahl von Instanzen ist.
Die Begrenzung der Tiefe des Algorithmus auf Wege von weniger als einer vorbestimmten Länge, wie oben erörtert, kann die Rechenzeit durch Begrenzen der Anzahl von Schritten in dem Vorgang weiter verringern. Eine Tiefe von 5, wie in dem oben gegebenen Beispiel, begrenzt dann den Algorithmus so, dass eine Verbindungsbitmap nur für Wege gespeichert wird, deren Länge 5 Objekte nicht überschreitet. Dies wird nicht die ganze Menge von Verbindungen berechnen, kann aber erwünscht sein, weil Wege mit erhöhter Länge gewöhnlich von geringerer Bedeutung sind.
Zur Beschleunigung der Rechenzeit der Bitmap kann es wünschenswert sein, den Zugriff auf das Informationssystem während der Berechnung der Instanz-Objekt-Bitmap zu beschränken. Das heißt, wie oben erörtert, die Instanz-Objekt-Bitmap wird vermutlich "offline" vor der Generierung von Anfragen berechnet, für die eine Vorhersage notwendig ist. Wie einem Fachmann auf diesem Gebiet jedoch verständlich sein wird, kann das Informationssystem für andere Zwecke verwendet werden, z. B. für Anfragen, bei denen eine Vorhersage nicht benötigt wird. Eine Minimierung der Belastung des Informationssystems ist daher wichtig, besonders in Echtzeit-Dialogdatenbanken, wo Server-Verfügbarkeit von äußerster Wichtigkeit ist.
In Übereinstimmung mit einer anderen Ausführungsform der vorliegenden Erfindung kann eine Cache-Speicherung von Vergleichsabbildungen verwendet werden, um die Schnelligkeit der "Offline"-Berechnung der Bitmap zu erhöhen. Wie einem Fachmann auf diesem Gebiet verständlich sein wird, ist eine Vergleichsabbildung eine Tabelle von Schlüsselpaaren – ein Schlüssel für jedes Objekt der Verbindung. In relationalen Datenbanken wäre dies eine innere Verbindung der zwei Tabellen, deren Verknüpfung untersucht wird. Durch Cache-Speicherung dieser Abbildung für jede der Verbindungen in dem System braucht der Algorithmus nicht mehr als einmal pro Verbindung beim System anfragen, wodurch die Systembelastung bedeutend minimiert wird. Zum Berechnen von A_i→D wird der Algorithmus z. B. die Datenbank für die Verbindungen C_k→D, dann B_j→C und dann A_i→B abfragen, wie oben beschrieben. Zum Berechnen der umgekehrten Verbindungen D_i→A besteht keine Notwendigkeit, die Datenbank erneut abzufragen. Die Verknüpfungstabellen zwischen jeden zwei zusammenhängenden Tabellen sind durch den Algorithmus bereits örtlich im Cache gespeichert.
Ferner können die im Cache gespeicherten Verknüpfungstabellen nach der Abfrage sortiert werden. Dies erlaubt ein schnelleres Mischen von Bitmaps. Zum Beispiel fragt der Algorithmus nach Berechnen der Bitmap aller Instanzen B_j (zu den Objekten C und D) die Verknüpfungstabelle A_i→B_j ab. Er sortiert diese Liste nach den Instanzen A_i und läuft dann auf allen Instanzen A_i (nicht nur den derzeit von der Verbindung retournierten) und sucht nach jeglichem Vorkommen in der im Cache gespeicherten Verknüpfungstabelle, in der A_i mit B_j verbunden ist. Wenn er ein relevantes Vorkommen findet, verknüpft er die Bitmap durch eine ODER-Operation mit der Bitmap der betreffenden Instanz in B. Durch Verwenden der im Cache gespeicherten Verknüpfungstabellen auf diese Art und Weise nimmt die Suche O(log N), nicht O(N).
Unter Bezugnahme auf das Flussdiagramm 500 in 5 wird nun ein Prozess oder Verfahren zum Berechnen einer Instanz-Objekt-Bitmap und Vorhersagen der Ergebnisse von Anfragen unter Verwendung derselben erörtert. Der erste Teil des Flussdiagramms vom Start zu Schritt 508 entspricht der Berechnung der Instanz-Objekt-Bitmap. Der zweite Teil des Prozesses von Schritt 510 bis 518 verkörpert die Vorhersage der Ergebnisse von Anfragen. Nach dem Start werden bei Schritt 502 für jede Instanz einer Datenbank die Verbindungswege zu benachbarten Objekten bestimmt; eine Variable L wird auf 1 gesetzt.
Bei Schritt 504 werden für jeden Suffixweg der Länge L Instanz-Objekt-Verbindungswege der Länge L + 1 berechnet; der Prozess geht weiter zu Schritt 506, wo L um 1 heraufgesetzt wird.
Beim nächsten Schritt 508 wird bestimmt, ob eine vorbestimmte Höchstlänge L_max erreicht wird; wenn dies der Fall ist, rückt der Prozess zu Schritt 510 vor, andernfalls geht er zu Schritt 504 zurück. Der Schleifendurchlauf durch die Schritte 504, 506 und 508 fügt Instanz-Objekt-Verbindungswege wachsender Längen hinzu. Bei jeder Schleife nimmt die Anzahl neuer Wege wahrscheinlich ab. Auf alle Fälle erhält man am Ende eine Bitmap von Instanz-Objekt-Verbindungen.
Bei Schritt 510 wird eine neue Anfrage erwartet. Wenn eine Anforderung für eine Anfrage erhalten wird, rückt der Prozess zu Schritt 512 vor, wo auf die Instanz-Objekt-Bitmap zugegriffen wird. Durch Zugreifen auf die Instanz-Objekt-Bitmap kann das System vorhersagen, ob die Abfrage-Anforderung eine Abfrage mit Ergebnissen generieren wird. Wenn bei Schritt 514 das Vorhandensein eines Ergebnisses vorhergesagt wird, rückt der Prozess zu Schritt 516 vor, andernfalls rückt er zu Schritt 518 vor. Bei Schritt 516 wird die Abfrage ausgeführt, und der Prozess kehrt zu Schritt 510 zurück. Bei Schritt 518 wird die Anfrage abgebrochen, und der Prozess kehrt dann zu Schritt 510 zurück.
Das Flussdiagramm 500 gemäß 5 ist lediglich ein Beispiel einer möglichen Ausführungsform der vorliegenden Erfindung. In Übereinstimmung mit einer anderen Ausführungsform der vorliegenden Erfindung kann der Prozess zum Generieren der Bitmap vollkommen von dem Vorgang der Verwendung der Bitmap zum Vorhersagen des Ergebnisses einer Anfrage abgetrennt sein. Das heißt mit Bezug auf 5, der obere Teil des Flussdiagramms 500 ist vom unteren Teil des Flussdiagramms 500 abgetrennt und läuft zu einer anderen Zeit ab. Auf alle Fälle ist die vorliegende Erfindung nicht auf die dargestellte Ausführungsform beschränkt.
Schließlich stellt die vorliegende Erfindung Systeme und Verfahren bereit, um einen Benutzer in Laufzeit zu unterrichten, dass eine spezifische Anfrage (z. B. eine Zieh-und-Verbindungsoperation in einem TopTier Hyper-Relational Server) kein Ergebnis oder keine Einträge liefern wird, ohne dass die Anfrage laufen gelassen oder auf die Datenbanken zugegriffen werden muss. Außerdem kann die vorliegende Erfindung zur Aufzählung realisierbarer Navigationsziele für bestimmte Instanzen verwendet werden und kann zur Anzeige der Wahrscheinlichkeit verwendet werden, dass eine Verbindung ein Ergebnis bringt. Darüber hinaus stellt die Erfindung ein Verfahren zur Offline-Berechnung einer Instanz-Objekt-Bitmap bereit. Obwohl oben eine detaillierte Beschreibung derzeit bevorzugter Ausführungsformen der Erfindung gegeben worden ist, werden für Fachleute auf dem Gebiet verschiedene Alternativen, Modifikationen und Äquivalente offensichtlich sein. Obwohl z. B. vom Algorithmus der vorliegenden Erfindung gesagt wird, dass er für OLTP-Datenbanken verwendet wird, ist er nicht auf OLTP beschränkt. Die vorliegende Erfindung kann mit jedem um Objekte herum erstellten System und die Verbindungen dazwischen verwendet werden. Daher sollte die obige Beschreibung nicht als den Schutzbereich der Erfindung einschränkend angenommen werden, der durch die angehängten Ansprüche definiert ist.

Claims

Verfahren der Vorhersage, ob eine Anfrage ein Ergebnis liefern wird, in einem Informationssystem, das Objekte, Instanzen der Objekte und Beziehungen zwischen zumindest einigen der Objekte und den Instanzen der Objekte umfasst, wobei das Verfahren die Schritte umfasst: – Bereitstellen einer Instanz-Objekt-Bitmap, die anzeigt, ob Instanzen von Objekten mit anderen Objekten verknüpft sind; – Zugreifen auf die Bitmap zum Bestimmen, ob die Anfrage ein Ergebnis liefern wird; und – Unterrichten eines Benutzers, dass die Anfrage das Ergebnis liefern wird; und dadurch gekennzeichnet ist, dass der Schritt Bereitstellen einer Instanz-Objekt-Bitmap das Generieren der Instanz-Objekt-Bitmap durch Berechnen von Wegen von Instanzen zu benachbarten Objekten durch Bestimmen eines Weges von einer Instanz in einem Objekt zu einer Instanz in einem benachbarten Objekt und Berechnen eines Weges von einer Instanz zu einem nicht benachbarten Objekt durch Mischen eines Weges von einer Instanz in einem ersten Objekt zu einer Instanz in einem zweiten Objekt mit einem berechneten Weg von der Instanz in dem zweiten Objekt zu dem nicht benachbarten Objekt umfasst.
Verfahren gemäß Anspruch 1, worin der Schritt Berechnen eines Weges von einer Instanz zu einem nicht benachbarten Objekt wiederholt wird.
Verfahren gemäß Anspruch 1, worin der Schritt Berechnen eines Weges von einer Instanz zu einem nicht benachbarten Objekt wiederholt wird, bis Verbindungswege einer vorbestimmten Länge berechnet werden.
Verfahren gemäß Anspruch 1 oder Anspruch 2, worin der Schritt Bereitstellen einer Instanz-Objekt-Bitmap das Bereitstellen einer Instanz-Objekt-Bitmap umfasst, die anzeigt, ob jede Instanz eines Objektes mit allen anderen Objekten durch einen Verbindungsweg verknüpft ist, der eine Länge gleich wie oder kürzer als eine vorbestimmte Länge aufweist.
Informationssystem mit Objekten, Instanzen der Objekte, Beziehungen zwischen zumindest einigen der Objekte und den Instanzen der Objekte, umfassend: – Mittel zum Bereitstellen einer Instanz-Objekt-Bitmap, die anzeigt, ob Instanzen von Objekten mit anderen Objekten verknüpft sind; – Mittel zum Zugreifen auf die Bitmap, um zu bestimmen, ob eine Anfrage ein Ergebnis liefern wird, und – Mittel zum Unterrichten eines Benutzers, dass die Anfrage das Ergebnis liefern wird, wodurch vorhersagt wird, ob die Anfrage ein Ergebnis liefern wird; dadurch gekennzeichnet, dass die Einrichtung zum Bereitstellen der Instanz-Objekt-Bitmap Mittel zum Generieren der Instanz-Objekt-Bitmap durch Berechnen von Wegen von Instanzen zu benachbarten Objekten durch Bestimmen eines Weges von einer Instanz in einem Objekt zu einer Instanz in einem benachbarten Objekt und durch Berechnen eines Weges von einer Instanz zu einem nicht benachbarten Objekt durch Mischen eines Weges von einer Instanz in einem ersten Objekt zu einer Instanz in einem zweiten Objekt mit einem berechneten Weg von der Instanz in dem zweiten Objekt zu dem nicht benachbarten Objekt umfasst.
System gemäß Anspruch 5, worin die Instanz-Objekt-Bitmap anzeigt, ob eine Instanz eines Objektes mit anderen Objekten durch einen Verbindungsweg verknüpft ist, der eine Länge gleich wie oder kürzer als eine vorbestimmte Länge aufweist.
System gemäß Anspruch 5, das ferner Mittel zum Abbrechen einer Anfrage von einer Instanz an ein Objekt umfasst, wenn die Instanz-Objekt-Bitmap anzeigt, dass die Instanz nicht mit dem Objekt verknüpft ist.
System gemäß Anspruch 5, das ferner eine Datennavigator-Schnittstelle mit zumindest einem ziehbaren Element und zumindest einem Ablegeziel umfasst, wobei eine Anfrage generiert wird, wenn ein ziehbares Element gezogen und an einem Ablegeziel abgelegt wird.
System gemäß Anspruch 8, das ferner Mittel zum Abbrechen der Anfrage umfasst, wenn die Instanz-Objekt-Bitmap anzeigt, dass das ziehbare Element nicht mit dem Ablegeziel verknüpft ist.
System gemäß Anspruch 8, das ferner Mittel zum Darstellen an der Schnittstelle umfasst, dass eine Anfrage keinerlei Ergebnis liefern wird, wenn die Instanz-Objekt-Bitmap anzeigt, dass das ziehbare Element nicht mit dem Ablegeziel verknüpft ist.