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

На правах рукописи

Бакулева Марина Алексеевна

МОДЕЛИ И АЛГОРИТМЫ АВТОМАТИЗАЦИИ ПРОЕКТИРОВАНИЯ СТРУКТУР ХРАНИЛИЩ ДАННЫХ ДЛЯ АНАЛИТИЧЕСКОЙ ОБРАБОТКИ ЧИСЛОВЫХ ПОКАЗАТЕЛЕЙ

Специальность 05 13 12 - Системы автоматизации проектирования (технические системы)

Автореферат диссертации на соискание ученой степени кандидата технических наук

0031В

Рязань - 2007

003161042

Работа выполнена на кафедре систем автоматизированного проектирования вычислительных средств (САПР ВС) ГОУ ВПО «Рязанский государственный радиотехнический университет»

Научный руководитель: кандидат технических наук, доцент Телков Игорь Анатольевич

Официальные оппоненты:

доктор технических наук, профессор Цветков Игорь Анатольевич

кандидат технических наук, доцент Пресняков Александр Николаевич Ведущая организация: ГНИИ ИТТ «Информика», г Москва

Защита состоится 2 ноября 2007г в 12 часов на заседании диссертационного совета Д212 211 02 в ГОУ ВПО «Рязанский государственный радиотехнический университет» по адресу 390005, г Рязань, ул Гагарина, д 59/1

С диссертацией можно ознакомиться в библиотеке Рязанского государственного радиотехнического университета

Автореферат разослан 29 сентября 2007 г

Отзывы на автореферат в двух экземплярах, заверенные печатью организации, просим направлять по адресу 390005, г Рязань, ул Гагарина, д 59/1, Рязанский государственный радиотехнический университет

Ученый секретарь диссертационного совета кандидат технических наук, доцент

И А Телков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

ХД являются основным источником данных оперативно-аналитических подсистем (On-line analytical processing system — OLAP-систем) современных систем поддержки принятия решений (СППР) Создание средств автоматизации проектирования структур ХД и предварительной обработки данных для анализа является важной задачей, поскольку от скорости и корректности этого процесса напрямую зависит способность информационной системы поддерживать (сопровождать) процессы принятия решений

В работах Р Кимбала, Б Инмона, М С Куприянова, Б Маркова рассматриваются методы построения ХД на основе реляционной модели В работах А Кэмбла, Д Селко метод построения модели основан на теории множеств Многомерная модель данных приводится в работе Э Франкони, У Сатлера, JI Черняка Некоторые из перечисленных методов применяются для автоматизации формирования многомерных представлений данных

Однако на данный момент не решена конкретная задача формализации процесса трансформации реляционной БД, нормализованной и зачастую распределенной архитектуры, в удобную с точки зрения анализа форму ХД Потребность оперативной обработки данных ХД (содержащих порядка ю7 записей) приводит к необходимости создания специализированных аналитических решений Для достижения приемлемого быстродействия (время ответа не более 5 секунд) необходимо разработать способ представления данных, адаптированный к условиям оперативного анализа

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

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

Объект исследования. Объектом исследований, проводимых в рамках диссертационной работы, является ХД и его взаимодействие с системами оперативного анализа числовых данных

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

• ускорение процесса проектирования ХД,

• повышение скорости аналитической обработки данных ХД Основные задачи. В работе поставлены следующие основные задачи

• разработать математическую модель реляционного ХД,

• разработать математическую модель многомерного ХД,

• разработать математическую модель операций над многомерным ХД,

• разработать алгоритмы, автоматизирующие процесс построения ХД на основе предложенных моделей,

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

• разработать алгоритмы OLAP на основе предложенной структуры,

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

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

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

• предложены новые модели реляционного и многомерного ХД на основе тензорного аппарата,

• разработан метод аналитической обработки данных ХД, основанный на вейвлет—преобразовании,

• разработан алгоритм автоматизации процесса проектирования ХД на основе разработанных моделей Основным преимуществом данного алгоритма является снижение временных затрат на разработку ХД и автоматизация рутинных операций по описанию разнообразных связей исходной БД и проецированию соответствующих отношений в ХД,

• разработаны алгоритмы агрегации и анализа данных ХД Отличие от известных заключается в использовании кратномасштабного анализа,

• разработаны алгоритмы ретроспективного анализа Отличие от известных алгоритмов, прежде всего - в большей производительности, полученной за счет применения сигнатурного поиска

Практическая ценность и внедрение результатов работы.

Практическая ценность полученных результатов состоит в следующем

• Создан комплекс программных средств на основе разработанного алгоритма автоматизации проектирования структур ХД, позволяющий сократить сроки проектирования ХД На основе данного комплекса в научно-производственном предприятии «Эльф 4M» (г Рязань) произведена реконструкция системы информационного обеспечения производственной деятельности предприятия

• Созданный комплекс программных средств по обработке данных ХД является инструментом, обеспечивающим высокую скорость аналитической обработки большого числа хранимых данных Внедрение разработанного комплекса значительно повысило эффективность работы научно-производственного предприятия «Эльф 4M», масштабы производства которого охватывают 12 стран (БД содержит »500000 записей) Созданный программный комплекс предоставляет руководителю актуальную информацию о темпах производства, географии сбыта, а также векторе развития предприятия

