Массив СУБД - Array DBMS

Системы управления массивами баз данных (массивные СУБД) предоставлять база данных услуги специально для массивы (также называемый растровые данные ), то есть однородные коллекции элементов данных (часто называемые пиксели, воксели и т. д.), расположенные на регулярной сетке из одного, двух или более измерений. Часто массивы используются для представления данных датчика, моделирования, изображения или статистики. Такие массивы обычно Большое количество данных, с отдельными объектами, размер которых часто достигает терабайт, а вскоре и петабайтов; например, современные архивы наблюдений за Землей и космосом обычно растут на терабайт в день. Базы данных массивов нацелены на обеспечение гибкого, масштабируемого хранения и поиска по этой категории информации.

Евклидова окрестность элементов в массивах
Евклидова окрестность элементов в массивах

Обзор

В том же стиле, что и стандарт системы баз данных Делая на наборах, СУБД на основе массивов предлагают масштабируемое, гибкое хранилище и гибкое извлечение / манипулирование массивами (концептуально) неограниченного размера. Поскольку на практике массивы никогда не кажутся автономными, такая модель массива обычно встраивается в некоторую общую модель данных, такую ​​как реляционная модель. Некоторые системы реализуют массивы по аналогии с таблицами, некоторые вводят массивы как дополнительный тип атрибута.

Управление массивами требует новых методов, особенно из-за того, что традиционные кортежи и объекты базы данных, как правило, хорошо помещаются на одной странице базы данных - единице доступа к диску на сервере, обычно 4КБ - в то время как объекты массива легко могут охватывать несколько носителей. Основная задача диспетчера хранения массивов - предоставить быстрый доступ к большим массивам и подмассивам. Для этого во время вставки массивы разбиваются на так называемые плитка или же куски удобного размера, которые затем выступают в качестве единиц доступа во время оценки запроса.

Предложение массивных СУБД языки запросов давая декларативный доступ к таким массивам, позволяющий создавать, манипулировать, искать и удалять их. Как, например, SQL, выражения произвольной сложности могут быть построены на основе набора основных операций над массивом. Из-за расширений, сделанных в модели данных и запросов, СУБД Array иногда попадают в категорию NoSQL категория в смысле «не только SQL». Запрос оптимизация и распараллеливание важны для достижения масштабируемость; Фактически, многие операторы массивов хорошо подходят для параллельной оценки, обрабатывая каждый тайл на отдельных узлах или ядрах.

Важные прикладные области СУБД Array включают Землю, Космос, Жизнь и Социальные науки, а также связанные с ними коммерческие приложения (такие как разведка углеводородов в промышленности и OLAP в делах). Разнообразие может наблюдаться, например, в геоданных, где временные ряды одномерных датчиков окружающей среды, двухмерные спутниковые изображения, трехмерные временные ряды изображений x / y / t и данные геофизики x / y / z, а также Можно найти 4-D x / y / z / t климатические и океанические данные.

История и статус

В реляционная модель данных, который преобладает сегодня, не поддерживает парадигму массивов напрямую в той же степени, что и наборы и кортежи. ISO SQL перечисляет тип атрибута со значениями массива, но это только одномерный, почти без операционной поддержки и не может использоваться для домены приложений массивных СУБД. Другой вариант - прибегнуть к BLOB-объекты («большие двоичные объекты»), которые эквивалентны файлам: байтовые строки (концептуально) неограниченной длины, но опять же без каких-либо функций языка запросов, таких как многомерное подмножество.

Первая значительная работа по выходу за рамки BLOB была начата с PICDMS.[1] Эта система предлагает предшественник языка запросов двумерных массивов, хотя все еще процедурный и без подходящей поддержки хранения.

Первый декларативный язык запросов, подходящий для нескольких измерений и с семантикой на основе алгебры, был опубликован Бауманн вместе с масштабируемой архитектурой.[2][3] Другой язык базы данных массивов, ограниченный до 2-D, был представлен Маратом и Салемом.[4] Основная теоретическая работа выполнена Libkin et al .;[5] в своей модели NCRA они расширяют вложенное реляционное исчисление многомерными массивами; Среди результатов - важный вклад в анализ сложности запросов к массивам. Алгебра карт, подходящая для двумерных и трехмерных пространственных растровых данных, была опубликована Mennis et al.[6]

