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

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

4853иьи

РЕДРЕЕВ Павел Григорьевич

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

05.13.17-теоретические основы информатики

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

1 5 СЕН 2011

Челябинск-2011

4853050

Работа выполнена в Омском филиале Учреждения Российской академии наук Института математики им. С.Л. Соболева Сибирского отделения РАН

Научный руководитель: доктор технических наук, профессор

ЗЫКИН Сергей Владимирович

Официальные оппоненты: доктор технических наук, профессор

МОКЕЕВ Владимир Викторович

кандидат физико-математических наук ТУРДАКОВ Денис Юрьевич

Ведущая организация:

Учреждение Российской академии наук Институт вычислительной математики и математической геофизики Сибирского отделения РАН

Защита состоится 28 сентября 2011 г. в 12 часов на заседании диссертационного совета Д 212.298.18 при Южно-Уральском государственном университете по адресу: 454080, г. Челябинск, пр. Ленина, 76, ауд. 1001.

С диссертацией можно ознакомиться в библиотеке Южно-Уральского государственного университета.

Автореферат разослан 25 августа 2011 г.

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

Общая характеристика работы

Актуальность работы. Актуальной проблемой для многих предприятий является оперативная обработка и анализ накопленной информации. Имея оперативный доступ к огромным массивам данных, сотрудники предприятия не в состоянии сделать из них какие-либо выводы без использования специальных методов представления и обработки информации. Наиболее популярным способом решения указанной проблемы в настоящее время является технология оперативной аналитической обработки данных OLAP (online analytical processing). Основой OLAP-технологии является построение гиперкубического (многомерного) представления данных.

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

Многие аналитики OLAP придерживаются точки зрения, что кубическое представление данных должно быть постоянно хранимым и периодически обновляемым из операционной базы данных (MOLAP). Основным аргументом в пользу такого дублирования данных выдвигается требование минимального времени отклика системы на запросы пользователя. При этом предполагается, что на одном гиперкубе будут удовлетворены все потребности пользователя в анализе данных. Другой подход заключается в преобразовании схемы исходной операционной базы данных в "звезду" или "снежинку" (ROLAP). Такой подход нарушает принцип независимости данных, в частности независимость схемы операционной базы данных от места и способа использования данных. Общий недостаток этих двух подходов в регламентированности предполагаемых операций анализа данных. И если пользователю потребуется по-иному сгруппировать данные, то ему придется не один рабочий день потратить на реорганизацию данных совместно со специалистом по информационным технологиям. Это и является основным сдерживающим фактором широкого распространения технологий аналитической обработки данных.

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

1. Исходные данные должны быть представлены в реляционном нормализованном виде, и к ним обеспечивается доступ по технологии OLTP (online transaction processing).

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

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

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

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

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

1. Разработать модель многомерного представления данных на плоскости — композиционную таблиц.

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

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

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

5. Провести вычислительный эксперимент для построения диагностической шкалы на исходных данных пациентов кардиологического диспансера.

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

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

1. Разработаны модель и алгоритмы формирования композиционной таблицы.

2. Исследованы свойства и условия существования промежуточного представления данных - таблицы связанных соединений.

3. Разработан алгоритм автоматизированного формирования иерархий в измерениях.

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

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

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

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

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

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

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

Апробация работы. Результаты работы доложены на следующих конференциях и семинарах:

• Седьмая международная конференция «Перспективы систем информатики». Рабочий семинар «Наукоемкое программное обеспечение». -Новосибирск, 2009.

• Всероссийская конференция с международным участием «Знания — Онтологии - Теории» (30HT-09). - Новосибирск, 2009.

• Школа-семинар «Новые алгебро-логические методы решения систем уравнений в алгебраических системах». - Омск, 2009.

• Семинар лаборатории МППИ ОФ ИМ СО РАН. - Омск, 2010.

Публикации. По теме диссертационной работы опубликовано 7 работ, из

них статьи в изданиях из перечня ВАК - 3. Все публикации написаны без соавторов, кроме [3], в которой Зыкину C.B. и Чернышеву А.К. принадлежит постановка задачи, решение задачи принадлежит Редрееву П.Г. Получено 1 свидетельство об отраслевой регистрации разработки.

Структура и объем диссертации. Диссертационная работа состоит из введения, пяти глав, заключения и списка литературных источников, изложенных на 114 страницах, объем библиографии - 101 наименование.

Содержание работы

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

В первой главе «Подходы к реализации OLAP-технологии» анализируются виды систем OLAP: реляционные системы OLAP (ROLAP), многомерные системы OLAP (MOLAP), гибридные системы OLAP (HOLAP).

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

Для представления данных в OLAP-системах используются многомерные модели данных, являющиеся гиперкубами, то есть обобщением электронных таблиц на произвольное количество измерений (dimensions). В многомерных моделях данные рассматриваются либо как меры (measures), которые являются числовыми значениями, либо как текстовые измерения. Меры - это величины, подвергаемые анализу по измерениям. Измерение включает в себя уровни из-

мерения, позволяющие пользователю анализировать меры с различной степенью детализации. Из уровней измерения могут формироваться иерархии. Наличие иерархий позволяет осуществлять выполнение таких часто используемых для анализа данных операций как roll-up и drill-down. Конкретное значение уровня иерархии называется элементом (member).

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

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

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

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

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

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

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

1. Пользователь из списка атрибутов БД формирует множества атрибутов: измерения X, Y,, Г2,..., YN и меры Z,, Z2,..„ ZN. XnYHS, (XvYJr&HZ, i=l,2,...N.

2. Автоматическое формирование иерархий измерений для множеств атрибутов*, Yj, Y2,..., Yn.

3. Задаются логические ограничения на измерения FB(X), Fi(Y]), F2(Y2),..., Fn(Y^, По умолчанию каждая формула есть конъюнкция условий определенности {IS NOT NULL) для атрибутов измерения.

4. Формирование контекстов измерений Со, С],..., С\. (некоторые контексты могут быть пустыми, а некоторые - псевдоконтекстами).

5. Формирование контекста приложения С/иц и соответствующей реализации таблицы связанных соединений с со схемой С и логическим ограничением FfC^FoPOAfFjfY^fY^v.. .VFa{YK>)

6. Формирование реализаций измерений X, Yj, Yj,..., Y^c сортировкой значений в соответствии с иерархией.

7. Формирование реализации (представления) композиционной таблицы (заполнение значений мер на соответствующих местах таблицы).

Рассмотрим правило формирования логического ограничения F(C).