• Созданный программный комплекс используется в ООО «Торгтек» (г Рязань) для оперативной обработки отчетной и аналитической информации

• Результаты, полученные в диссертационной работе, представляют часть НИР (НИР № 10-06Г (РНТП 3 2 3 7637) «Разработка нормативной базы, информационного обеспечения и регламентов открытой информационно-образовательной среды для дистанционной подготовки, переподготовки и повышения квалификации специалистов в области ИПИ (CALS) и CASE-технологий», НИР 11-06Г (РНТП 3 2 3 7652) «Интегрированная автоматизированная информационная система управления качеством образования ВУЗа»), проводимых РГРТУ

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

Апробация результатов диссертации. Результаты, полученные в рамках работы над диссертацией, докладывались на 10-й Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании», Рязань, 2005 г, 2-й Международной научно-практической конференции «Информационная деятельность проблемы науки и практики», Киев, 2005 г, 14-й Международной научно-технической конференции «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций», Рязань, 2005 г ,

11-й Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании», Рязань, 2006 г, 12-й Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании», Рязань, 2007 г

Публикации. Основные результаты диссертации опубликованы в 11 работах, из них 2 работы опубликованы в изданиях, рекомендованных ВАК

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, библиографического списка (82 источника), изложенных на 131 странице (содержит 10 таблиц, 53 рисунка), и 3 приложения Общий объем диссертации 147 страниц

СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность темы диссертационной работы, изложены цель и соответствующие ей задачи, приведена структура работы

Первая глава посвящена рассмотрению вопросов проектирования ХД Подчеркивается важная роль хранилища в СППР как основного источника данных для оперативного анализа (OLAP) Далее описываются отличия традиционных БД от ХД, главным из которых является упразднение требований нормализации Преимущество по обеспечению оперативности заключается в том, что ХД, как правило, не имеют никакого отношения к третьей нормальной форме, соответственно описание ХД средствами реляционной алгебры, которая создавалась как инструмент нормализации БД, становится достаточно проблематичным Поэтому далее приводится описание и анализ существующих подходов к моделированию ХД (обобщенная многомерная модель Энрико Франкони и Ананда Кэмбла, схема «звезда» и «снежинка», куб Грея, модель Кабиббо и Торлоне, многомерная модель фактов Голфарелли) с выводом о том, что работа по созданию модели ХД, объединяющей все этапы его проектирования является актуальной и востребованной

Далее формулируются основные проблемы проектирования

1 Руководителю, принимающему решения, необходимы самые разнообразные отчеты, причем каждый раз новые Однако, даже хорошо подготовленный пользователь, успешно справляясь с операциями поиска и сортировки, не может правильно объединять таблицы Существуют разнообразные инструменты (например, Crystal Reports, Reporting Services, Component One, Fast Report Studio), интерфейс которых достаточно прост, чтобы непрофессионалы в области информационных технологий могли готовить отчеты Однако в этом случае структура ХД должна быть понятна пользователям

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

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

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

Для решения задач автоматизации рассматривается возможность применения современной методология проектирования ХД — Dimensional Однако проектирование ХД на основе модели Dimensional требует выбора так называемого «центрального вопроса», на практике таких вопросов может быть достаточно много, следовательно, под каждый из них необходимо создавать отдельное ХД Это приводит к неоднократному выполнению сложной квалифицированной работы по описанию структуры будущего ХД, маршрута извлечения данных из множества реляционных таблиц (при этом надо хорошо представлять структуру исходной БД) и запроса на заполнение ХД Очевидно, что автоматизация этих процессов значительно разгрузит разработчика и сократит сроки внедрения Таким образом, автоматизация проектирования ХД является важной и актуальной задачей

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

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

Во второй главе разработана единая математическая модель для описания цепочки преобразований БД - ХД Получение данного представления является начальным этапом алгоритма автоматизации

Поскольку достаточно трудно описывать структуры ХД на абстрактных отношениях, то построение математических моделей рассматривается на конкретном примере (рисунок 1) Приведенный пример представляет собой усеченную версию БД предприятия, где осуществлялось внедрение

В разработанном математическом представлении БД каждой сущности ставится в соответствие тензор Сущности «Сотрудники» будет соответствовать

пх Л ТЛЬ Т)^

тензор рк , сущности «Требования» - тензор /V ¡ , «Выпуск» — г ¡i , «Изделие» - J>°" > «Сортировка» - _ «Заказчики» - \¿b , «Поставщики» - LP , «Детали» -

Mí «Производство» — i^rn Связь между сущностями БД,

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

К* ТНШчЛ 1 4« тр£.5ов<шия 1

члтжжк ть н "Ч •дата <1

Шспоргные г Чз сотрудника г

данные г-* N2 ¿лка^чнкл 1*

'Ч УТрЧДНПК11>у / х <■ I реоо£<11ШЯ'>Л !

