Массивная СУБД
или Система управления базой данных массива СУБД массива предоставляет услуги базы данных специально для массивов (также называемых растровыми данными ), то есть: однородных наборов элементов данных (часто называемых пикселями , вокселами и т. д.), расположенных на регулярной сетке из одного, двух, или более измерений. Часто массивы используются для представления данных датчиков, моделирования, изображений или статистических данных. Такие массивы, как правило, представляют собой большие данные , причем размеры отдельных объектов часто достигают размеров терабайтов, а вскоре и петабайтов; например, сегодняшние архивы наблюдений за Землей и космосом обычно растут на терабайты в день. Базы данных массивов предназначены для обеспечения гибкого, масштабируемого хранения и поиска этой категории информации.
Обзор
[ редактировать ]Подобно тому, как стандартные системы баз данных делают это с множествами, СУБД Array предлагают масштабируемое, гибкое хранилище и гибкий поиск/манипулирование массивами (концептуально) неограниченного размера. Поскольку на практике массивы никогда не кажутся автономными, такая модель массива обычно встроена в некоторую общую модель данных, например, в реляционную модель. Некоторые системы реализуют массивы по аналогии с таблицами, некоторые вводят массивы как дополнительный тип атрибута.
Управление массивами требует новых методов, особенно из-за того, что традиционные кортежи и объекты базы данных, как правило, хорошо умещаются в одной странице базы данных — единице доступа к диску на сервере, обычно 4 КБ , — в то время как объекты массива легко могут охватывать несколько носителей. Основная задача менеджера хранения массивов — обеспечить быстрый доступ к большим массивам и подмассивам. С этой целью во время вставки массивы разбиваются на так называемые плитки или фрагменты удобного размера, которые затем действуют как единицы доступа во время оценки запроса.
СУБД массивов предлагают языки запросов, предоставляющие декларативный доступ к таким массивам, позволяющие создавать, манипулировать, искать и удалять их. Как, например, в SQL , выражения произвольной сложности могут быть построены поверх набора основных операций с массивами. Из-за расширений, внесенных в модель данных и запросов, СУБД Array иногда относят к категории NoSQL в смысле «не только SQL». запросов Оптимизация и распараллеливание важны для достижения масштабируемости ; на самом деле многие операторы массивов хорошо подходят для параллельных вычислений, обрабатывая каждый фрагмент на отдельных узлах или ядрах.
Важные области применения СУБД Array включают науки о Земле, космосе, жизни и социальных науках, а также связанные с ними коммерческие приложения (например, разведку углеводородов в промышленности и OLAP в бизнесе). Происходящее разнообразие можно наблюдать, например, в геоданных, где одномерные временные ряды датчиков окружающей среды, двухмерные спутниковые изображения, трехмерные временные ряды изображений x/y/t и геофизические данные x/y/z, а также Можно найти 4-D данные о климате и океане x/y/z/t.
История и статус
[ редактировать ]кортежи . Преобладающая сегодня реляционная модель данных не поддерживает напрямую парадигму массива в той же степени, что и наборы и ISO SQL перечисляет тип атрибута со значением массива, но он является только одномерным, практически не имеет операционной поддержки и не может использоваться для областей приложений СУБД Array. Другой вариант — использовать BLOB («большие двоичные объекты»), которые эквивалентны файлам: байтовые строки (концептуально) неограниченной длины, но опять же без каких-либо функций языка запросов, таких как многомерное подмножество.
Первая значительная работа по выходу за рамки BLOB была проведена с PICDMS. [1] Эта система является предшественником языка запросов к двумерным массивам, хотя и остается процедурным и без подходящей поддержки хранилища.
Первый декларативный язык запросов, подходящий для нескольких измерений и с семантикой на основе алгебры, был опубликован Baumann вместе с масштабируемой архитектурой. [2] [3] Другой язык баз данных массивов, ограниченный двумерностью, был представлен Марате и Салемом. [4] Основополагающая теоретическая работа была проделана Либкиным и др.; [5] в своей модели, названной NCRA, они расширяют вложенное реляционное исчисление многомерными массивами; среди результатов есть важный вклад в анализ сложности запросов к массивам. Алгебра карт, подходящая для 2-D и 3-D пространственных растровых данных, была опубликована Mennis et al. [6]
Что касается реализаций СУБД Array, система rasdaman имеет самый длинный опыт внедрения массивов nD с полной поддержкой запросов. Oracle GeoRaster предлагает фрагментированное хранилище двумерных растровых карт, хотя и без интеграции SQL. TerraLib — это ГИС-программное обеспечение с открытым исходным кодом, которое расширяет технологию объектно-реляционной СУБД для обработки пространственно-временных типов данных; хотя основное внимание уделяется векторным данным, имеется также некоторая поддержка растров. Начиная с версии 2.0, PostGIS включает поддержку двумерных растров; специальная функция предлагает функциональность декларативного растрового запроса. SciQL — язык запросов к массивам, добавляемый в СУБД MonetDB . SciDB — это более поздняя инициатива по созданию поддержки баз данных массивов. Как и в SciQL, массивы рассматриваются как эквивалент таблиц, а не как новый тип атрибута, как в rasdaman и PostGIS.
Для частного случая данных разреженных OLAP хорошо зарекомендовали себя кубы данных ; они хранят значения ячеек вместе с их местоположением (адекватный метод сжатия, учитывая то, что мало мест вообще содержат достоверную информацию), и работают с ними с помощью SQL. Поскольку этот метод не масштабируется по плотности, стандартные базы данных сегодня не используются для хранения плотных данных, таких как спутниковые изображения, где большинство ячеек несут значимую информацию; скорее, в управлении научными данными и подобных ситуациях преобладают запатентованные специальные реализации. Следовательно, именно здесь СУБД Array могут внести особый вклад.
В целом СУБД Array — это новая технология. Хотя существуют оперативно развернутые системы, такие как Oracle GeoRaster , PostGIS 2.0 и rasdaman , все еще остается много открытых исследовательских вопросов, включая проектирование и формализацию языка запросов, оптимизацию запросов, распараллеливание и распределенную обработку , а также проблемы масштабируемости в целом. Кроме того, научные сообщества по-прежнему неохотно принимают технологию массивов баз данных и склонны отдавать предпочтение специализированным, запатентованным технологиям.
Концепции
[ редактировать ]При добавлении массивов в базы данных необходимо пересмотреть все аспекты проектирования базы данных — от концептуального моделирования (например, подходящих операторов) до управления хранилищем (например, управления массивами, охватывающими несколько носителей) и обработки запросов (например, эффективных стратегий обработки).
Концептуальное моделирование
[ редактировать ]Формально массив A задается (полной или частичной) функцией A : X → V , где X , область определения представляет собой d -мерный целочисленный интервал для некоторого d > 0, а V , называемый диапазоном , является некоторым (непустым) набор значений; в обозначениях множеств это можно переписать как { ( p , v ) | п ∈ Икс , 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 .
Следуя установившейся практике работы с базами данных, язык запросов к массивам должен быть декларативным и безопасным при вычислении. Поскольку итерация по массиву лежит в основе обработки массива, декларативность во многом сосредоточена на этом аспекте. Таким образом, требование заключается в том, что концептуально все ячейки должны проверяться одновременно – другими словами, запрос не навязывает какой-либо явной последовательности итераций по ячейкам массива во время оценки. Безопасность оценки достигается, когда каждый запрос завершается после конечного числа шагов (за конечное время); опять же, способ добиться этого — избегать общих циклов и рекурсии. В то же время отказ от явных последовательностей циклов открывает многочисленные возможности оптимизации.
Запрос массива
[ редактировать ]Примером операторов запроса массива могут служить алгебра Расдамана и язык запросов, которые устанавливают язык выражений для минимального набора примитивов массива. Мы начнем с общих основных операторов, а затем представим общие частные случаи и сокращения.
Оператор marray создает массив в некотором заданном экстенте домена и инициализирует его ячейки:
marray index-range-specification
values cell-value-expression
где спецификация индекса-диапазона определяет результирующий домен и привязывает к нему переменную итерации без указания последовательности итераций. оценивается Выражение-значения-ячейки в каждом месте домена.
Пример: «Вырез массива A, заданный угловыми точками (10,20) и (40,50)».
marray p in [10:20,40:50]
values A[p]
Этот особый случай, чистое подмножество, можно сократить как
A[10:20,40:50]
Эта подгруппа сохраняет размерность массива; Чтобы уменьшить размерность путем извлечения срезов, в измерении среза указывается одно значение точки среза.
Пример: «Срез временной серии x/y/t в позиции t=100, получение всех доступных данных в координатах x и y».
A[*:*,*:*,100]
Подстановочный оператор * указывает, что должна использоваться текущая граница массива; Обратите внимание, что массивы, границы измерений которых остаются открытыми во время определения, могут изменить размер этих измерений в течение срока службы массива.
В приведенных выше примерах просто скопированы исходные значения; вместо этого этими значениями можно манипулировать.
Пример: «Массив A, к каждому значению ячейки применена функция log()».
marray p in domain(A)
values log( A[p] )
Это можно сократить как:
log( A )
С помощью принципа, называемого индуцированными операциями , [7] язык запросов предлагает все операции, которые предлагает тип ячейки, также на уровне массива. Следовательно, над числовыми значениями доступны все обычные унарные и двоичные арифметические, экспоненциальные и тригонометрические операции, а также стандартный набор логических операторов.
Оператор конденсации объединяет значения ячеек в один скалярный результат, аналогично агрегированию SQL. Его применение имеет общий вид:
condense condense-op
over index-range-specification
using cell-value-expression
Как и в предыдущем случае с marray , спецификация index-range указывает домен, по которому выполняется итерация, и привязывает к нему переменную итерации — опять же, без указания последовательности итераций. Аналогично, выражение-значения-ячейки оценивается в каждом местоположении домена. Предложение конденсации определяет операцию агрегирования , используемую для объединения выражений значений ячеек в одно значение.
Пример: «Сумма по всем значениям в A».
condense +
over p in sdom(A)
using A[p]
Сокращенно для этой операции:
add_cells( A )
Таким же образом и по аналогии с агрегатами SQL предоставляется ряд дополнительных сокращений, включая подсчет, среднее, минимальное, максимальное и логические квантификаторы.
В следующем примере демонстрируется сочетание операторов Маррэй и Конденсация путем построения гистограммы.
Пример: «Гистограмма 8-битного изображения A в оттенках серого».
marray bucket in [0:255]
values count_cells( A = bucket )
Индуцированное сравнение A=bucket устанавливает логический массив того же размера, что A. и Оператор агрегации подсчитывает вхождения true для каждого значения Bucket , которое впоследствии помещается в соответствующую ячейку массива одномерной гистограммы.
Такие языки позволяют формулировать статистические и графические операции, которые можно выразить аналитически без использования циклов. Это было доказано [8] что выразительная сила таких языков массивов в принципе эквивалентна реляционным языкам запросов с ранжированием.
Хранение массива
[ редактировать ]Хранилище массивов должно вмещать массивы разных размеров и обычно больших размеров. Основная задача — поддерживать пространственную близость на диске, чтобы уменьшить количество обращений к диску во время подмножества. Обратите внимание, что эмуляция многомерных массивов в виде вложенных списков (или одномерных массивов) сама по себе не обеспечит этого и, следовательно, в целом не приведет к созданию масштабируемых архитектур.
Обычно массивы разбиваются на подмассивы, которые образуют единицу доступа. Обычное разделение, при котором все разделы имеют одинаковый размер (за исключением, возможно, границ), называется фрагментированием . [9] Обобщением, которое снимает ограничение на разделы одинакового размера, поддерживая любой тип разделения, является тайлинг . [10] Разделение массива может значительно улучшить доступ к подмножествам массива: адаптируя разбиение к шаблону доступа, сервер в идеале может получить все необходимые данные, используя только один доступ к диску.
Сжатие плиток иногда может существенно уменьшить необходимый объем памяти. Также для передачи результатов полезно сжатие, поскольку для больших объемов рассматриваемых данных пропускная способность сети часто является ограничивающим фактором.
Обработка запросов
[ редактировать ]Тайловая структура хранения предполагает стратегию потайловой обработки (на расдамане это называется тайловой потоковой передачей ). Большой класс практически значимых запросов можно оценить, загружая плитку за плиткой, что позволяет серверам обрабатывать массивы, на порядки превышающие объем их основной памяти.
Из-за огромных размеров массивов в научно-технических приложениях в сочетании с зачастую сложными запросами оптимизация играет центральную роль в обеспечении эффективности запросов к массивам. Может применяться как аппаратное, так и программное распараллеливание. Примером эвристической оптимизации является правило «максимальное значение массива, полученное в результате сложения по ячейкам двух входных изображений, эквивалентно сложению максимальных значений каждого входного массива». Заменив левый вариант правым выражением, затраты сокращаются с трех (затратных) обходов массива до двух обходов массива плюс одна (дешевая) скалярная операция (см. рисунок, на котором используется стандарт запросов SQL/MDA).
Домены приложений
[ редактировать ]Во многих, если не в большинстве, случаях, когда какое-либо явление отбирается или моделируется, результатом является растеризованный набор данных, который можно удобно хранить, извлекать и пересылать в виде массива. Обычно данные массива сопровождаются метаданными, описывающими их дальше; например, изображения с географической привязкой будут содержать свое географическое положение и систему координат, в которой они выражены.
Ниже приведены репрезентативные области, в которых обрабатываются данные крупномасштабных многомерных массивов:
- Науки о Земле: геодезия/картографирование, дистанционное зондирование , геология, океанография, гидрология, науки об атмосфере, науки о криосфере.
- Космические науки: планетарные науки, астрофизика (наблюдения с помощью оптических и радиотелескопов, космологическое моделирование).
- Науки о жизни: генные данные, конфокальная микроскопия, компьютерная томография.
- Социальные науки: кубы статистических данных
- Бизнес: OLAP, хранилища данных
Это всего лишь примеры; Как правило, массивы часто представляют данные датчиков, моделирования, изображений и статистические данные. Все больше пространственных и временных измерений объединяются с абстрактными осями, такими как продажи и продукты; Одним из примеров, когда такие абстрактные оси явно предусмотрены, является модель покрытия [Open_Geospatial_Consortium |Open Geospatial Consortium] (OGC) .
Стандартизация
[ редактировать ]Многие сообщества установили форматы обмена данными, такие как HDF , NetCDF и TIFF . Стандартом де-факто в сообществах наук о Земле является OPeNDAP , архитектура и протокол передачи данных. Хотя это не спецификация базы данных, она предлагает важные компоненты, характеризующие систему базы данных, такие как концептуальная модель и реализации клиент/сервер.
Декларативный язык растровых запросов Web Coverage Processing Service (WCPS) был стандартизирован Открытым геопространственным консорциумом (OGC).
В июне 2014 года рабочая группа ISO/IEC JTC1 SC32 WG3, поддерживающая стандарт баз данных SQL, решила добавить в SQL поддержку многомерных массивов в качестве нового типа столбца. [11] на основе первоначальной поддержки массивов, доступной начиная с версии SQL 2003 года . Новый стандарт, принятый осенью 2018 года, называется ISO 9075 SQL Part 15: MDA (Multi-Dimensional Arrays) .
Список массивовых СУБД
[ редактировать ]См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Чок, М., Карденас, А., Клингер, А.: Структура базы данных и возможности манипулирования системой управления базой данных изображений (PICDMS). IEEE ToPAMI, 6(4):484–492, 1984 г.
- ^ Бауманн, П.: Об управлении многомерными дискретными данными . Журнал VLDB 4 (3) 1994, специальный выпуск о системах пространственных баз данных, стр. 401–444.
- ^ Бауманн, П.: Алгебра массива базы данных для пространственно-временных данных и не только . Учеб. НГИТС'99, LNCS 1649, Springer 1999, стр.76-93.
- ^ Марат, А., Салем, К.: Язык для управления массивами. Учеб. VLDB'97, Афины, Греция, август 1997 г., стр. 46–55.
- ^ Либкин Л., Махлин Р., Вонг Л.: Язык запросов для многомерных массивов: методы проектирования, реализации и оптимизации. Учеб. ACM SIGMOD'96, Монреаль, Канада, стр. 228–239.
- ^ Меннис, Дж., Вигер, Р., Томлин, К.Д.: Функции алгебры кубических карт для пространственно-временного анализа. Картография и географическая информатика 32 (1) 2005 г., стр. 17–32.
- ^ Риттер, Г., Уилсон, Дж. и Дэвидсон, Дж.: Алгебра изображений: обзор. Компьютерное зрение, графика и обработка изображений, 49 (1) 1994, 297-336.
- ^ Махлин, Р.: Запросы к многомерным массивам на основе индексов: безопасность и эквивалентность. Учеб. ACM PODS'07, Пекин, Китай, июнь 2007 г., стр. 175–184.
- ^ Сараваги, С. , Стоунбрейкер, М .: Эффективная организация больших многомерных массивов. Учеб. ICDE'94, Хьюстон, США, 1994, стр. 328-336.
- ^ Фуртадо, П., Бауманн, П.: Хранение многомерных массивов на основе произвольного разбиения на мозаику . Учеб. ICDE'99, 23–26 марта 1999 г., Сидней, Австралия, стр. 328–336.
- ^ Чиргвин, Р.: SQL сопротивляется авторитету NoSQL в области больших данных с помощью спецификации SQL/MDA , The Register, 26 июня 2014 г.
