Программные продукты и системы

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

Представление темпоральных данных на основе реляционной БД

В широком смысле под темпоральными данными понимаются произвольные данные, явно или неявно связанные с определенными датами (моментами) или промежутками времени (интервалами). ТБД – это БД, хранящие темпоральные данные, причем известно правило интерпретации временных меток и интервалов для конкретной СУБД [3]. Таким образом, в темпоральной СУБД учитываются специфическая природа времени и изменчивость данных с течением времени.

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

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

Первый тип представления является примитивным, так как отсутствует какое-либо явное моделирование темпоральных данных. Каждая операция изменения данных update уничтожает предыдущую копию. Недостаток метода в том, что по сути темпоральная информация не поддерживается, а достоинство – в невысоких требованиях к хранилищу данных. Средством информирования пользователя о наличии изменений данных может выступать логический атрибут: его значение равно true при добавлении новой записи и false – при обновлении.

Второй тип представления предполагает добавление в исходное отношение дополнительных атрибутов, отвечающих за версионность записи. Это могут быть как простой счетчик записей, так и пара значений (Start_date, End_date), указывающих временной диапазон (интервал) актуальности записи. Пример такого представления приведен в таблице.

Это наиболее распространенный способ представления темпоральной информации. Достоинствами его являются простота реализации и полнота исторической информации, недостатками – необходимость явного представления времени в БД, отсутствие контроля со стороны СУБД разработчиков, усложнение ключа исходной таблицы и индексов. Кроме того, в случае нескольких темпоральных атрибутов в одном отношении происходит дублирование информации аналогично дублированию статических атрибутов. Главный недостаток данного метода применительно к ИСППР РВ в отсутствии языка запросов к темпоральной информации со стороны блока логического вывода, что делает этот метод непригодным для ИС типа ИСППР РВ.

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

Четвертый тип представления темпоральной информации самый громоздкий. Он предполагает создание отдельного отношения для каждого объекта, хранящего исторические данные, и является реализацией известной модели темпоральных объектов с абстрактным идентификатором [5]. При данном подходе возможно в полной мере моделировать темпоральную структуру атрибутов, однако моделирование доменов и отношений недоступно. Методы на основе этого подхода позволяют реализовать намного более сложную логику темпоральных запросов, чем уже рассмотренные, но для ИСППР РВ, ориентированных на управление и мониторинг сложных многокомпонентных систем (объектов), они не подходят, так как расходы памяти и вычислительных ресурсов на хранение и обработку информации слишком велики.

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

Шестой тип – альтернативная реализация предыдущего, ориентированного на упрощение представления связи «многие ко многим». Идея метода состоит в том, что, кроме интервала времени, в отношение добавляется атрибут с номером версии. При операции «естественное соединение» между отношениями для каждой пары записей проверяется номер версии, что намного проще анализа временных интервалов.

Краткий анализ различных подходов и методов представления темпоральной информации на основе РБД позволяет утверждать, что для динамических ИС типа ИСППР РВ эти методы неприменимы. Известные подходы к реализации ТБД с использованием классической реляционной СУБД, как правило, ведут к громоздким, плохо масштабируемым реализациям и применимы для очень узкого круга задач.

Использование языка XML

С помощью языка разметки XML для хранения темпорального атрибута можно обойти требо- вание атомарности, хотя это и требует дополнительной информации о структуре XML. По своей природе XML-документ обладает бесконечной вложенностью и может быть плохо структурированным. Эта особенность позволяет использовать его для моделирования временной оси в темпоральной модели. Для хранения темпоральных атрибутов в реляционной таблице Microsoft SQL Server 2005 позволяет описать структуру XML, удобную для моделирования времени, с помощью XML Schema Definition и назначить ее атрибуту в реляционной таблице. Таким образом осуществляется контроль над структурой XML, типами тэгов и атрибутов.

Рассмотрим пример использования XML для моделирования темпоральной структуры в Microsoft SQL Server 2005. Создание схемы XML и добавление ее к объектам сервера осуществляются с помощью команды T-SQL CREATE XML SCHEMA. Продемонстрируем задание схемы для темпорального атрибута:

CREATE XML SCHEMA COLLECTION dbo.sample_xsd AS ‘<xs:schema targetNamespace="http://tempuri.org/XMLSchema.xsd" elementFormDefault="qualified" xmlns="http://tempuri.org/XMLSchema.xsd" xmlns:mstns="http://tempuri.org/XMLSchema.xsd" xmlns:xs="http://www.w3.org/2001/XMLSchema"> <xs:element name="temporal_attribute"> <xs:complexType id="temporal_type"> <xs:sequence id="history_sequence" minOccurs="1" maxOccurs="unbounded"> <xs:element name="atomic_value" minOccurs="1" maxOccurs="unbounded"> <xs:complexType id="atomin_type"> <xs:attribute name="id" type="xs:integer" /> <xs:attribute name="value" type="xs:string" /> <xs:attribute name="time_stamp" type="xs:dateTime"> <xs:annotation> <xs:documentation>Time stamp for presentation single point of time. </xs:documentation> </xs:annotation> </xs:attribute> <xs:attribute name="beginnig_of_period" type="xs:dateTime"> <xs:annotation> <xs:documentation> Time stamp for presentation a beginning of time period. </xs:documentation> </xs:annotation> </xs:attribute> <xs:attribute name="end_of_period" type="xs:dateTime"><xs:annotation> <xs:documentation> Time stamp for presentation a finishing of time period. </xs:documentation> </xs:annotation> </xs:attribute> </xs:complexType> </xs:element> </xs:sequence> </xs:complexType> </xs:element> </xs:schema>’

Данная схема позволяет хранить список изменяющихся значений с временными метками. Создание таблицы с атрибутами типа XML также не представляет сложности:

CREATE TABLE xml_example_table (Record_ID int primary key, Temporal_Attribute XML(sample_xsd)).

Как уже отмечалось, к элементам типа XML можно обращаться при помощи запросов XQuery. Это позволяет смоделировать любые необходимые отношения между временными интервалами, которыми оперирует временная логика. Следующий пример демонстрирует извлечение записей из таблицы, удовлетворяющей условию, сформулированному на базе интервальной логики Аллена: «Найти все периоды жизни персонажа, пересекающиеся с периодом working» (заметим, что данный запрос крайне трудно было бы сформулировать на языке SQL):

SELECT Temporal_Attribute.query

(‘for $p in /temporal_attribute/atomic_value

where $p/@beginnig_of_period < /temporal_attribute/ atomic_value[@value=’working’]/@end_of_period

 and $p/@end_of_period> /temporal_attribute/ atomic_value [@value=’working’]/@beginnig_of_period’)

as life_periods from xml_example_table

В работе [6] исследованы различные варианты использования XML для создания эффективных темпоральных моделей для пользовательских приложений. Таким образом, подход на основе использования XML позволяет создать темпоральную структуру для любых атрибутов. При этом исключается дублирование данных и сохраняется атомарность значений атрибутов, однако серьезно усложняется анализ полей типа XML и возникает необходимость в усложнении языка запросов для выборки данных, что ведет к снижению производительности системы. Данный фактор сильно ограничивает XML-представление темпоральной информации в ИС.

Низкоуровневое представление темпоральной информации

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

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

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

Эта задача решается с помощью построения в координатах на плоскости или в координатах «время–значение» особых кривых, которые при заданном приближении могут охватить сколь угодно малую окрестность любой точки (например, кривая Гильберта). Таким образом, физически располагая данные на устройстве хранения в заданном порядке, можно значительно сократить дисковые операции при выборке данных. Это имеет решающее значение для ИС реального времени типа ИСППР РВ.

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

Язык запросов. Как пространственные, так и временные данные для собственной обработки используют свои диалекты языка SQL (к сожалению, язык темпоральных запросов до сих пор не включен в стандарт). Между языками запросов РБД и ПБД или ТБД существует ряд отличий [7]. Так, пространственные запросы не имеют фиксированного набора операторов и пространственные данные не могут естественным образом представляться в плоской структуре, поэтому результаты часто носят лишь приближенный характер. Для проверки истинности условий пространственных запросов требуются значительные вычислительные ресурсы, и алгоритмы исполнения подобных запросов существенно сложнее реляционных. Запросы могут быть следующих типов: обновление, выборка (подразделяются на точечные запросы и запросы диапазонов и областей), пространственные (темпоральные) соединения, простран- ственные (темпоральные) агрегаты.

Отметим, что построение собственного языка запросов является ключевым преимуществом для использования ТБД в ИСППР РВ, так как машина вывода в данном случае общается на одном языке с БД, что существенно упрощает разработку подобных систем и повышает их производительность.

Применение OLAP-технологии

Рассмотрим темпоральные аспекты в хранилищах данных (ХД) и их воздействие на среду OLAP (On-Line Analitical Processing) [8].

ХД можно охарактеризовать как объектно-ориентированный, интегрируемый, поддержива­ющий временной фактор и долговременный (неразрушающийся) набор данных для использования в ИС. В дополнение к ХД в ИСППР могут применяться различные приложения для поддержки принятия решений. Использование при этом OLAP-технологии многомерного анализа данных позволяет дополнить стандартные сред- ства ХД по подготовке различных отчетов средствами анализа и интерактивного доступа к данным. Предлагается расширение существующих сред ХД/OLAP средствами оперирования темпоральными данными. Для этого дополнительная информация о таких данных должна содержаться в репозитории метаданных, сохраняя базовую схе- му ХД.

