Содержание к диссертации
Введение
1. Сопровождение баз данных корпоративного уровня и современные методы аналитической обработки данных 14
1.1. Обзор особенностей сопровождения баз данных корпоративного уровня 14
1.2. Анализ современных методов аналитической обработки данных.. 17
1.3. Обзор сфер применения технологии интеллектуального анализа данных 34
Выводы по главе 1 38
2. Анализ методов обнаружения устоявшихся ассоциаций в данных, разработка методов реализации и структур данных 40
2.1. Алгоритмы поиска устоявшихся ассоциаций в данных 40
2.1.1. Алгоритм Apriori 45
2.1.2. Методы оптимизации алгоритма Apriori 50
2.1.2.1. Алгоритм «Разбиение» 50
2.1.2.2. Алгоритм «Выборочный анализ» 53
2.1.2.3. Алгоритм «Динамический подсчет наборов» 57
2.2. Разработка методов реализации алгоритмов в реляционных СУБД 62
2.2.1. Проблемы реализации алгоритмов поиска устоявшихся ассоциаций в данных 62
2.2.2. Структура исходных данных 64
2.2.3. Разработка структур рабочих и результирующих данных 67
2.2.4. Реализация алгоритмов и служебных функций 71
2.3. Сравнительный анализ алгоритмов 78
2.3.1. Условия и методы сравнительного анализа 78
2.3.2. Анализ сравнительных характеристик работы алгоритмов 80
Выводы по главе 2 88
3. Оперативное обнаружение устоявшихся ассоциаций в данных 90
3.1. Задача оперативного обнаружения устоявшихся ассоциаций в данных 90
3.2. Разработка методов реализации оперативной обработки данных ... 92
3.3. Параметры обработки и оценка результатов 100
Выводы по главе 3 106
4. Разработка реализации оперативного обнаружения устоявшихся ассоциаций в данных для сопровождения рбд автоматизированной системы оперативного диспетчерского управления ООО «Пермтрансгаз» 108
4.1. Особенности реализации базы данных системы оперативного диспетчерского управления 108
4.2. Сбор исходных статистических данных использования БД 111
4.3. Обработка статистических данных использования БД 117
4.4. Анализ результатов обработки данных 120
Выводы по главе 4 123
Заключение 125
Литература 127
Приложение 135
- Обзор особенностей сопровождения баз данных корпоративного уровня
- Проблемы реализации алгоритмов поиска устоявшихся ассоциаций в данных
- Разработка методов реализации оперативной обработки данных
- Сбор исходных статистических данных использования БД
Введение к работе
Современный уровень развития аппаратных и программных средств с некоторых пор сделал возможным повсеместное ведение баз данных оперативной информации на всех уровнях управления. В процессе своей деятельности промышленные предприятия, корпорации, ведомственные структуры, органы государственной власти и управления, их подразделения технического и программного обеспечения накопили большие объемы данных. Они хранят в себе большие потенциальные возможности по извлечению полезной аналитической информации, на основе которой можно выявлять скрытые тенденции, строить стратегию развития, находить новые решения.
Большие объемы и сложность потоков оперативной и статистической информации предполагают использование мощных систем управления базами данных (СУБД) [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. Анализ существующих средств аналитической обработки данных и, в частности, методов ИАД и задач обнаружения устоявшихся ассоциаций в данных и проблем их реализации.
Анализ специфики оперативной обработки данных с целью выявления устоявшихся ассоциаций в данных, области ее применения и основных требований к реализации.
Разработка методов реализации алгоритмов поиска устоявшихся ассоциаций в данных в рамках реляционных баз данных, включая разработку структуры рабочих данных и методов их обработки, выбор и обоснование формата входных данных, средств преобразования к требуемому формату.
Сравнительный анализ наиболее эффективных существующих алгоритмов поиска устоявшихся ассоциаций в данных, определение их достоинств и недостатков, выявление возможных путей оптимизации их выполнения.
Разработка методов, основанных на модификации и синтезе существующих алгоритмов, обеспечивающих возможности оперативного выявления изменений закономерностей в оперативных данных (в множестве устоявшихся ассоциаций). Обработка должна выполняться параллельно остальным процессам оперативной обработки данных, что накладывает дополнительные требования по минимизации затрат ресурсов вычислительной системы.
Разработка методов параметризации обработки данных и расширения атрибутики рабочих и результирующих данных, обеспечивающих возможность учета особенностей обработки данных и трактовку семантики получаемых данных.
Реализация программных модулей оперативного обнаружения ассоциаций для анализа данных аудита использования объектов промышленной БД пользователями и процессами.
Теоретическая значимость диссертации заключается в выполнении синтеза результатов современных исследований и разработок в области
аналитической обработки данных, в части задач интеллектуалыюго анализа данных [8], связанных с обнаружением устоявшихся ассоциаций в данных [40]. Существующие подходы к решению задач выявления закономерностей в данных [4], в частности, устоявшихся ассоциаций в данных, связаны с обработкой больших объемов ранее накопленных данных и требуют значительных затрат ресурсов на выполнение обработки, в следствие чего практически не пригодны для обработки поступающих в реальном времени данных с целью оперативного выявления происходящих изменений в закономерностях. В данной работе осуществляется попытка разработки методов, позволяющих осуществлять оперативное обнаружение изменений в тенденциях формирования наборов в данных при решении задач сопровождения промышленных БД корпоративного уровня. Научная новизна работы заключается в:
выполнении сравнительного анализа ряда современных, масштабируемых алгоритмов поиска устоявшихся ассоциаций в данных, определение их достоинств и недостатков, выявлении возможности оптимизации выполнения алгоритмов;
разработке алгоритма оперативного обнаружения устоявшихся ассоциаций в данных, позволяющего выявлять значимые изменения в тенденциях формирования наборов по мере их появления;
разработке методов параметризации обработки данных, позволяющих учитывать широкий спектр особенностей реализации и использования, и расширения возможностей толкования семантического значения получаемых данных за счет расширения спектра атрибутов рабочих и результирующих данных;
разработке методов использования предложенных алгоритмов и методов для автоматизации аналитической обработки данных аудита использования объектов БД в рамках выполнения задач
сопровождения БД корпоративного уровня, разработке и апробации элементов ИС.
Разработанные алгоритмы и методы расширяют возможности выявления и анализа тенденций и закономерностей [40], в частности, анализа физической реализации базы данных и информационных систем [18], с точки зрения выполняемых задач обработки данных, сокращают затраты ресурсов на выполнение анализа, автоматизируют процесс мониторинга использования базы данных, повышают качество информационного обслуживания администраторов.
В практическом плане ценность диссертации заключается в разработке и апробации методик реализации оперативного обнаружения устоявшихся ассоциаций в данных аудита [23] использования объектов БД для осуществления анализа релевантности физической структуры данных, выявления трендов поведения пользователей и прикладных систем и отклонений от них. Результаты, полученные в диссертации, доведены до практического использования в предприятиях нефтегазовой промышленности. Разработан программный комплекс, позволяющий в интерактивном режиме получать оперативные данные об использовании объектов базы данных для принятия решений по перепроектированию и модификации физической структуры БД, настроек СУБД, программных комплексов и обеспечению безопасности и сохранности данных.
Разработанные методы и алгоритмы прошли апробацию и внедрены для практического применения в ЗАО«АтлантикТрансгазСистема», 000«Пермтрансгаз», а также используются в учебном процессе в МАДИ(ГТУ).
Диссертационная работа состоит из введения, 4-х глав основного текста, заключения, списка литературы, состоящего из 91-го наименования и приложения.
Во введении подчеркивается актуальность проведенных исследований, поставлена цель, сформулированы решаемые задачи и приводится краткое содержание глав диссертации.
В первой главе рассмотрены основные аспекты и особенности сопровождения промышленных БД корпоративного уровня, необходимость и перспективы автоматизации аналитической обработки данных при выполнении ряда задач сопровождения. Представлены основные концепции хранения и анализа корпоративных данных. Проанализированы современные тенденции и основные направления в области автоматизации аналитической обработки данных, представлены три базовые сферы анализа данных. Особое внимание уделено, в частности, интеллектуальному анализу данных (ИАД) (сфера закономерностей). Представлена классификация задач по типам извлекаемой информации, классификация стадий и технологических методов ИАД. Рассмотрены основные сферы применения ИАД.
Во второй главе приводится формализация задачи обнаружения устоявшихся ассоциаций в данных, детально рассматриваются наиболее эффективные, с точки зрения обработки больших объемов данных, масштабируемые алгоритмы, выделяются их основные особенности с точки зрения обработки данных. Выделяются основные проблемы реализации и предлагаются методы реализации структур рабочих данных и их обработки с учетом реализации в рамках реляционной СУБД. Рассматриваются варианты представления исходных данных и способы их обработки. Предлагается вариант реализации предложенных методов в рамках реляционных СУБД корпоративного уровня [26] с использованием имеющихся в них средств оптимизации обработки данных. Приводятся результаты сравнительного анализа реализаций алгоритмов посредством предложенных методов в рамках СУБД Oracle. По результатам анализа алгоритмов и реализаций выделяется этап подсчета обеспечений наборов
связанный со сканированием исходного множества данных, как основное препятствие для повышения оперативности обработки данных ввиду значительных затрат на его выполнения. Также отмечается то, что незначительное увеличение множества подсчитываемых наборов не оказывает критичного влияния на быстродействие обработки.
В третьей главе сформулирована задача оперативного обнаружения устоявшихся ассоциаций в данных, область ее применения и место среди существующих методов автоматизации аналитической обработки данных. Разрабатывается алгоритм решения данной задачи, невысокие требования к ресурсам вычислительной системы которого, позволяют использовать его параллельно с задачами оперативной обработки транзакций (системами класса OLTP, OLAP). В основе алгоритма лежит синтез современных разработок в данной сфере, а также предлагаемый метод расширения рабочего множества и его атрибутики, позволяющий осуществлять пересчет обеспечений наиболее интересных наборов по мере поступления новых данных и значительно снизить частоту и сложность обработки большого объема ранее накопленных данных. Сформулирована и решена задача по параметризации выполнения обработки и расширению возможности трактовки семантики результатов обработки за счет введения дополнительных справочных атрибутов в рабочем множестве. Решение задачи позволило расширить возможности учета особенностей предметной области и реализации обработки данных, а также трактовки семантики результатов обработки.
В четвертой главе приведено описание программного комплекса, реализующего предложенный алгоритм обработки данных с целью автоматизации сопровождения корпоративной БД предприятий нефтегазовой промышленности в части выявления трендов использования объектов БД. Приведено описание основных особенностей физической реализации и использования целевой БД, описание методики сбора и
обработки данных аудита в рамках СУБД Oracle, под управлением которой реализуются данные БД. Приводится описание основных моментов реализации профаммного комплекса, осуществляющего обработку данных посредством предложенного алгоритма, и результаты его использования, полученные в начальный период использования. Также приводится описание отдельных фактов применения полученных данных при выполнении анализа релевантности физической структуры БД и эффективности реализации обработки данных в рамках компонентов ИС, а также эффекта от принятия соответствующих решений и выполнения изменений в структуре БД и методах обработки данных в профаммных модулях.
По результатам использования сделаны выводы об эффективности использования данного метода и профаммного комплекса, в частности, в рамках автоматизации обработки данных аудита при выполнении их анализа.
В заключении представлены основные результаты работы.
Основные положения и результаты диссертации докладывались и обсуждались на заседаниях кафедры «Автоматизированные системы управления» МАДИ (ГТУ) в 2001-2003 годах, на республиканских межрегиональных и международных научно-технических конференциях, симпозиумах и семинарах (2000-2003 гг.).
Обзор особенностей сопровождения баз данных корпоративного уровня
Сопровождение реляционной базы данных (РБД) и системы управления базами данных (СУБД) корпоративного уровня является чрезвычайно сложной и многогранной задачей [7,13,18,34]. БД может иметь чрезвычайно сложную структуру, хранить и обрабатывать огромные объемы данных, выполнять множество задач и обслуживать большое количество пользователей одновременно. При этом, в связи с современными требованиями к динамике развития, она может практически постоянно находиться в стадии модификации и модернизации, а задержки в ее работе, которые могут возникнуть при обслуживании и модификации, могут быть недопустимыми. Значительно возрастает роль физического проектирования. Для обеспечения эффективной работы необходимо выполнять целый комплекс сложных работ. Среди основных задач можно выделить [23]: Установка и модернизация самой СУБД, ее компонентов и инструментальных средств Проектирование и создание баз данных Планирование, распределение и перераспределение пространства для хранения данных Модификация и оптимизация структуры БД с учетом меняющихся требований Регистрация пользователей и выделение им привилегий Контроль и учет доступа пользователей к БД Резервирование и восстановление БД Обеспечение защиты данных Оптимизация производительности БД И многое другое. При этом в случае БД корпоративного уровня выполнение задач многократно усложняется в связи со сложностью охватываемых предметных областей, их количеством и сложностью взаимосвязей, масштабностью и сложностью моделей данных, количеством обслуживаемых автоматизированных систем, программных комплексов и пользователей, значительным диапазонам требований и т.п. Так, промышленные БД, применяемые в нефтегазовом комплексе, должны хранить огромные объемы исторических данных, обеспечивать возможность быстрой обработки больших потоков оперативных данных, поддерживать выполнение сложных аналитических обработок, осуществлять значительный объем вычислений. При этом, данные БД находятся в постоянной динамике. Помимо постоянной обработки растущих объемов данных могут меняться как сами данные, так и требования к ним, добавляться новые данные, создаваться и модернизироваться фрагменты БД и вся БД в целом, в связи с меняющимися требованиями, изменениями программного обеспечения и вводом новых систем, необходимостью реализации новых концепций и взглядов на данные и объект автоматизации, изменениями требований к полноте данных и пригодности их для различных видов обработки и т.п. Эффективная реализация сопровождения в подобных условиях становится чрезвычайно сложной и нетривиальной задачей.
Во многом, эффективность решения этих задач зависит от объема имеющейся информации и от пригодности данной информации для анализа. Классически для части описанных задач используется описание предметной области различной степени формализации, описания систем, приложений, потоков данных и т.п. При этом сама БД содержит в себе достаточно большой объем полезной при сопровождении информации. Самая разнообразная информация о БД, ее структуре, элементах и их характеристиках может быть получена из словаря данных [18,23]. Помимо этого, СУБД корпоративного уровня предоставляют множество возможностей аудита текущей активности, состояния системы и объектов, использования ресурсов [13], сбора справочных и статистических данных и т.п. по БД и самой СУБД. Данные возможности могут быть использованы как для обеспечения функционирования и безопасности, так и для настройки производительности, модификации физической структуры и распределении пространства, принятия решений по модернизации программ, работающих с данными и т.п.
Помимо встроенных средств аудита и сбора данных аудита существует набор средств визуализации показателей аудита. Тем не менее, информация все равно предстает в непосредственном виде (либо точные показатели, либо графики, позволяющие отследить вид изменений показателей, статистика). Существует так же набор формализованных методик извлечения информации, более пригодной для анализа и принятия решений [66], но, как правило, они представляют собой комплекс запросов и вычислений, нацеленных на проверку ограниченного перечня гипотез.
Данные средства и методы автоматизируют сопровождение лишь частично. Большой объем рутинной и аналитической работы остается неавтоматизированным, что снижает эффективность и повышает вероятность ошибок. Большая часть потенциально полезной информации вообще оказывается вне поля зрения.
Эффективным решением данной проблемы может стать использование методов аналитической обработки данных, которые позволят облегчить обработку данных о сопровождаемой БД, СУБД и использующих их информационных системах, своевременно выявлять тенденции и закономерности, обнаруживать отклонения и выявлять их причины. При этом, в отличие от простого сбора и визуализации статистических данных и количественных параметров текущей активности, предоставляющих «сырые» данные, необходимые для анализа принятия решений, и методик рутинной проверки ограниченного перечня существующих гипотез, данный подход позволит в большей степени автоматизировать работу аналитиков, представляя данные в наиболее удобной для анализа форме, снизить вероятность ошибок, связанными с ограничениями человеческих возможностей, автоматизировать выявление и проверку гипотез и скрытых закономерностей.
Проблемы реализации алгоритмов поиска устоявшихся ассоциаций в данных
Методы поиска устоявшихся ассоциаций в данных ориентированы на обработку, так называемых «транзакционных» данных. Транзакция — набор логически связанных действий или элементов, трактуемый как единое целое (должны быть выполнены (присутствовать) все, либо транзакция отменяется). Таким образом, анализируемые данные, представляют собой наборы (транзакции), состоящие из элементов, основной характеристикой которых является условная общность и неделимость существования элементов, входящих в один набор (транзакцию), во времени и пространстве. Вид транзакционных данных может значительно различаться. Основное различие заключается в методе хранения данных об одной транзакции. В тех случаях, когда количество элементов в транзакциях может значительно изменяться как в силу возможности различной наполненности транзакций элементами, так и в силу изменения количества допустимых элементов, а также требуется снизить избыточность, используется нормализованная [23,51,15,52,22] запись данных о транзакциях. При этом данные об одной транзакции состоят из нескольких записей в таблице, каждая из которой является записью о единичном элементе, входящем в транзакцию и самой транзакции (например, код транзакции), к которой он относится (Рис. 2.5).
В тех же случаях когда количество элементов, их вид и предназначение во всех транзакциях статичны, а их количество не велико, запись о транзакции целесообразно хранить в единой ненормальзиванной записи таблицы (например, статистическая информация о состоянии статичного ограниченного набора датчиков) (Рис. 2.6).
В зависимости от вида хранения информации о транзакциях изменяются и методы, применяемые для их обработки. Второй вариант хранения информации является более удобным для аналитической обработки (менее трудоемким), но менее универсальным, чем первый. Первый вариант более приемлем для систем оперативной обработки данных, но в случае интеллектуальной обработки потребует выполнения дополнительных операций (циклы чтения, группировки и т.п.) либо создания витрин или хранилищ данных «поверх» существующих структур.
Задачи выполнения анализа устоявшихся ассоциаций накладывают на данные еще одно ограничение. Для каждого элемента может учитываться только факт его участия в наборе. В тех случаях, когда требуется учитывать различные значения числовых или символьных данных, необходимо осуществлять преобразование данных. Так, например, если необходимо обрабатывать статистические данные, которые содержат поле с полом анкетируемого, поле месячного дохода и поле города проживания, нельзя говорить просто о наличие данного элемента в наборе. Если, например, данные о поле хранятся в виде целого числа с допустимыми значениями 0 и 1 (0 - мужской, 1 — женский) и единицу мы считаем признаком участия элемента в наборе, то учтены будут только женские анкеты. Ситуация усложняется при наличии большего спектра допустимых значений, как в полях дохода и города. Обработка подобных данных может быть осуществлена путем разбиения множества значений на конечное число не пересекающихся подмножеств. Каждому подмножеству ставится в соответствие элемент, факт вхождения в набор которого означает принадлежность исходного значения данному подмножеству. Так, элемент пол должен быть преобразован к двум элементам: мужской пол и женский пол. Одним из вариантов преобразования данных о доходе является расчет логарифма дохода и его округление, в результате чего будет получено ограниченное количество усредненных значений порядка дохода, каждый из которых можно выделить в отдельный элемент. Таким образом, можно будет анализировать включение в наборы дохода некоторого порядка. Для всех вариантов города должны быть созданы свои элементы. Следует отметить, что учитываться могут не все возможные значения. Так элементы могут быть созданы для определенных величин дохода или для определенного списка городов. Преобразование данных может быть выполнено предварительно путем создания представления или таблицы хранилища данных, а также может выполняться динамически при обработке. Динамическое преобразование возможно на стадии выборки данных либо на стадии формирования и подсчета кандидатов. Структура данных, используемая для создания и подсчета наборов-кандидатов, является отдельным, достаточно значимым вопросом. Данная структура должна поддерживать следующие операции: 1. Добавление нового набора-кандидата; 2. Подсчет обеспечений для каждого набора-кандидата; 3. Изменение состояний наборов (из подсчитываемых в уже подсчитанные или не подсчитываемые и из слабо обеспеченных в часто встречающиеся и т.п.); 4. Нахождение новых наборов-кандидатов на основе наборов, определенных как часто встречающиеся. Структура данных, используемая для формирования наборов и подсчета обеспечений в алгоритме Apriori и ему подобных, подобна хеш-дереву [36,49], обеспечивающему хранение необходимой информации в узлах. Это дерево обладает следующими свойствами: Каждый набор отсортирован по элементам; Каждый подсчитываемый или подсчитанный набор имеет узел, ассоциированный с ним (также как и все его префиксы); Корневым узлом является пустой набор; Все 1-элементные наборы привязаны к корневому узлу, и их ветвь помечена элементом, представляющим ее; Все другие наборы привязаны к их префиксам, содержащим все, кроме последнего, элементы. Они помечены этим последним элементом. На Рис. 2.7 изображено простое дерево описанной формы. Пунктирной линией показан путь, проходимый при подсчете транзакций с элементами ABC как A, AB, ABC, АС, В, ВС и С. Таким образом, набор представляет собой последовательность узлов, начиная с самого старшего. Каждый узел, кроме корневого, представляет собой элемент, входящий в некий набор и, в свою очередь, последний элемент в подмножестве набора.
Все характеристики наборов ассоциированы с последними узлами, представляющими их. Соответственно, каждый узел, кроме корневого, содержит счетчик набора, номер точки начала подсчета набора (если необходимо), состояние (подсчитываемый набор кандидат, набор негативной области, обеспеченный набор и т.п.) и его ветви (если внутренний узел), представляющие надмножества. Так, можно сказать, что 2-элементные наборы АВ, АС и AD представлены, соответственно, узлами В,С и D, привязанными к узлу А.
Проиллюстрируем работу с деревом на примере алгоритма Apriori: 1. На первом этапе в дерево добавляются узлы первого уровня (привязанные к корню), соответствующие всем допустимым элементам. При подсчете обеспечений наборов, входящих в очередную транзакцию, осуществляется переход по этим узлам, и если соответствующий элемент встречается в транзакции, то счетчик, ассоциированный с ним наращивается.
Разработка методов реализации оперативной обработки данных
Представленные выше методы обработки данных предусматривают выполнение циклических операций полного сканирования данных, что при всех методах оптимизации ведет к достаточно значительным затратам ресурсов, особенно в условиях интенсивного накопления огромных объемов данных, характерного для современного уровня развития информационных технологий. В данной работе предлагается реализовать методы, позволяющие оперативно отслеживать значимые изменения в закономерностях формирования наборов. Т.е. информация об изменениях должна быть получена максимально близко к моменту, с которого изменения можно считать значимыми (на основе получаемых данных можно с определенной степенью уверенности говорить о существовании закономерности).
С учетом того, что, помимо оперативного обнаружения существенных изменений, может быть актуальным отслеживать незначительные изменения в закономерностях, отслеживать локальные изменения и т.п., которые могут быть просто незаметны на фоне ранее накопленных данных и выявленных закономерностей, обработка может выполняться не на всем множестве, а на отдельной его части. Тем не менее, необходимость обеспечения репрезентативности выборки [91] и необходимость большой частоты выполнения обработки данных для повышения оперативности, приводит к достаточно серьезным затратам ресурсов в связи с необходимостью многократных операций сканирования данных и сопутствующих операций обработки данных о наборах. Это может отрицательно сказываться на выполнении оперативных задач обработки транзакций (функционировании OLTP и OLAP приложений). В связи с этим необходимо разработать методику, позволяющую снизить количество таких операций и затраты на их выполнение.
В данной работе предлагается реализовать гибридный вариант алгоритмов ДПН [49] и «Выборочного анализа» [91] и дополнить его методами, позволяющими контролировать значимые изменения закономерностей по мере их появления без необходимости выполнения повторных полных обработок данных.
На первом этапе посредством алгоритма ДПН обрабатываются ранее накопленные данные (исходное множество D). При этом может обрабатываться как все множество, так и некое репрезентативное подмножество D cD (как в «Выборочном анализе»). Для выполнения дальнейшей обработки данных о наборах, с учетом поступающих в реальном времени данных о транзакциях, предлагается расширить состав рабочего множества подсчитываемых наборов второго этапа. В результат обработки исходного множества D, помимо обеспеченных наборов L (Формула 2.3) следует включить все одноэлементные наборы С/, что соответствует множеству С]=Е (Формула 2.1), и наборы негативной области Bd (Формула 2.4).
При этом для всех этих наборов следует хранить величины их обеспечений. Множество этих наборов будет являться рабочим, на котором будет осуществляться подсчет обеспечений при поступлении новых данных.
На втором этапе по факту прихода информации об очередной транзакции (выполнение записи в БД) необходимо осуществлять проверку наличия наборов, входящих в нее, в множестве R и осуществлять соответствующую модификацию информации об обеспечении данных наборов. Данная операция может выполняться в фоновом режиме после осуществления записи данных о транзакции, что позволит дополнительно снизить негативное влияние на процесс записи данных о транзакции.
Предлагаемый состав рабочего множества позволяет, с одной стороны значительно сократить размеры этого множества, в сравнении с вариантом включения всех возможных вариантов наборов р()\{0}, а с другой, включить в него все наборы, необходимые для отслеживания перехода «границы значимости», и создания новых наборов-кандидатов [49], что и представляет основной интерес. Данное решение основывается на том, что в первую очередь обеспеченными (значимыми для рассмотрения) могут стать наборы негативной области Bd и 1-элементные наборы С/ (набор может быть обеспеченным тогда и только тогда, когда все его поднаборы являются обеспеченными), а новые наборы-кандидаты могут формироваться на основе обеспеченных наборов L. Для всех же остальных необходимо чтобы наборы, являющиеся их подмножествами, стали обеспеченными наборами. Что касается уменьшения обеспечения, то оно представляет наибольший интерес, когда касается обеспеченных наборов. Также может представлять интерес факт снижения обеспечения набора негативной области. Т.е. получается, что в оперативном режиме мы отслеживаем обеспечение всех наборов .«пограничной» области (тех, которые могут в ближайшем будущем изменить свое состояние) и при смене их состояния знаем реальную величину их обеспечения, а это позволяет отказаться от цикла сканирования данных при изменении «значимости» наборов с целью ее расчета и можно просто продолжить подсчет на основе поступающих данных. Проверка обеспечения может потребоваться только для новых наборов-кандидатов, которые могут формироваться, когда в процессе подсчета изменений обеспечений будут выявляться новые обеспеченные наборы.
Таким образом, необходимо выполнить одну полноценную обработку накопленных данных при инициализации процесса оперативного обнаружения, подготовить информацию обо всех обеспеченных наборах, одноэлементных и наборах негативной области и отслеживать текущие транзакции, модифицируя информацию об обеспечении данных наборов. Несмотря на расширение рабочего множества R, в сравнении с множеством, используемом при типовой обработке, его величина, как правило, будет достаточно не велика (сравнима с величиной рабочего множества на первых этапах работы алгоритма «Выборочный анализ»), что позволит снизить затраты оперативной памяти и вычислительных ресурсов на обработку данных о наборах.
Помимо отслеживания перехода наборов в другую группу, в том случае если один из необеспеченных наборов становится обеспеченным, следует выполнить проверку возможности формирования новых наборов-кандидатов на основе данного набора. Процедура формирования наборов осуществляется аналогично описанной ранее (Параграф 2.2). Сформированные наборы добавляются к рабочему множеству R. Расчет обеспечения среди поступающих транзакций может быть выполнен сразу после формирования новых наборов-кандидатов.
Сбор исходных статистических данных использования БД
При проектировании и модификации БД необходимо учитывать данные о требованиях пользователей, выполняемых ими задачах и используемых блоках данных и особенностях их использования [13]. В рамках реализованной и эксплуатируемой БД значительный объем полезной информации может быть получен на основе данных о выполняемых транзакциях [18]. Каждая транзакция состоит из одной или нескольких операций обработки данных и затрагивает ряд объектов БД. На основе данных о транзакциях, среди прочего, может быть получена следующая информация:
Закономерности использования объектов БД (таблицы, представления, синонимы, триггеры, процедуры, пакеты и т.п.) в рамках одной операции обработки данных; Закономерности в перечне выполняемых пользователями операций обработки данных по отношению к определенным объектам БД и/или в рамках одной сессии; Нестандартные операции, выполняемые пользователями или приложениями (исключение из закономерностей); Группы пользователей и задач, использующих общие данные, вид использования и его частота; Закономерности в использовании ресурсов при выполнении различных задач. На основе этих данных могут приниматься решения, имеющие целью повышение эффективности работы БД и всей ИС, по структуре данных и их размещению, модификации пользовательских и серверных приложений и распределении их по вычислительным ресурсам, изменению системных настроек, параметров и структуры БД, распределению привилегий и многое другое. Анализ процессов обработки данных является ценным средством в руках администраторов, помогая им быстро и эффективно реагировать на изменяющиеся требования, вид использования и ведения данных и структур. Получение аналитической информации включает два этапа: Сбор статистики использования ресурсов и объектов пользователями и процессами; Анализ статистических данных и вывод результатов анализа. Первый этап может быть решен средствами аудита, предлагаемыми самой СУБД либо множеством средств аудита, поставляемых в виде самостоятельных программных решений и представленных на рынке. Для эффективного выполнения второго этапа предполагается использовать алгоритм оперативного обнаружения устоявшихся ассоциаций в данных, который позволит оперативно выявлять основные закономерности и тенденции в использовании БД и ее объектов (операции обработки данных и затрагиваемые ими объекты), что особенно актуально в случае постепенной модификации структуры данных и ввода новых подсистем, их изменения. Оперативная обработка позволит выявить закономерности, которые могли бы теряться в общем потоке, в виду своей краткосрочности, либо проявлялись бы со значительным опозданием (только когда фактов стало бы достаточно много и была бы проведена очередная стандартная обработка данных), периодические и апериодические отклонения в закономерностях. В рамках выполнения задачи реализации промышленной БД и ее сопровождения на стадии ввода в эксплуатацию и начальном этапе использования была поставлена задача проанализировать тенденции использования объектов БД в рамках единых транзакций с целью проверки эффективности реализации БД с точки затраты ресурсов на выполнение существующих задач и выявления возможных путей ее оптимизации по структуре, реализации и использованию. Самая полная и достоверная информация о наборах таблиц, используемых пользователями в рамках одного обращения к БД, может быть получена из самой БД [18,23]. Все события, системные или пользовательские процессы и основные их атрибуты в современной СУБД фиксируются. Информация записывается в системные переменные, таблицы, журналы и прочие структуры СУБД. Способ хранения информации определяется ее природой и предназначением. Информация о статических объектах БД и их свойствах хранится в таблицах словаря данных. Оперативная, постоянно изменяющаяся информация, связанная с текущими процессами и событиями заносится в системные переменные и постоянно перезаписывается. Оперативная информация, которая может представлять интерес для администратора (загрузка процессора, операции ввода вывода, использование оперативной памяти, подключенные пользователи их действия и состояния и т.п.), может быть извлечена из таблиц динамических показателей СУБД [23]. Параметры сбора статистики обычно задаются при создании БД и могут быть многократно изменены администратором в последующем. Режим сбора, статистики операций, выполняемых пользователями, и обращений к объектам БД может быть активирован вручную. В СУБД Oracle, под управлением которой реализована целевая БД, активация режима сбора подобной статистики включает два этапа: 1. Инициализация поддержки режима сбора статистики. Выполняется в виде присвоения параметру AUDIT_TRAIL файла инициализации значения «истинна».