пост авщш п

ца'ж*шне 2

Ш

< Поставщики»!^

[ К» И'и<-лн.я Г

треботшм I

КОЛИЧЕСТВО к

«Вьи^ск»/^

<2 Ь

назван» <? 1

V

«Заказчики» С^

: 1 четллн н.нвание 1 П/ N2 н * де тя К" Д<Л ЛЛН } ,

1 / поставщика ! колпчес тво 1

, г* «Дегшн^.и £ ■ <Д> ■> н чы ОД С Г В 0 >' К

Кг нчделыя ? .

название «1

С

пен > ь

<Шд«лне>>/^

"Г"

Ке селздп

Рисунок 1 «Структура БД» Поскольку наполнение ХД происходит посредством обработки запросов БД, необходимо представить математическую модель работы СУБД

Рассмотрим тензорную модель простого запроса, то есть обращение к одной сущности Так как представлением тензора является ТУ-мерная матрица, которая при N=0 называется константой, при Ы= 1 - вектором и тд, то обработку запросов можно описать этими матрицами, представляющими тензор Например, запрос к сущности «Выпуск» (рисунок 1)

В тензорной модели БД данной сущности поставлен в соответствие тензор В матричном представлении тензор Р), будет иметь вид

ки к,-. к|

где элементы к}1 отображают значения атрибута «количество», зависящие от ключевых атрибутов «№ изделия» (индекс ]) и «№ требования» (индекс /) сущности «Выпуск» (рисунок 1)

Поток запросов к сущности БД обозначается е", под «А» подразумевается индекс (индексы), обозначающий входные данные запроса В общем случае е

можно описать матрицей, в которой единичные элементы расположены на позициях, равных значению «Л»

Тогда тензорная модель запроса описывается выражением * = ^ , которое имеет следующее матричное отображение

0 0 0 Кг К„

0 0 0 к21 к„

К, к,

0 0 0 Кл Кг Кш

Замечание знак «*» в тензорных уравнениях (выражениях) обозначает тензорную операцию умножения со сверткой (свертка производится по одноименным индексам)

Аналогично можно описать простые запросы ко всем сущностям БД Таким образом, получим тензорную модель обработки простых запросов в виде системы

' * п & - yf

е * О. ь

р 4, г г>12 па

е * Ь р = е

Г г-г лх лх

е * г г - е

I ч, \т ^гЬ (1гЬ

е * NI = е

у/ * п к _ к

• е * Р ¡1 = е е'*Т7 = е°с е**М'ре=е'р еК*Е'К = г

С и. ТТГ ^ ИБ

е *1¥ с = е

Все обозначения приведены в соответствии с рисунком 1 Для заполнения хранилищ данных, как правило, необходимо выполнение сложных запросов, в которых происходит обращение к нескольким сущностям В этом случае каждый запрос будет описываться системой тензорных уравнений, обобщение которых представляет собой тензорную модель работы реляционной СУБД

Для примера, приведенного на рисунке 1, эта модель будет иметь вид

е * И',* Р7 = е™

1 „ лг ' . Г! ь !>

е * Ы,'<2Ь = е е * N, = е

>* '* г>[ "

е ' е * Р,, = е е'Т7 = е°°

6 ё И/ л в

е** М I' ¿7 = е" ее'М\ = е

Тогда математическое описание одной из структур ХД (например, с данными о выпуске изделий), соответствующего схеме «звезда», имеет вид системы тензорных уравнений

е'*РЧ1=Р!' =е'*к е' * ИТ = ель 9

Тензорная модель возможной структуры ХД (например, с данными о производстве), соответствующего схеме «снежинка», имеет следующий вид

„8 * М>Р = еГ = е"= ' * Т™ = е"™ ? » Г/' = е"

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

В третьей главе диссертации описано кратномасштабное представление данных ХД, позволяющее значительно повысить производительность оперативного анализа, и представлены соответствующие алгоритмы аналитической обработки данных Следует подчеркнуть, что данные, подвергаемые обработке в ХД и последующему анализу, как правило, являются числовыми значениями, то есть представляют численные характеристики рассматриваемого процесса Поэтому последовательность анализируемых данных в общем случае представляет собой числовой ряд Для его преобразования к более удобному для анализа кратномасштабному представлению используются вейвлеты Хаара (в диссертации приводится обоснование выбора этого базиса) Пусть временной ряд IV(I) отображает численные показатели, содержащиеся в таблице фактов ХД Мощность данного ряда |й^(0| = и, тогда количество уровней иерархии р вычисляется по формуле р = 1о§2п Кратномасштабное представление данных в базисе Хаара выполняется по схеме, представленной на рисунке 2, где и> — элемент с номером пг на

№0 1 И'о.+И'о 2 ...

2 " 2

^0 3 «Ъ 3+14>0 4 21 2

^0 4 "'2 2

■ 2 V/ +м> 1—1 1 -

№0„-2

№ „ --- 2"1 2

2

Рисунок 2 Кратномасштабное представление ряда 10

Прежде чем данные ХД будут использованы ОЬАР-системой, производится предварительный подсчет числовых показателей — агрегирование В диссертации доказано, что использование кратномасштабного представления данных позволяет значительно сократить время выполнения агрегирования Разработано четыре алгоритма агрегации алгоритм агрегации по условным диапазонам, алгоритм разбиения на тетрады, алгоритм кратномасштабного погружения, алгоритм кратномасштабного разбиения

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

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

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

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

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

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

Вторая часть разработанной программной системы представляет собой комплекс программных средств для агрегации и анализа данных ХД В ходе экспериментов фиксировалось количество обрабатываемых данных (мощность исходного числового ряда), время одного прогона алгоритма по показаниям встроенного программного таймера и количество элементарных операций

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

----метод I

наим квадратов I

-предложенный

алгоритм

,"?> ^

анализируемый диапазон

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

Программной реализации алгоритмов агрегации данных ставилось в соответствие последовательное суммирование В результате получены следующие зависимости (рисунок 4)

- последовательное I суммирование | предложенный | алгоритм '

rft) jX) гЙ /Л

