Система управления базами данных массивов или СУБД массивов предоставляет службы баз данных специально для массивов (также называемых растровыми данными ), то есть: однородные коллекции элементов данных (часто называемых пикселями , вокселями и т. д.), расположенных на регулярной сетке из одного, двух или более измерений. Часто массивы используются для представления данных датчиков, моделирования, изображений или статистики. Такие массивы, как правило, являются Большими данными , с отдельными объектами, часто достигающими размеров в Терабайт, а вскоре и в Петабайт; например, сегодняшние архивы наблюдений за Землей и космосом обычно растут на Терабайты в день. Базы данных массивов нацелены на предоставление гибкого, масштабируемого хранения и поиска по этой категории информации.
В том же стиле, что и стандартные системы баз данных для множеств, СУБД Array предлагают масштабируемое, гибкое хранение и гибкое извлечение/манипулирование массивами (концептуально) неограниченного размера. Поскольку на практике массивы никогда не появляются автономно, такая модель массива обычно встраивается в некоторую общую модель данных, например, в реляционную модель. Некоторые системы реализуют массивы как аналогию с таблицами, некоторые вводят массивы как дополнительный тип атрибута.
Управление массивами требует новых методов, особенно из-за того, что традиционные кортежи и объекты базы данных, как правило, хорошо вписываются в одну страницу базы данных — единицу доступа к диску на сервере, обычно 4 КБ — в то время как объекты массива легко могут охватывать несколько носителей. Основная задача менеджера хранения массивов — предоставить быстрый доступ к большим массивам и подмассивам. Для этого массивы во время вставки разбиваются на так называемые плитки или фрагменты удобного размера, которые затем действуют как единицы доступа во время оценки запроса.
СУБД массивов предлагают языки запросов, предоставляющие декларативный доступ к таким массивам, позволяя создавать, манипулировать, искать и удалять их. Как, например, в SQL , выражения произвольной сложности могут быть построены поверх набора основных операций массива. Из-за расширений, сделанных в модели данных и запросов, СУБД массивов иногда включаются в категорию NoSQL , в смысле «не только SQL». Оптимизация и распараллеливание запросов важны для достижения масштабируемости ; на самом деле, многие операторы массивов хорошо подходят для параллельной оценки, обрабатывая каждую плитку на отдельных узлах или ядрах.
Важные области применения массивов СУБД включают в себя науки о Земле, космосе, жизни и социальных науках, а также связанные с ними коммерческие приложения (например, разведка углеводородов в промышленности и OLAP в бизнесе). Разнообразие, возникающее в результате, можно наблюдать, например, в геоданных, где можно найти временные ряды датчиков окружающей среды 1-D, спутниковые изображения 2-D, временные ряды изображений 3-D x/y/t и геофизические данные x/y/z, а также климатические и океанические данные 4-D x/y/z/t.
Реляционная модель данных , которая преобладает сегодня, напрямую не поддерживает парадигму массива в той же степени, что и наборы и кортежи. ISO SQL перечисляет тип атрибута со значением массива, но он является только одномерным, практически без операционной поддержки и не может использоваться в прикладных областях СУБД Array. Другой вариант — прибегнуть к BLOB («двоичным большим объектам»), которые эквивалентны файлам: байтовым строкам (концептуально) неограниченной длины, но опять же без какой-либо функциональности языка запросов, такой как многомерное подмножество.
Первая значительная работа по выходу за рамки BLOB-объектов была начата с помощью PICDMS. [1] Эта система предлагает предшественника языка запросов к двумерным массивам, хотя все еще процедурного и без подходящей поддержки хранения.
Первый декларативный язык запросов, подходящий для нескольких измерений и с семантикой на основе алгебры, был опубликован Бауманом вместе с масштабируемой архитектурой. [2] [3] Другой язык массивов баз данных, ограниченный 2-D, был представлен Марате и Сейлемом. [4] Основополагающая теоретическая работа была выполнена Либкиным и др.; [5] в своей модели, называемой NCRA, они расширяют вложенное реляционное исчисление многомерными массивами; среди результатов есть важные вклады в анализ сложности запросов массивов. Алгебра карт, подходящая для 2-D и 3-D пространственных растровых данных, была опубликована Меннисом и др. [6]
С точки зрения реализаций СУБД Array, система Rasdaman имеет самую длинную историю реализаций nD-массивов с полной поддержкой запросов. Oracle GeoRaster предлагает фрагментированное хранение 2-D растровых карт, хотя и без интеграции SQL. TerraLib — это программное обеспечение ГИС с открытым исходным кодом, которое расширяет технологию объектно-реляционных СУБД для обработки пространственно-временных типов данных; хотя основное внимание уделяется векторным данным, также есть некоторая поддержка растров. Начиная с версии 2.0, PostGIS встраивает поддержку растров для 2-D растров; специальная функция предлагает декларативную функциональность растровых запросов. SciQL — это язык запросов массивов, добавляемый в СУБД MonetDB . SciDB — это более поздняя инициатива по созданию поддержки базы данных массивов. Как и SciQL, массивы рассматриваются как эквивалент таблиц, а не как новый тип атрибута, как в Rasdaman и PostGIS.
Для особого случая разреженных данных кубы данных OLAP хорошо зарекомендовали себя; они хранят значения ячеек вместе с их местоположением — адекватный метод сжатия в условиях небольшого количества местоположений, содержащих действительную информацию, — и работают с ними с помощью SQL. Поскольку этот метод не масштабируется по плотности, стандартные базы данных сегодня не используются для плотных данных, таких как спутниковые изображения, где большинство ячеек несут значимую информацию; вместо этого в управлении научными данными и подобных ситуациях преобладают собственные специальные реализации. Следовательно, именно здесь СУБД Array могут внести особый вклад.
В целом, массивы СУБД являются новой технологией. Хотя существуют операционно развернутые системы, такие как Oracle GeoRaster , PostGIS 2.0 и rasdaman , все еще остается много открытых исследовательских вопросов, включая проектирование и формализацию языка запросов, оптимизацию запросов, распараллеливание и распределенную обработку , а также проблемы масштабируемости в целом. Кроме того, научные сообщества по-прежнему неохотно принимают технологию массивов баз данных и склонны отдавать предпочтение специализированным, фирменным технологиям.
При добавлении массивов в базы данных необходимо пересмотреть все аспекты проектирования базы данных — от концептуального моделирования (например, подходящие операторы) до управления хранилищем (например, управление массивами, охватывающими несколько носителей) и обработки запросов (например, эффективные стратегии обработки).
Формально массив A задается (полной или частичной) функцией A : X → V , где X , домен , представляет собой d -мерный целочисленный интервал для некоторого d > 0 , а V , называемый диапазоном , представляет собой некоторое (непустое) множество значений; в нотации множеств это можно переписать как { ( p , v ) | p ∈ X , v ∈ V } . Каждое ( p , v ) в A обозначает элемент массива или ячейку , и следуя общепринятой нотации, мы пишем A [ p ] = v . Примеры для X включают {0..767} × {0..1023} (для изображений размера XGA ), примеры для V включают {0..255} для 8-битных изображений в оттенках серого и {0..255} × {0..255} × {0..255} для стандартных изображений RGB .
Следуя устоявшейся практике баз данных, язык запросов массивов должен быть декларативным и безопасным при оценке. Поскольку итерация по массиву лежит в основе обработки массивов, декларативность во многом сосредоточена на этом аспекте. Таким образом, требование заключается в том, что концептуально все ячейки должны проверяться одновременно — другими словами, запрос не навязывает никакой явной последовательности итераций по ячейкам массива во время оценки. Безопасность оценки достигается, когда каждый запрос завершается после конечного числа (конечного времени) шагов; опять же, избегание общих циклов и рекурсии является способом достижения этого. В то же время избегание явных последовательностей циклов открывает многочисленные возможности оптимизации.
В качестве примера для операторов запроса массива может служить алгебра и язык запросов Rasdaman , которые устанавливают язык выражений над минимальным набором примитивов массива. Мы начнем с общих основных операторов, а затем представим общие специальные случаи и сокращения.
Оператор marray создает массив в некотором заданном объеме домена и инициализирует его ячейки:
спецификация индекса-диапазона marrayзначения ячейка-значение-выражениегде index-range-specification определяет домен результата и привязывает к нему переменную итерации, не указывая последовательность итерации. Выражение cell-value-expression вычисляется в каждом месте домена.
Пример: «Вырез массива A, заданный угловыми точками (10,20) и (40,50)».
marray p в [10:20,40:50]значения А[п]Этот особый случай, чистое подмножество, можно сократить до
А[10:20,40:50]Это подмножество сохраняет размерность массива; для уменьшения размерности путем извлечения срезов в размерности среза указывается одно значение точки среза.
Пример: «Срез временного ряда x/y/t в позиции t=100, извлечение всех доступных данных в x и y».
А[*:*,*:*,100]Подстановочный знак * указывает на то, что следует использовать текущую границу массива; обратите внимание, что массивы, в которых границы измерений остаются открытыми во время определения, могут изменить размер этих измерений в течение срока службы массива.
В приведенных выше примерах исходные значения просто скопированы; вместо этого этими значениями можно манипулировать.
Пример: «Массив A, к каждому значению ячейки которого применена функция log()».
marray p в домене (A)значения log( A[p] )Это можно сократить так:
журнал( А )Благодаря принципу, называемому индуцированными операциями , [7] язык запросов предлагает все операции, которые тип ячеек предлагает на уровне массива. Следовательно, для числовых значений доступны все обычные унарные и двоичные арифметические, экспоненциальные и тригонометрические операции простым способом, а также стандартный набор булевых операторов.
Оператор confine агрегирует значения ячеек в один скалярный результат, подобно агрегатам SQL. Его применение имеет общую форму:
конденсировать конденсировать-оппо спецификации индекса-диапазонаиспользование выражения-значения-ячейкиКак и в случае с marray ранее, index-range-specification определяет домен, по которому будет выполнена итерация, и связывает с ним переменную итерации — опять же, без указания последовательности итерации. Аналогично, cell-value-expression оценивается в каждом местоположении домена. Предложение condense-op определяет операцию агрегирования, используемую для объединения выражений значений ячеек в одно значение.
Пример: «Сумма всех значений в A».
конденсировать +над p в sdom(A)используя А[п]Сокращенное обозначение этой операции:
добавить_ячейки( А )Аналогично агрегатам SQL предусмотрен ряд дополнительных сокращений, включая подсчет, среднее, минимальное, максимальное и булевы квантификаторы.
Следующий пример демонстрирует комбинацию операторов marray и confense путем получения гистограммы.
Пример: «Гистограмма 8-битного изображения в оттенках серого A».
ведро маррея в [0:255]значения count_cells( A = ведро )Индуцированное сравнение, A=bucket , устанавливает логический массив того же размера, что и A. Оператор агрегации подсчитывает вхождения true для каждого значения bucket , которое впоследствии помещается в соответствующую ячейку массива одномерной гистограммы.
Такие языки позволяют формулировать статистические и визуальные операции, которые могут быть выражены аналитически без использования циклов. Было доказано [8] , что выразительная сила таких массивных языков в принципе эквивалентна реляционным языкам запросов с ранжированием.
Хранилище массивов должно вмещать массивы разных измерений и обычно больших размеров. Основная задача — поддерживать пространственную близость на диске, чтобы сократить количество обращений к диску во время подмножества. Обратите внимание, что эмуляция многомерных массивов как вложенных списков (или одномерных массивов) сама по себе не достигнет этого и, следовательно, в общем случае не приведет к масштабируемым архитектурам.
Обычно массивы разбиваются на подмассивы, которые формируют единицу доступа. Регулярное разбиение, при котором все разделы имеют одинаковый размер (за исключением, возможно, границ), называется фрагментацией . [ 9] Обобщением, которое снимает ограничение на разделы одинакового размера путем поддержки любого вида разбиения, является разбиение на фрагменты . [10] Разбиение массива на фрагменты может значительно улучшить доступ к подмножествам массива: настраивая разбиение на фрагменты в соответствии с шаблоном доступа, сервер в идеале может извлечь все необходимые данные всего за один доступ к диску.
Сжатие плиток иногда может существенно сократить объем необходимого хранилища. Также сжатие полезно для передачи результатов, поскольку для больших объемов рассматриваемых данных пропускная способность сетей часто является ограничивающим фактором.
Плиточная структура хранения предполагает стратегию обработки по плиткам (в rasdaman это называется потоковое хранение плиток ). Большой класс практически значимых запросов может быть оценен путем загрузки плитки за плиткой, тем самым позволяя серверам обрабатывать массивы на порядки больше, чем их основная память.
Из-за огромных размеров массивов в научных/технических приложениях в сочетании с часто сложными запросами оптимизация играет центральную роль в обеспечении эффективности запросов массивов. Можно применять как аппаратное, так и программное распараллеливание. Примером эвристической оптимизации является правило «максимальное значение массива, полученного в результате поячеечного сложения двух входных изображений, эквивалентно сложению максимальных значений каждого входного массива». Заменяя левый вариант правым выражением, затраты сокращаются с трех (дорогостоящих) обходов массива до двух обходов массива плюс одна (дешевая) скалярная операция (см. рисунок, где используется стандарт запросов SQL/MDA).
Во многих, если не в большинстве, случаях, когда какое-либо явление отбирается или моделируется, результатом является растрированный набор данных, который можно удобно хранить, извлекать и пересылать как массив. Обычно данные массива украшены метаданными, описывающими их далее; например, географически привязанные изображения будут нести свое географическое положение и систему координат, в которой они выражены.
Ниже приведены типичные домены, в которых обрабатываются данные многомерных массивов большого масштаба:
Это всего лишь примеры; как правило, массивы часто представляют данные датчиков, моделирования, изображений и статистики. Все больше пространственных и временных измерений объединяются с абстрактными осями, такими как продажи и продукты; одним из примеров, где такие абстрактные оси явно предусмотрены, является модель покрытия [Open_Geospatial_Consortium |Open Geospatial Consortium] (OGC) .
Многие сообщества установили форматы обмена данными, такие как HDF , NetCDF и TIFF . Фактическим стандартом в сообществах Earth Science является OPeNDAP , архитектура и протокол передачи данных. Хотя это не спецификация базы данных, она предлагает важные компоненты, характеризующие систему базы данных, такие как концептуальная модель и реализации клиент/сервер.
Декларативный язык запросов к георастровым данным, Web Coverage Processing Service (WCPS), был стандартизирован Открытым геопространственным консорциумом (OGC).
В июне 2014 года ISO/IEC JTC1 SC32 WG3, которая поддерживает стандарт баз данных SQL, решила добавить поддержку многомерных массивов в SQL в качестве нового типа столбцов [11] на основе первоначальной поддержки массивов, доступной с версии SQL 2003 года . Новый стандарт, принятый осенью 2018 года, называется ISO 9075 SQL Часть 15: MDA (Многомерные массивы) .