Правило 2.1. Каждое выражение Ft, i=0,l,...,N, должно быть представлено в виде дизъюнкции элементарных формул: F; . .vF;,^, где m(i) - мас-

сив целых чисел. Каждая элементарная формула является конъюнкцией атомарных условий: Fij = F'ij л F3y л ... л Fpij, где F'y = =Л?©<выражение>, <выражение> — константа либо атрибут А 'ч, © -операция сравнения.

Далее рассмотрим правило вычисления выражения F(C).

Правило 2.2. Пусть t — произвольный кортеж, определенный на множестве атрибутов V, если какой-либо терм F'ij формулы F не определен на множестве V (атрибуты Aq и/или А 'ч не принадлежат множеству V), то терм F*y заменяется значением 72?UE независимо от операции ©.

Для представления данных композиционная таблица множества атрибутов Хи Yj (j=l, 2, N) являются обобщенными координатами и могут рассматриваться как измерения.

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

Определение 2.1. Схема иерархии — это связный ориентированный ациклический граф Н=(А, Е), где А — множество атрибутов, Е - множество дуг.

Определение 2.2. Пусть V, D — атрибуты. Н - схема иерархии, тогда V<D, если в Н существует путь из вершины Vb D.

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

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

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

Для многозначной зависимости V -» D (Е), где V, D, Е - множества атрибутов, атрибуты из V располагаются в иерархии выше, чем атрибуты из IKjE.

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

Пусть II = {А,, А2, ..., А„} - некоторое множество атрибутов, Я - исходное отношение, определенное на всем множестве V и удовлетворяющее зависимостям йЕР, и {Я,, К2,...,11к} - множество отношений (декомпозиция Я), определенных на подмножествах атрибутов множества и.

Определение 2.3. Декомпозиция {Я,, Я2,..., Я*} обладает свойством соединения без потерь информации (СБПИ), если для любой реализации отношения Я, удовлетворяющей множеству зависимостей ВЕР, выполнено:

Я=яЯ1(И)1ХяЛ2(Я)Х...Хлы(Я),

где М - операция естественного соединения, щ(Я) - проекция отношения Я по атрибутам отношения Яр

Пусть Сх={Яи Я2,Я^ - произвольное множество отношений реляционной

БД.

Определение 2.4. Множество Сх будем называть контекстом, если оно удовлетворяет свойству СБПИ на зависимостях/)£■/».

Для повышения уровня автоматизации работы пользователя и снижения требований к его квалификации формирование контекстов осуществляется по исходным множествам атрибутов X, Г,, г1 (I = 1,2,Я).

Пусть РХ={Я1, Я2,..., Я^ - произвольное множество отношений реляционной

БД.

Определение 2.5. Множество Рх будем называть псевдоконтекстом, если для него не обязательно выполнение свойства СБПИ на зависимостях БЕР.

Способ формирования псевдоконтекста аналогичен способу формирования контекста, за исключением дополнения отношений для удовлетворения свойства СБПИ.

В качестве дополнительной информации для направленного выбора отношений при формировании контекстов можно использовать зависимости включения. Зависимости включения реализуются в виде связей на схеме БД. При этом, от отношения Я, к Я, может быть установлена связь 1:1 либо 1:М, где Я, -главное отношение, Я] - подчиненное.

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

Правило 2.4. При дополнении очередного отношения к формируемому контексту, прежде всего, выбираем отношения, которые являются подчиненными к уже выбранным отношениям.

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

Рассмотрим преобразование представления реляционной БД со схемой: Я,, Я2, .... Як в таблицу связанных соединений (С,1), где С - схема отношения, определенная на множестве атрибутов А,, А2, Ап, I- вектор вхождения длины к.

8

Определим принцип формирования кортежей tec, где с - реализация (множество кортежей) схемы отношения С. Рассмотрим все возможные сочетания без повторений отношений Rh R2, ..., Rk, удовлетворяющие свойству СБПИ. Пусть p~{R>»(i)> Rm(2), Rm(sJ - текущее сочетание отношений и />' его реализация, ограниченная логической формулой F: p'=CTf{Rm(1)XiRm(2)X...XRm(si).

Для каждого кортежа иер' формируем кортеж t по следующим правилам: t\Aj\-u[Aj\, если атрибут Aj принадлежит соединению, и t\Aj\=emp в противном случае, где етр - пустое значение. Каждому кортежу поставим в соответствие битовый вектор l(t) = (l,(t), l2(t),..., lk(t)), где Щ=1, если реализация ij схемы R. участвует в текущем соединении, и Щ=0 в противном случае.

Рассмотрим отношение частичного порядка над кортежами tec.

Определение 2.6. Кортеж tec является менее определенным или равным кортежу fee, когда для любого атрибута At выполнено: если то

t\Ai\=emp и lj(t')>lj(t),j=l,...,k. В этом случае будем писать: t<? и назовем кортеж t подчиненным кортежу t'.

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

Определение 2.7. Соединение отношений, удовлетворяющих свойству СБПИ будем называть связанным соединением.

Пусть X(J)=W(1)\u\RJ(2)\u...KJ[R}(m)]), где J=G(l)J(2),...J(m)), и [RJ(!)\ - множество атрибутов отношения R]0). Определим операцию проекции на множестве с.

Определение 2.8. яX(J)(c) есть совокупность кортежей u[X(J)], определенных на множестве атрибутов X(J), где для каждого u[X(J)\ существует кортеж tec такой, что u[X(J)\=t[X(J)\ и lm(t)=l, i=l,2,...,m.

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

Теорема 2.1. Для любого множества отношений R'={R'h R'2, ..., R'J, удовлетворяющего свойству СБПИ, выполнено:

nR(c)=af(R 'jtXR '¡X ...МД 'J.

Теорема 2.2. Представление с всегда существует и единственно для любой схемы реляционной БД.

В третьей главе «Модель данных «композиционная таблица»» рассматривается построение представления композиционной таблицы.

Обозначим R], R2, - исходные реляционные отношения, С - соответствующая этим отношениям таблица связанных соединений, R* - результирующая таблица.

Пусть X, Yi, Z{- множества атрибутов из R (1=1,2,..., N). Атрибуты X остаются неизменными в Л* и являются наименованиями строк, значения атрибутов Yi становятся именами столбцов в R* домены атрибутов Z,, дополненные пустым значением, распределяются между доменами новых атрибутов, введен-

9

ных для значений Г;. Естественными являются ограничения: ХглУг=0,

-Хпг=0, (I = 1, 2, Я). \Оот(У)\=и Щ=Ми где ЪотЩ область

значения атрибута У; в исходной БД,

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

У и •••> •••» Ян}

=> БсН(СТ)={Х, ^ОотЩиЩ (1=1,2,1Я) },

где Бек - схема описания отношения, Иот - область значений атрибута, ОотСУ^ОотСУ^хОотСУ^х УдеУ,-.

В данной работе предлагается отказаться от необходимости выполнения функциональных зависимостей вида Л", У)—>2/, 1=1,2,...,И, что позволит иметь в одной ячейке гиперкуба несколько значений (список) атрибутов 2/.

Определение 3.1. Множество атрибутов КЯ^ будем называть ключом атрибута в контексте Р, если зависимость выводима в 1Ф0, и не существует выводимой в П)° зависимости где и -множество функциональных зависимостей на атрибутах отношений из Р.

Определение 3.2. Значение атрибута где Я^еЯ], для текущего кортежа /еС дублирует значение ¿'[2^], /'еС, если:

\)Лг]р\=пг]р\,

