УДК 004.31.016

Голов В.А.

ГРАФОВЫЕ БАЗЫ ДАННЫХ: ВОЗМОЖНОСТИ И ОБЛАСТЬ ПРИМЕНЕНИЯ

Московский государственный университет приборостроения и информатики

 

В данной статье рассмотрены возможности графовых баз данных (ГБД), описаны области их применения, продемонстрированы типовые проблемы при их реализации и использовании, и предложены способы решения этих проблем.

Ключевые слова: графовые базы данных, база данных, СУБД, NOSQL

This article is devoted to some aspects of graph databases usage. Areas of its use and common problems with it are described, and resolution methods are proposed.

Keywords: graph databases, database, database management system, NOSQL

Базы данных и системы управления ими повсеместно используются в современных информационных технологиях. В базах данных хранят бухгалтерскую и материальную отчетность организации, на web-сервере организации значительная часть информации хранится также в базах данных. Подавляющее большинство используемых баз данных соответствуют  реляционной модели данных, предложенной Э.Ф. Коддом в конце 1960-х гг.

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

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

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

Более сложные структуры, включающие в себя подграфы основного графа, называются доменами [1].

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

К примеру, в фармакологии графовая модель данных может использоваться для исследования мутагенеза [2]. На рисунке 1 представлена формула органического вещества 1,6-динитро-9,10,11,12-тетрагидробензопирен. Задача, стоящая перед исследователями – классифицировать данное вещество как опасное либо безопасное для живых существ с точки зрения влияния вещества на ДНК клеток.

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

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

Рис. 1. Формула 1,6-динитро-9,10,11,12-тетрагидробензопирена.

 

В криминалистике графовые представления данных также применимы. На рисунке 2 показана схема связей причастных к заказному убийству. Для выявления участников, соучастников и заказчиков преступления необходимо обработать огромную массу информации, которая в основном имеет характер связности: «X звонил Y», «N встречался с Z» и так далее. Проработка всех связей лиц, входящих в круг подозреваемых по какому-либо делу, очень важна для пресечения дальнейшей противозаконной деятельности. Такая проработка должна быть выполнена в кратчайшие сроки.

Реляционная модель данных едва ли может предложить достойную структуру хранения и средства обработки для данных такого типа. Графовая же модель прекрасно совместима с таким набором данных.

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

 

Рис. 2. Криминалистическая схема связей причастных к преступлению

 

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

Все реализации СУГБД придерживаются основных принципов транзакций, называемые акронимом ACID – неразрывность или атомарность (atomicity), правильность (correctness), изолированность (isolation) и устойчивостью (durability) [3].

· Неразрывность (Атомарность). Транзакции неразрывны (выполняются по принципу «все или ничего»).

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

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

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

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

·     Neo4j

·     HyperGraphDB

·     NetworkX

·     InfoGrid Graph Database

·     AllegroGraph RDFStore

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

    Тем не менее, при реализации и использовании СУГБД возникают некоторые сложности. Наиболее «болезненные» из них – скорость обхода графа с наличием циклических подграфов и сложность в репликации либо резервном копировании.

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

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

Уже сейчас можно сделать уверенный вывод – у графовых баз данных есть хорошее будущее. Кроме перечисленных выше областей философия графовых БД сейчас активно вторгается на рынок серверов баз данных высоконагруженных проектов. Например, такие гиганты как Google и Facebook отказываются от реляционности в пользу хэш-таблиц и графовых баз данных, поскольку реляционная структура хранения данных не справляется с нагрузкой даже с  помощью агрессивного кэширования, и балансировки нагрузки [4]. Разумеется, хэш-таблицы это не вполне графовые БД, но, тем не менее, они относятся к движению NOSQL (Not Only SQL – «не только SQL»). Это движение не выступает против использования языка SQL, но считает, что применять SQL нужно только в случае необходимости.

Аудитория гигантов Интернет-рынка неуклонно растет, поэтому  рано или поздно архитектура большинства высоконагруженных web-проектов будет использовать все преимущества графовых баз данных

 

Литература:

1. Haixun Wang, Charu C. Aggarwal. Managing and Mining Graph Data. Springer Science+Business Media, 2010 г. — 610 с. На англ. яз.

2. Diane J. Cook, Lawrence B. Holder. Mining graph data. — Wiley-Interscience / A John Wiley & Sons, Inc., Publication, 2007 г. — 479 с. На англ. яз.

3. Дейт, К.Дж. Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2008 г. — 1329 с.

4. Видеофрагмент конференции QCon San-Francisco 2008 [Электронный ресурс]:  содержит рассказ инженера и архитектора компании Facebook Адити Агарвал (Aditya Agarwal) о внутренней архитектуре системы и используемых технологиях.  2008 г. Режим доступа: http://www.infoq.com/presentations/Facebook-Software-Stack