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

• Ха Ван Муон
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Ха Ван Муон

ВВЕДЕНИЕ

Глава 1. ОБЗОР МЕТОДОВ ОПТИМИЗАЦИИ РАБОТЫ

БАЗ ДАННЫХ

1.1 Классификации баз данных

1.2 Подходы к оптимизации работы реляционных баз данных

1.2.1 Оптимизация схемы реляционной базы данных

1.2.2 Подходы к организации распределенных баз данных

1.3 Оптимизация запросов к базам данных

1.4 Способы представления запросов и схем баз данных

1.5 Выводы

Глава 2. МЕТОДЫ ОПТИМИЗАЦИИ СТРУКТУРЫ БАЗ

ДАННЫХ ТИПА КЛЮЧ-ДОКУМЕНТ

2.1 Методы оптимизации структуры нераспределенных баз данных

^дь

2.1.1 Метод определения структуры коллекций для нераспределенных баз данных типа «ключ-документ»

2.1.2 Методика определения коллекций в базах данных типа «ключ-документ» в зависимости от исходных данных

2.1.3 Метод определения структуры вложенных документов в

БД типа «ключ-документ»

2.2 Методы оптимизации структуры распределенных баз данных КоБдЬ типа «ключ-документ»

2.2.1 Метод построения информационного графа запроса для распределенной реляционной базы данных

2.2.2 Метод построения схемы распределенной базы данных КоБдЬ типа «ключ-документ»

2.3 Выводы

Глава 3. ТРАНСЛЯЦИЯ ЗАПРОСОВ ИЗ ФОРМАТА

РЕЛЯЦИНОНОЙ БАЗЫ ДАННЫХ В ФОРМАТ БАЗЫ ДАННЫХ NOSQL ТИПА

«КЛЮЧ-ДОКУМЕНТ»

3.1 Языки запросов к базам данных

3.2 Трансляции запросов из формата MySQL в формат MongoDB c учетом структуры базы данных

3.2.1 Метод трансляции запросов из формата MySQL в

формат MongoDB c учетом структуры базы данных

3.2.2 Реализация метода трансляции запросов из формата MySQL в формат MongoDB

3.3 Пример применения разработанного метода трансляции запроса

из SQL в MongoDB с учетом структуры базы данных

3.4 Выводы

Глава 4. СОЗДАНИЕ ПРОГРАМНЫХ МОДУЛЕЙ ДЛЯ

ТЕСТИРОВАНИЯ РАЗРАБОТАННЫХ МЕТОДОВ

4.1 Описание программных модулей

4.1.1 Описание программных модулей для определения коллекций баз данных типа «ключ-документ» по заданному набору свойств объектов и запросов

4.1.2 Описание программного модуля для трансляции данных

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

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

4.2 Описание исходных баз данных, используемых при тестировании методов

4.2.1 Описание разработанных баз данных для тестирования методов

4.2.2 Описание базы данных «TPC - Н»

4.3 Тестирование разработанных методов на базах данных MySQL и MongoDB

4.3.1 Тестирование метода для определения коллекций для базы данных типов «ключ-документ» по заданному

набору свойств и запросов

4.3.2 Тестирование метода определения вложенных документов

4.3.3 Тестирование метода трансляции запросов из формата MySQL в формат MongoDB

4.3.4 Тестирование метода оптимизации распределенной базы данных

4.4 Выводы

ЗАКЛЮЧЕНИЕ

СПИСОК РИСУНКОВ

СПИСОК ТАБЛИЦ

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

ПРИЛОЖЕНИЕ А - Свидетельства о государственной

регистрации программы для ЭВМ

ПРИЛОЖЕНИЕ Б - Коды тестированных запросов к базе

данных «TPC - H» на MySQL и MongoDB

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

ВВЕДЕНИЕ

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

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

В мире за последние 30 лет проводится много исследований в области поиска подходов к консолидации данных из различных систем хранения и, как следствие, предложено множество различных решений этой проблемы. Среди известных результатов в области консолидации баз данных можно назвать системы SemInt [1;2], LSD (Learning Source Descriptions) в [3;4], SKAT (Semantic Knowledge Articulation Tool) [5], TranScm [6], Palopoli в [7], ARTEMIS [8; 9], MOMIS (Mediator enviroment for Multiple Information Sources) [10; 11]. Однако все эти системы сосредоточены на консолидации реляционных баз данных и не затрагивают проблему консолидации реляционной базы данных с NoSQL

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

1) Трансляция структуры реляционной базы данных в формат базы данных NoSQL, например «ключ значения», «ключ - документ», «семейство столбцов» или «графовую» базу данных. К наиболее известным подходам к трансляции реляционных баз данных в формат NoSQL относятся: построение правил видоизменения архитектуры базы данных [12-16] и трансляция на основе методов реляционной алгебры [17]. Например, авторы [18] применяют традиционные правила теории нормализации реляционной схемы базы данных (теоремы о нормальных формах: вторая и третья нормальные формы (2NF, 3NF) и нормальная форма Бойса-Кодда (BCNF)) для разработки схемы данных в NoSQL.

2) Трансляция запросов из формата реляционной базы данных в формат NoSQL базы данных. В большинстве работ процесс трансляции запросов сфокусирован на разработке программного обеспечения промежуточного уровня, которое выполняет SQL команды для обработки данных для NoSQL баз данных [19-25]. В отдельных работах [26-28] предложен подход к трансляции запроса с применением теории грамматик. Еще одним подходом является создание общих языков запроса, которые может использовать для реляционной и NoSQL баз данных одновременно. К таким системам выполнения запросов относятся, например UnQL (Unstructured Query Language) в [29] или Impala в [30].

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

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

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

1) Оптимизация структуры централизованной базы данных. Существуют стандартные походы для оптимизации схемы реляционной базы данных по времени выполнения к ней запросов, например нормализация и денормализа-ция [31; 32]. Вопросы оптимизации схемы базы данных NoSQL рассматриваются во многих работах, например [33; 34]. В [33] авторы предложили подход к сопоставлению модели данных приложения с физической схемой на основе оценки вычислительной нагрузки при заданной схеме. Решению проблемы построения концептуальной модели данных приложения по заданной схеме базы данных NoSQL посвящено исследование [34]. Подход основан на оценке вычислительных и временных затрат и использует методы целочисленного программирования.

2) Оптимизация структуры распределенной базы данных. Наиболее известными подходами к масштабированию распределенной базы данных являются шардинг и репликация. Процессам организации шардинга в NoSQL посвящены работы [35; 36].

3) Оптимизация запросов к базе данных по скорости обработки данных и обеспечению целостности данных. Среди работ, связанных напрямую с оптимизацией запросов к базам данных, можно выделить [37-39]. Для оптимизации запросов по скорости в некоторых работах [40; 41] предлагается применение методов распараллеливания и распределения вычислений.

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

— формализованных методов трансляции реляционных баз данных в NoSQL;

— формализованных методов оптимизации структур баз данных NoSQL;

— формализованных методов трансляции и оптимизации запросов к NoSQL базам данных с учетом их структуры.

Целью диссертационной работы является разработка совокупности формализованных методов трансляции данных из реляционной базы данных в формат базы данных NoSQL типа «ключ-документ» с оптимизацией ее схемы и запросов для ускорения обработки и хранения данных.

В соответствии с поставленной целью в диссертационной работе решались следующие задачи:

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

2. Разработка методов оптимизации структуры базы данных NoSQL для моделей «ключ-документ».

3. Разработка методики преобразования реляционной базы данных в формат базы данных NoSQL типа «ключ-документ».

4. Разработка метода оптимизации структуры распределенной базы данных NoSQL типа «ключ-документ».

