Array DBMS

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

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

Обзор

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

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

Такие СУБД предлагают языки запросов, дающие декларативный доступ к таким массивам, позволяя создавать, изменять, искать и удалять их. Как, например, в SQL, выражения произвольной сложности могут быть построены поверх множества операций с массивом. Из-за расширений, сделанных в модели данных и запросов, Array DBMSs иногда подпадают под категорию NoSQL категории (не только SQL). Оптимизации запросов и распараллеливание важны для достижения масштабируемости; на самом деле, многие операторы массив хорошо приспособлены к параллельной оценке, при обработке каждого фрагмента на отдельных узлов или ядер.

К важным областям приложений Array DBMS относятся Земля, Космос, Жизнь, и Общественные науки, а также связанные с ними коммерческие приложения (такие как, разведка и добыча углеводородов в промышленности и OLAP и в бизнесе). Наблюдение разнообразия может наблюдаться, например, в геоданных, где временные ряды 1-D экологических датчиков, 2-D спутниковые изображения, 3-D x / y / t временные ряды изображений и данные геофизики x / y / z, а также 4-D x / y / z / t данные о климате и океане.

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

Реляционная модель данных, преобладающая сегодня, не поддерживает прямую поддержку парадигмы массива в той же степени, что и множества с кортежами. ISO SQL перечисляет тип атрибута с признаками массива, но только одномерный, практически без оперативной поддержки и не используемый для Array DBMS. Другой вариант-прибегнуть к BLOBs ("большим двоичным объектам"), которые эквивалентны файлам: байтовые строки (концептуально) неограниченной длины, но опять же без каких-либо функций языка запросов, таких как многомерное подмножество.

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

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

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

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

Как правило, Array DBMS представляет собой новую технологию. В то время как существуют оперативно развернутые системы, такие как 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 алгебра и язык запросов, которые устанавливают язык выражения над минимальным набором примитивов массива. Мы начинаем с основных операторов ядра, а затем представляем общие частные случаи и сокращения

The marray operator creates an array over some given domain extent and initializes its cells:

marray index-range-specification
values cell-value-expression

Где index-range-specification определяет область результата и связывает с ней переменную итерации без указания последовательности итераций. А "cell-value-expression" оценивается в каждом местоположении домена.

Например: “Вырез массива А, заданный угловыми точками (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, с логом (), применяемым к каждому значению ячейки.”

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-specification указывает домен, который должен быть переименован, и привязывает к нему переменную итерации - опять же, без указания последовательности итераций. Также, cell-value-expression оценивается в каждом домене. Condense-op задает агрегирующую операцию, используемую для объединения выражений значений ячейки в одно значение.

Например: "Сумма по всем значениям A."

condense +
over p in sdom(a)
using A[p]

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

add_cells( A )

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

Следующий пример демонстрирует комбинацию операторов ""marray"" и ""condense"" путем получения гистограммы. Например: "Гистограмма над 8-битной черно-белым изображением A."

marray bucket in [0:255]
values count_cells( A = bucket )

Наведенное сравнение "A = bucket" устанавливает логический массив в той же степени, что и "A". Оператор агрегации подсчитывает "значения true" для каждого значения "bucket", которое затем помещается в ячейку соответствующего массива 1-D гистограммы.

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

Массив хранения данных

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

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

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

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

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

Образец правила для эвристического выбора оптимизации запросов

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

Области приложений

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

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

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

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

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

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

Язык декларативного георастрового запроса, Web Coverage Processing Service (WCPS), был стандартизован Open Geospatial Consortium (OGC).


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

Список Массивов СУБД

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

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

  1. "Database structure and manipulation capabilities of a picture database management system". (PICDMS). Chock, M., Cardenas, A., Klinger, A. 1984. 
  2. "On the Management of Multidimensional Discrete Data". Special Issue on Spatial Database Systems. Baumann, P. 1994. 
  3. "A Database Array Algebra for Spatio-Temporal Data and Beyond". Proc. NGITS’99. Baumann, P. Springer 1999.  Check date values in: |date= (help)
  4. "A language for manipulating arrays.". VLDB’97. Marathe, A., Salem, K. August 1997. 
  5. "A query language for multidimensional arrays: design, implementation and optimization techniques.". Proc. ACM SIGMOD’96. Libkin, L., Machlin, R., Wong, L. 1996. 
  6. "Cubic Map Algebra Functions for Spatio-Temporal Analysis.". Cartography and Geographic Information Science. Mennis, J., Viger, R., Tomlin, C.D. 2005. 
  7. "Image Algebra: An Overview. Computer Vision, Graphics, and Image Processing". Ritter, G., Wilson, J., Davidson, J. 1994. 
  8. "Index-Based Multidimensional Array Queries: Safety and Equivalence.". Proc. ACM PODS'07. Machlin, R. June 2007. 
  9. "Efficient Organization of Large Multidimensional Arrays.". Proc. ICDE'94. Sarawagi, S., Stonebraker, M. 1994. 
  10. "Storage of Multidimensional Arrays based on Arbitrary Tiling.". Proc. ICDE'99. Furtado, P., Baumann, P. March 23–26, 1999. 
  11. "SQL fights back against NoSQL's big data cred with SQL/MDA spec". The Register. Chirgwin, R. 26 Jun 2014. 

Шаблон:Database models Шаблон:Databases