С точки зрения реализаций СУБД Array Расдаман Система имеет самый длинный послужной список внедрения n-D массивов с полной поддержкой запросов. Oracle GeoRaster предлагает фрагментированное хранилище двухмерных растровых карт, хотя и без интеграции SQL. TerraLib это программное обеспечение ГИС с открытым исходным кодом, которое расширяет технологию объектно-реляционной СУБД для обработки пространственно-временных типов данных; Хотя основное внимание уделяется векторным данным, есть также некоторая поддержка растров. Начиная с версии 2.0, PostGIS встраивает растровую поддержку для двухмерных растров; специальная функция предлагает функциональные возможности декларативного растрового запроса. SciQL язык запросов к массивам, добавляемый в MonetDB СУБД. SciDB это более поздняя инициатива по созданию поддержки массивов баз данных. Как и в SciQL, массивы рассматриваются как эквивалент таблиц, а не как новый тип атрибута, как в rasdaman и PostGIS.

Для особого случая скудные данные, OLAP кубы данных хорошо известны; они хранят значения ячеек вместе с их местоположением - адекватный метод сжатия, несмотря на то, что несколько местоположений вообще несут достоверную информацию - и работают с ними с помощью SQL. Поскольку этот метод не масштабируется по плотности, стандартные базы данных сегодня не используются для плотных данных, таких как спутниковые изображения, где большинство ячеек несут значимую информацию; скорее проприетарные специальные реализации преобладают в управлении научными данными и подобных ситуациях. Следовательно, именно здесь СУБД Array могут внести особый вклад.

Как правило, СУБД Array - это новая технология. Хотя существуют оперативно развернутые системы, например Oracle GeoRaster, PostGIS 2.0 и Расдаман, есть еще много открытых исследовательских вопросов, включая дизайн и формализацию языка запросов, оптимизацию запросов, распараллеливание и распределенная обработка и проблемы масштабируемости в целом. Кроме того, научные сообщества по-прежнему неохотно используют технологию массивов баз данных и склонны отдавать предпочтение специализированной, проприетарной технологии.

Концепции

При добавлении массивов в базы данных необходимо пересмотреть все аспекты проектирования базы данных - от концептуального моделирования (например, подходящие операторы) до управления хранилищем (например, управления массивами, охватывающими несколько носителей) до обработки запросов (например, эффективных стратегий обработки).

Концептуальное моделирование

Формально массив А задается (полной или частичной) функцией А: Икс → V куда Икс, то домен это d-мерный целочисленный интервал для некоторых d> 0 и V, называется классифицировать, - некоторое (непустое) множество значений; в установленной записи это можно переписать как {(п,v) | п в Икс, v в V }. Каждый (п,v) в А обозначает элемент массива или клетка, и, следуя общепринятым обозначениям, пишем А[п] = v. Примеры для Икс включить {0..767} × {0..1023} (для XGA размер изображений), примеры для V включить {0..255} для 8-битных изображений в оттенках серого и {0..255} × {0..255} × {0..255} для стандартных RGB образы.

Следуя установленной практике баз данных, язык запросов к массивам должен быть декларативный и безопасен при оценке. Поскольку итерация по массиву лежит в основе обработки массива, декларативность в значительной степени сосредоточена на этом аспекте. Таким образом, требование состоит в том, что концептуально все ячейки должны проверяться одновременно - другими словами, запрос не требует какой-либо явной итерационной последовательности по ячейкам массива во время оценки. Безопасность оценки достигается, когда каждый запрос завершается после конечного числа шагов (за конечное время); опять же, избегая общих циклов и рекурсии, можно добиться этого. В то же время отказ от явных последовательностей циклов открывает множество возможностей оптимизации.

Запрос массива

В качестве примера для операторов запроса массива Расдаман могут служить алгебра и язык запросов, которые устанавливают язык выражений для минимального набора примитивов массива. Мы начнем с общих основных операторов, а затем представим общие частные случаи и сокращения.

В Marray оператор создает массив на некотором заданном экстенте домена и инициализирует его ячейки:

Marray индекс-классифицировать-Технические характеристикизначения клетка-ценить-выражение

куда индекс-диапазон-спецификация определяет область результатов и связывает с ней переменную итерации без указания последовательности итераций. В выражение-значение-ячейки оценивается в каждом месте домена.

Пример: «Вырез массива A, заданный угловыми точками (10,20) и (40,50)».

Marray п в [10:20,40:50]значения А[п]

Этот частный случай, чистое подмножество, может быть сокращено как

А[10:20,40:50]

Это подмножество сохраняет размерность массива; чтобы уменьшить размер за счет извлечения фрагментов, в измерении срезов указывается одно значение точки среза.

Пример: «Срез временного ряда x / y / t в позиции t = 100, извлекающий все доступные данные в x и y».

А[*:*,*:*,100]

