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

• Громей Дмитрий Дмитриевич
• кандидат наук
• 2020

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

ВВЕДЕНИЕ

Глава 1. Анализ существующих подходов к управлению схемой базы данных в СУБД реляционного типа при обработке конкурентных запросов

1.1 Процесс обработки запросов в реляционных СУБД

1.2 Особенности параллельной обработки запросов

1.2.1 Конкурентный доступ к данным. Определение конкурентных запросов

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

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

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

1.3.1 Особенности экспертного подхода к решению задачи оптимизации физической структуры базы данных

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

1.4 Выводы по главе и постановка задачи исследования

Глава 2. Теоретико-множественное описание процесса выполнения потока запросов в СУБД реляционного типа

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

2.2 Разработка теоретико-множественного описания процесса выполнения потока запросов

2.2.1 Определение закона композиции на множествах элементов процесса выполнения потока запросов

2.2.2 Теоретико-множественное описание конкурентных запросов

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

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

Глава 3. Разработка параметрической модели конкурентного доступа запросов

3.1 Особенности моделирования доли последовательных расчетов и требования к модели параллельных вычислений в реляционных СУБД

3.2 Исследование подходов к восстановлению регрессии методами машинного обучения

3.3 Метод получения параметрической модели конкурентного доступа запросов к данным в неоднородной памяти реляционной СУБД

3.4 Проверка адекватности разработанной модели

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

Глава 4. Разработка алгоритма ранжирования объектов логической схемы данных

4.1 Подходы к формированию управляющего воздействия на распределение данных в реляционных СУБД

4.2 Алгоритм ранжирования объектов логической схемы данных по предикатам запросов

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

4.4 Оценка корректности разработанных алгоритмов

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

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

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

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

5.2 Структура комплекса для проведения экспериментов

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

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

Заключение

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

Список использованных источников

ПРИЛОЖЕНИЕ

ПРИЛОЖЕНИЕ

ПРИЛОЖЕНИЕ

ПРИЛОЖЕНИЕ

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

ВВЕДЕНИЕ

Актуальность темы. Информатизация общества и научно-технический прогресс порождают новые условия функционирования систем управления базами данных (СУБД), такие как рост объема обрабатываемых данных, увеличение разнообразия и интенсивности запросов. Решение этих проблем лежит в области архитектуры параллельных вычислений, обеспечивающей масштабирование информационной инфраструктуры в соответствии с возникающими потребностями.

При этом эффективное применение СУБД требует целенаправленного управления схемой базы данных, её адаптации к потоку запросов, особенностям вычислительной системы и набору данных. Сложность выбора управляющего воздействия связана с многоэтапностью процесса обработки потока запросов. Особым условием такого процесса является обработка параллельных запросов, конкурирующих за доступ к одним и тем же данным. Поскольку специальное программное обеспечение (ПО) для работы с данными использует объекты логической схемы данных (ЛГСД), задача управления схемой базы данных, с учетом изменения ее состояния и нагрузки, порождаемой потоком запросов, в настоящее время решается методами экспертного аудита или с использованием специализированного ПО - анализаторов состояния базы данных, которое формирует рекомендации по изменению структуры базы данных.

Большой вклад в совершенствование специального математического и программного обеспечения подобных анализаторов внесли М. Волкер, Ш. Ломана, Ш. Яо, С. Чаудхури, Д.Л. Зверев, Л.Е. Борчук, Н.А. Гребников, В.М. Постников, Р.А. Бачацкий. Однако, в большинстве решений, модели, применяемые в них для оценки «стоимости» классов запросов, ориентируются на решение задач блокировки и синхронизации и игнорируют взаимное влияние параллельно выполняемых запросов. При таком подходе, сформированная структура базы данных является локально оптимальным решением и требует проведения дополнительного экспертного аудита.

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

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

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

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

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

2. Формализовать процесс выполнения потока запросов в СУБД реляционного типа в виде теоретико-множественного описания, отражающего закономерности между временем выполнения запроса и условиями доступа к данным этого запроса и конкурентно выполняемых с ним.

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

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

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

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

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

типа.

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

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

Тематика работы соответствует следующим пунктам паспорта специальности 05.13.11 «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»: п.3 «Модели, методы, алгоритмы, языки и программные инструменты для организации взаимодействия программ и программных систем»; п.4. «Системы управления базами данных и знаний»; п.8. «Модели и методы создания программ и программных систем для параллельной и распределенной обработки данных, языки и инструментальные средства параллельного программирования».

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

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

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

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

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

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

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

Положения, выносимые на защиту:

1. Теоретико-множественное описание процесса выполнения потока запросов обеспечивает получение зависимости оценки времени выполнения от условий доступа к данным конкурентно выполняемых запросов.

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

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

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

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

Результаты внедрения. Основные результаты работы, включая реализованное специальное программное обеспечение, внедрены в АО «Рекурсив» с целью совершенствования работы имеющихся баз данных.

Апробация результатов диссертационного исследования. Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях: XX International Open Conference «Modern informatization problems in simulation and social technologies» (Yelm, WA, USA, 2015), 11 Межведомственной конференции «Научно-техническое и информационное обеспечение деятельности спецслужб» (ИКСИ, Москва, 2016 г.); Х Всероссийской межведомственной научной конференции «Актуальные направления развития систем охраны, специальной связи и информации для нужд государственного управления» (Академия ФСО России, Орёл, 2017 г.), XXIV-th International Open Science Conference «Modern informatization problems in the technological and telecommunication systems analysis and synthesis» (Yelm, WA, USA, 2019).

Публикации. По результатам диссертационного исследования опубликовано 9 печатных работ, в т.ч. 2 статьи в изданиях, рекомендованных ВАК РФ, патент на изобретение, свидетельство о государственной регистрации программы, а также статья в издании, индексируемом в Scopus. В работах,

опубликованных в соавторстве, лично автором получены следующие результаты: [31,122] - теоретико-множественное описание процесса выполнения потока запросов; [55] - алгоритм ранжирования объектов логической схемы данных по предикатам запросов и алгоритм управления схемой реляционных баз данных; [123] - реализация компонент программного комплекса по разбору текстов запросов и расчету параметрической модели; [129,130] - формальное описание на множествах операций доступа к атомарным блокам данных параллельно выполняемых запросов; [138] - формализация структуры взаимодействия программных модулей системы управления схемой реляционной базы данных.

Объем и структура работы. Диссертация состоит из введения, пяти глав, заключения и приложений. Работа изложена на 1 31 странице машинописного текста, включая 25 рисунков, 5 таблиц и список литературы из 1 51 наименования.

ГЛАВА 1. АНАЛИЗ СУЩЕСТВУЮЩИХ ПОДХОДОВ К УПРАВЛЕНИЮ СХЕМОЙ БАЗЫ ДАННЫХ В СУБД РЕЛЯЦИОННОГО ТИПА ПРИ ОБРАБОТКЕ КОНКУРЕНТНЫХ ЗАПРОСОВ

