Base de datos gráfica

Un modelo de grafo de propiedades etiquetadas se representa mediante un conjunto de nodos, relaciones, propiedades y etiquetas. Tanto los nodos de datos como sus relaciones tienen nombre y pueden almacenar propiedades representadas por pares clave-valor . Los nodos pueden etiquetarse para agruparse. Las aristas que representan las relaciones tienen dos cualidades: siempre tienen un nodo de inicio y un nodo final, y son dirigidas; ^{[ 16 ]} lo que convierte al grafo en un grafo dirigido . Las relaciones también pueden tener propiedades. Esto es útil para proporcionar metadatos y semántica adicionales a las relaciones de los nodos. ^{[ 17 ]} El almacenamiento directo de relaciones permite un recorrido en tiempo constante . ^{[ 18 ]}

En un modelo de grafo RDF , cada adición de información se representa con un nodo separado. Por ejemplo, imaginemos un escenario en el que un usuario debe agregar una propiedad de nombre para una persona representada como un nodo distinto en el grafo. En un modelo de grafo de propiedades etiquetadas, esto se haría agregando una propiedad de nombre al nodo de la persona. Sin embargo, en RDF, el usuario debe agregar un nodo separado que hasNamelo conecte al nodo original de la persona. Específicamente, un modelo de grafo RDF se compone de nodos y arcos. Una notación de grafo RDF o una declaración se representa mediante: un nodo para el sujeto, un nodo para el objeto y un arco para el predicado. Un nodo puede dejarse en blanco, ser un literal o estar identificado por una URI . Un arco también puede estar identificado por una URI. Un literal para un nodo puede ser de dos tipos: simple (sin tipo) y tipado. Un literal simple tiene una forma léxica y, opcionalmente, una etiqueta de idioma. Un literal tipado se compone de una cadena con una URI que identifica un tipo de dato particular. Se puede utilizar un nodo en blanco para ilustrar con precisión el estado de los datos cuando estos no tienen una URI. ^{[ 19 ]}

El mecanismo de almacenamiento subyacente de las bases de datos de grafos puede variar. Algunas dependen de un motor relacional y "almacenan" los datos del grafo en una tabla (aunque una tabla es un elemento lógico, por lo que este enfoque impone otro nivel de abstracción entre la base de datos de grafos, el sistema de gestión de la base de datos de grafos y los dispositivos físicos donde se almacenan realmente los datos). Otras utilizan un almacén de clave-valor o una base de datos orientada a documentos para el almacenamiento, lo que las convierte inherentemente en estructuras NoSQL . Un nodo se representaría como cualquier otro almacén de documentos, pero las aristas que conectan dos nodos diferentes contienen atributos especiales dentro de su documento: los atributos _from y _to.

El rendimiento de la búsqueda de datos depende de la velocidad de acceso de un nodo a otro. Debido a que la adyacencia sin índice obliga a que los nodos tengan direcciones RAM físicas directas y apunten físicamente a otros nodos adyacentes, resulta en una recuperación rápida. Un sistema de grafos nativo con adyacencia sin índice no tiene que recorrer ningún otro tipo de estructura de datos para encontrar enlaces entre los nodos. Los nodos directamente relacionados en un grafo se almacenan en la caché una vez que se recupera uno de los nodos, lo que hace que la búsqueda de datos sea incluso más rápida que la primera vez que un usuario obtiene un nodo. Sin embargo, esta ventaja tiene un costo. La adyacencia sin índice sacrifica la eficiencia de las consultas que no utilizan recorridos de grafos . Las bases de datos de grafos nativas utilizan la adyacencia sin índice para procesar operaciones CRUD en los datos almacenados.

El modelo relacional recopila datos utilizando la información que contienen. Por ejemplo, se podrían buscar todos los usuarios cuyo número de teléfono incluya el código de área "311". Esto se haría buscando en almacenes de datos o tablas seleccionadas , buscando la cadena "311" en los campos de números de teléfono seleccionados. Este proceso puede ser lento en tablas grandes, por lo que las bases de datos relacionales ofrecen índices , que permiten almacenar los datos en una subtabla más pequeña, que contiene solo los datos seleccionados y una clave única (o clave primaria) del registro. Si los números de teléfono están indexados, la misma búsqueda se realizaría en la tabla de índices más pequeña, recopilando las claves de los registros coincidentes y luego buscando en la tabla de datos principal los registros con esas claves. Generalmente, una tabla se almacena de forma que la búsqueda mediante una clave sea muy rápida. ^{[ 27 ]}