5. Разработка метода трансляции запросов из формата реляционной базы данных в формат базы данных NoSQL типа «ключ-документ».

6. Создание программных модулей для тестирования разработанных методов.

Объект исследования. Базы данных различного типа, включая реляционные и NoSQL базы данных.

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

Методология и методы исследования. Для решения поставленных задач в диссертационной работе использовались теория баз данных, теория множеств, теория графов, теории функциональных зависимостей, реляционная алгебра. Для разработки программного обеспечения и тестирования разработанных методов использованы языки программирования C# и Python, среда разработки Microsoft Visual Studio Community 2019 версия 16.9.3, Visual studio code версия 1.59.0, СУБД MySQL 8.0.17, СУБД MongoDB 4.4.4 Community.

Основные результаты:

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

2. Методы оптимизации структуры базы данных NoSQL для модели «ключ-документ» с учетом и без учета встроенных документов.

3. Методика преобразования реляционной базы данных в формат базы данных NoSQL типа «ключ-документ» с учетом и без учета встроенных документов.

4. Метод оптимизации структуры распределенной базы данных NoSQL типа «ключ-документ».

5. Метод трансляции запросов из формата реляционной базы данных в формат базы данных NoSQL типа «ключ-документ».

6. Программное обеспечение для тестирования разработанных методов.

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

1. Методы оптимизации структуры базы данных NoSQL для модели «ключ-документ» с учетом и без учета встроенных документов.

2. Методика преобразования реляционной базы данных в формат базы данных NoSQL типа «ключ-документ».

3. Метод оптимизации структуры распределенной базы данных NoSQL типа «ключ-документ».

4. Метод трансляции запросов из формата реляционной базы данных в формат базы данных NoSQL типа «ключ-документ».

Научная новизна работы заключается в следующем:

1. Разработаны методы определения структуры коллекций для базы данных NoSQL типа «ключ-документ» со вложенными и без вложенных документов по заданному набору свойств и запросов, которые основаны на теории множеств и позволяют формализовано представить запросы и схему базы данных и определить оптимальный состав коллекций по скорости доступа к данным и объему хранимых данных путем применения операций над множествами.

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

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

4. Разработан метод трансляции запросов из формата реляционной базы данных в формат базы данных NoSQL типа «ключ-документ» с учетом ее схемы и структуры самих запросов.

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

Теоретическая значимость диссертационной работы заключается в:

1) выведении формул, позволяющих определять оптимальную структуру коллекций для базы данных NoSQL типа «ключ-документ» по заданному набору свойств объектов базы данных и метаинформации о запросах;

2) выведении формул, позволяющих определять структуру вложенных документов в базах данных NoSQL типа «ключ-документ»;

3) разработке концептуальной схемы применения разработанных методов для получения оптимальной структуры базы данных NoSQL типа «ключ-документ» на основе различных начальных условий трансляции баз данных;

4) способе представления объектов распределенной базы данных и описании подходов на основе теории графов для оптимизации структуры этих баз данных;

5) формализации подхода к представлению запросов к реляционной базе данных и их трансляции в формат NoSQL с учетом структуры баз данных.

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

1) разработанных методов для трансляции реляционной базы данных в формат базы данных NoSQL и/или последующей консолидации баз данных;

2) разработанных программных модулей для определения структуры коллекций базы данных NoSQL типа «ключ-документ» по заданному набору свойств и запросов, трансляции базы данных из формата реляционной базы данных в формат базы данных NoSQL типа «ключ-документ», трансляции запросов из формата реляционной базы данных в формат базы данных NoSQL типа «ключ-документ» с учетом структуры базы данных, параллельного выполнения запросов к распределённым базам данных в различных предметных областях и в научных исследованиях

Реализация результатов исследования:

1. Теоретические и практические результаты диссертационной работы были применены при решении задач в рамках международного научного проекта РФФИ «Создание информационно-технологической поддержки исследований болезни Паркинсона с учетом сбора и обработки данных большого объема в режиме реального времени» (18-57-34001 Куба_т) и программы создания и развития научного центра мирового уровня «Павловский центр «Интегративная физиология - медицине, высокотехнологичному здравоохранению и технологиям стрессоустойчивости» (соглашение от 13.11.2020 №075-15-2020-933).

2. Результаты работы используются в учебном процессе кафедры вычислительной техники ФГАОУ ВПО «Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В.И. Ульянова (Ленина)» при преподавании курсов «Распределенные базы данных», «Не реляционные базы данных», «Оптимизация баз данных»

Апробация работы. Основные результаты работы докладывались на следующих конференциях:

- 2021 IEEE Конференция российских молодых исследователей в области электротехники и электроники (2021 ElConRus) (Санкт-Петербург, 26-29 января 2021 г.)