Одной из архитектурных особенностей современных информационных систем (ИС) корпоративного сегмента является наличие развитой системы хранения данных (СХД), решающей комплекс задач хранения и обработки данных, а также управления этими процессами. В подавляющем большинстве, СХД таких ИС базируются на СУБД реляционного типа. При этом, практика эксплуатации подобных ИС в корпоративном сегменте показывает, что одним из основных показателей, характеризующих эффективность доступа пользователей к хранящейся информации, является время выполнения запросов сервером базы данных [1,2]. Увеличение значения этого показателя может привести к росту очереди запросов или даже к отказу в обслуживании.

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

Задачи разработки масштабируемых ИС, поддерживающих модели параллельных вычислений и базирующихся на реляционных СУБД, связаны, в первую очередь, с решением, как проблемы высокоскоростного доступа к общей памяти, поддерживаемой СХД ИС [5], так реализации распределенных транзакций [6,7], соответствующих требованиям ACID [3,4]. При этом, как отмечается в [8,9], реляционные СУБД являются системами с глобальной транзакционной целостностью, а значит наибольшая эффективность их горизонтального масштабирования, обеспечивающая минимизацию временной задержки синхронизации данных между узлами распределенной ИС, может быть

достигнута, как в случае многопроцессорной и многопоточной обработки данных, так и при эффективном распределении данных в узлах ИС. Соответственно, решение этих проблем хотя и находится в области классических задач, связанных с масштабированием систем параллельных вычислений [10,11,12], обладает рядом особенностей, присущих реляционным СУБД.

1.1 Процесс обработки запросов в реляционных СУБД

Анализ технической документации современных реляционных СУБД [13, 25, 142, 143] позволил определить:

- основные этапы обработки запросов;

- функциональные модули, участвующие в каждом из этапов;

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

В общем виде процесс обработки запросов в реляционных СУБД представлен на рисунке 1.1.

Рис. 1.1 Обобщенная схема процесса обработки запросов в реляционных

СУБД

Из рисунка 1.1 видно, запрос Q проходит несколько этапов обработки, основными из которых являются: синтаксический разбор запроса и его представление в виде абстрактного синтаксического дерева (Abstract Syntax Tree, AST), выбор плана выполнения запроса P, и его исполнение ядром СУБД [13,23]. Фактически, для исполнения запроса ядром СУБД, дерево AST транслируется в упорядоченную последовательность элементарных операций над множествами данных А. Это обусловлено тем, что в реляционной алгебре запрос Q определен над некоторыми множествами и задает целевые множества и операции над ними. При этом возможна реализация нескольких способов упорядочивания обрабатываемых множеств данных относительно дерева AST запроса Q, приводящих к формированию не одного, а множества планов выполнения запроса Р.

Рассмотрим это на примере следующего SQL-запроса (рисунок 1.2).

SELECT host.unit, host.name, doc.phone, doc.area FROM host INNER JOIN doc ON doc.id = host.id WHERE host.unit LIKE '1%' OR doc.area LIKE '1 этаж%';

Рис. 1.2 Пример SQL-запроса, демонстрирующий влияние порядка операторов в запросе на время его исполнения

Из рисунка 1 .2 видно, что операторы выборки могут быть упорядочены двумя способами:

1. Выбрать элементы множества «host».

2. Выбрать элементы множества «doc».

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

Взаимосвязь между подмножествами, над которыми определяется запрос ( и временем его выполнения приводит к тому, что на практике, для снижения размерности множества элементарных операций доступа к памяти А (рисунок 1.1), используются дополнительные сущности, увеличивающие кардинальность выборки - число отобранных записей [24,122]. К ним, в первую очередь, относится совокупность индексов, сегментов, реплик, материализованных представлений и иных объектов базы данных [25]. Эти сущности, определяющие распределение данных, позволяют уменьшать число объектов базы данных, к которым фактически осуществлен доступ, тем самым уменьшая время выполнения запроса. Например, сегментирование таблиц по ключу выборки позволяет уменьшить число строк, хранимых в памяти, к которым для проверки заданного условия необходим доступ [26, 28]. Введение подобных сущностей разграничивает реляционное представление данных в запросах и фактическое их представление в памяти ЭВМ.

Отрицательной стороной их использования является кратное увеличение числа планов выполнения запроса Р [27,122], а также увеличение числа объектов в области памяти ЭВМ, выделенной под хранение данных. Это означает, что при неоптимальном выборе распределения данных, особенно в условиях стохастического доступа к ним, суммарное время выполнения запросов существенно увеличивается.

Рассмотренные выше особенности наибольшее влияние оказывают при реализации параллельной обработки потока запросов.

1.2 Особенности параллельной обработки запросов

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

определяет особенность организации памяти ЭВМ, используемой ядром СУБД, а именно ее деление на две части:

1. Память, ассоциированную с конкретным рабочим потоком [10].

2. Память, совместно используемую несколькими рабочими потоками.

Память рабочего потока служит для размещения в ней [13,14]:

- самого запроса;

- промежуточных данных, используемых в процессе его обработки;

- служебных структур, необходимых для его обработки.

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

1.2.1 Конкурентный доступ к данным. Определение конкурентных запросов

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

Наиболее известным эффектом, возникающим вследствие функционирования конкурентных запросов, является состояние гонок (race conditions). Применительно к реляционным СУБД оно проявляется в таких

составных действиях, как «прочитай-измени-запиши» (геа^тоШ^у^гие) и «проверь-затем-действуй» (скеск^кеп-аМ) [25, 144].

Рис. 1.3 Пример возникновения конкурентного доступа между запросами

На рисунке 1.4 представлена условная временная диаграмма выполнения рабочих потоков трех запросов, отражающая возникновение периодов конкуренции. Периоды времени выполнения операций извлечения данных обозначены, как «ИД», периоды подготовки запроса обозначены, как «П», в периоды выполнения запроса обозначены, как «В».

П

ИД

ИД

Период конкуренции 1

ИД П ш ИД ИД П ш

1 1 1

П ШШШШ ИД П шиш

ИД

Поток запроса 1 Поток запроса 2 Поток запроса 3

Период конкуренции 2

Рис. 1.4 Диаграмма выполнения трех потоков запросов, отражающая возникновение периодов конкуренции

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

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

Решению проблемы конкурентного доступа к базам данных посвящены работы [15,16,17,18,19,20].

Наличие глобальной транзакционной целостности в соответствии с требованиями ACID определяет необходимость согласования доступа к совместно используемым данным. Чаще всего такое согласование может выполняется с помощью низкоуровневых примитивов синхронизации, предоставляемых вычислительной платформой, средствами программирования и СУБД. В общем случае в [30] выделяют два подхода реализации взаимодействия критических секций параллельно выполняемых процессов:

1. Основанный разделяемой памяти.

2. Основанный на передаче сообщений.

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

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

доступе к общему блоку памяти отличается от скорости доступа при последовательном выполнении одного рабочего потока, вследствие внутренних операций вычислительной системы, направленных на поддержание заявленной модели памяти. Указанные ограничения конкурентного доступа при использовании механизма разделяемой памяти рассматривается в работах [9,13,21,27,32,33,34].

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

Рис. 1.5 Зависимость времени обработки запросов с использованием механизма разделяемой памяти СУБД от количества параллельных рабочих потоков,

конкурирующих за доступ к памяти

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

зависимости от типа операции (чтение/запись) время обработки запроса существенно снижается.

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

Вне зависимости от рассмотренных выше механизмов согласования конкурентного доступа к данным, существует объективная причина увеличения времени обработки запросов, связанная с оценкой ускорения масштабирования параллельных вычислений (scaled speedup) Sn, выражаемой в законах Амдала-Уэра и Густавсона [22]. В общем виде эта оценка представлена выражением 1.1.

0 p • n + 5 (1.1)

Sn = —-= n + (1 - n)s,

p = s

где

я - доля последовательных расчетов;

р - доля параллельных расчетов;

п - количество обработчиков, обслуживающих рабочие потоки.

Эта оценка основана на предположении о неизбежном возникновении в параллельных вычислениях доли последовательных расчетов я, определяемой временем, затраченным на обеспечение совместного доступа к общим данным. Особенностью величины я при обработке конкурентных запросов в СУБД является нелинейный характер её влияния на суммарное время обработки всех запросов пропорционально числу рабочих потоков (величина п). При этом оценка 8п будет определяться некоторой нелинейной функцией, а при достижении некоторого предела величины я начинает существенно влиять на общую производительность СУБД [21,138]. Возникновение подобной проблемы рассматривается в [49,50,51,57].

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

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

Эта цель может быть достигнута двумя способами:

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

2. Использованием встроенных в СУБД объектов для организации эффективной адресации и расположения данных в памяти [35,122].

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

Второй способ ориентирован на использование таких объектов СУБД, как индексы, сегменты и реплики [13,23,138]. Индексы для предикатов запросов, с преимущественным доступом для чтения, позволяют ускорить операции чтения данных. Сегментирование таблиц по некоторому условию позволяет разбить один общий объект логической схемы базы данных на несколько частных, из которых предикату запросу будет соответствовать только один или несколько, что позволяет уменьшить число операций рабочих потоков над одной и той же областью памяти. Реплики можно рассматривать как один из основных способов обеспечения эффективной работы федеративных баз данных за счет дублирования частей общего состояния данных на множестве узлов и переадресацией поступающего запроса на один из них. В изолированных базах данных реплики в виде материализованных представлений могут обеспечивать денормализацию данных для сложных запросов, оперирующих сразу множеством таблиц.

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

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

2. Whalen, E. Oracle Performance Tuning and Optimization / Whalen E. -Sams Publishing, 2003. - 670 p.

3. Gray, J. The Transaction Concept: Virtues and Limitations / Gray Jim. Proceedings of the 7th International Conference on Very Large Databases: pages 144154, 1981.

4. Дейт, К. Дж. Введение в системы баз данных, 8-е издание / К. Дж. Дейт: пер. с англ. - М.: Издательский дом «Вильямс», 2005. - 1327 с.

5. Murali, V. Oracle RAC Perfomance Diagnostics and Tuning / Murali Vallath - Apress, 2014. - 712 p.

6. Величко, С. В. Современные СУБД для создания единой информационной среды в больших информационных системах. / С.В. Величко, Е.В. Межов // Вестник воронежского государственного технического университета. - 2003. - № 3. - С.68-73.

7. Lohman, G.M. Daniels, D. Haas, L.M. Kistler, R. Selinger, P.G. Optimization of Nested Queries in a Distributed Relational Database // Proc. 10th Int. Conf Very Large Data Bases, Singapore, Aug. 27-31, 1984. - New York. - 1984. -C.403-415.

8. Диго, С. М. Базы данных: проектирование и использование. Учебник / С. М. Диго. - М.: Финансы и статистика, 2005. - 171 с.

9. Bodorik, P. Correcting execution of distributed queries / P. Bodorik, J. Pyra, J. S. Riordon // Proceedings of the second international symposium on Databases in parallel and distributed systems, p. 192-201, July 02-04, 1990, Dublin, Ireland.

10. Воеводин, В.В. Параллельные вычисления / В.В. Воеводин, Вл.В. Воеводин. - СПб.: БХВ-Петербург, 2002. - 520 с.

11. Грегори, Р. Эндрюс Основы многопоточного, параллельного и распределённого программирования. - М.: Вильямс, 2003. - 512 с.

12. Gillenson, M. L. Fundamentals of Database Management Systems 2nd Edition. Wiley, 2011.

13. Кайт, Т. Oracle для профессионалов: архитектура, методики программирования и особенности версий 9i, 10g и 11g. 2-е издание / Том Кайт, пер. с англ. - М.: Вильямс, 2013. - 848 с.

14. Диго, С. М. Базы данных: проектирование и создание. Учебно-методический комплекс / М. Ф. Гарсия, Дж. Рединг, Э. Уолен, С. А. ДеЛюк. пер. с англ. - М: Эком, 2008. - 976 с.

15. Bruno, N. Configuration-parametric query optimization for physical design tuning / Nicolas Bruno, Rimma V. Nehme // Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008. Vancouver, Canada.

16. Yao, S.B. An Attribute Based Model for Database Access Cost Analyses // ACM Trans. Database Syst. - 1977. - 2. - № 1. - pp. 45-67.

17. Yao, S.B. Approximating Block Acess in Database Organizations // Commun. ACM. - 1977. - 20. - № 4. - pp. 260-261.

18. Wong, E Decomposition - A Strategy for Query Processing / Wong Eugene, Youssefi, K. // ACM Transactions on Database Systems, 3 (September) 1976.

19. Bing, Yao S. Optimization of Query Evaluation Algorithms // ACM TODS. - 1979. - 4. - № 2.

20. Bobby, L. Practical Oracle Database Appliance / Bobby L. Curtis, Fuad Arshad, Erik Benner, Maris Elsins // Apress; 2014, 272 p.

21. Agrawal, D. Database scalability, elasticity, and autonomy in the cloud. DASFAA, pp. 2-15, 2011.

22. John, L. Gustafson Reevaluating Amdahl's Law. Communications of the ACM 31(5), 1988. pp. 532-533.

23. Хендерсон, К. Microsoft SQL Server: структура и реализация. Профессиональное руководство. / Кен Хендерсон - пер. с англ. // М.: Вильямс, 2005. - 1056 с.

24. Christodoulakis, S. Estimating Record Selectivities // Inf. Syst. - 1983.8. - № 2. - C. 105-115.

25. Kyte, T. Oracle Database Architecture / Thomas Kyte, Darl Kuhn // Apress; 3rd ed. 2014. - 824 c.

26. DeWitt, D.J. Implementation Techniques for Main Memory Database Systems / D.J. DeWitt, R.H. Katz, F. Olken, L.D. Shapiro, M.R. Stonebraker, D. Wood // Proc. ACM SIGMOD Int. Conf. Manag. Data, Boston, Mass., June 18-21, 1984. New York, 1984, pp. 1-8.

27. Hasler, T. Oracle SQL. Optimization, Deployment, and Statistics / Tony Hasler // Apress; 2014. - 571 c.

28. Cornell, D.W. A Vertical Partitioning Algorithm for Relational Databases / Cornell D.W. Yu P.S. // 3rd Int. Conf. Data Eng., Los Angeles, Ca, Febr. 3-5, 1987. -Proc. Washington, D.C. -1987. - C.30-35.

29. Kim, W. Query Processing in Database Systems / Kim W., Reiner D.S., Batory D.S. Query // New York, N.Y.: Springer-Veiiag. - 1985.

30. Intel 64 and IA - 32 Architectures Software Developer's Manual Volume 3A: System Programming Guide, Part 1 [электронный ресурс]. URL: http: //www.intel .com/content/dam/www/public/us/en/documents/manual s/64-ia-32-architectures-software-developer-vol-3a-part-1 -manual .pdf.

31. Громей, Д.Д. Математическое обеспечения поддержки процесса управления схемой реляционной базы данных в задачах горизонтального масштабирования / Д.Д. Громей, Е.В. Лебеденко // Моделирование, оптимизация и информационные технологии. - 2019. - T. 7. - №2/25. С. 65 79, №2 (25), 2019. -Режим доступа: http://moit.vivt.ru/?p=9174

32. Benoit, D. Automatic Diagnosis of Performance Problems in Database Management Systems / Darcy G. Benoit // Proceedings of the Second International Conference on Automatic Computing, p.326-327, June 13-16, 2005

33. Mozafari, B. Performance and resource modeling in highly-concurrent oltp workloads. SIGMOD, pages 301-312, 2013.

34. Cheng, J.M. IBM Database 2 Performance: Design, Implementation, and Tuning / Cheng J.M., Loosley C.R., Shibamiya A., Worthington P.S. // IBM Syst. J.-1984.- 23. - № 2. -C.189-210.

35. Коннолли, Т. Базы данных. Проектирование, реализация и сопровождение. Теория и практика 3-е изд. / Коннолли Томас, Бегг Каролин. пер. с англ. - М.: «Вильямс», 2003.

36. Garcia-Arellano, C. Adaptive self-tuning memory in DB2. / C. Garcia-Arellano, J. Storm // International Conference on Very Large Data Bases, pages 10811092, 2006.

37. Zilio, D. C. DB2 design advisor: integrated automatic physical database design / D. C. Zilio, J. Rao // International Conference on Very Large Data Bases, pages 1087-1097, 2004.

38. Kwan, E. Automatic configuration for IBM DB2 universal database / Kwan E., Lightstone S. // Technical report, IBM, jan 2002.

39. Narayanan, D. Continuous resource monitoring for self-predicting DBMS / D. Narayanan, E. Thereska, A. Ailamaki // MASC0TS'05, pages 239-248.

40. Chaudhuri, S. Self-Tuning Database Systems: A Decade of Progress / Surajit Chaudhuri, Vivek Narasayya // Proceedings of the Second International Conference on Automatic Computing, p. 326-327, June 13-16, 2005.

41. Chaudhuri, S. Self-tuning database systems: a decade of progress / Chaudhuri S. and Narasayya V. // International Conference on Very Large Data Bases, pages 3-14, 2007.

42. Cecchet, E. Dolly: Virtualization-driven database provisioning for the cloud / Cecchet E., Singh R. // VEE' 11, pages 51-62, 2011.

43. Das, S. Elastras: An elastic, scalable, and self-managing transactional database for the cloud. ACM TDS, 38(1):5:1-5:45, 2013.

44. Valentin, G. DB2 advisor: an optimizer smartenough to recommend its own indexes / Valentin G., Zuliani M. // ICDE, pages 101-110, 2000.

45. Markl, V. LEO: An autonomic query optimizer for DB2 / V. Markl, G. M. Lohman, V. Raman // IBM Systems Journal, v.42 n.l, p.98-106, January 2003.

46. Stillger, M. LEO - DB2's LEarning Optimizer / Michael Stillger, Guy M. Lohman, Volker Markl, Mokhtar Kandil // Proceedings of the 27th International Conference on Very Large Data Bases, p. 19-28, September 11-14, 2001.

47. Zilio, S. DB2 Design Advisor: Integrated Automatic Physical Database Design / Zilio et al. // In Proceedings of the International Conference on Very Large Data Bases, Toronto, Canada, 2004.

48. Борчук, Л.Е. Асимптотическая модель затрат ресурсов вычислительной системы на выполнение реляционного запроса в РСУБД System R / Л.Е. Борчук // Кибернетика и высокие технологии XXI века С&Т 2006: Материалы 7-ой международной научно-технической конференции. - Воронеж: ВГУ, 2006. - С. 363-373.

49. Борчук, Л.Е. Математическая формализация глобального плана выполнения запросов реляционной СУБД / Л.Е. Борчук // Вестник ЧГУ. -Череповец, 2004. - С. 84-89.

50. Борчук, Л.Е. Проблемы моделирования поведения реляционных СУБД на конечном поле запросов / Л.Е. Борчук // Информационные технологии в производственных, социальных и экономических процессах (ИНФОТЕХ-2004): Сборник трудов участников четвертой международной научно-технической конференции. - Череповец, 2004. - С. 120-122.

51. Chacravarthy, U.S. Query Optimization: Additional Constraints / Chacravarthy U.S., Grant J., Minker Semantic J. // Proc. 1st Int. Conf. Expert Database Syst., Charleston, S.C., Apr. 1986. - New York - 1986. - C.259-270.

52. Борчук, Л.Е. Учитываемые параметры математической модели семейства SQL - запросов на примере РСУБД Oracle / Л.Е. Борчук // Системный анализ в проектировании и управлении: Труды VII международной научно -технической конференции. - СПб: Издательство «Нестор», 2004. - С. 139-141.

53. Шнайдср, Р. Д. Microsoft SQL Server. Проектирование высокопроизводительных баз данных / Роберт Д. Шнайдер. пер. с англ. - М: Лори, 1998. - 366 с.

54. Ma, L. Query-based Workload Forecasting for Self-Driving Database Management Systems / Ma L., Aken D. V., Hefny A., Mezerhane G., Pavlo A., Gordon G. J. // Proceedings of the 2018 ACM International Conference on Management of Data, 2018.

55. Громей, Д.Д. Алгоритмы управления логической структурой базы данных с использованием параметрической модели конкурентного доступа запросов, основанной на методе случайного леса / Д.Д. Громей // Computational Nanotechnology, Vol. 6, №2, 2019. - С. 41 47.

56. Зверев, Д.Л. Анализ времени выполнения запросов и избыточности данных при проведении оптимизации на стыке баз данных и югиентских приложений / Д.Л. Зверев // Седьмая научная сессия аспирантов ГУАП: Сб. докл.: В 2 ч. Ч I. Технические науки. - СПб.: СПбГУАП. - 2004. - С. 319-322.

57. Зверев, Д.Л. Исследование профилей параллельных вычислений как случайных функций / Д.Л. Зверев // Третья международная молодежная школа-семинар БИКАМП-01 - Сб. докл. - СПб.: СПбГУАП. - 2001. - С. 150-153.

58. Сукач, Е.И. Определение характеристик распределенной базы данных с помощью имитационного моделирования / Сукач Е.И., Еськова О.И., Каморникова Т.Я. // Изд. гомор. унив. - 2002. - № 6. - С.110-112.

59. Воронцов, К. В. Обзор современных исследований по проблеме качества обучения алгоритмов // Таврический вестник информатики и математики. - 2004. - № 1. - С. 5-24.

60. Jain, A. K. Statistical pattern recognition: A review / Jain A. K., Duin R. P. W., Mao J. // IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000.- Vol. 22, no. 1.- Pp. 4-37.

61. Kanevskiy, D. Y. Cooperative coevolutionary ensemble learning / Kanevskiy D. Y., Vorontsov K. V. // Multiple Classifier Systems: 7th International Workshop, Prague, Czech Republic, May 23-25, 2007. Lecture Notes in Computer Science. Springer-Verlag, 2007. - Pp. 469-478.

62. Tresp, V. Committee machines // Handbook for Neural Network Signal Processing / Ed. by Y. H. Hu, J.-N. Hwang. - CRC Press, 2001.

63. Загоруйко, Н. Г. Прикладные методы анализа данных и знаний. -Новосибирск: ИМ СО РАН, 1999. - 270 с.

64. Friedman, J. H. Stochastic gradient boosting / Jerome H. Friedman // Computational Statistics and Data Analysis - Nonlinear methods and data mining, Volume 38 Issue 4, 28 February 2002. С. 367 - 378.

65. Mason, L. Boosting algorithms as gradient descent / Mason L., Baxter J., Bartlett P., Frean M. // Proceedings of the 1999 conference on Advances in Neural Information Processing Systems 12. Denver, Co - MIT Press, 1999. С. 512-518.

66. Culp, M. Ada: an R Package for Stochastic Boosting / Culp Mark, Johnson Kjell, Michailidis George. // Journal of Statistical Software American Statistical Association, Volume VV, Issue II. - 2006.

67. Журавлёв, Ю. И. Экстремальные алгоритмы в математических моделях для задач распознавания и классификации // Доклады АН СССР. Математика. - 1976. - Т. 231, № 3.

68. Mason, L. Margins and Combined Classifiers: Ph.D. thesis / Australian National University. - 1999. - 134 c.

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

70. Skurichina, M. Bagging and boosting for the nearest mean classifier: Effects of sample size on diversity and accuracy / Skurichina M., Kuncheva L., Duin R. // Multiple Classifier Systems (Proc. Third International Workshop MCS, Cagliari, Italy) / Ed. by F. Roli, J. Kittler. - Vol. 2364.- Springer, Berlin, 2002.- Pp. 62-71.

71. Breiman, L. Bagging predictors // Machine Learning.- 1996.- Vol. 24, no. 2.- Pp. 123-140.

72. Skurichina, M. Limited bagging, boosting and the random subspace method for linear classifiers / Skurichina M., Duin R. P. W. // Pattern Analysis & Applications.- 2002. - no. 5. - Pp. 121-135.

73. Bousquet, O. Stability and generalization / Bousquet O., Elisseeff A. // Journal of Machine Learning Research. - 2002. - no. 2. - Pp. 499-526.

74. Mason, L. Generalization error of combined classifiers: / Mason L., Bartlett P., Golea M. // Tech. rep.: Department of Systems Engineering, Australian National University, 1997.

75. Wolpert, D.H. Stacked generalization / Wolpert David H. // Neural networks 5.2, 1992. 241-259 с.

76. Воронцов, К. В. Комбинаторные оценки качества обучения по прецедентам // Докл. РАН. - 2004. - Т. 394, № 2. - С. 175-178.

77. Ивахненко, А. А. Верхние оценки переобученное и профили разнообразия логических закономерностей / Ивахненко А. А., Воронцов К. В. // Математические методы распознавания образов - номер 13. - М.: МАКС Пресс, 2007. - С. 33-37.

78. Воронцов, К. В. О комбинаторном подходе к оценке качества обучения алгоритмов // Математические методы распознавания образов: Одиннадцатая Всероссийская конференция Тезисы докладов - Пущино, 2003 - С. 47-49.

79. Воронцов, К. В. Качество восстановления зависимостей по эмпирическим данным // Математические методы распознавания образов: 7-ая Всерос. конф. Тезисы докл. - Пущино, 1995 - С. 24-26.

80. Вапник, В. Н., Червоненкис А. Я. Теория распознавания образов. -М.: Наука, 1974. - 416 с.

81. Вапник, В. Н. Восстановление зависимостей по эмпирическим данным. - М.: Наука, 1979. - 448 с.

82. Bartlett, P. Generalization performance of support vector machines and other pattern classifiers / Bartlett P., Shawe-Taylor J. // Advances in Kernel Methods. -MIT Press, Cambridge, USA, 1999. - Pp. 43-54.

83. Burges, C.J.C. A tutorial on support vector machines for pattern recognition // Data Mining and Knowledge Discovery. - 1998. - Vol. 2, no. 2. - Pp. 121 -167.

84. Ratsch, G. SVM and Boosting: One Class / Ratsch G., Scholk B., Mika S., Muller K.R. // IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume 24, number 9, 2002. С. 1184-1199.

85. Anthony, M. Neural Network Learning: Theoretical Foundations / Martin Anthony, Peter L. Bartlett // Cambridge University Press, 1 edition, Cambridge, 2009. -404 c.

86. Хайкин, С. Нейронные сети: полный курс, 2-е издание. Пер. с англ. -М.: Издательский дом «Вильяме», 2006. - 1104 c.

87. Головко, В. А. Нейронные сети: обучение, организация и применение. - М.: ИПРЖР, 2001. - 256 с.

88. Ботов, П. В. Точные оценки вероятности переобучения для монотонных и унимодальных семейств алгоритмов / П.В. Ботов // Всеросс. конф. Математические методы распознавания образов №14. - М.: МАКС Пресс, 2009. -С. 7-10.

89. Воронцов, К. В. Комбинаторные обоснования обучаемых алгоритмов // Журнал вычислительной математики и математической физики - 2004. - Т. 44, № 11. - С. 2099-2112.

90. Schapire, R. E. Boosting the margin: a new explanation for the effectiveness of voting methods / Schapire R. E., Freund Y., Lee W. S., Bartlett P. // Annals of Statistics. - 1998.- Vol. 26, no. 5.- Pp. 1651-1686.

91. Schmidhuber, J. Deep Learning in Neural Networks: An Overview // Neural Networks. 61, 2015. С. 85-117.

92. Russakovsky, O. ImageNet Large Scale Visual Recognition Challenge / Russakovsky Olga, Jia Deng, Hao Su // International Journal of Computer Vision, December 2015, Volume 115, Issue 3, pp 211-252.

93. Breiman, L. Random Forests // Machine Learning, 45(1), 2001. С. 5-32.

94. Ho, Tin. The Random Subspace Method for Constructing Decision Forests. / Tin Kam Ho, Murray Hill // IEEE Transactions on Pattern Analysis and Machine Intelligence. Volume 20 Issue 8, 1998. С. 832-844.

95. Elisseeff, A. Stability of randomized learning algorithms / Andree Elisseeff, Theodoras Evgeniou, Massimiliano Pontil // Journal of Machine Learning Research. - 2005. - no. 6. - Pp. 55-79.

96. Breiman, L. Classification and Regression Trees / Breiman L. Friedman J., Stone C. J., Olshen R. A. // Belmont, California, U.S.A.: Wadsworth Publishing Company, 1984.

97. Mazurov, V. Committee constructions for solving problems of selection, diagnostics and prediction / Mazurov V., Khachai M., Rybin A. // Proceedings of the Steklov Institute of mathematics. - 2002. - Vol. 1. - Pp. 67-101.

98. Вапник, В. Н. О равномерной сходимости частот появления событий к их вероятностям / Вапник В. Н., Червоненкис А. Я. // ДАН СССР. - 1968. - Т. 181, № 4. - С. 781-784.

99. Кочедыков, Д. А. Структуры сходства в семействах алгоритмов классификации и оценки обобщающей способности // Всеросс. конф. Математические методы распознавания образов-14. - М.: МАКС Пресс, 2009.- С. 45-48.

100. Воронцов, К. В. Слабая вероятностная аксиоматика и надёжность эмпирических предсказаний // Математические методы распознавания образов-13. - М.: МАКС Пресс, 2007. С. 21-25.

101. Рязанов, В. В. О некоторых моделях голосования и методах их оптимизации / Рязанов В. В., Сенько О. В. // Распознавание, классификация, прогноз. - 1990. - Т. 3. - С. 106-145.

102. Воронцов, К. В. О проблемно-ориентированной оптимизации базисов задач распознавания // Журнал вычислительной математики и математической физики, 1998. - Т. 38, № 5. С. 870-880.

103. Иванов, М. Н. Отбор эталонов, основанный на минимизации функционала полного скользящего контроля / Иванов М. Н., Воронцов К. // Всеросс. конф. Математические методы распознавания образов-14. - М.: МАКС Пресс, 2009. С. 119-122.

104. Воронцов, К. В. Точные оценки вероятности переобучения // Доклады РАН. - 2009. - Т. 429, № 1 . - С . 15-18.

105. Bottou, L. On the effective VC dimension / Leon Bottou, Corinna Cortes, Vladimir Vapnik // Tech. Rep. Neuroporose, 1994. [электронный ресурс] ftp : //archive.cis. ohio-state.edu/pub/neuroprose.

106. Bontempi, G. A bound on the cross-validation estimate for algorithm assessment / Bontempi G., Birattari M. // Eleventh Belgium/Netherlands Conference on Artificial Intelligence (BNAIC), 1999. - Pp. 115-122.

107. Matsumoto, M. Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator / Matsumoto M.; Nishimura T. // ACM Transactions on Modeling and Computer Simulation. 8 (1), 1998. C. 3-30.

108. Agrawal, S. Automated Selection of Materialized Views and Indexes for SQL Databases / Agrawal, S., Chaudhuri, S., Narasayya, V. // In Proceedings of International Conference on Very Large Data Bases, Cairo, Egypt, 2000.

109. Debnath, B. SARD: A statistical approach for ranking database tuning parameters / Debnath B., Lilja D., Mokbel M. // Data Engineering Workshops (ICDEW) IEEE International Conference, pages 11-18, 2008.

110. Cheiney, J.P. A Functional Clustering Method for Optimal Access to Complex Domains in a Relational DBMS / J.P. Cheiney, G. Kierman // Proc. 4th International Conference of Data Engineering, Los Angeles, Calif., Feb. 1988. Washington, D.C., 1988. pp. 394-401.

111. Dageville, B. Automatic SQL Tuning in Oracle 10g / Dageville, В., Das, D., Dias, K., Yagoub, K., Zait, M., Ziauddin, M. // In Proc. Of the 30 International Conference on Very Large Data Bases, 2004.

112. Grazzini E. A Physical Structure for Efficient Processing of Relational Queries / E. Grazzini, R. Pinzani, F. Pippolini // Found. Data Organ. Proc. Int. Conf., Kyoto, May 22-24, 1985. New York; London, 1987. pp. 501-514.

113. Kim, W. Global Optimization of Relational Queries: A First Step / W. Kim // Query Processing in Database Systems. New York: Springer. 1985. pp. 206-216.

114. Satoh, К. Local and Global Query Optimization Mechanisms for Relational Databases / K. Satoh, M. Tsuchida, F. Nakamura, K. Oomachi // Proc. 11th Int. Conf. Very Large Databases, Stockholm, Sweden, Aug. 1985. Los Altos, Calif., 1985. pp. 405-417.

115. Sellis, T. Global Query Optimization / T. Sellis // Proc. ACM SIGMOD International Conference on Management Data, Washington, D.C., May 28-30, 1986. New York, 1986. pp. 191-205.

116. Галиев, Ш.И. Математическая логика и теория алгоритмов // Казань: Изд-во КГТУ им. А. Н. Туполева. - 2002. - 270 с.

117. Гуц, А.К. Математическая логика и теория алгоритмов: учебное пособие // Омск: Изд-во Наследие. Диалог-Сибирь. - 2003. - 108 с.

118. Игошин, В.И. Математическая логика и теория алгоритмов / М.: Издательский центр «Академия». - 2004. - 448 с.

119. Амосов, А.А. Вычислительные методы для инженеров / Амосов А.А., Дубинский Ю.А., Копченова Н.В. // М.: Высшая школа, 1994. - С. 544.

120. IEEE 754: Standard for Binary Floating-Point Arithmetic [электронный ресурс]. URL: http://grouper.ieee.org/groups/754/

121. Берж, К. Теория графов и ее применения / Под ред. Вайнштейна И.А. Пер. с англ. Зыкова А.А. // Москва: Изд. Иностранной литературы. - 1962. - 320 с.

122. Gromey, D. Construction of a parametric model of competitive access in relational databases by using a random forest method / D. Gromey, E. Lebedenko, D. Nikolaev, T. Rozhkova // Eastern-European Journal of Enterprise Technologies. Information technology. Industry control system. - 2019. - Vol. 3, №2 (99). - p. 15 24.

123. Свидетельство о государственной регистрации программы для ЭВМ №2019661464. Программа обработки журналов работы СУБД с синтаксическим разбором текстов поступивших запросов, выделением предикатов конкурирующих классов запросов и формированием выборки прецедентов для методов машинного обучения / Громей Д.Д., Лебеденко Е.В., Воробьев А.В.; заявители и правообладатели: Громей Д.Д., Лебеденко Е.В., Воробьев А.В.; заявл. 16.08.2019; опубл. 02.09.2019..

124. Березин, И.С. Методы вычислений, том 1 и том 2. / Березин И.С., Жидков Н.П. // М.: Наука, 1993. - 928 с.

125. Мессарович, М. Общая теория систем: математические основы / Мессарович М., Такахара Я. // Пер. с англ. - М.: Мир, 1978. - 312 с.

126. Калман, Р. Очерки по математической теории систем / Калман Р., Фалб П., Арбис М. // Пер. с англ. - М.: Мир, 1971. - 398 с.

127. Громей, Д.Д. Автоматизация распределения данных для СУБД с конкурентными запросами / Д.Д. Громей // Актуальные направления развития систем охраны, специальной связи и информации для нужд государственного управления: IX Всероссийская межведомственная научная конференция: материалы и доклады (Орёл, 11-12 февраля 2015 года). В 12 ч. Ч. 10 / под общ. ред. В. В. Мизерова. - Орёл: Академия ФСО России, 2015. - 181 с., С. 64-67.

128. Мессарович, М. Теория иерархических многоуровневых систем / Мессарович М., Мако Д., Такахара И. // Пер. с англ. - М.: Мир, 1973. - 344 с.

129. Громей, Д.Д. Алгоритм автоматического распределения данных в реляционных СУБД / Д.Д. Громей // Актуальные направления развития систем охраны, специальной связи и информации для нужд государственного управления: XI Всероссийская межведомственная научная конференция: материалы и доклады. В 10 ч. Ч. 7. - Орёл: Академия ФСО России, 2019. - 176 с. -T. 7. - С. 19-24.

130. Gromey, D.D. To the question of management of the diagram database in the problems of horizontal scalability of autonomous DBMS / D.D. Gromey, A.S. Bykova //Modern informatization problems in economics and safety. Proceedings of the XXIV-th International Open Science Conference. - 2019. p. 63-67.

131. Богомолов, А.М. Алгебраические основы теории дискретных систем / Богомолов А.М., Салий В.Н. // - М.: Найка. Физматлит, 1997. - 368 с.

132. Handbook of Simulation. Principles, Methodology, Advances, Applications and Practice / под ред. J. Banks. - John Wiley & Sons, Inc., 1998. - 864 с.

133. Дубровский, С.А. Методы обработки и анализа экспериментальных данных: учеб. пособие / С.А. Дубровский, В.А. Дудина, Я.В. Садыева // Липецк: Изд-во Липецкого государственного технического университета, 2015. - 62 с.

134. Губарев, В.В. Системный анализ в экспериментальных исследованиях; Учеб. пособие: В 3-х ч. - Новосибирск: Изд-во НГТУ, 2000. - Ч. 1. - 99 с.

135. Косарев, Е.Л. Методы обработки экспериментальных данных. -издание второе, переработанное - М.: ФИЗМАТЛИТ, 2008. - 208 с.

136. Поликарпов, В.М. Современные методы компьютерной обработки экспериментальных данных: учебное пособие / В.М. Поликарпов, И.В. Ушаков, Ю.М. Головин. - Тамбов: Издательство Тамбовского государственного технического университета, 2006. - 84 с.

137. Воронцов, К. В. Комбинаторный подход к проблеме переобучения // Всероссийская конференция Математические методы распознавания образов-14. -М.: МАКС Пресс, 2009. - С. 18-21.

138. Gromey, D.D. Automation of data distribution for the DBMS with competitive requests / D.D. Gromey, E.V. Lebedenko // Modern informatization problems in simulation and social technologies Proceedings of the XX-th International Open Science Conference, Yelm, WA, USA. - 2015. p. 167-173.

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

140. Белкин, А.Р. Принятие решений: комбинаторные модели апроксимацции информации. М.: Наука, 1990. - 160 с.

141. Венжега, А. В. Проблема переобучения при отборе признаков в линейной регрессии с фиксированными коэффициентами / Венжега А. В., Умеитаев С. А., Орлов А. А., Воронцов К. В. // Математические методы распознавания образов-13. - М.: МАКС Пресс, 2007. - С. 90-93.

142. PostgreSQL 11 Documentation [электронный ресурс]. URL: https://www.postgresql.org/files/documentation/pdf/11/postgresql-11-A4.pdf

143. SQL Server technical documentation [электронный ресурс]. URL: https://docs.microsoft.com/en-us/sql/sql-server/?view=sql-server-2017

144. Friesen, J. Synchronization //Java Threads and the Concurrency Utilities. -Apress, Berkeley, CA, 2015. - С. 21-38.

145. Будникова, А. А. Ошибки в системах баз данных: теорема Брюера / Будникова А. А., Богданов И. В., Кумратова А. М. //Цифровизация экономики: направления, методы, инструменты. - 2019. - С. 290-292.

146. Yoo, R. M. Performance evaluation of Intel transactional synchronization extensions for high-performance computing // Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis. -ACM, 2013. - С. 19.

147. Kao, K. F. An index selection method without repeated optimizer estimations / Kao K. F., Liao I. E. // Information sciences. - 2009. - Т. 179. - №. 13. -С. 2263-2272.

148. McLaughlin, S. Timing the changes in political structures: A new polity database //Journal of Conflict Resolution. - 1998. - Т. 42. - №. 2. - С. 231-242.

149. Ma, L. Query-based Workload Forecasting for Self-Driving Database Management Systems / L. Ma, D. Van Aken, A. Hefny, G. Mezerhane, A. Pavlo, and G. J. Gordon // in Proceedings of the 2018 International Conference on Management of Data, 2018, pp. 631-645.

150. Ross, K. Multi-source data analysis and evaluation of machine learning techniques for SQL injection detection / Ross, K., Moh, M., Moh, T., Yao, J. // Proceedings of the ACMSE 2018 Conference, Article No. 1, 2018.

151. Cumin, J. Data Exploration with SQL using Machine Learning Techniques / Cumin, J., Petit, J., Scuturici, V., Surdu, S. // Proc. 20th International Conference on Extending Database Technology (EDBT), 2017.

Псевдокод алгоритма ранжирования объектов логической схемы данных по

предикатам запросов

Input: LTREE : TRYPE; Q : QTYPE Output: Sortobj : []LTYPE

01 func main(LTREE : LTYPE, Q: QTYPE) : []LTYPE {

02

for _, v := range LTREE {

if v.IsLogical() && v.Value == 0 { WS := append(WS, v)

}

}

for _, q := range Q {

QT = QT + q.ExecuteTime SZ++

03

04

05

06

07

08

09

10 11 12

13

14

15

16

17

18

19

20 21 22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48 }

}

for i, v var LA var LT

= range WS {

= double(0) = double(0) N = append(NQ, 0) SR = append(SR, arrange(v.Right)) SL = append(SL, arrange(v.Left)) var X := predict(v) for root := v.Root; root != NULL { X = append(X, root) root = root.Root

}

for _, q := range Q {

if q.Predict.Union(X) != NULL { LT = LT + q.ExecuteTime

}

if q.Predict.Union(X) == NULL { N[i]++

}

}

LA = LT / QT SR[i] = SR[i] * LA SL[i] = SL[i] * LA if SR[i] > SL[i] {

R = append(R, SR[i] - SL[i]) } else {

R = append(R, SL[i] - SR[i])

}

head = sortstore(head, R[i], v)

}

for head. Left != NULL { head = head.Left

}

for head.Right != NULL {

result = append(result, head.Root)

}

return result

Выборка подмножества параметров модели применимых для ранжирования, расчет суммарного времени выполнения запросов и их количества

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

Расчет суммы затраченного на исходные запросы времени

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

Добавление узла в линейно упорядоченное множество, с учетом рассчитанного критерия R

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

Input: Q : []DB LOG Output: DDL : []SQL

01 func alg2(Q

02

03

04

05

06

07

08

09

10 11 12

13

14

15

16

17

18

19

20 21 22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60 61

var Result : var Dataset var DbModel var Sortobj

[]DB LOG) : []SQL { = new []SQL = new []MLFEATURE = new PMODEL = new []LTYPE

for _, q := range Q {

var Feature := new MLFEATURE Feature.Target = q.GetExecutionTime() for _, p := range q.predicts {

Feature[p.ObjectPath] = new TYPLE(p.Term, p.Value)

}

for _, c := range Q {

if c.GetConcurentTime(q) > 0 {

Feature[c.GetEqClass()] += c.GetConcurentTime(q)

}

}

Dataset = append(Dataset, Feature)

}

DbModel.LoadFeatures(Dataset) DbModel.Fit()

Sortobj = RangeAlg(DbModel.Trees())

for _, node : = range Sortobj { if node.color == 0 { var read := dobule(0) var cread := double(0) var write := double(0) for _, q : = range Q { if q.IsAssociate(node) { if q.IsWrite() {

write += q.GetExecutionTime() } else {

read += q.GetExecutionTime()

}

for _, c := range Q {

if c.IsAssociate(node) && c != q { cread += c.GetExecutionTime()

}

}

}

}

if IsPariteteScope(read, write) == true {

Result = append(Result, ConvToSlice(node } else if IsConcurentScope(cread, read) == Result = append(Result, ConvToMView(node } else if IsReadScopt(read, write) == true Result = append(Result, ConvToIndex(node } else {

Result = append(Result, ConvToIndexDrop(node.ObjectPath))

}

}

for _, a := range Sortobj {

if a.ObjectPath == node.ObjectPath { a.color = 1

}

}

node.color = 1

Расчет признаков для обучения параметрической модели

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

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

.ObjectPath, node.Term)) true {

.ObjectPath, node.Term)) {

.ObjectPath))

Выбор изменения схемы данных

}

return Result

Маркировка

ассоциированных объектов логической схемы

}

Исходный текст программной реализации модели доступа отдельного пользователя в среде Hammer DB

!/usr/local/bin/tclsh8.6

#THIS SCRIPT TO BE RUN WITH VIRTUAL USER OUTPUT ENABLED #EDITABLE OPTIONS################################################## set library Pgtcl ;# PostgreSQL Library

set total_iterations 1000000 ;# Number of transactions before logging off set RAISEERROR "false" ;# Exit script on PostgreSQL (true or false) set KEYANDTHINK "false" ;# Time for user thinking and keying (true or false) set rampup 2; # Rampup time in minutes before first Transaction Count is taken set duration 5; # Duration in minutes before second Transaction Count is taken set mode "Local" ;# HammerDB operational mode

set VACUUM "false" ;# Perform checkpoint and vacuuum when complete (true or false)

set DRITA_SNAPSHOTS "false";#Take DRITA Snapshots

set ora_compatible "false" ;#Postgres Plus Oracle Compatible Schema

set host "localhost" ;# Address of the server hosting PostgreSQL

set port "5432" ;# Port of the PostgreSQL server

set superuser "postgres" ;# Superuser privilege user

set superuser_password "postgres" ;# Password for Superuser

set default_database "postgres" ;# Default Database for Superuser

set user "tpcc" ;# PostgreSQL user

set password "tpcc" ;# Password for the PostgreSQL user set db "tpcc" ;# Database containing the TPC Schema set allwarehouses "true";# Use all warehouses to increase I/O #EDITABLE OPTIONS################################################## #LOAD LIBRARIES AND MODULES

if [catch {package require $library} message] { error "Failed to load $library - $message" } if [catch {::tcl::tm::path add modules} ] { error "Failed to find modules directory" } if [catch {package require tpcccommon} ] { error "Failed to load tpcc common functions" } else { namespace import tpcccommon::* }

if { [ chk_thread ] eq "FALSE" } {

error "PostgreSQL Timed Script must be run in Thread Enabled Interpreter" }

proc ConnectToPostgres { host port user password dbname } { global tcl_platform

if {[catch {set lda [pg_connect -conninfo [list host = $host port = $port user = $user password = $password dbname = $dbname ]]} message]} { set lda "Failed" ; puts $message error $message } else {

if {$tcl_platform(platform) == "windows"} {

#Workaround for Bug #95 where first connection fails on Windows catch {pg_disconnect $lda}

set lda [pg_connect -conninfo [list host = $host port = $port user = $user password =

$password dbname = $dbname ]] }

pg_notice_handler $lda puts

set result [ pg_exec $lda "set CLIENT_MIN_MESSAGES TO 'ERROR'" ]

pg_result $result -clear }

return $lda }

set rema [ lassign [ findvuposition ] myposition totalvirtualusers ] switch $myposition { 1 {

if { $mode eq "Local" || $mode eq "Master" } {

if { ($DRITA_SNAPSHOTS eq "true") || ($VACUUM eq "true") } {

set lda [ ConnectToPostgres $host $port $superuser $superuser_password $default_database ] if { $lda eq "Failed" } {

error "error, the database connection to $host could not be established" }

}

set ldal [ ConnectToPostgres $host $port $user $password $db ] if { $lda1 eq "Failed" } {

error "error, the database connection to $host could not be established" }

set ramptime 0

puts "Beginning rampup time of $rampup minutes" set rampup [ expr $rampup*60000 ] while {$ramptime != $rampup} {

if { [ tsv::get application abort ] } { break } else { after 6000 } set ramptime [ expr $ramptime+6000 ] if { ![ expr {$ramptime % 60000} ] } {

puts "Rampup [ expr $ramptime / 60000 ] minutes complete ..." }

}

if { [ tsv::get application abort ] } { break } if { $DRITA_SNAPSHOTS eq "true" } { puts "Rampup complete, Taking start DRITA snapshot." set result [pg_exec $lda "select * from edbsnap()" ]

if {[pg_result $result -status] ni {"PGRES_TUPLES_OK" "PGRES_COMMAND_OK"}} { if { $RAISEERROR } { error "[pg_result $result -error]" } else {

puts "DRITA Snapshot Error set RAISEERROR for Details" }

} else { pg_result $result -clear

pg_select $lda {select edb_id,snap_tm from edb$snap order by edb_id desc limit 1} snap_arr { set firstsnap $snap_arr(edb_id)

set first_snaptime $snap_arr(snap_tm) }

puts "Start Snapshot $firstsnap taken at $first_snaptime" }

} else {

puts "Rampup complete, Taking start Transaction Count." }

pg_select $lda1 "select sum(xact_commit + xact_rollback) from pg_stat_database" tx_arr {

set start_trans $tx_arr(sum) }

pg_select $lda1 "select sum(d_next_o_id) from district" o_id_arr {

set start_nopm $o_id_arr(sum) }

puts "Timing test period of $duration in minutes"

set testtime 0

set durmin $duration

set duration [ expr $duration*60000 ]

while {$testtime != $duration} {

if { [ tsv::get application abort ] } { break } else { after 6000 } set testtime [ expr $testtime+6000 ] if { ![ expr {$testtime % 60000} ] } {

puts -nonewline "[ expr $testtime / 60000 ] ...," }

}

if { [ tsv::get application abort ] } { break } if { $DRITA_SNAPSHOTS eq "true" } { puts "Test complete, Taking end DRITA snapshot." set result [pg_exec $lda "select * from edbsnap()" ]