DE69529088T2

DE69529088T2 - Verfahren und gerät für eine mehrdimensionale datenbank mit einem binären hyperräumlichen code

Info

Publication number: DE69529088T2
Application number: DE69529088T
Authority: DE
Inventors: Michael Galluchon; Edric Keighan; Herman P. Varma; A. Vretanos
Original assignee: Oracle Corp
Current assignee: Oracle Corp
Priority date: 1994-11-21
Filing date: 1995-10-31
Publication date: 2003-09-25
Anticipated expiration: 2015-11-01
Also published as: AU4199396A; EP0793831A1; EP0793831B1; CA2205836A1; WO1996016375A1; US6161105A; DE69529088D1; CA2205836C

Description

Hintergrund der Erfindung

1. Gebiet der Erfindung:

Die vorliegende Erfindung betrifft Verfahren und eine Einrichtung zum Speichern und Manipulieren mehrdimensionaler Daten und insbesondere betrifft die vorliegende Erfindung Datenbankstrukturen und Verfahren, bei denen räumliche Daten in dem Gerüst eines relationalen Datenbanksystems verwaltet werden.

2. Hintergrund:

Der Ort eines einzelnen Punktes im Raum kann durch eine Mehrzahl von Werten definiert sein. Diese "mehrdimensionalen Daten" können sowohl geographisch referenzierte Daten aus hydrologischen oder geologischen Messungen sein, aus dem Orbit oder von interplanetarischen Raumfahrzeugen gesammelte raum-basierende Daten, von computergestützten Konstruktions(CAD)-Systemen verwendete Daten als auch mehrdimensionale Geschäftsdaten wie beispielsweise für Entscheidungsunterstützungs-Systeme oder analytische Online-Bearbeitungssysteme erforderliche Daten. Die Daten können, abhängig von der Umgebung, einen hohen oder niedrigen relativen räumlichen Gehalt haben. Zum Beispiel sind hydrographische oder kartographische Daten nahezu ausschließlich räumlich, da jeder Datensatz einen Breitengrad, einen Längengrad, eine Höhe/Tiefe und gelegentlich eine Zeit umfaßt. Bei anderen Beispielen kann der räumliche Gehalt relativ gering sein, zum Beispiel bei einer Kundeninformationsdatenbank, bei der sich ein Ort in der Datenbank auf eins von vielen möglichen, einen Kunden betreffenden Datenbits beziehen kann.
Das Speichern und Manipulieren von räumlichen Daten in einem üblichen relationalen Datenbankverwaltungssystem liefert eine Vielzahl von Problemen. Da das relationale Datenbankverwaltungssystem ("RDBMS") eindimensional ist, muß jeder einen mehrdimensionalen Punkt betreffende Wert in einer einzelnen Spalte in der Datenbank gehalten werden. Indem jeder Wert in einer einzelnen Spalte gehalten wird, wird die Organisation der räumlichen Daten nicht bewahrt. Zusätzlich erfordert ein Suchen nach Datenpunkten in einem gegebenen mehrdimensionalen Raum unter Verwendung einer relationalen Datenbankstruktur einen erheblichen Rechenaufwand. Im Falle großer, zum Speichern von räumlichen Daten verwendeten relationalen Datenbanken ist die zum Auffinden und Manipulieren von räumlichen Daten erforderliche spaltenweise Suche (column by column range search) rechenintensiv und relativ langsam.
Ein Beispiel einer bekannten Anordnung ist beschrieben in H. P. Varma et al., "A structure for spatio-temporal databases", The International Hydrographic Review, Ausgabe 67, Nr. 1, Seiten 71-92, 1990.
Versuche, das Problem des Speicherns und des Verwaltens von räumlichen Daten in relationalen Datenbanksystemen zu lösen, führten zu Hybrid-Lösungen. Aus der Perspektive des relationalen Datenbankmodells ist die Verwendung von relationalen Datenbanksystemen für räumliche Daten ineffizient. Wie in Fig. 1 gezeigt ist, umfaßt eine Hybrid-Nährung zwei Datenbank-Engines nebeneinander, nämlich ein relationales Datenbankverwaltungssystem 50 und ein räumliches Datenbanksystem 55. Die RDBMS 50 hält nicht-räumliche Attributdaten. Ein Beispiel für Attributdaten sind der Wert für die Temperatur oder den Salzgehalt des Ozeans für einen dreidimensionalen Punkt im Pazifischen Ozean. Ein weiteres Beispiel nicht-räumlicher Attributdaten ist der Fluß kosmischer Strahlen durch einen Punkt im Raum zwischen der Erde und dem Mars. Wie in Fig. 1 dargestellt, ist die RDBMS 50 mit einer räumlichen Datenbank 55 verbunden, die entsprechende räumliche Daten mit räumlichen Indizes 57 referenziert oder verknüpft. Ein Beispiel eines bestehenden Hybrid-Systems ist eine von der Oracle-Corporation hergestellte RDBMS, die mit einer als ARC/Info bezeichneten räumlichen Datenbank verbunden ist. Die Oracle-ARC/Info-Hybrid-Datenbank wird zum Speichern und Verwalten kartographischer Projektionen und ähnlicher räumlicher Daten in Verbindung mit auf die räumlichen Daten bezogenen Attributen verwendet.
Ein in Fig. 1 gezeigter Hauptnachteil der Hybrid-Lösung ist das Erfordernis, sowohl zwei einzelne Datenbank-Engines als auch eine einzelne räumliche Indizes verwendende proprietäre Datenstruktur zu halten. Demzufolge stellt das Hybrid-System keine offen verteilte Datenbankarchitektur bereit, die einfach von einer Hybrid-Anwendung auf eine andere übertragbar ist. Darüber hinaus nimmt der Umfang und die Komplexität des Indizes zu, wenn die Größe der Datenbank zunimmt. Schließlich führt der rechnerische Mehraufwand zum Unterhalten dieses Indexes zu einer sich schnell verschlechternden Leistung, wenn neue Daten geladen werden und bestehende Datenbankdatensätze aktualisiert werden.
Die in Fig. 1 gezeigte Hybrid-Lösung wurde bei einem geographischen Informationssystem ("GIS") angewendet, das zum Manipulieren räumlicher Objekte unter Verwendung einer begrenzten zweidimensionalen Implementierung erzeugt wurde. Es existieren verschiedene derartige Hybrid-Systeme, jedes mit seinen eigenen einmaligen proprietären Techniken zum Definieren und Manipulieren räumlicher Daten. Es ist daher für den Benutzer eines Systems schwierig, auf Daten in einem anderen zuzugreifen, da das Format zum Speichern der Daten inkompatibel ist. Dieses führte zu der Entwicklung von "Austausch"-Standards, die ein "Standarddatenformat" definieren, das ein Lesen von mit einem System erzeugten Daten durch ein anderes ermöglicht, wenn diese durch ein dazwischenliegende Übersetzung in/aus ein/einem Austausch-Format geleitet werden. Das Ergebnis ist eine "Spaghettinetz"-Dateninfrastruktur von proprietären Datenformaten, die Daten mit anderen Systemen über hinderliche Übersetzung-In- und Übersetzung- Aus-Austauschformate ausgetauscht.
Die vorliegende Erfindung stellt ein verbessertes Verfahren und eine verbesserte Einrichtung zum Speichern, Manipulieren und Abrufen räumlicher und nicht-räumlicher Daten in einer Datenbank zur Verfügung. Die vorliegende Erfindung umfaßt eine als hydrographischer Hyperraum-Code ("HH-Code") bezeichnete Verbesserung an einer Datenstruktur. Die HH- Code-Grundstruktur wurde ursprünglich von H. P. Varma in einer Veröffentlichung mit dem Titel "A Strucaure for Spatial- Temporal Databases", International Hydrographic Review, Monaco LXVII (1) (Januar 1990) veröffentlicht (nachfolgend die "Varma-Veröffentlichung"). Der von Varma gelehrte HH- Code ist eine Datenstruktur auf der Grundlage einer Linearisierungstechnik, die die dimensionale Organisation von mehrdimensionalen Daten in den Daten selber hält, wodurch wesentliche Vorteile gegenüber sowohl der Hybrid- als auch üblichen RDBMS-Datenstrukturen zur Verfügung gestellt werden.
Die vorliegende Erfindung ist, wie es beschrieben wird, eine Verbesserung gegenüber der ursprünglichen, in der Varma-Veröffentlichung beschriebenen HH-Code-Datenstruktur. Die erfindungsgemäße Implementierung und Verwendung von binärem Hyperraum-Code ("BH-Code") überwindet die bekannten, der RDBMS innewohnenden Begrenzungen bezüglich effizientem Speichern, Manipulieren und Abrufen räumlicher Daten. Das erfindungsgemäße Datenbankverfahren und die erfindungsgemäße Datenbankeinrichtung sorgen für die nahtlose Handhabung von sowohl räumlichen als auch nicht-räumlichen Daten in derselben Datenbank und begründen eine wesentliche Verbesserung auf dem Gebiet der Datenbankstrukturen und -verwaltung.

Zusammenfassung der Erfindung

Die vorliegende Erfindung beschreibt eine verbesserte mehrdimensionale Datenbank, wobei räumliche Daten in dem Gerüst eines relationalen Datenbanksystems verwaltet werden. Die vorliegende Erfindung verwendet einen binären Hyperraum- Code (BH-Code), der als eine N-dimensionale Baumstruktur ausgelegten unter Verwendung einer rekursiven Zerlegungstechnik abgeleitet ist. Eine Gesamtheit von Daten wird rekursiv zerlegt, um einen gewünschten Grad der Auflösung zu erhalten, der der dezimalen Genauigkeit der Daten entspricht. Ein Punkt wird als sich in einem Bereich aufhaltend verstanden, was in dem Fall von drei Dimensionen zu dem Bereich mit der Form eines Würfels führt. N Dimensionen können unter Verwendung der erfindungsgemäßen binären BH-Code-Datenstruktur dargestellt werden. Die erfindungsgemäße BH- Code-Datenstruktur linearisiert mehrere Dimensionen in einen einzelnen BH-Code-Wert. Die erfindungsgemäße Verwendung von BW-Code gewährleistet sowohl die räumliche Organisation der Daten als auch jeder Dimension, wodurch der BH-Code in eine einzelne linearisierte Datenstruktur gefaßt wird. Jeder der BH-Code-Werte kann bis zu M sich auf die BW-Code-Daten beziehende Attribute aufweisen. Diese Attribute sind benutzerdefiniert und entsprechen physikalischen Charakteristika wie beispielsweise der Temperatur, dem Fluß kosmischer Strahlung, dem Salzgehalt und ähnlichem oder können nichtphysikalischen Daten wie beispielsweise Geld, Interessenslage, Kundennamen und -listen etc. entsprechen. Unter Verwendung der binären BH-Code-Datenstruktur gehaltene räumliche Daten gewährleisen die räumliche Organisation der Daten unabhängig von einem formalen Index. Eine mehrdimensionale Tabelle ist eine als eine partitionierte Tabelle bezeichnete logische Tabelle, die aus einer oder mehreren Partitionen oder Tabellen besteht. Jede Partition stellt einen eindeutigen begrenzten N-dimensionalen Raum dar, wobei alle Daten in einer Partition in der gleichen begrenzten Region des Raumes bestehen.
Ein automatisches Tabellenpartitionierungsschema umfaßt einen Grenzwert, der derart für die gesamte Mehrdimensionen- Tabelle gesetzt ist, daß, wenn der Grenzwert überschritten ist, automatisch ein Satz von Kinder-Partitionen aus den Eltern erzeugt wird und die Eltern anschließend gelöscht werden. Der Grenzwert stellt das maximale Datenvolumen dar, das in einer Partition gespeichert werden kann. Unter Verwendung des erfindungsgemäßen automatischen Datenpartitionierungsschemas werden im Raum gehäufte Datenpunkte in der gleichen Partition angeordnet. Jede Partition stellt einen unterschiedliche räumlichen Bereich dar und die räumlichen Charakteristika der Daten werden beibehalten. Beim Laden werden Mehrdimensionen-Datenpartitionen auf der Grundlage der für eine BH-Code-Datenstruktur definierten Anzahl von Dimensionen und des das Datenvolumen pro Partition definierenden Grenzwertes erzeugt. Damit umfaßt die erfindungsgemäße Datenbank eine Mehrzahl von Partitionen mit Einträgen von BH-Code und ihre entsprechenden Attribute überschreiten niemals den Grenzwert.
Ein Datenwörterbuch wird erzeugt, das ein Laden und einen Zugriff auf Daten in die und aus der Datenbank vereinfacht. Das Datenwörterbuch umfaßt eine Tabelle, die eine Liste sämtlicher in einer entsprechenden relationalen Datenbank-Engine gespeicherten Partitionen, die als mehrdimensional betrachtet werden, umfaßt. Die relationale Datenbank speichert sowohl eine Liste räumlicher als auch nichträumlicher Daten. Das Datenwörterbuch umfaßt zwei Klassen von Tabellen, nämlich partitionierte und nicht-partitioniere Mehrdimensionen-Tabellen. Nicht-partitionierte Mehrdimensionen-Tabellen entsprechen üblichen relationalen Datenbanktabellen mit einer oder mehreren räumlichen Spalten. Partitionierte Tabellen entsprechen mehrdimensionalen Tabellen, die ferner eine oder mehrere räumliche Spalte(n) aufweisen, aber auf der Grundlage einer räumlichen Spalte partitioniert sind. Eine partitionierte Multidimensionen-Tabelle weist eine Reihe von Partitionen auf, die unter Verwendung des erfindungsgemäßen automatischen Datenpartitionierungsschemas in Kind-Partitionen zerlegt werden. Jeder Eintrag in dem Datenwörterbuch umfaßt neben anderen Dingen eine Objektnummer, einen Partitionsnamen und die mehrdimensionale Erweiterung jeder Partition unter Verwendung von BH-Code-Werten. Es werden Verfahren zum Zugreifen auf Daten beschrieben, die in einem von einem Benutzer definierten mehrdimensionalen Fenster angeordnet sind.
Die vorliegende Erfindung stellt ferner Verfahren zum Verwenden von binärem BH-Code zum Darstellen, Speichern, Manipulieren und Abrufen zweidimensionaler Zeilen und topologischen Daten zur Verfügung. In dem Fall von Zeilen wird ein Zeilensegment als ein vierdimensionaler BH-Code-Wert dargestellt. Das Laden eines Zeilensegmentes in die erfindungsgemäße Datenbank verläuft analog zu dem Vorgang des Ladens von Punktdaten oder Bereichsdaten. Die Zeilen werden unter Verwendung einer gesonderten mehrdimensionalen Tabelle in die Datenbank geladen. Ein Grenzwert wird derart gesetzt, daß die Kind-Partitionen automatisch unter Verwendung des erfindungsgemäßen automatischen Datenpartitionierungsschemas erzeugt werden. Es wird ferner ein Verfahren zum Zugreifen auf in der Datenbank gespeicherte Zeilendaten zur Verfügung gestellt, das die Definition von Partitionsformen umfaßt, denen eine Zeile entsprechen kann. Eine Partitionsliste wird erzeugt und die Partitionsformen werden entschlüsselt. Es wird ermittelt, ob die Partitionsformen mit von dem Benutzer definierten Bereichen überlappen oder nicht. Eine Liste der überlappenden Partitionen wird anschließend kompiliert und in dem definierten Bereich befindliche Datensätze werden bestimmt. Die von BH-Code-Werten definierten Datensätze, die in dem von dem Benutzer definierten Bereich angeordnet sind, werden dem Benutzer berichtet. Es wird hier ferner Verfahren zum Verwalten von komplexeren, Topologie darstellenden räumlichen Objekten beschrieben.

Kurzbeschreibung der Zeichnungen

