Темпоральная модель данных и возможности ее реализации на основе технологии OLAP

Размещено на http://www.allbest.ru/

Темпоральная модель данных и возможности ее реализации на основе технологии OLAP

А.А. Еремеев

А.П. Еремеев

Д.А. Пантелеев

Московский энергетический институт

(Технический университет), Москва

В работе описываются модель представления темпоральных данных, ориентированная на интеллектуальные системы реального времени, и возможности ее реализации на основе технологии OLAP.

Ключевые слова: темпоральная модель данных, технология OLAP, интеллектуальные системы.

Для создания современных интеллектуальных систем, ориентированных на открытые и динамические предметные (проблемные) области, типичным представителем которых являются интеллектуальные системы поддержки принятия решений реального времени (ИСППР РВ) [Вагин и др., 2001], необходимо иметь достаточно развитые средства для представления временных зависимостей в поступающей и хранящейся в системе информации (данных и знаниях). В работах [Еремеев и др., 2003], [Еремеев и др., 2007] рассмотрены различные модели представления временных зависимостей (темпоральные модели) в интеллектуальных системах и методы моделирования темпоральных рассуждений, ориентированные на использование в ИСППР РВ.

ИСППР РВ оперирует, как правило, большими массивами быстро изменяемых данных, поступающих из различных внешних источников (датчиков, сенсоров, оператора или ЛПР - лица, принимающего решения), т.е. имеет дело с динамической информацией, для поддержки которой необходима соответствующая организация баз данных и знаний. Для представления статической информации подходят широко применяемая реляционная модель данных и соответствующие СУБД на ее основе. Однако они плохо подходят в случае динамической информации, так как не учитывают специфику фактора времени и не имеют развитых средств представления информации, актуальной в некоторый момент времени или на некотором заданном временном интервале. В этом случае целесообразно использовать темпоральную модель данных и в качестве средства поддержки таких данных - темпоральную базу данных (ТБД) [Еремеев и др., 2009].

Несмотря на то, что работы в направлении создания ТБД ведутся достаточно долго, на сегодняшний день не принят единый стандарт относительно ТБД и, как следствие этого, не созданы коммерческие системы управления ТБД (см., например, обзор [Кузнецов, 2007]).

В данной работе предлагается темпоральная модель данных и рассматриваются возможности ее реализации на основе концепции хранилища данных (Data Warehouse) и технологии (и среды) OLAP (Online Analytical Processing).

1. Темпоральная модель данных

В темпоральной модели категория времени является базовой сущностью, большинство понятий модели определяются с помощью интервалов времени, т.е. используется интервальное представление времени. Объектом темпоральной модели будем называть любую информационную либо структурную сущность, например, домен, атрибут, кортеж, отношение. Предполагается, что объект О определен на временном интервале I, если для любого момента , значение либо структура O существует. В темпоральной модели структура либо значения любого объекта неограниченно изменяются, версией объекта O будем называть каждое изменение объекта. темпоральный интеллектуальный analytical processing

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

T: .

Будем рассматривать темпоральную модель данных в тесной аналогии с реляционной моделью, поскольку основные сущности обоих моделей совпадают. Возможное расширение реляционной модели предложено Э. Коддом и описано в работе [Кодд, 1996].

Определение домена.

Известно, что в реляционной модели доменом называется множество однотипных значений, например, множество целых чисел или множество дней недели. Домен является простым (simple), если все его значения атомарны (не декомпозируются) [Коннели, 2003]. Домен в темпоральной модели так же удовлетворяет этим требованиям, однако он определен на некотором интервале времени. В общем случае, домен задается набором

,

где I - область определения объекта домена, i₁,…,i_m - области определения версий домена.

Декартово произведение.

Пусть есть n не обязательно различных доменов . В реляционной модели декартово произведение {D_i: i = 1, 2, ..., n} - это множество всех n-кортежей <t₁, t₂, ..., t_n>, таких, что t_iD_i для всех i, где t_i - атрибуты кортежа. Отношение R степени n определяется на этих n доменах, если оно является подмножеством их декартового произведения.

В темпоральной модели для каждого атрибута области определения должно иметься непустое пересечение: , i=1,…,n. Темпоральный кортеж определен на интервале I, если на I определены домены всех атрибутов и значения атрибутов определены в любой момент времени из интервала I.

Отношения.

В реляционной модели отношение состоит из множества кортежей, и каждый кортеж имеет одно и то же множество атрибутов. Если все домены являются простыми, то такое отношение имеет табличное представление со следующими свойствами: не существует дубликатов строк (кортежей); порядок строк и порядок столбцов (атрибутов) являются несущественными; все элементы таблицы являются атомарными значениями.

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