- II Международная конференция по нейронным сетям и нейротехнологиям (NeuroNT'2021) (Санкт-Петербург, 16 июня 2021 г.)

- The 21st International Conference on Computational Science and its Applications (Кальяри, Италия, 13-16 сентября 2021 г.)

Публикации по теме диссертации.

Полученные основные теоретические и практические результаты диссертационного исследования опубликованы в 11 трудах, в том числе в 2 научных статьях в журналах, рекомендуемых ВАК к опубликованию основных научных результатов диссертаций на соискание ученой степени кандидата наук, 3 научных статьях, опубликованных в зарубежных журналах, входящих в базы цитирования Web of Science и Scopus, 3 публикациях в сборниках конференций, 3 свидетельствах о государственной регистрации программы для ЭВМ.

Структура и объем диссертации

Диссертация состоит из введения, 4 глав, заключения, списка литературных источников, состоящего из 147 наименований, 2 приложений. Работа изложена на 190 машинописных страницах, включая 73 рисунка и 19 таблиц.

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

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

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

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

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

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

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

Глава 1. ОБЗОР МЕТОДОВ ОПТИМИЗАЦИИ РАБОТЫ БАЗ

ДАННЫХ

1.1 Классификации баз данных

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

— надежное хранение информации в памяти ЭВМ;

— выполнение специфических для данного приложения преобразований информации и вычислений;

— предоставление пользователю удобного интерфейса по доступу к данным.

Базы данных (БД) могут быть классифицированы по следующим признакам.

Классификация БД по технологии обработки данных:

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

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

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

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

Классификация систем БД по архитектуре:

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

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

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

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

Классификация БД по способу доступа к данным: По способам хранения и доступа к данным базы данных делятся на локальные и сетевые. Сетевые делятся на файл-северные и клиент - серверные (рис. 1.1)

Рисунок 1.1 — Классификация баз данных по способам хранения и доступа к

данным

В локальных базах данных все части хранятся на компьютере пользователя. При работе с локальными БД пользователь на каждом компьютере должен иметь свою копию БД. Основной проблемой локальных БД является синхронизация копий данных.

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

Пересылка файлов

Клиент

Сетевое приложение

СУБД

Рисунок 1.2 — Файл - серверные базы данных

В клиент-серверных базах данных СУБД и данные размешаются на одних носителях (серверах), а сетевое приложение устанавливается на других (кли-ентах)(Рис. 1.3).

Сервер БД Пересылка запросов и результатов Клиент

СУБД

i к у т Данные Сетевое приложение

Рисунок 1.3 — Клиент - серверные базы данных

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

Классификация БД по способам организации данных

По этой классификации базы данных делятся на три основных класса в соответствии с используемой моделью данных: реляционные БД, неструктурированные базы данных NoSQL и частино - структурированные базы данных

Реляционные базы данных

В основе реляционной базы данных (РБД) лежит реляционная модель, которая была предложена Эдгаром Коддом (Edgar F. Codd) [42] в 1969 году. С тех пор она стала доминирующей моделью базы данных для коммерческих приложений (по сравнению с другими моделями баз данных, такими как иерархические и сетевые модели).

В реляционной базе данных основными структурными единицами являются таблицы, которые можно связывать друг с другом [43-46]. Сегодня существует множество коммерческих систем управления реляционными базами данных, таких как Oracle, IBM DB2 и Microsoft SQL Server. Существует также множество бесплатных СУБД с открытым исходным кодом, таких как MySQL, mSQL (mini-SQL) и встроенная JavaDB (Apache Derby).

Достоинства и недостатки реляционных баз данных:

Достоинство:

1. Универсальный доступ к данным: РБД использует язык запросов SQL для обработки данных. SQL является языком запросов со стандартами, которых придерживаются большинство СУБД.

2. Целостность данных: важнейшая характеристика системы реляционной базы данных. Механизм поддержки целостности данных помогает избежать изолированных или несвязанных записей;

3. Оптимизация запросов: большинство систем управления реляционными БД имеют оптимизатор запросов, который выполняет грамматический и синтаксический анализ запросов и оптимизацию планов запросов с учетом собираемой статистики;

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

Недостатки [47]:

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

возможностями для обработки больших объемов данных, но это дорогое решение.

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

Базы данных

С начала 2000-х годов развитие веб-технологий, социальных сетей, мобильных устройств и интернета вещей привели к росту структурированных, полуструктурированных и неструктурированных данных. Приложения, работающие с этим данными, требуют наличия горизонтальной масштабируемости БД для мгновенной адаптации к возрастающему объему данных и увеличению скорости обработки запросов; возможности использования дополнительных ресурсов; высокой доступности к данным; устойчивости к неисправностям, аппаратным и программным сбоям, обновлениям событий; надежности транзакций; поддержки согласованности данных и минимальных затрат при изменении схемы базы данных.

Достижение вышеупомянутых требований в реляционной БД очень сложно и часто невозможно. Во-первых, жесткость реляционной схемы является препятствием в трансформации данных и, поэтому, не может удовлетворить требованиям приложений с динамически или часто изменяемыми сценариями обработки больших данных [48]. Во-вторых, масштабирование реляционной БД требует установки новых более мощных автономных серверов взамен существующих. Это дорогостоящий процесс, приводящий к недоступности системы во время каждого ее переноса на новый сервер и сложностям при согласовании распределенных нормализованных данных. Кроме того, в реляционной БД есть проблемы с доступностью и производительностью в связи с поддерживаемыми АСГО-транзакциями [49; 50]. Решение этих проблем РБД привело к развитию баз данных нового поколения, так называемых нереляционных баз данных, называемых NoSQL [51], целью которых является повышение доступности и масштабируемости данных.

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

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

Сравнение SQL и NoSQL [52]:

— структура и способ хранения данных: реляционные БД требуют заранее определенной структуры хранения данных, базы данных NoSQL не накладывают таких ограничений;

— запросы: независимо от лицензии реляционные СУБД используют единый язык SQL, каждая NoSQL СУБД реализует свой собственный способ работы с данными;

— масштабируемость: реляционная и NoSQL БД легко масштабируются по вертикали (например, за счет увеличения системных ресурсов). Однако NoSQL СУБД предоставляют более простые способы горизонтального масштабирования (например, создание кластера из нескольких машин). Добавление и удаление узлов в кластере не влияет на работоспособность и производительность всей системы. Дополнительным преимуществом этой архитектуры является то, что кластер NoSQL БД может быть развернут на обычном оборудовании, что значительно снижает стоимость всей системы;

Список литературы диссертационного исследования кандидат наук Ха Ван Муон, 2022 год

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

1. Li W., Clifton C. Semantic Integration in Heterogeneous Databases Using Neural Networks // Proceedings of the 20th International Conference on Very Large Data Bases. — ACM, 1994. — Pp. 1-2.

2. Li WS., Clifton C., Liu SY. Database Integration Using Neural Networks: Implementation and Experiences // Knowledge and Information Systems. — 2000. — Vol. 2, no. 1. — Pp. 73—96.

3. Doan A., Domingos P., Levy A. Learning source description for data integration // Proceedings of the Third International Workshop on the Web and Databases. — DBLP, 2000. — Pp. 81-86.

4. Doan A., Domingos P., Halevy A. Reconciling Schemas of Disparate Data Sources: A Machine-Learning Approach // SIGMOD Rec. — 2001. — Vol. 30, no. 2. — Pp. 509—-520.

5. Miller R. J., Haas L. M., Hernandez M. A. Schema Mapping as Query Discovery // Proceedings of 26th International Conference on Very Large Data Bases. — DBLP, 2000. — Pp. 77-88.

6. Milo T., Zohar S. Using schema matching to simplify heterogeneous data translation // Proceedings of the 24rd International Conference on Very Large Data Bases. — DBLP, 1998. — Pp. 122-133.

7. Palopoli L., Saccà D., Ursino D. An automatic technique for detecting type conflits in database shemes // Proceedings of the seventh international conference on Information and knowledge management. — ACM, 1998. — Pp. 306-313.

8. Castano S., De Antonellis V. A schema analysis and reconciliation tool environment for nheterogeneous databases // Proceedings. IDEAS'99. International Database Engineering and Applications Symposium (Cat. No.PR00265). — IEEE, 1999. — Pp. 53-62.

9. Castano S., De Antonellis V. Global viewing of heterogeneous data sources // IEEE Transactions on Knowledge and Data Engineering. — 2001. — Vol. 13, no. 2. — Pp. 277—-297.

10. Bergamaschi S., Castano S., Vincini M. Semantic integration of semistruc-tured and structured data sources // SIGMOD Rec. — 1999. — Vol. 28, no. 1.

— Pp. 54—-59.

11. Semantic integration of heterogeneous information sources / S. Bergamaschi, S. Castano, M. Vincini, D. Beneventano // Data & Knowledge Engineering. — 2001. — Vol. 36, no. 2. — Pp. 215—-249.

12. Chickerur S. Comparison of Relational Database with Document-Oriented Database ( MongoDB ) for Big Data Applications // 8th International Conference on Advanced Software Engineering and Its Applications. — IEEE, 2015.

— Pp. 41-47.

13. Hanine M., Bendarag A., Boutkhoum O. Data Migration Methodology from Relational to NoSQL Databases, World Academy of Science, Engineering and Technology // International Journal of Computer and Information Engineering. — 2015. — Vol. 9, no. 12. — Pp. 2559—-2563.

14. Alotaibi O, Pardede E. Transformation of Schema from Relational Database (RDB) to NoSQL Databases // Data. — 2019. — Vol. 4, no. 4.

15. Li X., Ma Z, Chen H. QODM: A query-oriented data modeling approach for NoSQL databases // 2014 IEEE Workshop on Advanced Research and Technology in Industry Applications (WARTIA). — IEEE, 2014. — Pp. 338-345.

16. Karnitis G., Arnicans G. Migration of Relational Database to Document-Oriented Database: Structure Denormalization and Data Transformation // 2015 7th International Conference on Computational Intelligence, Communication Systems and Networks. — IEEE, 2015. — Pp. 113-118.

17. Modeling MongoDB with Relational Model / G. Zhao, W. Huang, S. Liang, Y. Tang // 2013 Fourth International Conference on Emerging Intelligent Data and Web Technologies. — IEEE, 2013. — Pp. 115-121.

18. Application of NoSQL database MongoDB / Y. Gu, S. Shen, J. Wang, J. Kim // 2015 IEEE International Conference on Consumer Electronics -Taiwan. — IEEE, 2015. — Pp. 158-159.

19. Nuzhat F. Shaikh. Data Migration From SQL To MongoDB // International Journal Of Engineering Research And Development. — 2017. — Vol. 13, no. 11. — Pp. 32—-36.

20. Migration from RDBMS to Column-Oriented NoSQL: Lessons Learned and Open Problems / HJ. Kim, EJ. Ko, YH. Jeon, Lee KH. // Proceedings of the 7th International Conference on Emerging Databases. — Springer, 2017. — Pp. 25-33.

21. Lawrence R. Integration and Virtualization of Relational SQL and NoSQL Systems Including MySQL and MongoDB // 2014 International Conference on Computational Science and Computational Intelligence. — IEEE, 2014. — Pp. 285-290.

22. Correlation Aware Technique for SQL to NoSQL Transformation / J.C. Hsu, C.H. Hsu, S.C. Chen, Y.C. Chung // 7th International Conference on Ubi-Media Computing and Workshops(UMEDIA). — IEEE, 2014. — Pp. 43-46.

23. Zhang H., Wang Y, Han J. Middleware design for integrating relational database and NOSQL based on data dictionary // Proceedings 2011 International Conference on Transportation, Mechanical, and Electrical Engineering (TMEE). — IEEE, 2011. — Pp. 1469-1472.

24. Ma K, Abraham A. Toward lightweight transparent data middleware in support of document stores // 2013 Third World Congress on Information and Communication Technologies (WICT 2013). — IEEE, 2013. — Pp. 253-257.

25. Adriana J., Holanda M. NoSQL2: SQL to NoSQL Databases // Trends and Advances in Information Systems and Technologies. — Springer, 2018. — Pp. 938-948.

26. Query Mongo: MySQL to MongoDB Query Translator. — URL: http://www. querymongo.com./ (дата обращения: 2021-05-07).

27. Vincent R. SQL-to-MongoDB-db-query-converter. — URL: https:// github.com/vincentrussell/sql-to-mongo-db-query-converter./ (дата обращения: 2021-05-07).

28. Ramesh R. Mongodb translator - teiid 9.0 (draft). — URL: https:// docs.jboss.org/author/display/TEIID/MongoDB+Translator. (дата обращения: 2021-05-07).

29. Buneman P., Fernandez M, Suciu D. UnQL: A Query Language and Algebra for Semistructured Data Based on Structural Recursion // The VLDB Journal.

— 2000. — Vol. 9. — Pp. 76-110.

30. Impala: A Modern, Open-Source SQL Engine for Hadoop / K. Marcel, A. Behm, V. Bittorf et al. // 7th The biennial Conference on Innovative Data Systems Research(CIDR). — 2015.

31. Structural optimization of a full-text n-gram index using relational normalization / M.S. Kim, K.Y. Whang, J.G. Lee, M.J. Lee // The VLDB Journal. — 2008. — Vol. 17. — Pp. 1485-1507.

32. Pinto Y. A framework for systematic database de-normalization // Global Journal of Computer Science and Technology (GJCST). — 2009. — Vol. 9. — Pp. 44-52.

33. Mior M. J. Automated Schema Design for NoSQL Databases // Proceedings of the 2014 SIGMOD PhD Symposium. — 2014.

34. NoSE: Schema Design for NoSQL Applications / M. J. Mior, K. Salem, A. Aboulnaga, R. Liu // IEEE Transactions on Knowledge and Data Engineering. — 2017. — Vol. 29. — Pp. 2275-2289.

35. Bigtable: A Distributed Storage System for Structured Data / F. Chang, J. Dean, S. Ghemawat et al. // ACM Trans. Comput. Syst. — 2008. — Vol. 26.

— Pp. 4-26.

36. Lakshman A., Malik P. Cassandra: A Decentralized Structured Storage System // SIGOPS Oper. Syst. Rev. — 2010. — Vol. 44. — Pp. 35-40.

37. Perfopticon: Visual Query Analysis for Distributed Databases / D. Moritz, D. Halperin, B. Howe, J. Heer // Computer Graphics Forum. — 2015. — Vol. 34, no. 3. — Pp. 71—-80.

38. Jiao D. SQL to NoSQL : What to do and How // IOP Conference Series: Earth and Environmental Science. — 2019. — Vol. 234. — P. 012080.

39. Query optimization for massively parallel data processing / S. Wu, F. Li, S. Mehrotra, B.C. Ooi // Proceedings of the 2nd ACM Symposium on Cloud Computing. — ACM, 2011. — Pp. 1-13.

40. Parallelizing Query Optimization / W.S. Han, W. Kwak, J. Lee et al. // Proc. VLDB Endow. — 2008. — Vol. 1, no. 1. — Pp. 188-200.

41. Query Optimization of Distributed Database Based on Parallel Genetic Algorithm and Max-Min Ant System / W. Ban, J. Lin, J. Tong, S. Li // 2015 8th International Symposium on Computational Intelligence and Design (ISCID). — 2015.

42. Codd E. F. A relational model of data for large shared data banks // Communications of the ACM. — 1970. — Vol. 13, no. 6. — Pp. 377-387.

43. Date C.J. An Introduction to Database Systems 8th Edition. — Lebanon, Indiana, USA: Alfred Waller Ltd, 2003. — 1328 pp.

44. Beynon-Davies P. Relational Database Design (Information Systems S.). — Alfred Waller Ltd, 1992.

45. Connolly T., Begg C. Database Systems: A Practical Approach to Design, Implementation, and Management 6th Edition. — Harlow, Essex: Pearson, 2014. — 1440 pp.

46. Codd E. Further Normalization of the Data Base Relational Model // Research Report / RJ / IBM / San Jose, California. — 1971. — Vol. RJ909.

47. Stonebraker M. SQL Databases v. NoSQL Databases // Commun. ACM. — 2010. — Vol. 53, no. 4. — Pp. 10-11.

48. McAfee A., Brynjolfsson E. Big Data: The Management Revolution // Harvard business review. — 2Q12. — Vol. 9Q. — Pp. 6Q-67.

49. The Dangers of Replication and a Solution / J. Gray, P. Helland, P. O'Neil, D. Shasha // SIGMOD Rec. — 1996. — Vol. 25, no. 2. — Pp. 173-182.

5Q. Helland P. Life Beyond Distributed Transactions: An Apostate's Opinion // Queue. — 2Q16. — Vol. 14, no. 5. — Pp. 69-98.

51. Cattell R. Scalable SQL and NoSQL Data Stores // SIGMOD Rec. — 2Q11.

— Vol. 39, no. 4. — Pp. 12-27.

52. Шичкина Ю. А. Методы построения схемы и выполнения запросов в базах данных. — Санкт-Петербург: СПб.: ЛЭТИ, 2Q16. — 2Q6 с.

53. Клеменков П.А. Построение новостного рекомендательного сервиса реального времени с использованием NoSQL СУБД // Информатика и ее применения. — 2Q13. — № 7. — С. 14-21.

54. Meier A., Kaufmann M. SQL and NoSQL Databases. — Berkeley, CA: Apress, 2QQ2. — 698 pp.

55. Rossel G., Manna A. A Modeling methodology for NoSQL Key-Value databases // Database Systems Journal. — 2Q17. — Vol. 8. — Pp. 12-18.

56. Harrison G. Document Databases // Next Generation Databases / Ed. by G. Arrison. — Berkeley, CA.: Apress, 2Q15. — Pp. 53-63.

57. Apte T., Ingle M., Goyal A.K. Column-Store Databases: Approaches and Optimization Techniques // International Journal of Data Mining and Knowledge Management Process. — 2Q13. — Vol. 3. — Pp. 83-89.

58. Agrawal S., Patel A. A Study on Graph Storage Database of NoSQL // International Journal on Soft Computing, Artificial Intelligence and Applications.

— 2Q16. — Vol. 5. — Pp. 33-39.

59. DB-Engines Ranking. — URL: https://db-engines.com/en/ranking (дата обращения: 2Q21-Q5-Q7).

60. Pavlo A., Aslett M. What's Really New with NewSQL? // SIGMOD Rec. — 2016. — Vol. 45, no. 2. — Pp. 45-55.

61. Multidimensional Analysis of NewSQL Database Systems / I. Chereja, S.M.L. Hahn, O. Matei, A. Avram // Software Engineering and Algorithms / Ed. by R. Silhavy. — Cham: Springer, 2021. — Pp. 221-236.

62. TokuDB. — URL: https://github.com/percona/tokudb-engine (дата обращения: 2021-05-07).

63. NouDB. — URL: https://nuodb.com/ (дата обращения: 2021-05-07).

64. FoundationDB. — URL: https://github.com/apple/foundationdb (дата обращения: 2021-05-07).

65. Кириллов В.В., Громов Г.Ю. Введение в реляционные базы данных. — Санкт-Петербург: СПб.: БХВ-Петербург, 2009. — 464 с.

66. Пушников А.Ю. Введение в системы управления базами данных. Часть 1. Реляционная модель данных: Учебное пособие. — Уфа: Изд-е Башкирского ун-та., 1999. — 108 с.

67. William H. I. Information Engineering for the Practitioner: Putting Theory into Practice (Yourden Press Computing Series). — Englewood Cliffs, New Jersey: Prentice Hall, 1988. — 294 pp.

68. Menninger D. Breaking All the Rules: An Insider's Guide to Practical Normalization // Data Based Advis. — 1995. — Vol. 13, no. 1. — Pp. 116-121.

69. Westland J.C. Economic incentives for database normalization // Information Processing & Management. — 1992. — Vol. 28, no. 5. — Pp. 647-662.

70. Bolloju N., Toraskar K. Data Clustering for Effective Mapping of Object Models to Relational Models // J. Database Manage. — 1997. — Vol. 8, no. 4. — Pp. 16-23.

71. McFadden F.R., A.H. Jeffrey. Modern Database Management. — Redwood City, California: The Benjamin/Cummings Publishing Company, 1994.

72. Hanus M. To Normalize or Denormalize, That is the Question // Int. CMG Conference. — 1993.

73. Rodgers U. Denormalization: Why, What, and How? // Database Programming & Design. — 1989. — Vol. 12. — Pp. 46-53.

74. Integrating a knowledge-based component into a physical database design system / C.E. Dabrowski, D.K. Jefferson, J.V. Carlis, S.T. March // Information & Management. — 1989. — Vol. 17, no. 2. — Pp. 71-86.

75. Coleman G. Normalizing not only way // Computerworld. — 1989. — Vol. 12.

— Pp. 63-64.

76. Кузнецов С. Д., Посконин А. В. Системы управления данными категории NoSQL // Программирование. — 2014. — № 6. — С. 34-47.

77. Dash D., Polyzotis N., Ailamaki A. CoPhy: A Scalable, Portable, and Interactive Index Advisor for Large Workloads // Proc. VLDB Endow. — 2011. — Vol. 4, no. 6. — Pp. 362-372.

78. Schnaitter K., Polyzotis N. Semi-Automatic Index Tuning: Keeping DBAs in the Loop // Proc. VLDB Endow. — 2012. — Vol. 5, no. 5. — Pp. 478-489.

79. Automatic Index Selection for Large-Scale Datalog Computation / P. Subotic, H. Jordan, L. Chang et al. // Proc. VLDB Endow. — 2018. — Vol. 12, no. 2.

— Pp. 141-153.

80. Li L., Gruenwald L. Self-managing online partitioner for databases (SMOPD): a vertical database partitioning system with a fully automatic online approach // Proceedings of the 17th International Database Engineering & Applications Symposium. — IDEAS '13. — 2013. — Pp. 168-173.

81. Kaizen: A Semi-Automatic Index Advisor / I. Jimenez, H. Sanchez, Q.T. Tran, N. Polyzotis // Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. — SIGMOD '12. — 2012. — Pp. 685-688.

82. Naik S. TIER: Table index evaluator and recommender — A proposed model to improve transaction performance in distributed heterogeneous database //

2017 International Conference on Soft Computing and its Engineering Applications (icSoftComp). — 2017. — Pp. 1-8.

83. Boronski R., Bocewicz G. Indexes driven mechanism for grouped SQL queries // Pomiary, Automatyka, Robotyka. — 2013. — Vol. 2. — Pp. 135-145.

84. Boronski R., Bocewicz G. Relational Database Index Selection Algorithm // Computer Networks. CN 2014. Communications in Computer and Information Science / Ed. by A. Kwiecien, P. Gaj, P. Stera. — Cham: Springer, 2014. — Vol. 431. — Pp. 338-347.

85. Ankur S., Felix M. S., Jens D. The Case for Automatic Database Administration using Deep Reinforcement Learning. — URL: https://arxiv. org/abs/1801.05643 (дата обращения: 2021-05-07).

86. Active Learning for ML Enhanced Database Systems / L. Ma, B. Ding, S. Das, A. Swaminathan // Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. — SIGMOD '20. — 2020. — Pp. 175-191.

87. Automatically Indexing Millions of Databases in Microsoft Azure SQL Database / S. Das, M. Grbic, I. Ilic et al. // Proceedings of the 2019 International Conference on Management of Data. — SIGMOD '19. — 2019. — Pp. 666-679.

88. AI Meets AI: Leveraging Query Executions to Improve Index Recommendations / B. Ding, S. Das, R. Marcus et al. // Proceedings of the 2019 International Conference on Management of Data. — SIGMOD '19. — 2019. — Pp. 1241-1258.

89. Sadri Z, Gruenwald L., Lead E. DRLindex: Deep Reinforcement Learning Index Advisor for a Cluster Database // Proceedings of the 24th Symposium on International Database Engineering & Applications. — IDEAS '20. — 2020.

90. Gabriel P. L., Felipe M. Automated Database Indexing using Model-free Reinforcement Learning. — URL: https://arxiv.org/abs/2007.14244 (дата обращения: 2021-05-07).

91. Apache HBase. — URL: http://hbase.apache.org/. (дата обращения: 2021-05-07).

92. DataStax. — URL: http:// www.datastax. com/. (дата обращения: 2021-05-07).

93. Only Aggressive Elephants Are Fast Elephants / J. Dittrich, J.A. Quiane-Ruiz, S. Richter et al. // Proc. VLDB Endow. — 2012. — Vol. 5, no. 11. — Pp. 1591-1602.

94. Riak. — URL: http://basho.com/riak/. (дата обращения: 2021-05-07).

95. HIndex. — URL: https://github.com/Huawei-Hadoop/hindex. (дата обращения: 2021-05-07).

96. Gao X., Qiu J. Supporting Queries and Analyses of Large-Scale Social Media Data with Customizable and Scalable Indexing Techniques over NoSQL Databases // 2014 14th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing. — IDEAS '20. — 2014. — Pp. 587-590.

97. Chopade R., Pachghare V. MongoDB Indexing for Performance Improvement // ICT Systems and Sustainability. Advances in Intelligent Systems and Computing / Ed. by M. Tuba, S. Akashe, A. Joshi. — Singapore: Springer, 2020. — Vol. 1077. — Pp. 338-347.

98. Park C.S, Kim M.H, Lee Y.J. Usability-based caching of query results in OLAP systems // Journal of Systems and Software. — 2003. — Vol. 68, no. 2. — Pp. 103-119.

99. Kalnis P., Papadias D. Proxy-server architectures for OLAP // Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data. — SIGMOD '01. — 2001. — Pp. 367-378.

100. Baralis E., Paraboschi S., Teniente E. Materialized Views Selection in a Multidimensional Database // Proceedings of the 23rd International Conference on Very Large Data Bases. — VLDB '97. — 1997. — Pp. 156-165.

101. Watanabe Y, Kitagawa H. Query result caching for multiple event-driven continuous queries // Inf. Syst. — 2010. — Vol. 35, no. 1. — Pp. 94-110.

102. Data Quality and Query Cost in Pervasive Sensing Systems / D.J. Yates, E. M Nahum, J. F. Kurose, P.J. Shenoy // Sixth Annual IEEE International Conference on Pervasive Computing and Communications (PerCom 2008). — 2008. — Pp. 195-205.

103. Active semantic caching to optimize multidimensional data analysis in parallel and distributed environments / H. Andrade, T.M. Kurc, A. Sussman, J.H Saltz // Parallel Comput. — 2007. — Vol. 33, no. 7-8. — Pp. 497-520.

104. Mershad K.W, Artail H. CODISC: Collaborative and distributed semantic caching for maximizing cache effectiveness in wireless networks // J. Parallel Distributed Comput. — 2011. — Vol. 71, no. 3. — Pp. 495-511.

105. Abbani N., Artail H. Protecting data flow anonymity in mobile ad hoc networks that employ cooperative caching // Ad Hoc Networks. — 2015. — Vol. 26. — Pp. 69-87.

106. O'Neil E. J, O'Neil P. E, Weikum G. The LRU-K Page Replacement Algorithm for Database Disk Buffering // SIGMOD Rec. — 1993. — Vol. 22. — Pp. 297-306.

107. Aldibaja I., Suleiman A. Improving GDFS Web Cache Algorithm Using Semantic Similarity Measures // International Journal of Computer Science Trends and Technology. — 2017. — Vol. 5. — Pp. 6-11.

108. Visual Evaluation of SQL Plan Cache Algorithms / J. Kossmann, M. Dreseler, T. Gasda et al. // Databases Theory and Applications / Ed. by J. Wang, G. Cong, J. Chen, J. Qi. — Berkeley, CA.: Springer, Cham, 2018. — Pp. 350-353.

109. Michiardi P., Carra D., Migliorini S. Cache-Based Multi-Query Optimization for Data-Intensive Scalable Computing Frameworks // Information Systems Frontiers. — 2021. — Vol. 23. — Pp. 35-51.

110. Keller A., Basu J. A predicate-based caching scheme for client-server database architectures // The VLDB Journal. — 1996. — Vol. 5, no. 1. — Pp. 35-47.

111. Shim J., Scheuermann P., Vingralek R. Dynamic caching of query results for decision support systems // Proceedings. Eleventh International Conference on Scientific and Statistical Database Management. — 1999. — Pp. 254-263.

112. Mosin S. V., Zykin S. V. Truth space method for caching database queries // Modelirovanie i Analiz Informatsionnykh Sistem. — 2015. — Vol. 22, no. 2. — Pp. 248-258.

113. Lu H., Ooi B., Tan K. Query processing in parallel relational database systems.

— Los Alamitos, Calif: IEEE Press., 1994. — 382 pp.

114. Leslie H. Optimizing parallel query plans and execution // COMPCON Spring '91 Digest of Papers. — 1991. — Pp. 105-109.

115. Ganguly S., Hasan W., Krishnamurthy R. Query Optimization for Parallel Execution // Proceedings of the 1992 ACM SIGMOD International Conference on Management of Data. — 1992.

116. Zeller H., Graefe G. Parallel Query Optimization // Encyclopedia of Database Systems / Ed. by L. Liu, M.T. Ozsu. — Boston, MA: Springer US, 2009. — Pp. 2035-2038.

117. Wang H., Sun Y. Experience with Parallel Database Servers on Distributed Computing Platforms // MAS. — 2002.

118. Oracle9i Database Online Documentation, Release 2 (9.2). — URL: https: //docs.oracle.com/cd/A97630_01/index.htm (дата обращения: 2021-05-07).

119. Шевский В.С., Шичкина Ю.А. Анализ способов параллельного выполнения запросов к реляционным базам данных // Известия СПбГЭТУ «ЛЭТИ». — 2018. — № 9. — С. 45-53.

120. В.И. Мунерман. Реализация параллельной обработки данных в облачных системах // Современные информационные технологии и ИТ-образование.

— 2017. — Т. 13, № 2. — С. 57-63.

121. Database Query Optimization Based on Parallel Ant Colony Algorithm / W. Zheng, X. Jin, F. Deng et al. // IEEE 3rd International Conference on Image, Vision and Computing (ICIVC). — 2018.

122. Tushar M., Sanjay M. Oracle Parallel Processing. — California, USA: O'Reilly, 2000. — 268 pp.

123. Bouganim L., Dageville B., Valduriez P. Adaptive parallel query execution in DBS3 // Advances in Database Technology.EDBT 1996. Lecture Notes in Computer Science / Ed. by P. Apers, M. Bouzeghoub, Gardarin G. — Berlin, Heidelberg: Springer, 1996. — Vol. 1057. — Pp. 479-484.

124. Rahm E. Parallel Query Processing in Shared Disk Database Systems // SIG-MOD Rec. — 1993. — Vol. 2, no. 4. — Pp. 32-37.

125. Query Processing in a Parallel Object-Relational Database System / O. Michael, M. Wei, M. Hong, M. S. Ubell // IEEE Computer Society Technical Committee on Data Engineering. — 1996.

126. Chen P.P. The entity-relationship model—toward a unified view of data // ACM Trans. Database Syst. — 1976. — Vol. 1. — Pp. 9-36.

127. Меликов А. В. Применение теории множеств для организации данных исходной реляционной базы данных // Прикаспийский журнал: управление и высокие технологии. — 2011. — № 4. — С. 16-22.

128. Короткова М. А. Теория множеств и отношений. — Москва: Москва : НИЯУ МИФИ, 2016. — 72 с.

129. И.А. Фомина, С.А. Исаев. Реляционная алгебра. Язык SQL: Методические указания по курсам "Теория информационных систем" и "Базы данных". — Нижний Новгород: ННГУ им. Н.И. Лобачевского, 2005. — 26 с.

130. Optimization of relational databases schemas by means of n-tuple algebra / J. Shichkina, A. Degtyarev, B. Kulik, A. Fridman // AIP Conference Proceedings. — 2017. — Vol. 1863, no. 1.

131. Shichkina Y, Kupriyanov M., Shevsky V. The Application of Graph Theory and Adjacency Lists to Create Parallel Queries to Relational Databases // Internet of Things, Smart Spaces, and Next Generation Networks and Systems. NEW2AN 2018, ruSMART 2018. Lecture Notes in Computer Science / Ed. by

O. Galinina, S. Andreev, S. Balandin, Y. Koucheryavy. — Cham: Springer, 2018. — Vol. 11118. — Pp. 138-149.

132. Shichkina Y. Approaches to Speed up Data Processing in Relational Databases // Procedia Computer Science. — 2019. — Vol. 150. — Pp. 131-139.

133. Shichkina Y, Kupriyanov M, Al-Mardi M. Optimization Algorithm for an Information Graph for an Amount of Communications // Internet of Things, Smart Spaces, and Next Generation Networks and Systems. NEW2AN 2018, ruSMART 2016. Lecture Notes in Computer Science / Ed. by O. Galinina, S. Balandin, Y. Koucheryavy. — Cham: Springer, 2016. — Vol. 9870. — Pp. 50-62.

134. Mahajan D, Blakeney C, Zong Z. Improving the energy efficiency of relational and NoSQL databases via query optimizations // Sustainable Computing: Informatics and Systems. — 2019. — Vol. 22. — Pp. 120-133.

135. The Query Translation Landscape: a Survey / M. Mami, D. Graux, H. Thakkar et al. // ArXiv. — 2019. — Vol. abs/1910.03118.

136. Hursch C.J, Hursch J.L. SQL: the structured query language. — PA, United States: TAB Books, 1988. — 184 pp.

137. Chamberlin D.D., Boyce R. F. SEQUEL: A structured English query language // Proceedings of the 1974 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control. — 1974.

138. Справочник по Transact-SQL. — URL: https://docs.microsoft.com/ ru-ru/sql/t-sql/language-reference?view=sql-server-ver15 (дата обращения: 2021-05-07).

139. MongoDB. — URL: https://www.mongodb.com/ (дата обращения: 2021-05-07).

140. Parker Z, Poe S, Vrbsky S.V. Comparing NoSQL MongoDB to an SQL DB // Proceedings of the 51st ACM Southeast Conference. — 2013.

141. The MongoDB 5.0 Manual. — URL: https://docs.mongodb.com/manual/ (дата обращения: 2021-05-07).

142. Köhler Reinhard. Quantitative Syntax Analysis. — PA, United States: De Gruyter Mouton, 2012. — 224 pp.

143. PyParsing - A Python Parsing Module. — URL: https://github.com/ pyparsing/pyparsing (дата обращения: 2021-05-07).

144. Harkins S.S., Martin W. P. R. SQL: Access to SQL Server. — Berkeley, CA: Apress, 2002. — 698 pp.

145. Studio3T. — URL: https://studio3t.com/ (дата обращения: 2021-05-07).

146. Mongify. — URL: https://github.com/anlek/mongify (дата обращения: 2021-05-07).

147. TPC-H Vesion 2 and Version 3. — URL: http://www.tpc.org/tpch/ (дата обращения: 2021-05-07).

ПРИЛОЖЕНИЕ А - Свидетельства о государственной регистрации программы для ЭВМ

РФСШЙОШСТ ФВДИРАЩШШ

СВИДЕТЕЛЬСТВО

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

№ 2021680392

Трансляция тестовой базы данных из формата реляционной базы данных в документную (Translation of a test database from a relational database format to a document database)

Правообладатель: Федеральное государственное автономное образовательное учреждение высшего образования «Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В.И. Ульянова (Ленина)» (СПбГЭТУ «ЛЭТИ») (RU)

Авторы: Шичкина Юлия Александровна (RU), Ха Ван Муон (VN)

Заявка № 2021669368

Дата поступления 01 декабря 2021 Г.

Дата государственной регистрации

в реестре программ для эвм 09 декабря 2021 г.

Руководитель Федеральной службы по интеллектуальной собственности

Сертификат OX02A5CFBCOOB1ACF59A40A2F08092E9A118 Владелец Ивлиев Григорий Петрович

Действителен с'15.0^021 по 15.01.2035

Г.П. Ивлиев

ПРИЛОЖЕНИЕ Б - Коды запросов «Q1-Q5» к базе данных «TPC - H» на MySQL и MongoDB

Запрос Q1:

- На MySQL:

select

l_returnflag , l_linestatus ,

sum( l_quantity ) as sum_qty ,

sum( l_extendedprice ) as sum_base_price ,

sum( l_extendedprice * (1 — l_discount)) as sum_disc_price , sum( l_extendedprice * (1 — l_discount) * (1 + l_tax)) as sum_charge, avg (l_quantity) as avg_qty , avg (l_extendedprice ) as avg_price , avg (l_discount) as avg_disc , count (*) as count_order from

lineitem where

l_shipdate <= '1998 — 09 — 02' group by

l_returnflag , l_linestatus order by

l_returnflag , l_linestatus

- Для варианта 1:

db. getCollection("V") . aggregate ([ {

" $match" : { "L_SHIPDATE" : { "$lte": new Date(1998, 12, 1) }}

}, {

"$group" : {

" _id" : { "L_RETURNFLAG" :" $L_RETURNFLAG" , "L_LINESTATUS" : "

$L_LINESTATUS"},

"sum_qty" : { "$sum" : "$L_QUANTITY"}, " sum_base_price" : { "$sum" : "$L_EXTENDEDPRICE"},

" sum_disc_price" : { "$sum" :

{ "Smultiply" : [ "$L_EXTENDEDPRICE

",{ "Ssubtract" : [1, "$L_DISCOUNT" ]} ] }

},

"sum_charge" : { "Ssum" :

{"Smultiply" : [ "$L_EXTENDEDPRICE" ,{" Ssubtract" : [1, "SL_DISCOUNT" ]} , {"Sadd" : [1, "$L_TAX"]}] }}, " avg_qty" : { "Savg" : "SL_QUANTITY"}, " avg_price" : { "Savg" : "SL_EXTENDEDPRICE"}, " avg_disc" : { "Savg" : "SL_DISCOUNT"},

" count_order" : { "Ssum" : 1} }

},

{ Ssort : {"_id.L_RETURNFLAG" : 1, " _id. L_LINESTATUS" : 1}}])

- Для варианта 2:

db. getCollection(" lineitem ") . aggregate ([ {

"Smatch" : { "L_SHIPDATE" : { "Slte": new Date(1998, 12, 1) }}

}, {

"Sgroup" : {

" _id" : { "L_RETURNFLAG" :" SL_RETURNFLAG" , "L_LINESTATUS" : "

SL_LINESTATUS"},

"sum_qty" : { "Ssum" : "SL_QUANTITY"}, " sum_base_price" : { "Ssum" : "SL_EXTENDEDPRICE"},

" sum_disc_price" : { "Ssum" :

{ "Smultiply" : [ "SL_EXTENDEDPRICE

",{ "Ssubtract" : [1, "SL_DISCOUNT" ]} ] }

},

"sum_charge" : { "Ssum" :

{"Smultiply" : [ "SL_EXTENDEDPRICE" ,{" Ssubtract" : [1, "SL_DISCOUNT" ]} , {"Sadd" : [1, "SL_TAX" ]}] }}, " avg_qty" : { "Savg" : "SL_QUANTITY"}, "avg_price" : { "Savg" : "SL_EXTENDEDPRICE"}, " avg_disc" : { "Savg" : "SL_DISCOUNT"},

" count_order" : { "Ssum" : 1} }

},

{ Ssort : {"_id.L_RETURNFLAG" : 1, " _id. L_LINESTATUS" : 1}}])

- Для варианта 3 без вложенных документов:

db. getCollection("V3") . aggregate ([ {

"Smatch" : { "L_SHIPDATE" : { "Slte": new Date(1998, 12, 1) }}

}, {

"Sgroup" : {

" _id" : { "L_RETURNFLAG" :" SL_RETURNFLAG" , "L_LINESTATUS" : "

SL_LINESTATUS"},

"sum_qty" : { "Ssum" : "SL_QUANTITY"}, "sum_base_price" : { "Ssum" : "SL_EXTENDEDPRICE"},

" sum_disc_price" : { "Ssum" :

{ "Smultiply" : [ "SL_EXTENDEDPRICE

",{ "Ssubtract" : [1, "SL_DISCOUNT" ]} ] }

},

"sum_charge" : { "Ssum" :

{"Smultiply" : [ " Sl_extendedprice " , {" Ssubtract" : [1, "SL_DISCOUNT" ]} , {"Sadd" : [1, "SL_TAX" ]}] }}, " avg_qty" : { "Savg" : "SL_QUANTITY"}, "avg_price" : { "Savg" : "SL_EXTENDEDPRICE"}, " avg_disc" : { "Savg" : "SL_DISCOUNT"},

" count_order" : { "Ssum" : 1} }

},

{ Ssort : {" _id .L_RETURNFLAG" : 1, " _id. L_LINESTATUS" : 1}}]) Для варианта 3 с вложенными документами:

db. getCollection("V3") . aggregate ([ {

"Smatch" : { " Orders . lineitem .L_SHIPDATE" : { "Slte": new Date(1998, 12, 1)

}} }, {

"Sgroup" : {

" _id" : { "L_RETURNFLAG" :" SOrders . lineitem .L_RETURNFLAG" , " L_LINESTATUS" : "SOrders.lineitem. L_LINESTATUS" } ,

"sum_qty" : { "Ssum" : " SOrders . lineitem .L_QUANTITY" } , " sum_base_price " : { "Ssum" : " SOrders . lineitem .L_EXTENDEDPRICE

" sum_disc_price" : { "Ssum" :

{ "Smultiply" : [ " SOrders . lineitem .

L_EXTENDEDPRICE" ,{ "Ssubtract" : [1, " SOrders . lineitem .L_DISCOUNT" ] }] }

},

"sum_charge" : { "Ssum" :

{"Smultiply" : [ " SOrders . lineitem . L_EXTENDEDPRICE" ,{" Ssubtract" : [1, " SOrders . lineitem .L_DISCOUNT" ]} , {"Sadd" : [1, "SOrders . lineitem .L_TAX"]}] }},

" avg_qty" : { "Savg" : " SOrders . lineitem .L_QUANTITY" } , "avg_price" : { "Savg" : " SOrders . lineitem . L_EXTENDEDPRICE" } , "avg_disc" : { "Savg" : " SOrders . lineitem .L_DISCOUNT" } ,

" count_order" : { "Ssum" : 1} }

},

{ Ssort : {" _id .L_RETURNFLAG" : 1, " _id. L_LINESTATUS" : 1}}])

Запрос Q2:

- На MySQL:

select

s_acctbal , s_name, n_name, p_partkey , p_mfgr , s_address , s_phone, s_comment from part , supplier , partsupp , nation , region where

p_partkey = ps_partkey and s_suppkey = ps_suppkey and p_size = 15 and p_type like '%BRASS' and s_nationkey = n_nationkey and n_regionkey = r_regionkey and r_name = 'EUROPE' and ps_supplycost = ( select

min (ps_supplycost) from

partsupp , supplier , nation , region where

p_partkey = ps_partkey and s_suppkey = ps_suppkey and s_nationkey = n_nationkey and n_regionkey = r_regionkey and r_name = 'EUROPE'

)

order by

s_acctbal desc , n_name, s_name, p_partkey limit 100

- Для варианта 1:

db. getCollection("V") . aggregate( [

{

"$match" : {

"P_SIZE " : 1 7 ,

"P_TYPE" : { " $regex " : " BRASS " } , "R_NAME" : "EUROPE" , "SR_R_NAME" : "EUROPE"

}

}, {

" Sproject": {

"S_ACCTBAL" : 1 , "S_NAME" : 1 , "SN_N_NAME" : 1 , "P_PARTKEY" : 1 , "P_MFGR" : 1 , " S_ADDRESS " : 1 , "S_PHONE" : 1 , "S_COMMENT" : 1 , "PS_SUPPLYCOST" : 1

}

}, {

"Ssort " : {

"S_ACCTBAL": -1, "SN_N_NAME" : 1 , "S_NAME" : 1 , "P_PARTKEY" : 1

}

}])

- Для варианта 2:

db. getCollection (" part ") . aggregate ([ {

" Smatch " : {

"Sand " : [

{" Sexpr " : { "Seq": ["SP_SIZE" , 30]}}, {"P_TYPE" :{ " Sregex " : "BRASS"}}

]

}

}, {

" Slookup " : {

" from " : " partsupp " ,

let" : { " p_PARTKEY" :" $P_PARTKEY" } , pipeline ": [

{" $match ": { "$expr": { " $eq ": [" SPS_PARTKEY"

PARTKEY

{

"Slookup" :{

" from ":" supplier " ,

"let" : { " ps_SUPPKEY":" SPS_SUPPKEY" } , "pipeline " : [

{ "Smatch": { " Sexpr " :

{ "Seq": [" SS_SUPPKEY" , "SSps_SUPPKEY" ] }}},

{

" Slookup ": {

" from

":" nation " ,

" let "

: { " s_NATIONKEY":" SS_NATIONKEY" } , pipeline " : [

{"Smatch":{" Sexpr " : { "Seq": [" $N_NATIONKEY" , " $$s_NATIONKEY"]}}},

1 Slookup ": {

i from ":" region

let ": { " n_REGIONKEY":" SN_REGIONKEY" } ,

pipeline " : [

{" Smatch " :

' Sand " : [

{ " Sexpr " : { " Seq " : [" SR_REGIONKEY"

n_REGIONKEY" ] } }

{ "Sexpr": { "Seq": [" SR_NAME" , "EUROPE"]}}]

as " : " region

{

{

}

}

},

I" Sunwind " : " Sregion "}

" as

nation"

}

},

I" Sunwind " : " Snation "}

],

" as " i" supplier"

}

},

I " Sunwind ":" Ssupplier " }

],

" as " : " partsupp "

}

}, I

" Sunwind " : " Spartsupp "

}, I

" Sproject":

I

" partsupp . supplier .S_ACCTBAL" : 1 , " partsupp . supplier .S_NAME" : 1 , " partsupp . supplier . nation .N_NAME" : 1 , "P_PARTKEY" : 1 , "P_MFGR" : 1 ,

" partsupp . supplier .S_ADDRESS" : 1 , " partsupp . supplier .S_PHONE" : 1 , "partsupp . supplier .S_COMMENT" : 1 , "partsupp . PS_SUPPLYCOST " : 1

}

}, I

"Ssort " :

I

"partsupp . supplier .S_ACCTBAL" : -1, " partsupp . supplier . nation .N_NAME" : 1 , " partsupp . supplier .S_NAME" : 1 , "P_PARTKEY" : 1

}])

- Для варианта 3 без вложенных документов:

use TPCH_100mb_V2 var before = new Date()

db. getCollection("V2") . aggregate( [

{

"$match" : {

"P_SIZE ": 1 7 ,

"P_TYPE": { " $regex ":" BRASS" } , "SR_R_NAME": "EUROPE"

}

}, {

" Sproject": {

"S_ACCTBAL": 1 , "S_NAME" : 1 , "SN_N_NAME": 1 , "P_PARTKEY": 1 , "P_MFGR" : 1 , " S_ADDRESS": 1 , "S_PHONE": 1 , "S_COMMENT": 1 , "PS_SUPPLYCOST": 1

}

}, {

"Ssort " : {

"S_ACCTBAL": -1, "SN_N_NAME": 1 , "S_NAME" : 1 , "P_PARTKEY": 1

}

} ])

var after = new Date() execution_mills = after - before

- Для варианта 3 с вложенными документами:

use TPCH_ 1Gb_V3_Embedded

var before = new Date()

db. getCollection("V2") . aggregate(

[

{

"$match" : {

" Partsupp . Part . P_SIZE " : 17 , " Partsupp . Part .P_TYPE" : { " $regex " : " BRASS" } , " Nation . Region .R_NAME" : "EUROPE"

}

}, {

" Sproject": {

"S_ACCTBAL" : 1 ,

"S_NAME" :1 ,

"Nation .N_NAME" : 1 ,

"P_PARTKEY" : 1 ,

" Partsupp . Part .P_MFGR" : 1 ,

" S_ADDRESS " : 1 ,

"S_PHONE" : 1 ,

"S_COMMENT" : 1 ,

" Partsupp .PS_SUPPLYCOST" : 1

}

}, {

"Ssort " : {

"S_ACCTBAL": -1, "S_NAME" : 1 ,

" Partsupp . Part .P_PARTKEY" : 1

}

} ])

var after = new Date() execution_mills = after — before

Запрос Q3:

- На MySQL: