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

На правах

ЛИБМАН МИХАИЛ СЕРГЕЕВИЧ

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

Специальность: 05.13.01 — Системный анализ, управление и обработка информации (в науке и промышленности)

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

1013

005531531

Калуга - 2013

005531531

Работа выполнена в Калужском филиале Московского государственного технического университета им. Н.Э. Баумана.

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

Мазин Анатолий Викторович

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

Кухарев Александр Дмитриевич

кандидат технических наук, доцент Родионов Андрей Викторович

Ведущая организация: Обнинский институт атомной энергетики -

филиал федерального государственного автономного образовательного учреждения высшего профессионального образования «Национальный исследовательский ядерный университет «МИФИ» (ИАТЭ НИЯУ МИФИ), г. Обнинск

Защита состоится «/У_» г. на заседании совета по защите докторских

и кандидатских диссертаций Д 520.033.01 при Межрегиональном общественном учреждении «Институт инженерной физики» по адресу: 142210, Московская обл., г. Серпухов, Большой Ударный пер., д. 1а, зал диссертационных заседаний.

С диссертацией можно ознакомиться в библиотеке Межрегионального общественного учреждения «Институт инженерной физики».

Автореферат разослан «Л/» //^¿УЛ^СИЗ г.

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

Коровин О.В.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим запрос поиска данных, определенный как объединение трех множеств мощностью 100, 2 и 10 элементов соответственно. При использовании вложенных циклов, как способа объединения, алгоритмов выполнения данного запроса может быть три (см. рис. 1).

11общ=200+(1020..10) = 1220..210 Яобщ=1000+(220..2)=1220..Ю02 Кобщ=20+(1200..100) = 1220..120

В первом алгоритме (см. рис. 1(а)) сначала выполняется объединение множеств Г,, . Для выполнения этой операции потребуется Л=200 операций сравнения. Мощность результирующего множества /| 2 может изменяться от 102, если П= 0, до 1, если все элементы множеств совпадают. Операция объединения множества и потребует от Я=1020 операций сравнения до 11=10, в зависимости от мощности множества Соответственно и мощность выходного множества ?12 3 может изменяться от 112, если П/2П/3 = 0, до 1- Всего для решения поставленной задачи при помощи первого алгоритма потребуется от Л^ =1220 операций сравнения до =210, в зависимости от данных, хранимых в объединяемых множествах. Аналогично, на рис. 1(6) и 1(в) представлены два других алгоритма. Как видно, итоговое количество операций сравнения может отличаться в зависимости от используемого алгоритма и данных, хранимых в объединяемых множествах. Для выбора наиболее эффективного алгоритма необходимо оценить мощности выходных множеств, получаемых после первой операции объединения, для различных алгоритмов, и на основании этого выбрать оптимальный алгоритм, при этом, в зависимости от хранимых данных, оптимальный алгоритм может меняться.

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

Любой запрос можно представить в виде ориентированного дерева, в котором вершины дерева - это множества обрабатываемых данных, а дуги - операции обработки.

(а)

Ч \ 1 к

(б)

Рис. 1. Алгоритмы объединения трех множеств

Пусть Т = - множество вершин, по которым можно построить множе-

ство ориентированных деревьев () = ((2х,<21,(21,~.<2п), см. рис. 2(а). Каждая вершина может быть описана некоторым множеством йа = (с11,с12,с13,...,с//1).

Определим дерево (}, где (/р/2,;3,/4) - множество вершин дерева, а (,,,)-множество дуг дерева, определяющих операции обработки данных, см. рис. 2(6). Изменим исходное дерево 2 таким образом, что переход из некоторой вершины ^ в любую вершину с которой у вершины I, в дереве 2 определен маршрут, можно было бы выполнить по нескольким маршрутам (назовем их эквивалентными). При этом для каждой пары вершин может существовать конечное множество эквивалентных маршрутов, определяемых правилами эквивалентного преобразования реляционной алгебры. В результате, исходное дерево может быть дополнено множеством эквивалентных маршрутов, см. рис. 2(в).

Для каждой дуги можно определить «стоимость» перехода по данной дуге

(«стоимость» выполнения операции, ассоциированной с данной дугой). «Стоимость» - это оценка затрат ресурсов системы на выполнение операции. Пусть

QKQ1.Qj.Q3.....0„) - множество путей прохождения дерева из терминальных вершин в

корень графа. Определим «стоимость» прохождения дерева по маршруту как Л(0„) = /?(7;;) + Д(Л) + №3) + ..., где /?(/;),...-«стоимость» перехода по ду-

гам, входящим в маршрут С?„. С учетом эквивалентных маршрутов необходимо определить такой маршрут прохождения вершин дерева (), что бы общая «стоимость» выполнения всех переходов была минимальна 7?(0) = т1п(Л(Р[),/?(Р2)>й(Р3),...). Назовём такой маршрут оптимальным для дерева Q.

«Стоимость» перехода по дуге Ра определяется на основании мощности входного множества, обрабатываемого в операции. При этом для операций Р, и Г, мощности входных множеств можно определить на основании статистики, собранной по обрабатываемым входным множествам г, и С,, до выполнения операций. Для операции Р2 мощность входного множества определяется на основании мощности выходного множества операций . Обозначим данный параметр как /г,, тогда = /(А,). Мощность выходного множества операций зависит от операнда операции . Обозначим дан-

ный операнд s,. Тогда /;, = /(/^(.S',),/,). В свою очередь, значение операнда операции Ff зависит от , st = f ).

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

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

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

- Т = (tt,l2,t3,...ta) - множества обрабатываемых данных.

- А = (ям,а2|,...,а|2,я22,...,а|о,л2о,...) - множество атрибутов, определенных на множестве Т.

- D = (dl,d1,ds,...,db) - множество данных, хранимых в КИС.

- Q = пл{р,. (i, х/2 x...xtc)) - запрос обработки данных, где crf - операция селекции по условию F, лл - операции протекции. По правилам эквивалентного преобразования запрос Q можно представить в следующем виде:

(<х А2

(сг (о- С,)))) (О Изменение порядка выполнения операций nAd(aFj{td)) и способов выполнения операций позволяет получить множество Q = (Q,,Q2.....Q„) - множество алгоритмов выполнения запроса Q.

- R(Q„) - функция «стоимости» выполнения запроса Q при помощи алгоритма Q„. При выполнении запроса Q решается задача оптимизации:

*(Q) = mm(*(Q,).*(Q2),....«(Q.)) (2)

где Q - оптимальный алгоритм выполнения запроса (3, a R(Q) - «стоимость» выполнения запроса Q при помощи оптимального алгоритма Q.

R(Q„) = R(ql) + R(q2) + .. + R(qd) (3)

где qd -7tAd{oFd(Jd)) - операции, формирующие алгоритм Q, R{qd) - «стоимость» выполнения операции qd.

R{qd) = f(t,a,F,h"™) (4)

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

- s — операция поиска подстроки в отношении t по атрибуту a, s е F.

- S = (st,s2,s]t...se) - множество операций s обработки данных из ранее выполненных запросов.

В настоящее время при выполнении запросов с операцией s: h = hcon" - const. В результате задача (2) решается не оптимально.

Требуется разработать методику повышения оперативности поиска данных в КИС путем априорной оценки мощностей выходных множеств операций обработки данных. Оценка мощностей выходных множеств будет выполняться на основании множества S =(s,,s2,s3,..jt). Оперативность обработки данных будет достигнута путем передачи вычисленных значений мощностей выходных множеств в КИС для определения функции «стоимости» выполнения операции как фуикции R(qd) = f(t,a,F,h), где

h * hc""' = const. Решать поставленную задачу в условиях (1) - (4) необходимо в следующей последовательности:

- Разработать алгоритм прогнозирования операций обработки данных D' = (d',d2,d},...,dg) и априорной оценки мощностей выходных множеств операций обработки данных. Операции обработки данных определяются операндами операции, следовательно прогнозирование операций обработки данных решается прогнозированием операндов. Множество прогнозируемых операций обработки данных D' будет синтезировано на основании множества операций S из ранее выполненных запросов и множества данных D, хранимых в КИС, см. рис. 3. Мощность hg выходного множества операций dg е D'определяется на основании множеств D и D'. Элементы множества из 0' и их значения hg образуют множество

D'=f(S,D) (5)

H=f(D,D') (6)

D D

Рис. 3. Схема прогнозирования операций обработки данных и априорной оценки мощностей выходных множеств операций обработки данных - Разработать методику повышения оперативности поиска данных в КИС. Повышение оперативности поиска данных будет достигнуто за счет априорного определения мощностей выходных множеств операции .г, что позволит выбрать оптимальные алгоритмы выполнения запросов, т.е. функцию = /((.а,/7,/г1""') в КИС необходимо переопределить как = /(Г,а,.Г,/г), где И=/(з,Н), см. рис. 4.

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

Мощности выходных множеств операций будут оцениваться на основании множества Я, КЯМЛ^ЛЬ-ЧЛ»-

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

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

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

- Разработать процедуру априорной оценки мощностей Н выходных множеств операций обработки данных (элементов множества £>'), которые могут быть использованы в запросах поиска данных (выражение 6).

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

5 = Сг,,42,$з,...5,). По полученным кластерам, выполняется прогнозирование. Соответственно для реализации первой процедуры необходимо:

- Разработать способ кластеризации операций обработки данных из статистики запросов на кластеры Я =(г],г2,г3,...,г1), см. рис. 5.

К=ЖО) (7)

о-

А. ,

1 Я

Рис. 5. Способ кластеризации операций обработки данных Разработать способ синтеза операций обработки данных по кластерам Л и информации, хранимой в КИС, см. рис. 6.

0'=М,0) (8)

Я , ±

я 1

Рис.6. Способ синтеза операций обработки данных по кластерам Введем понятие регулярного выражения. Регулярное выражение - это шаблон, описывающий множество строк, соответствующих данному шаблону. Множество 5 может быть описано множеством регулярных выражений Я. Кластеризация элементов множества 5 выполняется при помощи множества Л. Данная задача решена при помощи генетического алгоритма (ГА).

Если представить данный ГА в виде черного ящика (рис. 5), то на его вход будет подаваться множество 5. На выходе будут получены регулярные выражения Я, которые будут описывать все элементы множества 5. Каждое регулярное выражение из Я определяет свой кластер.

Особи ГА - регулярные выражения, представляются на естественном языке. Начальная популяция определяется из элементов множества 5.

11 = 8 = (г1=з„г2=з2,..*1=х1) (9)

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

1. Формируется «брачная пара» из родительских кодировок. Первая особь rt = {rfrfrf...} выбирается случайным образом:

1 (Ю)

N

Вторая особь г( = {r,'r2'/j...} выбирается с вероятностью:

где N-число особей в популяции, Pv - функция фитнеса или целевая функция (ЦФ).

2. Случайным образом с равной вероятностью Р{п.)~—-—, Р(п2) = —-— в каж-

1— 111 '-k/l дой особи выбирается точка разрыва и, - для первой и п2 - для второй особи.

3. Хромосомы особей r„ = {r,lr}rf ...r^r^r*.,...} и г, = разрываются по точке разрыва.

4. Из полученных четырех частей родительских хромосом:

= {'•»з•••<}. = {<.,<♦«<*>•••> ('2) формируются хромосомы двух потомков. Первый потомок:

= U^. = <»2<.з-} (13)

Второй потомок:

П' = Пт U V (14) Опишем используемый в ГА оператор мутации.

1. Случайным образом с вероятностью

. (15)

" /МО/ tlPv(rty выбирается особь, которая будет подвергаться мутацииrm = {rlmr"r"...}, где N -число особей в популяции.

2. Случайным образом с вероятностью Р(т) =—!— в особи г выбирается ген г",

Нг.1

который будет подвергнут мутации.

3. Случайным образом с вероятностью

/>(*) = 1/(1-|Fr U К" |) (16)

из множества Vr\JVN выбирается ген г". V" = {Q,E,Y} - конечное множество нетерминальных символов грамматики, Y={a,6,...,A,E,...,a,b,...,A,B,...}, Q={1,2,3,...}, Е={!,@,#,$,%,...}; VT = {*,+,v,s,w,d,.} - множество терминальных символов грамматики, описывающих метасимволы регулярных выражений.

4. Ген г" из хромосомы гт заменяется на ген г"

-•;=fcnoUr; = 07)

После операций скрещивания и мутации формируют множество/"' = {гк \г,\гп'}.

Необходимо определить целевую функцию (ЦФ). Определим функцию:

Р(г,.,£>)=|Мг'П£>| (18)

где М'' =(т1,т,,т3,...,тп) - регулярное множество, определенное на регулярном выражении г/. Функция F(rJ,D) возвращает количество элементов из множества А которые удовлетворяют шаблону г,. Определим функцию:

где | О | - мощность множества £>. Значения функции Р/(г/,В) лежат на отрезке [О, 1]. В дальнейшем эту величину будем называть частотой появления шаблона па множестве О. Определим функцию:

(20)

N у=|

где ЛГ=]Л|. Данная функция дает усредненное значение численной оценки того, насколько точно все предложенные шаблоны описывают элементы множества О. Определим функцию:

РУ(И, А Г,) = Р/(ГП О) - Ра/(Я (21)

где Я' = (Я[}г^) - множества регулярных выражений, кроме г/.

Значение функции тем выше, чем больше элементов множества О удовлетворяют шаблону г. и чем меньше усредненное значение численной оценки того, насколько точно все шаблоны, за исключением г,, описывают элементы множества А Значения функции лежат на отрезке [0, 1]. Максимальное значение функция принимает в том случае, когда все элементы множества О удовлетворяют шаблону г] и ни один элемент множества О не удовлетворяет какому-либо другому шаблону.

Примем значение функции А^), как ЦФ - численное выражение значимости шаблона относительно других шаблонов в пространстве элементов множества А

/М'.,) = /ЧЛ. А',) (22)

Для каждого элемента множества г' вычисляется значение ЦФ. Если значение ЦФ удовлетворяет условию включения особи в популяцию:

(23)

'» м

то особь включается во множество Я

Л = [>»/, (24)

где г'={гк\г,\гт'}, /V- число особей в популяции.

Если размер популяции достиг определенного прогнозируемого значения:

|/г|=р=Хс„Ч (25)

к=о

то ГА прекращает свою работу, иначе процесс получения новых особей повторяется. Блок-схема ГА формирования классов операций обработки данных представлена па рис. 7.

Начало

.У,О

—I—

5

Рис. 7. Блок-схема генетического алгоритма Разработанный ГА определяет способ кластеризации операций обработки данных из статистики запросов. На основании множества регулярных выражений Я и множества О необходимо выполнить прогнозирование операций обработки данных О', которые могут быть указаны в запросе, см. рис. 6. Определим функцию:

/(т,с!) = {т\тгл(!ф0), (26)

где т и множество символов. Определим функцию:

'¡*и>

= (28)

О'^и^Ч^^ио; (29)

1=1 /=] »

гдеЛ^=|Л|. Выражение (29) описывает способ прогнозирования операций обработки данных £>', которые могут быть использованы в запросах поиска данных, по характеристикам кластеров Д т.е. выражение (29) описывает решение задачи, представленной выражением (5).

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

Рис. 8. Процедура прогнозирования операций обработки данных, которые могут быть использованы в запросах поиска данных Входными данными процедуры является множество 5 - множество операций обработки данных из ранее выполненных запросов. При помощи ГА выполняется кластеризация элементов множества 5 (шаг 1). Полученные кластеры описываются при помощи множества регулярных выражений Л. По множествам ЯнО выполняется прогнозирование операций, которые могут быть указаны в запросах поиска данных (шаг 2, 3). Данную процедуру необходимо выполнять с некоторой периодичностью.

Для упрощения поиска информации элементы множества И' кластеризуются по множеству регулярных выражений Л. Если элемент множества О' принадлежит регулярному множеству М" = (т1,т2,т},...,та), то он принадлежит кластеру, который определяет регулярное выражение г.

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

о

(31)

где Л/=|Л|. Для каждого кластера Г>1 формируется множество пар

= (32)

Множества Н, объединяются во множество //.

Я = иЯ(, (33)

где ¿V Ц Л [. Для каждого кластера Д вычисляется оценка средней мощности выходных множеств операций обработки из данного кластера:

(34)

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

(35)

Выражение (32) описывает процесс получения множества Н (см. выражение 6). Блок-схема процедуры априорной оценки мощностей выходных множеств операций обработки данных, которые могут быть использованы в запросах поиска данных, представлена на рис. 9.

С

Начало

3

/ ^_/

V

о

я=ия,

и

Рис. 9. Процедура априорной оценки мощностей выходных множеств операций обработки данных, которые могут быть использованы в запросах поиска данных Решение задач (5) и (6) позволяет описать разработанный алгоритм. Блок-схема алгоритма представлена на рис. 10.

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

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

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

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

ищется кластер, описываемый регулярным выражением, из множества Я:

г, =/(«,.?) = {т\тъх* 0}, (36)

где меМ' - (т1,т2,т1,...,тп) - некоторое регулярное множество, определенное на регулярных выражениях из множества Я.

Если такой кластер найден, т.е. г, ф 0, то во множестве Нг выполняется поиск

¿ж, = /(Я,,») = {Л«/, = *> (37)

Если то мощность выходного множества операции .V определяется как

мощность выходного множества элемента с1 ' е Нг.

А(5) = Ав (38)

Если ¿1к' = 0, то мощность выходного множества операции .у определяется как оценка средней мощности выходных множеств кластера Д., определенного на г.

Ш) = (39)

Если кластера, удовлетворяющего во множестве Л, не существует, т.е. г;. = У(й,5) = 0, то выходная мощность операции .? определяется как оценка средней

мощности выходных множеств всех кластеров й]

/ЗД = кСР (40)

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

Предлагается элементы множества Я = (Ц,/г1},{^2,/г2},{«/2,й2},...,{</г,/гг}), полученные прогнозируемые операции е1\ их оцениваемую выходною мощность А хранить в исходной КИС. Опишем схему хранения в терминах реляционной алгебры.

Отношение Г(/</Г,о,/,а) определяет схемы (атрибут о), отношения (атрибут /) и атрибуты (атрибут о), анализ которых был выполнен, и для которых можно использовать предложенную методику. ¡с!Т— уникальный идентификатор (первичный ключ) кортежей отношения Т.

Отношение определяет элементы множества Л, атрибут Г являть-

ся вторичным ключом, ссылкой на отношение Т(1'с1Т,о,(,а), атрибут г определяет множество кластеров и описывающих их регулярных выражений, по которым выполнялся синтез операций, атрибут А" определяет оценку средней мощности выходных множеств операций обработки данных, входящих в кластер г(. ¡с1 — уникальный идентификатор (первичный ключ) кортежей отношения Т. ШК — уникальный идентификатор (первичный ключ) кортежей отношения Я.

Отношение НШНД.А'М) определяет множество операций обработки данных, полученных после работы алгоритма. Атрибут К являться вторичным ключом, ссылкой на отношение Л, атрибут с/' — значения операций обработки данных, которые могут быть указаны в запросе, атрибут А - оценка мощности выходного множества операции обработки данных с!'. ¡с!Н - уникальный идентификатор (первичный ключ) кортежей отношения Н.

Допустим - операция обработки данных по отношению Гм>1 атрибуту ашп, оценку мощности выходного множества, которой надо вычислить. Необходимо в отношении Т(1с1Т,о,!,а) найти кортеж с идентификатором гс1Т, для которого значение атрибута ¡ = и атрибута а = ат,

кПт={1<1Т\1 = !1т-а = а1т} (41)

Если

МТ„*0, (42)

то необходимо в отношении Л(Ш,Г,г,Агс/') определить идентификатор кортежа ¡¿К, для которого значение атрибута г - {г | Вт,т п в)т Ф 0}

= {г IЭ «,ип»я * 0;Т=Ши„} (43)

Если

(44)

тогда в отношении //(¡¿//, Д,с/', А) по ключу к/Ям„ и значению определяется априорная оценка мощности выходного множества операции обработки данных .

1,1а„ = <МК=Шжт,с1' = *1т} (45)

Если выражение (44) имеет логическое значение «ложь», то А операции определяется выражением

= = (46)

Если выражение (42) имеет логическое значение «ложь», то А операции определяется выражением (39).

Запрос, передаваемый в КИС при помощи «подсказки», модифицируется и в него передается значение операции Рассмотрим способ передачи значения Ьт в запрос.

Любой запрос можно представить как множество подзапросов.

е=а (47)

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

е = (48)

или

б = (49)

где 5{а,,а2,...} - подмножество, определяющее атрибуты, по которым выполняется операция протекции; ,/2,...} - подмножество, определяющее отношения, по которым выполняется поиск данных в соответствии со множеством операторов №{/1,/2,/ъ,...} , определенных в запросе.

Определим элемент - «подсказку»

а' = !*+{1А.)*/, (50)

где - отношение, по которому выполняется операция /, = о(^), Ь1т - оцениваема мощность выходного множества операции = $.

Операция подстановки «подсказки» в запрос представляется операцией объединения (включения) элемента а' и подмножества 5{а,,о2,...}

5й-=аи5{0„<72>...} (51)

В результате исходный запрос Q представляется в следующем виде

е = бй=((5{а„а2,..}^„/2,..}^{/;,/2,/;,..})П5{а„^,...})и5л~ (52)

или

е=бл=(еп5)и54- (53)

На рис. 11 и 12 представлены блок-схема и схема разработанной методики. Алгоритм прогнозирования операций обработки данных и априорной оценки мощностей выходных множеств операций

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

Рис. 12. Блок-схема методики повышения оперативности поиска данных в КИС

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

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

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

уменьшить время поиска данных на 18%, уменьшить загрузку ЦП на 21%, уменьшить количество операций ввода/вывода на 18%. 22.00%

21.00% 20,00% 19.00% 18,00% 17.00% I б,от;

■ I

Уменьшение Уменьшение Уменьшение 4н|ру:<кн Ц11 кремени поиски кшшместкн данных операций

ш«>да.'в1.пшда

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

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

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

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

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

Выводы

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

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

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

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

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

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ Статьи в изданиях, внесенных в перечень ВАК Минобрнауки России

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

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

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

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

Публикации в других изданиях

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

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

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

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

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

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

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

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

Подписано в печать 08.06.2013г. Тираж 120 экз. Заказ №111 Отпечатано в ООО «ПИ-8 ПЛЮС» 248000, г. Калуга, ул. Ленина, 77 Тел./факс: (4842) 564-888 www.pi8plus.ru

КАЛУЖСКИЙ ФИЛИАЛ МОСКОВСКОГО ГОСУДАРСТВЕННОГО ТЕХНИЧЕСКОГО УНИВЕРСИТЕТА ИМ. Н. Э. БАУМАНА

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

04201360604 ЛИБМАН МИХАИЛ СЕРГЕЕВИЧ

АЛГОРИТМИЧЕСКОЕ И МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ПОВЫШЕНИЯ ОПЕРАТИВНОСТИ ПОИСКА ДАННЫХ В КОРПОРАТИВНЫХ ИНФОРМАЦИОННЫХ СИСТЕМАХ

Специальность: 05.13.01 - Системный анализ, управление и обработка информации (в науке и промышленности)

ДИССЕРТАЦИЯ ка соискание ученой степени кандидата технических наук

Научный руководитель -к.т.н., доцент, Мазин А.В.

Калуга - 2013

Стр.

ОГЛАВЛЕНИЕ

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

ВВЕДЕНИЕ 6

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

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

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

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

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

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

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

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

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

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

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

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

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

алгоритма 62

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

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

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

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

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

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

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

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

в КИС 82

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ВВЕДЕНИЕ

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

информационные системы (КИС) - это сложные системы, включающие информационное, математическое, методологическое, алгоритмическое, программное и техническое обеспечение. КИС нашли широкое применение во многих отраслях промышлености. КИС используются для решения задач планирования ресурсов предприятия (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 таблиц.

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

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

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

Алгоритмов выполнения одного запроса может быть несколько. Задачей КИС является выбор из всех возможных алгоритмов выполнения запроса алгоритма, позволяющего выполнить запрос наиболее оперативно. Определим такой алгоритм как оптимальный, а задачу поиска такого алгоритма - как задачу оптимизации алгоритмов выполнения запросов поиска данных [7, 11-32].

Рассмотрим запрос поиска данных, определенный как объединение трех множеств мощностью 100, 2 и 10 элементов соответственно.

При использовании вложенных циклов, как способа объединения, алгоритмов выполнения данного запроса может быть три- (см. рисунки 1.1 (а-в)).

В первом алгоритме (см. рисунок 1.1 (а)) сначала выполняется объединение множеств , . Для выполнения этой операции потребуется 11=200 операций сравнения. Мощность результирующего множества 2 может изменяться ОТ 102, если ДО 1, если все элементы

множеств совпадают. Операция объединения множества 2 и потребует

от 11=1020 операций сравнения до Я=10, в зависимости от мощности множества 2. Соответственно и мощность выходного множества /123

может изменяться ОТ 112, если п П ^з = 0, до 1. Всего для решения поставленной задачи при помощи первого алгоритма потребуется от Яо6щ=1220 операций сравнения до Яо6щ=210, в зависимости от данных,

хранимых в объединяемых множествах. Аналогично, на рисунках 1(6) и 1 (в) представлены два других алгоритма. Как видно, итоговое количество операций сравнения Яобщ может отличаться в зависимости от

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

Яобщ=200+(1020 10) = 1220 210 Кобщ^ 1000+(220 2) = 1220 1002 Яо6щ=20+(1200 100) = 1220 1