2)

3) ащр\=ПЩр\.

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

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

Определение 3.3. Значения в ячейке строки будем называть

однородными, если V /.

Определение 3.4. Представление г* сформировано корректно, если:

1. В каждой ячейке г* содержатся однородные значения.

2. В каждой ячейке г* отсутствуют дублированные значения.

3. В каждой строке г2*ег* с определенными значениями атрибутов из X, в ячейке где У] - определенные значения,/=/,... выполнено:

а) содержатся все значения, соответствующие наборам Г]*[Х],

УЬ

б) отсутствуют значения 2;/, для которых строка (>/*[Х],уу,гу;Д Цр еГ1*\у^р] не может быть получена при проекции связанного соединения некоторых отношений из набора Яь Я2,...ДМ по атрибутам х, г]р.

Теорема 3.1. Представление г* всегда корректно и единственно для совокупности отношений Я,, Я2,.,.,ЯМ, образующих связанные соединения.

Рассмотрены образы зависимостей ИЕР, которые используются при установлении иерархий в измерениях и анализе корректности заполнения значений мер композиционной таблицы.

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

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

1. (РХХ). Если Х'-*Х0 удовлетворяет г*, то Х'->Х0 удовлетворяет г.

2. (БУХ). Если для произвольных строк г7* г2*ег* из условия г,*\ур.г^0)]^етр, г2*\ул.гМ2)]*етр и Ул'=У]2', Ул'яУл> У}2'ЯУ]2, Уц', у]2'еОот(У)') V;: У^Уу, У'=иУ/, следует г,*\Х0\=г2*\Хв\, тогда У'^>Х0 удовлетворяет г.

3. (БгХ). Если из условия ЯМ9'г\ V р(0, 1 = 1, 1}, где 5)ре>1=^г1*\У]1к.г]т-\ (к=1,...,Ч1), 3;р(1)2=иг2*\у]2к.г]р(9] (к=1,...,Я2), для произвольных строк г,*, г2*ег*, следует г,*[Хо\=г2*\Хо\, тогда удовлетворяет г.

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

1. (РХУ). Если для произвольных строк Г]*, г2*ег* из условия

и г2 *\У]>2]р{2)]&етр для некоторого у, следует У1=У2, где у1°еур, у2е.у)2, иу,0,у20еОот(У0), тогда Х'->У0 удовлетворяет г.

2. (РУУ). Если для произвольных строк г2*, г2*ег* из условия Г!*[ул.гш]*етр, г2*\у]2.гМ2)}Фетр и ул'=у]2', ур'сУл, У]г'ЯУ]2, Уц\ ур'еОот(У/) V Л следует у1=у2, где у1&уки У2^ук2 для некоторого к, и у", у20еОот(У0), тогда У->У0 удовлетворяет г.

3. (игу). Если из условия 5]рР)'V р(г), I = 1, 1}, где

(к=1,...,91), Б]р0)2^>г2*\у]2к.г]р(г,\ (к=1,...,д2), ^е^' для произвольных строк 1-у*, г2*ег*, следует у1в=у2', где у10еу„1ъ, у°еуч,* для некоторых Ъ, g, д, и у,0, у2°еОот(У0), тогда 2<^>У0 удовлетворяет г.

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

1. (УХТ). Если для произвольных строк п*, г2*ег* из условия: Г1*^С\=Г2*^С\ и существуют^,, и этакие, что г,*\ук1.г0]*етр, г2*\ук2.г0]Фетр для некоторого к, следует г, *\ук1.г0] =г2 *\ук2.г0\, тогда зависимость Х'^г0 удовлетворяет г.

2. (БУг). Если для произвольных строк гг*, г2*ег* из условий Г1*\Ул-2М')\фетР> г2*\У]>2ш]^етр, г,*\ук1.г0]*етр и г2*\ук2.г0]*етр для

11

некоторого к и Ул'=Ур', Ул'ЯУл, Ул'ЯУр, Ул', yJ2'eDom(Yj') V/: YfoYj', F'=ul}', следует Лг*\yki-Zo\=r2, тогда зависимость Y'—>Z0 удовлетворяет г.

3. (FZZ). Если из условия iS^/n Sjp(i)2^0 V i = 1, lj, где

sjp(01=KJri*\y»-zlPV~\ (k=l,...,qi), Sjp(i)2=ur2*\yJ2k.Zjp0)] (k=l,...,q2), Zjp(9eZ' для произвольных строк Г/*, r2*er*, следует ri*\yqlb.Zo]=r2*\yq2g.Ze] для некоторых Ъ, g, q, тогда зависимость Z'-*Z0 удовлетворяет г.

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

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

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

Система генерации композиционной таблицы реализована в среде разработки Delphi. Доступ к базе данных осуществляется с помощью библиотеки ADODB. Запросы к БД осуществляются с помощью команд языка SQL.

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

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

1. Формирование схемы композиционной таблицы.

Пользователь осуществляет формирование множества атрибутов X, множеств Y], Y2,..., Ynи соответствующих множеств мер Zlt Z2,..., Znиз множества всех атрибутов из таблиц исходной базы данных. Производится проверка условий XnY,=0, (ХиYJnZHZ, i=l,2,...N.

2. Формирование иерархий измерений.

Пользователь имеет возможность определить желаемый порядок уровней иерархии для измерений A", Yj, Y2,..., Далее осуществляется автоматическое формирование схемы иерархии, при котором используются функциональные и многозначные зависимости исходной базы данных и порядок атрибутов, заданный пользователем. Затем пользователю предоставляется возможность модифицировать иерархии.

3. Задание логических ограничений на измерения.

Пользователь осуществляет задание логических ограничений на измерения Fo(X), Fi(Yi), F2(YJ,..„ Fn(Yis). Fi=FuvFi2v...где Fg - атомарные условия: A&const либо A/&Am, где ® - операция (=, Ф, <, >, с, >). Атомарные условия могут быть заданы как на атрибутах, входящих в схему композиционной

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

атрибутам XU{YjfKJ{Zjf. Также формируются контексты для тех измерений, в логические формулы которых входят атрибуты, не принадлежащие отношениям Cf„u, по атрибутам измерения и логической формулы для измерения.

4. Формирование контекстов измерений.

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

5. Формирование композиционной таблицы.

Осуществляется формирование таблицы связанных соединений с логическим ограничением F(C)=F0(X)a(F,(Y1)\/F2(Y2)v. .. v/v/УлД) и реализаций измерений, для которых сформирован контекст либо псевдоконтекст. Далее формируется представление композиционной таблицы и осуществляется ее вывод на экран.

Для формирования таблицы соединений используются вспомогательные алгоритмы: COMB — генерация сочетаний без повторений из к элементов по т\ IsSSBP - проверка выполнения свойства СБПИ; JoinTable - формирование текущего соединения с преобразованием его в С-таблицу. Описание указанных алгоритмов приведено во второй главе диссертации.

Вывод на экран композиционной таблицы осуществляется при выполнении алгоритма LOADR.

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

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

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

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

Атрибуты множества X: № истории болезни;

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

Атрибуты множества Z7: значение численного показателя;

Традиционно для расчета диагностической шкалы используется решающая функция: F(x)=aiXi+d}X2+...+ ünXn, где - вектор значений выде-

ленных параметров (координат в пространстве параметров), a=(ai,a2,...,at^ -веса выделенных параметров (коэффициенты).

Для значений функции F(x) определяются границы (оценочная шкала): go, gi> •••> Sk, где К — количество групп объектов О и О2, ■ ■■, Ок. При условии, что go<gi<—<gK, определение принадлежности произвольного объекта о с вектором значений параметров х' к группе Oj сводится к проверке выполнения неравенства: gj.i<F(x')<gj. При выполнении равенства значения функции F какой-либо границе F(x')=gj возникает ситуация неопределенности.

Для определения значений коэффициентов (aj,a2,...,a^) и значений границ go, gi, •••» gK, в распознавании образов традиционно используются обучающие выборки, заданные множеством групп объектов Oi, Ог, ..., О к- Пусть объект Оу-еО,- характеризуется вектором значений параметров: Функционалом риска выбрано суммарное количество ошибок Е при отнесении объекта к группе.

Таким образом, задача построения оценочной шкалы может быть записана в следующем виде: Е —> min, go<gi<—<gs, -1 ^ щ й 1, i=l,2,...,N. Ограничения на коэффициенты в/ реализуются за счет масштабирования. Заметим, что целевая функция (функционал риска) не является дифференцируемой. Это исключает использование градиентных методов для решения поставленной задачи.

Все пациенты кардиологического диспансера в соответствии с врачебным заключением были разделены на 3 группы: I, II и III степени заболевания.

Предварительный анализ данных заключался рассмотрении гистограмм распределения числовых параметров из выписок. Этот анализ позволил выделить наиболее значимые параметры. В результате предварительного анализа было выбрано 14 параметров: Частота сердечных сокращений (ЧСС), Систолическое артериальное давление (САД), Диастолическое артериальное давление (ДАД), Триглицериды, Холестерин, Hb, СОЭ, Удельный вес мочи (УВМ), Размер аорты (АО), ЗСЛЖ, КСР, ЛП_ЭХО-КГ, МЖП, Возраст.

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

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

В результате выполненных расчетов получены веса параметров и границы.

На разработанное программное обеспечение «Электронная шкала оценки тяжести и мониторинга артериальной гнпертензни» получено свидетельство о регистрации разработки.

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

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

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

1. Разработаны модель п алгоритмы формирования композиционной таблицы.

2. Исследованы свойства п условия существования промежуточного представления данных - таблицы связанных соединении.

3. Разработан алгоритм автоматизированного формирования иерархий в измерениях.

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

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

Публикации по теме диссертации

Статьи, опубликованные в журналах из списка ВАК

1. Редреев П.Г. Построение табличных приложений со списочными компонентами // Информационные технологии. 2009. №5. С. 7-12.

2. Редреев П.Г. Построение иерархий в многомерных моделях данных /У Известия Саратовского университета. Серия Математика. Механика. Информатика. 2009. Т. 9. вып. 4. ч. 1. С. 84-87.

3. Зыкни С. В.. Редреев П. Г.. Чернышев А. К. Формирование представлений данных для построения медицинских диагностических шкал /У Омский научный вестник. Серия Приборы, машины н технологии. 2011. № 2 (100). С. 160-165.

Другие публикации

4. Редреев П.Г. Формирование модели данных со списочными компонентами для работы с реляционными ба зами данных по технологии OLAP /У Материалы XLVI международной научной студенческой конференции «Студент и научно-технический прогресс»: Информационные технологии. Новосибирск. 2008. С. 170.

5. Редреев П.Г. Формирование иерархий измерений многомерных моделей данных // Седьмая международная конференция «Перспективы систем

'О

информатики»: материалы рабочего семинара «Наукоемкое программное обеспечение». Новосибирск. 2009. С. 231-234.

6. Редреев П.Г. Формирование представления данных со списочными компонентами для работы с реляционными базами данных по технологии OLAP // Материалы Всероссийской конференции с международным участием «Знания - Онтологии - Теории» (30HT-09). Новосибирск. 2009. Т.1. С. 232-235.

7. Редреев П.Г. Автоматизация построения иерархий в измерениях многомерных моделей данных // Новые алгебро-логические методы решения систем уравнений в алгебраических системах. Тезисы докладов. Омск. 2009. С. 58-59.

8. Зыкин C.B., Редреев П.Г., Полуянов А.Н., Чернышев А.К., Колмогорова О.Н. Электронная шкала оценки тяжести и мониторинга артериальной гипертензии // Хроники объединенного фонда электронных ресурсов «Наука и образование». №2 (21). 2011. URL:

http://ofernio.ru/portal/newspaper/ofernio/201 l/2.doc. (дата обращения: 01.03.2011)

Работа выполнялась при поддержке Российского фонда фундаментальных исследований (проект № 09-07-00059-а).

Разработка и исследование обобщенной табличной модели данных со списочными компонентами

диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 24.08.2011 Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1,0. Уч.-изд. л. 1,2. Тираж 120 экз.

Издательство Типография «Принт Экспресс», тел. (3812) 913-903.

Редреев Павел Григорьевич

Автореферат

Введение

Глава 1. Подходы к реализации OLAP-технологии.

Глава 2. Формирование представлений данных для аналитической обработки

2.1. Описание задачи

2.2. Формирование иерархий измерений

2.3. Формирование контекстов

2.4. Формирование «таблицы связанных соединений»

Глава 3. Модель данных «композиционная таблица»

3.1. Построение представления «композиционной таблицы»

3.2. Анализ корректности представления «композиционной таблицы»

Глава 4. Реализация программного обеспечения системы

4.1. Общее описание системы

4.2. Реализация технологии формирования «композиционной таблицы»

Глава 5. Описание и реализация приложения.

5.1. Описание задачи

5.2. Анализ данных 63 Заключение 71 Литература 73 Приложение 1. Обработка исходных данных. 87 Приложение 2. Диаграммы выборочной плостности вероятностей признаков.

Актуальность темы

Технологии баз данных имеют богатую историю развития [21, 43]. В настоящее время актуальной проблемой для многих предприятий является оперативная обработка и анализ накопленной информации. Имея оперативный доступ к огромным массивам данных, сотрудники предприятия не в состоянии сделать из них какие-либо выводы без использования специальных методов представления и обработки информации. Наиболее популярным способом решения указанной проблемы в настоящее время является технология оперативной аналитической обработки данных OLAP (online analytical processing). Основой OL АР-технологии является построение гиперкубического (многомерного) представления данных.

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

Многие аналитики OLAP придерживаются точки зрения, что кубическое представление данных должно быть постоянно хранимым и периодически обновляемым из операционной базы данных (MOLAP). Основным аргументом в пользу такого дублирования данных выдвигается требование минимального времени отклика системы на запросы пользователя. При этом предполагается, что на одном гиперкубе будут удовлетворены все потребности пользователя в анализе данных. Другой подход заключается в преобразовании схемы исходной операционной базы данных в "звезду" или "снежинку" (ROLAP). Такой подход нарушает принцип независимости данных, в частности независимость схемы операционной базы данных от места и способа использования данных. Общий недостаток этих двух подходов в регламентированности предполагаемых операций анализа данных. И если пользователю потребуется по-иному сгруппировать данные, то ему придется не один рабочий день потратить на реорганизацию данных совместно со специалистом по информационным технологиям. Это и является основным сдерживающим фактором широкого распространения технологий аналитической обработки данных.

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

1. Исходные данные должны быть представлены в реляционном нормализованном виде, и к ним обеспечивается доступ по технологии OLTP (online transaction processing);

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

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

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

Цель работы

Целью работы является исследование задачи автоматизации формирования схемы и представления данных в виде «композиционной таблицы» со списочными компонентами из. исходного реляционного представления данных при наложении ограничений на измерения.

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

1. Разработаны модель и алгоритмы формирования «композиционной таблицы».

2. Исследованы свойства и условия существования промежуточного представления данных - «таблицы связанных соединений».

3. Разработан алгоритм автоматизированного формирования иерархий в измерениях.

4. Разработан алгоритм автоматического формирования контекстов измерений и контекста приложения и доказана корректность построения представления «композиционной таблицы»

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

Апробация

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

Седьмая международная конференция «Перспективы систем информатики». Рабочий семинар «Наукоемкое программное обеспечение». - Новосибирск, 2009

Всероссийская конференция с международным участием «Знания - Онтологии - Теории» (ЗСШТ-09). - Новосибирск, 2009

Школа-семинар «Новые алгебро-логические методы решения систем уравнений в алгебраических системах». — Омск, 2009.

Семинар лаборатории МППИ ОФ ИМ СО РАН. - Омск, 2010.

Публикации

По теме диссертационной работы опубликовано 7 работ [19, 36, 37, 38, 39, 40, 41], из них: статьи в изданиях из перечня ВАК - 3. Получено 1 свидетельство о регистрации разработки [18].

Выводы

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

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

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

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

1. Разработаны модель и алгоритмы формирования «композиционной таблицы».

2. Исследованы свойства и условия существования промежуточного представления данных - «таблицы связанных соединений».

3. Разработан алгоритм автоматизированного формирования иерархий в измерениях.

4. Разработан алгоритм автоматического формирования контекстов измерений и контекста приложения и доказана корректность построения представления «композиционной таблицы»

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

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

Заключение

1. Александрович, Ю. С. Оценочные и прогностические шкалы в медицине критических состояний. Справочник Текст. / Ю. С. Александрович, В. И. Гордеев. - СПб. : Сотис, 2007. - 140 с. - 1.BN 5-85503-028-8

2. Бергер, А. Microsoft SQL Server 2005 Analysis Services. OLAP и многомерный анализ данных Текст. / А. Бергер, И. Горбач. СПб. : БХВ-Петербург, 2007. - 905 с. - ISBN 978-5-94157-158-1

3. Вейнеров, О. М. Разработка САПР: В 10-ти кн. Кн. 4. Проектирование баз данных САПР Текст. / О. М. Вейнеров, Э. Н. Самохвалов. М. : Высшая школа, 1990. - 144 с. - ISBN 5-06000741-3

4. Висков, А. В. Средства описания многомерных моделей данных Текст. / А. В. Висков, М. Б. Фомин // Вестник РУДН. Серия Прикладная и компьютерная математика. 2003. - Т. 2, № 1. - С. 128-139.

5. Гайдышев, И. Анализ и обработка данных Текст. : специальный справочник / И. Гайдышев ; Гл. ред. Е. Строганова. СПб. : Питер, 2001. - 752 с. - ISBN 5-318-00220-Х

6. Гарсиа-Молина, Г. Системы баз данных Текст. / Г. Гарсиа-Молина, Дж. Ульман, Дж. Уидом. М. : Вильяме, 2004. - 1088 с. -ISBN 5-8459-0384-Х

7. Гофман, В. Э. Работа с базами данных в Delphi Текст. / В. Э. Гофман, А. Д. Хомоненко. 3-е изд. - СПб. : БХВ-Петербург, 2005. - 625 с. - ISBN 5-94157-361-8

8. Генкин, А. А. Новая информационная технология анализа медицинских данных Текст. : программный комплекс ОМИС / А. А. Генкин. СПб. : Политехника, 1999. - 191 с. - ISBN 5-73250326-9

9. Гублер Е. В. Применение непараметрических критериев статистики в медико-биологических исследованиях Текст. : научное издание / Е. В. Гублер, А. А. Генкин. JI. : Медицина. Ленингр. отд-ние, 1973. - 140 с.

10. Дейт, К. Дж. Введение в системы баз данных Текст. / К. Дж. Дейтf- М. : Издательский дом «Вильяме», 2008. 1328 с. - ISBN 978-58459-0788-2

11. П.Джексон, Г. Проектирование реляционных баз данных для использования с микроЭВМ Текст. / Г. Джексон М. : Мир, 1991.- 252 с. ISBN 5-03-002006-3

12. Журавлев, Ю. И. Об алгебраическом подходе к решению задач распознавания или классификации Текст. / Ю. И. Журавлев // Проблемы кибернетики. 1978. - Т 33. - С. 5-68.

13. Зыкин, С. В. Построение отображения реляционной базы данных в списковую модель данных Текст. / С. В. Зыкин // Управляющие Системы и Машины. 2001. - № 3. - С. 42-63.

14. И.Зыкин, С. В. Построение математической модели учебного процесса для долгосрочного планирования Текст. / С. В. Зыкин, А. В. Кукин // Математические структуры и моделирование. Вып. 10. Омск: ОмГУ. - 2002. - С. 77 - 86.

15. Зыкин, С. В. Формирование гиперкубического представления реляционной базы данных Текст. / С. В. Зыкин // Программирование. 2006. - № 6. - С. 348-354.

16. Зыкин, С. В. Метод формирования представлений данных для работы с информационными ресурсами Текст. / С. В. Зыкин // Омский научный вестник. 2006. - № 3(36). - С. 124 - 126

17. Зыкин, С. В. Автоматизация формирования представлений данных для их аналитической обработки Текст. / С. В. Зыкин, А. Н. Полуянов // Вестник компьютерных и информационных технологий. 2010. - № 4. - С. 3-9.

18. Зыкин, С. В. Формирование представлений данных для построения медицинских диагностических шкал Текст. / С. В. Зыкин, П. Г. Редреев, А. К. Чернышев // Омский научный вестник. Серия Приборы, машины и технологии. 2011. - № 2 (100). - С. 160-165.

19. Калиниченко, Л. А. Методы и средства интеграции неоднородных баз данных Текст. : научное издание / Л. А. Калиниченко. М. : Наука. Гл.ред. физ.-мат. лит., 1983. - 423 с.

20. Когаловский, М. Р. Энциклопедия технологий баз данных Текст. / М. Р. Когаловский. М. : Финансы и статистика, 2002. - 800 с. -ISBN 5-279-02276-4

21. Когаловский, М. Р. Технология баз данных на персональных ЭВМ Текст. / М. Р. Когаловский. М. : Финансы и статистика, 1992 год. - 223 с. - ISBN 5-279-00708-0

22. Коннолли, Т. Базы данных Текст. / Т. Коннолли, К. Бегг. 3-е изд. - М. : Вильяме, 2003. - 1440 с. - ISBN 5-8459-0527-3

23. Корнеев В. В. Базы данных. Интеллектуальная обработка информации Текст. / В. В. Корнеев, А. Ф. Гареев, С. В. Васютин, В. В. Райх. М. : Нолидж, 2000. - 352 с. - ISBN 5-89251-089-1

24. Крёнке, Д. Теория и практика построения баз данных Текст./ Д. Крёнке; Пер. с англ. А. Вахитов. 8-е изд. - СПб. : Питер, 2002. -800 с. - ISBN 5-94723-275-8

25. Кристофидес, Н. Теория графов Текст. / Н. Кристофидес;Пер. с англ. М. : Мир, 1978. - 432 с.

26. Кузнецов, С. Д. Основы баз данных Текст. / С. Д. Кузнецов . М. : БИНОМ, 2007. - 484 с. - ISBN 978-5-94774-736-2

27. Кузнецов, С. Д. Базы данных: модели и языки Текст. : учеб. пособие / С. Д. Кузнецов. М. : БИНОМ, 2008. - 720 с. - ISBN 9785-9518-0132-6

28. Лбов, Г. С. Метод адаптивного поиска логической решающей функции Текст. / Г. С. Лбов, В. М. Неделько, С. В. Неделько // Сибирский журнал индустриальной математики. 2009. - Т XII. -№ 3(39). - С. 66-74.

29. Марков, А. С. Базы данных. Введение в теорию и методологию Текст. / А. С. Марков, К. Ю. Лисовский. М. : Финансы и статистика, 2006. - 511 с. - ISBN 5-279-02298-5

30. Мартин, Дж. Организация баз данных в вычислительных системах Текст. / Дж. Мартин ; Пер. с англ. 2-е изд., доп. - М. : Мир, 1980. - 662 с.

31. Мейер, Д. Теория реляционных баз данных Текст. / Д. Мейер ; Пер. с англ. М. : Мир, 1987 год. - 608 с.

32. Педерсен, Т. Б. Технология многомерных баз данных Текст. / Т. Б. Педерсен, К. С. Йенсен // Открытые системы. 2002. - № 1. - С. 45-50.

33. Редреев, П. Г. Построение табличных приложений со списочными компонентами Текст. / П. Г. Редреев // Информационные технологии. 2009. - №5. - С. 7-12.

34. Редреев, П. Г. Построение иерархий в многомерных моделях данных Текст. / П. Г. Редреев // Известия Саратовского университета. Серия Математика. Механика. Информатика. 2009. -Т. 9., вып. 4,ч. 1. - С. 84-87.

35. Редреев, П. Г. Автоматизация построения иерархий в измерениях многомерных моделей данных Текст. / П. Г. Редреев // Новые алгебро-логические методы решения систем уравнений в алгебраических системах. Тезисы докладов. Омск. - 2009. - С. 5859.

36. Роб, П. Системы баз данных: проектирование, реализация и управление Текст. / П. Роб, К. Коронел. 5-е изд. - СПб. : БХВ-Петербург, 2004. - 1040 с. - ISBN 5-94157-299-9

37. Саймон, А. Р. Стратегические технологии баз данных Текст. : менеджмент на 2000 год: Пер. с англ. / А. Р. Саймон ; Под ред. М.

38. Р. Когаловского M. : Финансы и статистика, 1999. - 478с. - ISBN 5-279-017789-2

39. Стивене, Р. Программирование баз данных Текст. / Р. Стивене; Пер. с англ. В.Д. Хорева ; Под ред. С. М. Молявко. М. : БИНОМ, 2003. - 384 с. - ISBN 5-9518-0025-0

40. Тейксейра С. Borland Delphi 6. Руководство разработчика Текст. : пер.с англ. / С. Тейксейра, К. Пачеко М. : Вильяме, 2002. - 1112 с. - ISBN 5-8459-0305-Х

41. Тиори, Т. Проектирование структур баз данных Текст. : В 2 кн. Кн.2. / Т. Тиори, Дж. Фрай; Пер. с англ. М. : Мир, 1985. - 320 с.

42. Туманов, В. Е. Проектирование реляционных хранилищ данных Текст. / В. Е. Туманов, С. В. Маклаков. М. : Диалог-МИФИ, 2007. - 336 с. - ISBN 5-86404-210-2

43. Ульман, Дж. Основы систем баз данных Текст. / Дж. Ульман; Пер.с англ. М. : Финансы и статистика, 1983. - 334 с.

44. Ульман, Дж. Д. Введение в системы баз данных Текст. / Дж. Д. Ульман, Д. Уидом. Москва : Лори, 2000. - 374 с. - ISBN 5-85582069-6

45. Федоров, А. Г. Введение в OLAP-технологии Microsoft Текст. / А. Г. Федоров, Н. 3. Елманова. Москва : Диалог-МИФИ, 2002. - 269 с.-ISBN586404-175-0

46. Хансен, Г. Базы данных: разработка и управление Текст . / Г. Хансен, Д. Хансен ; Пер. с англ. М. : Бином, 1999. - 699 с. - ISBN 5-7989-0015-0

47. Харрингтон, Д. JI. Проектирование реляционных баз данных Текст. / Д. Л. Харрингтон. М. : Лори, 2006. - 230 с. - ISBN 585582-082-3

48. Цаленко, М. Ш. Моделирование семантики в базах данных Текст. /М. Ш. Цаленко. М. : Наука, 1989. - 286 с. - ISBN 5-02-014106-2

49. Чаудхури, С. Технология баз данных в системах поддержки принятия решений Текст. / С. Чаудхури, У. Дайал, В. Ганти // Открытые системы. 2002. - N 1. - С. 37-44.

50. Щавелев, Л. В. Способы аналитической обработки данных для поддержки принятия решений Текст. / Л. В. Щавелев // СУБД. -1998.-№4-5.-С. 51-60.

51. Abello, A. Understanding analysis dimensions in a multidimensional object-oriented model Текст. / A. Abello, J. Samos, F. Saltor // 3rd International Workshop on Design and Management of Data Warehouses (DMDW). SwissLife. 2001. - P. 4.1-4.9.

52. Abello, A. Understanding Facts in a Multidimensional Object-Oriented Model Текст. / A. Abello, J. Samos, F. Saltor // Proceedings of the 4th ACM international workshop on Data warehousing and OLAP. 2001. - P. 32-39.

53. Agrawal, R. Modeling Multidimensional Databases Текст. / R. Agrawal, A. Gupta, A. Sarawagi // ICDE '97 Proceedings of the Thirteenth International Conference on Data Engineering. 1997. - P. 232 - 243.

54. Armstrong, R. Seven Steps to Optimizing Data Warehouse Performance Текст. / R. Armstrong // Computer. V. 34, № 12. -2001. - P. 76-79.

55. Baralis, E. Materialized View Selection in a Multidimensional Database Текст. / E. Baralis, S. Paraboschi, S. Teniente //Proceedings of the 23rd VLDB Conference. 1997. - P. 156-165.

56. Bell, D.A. Pragmatic Estimation of Join Sizes and Attribute Correlations Текст. / D.A. Bell, D.H.O. Ling, S. McClean // IEEE Int. Conf. of Data Engineering. 1989. - P. 76 - 84.

57. Blaschka, M. Finding Your Way through Multidimensional Data Models / M. Blaschka, C. Sapia, G. Hofling, B. Dinter Текст. // Proceedings of the 9th International Conference on Database and Expert Systems Applications. 1998. - P. 198-203.

58. Cabibbo, L. Querying Multidimensional Databases Текст. / L. Cabibbo, R. Torlone // DBPL. 1997. - P. 319-335.

59. Casanova, M. Inclusion Dependencies and Their Interaction with Functional Dependencies Текст. / M. Casanova, R. Fagin, C. Papadimitriou // Journal of Computer and System Sciences. 1984. - № 28(1).-P. 29-59.

60. Chaudhuri, S. Data Warehousing and OLAP for Decision Support (Tutorial) Текст. / S. Chaudhuri, U. Dayal // SIGMOD Conference. -1997. P. 507-508.

61. Codd, E. F. Providing OLAP to User-Analysts: An IT mandate Текст. / E. F. Codd, S. B. Codd, С. T. Salley. San Jose: Codd & Date Inc. -1993.-31 pp.

62. Giorgini, P. Goal-oriented requirement analysis for data warehouse design Текст. / P. Giorgini, S. Rizzi, M. Garzetti // In Proceedings of the 8th ACM international Workshop on Data Warehousing and OLAP: DOLAP '05. 2005. - P. 47-56.

63. Golfarelli, M. A Methodological Framework for Data Warehouse Design Текст. / M. Golfarelli, S. Rizzi // Proc. 1st DOLAP Workshop, Washington. 1998. - P. 3-9.

64. Gray, J. 1996. Data Cube: a relational aggregation operator generalizing group-by, cross-tab, and sub-totals Текст. / J. Gray, A. Bosworth, A. Layman, H. Pirahesh // IEEE International Conference on Data Engineering. 1996. - P. 152-159.

65. Gupta, A. Aggregate-query processing in data warehousing environment Текст. / A. Gupta, V. Harinarayan, D. Quass // 21th International Conference on Very Large Data Bases (VLDB 1995). -1995.-P. 358-369.

66. Gyssens, M. A Foundation for Multi-Dimensional Databases Текст. / M. Gyssens, L. Lakshmanan // VLDB'97, Proceedings of 23rd International Conference. 1997. - P. 106-115.

67. Harinarayan, V. Implementing data cubes efficiently Текст. / V. Harinarayan, A. Rajaraman, J.D. Ullman // In Proc. of the ACM SIGMOD Conference on Management of Data. 1996. - P. 205-216.

68. Hurtado, C. Reasoning about Summarizability in. Heterogeneous Multidimensional Schemas Текст. / С. Hurtado, A. Mendelzon // ICDT '01 Proceedings of the 8th International Conference on Database Theory. 2001. - P. 375 - 389.

69. Hurtado, С. OLAP Dimension Contraints Текст. / С. Hurtado, А. Mendelzon // PODS '02 Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. 2002. - P.l 69 - 179.

70. Hurtado, C. Computing cube view dependences in OLAP datacubes Текст. / С. Hurtado, С. Gutierrez // 15th International Conference on Scientific and Statistical Database Management. 2003. P. 33-42.

71. Husemann, B. Conceptual Data Warehouse Design Текст. / В. Husemann, J. Lechtenborger, G. Vossen // Proceedings of DMDW 2000. 2000. - P. 6.1-6.11.

72. Jagadish, H. What can hierarchies do for data warehouses Текст. / H. Jagadish, L. Lakshmanan, D. Srivastava // VLDB 1999. 1999. - P. 530-541.

73. Jensen, M.R. Discovering Multidimensional Structure in Relational Data Текст. / M.R. Jensen, T. Holmgren, T.B. Pedersen // In Proceedings of DaWaK'2004. 2004. - P. 138-148.

74. Lechtenborger, J. Multidimensional normal forms for data warehouse design Текст. / J. Lechtenborger, G. Vossen // Inf. Syst. 2003. - V. 28. -№5. - P. 415-434.

75. Lehner, W. Normal forms for multidimensional databases Текст. / W. Lehner, J. Albrecht, H. Wedekind // Proceedings of the Tenth International Conference on Scientific and Statistical Database Management. 1998. - P. 63-72.

76. Lehner, W. Modeling Large Scale OLAP Scenarios Текст. / W. Lehner // EDBT '98 Proceedings of the 6th International Conference on

77. Extending Database Technology: Advances in Database Technology. -1998.-P. 153 167.

78. Lenz, H. Summarizability in OLAP and Statistical Databases Текст. / H. Lenz, A. Shoshani // In SSDBM '97. 1997. - P. 132-143.

79. Levene, M. Justification for Inclusion Dependency Normal Form Текст. / M. Le vene, M.W. Vincent // IEEE Transactions on Knowledge and Data Engineering. 2000. - V. 12. - n.2. - P. 281-291.

80. Li, C. A Data Model for Supporting On-Line Analytical Processing Текст. / С. Li, X.S. Wang // CIKM '96, Proceedings of the Fifth International Conference on Information and Knowledge Management. 1996.-P. 81-88.

81. Li, H.-G. Progressive ranking of range aggregates Текст. / H.-G. Li, H. Yu, D. Agrawal, A. E. Abbadi // Data & Knowledge Engineering. -V. 63.-2007.-P. 4-25.

82. Malinowski, E. OLAP hierarchies: A conceptual perspective Текст. / E. Malinowski, E. Zimanyi // In Proc. of the 16th Int. Conf. on Advanced Information Systems Engineering. 2004. - P. 477-491.

83. Maniatis, A.S. Advanced visualization for OLAP Текст. / A.S. Maniatis, P. Vassiliadis, S. Skiadopoulos, Y. Vassiliou // Proceedings of the 6th ACM international workshop on Data warehousing and OLAP.-2003.-P. 9-16.

84. Mazon, J. Reconciling requirement-driven data warehouses with data sources via multidimensional normal forms Текст. / J. Mazon, J. Trujillo, J. Lechtenborger // Data Knowl. Eng. 2007. - V 63. - No. 3. -P. 725-751.

85. Miller, L. Data Warehouse Modeler: A CASE Tool for Warehouse Design Текст. / L. Miller, S. Nila // Thirty-First Annual Hawaii International Conference on System Sciences. 1998. - V. 6. - P 42-48.

86. Missaoui, R. The Implication Problem for Inclusion Dependencies: A Graph Approach Текст. / R. Missaoui, R. Godin // SIGMOD Record. -1990. -V 19. -№ 1. P. 36-40.

87. Niemi, T. Logical Multidimensional Database Design for Ragged and Unbalanced Aggregation Hierarchies Текст. / Т. Niemi, J. Nummenmaa // in Proceedings of 3rd International Workshop on Design and Management of Data Warehouses. 2001. - P. 7.1-7.8.

88. Nguyen, Т. B. Conceptual Multidimensional Data Model Based on MetaCube Текст. / Т. В. Nguyen, A. M. Tjoa, R. Wagner // In Proceedings of the First International Conference on Advances in Information Systems. 2000. - P. 24-33.

89. Parsaye, K. Surveying Decision Support: New Realms of Analysis Текст. / К. Parsaye // Database Programming and Design. 1996. - № 4.-P. 26-33.

90. Parsaye, K. OLAP and Data Mining: Bridging the Gap Текст. / К. Parsaye // Database Programming and Design. 1997. - № 2. - P. 3037.

91. Pedersen, T.B. A foundation for capturing and querying complex multidimensional data Текст. / T.B. Pedersen, C.S. Jensen, C.E. Dyreson // Inf. Syst. 2001. - V. 26. - № 5. - P. 383-423.

92. Pedersen Т. В. Multidimensional Databases Текст. / Т. В. Pedersen, С. S. Jensen // The Industrial Information Technology Handbook. -2005. P. 1-13.

93. Pourabbas, E. Characterization of Hierarchies and Some Operators in OLAP Текст. / E. Pourabbas, M. Rafanelli // DOLAP. 1999. - P. 5459.

94. Tryfona, N. StarER A Conceptual Model for Data Warehouse Design Текст. / N. Tryfona, F. Busborg, J. Borch // Proceedings of the 2nd ACM international workshop on Data warehousing and OLAP. 1999. -P. 3-8.

95. Tsois, A. MAC Conceptual Data Modeling for OLAP Текст. / A. Tsois, N. Karayannidis, T. Sellis // 3rd International Workshop on Design and Management of Data Warehouses. 2001. - P. 5.1-5.11.

96. Vassiliadis, P. Modeling Multidimensional Databases, Cubes and Cube Operations Текст. / P. Vassiliadis // Proc. 10th International Conf. Scientific and Statistical Database Management. 1998. - P. 5362.

97. Vassiliadis, P. A survey of logical models for OLAP databases Текст. / P. Vassiliadis, T. Sellis // SIGMOD Ree. 1999. - V. 28. - № 4. - P. 64-69.