^ ч<£ & £

диапазон агрегирования

Рисунок 4 Результаты экспериментальной оценки быстродействия предложенного алгоритма агрегации и алгоритма последовательного

суммирования

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

40 80 120 160 200 240 280 320 360 анализируемый диапазон

предложенный алгоритм

последовательное сравнение

Рисунок 5 Результаты экспериментальной оценки быстродействия алгоритма кратномасштабного анализа

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

Рисунок 6 Результаты экспериментальной оценки быстродействия алгоритма ретроспективного анализа

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

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

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

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

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

Основные результаты работы

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

В ходе выполнения работы

1 Выполнен анализ современных работ в области новых информационных технологий хранения и обработки данных, рассмотрены существующие модели и методы проектирования ХД, проанализированы возможности применения в ходе автоматизированного проектирования ранее разработанных моделей и методов

2 Разработано единое математическое описание исходных БД и ХД, что позволило моделировать процесс трансформации данных из нормализованной структуры БД в структуру, подчиненную условиям оперативного анализа

3 Разработан алгоритм автоматизации проектирования ХД, снижающий временные затраты разработчика на построение из исходной БД множества возможных структур ХД

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

5 Разработана модель данных, внедрение которой значительно повышает производительность работы с ХД

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

7 Разработан программный комплекс, подтверждающий экспериментально преимущества разработанных алгоритмов

8 Разработана и реализована программная система, позволяющая автоматизировать проектирование структур ХД

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1 Бакулева М А, Телков И А Применение современных математических методов для поиска информации в базах данных библиотек Библиотековедение Информационная деятельность проблемы науки и практики Материалы второй Международной научно-практической конференции К, 2005 Ч 1 - С 165-167

2 Бакулева М А Тензорная модель работы реляционной СУБД// Информационные технологии в проектировании Межвузовский сборник научных трудов Рязань РГРТА, 2004 - С 39-43

3 Бакулева М А Математическая модель построения многомерной БД Информационные технологии и телекоммуникации в образовании и науке Межвуз сб научн трудов Рязань РГРТА, 2005 - С 23-26

4 Бакулева М А Применение вейвлет-преобразований в задачах поиска информации для систем поддержки принятия решений Новые информационные технологии в научных исследованиях и в образовании Материалы десятой научно-технической конференции студентов, молодых ученых и специалистов Рязань РГРТА,2005 -С 103-104

5 Бакулева М А Математическое представление операций манипулирования измерениями при проектировании многомерной базы данных Проблемы передачи и обработки информации в сетях и системах телекоммуникации Материалы четырнадцатой международной научно-технической конференции Рязань, 2005 -С 125-126

6 Бакулева М А Применение вейвлет-преобразований в задачах поиска информации Информационные технологии и телекоммуникации в образовании и науке Межвуз сб научн трудов Рязань РГРТА, 2006 -С 26-31

7 Бакулева МА Анализ данных на основе вейвлет-преобразований в системах поддержки принятия решений Новые информационные технологии в научных исследованиях и в образовании Материалы одиннадцатой научно-технической конференции студентов, молодых ученых и специалистов Рязань РГРТА, 2006 -С 92-93

8 Бакулева М А Применение вейвлет-преобразований для представления данных хранилища Вестник РГРТА Научно-технический журнал Выпуск 18 Рязань РГРТА, 2006 - С 80-86

9 Бакулева М А Применение кратномасштабного представления в хранилищах данных Новые информационные технологии в научных исследованиях и в образовании Материалы одиннадцатой научно-технической конференции студентов, молодых ученых и специалистов Рязань РГРТА, 2007 -С 250

10 Бакулева М А, Бакулев А В Применение вейвлет-преобразования для анализа данных хранилища Вестник РГРТУ Научно-технический журнал Выпуск21 Рязань РГРТУ,2007 -С57-60

