Использование графовых баз данных в целях оптимизации анализа
…
3
Здесь
source_node
— строковое значение, идентифицирующее вер-
шину-источник ребра;
destination_node
— строковое значение, иден-
тифицирующее вершину-назначение ребра;
link_id
— целочисленное
64-разрядное число, дополнительный атрибут на ребре.
Без ограничения общности можем считать, что такой схемы дан-
ных достаточно для представления практически любого графа [1],
поскольку атрибут
link_id
может являться ссылкой на строку в таб-
лице реляционной БД, содержащей все параметры ребра. Аналогич-
ный атрибут можно ввести и для каждой вершины, но для наших це-
лей он не требуется.
Одна из самых актуальных задач, возникающих при анализе бил-
линговой информации, — поиск соседних вершин какой-либо опре-
деленной заданной вершины. Помимо непосредственно прямых со-
седей вершины может возникнуть потребность узнать всех соседей,
находящихся на определенном удалении от заданной вершины. Для
тестирования графовых БД была реализована функция, в которую
передается какое-либо
n
, а возвратиться должны все соседние вер-
шины, до которых минимальное расстояние не больше
n
. Обозначим
кратчайшее расстояние от вершины
s
до какой-либо вершины
v
функцией
s
v
σ ( )
. Тогда результатом работы реализованной функции
будет множество
{
}
|
( ) ,
.
bfs
s
V v v n v V
= σ ≤ ∈
Еще одна востребованная операция обработки биллинговой ин-
формации, на которой проводилось тестирование, — пересечение
найденных соседей двух вершин. Эта задача была реализована как
функция, в которую передается список вершин, для каждой вершины
находятся ее соседи не дальше определенного уровня, после чего для
всех пар вершин проводится пересечение таких множеств. Если пе-
ресечение проводилось для найденных соседей вершин
s
1
и
s
2
, ре-
зультатом будет множество
{
} {
}
1
2
sec
|
( ) ,
|
( ) ,
.
i
t
s
s
V
v v n v V v
v n v V
= σ ≤ ∈ ∩ σ ≤ ∈
Обзор графовых баз данных.
Проведем краткий обзор рассмат-
риваемых графовых БД с целью узнать их основные возможности, с
помощью которых проводилось тестирование.
Sones GraphDB.
Эта графовая БД разработана компанией Sones в
2009 г. и поддерживалась до конца 2011 г., после чего компания
обанкротилась. За время поддержки была выпущена версия 2.1, до-
ступная в двух вариантах: версия Community распространяется по
лицензии AGPL v3, для коммерческих же проектов необходимо при-
обретать версию Enterprise. Кроме того, важное отличие платной вер-
