Алгоритмическое и методическое обеспечение повышения оперативности поиска данных в корпоративных информационных системах тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Либман, Михаил Сергеевич

• Либман, Михаил Сергеевич
• кандидат технических наук
• 2013

Оглавление диссертации кандидат технических наук Либман, Михаил Сергеевич

ОГЛАВЛЕНИЕ

СПИСОК СОКРАЩЕНИЙ

ВВЕДЕНИЕ

1.1. Поиск информации в КИС

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

1.3. Запросы с операцией поиска подстроки

1.4. Влияние неточности априорной оценки мощности выходного множества на оперативность поиска данных в КИС

1.5. Постановка задач исследования 37 Выводы к главе 1 42 ГЛАВА 2. АЛГОРИТМ ПРОГНОЗИРОВАНИЯ ОПЕРАЦИЙ

ОБРАБОТКИ ДАННЫХ И АПРИОРНОЙ ОЦЕНКИ МОЩНОСТЕЙ ВЫХОДНЫХ МНОЖЕСТВ ОПЕРАЦИЙ ОБРАБОТКИ ДАННЫХ

2.1. Разработка процедуры прогнозирования операций обработки данных,

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

2.1.1. Способ кластеризации операций обработки данных

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

2.1.2.1. Выбор способа кодирования хромосом решений в

генетическом алгоритме 59 2.1.2.2 Формирование начальной популяции генетического

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

алгоритма

2.1.2.4. Выбор критерия остановки работы генетического алгоритма

2.1.2.5. Описание разработанного генетического алгоритма

2.1.3. Способ синтеза операций обработки данных по кластерам

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

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

Выводы к главе 2

ГЛАВА 3. МЕТОДИКА ПОВЫШЕНИЯ ОПЕРАТИВНОСТИ ПОИСКА ДАННЫХ В КИС

3.1. Разработка методики повышения оперативности поиска данных

в КИС

3.1.1. Разработка способа хранения прогнозируемых операций обработки данных

3.1.2. Разработка способа передачи в КИС априорной оценки мощности выходного множества операции обработки данных

3.2. Схема методики повышения оперативности поиска данных в КИС 91 Выводы к главе 3 ' 94 ГЛАВА 4. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ РАЗРАБОТАННЫХ МЕТОДИКИ И АЛГОРИТМА

4.1. Описание экспериментальной КИС

4.2. Разработка программного обеспечения повышения оперативности поиска данных в КИС

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

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

4.4.1. Анализ работы разработанного генетического алгоритма

4.5. Оценка повышения оперативности поиска данных в КИС при использовании разработанной методики

4.2.1. Оценка накладных расходов при использовании разработанной методики повышения оперативности поиска данных в КИС

4.7. Практическое использование разработанной методики повышения оперативности поиска данных в КИС

4.7.1. Выбор подсистем для внедрения разработанной методики

4.7.2. Выбор способа реализации разработанной методики 117 4.7.3 Результаты внедрения разработанной методики повышения оперативности поиска данных в КИС

4.7.3.1. Использование разработанной методики в подсистеме внесения изменений конструкторско-технологического состава изделия

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

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

4.3.3.4. Использование разработанной методики в задаче вычисления доли собственной разработки в составе изделия

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

ВЫВОДЫ И ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

СПИСОК СОКРАЩЕНИЙ

КИС - корпоративные информационные системы.

СУБД - система управления базами данных.

БД - база данных.

ГА - генетический алгоритм.

ЭВ - эволюционные вычисления.

ЭА - эволюционные алгоритмы.

ЦФ - целевая функция.

ЦП - центральный процессор.

ЖД - жесткий диск.

Введение диссертации (часть автореферата) на тему «Алгоритмическое и методическое обеспечение повышения оперативности поиска данных в корпоративных информационных системах»

ВВЕДЕНИЕ

Актуальность темы диссертации. Корпоративные

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

