Base de datos orientada a Grafos. ¿Qué son y para qué se usan?

20 agosto 2019

Base de datos orientada a Grafos. ¿Qué son y para qué se usan?

by Marcos Martínez Cedillo

¿Qué son las bases de datos orientadas a Grafos? Lo más probable es que hayas empezado a escuchar algo sobre este tipo de bases de datos, que si son capaces de detectar el fraude, que si son las mejores para establecer relaciones de los personajes de GOT (Game of Thrones), que si son capaces de mover millones de relaciones, que si son buenas para sistemas de recomendación, etc…

Si además estás buscando una alternativa a las documentales, tal vez te interese este artículo.

Antes de nada, algo de teoría.

Las bases de datos orientadas a grafos o BDOG tiene su principal característica en que representan la información en vértices y aristas cumpliendo con la disciplina matemática de la Teoría de Grafos, aunque como veremos, no va a ser necesario ser un experto matemático para poder usarlas.

Un grafo estará compuesto por dos elementos: los nodos (vértices) y las relaciones (aristas). Un nodo representa una entidad, en el que almacenaremos piezas de datos o atributos de tipo clave-valor, mientras que las relaciones representan cómo se conectan y se asocian dos nodos.

En algunos fabricantes de motores de BDOG podremos guardar datos y establecer etiquetas en las propias relaciones que nos servirá a posterior en las consultas que realicemos para poder filtrar o buscar información.

“Con la base de datos de tipo grafo podríamos demostrar el concepto teórico de los Seis grados de separación”

Las BDOG pertenecen al grupo de las NoSQL y dentro del teorema de CAP las podríamos englobar dentro de CA (Consistency, Availability) o PA (Partitioning, Availability). Esto puede generar algo de controversia, más adelante veremos los motivos de esta doble asignación.

Las clasificamos como NoSQL por las siguientes características:
  • No utilizan un modelo relacional
  • Carece de un esquema fijo, podemos tener nodos con diferente número de atributos.
  • Mantienen la disponibilidad y acceso de la información
  • Son buenas en modelos en cluster

Sus características principales son:

  • Son multidimensionales, pueden almacenar atributos de diverso tamaño en los nodos
  • Las relaciones pueden almacenar atributos
  • Las relaciones pueden ser sin dirección, unidireccionales y bidireccionales lo que puede convertir la representación a grafos dirigidos, muy útiles en el cálculo de caminos.
  • Tienen alto rendimiento en la búsqueda de resultados y sobre todo en la búsqueda de caminos.

¿En qué contextos las podemos usar?

Las BDOG están pensadas para aquellos ámbitos en donde es importante mantener un modelo extenso y amplio de la relación de la información a la vez que un esquema flexible de los datos. Podemos ver un ejemplo claro en las redes sociales, como Twitter o Facebook, donde tenemos el número de conexiones como las relaciones con nosotros y las personas como nodos del grafo.

“Las bases de datos de grafos no son nuevas, pero solventan un problema subyacente de las documentales”

Podríamos pensar que existen otros tipos de bbdd NoSQL que podrían perfectamente cumplir con las mismas características de un modelo flexible de datos, alta capacidad y velocidad en el tratamiento de la velocidad, como son las documentales, pero que al profundizar en su uso, rápidamente nos daremos cuenta de un problema y es que las bbdd NoSQL Documentales no son buenas en mantener las relaciones de información entre los documentos. Al final, las documentales realizan un encapsulamiento de su API para poder solucionar este problema, caso que ocurre con MongoDB y su “Document Reference” ($refID) que no es más que una referencia a un Embedded Document que apunta a Índice de un bloque de punteros interno.

Por este motivo, si tenemos un modelo de relaciones fuertes, o necesitamos recorrer relaciones de referencias, es más recomendable usar las bases de datos de tipo grafo.

“Los papeles de Panamá y la detección del fraude, son algunos de los ejemplos en las que las podemos utilizar”

A continuación vamos a indicar algunos de los contextos en los que podemos utilizara las BDOG:

Árboles jerárquicos en estructuras organizativas de empresas, donde existen estructuras en forma de árbol de los departamentos y las empleados que trabajan en estos. Usando algoritmos de BFS, DFS, podemos encontrar relaciones de profundidad y anchura entre empleados y departamentos en los que trabaja o trabajó.

