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

Лобанов Александр Анатольевич кандидат технических наук доцент, кафедра инструментального и прикладного программного обеспечения, МИРЭА – Российский технологический университет 119454, Россия, г. Москва, пр. Вернадского, 78, каб. Г-225 Lobanov Aleksandr Anatolevich PhD in Technical Science Associate Professor, Department of Instrumental and Applied Software, MIREA Russian Technological University 119454, Russia, g. Moscow, pr. Vernadskogo, 78, kab. G-225 aa.lobanoff@ya.ru Другие публикации этого автора

Фильгус Дмитрий Игревич аспирант, кафедра Инструментального и прикладного программного обеспечения, РТУ МИРЭА 119454, Россия, г. Москва, Проспект Вернадского, 78 Filgus Dmitrii Igrevich Postgraduate Student, Department of Tool and Application Software, Russian University of Technology 119454, Russia, g. Moscow, Prospekt Vernadskogo, 78 dmif42@ya.ru

Краткий анализ проблем управления множеством транзакций в сетевых базах данных

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

- отсутствует единая методология проектирования и реорганизации множества запросов и транзакций;

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

- данные задачи по своей природе являются NP-полными, и эффективных точных алгоритмов решения для них пока не существует;

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

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

Различные общие вопросы и прикладные аспекты применения распределенных вычислительных сред (РВС) исследованы в работах Загороднего А. Г., Згуровского М. З., Мартыненко Е. С., Фостера Я. (Foster I.), Кесельмана К. (Kesselman C.) и других ученых. Вопросам разработки методов и моделей планирования, оптимизации и повышения производительности функционирования РВС, обеспечения качества обслуживания в вычислительных средах с использованием современных технологий распределенных и параллельных вычислений в фундаментальных и прикладных исследованиях посвящены работы Воеводина В. В., Воеводина Вл. В., Гергеля В. П., Цветкова В.Я. ^[3,4], Горбенко А. В., Дорошенко А. Е., Корнеева В. В., Куссуль Н. Н., Листрового С. В., Мамойленко С. Н., Павлова А. А., Петренко А. И., Погорелого С. Д., Пономаренко В. С., Ролика А. И., Симоненко В. П., Стиренко С. Г., Топоркова В. В., Хорошевского В. Г., Шелестова А. Ю., Шматкова С. И., Буйи Р. (Buyya R.), Ксхафы Ф. (Xhafa F.) и других ученых. Наиболее известными исследованиями в области алгоритмического, математического и программного обеспечения распределения задач по вычислительным узлам гетерогенной вычислительной среды можно считать работы Бершадского А.М., Голубева И.А., Кальпеевой Ж.Б., Селиверстова Е.Ю., Покусина Н.В., Хачкинаева Г.М., Телеснина Б.А., Бычкова И.В., Agrawal D., Zhao H., Sakellariou R., Amar A., Bolze R., Boix E., Amedro B., Bodnartchouk V. и Baduel L. Выбор способа распределения задач (данных) по вычислительным узлам определяет общую эффективность вычислительной среды.

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

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

Анализируя некоторые работы ^[9-13], можно прийти к выводу, что управление нагрузкой состоит из ряда взаимосвязанных процессов, реализуемых в сетевой базе данных (СБД). Также можно прийти к заключению, что наиболее существенное влияние на качество и оперативность управления транзакциями и запросами в СБД оказывает влияние процесс формирования графика реализации множества транзакций и запросов пользователей. В свою очередь изучение данного процесса позволило выделить две основные задачи, требующие своего решения и являющихся составляющими процесса формирования графика реализации множества транзакций и запросов пользователей ^[14-16]:

- задача подготовки исходных данных;

- задача составления плана реализации запросов пользователей и транзакций.

Пусть имеется множество запросов и транзакций:

к сетевой базе данных, содержащей множество:

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

причем каждый атрибут a_jk проверяется на множестве условий:

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

Каждое требование r_ikl представляет собой ограничение на порядок проверки условий, заключающееся в обязательности предварительной проверки определенного подмножества условий, входящих в множества:

Перед проверкой условия L_ikl. Структуры запроса и транзакций поступающие на обслуживание представим в виде графа G(V,E), где множеству вершин соответствуют элементарные операторы транзакций и запросов. Введенные вершины соединены рёбрами, если, по логическим условиям, операторы оказывают влияние на выполнение следующих операторов транзакций и запросов. Ребрам графа сопоставим весовые характеристики представляющие собой сумму времени доступа к требуемому атрибуту a_j и время проверки логических условий L_ikl для реализации оператора запроса (транзакции) q_j в базе данных:

(1).

Поскольку время доступа к требуемому атрибуту T_jk^Дзависит от характеристик используемой система управления базами данных, организации структуры хранения сетевой базы данных и используемых методов доступа то его можно определить до начала выполнения процесса реализации транзакций и запросов. Методика определения данной временной характеристики приведена в ^[6]. Вторая же часть весовой характеристики T_jk⁰ зависит от логических условий предъявляемых пользователями в семантической части запросов и транзакций, а поскольку заранее нет возможности определить порядок появления тех или иных логических условий проверки атрибута a_j, то указанная временная характеристика является изменяемой и требующей динамической оценки в процессе решения задачи непосредственно.Поэтому возникает потребность в решении задачи подготовки исходных данных для определения весовых характеристик ребер графа G(V,E). Физически эта задача реализуется посредством создания в оперативной памяти матриц электронно-вычислительной машины, отражающих взвешенный граф набора транзакций и запросов, предварительный анализ которых проведен посредством применения теории реляционной алгебры.

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

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

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

(2),

где V_ik- количество экземпляров атрибута a_ik ; P_ik⁽¹⁾и P_ilk⁽²⁾ – коэффициенты использования a_ik,характеризующие вероятности использования экземпляров атрибута a_ik в процессах доступа и обработки, соответственно;T_jk^Д, – среднее время доступа к одному экземпляру атрибута a_ik ; T_ik⁰– среднее время обработки a_ik (проверки наложенного на a_ik условия или обработки –a_ik в качестве аргумента функции); W_ik – общее (по всем запросам) количество условий, одновременно проверяемых на a_ik.

Коэффициенты P_ik⁽¹⁾ и P_ilk⁽²⁾ определяются по формулам:

(3),

(4).

Где X_ikz–булева переменная, принимающая значение 0 только тогда, когда обработка a_ikz по всем P_ik условиям при текущих значениях данных утеряла свой смысл (например, если запись при обслуживании предыдущего запроса была удалена); Y_iklz–булева переменная, принимающая значение 0 только тогда, когда обработка a_ikz по l-му условию при текущих значениях данных утеряла свой смысл.

В выражении (1) V_ik определяется структурой информационной системы, ее временными характеристиками и используемым программным аппаратом обработки информации, и может быть определена до обработки запроса. Оптимизация достигается составлением такого упорядоченного множества пар при котором выражение (3) принимает наименьше значение. Построение такого упорядоченного множества определяется двумя факторами: последовательностью обхода a_ik в информационной структуре и выбором множества условий, одновременно проверяемых для каждого a_ik.

Назовём u-тым планом реализации множества запросов в информационной структуре упорядоченное множество пap

, где

где N_u — номер шага выполнения плана Su (на котором обрабатывается единственный атрибут);

– атрибут, который на d-ом шаге подвергается проверке одновременно на множестве таких условий L_ikld, что

и

Опишем множество S допустимых планов просмотра Su∈ S, если ∀dи ∀Likl ∈ Likdсправедливо:

т. е. для каждого проверяемого в соответствии с Su условия выполняется необходимое требование из R. Целевая функция (1) является временной оценкой исполнения плана Suна этапе диспетчеризации. Таким образом, задача сводится к нахождению оптимального плана S^*такого, что

(5).

Таким образом вторая задача может рассматриваться как задача определения кратчайшего гамильтонового пути (КГП) в графе G. Поскольку данная задача относится к классу NP – полных задач, а её решение должно осуществляться в реальном масштабе времени, возникает необходимость в разработке метода, позволяющего находить решение при заданных ограничениях на временные ресурсы. Кроме того, не менее важным требованием, выдвигаемым к алгоритмам реализующих метод поиска кратчайшего гамильтонового пути, является точность, поскольку число сбоев и коллизий в системе зависит от точности сформированного графика и способности выявления тупиковых ситуаций реализации множества транзакций и запросов. Общие методы решения данной задачи для динамических информационных систем являются трудноприменимыми в силу высоких требований к точности нахождения оптимального решения и скорости её решения из-за значительной размерности.

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

Пусть все возможные состояния некоторой системы определяются графом М(F,N) с n вершинами, где вершины соответствуют возможным состояниям системы. Такое пространство состояний можно представить в виде стянутого дерева путей D (рис. 1). Дерево всех путей D содержит (n-1) горизонтальную линейку и (n-1) ярус. Для прочтения путей на каждой горизонтальной линейке можно бывать только один раз. Исходя из стянутого дерева путей, для произвольной вершины j множество путей, ведущих в эту вершину из некоторой вершины s, можно представить в следующем виде:

где подмножества путей из произвольной вершины s в некоторую вершину j графа М(F,N) ранга r

Рисунок 1 - Стянутое дерево всех путей D графа M(F,N)

Используя граф D и введя правила формирования путей следующего ранга мы можем из произвольной вершины s поэтапно строить пути произвольного ранга вплоть до ранга r=n-1. Таким образом, для решения задачи определения кратчайшего гамильтонового пути в графе D нужно построить кратчайшие пути ранга г=n-1от вершины 1, 2, ...,n ко всем остальным вершинам графа и потом среди них выбирать кратчайший.

Рассмотрим процедуруА для определения кратчайшего гамильтонового пути в произвольном графе. Из вершины s строятся все возможные пути ранга r = 1 ко всем вершинам графа D, далее, используя пути ранга r = 1, строятся все возможные пути ранга r = 2 и на их основе формируются пути следующего ранга, с использованием рекуррентного соотношения

(6),

где (j, p) – ребро графа D; n – число различных вершин в графе D, и т. д. до построения путей ранга r = n – 1.

(7).

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

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

а) если анализируемый граф неполный и к вершине р не существует пути некоторого ранга r = k;

б) когда некоторая вершина р войдет во все пути предыдущего ранга.

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

Алгоритм А1 решения задачи определения кратчайших гамильтоновых путей в произвольных графах

Шаг 1. Присваиваем значение S: = 1 переменной S и в графе D используя процедуру А определяем кратчайшие пути ранга r = n – 1 от вершины S ко всем остальным вершинам графа и увеличиваем значение S: = S + 1.

Шаг 2. Проверяем S = n, если нет, то переходим к выполнению шага 1, иначе выполняем следующий шаг.

Шаг 3. Среди всех построенных кратчайших путей ранга r = n – 1 на шагах 1 и 2 выбираем самый короткий, и алгоритм заканчивает работу.

Для решения задачи за один проход определим точку входа, начиная с которой начнет работу алгоритм. Для этого введем понятие минимально удаленной вершиныi в произвольном графе G(V, E)

Пусть задан граф G(V, E) c n вершинами и множеством ребер E каждому из которых присвоен вес в виде произвольного положительного числа βj. Поставим каждой вершине s графа G(V, E)в соответствие вектор Хs

(8),

в котором на s-й позиции стоит символ , означающий, что элемент βs в Хs отсутствует. Множество {βj} представляет собой множество положительных чисел, к которым будем относить и 0. Будем говорить, что некоторая вершина i минимально удалена от вершины s, определяемой вектором Х_s, если расстояние d(s,i) между вершинами s и I определяется соотношением

(9).

Если существует Q вершин i, удовлетворяющих соотношению (9), то это означает, что существует Q минимально равно удаленных вершин от вершины s, определяемой вектором Хs. Определив вершину i входа для графа можно решать задачу определения кратчайшего гамильтонового пути за один проход процедуры А1, при этом погрешность по сравнению с n-проходной процедурой, как будет показано ниже, увеличивается не более чем на один процент, а сложность алгоритма понижается в n – 1 раз.

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

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

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

· область формирования исходных данных и настройки тестов;

· область анализа полученных результатов и их отображения на графиках;

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

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

· автоматический ввод расчетных данных;

· ручной ввод расчетных данных;

· отображение статистики;

· запись результатов в базу данных;

· простой и интуитивно доступный интерфейс.

При экспериментальном сравнении разработанных алгоритмов с известными весами ребер графа генерировались по равномерному закону распределения в диапазоне (0–50). Для получения среднего значения каждой точки графиков всех анализируемых характеристик решалось по 200 тестовых задач, все результаты статистического анализа получены с доверительной вероятностью 0,95. На всех рисунках разработанные алгоритмы А1 и А2 обозначены как метод –1 и метод–2. Как видно из графиков, приведенных на рис. 2 при n≥27, алгоритмы Литтла и локального поиска имеют существенно более высокую временную сложность по сравнению с разработанными.

Рисунок 2 – Зависимости числа элементарных операций от размерности решаемой задачи

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

Рисунок 3 – Зависимость относительной погрешности от размерности решаемой задачи

Из графиков приведенных на рис. 4, видно, что процент неточных решений для алгоритма А1 при n≥27 очень низок. Экспериментальное исследование показало, что при n≥27 на 2000 тестовых задач в среднем только 3 давали приближенное решение и при этом погрешность не превышала 1–2%.

Рисунок 4 - Зависимость числа неточных решений в % от размерности решаемой задачи

Использование эвристического правила в алгоритме А2 позволило с одной стороны существенно уменьшить временную сложность этого алгоритма по сравнению с А1, но при этом возрастает погрешность и число неточных решений в нем с увеличением размерности решаемой задачи растет.

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

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

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