Развитие методов, алгоритмов и программных средств для формирования транзакций на основе решения задач поиска кратчайших гамильтоновых путей в произвольных графах распределенных баз данных тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Фильгус Дмитрий Игоревич

• Фильгус Дмитрий Игоревич
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Фильгус Дмитрий Игоревич

Введение

Глава 1. Критический анализ существующих технических средств и способов управления рабочей нагрузкой в распределенной базе данных

1.1 Управление рабочей нагрузкой в распределенной базе данных

при использовании концепции многопрограммно сти

1.2 Оценка упорядочиваемо сти и восстанавливаемости транзакций

1.2.1 Правила достижения упорядочиваемо сти графов реализации рабочей нагрузки

1.2.2 Правила управления процессом реализации транзакций

на основе оценки времени выполнения работ

1.3 Основные определения и формализованное описание исходных данных

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

базах данных

1.5 Критический анализ методов решения задач целочисленного программирования с булевыми переменными

1.6 Анализ современных архитектур и технологий построения сложных мультимедиа систем и систем виртуальной реальности

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

базах данных

1.8 Формулирование научно-технических задач исследования

Глава 2. Разработка методов решения задач на произвольных

графах с использованием рангового подхода

2.1 Модель рангового подхода решения задач дискретной оптимизации

2.2 Метод поиска кратчайшего гамильтонова пути на графе с использованием рангового подхода решения задач дискретной оптимизации

2.2.1 Формализация задачи поиска кратчайшего гамильтонова

пути на графе

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

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

2.3 Метод решения задач квадратичного и линейного программирования с булевыми переменными

2.4 Метод параллельных вычислений для фрагментации данных в РСУБД на основе рангового подхода

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

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

2.4.3 Архитектуры параллельных вычислительных структур

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

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

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

распределенной базе данных

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

3.2 Модель формирования графика реализации рабочей нагрузки в распределённой базе данных с использованием аппарата сетей

Петри

3.2.1 Модели реализации отдельных типов операций над

записями СБД

3.2.2 Построение и анализ модели графика реализации

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

областей поиска

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

117

122

3.3.1 Исследование показателя числа элементарных операций необходимых для реализации разработанных алгоритмов

3.3.2 Исследование показателя числа обработанных векторов необходимых для реализации разработанных алгоритмов

3.3.3 Исследование показателя погрешности вносимой алгоритмом

3.3.4 Исследование показателя оперативности решения задачи

на заданной однопроцессорной машине

3.3.5 Исследование показателя числа неточных решений

3.3.6 Исследование алгоритмов целочисленного линейного программирования с булевыми переменными на основе рангового подхода

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

Заключение

Список литературы

Список сокращений и условных обозначений

Словарь терминов

Список рисунков

Список таблиц

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

распределенных базах данных

164

Приложение Б. Исходные данные для решения задачи

формирования графа допустимых переходов

Приложение В. Cвидетельство о государственной регистрации

программы на ЭВМ

Приложение Г. Акты о внедрении

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

Введение

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

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

Отметим, что высокая размерность проблемы, характерная для рассматриваемой предметной области, необходимость проведения вычислений (а в ряде ситуаций и решения самой проблемы назначения и планирования) в реальном времени не позволяют применять многие известные подходы, нацеленные на получение необходимиого результата. По этой причине широкое распространение на практике получили приближенные алгоритмы, позволяющие получить решение близкое к оптимальному за существенно меньшее время[4]. Сложность задач решаемых в этом направлении, обусловлена тем, что большинство из них носит комбинаторный характер, характеризуется экспоненциальной временной сложностью и относится к классу NP-полных задач, а их решение вычис-

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

Анализ процесса управления выполнением транзакций и запросов в вычислительных комплексах [7] позволил определить, что существующие подходы к построению плана выполнения запросов и транзакций являются реализацией двух взаимосвязанных задач: подготовки данных и непосредственно построения плана реализации запросов пользователей и транзакций. Задача подготовки данных, в применяемых подходах, рассматривается, как проведение оценивания операторов языка манипулирования данными временными характеристиками. Однако, такие оценки, не позволяют в полной мере администратору распределённой базы данных качественно определить поведение управляемого комплекса, поскольку, привязка к временным характеристикам является оценкой некоторой конкретной аппаратной реализации сети и её перенос на другую сеть может показать другие характеристики [3; 5].

Построения плана реализации запросов пользователей и транзакций сводится к решению задач поиска кратчайшего гамильтонова пути. Эти задачи относятся к классу КР-полных задач, которые с трудом поддаются решению даже при использовании современных ЭВМ. Доминирующее место в методах решения этих задач в настоящее время занимают комбинаторные методы. К ним, в первую очередь, можно отнести методы ветвей и границ, и некоторые его модификации в частности метод Литтла, алгоритм локального поиска. Практическое применение данных методов затруднено при решении задач большой размерности с требуемой точностью за допустимое время [8].

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

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

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

Объект исследования. Распределённая компьютерная база данных.

Предмет исследования определён паспортом специальности 05.13.11, область исследования №4 ("системы управления базами данных и знаний"), а так же перечнем задач решаемых в диссертации.

Большое количество исследований и публикации свидетельствует об актуальности настоящей диссертации. Так,с появлением новых задач в связи с развитием технологий распределенной обработки данных, решением задачи разработки методов и моделей повышения управляемости обслуживания и выполнения транзакций в РСУБД занимались такие ученые, как Андрианова Е.Г., Бернштейн П.А. (Bernstein P.A.), Вейкум Г. (Weikum G.), Воссен Г. (Vossen G.), Кульба В.В., Ковалевский С.С., Косяченко С.А., Раев В.К., Сигов А.С., Советов Б.Я., Чертовской В.Д., Чардин П. и др. Значительный вклад в теорию и практику вычислительных комплексов и параллельных вычислительных технологий внесли известные ученые, среди которых: С.М. Абрамов, Е.П. Балашов, В.Б. Бетелин, В.С. Бурцев, В.В. Васильев, В.В. Воеводин, Вл.В. Воеводин, В.М. Глушков, В.Ф. Евдокимов, Э.В. Евреинов, А.В. Забродин, В.П. Иванников, М.Б. Игнатьев, А.В. Каляев, И.А. Каляев, Ю.Г. Косарев, В.В. Корнеев, Л.Н. Королев, В.П. Кулагин, В.Г. Лазарев, А.О. Лацис, С.А. Лебедев, В.К. Левин, И.И. Левин, Г.И. Марчук, В.А. Мельников, Ю.И. Митропольский, Е.В. Никульчев, Д.А. Поспелов, И.В. Прангишвили, Д.В. Пузанков, Г.Е. Пухов, Г.Г. Рябов, А.С. Сигов, В.Б. Смолов, А.Н. Томилин, Я.А. Хетагуров, В.Г. Хорошевский, Б.Н. Четверушкин, Ю.И. Шо-кин, Н.Н. Яненко, P. Balaji, J. Dongarra, S. Cray, W. Gropp, T. Hoeler, S. Matsuoka,

R. Rabenseifner, M. Snir, T. Sterling, J.L. Traf, и др. Также в научно-технической литературе большое число публикаций посвящено проблемам назначения и планирования заданий. Основополагающие результаты были получены в работах Liu C.L., Layland J.W., Coffman E.G., Cottet F., Stankovic J. A., Martello S., Toth P., Keller H., Топоркова В.В., Костенко В.А., Листрового С.В., Минухина С.В. и других авторов. Анализ проводимых исследований в их работах показал, что пока нет общего подхода и остаются нерешённая задача повышения оперативности формирования графика реализации множества запросов пользователей и транзакций обеспечивающего устойчивое функционирование распределенной системы управления базой данных.

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

Для достижения этой цели в диссертации необходимо решение задач, связанных с:

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

2. решением задач квадратичного и линейного программирования с булевыми переменными;

3. решением задачи формирования нагрузки на дугах графа для поиска кратчайшего гамильтонова пути;

4. оценкаой эффективности алгоритмов.

Перечисленные задачи будут дополнены и уточнены в разделе 1.8 по результатам критического обзора Главы 1.

Научная новизна сформулирована в заключении диссертации.

Практическая значимость

1. Разработан алгоритм поиска кратчайшего гамильтонова пути, обеспечивает снижение времени решения задачи в 2 ^ 4 раза по сравнению с существующими методам.

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

и обеспечивает решение задачи формирования графика реализации запросов пользователей и транзакций при числе операторов ЯМД 3 < п < 100 за время Тнеобх. = 1 мин, что увеличивает количество операторов ЯМД, которые реализуются одновременно, в 3 раза по сравнению с существующими методами.

3. Разработано и зарегистрировано математическое и программное обеспечения решения задачи формирования графика реализации запросов пользователей и транзакций в РСУБД. Получено свидетельство о государственной регистрации программы для ЭВМ № 2019610724 16 января 2019 г. в Федеральной службе по интеллектуальной собственности - Роспатент.

4. Работа выполнялась в рамках государственного задания на научное исследование № 2.7178.2017/БЧ - "Исследование когнитивной семиотики в мультимедиа в среде виртуальной реальности"

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

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

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

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

Апробация работы. Основные результаты по теме диссертации изложены в 8 печатных изданиях, 5 из которых изданы в журналах, рекомендованных ВАК, 2 —в тезисах докладов.

Объем и структура работы. Диссертация состоит из введения, трёх глав, заключения и трёх приложений. Полный объём диссертации составляет 171 страницу, включая 43 рисунка и 10 таблиц. Список литературы содержит 112 наименований.

Глава 1. Критический анализ существующих технических средств и способов управления рабочей нагрузкой в распределенной базе данных

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

Важнейшей целью сопровождения функционирования распределенных баз данных является организация параллельного доступа многих пользователей к общим данным, используемым ими совместно. Обеспечить параллельный доступ относительно несложно, если все пользователи будут только читать данные, помещенные в базу данных. В этом случае работа каждого из них не оказывает никакого влияния на работу остальных пользователей [10; 11]. Однако, если два или больше пользователей одновременно обращаются к хранимым данным и хотя бы один из них имеет целью обновить хранимую в базе информацию, возможно взаимное влияние процессов друг на друга, способное привести к несогласованности данных [12—15].

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

нение операций двух транзакций чередуется, и таким образом достигается их параллельное выполнение. Кроме того, общая производительность комплексов (количество работы, выполняемой на протяжении заданного временного интервала) повышается, поскольку процессор выполняет команды другой транзакции, вместо того чтобы бесполезно ожидать завершения запущенной операции ввода/вывода. Однако, несмотря на то что каждая из транзакций может сама по себе выполняться вполне корректно, подобное чередование операций способно приводить к неверным результатам, из-за чего целостность и согласованность распределённой базы данных будет нарушена. Рассмотрим три примера потенциальных проблем, которые могут иметь место при параллельном выполнении транзакций, — проблему потерянного обновления, проблему зависимости от нефиксированных результатов и проблему несогласованной обработки [16—18].

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

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

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

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

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

1. нарушение семантики составления транзакций на узлах-серверах;

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

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

4. наличие тупиковых решений (взаимоблокировок), являющихся прозрачными для РСУБД при использования протоколов блокировок;

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

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

7. размер элементов данных выбранных в качестве защищаемой единицы для протокола управления данными противоречит уровню декомпозиции транзакций;

8. нарушение правил совместимости различных типов блокировок в многоуровневом протоколе блокирования.

1.2 Оценка упорядочиваемости и восстанавливаемости транзакций

1.2.1 Правила достижения упорядочиваемости графов реализации рабочей

нагрузки

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

выполнении в каждый момент времени только одной транзакции - предыдущая транзакция обязательно должна быть зафиксирована, прежде чем будет разрешено начатьвыполнение следующей транзакции [19; 20]. Однако назначение многопользовательских информационных комплексов состоит в обеспечении максимальной степени параллельности выполнения транзакций пользователей, поэтому те транзакции, которые не оказывают влияния на работу друг друга, вполне могут запускаться одновременно. Например, транзакции, обращающиеся к разным частям распределённой базы данных, не окажут влияния на работу друг друга и, следовательно, могут выполняться одновременно. В связи с этим в теории баз данных используют понятие упорядочиваемости как средства, способным помочь в выявлении тех транзакций, которые гарантированноне вызовут нарушения согласованности данных при одновременном выполнении [21—24].

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

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

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

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

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

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

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

Правило 3. Если некоторый глобальный график 53 является последовательным, то эквивалентные ему графики и 52 упорядоченные .

Правило 4. Если некоторый глобальный график 53 является упорядоченным по просмотру, то эквивалентные ему графики и 52 являются также упорядоченными по просмотру. Обратное утверждение не верно.

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

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

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

1. вершин, соответствующих каждой из транзакций;

2. направленных ребер Т{ ^, где транзакция 7], считывает значение элемента, записанного транзакцией ^;

