José Alexandre Macedo Blog

Conheça neste artigo as características dos modelos de graph database, aplicações que podem se beneficiar,  soluções na literatura e implementações disponíveis

Introdução

As redes complexas, segundo Newman (2003), são redes de dados onde a relação entre os elementos é tão ou mais importante que os próprios elementos. Ao representá-las através de grafos a relação é descrita pelas arestas e os elementos pelos vértices. Alguns exemplos destas redes são as sociais, as de informação e as biológicas.

A utilização de modelos de bancos de dados tradicionais para o armazenamento das redes complexas pode gerar gargalos na manipulação dos dados, devido a grande quantidade de dados normalmente existente. Além disso, os modelos tradicionais não são capazes de explorar os fundamentos dos grafos com respeito aos seus relacionamentos, vizinhanças e padrões (Angles, R. & Gutierrez, C. 2008). Com isso, surge a necessidade de um modelo de banco de dados baseado em grafos e capaz de corresponder às peculiaridades das redes complexas.

O modelo de graph database, como é chamado, caracteriza-se por ter estruturas de dados onde os esquemas e/ou instâncias são modelados como grafos (Angles, R. & Gutierrez, C. 2008).

De acordo com Angles, R. & Gutierrez, C. (2008) existem diversas vantagens ao se utilizar este modelo, entre elas:

· Graph database permite uma modelagem mais natural dos dados no contexto das redes complexas;

· Possibilidade de consultas que aproveitam a estrutura dos grafos, através de operações na linguagem de consulta que permitam, por exemplo, retornar os vértices adjacentes;

· Ao trabalhar diretamente com grafos e operações relacionadas, o nível de abstração aumenta facilitando a manipulação dos dados pelo desenvolvedor;

· As implementações dos modelos podem disponibilizar algoritmos de grafos eficientes para a realização de operações específicas.

Aplicações para os Graph Database

Existem diversas aplicações que podem se beneficiar do modelo dos graph databases, Newman (2003), dividiu-as em quatro classes distintas, sendo elas: redes sociais; redes de informação; redes de tecnologia; e redes biológicas.

· Redes Sociais: Neste tipo de rede os vértices são compostos por pessoas ou grupos e as arestas descrevem os relacionamentos. Alguns exemplos são as redes de amizades (Facebook e Orkut) e negócios (Linkedin);

· Redes de Informação: As redes deste grupo modelam fluxos de informações. Elas são utilizadas, por exemplo, para relacionar citações de trabalhos acadêmicos e para relacionar classes de palavras em dicionários de sinônimos;

· Redes Tecnológicas: Estas redes são caracterizadas pela importância dos aspectos geográficos e espaciais das estruturas. Alguns exemplos são: redes de computadores, redes de energia elétrica, rotas aéreas, redes de telefonia, sistemas de informação geográfico (GIS).

· Redes Biológicas: As redes biológicas representam informações biológicas onde existe um grande volume de dados de difícil gestão e análise. Estas redes ocorrem na regulação de genes, mapas metabólicos, estruturas químicas e relacionamento entre as espécies.

A utilização de uma estrutura de armazenamento em grafos traz benefícios para as redes complexas porque várias das operações necessárias podem ser realizadas aproveitando os algoritmos propostos na Teoria dos Grafos. Como exemplo: GIS utiliza operações de métricas para descobrir a distancia entre as entidades e o diâmetro da rede; as redes reguladoras utilizam o grau dos vizinhos próximos para descobrir a correlação de pares forte; e as redes sociais podem utilizar medidas para encontrar, por exemplo, o caminho mínimo entre duas pessoas da rede.

Definição de Modelo para Graph Databases

Os modelos de graph database têm como fundamentação formal definições matemáticas de grafos. Alguns exemplos destas definições que podem ou não ser utilizadas são, grafos direcionados ou não-direcionados, rotulados ou não rotulados, hipergrafos e etc. Um modelo de graph database é composto de três componentes básicos, uma estrutura de dados adequada, uma linguagem de transformação e restrições de integridade.

A estrutura de dados de um modelo se preocupa em definir como as informações serão armazenadas. Angles, R. & Gutierrez, C. (2008) mostraram que existe certo consenso na literatura com relação a este aspecto, onde de uma forma geral as estruturas para os esquemas e as instâncias são grafos rotulados e direcionados. Estes autores ainda mostraram que alguns trabalhos definem modelos utilizando a orientação a objetos.

A linguagem de transformação é responsável por definir como os dados devem ser manipulados. Esta linguagem deve incluir as operações que poderão ser realizadas, levando em consideração as características dos grafos como arestas, vizinhos, subgrafos e conectividade.

