Array DBMS: Difference between revisions

Revision as of 08:25, 17 August 2012

Revision as of 13:21, 25 August 2012

Line 1:

Array database management systems (DBMSs) provide [[Database_management_systemDatabase management system|database]] services specifically for [[Array|arraysarray]]s (also called [[Raster_graphicsRaster graphics|raster data]]), that is: homogeneous collections of data items (often called [[Pixel|pixelspixel]]s, [[Voxel|voxelsvoxel]]s, etc.), sitting on a regular grid of one, two, or more dimensions.

Array database management systems (DBMSs) provide [[Database_management_system|database]] services specifically for [[Array|arrays]] (also called [[Raster_graphics|raster data]]), that is: homogeneous collections of data items (often called [[Pixel|pixels]], [[Voxel|voxels]], etc.), sitting on a regular grid of one, two, or more dimensions.

Often arrays are used to represent sensor, simulation, image, or statistics data.

Such arrays tend to be [[Big_dataBig data|Big Data]], with single objects frequently ranging into Terabyte and soon Petabyte sizes; for example, today’s earth and space observation archives typically grow by Terabytes a day.

Array databases aim at offering flexible, scalable storage and retrieval on this information category.

[[Image:Euclidean_neighborhood_in_nEuclidean neighborhood in n-D_arraysD arrays.png|frame|x110px|alt=Euclidean neighborhood of elements in arrays|Euclidean neighborhood of elements in arrays]]

== Overview ==

In the same style as standard [[Database_Management_SystemDatabase Management System|database systems]] do on sets, Array DBMSs offer scalable, flexible storage and flexible retrieval/manipulation on arrays of (conceptually) unlimited size.

As in practice arrays never appear standalone, such an array model normally is embedded into some overall data model, such as the relational model.

Some systems implement arrays as an analogy to tables, some introduce arrays as an additional attribute type.

Line 18 ⟶ 16:

To this end, arrays get partitioned, during insertion, into so-called ''tiles'' or ''chunks'' of convenient size which then act as units of access during query evaluation.

Array DBMSs offer [[Data_Manipulation_LanguageData Manipulation Language|query languages]] giving [[Declarative_programmingDeclarative programming|declarative]] access to such arrays, allowing to create, manipulate, search, and delete them.

Like with, e.g., [[SQL]], expressions of arbitrary complexity can be built on top of a set of core array operations.

Due to the extensions made in the data and query model, Array DBMSs sometimes are subsumed under the [[NoSQL]] category, in the sense of "not only SQL".

Query [[Query_optimizationQuery optimization|optimization]] and [[Parallel_computingParallel computing|parallelization]] are important for achieving [[scalability]]; actually, many array operators lend themselves well towards parallel evaluation, by processing each tile on separate nodes or cores.

Important application domains of Array DBMSs include Earth, Space, Life, and Social sciences, as well as the related commercial applications (such as [[Oil_explorationOil exploration|hydrocarbon exploration]] in industry and [[OLAP]] in business).

The variety occurring can be observed, e.g., in geo data where 1-D environmental sensor time series, 2-D satellite images, 3-D x/y/t image time series and x/y/z geophysics data, as well as 4-D x/y/z/t climate and ocean data can be found.

== History and Status ==

The [[Relational_databaseRelational database|relational data model]], which is prevailing today, does not directly support the array paradigm to the same extent as sets and tuples. [[International_Organization_for_StandardsInternational Organization for Standards|ISO]] [[SQL]] lists an array-valued attribute type, but this is only one-dimensional, with almost no operational support, and not usable for the [[#Application_Domains|application domains]] of Array DBMSs.

Another option is to resort to [[Binary_large_objectBinary large object|BLOB]]s ("binary large objects") which are the equivalent to files: byte strings of (conceptually) unlimited length, but again without any query language functionality, such as multi-dimensional subsetting.

First significant work in going beyond BLOBs has been established with PICDMS.<ref>Chock, M., Cardenas, A., Klinger, A.: Database structure and manipulation capabilities of a picture database management system (PICDMS). IEEE ToPAMI, 6(4):484-492, 1984</ref>. This system offers the precursor of a 2-D array query language, albeit still procedural and without suitable storage support.

A first declarative query language suitable for multiple dimensions and with an algebra-based semantics has been published by [[Peter_Baumann_Peter Baumann (computer_scientistcomputer scientist)|Baumann]], together with a scalable architecture.<ref>Baumann, P.: [http://www.informatik.uni-trier.de/~ley/db/journals/vldb/vldb3.html#Baumann94 On the Management of Multidimensional Discrete Data]. VLDB Journal 4(3)1994, Special Issue on Spatial Database Systems, pp. 401 - 444</ref><ref>Baumann, P.: [http://www.informatik.uni-trier.de/~ley/db/conf/ngits/ngits99.html#Baumann99 A Database Array Algebra for Spatio-Temporal Data and Beyond]. Proc. NGITS’99, LNCS 1649, Springer 1999, pp.76-93</ref>.

Another array database language, constrained to 2-D, has been presented by Marathe and Salem.<ref>Marathe, A., Salem, K.: A language for manipulating arrays. Proc. VLDB’97, Athens, Greece, August 1997, pages 46 - 55</ref>.

Seminal theoretical work has been accomplished by Libkin et al.;<ref>Libkin, L., Machlin, R., Wong, L.: A query language for multidimensional arrays: design, implementation and optimization techniques. Proc. ACM SIGMOD’96, Montreal, Canada, pp. 228 - 239</ref>; in their model, called NCRA, they extend a nested relational calculus with multidimensional arrays; among the results are important contributions on array query complexity analysis.

A map algebra, suitable for 2-D and 3-D spatial raster data, has been published by Mennis et al.<ref>Mennis, J., Viger, R., Tomlin, C.D.: Cubic Map Algebra Functions for Spatio-Temporal Analysis. Cartography and Geographic Information Science 32(1)2005, pp. 17 - 32</ref>.

In terms of Array DBMS implementations, the [[rasdaman]] system has the longest implementation track record of n-D arrays with full query support.

[[Oracle_SpatialOracle Spatial|Oracle GeoRaster]] offers chunked storage of 2-D raster maps, albeit without SQL integration.

[[TerraLib]] is an open-source GIS software that extends object-relational DBMS technology to handle spatio-temporal data types; while main focus is on vector data, there is also some support for rasters.

Starting with version 2.0, [[Postgis|PostGIS]] embeds raster support for 2-D rasters; a special function offers declarative raster query functionality.

SciQL is an array query language being added to the [[MonetDB]] DBMS. [[Michael_Stonebraker#SciDB|SciDB]] is a more recent initiative to establish array database support. Like SciQL, arrays are seen as an equivalent to tables, rather than a new attribute type as in rasdaman and PostGIS.

For the special case of [[Sparse_matrixSparse matrix|sparse data]], [[OLAP]] data cubes are well established; they store cell values together with their ___location - an adequate compression technique in face of the few locations carrying valid information at all - and operate with SQL on them.

As this technique does not scale in density, standard databases are not used today for dense data, like satellite images, where most cells carry meaningful information; rather, proprietary ad-hoc implementations prevail in scientific data management and similar situations. Hence, this is where Array DBMSs can make a particular contribution.

Generally, Array DBMSs are an emerging technology. While operationally deployed systems exist, like [[Oracle_SpatialOracle Spatial|Oracle GeoRaster]], [[Postgis|PostGIS 2.0]] and [[rasdaman]], there are still many open research questions, including query language design and formalization, query optimization, parallelization and distributed processing, and scalability issues in general. Besides, scientific communities still appear reluctant in taking up array database technology and tend to favor specialized, proprietary technology.

== Concepts ==

Line 60 ⟶ 57:

Examples for ''X'' include {0..767} × {0..1023} (for [[Xga#Extended_graphics_array|XGA]] sized images), examples for ''V'' include {0..255} for 8-bit greyscale images and {0..255} × {0..255} × {0..255} for standard [[RGB]] imagery.

Following established database practice, an array query language should be [[Declarative_programmingDeclarative programming|declarative]] and safe in evaluation.

As iteration over an array is at the heart of array processing, declarativeness very much centers on this aspect. The requirement, then, is that conceptually all cells should be inspected simultaneously - in other words, the query does not enforce any explicit iteration sequence over the array cells during evaluation.

Evaluation safety is achieved when every query terminates after a finite number of (finite-time) steps; again, avoiding general loops and recursion is a way of achieving this.

At the same time, avoiding explicit loop sequences opens up manifold optimization opportunities.

=== Array Querying ===

Line 108 ⟶ 104:

</source>

Through a principle called ''induced operations'',<ref>Ritter, G. and Wilson, J. and Davidson, J.: Image Algebra: An Overview. Computer Vision, Graphics, and Image Processing, 49(1)1994, 297-336</ref>, the query language offers all operations the cell type offers on array level, too.

Hence, on numeric values all the usual unary and binary arithmetic, exponential, and trigonometric operations are available in a straightforward manner, plus the standard set of Boolean operators.

Line 151 ⟶ 147:

Commonly arrays are partitioned into sub-arrays which form the unit of access.

Regular partitioning where all partitions have the same size (except possibly for boundaries) is referred to as ''chunking''.<ref>Sarawagi, S., Stonebraker, M.: Efficient Organization of Large Multidimensional Arrays. Proc. ICDE'94, Houston, USA, 1994, pp. 328-336</ref>. A generalization which removes the restriction to equally sized partitions by supporting any kind of partitioning is ''tiling''.<ref>Furtado, P., Baumann, P.: [http://www.informatik.uni-trier.de/~ley/db/conf/icde/icde99.html#FurtadoB99 Storage of Multidimensional Arrays based on Arbitrary Tiling]. Proc. ICDE'99, March 23-2623–26, 1999, Sydney, Australia, pp. 328 - 336</ref>. Array partitioning can improve access to array subsets significantly: by adjusting tiling to the access pattern, the server ideally can fetch all required data with only one disk access.

Compression of tiles can sometimes reduce substantially the amount of storage needed. Also for transmission of results compression is useful, as for the large amounts of data under consideration networks bandwidth often constitutes a limiting factor.

Line 159 ⟶ 155:

A tile-based storage structure suggests a tile-by-tile processing strategy (in [[rasdaman]] called ''tile streaming''). A large class of practically relevant queries can be evaluated by loading tile after tile, thereby allowing servers to process arrays orders of magnitude beyoned their main memory.

[[File:Sample_heuristic_optimization_of_array_querySample heuristic optimization of array query.png|frame|x200px|alt=Sample rule for heuristic array query optimization|Sample rule for heuristic array query optimization]]

Due to the massive sizes of arrays in scientific/technical applications in combination with often complex queries, optimization plays a central role in making array queries efficient. Both hardware and software parallelization can be applied. An example for heuristic optimization is the rule "averaging over an array resulting from the cell-wise addition of two input images is equivalent to adding the averages of each input array". By replacing the left-hand variant by the right-hand expression, costs shrink from three (costly) array traversals to two array traversals plus one (cheap) scalar operation (see Figure, which uses the [[rasdaman]] query language introduced before).

Line 174 ⟶ 170:

These are but examples; generally, arrays frequently represent sensor, simulation, image, and statistics data.

More and more spatial and time dimensions are combined with ''abstract'' axes, such as sales and products; one example where such abstract axes are explicitl< foreseen is the [Open_Geospatial_Consortium |Open Geospatial Consortium] (OGC) [[Coverage_dataCoverage data|coverage model]].

== Standardization ==

Many communities have established data exchange formats, such as [[Hdf|HDF]], [[Netcdf|NetCDF]], and [[Tagged_Image_File_FormatTagged Image File Format|TIFF]].

A de facto standard in the Earth Science communities is [[Opendap|OPeNDAP]], a data transport architecture and protocol. While this is not a database specification, it offers important components that characterize a database system, such as a conceptual model and client/server implementations.

A declarative geo raster query language, [[Web_Coverage_Processing_Service|Web Coverage Processing Service]] (WCPS), has been standardized by the [[Open Geospatial Consortium]] (OGC).

== References ==

Line 190 ⟶ 184:

== See also ==

[[Data Intensive Computing]]

<!--- Categories --->

{{Uncategorized|date=August 2012}}

[[Category:Articles created via the Article Wizard]]