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

Во введении приведена актуальность темы диссертационной работы, освещены объект и
предмет исследования, сформулированы цель и задачи исследования, основные положения, выносимые
на защиту, прописана научная новизна, описана теоретическая и практическая значимость результатов.
В первой главе представлен обзор существующих подходов к трансляции баз данных из одного
формата в другой и оптимизации работы с базами данных NoSQL. В результате анализа существующих
типов баз данных установлено, что реляционные БД являются самыми распространенными формами
хранения данных. За последние десятилетия все больше используются на практике NoSQL и NewSQL.
При переходе от реляционных баз данных к NoSQL или NewSQL актуальной является проблема
автоматического преобразования форматов данных и сбора данных из баз данных разного типа.
Установлено, что для оптимизации структур баз данных существуют разные подходы, но отсутствуют
методы оптимизации структуры NoSQL-баз данных, таких как документные или семейство столбцов.
Проанализированы методы оптимизации запросов к базам данных. Установлено, что в качестве
механизмов ускорения выполнения запросов используются индексирование и кэширование, а также
параллельное выполнение запросов. Для оптимизации структуры запросов используются методы,
основанные на анализе плана выполнения запроса. Формализованных методов оптимизации запросов с
учетом метаданных об их структуре и схеме БД не существует.
Анализ существующих подходов к формализованному представлению запросов показал, что
наиболее эффективными являются методы теории графов и теории множеств.
Во второй главе описываются методы оптимизации структуры базы данных NoSQL.
Приведен метод определения структуры коллекций для баз данных типа «ключ-документ» по
заданному набору свойств и запросов и описана методика применения разработанных методов для
трансляции и проектирования баз данных типа «ключ-документ».
Входными данными метода являются: Совокупность свойств объектов, хранимых в базе
данных. Если задача заключается в трансляции реляционной базы данных в MongoDB, то в качестве
совокупности свойств объекта выступает множество полей всех таблиц.
Пусть Tr – это таблица реляционной базы данных, где r – номер таблицы, r = 1…k , k –
число таблиц; T( r , j ) – это поле в таблице Tr , где j – номер поля, j = 1…rn , rn – число полей вr -й
таблице. Тогда множество полей одной таблицы – это множество вида:
Tr = {T( r , j ) , j = 1, 2,…, rn }(1)
Множество всех полей реляционной базы данных будет определяться по формуле:
M = {T( r , j ) , r = 1, 2,…, k | T( r , j )  T( q ,i ) , r , q  k , j  rn , i  qn }(2)
Длина | M | множества M – это количество его элементов.
Совокупность множеств полей, входящих в запрос:
Si = {T( r , j ) , r  k , j  rn }(3)
где i – номер запроса (i = 1,2,…m) , m – число запросов к базе данных.
Выходные данные метода: Совокупность множеств коллекций документов с заданными
полями:
Vi = {T( r , j ) , r  k , j  rn }
удовлетворяющих условиям:
V1  V2  V3 = (4)
V1  V2  V3 = M = kr =1Tr(5)
(Si )(V j )( Si V j , Si Vi , i  j )(6)
где i – номер коллекции (i = 1,2,…, l ) , l – число коллекций.
Метод формирования коллекций для базы данных в формате MongoDB
Шаг 1. Создать множества полей таблиц и запросов по формулам (2) – (3). Число множеств
будет равно числу таблиц.
Шаг 2. Выбрать поля, которые не участвуют в запросах. Для этого:
2.1. Для каждого поля составить множества запросов, в которых это поле участвует в любой
части конструкции:
T ‘( r , j ) = {Si , i = 1… p, p  m | T( r , j )  Si }
где m – число запросов,r– номер таблицы, r = 1…k , k–число таблиц, j – номер поля в
таблице, j = 1…rn , rn – число полей в r -й таблице.
2.2. Все поля T( r , j ) , для которых длина множества | T ‘( r , j ) |= 0 , могут быть включены в
единую коллекцию MongoDB:
V1 = {T( r , j ) , r  k , j  rn || T ‘( r , j ) |= 0}
Примечание 1.: коллекции должны формироваться с учетом связей между таблицами.
Шаг 3. Выбрать поля, которые участвуют только в одном запросе, т.е. | T ‘( r , j ) |= 1 .
Если для любого T( r , j )  Si выполняется условие | T ‘( r , j ) |= 1 , то все поля T( r , j ) множества
S i должны войти в новую коллекцию:
V p = {T( r , j ) , r  k , j  rn | T( r , j )  Si & | T( r , j ) |= 1}, p  1(7)
Шаг 4. Убрать из рассмотрения все поля, которые вошли в коллекции V1 и V p на шагах 1-3.
Шаг 5. Составить коллекции из полей, к которым обращается несколько запросов.
5.1. Составить множество рассматриваемых запросов: I = {Si } , i = 1…m , где m – число
рассматриваемых запросов.
5.2. Составить попарные пересечения множеств Si  I .
S ‘k = Si  S j , i  j; i, j = 1,2,…,| I |; k = 1,2,…, C|2I |
| I |!| I | (| I | −1)
где C|I | ==
.
| (| I | −2) |!2!2
5.3. Для полученных не пустых пересечений составить множество P из запросов, входящих
в эти пересечения:
P = {S ‘i || S ‘i | 0, i  k , k = 1,2,…, C|2I |}
5.4. Найти разность множеств: I − P .
Если I − P   , то новая коллекция будет состоять из всех полей, входящих в запросы
разности множеств I − P .
Vp =| P|
i =1S ‘i , S ‘i  P
5.5. Положить I = P .
5.6. Из полученных пересечений найти новые не пустые пересечения по правилу:
if (( Si  S j ) & ( S j  Sk )), find ( Si  S j  S k )
или в общем виде:
S ”k = S ‘i  S ‘ j , if Sm | ( Sm  S ‘i & Sm  S ‘ j , i = j ); i, j = 1,2,…,| I |; k = 1,2,…, C|2I |
5.7. Повторить шаги 5.3 – 5.7 до тех пор, пока не останется одно пересечение, т.е. длина
множества не станет равной 1: | I |= 1 .
Шаг 6. В новое отношение включить все поля, вошедшие в последнее единственное
пересечение и не вошедшие в другие пересечения:
p
Vp+1 = M −Vi
i =1
Шаг 7. Конец метода.
Принцип применения предлагаемого метода для разного рода преобразования структуры
базы данных приведен на рис.1.
Постановка задачи

ДаНет

Существует
исходная БД

КонсолидацияПребразование

Цель
Сбор атрибутов в одно
отношение РБД. Приведение к
ДаНетнормальной форме
Подготовка атрибутов
РБД -> NoSQL

Сбор атрибутов в одноСбор атрибутов в одно
отношение РБД.отношение РБД. Приведение к
Приведение кнормальной форме
нормальной форме

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

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

Конец

Рис. 1. Применение метода определения коллекций в БД типа ключ-документ
Разработанный метод определения коллекций может быть применен для:
1) создания эффективной структуры новой базы данных типа ключ-документ;
2) трансляции данных из реляционной базы данных в базу данных типа ключ-документ;
3) трансляции данных из произвольной базы данных в базу данных типа ключ-документ;
3) консолидации баз данных.
Есть и другие возможности для применения данного метода, такие как создание временных
коллекций и т.п.
Далее в главе приведено описание метода определения структуры вложенных
документов в базах данных NoSQL типа «ключ-документ»:
Определение вложенных документов для двух отношений
Пусть:
1. даны два отношения реляционной модели, на основе которых строится схема не
реляционной БД типа «ключ-документ»: T1 и T2 :
T1{T11 , T12 ,…, T1k }
T2{T21 , T21 ,…, T2 n }
где Ti , j – это j-е поле i-го отношения, k – число полей в отношении T1 , n – число полей в
отношении T2 .
2. по методу определения коллекций в БД типа ключ-документ получена некоторая
коллекция:
Q{T11 ,…, T1m , T21 ,…, T2 r }, m  k , r  n
3. отношения T1 и T2 имеют связи типа 1 −  :
4. в отношениях определены ключи, принадлежащие данной коллекции:
T1 : T11 , T12 ,…, T1s1 , где 1  s1  m
T2 : T21 , T22 ,…, T2 s 2 , где 1  s 2  r
Выходные данные метода: новая структура коллекции Q т.е. Q ‘  Q
Решение: рассмотрим возможные варианты запросов к коллекции Q :
a) S1{T11 ,…, T1s1 ,…, T1i } – запрос, который обращается только к атрибутам одного
отношения, например T1 ;
b) S 2{T11 ,…, T1s1 ,…, T1i , T21 ,…, T2 s 2 ,…, T2 j } – запрос, который обращается к атрибутам обоих
отношений T1 и T2 .
Случай a). Так как предполагается, что схема РБД с отношениями T1 и T2 изначально
находится в нормальной форме, как минимум Бойса-Кодда или 4NF, то аномалия избыточности в
этой схеме сведена к минимуму и вложенных документов в данной коллекции быть не может.
Случай b). Связь 1 −  подразумевает, что одному кортежу из отношения T1 может
соответствовать множество кортежей из отношения T2 . Отсюда следует, что для того, чтобы
избежать хранения избыточных данных в коллекции , необходимо все атрибуты отношения T2 ,
участвующие в запросе S2 , выделить во вложенный документ. При этом возможны два случая:
b1): таких запросов как S2 всего один для коллекцииQ . В этом случае новая структура
коллекцииQ примет вид: Q ‘{T11 ,…,T1s1 ,…,T1m ,T ‘2 :{T21,…,T2 s 2 ,…,T2 j },…,T2 r } , где T ‘2 – это имя
нового ключа для вложенного документа.
b2): таких запросов как S2 более одного для коллекцииQ . В этом случае необходимо найти
множество T ‘2 , которое будет объединением всех множеств атрибутов отношения T2 , входящие в
запросы типа S2 . Формализовано это будет так: пусть есть совокупность запросов типа S2 к
коллекцииQ:
S21{T11 ,…, T1s1 , T21 ,…, T2 s 2 ,…, T2 j1};
…
S2t {T11 ,…, T1st ,…, T1it , T21 ,…, T2 s 2 ,…, T2 jt }
тогда вложенный документ будет состоять из атрибутов множества:
T ‘2 = {T21 ,…, T2 s 2 ,…, T2 j1}  …  {T21 ,…, T2 s 2 ,…,2 jt } = {T21 ,…, T2 s 2 ,…, T2 j1 ,…,T2 jt }
В этом случае новая структура коллекции примет вид:
Q ‘{T11 ,…, T1s1 ,…, T1m , T ‘2 :{T21 ,…, T2 s 2 ,…, T2 j1 ,…, T2 jt },…, T2 r }
где ′2 – это имя нового ключа для вложенного документа.
Примечание 2. Допустим, что после отделения всех атрибутов отношения T2 , участвующих в
запросах типа S2 , в новое множество T ‘2 , остались еще атрибуты отношения T2 , которые в запросе S2
не участвуют. Назовем это множество T ”2 = T2 − T ‘2 . Это может означать, что-либо к атрибутам
множества ″2 обращается отдельный запрос типа a) и опять же это означает, что коллекция построена
не оптимально. Либо, если коллекция построена оптимально, существует запрос, который обращается
одновременно к атрибутам T ‘2 и T ”2 . Последнее означает, что отделить атрибуты T ‘2 в отдельный
документ нельзя, т.к. это усложнит запросы типа a), обращающиеся одновременно к атрибутам T ‘2 и
T ”2 . Поэтому, во вложенный документ можно выделить полностью все атрибуты отношения T2 ,
входящие в коллекцию Q . Сформулируем унифицированное для всех случаев правило создания
вложенного документа с учетом примечания 2.
Правило 1. Пусть есть совокупность запросов типа S2 к коллекции Q :
S21{T11 ,…, T1s1 ,…, T1i1 , T21 ,…, T2 s 2 ,…,T2 j1};
…
S2t {T11 ,…, T1st ,…, T1it , T21 ,…, T2 s 2 ,…, T2 jt }
и совокупность запросов типа S1 к атрибутам отношения T2 из коллекцииQ:
S11{…, T2i1 ,…};
…
S1r {…, T2ir ,…}
Пусть T ‘2 ( S 2 ) – это множество всех атрибутов, участвующих в запросах типа S2 :
T ‘2 ( S2 ) = {T21 ,…, T2 s 2 ,…, T2 j1}  …  {T21 ,…, T2 s 2 ,…, T2 jt } = {T21 ,…, T2 s 2 ,…,T2 j1 ,…,T2 jt }
Пусть T ‘2 ( S1i ) – это множество всех атрибутов, участвующих в i-м запросе типа S1 . Тогда
– это множество тех атрибутов, которые необходимо присоединить ко вложенному документу, т.к.
они участвуют в запросе с некоторыми другими атрибутами отношения T2 , которые уже включены
во вложенный документ.
Т.к. запросов типа S1 может быть некоторое количество, то необходимо найти объединение
таких атрибутов. Пусть всего запросов S1 количество равное Vs , тогда вложенный документ будет
состоять из атрибутов множества:
Vs
T ‘2 = T ‘2 ( S2 ) ( S1i  ( S1i − T ‘2 ( S2 )))
i =1
T ”2 = T2 − T ‘2
В этом случае новая структура коллекции Q примет вид:
Q ‘{T11 ,…, T1s1 ,…, T1m , T ‘2 :{T ‘2 ( S2 ) Vs
i −1( S1i  ( S1i − T ‘2 ( S 2 )))}, T ”2} (8)
где T ‘2 — это имя нового ключа для вложенного документа.
Примечание 3. В данном методе была рассмотрена только связь типа 1 −  . Если схема
реляционной базы данных была изначально приведена к нормальной форме BCNF, 3NF или 4NF,
то других связей между отношениями T1 и T2 быть не может. Но, если по каким-либо причинам,
например проведенной денормализации схемы РБД, это связи существуют, то:
– для связи типа 1-1 вложенных документов быть не может, ввиду однозначности соответствия
каждому кортежу из отношения 1 единственного кортежа из отношения 2 .
– для связи типа  −  вложенные документы строятся по тому же принципу, что и для связи
1−  .
Определение вложенных документов для трех отношений с одним главным
отношением и двумя подчиненными
Пусть:
1. даны три отношения реляционной модели, на основе которых строится схема не
реляционной БД типа ключ-документ: T1 , T2 и T3 :
T1{T11 , T12 ,…, T1k }
T2{T21 , T22 ,…, T2 n }
T3{T31 , T32 ,…, T3m }
где Tij – это j-е поле i-го отношения, k – число полей в отношении T1 , n – число полей в
отношении T2 , m – число полей в отношении T3 .
2. по методу определения коллекций в БД типа ключ-документ получена некоторая
коллекция:
Q{T11 ,…, T1k ‘ , T21 ,…, T2 n ‘ , T31 ,…, T3m ‘}, k ‘  k , n ‘  n, m ‘  m
3. отношения T1 , T2 и T3 имеют связи типа 1 −  : или более схематично на рис. 2.а.

T1T1
1
T2T3T2T3
a)б)
Рис. 2. Связи между отношениями T1 , T2 и T3
4. в отношениях определены ключи, принадлежащие данной коллекции:
T1 : T11 , T12 ,…, T1s1 , где 1  s1  k ‘
T2 : T21 , T22 ,…, T2 s 2 , где 1  s 2  n ‘
T3 : T31 , T32 ,…, T3 s 3 , где 1  s3  m ‘
Выходные данные. Новая структура коллекции Q , т.е. Q ‘  Q
Решение: рассмотрим возможные варианты запросов к коллекции :
a) S1{T11 ,…, T1s1 ,…, T1i } – запрос, который обращается только к атрибутам одного отношения,
например 1 ;
b) S 2{T11 ,…, T1s1 ,…, T1i , T21 ,…, T2 s 2 ,…, T2 j } – запрос, который обращается к атрибутам двух
отношений T1 , T2 или T1 , T3 .
c) S3{T11 ,…, T1s1 ,…, T1i , T21 ,…, T2 s 2 ,…, T2 j , T31 ,…, T3 s 3 ,…, T3 r } – запрос, который обращается к
атрибутам всех трех отношений T1 , T2 и T3 .
d) S 4{T21 ,…, T2 s 2 ,…, T2 j , T31,…, T3 s 3 ,…, T3r } – запрос, который обращается к атрибутам двух
отношений T2 и T3 .
Случай a). Этот случай рассмотрен выше при определении вложенных документов для
коллекции, построенной из атрибутов двух отношений и показано, что вложенных документов в
данной коллекции быть не может.
Случай b). Этот случай рассмотрен выше при определении вложенных документов для
коллекции, построенной из атрибутов двух отношений по формуле (8) и показано, что новая
структура коллекции Q примет вид:
Vs

