Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Обзор [ править ]

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

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

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

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

История и статус [ править ]

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

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

Бауман опубликовал первый декларативный язык запросов, пригодный для нескольких измерений и с семантикой на основе алгебры , вместе с масштабируемой архитектурой. [2] [3] Другой язык массивов баз данных, ограниченный до 2-мерности, был представлен Маратом и Салемом. [4] Основная теоретическая работа выполнена Либкиным и др .; [5] в своей модели, называемой NCRA, они расширяют вложенное реляционное исчисление многомерными массивами; Среди результатов - важный вклад в анализ сложности запросов к массивам. Алгебра карт, подходящая для двумерных и трехмерных пространственных растровых данных, была опубликована 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 ) | 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 .

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

Запрос массива [ править ]

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

Оператор marray создает массив по некоторой заданной области домена и инициализирует его ячейки:

 индекс Маррея - диапазон - значения спецификации ячейка - значение - выражение

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

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

marray  p  в  [ 10 : 20 , 40 : 50 ] значения  A [ p ]

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

A [ 10 : 20 , 40 : 50 ]

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

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

A [ * : * , * : * , 100 ]

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

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

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

marray  p  в  домене ( A ) значения  log (  A [ p ]  )

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

журнал (  A  )

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

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

condense  condense - переход по  индексу - диапазон - спецификация с использованием  ячейки - значения - выражения

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

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

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

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

add_cells (  А  )

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

В следующем примере демонстрируется комбинация операторов marray и condense путем построения гистограммы.

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

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

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

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

Хранилище массива [ править ]

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

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

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

Обработка запросов [ править ]

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

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

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

Домены приложений [ править ]

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

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

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

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

Стандартизация [ править ]

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

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

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

Список массивов СУБД [ править ]

  • Oracle GeoRaster
  • MonetDB / SciQL
  • PostGIS
  • Расдаман
  • SciDB

См. Также [ править ]

  • Обработка данных с интенсивным использованием данных

Ссылки [ править ]

  1. ^ Чок, М., Карденас, А., Клингер, А.: Структура базы данных и возможности управления системой управления базой данных изображений (PICDMS). IEEE ToPAMI, 6 (4): 484–492, 1984 г.
  2. ^ Бауманн, П .: Об управлении многомерными дискретными данными . VLDB Journal 4 (3) 1994, специальный выпуск по системам пространственных баз данных, стр. 401–444
  3. ^ Бауманн, П .: Алгебра массивов баз данных для пространственно-временных данных и за их пределами . Proc. NGITS'99, LNCS 1649, Springer 1999, стр.76-93
  4. ^ Марат, А., Салем, К .: Язык для управления массивами. Proc. VLDB'97, Афины, Греция, август 1997 г., стр. 46–55.
  5. ^ Либкин, Л., Махлин, Р., Вонг, Л .: Язык запросов для многомерных массивов: методы проектирования, реализации и оптимизации. Proc. ACM SIGMOD'96, Монреаль, Канада, стр. 228–239.
  6. ^ Меннис, Дж., Вигер, Р., Томлин, CD: Функции алгебры кубических карт для пространственно-временного анализа. Картография и географическая информатика 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 г.