11 Телков И А, Бакулева М А Разработка математической модели многомерной базы данных Сборник материалов Всероссийского конкурса инновационных проектов аспирантов и студентов по приоритетному направлению развития науки и техники "Информационно-телекоммуникационные системы" / Под редакцией АО Сергеева — М ГНИИ ИТТ "Информика", 2005 — 132 с

Подписано в печать 27 09 2007 г Формат 60x84 1/16 Бумага для множительных аппаратов Печать офсетная Гарнитура Times Уел печ л 1,0 Уч-изд л 1,0 Тираж 100 экз

Рязанский государственный радиотехнический университет 390005, Рязань, ул Гагарина, д 59/1

Редакционно-издательский центр РГРТУ

Список применяемых сокращений.

Введение.

1 Анализ проблемы проектирования хранилищ данных.

1.1 Роль хранилища данных в системах поддержки принятия решений.

1.2 Модели хранилищ данных.

1.3 Методология проектирования хранилищ данных.

1.4 Структура данных хранилища данных.

1.5 Обоснование выбора инструментария для решения поставленных задач.

2 Математическая модель структуры. хранилища данных.

2.1 Тензорная модель реляционного хранилища данных.

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

2.1.2 Тензорная модель запросов к реляционной базе данных.

2.1.3 Тензорная модель реляционного хранилища данных.

2.1.4 Тензорная модель ROL АР.

2.2 Тензорная модель многомерного хранилища данных.

2.2.1 Модель операций над многомерным хранилищем данных

2.3 Алгоритм автоматизации проектирования хранилищ данных на основе разработанных моделей.

3 Алгоритмы повышения производительности систем оперативного анализа на основе кратномасштабного представления данных.

3.1 Анализ структуры реляционного хранилища данных.

3.2 Основная идея кратномасштабного анализа.

3.3 Обоснование выбора базиса Хаара.

3.4 Кратномасштабное представление данных хранилища на основе вейвлет разложения в базисе Хаара.

3.5 Агрегация данных масштабированного хранилища данных.

3.6 Расчет аналитических показателей.

3.6.1 Выделение тренда.

3.6.2 Периодичность.

3.6.3 Кратномасштабный анализ.

3.6.4 Ретроспективный анализ.

4 Экспериментальная часть.

4.1 Реализация алгоритма автоматизации.

4.2 Реализация алгоритмов агрегации и ЯОЬАР.

4.3 Результаты проводимых экспериментов.

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

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

Основу информационно-поисковых систем производственных предприятий, образовательных учреждений, муниципальных структур и коммерческих образований составляют многочисленные базы данных (БД), построенные на основе реляционной модели [17, 18, 23, 25, 26, 51]. Основной идеей реляционной модели является нормализация с целью экономии ресурсов памяти [17, 18, 21, 39]. Сложные по структуре и многообразию связей реляционные БД не отвечают требованиям производительности аналитических приложений и соответственно не могут выполнять функции информационной поддержки процедуры принятия решений.

Поэтому в современных информационных системах наиболее востребованы денормализованные БД - хранилища данных (ХД). ХД являются основным источником данных оперативно-аналитических подсистем (ОЬАР-систем) современных систем поддержки принятия решений (СППР).

Однако отсутствие единого математического описания исходной БД и ХД, проектируемого на ее основе, приводит к торможению процесса разработки и внедрения ХД.

В работах Р. Кимбала [68], Б. Инмона [65], М.С. Куприянова [12], Б. Маркова [30] рассматриваются методы построения ХД на основе реляционной модели. В работах А. Кэмбла [60], Д. Селко [39] метод построения модели основан на теории множеств. Многомерная модель данных приводится в работе Э. Франкони [60] и У. Сатлера [61]. Некоторые из перечисленных методов применяются для автоматизации формирования многомерных представлений данных.

Однако на данный момент не решена конкретная задача формализации процесса трансформации реляционной БД, нормализованной и зачастую распределенной архитектуры, в удобную с точки зрения анализа форму ХД.

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

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

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

Поэтому целями диссертационной работы являются:

1) ускорение процесса проектирования ХД;

2) повышение скорости аналитической обработки данных ХД.

Для достижения поставленных целей необходимо решить ряд задач:

1) разработать единую математическую модель реляционной БД и ХД;

2) разработать математическую модель многомерного ХД;

3) разработать математическую модель операций над многомерным

ХД;

4) разработать математическую модель структуры данных в ХД, отвечающую требованиям OLAP - систем по быстродействию;

5) разработать алгоритмы, автоматизирующие процесс построения ХД на основе предложенных моделей;

6) разработать алгоритмы OLAP на основе предложенной структуры;

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

Методы исследований. Для решения поставленных задач привлечены методы тензорной алгебры [1, 13, 15, 24, 27], кратномасштабного анализа [14, 19, 36, 37, 72], вейвлет-преобразований [34, 50, 53, 70, 71, 74, 81] и сигнатурного поиска [19,41, 48, 53].

В качестве инструментальных средств использовались: Borland Delphi 7, MySQL, PostgreSQL.

Научная новизна. В работе новыми являются следующие результаты:

1. Предложены новые модели реляционного и многомерного ХД на основе тензорного аппарата.

