Note: Descriptions are shown in the official language in which they were submitted.
..T>2
r
CA 02230301 1998-02-24
Peter Baumann
DE-80689 Miinchen
Database System for Management of Arrays
1. SUMMARY OT THE INVENTION
The invention relates to an application- or domain-independent database
system (DBS) for the. storage, retrieval, and manipulation of raster data,
i.e.
arrays of arbitrary (fixed or variable) size and number of dimensions over
arbitrary array base types. The invention is characterized by a strict separa-
tion of logical (conceptual) and physical level to achieve data independence,
i.e. to address raster data independently from their physical data structuring
(storage structure), encoding, and compression. Depending on the data for-
mat requested by the application, the DBS transparently effects the neces-
sary conversion and (de-)compression taking into account access and trans-
fer optimization issues.
On the conceptual level, the explicit definition of array structures via a
data
definition language (DDL) provides the DBS with the knowledge concerning
the complete array semantics. An orthogonal query language (DML) con-
tains array-specific primitives and operators which can be combined arbi-
trarily to form optimi.zable DML-expressions and -predicates. Standard
functions allow for explicit format conversion.
On the physical level, a storage architecture based on the combination of
array tiling and a spatial access structure (geo-index) allows for the e~cient
CA 02230301 1998-02-24
-2-
t
access to arrays and al-ray cut-outs as well as the distribution of an array
over several, potentially heterogeneous storage media.
The invention is particularly suited for raster applications which have de-
manding requirements with respect to functionality, data volumes, network
capability and access tune - in particular distributed, open multimedia sys-
terns.
2. TECHNICAL BACKGROUND OF THE INVENTION
2.1 Technical Area to which the Invention Relates
This invention pertains to a domain-independent database system (DBS) to
store, retrieve and manipulate arbitrary arrays in databases. The term array
is understood here in a programming language sense: A fixed-length or vari-
able-length sequence of similarly structured data items (cells, in computer
graphics and imaging often called pixels) addressed by (integer) position
numbers. The cells themselves may be arrays again, so that arrays of arbi-
trary dimensions can be constructed.
2.2 Prior Art with Sources
DBSs have a considerable tradition and play an important role in the stor-
age, retrieval and manipulation of large amounts of data. To this end, they
offer means for flexible data access, integrity and consistency management,
concurrent access by a plurality of users, query and storage optimization,
backup and recovery, etc. For communication between database application
(client) and database program (server) various techniques exist, which, for
CA 02230301 1998-02-24
-3-
example via function libraries (Application Programmer's Interface, API)
which are tied to the application, effect a network data communication in-
chiding a data conversion invisibly for the application.
However, these advantages are, as yet, only available for data items such as
integers and strings, as well as, for some while now, for so-called long
fields
or blobs (binary large objects), i.e. byte strings of variable length. As for
general raster data (for example audio (1D), raster images (2D) and video
(3D)), current practice is to regard them as bit strings and to map or project
them onto linear blobs for example in [MwLW-89] the authors first state
that "raw image data form a matrix of pixels" and then conclude that "the
raw data appear (in the database) just as a string of bits".
Due to this loss of semantics through the FORTRAN-type linearisation in
the database, raster data can only be read or written as a whole or in a line-
by-line fashion. Raster structures cannot be given in search criteria and can-
not be processed by the DBS, for example to extract only relevant parts.
Moreover, the application must choose one of a plurality of existing data
formats for encoding and compression. This choice is compulsory for all
other database applications having access thereto, and they alone must en-
sure the correct decoding and the decompression. Thus, the database appli-
cation programmer is burdened with a multitude of low-level (near-to-
machine), repetitive, error-prone and time consuming programming tasks.
Furthermore, linearisation of arrays in secondary and tertiary storage de
stroys the neighbouring relationships (locality) between array elements, as
shown in figure 2. A cut-out, which conveys a high degree of locality on a
logical level, is disposed on the background storage in a way which favours
CA 02230301 1998-02-24
-4-
only line-by-line access and puts all other access means at a drastic disad-
vantage. The consequence is an inadequate response time behaviour.
A typical system is described in [MwLW-89]: Raster images are provided in
the database as blobs, encoded in one of various possible image exchange
formats (for example TIFF or GIF); an additional flag indicates to the appli-
cation the presently used format. The EXTR.A/EXCESS-system [VaDe-91]
offers an algebra for modeling and querying raster data, but there is no ac-
companying appropriate storage technique, so that only small arrays (for ex-
ample 4x4-matrixes) can be eff-lciently managed. Sarawagi and Stonebraker
[SaSt-94] recently proposed a storage architecture for arrays based on tiling
(see below), but without a spatial index for access acceleration and without
optimizable query support next to the pure cut-out formation. In [Baum-94]
an approach for raster data management is proposed, which concerns the
conceptual as well as the physical level. A general solution for the problem
of data independence, i.e. the processing of raster data in a DML or API
without knowledge and reference of/to its physical storage structure, encod-
ing and compression, does not exist at the moment.
In imaging, tiling techniques are used for the processing of images, which,
due to their size, do not fit into the main memory as a whole (for example
[Tamu-80]). A tile is .a rectangular cut-out of an image. The image is de-
composed into tiles, so that these do not overlap and together cover the im-
age (see figure 5.1 ). Within a tile, data are stored using a conventional
line-
arisation scheme. Tiling can be advantageously used in order to simulate
neighbourhood/vicinity within an array on a linear storage medium, and thus
forms an important basis for the present invention.
CA 02230301 1998-02-24
-$-
For the management of geometric data such as points, lines and areas, many
spatial indices (geo-induces) exist in order to accelerate access to such data
elements in a database [Guet-94]. In the present invention, such a geo-index
is used for fast tile location.
3. PRESENTATION OF THE INVENTION
3.1 Technical Task 'to be solved
The present invention describes a DBS for raster data which performs:
~ Management of the full semantics of arbitrary arrays.
~ Declarative storage, retrieval and processing/manipulation of raster data
on the semantic level of arrays.
~ Data independence: the presentation of array data by the DBS is explicitly
chooseable by the application in a multitude of different data formats, in-
dependently from a database-internal storage format, encoding and com-
pression.
~ A storage technique which allows an eff'lcient management of very large
arrays, which may stretch across a plurality of possibly heterogeneous
storage media.
~ Storage and query optimization.
3.2 Advantageous Effects of the Invention
A DBS according to the present invention is especially suited for raster ap-
plications which have demanding requirements with respect to functionality,
CA 02230301 2000-10-23
-6-
data volumes, network capability and access time (response time behaviour).
Among the more
prominent application areas are distributed open multimedia systems, medical
imagery/PACS
(Picture Archiving and Communication System) /hospital information systems,
geographical and
environmental information systems (GIS/EIS) as well as scientific
visualization (mechanical
engineering, meteorology, hydrology, astronomy). In detail, the following
advantages can be
achieved:
~ Application or domain independence: array-specific data structures and
operations can
be combined arbitrarily with conventional definitions, expressions and
predicates; this
way, a DBS according the invention can be used for a plurality of application
domains.
~ Data independence: DBS functionality is available on arbitrary platforms and
networks
and independently from a specific data format or a specific set of data
formats.
~ Database application programmers are relieved from low level, repetitive,
error-prone and
time consuming tasks, in that uniform standard solutions are provided by DBS.
~ Less resource consumption due to the tailored/modified storage architecture
and a
declarative, optimizable query language; especially, the response time
behaviour depends
on the query result, and not on the overall data volume on which the query is
performed.
~ Transparent integration of storage media (for example hard disk, jukebox,
tape archives)
for data sets of arbitrary size, in particular for arrays spanning several
data carriers.
~ Classic database services such as transaction support, integrity maintenance
and recovery
become available for raster data.
CA 02230301 1998-02-24
-7-
4. BRIEF DESCRIPTION OF THE DRAWINGS
Figure 1: Schematical structure of an arrangement according to the inven-
tion: One or more computers on which raster data applications
are provided are, via a local or long distance net, connected with
the server on which the raster DBS is provided.
Figure 2: Destruction of spatial locality/neighbourhood through linearisa-
tion in connection with storage projection, shown for the exam-
ple of an array cutout formation (circles denote cells selected by
the cutout, dots represent cells not included by the query).
Figure 2.1: 2-D image with marked cutout (logical view).
Figure 2.2: Linearized image with scattered parts of the selected cutout.
Figure 3: Visualization of the effect of sample queries on arrays (selected
areas are shown with shaded lines).
Figure 3.1: Trim operation, applied to a 2-D array.
Figure 3.2: Projection along the x/z-plane of a 3-D array, yielding a 2-D ar-
ray.
Figure 3.3: Projection along the y-axis of a 3-D array; yielding a 1-D array.
Figure 4: Extension o~f a variable 2-D array during assignment.
Figure S: Raster storage management by means of a combination of tiling
and spatial index (geo-index); here: Example of storage of a 2-D
array.
Figure 5.1: Factoring of a 2-D image into tiles.
Figure 5.2: Spatial index (geo-index) of the tile-factoring in figure 5.1.
Figure 6: Retrieval-algorithm as flow-diagram.
Figure 7: Update-algorithm as flow-diagram.
Figure 8: System architecture of a raster database system according to the
present invention. The internal interface marked by arrows are
CA 02230301 2000-10-23
_g_
especially suitable for interconnection of network communication.
5. DESCRIPTION OF A WAY OF REALIZING THE INVENTION
The present invention is now described with reference to a specific, suitable
embodiment.
However, the invention is not limited to this embodiment. Rather, many
variations and
modifications are possible, without leaving the domain of the invention as
described below in
the claims or their equivalents.
5.1 Raster Semantics
In the following, the C++ type DDL of an object-orientated DBS is used; for
the example
queries, an SQL type DML is used. It is obvious, how the underlying concepts
are transferable
to other models and systems. The invention is in no way limited to a specific
syntax,
programming language, operating system or a specific database paradigm.
5.1.1 Structure definition
The conceptual scheme is described referring to an example mini-world,
stemming from the field
of sensor fusion in environmental information systems. Three object classes
seismicsensor for
variable-length 1-D-time series, LandsatTM (Thematic Mapper) for Landsat-TM
(Thematic
Mapper)-satellite images in the format 7020x5760 (2-D) and weathersimulation
for atmospheric
temperature distributions in a 1000x1000x1000 area (3-D) are defined below;
the simple #
denotes a variable number of cells in the specified dimension:
CA 02230301 1998-02-24
-9-
class SeismicSensor: public PObject
f
public:
coordinate location; // geographical position of sensor
unsigned data [ # ]; // sequence of measured data
class LandsatTM: public PObject
(public:
orbit orbitalData; l/ orbital parameter
Aperture aperture; // aperture
struct (unsigned short cl, c2, c3, c4, c5, c6, c7;~
aorta [7020 [5760; //7-band-image data
class WeatherSimulation: public PObject
f
public:
float data [looo~ [loooJ [looo]; //temperature data
5.1.2 Operations
The array operations can be grouped into value based operations, update
operations and general constructions/principles. The following value based
operations are suggested:
Constants. For use in query expressions or to initialize an array, cell values
can be indicated explicitly or implicitly. Example: 'A 2x2 integer array with
all cells zeroed. " This is indicated by a direct listing, the array structure
properly reflected here through curly braces:
f f o, o }, f o,
Implicit definition is done through some descriptive statement of the kind
CA 02230301 1998-02-24
- lU -
0: [ 1024 ] [ 768
in this case stating 'A 1024 x 768 image with all cells zeroed".
Trimming produces a rectangular array cutout. For example, the query "The
subarray of all Landsat TM images which is given by the corner points
(x0,y0) and (xl , yl) " (see figure 3.1 ) is phrased as
select 1. data [ x0 . . xl ] [ y0 . . y1 ]
from LandsatTM 1
Projection extracts a layer of thickness 1 from an array (cf. figure 3.2). For
example, "air temperature distribution over the whole simulation area at
height over ground h" is stated as
select w. data [ # ] [ h ] [ # ]
from WeatherSimulation w
Induced operations. For each operation available on the array base type
(e.g., subtraction on gl-eyscale pixels), a corresponding operation is made
available, which applies the base operation simultaneously to all array cells
(e.g. subtraction of two greyscale images). Example: "The c3 channel of all
Landsat TM images, reduced in intensity by the value d".
select l.data.c3 - d
from LandsatTM 1
Predicate iterators. The raster predicate some(p) yields true if and only
if at least one cell of a Boolean array p contains the value true. Correspond-
ingly, the raster predicate a 11 ( p ) returns true if and only if all cells
of p
contain true. Example: "The location of all seismic sensors where earth-
quake activity has exceeded t at some time in the past. "
select s.location
from SeismicSensor s
where some ( s.data > t )
Next, the update operations are listed.
CA 02230301 2000-10-23
- 11 -
Initialization. This operation, which is implicitly invoked upon every
creation of an array as part
of for example a tuple or an object, sets all cells to zero values and the
length of variable arrays
to zero.
Assignment. Through an assignment, the cells in an array or part of an array
receive new values.
If the array is variable and the cell positions to be occupied do not all lie
within the already
existing array, the array is extended appropriately. For instance, in figure
4, the old array a . old
is extended by array part v. new which only partially overlaps a . old. Hence,
a . new is formed
as an extended array, made a rectangle by introducing two newly created areas,
a.auxl and
a.aux2, filled with zero (null) values.
Finally, general construction principles are listed which are important
regarding flexibility and
generality of the invention.
Orthogonal query language. The operations listed above preferably are embedded
in a
declarative DML which describes what shall be done and not how to do it,
thereby clearing the
way for intelligent optimization. Expressions and predicates are (recursively)
formed using the
aforementioned array basic operations, the well-known Boolean operators,
parentheses,
functional nesting and, under certain circumstances, the calling of further
functions/methods.
Example 1: "The temperature distribution in a height h of all simulations, in
which at any point
in the area marked by the corner points (x0, y0, z0) and (xl, yl, zl) the
temperature t is exceeded. "
Trimming in three dimensions is here combined with the induced comparison and
of the
collaboration or collapsing into a single Boolean value by the "some"-
operator:
select w. data [ # , h , # ]
from WeatherSimulation w
CA 02230301 1998-02-24
- 12-
where some (w. data [x0 .. x1] [y0 .. yl] [z0 .. z1] > t)
Example 2: "The Landsat-TM images which contain regions of observed
seismic activity, as well as the corresponding sensor positions". Here, in
addition to the raster operation, geometrical operations area ( ) and con-
twins as well as parenthesizing/nesting are used:
select l.data, s.location
from LandsatTM 1, SeismicSensor s
where area (l.orbitalData, l.aperture) contains s.loca-
tion and some ( s.data > t )
Data independence. Raster data are presented to the application program as
generic arrays; the functionality, which is offered on arrays, is independent
of their physical structure in the database. In case now further
specifications
take place, data pass tile DBS-interface in the main memory representation
of the goal machine and the programming language of the application, for
example as C++ array, so that a direct further processing by means of the
application programming language is possible; this representation is called
the direct representation of an array with respect to a specific goal envi-
ronment. Alternatively hereto, the database application can explicitly request
a different representation by means of functions offered by DBS (for exam-
ple JPEG to exploit hardware support on the client side). All conversions
and compressions or decompressions which become necessary due to differ-
ences in DBS-internal storage format and the format necessary for the appli-
cation, are performed DBS-internally and invisibly for the application.
If, for example, a TIFF-encoding is requested (provided TIFF is applicable
to the array structure present) the built-in function tiff ( ) is requested
(called). Example:
'All Landsat-TM images in TIFF format":
CA 02230301 1998-02-24
-13-
select tiff (LandsatTM.data)
Like most other image data formats, TIFF includes further so-called regis-
tration data: These are set to zero values by DBS.
In case of JPEG, the percentage of quality reduction must additionally be
supplied, as JPEG performs a compression with selectable data loss:
select jpeg ( LandsatTM.data, 25 )
The database-internal representation is not known to the application; it can,
but must not be one of these formats. If the internal format does not match
the requested format, the query processor generates the necessary conver-
sion code.
5.2 System Architecture
Preferably, a hardware architecture as shown in figure 1 and a software ar-
chitecture as shown in figure 8 are used for a raster DBS. The application
interface (API) provides two basic ways of access: The query processor
offers the definition and manipulation of arrays as described above; in par-
ticular, it establishes a query execution plan. The raster import and export
facility serves as a bulk data interface (bulk loader) in case arrays as a
whole
are imported or exported. This special case of raster data access requires
only very simple operations, but a very efficient execution, wherefore it is
advantageously separately supported. The query optimizer attempts to rear-
range the execution plan, so that various quality-of service-criteria, e.g.
number of disc accesses, compression/decompression effort or overhead,
and network load (network traffic) are optimized. The basic access module
forms the virtual machine, on which the query processor executes the exe-
cution plan (query plan). Here, tiles are loaded, the requested contents are
extracted therefrom, induced operations are performed and the query result
is prepared and converted into the requested data format. The storage mah-
CA 02230301 1998-02-24
- 14-
ager processes complete tiles, for which writing and reading primitives are
offered. In order to speed-up tile determination a geo-index is maintained
internally.
Within a tile a conventional linearisation or any arbitrary storage mapping is
performed. The storage manager is based on an interface which offers per-
sistent, directly addressable data areas of specified or variable length with-
out fiirther semantics.
It is possible - however not necessary - to place a conventional DBS (for
example relational or object-oriented) under the storage manager, in order to
utilize transaction, recovery and further base (basic) mechanisms. In this
case the underlying DBS serves as persistent storage manager which man-
ages tiles and/or index records for example in blobs, without having specific
knowledge of the semantics. For example, in a relational DBS a relation
Tiles can be defined which holds the tiles of all arrays, regardless of their
dimension:
Tiles (oid:integer, tid:integer, c e:integer, tile: long)
Herein, oid is the object identifier of the array, tid is the tile identifier,
in
c a the respective tile encoding and compression is indicated, and tile
contains the tile data themselves.
It should be noted that at each place in this architecture network communi-
cation can take place; in particular, array construction from tiles and array
decomposition into tiles as well as compression and decompression can be
shifted from the server to the application machine (client machine). How-
ever, strict transparency should be maintained.
CA 02230301 1998-02-24
-15-
5.3 Query Processing
In the following, a DML-language embedding in C and a simplified API-
function dbCall ( ) is utilized in order to describe the basic principles of
query processing. In order to provide the above described functionality in
full, more complicated interface-techniques are necessary which are for ex-
ample state of the art il relational DBS. Encoding/compression is always to
be understood starting out from the main storage format. Decod-
ing/decompression is always performed into the main storage format of the
respectively used platform. Herefore, each array comprises an indicator
stating its present data format. It is stored in the database together with
the
tile; at the API, it is either explicitly set by the application, or produced
im-
plicitly by the preprocessor during source code analysis.
For the description of the method it is presumed that network communica-
tion takes place between the database server on the one side, and the data-
base API and the application on the other side, which, with heterogeneous
platforms, makes necessary a transmission encoding. Herein a compression
can be performed in order to reduce the communication volume. The meth-
ods utilized for compression and for encoding of arrays are not further
specified as they are not subject matter of the present invention; arbitrary
methods may be used.
The communication via network can be performed at the stated place in the
system architecture, cam be omitted or can be performed between other DBS
components (see the arrows in figure 8), wherein the encoding must take
place on the respectively occurring units (for example tiles).
CA 02230301 1998-02-24
- 16-
5.3.1 Retrieval
For the query "The Landsat-TM cutout between (50,100) and (100,200),
therefrom channel c3" the following piece of C-code is formulated in the
application program:
## short landsatPart[51] [101];
## select l.data.c3[50..100] [100..200]
~# from LandsatTM 1
## into :landsatPart:
The two double crosses ## make known the statements to the preprocessor,
which generates database-API-calls from this source code. These are sup-
plemented by information concerning data format. Program variables are
marked herein by a prepositioned colon which is filtered out by the preproc-
essor during code creation:
short landsatPart[51] [101];
dbCall ( "select 1. data. c3[50. . 100] [100. . 200]
from LandsatTM 1 into :1",
landsatPart,
CLIENT INTERNAL-FORMAT );
The first abcall ( ) -parameter is the query string, as transmitted to the
query processor; the variable name in the into-clause is replaced by a posi-
tion indicator for the first (and here only) result parameter landsatPart.
The second parameter is a pointer to the result array, in which the query re-
sult is placed by the API. The third parameter signals to the API, whether
the result array is to be delivered in the direct representation of the
applica-
CA 02230301 1998-02-24
tlOn (CLIENT-INTERNAL FORMAT or in a data format specified lri the query
(EXTERNAL FORMAT; based On the format lridlCatOr CLIENT INTERNAL-
FoRMAT as final parameter the API will, after completion of the query proc-
essing by the DBS, make available the query result in the program variable
landsatPart in the direct representation of the application.
If the query result is to be delivered in another data format known to the
DBS, the application makes this known by calling the corresponding con-
version function, for example by calling a standard fimction j peg ( ) for
JPEG-coding with a 25% reduction:
## char landsatPart (JPEG STRING SIZE];
## select jpeg ( 1. data. c3(50. . 100] (100. . 200], 25 )
## from LandsatTM 1
## into :landsatPart;
Herefrom, the preprocessor generates
char landsatPart(JPEG STRING SIZE];
dbCall ("select jpeg(l.data.c3(50..100] (100. .200], 25) \
from LandsatTM 1 into :1',
landsatPart,
EXTERNAL FORMAT );
Thus, the API provides the array generated by the server in the program
variable landsatPart JPEG-encoded.
During execution of such database requests the further processing of the
query according to above architecture is performed after the following al-
gorithm (figure 6):
CA 02230301 1998-02-24
-18-
1. transmit query to server;
2. generate and optimia;e query plan from the query;
3. allocate result array;
4. using the geo or spatial index determine the M set of the affected tiles;
S. for all tiles k; from M:
5.1 load kl in the main storage;
5.2 decode k, according to encoding information of the tile;
5.3 decompress k= according to encoding information of the tile;
5.4 copy relevant cells from k= according to query plan into the result
array;
6. perform remaining operations according to query plan on the result ar-
ray;
7. in case the direct representation of the application is requested for the
result array:
7.1 compress the array;
7.2 encode the array;
8. transfer result array to application;
9. in case the direct representation is requested for the result array:
9.1 decode the array into the main storage format of the application;
9.2 decompress the array;
In step 1 the query is transmitted from the client to the server. In the next
step the retrieval plan is generated by the query processor and the optimizer.
In step 3 storage space for the query result is provided in the server. The
storage manager determines, in step 4, the set of afFected tiles from the
query plan with the help of the spatial (geo) index. Controlled by the query
processor, the basis access module loads these tiles one after the other (5.1
),
expands them (5.2) and decompresses them (5.3) into the direct representa-
tion of the server and copies the relevant cutout in the result array (5.3);
in
CA 02230301 2000-10-23
- 19-
steps 5.2 and 5.3 the information stored with each tile, according to which
method the tile
contents were encoded and compressed, is utilized (see section 5.2). Possible
further directions
from the select-part of the query are performed by the basis access module in
step 6; inter alia
this comprises a transformation of the result, possibly requested by the
application, into a format
which differs from the direct representation of the application.
In case the result array is encoded in such a data format, it is regarded in
all following steps as
a byte string without further semantics and transferred to the application in
step 8, i.e. steps 7 and
9 are omitted. Otherwise, the array, which is provided in the direct
representation of the server,
is compressed on the semantic level of the array (also utilizing the structure
knowledge) and
encoded (step 7), and, on the application side in the API, again decoded and
decompressed (step
9). Thus, the result array finally is provided in the storage area specified
by the application either
in the direct representation of the application or in the other requested data
format.
5.3.2 Update
The following query shall serve as an example: "Replace in all Landsat-TM
images in channel
c3 in the area between (51,101) and (100, 200) the values by array a ". The
corresponding piece
of C-code reads:
## short a[51] [101];
## update LandsatTM
## set data .c3 [50 . . 100] [100 . . 200] _ :e;
Therefrom the preprocessor generates
CA 02230301 1998-02-24
-20-
short a[X_SIZE] (Y SIZE];
dbCall("update LandsatTM set data.c3(50..100] [100..200]
- ; 1 ~~
a
CLIENT INTERNAL FORMAT );
The first parameter of the query string (the variable name is again replaced
by a position indicator) is followed by the program variable a with the input
array. In view of the iFormat llldlCatOr CLIENT INTERNAL FORMAT aS last
parameter, the API expects a direct representation of the data in e.
If the input data are provided in another format known to DBS, the applica-
tion makes this known by calling the corresponding conversion function, for
example by calling a standard function inv j peg ( ) for JPEG-decoding:
## char a[JPEG STRING SIZE];
## update LandsatTM
## set data.c3 [ 50 .. 100 ] [ 100 .. 200 ] _
inv jpeg ( : e) ;
and therefrom the preprocessor generates
char e(JPEG STRING SIZE];
dbCall("update LandsatTM set data.c3I50..100]
[100. .200] _ \ inv jpeg( :1 ) ",
e,
EXTERNAL FORMAT );
The API transfers the contents of a to the server, so that a JPEG-encoded
array arrives therein.
CA 02230301 1998-02-24
-21-
The further execution by the DBS is performed, according to above architec-
ture, after the following algorithm (see figure 7):
1. in case the input array is provided in direct representation of the appli-
cation:
1. I compress the array;
1.2 encode the array;
2. transfer query and input array to server;
3. in case the input array is provided in the direct representation of the
application:
3.1 decode the array;
3.2 decompress the array;
4. generate and optimize query plan from the query;
5. mode input array according to query plan;
6. determine by means of spatial index the set M of the affected tiles;
7. for all tiles k; from M.'
7.1 load k; in the main storage;
7.2 decode k;;
7.3 decompress k~;
7.4 write relevant cells from the input array to k;
7.5 encode k;;
7.6 compress kt;
7. 7 store k;.
In case the input array is provided in the direct representation of the appli-
cation, it is converted in step 1 by means of a method for the array com-
pression and encoding into a system-neutral format, in step 2 it is transmit-
ted, together with the query, to the server and there transformed into the di-
rect representation of the server (steps 3.1 and 3.2). If the input array is
CA 02230301 1998-02-24
-22-
provided in a different format, it is regarded as a byte string without
further
semantics during transfer and transferred to the server in step 2.
In step 4 the query is translated into the internal query plan and optimized.
During execution, in step 5, modifications specified in the query are first
performed on the input array; inter alia the input array, if it is provided in
encoded form, is transformed into the direct representation of the server by
application of the conversion function specified in the query.
From the trim information in the query the storage manager determines, in
step 6, by means of the spatial index the affected tiles which, in step 7.1,
are
loaded by the storage manager and transmitted to the basis access module.
Controlled by the query processor, this expands the tiles (steps 7.2 and 7.3)
depending on the encoding information with each tile, updates the tiles with
the relevant cells from the expanded input array (7.4), transfers the tiles
back
into the storage formal: predetermined by the tile indicator (steps 7.5 and
7.6) and finally transfers them back to the storage manager for rewriting into
the database (7.7).
6. ESSENTIAL THOUGHTS CONCERNING THE INVENTION
1. A DBS for the management of arrays. The DBS can be implemented as
an individual system or as a component of a further DBS.
2. Said DBS with the ability to manage arrays
- of an arbitrary number of dimensions
- an arbitrary, possibly variable number of cells per dimension
- over arbitrary basis types.
3. Logical level:
CA 02230301 2000-10-23
- 23 -
- The DBS comprises a DDL for structure definition of arrays.
- The DBS comprises a DML in the usual database sense, which renders possible
the processing of arrays by means of arbitrary expressions and predicates
(possibly mixed with such ones over conventional data types).
- Data independence of raster data: the presentation of array data by the DBS
is
independent of the database-internal storage format, the encoding and the
compression as well as the programming language, operating system and
hardware of client and server. The application (client) can choose, which
format
the raster data shall have; the machine internal main storage representation
in the
application as well as an arbitrary number of data exchange formats can be
chosen.
4. Physical level:
The DBS uses a combination of n-dimensional tiling technique and a
n-dimensional spatial index in order to achieve a fast and efficient
management
of arrays of arbitrary size and dimension.
- Each tile can be stored individually on an arbitrary storage medium, so that
the
DBS can distribute an array over an arbitrary number of possibly heterogeneous
data carriers, without this becoming visible for the application.
- The DBS can utilize a number of compression methods internally, in order to
optimize the storage and transmission of raster data, without making the
compression/decompression visible for the application.
- By means of an indicator, which is stored with each tile, the encoding and
compression for each tile can be determined individually; especially,
different
tiles of the same array can be treated differently.
Each array in the main storage (with the DBS server or in the API on the
client
side) comprises an indicator for the encoding/compression
CA 02230301 2000-10-23
-24-
in which it is provided; this indicator is essential in order to offer
arbitrary data
formats on the API level, i.e. to realize data independence.
- Based on the data definition, the storage organization as well as other
useful
information, a query optimizer can reorganize the execution plan of a query
according to a multitude of methods, so that to the quality of service
criteria like
CPU-load, storage access, net load and response times can be optimized.
- As possible implementations tiles can be projected onto attributes of
another DBS
(for example relational or object orientated) in such a way that each tuple or
each
object comprises a tile (additionally possible management information). Thus,
classic data bank features such as transaction security and recovery can be
realized with limited means or effort.
7. LITERATURE REFERENCES
[Baum-94 ]
P. Baumann: On the Management of Multidimensional Discrete Data. VLDB Journal
3 (4) 1994, Special Issue on Spatial Databases, pp. O 1- 444
[Guet-94]
R.H. Gueting: An Introduction to Spatial Database Systems. VLDB Journal 3(4)
1994,
Special Issue on Spatial Databases, pp. 357- 400
MwI,W-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
CA 02230301 1998-02-24
-25-
[SaSt-94]
S. Sarawagi, M. Stonebraker: Efficient Organization of Large Multi-
dimensional Arrays. Proc. 10th Int. Conf. on Data Engineering, Febru-
ary 1994
[Tamu-80]
H. Tamura: Image Database Management for Pattern Information
Processing Studies. S. Chang, K. Fu (eds): Pictorial Information Sys-
tems, Lecture Noises in Computer Science Vol. 80, Springer 1980, pp.
198-227
[VaDe-91 ]
S. Vandenberg, D. DeWitt: Algebraic Support for Complex Objects
with Arrays, Identity, and Inheritance. Proc. ACM SIGMOD Conf.
1991, pp. 158-161