As restrições de integridade são responsáveis pela consistência dos dados. Essas restrições podem ser organizadas em consistência esquema-instância, integridade referencial e dependências de inclusão e funcional. Alguns exemplos de restrições são os rótulos com nomes únicos e restrições de digitações nos vértices.

Os componentes básicos que foram descritos são a base para os diversos modelos de graph database presentes na literatura. A seguir será apresentada uma visão geral destes modelos.

Graph Database na Literatura

As pesquisas iniciais relacionadas ao modelo de graph database não são recentes, sendo que, os primeiros estudos datam 1975 através de Roussopoulos e Mylopoulos que propuseram uma rede semântica para armazenar dados. Entretanto, apenas nas últimas décadas implementações dos modelos passaram a ser utilizadas em pesquisas e empresas, principalmente devido ao crescimento das redes sociais e redes biológicas.

O trabalho de Angles, R. & Gutierrez, C. (2008) realizou uma revisão bibliográfica sobre este assunto e mapeou de acordo com a Figura 1 o histórico do desenvolvimento dos modelos de graph database. Nesta Figura os vértices indicam modelos e as arestas citações.

Figura 1 Histórico do desenvolvimento dos modelos de Graph Database (Angles, R. & Gutierrez, C. 2008)

Apesar dos primeiros estudos terem iniciados em 1975 a maioria dos trabalhos apareceram muitos anos depois. Algumas das razões para isso foram que a comunidade envolvida com banco de dados passou a trabalhar com dados semiestruturados e pesquisadores que trabalhavam com graph databases passaram a trabalhar com aplicações particulares como dados espaciais, web e documentos.

A Figura 1 permite observar que alguns modelos foram extremamente influentes, entre eles o GOOD (Gyssens et al. 1990). Esta proposta utiliza a orientação a objetos e teve como objetivo ser uma base teórica para sistemas na qual manipulação e representação são baseados em grafos.

Existem propostas que utilizam generalizações de grafos apenas para modelagem de dados. Contudo, foram Levene & Poulovassilis (1990) que introduziram o modelo de banco de dados baseado em grafos chamado de Hypernode.

Cada trabalho presente na Figura 1 possui características específicas dos modelos, entretanto, este artigo não pretende explorar os detalhes de cada um, caso deseje conhecer mais sobre os modelos consulte o trabalho de Angles, R. & Gutierrez, C. (2008).

Graph Database na Prática

Os modelos de graph database precisam ser instanciados e transformados em ferramentas para que seja possível sua utilização. Com base nesta necessidade surgiram diversas propostas de implementações para graph databases. Entre estas propostas, algumas (Neo4J, OrientDB, DEX, InfoGrid, HyperGraphDB, InfiniteGraph e Sones) foram analisadas.

O estudo permitiu verificar que a maioria das implementações utilizam modelos de graph data base baseados em propriedades e na orientação a objetos. Apenas o Neo4J e OrientDB se preocupam em garantir as propriedades da ACID (atomicidade, consistência, integridade e durabilidade). As ferramentas Neo4J, DEX e HyperGraphDB disponibilizam algoritmos clássicos para a manipulação dos dados, entre eles, o algoritmo de Dijkstra é o único presente nas três ferramentas. Algumas das implementações são open source, entre elas, Neo4J, InfoGrid e Sones. Uma tabela comparando todas as características está disponível abaixo.

Conclusão

A utilização de graph databases para otimizar a manipulação de dados das redes complexas se mostrou uma opção adequada e não tão recente, apesar de ter ganho destaque na última década graças ao crescimento das redes sociais e biológicas.

Os modelos de graph database apresentam como características comuns a estrutura de dados, a linguagem de transformação e as restrições de integridade. Conhecemos também os vários modelos presentes na literatura, com destaque para alguns extremamente influentes como o GOOD.

Por fim, o artigo apresentou uma comparação entre as ferramentas disponíveis no mercado para trabalhar com graph database em redes complexas. Conhecemos as ferramentas disponíveis, com destaque para o Neo4J, uma implementação open source, capaz de garantir ACID e com diversos algoritmos disponíveis.

Referencias

ANGLES, R. & GUTIERREZ, C. Survey of graph database models. ACM Comput. Surv., 40(1):1–39, 2008.

IMPLEMENTAÇÕES GRAPH DATABASES. Acessado em: 27/06/2011

ww.graph-database.org/implementations/

ALGORITMOS DO NEO4J. Acessado em: 28/06/2011

http://docs.neo4j.org/chunked/stable/graph-algo.html

ALGORITMOS DO DEX. Acessado em: 28/06/2011

http://sparsity-technologies.com/downloads/javadoc.pdf

ALGORITMOS DO HYPERGRAPHDB. Acessado em: 28/06/2011

http://www.hypergraphdb.org/docs/javadoc/org/hypergraphdb/algorithms/GraphClassics.html