Q ‘ T11 ,…, T1s1 ,…, T1m , T ‘2 : T ‘2 ( S 2 )  ( S1i  ( S1i − T ‘2 ( S 2 )))  , T ”2 
i =1
где T ‘2 – это имя нового ключа для вложенного документа, атрибуты T ‘2 ( S 2 ) – это все
атрибуты отношенияT2 , входящие в запросы типа S2 к коллекции Q , Vs – количество запросов
типа S1 , T ”2 – множество атрибутов, которые не вошли в T ”2 из всех атрибутов отношения T2 ,
входящих в коллекцию Q .
Примечание 4. Если коллекция Q была построена в соответствии с методом определения
коллекция к БД типа ключ-документ, то множество T ”2 =  .
Случай c). Этот случай является обобщением случая b) с двух отношений со связью 1 − 
на две пары отношений со связью 1 −  . В данном случае новая структура коллекции Q примет
вид:

 11
Q ‘
1m2
T ,…,T , T ‘ : T ‘ ( S )  Vs ( S  ( S − T ‘ ( S ))) , T ” , 
23i =1 1i1i23 2
 (9)
Vs

T ‘3 : T ‘3 ( S3 )  i =1 ( S1i  ( S1i − T ‘3 ( S3 ))) , T ”3



где T ‘2 , T ‘3 – это имена новых ключей для вложенных документов; атрибуты T ‘2 ( S3 ) – это
все атрибуты отношения T2 , входящие в запросы типа 3 к коллекции Q ; атрибуты T ‘3 ( S3 ) – это
все атрибуты отношения T3 , входящие в запросы типа 3 к коллекции Q , Vs – количество запросов
типа S1 , T ”2 – множество атрибутов, которые не вошли в T ‘2 из всех атрибутов отношения T2 ,
входящих в коллекцию Q , T ”3 – множество атрибутов, которые не вошли в T ‘3 из всех атрибутов
отношения T3 , входящих в коллекцию Q .
Случай d). Т.к. запрос к атрибутам отношений T2 и T3 может быть выполнен только через
атрибуты отношения T1 , то этот случай в результате сводится к случаю c).
Определение вложенных документов для трех отношений с двумя главными
отношениями и двумя подчиненными
Входные данные. Пусть: 1. даны три отношения реляционной модели, на основе которых
строится схема не реляционной БД типа ключ-документ T1 , T2 и T3 :
T1{T11 , T12 ,…, T1k }
T2{T21 , T22 ,…, T2 n }
T3{T31 , T32 ,…, T3m }
где Tij – это j-е поле i-го отношения, k – число полей в отношении T1 , n – число полей в
отношении T2 , m – число полей в отношении T3 .
2. по методу определения коллекций в БД типа ключ-документ получена некоторая
коллекция:
Q{T11 ,…, T1k ‘ , T21 ,…, T2 n ‘ , T31 ,…, T3m ‘}, k ‘  k , n ‘  n, m ‘  m
3. отношения T1 , T2 и T3 имеют связи типа 1 −  : или более схематично на рис. 2.б.
4. в отношениях определены ключи, принадлежащие данной коллекции:
T1 : T11 , T12 ,…, T1s1 , где 1  s1  k ‘
T2 : T21 , T22 ,…, T2 s 2 , где 1  s 2  n ‘
T3 : T31 , T32 ,…, T3 s 3 , где 1  s3  m ‘
Выходные данные: Новая структура коллекцииQ , т.е. Q ‘  Q .
Решение: рассмотрим возможные варианты запросов к коллекцииQ:
a) S1{T11 ,…, T1s1 ,…, T1i } – запрос, который обращается только к атрибутам одного отношения,
например T1 ;
b) S 2{T11 ,…, T1s1 ,…, T1i , T21 ,…, T2 s 2 ,…, T2 j } – запрос, который обращается к атрибутам двух
отношений T1 , T2 или T2 , T3 .
c) S3{T11 ,…, T1s1 ,…, T1i , T21 ,…, T2 s 2 ,…, T2 j , T31 ,…, T3 s 3 ,…, T3 r } – запрос, который обращается к
атрибутам всех трех отношений T1 , T2 и T3 .
d) S 4{T11 ,…, T1s1 ,…, T1i , T31 ,…, T3 s 3 ,…, T3 r } – запрос, который обращается к атрибутам двух
отношений T1 и T3 .
Случай a). Этот случай рассмотрен выше при определении вложенных документов для
коллекции, построенной из атрибутов двух отношений и показано, что вложенных документов в
данной коллекции быть не может.
Случай b). Этот случай рассмотрен выше при определении вложенных документов для
коллекции, построенной из атрибутов двух отношений и показано, что новая структура коллекции
Q примет вид (9).
Случай c). Этот случай является обобщением случая b) с двух отношений на три отношения.
В данном случае новая структура коллекции Q примет вид:
T ‘ ( S )  Vs ( S  ( S − T ‘ ( S ) ) ),
 2 3i =1 1i1i23