Fig. 1 zeigt ein bekanntes Hybrid-System, bei dem ein relationales Datenbankverwaltungssystem und eine räumliche Datenbank durch Indizes verbunden sind.
Fig. 2 zeigt ein mögliches Computersystem, das die erfindungsgemäßen Lehren umfaßt.
Fig. 3 zeigt die erfindungsgemäße Verwendung der rekursiven Zerlegung.
Fig. 4 zeigt konzeptionell die erfindungsgemäße Verwendung des BH-Codes in Verbindung mit Attributen.
Fig. 5 zeigt die erfindungsgemäße Verwendung der rekursiven Zerlegung auf höheren Ebenen zum Erzielen einer größerem Auflösung.
Fig. 6 zeigt ein eindimensionales Beispiel der erfindungsgemäßen Verwendung des BH-Codes.
Fig. 7 zeigt die erfindungsgemäße Verwendung des BH-Codes in zwei Dimensionen.
Fig. 8 zeigt die erfindungsgemäße Verwendung des BH-Codes in drei Dimensionen.
Fig. 9 zeigt die Umwandlung von Rohdaten in BH-Code gemäß den Lehren der vorliegenden Erfindung.
Fig. 10 zeigt das erfindungsgemäße Datenpartitionierungsschema, wobei eine Eltern-Partition automatisch in Kinder-Partitionen zerlegt wird.
Fig. 11 zeigt schematisch die erfindungsgemäße Zerlegung eines gegebenen Bereichs in zweidimensionale Quadranten in Verbindung mit der Erzeugung von BH-Code/Attribut-Partitionen und dem Setzen eines Grenzwertes.
Fig. 12 zeigt schematisch die erfindungsgemäße automatische Datenpartitionierung für die Erzeugung von Kind-Partitionen und die rekursive Zerlegung eines zweidimensionalen Quadranten in zusätzliche Quadranten, wenn die Anzahl der Datenpunkte den gesetzten Grenzwert überschreitet.
Fig. 13 zeigt schematisch die rekursive Zerlegung eines zweidimensionalen Quadranten in zusätzliche Quadranten, wenn zusätzliche zweidimensionale Datenpunkte, die hinzugefügt worden sind, den Grenzwert überschreiten, und die Erzeugung von zusätzlichen Kind-Partitionen mit dem erfindungsgemäßen automatischen Datenpartitionierungsschema.
Fig. 14 zeigt schematisch die lineare Anordnung von Partitionen, die bei den in den Fig. 11, 12 und 13 gezeigten Vorgängen erzeugt wurden.
Fig. 15 zeigt sowohl die erfindungsgemäße BH-Code-Datenstruktur als auch bei dem bevorzugten Ausführungsbeispiel zur Verfügung stehende Kernfunktionen.
Fig. 16 zeigt eine Blockdarstellung der Implementierung der Erfindung unter Verwendung eines dem in Fig. 2 gezeigten ähnlich seienden Computersystems.
Fig. 17 zeigt eine Blockdarstellung des erfindungsgemäßen Datenwörterbuchs als Metadaten-Unterstützung für in einem relationalen Datenbanksystem gehaltenen mehrdimensionalen Daten.
Fig. 18 zeigt konzeptionell das erfindungsgemäße Datenwörterbuch bei der Verwendung in Verbindung mit einer automatischen Datentabellenpartitionierung.
Fig. 19 zeigt den Betrieb der vorliegenden Erfindung beim Datenzugriff.
Fig. 20(a) und Fig. 20(b) zeigen die erfindungsgemäße Verwendung des BH-Codes zum Definieren eines Zeilensegments.
Fig. 21(a) und Fig. 21(b) zeigen konzeptionell die erfindungsgemäße Erzeugung von sechszehn Partitionsformen für den Fall eines Zeilensegments.
Fig. 22(a), 22(b) und 22(c) zeigen die von der vorliegenden Erfindung zum Datenzugriff und zum Laden von Zeilensegmenten verwendeten sechszehn Partitionsformen.
Fig. 23 zeigt eine Region, durch die sich Zeilensegmente teilweise oder vollständig erstrecken.
Fig. 24 zeigt konzeptionell die Schnittmenge der Innenräume und der Begrenzungen von Objekten.
Fig. 25 zeigt eine Tabelle der erfindungsgemäßen Verwendung eines Vier-Schnittmengen-Verfahrens für die Implementierung von topologischen Beziehungsoperationen.
Fig. 26(a) und 26(b) zeigen konzeptionell die erfindungsgemäße Implementierung von BH-Code zum Darstellen und Betreiben oben genannter Topologie.

Bezeichnungen und Thermenologie

Die folgende detaillierte Beschreibung ist weitgehend in Form von algorithmischen und symbolischen Darstellungen des Bearbeitens von Datenbits in einem Computerspeicher dargestellt. Diese algorithmischen Beschreibungen und Darstellungen sind die von Fachleuten auf dem Gebiet der Datenverarbeitung verwendeten Mittel, um den Inhalt ihrer Arbeit anderen Fachleuten möglichst effektiv mitzuteilen.
Ein Algorithmus wird hier und allgemein als eine selbstkonsistente Sequenz von zu einem gewünschten Ergebnis führenden Schritten verstanden. Diese Schritte sind es, die eine physikalische Manipulation von physikalischen Größen erfordern. Üblicherweise aber nicht notwendigerweise sind diese Größen in Form von elektrischen oder magnetischen Signalen gegeben, die gespeichert, übertragen, kombiniert, verglichen und anderweitig manipuliert werden können. Es erweist sich zeitweise als zweckmäßig, gewöhnlich aus Gründen der allgemeinen Verwendung, diese Signale als Bits, Werte, Elemente, Symbole, Zeichen, Ausdrücke, Speicherzellen, Anzeigeelemente oder ähnliches zu bezeichnen. Es sollte jedoch bedacht werden, das all diese und ähnliche Ausdrücke den entsprechenden physikalischen Größen zuzuordnen sind und lediglich geeignete Bezeichnungen für diese Größen anzuwenden sind.
Ferner werden die durchgeführten Manipulationen oftmals mit Ausdrücken wie beispielsweise hinzuführen, vergleichen, verschlüsseln oder entschlüsseln bezeichnet, die üblicherweise den Gedankengängen eines menschlichen. Betreibers zugeordnet sind. Bei keiner der hierin beschriebenen Operationen, die einen Teil der vorliegenden Erfindung bilden, ist eine derartige Fähigkeit eines menschlichen. Bedieners notwendig oder in vielen Fällen wünschenswert; die Operationen sind Maschinenoperationen. Verwendbare Maschinen zum Ausführen der Operationen der vorliegenden Erfindung umfassen Universalcomputer oder ähnliche Einrichtungen. In allen Fällen soll der Unterschied zwischen den Verfahrensoperationen beim Betreiben eines Computers und dem Verfahren der Rechnung selbst beachtet werden. Die vorliegenden Erfindung betrifft Verfahrensschritte zum Betreiben eines Computers und Verarbeiten von elektrischen oder anderen physikalischen Signalen, um andere gewünschte physikalische Signale zu erzeugen.
Die vorliegende Erfindung betrifft ferner eine Einrichtung zum Ausführen dieser Operationen. Diese Einrichtung kann für die gewünschten Zwecke speziell konstruiert sein oder sie kann einen Universalcomputer aufweisen, der von einem in dem Computer gespeicherten Computerprogramm selektiv aktiviert oder rekonfiguriert wird. Die hierin dargestellten Algorithmen betreffen an sich keinen bestimmten Computer oder andere Einrichtung. Insbesondere können verschiedene Universalmaschinen mit der erfindungsgemäßen Lehre verwendet werden oder es kann sich als praktischer erweisen, spezialisierte Einrichtungen zum Ausführen der erforderlichen Verfahrensschritte herzustellen. Die für eine Vielzahl dieser Maschinen erforderliche Struktur wird aus der weiter unten gegebenen Beschreibung deutlich.

Kodierungsdetails

Hierin wurde keine bestimmte Programmiersprache zum Ausführen der verschiedenen Prozeduren aufgezeigt. Dies ist teilweise der Fall, da nicht alle Sprachen, die erwähnt werden könnten, allgemein verfügbar sind. Jeder Benutzer eines bestimmten Computers wird eine Sprache kennen, die für seine unmittelbaren Zwecke am geeignetsten erscheint. Da die zum Ausführen der Erfindung verwendbaren Computer aus einer Vielzahl unterschiedlicher Elemente bestehen, wurde kein detaillierter Programmausdruck bereitgestellt. Es wird angenommen, daß die hierin beschriebenen und in den begleitenden Zeichnungen gezeigten Operationen und andere Prozeduren ausreichend beschrieben sind, um dem Durchschnittsfachmann ein Ausführen der Erfindung oder eines von ihm benötigten Teils zu ermöglichen.

Detaillierte Beschreibung der Erfindung

Die folgende detaillierte Beschreibung ist in mehrere Abschnitte aufgeteilt. Der erste von diesen beschreibt eine allgemeine Systemanordnung zum Speichern, Abrufen und Manipulieren von räumlichen und nicht-räumlichen Daten unter Verwendung der erfindungsgemäßen Datenbankstruktur. Dieser erste Abschnitt beschreibt ferner die erfindungsgemäße Implementierung einer binären BH-Code-Datenstruktur. Folgende Abschnitte beschreiben eine Einrichtung und Verfahren zum Datenpartitionieren und zum Datenzugriff und Laden unter Verwendung der erfindungsgemäßen Implementierung des BH-Codes. Zusätzliche Abschnitte beschreiben ferner die erfindungsgemäße Verwendung der BH-Code-Datenstruktur für topologische Systeme wie beispielsweise dreidimensionale Kartographie.
Bei der folgenden Beschreibung werden zahlreiche Details wie beispielsweise algorithmische Konventionen, spezielle Speicherzellen, Sammlungen von Zellen, Attribute, Dimensionen und Datenstrukturen etc. dargelegt, um für ein eingehendes Verständnis der vorliegenden Erfindung zu sorgen. Für Fachleute ist es jedoch ersichtlich, daß die vorliegende Erfindung ohne diese speziellen Details ausgeführt werden kann. Bei anderen Beispielen werden bekannte Schaltungen, Strukturen und elektronische Komponenten nicht detailliert beschrieben, um die vorliegende Erfindung nicht unnötig zu verkomplizieren.

Allgemeine Systemkonfiguration

Fig. 2 zeigt ein übliches computerbasiertes System zum Implementieren der vorliegenden Erfindung. Es wird ein Computer 60 mit drei Hauptkomponenten gezeigt. Die erste von diesen ist die Eingabe/Ausgabe(I/O)-Schaltung 62, die zum Übermitteln von Informationen in entsprechend strukturierter Form zu und von anderen Teilen des Computers 60 verwendet wird. Ferner wird als ein Teil des Computers 60 die zentrale Verarbeitungseinheit (CPU) 64 und ein Speicher gezeigt. Die letzteren zwei Elemente sind üblicherweise in den meisten Universalcomputern und fast allen Spezialcomputern zu finden. Tatsächlich sollen die verschiedenen in dem Computer 60 enthaltenen Elemente repräsentativ für diese breite Gruppe von Datenprozessoren sein. Spezielle Beispiele von als Computer 60 geeigneten Datenprozessoren umfassen von Sun Microsystems Inc. und Silicon Graphics, beide in Californien angesiedelt, hergestellte Maschinen. Andere Computer mit ähnlichen Fähigkeiten können auf eine sehr ähnliche Weise verwendet werden, um die verschiedenen weiter unten beschriebenen Funktionen auszuführen.
Ferner ist in Fig. 2 eine in einem üblichen Ausführungsbeispiel als eine Tastatur gezeigte Eingabeeinrichtung 68 gezeigt. Es sollte jedoch verständlich sein, daß die Eingabeeinrichtung tatsächlich auch ein Kartenleser, ein Magnetbandleser oder ein anderes bekanntes Eingabegeräte (einschließlich eines anderen Computers) sein kann. Eine Massenspeichereinrichtung 70 ist mit der I/O-Schaltung 62 verbunden. Der Massenspeicher 70 kann zum Speichern aller oder eines Teils des die vorliegende Erfindung implementierenden Computerprogramms oder anderer Programme verwendet werden und kann in Form eines Festplattenlaufwerks, einer optischen Speicherplatte oder anderer bekannter Massenspeichereinrichtungen vorliegen. Es wird deutlich, daß die in dem Massenspeicher 70 gehaltenen Daten in entsprechenden Fällen auf eine übliche Art im Computer 60 als Teil des Speichers 66 enthalten sein können.
Ferner ist eine "Maus"-Eingabeeinrichtung 72 gezeigt, die dem Benutzer auf bekannte Art eine Eingabe graphischer Informationen über die I/O-Schaltung 62 in den Computer 60 ermöglicht. Üblicherweise stellt die Maus 72 eine Cursor- Steuerung zum Identifizieren und Anordnen eines Cursors auf einem Anzeigebildschirm zur Verfügung. Eine Kathodenstrahlröhre(CRT) ist gezeigt, die zum Anzeigen der durch die vorliegende Erfindung erzeugten Bilder verwendet wird. Ein derartiger Anzeigemonitor kann die Form eines beliebigen der verschiedenen bekannten Arten von Bildschirmen haben.

Daten vom binären Hyperraum-Code(BH-Code)-Typ

