When adding arrays to databases, all facets of database design need to be reconsidered – ranging from conceptual modeling (such as suitable operators) over storage management (such as management of arrays spanning multiple media) to query processing (such as efficient processing strategies).
Conceptual modeling
Formally, an array A is given by a (total or partial) function A: X → V where X, the domain is a d-dimensional integer interval for some d> 0 and V, called range, is some (non-empty) value set; in set notation, this can be rewritten as { (p,v) | p ∈ X, v ∈ V}. Each (p,v) in A denotes an array element or cell, and following common notation we write A[p] = v. Examples for X include {0..767} × {0..1023} (for 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 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
As an example for array query operators the rasdaman algebra and query language can serve, which establish an expression language over a minimal set of array primitives. We begin with the generic core operators and then present common special cases and shorthands.
The marray operator creates an array over some given domain extent and initializes its cells:
marray index-range-specification values cell-value-expression
where index-range-specification defines the result domain and binds an iteration variable to it, without specifying iteration sequence. The cell-value-expression is evaluated at each location of the domain.
Example: "A cutout of array A given by the corner points (10,20) and (40,50)."
marray p in [10:20,40:50] values A[p]
This special case, pure subsetting, can be abbreviated as
This subsetting keeps the dimension of the array; to reduce dimension by extracting slices, a single slicepoint value is indicated in the slicing dimension.
Example: "A slice through an x/y/t timeseries at position t=100, retrieving all available data in x and y."
The wildcard operator * indicates that the current boundary of the array is to be used; note that arrays where dimension boundaries are left open at definition time may change size in that dimensions over the array's lifetime.
The above examples have simply copied the original values; instead, these values may be manipulated.
Example: "Array A, with a log() applied to each cell value."
marray p in domain(A) values log( A[p] )
This can be abbreviated as:
Through a principle called induced operations, [7] 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.
The condense operator aggregates cell values into one scalar result, similar to SQL aggregates. Its application has the general form:
condense condense-op over index-range-specification using cell-value-expression
As with marray before, the index-range-specification specifies the domain to be iterated over and binds an iteration variable to it – again, without specifying iteration sequence. Likewise, cell-value-expression is evaluated at each domain location. The condense-op clause specifies the aggregating operation used to combine the cell value expressions into one single value.
Example: "The sum over all values in A."
condense + over p in sdom(A) using A[p]
A shorthand for this operation is:
In the same manner and in analogy to SQL aggregates, a number of further shorthands are provided, including counting, average, minimum, maximum, and Boolean quantifiers.
The next example demonstrates combination of marray and condense operators by deriving a histogram.
Example: "A histogram over 8-bit greyscale image A."
marray bucket in [0:255] values count_cells( A = bucket )
The induced comparison, A=bucket, establishes a Boolean array of the same extent as A. The aggregation operator counts the occurrences of true for each value of bucket, which subsequently is put into the proper array cell of the 1-D histogram array.
Such languages allow formulating statistical and imaging operations which can be expressed analytically without using loops. It has been proven [8] that the expressive power of such array languages in principle is equivalent to relational query languages with ranking.