3. направленных ребер Т{ ^ Ту, где транзакция Т^, записывает значение в элемент данных после того, как он был считан транзакцией ^.

Правило 7. Два графика 51 и 52, состоящих из одних и тех же операций, входящих в состав п транзакций Т1 , Т2, ... Тп, являются эквивалентными по просмотру, если выполняются следующих три условия.

1. для каждого элемента данных х : если транзакция Т^, прочла исходное знчение х в графике 51, эта же транзакция должна прочесть исходное значение х ив графике 52;

2. для каждой операции чтения элемента данных х транзакцией в графике 51 : если считанное значение элемента х было записано транзакцией ^, то и в графике 52 транзакция Т{ должна считывать значение элемента х, записанное транзакцией ^;

3. для каждого элемента данных х : если в графике 51 последняя операция записи значения х была выполнена транзакцией ^, эта же самая транзакция должна выполнять последнюю запись значения элемента данных х ив графике 52.

Правило 8. Каждый конфликтно упорядоченный график является упорядоченным по просмотру, обратное утверждение неверно. Данный график является упорядоченным по просмотру, но не является конфликтно упорядоченным. В этом примере для транзакций Т1 и Т2 не соблюдается правило вынужденной записи — другими словами, в них выполняется слепая запись.

Список литературы диссертационного исследования кандидат наук Фильгус Дмитрий Игоревич, 2020 год

Список литературы

1. Соколинский, Л. Б. Методы организации параллельных систем баз данных на вычислительных системах с массовым параллелизмом: Дис. ... докт. физ.-мат. наук: 05.13.18 / Л. Б. Соколинский. — Челябинск, 2003. — 247 с.

2. Третьяк, В. Ф. Параллельная вычислительная структура для решения задачи булевого линейного программирования / В. Ф. Третьяк, С. В. Кавун // Труды IV международной научно-технической конференции. Информационные технологии: наука, техника, технология, образование, здоровье. — 1996. — С. 37—39.

3. Листровой, С. В. Метод решения задач целочисленного линейного программирования с булевыми переменными на основе рангового подхода / С. В. Листровой, Д. Ю. Голубничий, Е. С. Листровая // Электрон. моделирование. — 1998. — № 6. — С. 14—32.

4. Листровой, С. В. Разработка метода мониторинга распределенной вычислительной системы на основе определения кратчайших путей и кратчайших гамильтоновых циклов в графе / С. В. Листровой, С. В. Ми-нухин, Е. С. Листровая // Восточно-Европейский журнал передовых технологий. — 2015. — Т. 6. № 4 (78). — С. 32—45.

5. Теоретические основы проектирования оптимальных структур распределенных баз данных / В. В. Кульба [и др.]. — М. : СИНТЕГ, 1999. — 660 с.

6. Осиевский, С. В. Процедура определения точки входа на основе анализа векторов весовых характеристик исходного графа состояний / С. В. Оси-евский, А. А. Тимченко // Системи обробки шформацп. — 2002. — Вып. 22, №6.— С. 281—284.

7. Кофман, А. Методы и модели исследования операций. Целочисленное программирование. / А. Кофман, А. Анри-Лабродер. — М. : Мир, 1977. — 265 с.

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

сетевой базе данных / Д. И. Фильгус // Кибернетика и программирование. — 2018. — № 4.

9. Сергиенко, И. В. Модели и методы решения на ЭВМ комбинаторных задач оптимизации / И. В. Сергиенко, М. Ф. Каспшицкая. — ^ : Наук. думка, 1981. — 228 с.

10. Аникин, Н. А. Управление параллельным выполнением транзакций в распределенных гетерогенных базах данных при доступе из мобильной среды: Дис. ... канд. тех. наук: 05.13.11 / Н. А. Аникин. — Москва, 2012. — 230 с.

11. Мезенцев, Ю. А. Прикладные задачи и алгоритмы оптимизации расписаний параллельных обслуживающих систем / Ю. А. Мезенцев // Научный вестник Новосибирского государственного технического университета. — 2016. — Вып. 62, № 1. — С. 49—73.

12. Цветкова, Ю. А. Разработка и исследование элементов и устройств для повышения производительности параллельных вычислителей ориентированных на обработку многомерных задач: Дис. ... канд. тех. наук: 05.13.11 / Ю. А. Цветкова. — Таганрог, 2011. — 158 с.

13. Аль-хулайди Абдулмаджид, А. Г. Разработка и исследование алгоритмов управления очередями заданий при организации параллельных вычислений в кластерных вычислительных системах: Дис. ... канд. тех. наук: 05.13.01 / А. Г. Аль-хулайди Абдулмаджид. — Ростов-на-Дону, 2011. — 184 с.

14. Ковягин, В. В. Информационная реальность: сущность и особенности: Дис. ... канд. фил. наук: 09.00.11 / В. В. Ковягин. — Улан-Уде, 2018. — 178 с.

15. Квантовая информатика: обзор основных достижений / А. С. Сигов [и др.] // Российский технологический журнал. — 2019. — Т. 7, № 1. — С. 5—37.

16. Сергеев, И. В. Программное и математическое обеспечение системы репликации данных СУБД независимых платформ: Дис. ... канд. техн. наук: 05.13.11 / И. В. Сергеев. — Москва, 2003. — 131 с.

17. Минухин, С. В. Модели, методы, информационные технологии планирования пакетов заданий в распределенных вычислительных системах: Дис. ... доктора тех. наук: 05.13.06 / С. В. Минухин. — Харьков, 2017. — 486 с.

18. Курносов, М. Г. Алгоритмы организации функционирования распределенных вычислительных систем с иерархической структурой: Дис. ... доктора тех. наук: 05.13.15 / М. Г. Курносов. — Новосибирск, 2016. — 281 с.

19. Бурлуцкая, М. В. Математическое и программное обеспечение обработки потоковых данных в распределенных системах на основе корреляционного разложения потока: Дис. ... канд. техн. наук: 05.13.11 / М. В. Бурлуцкая. — Воронеж, 2016. — 129 с.

20. Скородумов, Ю. М. Назначение и планирование заданий в распределенных системах реального времени: Дис. ... канд. тех. наук: 05.13.11 / Ю. М. Скородумов. — Санкт-Петербург, 2016. — 124 с.

21. Горобец, В. В. Математические модели и алгоритмы оптимизации размещения данных биллинговых OLTP-систем: Дис. ... канд. тех. наук: 05.13.18 / В. В. Горобец. — Новочеркаск, 2014. — 190 с.

22. Горобец, В. В. Современная биллипговая OLTP-система на базе технологии Cloud Computing / В. В. Горобец. — KG : LAP LAMBERT Academic Publishing: AV Akademikerverlag GmbH &Co, 2013. — 171 с.

23. Хантимиров, Р. И. Методы и алгоритмы распределения ресурсов в облачных вычислительных средах, реализованных на основе модели «инфраструктура как сервис»: Дис. ... канд. тех. наук: 05.13.15 / Р. И. Хантимиров. — Москва, 2015. — 117 с.

24. Зыков, С. В. Технология интеграции данных в гетерогенных корпоративных программных комплексах: Дис. ... доктора тех. наук: 05.13.11 / С. В. Зыков. — Москва, 2017. — 128 с.

25. Косяченко, С. А. Задача синтеза оптимальной модульной системы обработки данных реального времени с двухзвенной архитектурой «Клиент-Сервер» / С. А. Косяченко, С. С. Ковалевский, С. К. Сомов // Проблемы управления. — 2013. — № 4. — С. 41—49.

26. Буй, Д. Б. Модели, методы и алгоритмы оптимизации запросов в базах данных / Д. Б. Буй, В. Г. Скобелев // Компьютерные системы и информационные технологии. — 2014. — 2 (66). — С. 43—58.

27. Колпаков, Р. М. Об оценках вычислительной сложности варианта параллельной реализации метода ветвей и границ для задачи о ранце / Р. М. Колпаков, М. А. Посыпкин // Известия РАН: Теория и системы управления. — 2011. — № 5. — С. 74—83.

28. Смирнов, С. А. Предварительная декомпозиция задач дискретной оптимизации для ускорения алгоритма ветвей и границ в распределенной вычислительной среде / С. А. Смирнов, В. В. Волошинов // Компьютерные исследования и моделирование. — 2015. — Т. 7. № 3. — С. 719—725.

29. Овчинников, В. А. Систематизация точных методов дискретной оптимизации / В. А. Овчинников // Наука и образование: научное издание МГТУ им. Н. Э. Баумана. — 2015. — № 6. — С. 288—304.

30. Болбаков, Р. Г. Абдуктивный вывод / Р. Г. Болбаков, В. Я. Цветков // Философия информационного поля. — 2018. — Т. 21, № 3. — С. 68—71.

31. Плутенко, А. Д. Разработка теоретических основ анализа процессов доступа к базам данных распределенных автоматизированных систем: Дис. ... докт. техн. наук: 05.13.18 / А. Д. Плутенко. — Блоговещенск, 2004. — 371 с.

32. Корепанов, В. Д. Использование нейронных сетей при модификации генетического алгоритма / В. Д. Корепанов, В. П. Кулагин, Р. Ф. Халабия // Информационные технологии. — 2018. — Т. 24, № 12. — С. 799—804.

33. Зиновьев, Э. В. Управление сетевыми информационными процессами и ресурсами / Э. В. Зиновьев. — Рига : Зинатне, 1987. — 303 с.

34. Дубинин В. Н. Зинкин, С. А. Сетевые модели распределенных систем обработки, хранения и передачи данных / С. А. Дубинин В. Н. Зинкин. — Пенза : Приволжский Дом знаний, 2013. — 452 с.

35. Мамедов, К. Ш. Алгоритмы построения гарантированного решения и гарантированного приближенного решения многомерной задачи о ранце / К. Ш. Мамедов, Н. Н. Мамедов // Проблемы управления и информатики. — 2014. — № 5. — С. 30—37.

36. Вардомацкая, Е. Ю. Оптимизация маршрута с использованием теории графов в пакетах прикладных программ / Е. Ю. Вардомацкая, В. Л. Шарстнев, Я. А. Алексеева // Вестник Витебского государственного технологического университета. — 2016. — Вып. 30, № 1. — С. 130—139.

37. Надежность и эффективность в технике. Справочник в 10 томах. / Под ред. А. И. Рембезы. — М. : Машиностроение, 1986. — 233 с. — 1 т.: Методология. Организация. Терминология.

38. Надежность и эффективность в технике. Справочник в 10 томах / Под ред. В. Ф. Уткина. — М. : Машиностроение, 1988. — 328 с. — 3 т.: Эффективность технических систем.

39. Насонов, Д. В. Эволюционные алгоритмы распределения больших данных в вычислительно-интенсивных задачах: Дис. ... канд. тех. наук: 05.13.11 / Д. В. Насонов. — Санкт-Петербург, 2016. — 154 с.

40. Ярыгина, А. С. Методы и средства эффективного выполнения сценариев аналитической обработки данных на основе оптимизации и приближенных вычислений: Дис. ... канд. физ.мат. наук: 05.13.17 / А. С. Ярыгина. — Санкт-Петербург, 2015. — 146 с.

41. Гэри, М. Вычислительные машины и трудно решаемые задачи / М. Гэри, Д. Джонсон. — М. : Мир, 1982. — 416 с.

42. Ф., Х.Теория графов / Х. Ф. — Москва : Ленанд, 2018. — 304 с.

43. Хусаинов, А. А. Дискретная математика: учеб. пособие / А. А. Хусаинов, Н. Н. Михайлова. — Комсомольск-на-Амуре : ФГБОУ ВПО «КнАГТУ», 2013. — 78 с.

44. Михалевич, В. С. Последовательные алгоритмы оптимизации и их применение / В. С. Михалевич // Кибернетика. — 1965. — № 1. — С. 85—89.

45. Моудера, Д. Исследование операций: В 2-х томах. / Д. Моудера, С. Элма-граби. — М. : Мир, 1981. — 677 с. — 2 т.

46. Олешко, М. В. Алгоритм для решения задач целочисленного программирования с булевыми переменными, использующий вероятностные оценки. Программное обеспечение экстремальных задач и пакеты прикладных программ / М. В. Олешко, В. П. Шило. — 1982.

47. Венцель, Е. С. Исследование операций. Задачи, принципы, методология. / Е. С. Венцель. — М. : Наука, 1980. — 208 с.

48. Воеводин, В. В. Математические модели и методы в параллельных процессах / В. В. Воеводин. — М. : Наука, 1986. — 296 с.

49

50

51

52

53

54

55

56

57

58

59

60

61

62

Юдин, Д. Б. Линейное программирование (теория, методы и приложения) / Д. Б. Юдин, Е. Г. Гольштейн. — М. : Наука, 1969. — 424 с.

Вагнер, Г. Основы исследования операций. / Г. Вагнер. — М. : Мир, 1969. — 354 с. — 2 т.

Васильев, В. В. Специализированные вычислительные структуры для решения сетевых задач и их применение.Неоднородные вычислительные системы. / В. В. Васильев. — 1975.

Вишенчук, И. М. Алгоритмические операционные устройства и суперЭВМ / И. М. Вишенчук, Н. Черкасский. — К. : Техника, 1990. — 197 с.

Рейнгольд, Э. Комбинаторные алгоритмы. Теория и практика / Э. Рейнгольд, Ю. Нивергельт, Н. Део. — М. : Мир, 1980. — 312 с.

Саати, Т. Целочисленные методы оптимизации и связанные с ними экстремальные проблемы / Т. Саати. — М. : Мир, 1973. — 304 с.

Самойленко, С. И. Сети ЭВМ. / С. И. Самойленко. — М. : Наука, 1986. — 160 с.

Чуев, Ю. В. Исследование операций в военном деле. / Ю. В. Чуев. — М. : Воениздат, 1970. — 256 с.

Стайглиц, К. Комбинаторная оптимизация. Алгоритмы и сложность / К. Стайглиц. — М. : Мир, 1985. — 512 с.

Пирьянович, В. А. Машинные эксперименты по решению задач целочисленного программирования с помощью локально-стохастических алгоритмов / В. А. Пирьянович // Журнал вычислительной математики и математической физики. — 1979. — Т. 19, № 1. — С. 79—87.

Полунин, И. Ф. Курс математического программирования. / И. Ф. Полунин. — Минск : Высш. школа, 1970. — 320 с.

Кристофидес, Н. Теория графов. Алгоритмический подход. / Н. Кристо-фидес. — М. : Мир, 1978. — 432 с.

Кудрявцев, Е. Исследование операций в задачах, алгоритмах и программах. / Е. Кудрявцев. — М. : Радио и связь, 1984. — 182 с.

Юсупов, Р. М. Статистические методы обработки результатов наблюдений / Р. М. Юсупов. — М. : МО СССР, 1984. — 563 с.

63. Шнепс, М. А. Системы распределения информации. Методы расчета: Справ. пособие. / М. А. Шнепс. — М. : Связь, 1979. — 344 с.

64. Демичев, Г. М. Складское тарное хозяйство (Учебн. для инж. экон. спец. вузов) / Г. М. Демичев. — 3-е изд., переработанное и дополненное. — М. : Высшая школа, 1990. — 191 с.

65. Сергиенко, И. В. Метод неявного перебора для решения некоторых экстремальных задач на множествах / И. В. Сергиенко, В. А. Рощин // Обчислювальна та прикладна математика. Сер."Оптим1защя". — 1996. — С. 106—118.

66. Сухарев, А. Г. Курс методов оптимизации / А. Г. Сухарев, А. В. Тимохов,

B. В. Федоров. — М. : Наука, 1986. — 328 с.

67. Генкин, В. Л. Информационные устройства транспортно-складских систем. Ленинград, институт авиационного приборостроения / В. Л. Генкин. — Л. : Издательство ЛГУ, 1988. — 150 с.

68. Козерацкая, Л. Н. Множество строго эффективных точек задачи целочисленной векторной оптимизации как характеристики ее устойчивости / Л. Н. Козерацкая // Кибернетика и системный анализ. — 1997. — № 6. —

C. 184—187.

69. Корбут, А. А. Приближенные методы дискретного программирования /

A. А. Корбут, Ю. Ю. Финкельштейн // Изв. АН СССР. Тех. кибернетика. — 1983. — № 1. — С. 165—176.

70. Баранов, В. И. Экстремальные комбинаторные задачи и их приложения. /

B. И. Баранов, Б. С. Стечкин. — М. : Наука, 1989. — 160 с.

71. Харченко, В. С. Теоретические основы дефектоустойчивых цифровых систем с версионной избыточностью / В. С. Харченко. — МОУ, 1996. — 506 с.

72. Замбицкий, Д. К. Алгоритмы решения оптимизационных задач на сетях / Д. К. Замбицкий, Д. Д. Лозовану. — Кишинев : Штиница, 1983. — 116 с.

73. Зиновьев, Э. В. Конфликтные ситуации в информационных системах / Э. В. Зиновьев, А. А. Стрекалев. — Рига : Зинатне, 1985. — 166 с.

74. А., Е. В. Лекции по теории графов / Е. В. А. — Москва : URSS, 2013. — 383 с.

75. Системы и модели управления. Обоснование решений методами математического программирования. Метод. Пособие / Под ред. В. И. Вишневецкого. - М. : МО СССР, 1982. - 47 с.

76. Сергиенко, И. В. Вопросы исследования систем обработки данных и повышения их эффективности / И. В. Сергиенко, В. В. Скопецкий // Кибернетика. - 1977. - № 6. - С. 61-72.

77. Сергиенко, И. В. Вероятностный подход к оценке эвристик для задач булева линейного программирования / И. В. Сергиенко, В. П. Шило // Кибернетика. - 1987. - № 1. - С. 12-17.

78. Сергиенко, И. В. Исследование устойчивости и параметрический анализ дискретных оптимизационных задач / И. В. Сергиенко, Л. Н. Козерацкая, Т. Т. Лебедева. - К. : Наук. думка, 1995. - 170 с.

79. Фильгус, Д. И. Развитие методов параллельных вычислений для фрагментации данных сетевой базы данных на основе рангового подхода / Д. И. Фильгус, Е. Г. Андрианова, В. К. Раев // Электронный журнал Cloud of Science. - 2018. - Т. 3, № 5.

80. Фильгус, Д. И. Метод поиска кратчайшего гамильтонового пути в произвольном графе на основе рангового подхода, обеспечивающего высокую оперативность и малую погрешность решения задачи организации процесса управления множеством транзакций и запросов при их реализации в сетевых базах данных / Д. И. Фильгус, А. А. Лобанов // Кибернетика и программирование. - 2018. - № 5.

81. Андрианова, Е. Г. Диссипация и энтропия в физических и информационных системах / Е. Г. Андрианова, С. В. Мельников, В. К. Раев // Фундаментальные исследования. - 2015. - № 8-2. - С. 233-238.

82. Никульчев, Е. В. Актуализация образовательных программ на основе патентного анализа как индикатора развития инновационных технологий / Е. В. Никульчев, Д. Ильин, Г. Г. Бубнов // Cloud of Science. - 2017. - Т. 4, №4.-С. 513-524.

83. Гришмановский, П. В. Анализ технологий репликации данных и методы повышения эффективности разрешения конфликтов ирепликаци / П. В. Гришмановский, Е. В. Базилевкий // Вестник Волжского университета им. В. Н. Татищева. - 2012. - Вып. 19, № 2. - С. 98-106.

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

B. В. Горобец // Известия высших учебных заведений. Северо-Кавказский регион. Серия: Технические науки. — 2013. — Вып. 171, № 2. — С. 9—13.

85. Мейкшан, Л. И. Анализ двухуровневой информационной системы с репликацией данных / Л. И. Мейкшан // Инфокоммуникационные технологии. — 2009. — Т. 7, № 2. — С. 56—60.

86. Локшин, М. В. Исследование надежности RAID-0 массивов в системах с репликацией данных / М. В. Локшин // Вестник Воронежского государственного технического университета. — 2013. — Т. 9, № 6—3. — С. 47—93.

87. Ziane, M. Parallelism and query optimization / M. Ziane, M. Zait, H. Q. Hong // International Journal of Computer Science and Engineering. — 1995. - Vol. 10, no. 1. - P. 50-56.

88. Воробьев, С. П. Исследование модели транзакционной системы с репликацией фрагментов базы данных, построенной по принципам облачной среды / С. П. Воробьев, В. В. Горобец // Инженерный вестник Дона. — 2012. — Вып. 22, № 4—1. — С. 29.

89. Локшин, М. В. Методика получения временных оценок исполнения запросов в параллельных СУБД с репликацией данных / М. В. Локшин // Системы управления и информационные технологии. — 2014. — Т. 58, № 4. — С. 41—44.

90. Кульба, В. В. Репликация, резервирование и схемы восстановления информации в ненадежных распределенных системах / В. В. Кульба,

C. К. Сомов // Вестник РГГУ. Серия: Экономика. Управление. Право. — 2017. — Вып. 9, № 3. — С. 28—39.

91. Котиков, П. Е. Репликация данных между серверами баз данных в среде геоинформационных систем / П. Е. Котиков, А. А. Нечай // Вестник Российского нового университета. Серия: Сложные системы: модели, анализ и управление. — 2015. — № 1. — С. 88—91.

92. Сорокин, В. Е. Репликация данных в иерархических информационных системах с непостоянной связностью узлов / В. Е. Сорокин // Программные продукты и системы. — 2015. — № 4. — С. 203—209.

93. Listrovoy, S. V. Solutioon Method on the Basis of Rank Approach for integer Linear Programming Problems with Boolean Variables / S. V. Listrovoy, D. Y. Golubnichiy, E. S. Listrovaya // Engineering Simulation. — 1999. — No. 16. - P. 707-725.

94. Listrovoy, S. V. Parallel algorithms of calculation process optimization for the boolean programming problems Engineering Simulation / S. V. Listrovoy, D. Y. Golubnichiy, E. S. Listrovaya // Engineering Simulation. — 1999. — No. 16. - P. 569-579.

95. Листровой, С. В. Ранговый подход к решению задач линейного и нелинейного булевого программирования для планирования и управления в распределенных вычислительных системах / С. В. Листровой, Е. С. Лист-ровая, М. С. Курцев // Электрон. моделирование. - 2017. - Т. 39, № 1. -С. 19-38.

96. Фильгус, Д. И. Определение кратчайших гамильтоновых путей в произвольных графах распределенных баз данных / Д. И. Фильгус, Е. Г. Андрианова, В. К. Раев // Российский технологический журнал. - 2019. - Т. 7, № 4.

97. Дыйканов, С. К. Задача о подсчете гамильтоновых путей и циклов / С. К. Дыйканов // Вестник современной науки. - 2016. - Вып. 18, №6.1.-С. 8-9.

98. Метод взвешенного случайного перебора для решения задач дискретной комбинаторной оптимизации / Э. И. Ватутин [и др.] // Известия Волгоградского государственного технического университета. - 2014. - Вып. 137, № 10. - С. 59-64.

99. Частикова, В. А. Разработка и сравнительный анализ эвристических алгоритмов для поиска наименьшего гамильтонова цикла в полном графе / В. А. Частикова, К. А. Власов // Фундаментальные исследования. -2013. -№ 10. - С. 63-67.

100. Авезова, Я. Э. Условия примитивности и оценки экспонентов множеств ориентированных графов / Я. Э. Авезова, В. М. Фомичев // Прикладная дискретная математика. - 2017. - № 35. - С. 89-101.

101. Федорин, А. Н. Многокритериальные задачи ранцевого типа: разработка и сравнительный анализ алгоритмов: Дис. ... канд. техн. наук: 05.13.18 / А. Н. Федорин. — Нижний Новгород, 2010. — 132 с.

102. Лупин, С. А. Параллельная реализация алгоритмов дискретной оптимизации / С. А. Лупин, Ш. Тан, М. Х. Чжо // Современные информационные технологии и ИТ-образование. — 2012. — № 8. — С. 912—918.

103. Ураков, А. Р. Алгоритм решения динамической задачи поиска кратчайших расстояний в графе / А. Р. Ураков, . Т. В. Тимеряев // УБС. — 2017. — № 65. — С. 60—86.

104. Величко, А. С. Параллельные алгоритмы для задач условной оптимизации большой размерности с декомпозицией ограничений / А. С. Величко // УБС. — 2016. — № 62. — С. 60—74.

105. Тянь, Б. Балансировка нагрузки на основе оценок алгоритмической сложности подзадач / Б. Тянь, М. А. Посыпкин, И. Х. Сигал // Информационные технологии и вычислительные системы. — 2015. — № 1. — С. 10—18.

106. Третьяк, В. Ф. Алгоритм параллельных вычислений для решения задачи ЦЛП с БП / В. Ф. Третьяк, С. В. Листровой, С. В. Яблочков // 1нформацшш системи. — 1998. — № 3.

107. Третяк, В. Ф. Патент на полезную модель № 69487, Украина, МПК в06 Б15/00. Устройство для решения задач на графах / В. Ф. Третяк, Г. Д. Ю. — 2012. — Бюл. № 8.

108. Осиевский, С. В. Способ решения задачи параллельной обработки запросов к базам данных / С. В. Осиевский // Системи обробки шформацп. — 2002. — Вып. 21, № 5. — С. 197—204.

109. Рябухин, С. И. Применение сетей Петри для моделирования событийно-процесных цепей и построения структуры базы даных / С. И. Рябухин // Весник НГУ. Серия Информационные технологии. — 2013. — Том 1, выпуск 4. — С. 92—101.

110. Королев, Ю. И. Методы и программные средства моделирования сложных динамических систем на основе темпоральной модификации раскрашенных сетей Петри : Дис. ... канд. тех. наук: 05.13.11 / Ю. И. Королев. — Москва, 2015. — 145 с.

111. Фишер, А. В. Разработка методического аппарата системного анализа при использовании хронологической информации: Дис. ... канд. тех. наук: 05.13.01 / А. В. Фишер. — Краснодар, 2014. — 134 с.

112. Бабичев, С. Л. Статический анализ проблем синхронизации параллельных алгоритмов в вычислительных системах с общей памятью: Дис. ... канд. физ.-мат. наук: 05.13.18 / С. Л. Бабичев. — Москва, 2012. — 106 с.

Список сокращений и условных обозначений

ЗНП задача о наименьшем покрытии

ЗНР задача о наименьшем разбиении

РЗ размерность задачи

СВР среднее время решения

Шт штуки

АСУ автоматизированные системы управления ОУ объект управления

ОО объект обслуживания

ЦЛП целочисленное линейное программирование

БП булевые переменные

ПВС параллельные вычислительные системы

ДП динамическое программирование

ПАВ последовательный анализ вариантов ЯМД языка манипулирования данными СУБД Система управления базами данных

Словарь терминов

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

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

Анализ — метод научного исследования, состоящий в расчленении целого на составные элементы

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

Большие данные (Big Data) — информация, обработка и хранение которой сильно затруднены или невозможны в рамках одного вычислительного ресурса, представленного персональной рабочей станцией, сервером

Вертикальная фрагментация (vertical fragmentation) — назначение экземпляров различных частей одного типа в две или более среды базы данных

Горизонтальная фрагментация (horizontal fragmentation) — назначение различных множеств или различных типов экземпляров данных в две или более среды баз данных

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

Данные распределения (distribution data) — данные, которые определяют информацию о размещении, дублировании и фрагментации объектов данных в распределенной системе баз данных

Запрос — задание на поиск данных в базе данных, удовлетворяющих некоторым условиям, в том числе содержащим координаты искомых объектов (см. пространственный запрос)

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

Класс NP (от англ. non-deterministic polynomial)-множество алгоритмов, время работы которых сильно зависит от размера входных данных, но если предо ставить алгоритму некоторые дополнительные сведения (так называемых свидетелей решения), то он сможет достаточно быстро (за время, не превосходящее многочлена от размера данных) решить задачу

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

Оптимальное решение -решение, минимизирующее или максимизирующее некоторый показатель при заданной системе ограничений

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

Операция - совокупность действий, мероприятий, направленных на достижение некоторой цели

Показатель эффективности операции -мера степени соответствия реального результата операции требуемому

Параллельная обработка -в автоматизированных системах: одновременное выполнение нескольких программ или разных частей одной программы при работе с данными

Эффективность операции -степень соответствия реального .*зультата операции желаемому

Распределенная (децентрализованная) БД [distributed (decentralized) database] - 1) Назначение экземпляров данных базы данных в две или более среды базы данных; 2)совокупность баз данных, физически распределенная по взаимосвязанным ресурсам вычислительной сети и доступная для совместного использования в различных приложениях; 3) территориально распределенная совокупность локальных БД, объединенных согласованными принципами организации комплектования и эксплуатации, а также каналами связи, и доступная для совместного использования

