Teoria dos Grafos

Bancos de Dados Orientados a Grafos

Sérgio R. Umlauf1, Gabriel de S. V. Batista¹, Henrique A. Belviso1, Kelseyn Chistian¹, Wesley Rolin¹

1Engenharia e Tecnologia - Universidade Anhembi Morumbi (UAM)
Rua Casa do Ator, 295 - São Paulo - SP - Brasil

umlauf@gmail.com, henrique.albanese@gmail.com, svbgabriel@gmail.com, kelseyn.santos01@etec.sp.gov.br, goiaba@gmail.com  

Abstract. This meta-paper provides a comprehensive view of Graph Databases. Concepts, use, employability and development of this database architecture will be addressed.

Resumo. Esse artigo fornece uma visão abrangente dos Bancos de Dados Orientados a Grafos. Serão abordados os conceitos, uso, empregabilidade e desenvolvimento dessa arquitetura de banco de dados.

1. Grafos

        A teoria dos grafos é um ramo da matemática que estuda as relações entre os objetos de um determinado conjunto. Para tal, são empregadas estruturas chamadas de grafos, G(V,A), onde V é um conjunto não vazio de objetos denominados vértices e A é um conjunto de pares não ordenados de V, chamado arestas.

Dependendo da aplicação, arestas podem ou não ter direção, pode ser permitido ou não arestas ligarem um vértice a ele próprio e vértices e/ou arestas podem ter um peso (numérico) associado. Se as arestas têm uma direção associada (indicada por uma seta na representação gráfica) temos um grafo direcionado, grafo orientado ou digrafo. Um grafo com um único vértice e sem arestas é conhecido como o grafo trivial. Estruturas que podem ser representadas por grafos estão em toda parte e muitos problemas de interesse prático podem ser formulados como questões sobre certos grafos. O desenvolvimento de algoritmos para manipular grafos é um importante tema da ciência da computação.  

2. Motivação para o surgimento dos Bancos de Dados Orientados a Grafos

           Os dados armazenados em bancos são utilizados na mineração para pesquisas em geral, como conhecer um público antes de lançar um novo produto. Uma grande massa de dados pode ser um fator determinante na questão da escalabilidade e em custos de manutenção desses dados.

Bancos de dados relacionais podem ser escalonados, mas quanto maior a quantidade de registros, maior o custo de sua utilização, pois para atender a demanda pode ser necessário o uso de mais máquinas e a contratação de mais profissionais para sua manutenção.

Bancos de dados NoSQL, como os orientados a grafos, permitem uma escalabilidade mais barata e menos trabalhosa, pois exigem máquinas menos potentes e contam com facilidade de manutenção.

3. Como funciona um Banco de Dados Orientado a Grafos

            Como vimos, nós são conectados por meio de relações nomeadas e direcionadas, sendo que tanto os nós quanto os relacionamentos podem ter propriedades. Dentre as diferentes arquiteturas de implementação, dizemos que um BDOG tem capacidade de processamento nativo se ele possuir uma propriedade chamada adjacência livre de índice [Robinson, Webber e Eifrem 2013].

Um motor de banco de dados que utiliza adjacência livre de índice é aquele em que cada nó mantém referências diretas a seus nós adjacentes; cada nó, por conseguinte, atua como um micro-índice dos outros nós próximos. Significa que tempos de consulta não dependem do tamanho total do grafo.

Um motor de BDOG não-nativo, por sua vez, utiliza um índice global para ligar os nós. Estes índices adicionam uma camada a mais à busca nos grafos, aumentando, assim, o custo computacional. Em uma busca em uma base de dados com índices, temos que primeiro fazer uma busca no índice, a um custo de O(log n). Porém, o custo, se quisermos achar os registros realcionados, é O(m log n).

A Figura 1 mostra como relacionamentos eliminam a necessidade de percorrer índices.

[pic 1]

Figura 1. Relacionamentos, ao invés de índices, para buscas

Num BDOG de propósito genérico, relacionamentos podem ser percorridos em ambos os sentidos (de trás para a frente ou de frente para trás) com custo extremamente baixo. Como vemos na Figura 1, para encontrar os amigos de Alice utilizando um grafo, simplesmente seguimos os seus relacionamentos FRIEND de saída, ao custo de O(1) cada. Para encontrar quem tem amizade com Alice, simplesmente seguimos todos os seus relacionamentos FRIEND de entrada, até suas fontes, novamente a um custo de O(1) cada.

4. Comparação com Bancos de Dados Relacionais

            Como já percebemos, o banco de dados orientado a grafos, sua arquitetura é muito diferente do dando banco de dedos relacional. Suas principais diferenças são com o desemprenho, modelagem, programação etc.

Para que seja possível percebemos o desempenho real do banco de dados a grafos é necessário que tenhamos muitos dados para trabalhar, ou quando percebemos que os relacionamentos são importantes quanto os próprios dados guardados. Percebemos também, a necessidade do bando de dados orientado a grafos, quando temos muitas junções para realizar determinada tarefa.

...