1 Zusammenfassung der Erfindung

Die Erfindung bezieht sich auf ein anwendungsneutrales Datenbanksystem (DBS) zur Spei¬ cherung, Wiedergewinnung und Manipulation von Rasterdaten, d.h. Arrays beliebiger (fester oder variabler) Größe und Dimension über beliebigen Array-Basistypen. Die Erfindung ist charakterisiert durch die strikte Trennung von logischer (konzeptueller) und physischer Ebene, um Datenunabhängigkeit zu erreichen, also die Möglichkeit, Rasterdaten unabhängig von ihrer physischen Ablagestruktur, Codierung und Kompression anzusprechen. Abhängig von dem Datenformat, das die Applikation anfordert, nimmt das DBS transparent unter Berücksichtigung von Aspekten der Zugriffs- und Übertragungsoptimierung die erforderliche Umwandlung und (De-) Kompression vor.

Auf der konzeptuellen Ebene vermittelt die explizite Definition von Arraystrukturen über eine Datendefinitionssprache (DDL) dem DBS das Wissen über die vollständige Array-Semantik. Eine orthogonale Anfragesprache (DML) enthält Array-spezifische Primitive sowie Operato¬ ren, die beliebig kombiniert werden können, um optimierbare DML- Ausdrücke und -Prädi¬ kate zu formulieren. Standardfunktionen gestatten die explizite Foπnatumwandlung. Auf der physischen Ebene erlaubt eine Speicherarchitektur, die auf der Kombination von Array-Kachelung und einer räumlichen Zugriffsstruktur (Geo-Index) beruht, den effizienten Zugriff auf Arrays und Teilarrays sowie die Verteilung von Arrays über mehrere, unter Umständen heterogene Speichermedien.

Die Erfindung eignet sich vor allem für Rasterapplikationen mit hohen Anforderungen hin¬ sichtlich Funktionalität, Datenvolumen, Netzwerkfähigkeit und Zugriffszeit - insbesondere verteilte, offene Multimediasysteme.

2 Technischer Hintergrund der Erfindung

2.1 Technisches Gebiet, auf das sich die Erfindung bezieht

Die vorliegende Erfindung bezieht sich auf ein anwendungsneutrales Datenbanksystem (DBS) zur Speicherung, Wiedergewinnung und Manipulation von beliebigen Arrays in Datenbanken. Der Begriff Array wird in diesem Zusammenhang in einem programmiersprachlichen Sinn verstanden: Eine Sequenz fester oder variabler Länge von gleichartig strukturierten Datenele¬ menten (Zellen; in den Bereichen Computergraphik und Bildverarbeitung oft als Pixel bezeichnet), die über ihre (ganzzahligen) Positionsnummern adressiert werden. Die Zellen selbst können selbst wieder Arrays sein, sodaß sich Arrays beliebiger Dimension konstruieren lassen.

2.2 Einschlägiger Stand der Technik mit Fundstellen

