Capítulo 11.
Bases de datos de grafos
Las bases de datos de grafos permiten almacenar entidades y relaciones entre estas entidades. Las
entidades también se conocen como nodos, que tienen propiedades. Piense en un nodo como una
instancia de un objeto en la aplicación. Las relaciones se conocen como aristas que pueden tener
propiedades. Los bordes tienen un significado direccional; Los nodos están organizados por
relaciones que le permiten encontrar patrones interesantes entre los nodos. La organización del
grafo permite que los datos se almacenen una vez y luego se interpreten de diferentes maneras en
función de las relaciones.
11.1. ¿Qué es una base de datos de grafos?
En el gráfico de ejemplo de la figura 11.1, vemos un montón de nodos relacionados entre sí. Los
nodos son entidades que tienen propiedades, como name. El nodo de Martin es en realidad un nodo
que tiene la propiedad de name establecida en Martin.
Figura 11.1. Un ejemplo de estructura gráfica
También vemos que los bordes tienen tipos, como Me gusta, autor, etc. Estas propiedades nos
permiten organizar los nodos; por ejemplo, los nodos Martin y Pramod tienen una ventaja que los
conecta con un tipo de relación de amigo. Los bordes pueden tener varias propiedades. Podemos
asignar una propiedad de since en el tipo de relación de amistad entre Martin y Pramod. Los
tipos de relación tienen un significado direccional; El tipo de relación de amistad es
bidireccional, pero los Me gusta no lo son. Cuando a Dawn le gusta
NoSQL Distilled, no significa automáticamente que a NoSQL Distilled le guste Dawn.
Una vez que tenemos un grafo de estos nodos y bordes creados, podemos consultar el grafo de
muchas maneras, como "obtener todos los nodos empleados por Big Co a los que les gusta
NoSQL Distilled". Una consulta en el grafo también se conoce como recorrer el grafo. Una
ventaja de las bases de datos de grafos es que podemos cambiar los requisitos de recorrido sin tener
que cambiar los nodos o los bordes. Si queremos "obtener todos los nodos a los que les guste
NoSQL Distilled", podemos hacerlo sin tener que cambiar los datos existentes o el modelo de la
base de datos, porque podemos recorrer el gráfico de la forma que queramos.
Por lo general, cuando almacenamos una estructura similar a un grafo en RDBMS, es para un
solo tipo de relación ("quién es mi gerente" es un ejemplo común). Agregar otra relación a la
mezcla generalmente significa muchos cambios de esquema y movimiento de datos, lo que no es el
caso cuando usamos bases de datos de grafos. Del mismo modo, en las bases de datos relacionales
modelamos el grafo de antemano en función del Traversal que queremos; si el Traversal
cambia, los datos tendrán que cambiar.
En las bases de datos de grafos, el recorrido de las uniones o relaciones es muy rápido. La
relación entre los nodos no se calcula en el momento de la consulta, sino que se conserva como
una relación. Recorrer las relaciones persistentes es más rápido que calcularlas para cada consulta.
Los nodos pueden tener diferentes tipos de relaciones entre ellos, lo que le permite representar
relaciones entre las entidades de dominio y tener relaciones secundarias para cosas como
categoría, ruta, árboles de tiempo, árboles cuádruples para la indexación espacial o listas
vinculadas para el acceso ordenado. Dado que no hay límite para el número y el tipo de relaciones
que puede tener un nodo, todos ellos se pueden representar en la misma base de datos de grafos.
11.2. Funciones
Hay muchas bases de datos de grafos disponibles, como Neo4J [Neo4J], Infinite Graph [Infinite
Graph], OrientDB [OrientDB] o FlockDB [FlockDB] (que es un caso especial: una base de datos de
grafos que solo admite relaciones de una sola profundidad o listas de adyacencia, donde no se puede
atravesar más de un nivel de profundidad para las relaciones). Tomaremos a Neo4J como
representante de las soluciones de bases de datos de grafos para discutir cómo funcionan y cómo se
pueden usar para resolver problemas de aplicaciones.
En Neo4J, crear un grafo es tan simple como crear dos nodos y luego crear una relación. Vamos a
crear dos nodos, Martin y Pramod:
Haga clic aquí para ver la imagen del código
Nodo martin = [Link]();
[Link]("nombre", "Martín");
Nodo pramod = [Link]();
[Link]("nombre", "Pramod");
Hemos asignado a la propiedad name de los dos nodos los valores de Martin y Pramod. Una vez
que tenemos más de un nodo, podemos crear una relación:
Haga clic aquí para ver la imagen del código
[Link](pramod, AMIGO);
[Link](martín, AMIGO);
Tenemos que crear una relación entre los nodos en ambas direcciones, para la dirección de la
La relación importa: Por ejemplo, un nodo de producto puede gustar al usuario, pero el producto
no puede gustar
el usuario. Esta direccionalidad ayuda a diseñar un modelo de dominio enriquecido (Figura 11.2).
Los nodos conocen las relaciones ENTRANTES y SALIENTES que se pueden recorrer en ambos
sentidos.
Figura 11.2. Relaciones con las propiedades
Las relaciones son ciudadanos de primera clase en las bases de datos de grafos; La mayor parte
del valor de las bases de datos de grafos se deriva de las relaciones. Las relaciones no solo tienen
un tipo, un nodo inicial y un nodo final, sino que pueden tener propiedades propias. Usando estas
propiedades en las relaciones, podemos agregar inteligencia a la relación, por ejemplo, desde
cuándo se hicieron amigos, cuál es la distancia entre los nodos o qué aspectos se comparten entre
los nodos. Estas propiedades de las relaciones se pueden utilizar para consultar el gráfico.
Dado que la mayor parte de la potencia de las bases de datos de grafos proviene de las relaciones
y sus propiedades, se necesita mucho trabajo de reflexión y diseño para modelar las relaciones en el
dominio con el que estamos tratando de trabajar. Agregar nuevos tipos de relación es fácil; cambiar
los nodos existentes y sus relaciones es similar a la migración de datos ("Migraciones en bases de
datos de grafos", p. 131), porque estos cambios tendrán que hacerse en cada nodo y en cada relación
en los datos existentes.
11.2.1.Consistencia
Dado que las bases de datos de grafos funcionan en nodos conectados, la mayoría de las
soluciones de bases de datos de grafos no suelen admitir la distribución de los nodos en diferentes
servidores. Sin embargo, hay algunas soluciones que admiten la distribución de nodos en un
clúster de servidores, como Infinite Graph. Dentro de un solo servidor, los datos siempre son
consistentes, especialmente en Neo4J, que es totalmente compatible con ACID. Cuando se ejecuta
Neo4J en un clúster, una escritura en el maestro se sincroniza finalmente con los esclavos,
mientras que los esclavos siempre están disponibles para lectura. Las escrituras en esclavos están
permitidas y se sincronizan inmediatamente con el maestro;
Sin embargo, otros esclavos no se sincronizarán inmediatamente, ya que tendrán que esperar a que
los datos se propaguen desde el maestro.
Las bases de datos de gráficos garantizan la coherencia a través de las transacciones. No permiten
relaciones colgantes: el nodo inicial y el nodo final siempre deben existir, y los nodos solo se
pueden eliminar si no tienen ninguna relación asociada.
11.2.2.Transacciones
Neo4J cumple con ACID. Antes de cambiar cualquier nodo o agregar cualquier relación a los
nodos existentes, tenemos que iniciar una transacción. Sin ajustar las operaciones en las
transacciones, obtendremos una NotInTransactionException. Las operaciones de lectura se
pueden realizar sin iniciar una transacción.
Haga clic aquí para ver la imagen del código
Transacción transacción = [Link]();
try {
Nodo nodo = [Link]();
[Link]("nombre", "NoSQL destilado");
[Link]("publicado", "2012");
transacción.éxito();
} finalmente {
transacció[Link]();
}
En el código anterior, iniciamos una transacción en la base de datos, luego creamos un nodo y
establecemos las propiedades
en él. Marcamos la transacción como exitosa y finalmente la completamos hasta el final. Una
transacción debe marcarse como correcta, de lo contrario, Neo4J asume que fue un error y la
revierte cuando se emite finish. Establecer el éxito sin emitir finish tampoco compromete los
datos en la base de datos. Esta forma de gestionar las transacciones hay que recordarla a la hora de
desarrollarla, ya que difiere de la forma estándar de hacer transacciones en un RDBMS.
11.2.3.Disponibilidad
Neo4J, a partir de la versión 1.8, logra una alta disponibilidad al proporcionar esclavos replicados.
Estos esclavos también pueden manejar escrituras: cuando se escriben en, sincronizan la escritura
con el maestro actual, y la escritura se confirma primero en el maestro y luego en el esclavo. Otros
esclavos eventualmente recibirán la actualización. Otras bases de datos de gráficos, como Infinite
Graph y FlockDB, proporcionan almacenamiento distribuido de los nodos.
Neo4J utiliza el Apache ZooKeeper [ZooKeeper] para realizar un seguimiento de los últimos ID
de transacción persistentes en cada nodo esclavo y en el nodo maestro actual. Una vez que se inicia
un servidor, se comunica con ZooKeeper y descubre qué servidor es el maestro. Si el servidor es el
primero en unirse al clúster, se convierte en el maestro; Cuando un maestro deja de funcionar, el
clúster elige un maestro de los nodos disponibles, lo que proporciona una alta disponibilidad.
11.2.4.Características de consulta
Las bases de datos de grafos son compatibles con lenguajes de consulta como Gremlin [Gremlin].
Gremlin es un lenguaje específico de dominio para recorrer grafos; puede recorrer todas las bases
de datos de gráficos que implementan el gráfico de propiedades Blueprints [Blueprints]. Neo4J
también tiene el lenguaje de consulta Cypher [Cypher] para consultar el gráfico. Fuera de estos
lenguajes de consulta, Neo4J le permite consultar el grafo para las propiedades de los nodos,
recorrer el grafo o navegar por las relaciones de los nodos utilizando enlaces de lenguaje.
Las propiedades de un nodo se pueden indexar mediante el servicio de indexación. Del mismo
modo, las propiedades de las relaciones o los bordes se pueden indexar, por lo que el valor puede
encontrar un nodo o un borde. Se deben consultar los índices para encontrar el nodo de inicio para
comenzar un recorrido. Echemos un vistazo a la búsqueda del nodo mediante la indexación de
nodos.
Si tenemos el gráfico que se muestra en la Figura 11.1, podemos indexar los nodos a medida
que se agregan a la base de datos, o podemos indexar todos los nodos más tarde iterando sobre
ellos. Primero tenemos que crear un índice para los nodos utilizando el IndexManager.
Haga clic aquí para ver la imagen del código
Index<Node> nodeIndex = [Link]().forNodes("nodos");
Estamos indexando los nodos para la propiedad name. Neo4J utiliza Lucene [Lucene] como
su servicio de indexación. Veremos más adelante que también podemos utilizar la capacidad de
búsqueda de texto completo de Lucene. Cuando se crean nuevos nodos, se pueden agregar al
índice.
Haga clic aquí para ver la imagen del código
Transacción de transacción =
[Link](); try {
Index<Node> nodeIndex =
[Link]().forNodes("nodos"); [Link](martin,
"nombre", [Link]("nombre"));
[Link](pramod, "nombre",
[Link]("nombre")); transacción.éxito();
} finalmente {
transacció[Link]();
}
La adición de nodos al índice se realiza dentro del contexto de una transacción. Una vez
indexados los nodos,
Podemos buscarlos usando la propiedad indexada. Si buscamos el nodo con el nombre de
Barbara, consultaríamos el índice para que la propiedad de name tenga un valor de Barbara.
Haga clic aquí para ver la imagen del código
Nodo nodo = [Link]("nombre", "Bárbara").getSingle();
Obtenemos el nodo cuyo nombre es Martín; dado el nodo, podemos obtener todas sus relaciones.
Haga clic aquí para ver la imagen del código
Nodo martin = [Link]("nombre", "Martin").getSingle();
allRelationships = [Link]();
Podemos conseguir relaciones tanto ENTRANTES como SALIENTES.
Haga clic aquí para ver la imagen del código
incomingRelations = [Link](Direcció[Link]);
También podemos aplicar filtros direccionales en las consultas al consultar una relación. Con el
gráfico de la Figura 11.1, si queremos encontrar a todas las personas a las que les gusta NoSQL
Distilled, podemos encontrar el nodo NoSQL Distilled y luego obtener sus relaciones con
[Link]. En este punto también podemos agregar el tipo de relación al filtro de
consulta, ya que estamos buscando solo nodos que LIKE NoSQL Distilled.
Haga clic aquí para ver la imagen del código
Nodo nosqlDestilado = [Link]("nombre",
"NoSQL destilado").getSingle();
relaciones = [Link](ENTRANTE, ME
GUSTA); for (Relación de relación : relaciones) {
[Link]([Link]());
}
Encontrar nodos y sus relaciones inmediatas es fácil, pero esto también se puede lograr en bases
de datos RDBMS. Las bases de datos de grafos son realmente eficaces cuando se desea recorrer
los grafos a cualquier profundidad y especificar un nodo de inicio para el recorrido. Esto es
especialmente útil cuando se intenta encontrar nodos que están relacionados con el nodo inicial en
más de un nivel inferior. A medida que aumenta la profundidad del gráfico, tiene más sentido
recorrer las relaciones mediante un Traverser en el que puede especificar que está buscando
ENTRANTES, SALIENTES o AMBOS tipos de relaciones. También puede hacer que el trazador
transversal vaya de arriba hacia abajo o hacia los lados en el gráfico mediante valores Order de
BREADTH_FIRST o DEPTH_FIRST. El recorrido tiene que comenzar en algún nodo, en este ejemplo,
intentamos encontrar todos los nodos a cualquier profundidad que estén relacionados como un
AMIGO con Barbara:
Haga clic aquí para ver la imagen del código
Nodo barbara = [Link]("nombre", "Barbara").getSingle();
Traverser friendsTraverser =
[Link](Order.BREADTH_FIRST,
StopEvaluator.END_OF_GRAPH,
ReturnableEvaluator.ALL_BUT_START_NODE,
[Link],
[Link]);
El friendsTraverser nos proporciona una forma de encontrar todos los nodos que están
relacionados con Barbara donde el tipo de relación es FRIEND. Los nodos pueden estar a cualquier
profundidad, amigo de un amigo en cualquier nivel, lo que le permite explorar las estructuras de los
árboles.
Una de las buenas características de las bases de datos de grafos es encontrar rutas entre dos
nodos, determinando si hay varias rutas, encontrando todas las rutas o la ruta más corta. En el
gráfico de la figura 11.1, sabemos que Bárbara está conectada a Jill por dos caminos distintos;
para encontrar todos estos caminos y la distancia entre Bárbara y Jill a lo largo de esos diferentes
caminos, podemos usar
Haga clic aquí para ver la imagen del código
Nodo barbara = [Link]("nombre",
"Barbara").getSingle(); Node jill = [Link]("nombre",
"Jill").getSingle(); PathFinder<Path> finder =
[Link](
[Link](FRIEND,[Link])
,MAX_DEPTH);
Iterable<Path> paths = [Link](barbara, jill);
Esta función se utiliza en las redes sociales para mostrar las relaciones entre dos nodos
cualesquiera. Para encontrar todas las rutas y la distancia entre los nodos de cada ruta, primero
obtenemos una lista de rutas distintas entre los dos nodos. La longitud de cada ruta es el número de
saltos en el grafo necesarios para llegar al nodo de destino desde el nodo de inicio. A menudo, es
necesario obtener la ruta más corta entre dos nodos; de los dos caminos de Barbara a Jill, el
camino más corto se puede encontrar usando
Haga clic aquí para ver la imagen del código
PathFinder<Path> finder = [Link](
[Link](FRIEND, [Link])
, MAX_DEPTH);
Iterable<Path> paths = [Link](barbara, jill);
Muchos otros algoritmos de grafos se pueden aplicar al grafo en cuestión, como el algoritmo de
Dijkstra
[Dijkstra] para encontrar el camino más corto o más barato entre nodos.
Haga clic aquí para ver la imagen del código
START beginingNode = (especificación del nodo inicial)
MATCH (relación, coincidencias de patrones)
WHERE (condición de filtrado: en datos en nodos y relaciones)
RETURN (Qué devolver: nodos, relaciones, propiedades) ORDER
BY (propiedades por las que ordenar)
SKIP (nodos para saltar desde
arriba) LIMIT (limitar los
resultados)
Neo4J también proporciona el lenguaje de consulta Cypher para consultar el gráfico. Cypher
necesita un nodo para iniciar la consulta. El nodo de inicio se puede identificar por su ID de nodo,
una lista de ID de nodo o búsquedas de índice. Cypher utiliza la palabra clave MATCH para hacer
coincidir patrones en las relaciones; la palabra clave WHERE filtra las propiedades de un nodo o
relación. La palabra clave RETURN especifica lo que devuelve la consulta
: nodos, relaciones o campos en los nodos o relaciones.
Cypher también proporciona métodos para ORDER, AGGREGATE, SKIP y LIMIT los datos. En la
Figura 11.2, encontramos todos los nodos conectados a Barbara, ya sea entrante o saliente, mediante
el uso de --.
Haga clic aquí para ver la imagen del código
START barbara = node:nodeIndex(name =
"Barbara") MATCH (barbara)--(connected_node)
DEVOLVER connected_node
Cuando nos interesa la significación direccional, podemos usar
PARTIDO (Bárbara)<--(connected_node)
para las relaciones entrantes o
PARTIDO (bárbara)-->(connected_node)
para las relaciones extrovertidas. La coincidencia también se puede realizar en relaciones específicas
utilizando el método
:RELATIONSHIP_TYPE convención y devolviendo los campos o nodos obligatorios.
Haga clic aquí para ver la imagen del código
START barbara = node:nodeIndex(name =
"Barbara") MATCH
(barbara)-[:FRIEND]->(friend_node)
RETURN friend_node.nombre,friend_node.ubicación
Comenzamos con Bárbara, encontramos todas las relaciones salientes con el tipo de AMIGO y
devolvemos los nombres de los amigos. La consulta de tipo de relación solo funciona para la
profundidad de un nivel; Podemos hacer que funcione para profundidades mayores y averiguar la
profundidad de cada uno de los nodos resultantes.
Haga clic aquí para ver la imagen del código
START barbara=node:nodeIndex(name = "Barbara")
MATCH path = barbara-[:FRIEND*1..3]->end_node
RETURN [Link],end_node.name, length(path)
Del mismo modo, podemos consultar las relaciones en las que existe una propiedad de relación
determinada. También podemos filtrar por las propiedades de las relaciones y consultar si una
propiedad existe o no.
Haga clic aquí para ver la imagen del código
START barbara = node:nodeIndex(name =
"Barbara") MATCH
(barbara)-[relación]->(related_node)
WHERE type(relation) = 'FRIEND' AND [Link]
RETURN related_node.name, [Link]
Hay muchas otras características de consulta en el lenguaje Cypher que se pueden usar para
consultar gráficos de base de datos.
11.2.5.Escalada
En las bases de datos NoSQL, una de las técnicas de escalado más utilizadas es la fragmentación, en
la que los datos se dividen y distribuyen en diferentes servidores. Con las bases de datos de grafos,
la fragmentación es difícil, ya que las bases de datos de grafos no están orientadas a agregados, sino
a relaciones. Dado que cualquier nodo dado se puede relacionar con cualquier otro nodo, almacenar
nodos relacionados en el mismo servidor es mejor para el recorrido de grafos. Recorrer un grafo
cuando los nodos están en diferentes máquinas no es bueno para el rendimiento. Conociendo esta
limitación de las bases de datos de grafos, todavía podemos escalarlas utilizando algunas técnicas
comunes descritas por Jim Webber [Webber Neo4J Scaling].
En términos generales, hay tres formas de escalar bases de datos de grafos. Dado que las
máquinas ahora pueden venir con mucha RAM, podemos agregar suficiente RAM al servidor para
que el conjunto de trabajo de nodos y relaciones se mantenga completamente en la memoria. Esta
técnica solo es útil si el conjunto de datos con el que estamos trabajando cabe en una cantidad
realista de RAM.
Podemos mejorar el escalado de lectura de la base de datos agregando más esclavos con acceso
de solo lectura a los datos, con todas las escrituras yendo al maestro. Este patrón de escritura una
vez y lectura de muchos servidores es una técnica probada en clústeres MySQL y es realmente útil
cuando el conjunto de datos es lo suficientemente grande como para no caber en la RAM de una
sola máquina, pero lo suficientemente pequeño como para ser replicado en varias máquinas.
Los esclavos también pueden contribuir a la disponibilidad y al escalado de lectura, ya que pueden
configurarse para que nunca se conviertan en maestros, permaneciendo siempre en solo lectura.
Cuando el tamaño del conjunto de datos hace que la replicación no sea práctica, podemos
fragmentar (consulte la sección "Partición" en p. 38) los datos del lado de la aplicación utilizando
el conocimiento específico del dominio. Por ejemplo, los nodos que se relacionan con América
del Norte se pueden crear en un servidor, mientras que los nodos que se relacionan con Asia en
otro. Esta fragmentación a nivel de aplicación debe comprender que los nodos se almacenan en
bases de datos físicamente diferentes (Figura 11.3).
Figura 11.3. Particionamiento de nodos a nivel de aplicación
11.3. Casos de uso adecuados
Veamos algunos casos de uso adecuados para las bases de datos de grafos.
11.3.1.Datos conectados
Las redes sociales son el lugar donde se pueden desplegar y utilizar las bases de datos de gráficos
de forma muy eficaz. Estos gráficos sociales no tienen por qué ser solo del tipo amigo; Por ejemplo,
pueden representar a los empleados, sus conocimientos y dónde trabajaron con otros empleados en
diferentes proyectos. Cualquier dominio rico en enlaces es adecuado para bases de datos de grafos.
Si tiene relaciones entre entidades de dominio de diferentes dominios (como social, espacial,
comercial) en una sola base de datos, puede hacer que estas relaciones sean más valiosas
proporcionando la capacidad de recorrer los dominios.
11.3.2.Servicios de enrutamiento, despacho y basados en la ubicación
Cada ubicación o dirección que tiene una entrega es un nodo, y todos los nodos donde el repartidor
debe realizar la entrega se pueden modelar como un grafo de nodos. Las relaciones entre nodos
pueden tener la propiedad de distancia, lo que le permite entregar los productos de manera eficiente.
Las propiedades de distancia y ubicación también se pueden usar en gráficos de lugares de interés,
de modo que la aplicación pueda proporcionar recomendaciones de buenos restaurantes u opciones
de entretenimiento cercanas. También puede crear nodos para sus puntos de venta, como librerías o
restaurantes, y notificar a los usuarios cuando estén cerca de alguno de los nodos para proporcionar
servicios basados en la ubicación.
11.3.3.Motores de recomendación
A medida que se crean nodos y relaciones en el sistema, se pueden usar para hacer recomendaciones
como "tus amigos también compraron este producto" o "al facturar este artículo, estos otros artículos
generalmente se facturan". O bien, se puede utilizar para hacer recomendaciones a los viajeros
mencionando que cuando otros
Los visitantes que vienen a Barcelona suelen visitar las creaciones de Antonio Gaudí.
Un efecto secundario interesante del uso de las bases de datos de gráficos para las
recomendaciones es que, a medida que aumenta el tamaño de los datos, el número de nodos y
relaciones disponibles para hacer las recomendaciones aumenta rápidamente. Los mismos datos
también se pueden usar para extraer información, por ejemplo, qué productos siempre se compran
juntos o qué artículos siempre se facturan juntos; Se pueden generar alertas cuando no se cumplen
estas condiciones. Al igual que otros motores de recomendación, las bases de datos de gráficos se
pueden utilizar para buscar patrones en las relaciones para detectar fraudes en las transacciones.
11.4. Cuándo no usarlo
En algunas situaciones, es posible que las bases de datos de gráficos no sean apropiadas. Cuando
desee actualizar todas las entidades o un subconjunto de ellas, por ejemplo, en una solución de
análisis en la que es posible que sea necesario actualizar todas las entidades con una propiedad
modificada, es posible que las bases de datos de gráficos no sean óptimas, ya que cambiar una
propiedad en todos los nodos no es una operación sencilla. Incluso si el modelo de datos funciona
para el dominio del problema, es posible que algunas bases de datos no puedan manejar muchos
datos, especialmente en operaciones de grafos globales (aquellas que involucran todo el grafo).