Die vorliegende Erfindung verwendet eine verbesserte HH- Code-Datenstruktur. In der ursprünglichen Varma-Veröffentlichung vom Januar 1990 ist die beschriebene Datenstruktur auf eine Implementierung auf der Grundlage von Zeichen beschränkt und kann höchstens fünf Dimensionen unterstützen. Ferner ist die in der Varma-Veröffentlichung beschriebene ursprüngliche Datenstruktur speicherineffizient. Ein weiterer Nachteil der ursprünglichen Varma-HH-Code-Datenstruktur ist, daß sie auf der Anwendungsebene implementiert wird und lediglich ein einfaches Datenwörterbuch verwendet. Wie es beschrieben wird, implementiert die vorliegende Erfindung eine verbesserte binäre Datenstruktur, die die Schnittmenge eines Punktes in mehreren Dimensionen darstellt. Ein einzelner eindeutiger BH-Code-Wert hält alle ursprünglichen Datenwerte mit voller Genauigkeit und gewährleistet ohne die Notwendigkeit des Erzeugens und Erhaltens einer separaten Indexstruktur die räumliche Organisation der Daten. Wie es darüber hinaus beschrieben wird, ermöglicht die verbesserte erfindungsgemäße BH-Code-Datenstruktur das Ausbilden von Zeilensegmenten und die Bearbeitung topologischer Beziehungsoperatoren.
Es wird nun auf Fig. 3 Bezug genommen. Die erfindungsgemäße BH-Code-Datenstruktur ist in zwei Dimensionen als eine unter Verwendung der rekursiven Zerlegung erhaltene vierfache Baumstruktur ausgebildet. Bei dem in Fig. 3 gezeigten Beispiel wurde die Welt in zwei Dimensionen abgeflacht, wobei jeder Bereich der Welt in Quadranten zerlegt werden kann. Auf einer ersten Ebene ist die Welt in vier Quadranten (zunächst die Quadranten 0, 1, 2 und 3) unterteilt. Folglich kann der BH-Code als eine geordnete Aufteilung des Objektraums verstanden werden. Bei der Gesamtheit der Daten (bei dem Beispiel von Fig. 3 besteht die Gesamtheit aus einer Weltkarte) kann eine Unterteilung bis zu einer benutzerdefinierten Ebene fortgesetzt werden. Diese Unterteilung kann als eine Auflösung oder Genauigkeit der Daten verstanden werden. Wie durch Fokussieren in einen bestimmten Bereich (zum Beispiel den durch die Ziffer 90 gekennzeichneten Bereich) gezeigt, ist der interessierende Bereich, nämlich Nord Amerika bei dem vorliegenden Beispiel, sequentiell und rekursiv in Quadranten (0, 1, 2, 3) unterteilt. Ein Punkt kann verstanden werden als sich in einem kleinen Bereich aufhaltend, was in dem Fall von drei Dimensionen zu einem Bereich mit der Form eines Würfels oder eines dreidimensionalen Rechtecks führt. Damit gibt es, abhängig von der erwünschten Auflösung, keine theoretische Begrenzung der möglichen Zerlegung. Aus praktischen Gründen wird der Grad der rekursiven Zerlegung von dem jeweiligen verwendeten Computersystem begrenzt sein, in dem die Daten gespeichert sind. Für geographische Daten würde eine Auflösung von 9,3 · 4,7 mm auf der Erdoberfläche erfordern, daß eine BH-Code-Datenstruktur rekursiv bis Ebene 32 zerlegt wird.
Es wird nun auf Fig. 4 Bezug genommen. Beim Verwenden eines standardmäßigen relationalen Datenbankmodells (bezeichnet mit der Ziffer 92) werden neben einem oder mehr Attributen (zum Beispiel Temperatur, Salzgehalt, Energie etc.) mehrdimensionale Daten üblicherweise in in der Figur als DIM(1) und DIM(2) bezeichneten Spalten gehalten. Unter Verwendung der Lehren des erfindungsgemäßen BH-Codes werden DIM(1) und DIM(2) als ein einzelnes Element in der Form von BEI-Code gehalten, der die Schnittmenge dieser beiden Dimensionen darstellt. Es ist verständlich, daß, wenn die Anzahl der Dimensionen zunimmt, die Komplexität der ein übliches RDBMS verwendenden Tabelle 92 ebenfalls zunimmt: Auch bei N Dimensionen jedoch fügt die erfindungsgemäße binäre BH-Code- Darstellung der Mehrdimensionen-Daten keine Spalten zu der Datenbank hinzu und hält sämtliche dimensionalen Informationen in der Form eines einzelnen BH-Code-Eintrages. Wie es beschrieben wird, wird der BH-Code folglich zu einem Hyperraum-Schlüssel mit Attributen. Bei dieser Beschreibung können mehr Dimensionen als eine Anzahl von unabhängigen Vektoren definiert sein. Ein Beispiel eines nulldimensionalen Raums ist ein Punkt. Ein eindimensionaler Raum kann eine Linie oder der Rand eines Kreises sein. Ein zweidimensionaler Raum kann eine offene oder geschlossene Scheibe oder deren topologische Bilder sein. Eine wichtige Eigenschaft eines N- dimensionalen Raums ist, daß er Elemente mit N Dimensionen enthalten kann. Ein Objekt weist die gleichen Dimensionen N auf wie der das Objekt kodierende Raum, wenn das Objekt in diesem Raum existiert. Der BH-Code linearisiert mehrere Dimensionen in eine einzelne BH-Code-Zahl.
Es wird nun Bezug genommen auf Fig. 5, in der der erfindungsgemäße rekursive Zerlegungsvorgang detaillierter gezeigt ist. Eine Gesamtheit von Daten ist wie gezeigt in dem mit "00" bezeichneten Bereich definiert. Auf Ebene 1 ist der Bereich "00" in vier Unterbereiche "00", "01", "10" und "11" zerlegt. Wenn zum Beispiel in Bereich "01" eine höhere Auflösung erwünscht ist, dann wird der Bereich "01" weiter in eine zweite und dritte Ebene mit "0100", "0101", "0110" und "0111" zerlegt.
Es wird nun auf Fig. 6 Bezug genommen. Die BH-Code-Kodierung umfaßt eine binäre Struktur, deren eine Dimension als (geographische) Länge bezeichnet werden kann. Der BH- Code stellt eine binäre Zerlegung jeder entweder eine "Wahr"- oder "Falsch"-Aussage darstellenden Dimension dar. Wenn die Breite zusätzlich zu der Länge hinzugefügt ist, wie es in Fig. 7 gezeigt ist, dann ist die Breiten-Dimension unterteilt, wobei zwei Bits zum Darstellen der zwei Dimensionen in dem Breite/Länge-Raster verwendet werden. Die Schnittmenge der Länge und der Breite in dem unteren linken Quadranten führt zu "00", wohingegen die Schnittmenge in dem oberen rechten Quadranten durch "11" dargestellt ist. Es wird nun auf Fig. 8 Bezug genommen. Wenn eine dritte Dimension wie beispielsweise die Höhe hinzugefügt wird, werden drei Bits verwendet, um jede der den als die Region 95 bezeichneten Würfel aufweisenden würfelförmigen Regionen darzustellen. Den Fachleuten ist ersichtlich, daß jedes der drei Bits einen einzelnen Wert darstellt, wobei die Schnittmenge der drei Bits einen darin angeordneten dreidimensionalen Raum eindeutig identifiziert, und einen Teil des größeren würfelförmigen Bereichs 95 bildet. Der kubische Raum mit einem binären BH-Code von 011 zum Beispiel ist fett gezeigt und in der Figur durch die Ziffer 3 gekennzeichnet. Es ist ferner ersichtlich, daß der binäre BH-Code der Nummerierung der Unterwürfel innerhalb des größeren kubischen Bereichs 95 entspricht. Die Binärzahl 111 entspricht dem Würfel 7 in dem würfelförmigen Bereich 95. Bei dem in Fig. 8 gezeigten Beispiel erstreckt sich die Länge von -180º bis +180º, die Breite von -90º bis +90º und die Höhe von -5 km bis +1 km. Der zum Beispiel den BH-Code 011 identifizierende Würfel "3" in Fig. 8 stellt ein Raumvolumen zwischen der Breite 0-90º und der Länge 0-180º und zwischen der Höhe -5 km bis -2 km dar.
Den Fachleuten ist ersichtlich, daß die Verwendung des binären BH-Codes sowohl die räumliche Organisation der Daten als auch die Daten selbst erhält. Unter Verwendung des in Fig. 8 gezeigten Beispiels kann die Dichte der kosmischen Strahlung mit einer durch die Dimensionen jedes der Würfel in dem würfelförmigen Bereich 95 definierten Auflösung gemessen werden. Der Würfel mit dem BH-Code 011 stellt ein Raumvolumen dar. Für eine feinere Auflösung wird die erfindungsgemäße Verwendung der rekursiven Zerlegung derart angewendet, daß jeder der Würfel der Reihe nach in acht zusätzliche würfelförmige Bereiche in beispielsweise dem Würfel 011 zerlegt wird. Obwohl die vorliegende Erfindung unter Bezugnahme auf die Figuren in drei Dimensionen beschrieben ist, ist es ersichtlich, daß die vorliegende Erfindung in N Dimensionen verwendet werden kann. Es sei daran erinnert, daß BH-Codes den Ort eines Punktes in einem N-dimensionalen Raum identifizieren. Wie es in Fig. 4 gezeigt ist, weist jeder der BH-Codes bis zu M Attribute auf, die sich auf den von dem BH-Code identifizierten Punkt (oder genauer der Bereich) im Raum beziehen. Diese Attribute sind benutzerdefiniert und können physikalischen Charakteristika entsprechen. Zum Beispiel können die Attribute Messungen der Temperatur, des Salzgehaltes, des Flußes kosmischer Strahlung und ähnliches umfassen oder nicht-physikalischen Daten wie beispielsweise Geld, Interessenslage, Kundennamen und -listen etc. entsprechen. Demzufolge stellt der BH-Code einen Bereich dar, der abhängig von der gewünschten Auflösung in einer Größenordnung von mikroskopisch bis makroskopisch liegen kann. Darüber hinaus ist die von der Erfindung gelehrte BH- Kodierung eine Datenstruktur auf der Grundlage eines Bits und nicht auf die anfänglich in der Varma-Veröffentlichung beschriebene zeichenbasierende Implementierung begrenzt. Darüber hinaus ist der HH-Code gemäß der Varma-Veröffentlichung von Varma implementiert und auf höchstens fünf Dimensionen begrenzt. Die erfindungsgemäße Verwendung des BH-Codes ist nicht auf Zeichen oder eine beliebig festgesetzte Anzahl von Dimensionen begrenzt.
Es wird nun auf Fig. 9 Bezug genommen, in der ein weiteres Beispiel der Verwendung des BH-Codes zur Verfügung gestellt wird. Exemplarisch sei angenommen, daß Rohdaten wie in der Figur gezeigt bereitgestellt werden. Der erfindungsgemäße erste Schritt ist es, einen BH-Code für die bereitgestellten Daten zu bestimmen. Der den Rohdaten entsprechende Bereich in Fig. 9 ist allgemein mit der Ziffer 98 bezeichnet. Wie gezeigt halten sich die Rohdaten in drei Quadranten in dem definierten Bereich auf, nämlich den Quadranten 00, 20 und 31. Mit P&sub0;, P&sub2; und P&sub3; bezeichnete Partitionen werden erzeugt. P&sub0; umfaßt wie gezeigt einen einzelnen Eintrag des BH-Codes 00, P&sub2; einen einzelnen Eintrag für den BH-Code 20 und die Partition P&sub3; umfaßt zwei als 3123 und 3130 bezeichnete Einträge. Die Erzeugung von Datenpartitionen ist genauer in dem folgenden Abschnitt mit dem Titel Datenpartitionierung beschrieben. Es sei daran erinnert, daß die BH-Codes einen bestimmten Bereich im Raum kennzeichnen, auf den sich bestimmte Attribute beziehen. Zum Beispiel kann der Ort mit dem BH-Code 3130 einen Bereich im Ozean mit den Attributen Temperatur und Salzgehalt entsprechen. Für Fachleute ist ersichtlich, daß die Auswahl der Attribute und die Anzahl der Attribute eine Frage der Gestaltungswahl auf der Grundlage der Anwendung ist, mit der die vorliegende Erfindung verwendet wird.

Datenpartitionierung unter Verwendung von BH-Code