2. Разработан метод аналитической обработки данных ХД, основанный на вейвлет - преобразовании.

3. Разработан алгоритм автоматизации процесса проектирования ХД на основе разработанных моделей. Основным преимуществом данных алгоритмов является снижение временных затрат на разработку ХД и автоматизация рутинных операций по описанию разнообразных связей исходной БД и проецированию соответствующих отношений в ХД.

4. Разработаны алгоритмы агрегации и анализа данных ХД. Отличие от известных заключается в использовании кратномасштабного анализа.

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

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

1. Создан комплекс программных средств на основе разработанного алгоритма автоматизации проектирования структур ХД, позволяющий сократить сроки проектирования ХД. На основе данного комплекса в научно -производственном предприятии «Эльф 4М» (г. Рязань) произведена реконструкция системы информационного обеспечения производственной деятельности предприятия.

2. Созданный комплекс программных средств по обработке данных ХД является инструментом, обеспечивающим высокую скорость аналитической обработки большого числа хранимых данных. Внедрение разработанного комплекса значительно повысило эффективность работы научно - производственного предприятия «Эльф 4М», масштабы производства которого охватывают 12 стран (БД содержит «500000 записей). Созданный программный комплекс предоставляет руководителю актуальную информацию о темпах производства, географии сбыта, а также векторе развития предприятия.

3. Созданный программный комплекс используется в ООО «Торгтек» (г. Рязань) для оперативной обработки отчетной и аналитической информации.

Апробация результатов диссертации. Результаты, полученные в рамках работы над диссертацией, докладывались на 10-й Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании»,

Рязань, 2005 г. [6]; 2-й Международной научно-практической конференции «Информационная деятельность: проблемы науки и практики», Киев, 2005 г. [10]; 14-й Международной научно-технической конференции «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций», Рязань, 2005 г. [5]; 11-й Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании», Рязань, 2006 г. [3]; 12-й Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании», Рязань, 2007 г. [9].

Публикации. Основные результаты диссертации опубликованы в 11 работах, из них 2 работы опубликованы в изданиях, рекомендованных ВАК.

Внедрение результатов работы. Результаты, полученные в диссертационной работе, внедрены и использованы в научно - производственном предприятии «Эльф 4M» (г. Рязань), ООО «Торгтек» (г. Рязань) (приложение 3), а также представляют часть НИР (НИР № 10-06Г (РНТП 3.2.3.7637) «Разработка нормативной базы, информационного обеспечения и регламентов открытой информационно-образовательной среды для дистанционной подготовки, переподготовки и повышения квалификации специалистов в области ИЛИ (CALS) и CASE-технологий», НИР 11-06Г (РНТП 3.2.3.7652) «Интегрированная автоматизированная информационная система управления качеством образования ВУЗа»), проводимых РГРТУ.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, библиографического списка (82 источника), изложенных на 131 странице (содержит 10 таблиц, 53 рисунка), и 3 приложения. Общий объем диссертации 147 страниц.

ЗАКЛЮЧЕНИЕ

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

В ходе выполнения работы:

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

2. Разработано единое математическое описание исходных БД и ХД, что позволило моделировать процесс трансформации данных из нормализованной структуры БД в структуру, подчиненную условиям оперативного анализа.

3. Разработан алгоритм автоматизации проектирования ХД, снижающий временные затраты разработчика на построение из исходной БД множества возможных структур ХД.

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

5. Разработана модель данных, внедрение которой значительно повышает производительность работы с ХД.

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

7. Разработан программный комплекс, подтверждающий экспериментально преимущества разработанных алгоритмов.

8. Разработана и реализована программная система, позволяющая автоматизировать проектирование ХД и получать альтернативные структуры для выбора оптимальной с точки зрения задач анализа.

1. Арменский А.Е. Тензорные методы построения информационных систем. -М.: Наука, 1989. 152 с.

2. Бакулева М.А, Бакулев А.В Применение вейвлет-преобразования для анализа данных хранилищаУ/Вестник РГРТУ. — 2007. — № 21. — С.57 — 60

3. Бакулева М.А. Математическая модель построения многомерной БД. Информационные технологии и телекоммуникации в образовании и науке. Межвуз. сб. научн. трудов. Рязань: РГРТА, 2005. — С.23—26

4. Бакулева М.А. Применение вейвлет-преобразований в задачах поиска информации. Информационные технологии и телекоммуникации в образовании и науке. Межвуз. сб. научн. трудов. Рязань: РГРТА, 2006. — С.26—31

5. Бакулева M.А. Применение вейвлет-преобразований для представления данных хранилища/УВестник РГРТА. — 2006. — № 18. — С.80— 86

6. Бакулева М.А. Тензорная модель работы реляционной СУБД// Информационные технологии в проектировании. Межвуз. сб. научн. трудов. Рязань: РГРТА, 2004. С.39-43

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

8. Беклемишев Д.В. Курс аналитической геометрии и линейной алгебры. — М.: «Физико математическая литература», 2006. — 304 с.