Оператор подстановочного знака * указывает, что должна использоваться текущая граница массива; обратите внимание, что массивы, в которых границы измерений остаются открытыми во время определения, могут изменять размер в этих измерениях в течение срока службы массива.

В приведенных выше примерах просто скопированы исходные значения; вместо этого этими значениями можно управлять.

Пример: «Массив A с применением log () к каждому значению ячейки».

Marray п в домен(А)значения бревно( А[п] )

Это может быть сокращено как:

бревно( А )

Через принцип, называемый индуцированные операции,[7] язык запросов также предлагает все операции, предлагаемые типом ячейки, на уровне массива. Следовательно, с числовыми значениями доступны все обычные унарные и двоичные арифметические, экспоненциальные и тригонометрические операции, а также стандартный набор логических операторов.

В конденсировать Оператор агрегирует значения ячеек в один скалярный результат, аналогично агрегатам SQL. Его приложение имеет общий вид:

конденсировать конденсировать-opнад индекс-классифицировать-Технические характеристикис помощью клетка-ценить-выражение

Как и с Marray перед индекс-диапазон-спецификация задает домен, по которому будет выполняться итерация, и связывает с ним переменную итерации - опять же, без указания последовательности итераций. Так же, выражение-значение-ячейки оценивается в каждом местоположении домена. В конденсирующий Предложение определяет операцию агрегирования, используемую для объединения выражений значений ячеек в одно значение.

Пример: «Сумма всех значений в A.»

конденсировать +над п в сдом(А)с помощью А[п]

Сокращение для этой операции:

add_cells( А )

Таким же образом и по аналогии с агрегатами SQL предоставляется ряд дополнительных сокращений, включая подсчет, среднее, минимальное, максимальное и логические кванторы.

Следующий пример демонстрирует комбинацию Marray и конденсировать операторы путем построения гистограммы.

Пример: "Гистограмма 8-битного изображения A в оттенках серого"

Marray ведро в [0:255]значения count_cells( А = ведро )

Вызванное сравнение, A = ведро, устанавливает логический массив того же размера, что и А. Оператор агрегации подсчитывает вхождения истинный для каждого значения ведро, который впоследствии помещается в соответствующую ячейку массива одномерной гистограммы.

Такие языки позволяют формулировать статистические операции и операции с изображениями, которые могут быть выражены аналитически без использования циклов. Было доказано[8] что выразительная сила таких языков массивов в принципе эквивалентна реляционным языкам запросов с ранжированием.

Хранение массива

Хранилище массивов должно вмещать массивы разных размеров и, как правило, больших размеров. Основная задача - поддерживать пространственную близость на диске, чтобы уменьшить количество обращений к диску во время поднабора. Обратите внимание, что эмуляция многомерных массивов в виде вложенных списков (или одномерных массивов) сама по себе этого не обеспечивает и, следовательно, в целом не приводит к масштабируемым архитектурам.

Обычно массивы делятся на подмассивы, которые образуют единицу доступа. Обычное разбиение, при котором все разделы имеют одинаковый размер (за исключением, возможно, границ), называется дробление.[9] Обобщение, которое снимает ограничение на разделы одинакового размера, поддерживая любой вид разделения, - черепица.[10] Разделение массивов может значительно улучшить доступ к подмножествам массивов: подстраивая мозаику в соответствии с шаблоном доступа, сервер в идеале может получить все необходимые данные только с одного доступа к диску.

Сжатие плиток иногда может существенно уменьшить необходимый объем хранилища. Также для передачи результатов полезно сжатие, поскольку для больших объемов рассматриваемых данных пропускная способность сети часто является ограничивающим фактором.

Обработка запросов

Структура хранения на основе плитки предлагает стратегию обработки плитки за плиткой (в Расдаман называется потоковое воспроизведение плитки). Большой класс практически релевантных запросов можно оценить, загружая плитку за плиткой, что позволяет серверам обрабатывать массивы на порядки, превышающие их основную память.

Преобразование запроса в более эффективную, но эквивалентную версию при оптимизации запроса массива

Из-за огромных размеров массивов в научных / технических приложениях в сочетании с часто сложными запросами оптимизация играет центральную роль в повышении эффективности запросов к массивам. Может применяться как аппаратное, так и программное распараллеливание. Примером эвристической оптимизации является правило «максимальное значение массива, полученного в результате добавления двух входных изображений по ячейкам, эквивалентно сложению максимальных значений каждого входного массива». При замене левого варианта на правое выражение затраты сокращаются с трех (дорогостоящих) обходов массива до двух обходов массива плюс одна (дешевая) скалярная операция (см. Рисунок, на котором используется стандарт запросов SQL / MDA).

