Una base de datos de gráficos ( GDB ) es una base de datos que utiliza estructuras de gráficos 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 del almacén con una colección de nodos y aristas, representando las aristas las relaciones entre los nodos. Las relaciones permiten que los datos del almacén se vinculen directamente y, en muchos casos, se recuperen con una sola operación. Las bases de datos de gráficos tienen como prioridad las relaciones entre los datos. Consultar relaciones es rápido porque se almacenan perpetuamente en la base de datos. Las relaciones se pueden visualizar intuitivamente utilizando bases de datos de gráficos, lo que las hace útiles para datos muy interconectados. [2]
Las bases de datos de gráficos se denominan comúnmente bases de datos NoSQL . Las bases de datos de gráficos son similares a las bases de datos de modelos de red de la década de 1970 en que ambas representan gráficos generales, pero las bases de datos de modelos de red operan en un nivel más bajo de abstracción [3] y carecen de un recorrido fácil a través de una cadena de bordes. [4]
El mecanismo de almacenamiento subyacente de las bases de datos de gráficos puede variar. Las relaciones son ciudadanos de primera clase en una base de datos gráfica y se pueden etiquetar, dirigir y otorgar propiedades. Algunos dependen de un motor relacional y almacenan los datos del gráfico 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 la base de datos de gráficos y los dispositivos de almacenamiento físico). Otros utilizan un almacén de valores clave o una base de datos orientada a documentos para el almacenamiento, lo que los convierte en estructuras inherentemente NoSQL.
A partir de 2021 [actualizar], ningún lenguaje de consulta de gráficos se ha adoptado universalmente de la misma manera que SQL para las bases de datos relacionales, y existe una amplia variedad de sistemas, muchos de los cuales están estrechamente vinculados a un producto. Algunos de los primeros esfuerzos de estandarización conducen a lenguajes de consulta de múltiples proveedores como Gremlin , SPARQL y Cypher . En septiembre de 2019, los miembros del Comité Técnico Conjunto 1 de ISO/IEC (ISO/IEC JTC 1) aprobaron una propuesta de 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 pretende 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 gráficos se diferencian de los motores de cálculo de gráficos. Las bases de datos de gráficos 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álculo de gráficos se utilizan en el procesamiento analítico en línea (OLAP) para análisis masivos. [5] Las bases de datos de gráficos 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 gráficos patentadas, [6] junto con la introducción de bases de datos de gráficos de código abierto .
Un estudio concluyó que un RDBMS era "comparable" en rendimiento a los motores de análisis de gráficos existentes al ejecutar consultas de gráficos. [7]
A mediados de la década de 1960, las bases de datos de navegación como el IMS de IBM admitían estructuras en forma de árbol en su modelo jerárquico , pero la estricta estructura de árbol podía evitarse con registros virtuales. [8] [9]
Las estructuras de gráficos se podían representar en bases de datos de modelos de red de finales de la década de 1960. CODASYL , que había definido COBOL en 1959, definió el lenguaje de base de datos de red en 1969.
Los gráficos etiquetados se podían representar en bases de datos de gráficos de mediados de la década de 1980, como el Modelo de datos lógicos. [10] [11]
Las bases de datos de objetos comerciales (ODBMS) surgieron a principios de los años 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 la década de 1990 con 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, estuvieron disponibles bases de datos comerciales de gráficos ACID que podían ampliarse horizontalmente . Además, SAP HANA incorporó tecnologías en memoria y en columnas para graficar bases de datos. [12] También en la década de 2010, estuvieron disponibles bases de datos multimodelo que admitían modelos 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 gráficas 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, estuvieron disponibles bases de datos de gráficos basadas en la nube , como Amazon Neptune y Neo4j AuraDB .
Las bases de datos de gráficos representan los datos tal como se ven conceptualmente. Esto se logra transfiriendo los datos a nodos y sus relaciones a bordes.
Una base de datos de grafos es una base de datos que se basa en la teoría de grafos . Consta de un conjunto de objetos, que puede ser un nodo o una arista.
Un modelo de gráfico de propiedades etiquetadas está representado por un conjunto de nodos, relaciones, propiedades y etiquetas. Ambos nodos de datos y sus relaciones tienen nombre y pueden almacenar propiedades representadas por pares clave-valor . Los nodos se pueden etiquetar para agruparlos. Las aristas que representan las relaciones tienen dos cualidades: siempre tienen un nodo inicial y un nodo final, y están dirigidas; [13] haciendo del gráfico 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 propiedades etiquetadas, esto se haría agregando una propiedad de nombre al nodo de la persona. Sin embargo, en un RDF, el usuario debe agregar un nodo separado llamado hasName
conectarlo al nodo persona original. Específicamente, un modelo de gráfico RDF se compone de nodos y arcos. Una notación gráfica RDF o una declaración está representada por: un nodo para el sujeto, un nodo para el objeto y un arco para el predicado. Un nodo puede dejarse en blanco, ser literal y/o identificarse mediante un URI . Un arco también puede identificarse mediante un URI. Un literal para un nodo puede ser de dos tipos: simple (sin tipo) y con tipo. Un literal simple tiene una forma léxica y, opcionalmente, una etiqueta de idioma. Un literal escrito se compone de una cadena con un URI que identifica un tipo de datos particular. Se puede utilizar un nodo en blanco para ilustrar con precisión el estado de los datos cuando los datos no tienen un URI . [dieciséis]
Las bases de datos de gráficos son una herramienta poderosa para consultas similares a gráficos. Por ejemplo, calcular el camino más corto entre dos nodos en el gráfico. Se pueden realizar otras consultas similares a gráficos en una base de datos de gráficos de forma natural (por ejemplo, cálculos de diámetro de gráficos 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 detalles extensos de los casos de uso futuros de la base de datos.
El mecanismo de almacenamiento subyacente de las bases de datos de gráficos puede variar. Algunos dependen de un motor relacional y "almacenan" los datos del gráfico 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 del gráfico, el sistema de gestión de la base de datos del gráfico y los dispositivos físicos donde se almacenan los datos). está realmente almacenado). Otros utilizan un almacén de valores clave o una base de datos orientada a documentos para el almacenamiento, lo que los convierte en estructuras inherentemente NoSQL . Un nodo se representaría como cualquier otro almacén de documentos, pero los bordes que unen dos nodos diferentes contienen atributos especiales dentro de su documento; un atributo _from y _to.
El rendimiento de la búsqueda de datos depende de la velocidad de acceso de un nodo particular a otro. Debido a que la adyacencia sin índice obliga a los nodos a tener direcciones RAM físicas directas y apuntar físicamente a otros nodos adyacentes, esto resulta en 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 enlaces entre los nodos. Los nodos directamente relacionados en un gráfico 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 busca 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 adyacencia sin índice para procesar operaciones CRUD en los datos almacenados.
Se han reconocido múltiples categorías de gráficos por tipo de datos. Gartner sugiere cinco categorías amplias 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 industrial de facto para los sistemas de almacenamiento de datos a gran escala. Los modelos relacionales requieren un esquema estricto y una normalización de datos que separe los datos en muchas tablas y elimine cualquier dato duplicado dentro de la base de datos. Los datos se normalizan para preservar la coherencia 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 es necesario 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 genera 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 necesaria ] y se asignan más directamente a la estructura de las aplicaciones orientadas a objetos . Pueden escalar de forma más natural [ cita necesaria ] 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 adecuados 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 una gran cantidad de elementos de datos, lo que permite la manipulación de los datos en su estructura natural. A pesar de las ventajas de las bases de datos gráficas y su reciente popularidad sobre [ cita necesaria ] 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 menor latencia. [19]
El modelo relacional recopila datos utilizando la información de 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 tablas o almacenes de datos seleccionados , buscando en los campos de números de teléfono seleccionados la cadena "311". Este puede ser un proceso que requiere mucho tiempo 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, se producirí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 la búsqueda mediante 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 para usuarios puede contener un elemento de datos llamado userpk
, que contiene la clave principal del registro de usuario al que está asociado. Para vincular a los 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 userpk
columna 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 de correo electrónico para crear registros compuestos que contengan todos los datos seleccionados. Esta operación, denominada unión , puede resultar costosa desde el punto de vista computacional. Dependiendo de la complejidad de la consulta, la cantidad de combinaciones y la indexación de varias claves, es posible que el sistema tenga que buscar en varias tablas e índices y luego ordenarlos todos para que coincidan. [20]
Por el contrario, las bases de datos de gráficos almacenan directamente las relaciones entre registros. En lugar de encontrar una dirección de correo electrónico buscando la clave de usuario en la userpk
columna, el registro de usuario contiene un puntero que hace referencia directamente al registro de dirección de correo electrónico. Es decir, una vez seleccionado un usuario, el puntero se puede seguir directamente a los registros de correo electrónico, no es necesario 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 en el código de área "311", el motor primero realizará una búsqueda convencional para encontrar los usuarios en "311", pero luego recuperará las direcciones de correo electrónico siguiendo los enlaces que se encuentran en esos registros. Una base de datos relacional primero encontraría a todos los usuarios en "311", extraería una lista de las claves principales, realizaría otra búsqueda de cualquier registro en la tabla de correo electrónico con esas claves principales y vincularía los registros coincidentes. Para este tipo de operaciones comunes, las bases de datos gráficas serían teóricamente más rápidas. [20]
El verdadero valor del enfoque gráfico se vuelve evidente cuando se realizan búsquedas que tienen más de un nivel de profundidad. Por ejemplo, considere 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 tiene que buscar primero todos los usuarios con un código de área en "311", luego buscar en la tabla de suscriptores 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" y luego seguiría los vínculos de retroceso a través de la relación del suscriptor para encontrar los usuarios suscriptores. Esto evita varias búsquedas y el uso de memoria involucrado en almacenar 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 incluirí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 crece 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 primero requiere que el sistema encuentre a los actores de Lo que el viento se llevó , busque todas las películas en las que aparecieron, encuentre todos los actores de todas esas películas que no fueron los protagonistas de Lo que el viento se llevó y luego busque todas las películas. estaban, finalmente filtrando esa lista a aquellos con descripciones que contienen "submarino". En una base de datos relacional, esto requeriría varias búsquedas separadas en las tablas de películas y actores, hacer otra búsqueda en películas de submarinos, encontrar todos los actores de esas películas y luego comparar los (grandes) resultados recopilados. Por el contrario, la base de datos gráfica iría desde Lo que el viento se llevó hasta Clark Gable , reuniría los enlaces a las películas en las que ha estado, 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. En la lista resultante de películas se puede buscar "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 sean actores, en lugar de directores u operadores 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 "principal", y realizando una búsqueda de personas que sean "actores" "principales" en la película Lo que el viento se llevó , el La base de datos produciría 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 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 se adaptan muy bien a diseños de datos planos, donde las relaciones entre datos tienen solo uno o dos niveles de profundidad. Por ejemplo, es posible que una base de datos de contabilidad necesite buscar todas las partidas de todas las facturas de un cliente determinado, una consulta de tres combinaciones. Las bases de datos de gráficos están dirigidas a conjuntos de datos que contienen muchos más enlaces. Son especialmente adecuados para los sistemas de redes sociales , donde la relación de "amigos" es esencialmente ilimitada. Estas propiedades hacen que las bases de datos gráficas 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, imagine un modelo relacional con dos tablas: una people
tabla (que tiene una columna person_id
y person_name
) y una friend
tabla (con friend_id
y person_id
, que es una clave externa de la people
tabla). En este caso, buscar a todos los amigos de Jack daría como resultado la siguiente consulta SQL.
SELECCIONE p2 . nombre_persona DE personas p1 ÚNETE a amigo EN ( p1 . person_id = amigo . persona_id ) ÚNETE a personas p2 EN ( p2 . persona_id = amigo . amigo_id ) DONDE p1 . nombre_persona = 'Jack' ;
La misma consulta puede traducirse a:
PARTICIPAR ( p1 : persona { nombre : 'Jack' }) -[ : AMIGO_CON ]- ( p2 : persona ) VOLVER p2 . nombre
PREFIJO foaf : <http://xmlns.com/foaf/0.1/>SELECCIONE ?nombre DONDE { ?s un foaf : Persona . ?s foaf : nombre "Jack" . ?s foaf : lo sabe . ?o foaf : nombre ?nombre . }
PREFIJO foaf : <http://xmlns.com/foaf/0.1/>SELECCIONE ?nombre DONDE { ?s foaf : nombre "Jack" ; foaf : ¿ sabe ? ?o foaf : nombre ?nombre . }
SELECCIONA personas . nombre FROM ( 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 sencilla de una consulta de relación 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 de gráficos 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 de gráficos no necesariamente proporcionan 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 establecidas. [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}}
: Citar diario requiere |journal=
( ayuda )