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

РАЗРАБОТКА МЕТОДОВ ОПЕРАТИВНОГО ОБНАРУЖЕНИЯ

УСТОЯВШИХСЯ АССОЦИАЦИЙ В ДАННЫХ И ИХ ИСПОЛЬЗОВАНИЕ ПРИ СОПРОВОЖДЕНИИ БАЗ ДАННЫХ КОРПОРАТИВНОГО УРОВНЯ

Специальность 05.13.06 - Автоматизация и управление технологическими процессами и производствами (промышленность)

АВТОРЕФЕРАТ

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

Москва - 2004

Работа выполнена в Московском автомобильно-дорожном институте (государственном техническом университете) на кафедре «Автоматизированные системы управления»

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

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

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

Кандидат технических наук, доцент Будихин Анатолий Владимирович Доктор технических наук, профессор Марсов Вадим Израилевич Кандидат технических наук Панкратов Владимир Семенович Научно производственная фирма «Круг», г. Пенза

Защита диссертации состоится "_"_2004 г. в_час.

на заседании диссертационного совета Д.212.126.05 при Московском автомобильно-дорожном институте (государственном техническом университете) по адресу:

125319, ГСП-47, г. Москва, Ленинградский пр., д. 64.

С диссертацией можно ознакомиться в библиотеке МАДИ (ГТУ).

Автореферат разослан и_"_2004 г.

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

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

Михайлова Н.В

2004-4 26839

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

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

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

)i»OC. (lAUmJKAwlbHAii i БИБЛИОТЕКА j

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

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

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

Целью исследования- является разработка методов автоматизации оперативного обнаружения устоявшихся ассоциаций в обрабатываемых реляционной СУБД данных и изменений в них.

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

1. анализ существующих средств аналитической обработки данных и, в частности, методов ИАД и задач обнаружения устоявшихся ассоциаций в данных и проблем их реализации;

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

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

обоснование формата входных данных, средств преобразования к требуемому формату;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Разработанные методы и алгоритмы прошли апробацию и внедрены для практического применения в ЗАО «АтлантикТрансгазСистема», ООО «Пермтрансгаз», а также используются в учебном процессе в МАДИ(ГТУ).

Апробация результатов. Основные положения и результаты диссертации докладывались и обсуждались на заседаниях кафедры «Автоматизированные системы управления» МАДИ (ГТУ) в 2001-2003 годах, на республиканских межрегиональных и международных научно-технических конференциях, симпозиумах и семинарах (2000-2003 гг.).

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

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

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

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

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

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

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

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

Рис. 1 Стадии НАД

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

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

1. Формирование наборов-кандидатов (наборов, которые могут стать обеспеченными)

2. Подсчет обеспечений сформированных наборов-кандидатов

В связи с этим на уровне реализации выделяются две подзадачи:

1. Обработка данных о наборах (поиск, формирование, подсчет обеспечений)

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

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

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

Рис. 2 Структурарабочих данных

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

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

эффективные подходы к оптимизации обработки. В частности, наиболее критичным для быстродействия является сканирование исходного множества данных на этапе подсчета обеспечений (Рис. 3).

Рис. 3. Графики зависимости времени выполнения обработки алгоритмами от величины порогового обеспечения Так, в большинстве случаев алгоритмы Apriori и «Разбиение» выполняют почти на один цикл сканирования данных больше, чем ДПК и «Выборочный анализ», в связи с чем в этих случаях на их выполнение требуется в два раза больше времени. При пороговом обеспечении 0,3 при проводимых испытаниях алгоритму «Выборочный анализ» потребовалось выполнить лишний цикл сканирования данных, что также отразилось на времени выполнения. Причем загрузка процессора и дисковых устройств при этом достаточно высоки (до 40% загрузки процессора Pentium 3 - 500 Мгц). В связи с этим, для реализации оперативной обработки необходимо в первую очередь минимизировать необходимость выполнения таких сканирований и их трудоемкость. Также можно говорить о допустимости незначительного увеличения множества подсчитываемых наборов-кандидатов и выполнении обработки на основе репрезентативной выборки из множества исходных данных (множество подсчитываемых наборов при выполнении алгоритма «Выборочный анализ» больше аналогичного

множества при выполнении обработки алгоритмом ДГОС на величину множества наборов негативной области

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

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

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

где Е - множество элементов (£ = {е,,е3.....е,}), из которых

формируются транзакции составляющие множество

транзакций Б

Р(Х) - вероятность появления набора X в множестве транзакций Д равная отношению мощности множества транзакций, содержащих данный набор к мощности всего множества транзакций D

р(ул_ |{(Г„Г,.....Т,)\Т^Р&.Т,^Х}\

(3)

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

• Все возможные 1-элементные наборыС;=£;

• Наборы негативной области

(4)

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

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

Д = С,и1иЯ<Г

(5)

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

Рис. 4Общий вид алгоритма

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

• использования различных величин порогового обеспечения на разных этапах обработки данных ( сна этапе подготовки рабочих данных и а' на стадии оперативной обработки) с целью более раннего выявления появившихся тенденций;

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

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

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

Структура рабочих данных будет иметь вид представленный на Рис. 5.

ХММ1*Р«М

Сод«р) :ос«да итумл 44лмтм<Ьм«*т00 WM MUMRPA/ftt «»1» ИД*мти«м«тор «ММИТ» NUMBER{S) <Яв> Омтчик 1 NUMBEKflO) Счетчик 2 NUMB6J410) Статус NUMBERS) ПрММАуиМ Ст»ту© NUMBER(1) Дата иамммм отатуо* DATE РодитепьсямЯ УЯЙ NUMBER«) дочерни* умл мимвея<в)' «не» ОМ««ММ* у«ел NUMBERCV) "W* Прммн

Рис. 5 Модифицированная структурарабочихданных

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

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

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

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

Рассматриваемая реализация программного комплекса была предназначена для анализа данных аудита выполнения операций обработки данных и обращений к объектам БД. База данных реализована под СУБД Oracle 8i на ЭВМ РШ500 с 512Мб ОП и охватывает несколько предметных областей, является базой данных общего назначения и используется системами различного типа (от систем оперативной обработки транзакций -OLTP, до систем поддержки принятия решений - DSS), в связи с чем к ней предъявляются различные, подчас противоречивые, требования. Вместе с тем, БД содержит множество пользовательских объектов со сложными взаимосвязями между ними и пребывает в состоянии непрерывного развития и модификации, обусловленном выполняемым поэтапным развитием использующих ее автоматизированных систем и меняющимися условиями эксплуатации. БД одновременно использует множество пользователей в рамках работы с серией программных модулей, в том числе и от сторонних поставщиков, ввиду чего особенности реализации ими обработки данных неизвестны. В таких условиях эффективный анализ информации об использовании объектов БД и выполняемых пользователями и приложениями операциях без средств автоматизации практически невозможен.

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

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

решения данной группы задач. Так, при незначительной загрузке процессора сервера БД (в среднем порядка 1-3% и кратковременными пиками (до 3-х секунд) до 30% в моменты выполнения проверок обеспечения новых наборов на множестве исходных данных о 30000 транзакциях, представленных более чем 400000 записей представления аудита) осуществлялась обработка поступающих данных о транзакциях. В процессе обработки данных были выявлены изменения в тенденциях обращения к группам таблиц в рамках общей операции обработки по ряду которых были приняты решения о проведении анализа их причин. В результате анализа, в частности, было определено, что причиной изменения тенденций являются модификации в некоторых программных комплексах и структурах БД. Были разработаны решения, позволившие, в ряде случаев, посредством модификации программ и структур БД (частичная денормализация, дополнительная индексация и т.п.), снизить интенсивность обращения к объектам и снизить затраты (врени, вычислительных ресурсов, оперативной памяти) на их выполнение на 1075%. При этом, использование программного комплекса позволило значительно снизить объем рутинных операций по выявлению таких изменений в закономерностях и повысить вероятность их обнаружения. При уровне затрат ресурсов на обработку, позволяющем использовать данный алгоритм в фоновом режиме параллельно с прочими задачами оперативной обработки данных, может осуществляться обработка, позволяющая в кротчайшие сроки выявлять значимые изменения в закономерностях группирования элементов, что чрезвычайно актуально в условиях быстро меняющихся параметров использования БД, характерных для промышленных БД и, в частности, динамично развивающихся сложных БД предприятий нефтегазовой промышленности.

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

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

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

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

Основные положения диссертации нашли свое отражение в следующих публикациях:

1. Платонов СВ., Гоголин СВ., Аликин B.C., Проблема ведения истории изменений справочных данных // Современные информационные технологии в автотранспортном комплексе и дорожном строительстве: Сб. науч. тр. — М.: МАДИ, 1999. — С. 54-59.

2. Платонов СВ., Аликин B.C., Оперативное обнаружение обеспеченных наборов в данных // Автоматизированные системы в автотранспортном и дорожно-строительном комплексе: Сб. науч. тр. — М.:МАДИ, 2001. — С 101-105.

3. Гоголин СВ., Богданов Н.К., Платонов СВ., Методы хранения и интеллектуальной обработки данных в автоматизированных системах экологического мониторинга и анализа // Труды 4-ой международной научно-практической конференции "Высокие технологии в экологии", Воронеж: Воронежское отд. РЭА, 2001 - С. 226-230.

4. Горбунов Л.И., Чекункова М.С, Платонов СВ., Гладюк Е.В., Системы диспетчерского управления поставками газа // Промышленные АСУ и контроллеры, 2002.—№5. — С. 19-22.

5. Платонов СВ. Метод реализации оперативного обнаружения устоявшихся ассоциаций в данных // Моделирование и оптимизация в управлении: Сб. науч. тр. — М.: МАДИ, 2003. — С 114-119.

6. Budikhin A.V., Gogolin S.V., Platonov S.V., Operative finding of the large itemsets in intelligent systems // In proc. of Int'l Conf. Information and Telecommunication Technologies in Intelligent Systems. - Barcelona, Spain, 2003. -P. 14-16.

* . 1 7 0 (

РНБ Русский фонд

2004-4 26839

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано к печати 27.01.2004 г. Формат 60x90 1/16. Усл.печл. 1,25. Тираж 100 экз. Заказ 037. Тел. 939-3890,939-3891,928-1042. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

ВВЕДЕНИЕ.

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

1.1. Обзор особенностей сопровождения баз данных корпоративного уровня.

1.2. Анализ современных методов аналитической обработки данных.

1.3. Обзор сфер применения технологии интеллектуального анализа данных.

Выводы по главе 1.

2. АНАЛИЗ МЕТОДОВ ОБНАРУЖЕНИЯ УСТОЯВШИХСЯ АССОЦИАЦИЙ В ДАННЫХ, РАЗРАБОТКА МЕТОДОВ РЕАЛИЗАЦИИ И СТРУКТУР ДАННЫХ.

2.1. Алгоритмы поиска устоявшихся ассоциаций в данных.

2.1.1. Алгоритм Apriori.

2.1.2. Методы оптимизации алгоритма Apriori.

2.1.2.1. Алгоритм «Разбиение».

2.1.2.2. Алгоритм «Выборочный анализ».

2.1.2.3. Алгоритм «Динамический подсчет наборов».

2.2. Разработка методов реализации алгоритмов в реляционных

СУБД.

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

2.2.2. Структура исходных данных.

2.2.3. Разработка структур рабочих и результирующих данных.

2.2.4. Реализация алгоритмов и служебных функций.

2.3. Сравнительный анализ алгоритмов.

2.3.1. Условия и методы сравнительного анализа.

2.3.2. Анализ сравнительных характеристик работы алгоритмов.

Выводы по главе 2.

3. ОПЕРАТИВНОЕ ОБНАРУЖЕНИЕ УСТОЯВШИХСЯ АССОЦИАЦИЙ В ДАННЫХ.

3.1. Задача оперативного обнаружения устоявшихся ассоциаций в данных.

3.2. Разработка методов реализации оперативной обработки данных.

3.3. Параметры обработки и оценка результатов.

Выводы по главе 3.

4. РАЗРАБОТКА РЕАЛИЗАЦИИ ОПЕРАТИВНОГО ОБНАРУЖЕНИЯ УСТОЯВШИХСЯ АССОЦИАЦИЙ В ДАННЫХ ДЛЯ СОПРОВОЖДЕНИЯ РБД АВТОМАТИЗИРОВАННОЙ СИСТЕМЫ ОПЕРАТИВНОГО ДИСПЕТЧЕРСКОГО УПРАВЛЕНИЯ ООО «ПЕРМТРАНСГАЗ».

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

4.2. Сбор исходных статистических данных использования БД.

4.3. Обработка статистических данных использования БД.

4.4. Анализ результатов обработки данных.

Выводы по главе 4.

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

Большие объемы и сложность потоков оперативной и статистической информации предполагают использование мощных систем управления базами данных (СУБД) [7], а также мощных серверов или их групп. На современном этапе развития, наиболее распространенные реляционные СУБД [7,15,22,51,52] позволяют хранить и обрабатывать миллиарды записей, выполнять параллельные вычисления, работать с распределенными базами данных (БД), предоставляют мощный инструментарий обработки данных, умелое использование которого может обеспечить значительное повышение производительности выполняемых задач. Но простое накопление и хранение данных, реализуемое в первую очередь, далеко не исчерпывает возможностей технологии баз данных.

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

Автоматизация аналитической обработки данных имеет огромное значение для всех областей жизнедеятельности человека (стратегическое и бизнес планирование, исходная информация для систем принятия решений и управления, накопление информации для экспертных систем, основа самообучающихся систем, моделирование и проектирование, диагностика, мониторинг и многое другое). Автоматизация может снизить стоимость данных операций в тысячи раз, сократив труд экспертов, а также значительно повысить ценность получаемых данных за счет оперативности и достоверности. По оценкам экспертов и имеющимся примерам внедрения подобных технологий отдача может достигать 1000% [17].

В последние годы в мире оформился ряд взаимодополняющих концепций хранения и анализа данных. Наиболее эффективными и распространенными являются: оперативная аналитическая обработка (online analytical processing, OLAP) [29,43,53], хранилища данных (data warehouse) [19,28,65,23,51], интеллектуальный анализ данных (НАД) [14] или добыча данных (data mining) [24,57,67,77,80,92]. Все они занимают некоторую нишу на рынке информационных технологий и, в силу своих функциональных различий, и взаимодополнения по сферам применения, вероятнее всего, продолжат параллельно существовать и в дальнейшем.

Тем не менее, стремительно развивающийся сектор аналитической обработки данных, растущие объемы потоков данных и их интенсивность, объемы накопленных данных и сложность их структуры предъявляет все новые требования к методам анализа. В первую очередь, требования связаны с полнотой получаемой информации и снижением затрат на ее получения. Необходимо наиболее оперативно получать максимум информации, пригодной для аналитической обработки и принятия решений, как на основе накопленных данных, так и поступающих, своевременно реагировать на изменение тенденций и правил. В связи с этим возникает необходимость и в оперативном выявлении изменений в закономерностях, информация о которых может использоваться как в явном виде, так и для задания правил для прочих аналитических систем (например, OLAP - Оп-Line Transaction Processing). Как только на основе поступающих данных становится возможно говорить об изменениях в закономерностях и правилах, необходимо, чтобы эта информация становилась доступна, при этом выявление подобных изменений должно быть оптимизировано по затрачиваемым ресурсам. Растущие требования к масштабируемости аналитической обработки, полноте информации и оперативности извлечения новых знаний о закономерностях обосновывают выбор темы диссертации и ее актуальность.

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

Предметом исследования являются методы автоматизации аналитической обработки [14,53] оперативных данных в промышленных реляционных БД фактографического типа [7,27,32]. В частности, решение задачи выявления устоявшихся ассоциаций в данных [8], которое позволит оперативно выявлять текущие изменения, обладает значительным потенциалом в области поддержки принятия решения и стратегического планирования.

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

Целью исследования является повышение эффективности автоматизации обнаружения устоявшихся ассоциаций в данных [36,49,91] за счет обеспечения возможности обработки и учета поступающих оперативных данных в реляционных СУБД. Исходя из этого, основными задачами исследования являются:

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

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

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

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

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

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

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

Теоретическая значимость диссертации заключается в выполнении синтеза результатов современных исследований и разработок в области аналитической обработки данных, в части задач интеллектуального анализа данных [8], связанных с обнаружением устоявшихся ассоциаций в данных [40]. Существующие подходы к решению задач выявления закономерностей в данных [4], в частности, устоявшихся ассоциаций в данных, связаны с обработкой больших объемов ранее накопленных данных и требуют значительных затрат ресурсов на выполнение обработки, в следствие чего практически не пригодны для обработки поступающих в реальном времени данных с целью оперативного выявления происходящих изменений в закономерностях. В данной работе осуществляется попытка разработки методов, позволяющих осуществлять оперативное обнаружение изменений в тенденциях формирования наборов в данных при решении задач сопровождения промышленных БД корпоративного уровня.

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

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

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

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

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

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

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

Разработанные методы и алгоритмы прошли апробацию и внедрены для практического применения в ЗАО«АтлантикТрансгазСистема», 000«Пермтрансгаз», а также используются в учебном процессе в МАДИ(ГТУ).

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

Выводы по главе 4

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

6. На основе разработанных алгоритмов и методов реализован программный комплекс автоматизации сопровождения фактографической промышленной БД в части анализа данных аудита использования объектов БД и трендов поведения пользователей. Программный комплекс позволил выявлять изменения в тенденциях использования объектов БД и выполнении групп операций по обработке данных, и снизить затраты на сопровождение БД, реализацию и апробацию автоматизированных систем, использующих БД. Комплекс был внедрен в ЗАО «АтлантикТрансгазСистема», ООО «Пермтрансгаз», а также используется в учебном процессе в МАДИ (ГТУ).

1. Арагон Л. Долой грязь! // PC Week/RE, - 1998. - № 6, - С. 53-54

2. Вайну Я.Я.-Ф. Корреляция рядов динамики. М: Статистика, 1977. — 119с.

3. Вирт Н. Алгоритмы + структуры данных = программы: Пер. с англ. — М.: Мир, 1985.-406 с.

4. Ганти Венкатеш, Герке Йоханнес, Рамакришнан Раджу. Добыча данных в сверхбольших базах данных // Открытые системы. 1999. - № 9-10.

5. Гик Дж., ван. Прикладная общая теория систем. — М.: Мир, 1981.

6. Грабер М. Справочное руководство по SQL: Пер. с англ. М.: ЛОРИ, 1997. ISBN 5-85582-022-Х.

7. Дейт К. Дж. Введение в системы баз данных: издание 7.- М.: Вильяме, 2001.-848с.

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

9. Дюран Б., Оделл П. Кластерный анализ: Пер. с англ. — М: Статистика, 1977.- 128 с.

10. Ю.Жамбю М. Иерархический кластер-анализ и соответствия: Пер. с франц.- М.: Финансы и статистика, 1988. 342 с.

11. Кириллов В.В. Структуризованный язык запросов (SQL). СПб.: ИТМО, 1994.-80 с.

12. Киселев М., Соломатин Е. Средства добычи знаний в бизнесе и финансах // Открытые системы. 1997. — № 4. - С. 41- 44.

13. Коннолли Т., Бегг К., Страчан А. Базы данных. Проектирование, реализация и сопровождение. Теория и практика. — М.: Вильяме, 2001. -1120с.

14. Корнеев В.В., Гареев А.Ф., Васютин С.В., Райх В.В. Базы данных. Интеллектуальная обработка информации. // М.: Нолидж, 2001

15. Кодц Е.Ф. Реляционная модель данных для больших совместно используемых банков данных // СУБД. 1995. — № 1. - С. 145-160.

16. Кравчук В.А. и др. Введение в Oracle PL/SQL. К.,: Издательство «ДиаСофт». 1998.-400 с.

17. Кречетов Н., Иванов П. Продукты для интеллектуального анализа данных // ComputerWeek-Москва, 1997. - № 14-15. - С. 32-39.

18. Крейг С. Маллинс. Администрирование баз данных. Полное справочное руководство по методам и процедурам. М.: Кудиц-образ. 2003. - 752с.

19. Кузнецов С.Д., Артемьев В. Обзор возможностей применения ведущих СУБД для построения хранилищ данных (Data Warehouse) // 3-я ежегодная конференция Корпоративные базы данных '98: Доклады и тезисы/Центр информационных технологий. М., 1998.-С. 153-161.

20. Мандель И.К. Кластерный анализ. М.: Финансы и статистика, 1988. — 176 с.

21. Мартин Дж. Организация баз данных в вычислительных системах. М.: Мир.-1980.-662 стр.

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

23. Пейдж Вильям Дж., Хьюз Натан, Остин Дэвиди др. Использование Oracle 8. К.,М.,СПб.: Издат. Дом «Вильяме», 1998. - 752с.

24. Прижиялковский В.В. Сложный анализ данных большого объема: новые перспективы компьютеризации // СУБД. — 1996. — № 4. — С. 71-83.

25. Раден Н. Данные, данные и только данные // ComputerWeek-Москва. -1996.-№8.-С. 28.

26. Райордан P.M. Основы реляционных баз данных. — М.: Русская редакция, 2001.-384с.

27. Ролланд Фред. Основные концепции баз данных. — М.: Вильяме, 2002. — 256с.

28. Сахаров Л.Л. Концепция построения и реализации информационных систем, ориентированных на анализ данных // СУБД — 1996. — № 5. С. 55-70.

29. Сахаров Л.Л. Принципы проектирования и использования многомерных баз данных (на примере Oracle Express Server) // СУБД. 1996. — № 3. -С. 44-59.

30. Туо Дж. Инструменты для анализа информации на настольных ПК // ComputerWeek-Москва. 1996. - № 38. - С. 34-35,46.

31. Туо Дж. Каждому пользователю свое представление данных // ComputerWeek-Москва. - 1996. -№ 38. С. 1, 32-33.

32. Ульман Дж., Уцдом Дж. Введение в системы баз данных. — М.: Лори, 2000. 274с.

33. Уоссермен Ф. Нейрокомпьютерная техника: Теория и практика. — М.: Мир, 1992.-240 с.

34. Харрингтон Дж. Проектирование реляционных Баз Данных. Просто и доступно. М.: Лори, 2000. - 230с.

35. Эделстейн Г. Интеллектуальные средства анализа, интерпретации и представления данных в информационных хранилищах // ComputerWeek-Москва.- 1996.-№ 16.-С. 32-33.

36. Agrawal R. and Srikant R. Fast algorithms for mining association rules. In Proceedings of the 20th VLDB Conference, Santiago, Chile, 1994. P. 487499.

37. Agrawal R. and Srikant R. Mining Sequential Patterns. In Proceedings of the 11th International Conference on Data Engineering, Taipei, Taiwan, 1995. P. 3-14.

38. Agrawal R. et al. Fast Discovery of Association Rules. Advances in Knowledge Discovery and Data Mining, Fayyad U.M. et al., eds., AAAI/MIT Press, Menlo Park, Calif., 1996, P. 307-328.

39. Agrawal R., Imilienski Т., and Svvami A. Database Mining: A perfomance Perspective. IEEE Transaction on Knowledge and Data Engineering, №5(6): -december 1993. P. 914-925.

40. Agrawal R., Imilienski Т., and Swami A. Mining Association Rules between Sets of Items in Large Databases. Proc. of the ACM SIGMOD Int'l Conf. on Management of Data. May 1993. P. 207-216.

41. Agrawal R., Lin K., Sawhney S., and Shim K. Fast similarity search in the presence of noise, scaling and translation in time-series databases. In Proc. of the Int'l Conf. on Very Large DataBases (VLDB), 1995. P. 490-501.

42. Alalouf C. Hybrid OLAP. — St. Laurent, Canada: Speedware Corporation Inc.,1997.

43. An Introduction to Multidimensional Database Technology. Kenan System Corporation, 1995.

44. ANSI X3.135-1992, American National Standard for Information Systems -Database Language SQL, November, 1992.

45. Boulding К. E. General Systems Theory The Skeleton of Science // Management Science. 1956. - № 2.

46. Bradley P., Fayyad U., and Reina C. Scaling Clustering Algorithms to Large Databases. Proc. 4th Int'l Conf. Knowledge Discovery and Data Mining, AAAI Press, Menlo Park, Calif., 1998, P. 9-15.

47. Brand E., Gerritsen R. Data mining and Knowledge Discovery // DBMS. —1998.-№7.

48. Brin S., Motwani R., Silverstain C. Beyond Market Baskets: Generalizing Association Rules to Correlations. SIGMOD Conference. 1997. P. 265-276.

49. Brin S. et al. Dynamic Itemset Counting and Implication Rules for Market Basket Data. Proc. ACM SIGMOD Int'l Conf. Management of Data, ACM Press, New York, 1997, P. 255-264.5Q.CFO Vision. SAS Institute Inc., 1997.

50. Codd E. F. Л Relational Model of Data for Large Shared Databanks // Communications of the ACM. -v. 13.6, 1970. - P. 377-387.

51. Codd E.F. Relational database: a practical foundation for productivity // Communications of the ACM, v. 25.2. - 1982. - P. 109-117.

52. Codd E.F., Codd S.B., Salley C.T. Providing OLAP (On-Line Analytical Processing) to User-Analysts: An IT Mandate. E.F. Codd & Associates, 1993.

53. Demarset M. Building the Data Mart. DBMS. 1994. - №7. - P. 44-50.

54. Ester M. et al. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. Proc. 2nd Int'l Conf. Knowledge Discovery Databases and Data Mining, AAAI Press, Menlo Park, Calif., 1996, P. 226231.

55. Fausett L. V. Fundamentals of Neural Networks: Architectures, Algorithms, and Applications. Englewood Cliffs, New Jersey: Prentice Hall, 1994. — P. 461.

56. Fayyad U.M. et al., eds. Advances in Knowledge Discovery and Data Mining, AAAI/MIT Press, Menlo Park, Calif., 1996.

57. Frawley W.L., Piatetsky-Shapiro G., Matheus C.J. Knowledge discovery in database: An overview. Al Magazine. 1992. - №13(3). - P. 57-70.

58. Fuernkranz J. A Brief Introduction to Knowledge Discovery in Databases // OEGAI Journal. 1995.-№ 14(4).-P. 14-17.

59. Ganti V. et al. Clustering Large Datasets in Arbitrary Metric Spaces. Proc. 15th Int'l Conf. Data Eng., IEEE CS Press, Los Alamitos, Calif., 1999, P. 502-511.

60. Gehrke J., Ramakrishnan R., and Ganti V. RainForest- a Framework for Fast Decision Tree Construction of Large Datasets. Proc. 24th Int'l Conf. Very Large Data Bases, Morgan Kaufmann, San Francisco, 1998, P. 416-427.

61. Gray J. Chaudhuri S., Bosworth Л., etc. Data Cube: Л relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals // Data Mining and Knowledge Discovery. 1997. -№ 1. - P. 29-53.

62. Guha S., Rastogi R., and Shim K. CURE: An Efficient Clustering Algorithm for Large Databases. Proc. ACM SIGMOD Int'l Conf. Management of Data, ACM Press, New York, 1998, P. 73-84.

63. Harinarayan V., Rajaraman A., Ullman J.D. Implementing Data cubes efficiently // SIGMOD Conference. Montreal, CA, - 1996.

64. Inmon W.H. Building the Data Warehouse (Second Edition). — NY, NY: John Wiley, 1993.

65. Johnson Joe. Using Oracle Database Auditing to Tune Performance // Oracle magazine, November 1999.

66. Knowledge Discovery Through Data Mining: What Is Knowledge Discovery? Tandem Computers Inc., 1996.

67. Kosko B. Neural Networks and Fuzzy Systems: A Dynamical System Approach to Machine Intelligence. Englewood Cliffs, New Jersey: Prentice Hall, 1992.-452 p.

68. Kramer S. Structural Regression Tree. — Vienna: Austrian Research Institute for Artificial Intelligence, Technical Report OEFAI-TR-95-35, 1995.

69. Kulkarni J., King R. Business Intelligence System and Data Mining. — SAS Institute Inc., 1996.

70. Mannila H., Toivonen H., and Verkamo A.I. Discovering Frequent Episodes in Sequences. Proc. 1st Int'l Conf. Knowledge Discovery Databases and Data Mining, AAAI Press, Menlo Park, Calif., 1995, P. 210-215.

71. Mannila H., Toivonen H. On an algorithm for finding all interesting sentences. In Cybernetics and Systems, Volume II, The Thirteenth European Meeting on Cybernetics and System Research, Vienna, Austria, April 1996. — P. 973-978.

72. Mehta M., Agrawal R. and Rissanen J. Sliq: A fast scalable classifier for data mining. March 1996. P. 18-32.

73. Meiton J. and Simon A.R., "Understanding The New SQL: A Comlete Guide", Morgan Kaufmann. 1993. '

74. Michie D., Spiegelhalter D.J., and Taylor C.C. Machine Learning, Neural and Statistical Classification, Ellis Horwood, Chichester, UK. 1994.

75. Mumick I.S., Quass D., Mumick B.S. Maintenance of Data Cubes and Summary Tables in a Warehouse. Standford University, Database Group. 1996.

76. Newquist H.P. Data Mining. The AI Metamorphosis // Database Programming and Design. 1996. - № 9.

77. Ng R.T. and Han J. Efficient and Effective Clustering Methods for Spatial Data Mining. Proc. 20th Int'l Conf. Very Large Data Bases, Morgan Kaufmann, San Francisco. 1994. P. 144-155.

78. Park J.S., Chen M.-S., and Philip S.Y. An Effective HashBased Algorithm for Mining Association Rules. Proc. ACM SIGMOD Int'l Conf. Management of Data, ACM Press, New York. 1995. P.175-186.

79. Parsaye K. A Characterization of Data mining technologies and Processes // The Journal of Data Warehousing. 1998. - № 1.

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

81. Pyne A. The SAS System and Web Integration. SAS Institute Inc. 1996.

82. Raden N. Star Schema. Santa Barbara, CA: Archer Decision Sciences, Inc. 1995-1996.

83. Ramaswamy S., Mahajan S., and Silbershatz A. On the Discovery of Interesting Patterns in Association Rules. Proc. 24th Int'l Conf. Very Large Data Bases, Morgan Kaufmann, San Francisco. 1998. P. 368-379.

84. Silverstain C, Brin S., Motwani R., Ullman J.D. Scalable Techniques for Mining Causal Structures. Data Mining and Knowledge Discovery. 4(2/3). 2000. P. 163-192.

85. Srikant R. and Agrawal R. Mining generalized association rules. 1995. P. 407-419.

86. Toivonen H. Sampling Large Databases for Association Rules. Proc. 22nd Int'l Conf. Very Large Data Bases (VLDB), Morgan Kaufmann, San Francisco. 1996.-P. 134-145.

87. Tukey J. Exploratory Data Analysis. NY: McMillan. 1973.

88. Zhang Т., Ramakrishnan R., and Livny M. Birch: An Efficient Data Clustering Method for Large Databases. Proc. ACM SIGMOD Int'l Conf. Management of Data, ACM Press, New York. 1996. P. 103-114.