Другие журналы

научное издание МГТУ им. Н.Э. Баумана

НАУКА и ОБРАЗОВАНИЕ

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

77-30569/225699 Адаптация темпоральной реляционной модели данных в многомерном пространстве

# 09, сентябрь 2011
Файл статьи: Елисеев_P.pdf (519.41Кб)
авторы: Балдин А. В., Елисеев Д. В.

УДК. 004.652

МГТУ имени Н.Э. Баумана

bal@bmstu.ru

d-eli@mail.ru

Введение

Темпоральные модели данных на базе реляционной модели применимы в системах, в которых структура темпоральных данных не изменяется. Под темпоральными понимаются данные, связанные с определёнными датами или промежутками времени [1]. В темпоральных моделях факты представлены как блоки данных с отметкой времени, которая используется для определения периода времени, когда они были действительны в предметной области и хранились в базе данных.

Известны несколько темпоральных моделей данных на базе реляционной, использующие отметки времени с кортежами, которые были предложены Р. Снодграсом [2, 12], К. Дженсеном [2, 13], Дж. Бен-Зви [2], и использующие отметки времени со значениями атрибутов, которые были предложены C. Гадией [2], Е. МакКензи [2]. Эти темпоральные модели применимы в системах, в которых структура темпоральных данных не изменяется. При этом темпоральные модели на базе реляционной характеризуются избыточностью хранения данных, за исключением моделей с темпоральностью на уровне атрибутов, которые используют отношения не в первой нормальной форме, что вызывает трудности реализации на современных реляционных базах данных.

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

1 Темпоральные реляционные модели с изменяемой структурой данных

Рассмотрим динамично меняющиеся предметные области, деятельность в которых основана на накопленной истории выполненных операций. Примерами таких предметных областей являются: система управления предприятием [3, 4], система управления персоналом [5], финансовые приложения, страховые приложения и ряд других, которые обладают следующими особенностями:

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

2.      Предметная область содержит темпоральные данные.

3.      Необходимо хранить историю изменения темпоральных данных в течение длительного периода времени и анализировать изменения во времени различных показателей.

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

Рассмотрим обобщённую модель представления темпоральных данных. Пусть отношение с темпоральными кортежами R имеет набор атрибутов , где T—атрибут, определяющий отметку времени. Данная модель является самым естественным и наиболее часто используемым способом представления отношений с темпоральными кортежами [13]. В этом случае отношение состоит из темпоральных кортежей, которые определяют состояния объектов предметной области.

На рис. 1 представлены графики зависимости размера отношения VОТН от количества кортежей в отношении при неизменной схеме отношения (рис. 1.а) и при изменяющейся (рис. 1.b).

Рис. 1. Зависимость размера отношения с темпоральными кортежами от количества кортежей в отношении:
а) при не изменяющейся схеме отношения; b) при изменяющейся схеме отношения.

На графиках (рис. 1) ось n - количество кортежей в отношении. Если схема отношения постоянна, то размер отношения растёт линейно при увеличении количества кортежей, , где k – количество атрибутов в схеме отношения (рис. 1.а).

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

Изменение схемы отношения изображено на графике (рис. 1.b) при количестве кортежей равном n=n1 и n=n2. При изменении схемы отношения, когда n=n1 размер отношения увеличивается от V1b к V2b, и увеличивается угол наклона графика. Аналогично происходит, когда n=n2. Математически зависимость размера отношения от количества кортежей при изменяющейся схеме отношения представлена в формуле 1.

,                              (1)

Так как после каждого изменения отношения увеличивается угол наклона прямой, то размер отношения растёт быстрей. На рис. 1 при количестве кортежей в отношении n=n2, V4a<V4b на величину . Из формулы 1 видно, что размер отношения зависит от того, когда произошло изменение его схемы. Чем больше кортежей содержит отношение, тем больше его размер будет после добавления новых атрибутов.

Таким образом, применение стандартных темпоральных моделей на базе реляционной приводит к следующим недостаткам:

1)       Увеличение избыточности хранения информации по мере изменения структуры данных.

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

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

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

2 Темпоральная реляционная модель с изменяемой структурой данных на базе многомерного пространства

2.1 Структура многомерного пространства описывающего темпоральную реляционную модель данных

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

«МИВАРное» пространство (Многомерное Информационное ВАРьирующееся  пространство) - самоорганизующееся динамическое многомерное объектно-системное дискретное пространство унифицированного представления данных и правил [6].

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

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

Структура многомерного пространства для описания темпоральной реляционной модели данных с изменяемой структурой приведено в работе [7]. Многомерное пространство, описывающее темпоральную реляционную модель состоит из пяти основных осей:

1)      V – множество сущностей предметной области.

2)      S – множество атрибутов сущностей предметной области.

3)      ID – множество идентификаторов записи отношения. Множество идентификаторов записей отношения будем считать множество натуральных чисел. В отношении идентификатор выделяет конкретную запись. Поэтому в каждом отношении идентификатор записи не должен повторяться, должен быть уникальным.

4)      T – множество времён изменений состояний модели данных. Введём на множестве Т отношение порядка  т.е. когда событие t2 произошло не раньше события t1.

5)     U – множество модификаторов. Содержит идентификатор пользователя, который произвёл изменение значения точки многомерного пространства.

Тогда многомерное пространство будет иметь следующий вид:

На рис. 2 представлено подпространство (V,S,ID), определяющее реляционную модель данных, а выделенная точка хранит значение атрибута sj в кортеже n отношения vi.

Рис. 2. Подпространство представления реляционной модели

2.2 Алгебра многомерных матриц для пространства, описывающего темпоральную реляционную модель

Определение: Р-мерная матрица (многомерная матрица) – совокупность элементов  где индексы  принимают значения от 1 до  соответственно.

Р-мерная матрица содержит  элементов и обозначается

 [8].

В работе [9] описана алгебра многомерных матриц  для пространства, содержащего темпоральную реляционную модель. Е – множество многомерных матриц, а  - множество операций.

Множество многомерных матриц определяется , где СМ  - многомерная матрица, представляющая всю темпоральную реляционную модель данных, а  - операция объединения подпространств, определяющих многомерные матрицы, рассмотренная ниже.

Алгебра многомерных матриц содержит 6 операций: объединение, пересечение, разность подпространств многомерных матриц, срез, срез первых, срез последних.

Пусть даны 2 многомерные матрицы


1)       Объединение, пересечение и разность подпространств многомерных матриц определяются следующим образом:

.

.

2)       Срезом многомерной матрицы  называется многомерная матрица следующего вида:

3)       Срезом первых многомерной матрицы  называется многомерная матрица следующего вида:

 - класс эквивалентности по отношению ,

 - элемент множества  с минимальным значением координаты t.

4)       Срезом последних многомерной матрицы  называется многомерная матрица следующего вида:

 - элемент множества  с максимальным значением координаты t.

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

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

3 Операторы преобразования между реляционной моделью данных и многомерным пространством

3.1 Формальное описание реляционной модели

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

RD={r1, r2, …, rK}, где K – количество отношений в модели,

rii-ое отношение, .

ri=(Ri, Dri), где Ri – схема отношения ri,

Ri={RiA1, RiA2, …, RiAPi}, RiAj – атрибуты схемы отношения Ri, .

Dri – множество кортежей отношения ri.

По аналогии с формальным описанием реляционной модели данных обобщённую модель представления темпоральных данных HD можно представить следующим образом:

HD={h1, h2, …, hK}, где K – количество отношений в модели RD.

hi=(Hi, Dhi), где Hi=RiÈ{Период, Идентификатор}.

Dhi – множество кортежей отношения hi.

HD описывает историю изменения кортежей отношений реляционной модели RD.

3.2 Преобразование реляционной модели к многомерному пространству

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

Введём оператор преобразования  реляционной модели данных в многомерное пространство.

. При этом выполняются следующие действия:

1.      , где vri – название отношения ri, .

2.      .

3.      Т.к. Dri – конечное множество, то существует взаимно однозначное соответствие , где ,  - мощность множества Dri.

      Тогда .

4.      T={t0}.

5.      U={u0}.

6.      , , , ,

                        где  - значение атрибута RiAj в кортеже n отношения ri.

Переход от реляционной модели данных к многомерному пространству с помощью введённого преобразования  позволяет описывать процесс изменения рассматриваемой модели. Изменение модели происходит путём добавления новых точек в многомерном пространстве. Координаты точек определяют структуру данных. В результате, изменение структуры данных и изменение самих данных в отношениях с точки зрения многомерного пространства выполняются одновременно. Такое представление реляционной модели позволяет вести историю изменения вплоть по каждому атрибуту в отношении отдельно, что минимизирует общее количество отношений в темпоральной реляционной модели.

3.3 Преобразование многомерного пространства в реляционную модель

Т.к. все изменения с моделью предметной области происходят в многомерном пространстве, то со временем модель изменяется от первоначальной. Для получения изменённой реляционной модели определим преобразования  и .

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

. При этом выполняются следующие действия:

1.      .

2.      .

3.      .

4.      ri=(Ri, Dri), RD={ri}, .

Введём оператор преобразования  многомерного пространства в историю изменения отношений реляционной модели. Данное преобразование получает из многомерного пространства таблицы, описывающие историю изменения кортежей в отношении.

. При этом выполняются следующие действия:

1.      .

2.      .

3.      .

4.      hi=(Hi, Dhi), HD={hi}, .

4 Методика адаптации темпоральной реляционной модели данных в многомерном пространстве

Методика адаптации темпоральной реляционной модели данных в многомерном пространстве представлена на рис. 3.

Рис. 3 Методика адаптации темпоральной реляционной модели данных в многомерном пространстве

Методика состоит из трёх этапов:

1 этап. Преобразование исходной реляционной модели данных в многомерное пространство.

Исходными данными для построения темпоральной реляционной модели предметной области в многомерном пространстве является реляционная модель данных RD0=(r01, r02, …, r0k). RD0 с помощью оператора  преобразуется в многомерную модель данных: .

2 этап. Изменение модели предметной области в многомерном пространстве.

Изменение модели предметной области проводится в многомерном пространстве. Процесс изменения реляционной модели происходит путём добавления новых точек в многомерное пространство. Координаты точек определяют структуру данных.

На рис. 3 изменение многомерного пространства изображено двумя блоками:

1)       «Анализ и формализация изменений объектов предметной области». Результатом выполнения данной функции является изменение многомерного пространства: либо изменяется структура пространства (добавляются новые оси), либо происходит изменение множеств, определяющих оси пространства (добавляются новые элементы в эти множества).

2)       «Ввод новых данных и изменение данных». Результатом выполнения данной функции является сохранение значений новых точек в многомерном пространстве.

Процесс изменения модели предметной области является итерационным (рис. 4), т.е. каждое следующее состояние модели предметной области зависит от предыдущего: Ci=δ(Ci-1), где  – функция, задающая изменения текущего состояния модели от предыдущего.

Рис. 4. Процесс изменения модели предметной области

Кроме того, рассматриваемый процесс протекает во времени, т.е. каждое состояние модели предметной области действительно в определённом промежутке времени: . Преобразование реляционной модели данных в многомерное пространство позволяет описать процесс изменения модели во времени. При этом состояние модели данных получается из многомерного пространства посредством использования операции «Срез последних»: .

3 Этап. Выполнение запросов к многомерному пространству.

Данный этап состоит из трёх подпунктов.

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

3.2 Преобразование выделенного подпространства  в реляционную модель данных. С помощью операторов  и  выделенное подпространство преобразуется в реляционную модель данных RDi=a()=(ri1, ri2, …, rik), либо в обобщённую модель представления темпоральных данных HDi= β()=(hi1, hi2, …, hik).

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