Sistemas de recomendación, para tiendas, donde un cliente tiene una compra pendiente de un producto, y por relación de similitud o proximidad de productos te ofrece otros para completar el pedido. Por ejemplo: quiero comprar gel de ducha y el sistema me recomienda que también compre un champú. Esto se consigue gracias a que entre ambos productos existe una o varias relaciones.

Cálculo de rutas en logística, son capaces de aplicar el algoritmo del camino más corto, usando algoritmos de Kruskal, Dijkstra o Prim. Lo que le facilita a la empresa el cálculo y reducción de costes en la selección de las rutas.

Detección del fraude, es difícil ver en una maraña de empresas por donde circula el dinero, sobre todo si se usan empresas pantalla o empresas en paraísos fiscales, testaferros, sociedades, etc. Al final tenemos un conjunto de datos de diferentes fuentes pero con relaciones directas o indirectas dificultando el seguimiento del dinero y por tanto ocultando el fraude.

Un ejemplo lo tenemos en los “Papeles de Panamá”, en el que tenemos más de 2’6 Terabytes de información, siendo complejo y costoso analizar toda esta información. Con un modelo basado en grafos, nos facilita el trabajo pudiendo seguir la pista,sobre todo si hay una representación visual de los datos, ejecutando consultas y búsquedas de los elementos, llegando a establecer las relaciones por donde haya podido circular el dinero.

Relaciones sociales, donde mayor uso se le puede dar y en donde mejor encajan.

En este caso tenemos múltiples ejemplos, desde temas relacionados con el cine, personajes, actores, directores, etc…En cuántas películas ha actuado nuestro actor favorito, con qué personajes ganó un premio, con que directores ha trabajado, son algunas de las consultas que podríamos realizar.

También lo podemos usar para modelar el conocimiento adquirido por los empleados, que tecnologías conocen, en qué proyectos han estado trabajando, con qué personas han estado trabajando.

Incluso en el ámbito policial o de investigación, quien no ha visto en las películas el típico panel con las fotos de los investigados y líneas rojas que cruzan el panel de un lado al otro. Si, eso podría ser una BDOG.

Modelos de redes, donde una red de sistemas o computadoras puede ser representado por un grafo.

Para finalizar podemos pensar en soluciones aún más complejas, utilizadas en la área de la investigación genética y la existencia relacional directa entre las enfermedades y la genealogía.

La controversia de CAP

El teorema de CAP dice que al nivel de sistema de cómputo distribuido es imposible garantizar simultáneamente más de dos características del modelo, y que como habíamos visto anteriormente, las BDOG se pueden clasificar como CP (Consistency-Partitioning) o CA (Consistency-Availability). Esto puede generar alguna controversia, pero principalmente se debe a cómo los fabricantes de software han decidido la implementación de la solución del motor de la base de datos con base en las características de CAP.

Dependiendo de la lectura que hagamos, podemos encontrar que Neo4J se engloban dentro de CP o CA y esto es porque Neo4J cumple con ACID y la transaccionalidad, a costa de nos ser tan flexible en el particionamiento, que siempre se verá penalizado aunque lo ofrezcan en su versión Enterprise. En cambio otros motores como RedisGraph, facilitan el particionamiento frente a la consistencia o AWS Neptune que también admiten ACID alta tolerancia al particionamiento, https://aws.amazon.com/es/neptune/.

Tabla de la controversia:

Conclusiones

Como hemos visto a lo largo del artículo, las BDOG nos ofrecen una gran versatilidad frente a otros modelos de tipos NoSQL y las recomendamos utilizar en los casos en los que se haga un principal hincapié en las relaciones de relación entre las entidades junto con un modelo de la información datos, flexible. Además, los algoritmos de búsqueda, descubrimiento de caminos cortos, exploración en anchura y profundidad que incluyen estas base de datos son temas que resultan muy interesantes seguir aprendiendo sobre ello.

Referencias

Teorema de Cap, wikipedia. Link: https://es.wikipedia.org/wiki/Teorema_CAP

Graph Database for Beginners, link: https://go.neo4j.com/rs/710-RRC-335/images/Graph_Databases_for_Beginners.pdf

Learning Neo4j- Rik Van Bruggen, link: http://neo4j.com/book-learning-neo4j/

Volver a la listaSiguiente artículo
arrow

Titulo

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat.