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

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

2 О А Б Г 2009

Полуянов Андрей Николаевич

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

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

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

ОМСК-2009

003475299

Работа выполнена в Омском Филиале Института Математики СО РАН им. Академика С.Л. Соболева

Научный руководитель - доктор технических наук

Зыкин Сергей Владимирович

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

Родионов Алексей Сергеевич

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

Соколинский Леонид Борисович

Ведущая организация - Институт системного программирования РАН

Защита диссертации состоится 10 сентября 2009 г. в 15 часов на заседании Совета Д 219.005.02 при Государственном образовательном учреждении высшего профессионального образования "Сибирский государственный университет телекоммуникаций и информатики" Министерства Российской Федерации по связи и информации по адресу: 630102, г. Новосибирск, ул. Кирова, 86.

С диссертацией можно ознакомиться в библиотеке Сибирского государственного университета телекоммуникаций и информатики (СибГУТИ) по адресу: 630102, г. Новосибирск, ул. Кирова, 86.

Отзывы на автореферат просьба высылать по адресу: 630102, г. Новосибирск, ул. Кирова, 86, заместителю декана ИВТ Резван И.И.

Автореферат разослан 2009 г.

Ученый секретарь

диссертационного совета Д 219.005.02 кандидат технических наук

доцент

Иван Иванович Резван

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация и внедрение результатов работы.

Работа выполнялась в рамках проекта № 2.2 «Алгоритмы и методы инструментальной и интеллектуальной поддержки технологий принятия решений» ОМН РАН.

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

Результаты диссертационной работы используются в Государственном учреждении здравоохранения Омской области «Клинический медико-хирургический центр Министерства здравоохранения омской области» и Федеральном государственном учреждении «Западно-сибирский медицинский центр Российского здравоохранения».

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

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

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

VIII Школа-семинар «Математическое моделирование и информационные технологии». - Улан-Удэ, 2006.

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

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

Публикации. По теме диссертационной работы опубликовано 5 работ, из них: статьи в изданиях из перечня ВАК - 1. Получено 1 свидетельство об отраслевой регистрации разработки.

Основные положения диссертации, выносимые на защиту.

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

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

3. Разработан алгоритм проверки существования соединения отношений и доказана его корректность.

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

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

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

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе описываются подходы к реализации технологии оперативной аналитической обработки данных OLAP (online analytical processing). Проводится сравнение разработанной системы с существующими программными продуктами.

Построение гиперкубического (многомерного) представления данных является основой для технологии OLAP.

Основное назначение этой технологии - преобразование данных к виду, удобному для их последующей аналитической обработки. Такое представление используется в интеллектуальном анализе данных (Data Mining).

Наиболее распространенными на данный момент средствами для работы с лшеркубическими представлениями данных являются Microsoft Analysis Services, ORACLE Analytic Workspace Manager.

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

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

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

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

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

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

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

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

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

RRD=>TJ^>ST,

где RRD - реляционное представление данных, TJ - таблица соединений, ST-гиперкуб "семантическая трансформация".

В данном случае RRD представление исходной операционной базы данных, ST - целевое представление (гиперкуб). Представление TJ является промежуточным.

Рассмотрим принцип формирования таблицы соединений (S-таблицы). Пусть задано множество отношений 3i=(Ri, R2, RJ, выбранных пользователем из реляционной БД для формирования гиперкуба, где /?, определены на подмножествах атрибутов Кортеж/[ЛГ]

- совокупность значений атрибутов AjgXcJJ, заданных в кортеже Определим пустое значение атрибута Aj в кортеже и: u[Aj]=emp. При этом значение етр не равно любому другому значению, в том числе неопределенному и пустому. В отношениях R, допустимо присутствие определенных и неопределенных значений, а значение етр является служебным и может появиться только в формируемом кортеже таблицы соединений, как следствие отсутствия соответствующего кортежа в /?,-. В пользовательском представлении данных (гиперкубе) значение етр и неопределенные значения будут обозначать одно и тоже - отсутствующее значение данных, а причины, по которым это значение отсутствует, в гиперкубе несущественны.

Определение. Выражение 7?/tXR2tx!...M/?t, где м-операция естественного соединения, будем называть существующим соединением, если для совокупности отношений /?„ i-J,...,k, существует хотя бы одна перестановка V,, V2, ..., Vt отношений R,, R2, ..., Rk такая, что ([ V,]u[V2]u...u[V;|)nfVy+/] £ 0,

Таблица соединений (S,l), где S - отношение, определенное на множестве атрибутов U, формируется следующим образом: пусть teS некоторый кортеж. Для каждого кортежа и каждого существующего соединения формируется кортеж t по следующим правилам: /[Л,]=нЦ,], если атрибут Aj принадлежит соединению, и t[Aj[ = етр в противном случае. Каждому кортежу поставим в соответствие битовый вектор l(t) = (lt(t), l2(t), ..., h(0)> где 1/0=1, если отношение Rj участвует в текущем соединении, и 1/0=0 в противном случае.

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

Определение. Кортеж teS является менее определенным или равным кортежу f'eS, когда для любого атрибута Л, выполнено: если f[A,]#'[A,], то t[Ai\=emp и l/t')>l/t), j=l,...,k. В этом случае будем писать: t<t' и назовем кортеж t подчиненным кортежу t'.

Замечание. Рассмотренное определение частичного порядка означает то, что кортеж t' содержит в себе все менее определенные либо равные кортежи. Следовательно, в представлении s достаточно хранить только кортеж I'.

Определение. Представление данных S со схемой (Ah А2, А,„ I), в котором удалены все подчиненные кортежи, будем называть 5-таблицей.

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

Для реализации ограничений на данные предлагается ввести понятие контекстного ограничения.

Определение. Совокупность отношений С,- = (Rmay, Rmd), —> R«oJ будем называть естественным контекстным ограничением или просто контекстом,

если при формировании S-таблицы участвует результат естественного соединения отношений /R„1(/> Äm«> •••» Rm<jJ и не участвуют их остатки. Набор естественных контекстных ограничений обозначим С = {ChC2,...,Cp}.

Ограничение называется "контекстным", поскольку отношения ограничивают данные друг друга за счет операции естественного соединения.

Дополнительное ограничение в виде логического выражения F накладывается на все кортежи S-таблицы. Для задания F удобно воспользоваться представлением в виде КНФ: F=F/aF2a...aF,, где Fi=Fi,vFi2v.. .vFij(i), где Fy - атомарные условия: AjQconst либо AiQAm , где © -операция (=, <, >, <, >). Неопределенные атомарные условия на промежуточных естественных соединениях заменяются на значение "ИСТИНА" или "ЛОЖЬ" так, чтобы не влиять на промежуточные результаты.

Выделим основные свойства таблицы соединений.

Свойство. Если декомпозиция p(Rh R2, ..., Rt) обладает свойством соединения без потерь информации и отсутствуют многозначные зависимости

0-~X(Y), то естественное соединение Й/М/^М.-.М/?* будет существующим.

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

Свойство (основное). Любое существующее соединение подмножества отношений базы данных равно проекции на S по этому подмножеству отношений.

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

Сформированная 5-таблица является источником данных для построения гиперкуба. Пусть X - множество атрибутов из 17, входящих без изменения в результирующее представление ST, F - множество атрибутов из U, значения которых становятся именами атрибутов в результирующем представлении, Z -множество атрибутов из U, значения которых, становятся значениями вновь введенных атрибутов. На множества X, Y, Z накладываются ограничения: XnY = 0,XnZ = 0,Yr\Z = 0.

Схема ST имеет следующий вид:

Sch(ST)={ X, Dom(Y)x{Z} }, где Sch - схема отношения, Dom - множество допустимых значений атрибутов, х - декартово произведение. Dorn(Y) = Dom(Yt) х Dom(Y2) х ... х Dom(Y4), У. Вновь введенные атрибуты имеют следующие имена: у'l...yiqZp , где У/ -у-тое значение атрибута У,, Zv - атрибут из множества Z.

Для формирования таблицы соединений потребуются следующие вспомогательные алгоритмы: Reduct - сокращение логического выражения F для текущего соединения; Comb - генерация сочетаний без повторений из к элементов по от; Exist - проверка на "существование" соединения; Transf_TJ -формирование текущего соединения с преобразованием его в ¿'-таблицу.

Обозначим: 1т - массив из т элементов, содержащий текущее сочетание из к элементов по т без повторений, (0,0,...,0) - начальное состояние массива /„;

Or(R) - операщ1Я селекции на отношении R в соответствии с набором ограничений F.

Представим описание вспомогательных алгоритмов:

Reduct: input( F, [Я]) output( F')

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

Comb: input( I„, т, к)

outpuK /и, (TRUE, FALSE})

При первом входе массив 1т имеет значение (0,0,...,0). При последующих входах в качестве значения 1т используется значение предыдущего выхода алгоритма. Значение TRUE выдается при наличии нового сочетания, FALSE - в противном случае и массив 1т принимает значение (0,0,...,0).

Exist: input( /,„, % т)

output( {TRUE, FALSE})

В данном алгоритме, проверяется выполнение условия существования соединения для совокупности отношений из 9tс номерами /„. Значение TRUE выдается при существовании соединения, FALSE - в противном случае.

Trans_TJ: input( /„„ % U, F, m, к, n) outpuli (S,l))

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

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

Существует два способа формирования S-таблицы:

1) преобразовать все контексты во временные S-таблицы, а затем комбинировать эти таблицы, введя операцию, аналогичную естественному соединению;

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

Рассмотрим основной алгоритм формирования S-таблицы с использованием контекстных ограничений и ограничений, задаваемых логической формулой F. Исходными данными для алгоритма является множество отношений Ri,

..., RJ и контексты C={ChC1,...,C!l}. begin Load_TJ (S,l)=0

for m=k to 1 step -1 Im=(0,0,...,0)

do while Comb( /„, m, k) for m'=1 top I'„M0,0,-,0) do while Comb(/'m, m', p)

if fuCj lye/'„•/=/„ and Exist(/'m., C, m') then if <Свойство СБПИ выполнаи» then (S',/')=Transf_TJ(/m, SR, v, F, m, к, и) for each € S for each tje S'

if ш,)) >(tjAtj)) then (S',r) = (S',l')-(tjntj))

endif endfor endfor

(S,0=(S,0 u (S',11) exit for endif endif enddo endfor enddo endfor

end Load_TJ

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

Поскольку область значений координат гиперкуба определяется результирующей S-таблицей, обозначим ТДХ] - область значений по координате X, TJ[Yj] - область значений по координате У,-, j-l,...,q. Схема гиперкуба будет иметь следующий вид:

Sch(ST) = (X, TJIY.MZ}, TJ[Y2]x{Z},..., TJ[Yq\x{Z}}. Рассмотрим алгоритм построения представления S-таблицы. Исходные данные TJ, X,Y = [Yh Y2,YJ, Z= fZh Zh ..., ZJ. begin Load_ST Temp(ST)=0 for each teTJ

Temp(X)=Temp(X)KJt[X] for i=I to q

Temp(YJ^remp(YJut{Yi] for j=l to s

if Temp(XYiZj)=0 then TempfXYiZjHlZj]

else

type *, "Нарушено условие существования гиперкуба" stop endif cndfor endfor endfor

ST=Sort(Temp(ST)) end Load_ST

Условием существования гиперкуба является наличие функциональной зависимости XY—&. Операция объединения использована в алгоритме с целью недопущения дублирования значений координат. В реализации целесообразно иметь возможность использования непрямой сортировки: для атрибутов X и Y вводятся дополнительные атрибуты, по которым осуществляется сортировка. При загрузке ST эти атрибуты удаляются.

Рассмотрим базовые зависимости, используемые при проектировании схемы базы данных (БД). Пусть задана схема отношения R на совокупности атрибутов U = {А I, А2, ..., A J и задана схема БД 5Е=/7?; , R2 , ..., RJ, полученная в результате проектирования. Пусть D - множество зависимостей -функциональных (ФЗ), многозначных (МЗ), включения (ЗВ), соединения (ЗС), определенных на множестве атрибутов U и отношений %

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

Определение. Зависимость </,б£) будем считать реализованной, если

переход из состояния SjGS в состояние s&S, противоречащий зависимости </,-, будет заблокирован организационно-техническими средствами.

Другими словами, в произвольном отношении Д„б5Гневозможно добавить, удалить или модифицировать кортеж, если после выполнения операции он

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

Для реализации ЗВ используются связи на схеме БД. Обозначим L/(iJ) -связь 1:1 от Я; к Я,, где Я; главное отношение; L^iJ) - связь 1:М от Я, к Rj, где Ri главное отношение; L(ij) - связь 1:1 либо 1:М от Я, к Я7, где Я, главное отношение.

Определение. Между отношениями Я, и Rj существует связь L,(iJ), если PK(Ri)=PK(Rj) и для любых реализаций Я, и Rj, выполнено Rj[V\^Ri[V], где У=[Я,]п[Яу], [Я,] - множество атрибутов, на которых определено отношение Я,.

Определение. Между отношениями Я,- и Яу- существует связь Lf/iJ), если PK(Ri)*PK(Rj) и PWddLRj],

Заметим, что определения ФЗ и ЗС соответствуют частному случаю типизированных ЗВ, которые поддерживается системами управления базами данных за счет создания внешних ключей (foreign key). Ограничение целостности, задаваемое связью Ьм('ф, подразумевает Яу[У}сЯ,[У], где У=[Я,]п[Яу|. Связь устанавливается между парой отношений по однотипным атрибутам, что позволяет СУБД предотвратить удаление кортежа в главном отношении, если в подчиненном отношении имеется кортеж с совпадающими значениями связанных атрибутов. С другой стороны, в подчиненное отношение не удастся добавить кортеж, если в главном отношении нет кортежа с совпадающими значениями связанных атрибутов. Аналогично ФЗ более сложные варианты ЗВ могут быть заданы с использованием триггеров.

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

Определение. ФЗ V—*W реализована на множестве отношений R'=(R',, R'2>

R'q), q>О и VuWc[ft'], если для любых реализаций отношений Я',, R'2,

R'„ ФЗ V-+W выполнена для m/Я';=Я';ХЗЯ'2М... МЯ'Г

Рассмотрим R"-(R"i, R"2, R"p) произвольное множество отношений БД F" - множество реализованных ФЗ на отношениях из Я". Пусть W и V, где

и У£[ш/Я">]. Обозначим W* - замыкание множества атрибутов на множестве ФЗ.

Теорема. ФЗ W—*Vреализована вт/R"), если V&W* на множествeF".

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

Определение. ЗВ ЯДУ]£Я,[У1 будем считать реализованной на схеме БД, если установлена связь L(ij) по множеству атрибутов W, где УЯУ/.

Теорема. ЗВ реализована на схеме БД, если где

У£ IV.

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

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

Пусть /?=/К/, Нг, Яр} - произвольное множество отношений реляционной БД. I) - множество реализованных зависимостей на отношениях из й.

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

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

Первоначальный выбор измерений и мер гиперкуба, а также атрибутов для формулы /*■, предлагается сделать в расширенном виде: где Л,- -

наименование отношения из исходной реляционной БД и Aj - наименование атрибута в этом отношении. Таким образом, будет задано начальное множество отношений Я°2,..., Япч}, участвующее в обязательном порядке сначала

в формировании таблицы соединения, а потом - гиперкуба.

Дальнейшая задача состоит в дополнении множества К0 отношениями из % чтобы результирующее множество удовлетворяло свойству СБПИ на множестве реализованных зависимостей, то есть являлось контекстом. В общем случае таких вариантов дополнения существует несколько. Каждый из вариантов (контекстов) имеет свою смысловую нагрузку, поэтому окончательный выбор контекста может выполнить только пользователь. Задача алгоритма заключается в последовательной генерации контекстов без зацикливания. Для сокращения количества перебираемых вариантов при формировании контекстов, ближайших к множеству предлагается сделать этот перебор направленным. То есть, очередным претендентом на дополнение к текущему множеству отношений будет /?,, которое позволяет сделать наибольшее количество подстановок в таблице алгоритма проверки свойства СБПИ.

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

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

2) Если 9t обладает свойством СБПИ, то 9t образует существующее соединение. Следовательно, выбирать для проверки СБПИ следует отношения, имеющее непустое пересечение с уже выбранными отношениями.

3) Новое отношение /?, имеет связь М:1 с уже выбранным отношением Rj.

В соответствии с приведенными критериями разработан алгоритм автоматического формирования контекста приложения.

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

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

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

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

При формировании гиперкуба используется последовательность преобразований RRD =>TJ=>ST и алгоритмы, описанные в главе 2 диссертации.

Система генерации гиперкубов реализована в виде WEB-приложения. В качестве WEB-сервера используется Apache. Информация доводится до пользователя с помощью динамически формируемых WEB-страниц, содержащих информацию, написанную на языке гипертекстовой разметки HTML. При разработке системы задействован механизм фреймов. Ввод в систему пользовательских данных осуществляется с помощью механизма форм языка HTML. Для облегчения работы с формами используются средства языка JavaScript. Информация, занесенная в систему, сохраняется в служебных таблицах реляционной СУБД. Обмен данными с СУБД, формирование WEB-страниц и обработка пользовательских данных осуществляться с помощью сценариев, написанных на языке программирования PHP. Доступ к базе данных осуществляется с помощью библиотеки ADOdb языка PHP. Запросы к БД осуществляются с помощью команд языка SQL.

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

Выбор ADOdb для работы с СУБД обусловлен универсальностью данной библиотеки. При использовании ADOdb, для перехода с одной СУБД на

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

В целом, взаимодействие между клиентом, \УЕВ-сервером, серверным приложением и СУБД представлено на рис. 1.

ПОЛЬЗОВАТЕЛЬ

ПВвод/просмтотр данных

Рис. 1 Схема взаимодействия приложений

Опишем алгоритм работы пользователя с реализованной системой.

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

1. Задание схемы гиперкуба.

Пользователь осуществляет ввод следующей информации:

• наименование приложения (гиперкуба);

• перечень отношений, участвующих в формировании таблицы соединений;

• множество атрибутов X, У, 2, IV;

• множество атрибутов сортировки.

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

2. Задание ограничений на данные.

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

3. Формирование гиперкуба.

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

Для формирования таблицы соединений используются вспомогательные алгоритмы: Reduct - сокращение логического выражения F для текущего соединения; Comb - генерация сочетаний без повторений из к элементов по т; Exist - проверка на "существование" соединения; Transf_TJ - формирование текущего соединения с преобразованием его в S-таблицу. Описание указанных алгоритмов приведено во второй главе диссертации.

Вывод на экран гиперкубического представления данных осуществляется при выполнении алгоритма LOAD_ST.

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

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

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

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

Исходные данные по пациентам содержатся в реляционной базе данных. В отношении «Пациенты» хранятся данные по пациентам. Отношение «Группы» предназначено для разделения пациентов на группы, определяющие вид применяемого метода лечения. К первой и второй группам относятся пациенты, находящиеся в тяжелом состоянии. Состояние пациентов первой группы является наиболее тяжелым. При лечении пациентов 1-й и 2-й групп применялись новые методы лечения. Третья группа является контрольной, при лечении пациентов данной группы использовались обычные методы лечение. Отношение «Виды показателей» содержит описание анализов, применяемых для контроля состояния пациентов. Отношение «Показатели» предназначено для хранения значений показателей анализов по пациентам за определенную дату. Отношение «Шкала» содержит данные для оценки состояния пациентов в баллах (от 0 до 100). В данном отношении хранится разбиение на интервалы по всем показателям и баллы для каждого из интервалов. Отношение «Баллы» предназначено для хранения расчетных баллов оценки состояния пациентов на определенную дату.

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

Выбранные отношения: Пациенты, Группы, Виды показателей. Показатели, Типы значений показателей;

Атрибуты множества X: Дата взятия, ФИО пациента;

Атрибут множества Y: Наименование анализа, № группы;

Атрибуты множества Z: Значение анализа;

Ограничения F = «Тип = "числовой"», С = {{ Виды показателей. Типы значений показателей }}\

Далее данные были проанализированы по непараметрическому критерию Уилкоксона.

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

При сравнении групп 1 и 2 с группой 3 (контрольная группа) по значениям параметров Асат, Алат, ЛИИ получено, что количество инверснй параметра в группе пациентов 1 и 2 по сравнению с группой 3 на третий день прохождения лечения лежит в интервале значений с уровнем значимости 5% (вероятность отвергнуть правильную гипотезу). Это позволяет принять гипотезу о том, что значения параметров принадлежат одной генеральной совокупности. Сравнение тех же больных по тому же параметру на первый день лечения показывает, что эта гипотеза должна быть отвергнута.

На основании данного исследования можно сделать вывод об эффективности применяемого метода лечения для групп 1 и 2.

Разработанная шкала основана на применяемых в медицине шкалах для оценки состояния больного APACHE 2 и SAPS 2. По параметрам, отсутствующим в данных шкалах интервальные границы были уточнены при обработке статистических данных с использованием меры Кульбака. Границы интервалов выбирались исходя из максимизации информационной меры Кульбака значимости параметров при сравнении выборок по 1,2 и 3-ей группам.

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

М — (^оаллов ко параметрам ^ ^максимальных баллов по параметрам)* 100,

где М - баллы оценки состояния пациента (от 0 до 100),

ZsajuioB по параметрам - сумма баллов по параметрам, значения по которым заданы пользователем, исходя из бальной оценки интервала в который попало значение параметра (или исходя из номера интервала для строковых параметров),

^максимальных баллов по параметрам ~ СуММЭ МаКСИМЭЛЬНО ВОЗМОЖНЫХ баЛЛОВ ПО

параметрам, значения по которым заданы пользователем.

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

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

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

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

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

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

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

В приложении 1 проведено подробное сравнение разработанной системы с программными продуктами Microsoft Analysis Services и ORACLE Analytic Workspace Manager на каждом из этапов формирования гиперкубического представления данных.

В приложении 2 приведена расчетная таблица параметров для шкалы оценки печеночной недостаточности.

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

1. Зыкин C.B., Полуянов А.Н. Реализация OLAP-технологии на основе межмодельных преобразований данных // Информационные технологии моделирования и управления. - 2008. - № 1(44). - С. 72-77.

2. Зыкин C.B., Полуянов А.Н. Реализация ограничений на данные в OLAP-технологии // Материалы Всероссийской конференции с международным участием "Знания - Онтологии - Теории" (30HT-07). - Новосибирск, 2007. -Т.1.-С. 80-82.

3. Зыкин C.B., Полуянов А.Н. Формирование представлений данных с контекстными ограничениями // Омский научный вестник. Серия "Приборы, машины и технологии", 2008. - № 1(64). - С. 141-144.

4. Полуянов А.Н. Автоматизация формирования гиперкубического представления данных // Системы управления и информационные технологии, 2.2(32), 2008. - С. 289-293.

5. Полуянов А.Н. Алгоритм проверки существования соединения отношений при межмодельных преобразованиях данных// Математическое моделирование и информационные технологии: управление, искусственный интеллект, прикладное программное обеспечение, технологии программирования: материалы VIII школы-семинара молодых ученых / Ин-т динамики систем и теории управления СО РАН. - Иркутск, 2006. - С. 145-149.

6. Ревзин А.И., Полуянов А.Н., Чернышев А.К., Зыкин C.B., Шутов В.Ю. Шкала оценки печеночной недостаточности // Отраслевой фонд алгоритмов и программ. Свидетельство об отраслевой регистрации разработки № 12149 от 12.01.2009 г. "Национальный информационный фонд документов" ГКЦИТ Федерального агентства по образованию. Номер государственной регистрации: 50200900155 от 16.01.2009 г.

Полуянов Андрей Николаевич

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

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

Подписано в печать 30 июля 2009 г. Формат бумаги 60x84/16, печ. л. 1.0, заказ 342, тираж 120 экз.

Издательство Омского государственного университета 644077, г. Омск, пр. Мира, 55-а, госуниверситет

Введение

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

Глава 2. Автоматизация формирования гиперкуба

2.1. Общие принципы формирования гиперкуба

2.2. Формирование таблицы соединений

2.3. Формирование гиперкубического представления

2.4. Реализованные зависимости

2.5. Автоматизация формирования контекста приложения

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

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

3.2. Выбор средств для реализации системы

3.3. Реализация технологии формирования гиперкуба

Глава 4. Использование системы для анализа данных

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

4.2. Анализ данных

4.3. Описание работы программного обеспечения 62 Заключение 67 Литература 70 Приложение 1. Сравнение разработанной технологии с программными продуктами Microsoft SQL Server и Oracle. 78 Приложение 2. Шкала оценки печеночной недостаточности

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

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

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

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

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

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

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

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

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

Цель работы

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

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

Рассмотрим основные результаты (защищаемые положения), описанные в соответствующих разделах диссертации.

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

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

3. Разработан алгоритм проверки существования соединения отношений и доказана его корректность.

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

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

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

Апробация

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

VIII Школа-семинар «Математическое моделирование и информационные технологии». - Улан-Удэ, 2006.

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

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

Публикации

По теме диссертационной работы опубликовано 5 работ, из них: статьи в изданиях из перечня ВАК - 1. Получено 1 свидетельство об отраслевой регистрации разработки.

Выводы

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

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

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

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

На защиту выносятся следующие научные положения:

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

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

3. Разработан алгоритм проверки существования- соединения отношений и доказана его корректность. Для проверки свойства существования соединения отношений разработан алгоритм, проверяющий данное свойство. Доказана корректность данного алгоритма.

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

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

6. С использованием программного обеспечения проведена подготовка и анализ данных по оценке эффективности методов лечения пациентов с печеночной недостаточностью. На основе анализа результатов разработано программное обеспечение для визуальной интерпретации состояния пациентов. Программное обеспечение было использовано для подготовки и аналитической обработки данных для заключения выводов об эффективности применения новых методов лечения и реабилитации пациентов с заболеваниями печени. Разработанное программное «Шкала оценки печеночной недостаточности» позволяет в динамике оценивать состояние пациентов с заболеваниями печени и визуализировать данное состояние, получить заключение об эффективности применяемого метода лечения.

Заключение

1. Александрович Ю.С., Гордеев В.И. Оценочные и прогностические шкалы в медицине критических состояний. Справочник. — Санкт-Петербург: Сотис, 2007. - 137 с.

2. Андерсон Р. Доказательство правильности программ. — М.: Мир, 1982. 168 с.

3. Аргерих JI. Профессиональное PHP программирование, 2-е издание. Пер. с англ. - СПб: Символ-Плюс, 2003. - 1048 с.

4. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 535 с.

5. Бергер А. Microsoft SQL Server 2005 Analysis Services. OLAP и многомерный анализ данных. СПб.: БХВ-Петербург, 2007. — 928 с.

6. Бешелев С.Д. и др. Математико-статистические методы экспертных оценок. -М.: Статистика, 1974. 159 с.

7. Бобровский С.И. Технологии Delphi 2006. Новые возможности -СПб.: Питер, 2006.-288 с.

8. Бронштейн И.Н., Семендяев К.А. Справочник по математике для инженеров и учащихся вузов. М.: Наука, 1981.- 720 с.

9. Генкин Я.Я. Новая информационная технология анализа медицинских данных. СПб.: Политехника, 1999. — 191 с.

10. Ю.Грабер M. SQL. Справочное руководство. -М: Лори, 1997. -291с.

11. П.Грофф Дж., Вайнберг П. SQL: полное руководство: Пер. с англ. -К.: Издательская группа BHV, 2000. 608 с.

12. Дейт К. Введение в системы баз данных. М.: Диалектика, 1998. -782 с.

13. Джексон Г. Проектирование реляционных баз данных для использования с микроЭВМ. М.: Мир, 1991. - 256 с.

14. Н.Зыкин C.B. Актуализация базы данных в OLAP-технологии // Материалы Всероссийской конференции с международным участием «Знания Онтологии — Теории» (30HT-07). -Новосибирск, 2007. - Т.1. - С. 73-79.

15. Зыкин C.B. Межмодельные отображения в базах данных. Омск: ОмГУ, 2000, Адрес: http://www.omsu.omskreg.ru/edumat/

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

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

18. Зыкин C.B. Формирование пользовательского представления реляционной базы данных с помощью отображений // Программирование. 1999. - № 3. - С. 70 - 80.

19. Зыкин C.B., Полуянов А.Н. Реализация OLAP-технологии на основе межмодельных преобразований данных // Информационные технологии моделирования и управления. -2008. -№ 1(44). С. 72-77.

20. Зыкин C.B., Полуянов А.Н. Реализация ограничений на данные в OLAP-технологии // Материалы Всероссийской конференции с международным участием «Знания — Онтологии — Теории» (30HT-07). Новосибирск, 2007. - Т.1. - С. 80-82.

21. Зыкин C.B., Полуянов А.Н. Формирование представлений данных с контекстными ограничениями // Омский научный вестник. Серия "Приборы, машины и технологии", 2008, № 1(64). С. 141-144.

22. Калиниченко Л.А. Методы и средства интеграции неоднородных баз данных. — М.: Наука, 1983. 423 с.

23. Карпова Т. Базы данных. Модели, разработка, реализация. СПб.: Питер, 2001.-304 с.

24. Кнут Д.Э. Искусство программирования, т. 3. Сортировка и поиск, 2-е изд. М.: Вильяме, 2000. - 832 с.

25. Когаловский М.Р. Энциклопедия технологий баз данных. М.: Финансы и статистика, 2002. - 800 с.

26. Кузнецов С.Д. Выработка оптимальных планов выполнения запросов в реляционных СУБД// Программирование. 1990. - № 2. -С. 28-43.

27. Кузнецов С.Д. Логическая оптимизация запросов в реляционных СУБД// Программирование. 1989. - № 6. - С. 46 - 59.

28. Кульба В.В., Ковалевский С.С., Косяченко С.А., Сиротюк В.О. Теоретические основы проектирования оптимальных структур распределенных баз данных. М.: СИНТЕГ, 1999. - 660 с.

29. Лавров С.С., Гончарова М.И. Автоматическая обработка данных. Хранение информации в памяти ЭВМ. М.: Наука, 1971. - 160 с.

30. Мартин Дж. Организация баз данных в вычислительных системах. М.: Мир, 1980.-662 с.31 .Математика и кибернетика в экономике: Словарь-справочник / Сост: И.И. Гонтарева, М.Б. Немчинова, и др. изд. 2-е, перераб. и доп. — М.: Экономика, 1975. — 700 с.

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

32. Мюллер П. и др. — Таблицы по математической статистике. М.: Финансы и статистика, 1982. — 278 с.

33. Наумов А.Н., Вендров A.M., Иванов B.K. Системы управления базами данных и знаний. М.: Финансы и статистика, 1991. — 352 с.35.0зкархан Э. Машины баз данных и управление базами данных. -М.: Мир, 1989. 696 с.

34. Осипов М.А., Мачульский O.JL, Калиниченко JI.A. Отображение модели данных XML в объектную модель языка СИНТЕЗ// Программирование. 2000. - № 4. - С. 23 -30.

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

36. Перевозчикова О.Л., Тульчинский В.Г. Структурный анализ и синтез маршрутных схем для задач Macro Mining // Кибернетика и системный анализ. 2003. - № 1. - С. 82 - 95.

37. Полуянов А.Н. Автоматизация формирования гиперкубического представления данных // Системы управления и информационные технологии, 2.2(32), 2008. С. 289-293

38. Сигнор Р., Стегман Михаэль О. Использование ODBC для доступа к базам данных. М.: БИНОМ, 1995.-384 с.

39. Ульман Д., Уидом Д. Введение в системы баз данных. М.: ЛОРИ, 1999.-374 с.

40. Ульман Д., Хопкрофт Д., Ахо А. Структуры данных и алгоритмы. -М.: Вильяме, 2000. 384 с.

41. Ульман Дж. Основы систем баз данных. М.: Финансы и статистика, 1983. - 334 с.

42. Фаронов В.В. Программирование баз данных в Delphi 7 Спб. : Питер, 2006. - 458 с.

43. Хаббард Ж. Автоматизированное проектирование баз данных: -М.: Мир, 1984.-293 с.

44. Ходоровский В.В. К вопросу нормализации отношений в реляционных базах данных// Программирование. 2002. - N 1. - С. 55-71.

45. Цаленко М.Ш. Моделирование семантики в базах данных. М.: Наука, 1989.-287 с.

46. Цикритзис Д. Модели данных. М.: Финансы и статистика, 1985. -343 с.

47. Четвериков В.Н., Ревунков Г.И., Самохвалов Э. Базы и банки данных. М.: Высшая школа, 1987. - 248 с.

48. Штефан И. А. Математические методы обработки экспериментальных данных: Учебное пособие / И.А. Штефан, В.В. Штефан; ГУ Кузбасский государственный технический университет. — Кемерово, 2003. — 123 с.

49. Armstrong R. Seven Steps to Optimizing Data Warehouse Performance// Computer, V. 34, № 12, 2001. P. 76-79.

50. Beeri C., Fagin R., Maier D., Yannakakis M. On the Desirability of Acyclic Database Schemes// ACM. 1983. - V 30, - № 3. - P. 479 -513.

51. Building OLAP llg Cubes. Адрес: http://www.oracle.com/technology/obe/olapcube/BuildiCubes.htm.

52. Cabibbo L., Torlone R. Querying Multidimensional Databases // Lecture Notes In Computer Science. 1997. - V.1369. - P.319-335.'

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

54. Chatziantoniou D. Using grouping variables to express complex decision support queries// Data & Knowledge Engineering, V. 61, 2007. P. 114-136.

55. Chatziantoniou D., Ross K.A. Partitioned optimization of complex queries// Inf. Syst., V. 32, № 3, 2007. P. 248-282.

56. Chaudhuri S., Dayal U. Data Warehousing and OLAP for Decision Support (Tutorial)// SIGMOD Conference, 1997, P. 507-508.

57. Eisenberg A., Melton J. SQL Standardization: The Next Steps// ACM SIGMOD Record. V. 29 - № 1 - 2000, P. 63-67.

58. Ganti V., Gehrke J., Ramakrishnan R. Mining Very Large Data Sets// Computer, Aug. 1999, P. 38-45.

59. Garmany J., Walker J., Clark T. Logical Database Design Principles. — New York: Auerbach Publications, 2005. 180 p.

60. Gray J., Chaudhuri S., Bosworth A., etc. Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals// Data Mining and Knowledge Discovery. 1997. - № 1. - P. 2953.

61. Gupta A., Harinarayan V., Quass D. Aggregate-query processing in data warehousing environment // 21th International Conference on Very Large Data Bases (VLDB 1995), Zurich. 1995.

62. Harinarayan V., Rajaraman A., Ullman J. D. Implementing Data Cubes Efficiently// SIGMOD Conference. Montreal, CA. -1996. - P. 205216.

63. Lechtenborger J., Vossen G. Multidimensional normal forms for data warehouse design// Inf. Syst., V. 28, № 5, 2003. P. 415-434.

64. Levene M., Vincent M.W. Justification for Inclusion Dependency Normal Form// IEEE Transactions on Knowledge and Data Engineering. 2000. - V 12,-№ 2.-P. 281 -291.

65. Li H.-G., Yu H., Agrawal D., Abbadi A.E. Progressive ranking of range aggregates// Data & Knowledge Engineering, V. 63, 2007. P. 425.

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

67. Missaoui R., Godin R. The Implication Problem for Inclusion Dependencies: A Graph Approach// SIGMOD Record. 1990. - V 19, -№ 1.-P. 36-40.

68. Parsaye K. OLAP and Data Mining: Bridging the Gap// Database Programming and Design. 1997. - № 2. - P. 30-37.

69. Parsaye K. Surveying Decision Support: New Realms of Analysis// Database Programming and Design. 1996. - № 4. - P. 26-33.

70. Pedersen T.B., Jensen C.S., Dyreson C.E. A Foundation for Capturing and Querying Complex Multidimensional Data// Information Systems. -V. 26-№.5-2001

71. Vassiliadis P., Sellis T. A survey of logical models for OLAP databases// SIGMOD Ree., V. 28, № 4, 1999. P. 64-69.

72. Zykin S.V. Generation of User View for a Relational Database by Mappings// Programming and Computer Software. V. 25. - №. 3. -1999.-P. 173 - 183.