9. Бердышев В.И., Петрак JI.B. Аппроксимация функций, сжатие численной информации, приложения. — Екатеринбург: УрО РАН, 1999.

10. Борисенко А.И., Таранов И.Е. Векторный анализ и начала тензорного исчисления. — Харьков: Изд-во Харьковского государственного университета, 1959. — 238 с.

11. Грехем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. — М.: Мир, 1998. — 703 с.

12. Дарвин X., Дэйт К. Системы баз данных третьего поколения: Манифест/СУБД. — 1995. — № 2.

13. Дарвин X., Дэйт К. Третий манифест//СУБД. — 1996. — № 1.

14. Добеши И. Десять лекций по вейвлетам. — Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. — 464 с.

15. Долотов Д. Хранилище данных для «Мострансгаза»//Открытые системы. — 2003. — № 4. — С.43—48

16. Дэйт К. Введение в системы баз данных. — М.: «Вильяме», 1999. —848 с.

17. Дюк В., Самойленко A. Data Mining: учебный курс. — СПб.: Питер, 2001.—257 с.

18. Зильбершатц А., Стоунбрейкер М., Ульман Д. Базы данных: достижения и перспективы на пороге 21-го столетия//СУБД. 1996. № 3.

19. Кадомцев С.Б. Аналитическая геометрия и линейная алгебра. — М.: «Физико математическая литература», 2003. — 160 с.

20. Кодд Э. Расширение реляционной модели для лучшего отражения семантики//СУБД. — 1996. — № 5.

21. Кодд Э. Расширение реляционной модели для лучшего отражения семантики//СУБД. — 1996. — № 6.

22. Корячко В.П., Скворцов C.B., Телков И.А. Архитектуры многопроцессорных систем и параллельные вычисления. — М.: Высш.шк., — 1999. — 235 с.

23. Макаров A.A., Тюрин Ю.Н. Анализ данных на компьютере. — М.: ИНФРА-М, — 2003. — 544 с.

24. Маклаков С. Проектирование хранилищ данных//Компьютер пресс. —2001. —№ 1.

25. Марков Б. Проектирование систем регистрации и анализа данных. — http://www.citforum.ru/database/articles/regdata.shtml

26. Некрасов В. Архитектуры OLAP клиентов/ЛСомпьютерная неделя. — 2001. —№ 30.

27. Некрасов В. Введение в OLAP на практическом приме-ре//Компьютерная неделя. — 2001. — № 16.

28. Некрасов В., Кононова О. Распространенные заблуждения о хранилищах данных/ЯШ Magazine. — 2003. — № 5.

29. Новиков И.Я., Стечкин С.Б. Основные конструкции всплесков // Фундаментальная и прикладная математика. — 1997. — Т. 3, № 4. — С.999— 1028

30. Переберин A.B. О систематизации вейвлет-преобразований// Вычислительные методы и программирование. — 2001. — Т. 2, № 2. — С. 133158

31. Петухов А. П. Введение в теорию базисов всплесков. — СПб.: СПбГТУ, 1999.— 132с.

32. Пржияковский В.В. Абстракции в проектировании БД//СУБД. — 1998. —№ 1.

33. Пушников А.Ю. Введение в системы управления базами данных. Часть 1. Реляционная модель данных: Учебное пособие. — Уфа: Башкирский университет, 1999. — 108 с.

34. Селко Д. Стиль программирования Джо Селко на SQL. — СПб.: «Питер», 2006. — 206 с.

35. Столниц Э., ДеРоуз Т., Салезин Д. Вейвлеты в компьютерной графике. — Ижевск: НИЦ «Регулярная и хаотическая динамика», 2002. — 272 с.

36. Федоров А., Елманова Н. Хранилище данных//Компьютер пресс. — 2001. —№5. —С.137—145

37. Фищенко В.К., Кулешов Е. Л. Использование вейвлет-преобразования для оптимального оценивания тренда случайного процес-са//«Автометрия». — 2003. — Т. 39, № 1. — С. 103 — 113

38. Черняк JI. Хранилища и карты данных// Открытые системы. — 2005. — №47.

39. Agrawal R., Gupta A., Sarawagi S. Modeling multidimensional databases. — In Proc. of ICDE-97. — 1997. — P.56—72

40. Battle G. A block spin construction of ondelettes. Lemarie functions// Math. Phys. — 2002. — No. 10. — P.601—615

41. Bourgain J. A remark on the uncertainty principle for Hilbertian basis// Funct. Anal. —2001. — No. 79. — P. 136—143

42. Burt P.J., Adelson E.H. The Laplasian Pyramid as a Compact Image Code//IEEE Trans, on Communications. — 1983. — Vol. COM-31, No. 4. — P.532—540

43. Cabibbo L., Torlone R. A logical approach to multidimensional databases. — In Proc. of EDBT-98. — 1998. — P.23—29

44. Chui K. An Introduction to Wavelets. — Boston: Academic Press,1992

45. Codd E.F. Extending the Relational Database Model to Capture More Meaning//ACM Transactions on Database Systems. — 1979. — No. 4. — P.67— 78