Таким образом, методика включает однократное преобразование начальной реляционной модели данных в многомерное пространство и дальнейшую работу с этой многомерной моделью: ввод новых данных, изменение структуры данных и выполнение запросов к многомерному представлению темпоральной реляционной модели с изменяемой структурой данных.

Заключение

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

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

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

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

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

  1. История и актуальные проблемы темпоральных баз данных [Электронный ресурс] / Костенко Б.Б., Кузнецов С.Д., 2007 – Режим доступа: http://citforum.ru/database/articles/temporal/4.shtml, (Дата обращения: 14.08.2011)
  2. Исследование и разработка темпоральной модели данных в рамках МИС Интерин PROMIS [Электронный ресурс]/ Базаркин А. Н., 2009 - Режим доступа: https://edu.botik.ru/proceedings/psta2009/v2/037-Bazarkin.Research_and.pdf, (Дата обращения: 14.08.2011)
  3. Информационная управляющая система МГТУ им. Н.Э. Баумана «Электронный университет»: концепция и реализация / Т.И. Агеева, А.В. Балдин, В.А. Барышников и др.; [под ред. И.Б. Фёдорова, В.М. Черненького]. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2009. – 376 с.
  4. Информационные технологии в инженерном образовании / под ред.С.В. Коршунова, В.Н. Гузненкова. – М.: Изд-во  МГТУ им. Н.Э. Баумана, 2007. – 432 с.
  5. «Персонал – Кадры» – адаптивная функционально-развиваемая система информационной поддержки управления кадрами [Электронный ресурс] - Режим доступа: http://www.personal.bravosoft.ru/doc/doc002.htm, (Дата обращения: 14.08.2011)
  6. Варламов О.О. Эволюционные базы данных и знаний для адаптивного синтеза интеллектуальных систем. Миварное информационное пространство. - М: Радио и связь, 2002.-286 с.
  7. Адаптируемая модель данных на основе многомерного пространства [Электронный ресурс] / Балдин А.В., Елисеев Д.В. - Электрон. журн. – М.: «Наука и образование: электронное научно-техническое издание», 2010 – Режим доступа:  http://technomag.edu.ru/doc/161410.html, свободный, (Дата обращения: 14.08.2011)
  8. Реализация матричной модели данных в иерархических структурах [Электронный ресурс] / Сергеев В. П. - Электрон. журн. – Математическая морфология., 2007 – Режим доступа:  http://www.smolensk.ru/user/sgma/MMORPH/N-14-html/sergeev/sergeev.htm, свободный, (Дата обращения: 14.08.2011)
  9. Алгебра многомерных матриц для обработки адаптируемой модели данных [Электронный ресурс] / Балдин А.В., Елисеев Д.В. - Электрон. журн. – М.: «Наука и образование: электронное научно-техническое издание», 2011 – Режим доступа:  http://technomag.edu.ru/doc/199561.html, свободный, (Дата обращения: 14.08.2011)
  10. Гарсиа-Молина, Гектор, Ульман, Джеффри, Д., Уидом, Дженнифер Г   Системы баз данных. Полный курс. : Пер. с англ. — М.: Издательский дом "Вильямс", 2003. — 1088 с.
  11. Developing Time-Oriented Database Applications in SQL, Richard T. Snodgrass, Morgan Kaufmann Publishers, Inc., San Francisco, July, 1999, 504 pages.
  12. Jensen C. S. and R. T. Snodgrass, Semantics of Time-Varying Information // Information Systems, Vol. 21, No. 4, 1996, pp. 311–352. [Электронный ресурс], Режим доступа: http://www.cs.arizona.edu/~rts/pubs/ISJune96.pdf, свободный, (Дата обращения: 14.08.2011)
  13. Andreas Steiner. A Generalisation Approach to Temporal Data Models and their Implementations [Электронный ресурс], 1998 - Режим доступа: http://www.timeconsult.com/Publications/diss.pdf, (Дата обращения: 14.08.2011)
Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2019 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)