Решение - выбор одной альтернативы из множества рассматриваемых альтернатив

Способ -действие или система действий, применяемых при исполнении какой-нибудь работы, при осуществлении чего-нибудь

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

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

Система управления базами данных, СУБД (data base management system, DBMS) — совокупность программных и языковых средств, обеспечивающих управление базами данных

Стратегия — любое правило, предписывающее определенные действия в каждой ситуации процесса принятия решения

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

Целевая функция — в экстремальных задачах функция, максимум или минимум которой необходимо найти

Фрагментация — назначение экземпляров данных базы данных в две или более среды базы данных

1.1 Схема управления базой данных [8]....................49

1.2 Схема прохождения запроса [21]......................54

1.3 Пример схем фрагментации [21]......................55

2.1 Граф Сд ...................................59

2.2 Геометрическая интерпретация графа Сд.................60

2.3 Стянутое дерево всех путей В графа в(У,Е)...............65

2.4 Стянутое дерево всех путей В графа в(У,Е), с применением процедуры А ................................. 66

2.5 Стянутое дерево путей В графа в(У,Е), с применением процедуры

А (случай б) ................................. 68

2.6 Блок схема работы алгоритма процедуры А ...............69

2.7 Схема алгоритма ПКГП1..........................72

2.8 Схема алгоритма ПКГП2..........................74