46. Codd E.F. Providing OLAP to user-analysts: An IT mandate. Technical report, 1993.

47. Cohen A., Daudechies I., Feauveau J.C. Biorthogonal bases of compactly supported wavelets//Communications on Pure and Applied Mathematics. — 1992. — No. 45 — P.485—500

48. Date C.J. The Extended Relational Model RM/T. In C.J. Date, Relational Database Writings 1991-1994. — Mass.: Addison-Wesley, 1995

49. Daubechies I. Ten Lectures on Wavelets. — Philadelphia: SIAM,

50. Eidenderger H. Visual Data Mining. — Seattle: ACM, 2004. —307p.

51. Fayyad U.M., Piatetsky-Shapiro G., Smyth P., Uthurusamy R. Advances in Data Mining and Knowledge Discovery//MIT Press, Cambridge, — 1995.

52. Finkelstein A., Salesin D. Multiresolution Curves. —New York: In Proceedings of SIGGRAPH, 1994. — P.261—268

53. FIPS Integration Definition for Information Modeling: IDEF1X. — Computer Systems Laboratory, National Institute of Standards and Technology, 1993. — (Federal Information Processing Standards Publication 184)

54. Franconi E., Kamble A. The GMD Data Model and Algebra for Multidimensional Information. — In Proc. 5th International Conference on Data Warehousing and Knowledge Discovery. — 2003. — P.55-65

55. Franconi E., Sattler U. A data warehouse conceptual data model for multidimensional aggregation: a preliminary report//Journal of the Italian Association for Artificial Intelligence. — 1999. — P.9—21

56. Golfarelli M., Maio D., Rizzi S. The dimensional fact model: a conceptual model for data warehouses//IJCIS. — No. 7 — 1998. — P. 215—247

57. Gray J., Bosworth A., Layman A., Pirahesh H. Data cube: a relational aggregation operator generalizing group-by, cross-tabs and subtotals. — In Proc. ofICDE-96. — 1996. — P. 121—143

58. Gupta H. Selection of Views to Materialize in a Data Warehouse. — In Proc. of the 6th Intl. Conf. on Database Theory. — 1997. — P.98—112

59. Inmon B. Building the Data Warehouse. — New York: John Wiley & Sons, 1996.

60. Jagadish H.V., Lakshmanan V.S., Srivastava D. What can hierarchies do for data warehouses? — In Proc. 25th International Conference on Very Large Databases (VLDB). — 1999. — P.530—541

61. Jawerth B., Sweldens W. An Overwiew of Wavelet Based Multiresolution Analyses//SIAM Rev. — 1994. — Vol. 36, No. 3. — P. 377—412

62. Kimball R. The Data Warehouse Toolkit: Practical Techniques for Building Dimensional Data Warehouse. — New York: John Wiley & Sons, 2000.

63. Klein H.K., Hirschheim R.A. A Comparative Framework of Data Modelling Paradigms and Approaches//The Computer Journal. — 1987. — No. 1—P.8—15

64. Lemarie P.G. One nouvelle base d'ondelettes de //Math. Pures et Appl. —1997. — No. 67 — P. 227—236

65. Mallat S. A Wavelet Tour of Signal Processing. — New York — London: Academic Press, 1998

66. Mallat S. Multiresolution Approximation and Wavelet Othonormal Bases L2(R)//Trans. AMS. — 1989. — Vol. 1, No. 315. — P. 69-87

67. Manna Z., Pnueli A. The Temporal Logic of Reactive and Concurrent Systems//Springer Verlag. —1992. — P. 12—25

68. Meyer Y. Principe d'incertitude, bases hilbertiennes et algebras d'operateurs//Seminaire Bourbaki. — 1985. — No. 662. — P. 142—167

69. Ross K.A., Srivastava D., Sudarshan S. Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time. — In Proc, of the ACM SIGMOD Intl. Conf. on Management of Data. — 1996. — P.447—458

70. Roussopoulos N. View Indexing in Relational Databases//ACM Transactions on Database Systems. — 1982. — No. 17. — P. 258—290

71. Theodoratos D., Sellis T. Data Warehouse Schema and Instance Design. — In Proc. of the 17th Intl. Conf. on Conceptual Modeling. — 1998. — P.363—376

72. Theodoratos D., Sellis T. Dynamic Data Warehouse Design. — Technical Report, Knowledge and data Base Systems Laboratory, Electrical and Computer Engineering Dept., National Technical University of Athens. — 1998. — P. 1—25

73. Vassiliadis P., Skiadopoulos S. Modeling and optimisationissues for multidimensional databases. — In Proc. of CAiSE-2000. — 2000. — P. 482— 497

74. Wilson K.G. Generalized Wannier Functoins. — Cornell University,1987.

75. Wojtaszczyk P. A Mathematical Introduction to Wavelets. — Cambridge: Cambridge University Press, 1997

76. Yang J., Karlapalem K., Li Q. Algorithms for Materialized View Design in Data Warehousing Environment. — In Proc. of the 23rd Intl. Conf. on Very Large Data Bases. — 1997. — P.136—145