Сервер OLAP должен быть в состоянии выполнять темпоральные запросы. При использовании этого вида запросов могут произойти некоторые события, например, ряд элементов станут недопустимыми в определенное время. Решить проблему помогут цветные таблицы для явного представления подобных ситуаций.

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

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

Обобщенная среда (архитектура) OLAP (рис. 1) включает три уровня: клиент (пользовательский интерфейс), воспринимающий запросы пользователя; сервер, осуществляющий обработку информации (данных); компонент для хранения данных, состоящий из ХД (Date Warehause, DWH) и репозитория метаданных и предоставляющий информацию о фактах, размерностях и иерархиях.

Сервер OLAP принимает запрос (шаг 1) и получает метаинформацию о выбранном кубе и соответствующих иерархиях (шаги 2, 3), заносит запрос в ХД (шаг 4), получает результат (шаг 5) и возвращает его клиенту (шаг 6), а тот передает результат пользователю. При последующем анализе (шаг 7) сервер OLAP использует метаинформацию.

Навигационный доступ осуществляется с помощью команд ROLL-UP и DRILL-DOWN, причем изменения происходят в выбранной иерархии в соответствии с уровнем детализации. Представление результатов может быть как в двухмерном виде (таблица), так и в трехмерном (вложенные таблицы). Элементы размерностей имеют свойство снимка БД. Ребра дерева иерархии снабжены сроком действия промежутков времени. Самая мелкая грануляция размерности «время» должна выбираться как единица границ интервала. При этом родительские вершины дерева – это строки, дочерние – столбцы, а элементы соответствующей матрицы – интервалы.

В ТOLAP допустимы темпоральные запросы. Язык запросов расширяется условием WITH TIME ON DIMENSION , определяющим размерности, на которых должен базироваться OLAP-процесс. Вследствие этого становятся возможными выбор временной версии размерности и инициирование процедуры анализа данных с учетом произошедших изменений.

Архитектура OLAP, ориентированная на обработку темпоральных запросов, представлена на рисунке 2. Изменения выделены темным фоном: в репозитории метаданных дополнительно будут храниться сроки (интервалы) действия; сервер должен понимать темпоральные запросы и хранить метаданные с информацией о версии. Сервер принимает темпоральный запрос (шаг 1) от клиента, интерпретирует его и определяет, какие измерения для какой даты должны использоваться. В репозитории метаданных решается вопрос о допустимых сущностях к требуемой дате (шаг 2), определяется соответствующая версия информации (шаг 3), на основе чего сервер делает запрос к ХД (шаг 4) и получает результат (шаг 5). Компонент представления должен показать пользователю, какие данные затронуты темпоральными аспектами (шаги 6 и 7). Для этого используются цветной фон и дополняющая изображение легенда.

В настоящее время описанные средства представления и оперирования темпоральной информацией с использованием ТБД и OLAP-техноло­гии реализуются в составе базовых инструментальных средств конструирования ИСППР РВ для мониторинга и управления сложными объектами и процессами типа объектов энергетики и транспортных систем.

Литература

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

2. Еремеев А.П., Еремеев А.А., Пантелеев А.А. Темпоральные базы данных и их применение в интеллектуальных системах // Интеллектуальные системы: коллектив. монография. Вып. 4; [под. ред. В.М. Курейчика]. М.: Физматлит, 2010. С. 253–276.

3. Кузнецов С.Д. История и актуальные проблемы темпоральных баз данных. 2007. URL: http://www.citforum.ru/data­base/articles/temporal/ (дата обращения: 01.09.2010).

4. Kimball R., Ross M. The Data Warehouse Toolkit: The Complete Guide to Dimensional Modeling (Second Edition). John Wiley & Sons. 2002, pp. 188–198.

5. Петухова Н. Проблемы обеспечения информационной безопасности в темпоральных базах данных // Transport and Telecommunications. 2006. № 03. С. 30–32.

6. Fusheng Wang et al. Using XML to Build Efficient Transaction-Time Temporal Database Systems on Relational Databases, 2006. URL: http://www.cs.ucla.edu/~zaniolo/pa­pers/icde06xml.pdf (дата обращения: 01.09.2010).

7. Шекхар С., Чуалуа С. Основы пространственных баз данных. М.: Кудиц-образ, 2004. 322 с.

8. Herden O. TOLAP: Temporal Online Analytical Processing // International Baltic Conference on Databases and Information Systems 2, 2002, pp. 55–66.