Unter Verwendung von BH-Code verwaltete räumliche Daten können als N-dimensionale Speicherbereiche angesehen werden, die nicht-räumliche Daten enthalten können. Einer der Hauptvorteile der erfindungsgemäßen binären BH-Code-Datenstruktur ist ihre Fähigkeit, die räumliche Organisation der Daten unabhängig von einer formalen Indexdatenstruktur zu gewährleisten. In der Tat ordnet eine gängige Binär-Sortierung, angewendet auf unter Verwendung des binären BH-Codes dargestellte räumliche Daten, diese Daten basierend auf der Anzahl der Dimensionen des BH-Codes räumlich an. Eine mehrdimensionale Tabelle ist eine als eine partitionierte Tabelle bezeichnete logische Tabelle, die aus einer oder mehreren Partitionen besteht. Jede Partition stellt einen eindeutig begrenzten N-dimensionalen Raum dar, wobei sämtliche Daten in einer Partition in den gleichen begrenzten Raumbereich existieren.
Das erfindungsgemäße automatische Datenpartitionierungsschema ist in Fig. 10 konzeptionell gezeigt. Wie es nachfolgend genauer beschrieben wird, sind die BH-Code-Daten und ihre entsprechenden Attribute in räumlich organisierten Partitionen (die hier zuweilen als "Tabellen" bezeichnet werden) gespeichert. Ein "Grenzwert" ist für jeden mehrdimensionalen Speicherbereich gesetzt, so daß eine Kind-Partition aus der Eltern-Partition erzeugt wird, wenn der Grenzwert überschritten wird. Der Grenzwert stellt das größte Datenvolumen dar, das in einer beliebigen, einem mehrdimensionalen Speicherbereich entsprechenden Partitionen gespeichert werden kann. Wie es in Fig. 10 konzeptionell gezeigt ist, kann der Grenzwert überschritten werden, wenn der BH-Code und die entsprechenden Attribute in einer Eltern-Partition gespeichert werden, was zu der Erzeugung der Datenpartitionen 0-3 führt. Ein einzigartiges Merkmal des erfindungsgemäßen Datenpartitionierungsschemas ist, daß im Raum angehäufte Datenpunkte in der gleichen Partition angeordnet sind. Demzufolge stellt jede Partition einen unterschiedlichen räumlichen Bereich dar und die räumlichen Charakteristika der Daten bleiben erhalten. Aus der folgenden Beschreibung wird ersichtlich, daß das erfindungsgemäße Datenpartitionierungsschema gleich arbeitet, egal wie viele Dimensionen (0-N) verwendet werden. Anders als bekannte RDBMS und Hybrid-Systeme, die zusätzliche Indizes für jede hinzugefügte Dimension benötigen, vermeidet die erfindungsgemäße Verwendung des binären BH-Codes und der automatischen Datenpartitionierung die Erfordernis von mehreren räumlichen Indizes.
Im Betrieb werden mehrdimensionale Datenpartitionen beim Laden auf der Grundlage der für einen BH-Code-Datentyp definierten Dimensionen und ein benutzerdefiniertes Datenvolumen pro Partition (der erfindungsgemäße "Grenzwert") erzeugt. Für jede erzeugte Partition wird ein Eintrag pro Partition in einem mehrdimensionalen Datenwörterbuch gehalten, das genauer im Folgenden beschrieben wird.
Unter der Bezugnahme auf Fig. 11 wird das erfindungsgemäße automatische Datenpartitionierungsschema genauer beschrieben. Exemplarisch sei angenommen, daß eine Gesamtheit der Daten 100 anfänglich vier Partitionen (0-3) umfaßt und daß die drei Partitionen P&sub0;, P&sub1; und P&sub2; drei darin angeordnete Datenpunkte aufweisen. Wie gezeigt, werden anfänglich vier Partitionen P&sub0;, P&sub1;, P&sub2; und P&sub3; erzeugt. Jede der Partitionen umfaßt sowohl eine räumliche Spalte mit dem BH-Code für jeden der in dem entsprechenden Quadranten angeordneten Punkte als auch Attributspalten A&sub1;, A&sub2;-AN. Aus Gründen der Veranschaulichung umfassen die Partitionen P&sub0;, P&sub1;, P&sub2; und P&sub3; nur zwei Attributspalten A&sub1; und A&sub2;. Wie zuvor beschrieben, können diese Attributspalten physikalischen Parametern wie beispielsweise Temperatur, Salzgehalt oder dem Fluß kosmischer Strahlung oder nicht-physikalischen Daten wie beispielsweise Telefonnummern, Kundennamen und ähnlichem entsprechen. Wie gezeigt weist jeder der Quadranten 0, 1 und 2 drei darin angeordnete Datenpunkte auf. Entsprechend weist jede der Partitionen P&sub0;-P&sub2; drei in der Figur als schattierte und schraffierte Abschnitte dargestellte Einträge in jeder Tabelle auf. Darüber hinaus wird der Grenzwert aus beschreibungstechnischen Gründen als gleich fünf gesetzt angenommen, wodurch die Anzahl der Einträge in jeder der Partitionen P&sub0;-P&sub3; auf fünf begrenzt wird. In der Partition P&sub3; existieren keine Daten und kein Speicherraum wird durch Halten dieser Partition verschwendet. Aus Gründen der Klarheit jedoch ist Partition P&sub3; in den Figuren gezeigt.
Wie es in Fig. 11 gezeigt ist, weist jede der Partitionen P&sub0;-P&sub2; drei Einträge auf, wobei zwei der Einträge nicht schattiert sind, wodurch angezeigt wird, daß zwei zusätzliche Datenpunkte in jeder der Partitionen P&sub0;-P&sub2; gespeichert werden können. In der Praxis werden leere Partitionen wie beispielsweise P&sub3; nicht erzeugt, wodurch Speicherraum bei dem in Fig. 2 gezeigten Computersystem eingespart wird. Aus erklärungstechnischen Gründen jedoch sind die unbenutzten Dateneinträge gezeigt, um die vorliegende Erfindung eindeutig zu beschreiben. Aus Gründen der Veranschaulichung sind die Punkte in der Partition P&sub0; darüber hinaus durch die Ziffern 102, 104 und 106 gekennzeichnet. Aus Gründen der Veranschaulichung sind die in der Partition P&sub2; angeordneten Punkte als 108, 110 und 112 gekennzeichnet. Die Punkte 122, 124 und 126 sind in der Partition P&sub1; angeordnet. Wie gezeigt existieren keine Daten in der Partition P&sub3;.
Exemplarisch sei angenommen, daß zusätzliche Daten in der Gesamtheit der Daten 100 zu speichern sind. Es wurden beispielsweise zwei zusätzliche Punkte 135 und 138 zu Quadrant 1 hinzugefügt und sind in der Partition P&sub1; gezeigt. Da der Grenzwert auf fünf gesetzt wurde, wird der Grenzwert durch die Hinzufügung der Punkte 138 und 135 in Quadrant 1 nicht überschritten und keine Veränderungen an den entsprechenden Partitionen sind notwendig. Die Hinzufügung der Punkte 140, 142 und 144 zu Quadrant 0 jedoch führt wie gezeigt zu einer den Grenzwert von fünf überschreitenden Gesamtzahl von (sechs) Datenpunkten. Gemäß den Lehren der vorliegenden Erfindung wird der Quadrant dann in vier, bei dem vorliegenden Beispiel als P&sub0;&sub0;, P&sub0;&sub1;, P&sub0;&sub2; und P&sub0;&sub3; gekennzeichnete Kind-Partitionen (in zwei Dimensionen) zerlegt, wenn der Grenzwert in einem beliebigen Quadranten überschritten wird. Ferner wird wie gezeigt die Eltern-Partition P&sub0; in der erfindungsgemäßen Datenbankstruktur nicht beibehalten. Die Partition P&sub0;&sub0; umfaßt einen dem Punkt 102 entsprechenden Eintrag, wie es am anschaulichsten in Fig. 12 gezeigt ist. Die Partition P&sub0;&sub1; umfaßt zwei Einträge, die den Punkten 104 und 144 entsprechen, und die Partition P&sub0;&sub2; umfaßt einen dem Punkt 106 entsprechenden Eintrag. Entsprechend umfaßt die Partition P&sub0;&sub3; zwei Einträge, die den Punkten 140 und 142 entsprechen.
Es wird nun auf die Fig. 13 Bezug genommen. Exemplarisch sei angenommen, daß zusätzliche Datenpunkte zu dem von der Partition P&sub0;&sub2; dargestellten Quadranten 2 hinzugefügt sind. Die Hinzufügung der Punkte 150, 155, 157, 159 und 160 führt, wie gezeigt, zu insgesamt sechs Dateneinträgen, wodurch der Grenzwert von fünf für jede Tabelle überschritten ist. Demgemäß wird der von Partition P&sub0;&sub2; dargestellte Quadrant 2 zerlegt und wie gezeigt in vier zusätzliche Partitionen P&sub0;&sub2;&sub0;, P&sub0;&sub2;&sub1;, P&sub0;&sub2;&sub2; und P&sub0;&sub2;&sub3; partitioniert. Der Inhalt der Partition P&sub0;&sub2; wird in den einzelnen Kinder-Partitionen wiedergegeben und die Partition P&sub0;&sub2; wird nicht in der erfindungsgemäßen Datenbank gehalten. Die Partition P&sub0;&sub2;&sub0; enthält wie gezeigt einen Eintrag für den Datenpunkt 150, die Partition P&sub0;&sub2;&sub1; umfaßt einen den Punkt 106 darstellenden Eintrag, die Partition P&sub0;&sub2;&sub2; umfaßt drei die Punkte 155, 157 und 159 darstellende Einträge und die Partition P&sub0;&sub2;&sub3; umfaßt einen den Punkt 160 darstellenden Eintrag.
Somit umfaßt die Datenbank der vorliegenden Erfindung gemäß dem erfindungsgemäßen automatischen Datenpartitionierungsschemas eine Mehrzahl von Partitionen mit Einträgen von BH-Code und ihre entsprechenden Attribute übersteigen niemals den Grenzwert. Darüber hinaus wird, sobald eine Eltern- Partition vier Kind-Partitionen (in zwei Dimensionen) erzeugt hat, die Eltern-Partition (zum Beispiel die Partition P&sub0;&sub2;) nicht beibehalten, wie es in den Fig. 12 und 13 gezeigt ist.
Es wird nun auf die Fig. 14 Bezug genommen. Wenn sämtliche der in den Fig. 11, 12 und 13 dargestellten aktiven Partitionen in einem linearen Feld angeordnet sind, nehmen sie die in der Fig. 14 gezeigte Konfiguration an. Die Hierarchie der Partition wird erfindungsgemäß nicht beibehalten, sondern die Partitionen werden eher bei ihrem Grad der Auflösung in einer linearen Art beibehalten. Ferner ist ersichtlich, daß durch eine Untersuchung der Länge der Partitionsausdehnung (BH-Code) die relative Größe und die Anzahl der rekursiven Zerlegungen in einer Partition bestimmt werden können. Somit stellt die Partition P&sub1; einen größeren Quadranten in Bezug auf die Partition P&sub0;&sub1; dar. P&sub0;&sub2;&sub0; stellt entsprechend eine viel kleineren Bereich als die Partition P&sub1; dar. Wie es unter Bezugnahme auf die erfindungsgemäße Wörterbuchfunktion beschrieben wird, werden die Partitionen in einem Wörterbuch gehalten, das die verschiedenen mehrdimensionalen Informationen verfolgt. Unter Verwendung des erfindungsgemäßen Datenpartitionierungsschemas ist es möglich, für jeden Punkt rechtzeitig zu bestimmen, welchen Bereich eine bestimmte Partition abdeckt. Damit verringert das erfindungsgemäße automatische Datenpartitionierungsschema die für den Datenzugriff erforderliche Zeit beträchtlich. Bei der vorliegenden Implementierung der Erfindung werden die von dem erfindungsgemäßen Datenpartitionierungsschema erzeugten Partitionen als Tabellen in einem Datenbanksystem, wie es beispielsweise von der Oracle Corporation hergestellt wird, gespeichert. Die Tabellen werden physikalisch als Tabellenobjekt in die Datenbank geschrieben.

BH-Code-Datenstruktur

Unter Bezugnahme auf die Fig. 15 ist die erfindungsgemäße Implementierung des BH-Codes, wie er von dem in der Fig. 2 gezeigten Computersystem verwendet wird, gezeigt. Die BH-Code-Datenstruktur weist eine Reihe von die eigentlichen BH-Code-Daten darstellenden Datenbytes auf. Zusätzlich zu den BH-Code-Daten bilden auch eine Anzahl von als "Meta"-Daten bezeichneten Datenbytes einen Abschnitt der BH-Code-Datenstruktur. Zum Beispiel umfassen die Metadaten wie gezeigt ein "Typ"-Indentifizierer-Byte 200. Das Typ-Identifizierer- Byte kennzeichnet, ob der in den Datenbytes bereitgestellte BH-Code Punkt- oder Zeilendaten darstellt. Ein "Topologie"- Byte 202 wird in dem Fall von der Erfindung verwendet, wenn von dem BH-Code eine Topologie dargestellt wird. Die Verwendung des BH-Codes für topologische Daten wird in dieser Beschreibung im Folgenden näher beschrieben. Ein "Dimensions"- Byte 204 kennzeichnet die Anzahl der Dimensionen in dem BH- Code. Wie gezeigt werden eine Mehrzahl von "Ebenen"-Bytes einschließlich Ebenen-Byte 208 bis Ebenen-Byte 210 bereitgestellt. Die Anzahl der Ebenen stellt die für jede Dimension kodierte Genauigkeit dar. Es wird beabsichtigt, daß obwohl eine Anzahl von Dimensionen wie beispielsweise Breite, Länge und Tiefe unter Verwendung von BH-Code dargestellt werden können, in dem System nicht sämtliche Dimensionen bei dem gleichen Grad der Genauigkeit gehalten werden müssen.
In Fig. 15 ist ebenso ein Beispiel eines dreidimensionalen BH-Codes mit vier Ebenen gezeigt. Die erste Ebene der Unterteilung ist durch 010 dargestellt, die zweite Ebene der Unterteilung durch 111, die dritte Ebene der Unterteilung durch 101 und die vierte Ebene der Unterteilung ist durch 001 dargestellt. Die erste binäre Größe jeder Ebene stellt die erste Dimension dar, die zweite binäre Größe jeder Ebene stellt die Dimension dar und die dritte binäre Größe jeder Ebene stellt die dritte Dimension dar. Unter Bezugnahme auf das in Fig. 15 gezeigte Beispiel ist das Typ-Byte 200 auf 0 gesetzt und zeigt, daß die von dem binären BH-Code dargestellten Daten Punktdaten sind. Das Topologie-Byte 202 ist auf 0 gesetzt und zeigt an, daß die Topologie nicht aufgerufen wird und das Dimensions-Byte 204 ist auf einen Wert von 3 gesetzt und zeigt an, daß die BH-Code-Daten drei Dimensionen darstellen. Wie gezeigt ist das Ebenen-Byte 208 auf einen Genauigkeitsgrad von 3 Bits gesetzt. Ein Genauigkeitsgrad von 3 Bits wird von dem erfindungsgemäßen System so interpretiert, daß gültige Bits in den BH-Code-Daten als 011 identifiziert werden. Das in Fig. 15 als Bit 212 identifizierte 0-Bit wird als ein Null-Bit betrachtet, da lediglich drei Genauigkeitsgrade in dem Ebenen-Byte 208 gesetzt wurden. Das in Fig. 15 als 214 bezeichnete und einen Wert von "3" aufweisenden Ebenen-Byte führt zu einem Genauigkeitsgrad von drei Bits mit den Werten 001, wobei das durch die Ziffer 216 gekennzeichnete 0-Bit als Null-Bit betrachtet wird. Das Ebenenbit für die dritte Dimension (gekennzeichnet mit der Ziffer 216) ist auf einen Genauigkeitsgrad von "4" gesetzt. Somit ist der binäre BH-Code mit einer Genauigkeit von vier Bits als 0111 gekennzeichnet.
Die erfindungsgemäße Verwendung der Ebenen-Bits zum selektiven Setzen des Genauigkeitsgrades für jede Dimension ermöglicht eine maximale Optimierung der Datensammlung, -speicherung und -abrufung. In bestimmten Fällen kann es wünschenswert sein, jede Dimension auf einem unterschiedlichen Genauigkeitsgrad zu halten. Zum Beispiel kann ein Genauigkeitsgrad von drei Bits für die Länge und die Breite angemessen sein, wenn jedoch eine dritte Dimension für die Zeit verwendet wird, kann eine zusätzliche Genauigkeit erforderlich sein (zum Beispiel wenn die Zeit in Millisekunden anstatt in zehntel Sekunden gemessen wird).
Es wird weiter auf die Fig. 15 Bezug genommen. Eine Anzahl von in dem vorliegenden bevorzugten Ausführungsbeispiel implementierten Kernfunktionen wird gezeigt. Die Kernfunktion BHENCODE wird von der vorliegenden Erfindung verwendet, um die in Fig. 15 gezeigte BH-Code-Datenstruktur aus den BH-Code-Rohdaten erzeugen. Entsprechend verwendet die Kernfunktion BHDECODE die in der Figur gezeigte BH-Code-Datenstruktur zum Wiedererlangen der ursprünglichen Rohdaten. Die Kernfunktionen BHCOMPOSE und BHCOLLAPSE erlauben die Manipulation von dimensionalen Daten in der mehrdimensionalen Datenstruktur. Zum Beispiel kann eine neue zweidimensionale BH-Code-Datenstruktur unter Verwendung der auf einer vierdimensionalen Datenstruktur arbeitenden Kernfunktion BHCOMPOSE erzeugt werden. Die Kernfunktion BHCOLLAPSE ermöglicht es dem erfindungsgemäßen System, Dimensionen aus einer bestehenden BH-Code-Datenstruktur zu entfernen. Zum Beispiel kann eine anfänglich dreidimensionale BH-Code-Datenstruktur durch das Entfernen von einer Dimension unter Verwendung der Kernfunktion BHCOLLAPSE in eine zweidimensionale Struktur überführt (collapsed) werden.
Die Kernfunktion BHMATCH kann von der vorliegenden Erfindung zum Vergleichen von zwei BH-Code-Strukturen verwendet werden, um zu bestimmen, ob diese mit einem speziellen Genauigkeitsgrad übereinstimmen oder nicht. Die Kernfunktion BHCOMMON CODE vergleicht zwei BH-Code-Datenstrukturen und leitet die allgemeinen Charakteristika der beiden BH-Codes ab. Es ist ersichtlich, daß es durch ein Extrahieren der gemeinsamen Elemente zwischen zwei BH-Code-Datenstrukturen einfach ist, zu bestimmen, ob sich die zwei Datenpunkte in demselben räumlichen Speicherbereich aufhalten oder nicht. Die Kernfunktion BHNDIM stellt eine Ausgabe der Anzahl der Dimensionen des BH-Codes zur Verfügung. Die Funktion BHLENGTH bestimmt den Genauigkeitsgrad für jede spezielle Dimension oder wahlweise den höchsten Genauigkeitsgrad der BH-Code-Datenstruktur, auf die die Funktion BHLENGTH angewendet werden soll. Die Funktion BHPRECISION stellt eine dezimale Darstellung eines speziellen Genauigkeitsgrades zur Verfügung. Die Funktion BHLEVEL gibt entsprechend die Anzahl der für einen bestimmten Genauigkeitsgrad erforderlichen Ebenen zurück. BHCELLSIZE stellt die Größe der Begrenzungen eines Bereiches zur Verfügung, in dem sich ein Datenpunkt aufhält. Für den Fall zum Beispiel, daß Datenmessungen des Salzgehaltes eines Ozeans bei einer Tiefe von 1000 Fuß unter einem Punkt in dem Ozean vorgenommen werden, wie es zuvor in der Beschreibung beschrieben wird, hält sich der Datenpunkt für den Wert des Salzgehaltes des Ozeans in einem Bereich auf, dessen Größe eine Funktion der Meßmethoden und -einrichtungen ist, die zum Erreichen einer bestimmten Auflösung verwendet werden. Die Funktion BHCESIZE identifiziert die Größe des Bereiches in dem die BH-Code-Daten angeordnet sind.
Das Kernkommando BHSUBSTR gibt die Teilkette eines BH- Codes zurück, die dem Benutzer ein Vereinigen der Daten auf der Grundlage von räumlichen Informationen ermöglicht. Ein Beispiel für die Verwendung der BHSUBSTR-Funktion ist das Bestimmen des Wertes des durchschnittlichen Salzgehaltes zwischen zwei oder mehr, Messungen bei unterschiedlichen Datengenauigkeiten darstellenden, BH-Code-Datenpunkten. Durch der Verwendung von BHSUBSTR kann der Benutzer je nach seinen Anforderungen von einer maximalen Genauigkeit in einer geringeren wechseln. Die Funktion BHDISTANCE stellt einen Entfernungswert zwischen zwei BH-Code-Datenpunkten zur Verfügung. Beim Betrieb bestimmt BHDISTANCE das Quadrat des numerischen charakterischen Abstandswertes zwischen den Mittelpunkten der beiden BH-Code-Daten. Die Funktionen BHJLDATE und BHCLDATE ermöglichen es dem Benutzer, Messungen zwischen julianischen und Kalenderdaten mit einer Genauigkeit von Millisekunden umzuwandeln.
Es wird nun auf Fig. 16 Bezug genommen. Es ist eine allgemeine Darstellung der vorliegenden Erfindung gezeigt, die auf einem Computersystem wie beispielsweise dem in Fig. 2 gezeigten implementiert ist. Räumliche BH-Code-Daten und Attributdaten sind auf einer Magnetplatte 230 gespeichert. Ein Computerserver 232 ist mit der Platte verbunden, die in Verbindung mit einem SQL-Sprachenprogramm (234) arbeitet. Wie gezeigt sind verschiedene Einrichtungen einschließlich eines Konverters 236, eines Laders 238, eines Extraktors 239 und eines Import/Export-Behandlers 240 über die gebräuchliche Schnittstelle des SQL mit dem Server 232 verbunden. Zusätzlich ist ein Archivierungsprogramm 242 wie gezeigt mit dem Server 232 verbunden. Darüber hinaus ist es beabsichtigt, daß das erfindungsgemäße System mit anderen Workstations, die beispielsweise Drittanwendungen 245 und Visualisierungstools 248 zur Verfügung stellen, verbunden ist.