Las bases de datos relacionales no contienen inherentemente la idea de relaciones fijas entre registros. En cambio, los datos relacionados se vinculan entre sí almacenando la clave única de un registro en los datos de otro. Por ejemplo, una tabla que contiene direcciones de correo electrónico de usuarios podría contener un elemento de datos llamado userpk, que contiene la clave primaria del registro de usuario con el que está asociado. Para vincular usuarios y sus direcciones de correo electrónico, el sistema primero busca las claves primarias de los registros de usuario seleccionados, busca esas claves en la userpkcolumna de la tabla de correo electrónico (o, más probablemente, en un índice de ellas), extrae los datos del correo electrónico y luego vincula los registros de usuario y correo electrónico para crear registros compuestos que contienen todos los datos seleccionados. Esta operación, denominada unión , puede ser computacionalmente costosa. Dependiendo de la complejidad de la consulta, el número de uniones y la indexación de varias claves, el sistema puede tener que buscar en varias tablas e índices y luego ordenarlos para que coincidan. ^{[ 27 ]}

En cambio, las bases de datos de grafos almacenan directamente las relaciones entre los registros. En lugar de encontrar una dirección de correo electrónico buscando la clave de su usuario en la userpkcolumna, el registro del usuario contiene un puntero que se refiere directamente al registro de la dirección de correo electrónico. Es decir, una vez seleccionado un usuario, se puede seguir el puntero directamente a los registros de correo electrónico, sin necesidad de buscar en la tabla de correos electrónicos para encontrar los registros coincidentes. Esto puede eliminar las costosas operaciones de unión. Por ejemplo, si se buscan todas las direcciones de correo electrónico de los usuarios del código de área "311", el motor primero realizaría una búsqueda convencional para encontrar a los usuarios en "311", pero luego recuperaría las direcciones de correo electrónico siguiendo los enlaces encontrados en esos registros. Una base de datos relacional primero encontraría a todos los usuarios en "311", extraería una lista de las claves primarias, realizaría otra búsqueda de cualquier registro en la tabla de correos electrónicos con esas claves primarias y vincularía los registros coincidentes. Para este tipo de operaciones comunes, las bases de datos de grafos serían teóricamente más rápidas. ^{[ 27 ]}

El verdadero valor del enfoque de grafos se hace evidente cuando se realizan búsquedas de más de un nivel de profundidad. Por ejemplo, consideremos una búsqueda de usuarios que tengan "suscriptores" (una tabla que vincula a los usuarios con otros usuarios) en el código de área "311". En este caso, una base de datos relacional primero tendría que buscar a todos los usuarios con un código de área en "311", luego buscar en la tabla de suscriptores a cualquiera de esos usuarios y, finalmente, buscar en la tabla de usuarios para recuperar los usuarios coincidentes. En cambio, una base de datos de grafos buscaría a todos los usuarios en "311" y luego seguiría los enlaces inversos a través de la relación de suscriptor para encontrar a los usuarios suscriptores. Esto evita varias búsquedas, consultas y el uso de memoria que implica mantener todos los datos temporales de múltiples registros necesarios para construir la salida. En términos de notación Big O , esta consulta sería:${\displaystyle O(\log n)+O(1)}$tiempo, es decir, proporcional al logaritmo del tamaño de los datos. En contraste, la versión relacional sería múltiple.${\displaystyle O(\log n)}$búsquedas, además de la${\displaystyle O(n)}$tiempo necesario para unir todos los registros de datos. ^{[ 27 ]}

La ventaja relativa de la recuperación de grafos aumenta con la complejidad de la consulta. Por ejemplo, se podría querer saber "esa película sobre submarinos con el actor que actuó en esa película con ese otro actor que protagonizó Lo que el viento se llevó ". Esto requiere que el sistema primero encuentre a los actores de Lo que el viento se llevó , encuentre todas las películas en las que participaron, encuentre a todos los actores de todas esas películas que no fueron los protagonistas de Lo que el viento se llevó , y luego encuentre todas las películas en las que participaron, filtrando finalmente esa lista para mostrar solo aquellas con descripciones que contengan "submarino". En una base de datos relacional, esto requeriría varias búsquedas separadas en las tablas de películas y actores, realizar otra búsqueda en películas de submarinos, encontrar a todos los actores en esas películas y luego comparar los (grandes) resultados recopilados. En cambio, la base de datos de grafos iría desde Lo que el viento se llevó hasta Clark Gable , recopilaría los enlaces a las películas en las que ha participado, recopilaría los enlaces desde esas películas a otros actores y luego seguiría los enlaces desde esos actores de vuelta a la lista de películas. La lista de películas resultante se puede buscar luego por "submarino". Todo esto se puede hacer mediante una sola búsqueda. ^{[ 28 ]}

