Унификация модели данных, основанной на многомерных массивах, при интеграции неоднородных информационных ресурсов © С. А. Ступников ИПИ РАН, Москва ssa@ipi.ac.ru облаках. Одним из важных видов таких моделей Аннотация являются модели данных, основанные на В работе рассматривается отображение многомерных массивах (array-based data models или array data models) и называемые далее ММ- одной из моделей данных, основанной на моделями. Родственными данным моделям являются многомерных массивах – модели СУБД SciDB в каноническую модель систем так называемые «кубы данных», используемые в виртуальной или материализованной OLAP технологии [18, 16]. Исследования ММ- моделей начались достаточно давно [14, 5] и интеграции баз данных. Для продолжают развиваться. В данной статье определенности в статье рассматривается отображение в объектную модель данных – рассматривается конкретная модель, а именно – модель, используемая в СУБД SciDB [15]. язык СИНТЕЗ, использующийся в качестве канонической модели данных в технологии История SciDB начинается с 2007 года, когда на предметных посредников. симпозиуме по Экстремально большим базам Проиллюстрирован метод доказательства данных (XLDB) представителями науки и сохранения информации и семантики промышленности был сделан вывод, что операций при отображении моделей данных существующие СУБД не в состоянии с использованием формального языка манипулировать объемами данных, которые спецификаций. Целью работы является появятся в ближайшем будущем. Одним из создание обоснованной теоретической базы примеров поставщиков таких данных является для интеграции ресурсов, основанных на строящийся телескоп LSST (Large Synoptic Survey многомерных массивах. Telescope) [13]. Был также сделан вывод о Работа выполнена при поддержке РФФИ необходимости разработки СУБД нового поколения, (гранты 10-07-00342-а, 11-07-00402-а) и которая должна удовлетворять, в частности, Президиума РАН (программа 16П, проект 4.2). следующим требованиям [6]:  модель данных основывается на 1 Введение многомерных массивах, а не на кортежах; Развитие науки и промышленности, широкое  модель хранения базируется на версионности, распространение информационных технологий а не на обновлении значений; ведет к накоплению огромных объемов данных как  масштабируемость до сотен петабайт и в науке, так и в бизнесе. Данные могут быть как высокая отказоустойчивость; наблюдательными, экспериментальными, так и  СУБД является свободно распространяемым полученными в ходе компьютерного программным обеспечением. моделирования. Данные таких масштабов (часто Некоторое время спустя был запущен измеряемых уже в петабайтах) называются международный проект под руководством Майкла «большими данными» (Big Data) [7], плохо Стоунбрейкера, целью которого являлось создание поддаются обработке и анализу в рамках хорошо новой системы управления базами данных, известных технологий баз данных, опирающихся в получившей название SciDB. В настоящее время основном на реляционную модель данных. свободно распространяется очередная версия Именно поэтому развиваются различные модели системы для ОС Ubuntu и RedHat. данных, нацеленные на параллельную обработку и Целью данной статьи является исследование анализ данных в распределенных средах – гридах и вопроса об унификации модели данных системы SciDB (будем называть ее в дальнейшем ADM – Труды 14-й Всероссийской научной конференции Array Data Model [17]) для виртуальной или «Электронные библиотеки: перспективные методы и материализованной интеграции ресурсов при технологии, электронные коллекции» — RCDL-2012, создании федеративных баз данных или хранилищ Переславль-Залесский, Россия, 15-18 октября 2012 г. данных. 42 При материализованной интеграции Нужно отметить, что ADM подвергается предполагается создание хранилища данных некоторой критике со стороны исследователей, (warehouse), в которое загружаются ресурсы, продолжающих развитие моделей, основанных на подлежащие интеграции. В процессе загрузке многомерных массивах. Так, авторы языка SciQL происходит преобразование данных из схемы [12] отмечают, что язык ADM является смесью SQL ресурса в общую схему хранилища. и деревьев алгебраических операций. По их Виртуальная же интеграция рассматривается в мнению, язык для СУБД, основанных на статье применительно к предметным посредникам многомерных массивах, должен быть интегрирован [9]. Предметные посредники представляют собой с синтаксисом и семантикой SQL:2003. Несмотря на специальный вид программного обеспечения, эти замечания, модель ADM представляет образующий промежуточный слой между несомненный практический интерес для интеграции пользователем (приложением) и неоднородными баз данных. SciDB используется как в научных информационными ресурсами. При этом данные из проектах, связанных с LSST (предполагается после ресурсов не материализуются в посреднике. запуска телескопа) и физикой высоких энергий, так Федеративная схема посредника, описывающая и в коммерческих, связанных с генетикой, некоторую предметную область, создается страхованием, финансами. Сравнительное независимо от существующих ресурсов. Ресурсы, тестирование SciDB с СУБД Postgres и релевантные предметной области, затем статистическим ПО R показало преимущества регистрируются в посреднике – их схемы SciDB по производительности и масштабируемости. связываются специальными семантическими Статья организована следующим образом. В отображениями с федеративной схемой. разделе 2 рассмотрены и проиллюстрированы Исполнительная среда посредников предоставляет основные принципы отображения модели данных возможность пользователям (приложениям) ADM в язык СИНТЕЗ. В разделе 3 рассмотрен задавать запросы (программы) к посреднику в метод доказательства сохранения информации и терминах федеративной схемы. Эти запросы семантики операций при отображении моделей с переписываются в частичные запросы над использованием формального языка спецификаций информационными ресурсами, затем исполняются AMN [1]. Метод проиллюстрирован на структурах на ресурсах. Результаты частичных запросов данных и операциях ЯМД моделей SciDB и объединяются и выдаются пользователю также в СИНТЕЗ. терминах федеративной схемы. Важным понятием технологии систем 2 Отображение модели ADM в язык интеграции баз данных является каноническая СИНТЕЗ модель, служащая общим языком, унифицирующим разнообразные модели ресурсов. SciDB поддерживает два языка для работы с массивами: AQL (Array Query Language) и AFL Унификацией некоторой исходной модели (Array Functional Language). AQL является SQL- данных называется ее отображение в каноническую подобным декларативным языком, включающим как модель, сохраняющее информацию и семантику операции ЯОД, так и операции ЯМД. AFL операций языка манипулирования данными (ЯМД) представляет собой функциональный язык [20]. Унификация должна быть доказуемо манипулирования массивами, операции которого правильной. Очевидно, что унификация моделей можно объединять в композиции. Допускается ресурсов является необходимым предусловием для использование операций AFL в запросах AQL. регистрации ресурсов в посреднике – семантические отображения, связывающие федеративную схему и Операции языков и отображение будут схемы ресурсов, нужно проводить в единой иллюстрироваться на адаптированных примерах из (канонической модели) [10]. сценария применения SciDB в области оптической астрономии [2], а также на простых примерах из В качестве канонической модели в данной документации SciDB [17]. работе рассматривается язык СИНТЕЗ [11] - комбинированная слабоструктурированная и объектная модель данных, нацеленная на разработку 2.1 Отображение языка определения данных предметных посредников для решения задач в средах неоднородных ресурсов. Разработан Отображение ЯОД в данном разделе прототип программных средств для поддержки описывается независимо от вида интеграции – среды предметных посредников с языком СИНТЕЗ в виртуальной или материализованной. роли канонической модели [19]. Основной единицей определения данных в С точки зрения предметных посредников СУБД, модели ADM является массив, имеющий конечное основанные на многомерных массивах, количество измерений d1, d2, ..., dn [17]. Длиной представляют собой новый вид ресурсов, измерения называется количество упорядоченных подлежащих интеграции в посредниках вместе с значений в этом измерении. По умолчанию типом привычными ресурсами – реляционными и измерения являются 64-битные целые числа. объектными СУБД, веб-сервисами и т.д. Поддерживаются также нецелочисленные 43 измерения, например строки или числа с плавающей различающих измерения и атрибуты, составляющие точкой. Каждая комбинация значений измерений ячейку: соответствует ячейке массива, которая может  по набору значений измерений однозначно содержать конечное количество значений, определяется набор значений атрибутов называемых атрибутами. Типом атрибута может ячейки (уникальность измерений); быть один из встроенных типов ADM [17].  ячейка массива всегда определяется полным Основная операция ЯОД ADM – создание набором значений измерений массива - выглядит следующим образом: (определенность измерений). CREATE ARRAY source Заметим также, что отсутствие в коллекции < ampExposureId: int64 NULL, объекта с некоторым набором значений измерений filterId: int8, означает пустую ячейку в массиве. apMag: double > [ ra(double), de(double), objectId=0:*]; Для нецелочисленных измерений ra и de кроме Создается масcив оптических источников source, атрибутов в языке СИНТЕЗ определяются функции измерениями которого являются координаты ra и de ra2long, de2long, преобразующие нецелочисленные типа double и целочисленный идентификатор значения в целочисленные. Необходимость объекта. Для целочисленного измерения указаны его привнесения этих функций вызвана следующим. нижняя (0) и верхняя (* - обозначающая При попытке описать операции, характерные для бесконечность) границы. Ячейка массива состоит из ММ-моделей, в объектной модели (в частности, в трех атрибутов: ampExposureId, filterId, apMag. языке СИНТЕЗ), выясняется необходимость Указано, что атрибут ampExposureId может применения существенно различных механизмов принимать неопределенное значение NULL. В работы с целочисленными и нецелочисленными данном примере приведены только некоторые из измерениями. Это вызвано различием типов реально используемых атрибутов и измерений. измерений, возможной неравномерностью шага измерения и т.д. Для того, чтобы обеспечить В языке СИНТЕЗ создание массива возможность единообразного описания операций представляется определением одноименного класса: над целочисленными и нецелочисленными { source; in: class; измерениями и необходимы функции, приводящие instance_type:{ нецелочисленные измерения к целочисленным. double ra; ra2long: {in: function; params: {-ret/long}; }; Ограничения, связанные с нижними и верхними double de; границами целочисленных измерений, de2long: {in: function; params: {-ret/long}; }; представляются в языке СИНТЕЗ во-первых, long objectId; metaslot lower: 0; higher: inf; end метаслотом соответствующего атрибута (например, objectIdBounds: {in: invariant; objectId). В метаслоте хранится метаинформация, {{ all s (source(s) -> s.objectId >= 0) }} связанная с атрибутом, как с отдельной сущностью }; языка. В данном случае метаслот включает два long ampExposureId; слота lower и higher, отвечающих, соответственно, short filterId; double apMag; верхней и нижней границе измерения. Во-вторых, key: { unique; { ra, de, objectId } }; создается инвариант (например, objectIdBounds) definiteness: {obligatory; предикативная спецификация которого { ra, de, objectId, filterId, apMag } }; устанавливает ограничения на значения измерения }; для каждого из объектов класса, отвечающего } массиву. Спецификация инварианта имеет вид Как измерения, так и атрибуты, составляющие формулы первого порядка, где all – квантор ячейку, представляются в языке СИНТЕЗ существования, -> – импликация. атрибутами типа экземпляров (instance_type) класса. Необходимо отметить, что массив Между встроенными типами ADM (int8, int64, представляется в объектной модели множеством double и т.д.) и встроенными типами языка СИНТЕЗ объектов класса (фактически, кортежей значений (short, long, double) устанавливается взаимно- атрибутов). При этом наблюдается некоторое однозначное соответствие. Совокупность атрибутов, противоречие со стремлением создателей ММ- соответствующих измерениям, объявляется моделей отойти от моделей, основанных на уникальной (инвариант key, выражаемый кортежах. Однако, в контексте интеграции ресурсов встроенным утверждением unique). Объявляется ММ-модели - лишь один класс из большого также, что атрибуты, соответствующие измерениям множества разнообразных классов моделей данных. и не-NULL атрибутам ADM, должны быть Представление специфических ММ-моделей в определены у всех экземпляров класса (инвариант объектной модели является методологически и definiteness, выражаемый встроенным утверждением технически гораздо более простым и естественным, obligatory). нежели использование многомерных массивов в Таким образом обеспечивается сохранение качестве канонической модели. отличительных свойств многомерных массивов («кубов данных»), существенным образом 44 Изложенные принципы отображения ЯОД могут программы на языке канонической модели быть обобщены на случай, когда канонической исполняются непосредственно на данных. является объектная или объектно-реляционная Отображение ЯМД нужно лишь для того, чтобы модель, отличная от языка СИНТЕЗ. Также, убедиться, что отображение моделей сохраняет непринципиальным является выбор модели данных, информацию и семантику операций. Семантически основанной на многомерных массивах. В общем правильное отображение служит базой для процесса виде, принципы отображения ЯОД выглядят Извлечения-Преобразования-Загрузки (ETL), следующим образом: формирующего из данных ресурса данные  массив отображается в коллекцию хранилища: ETL-процесс может быть выражен типизированных объектов (класс) объектной только в терминах канонической модели. модели;  измерения и атрибуты, составляющие ячейку Язык запросов (программ) модели СИНТЕЗ массива, отображаются в атрибуты типа представляет собой Datalog-подобный язык в экземпляров класса; объектной среде. Программа представляет собой  между встроенными типами модели, набор конъюнктивных запросов (правил) вида основанной на многомерных массивах, и q(x/T) :- C1(x1/T1), … , Cn(xn/Tn), встроенными типами объектной модели F1(X1, Y1), … Fm(Xm, Ym), B. устанавливается взаимно-однозначное Тело запроса представляет собой конъюнкцию соответствие; предикатов-коллекций, функциональных  совокупность атрибутов, соответствующих предикатов и ограничения. Здесь Сi - имена измерениям, объявляется уникальной (при коллекций (классов), Fj – имена функций, xi – имена помощи механизма ключей, утверждений или переменных, значения которых пробегают по инвариантов); классам, Ti – типы переменных, Xj и Yj – входные и  атрибуты, соответствующие измерениям и не- выходные параметры функций, B – ограничение, NULL атрибутам ячейки массива, налагаемое на xi, Xj, Yj. Предикаты, находящиеся в объявляются определенными (при помощи голове правил, могут быть использованы в телах утверждений или инвариантов); других правил в качестве предикатов-коллекций.  для нецелочисленных измерений в типе В дальнейшем будет часто использоваться экземпляров дополнительно определяются запись предиката-коллекции вида source([ra, de]). методы, преобразующие нецелочисленные Неформально это означает, что нас не интересуют значения в целочисленные; объекты класса source целиком, а лишь их атрибуты  ограничения, связанные с нижними и ra, de. Формально запись означает сокращение от верхними границами целочисленных source(_/source.inst[ra, de]). Здесь знак _ обозначает измерений, отображаются при помощи анонимную переменную, source.inst – анонимный инвариантов или встроенных утверждений о тип экземпляров (instance) класса source, ra, de – кардинальности соответствующих атрибутов. необходимые атрибуты типа экземпляров класса. В случае использования инвариантов при отображении, границы измерений Будет также использоваться запись source([i, j, представляются также метаданными val1/val]), означающая переименование атрибута val атрибута. в val1. 2.2 Отображение языка манипулирования При отображении ЯМД будут сначала данными рассмотрены основные конструкции языка При интеграции баз данных для установления программ СИНТЕЗ, соответствующие конструкциям семантических соотношений между схемами языка AQL. Затем будут рассмотрены конструкции ресурсов и федеративной схемой необходимо СИНТЕЗ, соответствующие конструкциям языка отображение ЯОД исходной модели в AFL. каноническую. ЯМД канонической модели, Начнем рассмотрение с конструкций языка напротив, необходимо отображать в ЯМД исходной СИНТЕЗ, соответствующих конструкциям языка модели. Это связано с тем, что запросы к AQL, связанных с извлечением данных. посреднику в канонической модели необходимо отображать в запросы к ресурсам. Предикаты-классы, условия, подзапросы. Отметим отличие виртуальной и Рассмотрим программу, извлекающую координаты материализованной интеграции. При виртуальной (ra, de) и апертурную звездную величину (apMag) интеграции отображение ЯМД обеспечивает астрономических источников из класса source с возможность трансляции программ на языке условием на фильтр (filterId) и апертурную посредника в запросы на языке ресурсов. звездную величину, причем запрос q использует В случае материализованной интеграции данные результаты запроса r. извлекаются из ресурса и представляются в q([ra, de, apMag]) :- r([ra, de, apMag]), filterId= #filterId. хранилище в канонической модели. При этом r([ra, de, apMag]) :- 45 source([ra, de, apMag]), apMag >= #apMag. Здесь #filterId и #apMag – некоторые константы Группирование. Рассмотрим запрос, соответствующих типов. возвращающий среднее значение звездной Такая программа представляется в AQL величины uMag, вычисленное на группе по следующим запросом: идентификатору объекта filterId: SELECT apMag FROM q([objectId, avgMag]) :- ( SELECT apMag FROM source group_by({objectId}, q2(obj/[ra,de,filterId, uMag])), WHERE apMag >= #apMag ) avgMag = average(obj.uMag). WHERE filterId = #filterId; Здесь коллекция q2, на которой производится Простые условия отображаются в AQL без группирование по атрибуту objectId – результат изменений, рекурсивные запросы представляются соединения классов source и objectSummary, вложенными запросами. Заметим, что координаты рассмотренный выше. ra, de не указываются в секции SELECT – они Очевидно, в AQL запрос представляется при являются измерениями и извлекаются по помощи конструкции GROUP BY: умолчанию. SELECT avg(uMag) AS avgMag FROM q2 GROUP BY objectId; Функциональные предикаты. Рассмотрим запрос, конструирующий из двух звездных величин uMag, Агрегация в бегущем окне (Window Aggregation). rMag в разных фильтрах цветовую разность: Такой вид агрегации является специфическим для q([objectId, ugColor]) :- моделей, основанных на многомерных массивах. objectSummary([objectId, uMag, rMag]), Окно определяется своим размером в каждом diff(uMag, rMag, ugColor). измерении массива. Центроид окна располагается в Запрос включает функциональный предикат, каждом из элементов массива и для каждого такого семантика которого определяется функцией diff: окна вычисляется некоторая агрегирующая { diff; in: function; функция. Например, для вычисления среднего params: {+min/float, +sub/float, -res/float}; значения в бегущем окне размера 3х3 в квадратной {{ res = min - sub }} матрице 4х4, определяемой в AQL следующим } образом: В двойных фигурных скобках заключена CREATE ARRAY source [i = 0:3, j = 0:3]; предикативная спецификация функции, необходим запрос связывающая значения входных и выходных q([i, j, avgVal]) :- source(x/[i, j]), параметров в формуле типизированного исчисления windowAggr(i, j, avgVal). первого порядка. где семантика предиката windowAggr определяется Для простоты изложения рассматривается функцией функция, возвращающая разность параметров. { windowAggr; in: function; В AQL запрос представляется следующим params: {+i0/long, +j0/long, -res/double}; образом: {{ source(x/[i, j, val]) & i >= i0 - 1 & i <= i0 + 1 & SELECT uMag – rMag AS ugColor j >= j0 - 1 & j <= j0 + 1 & res = average(x.val) }} FROM objectSummary; } где массив objectSummary имеет вид вычисляющей среднее значение в окне с заданным CREATE ARRAY objectSummary центроидом в классе source. < uMag: float NULL, gMag: float NULL > AQL предлагает для агрегации в бегущем окне [ objectId=0:* ]; специальную конструкцию WINDOW: Таким образом, если результат функции SELECT avg(val) AS avgVal описывается выражением, составленным из FROM source WINDOW 3, 3; операций над простыми встроенными типами, то в AQL подобное выражение может быть в явном виде Рассмотрим конструкции языка СИНТЕЗ, вынесено в оператор SELECT. соответствующие конструкциям языка AQL, и связанные с изменением данных. Соединение классов. Соединение по определенным атрибутам (например, objectId) Обновление. Рассмотрим запрос, изменяющий q2([ra, de, filterId, uMag]) :- значения в квадратной матрице (см. предыдущий source([ra, de, objectId, fliterId]), пример) на значения с обратным знаком в том objectSummary([objectId, uMag]) случае, если модуль значения больше 5. представляется в AQL конструкцией JOIN-ON: source(x/[i, j, val]) :- SELECT filterId, uMag INTO q2 source(x/[i, j, val1/val]), abs(val) > 5, val = -val1. FROM source В AQL данный запрос представляется JOIN objectSummary следующим образом: ON Source.objectId = ObjectSummary.objectId; 46 UPDATE source SET val = -val WHERE abs(val) > 5; Расширение элементов массива в подмассивы. Каждый элемент массива расширяется в подмассив Удаление. Рассмотрим программу, удаляющую определенного размера. Значения всех ячеек из базы данных класс и все его содержимое: подмассива дублируют значение оригинальной -source(x) :- source(x).; ячейки. Пример программы, расширяющей каждую delete_frame(source). ячейку матрицы 3х3 в подматрицу 2х2: В правилах со знаком – в голове осуществляется q([i, j, val]) :- {x/[i, j, val] | exists y ( удаление объектов из коллекции. В данном случае source(y/[i1/i, j1/j, val]) & из коллекции удаляются все объекты. Функция ( i = i1*2 & j = j1*2 | i = i1*2 +1 & j = j1*2 | i= i1*2 & j= j1*2 + 1 | i= i1*2 +1 & j= j1*2 +1) ) }. delete_frame удаляет коллекцию как объект из базы данных. Операция ; обозначает последовательную Здесь выражение {x/T | F(x)}, где F – формула со композицию программ. В AQL данный запрос свободной переменной х, обозначает конструкцию представляется при помощи операции DROP: выделения множества; exists обозначает квантор существования. DROP ARRAY source; В ADM запрос представляется с использованием Продолжим описание отображения для операции xgrid: конструкций языка СИНТЕЗ, соответствующих SELECT * FROM xgrid(source, 2, 2); конструкциям AFL. Для экономии места будет рассмотрено лишь ограниченное количество Умножение матриц. Умножение матриц в конструкций. Рассматриваемые конструкции объектной модели (как и в реляционной) требует связаны только с извлечением данных. соединения матриц по разным индексам и дальнейшей группировки с суммированием Вычисление значений новых атрибутов. произведений элементов матриц: Рассмотрим запрос, вычисляющий значение нового r([i, j, val1, val2]) :- left([i, j1/j, val1/val]), атрибута – расстояние в километрах по имеющемуся right([i1/i, j, val2/val]), j1 = i1. расстоянию в милях: q([i, j, val]) :- group_by({i, j}, r(x/[i, j, val1, val2])), val = sum(x.val1*x.val2). q([i, miles, kilometers]) :- distance([i, miles]), kilometers = 1.6*miles. В ADM запрос представляется с использованием В ADM данный запрос представляется с операции multiply: использованием операции apply языка AFL: SELECT * FROM multiply(left, right); SELECT * FROM apply(distance, kilometers, 1.6*miles); На основании рассмотренного отображения ЯМД можно заметить, что многие из операций AFL Увеличение размерности массива и (например, xgrid) имеют достаточно сложно конкатенация массивов. Под массивом имеется устроенный прообраз в канонической модели. ввиду структура данных, полученная в результате Между тем, эти операции являются естественными отображения массива модели ADM в язык СИНТЕЗ для массивов. Поэтому, при интеграции ресурсов, (раздел 2.1). Рассмотрим программу, соединяющую основанных на многомерных массивах, в в двумерный массив два вектора: канонической модели возможно использование специального класса array, инкапсулирующего q([x, y, val]) :- vector1([x, val]), y =1. q([x, y, val]) :- vector2([x, val]), y = 2. специфические операции, характерные для многомерных массивов: В ADM запрос представляется с использованием операций adddim и substitute: { array; in: class; instance_type: { SELECT * xgrid: { in: function; FROM concat(adddim(vector1, y), adddim(vector2, y)); params: { +dimensions/{sequence; type_of_element: string;}, +scales/{sequence; type_of_element: integer;}}; Поиск (lookup). При особом виде соединения - }; }; поиске - наборы атрибутов из ячеек одного массива } (pattern) используются как координаты ячеек В приведенном примере рассмотрена сигнатура другого массива (source). Результирующий массив единственной операции xgrid, параметрами которой имеет ту же форму, что и первый массив, и являются последовательность имен измерений содержит значения из ячеек второго массива: dimensions и последовательность масштабов q([k, val]) :- pattern([k, i, j]), source([i, j, val]). увеличения по каждому из измерений scales. В ADM запрос представляется с использованием Параметром операции по умолчанию также операции lookup: считается класс array как коллекция объектов. При SELECT * FROM lookup(pattern, source); отображении ЯОД каждый класс - образ массива (например, класс source из раздела 2.1) становится подклассом класса array: 47 { source; in: class; superclass: array; замкнутой формулы, связывающей состояния instance_type: { … }; машин MS и MT. } Будем считать отображение  сохраняющим Аналогично xgrid, операциями класса array информацию и семантику операций, если машина могут быть представлены такие операции AFL, как MS, соответствующая исходной модели, уточняет substitute, sort, multiply и т.д. машину MT, соответствующую целевой модели. Заметим, что решение о представлении Уточнение доказывается интерактивно при помощи операций, характерных для многомерных массивов, специальных программных средств [3]. в рамках специального класса канонической модели допускает обобщение на объектные канонические В качестве иллюстрации основных принципов модели, отличные от языка СИНТЕЗ, и модели, выражения семантики моделей ADM и СИНТЕЗ в основанные на многомерных массивах, отличные от AMN рассмотрим частичные AMN-спецификации, ADM. соответствующие данным моделям. Часть спецификации, соответствующая В данной статье не рассматриваются операции объектной модели языка СИНТЕЗ, выглядит AFL, имеющие альтернативное представление следующим образом: конструкциями AQL - соединение, агрегация, 1 REFINEMENT ObjectDM фильтрация и т.д. Не рассматриваются также 2 ABSTRACT_VARIABLES операции, тесно связанные с реализацией, а не с 3 typeNames, classNames, attributeNames, моделью данных – чтение и запись файлов, загрузка 4 instanceType, typeAttributes, attributeType, подключаемых модулей, вывод служебной 5 unique, obligatory, 6 intAttributeLowerBound, intAttributeHigherBound, информации и т.д. 7 objectIDs, objectType, objectsOfClass, 8 integerAttributeValue 3 Сохранение информации и семантики 9 INVARIANT операций ЯМД при отображении 10 typeNames: POW(STRING_Type) & 11 classNames: POW(STRING_Type) & Метод доказательства сохранения информации и 12 attributeNames: NAT +-> STRING_Type & семантики операций при отображении моделей 13 instanceType: classNames --> typeNames & данных [8] основывается на представлении 14 typeAttributes: typeNames --> семантики моделей в формальном языке 15 POW(dom(attributeNames)) & спецификаций AMN [1]. 16 attributeType: dom(attributeNames) +->BuiltInTypes& 17 unique: typeNames --> POW(dom(attributeNames))& Язык AMN представляет собой теоретико- 18 obligatory: typeNames --> модельную нотацию, основанную на теории 19 POW(dom(attributeNames)) & множеств и типизированном языке первого порядка. 20 intAttributeLowerBound: Спецификации AMN называются абстрактными 21 dom(attributeNames) +-> INT & машинами. AMN позволяет интегрированно 22 objectIDs: POW(NAT) & рассматривать спецификацию пространства 23 objectType: objectIDs --> typeNames & 24 objectsOfClass: classNames --> POW(objectIDs) & состояний и поведения машины (определенного 25 !(cc).(cc: classNames => операциями на состояниях). В AMN формализуется 26 !(oo).(oo: objectsOfClass(cc) => специальное отношение между спецификациями – 27 objectType(oo) = instanceType(cc))) & уточнение. Неформально, спецификация B уточняет 28 integerAttributeValue: спецификацию A, если пользователь может 29 dom(attributeNames) +-> (objectIDs +-> INT) & использовать B вместо A, не замечая факта замены A 30 !(oo, aa).(oo: dom(objectType) & на B. 31 aa: typeAttributes(objectType(oo)) & 32 aa: obligatory(objectType(oo)) => Идея метода заключается в следующем. 33 (attributeType(aa) = Integer => Рассмотрим исходную модель S и целевую модель 34 oo: dom(integerAttributeValue(aa)))) & T. Построим отображение  модели S в модель T 35 !(oo, aa).(oo: objectIDs & (подобно изложенному в предыдущем разделе). 36 aa: typeAttributes(objectType(oo)) & Выразим семантику моделей в виде абстрактных 37 oo: dom(integerAttributeValue(aa) => машин AMN, построив при этом машины MS и MT 38 (aa: dom(intAttributeLowerBound) => соответственно. При этом структуры данных 39 (integerAttributeValue(aa)(oo) >= 40 intAttributeLowerBound(aa))) ) & моделей – классы, массивы представляются 41 !(oo1, oo2).(oo1: objectIDs & oo2: objectIDs & переменными машин, различные свойства структур 42 objectType(oo1) = objectType(oo2) & данных представляются инвариантами машин, 43 unique(objectType(oo1)) /= {} & характерные операции моделей данных 44 !(aa).(aa: unique(objectType(oo1)) => представляются операциями машин. 45 (attributeType(aa) = Integer => Рассматриваемые операции исходной и целевой 46 integerAttributeValue(aa)(oo1) = модели должны быть связаны отображением ЯМД. 47 integerAttributeValue(aa)(oo2)) ) => Отображение ЯОД представляется в виде 48 oo1 = oo2 ) специального склеивающего инварианта – 49 OPERATIONS 48 50 update(cls, attr, exp, cond) = Некоторые дополнительные необходимые 51 PRE cls: classNames & свойства переменных состояния представлены 52 attr: typeAttributes(instanceType(cls)) & конъюнктивными компонентами инварианта: 53 attributeType(attr) = Integer & 54 exp: INT --> INT & cond: NAT --> BOOL  тип объекта - экземпляра класса есть тип 55 THEN экземпляров этого класса (25-27); 56 integerAttributeValue :=  для любого объекта и любого определенного 57 integerAttributeValue <+ атрибута типа этого объекта функция 58 { xx | xx: (NAT*(NAT<->INT)) & значений атрибута определена на объекте (30- 59 #(oo, val).( oo: objectsOfClass(cls) & val: INT & 34); 60 xx = attr |-> ({oo |-> val}) &  для любого объекта и любого целочисленного 61 (cond(integerAttributeValue(attr)(oo)) = TRUE => 62 val = exp(integerAttributeValue(attr)(oo))) & атрибута типа объекта, определенного на 63 (cond(integerAttributeValue(attr)(oo)) = FALSE объекте и для которого определена нижняя 64 => val = integerAttributeValue(attr)(oo)) ) } (верхняя) граница, значение атрибута не 65 END меньше (не больше) нижней (верхней) 66 END границы (35-40); Переменные, составляющие пространство  объект однозначно идентифицируется состояний объектной модели, объявлены в разделе набором своих уникальных атрибутов (41-48). ABSTRACT_VARIABLES машины ObjectDM и Из всего ЯМД в спецификации рассмотрена типизируются в разделе INVARIANT. Так, имена единственная операция update обновления значений типов и классов представлены переменными атрибута в объектах класса. Параметрами операции typeNames, classNames, тип которых – подмножество являются имя класса cls, имя целочисленного множества строк (строки спецификации 10-11). атрибута attr типа экземпляров класса, функция exp Атрибуты (переменная attributeNames) отвечающая за преобразование атрибута и функция представлены частичной функцией, ставящей в cond, отвечающая условию на значение атрибута. соответствие уникальному идентификатору Пусть o – некоторый объект класса cls, для которого атрибута (натуральному числу) имя атрибута определено значение атрибута attr и это значение (строка 12). Типы экземпляров классов (переменная есть v. Тогда операция update (50-65) изменяет instanceType) представлены тотальной функцией из значение атрибута на exp(v) в случае, если множества имен классов в множество имен типов выражение cond(v) принимает значение истина и (13). Принадлежность атрибутов типам (переменная оставляет значение атрибута без изменений в typeAttributes) выражена тотальной функцией из противном случае. Очевидно, такая операция update множества имен типов в множество подмножеств есть обобщение примера обновления, атрибутов (14-15). Типы значений атрибутов рассмотренного в разделе 2.2. Действительно, для (переменная attributeType) представлены функцией рассмотренного примера cls есть source, attr есть val, из множества атрибутов в множество встроенных exp(v) = -v, cond(v) = abs(v). типов данных (16). Такими же функциями Заметим, что в данной спецификации для представлены множества уникальных атрибутов простоты не рассмотрены некоторые черты типов unique (17) и множества определенных объектной модели, например отношения тип-подтип атрибутов obligatory (18-19). Нижние границы и класс-подкласс. целочисленных атрибутов (переменная intAttributeLowerBound) представлены частичной функцией из множества атрибутов в множество Рассмотрим теперь часть спецификации, целых чисел (20-21). Аналогично представляются соответствующей модели ADM: верхние границы. Идентификаторы объектов 1 REFINEMENT ArrayDM (переменная objectIDs) представлены 2 REFINES ObjectDM подмножеством натуральных чисел (22). Типы 3 ABSTRACT_VARIABLES объектов (переменная objectType) представлены 4 arrayNames, dimensionNames, cellAttributeNames, тотальной функцией из множества объектных 5 arrayDimensions, arrayCellAttributes, идентификаторов в множество имен типов (23). 6 cellAtrributeType, nullable, 7 dimLowerBound, dimHigherBound, Состав классов (переменная objectsOfClass) 8 cells, dimensionValue, integerCellAttributeValue представлен тотальной функцией из множества 9 INVARIANT имен классов в множество подмножеств 10 arrayNames: POW(STRING_Type) & идентификаторов объектов (24). Значения 11 dimensionNames: NAT +-> STRING_Type & целочисленных атрибутов объектов (переменные 12 cellAttributeNames: NAT +-> STRING_Type & integerAttributeValue) представлены функциями из 13 arrayDimensions: множества атрибутов в функции из множества 14 arrayNames --> POW(dom(dimensionNames)) & идентификаторов объектов в множества значений 15 arrayCellAttributes: атрибутов (28-29). Функции для нецелочисленных 16 arrayNames --> POW(dom(cellAttributeNames)) & 17 cellAtrributeType: атрибутов определяются аналогично. 18 dom(cellAttributeNames) --> BuiltInTypes & 19 nullable: dom(cellAttributeNames) --> BOOL & 20 dimLowerBound: dom(dimensionNames) --> INT & 49 21 dimHigherBound: dom(dimensionNames) +-> INT & значение по крайней мере одного атрибута 22 cells: arrayNames --> POW(NAT) & (33-38). 23 dimensionValue: 24 NAT*dom(dimensionNames) +-> INT & Аналогично объектной модели рассмотрена 25 integerCellAttributeValue: единственная операция ЯМД – операция обновления 26 NAT*dom(cellAttributeNames) +-> INT & update (40-54). Сигнатура операции совпадает с 27 !(arr, cell1, cell2).(arr: arrayNames & сигнатурой операции объектной модели. Семантика 28 cell1: cells(arr) & cell2: cells(arr) & операции также аналогична: значение v атрибута 29 !(dim).(dim: arrayDimensions(arr) => attr массива cls заменяется на exp(v), если значение 30 dimensionValue(cell1, dim) = cond(v) есть истина и не изменяется в противном 31 dimensionValue(cell2, dim)) случае. 32 => cell1 = cell2 ) & 33 !(arr, cell).(arr: arrayNames & cell: cells(arr) => Заметим, что в данной спецификации для 34 !(dim).(dim: arrayDimensions(arr) => простоты не рассмотрены некоторые черты ADM, 35 (cell |-> dim): dom(dimensionValue)) & например, нецелочисленные измерения. 36 #(attr).(attr: arrayCellAttributes(arr) & 37 cellAtrributeType(attr) = Integer & 38 (cell, attr): dom(integerCellAttributeValue)) ) Для формального доказательства того, что 39 OPERATIONS машина ArrayDM уточняет машину ObjectDM 40 update(cls, attr, exp, cond) = необходимо построить инвариант уточнения, 41 PRE cls: arrayNames & attr: arrayCellAttributes(cls) & связывающий переменные машин и добавить его к 42 cellAtrributeType(attr) = Integer & инварианту уточняющей машины. 43 exp: INT --> INT & cond: NAT --> BOOL 44 THEN Инвариант уточнения выглядит следующим 45 integerCellAttributeValue := образом: 46 integerCellAttributeValue <+ 1 classNames = arrayNames & 47 { yy | yy: (NAT*NAT)*INT & 2 attributeNames=dimensionNames\/cellAttributeNames& 48 #(cell, val).(cell: cells(cls) & val: INT & 3 !(arr, dim).(arr: arrayNames & 49 yy = ((cell |-> attr)|-> val) & 4 dim: arrayDimensions(arr) => 50 (cond(integerCellAttributeValue(cell, attr)) = TRUE => 5 #(attr).(attr: typeAttributes(instanceType(arr)) & 51 val = exp(integerCellAttributeValue(cell, attr))) & 6 attr = dim & attributeType(attr) = Integer) ) & 52 (cond(integerCellAttributeValue(cell, attr))= FALSE=> 7 !(arr, cattr).(arr: arrayNames & 53 val = integerCellAttributeValue(cell, attr)) ) } 8 cattr: arrayCellAttributes(arr) => 54 END 9 #(attr).(attr: typeAttributes(instanceType(arr)) & 55 END 10 attr=cattr& attributeType(attr)=attributeType(cattr)))& Имена массивов представлены переменной 11 !(arr, cattr).(arr: arrayNames & cattr /: dom(nullable) & arrayNames (строка спецификации 10); имена 12 cattr: arrayCellAttributes(arr) => 13 cattr: obligatory(instanceType(arr)) ) & измерений – переменной dimensionNames (строка 14 !(arr, dim).(arr: arrayNames & 11); имена атрибутов ячеек массива – переменной 15 dim: arrayDimensions(arr) => cellAttributeNames (12); принадлежность измерений 16 dim: unique(instanceType(arr)) ) & массивам – переменной arrayDimensions (13-14); 17 !(dim).(dim: dom(dimLowerBound) => принадлежность атрибутов ячеек – переменной 18 dim: dom(intAttributeLowerBound) & arrayCellAttributes (15-16); тип атрибута ячейки – 19 dimLowerBound(dim) = переменной cellAtrributeType (17-18); атрибуты 20 intAttributeLowerBound(dim)) & ячеек массивов, которые могут принимать 21 cells = objectsOfClass & неопределенные значения – переменной nullable 22 !(cell, dim).(cell: NAT & dim: NAT & 23 (cell |-> dim): dom(dimensionValue) => (19); верхние (нижние) границы измерений – 24 cell: dom(integerAttributeValue(dim)) & переменной dimLowerBound (dimHigherBound) (20- 25 dimensionValue(cell, dim) = 21); множества идентификаторов ячеек массивов – 26 integerAttributeValue(dim)(cell) ) & переменной cells (22), значения измерений в ячейках 27 !(cell, cattr).(cell: NAT & cattr: NAT & – переменной dimensionValue (23-24); значения 28 (cell |-> cattr): dom(integerCellAttributeValue) => атрибутов ячеек – переменной 29 cell: dom(integerAttributeValue(cattr)) & integerCellAttributeValue (25-26). Переменные 30 integerCellAttributeValue(cell, cattr) = типизируются при помощи частичных и тотальных 31 integerAttributeValue(cattr)(cell) ) функций аналогично переменным, использующимся Инвариант формализует принципы отображения для придания семантики объектной модели. ЯОД, изложенные в разделе 2.1: Дополнительные необходимые свойства  множество имен массивов совпадает с переменных состояния представлены множеством имен классов (строка 1); конъюнктивными компонентами инварианта:  множество идентификаторов и имен  любая ячейка любого массива однозначно измерений и атрибутов ячеек совпадает с идентифицируется набором значений множеством идентификаторов и имен измерений (27-32); атрибутов типов экземпляров классов (2);  для любой ячейки любого массива  любому измерению массива соответствует определены значения всех измерений и атрибут типа экземпляра класса, соответствующего этому массиву (3-6); 50  любому атрибуту ячейки любого массива – например, другую объектную (ODMG) или соответствует атрибут типа экземпляра объектно-реляционную модель (SQL:2003). класса, соответствующего этому массиву и Результаты также могут быть использованы для типы атрибутов совпадают (7-10); интеграции ресурсов, представленных в модели,  атрибут ячейки массива, который может основанной на многомерных массивах, но отличной принимать неопределенные значения, от ADM. соответствует определенному (obligatory) Некоторые вопросы отображения требуют атрибуту типа (11-13); дальнейших исследований, например, следует ли  измерения соответствуют уникальным иметь в канонической модели при интеграции атрибутам типов (14-16); массив-ориентированных моделей данных  верхние (нижние) границы измерений равны операции, связанные с размером порции (chunk size) верхним (нижним) границам данных в БД [17]. соответствующих атрибутов типов (17-20); Дальнейшую работу можно разбить на три этапа:  непустые ячейки массивов соответствуют  построение трансформации, реализующей объектам классов (21); изложенное отображение;  для любой ячейки значения ее измерений и  расширение инструментальных средств определенных атрибутов совпадают со поддержки предметных посредников для значениями соответствующих атрибутов виртуальной интеграции SciDB-ресурсов: (i) объекта, соответствующего ячейке (22-31). расширение средств регистрации ресурсов в посреднике [19] трансформацией ЯОД ADM Спецификации ObjectDM и ArrayDM вместе с в каноническую модель; (ii) создание SciDB- инвариантом уточнения были загружены в адаптера - специального ПО, связывающего инструментальное средство Atelier B [3]. исполнительную среду посредников с SciDB- Автоматически были сгенерированы теоремы, ресурсами (составной частью адаптера выражающие уточнение спецификаций. В является трансформация ЯМД); частности, для операции update были сгенерированы  применение технологии предметных 10 теорем. 3 из них были доказаны автоматически, посредников для решения научных задач в для доказательства остальных необходимо некоторой предметной области над применять интерактивные средства доказательства. множеством неоднородных ресурсов, включающим SciDB-ресурсы. 4 Родственные исследования и направления дальнейшей работы Благодарности Родственными данной работе следует считать Автор выражает благодарность Л. А. Калиниченко, работы, связанные с отображением моделей, П. Е. Велихову и А. Е. Вовченко за полезные основанных на многомерных массивах, в замечания, высказанные в ходе обсуждения данной реляционную модель данных. Обычно эти работы работы на семинарах ИПИ РАН. нацелены на реализацию многомерных массивов при помощи реляционных СУБД. Такие работы начались одновременно с исследованиями моделей, Литература основанных на многомерных массивах [5], и [1] Abrial J.-R. The B-Book: Assigning Programs to продолжаются в настоящее время [4]. Meanings. Cambridge: Cambridge University Основные особенности данной работы состоят в Press, 1996. следующем. В качестве исходной модели при [2] Astronomy in ArrayDB. http://trac.scidb.org/raw- отображении используется специфическая модель, attachment/wiki/UseCases/Astronomy%20in%20Array основанная на многомерных массивах, СУБД SciDB, DB.pdf язык которой представляет собой комбинацию [3] Atelier B, the industrial tool to efficiently deploy декларативного SQL-подобного языка и the B Method. http://www.atelierb.eu/index-en.php функционального языка, включающего специфические операции над многомерными [4] Alex van Ballegooij. RAM: Array Database массивами. В качестве целевой модели используется Management through Relational Mapping. SIKS объектная модель с Datalog-подобным языком Dissertation Series, N 2009-25. – 2009. http://oai.cwi.nl/oai/asset/14074/14074D.pdf запросов (программ) – язык СИНТЕЗ. Для отображения обеспечивается формальное [5] P. Baumann. A Database Array Algebra for доказательство сохранения информации и Spatio-Temporal Data and Beyond. In Next семантики операций ЯМД. Generation Information Technologies and Systems, pages 76–93, 1999. Отметим, что результаты работы могут быть с легкостью обобщены и использованы при [6] J. Becla, K.-T. Lim. Report form the First интеграции в системах, использующих Workshop on Extremely Large Databases. Data каноническую модель, отличную от языка СИНТЕЗ Science Journal, Volume 7, 2008. 51 [7] Challenges and Opportunities with Big Data // A [16] Torben Bach Pedersen, Christian S. Jensen. community white paper developed by leading Multidimensional Database Technology. IEEE researchers across the United States. – 2012. Computer, vol. 34, no. 12, pp. 40-46, 2001. http://cra.org/ccc/docs/init/bigdatawhitepaper.pdf [17] SciDB User's Guide. Version 12.3. – 2012. [8] Kalinichenko L.A. Method for Data Models http://www.scidb.org/ Integration in the Common Paradigm. Proc. of the [18] P. Vassiliadis and T. K. Sellis. A Survey of First East-European Symposium on Advances in Logical Models for OLAP Databases. SIGMOD Databases and Information Systems ADBIS'97. - Record, 28(4):64–69, 1999. St.-Petersburg: Nevsky Dialect, 1997. - V. 1: [19] Брюхов Д.О., Вовченко А. Е., Захаров В.Н., Regular Papers. - P. 275-284. Желенкова О.П., Калиниченко Л.А., Мартынов [9] Kalinichenko L.A., Briukhov D.O., Martynov Д.О., Скворцов Н.А., Ступников С.А. D.O., Skvortsov N.A., Stupnikov S.A. Mediation Архитектура промежуточного слоя Framework for Enterprise Information System предметных посредников для решения задач Infrastructures. Proc. of the 9th International над множеством интегрируемых неоднородных Conference on Enterprise Information Systems распределенных информационных ресурсов в ICEIS 2007. - Funchal, 2007. - Volume Databases гибридной грид-инфраструктуре виртуальных and Information Systems Integration. - P. 246-251. обсерваторий // Информатика и ее применения. [10] Kalinichenko L.A., Stupnikov S.A. Heterogeneous – М., 2008. – Т. 2, Вып. 1. – С. 2-34. information model unification as a pre-requisite to [20] Захаров В. Н., Калиниченко Л. А., Соколов И. resource schema mapping // A. D’Atri and D. А., Ступников С. А. Конструирование Saccà (eds.), Information Systems: People, канонических информационных моделей для Organizations, Institutions, and Technologies интегрированных информационных систем // (Proc. of the V Conference of the Italian Chapter Информатика и ее применения. – М., 2007. – Т. of Association for Information Systems itAIS). – 1, Вып. 2. – C. 15-38. Berlin-Heidelberg: Springer Physica Verlag, 2010. – P. 373-380. Unification of an Array Data Model for the [11] Kalinichenko L.A., Stupnikov S.A., Martynov Integration of Heterogeneous Information D.O. SYNTHESIS: a Language for Canonical Resources Information Modeling and Mediator Definition for Problem Solving in Heterogeneous Information Sergey Stupnikov Resource Environments. Moscow: IPI RAN, 2007. - 171 p. In the paper a mapping of an array-based data model – the SciDB DBMS model - into a canonical model [12] Martin L. Kersten, Ying Zhang, Milena Ivanova, used for virtual or materialized database integration is Niels Nes: SciQL, a query language for science presented. To be precise, a mapping into an object applications. EDBT/ICDT Array Databases model - the SYNTHESIS language is considered. The Workshop 2011:1-12 SYNTHESIS language is used as the canonical model in [13] Large Synoptic Survey Telescope. the subject mediator technology. http://www.lsst.org A method for proving of preserving the information [14] Leonid Libkin, Rona Machlin, Limsoon Wong. A and the semantics of operations by the mapping is Query Language for Multidimensional Arrays: illustrated. The method uses a formal specification Design, Implementation, and Optimization language. Techniques. SIGMOD, 1996. – P.228-239. An aim of the work is developing of a sound [15] Overview of SciDB: Large Scale Array Storage, theoretical basis for the integration of array-based Processing and Analysis. The SciDB Development resources. team. SIGMOD, 2010. 52