В настоящее время более 60% используемых КИС - это производственные КИС. Для своевременного решения задач производства КИС должны обеспечить быстрое выполнение основных бизнес-процессов предприятия, т.е. обеспечить оперативное решение задач производства. Так как 80% из всех выполняемых в КИС операций составляют операции поиска данных, то оперативность решения задач производства может быть достигнута повышением оперативности поиска данных в КИС. Под оперативностью поиска данных подразумевается получение требуемых данных за наименьшее время.

Оперативность поиска данных в КИС напрямую зависит от объемов обрабатываемых данных. Например, формирование состава изделия, включающего порядка 200 деталей и сборочных единиц занимает 15 секунд, в свою очередь формирование состава изделия из 500 деталей и сборочных единиц занимает уже более 3 минут. Из-за сложности выпускаемой техники (например, морская трех-координатная PJIC, типа «Позитив», включает более 10 тысяч деталей и сборочных единиц, береговой комплекс разведки воздушной и надводной обстановки, типа

«Монолит», - более 20 тысяч) простым увеличением вычислительной мощности невозможно обеспечить требуемую оперативность поиска данных в КИС.

Задачу обеспечения требуемой оперативности поиска данных в КИС решает подсистема поиска, хранения и обработки данных. Данные в КИС хранятся в структурированном виде. В настоящее время наиболее распространенной структурированной моделью хранения данных в КИС является реляционная модель данных, которая используется в 90% современных КИС.

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

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

алгоритмов выполнения запроса алгоритма, позволяющего выполнить запрос за наименьшее время (оптимального алгоритма выполнения запроса).

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

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

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

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

множества. В большинстве случаев это может привести к выбору неоптимальных алгоритмов выполнения запроса и снижению оперативности поиска данных в КИС.

Вопросом решения задачи повышения оперативности поиска данных в КИС уделено внимание в школах таких ученых, как Кузнецов С.Д., Григорьев Ю.А., Кузнецов Л.А., Погодаев А.К., Овчинников В.В., Льюис Дж. [1-10]. Однако, вопрос априорной оценки мощностей выходных множеств операций обработки данных для повышения оперативности поиска данных в КИС является открытым.

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

Объект исследования - процесс поиска данных в КИС.

Предмет исследования - алгоритмическое и методическое обеспечение поиска данных в КИС.

Цель исследования - повышение оперативности поиска данных в КИС на основе априорной информации о мощностях выходных множеств операций обработки данных.

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

Научные результаты, представляемые к защите:

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

оценки мощностей выходных множеств операций обработки данных.

2. Методика повышения оперативности поиска данных в КИС.

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

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

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

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

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

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

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

Внедрение результатов исследований. Теоретические и практические результаты диссертационного исследования используются в учебном процессе в КФ МГТУ им. Н.Э. Баумана. Результаты диссертационной работы внедрены на промышленных предприятиях ОАО «Тайфун», ОАО «Русполимет».

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

обсуждались на шести всероссийских и одной международной научно-технической конференции.

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

Структура и объём работы. Диссертационная работа состоит из введения, четырёх разделов, выводов, заключения и списка литературы, включающего 132 источника. Работа изложена на 150 страницах и содержит 27 рисунков и 8 таблиц.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Либман, Михаил Сергеевич

ВЫВОДЫ И ЗАКЛЮЧЕНИЕ

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

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

Для подтверждения эффективности предложенной методики были проведены экспериментальные исследования. Эксперимент показал, что использование разработанной методики повышения оперативности поиска данных в КИС позволяет, в среднем, уменьшить время поиска данных на 18%, уменьшить загрузку ЦП на 21%, уменьшить количество операций ввода/вывода на 18%. Также были вычислены накладные расходы, вызванные использованием предложенной методики повышения оперативности поиска данных в КИС. Полученные результаты позволяют сказать, что выигрыш от ее использования перекрывает накладные расходы, вызванные ее применением.

Разработанная методика повышения оперативности поиска данных в КИС была внедрена в состав системы М4, используемой на предприятии ОАО НЛП «Тайфун». В результате внедрения разработанной методики удалось уменьшить время выполнения ряда производственных задач. Разработанная методика была внедрена в состав таких подсистем как: ведение договоров; констукторско-технологическая подготовка производства, формирование состава изделия; формирование расцеховочных маршрутов; работы с материалоемкостью и трудоемкостью изделия и т.д. Внедрение позволило:

• Уменьшить время «накатки» изменений конструкторско-технологического состава изделия. После внедрения разработанной методики время выполнения задачи сократилось на 30%. Если ранее данная задача не укладывалась в период с 18.00 до 8.00, то после внедрения разработанной методики время выполнения задачи стало менее 10 часов;

• Уменьшить время формирования отчетов по «трудоемкости» изготовления продукции до 40%. Время формирования отчета для изделия, включающего порядка 10 тысяч деталей и сборочных единиц, до внедрения методики составляло 3 часа 40 минут, после стало 2 часа 10 минут.

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

Результаты диссертации внедрены на промышленных предприятиях и в учебный процесс КФ МГТУ им. Н.Э.Баумана, что подтверждается актами внедрения.

Положения работы поддержаны областной стипендией им. П.Л. Чебышева (2009 г.); присуждением Калужской областной стипендии имени П.М. Голубицкого (2010 г.); победой на конкурсе аспирантов высших учебных заведений и научных организаций, расположенных на территории Калужской области (2010г.); первым местом на областном конкурсе профессионального мастерства среди молодых специалистов в области информационных технологий 20 Юг; первым местом на Всероссийском конкурсе научно-исследовательских работ студентов и аспирантов в области информатики и информационных технологий (Белгород 2012 г.).

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

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

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

3. Разработанная в рамках диссертационного исследования методика повышения оперативности поиска данных в КИС позволяет в среднем уменьшить время поиска данных на 18%, уменьшить загрузку центрального процессора на 21%, уменьшить количество операций ввода/вывода на 18%).

4. Результаты диссертации были внедрены на промышленных предприятиях, что позволило сократить время решения производственных задач на 30-40%.

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

Список литературы диссертационного исследования кандидат технических наук Либман, Михаил Сергеевич, 2013 год

СПИСОК ЛИТЕРАТУРЫ

1. Кузнецов С.Д., Мендкович H.A. Новые алгоритмы лексической оптимизации запросов // Моделирование и анализ информационных систем. 2009. Т. 16, №4. С. 22-33.

2. Григорьев Ю. А., Остриков С. П. Оценка времени выполнения запросов с коррелированными подзапросами и операциями агрегирования // Математическое моделирование. 2006. Т. 18, № 4. С. 10-18.

3. Кузнецов Л.А., Погодаев А.К, Овчинников В.В. Оптимизация запросов к базам данных информационных систем // Управление большими системами. 2003. № 4. С. 24-34.

4. Погодаев А.К., Дятчина Д.В., Муравейко А.Ю. Альтернативные соединения таблиц баз данных // Системы управления и информационные технологии. 2005. № 5. С. 99-102.

5. Григорьев Ю. А., Остриков С. П. Выбор оптимального плана выполнения запроса с вложенными коррелированными подзапросами // Информатика и системы управления. 2006. № 1. С. 3-14.

6. Гребенников H.A., Григорьев Ю.А. Метод поиска оптимального плана на основе нисходящей стратегии // Информатика и системы управления. 2003. №1. С. 3-15.

7. Дейт К. Дж. Введение в системы баз данных. М.: Издательский дом Вильяме, 2005. 1382 с.

8. Григорьев Ю.А., Ревунков Г.И. Банки данных. М.: Изд-во МГТУ им. Н.Э. Баумана, 2002. 320 с.

9. Миллсап К., Хольт Д. Oracle. Оптимизация производительности. СПб.: Символ-Плюс, 2006. 464 с.

10. Льюис Дж. Oracle. Основы стоимостной оптимизации. СПб.: Питер, 2007. 528 с.

11. Seiinger P.G., et al. Access Path Se-lection in a Relational Database Management System // Management of data: Proceedings of the international conference. New York, 1979. P. 23-34.

12. Blasgen M.W., Eswaran K.P. Storage and Access in Relational Databases // IBM Systems Journal. 1977. № 4. P. 363-377.

13. Graefe C., Cole R.L. Fast Algorithms for Universal Quantification in Large Databases // Transactions on Database Systems. 1995. № 2. P. 187-236.

14. Negri M., Pelagatti G. Distributive Join: A New Algorithm for Joining Relations // Transactions on Database Systems. 1991. № 4. P. 655-669.

15. Shapiro L.D. Join Processing in Database Systems with Large Main Memories // Transactions on Database Systems. 1986. T. 11, № 3. P. 239-264.

16. Sacco G.M. Fragmentation: A Technique for Efficient Query Processing // Transactions on Database Systems. 1986. T. 11, № 2. P. 113-133.

17. Merrett T.H. Why Sort/Merge Gives the Best Implementation of the Natural Join // ACM SIGMOD Record. 1983. T. 13, № 2. P. 40-51.

18. P. Krishnan, J. S. Vitter, B. R. Iyer. Estimating alphanumeric selectivity in the presence of wildcards // SIGMOD. 1996. P. 282—293.

19. Jarke M., Koch J. Query Optimization in Database Systems // Computing Surveys. 1984. T. 16, №2. P. 111-152.

20. Antoshenkov G. Query Processing in DEC Rdb: Major Issues and Future Challenges // Bulletin of the Technical Committee on Data Engineering. 1993. T. 16, №4. P. 42-52.

21. Antoshenkov G. Dynamic Optimization of a Single Table Access // The International Journal on Very Large Data Bases. 1991. T. 4, № 5. P. 1-12.

22. Antoshenkov G. Random Sampling from Pseudo-Ranked B+ Trees. // Very Large Data Bases: Proceedings of the international conference. San Francisco, 1992. P. 375-382.

23. Antoshenkov G. Dynamic Query Optimization in Rdb/VMS. // Data Engineering: Proceedings of the international conference. Washington, 1993. P. 538-547.

24. Markl, V., Lohman G. M., Raman V. LEO: An autonomic query optimizer for DB2 // IBM SYSTEMS JOURNAL. 2003. T. 42, № 1. P. 98-106.

25. Vance В., Maier D. Rapid Bushy Join-Order Optimization with cartesian Products // Management of data: Proceedings of the international conference. New York, 1996. P. 35-46.

26. Рублев В. С. Организация выполнения объектных запросов в динамической информационной модели DIM // Моделирование и анализ информационных систем. 2011. №18. С. 39-51.

27. Дятчина Д.В., Муравейко А.Ю. Алгоритм оптимизации альтернативных соединения таблиц реляционной базы данных в управлении организации // Управление большими системами. 2006. № 14. С. 63-68.

28. Самарев Р.С. Методы и модели проектирования параллельных СУБД.: Автореф. ... дис. к. тех. наук. М. 2007. 18 с.

29. Беляков. C.JL, Диденко Д.А. Оптимизация запросов к кадастровой базе данных // Известия южного федерального университета. Технические науки. 2008. Т. 87, № 10. С. 178-182.

30. Алгазинов Э.К., Тимашов Д.С. Применение метаописаний данных в оптимизации запросов // Информационные технологии моделирования и управления. 2005. № 5. С. 716-720.

31. Niemiec R.J. Oracle Database 10g Performance Tuning Tips & Techniques. Osborne.: McGraw-Hill, 2007. 968 p.

32. Андреев A.M., Самарев P.С., Сюзев B.B. Анализ производительности разрабатываемых систем управления базами данных и информационных

систем на их основе с использованием алгебраических моделей // Вестник Московского государственного технического университета им. Н.Э. Баумана. Приборостроение. 2007. № 3. С. 93-114.

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

34. Ульман Дж. Д., Уидом Дж. Основы реляционных баз данных. М.: Издательство Лори, 2006. 382 с.

35. Кренке Д. Теория и практика построения баз данных. СПб.: Питер, 2005. 864 с.

36. Yannis Ioannidis. The History of Histograms // Very Large Data Bases. 2003, № 29. P. 19-30.

37. Poosala V., Ioannidis Y., Haas P. Improved Histograms for Selectivity Estimation of Range Predicates // Management of data: Proceedings of the international conference. New York, 1996. P. 294-305

38. Gibbons P., Matias Y., Poosala V. Fast Incremental Maintenance of Approximate Histograms // Very Large Data Bases: Proceedings of the international conference. San Francisco, 1997. P. 466-475.

39. Логвинов, A.M., Поленова, Ю.Е., Травин, Г.А. Травин, М.Г. Основанные на вейвлетах гистограммы для оценки селективности запросов // Научные ведомости БелГУ. Сер. История. Политология. Экономика. Информатика. 2009. №7, вып. 10/1. С. 185-191.

40. Matias Y., Vitter J.S., Wang M. Wavelet-based histograms for selectivity estimation // Management of data: Proceedings of the international conference. New York, 1998. P. 448-459.

41. Garofalakis M., Gibbons P. Wavelet Synopses with Error Guarantees 11 Management of data: Proceedings of the international conference. New York, 2002. P. 476-487.

42. Chaudhuri S., Motwani R., Narasayya V. Random Sampling for Histogram Construction: How Much is Enough? // SIGMOD. 1998. P. 436-447.

43. Gibbons P., Matias Y., Poosala V. Fast Incremental Maintenance of Approximate Histograms // VLDB. 1997. P. 466-475.

44. Chaudhuri S., Motwani R., Narasayya V. Random Sampling for Histogram Construction: How Much is Enough? // Management of data: Proceedings of the international conference. 1998. P. 436-447.

45. Piatetsky-Shapiro G., Connell C.: Accurate Estimation of the Number of Tuples Satisfying a Condition //SIGMOD. 1984. P. 256-276.

46. Poosala V., Ioannidis Y., Haas P. Improved Histograms for Selectivity Estimation of Range Predicates // SIGMOD. 1996. P. 294-305.

47. Barbar D. The New Jersey Data Reduction Report // Data Engineering Bulletin. 1997. T. 20, №4. P. 3-45.

48. Matias Y., Vitter J., Wang M. Wavelet-Based Histograms for Selectivity Estimation // SIGMOD. 1998. P. 448-459.

49. Дьяконов В. П. Вейвлеты. От теории к практике. М.: COJTOH-Пресс, 2004. 400 с.

50. Vitter J., Wang М. Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets//SIGMOD. 1999. P. 193-204.

51. Vitter J., Wang M., Iyer B. Data Cube Approximation and Histograms via Wavelets // CIKM. 1998. P. 96-104.

52. Chakrabarti K., Garofalakis M., Rastogi R., Shim K. Approximate Query Processing Using Wavelets // VLDB Journal. 2001. T. 10, № 2. P. 199-223.

53. Gilbert A., Kotidis Y., Muthukrishnan S., Strauss M. Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries // VLDB. 2001. P. 79-88.

54. Sun W., Ling Y., Rishe N., Deng Y. An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment //SIGMOD. 1993. P. 79-88.

55. Belussi A., Faloutsos C. Estimating the Selectivity of Spatial Queries Using the Correlation Fractal Dimension // VLDB. 1995. P. 299-310. '

56. Krishnan P., Vitter J., Iyer B. Estimating Alphanumeric Selectivity in the Presence of Wildcards // SIGMOD. 1996. P. 282-293.

57. Jagadish H. V., Kapitskaia O., Ng R., Srivastava D. Multi-Dimensional Substring Selectivity Estimation // VLDB. 1999. P.387-398

58. Wang M., Vitter J., Iyer B. Selectivity Estimation in the Presence of Alphanumeric Correlations // ICDE. 1997. P. 169-180.

59. Alsabti K., Ranka S., Singh V. A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data // VLDB. 1997. P. 346-355.

60. Manku G. S., Rajagopalan S., Lindsay B. Approximate Medians and Other Quantiles in One Pass and with Limited Memory // SIGMOD. 1998. P. 426-435.

61. Manku G. S., Rajagopalan S., Lindsay B. Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets // SIGMOD. 1999. P. 251-262.

62. Acharya S., Gibbons P., Poosala V., Ramaswamy S. Join Synopses for Approximate Query Answering // SIGMOD. 1998. P. 275-286.

63. Hellerstein J., Haas P., Wang H. Online Aggregation // SIGMOD. 1997. P. 171-182.

64. Haas P., Hellerstein J. Ripple Joins for Online Aggregation // SIGMOD. 1999. P. 287-298.

65. Luo G., Ellmann С., Haas P., Naughton J. A Scalable Hash Ripple Join Algorithm // SIGMOD. 2002. P. 252-262.

66. Грабер M. SQL. M.: Лори, 2007. 672 с.

67. Либман М.С. Телерман Н.Э. Ошибка оптимизатора при оценке кардинальности запросов с оператором Like // Наукоемкие технологии в прибора- и машиностроении и развитие инновационной деятельности в вузе: Материалы Всерос. н-т конф. Москва, 2009. С. 93-97.

68. Райордан Р. Основы реляционных баз данных. М.: Издательско-торговый дом Русская Редакция, 2001. 384 с.

69. Либман М.С. Анализ выполнения запросов с оператором Like в базах данных // Сб. науч. работ лауреатов областных премий и стипендий. Калуга, 2010. Выпуск 6. С. 75-79.

70. Либман М.С., Мазин А.В. Влияние ошибки оценки кардинальности оптимизатором на производительность баз данных // Интеллектуализация информационного поиска, скантехнологии и электронные библиотеки: Сб. тр. Всерос. науч. школы-семинара. Таганрог, 2010. С. 138-140.

71. Гайя Кришна Вайдьянатха, Киртикумар Дешпанде, Костелак Дж. Oracle 101. Настройка производительности. М.: Лори, 2003. 432 с.

72. Oracle9i Database Reference Release 2 (9.2) [Электронный ресурс] // Oracle9i Database Online Documentation (Release 2 (9.2)). URL. http://d0wnl0ad.0racle.c0m/d0cs/cd/B 10501 01 /server.920/a96536/toc.htm (дата обращения 30.05.2010)

73. Loney К., Theriault M. Oracle9i DBA. Handbook. Osborne.: McGraw-Hill, 2002. 753 p.

74. Oracle® Database Performance Tuning Guide 10g Release 2 (10.2) [Электронный ресурс] // Oracle Database 10g Documentation Library. URL.

http://d0wnl0ad.0racle.c0m/d0cs/cd/B 193 06_01 /server. 102/b 14211 /toc.htm (дата обращения 30.05.2010).

75. Breitling W. A look under the hood of CBO: the 10053 Event // Oracle System Performance. 2003. № 1. P. 1-19.

76. Ожегов С.И. Словарь русского языка. М.: Русский язык, 1985. 797с.

77. Вятченин Д.А. Нечеткие методы автоматической классификации. Минск: УП Технопринт, 2004. 219с.

78. Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986. 576 с.

79. Погодаев А.К., Комар Ф.В. Автоматизированный метод отождествления объектов схем баз данных // Системы управления и информационные технологии. 2008. № 1(33). С. 192-196.

80. Погодаев А.К., Комар Ф.В. Метод интегрирования схем данных на основе семантического описания атрибутов // Программные продукты и системы. 2008. № 1(81). С. 53-56.

81. Смит Б. Методы и алгоритмы вычислений на строках.. М.: Вильяме, 2006. 496 с.

82. Фридл Дж. Регулярные выражения. СПб.: Символ-Плюс, 2008. 608 с.

83. Гладкий A.B. Формальны грамматики и языки. М.: Наука, 172. 368 с.

84. Серебряков В.А., Галочкин М.П. Основы конструирования компиляторов. М.: Едиториал УРСС, 2001. 224 с.

85. Либман М.С. Определение оптимального регулярного выражения для описания подстроки поиска // Наукоемкие технологии в прибора- и машиностроении и развитие инновационной деятельности в вузе: Тез. докл. н-т. конф. Москва, 2009. Т. 3. С. 101-103.