Если U - некоторая совокупность атрибутов некоторого отношения, то U-компонентом кортежа t этого отношения называется множество пар (A:v), полученных путем удаления из t тех пар, которые содержат атрибуты, не принадлежащие U. Причем, .

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

Ключ, как и любой элемент темпоральной модели имеет свою область определения, поэтому для выбора первичного ключа из всего множества возможных ключей, следует выбрать тот, который определен на всем требуемом интервале. Заметим так же, что первичный домен, на котором определен первичных ключ, должен быть задан на области определения БД, то есть

Ограничения целостности темпоральной модели.

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

2. Обработка данных в темпоральной модели

Определим операции для манипулирования n-арными темпоральными отношениями. Соответствующие операции для реляционной модели описаны в [Коннели, 2003], [Зеленков, 1997]. Далее R и S обозначают отношения; A, B, C и т.д. (возможно с индексами) - совокупности атрибутов; c - кортеж соответствующей степени и соответствующими доменами.

Операция THETA-SELECT (ограничение).

Пусть и{<, ?, =, ?, >, ?} - какое-либо из бинарных отношений, применимое к атрибутам A и кортежу c. Тогда R[Aиc] есть множество кортежей из R, A-компоненты каждого из которых находятся в отношении и с кортежем c, причем область определения А-компонентов и с - совпадает.

.

Вместо кортежа c может использоваться другой атрибут или другая совокупность атрибутов B отношения R при условии, что A и B определены на общих доменах. Тогда R[Aиc] - множество кортежей из R, каждый из которых удовлетворяет условию, что его A-компонент находится в отношении и с B-компонентом. Если и представляет собой равенство (распространенный случай), операция THETA-SELECT называется просто SELECT (селекцией).

Операция PROJECTION (проекция).

R[A₁, A₂, ... A_n] - отношение, получаемое путем удаления из R всех столбцов за исключением тех, которые специфицируются атрибутами A₁, A₂, ... A_n, и последующего удаления избыточных строк-дубликатов, причем область определения проекции совпадает с областью определения исходного отношения, т.е.

T(R[A₁, A₂, ... A_n]) = T(R)

Операция THETA-JOIN (тета-соединение).

Пусть заданы отношения R(A, B₁) и S(B₂,C), такие, что B₁ и B₂ определены на общем домене, и пусть и{=, <, <, ?, ?, >, ?,} которое применимо к домену атрибутов B₁, B₂. Тета-соединение R по B₁ с S по B₂ обозначается как R[B₁иB₂]S. Это - конкатенация строк отношения R со строками отношения S, формируемая всякий раз, когда компонент B₁ строки R находится в отношении и с компонентом B₂ строки S. Для темпоральной модели область определения тета-соединения соответствует интервалу, при котором выполнялось отношение и. То есть,

Если отношение и является равенством, операция THETA-JOIN называется EQUI-JOIN (эквисоединением). Только операция EQUI-JOIN дает результат, который обязательно содержит два идентичных столбца (один, продуцированный из B₁, а другой - из B₂). В общем случае допускается использование в качестве и произвольного бинарного отношения, которое применимо к домену атрибутов B₁и B₂.

Операция NATURAL JOIN (естественное соединение).

Данная операция подобна операции EQUI-JOIN за исключением того, что в этом случае удаляются избыточные столбцы, сгенерированные при выполнении соединения. Естественное соединение - это соединение, используемое при нормализации совокупности отношений.

Операция DIVIDE (деление).

Пусть заданы отношения R(A,B₁) и S(B₂,C) такие, что B₁ и B₂ определены на одном и том же домене (доменах). Тогда R[B₁чB₂]S - это максимальное подмножество R[A], такое, что его декартово произведение с S[B₂] включается в R. Для темпоральной модели, зависимости между областью определения задаются следующим образом:

.

3. Хранилища данных и технология OLAP

Для реализации и анализа ТБД предлагается использовать технологию OLAP (Online Analytical Processing) [Codd et al., 1996;]. Рассмотрим основные положения этой технологии. Хотя технология OLAP и не является необходимым атрибутом хранилищ данных (Date Warehouse), эта технология в настоящее время активно применяется для анализа накопленной в хранилище информации.

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

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

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

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

Рис.1. Гиперкуб данных

Используются следующие обозначения. OLAP-куб данных обозначается как множество ячеек H(D, M), соответствующее множествам D, M, где D={d₁, d₂,…, d_n} множество измерений гиперкуба; множество меток измерения d_i; - множество меток гиперкуба; множество фиксированных измерений; множество фиксированных меток. Подмножество OLAP-куба, соответствующее множествам фиксированных значений будем обозначать как . Каждой ячейке OLAP-куба соответствует единственно возможный набор меток измерений . Ячейка может быть пустой (не содержать данных) или содержать значение показателя - меру. Множество мер OLAP-куба H(D, M) обозначается V(H).

Для реализации темпоральной модели данных (темпорального OLAP-куба) предлагается использовать темпоральный OLAP язык - TOLAP [Alejandro et al., 2002]. TOLAP комбинирует возможности языков темпоральных запросов типа TSQL2 или SQL/TP с некоторыми возможностями языков высокого уровня типа HiLog или SchemaLog.

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

Запрос возвращает проекцию кортежей в Services таким образом, чтобы pat свертывался к 'Union'. Переменная pat представляет элемент на самом низком уровне размерности Patient. Кортеж Services соответствует результату, если пациент pat был обслужен доктором doc в день day во время t, и pat был присоединен к учреждению типа 'Union' во время прохождения лечения. Выражение pat[t]>insType:'Union' называется атомом свертки, а Services(doc,proc,pat,day,qty,t) - атомом факта. Это пример запроса с неагрегированными данными. Запросы с агрегатами также могут быть выражены в TOLAP. Например, запрос: “общее количество процедур в неделю”

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

Функция свертки, представленная атомом свертки doc[t] >doctorId:dr реализует тождество на временном интервале, где doctorId - нижний уровень размерности.

TOLAP также позволяет запрашивать метаданные, поддерживая запросы без таблицы фактов в тексте правил, которые называются метазапросами. Пример метазапроса р: “Перечислите периоды, во время которых ни одна кардиохирургия не была доступна”:

Аналогично языку Datalog, правила могут быть скомпилированы в программы.

Базовые программные модули предложенной темпоральной модели данных реализуются в среде OLAP на кафедре прикладной математики МЭИ (ТУ) в плане исследований по тематике разработки методов, моделей и базовых инструментальных средств конструирования ИСППР РВ семиотического типа на основе нетрадиционных логик [Вагин и др., 2008].

Список литературы

1. [Барсегян и др, 2004] Барсегян А.А., Куприянов М.С., Степаненко В.В., Холод И.И. Методы и модели анализа данных: OLAP и Data Mining - СПб.: БХВ-Петербург, 2004.

2. [Вагин и др., 2001] Вагин В.Н., Еремеев А.П. Некоторые базовые принципы построения интеллектуальных систем поддержки принятия решений реального времени // Известия РАН. Теория и системы управления. 2001. № 6.

3. [Вагин и др., 2008] Вагин В.Н., Еремеев А.П. Исследования и разработки кафедры прикладной математики по конструированию интеллектуальных систем поддержки принятия решений на основе нетрадиционных логик // Вестник МЭИ. 2008. № 5.

4. [Еремеев и др., 2003] Еремеев А.П., Троицкий В.В. Модели представления временных зависимостей в интеллектуальных системах поддержки принятия решений // Известия РАН. Теория и системы управления. 2003. № 5.

5. [Еремеев и др., 2007] Еремеев А.П., Куриленко И.Е. Реализация механизма временных рассуждений в современных интеллектуальных системах // Известия РАН. Теория и системы управления. 2007. № 2.

6. [Еремеев и др., 2009] Еремеев А.П., Еремеев А.А., Пантелеев А.А. Использование темпоральных баз данных для систем поддержки принятия решений // Тр. Конгресса по интеллектуальным системам и информационным технологиям “AIS-IT'09”. Научное изд. в 4-х томах. - М.: Физматлит, 2009. Т.1.

7. [Зеленков, 1997] Зеленков Ю. Введение в базы данных. Центр Интернет ЯрГУ. 1997. - http://www.mstu.edu.ru/education/materials/zelenkov/toc.html # 1997

8. [Кодд, 1996] Кодд Э. Ф. Расширение реляционной модели для лучшего отражения семантики. Перевод М.Р. Когаловского. - Журнал «Системы управления базами данных» 1996. № 5. Новая редакция: Сергей Кузнецов, 2009 г.

9. [Коннели, 2003] Коннели Т. Базы данных. - М.: Вильямс, 2003.

10. [Кузнецов, 2007] Кузнецов С.Д., История и актуальные проблемы темпоральных баз данных, 2007. - http://www.citforum.ru/database/articles/temporal/

11. [Alejandro et al., 2002] Alejandro A. Vaisman and Alberto O. Mendelzon, A Temporal Query Language for OLAP:Implementation and a Case Study, In Proceedings of the 26th VLDB Conference, Cairo, Egypt, 2002.

12. [Codd et al., 1996] Codd E. F., Codd S. B., Salley C. T. Providing OLAP to User-Analysts: An IT Mandate, Arbor Software Corp. Papers, 1996.

Размещено на Allbest.ru