DBSe haben eine beträchtliche Tradition und spielen ein wichtige Rolle in der Speicherung, Wiedergewinnung und Manipulation großer Dateπmengen. Dazu bieten sie Mittel für flexi¬ blen Datenzugriff, Integritäts- und Konsistenzverwaltung, Mehrbenutzerverwaltung, Anfrage- und Speicheroptimierung, Backup und Recovery etc. Zur Kommunikation zwischen Daten¬ bankanwendung (Client) und dem Datenbankprogramm (Server) existieren diverse Techni¬ ken, die z.B. über Funktionsbibliotheken (Applicauon Programmer 's Interface, API), die an die Anwendung gebunden werden, eine für die Anwendung unsichtbare Netzwerk-Datenkom¬ munikation einschließlich Datenkonversion vornehmen.

Allerdings sind diese Vorteile bisher nur für Datenelemente wie ganze Zahlen und Strings sowie seit einiger Zeit für sogenannte lange Felder oder Blobs (binary large objects), also variabel lange Byteketten, verfügbar. Allgemeine Rasterdaten (z.B. Audio (ID), Rasterbilder (2D) und Video (3D) werden gemäß gängiger Praxis als Bitketten betrachtet und auf lineare Blobs abgebildet; beispielsweise konstatieren in [MwLW-89] die Autoren zuerst "die Bild- Rohdaten bilden eine Pixelmatrix", um dann fortzufahren "die Rohdaten erscheinen [in der Datenbank] einfach als ein Bitstring".

Aufgrund des Semantikverlusts durch die FORTRAN-artige Linearisierung in der Datenbank können Rasterdaten nur als Ganzes oder zeilenweise gelesen und geschrieben werden. Raster¬ strukturen können nicht in Suchkriterien angegeben werden und können auch nicht durch das DBS bearbeitet werden, um etwa relevante Ausschnitte zu extrahieren. Darüberhinaus muß sich die Anwendung auf eines aus der Vielzahl existierender Datenformate zur Codierung und Kompression fesüegen. Diese Wahl ist für auch alle anderen Datenbank- Applikationen ver¬ bindlich, die darauf zugreifen, und ihnen allein obliegt die korrekte Decodierung und Dekom- pression. Dem Datenbank-Anwendungsprogrammierer wird damit eine Vielzahl von maschinennahen, sich wiederholenden, fehleranfalligen und zeitraubenden Programmierauf¬ gaben aufgebürdet

Weiterhin zerstört die Linearisierung von Arrays im Sekundär- und Tertiärspeicher die Nach¬ barschaftsbeziehung zwischen Arrayelementen, wie Abb. 2 zeigt Ein Ausschnitt, der auf logi¬ scher Ebene ein hohes Maß an Lokalität aufweist, wird auf dem Hintergrundspeicher in einer Art verstreut, die nur den zeilenweisen Zugriff begünstigt und alle anderen Zugriffsarten dra¬ stisch benachteiligt Die Folge ist ein ungenügendes Antwortzeitverhalten. Ein typisches System wird in [MwLW-89] beschrieben: Rasterbilder liegen in der Datenbank als Blobs, codiert in einem von mehreren möglichen Bildaustauschfoπnaten (z.B. TIFF oder

GIF); ein zusätzliches Flag zeigt der Anwendung das aktuell verwendete Format an. Das EXTRAJEXCESS-System [VaDe-91] bietet eine Algebra für die Modellierung und Abfrage von Rasterdaten, jedoch keine darauf abgestimmte Speichertechnik, sodaß nur kleine Arrays (z.B. 4x4-Matrizen) effizient verwaltet werden können. Sarawagi und Stonebraker [SaSt-94] haben kürzlich eine Speicherarchitektur für Arrays vorgeschlagen, die auf Kachelung (siehe unten) basiert, aber ohne räumlichen Index zur Zugriffsbeschleunigung und ohne optimierbare Anfrageunterstützung neben der reinen Ausschnittsbildung. In [Baum-94] wird ein Ansatz für die Rasterdatenverwaltung vorgeschlagen, der sowohl die konzeptuelle als auch die physische Ebene behandelt Eine allgemeine Lösung für das Problem der Datenunabhängigkeit, also der Bearbeitung von Rasterdaten in einer DML bzw. einem API ohne Kenntnis und Bezugnahme auf ihre physische Ablagestruktur, Codierung und Kompression, existiert derzeit nicht In der Bildverarbeitung werden Kachelungstechniken für die Bearbeitung von Bildern ver¬ wendet, die aufgrund ihrer Größe nicht als Ganzes in den Hauptspeicher passen (siehe z.B. [Tamu-80]. Eine Kachel ist ein rechteckiger Bildausschnitt. Das Bild wird so in Kacheln zer¬ legt, daß sich diese nicht überlappen und insgesamt das gesamte Bild überdecken (siehe Abb. 5.1). Innerhalb einer Kachel werden die Daten vermöge eines konventionellen Linearisie¬ rungsschemas abgelegt Kachelung kann vorteilhaft eingesetzt werden, um Nachbarschaft innerhalb eines Arrays auf einem linearen Speichermedium zu simulieren, und bildet daher eine wichtige Grundlage für die vorliegende Erfindung.

Für die Verwaltung geometrischer Daten wie Punkte, Linien und Flächen existiert eine Viel¬ zahl von räumlichen Indizes (Geo-Indizes), um den Zugriff auf derartige Datenelemente in einer Datenbank zu beschleunigen [Guet-94]. In der vorliegenden Erfindung wird ein derarti¬ ger Geo-Index zur schnellen Kachelsuche eingesetzt.

3 Darstellung der Erfindung

3.1 Zu lösende technische Aufgabe

Die vorliegende Erfindung beschreibt ein DBS für Rasterdaten, das folgendes leistet:

^• Verwaltung der vollen Semantik von beliebigen Arrays.

• Deklarative Speicherung, Wiedergewinnung und Bearbeitung von Rasterdaten auf der semantischen Ebene von Arrays.

^• Datenunabhängigkeit: Die Präsentation von Arraydaten durch das DBS ist explizit von der Anwendung in einer Vielzahl unterschiedlicher Datenformate wählbar, unabhängig vom datenbank-internen Speicherformat der Codierung und Kompression.

^• Eine Speichertechnik, die die effiziente Verwaltung sehr großer Arrays erlaubt, die sich über mehrere, möglicherweise heterogene, Datenträger erstrecken können.

^• Speicher- und Anfrageoptimierung.

3.2 Vorteilhafte Wirkungen der Erfindung

Ein erfindungsgemäßes DBS ist insbesondere für Raster- Applikationen geeignet, die hohe Anforderungen hinsichtlich Funktionalität, Datenvolumen, Netzwerkfähigkeit und Antwort¬ zeitverhalten stellen. Zu den wichtigsten Anwendungsfeldem zählen verteilte, offene Multi¬ mediasysteme, Medizinische Büdverart>eitιmg/PACS/TCrarjkenhaus-Infoπnationssystem e, geographische und Umwelt-Informationssysteme (GIS/EIS) sowie wissenschaftliche Visuali-

sierung (Maschinenbau, Meteorologie, Hydrologie, Astronomie). Im einzelnen lassen sich folgende Vorteile erzielen:

• Anwendungsneutralität: Die Array-spezifischen Datenstrukturen und Operationen lassen sich beliebig mit konventionellen Definitionen, Ausdrücken und Prädikaten mischen; damit kann ein erfindungsgemäßes DBS in einer Vielzahl von Anwendungsfeldern eingesetzt werden.

• Datenunabhängigkeit: Die DBS-Funktionalität ist auf beliebigen Plattformen und Netzwer¬ ken verfügbar und unabhängig von einem speziellen Datenformat oder einer bestimmten Menge von Datenfoπnaten.

• Datenbank-Anwendungsprogrammierer werden von maschinennahen, sich wiederholen¬ den, feUeranfalligen und zeitraubenden Aufgaben befreit, indem vom DBS einheitliche Standard-Lösungen angeboten werden.

• Geringerer Ressourcenverbrauch aufgrund einer angepaßten Speicherarchitektur und einer deklarativen, optimierbaren Anfragesprache; insbesondere hängt das Antwortzeitverhalten vom Anfrageergebnis ab und nicht vom Gesamtdatenvolumen, auf dem die Anfrage ausge¬ führt wird.

• Transparente Integration von Speichermedien (z.B. Festplatte, Jukebox, Bandarchive) für Datenmengen beliebiger Größe, insbesondere für Arrays, die sich über mehrere Datenträ¬ ger erstrecken.

• Klassische Datenbankdienste wie Transaktionsunterstützung, Integritätsverwaltung und Recovery werden für Rasterdaten verfügbar.

4 Erläuterungen zu den Abbildungen

Abb. 1: Schematischer Aufbau einer erfindungsgemaßen Anordnung:

Ein oder mehrere Rechner, auf denen Rasterdaten- Anwendungen laufen, sind über ein lokales oder Weitverkehrsnetz mit dem Server verbunden, auf dem das Raster-DBS läuft

Abb. 2: Zerstörung der räumlichen Nachbarschaft durch die Linearisierung im Zuge derSpeicherabbildung, gezeigt am Beispiel der Array-Ausschnittsbildung. (Kreise bedeuten durch den Ausschnitt selektierte Zellen, Punkte repräsentie¬ ren von der Anfrage nicht erfaßte Zellen.)

Abb. 2.1: 2-D Bild mit markiertem Ausschnitt (logische Sicht).

Abb. 2.2: Linearisiertes Bild mit verteilten Bestandteilen des selektierten Ausschnitts.

Abb. 3: Visualisierung der Wirkung von Beispielsanfragen auf Arrays

(selektierte Teile schraffiert dargestellt). Abb. 3.1: Trimm-Operation, angewendet auf ein 2-D-Array. Abb. 3.2: Projektion entlang der x/z-Ebene eines 3-D- Arrays; das Ergebnis ist ein 2-D- Array. Abb. 33: Projektion entlang der y-Achse eines 3-D-Arrays; das Ergebnis ist ein 1-D- Array.

Abb. 4: Erweiterung eines variablen 2-D-Arrays im Zuge einer Zuweisung.

Abb. 5: Rasterdatenspeicherung mittels einer Kombination von Kachelung und Geo-

Index; hier Beispiel der Abspeicherung eines 2-D-Arrays. Abb. 5.1: Zerlegung eines 2-D-Bilds in Kacheln. Abb. 52: Geo-Index zur Kachel-Zerlegung in Abb. 5.1.

Abb. 6: Retrieval-Algorithmus als Flußdiagramm.

Abb. 7: Update- Algorithmus als Flußdiagramm.

Abb. 8: Systemarchitektur eines erfindungsgemäßen Rasterdatenbanksystems.

Die mit Pfeilen markierten internen Schnittstellen eignen sich besonders zum Dazwischenschalten von Netzwerkkommunikation.

5 Beschreibung eines Weges zur Ausführung der Erfindung

Die vorliegende Erfindung wird unter Bezugnahme auf eine bestimmte geeignete Ausführung beschrieben. Die Erfindung ist jedoch nicht auf diese Ausführung beschränkt; vielmehr lassen sich viele Variationen und Modifikationen vornehmen, ohne den Bereich der Erfindung zu ver¬ lassen, wie er in den unten angegebenen Ansprüchen bzw. deren Äquivalent dargestellt ist.

5.1 Raster-Semantik

Im folgenden findet die C-t-f-artige DDL eines objektorientierten DBS Verwendung; für die Beispielsanfragen wird eine SQL-artige DML benutzt Es ist offensichtlich, wie die dahinter- liegenden Konzepte auf andere Modelle und Systeme zu übertragen sind; die Erfindung beschränkt sich in keiner Weise auf eine bestimmte Syntax, Programmiersprache, ein Betriebssystem oder ein bestimmtes Datenbank-Paradigma.

5.1.1 Stjrukturdefinition

Das konzepmelle Schema wird anhand einer Beispiels-Miniwelt beschrieben, die dem Bereich Sensor-Fusion in Umweltinformationssystemen entstammt Drei Objektklassen Seismic- Sensor für variabel-lange 1 -D-Zeitreihen, Lands ^' atTM für Landsat-TM-Satellitenbilder im Format 7020x5760 (2-D) und WeatherSimulation für atmosphärische Temperaturvertei¬ lungen in einem lOOOxlOOOxlOOO-Bereich (3-D) werden unten definiert; das Symbol # notiert eine variable Anzahl von Zellen in der angegebenen Dimension: class SeismicSensor : public PObject { public:

Coordinate location ; / / geogr. Position des Sensors unsigned data [ # 1 ; // Sequenz der Meßwerte

> ; class LandsatTM: public PObject { public :

Orbit orbitalData; / / Umlaufbahnparameter

Aperture aperture; // Apertur

ERSATZBLAπ (REGEL 26)

struct { unsigned short cl , c2 , c3 , c4 , c5 , c6 , c7; } data [ 7020 1 [ 5760 ] ; // 7-Band-Bilddaten } ; class WeatherSimulation: public PObject

{ public : float data [ 1000 1 [ 1000 ] [ 1000 ] ; // Temperaturwerte

> ;

5.1.2 Operationen

Die Arrayoperationen lassen sich in wertebasierte Operationen, Änderungsoperationen und allgemeine Konstruktoren einordnen. Folgende wertebasierten Operationen werden vorge¬ schlagen:

Konstanten. Für den Gebrauch in Anfrageausdrücken oder um ein Array zu initialiseren, las¬ sen sich Zellwerte explizit oder implizit angeben. Beispiel: "Ein 2x2 Ganzzahl-Array, überall mit 0 besetzt." Dies wird durch eine direkte Auflistung beschrieben, wobei die Arraystruktur angemessen erscheint hier durch geschweifte Klammem:

{ { 0 , 0 } , { 0 , 0 } } Eine implizite Angabe geschieht durch einen deskriptiven Ausdruck der Art

{ 0 : [ 1024 ] [ 768 ] } der in diesem Fall bedeutet "ein 1024 x 768 Bild mit 0 in allen Zellen". Trimmen erzeugt einen rechteckigen Arrayausschnitt Beispielsweise läßt sich die Anfrage "der Bildausschnit aller Landsat-TM-Bildern, der durch die Eckpunkte (xO.yO) und (xl.yl) festgelegt isf (vgl. Abb. 3.1) formulieren als select l . data [ xO . . xl ] [ yO . . yl ] from Landsat TM 1

Projektion extrahiert eine Schicht der Dicke 1 aus einem Array (Abb. 3.2). Beispiel: "Die Lufttemperaturverteilung über dem gesamten Simulationsgebiet in einer Höhe über Grund h" wird ausgedrückt als select w.data [ # ] [ h l [ # ] from WeatherSimulation w

Induzierte Operationen. Für jede auf dem Array-Basistyp verfügbare Operation (z.B. Sub¬ traktion auf Grauwert-Pixeln) wird eine korrespondierende Operation zur Verfügung gestellt, die diese Basisoperation simultan auf alle Arrayzellen anwendet (z.B. Subtraktion zweier Grauwertbilder). Beispiel: "Den c3-Kanal aller Landsat-TM-Bilder, um den Wert d in der Intensität vermindert ^' ''. select l .data. c3 - d from Lands atTM 1

Prädikats-Iteratoren. Das Rasterprädikat some (p) ergibt true genau dann, wenn minde¬ stens eine der Zellen eines Booleschen Arrays p den Wert true enthält Entsprechend evalu- iert all (p ) zu true genau dann, wenn alle Zellen von p true enthalten. Beispiel: "Der Ort aller Seismik-Sensoren, an denen irgendwann in der Vergangenheit die Erdbebenaktivität t überstiegen hat''. select s . location from SeismicSensor s where some ( s .data > t )

Als nächstes werden Änderungsoperationen aufgelistet

Initialisierung. Diese Operation, die implizit bei jeder Erzeugung eines Arrays als Teil eines Tupels, eines Objekts o.a. aufgerufen wird, setzt alle Zellen auf Nullwerte und die Länge varia¬ bler Arrays auf 0.

Zuweisung. Durch eine Zuweisung erhalten die Zellen in einem Array oder einem Teil eines Arrays neue Werte. Falls das Aιτay variabel ist und die zu besetzenden Zellpositionen nicht alle in dem vorher existierenden Array liegen, wird das Array entsprechend erweitert Bei¬ spielsweise wird in Abb. 4 das existierende Array a. old um den Teil v.new erweitert, der a . old nur teilweise überdeckt Daher wird als erweitertes Array a . new gebildet Zwei neu erzeugte Gebiete a . auxl und a . aux2 dienen zur Erhaltung der Rechteckform und werden mit Nullwerten initialisiert

Zuletzt werden allgemeine Konstruktionsprinzipien aufgeführt, die für die Flexibilität und Allgemeinheit der Erfindung wesentlich sind.

Orthogonale Anfragesprache. Die oben angegebenen Operationen sind vorzugsweise in eine deklarative DML eingebettet die beschreibt, was getan werden soll, und nicht, wie es geschehen soll, und damit den Weg für intelligente Optimierung bereitet. Ausdrücke und Prä¬ dikate werden (rekursiv) gebildet aus den Array-Basisoperationen, den bekannten Booleschen Operatoren, Klammerung, funktionale Schachtelung sowie u.U. den Aufruf weiterer Funktio¬ nen bzw. Methoden.

Beispiel 1 : "Die Temperaturverteilung in der Höhe h von allen Simulationen, bei denen irgendwo in dem durch die Eckpunkte (xO,y0,z0) and (xl,yl,zl) markierten Gebiet die Tempe¬ ratur t überschritten wird." Trimm n in drei Dimensionen wird hier kombiniert mit dem indu¬ zierten Vergleich und dem Kollabieren in einen einzigen Booleschen Wert durch den some- Operator: select w.data [ # , h, # ] from WeatherSimulation w where some ( w.data [ xO . . xl ] [ yO . . yl 1 [ zO . . zl ] > t ) Beispiel 2: "Die Landsat-TM-Bilder, die Regionen mit beobachteter seismischer Aktivität ent¬ halten, sowie die zugehörigen Sensorpositionen". Zusätzlich zu den Rasteroperationen finden hier geometrische Operationen area ( ) und contains Verwendung sowie Schachtelung: select l .data, s . location from LandsatTM 1 , SeismicSensor s where area ( 1. orbitalData , 1. aperture ) contains s . location and some ( s .data > t ) Datenunabhängigkeit Rasterdaten werden dem Anwendungsprogramm als generische Arrays präsentiert; die Funktionalität, die auf Arrays angeboten wird, ist unabhängig von ihrer physischen Struktur in der Datenbank. Finden keine anderweitigen Festlegungen statt, dann passieren Daten die DBS-Schnittstelle in der Hauptspeicher-Darstellung der Zielmaschine und der Programmiersprache der Applikation, z.B. als C-H-Array, sodaß eine unmittelbare Weiterverarbeitung durch die Mittel der Applikatiohs-Programmiersprache möglich ist; diese Repräsentation wird im folgenden die direkte Darstellung eines Arrays bzgl einer bestimmten Zielumgebung genannt Alternativ kann die Datenbankanwendung mittels vom DBS bereitge¬ stellter Funktionen explizit eine andere Darstellung anfordern (z.B. JPEG, um Hardware- Unterstützung auf der Anwendungsseite nutzen zu können). Sämtliche Umwandlung und

Kompression bzw. Dekomprcssion, die aufgrund von Unterschieden im DBS-internen Spei¬ cherformat und dem für die Anwendung benötigten Format erforderlich werden, erfolgt DBS- intern und für die Anwendung unsichtbar.

Wird z.B. eine TIFF-Codierung angefordert (vorausgesetzt, TIFF ist auf die vorliegende Aπaystruktur anwendbar), dann wird die eingebaute Funktion tif f ( ) aufgerufen. Beispiel: "Alle Landsat-TM-Bilder in ΗFF-Formaf: select tiff ( LandsatTM.data ) Wie die meisten anderen Bilddatenformate auch, beinhaltet TIFF weitere sogenannte Regi¬ strierungsdaten; diese werden vom DBS auf Null werte gesetzt.

Im Fall von JPEG muß zusätzlich der Prozentsatz der Qualitätsreduktion angegeben werden, da JPEG mit wählbarer Veriustrate komprimiert select jpeg( LandsatTM.data, 25 ) Die datenbank-interne Repräsentation ist der Anwendung nicht bekannt; sie kann, muß aber nicht eines dieser Formate sein. Falls das interne Format nicht dem angeforderten entspricht, erzeugt der Anfrageprozessor den erforderlichen Code zur Umwandlung.

5.2 Systemarchitektur

Vorzugsweise wird für ein Raster-DBS eine Hardware- Architektur wie in Abb. 1 und eine Software-Architekmr wie in Abb. 8 eingesetzt. Die Anwendungsschnittstelle (API) bietet zwei grundsätzliche Zugriffswege: Der Anfrageprozessor erlaubt die Definition und Manipu¬ lation von Arrays wie oben beschrieben; insbesondere erstellt er den Plan für die Anfragebe¬ arbeitung. Die Rasterimport- und -exportschnittstelle dient als Massendaten-Schnittstelle im Fall, daß Arrays als Ganzes ein- oder ausgelagert werden sollen. Dieser Spezialfall des Raster¬ datenzugriffs erfordert nur sehr einfache Operationen, aber sehr effiziente Abarbeitung, wes¬ wegen er vorteilhaft eigens unterstützt wird. Der Anfrageoptimierer versucht, den Abarbeitungsplan so umzustellen, daß verschiedene Dienstqualitäts-Kriterien wie Anzahl der Plattenzugriffe, Kompressions/Dekompressionsaufwand und Netzlast optimiert werden. Das Basis-Zugriffsmodul bildet die virtuelle Maschine, auf der der Anfrageprozessor den Abarbei¬ tungsplan ausführt Hier werden Kacheln geladen, der angeforderte Inhalt wird daraus extra¬ hiert, induzierte Operationen werden ausgeführt und das Anfrageergebenis wird vorbereitet und in das angeforderte Datenformat konvertiert Der Speicherverwalter bearbeitet vollstän¬ dige Kacheln, für die Schreib- und Leseprimitive angeboten werden. Zur Beschleunigung der Kachelbestimmung wird intern ein Geo-Index mitgeführt

Innerhalb einer Kachel erfolgt eine konventionelle Linearisierung oder eine beliebige andere Speicherabbildung. Der Speicherverwalter setzt auf einer Schnittstelle auf, die persistente, direkt adressierbare Datenberciche fester oder variabler Länge und ohne weitere Semantik bie¬ tet

Es ist möglich - allerdings nicht notwendig -, ein konventionelles DBS (z.B. relational oder objektorientiert) unter den Speicherverwalter zu setzen, um Transaktions-, Recovery- und weitere Basismechanismen auszunutzen. In diesem Fall dient das unterliegende DBS als per¬ sistenter Speicherverwalter, der Kacheln und/oder Index-Records z.B. in Blobs verwaltet ohne besondere Kenntnis der Semantik zu besitzen. Beispielsweise kann in einem relationalen DBS eine Relation Tiles definiert sein, die die Kacheln aller Axrays, unabhängig von ihrer Dimension, aufnimmt:

Tiles( oid: integer, tid: integer, c_e: integer, tile: long)

Dabei ist oid der Objektidentifikator des Arrays, tid ist der Kachelidentifikator, in c_e ist die jeweilige Kachelcodierung und -kompression vermerkt, und tile enthält die Kacheldaten selbst

Man beachte, daß an jeder Stelle in dieser Architektur Netzwerkkommunikation stattfinden kann; insbesondere können Arrayaufbau aus Kacheln bzw. Arrayzerlegung in Kacheln sowie

Kompression und Dekompression vom Server zur Applikationsmaschine verlegt werden, wobei jedoch auf strikte Transparenz zu achten ist

53 Anfragebearbeitung

Im folgenden wird von einer DML-Spracheinbettung in C und einer vereinfachten API-Funk¬ tion dbCall ( ) Gebrauch gemacht, um die Grundprinzipien der Anfragebearbeitung zu erläu¬ tern. Um die volle oben beschriebene Funktionalität bereitzustellen, sind aufwendigere Interface-Techniken erforderlich, wie sie z.B. in relationalen DBSen Stand der Technik sind. Codierung/Kompression versteht sich immer ausgehend vom Hauptspeicherformat, Decodie- rung/Dekompression geschieht immer in das Hauptspeicherformat der jeweils benutzten Platt¬ form. Dazu besitzt jedes Array einen Indikator, der sein akmelles Datenformat angibt. In der Datenbank ist er mit der Kachel abgelegt; am API wird er entweder durch die Applikation explizit gesetzt oder vom Präprozessor implizit im Zuge der Quellcode-Analyse erzeugt Für die Beschreibung des Verfahrens wird davon ausgegangen, daß zwischen dem Datenbank- server einerseits und dem Datenbank- API und der Anwendung andererseits Netzwerkkommu¬ nikation stattfindet die bei heterogenen Plattformen eine Übertragungscodierung notwendig macht. Dabei kann zur Verringerung des Kommunikationsaufwands Kompression stattfinden. Die zur Anwendung kommenden Verfahren zur Kompression und das Codierung von werden nicht weiter spezifiziert, da sie nicht Gegenstand der vorliegenden Erfindung sind; es können beliebige Methoden eingesetzt werden.

Die Kommunikation via Netzwerk kann an der angegebenen Stelle in der Systemarchitektur erfolgen, sie kann ganz entfallen oder sie kann zwischen anderen DBS-Komponenten stattfin¬ den (vgl. die Pfeile in Abb. 8), wobei die Codierung auf den jeweils auftretenden Einheiten (z.B. Kacheln) erfolgen muß.

53.1 Retrieval

Für die Anfage "Den Landsat-TM-Ausschnitt zwischen (50,100) und (100,200), davon den Kanal c3" sei folgendes C-Codestück im Anwendungsprogramm formuliert:

{

## short landsatPart f 51] [101] ;

## select 1. data. c3 [50. .100] [ 100. .200 ]

## from Lands atTM 1

## into : landsatPart;

} Die zwei Doppelkreuze ## machen die Statements dem Präprozessor bekannt der aus diesem Quellcode Datenbank-API- Aufrufe generiert Diese werden um Angaben zum Datenformat ergänzt Programmvariablen sind hier durch einen vorangestellten Doppelpunkt gekennzeich¬ net, der vom Präprozessor bei der Codeerzeugung ausgefiltert wird:

{ short landsatPart[51] [101]; dbCalK "select 1.data.c3 [50..100] [100..200]

from LandsatTM 1 into : 1" , landsatPart,

CLIENT_INTERNAL_FORMAT ) ; } Der erste dbCall ( ) -Parameter ist der Anfragestring, wie er an den Anfrageprozessor über¬ mittelt wird; der Variablenname in der into-Klausel ist ersetzt durch einen Positionsindikator für den ersten (und hier einzigen) Resultatparameter landsatPart. Der zweite Parameter ist ein Zeiger auf das Resultatarray, in das vom API das Anfrageergebnis gestellt wird. Der dritte Parameter signalisiert dem API, ob das Ergebnisarray in der direkten Darstellung der Anwen¬ dung (CLIENT_INTERNAL_FORMAT) oder in einem in der Anfrage genauer spezifizierten Datenformat (EXTERNAL_FORMAT) abzuliefern ist; aufgrund des Formatindikators CLIENT_INTERNAL_FORMAT als letztem Parameter wird das API nach erfolgter Anfragebe¬ arbeitung durch das DBS das Anfrageergebnis in der Programmvariablen landsatPart in der direkten Darstellung der Applikation bereitzustellen.

Soll das Anfrageergebnis in einem dem DBS bekannten anderen Datenformat geliefert wer¬ den, dann macht die Applikation dies durch den Aufruf der zugehörigen Konversionsfunktion bekannt beispielsweise durch den Aufruf einer Standardfunktion jpeg ( ) zur JPEG-Codie¬ rung mit 25% Reduktion:

{

## char landsatPart [ JPEG_ΞTRING_SIZE] ; ## select jpeg ( 1 . data. c3 [50. .100 ] [ 100. .200 ] , 25 ) ## from LandsatTM 1

## into : landsatPart;

} Der Präprozessor generiert daraus { char landsatPart [JPEG_STRING_SIZE] ; dbCalK "select jpeg ( 1. data. c3 [50. .100 ] [ 100 . .200 ] , 25 ) \ from LandsatTM 1 into : 1 " , landsatPart , EXTERNAL_FORMAT ) ; }

Damit stellt das API das vom Server generierte Array in der Programmvariablen landsat¬ Part JPEG-codiert bereit

Bei der Ausführung derartiger Datenbankaufrufe erfolgt die weitere Bearbeitung der Anfrage gemäß obiger Architektur nach folgendem Algorithmus (Abb. 6):

/. übertrage Anfrage zum Server;

2. erzeuge und optimiere Anfrageplan aus der Anfrage;

3. allokiere das Resultatarray;

4. bestimme unter Zuhilfenahme des Geo-Index die M Menge der betroffenen Kacheln;

5. fiir alle Kacheln k: aus M:

5.1 lade k: in den Hauptspeicher;

5.2 decodiere k: gemäß Coderiungsinformaύon der Kachel;

5.3 dekomprimiere k _j gemäß Coάeriungsinformation der Kachel;

5.4 kopiere relevante Zellen aus kι gemäß Anfrageplan in das Resultatarray;

6. führe restliche Operationen gemäß Anfrageplan auf dem Ergebnisarray aus;

7. falls für das Resultatarray die direkte Darstellung der Anwendung angefordert ist:

7.1 komprimiere das Array;

7.2 codiere das Array;

8. transferiere Resultatarray zur Anwendung;

9. falls für das Resultatarray die direkte Darstellung der Anwendung angefordert ist:

9.1 decodiere das Array in das Hauptspeicherformat der Anwendung;

9.2 dekomprimiere das Array;

In Schritt 1 wird die Anfrage vom Client zum Server übertragen. Im nächsten Schritt wird der Zugriffsplan vom Anfrageprozessor und dem Optimierer erstellt. In Schritt 3 wird im Server der Speicherplatz für das Anfrageergebnis bereitgestellt. Der Speicherverwalter bestimmt in Schritt 4 aus dem Anfrageplan unter Zuhilfenahme des Geo-Index die Menge der betroffenen Kacheln M. Gesteuert vom Anfrageprozessor, lädt das Basis-Zugriffsmodul diese Kacheln der Reihe nach (5.1), expandiert (5.2) und dekomprimiert (5.3) sie in die direkte Darstellung des Servers und kopiert den relevanten Ausschnitt in das Resultatarray (5.3); In den Schritten 5.2 und 5.3 wird die bei jeder Kachel gespeicherte Infoπnation, nach welchem Verfahren der Kachelinhalt codiert und komprimiert wurde, verwendet (vgl. Abschnitt 5.2). Eventuelle wei¬ tere Anweisungen aus dem select-Teil der Anfrage werden vom Basis-Zugriffsmodul in Schritt 6 ausgeführt; unter anderem zählt dazu eine eventuell von der Anwendung angefor¬ derte Umwandlung des Ergebnisses in ein Format, das von der direkten Darstellung der Anwendung verschieden ist

Falls das Ergebnisarray in einem solchen Datenformat codiert ist, wird es in allen folgenden Schritten als Bytestring ohne weitere Semantik betrachtet und in Schritt 8 zur Anwendung transferiert d.h. Schritt 7 und 9 entfallen. Anderenfalls wird das Array, das in der direkten Dar¬ stellung des Servers vorliegt, auf der semantischen Ebene des Arrays (also unter Ausnutzung des Strukturwissens) komprimiert und codiert (Schritt 7) und auf der Anwendungsseite im API wieder decodiert und dekomprimiert (Schritt 9). Damit liegt das Ergebnisarray schließlich in dem von der Anwendung angegebenen Speicherbereich entweder in der direkten Darstel¬ lung der Applikation oder im sonstigen angeforderten Datenformat vor.

5.3.2 Update

Als Beispielsanfrage diene "Ersetze in allen Landsat-TM-Bildern im Kanal c3 im Bereich zwi¬ schen (51,101) und (100,200) die Werte durch das Array e". Das entsprechende C-Codestück lautet

{

## Short e [51] [101] ; ## update LandsatTM

## set data.c3 [ 50 . . 100 ] [ 100 . . 200 ] = : e;

) Der Präprozessor erzeugt daraus {

ERSATZBLAπ (REGEL 26)

Short e[X_SIZE] [Y_SIZE] ; dbCalK "update LandsatTM set data.c3 [50 .. 100] [100 .. 200] = •1" e,

CLIENT_INTERNAL_FORJMAT ) ;

} Auf den ersten Parameter mit dem Anfragestring (der Variablenname ist wiederum ersetzt durch einen Positionsindikator) folgt die Programmvariable e mit dem Eingabearray. Auf¬ grund des Formatindikators CLIENT_INTERNAL_FORMAT als letztem Parameter erwartet das API eine direkte Darstellung der Daten in e.

Liegen die Eingabedaten in einem anderen dem DBS bekannten Format vor, dann macht die Applikation dies durch den Aufruf der zugehörigen Konversionsfunktion bekannt, beispiels¬ weise durch den Aufruf einer Standardfunktion inv_jpeg ( ) zur JPEG-Decodierung:

{

## char e [JPEG_STRING_SIZE] ; ## update LandsatTM

## set data. c3 [ 50 . . 100 ] [ 100 . . 200 ] = inv_jpeg ( : e

) ; } und der Präprozessor generiert daraus

{ char e [JPEG_STRING_SIZE] ; dbCalK "update LandsatTM set data. c3 [ 50 . . 100] [ 100 . . 200] = \ inv_jpeg ( : 1 ) * , e ,

EXTERNAL_FORMAT ) ; } Das API transferiert den Inhalt von e zum Server, sodaß dort ein JPEG-codiertes Array ankommt

Die weitere Ausführung durch das DBS geschieht gemäß obiger Architekmr nach folgendem Algorithmus (vgl. Abb. 7):

1. falls das Eingabearray in der direkten Darstellung der Anwendung vorliegt:

1.1 komprimiere das Array;

1.2 codiere das Array;

2. übertrage Anfrage und Eingabearray zum Server;

3. falls das Eingabearray in der direkten Darstellung der Anwendung vorliegt:

3.1 decodiere das Array;

3.2 dekomprimiere das Array;

4. erzeuge und optimiere Anfrageplan aus der Anfrage;

5. modifiziere Eingabearray gemäß Anfrageplan;

6. bestimme mittels Geo-Index die Menge M der betroffenen Kacheln;

7. für alle Kacheln k( aus M:

7.1 lade kj in den Hauptspeicher;

Z2 decodiere /c _z -;

7.3 dekomprimiere kz;

7.4 schreibe relevante Zellen aus dem Eingabearray nach k;

7.5 codiere /:,•;

7.6 komprimiere k _it -

7.7 speichere fy;

Falls das Eingabearray in der direkten Darstellung der Anwendung vorliegt, wird es in Schritt 1 mittels eines Verfahrens zur Array-Kompression und -Codierung in ein systemneutrales For¬ mat konvertiert, in Schritt 2 zusammen mit der Anfrage zum Server übertragen und dort in die direkte Darstellung des Servers übergeführt (Schritt 3.1 und 3.2). Liegt das Eingabearray in einem anderen Format vor, dann wird es beim Transfer als Bytestring ohne weitere Semantik betrachtet und in Schritt 2 zum Server transferiert.

In Schritt 4 wird die Anfrage in den internen Anfrageplan übersetzt und optimiert. Bei seiner Ausführung werden zuerst in Schritt 5 in der Anfrage spezifizierte Modifikationen auf dem Eingabearray vorgenommen; unter anderem wird das Eingabearray, falls es codiert vorliegt, durch Anwendung der in der Anfrage spezifizierten Konversionsfunktion in die direkte Dar¬ stellung des Servers übergeführt

Aus den Trimm-Angaben in der Anfrage bestimmt der Speicherverwalter im Schritt 6 mithilfe des Geo-Index die betroffenen Kacheln, welche im Schritt 7.1 vom Speicherverwalter geladen und an das Basis-Zugriffsmodul übergeben werden. Gesteuert vom Anfrageprozessor, expan¬ diert dieses die Kacheln (Schritt 7.2 und 7.3) abhängig von der Codierungsinformation bei jeder Kachel, aktualisiert die Kacheln mit den relevanten Zellen aus dem expandierten Einga¬ bearray (7.4), führt die Kacheln wieder in das vom Kachelindikator vorgegebene Speicherfor¬ mat zurück (Schritt 7.5 und 7.6) und übergibt sie schließlich wieder an den Speicherverwalter zum Zurückschreiben in die Datenbank (7.7).

6 Erfindungswesentliche Gedanken

1. Ein DBS zur Verwaltung von Arrays. Das DBS kann als eigenständiges System implemen¬ tiert sein oder als Bestandteil eines anderen DBS.

2. Besagtes DBS mit der Fähigkeit, Arrays

- mit einer beliebigen Anzahl von Dimensionen

- einer beliebigen, unter Umständen variablen Anzahl von Zellen pro Dimension

- über beliebigen Basistypen zu verwalten.

3. Logische Ebene:

- Das DBS besitzt eine DDL zur Strukturdefinition von Arrays.

- Das DBS besitzt eine DML im herkömmlichen Datenbank-Sinn, die Arrays mittels beliebiger Ausdrücke und Prädikate (evtl. gemischt mit solchen über konventionellen Datentypen) zu bearbeiten erlaubt

- Datenunabhängigkeit auf Rasterdaten: Die Präsentation von Arraydaten durch das DBS ist unabhängig vom datenbank-internen Speicherformat der Codierung und Kompres-

sion sowie von Programmiersprache, Betriebssystem und Hardware von Client und Ser¬ ver. Die Applikation kann auswählen, welches Format die Rasterdaten besitzen sollen; zur Auswahl stehen die maschineninterne Hauptspeicherdarstellung in der Applikation sowie eine beliebige Anzahl von Datenaustauschformaten.

4. Physische Ebene:

- Das DBS verwendet eine Kombination aus n-dimensionaler Kachelungstechnik und einem n-dimensionalen Geo-Index, um eine schnelle und effiziente Verwaltung von Arrays beliebiger Größe und Dimension zu erreichen.

- Jede Kachel kann individuell auf einem beliebigen Speichermedium abgelegt werden, sodaß das DBS ein Array über eine beliebige Anzahl möglicherweise heterogener Datenträger verteilen kann, ohne daß dies der Anwendung sichtbar wird.

- Das DBS kann intern eine Vielzahl von Kompressionsverfahren einsetzen, um die Ablage und Übertragung von Rasterdaten zu optimieren, ohne die Kompression/ Dekompression für die Anwendung sichtbar zu machen.

- Durch einen Indikator, der mit jeder Kachel gespeichert wird, kann die Codierung und Kompression für jede Kachel einzeln festgelegt werden; insbesondere lassen sich ver¬ schiedene Kacheln desselben Arrays unterschiedlich behandeln.

- Jedes Array im Hauptspeicher (beim DBS-Server oder im API auf Client-Seite) besitzt einen Indikator für die Codierung/Kompression, in der es vorliegt; dieser Indikator ist wesentlich, um beliebige Datenformate auf API-Ebene anbieten zu können, also zur Realisierung von Datenunabhängigkeit.

- Ein Anfrageoptimierer kann, basierend auf der Datendefinition, der Speicherorganisa¬ tion sowie anderer brauchbarer Information, den Ausführungsplan einer Anfrage nach einer Vielzahl von Methoden so reorganisieren, daß Dienstqualitätskriterien wie CPU- Last Speicherzugriff, Netzlast und Antwortzeiten optimiert werden.

- Als mögliche Implementierung können Kacheln auf Attribute eines anderen DBS (z.B. relational oder objektorientiert) dergestalt abgebildet werden, daß jedes Tupel bzw. jedes Objekt eine Kachel enthält (zuzüglich etwaiger Verwaltungsinformation). Damit lassen sich mit beschränktem Aufwand klassische Datenbankeigenschaften wie Trans¬ aktionsschutz und Recovery realisieren.

7 Literatlirreferenzen

[Baum-94]

P. Baumann: On the Management of Multidimensional Discrete Data. VLDB Journal 3(4)

1994, Special Issue on Spatial Databases, pp. 01 - 444 [Guet-94]

R.H. Gueting: An Introduction to Spatial Database Systems. VLDB Journal 3(4) 1994, Spe¬ cial Issue on Spatial Databases, pp. 357 - 400 [MwLW-89]

K. Meyer-Wegener, W. Lum; C. Wu: Image Management in a Multimedia Database. Proc.

Working Conference on Visual Databases, Tokyo, Japan, April 1989, Springer 1989, pp.29

- 40 [SaSt-94]

ERSATZBLAπ (REGEL 26)

S. Sarawagi, M. Stonebraker: Efficient Organization of Large Multidimensional Arrays.

Proc. lOth Int Conf. on Data Engineering, February 1994 [Tamu-80]

H. Tamura: Image Database Management for Pattern Information Processing Studies. S.

Chang, K. Fu (eds): Pictorial Information Systems, Lecture Notes in Computer Science

Vol. 80, Springer 1980, pp. 198 - 227 [VaDe-91]

S. Vandenberg, D. De Witt Algebraic Support for Complex Objects with Arrays, Identity, and Inheritance. Proc. ACM SIGMOD Conf. 1991, pp. 158 - 167

ERSATZBLAπ (REGEL 26)