Una base de datos gráfica ( GDB ) es una base de datos que utiliza estructuras gráficas para consultas semánticas con nodos , aristas y propiedades para representar y almacenar datos. [1] Un concepto clave del sistema es el gráfico (o arista o relación). El gráfico relaciona los elementos de datos en el almacén con una colección de nodos y aristas, y las aristas representan las relaciones entre los nodos. Las relaciones permiten que los datos en el almacén se vinculen directamente y, en muchos casos, se recuperen con una sola operación. Las bases de datos gráficas mantienen las relaciones entre los datos como una prioridad. La consulta de relaciones es rápida porque se almacenan de forma perpetua en la base de datos. Las relaciones se pueden visualizar de forma intuitiva utilizando bases de datos gráficas, lo que las hace útiles para datos muy interconectados. [2]
Las bases de datos de grafos se conocen comúnmente como bases de datos NoSQL . Las bases de datos de grafos son similares a las bases de datos de modelos de red de los años 1970 en que ambas representan grafos generales, pero las bases de datos de modelos de red operan en un nivel de abstracción más bajo [3] y carecen de una fácil navegación sobre una cadena de aristas. [4]
El mecanismo de almacenamiento subyacente de las bases de datos de grafos puede variar. Las relaciones son ciudadanos de primera clase en una base de datos de grafos y se pueden etiquetar, dirigir y asignar propiedades. Algunas dependen de un motor relacional y almacenan los datos de los grafos en una tabla (aunque una tabla es un elemento lógico, por lo tanto, este enfoque impone un nivel de abstracción entre el sistema de gestión de bases de datos de grafos y los dispositivos de almacenamiento físicos). Otras utilizan un almacén de clave-valor o una base de datos orientada a documentos para el almacenamiento, lo que las convierte en estructuras inherentemente NoSQL.
A partir de 2021 [actualizar], ningún lenguaje de consulta de gráficos ha sido adoptado universalmente de la misma manera que SQL para bases de datos relacionales, y existe una amplia variedad de sistemas, muchos de los cuales están estrechamente vinculados a un producto. Algunos esfuerzos de estandarización tempranos llevaron a lenguajes de consulta de múltiples proveedores como Gremlin , SPARQL y Cypher . En septiembre de 2019, los miembros del Comité Técnico Conjunto ISO/IEC 1 (ISO/IEC JTC 1) aprobaron una propuesta para un proyecto para crear un nuevo lenguaje de consulta de gráficos estándar (ISO/IEC 39075 Tecnología de la información - Lenguajes de bases de datos - GQL). GQL está destinado a ser un lenguaje de consulta de base de datos declarativo, como SQL. Además de tener interfaces de lenguaje de consulta, se accede a algunas bases de datos de gráficos a través de interfaces de programación de aplicaciones (API).
Las bases de datos de grafos se diferencian de los motores de cómputo de grafos. Las bases de datos de grafos son tecnologías que son traducciones de las bases de datos de procesamiento de transacciones en línea relacionales (OLTP). Por otro lado, los motores de cómputo de grafos se utilizan en el procesamiento analítico en línea (OLAP) para el análisis masivo. [5] Las bases de datos de grafos atrajeron una atención considerable en la década de 2000, debido a los éxitos de las principales corporaciones tecnológicas en el uso de bases de datos de grafos propietarias, [6] junto con la introducción de bases de datos de grafos de código abierto .
Un estudio concluyó que un RDBMS era "comparable" en rendimiento a los motores de análisis de gráficos existentes en la ejecución de consultas de gráficos. [7]
A mediados de la década de 1960, las bases de datos de navegación como IMS de IBM admitían estructuras de tipo árbol en su modelo jerárquico , pero la estricta estructura de árbol podía eludirse con registros virtuales. [8] [9]
Las estructuras gráficas se pudieron representar en bases de datos de modelos de red desde finales de la década de 1960. CODASYL , que había definido COBOL en 1959, definió el lenguaje de bases de datos de red en 1969.
Los gráficos etiquetados se pudieron representar en bases de datos de gráficos desde mediados de la década de 1980, como el Modelo Lógico de Datos. [10] [11]
Las bases de datos de objetos comerciales (ODBMS) surgieron a principios de la década de 1990. En 2000, el Object Data Management Group publicó un lenguaje estándar para definir estructuras de objetos y relaciones (gráficos) en su publicación ODMG'93.
A principios de la década de 1990 aparecieron varias mejoras en las bases de datos gráficas, que se aceleraron a finales de esa década con los intentos de indexar páginas web.
A mediados y finales de la década de 2000, estuvieron disponibles bases de datos de gráficos comerciales con garantías ACID , como Neo4j y Oracle Spatial and Graph .
En la década de 2010, se pusieron a disposición bases de datos de gráficos ACID comerciales que podían escalarse horizontalmente . Además, SAP HANA incorporó tecnologías en memoria y en columnas a las bases de datos de gráficos. [12] También en la década de 2010, se pusieron a disposición bases de datos multimodelo que admitían modelos de gráficos (y otros modelos como bases de datos relacionales o bases de datos orientadas a documentos ), como OrientDB , ArangoDB y MarkLogic (a partir de su versión 7.0). Durante este tiempo, las bases de datos de gráficos de varios tipos se han vuelto especialmente populares en el análisis de redes sociales con la llegada de las empresas de redes sociales. También durante la década, se pusieron a disposición bases de datos de gráficos basadas en la nube como Amazon Neptune y Neo4j AuraDB .
Las bases de datos gráficas representan los datos tal como se los ve conceptualmente. Esto se logra transfiriendo los datos a nodos y sus relaciones a aristas.
Una base de datos de grafos es una base de datos que se basa en la teoría de grafos . Consiste en un conjunto de objetos, que pueden ser un nodo o una arista.
Un modelo de gráfico de propiedades etiquetadas se representa mediante un conjunto de nodos, relaciones, propiedades y etiquetas. Tanto los nodos de datos como sus relaciones reciben un nombre y pueden almacenar propiedades representadas por pares clave-valor . Los nodos se pueden etiquetar para agruparlos. Los bordes que representan las relaciones tienen dos cualidades: siempre tienen un nodo de inicio y un nodo final, y están dirigidos; [13] lo que hace que el gráfico sea un gráfico dirigido . Las relaciones también pueden tener propiedades. Esto es útil para proporcionar metadatos y semántica adicionales a las relaciones de los nodos. [14] El almacenamiento directo de relaciones permite un recorrido en tiempo constante . [15]
En un modelo de gráfico RDF , cada adición de información se representa con un nodo separado. Por ejemplo, imagine un escenario en el que un usuario tiene que agregar una propiedad de nombre para una persona representada como un nodo distinto en el gráfico. En un modelo de gráfico de propiedad etiquetada, esto se haría con una adición de una propiedad de nombre en el nodo de la persona. Sin embargo, en un RDF, el usuario tiene que agregar un nodo separado llamado que hasNamelo conecta con el nodo de persona original. Específicamente, un modelo de gráfico RDF se compone de nodos y arcos. Una notación de gráfico 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 y/o estar identificado por un URI . Un arco también puede estar identificado por un URI. Un literal para un nodo puede ser de dos tipos: simple (sin tipo) y tipificado. Un literal simple tiene una forma léxica y, opcionalmente, una etiqueta de idioma. Un literal tipado está formado por una cadena con un URI que identifica un tipo de datos en particular. Se puede utilizar un nodo en blanco para ilustrar con precisión el estado de los datos cuando estos no tienen un URI . [16]
Las bases de datos de grafos son una herramienta poderosa para realizar consultas de tipo gráfico. Por ejemplo, calcular la ruta más corta entre dos nodos del grafo. Se pueden realizar otras consultas de tipo gráfico en una base de datos de grafos de manera natural (por ejemplo, cálculos del diámetro del grafo o detección de comunidades).
Los gráficos son flexibles, lo que significa que permiten al usuario insertar nuevos datos en el gráfico existente sin perder la funcionalidad de la aplicación. No es necesario que el diseñador de la base de datos planifique con gran detalle los casos de uso futuros de la base de datos.
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 tanto, 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 en estructuras inherentemente NoSQL . Un nodo se representaría como cualquier otro almacén de documentos, pero los bordes que vinculan 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 en particular a otro. Debido a que la adyacencia sin índice obliga a los nodos a tener direcciones RAM físicas directas y a apuntar físicamente a otros nodos adyacentes, da como resultado una recuperación rápida. Un sistema de gráficos nativo con adyacencia sin índice no tiene que moverse a través de ningún otro tipo de estructuras de datos para encontrar vínculos entre los nodos. Los nodos directamente relacionados en un gráfico se almacenan en la memoria 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 gráficos . Las bases de datos de gráficos nativos utilizan la adyacencia sin índice para procesar las operaciones CRUD en los datos almacenados.
Se han reconocido múltiples categorías de gráficos según el tipo de datos. Gartner sugiere cinco categorías generales de gráficos: [17]
Desde el artículo de Edgar F. Codd de 1970 sobre el modelo relacional , [18] las bases de datos relacionales han sido el estándar de facto de la industria para los sistemas de almacenamiento de datos a gran escala. Los modelos relacionales requieren un esquema estricto y una normalización de datos que separa los datos en muchas tablas y elimina cualquier dato duplicado dentro de la base de datos. Los datos se normalizan para preservar la consistencia de los datos y admitir transacciones ACID . Sin embargo, esto impone limitaciones sobre cómo se pueden consultar las relaciones.
Una de las motivaciones del diseño del modelo relacional fue lograr un acceso rápido fila por fila. [18] Los problemas surgen cuando existe la necesidad de formar relaciones complejas entre los datos almacenados. Aunque las relaciones se pueden analizar con el modelo relacional, se requieren consultas complejas que realicen muchas operaciones de unión en muchos atributos diferentes en varias tablas. Al trabajar con modelos relacionales, también se deben considerar las restricciones de clave externa al recuperar relaciones, lo que causa una sobrecarga adicional.
En comparación con las bases de datos relacionales , las bases de datos gráficas suelen ser más rápidas para conjuntos de datos asociativos [ cita requerida ] y se adaptan más directamente a la estructura de las aplicaciones orientadas a objetos . Pueden escalar de forma más natural [ cita requerida ] a grandes conjuntos de datos, ya que normalmente no necesitan operaciones de unión , que a menudo pueden resultar costosas. Como dependen menos de un esquema rígido, se comercializan como más adecuadas para gestionar datos ad hoc y cambiantes con esquemas en evolución.
Por el contrario, los sistemas de gestión de bases de datos relacionales suelen ser más rápidos a la hora de realizar la misma operación en grandes cantidades de elementos de datos, lo que permite manipular los datos en su estructura natural. A pesar de las ventajas de las bases de datos gráficas y su reciente popularidad sobre las bases de datos relacionales, se recomienda que el modelo gráfico en sí no sea la única razón para reemplazar una base de datos relacional existente. Una base de datos gráfica puede volverse relevante si hay evidencia de una mejora del rendimiento en órdenes de magnitud y una latencia menor. [19]
El modelo relacional reúne datos utilizando la información contenida en los datos. Por ejemplo, se podrían buscar todos los "usuarios" cuyo número de teléfono contenga el código de área "311". Esto se haría buscando en almacenes de datos seleccionados, o tablas , buscando en los campos de número de teléfono seleccionados la cadena "311". Este puede ser un proceso que consume mucho tiempo en tablas grandes, por lo que las bases de datos relacionales ofrecen índices , que permiten almacenar datos en una subtabla más pequeña, que contiene solo los datos seleccionados y una clave única (o clave principal) del registro. Si los números de teléfono están indexados, se realizaría la misma búsqueda en la tabla de índice más pequeña, reuniendo las claves de los registros coincidentes y luego buscando en la tabla de datos principal los registros con esas claves. Por lo general, una tabla se almacena de una manera que permite que una búsqueda a través de una clave sea muy rápida. [20]
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 registro. Por ejemplo, una tabla que contiene direcciones de correo electrónico de usuarios puede contener un elemento de datos llamado userpk, que contiene la clave principal del registro de usuario con el que está asociado. Para vincular a los usuarios y sus direcciones de correo electrónico, el sistema primero busca las claves principales de los registros de usuario seleccionados, busca esas claves en la userpkcolumna de la tabla de correo electrónico (o, más probablemente, un índice de ellas), extrae los datos de correo electrónico y luego vincula los registros de usuario y correo electrónico para crear registros compuestos que contengan todos los datos seleccionados. Esta operación, denominada unión , puede ser costosa desde el punto de vista computacional. Dependiendo de la complejidad de la consulta, la cantidad de uniones y la indexación de varias claves, el sistema puede tener que buscar en varias tablas e índices y luego ordenarlos todos para que coincidan. [20]
En cambio, las bases de datos de grafos almacenan directamente las relaciones entre registros. En lugar de encontrar una dirección de correo electrónico buscando la clave de su usuario en la userpkcolumna, el registro de usuario contiene un puntero que hace referencia directamente al registro de la dirección de correo electrónico. Es decir, una vez seleccionado un usuario, se puede seguir el puntero directamente hasta los registros de correo electrónico, sin necesidad de buscar en la tabla de correo electrónico para encontrar los registros coincidentes. Esto puede eliminar las costosas operaciones de unión. Por ejemplo, si uno busca 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 los usuarios en "311", pero luego recuperaría las direcciones de correo electrónico siguiendo los vínculos encontrados en esos registros. Una base de datos relacional primero encontraría todos los usuarios en "311", extraería una lista de las claves primarias, realizaría otra búsqueda de todos los registros en la tabla de correo electrónico 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. [20]
El verdadero valor del enfoque gráfico se hace evidente cuando se realizan búsquedas que tienen más de un nivel de profundidad. Por ejemplo, considere una búsqueda de usuarios que tienen "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 tiene que buscar primero 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. Por el contrario, una base de datos gráfica buscaría todos los usuarios en "311", luego seguiría los vínculos de retroceso a través de la relación de suscriptor para encontrar los usuarios suscriptores. Esto evita varias búsquedas, consultas y el uso de memoria involucrado en mantener todos los datos temporales de múltiples registros necesarios para construir la salida. En términos de notación O grande , esta consulta sería tiempo, es decir, proporcional al logaritmo del tamaño de los datos. Por el contrario, la versión relacional sería múltiples búsquedas, más el tiempo necesario para unir todos los registros de datos. [20]
La ventaja relativa de la recuperación de gráficos aumenta con la complejidad de una consulta. Por ejemplo, uno podría querer saber "esa película sobre submarinos con el actor que estuvo en esa película con ese otro actor que interpretó el papel principal en Lo que el viento se llevó ". Esto requiere primero que el sistema encuentre los actores de Lo que el viento se llevó , encuentre todas las películas en las que participaron, encuentre todos los actores de todas esas películas que no fueron el protagonista de Lo que el viento se llevó y luego encuentre todas las películas en las que participaron, filtrando finalmente esa lista para aquellos con descripciones que contengan "submarino". En una base de datos relacional, esto requeriría varias búsquedas separadas a través de las tablas de películas y actores, haciendo otra búsqueda en películas de submarinos, encontrando todos los actores de esas películas y luego comparando los resultados recopilados (grandes). En contraste, la base de datos de gráficos iría desde Lo que el viento se llevó hasta Clark Gable , reuniría los enlaces a las películas en las que ha participado, reuniría los enlaces de esas películas a otros actores y luego seguiría los enlaces de esos actores de regreso a la lista de películas. La lista de películas resultante se puede buscar por "submarino". Todo esto se puede hacer mediante una sola búsqueda. [21]
Las propiedades añaden otra capa de abstracción a esta estructura 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 los bordes. Por ejemplo, se podría etiquetar a Clark Gable como "actor", lo que permitiría al sistema encontrar rápidamente todos los registros que son actores, en lugar de director u operador de cámara. Si se permiten etiquetas en los bordes, 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 son "protagonistas" o "actores" en la película Lo que el viento se llevó , la base de datos produciría Vivien Leigh , Olivia de Havilland y Clark Gable. La consulta SQL equivalente tendría que depender de datos agregados en la tabla que vincula a personas y películas, lo que agregaría más complejidad a la sintaxis de la consulta. Este tipo de etiquetas pueden mejorar el rendimiento de la búsqueda en determinadas circunstancias, pero generalmente son más útiles para proporcionar datos semánticos adicionales para los usuarios finales. [21]
Las bases de datos relacionales son muy adecuadas para diseños de datos planos, donde las relaciones entre los datos tienen solo uno o dos niveles de profundidad. Por ejemplo, una base de datos de contabilidad podría necesitar buscar todos los artículos de línea de todas las facturas de un cliente determinado, una consulta de tres uniones. Las bases de datos de gráficos están destinadas a conjuntos de datos que contienen muchos más vínculos. Son especialmente adecuadas para sistemas de redes sociales , donde la relación de "amigos" es esencialmente ilimitada. Estas propiedades hacen que las bases de datos de gráficos sean naturalmente adecuadas para tipos de búsquedas que son 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 gráficos se están volviendo muy populares para grandes sistemas en línea como Facebook , Google , Twitter y sistemas similares con vínculos profundos entre registros.
Para ilustrarlo mejor, imaginemos un modelo relacional con dos tablas: una peopletabla (que tiene una columna person_idy ) y una tabla (con y , que es una clave externa de la tabla). En este caso, la búsqueda de todos los amigos de Jack daría como resultado la siguiente consulta SQL.person_namefriendfriend_idperson_idpeople
SELECCIONAR p2 . nombre_persona DE personas p1 UNIRSE amigo EN ( p1 . id_persona = amigo . id_persona ) UNIRSE personas p2 EN ( p2 . id_persona = amigo . id_amigo ) DONDE p1 . nombre_persona = 'Jack' ; La misma consulta se puede traducir como:
COINCIDIR ( p1 : persona { nombre : 'Jack' }) -[ : AMIGO_CON ]- ( p2 : persona ) DEVOLVER p2 . nombre PREFIJO foaf : <http://xmlns.com/foaf/0.1/>SELECCIONAR ?nombre DONDE { ?s a foaf : Persona . ?s foaf : nombre "Jack" . ?s foaf : sabe ?o . ?o foaf : nombre ?nombre . }PREFIJO foaf : <http://xmlns.com/foaf/0.1/>SELECCIONAR ?nombre DONDE { ?s foaf : nombre "Jack" ; foaf : sabe ?o . ?o foaf : nombre ?nombre . }SELECCIONAR personas . nombre DE ( PREFIJO SPARQL foaf : <http://xmlns.com/foaf/0.1/> SELECCIONAR ? nombre DONDE { ?s foaf : nombre "Jack" ; foaf : sabe ?o . ?o foaf : nombre ? nombre . } ) COMO personas ; Los ejemplos anteriores son una ilustración simple de una consulta relacional básica. Condensan la idea de que la complejidad de las consultas de los modelos relacionales aumenta con la cantidad total de datos. En comparación, una consulta de base de datos gráfica puede ordenar fácilmente el gráfico de relaciones para presentar los resultados.
También hay resultados que indican que las consultas simples, condensadas y declarativas de las bases de datos gráficas no necesariamente ofrecen un buen rendimiento en comparación con las bases de datos relacionales. Si bien las bases de datos gráficas ofrecen una representación intuitiva de los datos, las bases de datos relacionales ofrecen mejores resultados cuando se necesitan operaciones de conjuntos. [15]
La siguiente es una lista de bases de datos de gráficos notables :
Los modelos de red [...] carecen de un buen nivel de abstracción: es difícil separar el modelo de base de datos de la implementación real
Los modelos de red [...] carecen de un buen nivel de abstracción: es difícil separar el modelo de base de datos de la implementación real
{{cite journal}}: Requiere citar revista |journal=( ayuda )