Домены приложений

Во многих - если не в большинстве - случаев, когда какое-либо явление дискретизируется или моделируется, результатом является набор растрированных данных, который можно удобно хранить, извлекать и пересылать в виде массива. Обычно данные массива украшены метаданными, которые их дополнительно описывают; например, изображения с географической привязкой будут нести его географическое положение и систему координат, в которой оно выражено.

Ниже приведены репрезентативные области, в которых обрабатываются данные крупномасштабных многомерных массивов:

  • Науки о Земле: геодезия / картографирование, дистанционное зондирование, геология, океанография, гидрология, атмосферные науки, криосферные науки
  • Космические науки: Планетарные науки, астрофизика (наблюдения с помощью оптических и радиотелескопов, космологическое моделирование)
  • Науки о жизни: данные о генах, конфокальная микроскопия, компьютерная томография
  • Социальные науки: кубы статистических данных
  • Бизнес: OLAP, хранилища данных

Это всего лишь примеры; Как правило, массивы часто представляют данные датчиков, моделирования, изображений и статистики. Все больше и больше пространственных и временных измерений сочетаются с Абстрактные оси, такие как продажи и продукты; одним из примеров, где такие абстрактные оси явно предусмотрены, является [Open_Geospatial_Consortium | Открытый геопространственный консорциум] (OGC) модель покрытия.

Стандартизация

Многие сообщества установили форматы обмена данными, такие как HDF, NetCDF, и TIFF. Стандартом де-факто в сообществах наук о Земле является OPeNDAP, архитектура и протокол передачи данных. Хотя это не спецификация базы данных, она предлагает важные компоненты, характеризующие систему базы данных, такие как концептуальная модель и реализации клиент / сервер.

Декларативный язык гео-растровых запросов, Служба обработки веб-материалов (WCPS) был стандартизирован Открытый геопространственный консорциум (OGC).

В июне 2014 года ISO / IEC JTC1 SC32 WG3, который поддерживает стандарт базы данных SQL, решил добавить поддержку многомерных массивов в SQL в качестве нового типа столбца,[11] на основе начальной поддержки массива, доступной с Версия SQL 2003 г.. Новый стандарт, принятый осенью 2018 года, носит название ISO 9075 SQL, часть 15: MDA (многомерные массивы).

Список массивных СУБД

Смотрите также

Рекомендации

  1. ^ Чок, М., Карденас, А., Клингер, А.: Структура базы данных и возможности управления системой управления базой данных изображений (PICDMS). IEEE ToPAMI, 6 (4): 484–492, 1984 г.
  2. ^ Бауманн, П .: Об управлении многомерными дискретными данными. VLDB Journal 4 (3) 1994, специальный выпуск по системам пространственных баз данных, стр. 401–444
  3. ^ Бауманн, П .: Алгебра массивов базы данных для пространственно-временных данных и не только. Proc. НГИЦ’99, LNCS 1649, Springer 1999, стр.76-93
  4. ^ Марат, А., Салем, К .: Язык для управления массивами. Proc. VLDB’97, Афины, Греция, август 1997 г., стр. 46–55.
  5. ^ Либкин, Л., Махлин, Р., Вонг, Л .: Язык запросов для многомерных массивов: методы проектирования, реализации и оптимизации. Proc. ACM SIGMOD’96, Монреаль, Канада, стр. 228–239.
  6. ^ Меннис, Дж., Вигер, Р., Томлин, К.Д .: Функции алгебры кубических карт для пространственно-временного анализа. Картография и географическая информатика 32 (1) 2005, стр. 17–32
  7. ^ Риттер, Г. и Уилсон, Дж. И Дэвидсон, Дж .: Алгебра изображений: обзор. Компьютерное зрение, графика и обработка изображений, 49 (1) 1994, 297-336
  8. ^ Махлин, Р.: Запросы многомерного массива на основе индекса: безопасность и эквивалентность. Proc. ACM PODS'07, Пекин, Китай, июнь 2007 г., стр. 175–184.
  9. ^ Сараваги, С., Стоунбрейкер, М .: Эффективная организация больших многомерных массивов. Proc. ICDE'94, Хьюстон, США, 1994, стр. 328-336.
  10. ^ Фуртадо П., Бауманн П. Хранение многомерных массивов на основе произвольной мозаики. Proc. ICDE'99, 23–26 марта 1999 г., Сидней, Австралия, стр. 328–336.
  11. ^ Чиргвин, Р .: SQL сопротивляется репутации больших данных NoSQL с помощью спецификации SQL / MDA, The Register, 26 июн 2014 г.