Q ‘ T11 ,…,T1m , T ‘2 :  , T ”2 , T ”3  (10)



T ‘3 : T ‘3 ( S3 )  i =1 ( S1i  ( S1i − T ‘3 ( S3 ) ) ) 

Vs



где T ‘2 , T ‘3 – это имена новых ключей для вложенных документов; атрибуты T ‘2 ( S3 ) – это
все атрибуты отношения T2 , входящие в запросы типа 3 к коллекции Q ; атрибуты T ‘3 ( S3 ) – это
все атрибуты отношения T3 , входящие в запросы типа 3 к коллекции Q , Vs – количество запросов
типа S1 , T ”2 – множество атрибутов, которые не вошли в T ‘2 из всех атрибутов отношения T2 ,
входящих в коллекцию Q , T ”3 – множество атрибутов, которые не вошли в T ‘3 из всех атрибутов
отношения T3 , входящих в коллекцию Q .
Случай c). Т.к. запрос к атрибутам отношений 1 и 3 может быть выполнен только через
атрибуты отношения 2 , то этот случай в результате сводится к случаю b).
Примечание 5. Если коллекция Q построена более чем для 3-х отношений, то вложенные
документы строятся также как и для трех отношений.
Методика определения структуры вложенных документов в БД типа «ключ-документ»
Прежде чем перейти к методике применения методов определения коллекций с вложенными
документами в БД типа ключ-документ, необходимо сделать несколько примечаний.
Примечание 6. Если в коллекции Q из атрибутов, относящихся к трем отношениям нет
запросов, обращающихся к атрибутам всех трех отношений, то такую коллекцию лучше разбить на
две коллекции.
Рассмотрим отдельно два случая.
Случай 1. Три отношения с одним главным отношением и двумя подчиненными (см.
рис. 2.а).
Если к коллекции Q нет запроса, который обращается к атрибутам всех трех отношений T1
,T2 и T3 :
S3{T11 ,…, T1s1 ,…, T1i , T21 ,…, T2 s 2 ,…, T2 j , T31 ,…, T3 s 3 ,…, T3r }
но, есть запросы, которые обращаются к атрибутам двух отношенийT1 , T2 или T2 , T3 :
S21{T11 ,…, T1s1 ,…, T1i , T21,…, T2 s 2 ,…, T2 j }
S22{T11 ,…, T1s1 ,…, T1i , T31 ,…, T3 s 3 ,…, T3r ,…, T2t }
то вместо формулы (2.9) следует коллекцию Q разбить на две коллекции со вложенными
документами в соответствии с формулой (2.8):

Vs


Q ‘1 T11 ,…, T1s1 ,…, T1m , T ‘2 : T ‘2 ( S21 )  ( S1i  ( S1i − T ‘2 ( S 21 )) )  , T ”2 

i =1

(11)

Vs


Q ‘2 T11 ,…, T1s1 ,…, T1m , T ‘2 : T ‘3 ( S22 )  ( S2i  ( S1i − T ‘3 ( S22 )) )  , T ”3 

i =1

где T ‘2 , T ‘3 – это имена новых ключей для вложенных документов; атрибуты T ‘2 ( S3 ) – это
все атрибуты отношения T2 , входящие в запросы типа 3 к коллекции Q ; атрибуты T ‘3 ( S3 ) – это
все атрибуты отношения T3 , входящие в запросы типа 3 к коллекции Q , Vs – количество запросов
типа S1 , T ”2 – множество атрибутов, которые не вошли в T ‘2 из всех атрибутов отношения T2 ,
входящих в коллекцию Q , T ”3 – множество атрибутов, которые не вошли в T ‘3 из всех атрибутов
отношения T3 , входящих в коллекцию Q .
Случай 2. Три отношения с двумя главными отношениями и двумя подчиненными (см.
рис. 2.б).
Если к коллекции Q нет запроса, который обращается к атрибутам всех трех отношений T1 ,
T2 и T3 :
S3{T11 ,…, T1s1 ,…, T1i , T21 ,…, T2 s 2 ,…, T2 j , T31 ,…, T3 s 3 ,…, T3r }
но, есть запросы, которые обращаются к атрибутам двух отношенийT1 , T2 или T2 , T3 :
S21{T11 ,…, T1s1 ,…, T1i , T21,…, T2 s 2 ,…, T2 j }
S22{T11 ,…, T1s1 ,…, T1i , T31 ,…, T3 s 3 ,…, T3r ,…, T2t }
то вместо формулы (10) следует коллекцию Q разбить на две коллекции со вложенными
документами в соответствии с формулой (2.8):

Vs


Q ‘1 T11 ,…, T1s1 ,…, T1m , T ‘2 : T ‘2 ( S21 )  ( S1i  ( S1i − T ‘2 ( S 21 )) )  , T ”2 

i =1

(12)

Vs


Q ‘2 T11 ,…, T1s1 ,…, T1m , T ‘2 : T ‘3 ( S22 )  ( S2i  ( S1i − T ‘3 ( S22 )) )  , T ”3 

i =1

где T ‘2 , T ‘3 – это имена новых ключей для вложенных документов; атрибуты T ‘2 ( S3 ) – это
все атрибуты отношения T2 , входящие в запросы типа 3 к коллекции Q ; атрибуты T ‘3 ( S3 ) – это
все атрибуты отношения T3 , входящие в запросы типа 3 к коллекции Q , Vs – количество запросов
типа S1 , T ”2 – множество атрибутов, которые не вошли в T ‘2 из всех атрибутов отношения T2 ,
входящих в коллекцию Q , T ”3 – множество атрибутов, которые не вошли в T ‘3 из всех атрибутов
отношения T3 , входящих в коллекцию Q .
С учетом формул (8) – (12) методика определения коллекций со вложенными документами
для БД типа ключ-документ представлена на рис. 4.
Vk – Число коллекций,
Ti – Отношения,
Si – Запросы,
Qi – Коллекции,
R – Связи между отношения

Для каждой коллекции:
i= 1,Vk

Число отношений <3 Число отношений = 2 Максимальное число отношений < Числа отношений в коллекции Формула (8)ДекомпозицияФормулы (9) - коллекции по (11) –(10) (12) Конец Рис. 4. Методика определения вложенных документов В конце главы представлен разработанный метод оптимизации структуры распределенной базы данных NoSQL типа «ключ-документ». Для распределенной базы данных был применен подход, основанный на информационных графах, для исследования зависимостей подзапросов от местоположения и доступности данных в соответствии с заданной схемой распределенной БД и информацией о шардах и репликах. Метод построения информационного графа запроса для распределенной реляционной БД: 1) Каждой таблице РБД поставить в соответствие входную вершину информационного графа. 2) Каждому элементарному подзапросу поставить в соответствие вершину информационного графа. 3) Соединить вершины информационного графа направленными ребрами в соответствии с правилом: если подзапрос А получает данные от таблицы (или подзапроса) В, то соединить вершины А и В направленным ребром от В к А. 4) Адаптация графа под горизонтальный шардинг для случая, когда таблица T распределенной БД разделена на k частей, хранимых на отдельных шардах: a) создать k входных вершин графа, каждая из которых будет соответствовать определенной части таблицы на определенном шарде: Ti , i = 1...k . b) если таблица T была связана ребром с запросом Q , то создать k вершин графа, каждая из которых будет соответствовать запросу Q , выполняемому для определенной части таблицы на определенном шарде: Qi , i = 1...k . Далее возможен один из трех вариантов: 1) Вариант 1. A. все вершины, которые были до этого соединены с вершиной Q , соединить с вершинами Qi , i = 1...k ; B. соединить каждую вершину, соответствующую части таблицы T , с вершиной, соответствующей запросу Q , и выполняемому для данной части таблицы T , т.е. Ti соединить с Qi (пример этого варианта представлен на рис.5.b); C. если вершина Q не являлась выходной вершиной графа, то: создать вершину Q’, которая будет соответствовать запросу по агрегации данных из запросов Qi над частями таблицы Ti . 2) Вариант 2. D. соединить каждую вершину, соответствующую части таблицы T , с вершиной, соответствующей запросу Q , и выполняемому для данной части таблицы T , т.е. Ti соединить с Qi (пример этого варианта представлен на рис.5.с); E. если вершина Q не являлась выходной вершиной графа, то: создать вершину Q ' , которая будет соответствовать запросу по агрегации данных из запросов Qi над частями таблицы Ti ; F. если есть вершины (кроме T ), которые были до этого соединены с вершиной Q , то создать узел Q '' и соединить все вершину и вершину Q ' с вершиной Q '' ; 3) Вариант 3. A. все вершины, которые были до этого соединены с вершиной Q , соединить с вершинами Qi , i = 1...k ; B. соединить каждую вершину, соответствующую части таблицы T , с вершиной, соответствующей запросу Q , и выполняемому для данной части таблицы T , т.е. Ti соединить с Qi (пример этого варианта представлен на рис.5.d); C. если вершина Q не являлась выходной вершиной графа b была связана ребром с запросом Q1 , то создать k вершин графа, каждая из которых будет соответствовать запросу Q1 , выполняемому для определенной части запроса Qi на определенном шарде: Q1i , i = 1...k . D. соединить каждую вершину, соответствующую части запроса Q , с вершиной, соответствующей части запроса Q1 , т.е. соединить Qi c Q1i ; E. если вершина Q1 не являлась выходной вершиной графа, то: создать вершину Q '' , которая будет соответствовать запросу по агрегации данных из запросов Q1i . c) если в графе есть еще таблицы, которые также распределены по шардам, то шаг b) повторяется для каждой такой таблицы. T12 Q12 T1QQ2 Q1Q2T11 Q11 T2 T2 T3 T3 (a)(b) Q12T12Q12Q22 T12Q QQ2Q Q11T11 Q11Q21 T11 T2 T2 T3 T3 (c)(d) Рис. 5. Способы представление запроса к распределенной базе данных с помощью информационного графа Метод построения схемы распределенной базы данных NoSQL типа «ключ-документ»: 1. Построить информационный граф с учетом операций шардинга и репликаций. 2. Привести информационный граф к параллельной форме, минимизирующей передачу данных с шарда на шард с помощью метода оптимизации параллельных алгоритмов по числу коммуникаций. 3. Выполнить действие 1-2 для всех запросов, структура которых должна быть учтена при оптимизации схемы документной базы данных с целью ускорения выполнения этих запросов. 4. На основе метаданных о таблицах, полях, запросах и связях с помощью методов оптимизации схемы документной базы данных с вложенными или без вложенных документов сформировать структуру коллекций документов. 5. Усовершенствовать структуру документов с учетом графов информационных зависимостей запросов, минимизировав число операций объединения данных. В третьей главе приведено описание трансляции запросов формата SQL в формат MongoDB. Предлагаемый нами метод автоматической трансляции запросов из формата SQL в формат MongoDB с учетом структуры баз данных MySQL и MongoDB заключается в следующем: Входными данным являются: код запроса к базе данных MySQL, метаданные о структуре баз данных MySQL и MongoDB. Выходные данные: код запроса к базе данных MongoDB. Шаг 1. Парсинг запроса в формате MySQL 1.1. Парсинг запроса в формате MySQL по формальной грамматике языка SQL-запросов. Результатами парсинга являются токены (слова). 1.2. Формирование списков не ключевых токенов из общего списка токенов, получаемых из парсинга запроса в формате MySQL. Шаг 2. Формирование словаря предложений запроса MongoDB. Шаг 3. Переформирование предложений словаря с учетом структуры базы данных MongoDB. 3.1. Определение структуры базы данных MongoDB. 3.2. Переформирование предложений словаря с учетом структуры базы данных MongoDB. Шаг 4. Синтез выходного запроса из предложений словаря с учетом структуры базы данных MongoDB и на основе синтаксиса функции «aggregate» в MongoDB. В четвертой главе приведено подробное описание разработанных модулей, сведение баз данных для тестирования и тестирование разработанных методов. Для тестирования разработанных метода были спроектированы разные базы данных с разными структурам и использована база данных «TPC - H». Также были сгенерированы разные объемы данных для баз данных. Тестирование метода определения структуры коллекций для нераспределенных баз данных типа ключ-документ с учетом запросов было выполнено с базами «Telecommunication_business» и «TPC - H» с разными объёмами данных. В тестирование рассмотрены три варианты структуры базы данных: каждой таблице в реляционной базе данных поставить в соответствие отдельную коллекцию документов в MongoDB (Вариант 1), из всех таблиц реляционной базы данных сделать одну коллекцию документов в MongoDB(Вариант 2) и создать такой набор коллекций документов в MongoDB, чтобы они наиболее полно подходили под выполняемые запросы (Вариант 3). К базе данных «Telecommunication_business» были выполнены 9 запросы и к базе данных «TPC - H» выполнены запросы «Q1-Q5». На рис.6 приведены графики времени выполнения запросов «Q1-Q5» к базе данных «TPC - H» с разными структурами и разными объемами. Результаты тестирования показали разработанный метод является наиболее оптимальным с точки зрения времени выполнения запроса. Для тестирования метод определения структуры вложенных документов в БД типа ключ- документ использованы проектированные базы данных «Test1 – Test5» и база данных «TPC - H». На рис.7. приведен результат тестирования с базой данных «TPC - H». Для каждой базы рассмотрены две структуры: без вложенных документов и с вложенными документами. Результаты тестирования со спроектированными базами данных и базой данных «TPC - H» показывают эффективность применения разработанного метода определения структуры вложенных документов с учетом связей между объектами в базе данных и структуры запросов, которые к ним выполняются Рис. 6. - Графики времени выполнения запросов «Q1-Q5» к базе данных «TPC - H» с разными структурами и разными объемами Рис. 7. - Графики времени выполнения запросов «Q1-Q5» к базе данных «TPC - H» с разными структурами и разными объемами В тестировании методов оптимизации структуры распределенных баз данных NoSQL рассмотрены три варианты: централизованная база данных, распределенная база данных с наличием шардинга, но при отсутствии репликаций и распределенная база данных с наличием шардов и реплик. Для двух варианта распределённых баз данных, исходный запрос разделен на подзапросы и в зависимости от структур БД оптимизирован план выполнения подзапросов за счет параллельного выполнения. Тестирование выполнено на MySQL и MongoDB с разными объемами баз данных. Результат тестирования (рис. 8) показал, что что максимальное распараллеливание запроса в БД перед объединением результата программой работает быстрее всего. Кроме времени выполнения запросов, в испытании были также протестированы объем памяти при выполнении запросов для всех вариантов. Рис. 8. - Время выполнения запроса для разных вариантов схемы БД MongoDB и объема данных В тестировании исследовались три важных параметра: физическая память, задействованная память ОЗУ и максимальная ОЗУ при выполнении запросов с разными вариантами и разными объемами. Из результатов тестирования (рис. 9) видно, что вариант «распределенная база данных с шардированием и репликацией» использует наибольший объем памяти по сравнению с остальными вариантами. Ускоренный вариант выполнения требует большего объема памяти из-за хранения дубликатов данных. Рис. 9. График ОЗУ при выполнении запросов для разных объемов В заключении сформированы основные результаты диссертационного исследования. ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ 1. Проанализированы существующие подходы к трансляции баз данных из одного формата в другой, а также подходы к оптимизации структуры NOSQL БД и оптимизации запросов к ним. 2. Разработаны методы оптимизации структуры базы данных NoSQL для модели «ключ- документ», основанные на теории множеств и позволяющие автоматизировать процесс построения по заданной совокупности свойств объектов и с учетом их вхождений в запросы к базе данных определить оптимальную структуру базы данных NoSQL типов «ключ-документ» и структуру вложенных документов в этой БД. Методы учитывают тип связей между таблицами реляционной модели. В зависимости от типа связи выведены правила для создания структуры коллекции со вложенными документами. 3. Разработана методика преобразования реляционной базы данных в формат NoSQL типа «ключ-документ» в зависимости от исходных данных, таких как наличие информации о существующей реляционной базе данных, наличия необходимости трансляции исходной базы данных в новый формат, принадлежности реляционной базы данных к нормальной форме. 4. Разработан метод построения схемы распределенной базы данных NoSQL типа «ключ- документ» с учетом информационного графа запроса и структуры распределенной РБД. Метод основан на теории графов и теории множеств и позволяет построить на шардах и репликах оптимальную по скорости выполнения запросов структуру коллекций. 5. Разработан метод трансляции запросов из формата SQL в формат MongoDB с учетом структуры базы данных. Разработанный метод состоит из четырех шагов: парсинг исходного запроса SQL, формирование словаря предложений запроса MongoDB, переформирование предложений словаря с учетом структуры базы данных MongoDB и синтез выходного запроса. 6. Созданы программные модули для тестирования разработанных методов и получены результаты тестирования на сгенерированных и существующих тестовых базах данных, которые показали эффективность разработанных методов.