2.9 Исходный граф поиска кратчайших гамильтоновых пути [6]......75

2.10 Граф поиска кратчайшего гамильтонова пути с введением

фиктивной вершины [6] ........................... 76

2.11 Схема процедуры поиска точки входа в граф с использованием

анализа весовых характеристик ...................... 79

2.12 Схема работы алгоритма ПКГП3 с использованием анализа весовых характеристик графа - состояний.....................82

2.13 а) Граф в (графовое представление структуры вычислительного алгоритма); Графовое представление вычислительного алгоритма с разбиением на ранги б) дерево всех путей; в) стянутое дерево всех путей ..................................... 88

2.14 а) граф схема алгоритма вычислительного процесса; б) соответствующая ему матрица - смежности ............... 91

2.15 Стянутое дерево всех путей для графа представленного на рис. 2.14 . 91

2.16 Блок схема алгоритма параллельных вычислений............101

2.17 Архитектура ПВС систолического типа [107]...............104

2.18 Архитектура ПВС волнового типа [107]..................106

3.1 Алгоритм формирования графика реализации запросов и пользователей транзакций .........................112

3.2 Модель реализации операции выборки..................114

3.3 Модель реализации операции выборки..................114

3.4 Модель реализации операции выборки .................. 115

3.5 Модель реализации операции выборки [108]...............116

3.6 Модель реализации операции выборки [108]...............117

3.7 График зависимости числа элементарных операций от размерности задачи (зона 1)................................123

3.8 График зависимости числа элементарных операций от размерности задачи (зона 2)................................124

3.9 График зависимости числа элементарных операций от размерности задачи (зона 3)................................125

3.10 График зависимости числа обработанных векторов от размерности задачи (зона 1) ................................ 126

3.11 График зависимости числа обработанных векторов от размерности задачи (зона 2) ................................ 126

3.12 Зависимость погрешности от размерности задачи............128

3.13 Зависимость погрешности от размерности решаемой задачи для алгоритма ПКГП3 .............................. 129

3.14 График вероятности своевременного решения задачи при Тзад=3 мин 130

3.15 График вероятности своевременного решения задачи при Тзад=10 мин 131

3.16 График вероятности своевременного решения задачи при Тзад=30 мин 132

3.17 График вероятности своевременного решения задачи при Тзад=30

мин алгоритмом ПКГП3 .......................... 133

3.18 График зависимости числа неточных решений от размерности

задачи, %...................................134

3.19 График зависимости числа неточных решений от общего числа реализаций, %................................134

3.20 Графики оценки показателя эффективности W (ш) и вероятности поступления на обработку суммарного числа запросов пользователей и транзакций ........................ 135

3.21 Зависимость погрешности и ее характеристик от размерности задачи . 138

3.22 График зависимости показателя вероятности своевременного

решения задачи от ее размерности.....................140

1 Влияние технического совершенствования ЭВМ на полиномиальные

- и экспоненциальные алгоритмы.....................35

2 Максимальная размерность задач, разрешимых за данное - время . . 36

3 Матрица достижимости между операциями запроса после

процедуры декомпозиции .......................... 76

4 Матрица условных индексов ........................ 77

5 Порядок вычислений............................105

6 Численные значения математических ожиданий числа обработанных векторов ................................... 127

7 Пример проблемы потерянного обновления ...............164

8 Пример проблемы зависимости от нефиксированных результатов . . .164

9 Пример проблемы несогласованной обработки..............165

10 Исходные данные для решения задачи формирования графа допустимых переходов...........................166

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

Таблица 7 — Пример проблемы потерянного обновления

время Транзакция Т1 Транзакция Т2 Поле Ъе1ж

Ъ begin_transaction 100

t2 begin_transaction геаё(Ъе1ж) 100

tз Яеаё(Ъе1ж) Ъе1ж =Ъе1ж + 100 100

Ъе1ж =Ъе1ж - 10 write (Ъе1ж) 200

t5 write (Ъе1ж) commit 90

t6 commit 90

Таблица 8 — Пример проблемы зависимости от нефиксированных результатов

время Транзакция Т1 Транзакция Т2 Поле Ъе1ж

Ъ begin_transaction 100

t2 read(be1ж) 100

tз Ъе1ж =Ъе1ж + 100 100

14 begin_transaction write (Ъе1ж) 200

t5 read(be1ж) 200

Ъе1ж =Ъе1ж - 10 ro11back 100

write (Ъе1ж) 190

и commit 190

Таблица 9 — Пример проблемы несогласованной обработки

время Транзакция Т1 Транзакция Т2 Поле Ъе1ж Поле Ъе1у Поле Ъе1^ Поле sum

ъ begin_transaction 100 50 25

t2 begin_transaction sum=0 100 50 25 0

tз геаё(Ъе1ж) read(be1ж) 100 50 25 0

t4 Ъе1ж =Ъе1ж - 10 sum=sum+ Ъе1ж 100 50 25 100

t5 write (Ъе1ж) read(be1y) 90 50 25 100

t6 геаё(Ъе1^) sum=sum+ Ъе1у 90 50 25 150

t7 Ъе1^ =Ъе1^ + 10 90 50 25 150

t8 write (Ъе1^) 90 50 35 150

19 commit read(be1z) 90 50 35 150

t10 sum=sum+ Ъе1^ 90 50 35 185

1ц commit 90 50 35 185

Исходные данные для решения задачи формирования графа допустимых

переходов

Таблица 10 — Исходные данные для решения задачи формирования графа допустимых переходов

Наименование Обозначение

Характеристики множества групповых информационных элементов Рг = К} , (г = 1,1о)

Вектора длин групп 9 = Ш

Вектора количества экземпляров в группах Матрица времен получения информации, содержащейся в группах, по запросам пользователей Матрица семантической смежности для множества групповых информационных элементов X = {Хг} Т = ||т^|| , где тк% - максимально допустимое время получения информации г-й группы по запросу к-го пользователя Аг = ЦогЦ, где а^=1, если существует семантическая связь между г-й и у'-й группами, аг^-=0 -в противном случае

Характеристики множества детерминированных запросов пользователей = {Зр}, (р = 1,Р0)

Матрица использования групп информационных элементов при выполнении запросов W3 = ||©^||, где ©рт=1, если р-й запрос использует в процессе выполнения г'-й групповой информационный элемент, ©^=0 - в противном случае

Матрица частот использования запросов пользователями на заданном интервале времени Матрица средних значений числа анализируемых экземпляров групп при выполнении запросов Матрица средних значений числа выбираемых экземпляров групп в соответствии с условиями выполнения запроса ЛЗ = , где Ефк - частота использования p-го запроса ^м пользователем V3 = где ^З,- среднее количество групповых информационных элементов, выбираемых в результате выполнения p-го запроса Г II 3 II 3 Гз = УтЗ^У, где у^-среднее количество анализируемых экземпляров г'-й группы при выполнениир-го запроса

Характеристики множества заданий пользователей на корректировку и обновление информации в РБД К = {к8}, (й = 1,50)

Матрица использования групп информационных элементов при выполнении заданий на корректировку Матрица частот использования заданий на корректировку пользователями на заданном интервале времени Матрица средних значений числа корректируемых экземпляров групп Wк = ||©к||, где = 1, если 5-е задание на корректировку изменяет или удаляет г'-й групповой информационный элемент, = 0 - в противном случае Лк = Ц^Ц , где - частота использования 5-го задания на корректировку к-м пользователем Гк = Цу^Ц , где у к - среднее значение количества корректируемых экземпляров '-й группы при выполнении 5-й корректировки

Характеристики множества пользователей и = {ик}, (к = 1,^о)

Матрица прикрепления пользова- К = \\Vkr|| , где Укг = 1, если к-й

телей к узлам ВС пользователь прикреплен к г-му

узлу ВС, укг =0 - в противном

случае

ФЗ = З Щр , где у3кр = 1, ес-

Матрица использования запро- ли к-й пользователь использует

сов пользователями РБД р-й запрос = 0 - в противном

случае

ф^ = ^фЦ ' где фь = 1

если

если к-й пользователь использует

Матрица использования заданий Б-е задание на корректировку,

на корректировку пользователями ф1 = 0 - в противном случае

РБД

Cвидетельство о государственной регистрации программы на ЭВМ

Приложение Г Акты о внедрении

«Утверждаю»

Генеральный директор ООО «РТЛС исследования и разработки»

_, _Табаровский О.И.

2019 г.

АКТ

внедрения результатов диссертационной работы Фильгуса Дмитрия Игоревича, представленной на соискание учёной степени кандидата технических наук

г. Москва

- ; 2019 г

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

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

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

Генеральный директор

Табаровский О.И.

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное учреждение .высшего образования «МИРЭА - Российский технологический унипершалч».,

КЛ». о г Л УЛь.

РТУ МИРЭА

Директор институ$|

«УТВЕРЖДАЮ»

Акт внедрения в учебный процесс материалов дпесер^^ионЕ.

[ работы

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

Настоящим актом подтверждается, что основные положения и результаты диссертационного исследования внедрены в учебный процесс кафедры «Инструментального и прикладного программного обеспечения» федерального государственного бюджетного образовательного учреждения высшего образования "МИРЭА - Российский технологический университет".

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

Зав. кафедрой инструментального и прикладного программного обеспечения, К.Т.Н., Проф

С

Мордвинов В.А.