Las propiedades añaden otra capa de abstracción a esta estructura, lo que también mejora muchas consultas comunes. Las propiedades son esencialmente etiquetas que se pueden aplicar a cualquier registro o, en algunos casos, también a las aristas. Por ejemplo, se podría etiquetar a Clark Gable como "actor", lo que permitiría al sistema encontrar rápidamente todos los registros de actores, en contraposición a directores u operadores de cámara. Si se permiten etiquetas en las aristas, también se podría etiquetar la relación entre Lo que el viento se llevó y Clark Gable como "protagonista", y al realizar una búsqueda de personas que sean "protagonistas" "actores" en la película Lo que el viento se llevó , la base de datos mostraría a Vivien Leigh , Olivia de Havilland y Clark Gable. La consulta SQL equivalente tendría que basarse en datos adicionales en la tabla que vincula personas y películas, lo que añade más complejidad a la sintaxis de la consulta. Este tipo de etiquetas pueden mejorar el rendimiento de la búsqueda en ciertas circunstancias, pero generalmente son más útiles para proporcionar datos semánticos adicionales a los usuarios finales. ^{[ 28 ]}

Las bases de datos relacionales son muy adecuadas para estructuras de datos planas, donde las relaciones entre datos tienen solo uno o dos niveles de profundidad. Por ejemplo, una base de datos contable podría necesitar consultar todos los elementos de todas las facturas de un cliente determinado, una consulta de triple unión. Las bases de datos de grafos están diseñadas para conjuntos de datos con muchos más enlaces. Son especialmente adecuadas para sistemas de redes sociales , donde la relación de "amigos" es prácticamente ilimitada. Estas propiedades hacen que las bases de datos de grafos sean idóneas para los tipos de búsquedas cada vez más comunes en sistemas en línea y en entornos de big data . Por esta razón, las bases de datos de grafos se están volviendo muy populares para grandes sistemas en línea como Facebook , Google , Twitter y sistemas similares con enlaces profundos entre registros.

Para ilustrarlo mejor, imaginemos un modelo relacional con dos tablas: una peopletabla (que tiene una columna person_idy person_name) y una friendtabla (con friend_idy person_id, que es una clave foránea de la peopletabla ). En este caso, la búsqueda de todos los amigos de Jack daría como resultado la siguiente consulta SQL.

SELECT p2 . person_name FROM people p1 JOIN friend ON ( p1 . person_id = friend . person_id ) JOIN people p2 ON ( p2 . person_id = friend . friend_id ) WHERE p1 . person_name = 'Jack' ;

La misma consulta puede traducirse a --

• Cypher , un lenguaje de consulta para bases de datos de grafos.

  COINCIDIR ( p1 : persona { nombre : 'Jack' }) -[ : AMIGO_CON ]- ( p2 : persona ) DEVOLVER p2 . nombre

• Gremlin , un lenguaje de consulta de grafos de estilo imperativo mantenido por Apache TinkerPop y utilizado por muchas bases de datos de grafos ^{[ 29 ].}

  g . V (). hasLabel ( "persona" ). has ( "nombre" , "Jack" ). out ( "amigosCon" ). hasLabel ( "persona" ). values ​​( "nombre" )

• SPARQL , un lenguaje de consulta para bases de datos de grafos RDF estandarizado por el W3C y utilizado en múltiples almacenes de triples y cuádruples RDF.
  • Formato largo

    PREFIJO foaf : <http://xmlns.com/foaf/0.1/>SELECCIONAR ?nombre DONDE { ?es un foaf : Persona . ?es foaf : nombre "Jack" . ?es foaf : conoce ?o . ​​?o foaf : nombre ?nombre . }

  • Formato corto

    PREFIJO foaf : <http://xmlns.com/foaf/0.1/>SELECT ?name WHERE { ?s foaf : name "Jack" ; foaf : knows ?o . ​​?o foaf : name ?name . }

• SPASQL, un lenguaje de consulta de bases de datos híbrido que extiende SQL con SPARQL.

  SELECT people . name FROM ( SPARQL PREFIX foaf : <http://xmlns.com/foaf/0.1/> SELECT ?name WHERE { ?s foaf : name "Jack" ; foaf : knows ?o . ​​?o foaf : name ?name . } ) AS people ;