86. Рутковская Д., Пилиньский М., Рутковский JI. Нейронные сети, генетические алгоритмы и нечеткие системы. М.: Горячая линия -Телеком, 2006. 452 с.

87. Beyer H.G., Schwefel Н.Р. How to Analyse Evolutionary Algorithms? // Theoretical Computer Science. 2002. № 287. P. 101-130.

88. Holland J.H. Adaptation in Natural and Artificial Systems. MI: The University of Michigan Press, 1975. 210 p.

89. Goldberg, D.E., Richardson J., Genetic Algorithms with Sharing for Multimodal Function Optimization // Genetic Algorithms and their Applications. 1987. № 2. P. 41-49.

90. Grefenstette J.J. Genetic Search with Approximate Function Evaluation // Genetic Algorithms Pages. 1985. № 1. P. 112-120.

91. Syswerda G. Uniform Crossover in Genetic Algorithms // Genetic Algorithms. 1989. № 3. P. 2-9.

92. DeJong K.A. An analysis of the behavior of a class of genetic adaptive systems: Ph.D. dissertation. Univ. Michigan. 1975. 266 p.

93. Редько В.Г. Эволюционная кибернетика. М.: Наука, 2003. 156 с.

94. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. М.: Физматлит, 2003. 432 с.

95. James D. Kelly, Lawrence Davis. A hybrid genetic algorithm for classification August // Artificial intelligence. T. 2, № 11. P. 645-650

96. Schaffer J. D., Eshelman L. J. Designing Multiplierless Digital Filters Using Genetic Algorithms // Genetic Algorithms: Proceedings of the international conference. San Francisco, 1993. P. 439-444.

97. Goldberg D.E. Genetic and evolutionary algorithms come of age Communications // ACM. 1994. T. 37, № 3. P. 113 - 119.

98. Goldberg D.E. Genetic Algorithm in Search, Optimization, and Machine Leerning. Addison-Wesley Publishing Company, 1989. 372 p.

99. Lawrence D. Handbook of Genetic Algorithms. New York: Van Nostrand Reinhold, 1991. 385 p.

100. Гудман Э.Д., Коваленко А.П. Эволюционные вычисления и генетические алгоритмы. М.: Изд-во ТВП, 1996. 760 с.

101. Либман М.С. Алгоритм и программные средства вычисления прогнозируемой мощности результата выполнения операции поиска подстроки в базах данных // Всероссийский конкурс научно-исследовательских работ студентов и аспирантов в области информатики и информационных технологий: Сб. науч. работ. Том 2. Белгород, 2012. С 27-31.

102. Либман М.С. Использование генетического алгоритма для решения задачи поиска оптимального регулярного выражения // Молодежь и современные информационные технологии: Сб. тр. Всерос. н-пр. конф. Томск, 2010. С 111-112.

103. Либман М.С., Мазин A.B.,Телерман Н.Э. Использование генетического алгоритма для описания классов условий поиска //Радиопромышленность. Выпуск 1. Москва, 2011. С 127.

104. Либман М.С., Телерман Н.Э. Критерий выбора регулярного выражения для классификации и прогнозирования условия поиска // Применение кибернетических методов в решении проблем общества XXI века: Материалы н-т. конф. Обнинск, 2011 г. С. 16-18.

105. Либман М.С., Мазин A.B., Телерман Н.Э. Получение регулярных выражений удовлетворяющих строке при помощи генетического алгоритма // Научное творчество XXI века: Материалы Всерос. н. конф. Красноярск, 2010. С. 42.

106. Либман М.С. Исследование вопроса об изменении классов данных, запрашиваемых пользователем // Применение кибернетических методов в решении проблем общества XXI века: Тез. докл. н-т. конф. Обнинск, 2010. С. 16-17.

107. Курейчик В.М., Лебедев Б.К. Определения и основные понятия генетических алгоритмов [Электронный ресурс] // Интернет-лекция в рамках научной школы третьей конференции молодых ученых. URL. http://faculty.ifmo.ru/csd (дата обращения 30.05.2010).

108. Holland J. Н. Adaptation in natural and artificial systems. Michigan: University of Michigan Press, 1975. 228 p.

109. Комарцова Л.Г. Максимов A.B. Нейрокомпьютеры. М.: МГТУ им. Н. Э. Баумана, 2004. 400 с.

110. Гладков Л. А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. М: Физматлит, 2006. 320 с.

111. Каширина И.Л.. Введение в эволюционное моделирование. Воронеж: ИПЦ ВГУ, 2007. 39 с.

112. Крутейчик В.В. Эволюционные методы решения оптимизационных задач. Таганрог: Изд-во ТРГУ, 1999. 99 с.

113. Крутейчик В.В. Эволюционные, синтетические и гомеостатические методы принятия решений. Таганрог: Изд-во ТРГУ, 2001. 221 с.

114. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. М.: Физматлит, 2006. 320 с.

115. Крутейчик В.М. Генетические алгоритмы и их применение. Таганрог: Изд-во ТРГУ, 2002. 400 с.

116. Либман М.С. Расчет стоимости выполнения SQL запросов с операцией Like // Наукоемкие технологии в прибора- и машиностроении и

развитие инновационной деятельности в вузе: Материалы н. конф. Том 2. Москва, 2010 г. С 109.

117. Либман М.С., Мазин A.B. Анализ накладных расходов, вызванных использованием разработанных методов определения кардинальности // Вопросы радиоэлектроники. 2012. Выпуск 3. С. 35-42.

118. Григорьев Ю.А., Ухаров А.О. Вейвлет сжатие в хранилищах OLAP // Организация баз данных. 2008. №4ю. С. 3-10.

119. Коротков А. Е., Панферов В. В. Применение обобщенного дерева поиска для нечеткого поиска строки // Наука и образование. 2011. №3. С. 11-27.

120. Либман М.С. Мазин A.B. Повышение точности оценки кардинальности SQL запросов с оператором Like // Вопросы радиоэлектроники. 2010. Выпуск 4. С. 155-167.

121. Монтгомери Д.К. Планирование эксперимента и анализ данных. Л.: Судостроение, 1980. 384 с.

122. Славутский Л.А. Основы регистрации данных и планирования эксперимента. Чебоксары: Изд-во ЧТУ, 2006. 200 с.

123. Либман М.С., Мазин A.B. Реализация методов повышения точности оценки кардинальности в запросах с оператором поиска подстрок // Радиопромышленность. Выпуск 3. Москва, 2011. С 79.

124. Чугреев В. Л. Объектно-ориентированное программирование -перспективы развития // Современные проблемы информатизации в технике и технологиях: Труды международной н. конф. Воронеж, 2000. С. 99-100.

125. Джесс Либерти. Программирование на С#. М.: Символ-Плюс, 2003. 688 с.

126. Герберт Шилдт. С# 4.0 полное руководство. - М.: Вильяме, 2011.-1056с.

127. Interface Ltd. [Электронный ресурс] // ORACLE 7. Server Application Developer's Guide. РУКОВОДСТВО РАЗРАБОТЧИКА ПРИЛОЖЕНИЙ. URL. http://www.interface.ru/fset.asp?Url=/oracle/ora7/ora7 a05a.htm ~ (дата обращения 26.09.2011)

128. Третьяк Л.Н. Обработка прямых измерений с многократными наблюдениями. Оренбург: ИПК ОГУ, 2002. 60 с.

129. Фадеев М.А. Элементарная обработка результатов эксперимента. Нижний Новгород: Изд-во Нижегородского госуниверситета, 2002. 108 с.

130. Либман М.С. Мазин А.В. Анализ эффективности предлагаемых методов повышения точности оценки кардинальности запросов с подзапросами поиска данных, удовлетворяющих шаблону // Т-сот. Телекоммуникации и транспорт. Москва, 2010. Выпуск 5. С. 20-25.

131. Либман М.С. Мазин А.В. Тестирование производительности баз данных // RSDN Magazine. Москва, 2010. Выпуск 2. С. 3-5.

132. Глудкин О.П., Черняев В.Н. Анализ и контроль технологических процессов производства РЭА. М.: Радио и связь, 1983. 296 с.