Datenwörterbuch

Die erfindungsgemäße Verwendung des BH-Codes ermöglicht das Erzeugen eines Datenwörterbuches, das sowohl das Laden als auch den Zugriff von Daten in und aus der Datenbank erleichtert. Die räumlichen Informationen werden, wie es beschrieben wird, in dem Wörterbuch gehalten, wodurch ein effizientes Laden und Auslesen ermöglicht wird. Es wird nun auf die Fig. 17 Bezug genommen. Darin ist eine schematische Darstellung des erfindungsgemäßen Mehrdimensionen-Datenwörterbuchs allgemein mit der Zahl 300 bezeichnet. Darüber hinaus zeigt Fig. 17 einen Abschnitt einer durch die Zahl 302 gekennzeichneten Datenbankstruktur, wobei das aktuelle Ausführungsbeispiel eine von der Oracle Corporation angebotene relationale Datenbank (RDBMS) aufweist.
Das erfindungsgemäße Datenwörterbuch 300 umfaßt wie gezeigt eine mehrdimensionale Tabelle 304. Die mehrdimensionale Tabelle 304 enthält eine Liste aller in der RDBMS-Datenbank gespeicherten Tabellen, die als mehrdimensional betrachtet werden. Wie zuvor beschrieben, findet die vorliegende Erfindung Anwendung bei sowohl räumlichen als auch nicht-räumlichen Daten. Von den in der RDBMS 302 gespeicherten Tabellen speichert die Mehrdimensionen-Tabelle 304 eine Liste der Tabellen, die als räumlich und daher als mehrdimensional betrachtet werden.
Das Datenwörterbuch 300 liefert und arbeitet mit zwei Klassen von Tabellen, und zwar partitionierte Mehrdimensionen-Tabellen und nicht-partitionierte Mehrdimensionen-Tabellen. Eine partitionierte Tabelle 306 ist mit der Mehrdimensionen-Tabelle 304 verbunden. Nicht-partitionierte Mehrdimensionen-Tabellen sind übliche RDBMS-Tabellen, die eine oder mehrere räumliche Spalten oder Spalten vom BH-Code-Typ umfassen. Partitionierte Tabellen sind Mehrdimensionen-Tabellen, die ferner eine oder mehrere räumliche Spalten aufweisen, die aber auf einer dieser räumlichen Spalten partitioniert sind. Mit anderen Worten weist die partitionierte Tabelle 306 eine Reihe von Partitionen auf, die in Kind-Partitionen zerlegt werden können, wie es zuvor unter Bezug auf die Datenpartitionierung beschrieben wurde. Die Liste der in der Mehrdimensionen-Wörterbuchtabelle 304 gespeicherten mehrdimensionalen Tabellen kann aus partitionierten Mehrdimensionen-Tabellen bestehen, wobei jede Partition ein Teil einer Mehrdimensionen-Tabelle sein muß. Eine Mehrdimensionen-Spaltentabelle 310 ist mit der partitionierten Tabelle 306 und der Mehrdimensionen-Tabelle 304 verbunden. Die Mehrdimensionen-Spaltentabelle 310 hält eine Liste aller Spalten in der Datenbank, von denen angenommen wird, daß sie vom BH- Code-Typ oder von einem anderen Datenbanktyp sind. Wie dargestellt ist die Beziehung zwischen der Mehrdimensionen- Spaltentabelle 310 und der Mehrdimensionen-Tabelle 304 derart, daß jeder in der Mehrdimensionen-Tabelle 304 angeordneter Mehrdimensionen-Tabelleneintrag durch eine oder mehrere Mehrdimensionen-Spalten definiert ist. Die Dimensionen- Tabelle 320 weist eine Tabelle auf, die die Dimensions-Informationen für jede BH-Code-Spalte hält. Es daran erinnert, daß eine Dimensionen-Spalte eine Spalte vom BH-Code-Typ ist und diese Spalte weist eine oder mehrere Dimensionen auf. Die Dimensionen-Tabelle 320 hält die Definitionen der Dimensionen und die Beziehung zwischen diesen, die anzeigt, daß eine Mehrdimensionen-Spalte durch eine oder mehrere Dimensionen definiert sein muß, und eine Dimension muß für eine Mehrdimensionen-Spalte definiert sein.
Die Beziehung zwischen der Mehrdimensionen-Tabelle 304 und der Mehrdimensionen-Spaltentabelle 310 ist, wie es in Fig. 17 gezeigt ist, auf zwei Wegen definiert. Ein direkter Weg ist für eine nicht-partitionierte Tabelle von der Mehrdimensionen-Tabelle 304 zu der Mehrdimensionen-Spaltentabelle 310 definiert. Da es zwei Klassen von Mehrdimensionen- Tabellen gibt, und zwar partitionierte und nicht-partitionierte, kann eine die Lehren der vorliegenden Erfindung verwendende nicht-partitionierte Tabelle räumliche Daten speichern, jedoch besteht dann ein Bedarf daran, eine Identifikation darüber zu halten, welche Spalten in der nicht-partitionierten Tabelle räumliche Daten darstellen. Darüber hinaus kann eine aus einer oder mehreren Partitionen bestehende mehrdimensionale Tabelle aus einer oder mehreren Mehrdimensionen-Spalten bestehen.
Es wird weiter auf Fig. 17 Bezug genommen. Das RDBMS- Datenwörterbuch 302 verwendet drei Tabellen in einem üblichen Oracle-Datenwörterbuch. Die Objekttabelle 325 hält eine Liste aller Objekte in der Datenbank einschließlich, ohne Einschränkung, Tabellen, Ansichten und ähnliches. Eine Tab- Tabelle 328 weist eine Untertabelle der Objekttabelle 325 auf, die Informationen bezüglich aller Objekte, von denen angenommen wird, Tabellen zu sein, speichert. Eine Spaltentabelle 330 hält Informationen über sämtliche Spalten in Tabu, die Teil der Tabellen sind, die Teil der Objekte in der Objekttabelle 325 sind.
Wie es in Fig. 17 gezeigt ist, ist die Objekttabelle 325 mit der Mehrdimensionen-Tabelle 304 verbunden. Die Tab- Tabelle 328 ist mit der partitionierten Tabelle 306 verbunden und die Spaltentabelle 330 ist mit der Mehrdimensionen- Spaltentabelle 310 verbunden. Die Verbindung zwischen der Objekttabelle 325 und der Mehrdimensionen-Tabelle 304 gibt die Konvention wieder, daß von allen Mehrdimensionen-Tabellen angenommen wird, daß sie Datenbankobjekte sind. Ein Objekt kann daher als eine Mehrdimensionen-Tabelle angesehen werden. Daher wird von allen Mehrdimensionen-Tabellen angenommen, daß sie Datenbankobjekte sind. Das Oracle-Wörterbuch sorgt dafür, daß von einer in der Tab-Tabelle 328 gelisteten Tabelle angenommen werden kann, daß sie eine partitionierte Tabelle ist, aber daß eine partitionierte Tabelle als eine reguläre Oracle-Tabelle registriert sein muß. Wie gezeigt ist die Spaltentabelle 330 mit der Mehrdimensionen-Spaltentabelle 310 verbunden. Von einer in der Spaltentabelle 330 gelisteten Datenbankspalte kann angenommen werden, daß sie eine Mehrdimensionen-Spalte ist, die in der Mehrdimensionen- Spaltentabelle 310 gelistet sein würde. Eine in der Tabelle 310 gelistete Mehrdimensionen-Spalte muß jedoch als eine Datenbankspalte in der Spaltentabelle 330 registriert sein.
Wie es beschrieben wird, ermöglicht das Datenwörterbuch 300 einen effizienten Datenzugriff auf Mehrdimensionen-Daten, die gemäß den Lehren der vorliegenden Erfindung gespeichert sind.
Es wird nun auf Fig. 18 Bezug genommen. Wie gezeigt kann eine exemplarische Partitionen-Tabelle (hier als "md$ptab" bezeichnet) konzeptionell betrachtet werden als zwei Spalten umfassend, nämlich OBJ# und COM_BH CODE. Es wird deutlich, daß in der gegenwärtigen Implementierung der vorliegenden Erfindung die md$ptab-Tabelle eine Mehrzahl von Spalten umfaßt. COM_BH CODE stellt die Ausdehnung einer Partition dar, mit anderen Worten, wie viel Raum eines Bereichs die Partition abdeckt. Die Gesamtheit der Daten kann als ein in der Fig. 18 gezeigter Bereich 400 aufgefaßt werden. Wie zuvor unter Bezugnahme auf die BH-Code-Datenstruktur und das Datenpartitionierungsschema beschrieben ist der Bereich 400 rekursiv in vier Quadranten (in zwei Dimensionen) zerlegt. Die rekursive Zerlegung in Quadranten wird durch den Grenzwert (der in Fig. 18 auf sechs gesetzt ist) und die Dichte der räumlich gesammelten Daten gelenkt. Daher stellt jede der Partitionen, die erfindungsgemäß zerlegt worden sind, ein Objekt in dem Datenwörterbuch dar. Jede der in der Tabelle md$ptab gezeigten Objektnummern ist ein Datensatz in der Mehrdimensionen-Tabelle 304. Es wird deutlich, daß die Organisation des Datenwörterbuchs und das erfindungsgemäße automatische Datenpartitionierungsschema zusammenhängen, wobei jede Tabelle ein Objekt mit einem entsprechenden COM_BH CODE darstellt.
Es wird nun auf Fig. 19 Bezug genommen. Es wird ein weiteres Beispiel des erfindungsgemäßen Datenwörterbuchs und der Tabellenpartitionierung beschrieben, wobei die Erfindung Daten, die mit einem durch einen Benutzer definierten Bereich überlappen, identifiziert. Wie gezeigt wurde eine Gesamtheit der Daten 410 rekursiv gemäß den Lehren der vorliegenden Erfindung zerlegt. Durch den Prozeß der rekursiven Zerlegung sind Bereiche und entsprechende Partitionen P&sub0;, P&sub1;, P&sub5;, P&sub1;&sub1;, P&sub1;&sub2;, P&sub1;&sub3; und P&sub1;&sub4; erzeugt worden. Die md$ ptab-Tabelle 415 umfaßt eine Liste von Objekten mit entsprechenden üblichen BH-Codes (COM_BH CODE) für jede der Partitionen. Der COM_BH CODE stellt die Ausdehnung der Partition dar, mit anderen Worten, die Ausdehnung des Bereichs, den die Partition abdeckt. Ein Benutzer kann die Erfindung zu der Abfrage "wähle alle Daten" veranlassen, wobei die Daten sich in irgendeinem von dem Benutzer definierten Bereich der Gesamtheit der Daten aufhalten. Wie in der Figur gezeigt, identifiziert die vorliegende Erfindung jede der Tabellen (OBJ#), in der sich zumindest ein Abschnitt des angeforderten Bereichs aufhält (schematisch als ein gestrichelter Bereich 420 gekennzeichnet). Die vorliegende Erfindung erzeugt anschließend eine Liste der Partitionen (OBJ#), die zumindest einen Abschnitt des Bereichs 420 umfassen. Bei dem gezeigten Beispiel umfaßt diese Liste P&sub5;, P&sub1;&sub1;, P&sub0; und P&sub1;.
Sobald die Objektliste identifiziert wurde, wird die Benutzeranfrage beantwortet, indem die Daten identifiziert werden, die aus der ersten Partition, die die vorliegende Erfindung identifiziert hat (P&sub5;), angefordert werden. Die Funktion BHWINDOW ist eine eingebaute interne Funktion, die festlegt, ob ein den Gegenstand einer Suche darstellender Datenpunkt in dem aktuell gekennzeichnetem Fenster angeordnet ist. Damit wird die ursprüngliche Benutzeranfrage auf eine oder mehrere Unteranfragen ausgedehnt, die dann von einem relationalen Operator UNION ALL zusammengefügt werden. UNION ALL ist eine Operation in der Datenbank, die sämtliche Zeilen der ersten Anfrage nimmt und mit den Zeilen der zweiten Anfrage zusammenfügt und diese Operation für jede der identifizierten Partitionen durchführt. Eine zweite Anfrage wählt den Ort und die Tiefe der zweiten Partition, die in dem Beispiel als Partition P&sub1;&sub1; identifiziert ist. Entsprechend fragt die vorliegende Erfindung bei jeder der Partitionen an, die als in dem von dem Benutzer definierten Bereich 420 angeordnet identifiziert sind. Die Ergebnisse sämtlicher dieser Anfragen werden anschließend dem Benutzer aufgezeigt.
Es wird deutlich, daß die erfindungsgemäße Methodik für den Datenzugriff insofern eine verbesserte Effizienz zur Verfügung stellen, daß andere, nicht an der Anfrage beteiligte Partitionen (beispielsweise P&sub1;&sub3; und P&sub1;&sub2;) verworfen werden. Durch das Verwerfen von nicht Benötigtem und dem ausschließliche Betrachten von Benötigtem wird Effizienz erzielt. Die vorliegende Erfindung verwirft P&sub1;&sub3; und P&sub1;&sub2; und die drei anderen nicht benannten Partitionen, da diese nicht Teil der Anfrage sind. Das Fenster deckt lediglich P&sub5;, P&sub1;&sub1;, P&sub0; und P&sub1; ab. Diese sind die einzigen Partitionen, die zum Auflösen der Anfrage untersucht werden.
Um die oben ausgeführte Beschreibung zusammenzufassen: Der Prozeß des Auflösens einer beliebigen räumlichen Anfrage ist ein Prozeß in zwei Schritten. Der erste Schritt identifiziert die ein benutzerdefiniertes Fenster überlappenden Partitionen. Wie es in dem Beispiel von Fig. 19 gezeigt ist, sind dies die Partitionen P&sub5;, P&sub1;&sub1;, P&sub0; und P&sub1;. Das (durch die Kreuzschraffur definierte) Fenster wird untersucht und es wird bestimmt, welche Partitionen überlappen. Dieses wird mathematisch vollzogen und zwar indem die vorliegende Erfindung jede Partition auswählt, die in md$ptab enthalten ist und beginnt in der Tabelle bei P&sub0;. Wenn P&sub0; in dem Fenster liegt, wird sie ausgewählt. Dann wird bei P&sub1; fortgefahren und eine geometrische Berechnung ausgerechnet. Überlappt sie das Fenster? Bei dem vorliegenden Beispiel überlappt sie und P&sub1; wird somit ausgewählt. Das gleiche Muster folgt für P&sub5; bis P&sub1;&sub3;. Wie zu sehen ist, liegen P&sub1;&sub2;, P&sub1;&sub3; und P&sub1;&sub4; außerhalb des fraglichen Fensters und werden zurückgewiesen, genau wie die anderen nicht bezeichneten Partitionen in der Figur. Der nächste Schritt identifiziert alle Datensätze in den ausgewählten Partitionen, die ein benutzerdefiniertes Fenster identisch überlappen.
Laden von und Zugriff auf zweidimensionale Zeilen Mathematisch besteht eine Zeile aus zwei Endpunkten einschließlich eines mit einem Zeilensegment verbundenen ersten Punktes (X&sub1;, Y&sub1;) und eines zweiten Punktes (X&sub2;, Y&sub2;) (siehe Fig. 20(a)). Gemäß den Lehren der vorliegenden Erfindung ist ein Zeilensegment als ein vierdimensionaler BH-Code dargestellt. Der Wert von jedem der vier Punkte X&sub1;, Y&sub1;, X&sub2; und Y&sub2; ist als ein vierdimensionaler BH-Code dargestellt, wobei Dimension 1 (DIM1) gleich X&sub1; ist, Dimension 2 (DIM2) aus Y&sub1; besteht, Dimension 3 (DIM3) X&sub2; entspricht und Dimension 4 (DIM4) aus Y&sub2; gebildet wird (siehe Fig. 20(b)). Somit stellt eine vierdimensionale Dateneinheit bei der erfindungsgemäßen räumlichen Datenbank ein zweidimensionales Zeilensegment dar. Das Laden von Zeilensegmentdaten in die erfindungsgemäße Datenbank verläuft analog zu der zuvor unter Bezugnahme auf das Laden von Punkten beschriebenen Operation. Das erfindungsgemäße Datenwörterbuch hält Informationen über die Partitionen, die zum Speichern von Zeilen verwendet werden. Die Zeilen werden in diese Partitionen geladen und wie im Falle von Punkten unterteilt die vorliegende Erfindung die Partitionen so, wie es für Punkte beschrieben wurde, wenn der Grenzwert (der das größte in einer Partition erlaubte Datenvolumen darstellt) überschritten wird. Der Unterschied ist der, daß, wenn eine zweidimensionale Punkt- Partition unterteilt wird, die vorliegende Erfindung diese jedoch in vier Partitionen unterteilt, da eine Zeile durch ein vierdimensionales Objekt dargestellt wird und bei jeder Unterteilung für Zeilen bis zu sechszehn (2&sup4;) Partitionen erzeugt werden können. Die vorliegende Erfindung erzeugt diese Partitionen lediglich für die Partitionen, in denen Daten gespeichert werden. Die nicht verwendeten Partitionen verschwenden keinen Speicherplatz und keinen Plattenspeicher und werden lediglich von den in der md$ptab-Tabelle in dem Datenwörterbuch gehaltenen Daten abgeleitet.
Beim Zugriff auf Zeilendaten erfolgt die erfindungsgemäße Anwendung auf zweidimensionale Zeilen analog dem Zugriff auf Punktdaten. Die vorliegende Erfindung identifiziert einen Bereich, an dem der Benutzer interessiert ist und identifiziert die Partitionen. Wenn es einen Bereich gibt, den Zeilen durchqueren, wird dieser zum Identifizieren der Linien, die einen Endpunkt in dem Bereich oder beide Endpunkte in dem Bereich haben, weitergeleitet. Es ist jedoch schwieriger, eine Zeile zu identifizieren, deren Endpunkte sich außerhalb des Bereiches befinden. Dieser Fall des "Durchlaufens" stellt außergewöhnliche Probleme für den Zugriff auf Zeilendaten dar. Die vorliegende Erfindung umfaßt, wie es beschrieben wird, ein Verfahren zum Identifizieren der richtigen Partitionen für Zeilen und beachtet den Fall des Durchlaufens. Wie bei dem Fall von Zeilen wird ein Wörterbuch für Objekte (OBJ#) und ein entsprechender COM_BH CODE zur Verfügung gestellt. Jede der Partitionen speichert Zeilen unterschiedlicher Art. Da die Zeilen zwischen den Partitionen oder außerhalb der Partitionen existieren und die Partitionen möglicherweise durchlaufen, ist es der erste Schritt bei dem Verfahren, die Partitionen zu identifizieren. Jedoch unterscheidet sich zwischen Punkten und Zeilen die Art, auf die Partitionen identifiziert werden. Sobald die Partitionen jedoch identifiziert worden sind, fährt das Verfahren fort, wie es dies bei Punkten tut. Die vorliegende Erfindung erzeugt SQL-Anweisungen, die dann vereint werden, um den resultierenden Datensatz zurückzugeben.
Es wird nun auf die Fig. 21(a) und 21(b) Bezug genommen. Eine Zeile 500 ist durch ein vierdimensionales Objekt X&sub1;, Y&sub1;, X&sub2; und Y&sub2; dargestellt. Die Ebenen P&sub1; (502) und P&sub2; (504) sind definiert, in denen sich jeder der Endpunkte aufhält. Wie gezeigt definiert eine erste Ebene der rekursiven Zerlegung der Ebenen P&sub1; und P&sub2; vier Quadranten gleicher Größe in jeder der entsprechenden Ebenen. Ein Endpunkt in der Ebene P&sub1; kann überall in der Ebene angeordnet sein. Aus beschreibungstechnischen Gründen sei angenommen, daß der Punkt X&sub1;, Y&sub1; in einem Quadranten 505 der Ebene P&sub1; angeordnet ist. Entsprechend kann sich der Endpunkt X&sub2;, Y&sub2; in einem beliebigen der vier Quadranten der Ebene P&sub2; (504) aufhalten. In dem einfachsten Fall kann sich der Endpunkt X&sub2;, Y&sub2; in ei¬ nem Quadranten 510 aufhalten und dadurch die zwei Endpunkte durch ein Zeilensegment verbinden. Da die zwei Ebenen P&sub1; und P&sub2; jedoch identisch sind, kann der Endpunkt des Zeilensegmentes 500 in einem beliebigen der vier Quadranten, in die die Ebene P&sub2; zerlegt worden ist, angeordnet sein. Dadurch wird deutlich, daß, angenommen der ursprüngliche Endpunkt (X&sub1;, Y&sub1;) ist in dem Quadranten 505 der Ebene P&sub1; angeordnet, der das Zeilensegment 500 definierende gegenüberliegende Endpunkt in den Quadranten 510, 515, 520 oder 525 angeordnet sein kann. Wenn der ursprüngliche Endpunkt (X&sub1;, Y&sub1;) entsprechend in dem Quadranten 530 angeordnet ist, kann der Endpunkt in einem beliebigen der vier in der Ebene P&sub2; definierten Quadranten angeordnet sein.
Gemäß den Lehren der vorliegenden Erfindung identifiziert ein anfänglicher Schritt alle möglichen Partitionsformen, die durch die Endpunkte des Zeilensegmentes 500 definiert sein können. Es ist ersichtlich (obwohl in Fig. 22(a) nicht vollständig gezeigt, um die Beschreibung nicht unnötig zu verkomplizieren), daß es sechzehn mögliche Kombinationen der das Zeilensegment 500 definierenden Endpunkte zwischen den Ebenen P&sub1; (502) und P&sub2; (504) gibt. Dies ist der Fall, da ein Endpunkt in einem beliebigen der Quadranten von P&sub1; beginnen kann und einen entsprechenden Endpunkt in einem beliebigen der Quadranten von P&sub2; haben kann. Wie es beschrieben wird, gibt es sechszehn mögliche Partitionsformen, die von einem Zeilensegment mit in den Ebenen P&sub1; und P&sub2; angeordneten Endpunkten definiert sein können. Die erste der möglichen Partitionsformen ist der Fall, bei dem ein Endpunkt (X&sub1;, Y&sub1;) in beispielsweise Quadrant 505 angeordnet ist und ein entsprechender Endpunkt in Quadrant 510 angeordnet ist. Eine zweidimensionale Darstellung dieser vier Partitionsformen ist in Fig. 22(b) dargestellt und ist allgemein mit der Zahl 600 gekennzeichnet.
Die sechszehn möglichen Kombinationen von Endpunkt- zu Endpunkt-Orten zwischen den Ebenen P&sub1; und P&sub2; führen entsprechend zu sechszehn Partitionsformen. Zusätzliche Formen umfassen vertikale Rechtecke, die kollektiv mit der Zahl 604 gekennzeichnet sind und beispielsweise einem in Quadrant 505 von Ebene P&sub1; beginnendem und in Quadrant 520 von P&sub2; endendem Endpunkt entsprechen. Die kollektiv mit der Zahl 608 gekennzeichneten Partitionen entsprechen neben den entsprechenden Kombinationen einem Endpunkt (X&sub1;, Y&sub1;) in beispielsweise Quadrant 505 und haben einen Endpunkt in Quadrant 515 von Ebene P&sub2;. Ein letzter Satz von Formen umfaßt Diagonalen, die in Fig. 22(b) allgemein mit der Zahl 610 gekennzeichnet sind. Diese Partitionen werden durch einen in beispielsweise Quadrant 506 von Ebene P&sub1; angeordneten Endpunkt erzeugt und haben einen Endpunkt in Quadrant 515 von P&sub2; und den entsprechenden Kombinationen.
Indem die Ebenen miteinander zusammengeführt werden und die in zwei Dimensionen erzeugten Partitionsformen analysiert werden, werden folglich sechszehn Partitionsformen erzeugt. Die in Fig. 22(b) gezeigten sechszehn Partitionsformen stellen alle möglichen Partitionsformen dar, die unter Verwendung von sich zwischen den Ebenen von P&sub1; und P&sub2; erstreckenden Zeilensegmenten erzeugt werden können.
Die sechszehn in den Fig. 22(a), 22(b) und 22(c) dargestellten Partitionsformen stellen die Partitionen in dem erfindungsgemäß Datenwörterbuch dar. Durch Untersuchung der Datensätze in dem Zeilensegment-Datenwörterbuch und einem Entschlüsseln dieses, so daß es in einer graphischen Form vorliegt, wird eine der sechszehn Partitionsformen erzeugt. Bei dem vorliegenden Ausführungsbeispiel wird ein Datenwörterbuch für alle räumlichen Spalten einschließlich Punkten und Zeilen verwendet.
Gemäß dem Verfahren der vorliegenden Erfindung ist der erste Schritt beim Zugreifen auf in der Datenbank gespeicherte Zeilendaten ein erstes Identifizieren der Partitionsform, der die Zeile entspricht. Diese muß eine der in Fig. 22(b) gezeigten sechszehn Partitionsformen sein. Der nächste Schritt ist ein Extrahieren aller Partitionsdatensätze aus dem Wörterbuch, das zu der Tabelle gehört, aus der die Daten extrahiert sind. Anschließend wird eine Liste dieser Partitionen für vierdimensionale BH-Codes kompiliert und die vorliegende Erfindung entschlüsselt diesen BH-Code. Beim Entschlüsseln des BH-Codes wird eine der sechszehn Partitionsformen erhalten. Sobald die Partition identifiziert ist, wird die Partition dann mit dem benutzerdefinierten Bereich überlappt, um festzustellen, ob der partitionierte Abschnitt mit dem Bereich überlappt oder nicht.
Zur Erleichterung des Verständnisses ist in Fig. 22(c) ein mit der Zahl 700 gekennzeichneter rechteckiger Abschnitt gezeigt, der dem benutzerdefinierten fraglichen Bereichs entspricht. Exemplarisch sei angenommen, daß eine Partitionsform 702 aus den BH-Code-Daten erhalten wurde. Wenn festgestellt wird, daß die Partitionsform 702 nicht mit dem Bereich von Interesse 700 zusammenhängt, wird diese einfach verworfen, da die Partition sich nicht in einem Abschnitt des Bereiches von Interesse 700 aufhält. Der nächste Eintrag in der Datenwörterbuch-Liste wird entschlüsselt und die Partition extrahiert. Eine Überlappungsfunktion wird ausgeführt und eine oder mehrere Bedingungen werden erhalten. Entweder werden die Bereiche nicht zusammenhängen oder die Partition wird vollständig von dem Bereich umschlossen sein (siehe Partition 704, die in dem Bereich 700 angeordnet ist). Alternativ können die Bereiche wie beispielsweise Partition 710 und Bereich 700 teilweise überlappen und sich dadurch schneiden. Bei dem in Fig. 22(c) dargestellten Beispiel werden die Partition 704 und die Partition 710 zum Verarbeiten gespeichert, und die Partition 702 wird verworfen. Entsprechend wird in dem in Fig. 22(c) gezeigten Beispiel, bei dem die Partition 712 den Bereich 700 vollständig umfaßt, die Partition 712 zum Verarbeiten gespeichert.
Kurz gesagt untersucht die vorliegende Erfindung die Partitionsliste, bestimmt welche der Partitionen definiert sind, entschlüsselt die Partitionsformen, ermittelt welche der Formen mit dem benutzerdefinierten Bereich überlappt und kompiliert eine Liste der Partitionen, die Datensätze aufweisen kann, die innerhalb des Bereichs liegen. Im nächsten Schritt liest die vorliegende Erfindung aus der Liste der kompilierten Partitionen jeden Datensatz in jeder identifizierten Partition und bestimmt, ob dieser Datensatz in dem Bereich liegt. Wenn dies der Fall ist, gibt die vorliegende Erfindung den Datensatz dem Benutzer als einen Datensatz zurück, der in dem definierten Bereich liegt. Wenn der Eintrag nicht in dem Bereich liegt, wird er verworfen.

Anwendung der vorliegenden Erfindung auf Topologie

Die Verwaltung räumlicher Daten erfordert mehr als die Verwaltung von Punkten und Zeilen. Die Verwaltung räumlicher Daten erfordert ebenso die Verwaltung von komplexeren räumlichen Objekten. Beispielsweise weist ein Datensatz, der eine Straße durch einen Park darstellt, komplexe Objekte aus einfachen Elementen auf. Die Straße besteht aus Zeilensegmenten und der Park besteht aus Zeilensegmenten und/oder Bereichsdaten. Ziel der vorliegenden Erfindung ist es, eine Datenstruktur zum effizienten Halten eines komplexen Objektes und damit zum Halten seiner Topologie zur Verfügung zu stellen. Die Topologie eines Objektes muß gehalten werden, um die Beziehung unter den verschiedenen Objekten zu bestimmen.
Es wird nun auf die Fig. 23 Bezug genommen. Ein Park ist konzeptionell dargestellt und ist mit der Zahl 800 bezeichnet. Straßen R&sub8;&sub0;&sub2;, R&sub8;&sub0;&sub4; und R&sub8;&sub0;&sub6; durchlaufen oder aber schneiden den Park 800. Ein See 820 ist als ein vollständig in dem Park 800 angeordneter Bereich definiert. Wichtige Informationen umfassen die Beziehung der Straßen zu dem Park und welche Straßen den Park durchziehen und welche Straßen den Park kreuzen. Die vorliegende Erfindung wendet ihre einzigartige Datenstruktur des binärem BH-Codes auf eine von Max Egenhofer entwickelte und in einer Veröffentlichung mit dem Titel "Toward Formal Definitions of Topological Relations Among Spatial Objects" (Universität von Maine) beschriebene Theorie an. Eine Kopie dieser Veröffentlichung wurde gleichzeitig mit der Anmeldung dieser Patentanmeldung, auf der dieses Patent basiert, eingereicht.
Unter Verwendung der Methodik von Egenhofer implementiert die vorliegende Erfindung einen als eine Vier-Schnittmengen-Methodik bezeichneten Prozeß.
Es wird auf Fig. 24 Bezug genommen. Eine Topologie T1 kann durch ihre Innenräume (I1) und Grenzen (B1) definiert sein. Entsprechend kann eine zweite Topologie T2 durch ihre Innenräume (T2) und Grenzen (B2) definiert sein. Um festzustellen, ob die Topologie T1 und T2 überlappen oder nicht, wird ermittelt, ob sich die Grenzen (B1 und B2) überschneiden, und eine entsprechende Operation wird durchgeführt, um festzustellen, ob sich die Innenräume I1 und I2 überschneiden. Wenn eine zusätzliche Topologie T3 hinzugefügt wird, die durch ihre Innenräume (I3) und Grenzen (B3) definiert ist, kann ermittelt werden, ob die Topologie T3 die Topologie T1 berührt oder nicht. Die Ermittlung, ob sich die Topologie T1 und T3 berühren, führt zu einer Überschneidung zwischen den Grenzen von B1 und B3, aber nicht zu einer Überschneidung zwischen den Innenräumen von I1 und I3, wie es in der Fig. 24 gezeigt ist.
Es wird nun auf die Fig. 25 Bezug genommen. Eine Tabelle einer Vier-Schnittmengen-Beziehung ist gezeigt. Aus exemplarischen Gründen sei angenommen, daß zwei Objekte A und B existieren, wobei IA den Innenraum von A und IB den Innenraum von B darstellt. Entsprechend werden die Grenzen von A durch BA und die Grenzen von B durch BB dargestellt. Wie gezeigt können vier Spalten die Beziehung zwischen den zwei Objekten A und B definieren. Die erste Beziehung ist der Fall, bei dem der Innenraum von A (IA) den Innenraum von B (IB) schneidet. Die zweite Spalte der in Fig. 25 gezeigten Tabelle zeigt den Fall, daß die Grenzen von Bereich A (BA) die Grenzen von Bereich B (BB) schneiden. Darüber hinaus kann, wie es in der Figur gezeigt ist, der Innenraum von A (IA) die Grenze von Objekt B (BB) schneiden. Schließlich kann der Innenraum von Objekt B (IB) die Grenze von A (BA) schneiden. Die Ergebnisse dieser Überschneidungen definieren die Beziehungen zwischen den Objekten A und B. Die Objekte A und B können getrennt sein, sie können überlappen oder sie können sich berühren. Bei der Konvention dieser Beschreibung zeigt eine 0 in der in Fig. 25 gezeigten Tabelle, daß eine Bedingung nicht erfüllt ist und eine 1 zeigt an, daß eine Bedingung erfüllt ist. Beispielsweise, wie es für die Beziehung der Berührung gezeigt ist, ist der einzige erfüllte Fall bei dem Beispiel der, bei dem die Grenzen von A (BA) die Grenzen von B (BB) schneiden.
Kurz gefaßt wird die Vier-Schnittmengen-Beziehung verwendet, um zwei Arten von topologischen Anfragen zu beantworten. Die Erste liegt vor, wenn es zwei Objekte gibt und der Benutzer die Beziehung zwischen diesen kennen möchte. Wenn der Benutzer beispielsweise zwei Objekte vorliegen hat (beispielsweise T1 und T2) und zu wissen wünscht, wie die Beziehung zwischen diesen beiden Objekten ist. Die zweite topologische Anfrage liegt vor, wenn der Benutzer ein Objekt hat und wünscht, andere Objekte zu finden, die in einer bestimmten Beziehung zu diesem Objekt stehen, beispielsweise T1 und T3.
Es wird nun auf die Fig. 26(a) Bezug genommen. Die vorliegende Erfindung verwendet die Vier-Punkt-Schnittmengen- Techniken nach Egenhofer um Topologieoperationen zu bearbeiten. Wie es in der Fig. 26(a) gezeigt ist, ist ein Objekt T&sub4; durch einen Innenraum I&sub4; und eine Grenze B&sub4; definiert. Das Objekt T&sub4; ist rekursiv durch ein als "Tiling" bezeichnetes Verfahren rekursiv zerlegt, um das Objekt in Bereiche zu zerlegen, die durch BH-Codes dargestellt werden. Es ist beabsichtigt, daß das Verfahren des "Tilings" eines Objektes, um es in die erfindungsgemäße Datenbank aufzunehmen, ein für einen Benutzer nicht sichtbares automatisiertes Verfahren ist. Jedes "Tile" wird in der erfindungsgemäßen Datenbank durch einen BH-Code dargestellt. Für Fachleute ist ersichtlich, daß der zum Zerlegen eines Objektes in seine entsprechenden BH-Codes erforderliche Grad des "Tilings" eine Funktion der erforderten Auflösung ist. Beispielsweise können Bereiche, die innere Bereiche darstellen, durch BH-Codes definiert werden, die relativ große "Tiles" darstellen. Die Bereiche nahe der Grenze (B&sub4;) erfordern eine höhere Auflösung mit einem entsprechend größeren Grad des "Tilings", um die Grenzen unter Verwendung von BH-Code zu definieren.
Es wird nun auf die Fig. 15 in Verbindung mit der Fig. 26(b) Bezug genommen. Die erfindungsgemäße BH-Code-Datenstruktur umfaßt ein Topologie-Bit 202. Gemäß den Lehren der vorliegenden Erfindung ist ein für einen inneren Bereich repräsentativer BH-Code definiert als ein Topologie-Bit aufweisend, das gleich einer logischen "1" gesetzt ist. Für Grenzbereiche identifizierende BH-Codes ist das Topologie- Bit 202 gleich einer logischen "0" gesetzt. Es ist ersichtlich, daß ein beliebiger einer Anzahl von logischen Zuständen verwendet werden kann, um innere Bereiche und Grenzbereiche darzustellen und das die in dieser Beschreibung angewendete Konvention nur exemplarisch für eine von vielen verfügbaren Konventionen ist.
Wie in der Fig. 26(b) gezeigt, wird eine objektpartitionierte Tabelle für das Objekt T&sub4; unter Verwendung der Lehren der Erfindung erzeugt, die zuvor unter Bezugnahme auf die Daten-Partitionierung beschrieben wurden. Wie in der Fig. 26(b) gezeigt, wird die Topologie für jedes Objekt (beispielsweise T&sub4;) durch eine bestimmte partitionierte Tabelle dargestellt, wobei der BH-Code identifiziert, ob ein bestimmter Bereich einen Teil eines Innenraums oder einer Grenze des Objektes bildet oder nicht. Andere Objekte (beispielsweise T&sub1;, T&sub2; und T&sub3; in der Fig. 24) werden "getilet" und entsprechende partitionierte Tabellen für jedes der Objekte werden erzeugt. Entsprechend können Zeilensegmente ebenso, wie es zuvor in dieser Beschreibung beschrieben wurde, unter Verwendung partitionierter Tabellen statt als Zeilensegmente unter Verwendung vierdimensionalen BH-Codes dargestellt werden. Demgemäß können unter Verwendung der Lehren der vorliegenden Erfindung alle mehrdimensionalen Objekte "getilet" und in Bereiche zerlegt werden, die durch BH-Codes und partitionierte Tabellen dargestellt werden.
Wenn Objekte "getilet" wurden und partitionierte Tabellen mit BH-Codes entsprechend entweder inneren Bereichen oder Grenzbereichen erzeugt wurden, können die in der Fig. 25 gezeigten Operationen an den BH-Codes durchgeführt werden, die in den entsprechenden partitionierten Tabellen angeordnet sind. Die Operationen des Trennens, des Überlappens und des Berührens können an den BH-Code-Einträgen ausgeführt werden, die die partitionierten Tabellen aufweisen. Entsprechend können in der Fig. 15 gezeigten Kernfunktionen auf den BH-Code angewendet werden, der die partitionierten Tabellen für die verschiedenen Objekte aufweist.
Unter Verwendung der erfindungsgemäßen Lehren wird es deutlich, daß die Grenzen der Objekte auch zusätzliche Dimensionen einschließlich Tiefe oder Zeit darstellen können. Darüber hinaus können in dem Fall von unscharfen Grenzen zusätzliche Dimensionen zum Definieren von Gradienten verwendet werden. Ein Beispiel, bei dem Grenzen unscharf sein können, und durch eine zusätzliche BH-Code-Dimension dargestellt werden, ist der Fall, beidem sich ein gasförmiger Nebel in einen umliegenden Raum ausdehnt oder eine unterirdische Wasserführung sich durch angrenzende Bereiche von Sand und Gestein ausdehnt. Die Verwendung von BH-Code zum Definieren topologischer Beziehungen liefert einmalige Vorteile gegenüber bekannten Systemen, die Grenzen unter Verwendung von Zeilensegmenten zum Definieren von Grenzen darstellen. Die erfindungsgemäße BH-Codes verwendende Punktmengen-Topologie geht über zwei Dimensionen hinaus und stellt einen wesentlichen Fortschritt der Technik dar.

Claims

1. Ein Verfahren zum Speichern dimensionaler Datenpunkte in einer Datenbank, umfassend die Schritte:

Bereitstellen eines Elements zum Ausführen des Schritts des Empfangens dimensionaler Datenpunkte;

Bereitstellen eines Elements zum Ausführen des Schritts des Bestimmens eines binären Hyperraum-Codes, BH-Codes, für die Datenpunkte durch rekursives Definieren räumlicher Zellen, in welchen sich ein vorgegebenes Volumen der dimensionalen Datenpunkte aufhält, wobei die räumlichen Zellen durch binäre Größen identifiziert werden, die den Ort der räumlichen Zellen relativ zueinander darstellen, dadurch gekennzeichnet, daß der BH-Code eine Datenstruktur enthält, die BH-Code-Daten und Metadaten aufweist.

2. Das Verfahren zum Speichern dimensionaler Daten nach Anspruch 1, ferner umfassend das Bereitstellen eines Elements zum Durchführen des Schritts des Erzeugens von BH- Code-Datenpartitionen auf der Grundlage der Anzahl der Dimensionen der dimensionalen Datenpunkte und des vorgegebenen Volumens.

3. Das Verfahren zum Speichern dimensionaler Daten nach Anspruch 2, wobei dann, wenn während der Erzeugung der BH- Code-Datenpartitionen das vorgegebene Volumen überschritten wird, zusätzliche Kind-Datenpartitionen erzeugt werden und die ursprüngliche Eltern-Datenpartition nicht beibehalten wird.

4. Das Verfahren zum Speichern dimensionaler Daten nach Anspruch 3, wobei die Anzahl der Kind-Partitionen, welche erzeugt werden, eine Funktion der Anzahl der Dimensionen der dimensionalen Daten ist.

5. Das Verfahren zum Speichern dimensionaler Daten nach Anspruch 4, wobei Attributdaten den die dimensionalen Daten darstellenden BH-Codes zugeordnet werden, wobei die Attributdaten ferner den BH-Code-Datenpartionen zugeordnet werden.

6. Das Verfahren zum Speichern dimensionaler Daten nach Anspruch 5, ferner einschließend ein Element zum Ausführen des Schritts des Erzeugens eines Datenwörterbuchs, wobei das Datenwörterbuch jeweils einen Eintrag für jede der erzeugten Datenpartitionen speichert.

7. Das Verfahren zum Speichern dimensionaler Daten nach Anspruch 6, wobei sämtliche Datenpartitionen, die in dem Datenwörterbuch gespeichert sind, Datenbankobjekte sind.

8. Das Verfahren zum Speichern dimensionaler Daten nach Anspruch 1, wobei die Metadaten Dimensionsbits enthalten, welche die Anzahl der Dimensionen in BH-Codedaten identifizieren.

9. Das Verfahren zum Speichern dimensionaler Daten nach Anspruch 8, wobei die Metadaten ein Typbit einschließen, um den Typ der BH-Code-Daten als ein geometrisches Objekt zu identifizieren.

10. Das Verfahren zum Speichern dimensionaler Daten nach Anspruch 9, wobei die Metadaten ein Topologiebit einschließen, um zu identifizieren, ob die BH-Code-Daten das Innere oder die Begrenzung der Topologie darstellen.

11. Das Verfahren zum Speichern dimensionaler Daten nach Anspruch 10, wobei die Metadaten Ebenenbits enthalten, um die Anzahl der Ebenen der Genauigkeit zu identifizieren, welche in den BH-Code-Daten für jede von den Dimensionsbits identifizierte Dimension codiert sind.

12. Das Verfahren zum Speichern dimensionaler Daten nach Anspruch 7, wobei das Datenwörterbuch eine Mehrdimensionstabelle enthält, welche eine Liste sämtlicher in einer zugehörigen relationalen Datenbank gespeicherten Tabellen, welche mehrdimensional sind, enthält.

13. Das Verfahren zum Speichern dimensionaler Daten nach Anspruch 12, wobei die relationale Datenbank eine Liste der dimensionalen Daten, einschließlich sowohl räumlicher als auch nicht-räumlicher, speichert.

14. Das Verfahren zum Speichern dimensionaler Daten nach Anspruch 13, wobei das Datenwörterbuch partitionierte Tabellen und nicht-partitionierte Tabellen enthält, wobei die nicht-partitionierten Tabellen Relationale-Datenbank-Tabellen umfassen, welche wenigstens eine Attribute aufweisende Spalte mit räumlichen BH-Code-Spalten enthalten.

15. Das Verfahren zum Speichern dimensionaler Daten nach Anspruch 14, wobei die partitionierten Tabellen mehrdimensionale Tabellen umfassen, welche wenigstens eine räumliche Spalte enthalten und welche auf der wenigstens einen der räumlichen Spalten partitioniert sind.

16. Eine mit einem Computer gekoppelte Einrichtung zum Speichern dimensionaler Daten in einer Datenbank, aufweisend:

ein mit dem Computer gekoppeltes Element zum Bestimmen eines binären Hyperraum-Codes (BH-Codes) für die dimensionalen Datenpunkte durch rekursives Zerlegen räumlicher Zellen, in welchen sich ein vorgegebenes Volumen der dimensionalen Datenpunkte aufhält, wobei die räumlichen Zellen durch binäre Größen identifiziert sind, die den Ort der räumlichen Zellen relativ zueinander darstellen, wobei der BH-Code eine Datenstruktur enthält, die BH-Code-Daten und Metadaten aufweist; und

ein Element zum Partitionieren und Speichern des BH-Codes in der Datenbank.

17. Die Einrichtung nach Anspruch 16, wobei das Element zum Partitionieren BH-Code-Datenpartitionen auf der Grundlage der Anzahl der Dimensionen der dimensionalen Datenpunkte und des vorgegebenen Volumens erzeugt.

18. Die Einrichtung nach Anspruch 17, wobei dann, wenn während des Erzeugens der BH-Code-Datenpartitionen das vorgegebene Volumen überschritten wird, zusätzliche Kind-Datenpartitionen erzeugt werden und die ursprüngliche Eltern-Datenpartition nicht beibehalten wird.

19. Die Einrichtung nach Anspruch 18, wobei die Anzahl der Kind-Partitionen, welche erzeugt werden, eine Funktion der Anzahl der Dimensionen der dimensionalen Daten ist.

20. Die Einrichtung nach Anspruch 19, wobei Attributdaten den die dimensionalen Daten darstellenden BH-Codes zugeordnet werden, wobei die Attributdaten ferner den BH-Code- Datenpartitionen zugeordnet sind.

21. Die Einrichtung nach Anspruch 20, ferner enthaltend ein Element zum Erzeugen eines Datenwörterbuchs, wobei das Datenwörterbuch jeweils einen Eintrag für jede der erzeugten Datenpartitionen speichert.

22. Die Einrichtung nach Anspruch 21, wobei sämtliche in dem Datenwörterbuch gespeicherten Datenpartitionen Datenbankobjekte sind.

23. Die Einrichtung nach Anspruch 16, wobei die Metadaten Dimensionsbits enthalten, welche die Anzahl der Dimensionen in den BH-Code-Daten identifizieren.

24. Die Einrichtung nach Anspruch 23, wobei die Metadaten ein Typbit enthalten, um den Typ der BH-Code-Daten als ein geometrisches Objekt zu identifizieren.

25. Die Einrichtung nach Anspruch 24, wobei die Metadaten ein Topologiebit enthalten, um zu identifizieren, ob die BH-Code-Daten das Innere oder die Begrenzung der Topologie darstellen.

26. Die Einrichtung nach Anspruch 25, wobei die Metadaten Ebenenbits enthalten, um die Anzahl der Ebenen der Genauigkeit zu identifizieren, welche in den BH-Code-Daten für jede von den Dimensionsbits identifizierte Dimension codiert sind.

27. Die Einrichtung nach Anspruch 22, wobei das Datenwörterbuch eine Mehrdimensionstabelle enthält, welche eine Liste sämtlicher in einer zugehörigen relationalen Datenbank gespeicherten Tabellen enthält, welche mehrdimensional sind.

28. Die Einrichtung nach Anspruch 27, wobei die relationale Datenbank eine Liste der dimensionalen Daten, einschließlich sowohl räumlicher als auch nicht-räumlicher speichert.

29. Die Einrichtung nach Anspruch 28, wobei das Datenwörterbuch partitionierte Tabellen und nicht-partitionierte Tabellen enthält, wobei die nicht-partitionierten Tabellen Relationale-Datenbank-Tabellen umfassen, welche wenigstens eine Attribute aufweisende Spalte mit räumlichen BH-Code- Spalten enthält.

30. Die Einrichtung nach Anspruch 28, wobei die partitionierten Tabellen mehrdimensionale Tabellen umfassen, welche wenigstens eine räumliche Spalte enthalten und welche auf der wenigstens einen der räumlichen Spalten partitioniert sind.

31. Das Verfahren nach Anspruch 1, ferner einschließend ein Verfahren zum Speichern eines Liniensegments in einer Datenbank, umfassend die Schritte:

Bereitstellen eines Elements zum Durchführen des Schritts des Empfangens von Datenpunkten, die einen ersten (x&sub1;, y&sub1;) und einen zweiten (x&sub2;, y&sub2;) Endpunkt des Liniensegments repräsentieren;

Bereitstellen eines Elements zum Durchführen des Schritts des Bestimmens eines binären Hyperraum-Codes (BH)- Codes für den ersten und den zweiten Endpunkt, indem räumliche Zellen definiert werden, in welchen sich der erste und der zweite Endpunkt aufhalten, wobei die räumlichen Zellen durch binäre Größen identifiziert sind, die den Ort der räumlichen Zellen relativ zueinander darstellen.

32. Das Verfahren nach Anspruch 31, wobei das Liniensegment durch einen Vier-Dimensions-BH-Code dargestellt wird.

33. Das Verfahren nach Anspruch 32, wobei eine erste Dimension x&sub1; darstellt, eine zweite Dimension y&sub1; darstellt, eine dritte Dimension x&sub2; darstellt und eine vierte Dimension y&sub2; darstellt.

34. Das Verfahren nach Anspruch 32, wobei eine Mehrzahl von Liniensegmenten in der Datenbank gespeichert wird, wobei jedes der Liniensegmente durch einen BH-Code dargestellt wird.

35. Das Verfahren nach Anspruch 34, ferner bereitstellend ein Element zum Ausführen der Schritte des Erzeugens von BH-Code-Datenpartitionen auf der Grundlage einer vorgegebenen Anzahl von BH-Code-Einträgen, welche in irgendeiner Partition angeordnet sein können.

36. Das Verfahren nach Anspruch 35, wobei dann, wenn während des Erzeugens von BH-Code-Datenpartitionen die vorgegebene Anzahl von BH-Code-Einträgen überschritten wird, zusätzliche Kind-Datenpartitionen erzeugt werden und die ursprüngliche Eltern-Datenpartition nicht beibehalten wird.

37. Das Verfahren nach Anspruch 36, wobei für jede der Eltern-Datenpartitionen, in welcher die vorgegebene Anzahl von BH-Code-Einträgen überschritten wird, sechszehn Kind-Datenpartitionen erzeugt werden.

38. Das Verfahren nach Anspruch 37, wobei von den sechszehn Datenpartitionen nur diejenigen Partitionen, in welchen der BH-Code tatsächlich gespeichert ist, in der Datenbank aufrechterhalten werden.

39. Das Verfahren nach Anspruch 38, wobei Attributdaten den die dimensionalen Daten darstellenden BH-Codes zugeordnet werden, wobei die Attributdaten ferner den BH-Code-Datenpartitionen zugeordnet werden.

40. Das Verfahren nach Anspruch 39, ferner umfassend ein Element zum Durchführen der Schritte des Erzeugens eines Datenwörterbuchs, wobei das Datenwörterbuch jeweils einen Eintrag für jede der erzeugten Datenpartitionen speichert.

41. Das Verfahren nach Anspruch 40, wobei sämtliche in dem Datenwörterbuch gespeicherten Datenpartitionen Datenbankobjekte sind.

42. Das Verfahren nach Anspruch 41, wobei der BH-Code aus einer Datenstruktur besteht, die BH-Code-Daten und Metadaten aufweist.

43. Das Verfahren nach Anspruch 42, wobei die Metadaten ein Typbit enthalten, um den Typ der BH-Code-Daten als ein geometrisches Objekt zu identifizieren.

44. Das Verfahren nach Anspruch 41, wobei das Datenwörterbuch eine Mehrdimensionstabelle enthält, welche eine Liste sämtlicher in einer zugehörigen relationalen Datenbank gespeicherten Tabellen, welche mehrdimensional sind, enthält.

45. Das Verfahren nach Anspruch 41, ferner einschließend ein Verfahren zum Zugreifen auf die gespeicherten Liniensegmente, umfassend die Schritte:

Bereitstellen eines Elements zum Durchführen des Schritts, daß ein Benutzer einen interessierenden Bereich definiert;

Bereitstellen eines Elements zum Durchführen des Schritts des Identifizierens, welche der Datenpartitionen Liniensegmente definieren, welche zumindest partiell in dem interessierenden Bereich angeordnet sind;

Bereitstellen eines Elements zum Durchführen des Schritts des Zusammenstellens einer Liste der identifizierten Datenpartitionen;

Bereitstellen eines Elements zum Durchführen des Schritts des Bestimmens, ob jeder der BH-Code-Einträge in den identifizierten Partitionen in dem interessierenden Bereich angeordnet ist und des Berichtens derjenigen BH-Code- Einträge, welche in dem Bereich angeordnet sind, an den Be¬ nutzer.

46. Das Verfahren nach Anspruch 45, wobei die Schritte des Identifizierens, welche der Datenpartitionen Liniensegmente definieren, welche zumindest teilweise in dem interessierenden Bereich angeordnet sind, die Schritte einschließt:

Bereitstellen eines Elements zum Durchführen des Schritts des Definierens von sechszehn möglichen Partitionsformen für die gespeicherten Liniensegmente, wobei die sechszehn Partitionsformen die Datenpartitionen in dem Datenwörterbuch repräsentieren;

Bereitstellen eines Elements zum Durchführen des Schritts des Überprüfens jedes der BH-Code-Einträge in den in dem Datenwörterbuch gespeicherten Partitionen und des Decodierens des BH-Codes.

47. Die Einrichtung nach Anspruch 17, ferner einschließend eine mit einem Computer gekoppelte Einrichtung zum Speichern eines Liniensegments in einer Datenbank, aufweisend:

ein Element zum Empfangen von Datenpunkten, die einen ersten (x&sub1;, y&sub2;) und einen zweiten (x&sub2;, y&sub2;) Endpunkt des Liniensegments darstellen;

ein Element zum Bestimmen eines binären Hyperraum-Codes (BH-Codes) für den ersten und den zweiten Endpunkt, indem räumliche Zellen definiert werden, in welchen sich der erste und der zweite Endpunkt aufhalten, wobei die räumlichen Zellen durch binäre Größen identifiziert sind, die den Ort der räumlichen Zellen relativ zueinander repräsentieren.

48. Die Einrichtung nach Anspruch 47, wobei das Liniensegment durch einen Vier-Dimensions-BH-Code dargestellt wird.

49. Die Einrichtung nach Anspruch 48, wobei eine erste Dimension x&sub1; darstellt, eine zweite Dimension y&sub1; darstellt, eine dritte Dimension x&sub2; darstellt und eine vierte Dimension y&sub2; darstellt.

50. Die Einrichtung nach Anspruch 49, wobei eine Mehrzahl von Liniensegmenten in der Datenbank gespeichert ist, wobei jedes der Liniensegmente durch einen BH-Code dargestellt wird.

51. Die Einrichtung nach Anspruch 50, ferner bereitstellend ein Element zum Erzeugen von BH-Code-Datenpartitionen auf der Grundlage einer vorgegebenen Anzahl von BH-Code-Einträgen, welche in irgendeiner Partition angeordnet werden können.

52. Die Einrichtung nach Anspruch 51, wobei dann, wenn während des Erzeugens von BH-Code-Datenpartitionen die vorgegebene Anzahl von BH-Code-Einträgen überschritten wird, zusätzliche Kind-Datenpartitionen erzeugt werden und die ursprüngliche Eltern-Datenpartition nicht beibehalten wird.

53. Die Einrichtung nach Anspruch 52, wobei für jede der Eltern-Datenpartitionen, in welcher die vorgegebene Anzahl von BH-Code-Einträgen überschritten wird, sechszehn Kind-Datenpartitionen erzeugt werden.

54. Die Einrichtung nach Anspruch 53, wobei von den sechszehn Datenpartitionen nur diejenigen Partitionen, in welchen tatsächlich BH-Code gespeichert ist, in der Datenbank aufrechterhalten bleiben.

55. Die Einrichtung nach Anspruch 54, wobei Attributdaten den die dimensionalen Daten repräsentierenden BH-Codes zugeordnet werden, wobei die Attributdaten ferner den BH- Code-Datenpartitionen zugeordnet werden.

56. Die Einrichtung nach Anspruch 55, ferner einschließend ein Element zum Erzeugen eines Datenwörterbuchs, wobei das Datenwörterbuch jeweils einen Eintrag für jede der erzeugten Datenpartitionen speichert.

57. Die Einrichtung nach Anspruch 56, wobei sämtliche in dem Datenwörterbuch gespeicherten Datenpartitionen Datenbankobjekte sind.

58. Die Einrichtung nach Anspruch 57, wobei der BH-Code aus einer Datenstruktur besteht, die BH-Code-Daten und Metadaten aufweist.

59. Die Einrichtung nach Anspruch 58, wobei die Metadaten ein Typbit enthalten, um den Typ der BH-Code-Daten als ein geometrisches Objekt zu identifizieren.

60. Die Einrichtung nach Anspruch 59, wobei das Datenwörterbuch eine Mehrdimensionstabelle enthält, welche eine Liste sämtlicher in einer zugehörigen relationalen Datenbank gespeicherten Tabellen enthält, welche mehrdimensional sind.

61. Die Einrichtung nach Anspruch 60, ferner einschließend eine Einrichtung zum Zugreifen auf die gespeicherten Liniensegmente, aufweisend:

ein Element für einen Benutzer zum Definieren eines interessierenden Bereichs;

ein Element zum Identifizieren, welche der Datenpartitionen Liniensegmente definieren, welche zumindest teilweise in dem interessierenden Bereich angeordnet sind;

ein Element zum Zusammenstellen einer Liste der identifizierten Datenpartitionen;

ein Element zum Bestimmen, ob jeder der BH-Code-Einträge in den identifizierten Partitionen innerhalb des interessierenden Bereichs angeordnet ist und zum Berichten derjenigen BH-Code-Einträge an den Benutzer, welche in dem Bereich angeordnet sind.

62. Das Verfahren nach Anspruch 1, ferner einschließend ein Verfahren zum Speichern einer topologischen Darstellung eines ersten Objekts in einer Datenbank, umfassend die Schritte:

Bereitstellen eines Elements zum Durchführen des Schritts des Definierens eines Inneren I&sub1; und einer Begrenzung B&sub1; für das erste Objekt; und

Bereitstellen eines Elements zum Durchführen des Schritts des rekursiven Zerlegens des ersten Objekts in erste Objekt-Verlegeelement(Tile)-Gebiete, die durch BH-Codes definiert werden.

63. Das Verfahren nach Anspruch 62, ferner umfassend den Schritt des Erzeugens einer Objekt-Portioniert-Tabelle für das erste Objekt, wobei die BH-Codes identifizieren, ob jedes der ersten Tile-Gebiete Teil des Inneren I&sub1; oder der Begrenzung B&sub1; sind.

64. Das Verfahren nach Anspruch 63, ferner einschließend die Schritte:

Bereitstellen eines zweiten Objekts;

Bereitstellen eines Elements zum Durchführen des Schritts des Definierens eines Inneren I&sub2; und einer Begrenzung B&sub2; für das zweite Objekt; und

Bereitstellen eines Elements zum Durchführen des Schritts des rekursiven Zerlegens des zweiten Objekts in zweite Objekt-Verlegeelement(Tile)-Gebiete, die durch BH-Codes definiert werden.

65. Das Verfahren nach Anspruch 64, ferner umfassend den Schritt des Erzeugens einer Objekt-Partitioniert-Tabelle für das zweite Objekt, wobei die BH-Codes für das zweite Objekt identifizieren, ob jedes der zweiten Objekt-Tile-Gebiete Teil des Inneren I&sub2; oder der Begrenzung B&sub2; sind.

66. Das Verfahren nach Anspruch 65, ferner einschließend den Schritt des Anwendens einer Schnittmethodik auf die BH- Codes in der ersten und der zweiten Objekt-Partitioniert-Tabelle, um die Beziehung des ersten und des zweiten Objekts zueinander zu bestimmen.

67. Das Verfahren nach Anspruch 66, wobei die Schnittmethodik eine Egenhofer-Vier-Punkt-Schnittmethodik ist.

68. Die Einrichtung nach Anspruch 16, ferner einschließend eine Einrichtung zum Speichern einer topologischen Darstellung eines ersten Objekts in einer Datenbank, aufweisend:

ein Element zum Definieren eines Inneren I&sub1; und einer Begrenzung B&sub2; für das erste Objekt; und

ein Element zum rekursiven Zerlegen des ersten Objekts in Erste-Objekt-Verlegeelement(Tile)-Gebiete, die durch binäre Hyperraum-Codes (BH-Codes) definiert sind.

69. Die Einrichtung nach Anspruch 68, ferner enthaltend ein Element zum Erzeugen einer Objekt-Partitioniert-Tabelle für das erste Objekt, wobei die BH-Codes identifizieren, ob jedes der ersten Verlegeelement-Gebiete Teil des Inneren I&sub1; oder der Begrenzung B&sub1; sind.

70. Die Einrichtung nach Anspruch 69, ferner einschließend ein zweites Objekt;

ein Element zum Definieren eines Inneren I&sub2; und einer Begrenzung B&sub2; für das zweite Objekt; und

ein Element zum rekursiven Zerlegen des zweiten Objekts in zweite Objekt-Verlegeelement(Tile)-Gebiete, die durch BH- Codes definiert sind.

71. Die Einrichtung nach Anspruch 70, ferner einschließend ein Element zum Erzeugen einer Objekt-Partitioniert-Tabelle für das zweite Objekt, wobei die BH-Codes für das zweite Objekt identifizieren, ob jedes der zweiten Verlegeelement-Gebiete Teil des Inneren I&sub2; oder der Begrenzung B&sub2; sind.

72. Die Einrichtung nach Anspruch 71, ferner einschließend ein Element zum Anwenden einer Schnittmethodik auf die BH-Codes in der ersten und der zweiten Objekt-Partitioniert- Tabelle, um die Beziehung des ersten und des zweiten Objekts zueinander zu bestimmen.

73. Die Einrichtung nach Anspruch 72, wobei die Schnittmethodik eine Egenhofer-vier-Punkt-Schnittmethodik ist.