В работе рассматривается отображение одной из моделей данных, основанной на многомерных массивах - модели СУБД SciDB в каноническую модель систем виртуальной или материализованной интеграции баз данных. Для определенности в статье рассматривается отображение в объектную модель данных язык СИНТЕЗ, использующийся в качестве канонической модели данных в технологии предметных посредников. Проиллюстрирован метод доказательства сохранения информации и семантики операций при отображении моделей данных с использованием формального языка спецификаций. Целью работы является создание обоснованной теоретической базы для интеграции ресурсов, основанных на многомерных массивах.
Работа выполнена при поддержке РФФИ (гранты 10-07-00342-а, 11-07-00402-а) и Президиума РАН (программа 16П, проект 4.2).
Развитие науки и промышленности, широкое распространение информационных технологий ведет к накоплению огромных объемов данных как в науке, так и в бизнесе. Данные могут быть как наблюдательными, экспериментальными, так и полученными в ходе компьютерного моделирования. Данные таких масштабов (часто измеряемых уже в петабайтах) называются «большими данными» (Big Data) [7], плохо поддаются обработке и анализу в рамках хорошо известных технологий баз данных, опирающихся в основном на реляционную модель данных.
Именно поэтому развиваются различные модели данных, нацеленные на параллельную обработку и анализ данных в распределенных средах – гридах и Труды 14-й Всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» — RCDL-2012, Переславль-Залесский, Россия, 15-18 октября 2012 г.
История SciDB начинается с 2007 года, когда на симпозиуме по Экстремально большим базам данных (XLDB) представителями науки и промышленности был сделан вывод, что существующие СУБД не в состоянии манипулировать объемами данных, которые появятся в ближайшем будущем. Одним из примеров поставщиков таких данных является строящийся телескоп LSST (Large Synoptic Survey Telescope) [13]. Был также сделан вывод о необходимости разработки СУБД нового поколения, которая должна удовлетворять, в частности, следующим требованиям [6]: модель данных основывается на многомерных массивах, а не на кортежах; модель хранения базируется на версионности, а не на обновлении значений; масштабируемость до сотен петабайт и высокая отказоустойчивость; СУБД является свободно распространяемым программным обеспечением.
Некоторое время спустя был запущен международный проект под руководством Майкла Стоунбрейкера, целью которого являлось создание новой системы управления базами данных, получившей название SciDB. В настоящее время свободно распространяется очередная версия системы для ОС Ubuntu и RedHat.
Целью данной статьи является исследование вопроса об унификации модели данных системы SciDB (будем называть ее в дальнейшем ADM – Array Data Model [17]) для виртуальной или материализованной интеграции ресурсов при создании федеративных баз данных или хранилищ данных.
При материализованной интеграции предполагается создание хранилища данных (warehouse), в которое загружаются ресурсы, подлежащие интеграции. В процессе загрузке происходит преобразование данных из схемы ресурса в общую схему хранилища.
Виртуальная же интеграция рассматривается в статье применительно к предметным посредникам [9]. Предметные посредники представляют собой специальный вид программного обеспечения, образующий промежуточный слой между пользователем (приложением) и неоднородными информационными ресурсами. При этом данные из ресурсов не материализуются в посреднике. Федеративная схема посредника, описывающая некоторую предметную область, создается независимо от существующих ресурсов. Ресурсы, релевантные предметной области, затем регистрируются в посреднике – их схемы связываются специальными семантическими отображениями с федеративной схемой. Исполнительная среда посредников предоставляет возможность пользователям (приложениям) задавать запросы (программы) к посреднику в терминах федеративной схемы. Эти запросы переписываются в частичные запросы над информационными ресурсами, затем исполняются на ресурсах. Результаты частичных запросов объединяются и выдаются пользователю также в терминах федеративной схемы.
Важным понятием технологии систем интеграции баз данных является каноническая модель, служащая общим языком, унифицирующим разнообразные модели ресурсов.
Унификацией некоторой исходной модели данных называется ее отображение в каноническую модель, сохраняющее информацию и семантику операций языка манипулирования данными (ЯМД) [20]. Унификация должна быть доказуемо правильной. Очевидно, что унификация моделей ресурсов является необходимым предусловием для регистрации ресурсов в посреднике – семантические отображения, связывающие федеративную схему и схемы ресурсов, нужно проводить в единой (канонической модели) [10].
В качестве канонической модели в данной работе рассматривается язык СИНТЕЗ [11] комбинированная слабоструктурированная и объектная модель данных, нацеленная на разработку предметных посредников для решения задач в средах неоднородных ресурсов. Разработан прототип программных средств для поддержки среды предметных посредников с языком СИНТЕЗ в роли канонической модели [19].
С точки зрения предметных посредников СУБД, основанные на многомерных массивах, представляют собой новый вид ресурсов, подлежащих интеграции в посредниках вместе с привычными ресурсами – реляционными и объектными СУБД, веб-сервисами и т.д.
Нужно отметить, что ADM подвергается некоторой критике со стороны исследователей, продолжающих развитие моделей, основанных на многомерных массивах. Так, авторы языка SciQL [12] отмечают, что язык ADM является смесью SQL и деревьев алгебраических операций. По их мнению, язык для СУБД, основанных на многомерных массивах, должен быть интегрирован с синтаксисом и семантикой 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 представляет собой функциональный язык манипулирования массивами, операции которого можно объединять в композиции. Допускается использование операций AFL в запросах AQL.
Операции языков и отображение будут иллюстрироваться на адаптированных примерах из сценария применения SciDB в области оптической астрономии [2], а также на простых примерах из документации SciDB [17]. 2.1 Отображение языка определения данных Отображение ЯОД в данном разделе описывается независимо от вида интеграции – виртуальной или материализованной.
Основной единицей определения данных в модели ADM является массив, имеющий конечное количество измерений d1, d2, ..., dn [17]. Длиной измерения называется количество упорядоченных значений в этом измерении. По умолчанию типом измерения являются 64-битные целые числа. Поддерживаются также нецелочисленные измерения, например строки или числа с плавающей точкой. Каждая комбинация значений измерений соответствует ячейке массива, которая может содержать конечное количество значений, называемых атрибутами. Типом атрибута может быть один из встроенных типов ADM [17].
Основная операция ЯОД ADM массива - выглядит следующим образом: – создание CREATE ARRAY source < ampExposureId: int64 NULL, filterId: int8, apMag: double > [ ra(double), de(double), objectId=0:*]; Создается масcив оптических источников source, измерениями которого являются координаты ra и de типа 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; {{ all s (source(s) -> s.objectId >= 0) }} }; long ampExposureId; short filterId; double apMag; key: { unique; { ra, de, objectId } }; definiteness: {obligatory; { ra, de, objectId, filterId, apMag } }; }; } Как измерения, так и атрибуты, составляющие ячейку, представляются в языке СИНТЕЗ атрибутами типа экземпляров (instance_type) класса. Между встроенными типами ADM (int8, int64, double и т.д.) и встроенными типами языка СИНТЕЗ (short, long, double) устанавливается взаимнооднозначное соответствие. Совокупность атрибутов, соответствующих измерениям, объявляется уникальной (инвариант key, выражаемый встроенным утверждением unique). Объявляется также, что атрибуты, соответствующие измерениям и не-NULL атрибутам ADM, должны быть определены у всех экземпляров класса (инвариант definiteness, выражаемый встроенным утверждением obligatory).
Таким образом обеспечивается отличительных свойств многомерных («кубов данных»), существенным сохранение массивов образом различающих измерения и атрибуты, составляющие ячейку: по набору значений измерений однозначно определяется набор значений атрибутов ячейки (уникальность измерений); ячейка массива всегда определяется полным набором значений измерений (определенность измерений).
Заметим также, что отсутствие в коллекции объекта с некоторым набором значений измерений означает пустую ячейку в массиве.
Для нецелочисленных измерений ra и de кроме атрибутов в языке СИНТЕЗ определяются функции ra2long, de2long, преобразующие нецелочисленные значения в целочисленные. Необходимость привнесения этих функций вызвана следующим. При попытке описать операции, характерные для ММ-моделей, в объектной модели (в частности, в языке СИНТЕЗ), выясняется необходимость применения существенно различных механизмов работы с целочисленными и нецелочисленными измерениями. Это вызвано различием типов измерений, возможной неравномерностью шага измерения и т.д. Для того, чтобы обеспечить возможность единообразного описания операций над целочисленными и нецелочисленными измерениями и необходимы функции, приводящие нецелочисленные измерения к целочисленным.
Ограничения, связанные с нижними и верхними границами целочисленных измерений, представляются в языке СИНТЕЗ во-первых, метаслотом соответствующего атрибута (например, objectId). В метаслоте хранится метаинформация, связанная с атрибутом, как с отдельной сущностью языка. В данном случае метаслот включает два слота lower и higher, отвечающих, соответственно, верхней и нижней границе измерения. Во-вторых, создается инвариант (например, objectIdBounds) предикативная спецификация которого устанавливает ограничения на значения измерения для каждого из объектов класса, отвечающего массиву. Спецификация инварианта имеет вид формулы первого порядка, где all – квантор существования, -> – импликация.
Необходимо отметить, что массив представляется в объектной модели множеством объектов класса (фактически, кортежей значений атрибутов). При этом наблюдается некоторое противоречие со стремлением создателей ММмоделей отойти от моделей, основанных на кортежах. Однако, в контексте интеграции ресурсов ММ-модели - лишь один класс из большого множества разнообразных классов моделей данных. Представление специфических ММ-моделей в объектной модели является методологически и технически гораздо более простым и естественным, нежели использование многомерных массивов в качестве канонической модели.
Изложенные принципы отображения ЯОД могут быть обобщены на случай, когда канонической является объектная или объектно-реляционная модель, отличная от языка СИНТЕЗ. Также, непринципиальным является выбор модели данных, основанной на многомерных массивах. В общем виде, принципы отображения ЯОД выглядят следующим образом: массив отображается в коллекцию типизированных объектов (класс) объектной модели; измерения и атрибуты, составляющие ячейку массива, отображаются в атрибуты типа экземпляров класса; между встроенными типами модели, основанной на многомерных массивах, и встроенными типами объектной модели устанавливается взаимно-однозначное соответствие; совокупность атрибутов, соответствующих измерениям, объявляется уникальной (при помощи механизма ключей, утверждений или инвариантов); атрибуты, соответствующие измерениям и неNULL атрибутам ячейки массива, объявляются определенными (при помощи утверждений или инвариантов); для нецелочисленных измерений в типе экземпляров дополнительно определяются методы, преобразующие нецелочисленные значения в целочисленные; ограничения, связанные с нижними и верхними границами целочисленных измерений, отображаются при помощи инвариантов или встроенных утверждений о кардинальности соответствующих атрибутов. В случае использования инвариантов при отображении, границы измерений представляются также метаданными атрибута. 2.2 Отображение языка манипулирования данными
При интеграции баз данных для установления семантических соотношений между схемами ресурсов и федеративной схемой необходимо отображение ЯОД исходной модели в каноническую. ЯМД канонической модели, напротив, необходимо отображать в ЯМД исходной модели. Это связано с тем, что запросы к посреднику в канонической модели необходимо отображать в запросы к ресурсам.
Отметим отличие виртуальной и материализованной интеграции. При виртуальной интеграции отображение ЯМД обеспечивает возможность трансляции программ на языке посредника в запросы на языке ресурсов.
В случае материализованной интеграции данные извлекаются из ресурса и представляются в хранилище в канонической модели. При этом программы на языке канонической модели исполняются непосредственно на данных. Отображение ЯМД нужно лишь для того, чтобы убедиться, что отображение моделей сохраняет информацию и семантику операций. Семантически правильное отображение служит базой для процесса Извлечения-Преобразования-Загрузки (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 – ограничение, налагаемое на 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.
При отображении ЯМД будут сначала рассмотрены основные конструкции языка программ СИНТЕЗ, соответствующие конструкциям языка AQL. Затем будут рассмотрены конструкции СИНТЕЗ, соответствующие конструкциям языка AFL.
Начнем рассмотрение с конструкций языка СИНТЕЗ, соответствующих конструкциям языка AQL, связанных с извлечением данных.
Предикаты-классы, условия, подзапросы. Рассмотрим программу, извлекающую координаты (ra, de) и апертурную звездную величину (apMag) астрономических источников из класса source с условием на фильтр (filterId) и апертурную звездную величину, причем запрос q использует результаты запроса r.
q([ra, de, apMag]) :- r([ra, de, apMag]), filterId= #filterId. r([ra, de, apMag]) :source([ra, de, apMag]), apMag >= #apMag.
Здесь #filterId и #apMag – некоторые константы соответствующих типов.
Такая программа представляется в AQL следующим запросом:
SELECT apMag FROM ( SELECT apMag FROM source
WHERE apMag >= #apMag ) WHERE filterId = #filterId; Простые условия отображаются в AQL без изменений, рекурсивные запросы представляются вложенными запросами. Заметим, что координаты ra, de не указываются в секции SELECT – они являются измерениями и извлекаются по умолчанию.
Функциональные предикаты. Рассмотрим запрос, конструирующий из двух звездных величин uMag, rMag в разных фильтрах цветовую разность: q([objectId, ugColor]) :objectSummary([objectId, uMag, rMag]), diff(uMag, rMag, ugColor). Запрос включает функциональный предикат, семантика которого определяется функцией diff: { diff; in: function; params: {+min/float, +sub/float, -res/float}; {{ res = min - sub }} } В двойных фигурных скобках заключена предикативная спецификация функции, связывающая значения входных и выходных параметров в формуле типизированного исчисления первого порядка.
Для простоты изложения рассматривается функция, возвращающая разность параметров.
В AQL запрос представляется образом:
SELECT uMag – rMag AS ugColor
FROM objectSummary; где массив objectSummary имеет вид
CREATE ARRAY objectSummary < uMag: float NULL, gMag: float NULL > [ objectId=0:* ]; следующим Таким образом, если результат функции описывается выражением, составленным из операций над простыми встроенными типами, то в AQL подобное выражение может быть в явном виде вынесено в оператор SELECT.
Соединение классов. Соединение определенным атрибутам (например, objectId) по q2([ra, de, filterId, uMag]) :source([ra, de, objectId, fliterId]), objectSummary([objectId, uMag]) представляется в AQL конструкцией JOIN-ON: SELECT filterId, uMag INTO q2 FROM source JOIN objectSummary ON Source.objectId = ObjectSummary.objectId;
Группирование. Рассмотрим запрос, возвращающий среднее значение звездной величины uMag, вычисленное на группе по идентификатору объекта filterId: q([objectId, avgMag]) :group_by({objectId}, q2(obj/[ra,de,filterId, uMag])), avgMag = average(obj.uMag).
Здесь коллекция q2, на которой производится группирование по атрибуту objectId – результат соединения классов source и objectSummary, рассмотренный выше.
Очевидно, в AQL запрос представляется при помощи конструкции GROUP BY:
SELECT avg(uMag) AS avgMag FROM q2 GROUP BY objectId; Агрегация в бегущем окне (Window Aggregation). Такой вид агрегации является специфическим для моделей, основанных на многомерных массивах. Окно определяется своим размером в каждом измерении массива. Центроид окна располагается в каждом из элементов массива и для каждого такого окна вычисляется некоторая агрегирующая функция. Например, для вычисления среднего значения в бегущем окне размера 3х3 в квадратной матрице 4х4, определяемой в AQL следующим образом:
CREATE ARRAY source <val: double>[i = 0:3, j = 0:3]; необходим запрос q([i, j, avgVal]) :- source(x/[i, j]),
windowAggr(i, j, avgVal). где семантика предиката windowAggr определяется функцией { windowAggr; in: function; params: {+i0/long, +j0/long, -res/double}; {{ source(x/[i, j, val]) & i >= i0 - 1 & i <= i0 + 1 & j >= j0 - 1 & j <= j0 + 1 & res = average(x.val) }} } вычисляющей среднее значение в окне с заданным центроидом в классе source.
AQL предлагает для агрегации в бегущем окне специальную конструкцию WINDOW:
SELECT avg(val) AS avgVal FROM source WINDOW 3, 3; Рассмотрим конструкции соответствующие конструкциям связанные с изменением данных. языка СИНТЕЗ, языка AQL, и Обновление. Рассмотрим запрос, изменяющий значения в квадратной матрице (см. предыдущий пример) на значения с обратным знаком в том случае, если модуль значения больше 5.
source(x/[i, j, val]) :
source(x/[i, j, val1/val]), abs(val) > 5, val = -val1.
В AQL данный следующим образом: запрос представляется UPDATE source SET val = -val WHERE abs(val) > 5; Удаление. Рассмотрим программу, удаляющую из базы данных класс и все его содержимое: -source(x) :- source(x).; delete_frame(source).
В правилах со знаком – в голове осуществляется удаление объектов из коллекции. В данном случае из коллекции удаляются все объекты. Функция delete_frame удаляет коллекцию как объект из базы данных. Операция ; обозначает последовательную композицию программ. В AQL данный запрос представляется при помощи операции DROP: DROP ARRAY source; Продолжим описание отображения для конструкций языка СИНТЕЗ, соответствующих конструкциям AFL. Для экономии места будет рассмотрено лишь ограниченное количество конструкций. Рассматриваемые конструкции связаны только с извлечением данных.
Вычисление значений новых атрибутов. Рассмотрим запрос, вычисляющий значение нового атрибута – расстояние в километрах по имеющемуся расстоянию в милях: q([i, miles, kilometers]) :
distance([i, miles]), kilometers = 1.6*miles.
В ADM данный запрос представляется с использованием операции apply языка AFL: SELECT * FROM apply(distance, kilometers, 1.6*miles); Увеличение размерности массива и конкатенация массивов. Под массивом имеется ввиду структура данных, полученная в результате отображения массива модели ADM в язык СИНТЕЗ (раздел 2.1). Рассмотрим программу, соединяющую в двумерный массив два вектора: q([x, y, val]) :- vector1([x, val]), y =1. q([x, y, val]) :- vector2([x, val]), y = 2.
В ADM запрос представляется с использованием операций adddim и substitute:
SELECT * FROM concat(adddim(vector1, y), adddim(vector2, y)); Поиск (lookup). При особом виде соединения поиске - наборы атрибутов из ячеек одного массива (pattern) используются как координаты ячеек другого массива (source). Результирующий массив имеет ту же форму, что и первый массив, и содержит значения из ячеек второго массива: q([k, val]) :- pattern([k, i, j]), source([i, j, val]).
В ADM запрос представляется с использованием операции lookup:
SELECT * FROM lookup(pattern, 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) ) }. Здесь выражение {x/T | F(x)}, где F – формула со свободной переменной х, обозначает конструкцию выделения множества; exists обозначает квантор существования.
В ADM запрос представляется с использованием операции xgrid:
SELECT * FROM xgrid(source, 2, 2); Умножение матриц. Умножение матриц в объектной модели (как и в реляционной) требует соединения матриц по разным индексам и дальнейшей группировки с суммированием произведений элементов матриц: 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).
В ADM запрос представляется с использованием операции multiply:
SELECT * FROM multiply(left, right); На основании рассмотренного отображения ЯМД можно заметить, что многие из операций AFL (например, xgrid) имеют достаточно сложно устроенный прообраз в канонической модели. Между тем, эти операции являются естественными для массивов. Поэтому, при интеграции ресурсов, основанных на многомерных массивах, в канонической модели возможно использование специального класса array, инкапсулирующего специфические операции, характерные для многомерных массивов: { array; in: class; instance_type: { xgrid: { in: function; params: { +dimensions/{sequence; type_of_element: string;}, +scales/{sequence; type_of_element: integer;}}; }; }; } В приведенном примере рассмотрена сигнатура единственной операции xgrid, параметрами которой являются последовательность имен измерений dimensions и последовательность масштабов увеличения по каждому из измерений scales. Параметром операции по умолчанию также считается класс array как коллекция объектов. При отображении ЯОД каждый класс - образ массива (например, класс source из раздела 2.1) становится подклассом класса array: { source; in: class; superclass: array; instance_type: { … }; Аналогично xgrid, операциями класса array могут быть представлены такие операции AFL, как substitute, sort, multiply и т.д.
Заметим, что решение о представлении операций, характерных для многомерных массивов, в рамках специального класса канонической модели допускает обобщение на объектные канонические модели, отличные от языка СИНТЕЗ, и модели, основанные на многомерных массивах, отличные от ADM.
В данной статье не рассматриваются операции AFL, имеющие альтернативное представление конструкциями AQL - соединение, агрегация, фильтрация и т.д. Не рассматриваются также операции, тесно связанные с реализацией, а не с моделью данных – чтение и запись файлов, загрузка подключаемых модулей, вывод служебной информации и т.д. 3 Сохранение информации и семантики операций ЯМД при отображении
Метод доказательства сохранения информации и семантики операций при отображении моделей данных [8] основывается на представлении семантики моделей в формальном языке спецификаций AMN [1].
Язык AMN представляет собой теоретикомодельную нотацию, основанную на теории множеств и типизированном языке первого порядка. Спецификации AMN называются абстрактными машинами. AMN позволяет интегрированно рассматривать спецификацию пространства состояний и поведения машины (определенного операциями на состояниях). В AMN формализуется специальное отношение между спецификациями – уточнение. Неформально, спецификация B уточняет спецификацию A, если пользователь может использовать B вместо A, не замечая факта замены A на B.
Идея метода заключается в следующем. Рассмотрим исходную модель S и целевую модель T. Построим отображение модели S в модель T (подобно изложенному в предыдущем разделе). Выразим семантику моделей в виде абстрактных машин AMN, построив при этом машины MS и MT соответственно. При этом структуры данных моделей – классы, массивы представляются переменными машин, различные свойства структур данных представляются инвариантами машин, характерные операции моделей данных представляются операциями машин. Рассматриваемые операции исходной и целевой модели должны быть связаны отображением ЯМД. Отображение ЯОД представляется в виде специального склеивающего инварианта – замкнутой формулы, связывающей машин MS и MT. состояния Будем считать отображение сохраняющим информацию и семантику операций, если машина MS, соответствующая исходной модели, уточняет машину MT, соответствующую целевой модели. Уточнение доказывается интерактивно при помощи специальных программных средств [3].
В качестве иллюстрации основных принципов выражения семантики моделей ADM и СИНТЕЗ в AMN рассмотрим частичные AMN-спецификации, соответствующие данным моделям.
Часть спецификации, соответствующая объектной модели языка СИНТЕЗ, выглядит следующим образом:
REFINEMENT ObjectDM ABSTRACT_VARIABLES typeNames, classNames, attributeNames, instanceType, typeAttributes, attributeType, unique, obligatory, intAttributeLowerBound, intAttributeHigherBound, objectIDs, objectType, objectsOfClass, integerAttributeValue INVARIANT typeNames: POW(STRING_Type) & classNames: POW(STRING_Type) & attributeNames: NAT +-> STRING_Type & instanceType: classNames --> typeNames & typeAttributes: typeNames -->
POW(dom(attributeNames)) & attributeType: dom(attributeNames) +->BuiltInTypes& unique: typeNames --> POW(dom(attributeNames))& obligatory: typeNames -->
POW(dom(attributeNames)) & intAttributeLowerBound:
dom(attributeNames) +-> INT & objectIDs: POW(NAT) & objectType: objectIDs --> typeNames & objectsOfClass: classNames --> POW(objectIDs) & !(cc).(cc: classNames => !(oo).(oo: objectsOfClass(cc) => objectType(oo) = instanceType(cc))) & integerAttributeValue:
dom(attributeNames) +-> (objectIDs +-> INT) & !(oo, aa).(oo: dom(objectType) & aa: typeAttributes(objectType(oo)) & aa: obligatory(objectType(oo)) => (attributeType(aa) = Integer =>
oo: dom(integerAttributeValue(aa)))) & !(oo, aa).(oo: objectIDs & aa: typeAttributes(objectType(oo)) & oo: dom(integerAttributeValue(aa) => (aa: dom(intAttributeLowerBound) => (integerAttributeValue(aa)(oo) >= intAttributeLowerBound(aa))) ) & !(oo1, oo2).(oo1: objectIDs & oo2: objectIDs & objectType(oo1) = objectType(oo2) & unique(objectType(oo1)) /= {} & !(aa).(aa: unique(objectType(oo1)) => (attributeType(aa) = Integer => integerAttributeValue(aa)(oo1) =
integerAttributeValue(aa)(oo2)) ) =>
oo1 = oo2 )
OPERATIONS
Переменные, составляющие пространство
состояний объектной модели, объявлены в разделе
ABSTRACT_VARIABLES машины ObjectDM и
типизируются в разделе INVARIANT. Так, имена
типов и классов представлены переменными
typeNames, classNames, тип которых – подмножество
множества строк (строки спецификации 10-11).
Атрибуты (переменная attributeNames)
представлены частичной функцией, ставящей в
соответствие уникальному идентификатору
атрибута (натуральному числу) имя атрибута
(строка 12). Типы экземпляров классов (переменная
instanceType) представлены тотальной функцией из
множества имен классов в множество имен типов
(
Некоторые дополнительные необходимые свойства переменных состояния представлены конъюнктивными компонентами инварианта: тип объекта - экземпляра класса есть тип экземпляров этого класса (25-27); для любого объекта и любого определенного атрибута типа этого объекта функция значений атрибута определена на объекте (3034); для любого объекта и любого целочисленного атрибута типа объекта, определенного на объекте и для которого определена нижняя (верхняя) граница, значение атрибута не меньше (не больше) нижней (верхней) границы (35-40); объект однозначно идентифицируется набором своих уникальных атрибутов (41-48). Из всего ЯМД в спецификации рассмотрена единственная операция update обновления значений атрибута в объектах класса. Параметрами операции являются имя класса cls, имя целочисленного атрибута attr типа экземпляров класса, функция exp отвечающая за преобразование атрибута и функция cond, отвечающая условию на значение атрибута. Пусть o – некоторый объект класса cls, для которого определено значение атрибута attr и это значение есть v. Тогда операция update (50-65) изменяет значение атрибута на exp(v) в случае, если выражение cond(v) принимает значение истина и оставляет значение атрибута без изменений в противном случае. Очевидно, такая операция update есть обобщение примера обновления, рассмотренного в разделе 2.2. Действительно, для рассмотренного примера cls есть source, attr есть val, exp(v) = -v, cond(v) = abs(v).
Заметим, что в данной спецификации для простоты не рассмотрены некоторые черты объектной модели, например отношения тип-подтип и класс-подкласс.
Рассмотрим теперь часть соответствующей модели ADM: спецификации, REFINEMENT ArrayDM REFINES ObjectDM ABSTRACT_VARIABLES arrayNames, dimensionNames, cellAttributeNames, arrayDimensions, arrayCellAttributes, cellAtrributeType, nullable, dimLowerBound, dimHigherBound, cells, dimensionValue, integerCellAttributeValue INVARIANT arrayNames: POW(STRING_Type) & dimensionNames: NAT +-> STRING_Type & cellAttributeNames: NAT +-> STRING_Type & arrayDimensions:
arrayNames --> POW(dom(dimensionNames)) & arrayCellAttributes:
arrayNames --> POW(dom(cellAttributeNames)) & cellAtrributeType:
dom(cellAttributeNames) --> BuiltInTypes &
nullable: dom(cellAttributeNames) --> BOOL &
dimLowerBound: dom(dimensionNames) --> INT &
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Имена массивов представлены переменной
arrayNames (строка спецификации 10); имена
измерений – переменной dimensionNames (строка
11); имена атрибутов ячеек массива – переменной
cellAttributeNames (
Дополнительные необходимые свойства переменных состояния представлены конъюнктивными компонентами инварианта: любая ячейка любого массива однозначно идентифицируется набором значений измерений (27-32); для любой ячейки любого массива определены значения всех измерений и значение по крайней мере одного атрибута (33-38).
Аналогично объектной модели рассмотрена единственная операция ЯМД – операция обновления update (40-54). Сигнатура операции совпадает с сигнатурой операции объектной модели. Семантика операции также аналогична: значение v атрибута attr массива cls заменяется на exp(v), если значение cond(v) есть истина и не изменяется в противном случае.
Заметим, что в данной спецификации для простоты не рассмотрены некоторые черты ADM, например, нецелочисленные измерения.
Для формального доказательства того, что машина ArrayDM уточняет машину ObjectDM необходимо построить инвариант уточнения, связывающий переменные машин и добавить его к инварианту уточняющей машины.
Инвариант уточнения выглядит следующим
образом:
множество имен массивов совпадает с
множеством имен классов (строка 1);
множество идентификаторов и имен
измерений и атрибутов ячеек совпадает с
множеством идентификаторов и имен
атрибутов типов экземпляров классов (2);
любому измерению массива соответствует
атрибут типа экземпляра класса,
соответствующего этому массиву (
Основные особенности данной работы состоят в следующем. В качестве исходной модели при отображении используется специфическая модель, основанная на многомерных массивах, СУБД SciDB, язык которой представляет собой комбинацию декларативного SQL-подобного языка и функционального языка, включающего специфические операции над многомерными массивами. В качестве целевой модели используется объектная модель с Datalog-подобным языком запросов (программ) – язык СИНТЕЗ. Для отображения обеспечивается формальное доказательство сохранения информации и семантики операций ЯМД.
Отметим, что результаты работы могут быть с легкостью обобщены и использованы при интеграции в системах, использующих каноническую модель, отличную от языка СИНТЕЗ – например, другую объектную (ODMG) или объектно-реляционную модель (SQL:2003). Результаты также могут быть использованы для интеграции ресурсов, представленных в модели, основанной на многомерных массивах, но отличной от ADM.
Некоторые вопросы отображения требуют дальнейших исследований, например, следует ли иметь в канонической модели при интеграции массив-ориентированных моделей данных операции, связанные с размером порции (chunk size) данных в БД [17].
Дальнейшую работу можно разбить на три этапа: построение трансформации, реализующей изложенное отображение; расширение инструментальных средств поддержки предметных посредников для виртуальной интеграции SciDB-ресурсов: (i) расширение средств регистрации ресурсов в посреднике [19] трансформацией ЯОД ADM в каноническую модель; (ii) создание SciDBадаптера - специального ПО, связывающего исполнительную среду посредников с SciDBресурсами (составной частью адаптера является трансформация ЯМД); применение технологии предметных посредников для решения научных задач в некоторой предметной области над множеством неоднородных ресурсов, включающим SciDB-ресурсы. Благодарности Автор выражает благодарность Л. А. Калиниченко, П. Е. Велихову и А. Е. Вовченко за полезные замечания, высказанные в ходе обсуждения данной работы на семинарах ИПИ РАН. Литература [1] Abrial J.-R. The B-Book: Assigning Programs to Meanings. Cambridge: Cambridge University Press, 1996. [2] Astronomy in ArrayDB. http://trac.scidb.org/rawattachment/wiki/UseCases/Astronomy%20in%20Array DB.pdf
In the paper a mapping of an array-based data model – the SciDB DBMS model - into a canonical model used for virtual or materialized database integration is presented. To be precise, a mapping into an object model - the SYNTHESIS language is considered. The SYNTHESIS language is used as the canonical model in the subject mediator technology.
An aim of the work is developing of a sound theoretical basis for the integration of array-based resources.