Procedimiento para manipular y consultar mediante un sistema computacional multigrafos dirigidos, etiquetados y con atributos.

La presente invención establece un procedimiento para, dada una representación lógica de datos en forma de red o multígrafo,

crear un conjunto de estructuras que la permitan su almacenamiento eficiente en un sistema digital y su consiguiente manipulación. El multígrafo se representa usando mapas de bits con contadores de elementos y mapeos entre valores y mapas de bits organizados con el fin de facilitar la manipulación de dichos multígrafos. Los bits en los mapas de bits representan dos aspectos fundamentales del multígrafo: 1) Indexación de todos los objetos del multígrafo en función de sus identificadores y 2) conectividad entre objetos del multígrafo, ya sean nodos o arcos. Los mapeos permiten, dado un valor, acceder a los objetos del multígrafo que lo contienen. Las operaciones de multígrafo se resuelven accediendo a los mapeos y aplicando operaciones lógicas sobre los mapas de bits. Esta manera de representar un grafo permite realizar operaciones sobre grafos eficientemente como: insertar un nodo o un arco, insertar un atributo, obtener los arcos de entrada y salida de un atributo, etc.

Procedimiento para manipular y consultar mediante un sistema computacional multigrafos dirigidos, etiquetados y con atributos. Antecedentes de la invención

La presente invención se refiere de forma genérica a un método para manipular y consultar redes o multigrafos en sistemas computacionales que permita la resolución eficiente de distintas operaciones genéricas sobre estos.

El análisis y la manipulación de multigrafos de forma eficiente se está convirtiendo en una necesidad ante el creciente volumen de datos estructurados en forma de red o multigrafo.

Son conocidos los métodos para la gestión de datos en forma de multigrafo, aunque presentan limitaciones en lo que se refiere a la capacidad de almacenaje y manipulación eficiente de este tipo de datos. Concretamente, estos métodos no permiten gestionar eficientemente datos en forma de multigrafo cuando el tamaño de estos crece significativamente. Esto se produce porque las estructuras de datos utilizadas no favorecen la ejecución eficiente de algunas de las operaciones de multigrafos más comunes y, específicamente, porque: 1) las estructuras de datos no permiten acceder rápidamente a la información tal y como requieren dichas operaciones y 2) las estructuras de datos no están optimizadas para tener en cuenta que la capacidad de memoria es limitada. Ejemplos de dichas operaciones son: buscar patrones en un multigrafo, explorar el multigrafo a través de la relación de un nodo con sus vecinos, encontrar el diámetro del multigrafo, etc.

El uso de sistemas basados en modelos de datos tradicionales como el relacional para la gestión de multigrafos no cumple con los requerimientos necesarios para construir un sistema eficiente que permita consultar y manipular dichos multigrafos cuando estos son muy grandes. En el modelo relacional se considera que los datos se almacenan en registros que se organizan en relaciones. Mientras esta organización favorece consultas donde lo más importante es la información almacenada en cada registro, no favorece algunas consultas típicas de multigrafos, relativas al análisis de la relación entre entidades.

El uso de sistemas de representación específicos para multigrafos como las matrices de incidencia permiten manipular multigrafos eficientemente, pero requieren que el multigrafo entero se pueda manipular en memoria, y presentan restricciones severas cuando los elementos del multigrafo contienen atributos asociados, o cuando se debe guardar más información aparte de la propia estructura del multigrafo.

En consecuencia, se necesita un sistema para gestionar con medios computacionales multigrafos genéricos con atributos que permita la transformación y consulta de dichos multigrafos de forma eficiente y sin requerir que la totalidad del multigrafo tenga cabida en la memoria disponible en el sistema. Definiciones

Un grafo es una estructura matemática que representa una red formada por nodos y arcos. Los objetos de un grafo son el conjunto de sus nodos y arcos.

D1/ Un nodo es cada uno de los puntos de conexión o entidades de un grafo o red.

D2/ Un arco es una relación entre dos nodos de un grafo o red. En general, un arco se representa como una línea entre dos nodos.

D3/ Un arco dirigido es una relación entre un nodo origen o saliente, y un nodo destino o entrante. En general, un arco dirigido se representa como una flecha con origen en el nodo saliente, y destino en el nodo entrante.

D4/ En un grafo etiquetado todos los nodos y arcos tienen una etiqueta. Todos los objetos con la misma etiqueta se dice que pertenecen al mismo tipo de objeto.

D5/ En un grafo con atributos cada objeto puede tener, opcionalmente, uno o mas atributos con un valor asociado para cada uno de ellos. Cada atributo de un objeto se identifica con un nombre de atributo diferente.

D6/ En un multigrafo dos nodos cualesquiera pueden estar relacionados por más de un arco de cualquier tipo de arco, dirigido o no.

D7/ Un multigrafo etiquetado y dirigido con atributos es un grafo que se define a partir de las definiciones D3, D4, D5 y D6 anteriores.

D8/ Un mapeo es una aplicación matemática no inyectiva y sobreyectiva entre dos conjuntos, el origen de claves únicas, y el de imagen de valores asociados. En una aplicación no inyectiva, los elementos del conjunto imagen pueden tener dos o más orígenes. En una aplicación sobreyectiva, todos los elementos del conjunto imagen tienen al menos un origen.

D9/ Un mapa de bits, o vector de bits, es una estructura de datos que almacena de forma compacta secuencias de valores lógicos cierto y falso, donde cierto o presencia se representa con el valor 1, y falso o ausencia con el valor 0. Un mapa de bits de n bits representa un subconjunto de {1, 2, ..., n}, donde el valor i pertenece al subconjunto si el bit en la posición i del mapa de bits está marcado a 1. En consecuencia, la cardinalidad de dicho subconjunto es igual al número de bits marcadosa1enel mapa de bits. Descripción resumida de la invención

La presente invención se refiere a un método para transformar y consultar datos estructurados en forma de red o multigrafo genérico, gracias al cual se consiguen notables mejoras en la eficiencia de acceso y manipulación de estos datos en relación a otras transformaciones de este tipo de datos conocidas hasta ahora.

La presente invención determina unas estructuras y métodos de acceso y transformación de datos para manipular un multigrafo que representa una red de interés. El multigrafo incluye dos tipos de objetos: nodos que representan entidades o puntos en la red de interés y arcos dirigidos que enlazan pares de nodos. Ambos, nodos y arcos, tienen identificadores únicos dentro del multigrafo y pueden contener atributos para guardar características de los mismos. Opcionalmente, los objetos de un multigrafo pueden estar organizados en distintos tipos. Opcionalmente, los arcos pueden ser no dirigidos. El multigrafo se transforma usando mapas de bits con contadores de elementos y mapeos entre valores y mapas de bits organizados con el fin de facilitar la manipulación de dichos multigrafos. Los bits en los mapas de bits representan dos aspectos fundamentales del multigrafo: 1) indexación de todos los objetos del multigrafo en función de sus identificadores y 2) conectividad entre objetos del multigrafo, ya sean nodos o arcos. Los mapeos permiten, dado un valor, acceder a los objetos del multigrafo que lo contienen. Las operaciones de multigrafo se

resuelven accediendo a los mapeos y aplicando operaciones lógicas sobre los mapas de bits. Podemos ver un conjunto de ejemplos sobre multigrafos:

Ejemplo 1. Obtener el número de objetos de un cierto tipo. Resolver esta operación implica acceder al mapa de bits correspondiente y retornar el valor almacenado en el contador del mapa de bits.

Ejemplo 2. Obtener los objetos de un cierto tipo cuyos atributos cumplen una serie de restricciones en función de unos valores dados. Resolver esta operación implica acceder, en base a los valores provistos en las restricciones, a través de los mapeos, a los mapas de bits asociados a ese atributo. El resultado se obtiene aplicando iterativamente operaciones lógicas bit a bit sobre estos mapas de bits.

Ejemplo 3. Obtener el grado de entrada de un nodo en un multigrafo dirigido, es decir, el número de arcos que van de cualquier nodo a este nodo. Resolver esta operación implica acceder al mapa de bits del nodo en particular que contiene información sobre los arcos entrantes utilizando un mapeo directo entre el identificador del nodo y el mapa de bits. El resultado se calcula obteniendo el contador de dicho mapa de bits.

Ejemplo 4. Obtener los nodos conectados a través de al menos un arco a un nodo concreto. Resolver esta operación implica acceder a los mapas de bits del nodo en particular que contiene información sobre los arcos entrantes y salientes respectivamente y, a partir de los arcos, obtener información sobre los nodos conectados al nodo origen a través de estos arcos. El resultado se calcula obteniendo los dos mapas de bits correspondientes a partir del identificador del nodo y un mapeo valor-mapa de bits. Y, a partir de los identificadores de arco obtenidos y operaciones lógicas, encontrar los nodos asociados.

Ejemplo 5. Obtener una segmentación de los nodos de un multigrafo agrupados por su valor en un cierto atributo. Resolver esta operación implica iterar...

1. Procedimiento para manipular y consultar mediante un sistema computacional multigrafos dirigidos etiquetados y con atributos mediante estructuras de datos en forma de mapas de bits y mapeos, en donde dichas estructuras de datos comprenden:

a. nodos y arcos del multigrafo que se denominan objetos del multigrafo, que están asociados a un tipo concreto de objeto y contienen valores asociados denominados atributos.

b. objetos del multigrafo identificados mediante un identificador numérico único.

c. para cada tipo de objeto, el identificador numérico único de los objetos del multigrafo, según el apartado b, almacenado mediante el uso de un mapa de bits, marcando el bit en la posición correspondiente al identificador de cada objeto e incrementando un contador de objetos en el mismo.

d. para cada atributo asociado a un objeto del multigrafo de un tipo concreto se usa un mapeo en el cual, para cada valor en susodicho atributo se asigna un mapa de bits que contiene el número de objetos de ese tipo que contienen dicho valor en dicho atributo y en el cual se marca el bit en la posición correspondiente al identificador de cada uno de estos objetos.

e. para a cada atributo asociado a un objeto del multigrafo de un tipo concreto se usa un mapeo en el cual, para cada identificador de cada uno de estos objetos, se asigna el valor en dicho atributo.

f. para cada nodo con uno o más arcos de salida el identificador numérico único de estos arcos, según el apartado b, se almacena mediante el uso de un mapa de bits, marcando el bit en la posición correspondiente al identificador de cada arco saliente y incrementando un contador de objetos en el mismo.

g. para cada nodo con uno o más arcos de entrada el identificador numérico único de estos arcos, según el apartado b, se almacena mediante el uso de un mapa de bits, marcando el bit en la posición correspondiente al identificador de cada arco entrante e incrementando un contador de objetos en el mismo.

h. un mapeo que relaciona el identificador único de los nodos con uno o más arcos de salida y los mapas de bits asociados, según el apartado

d.

i. un mapeo que relaciona el identificador único de los arcos con el identificador único de su nodo origen.

j. un mapeo que relaciona el identificador único de los nodos con uno o más arcos de entrada y los mapas de bits asociados, según el apartado

g.

k. un mapeo que relaciona el identificador único de los arcos con el identificador único de su nodo destino,

caracterizado porque dicho procedimiento de manipulación comprende transformar un multigrafo de manera que insertar un nuevo nodo implica modificar el valor de un mapa de bits correspondiente al objeto, marcando el bit en la posición correspondiente al identificador de dicho objeto y poniendo un bit a uno, según el apartado c.

2. Procedimiento según la reivindicación 1, en el cual insertar un nuevo arco implica modificar el valor de un mapa de bits, poniendo un bit a uno, según el apartado c, asociar los valores correspondientes al identificador del nuevo nodo y los identificadores de los nodos unidos por el nuevo arco en los mapeos, según los apartados h, i, jyk.

3. Procedimiento según la reivindicación 1, en el cual insertar un nuevo valor a un atributo en un objeto se realiza asociando valores al identificador del objeto, para ese atributo, a través de mapeos, según los apartadosdyedelareivindicación 1.

4. Procedimiento según la reivindicación 1, en el cual la consulta de un multigrafo, comprende obtener los arcos de entrada y salida de un nodo implica acceder a dos mapas de bits a través de dos mapeos entre el identificador de objeto de dicho nodo y dichos mapas de bits, según los apartados h y j de la reivindicación 1, y la posterior operación lógica bit a bit de unión de los dos mapas de bits obtenidos.

5. Procedimiento, según la reivindicación 4, en el cual para dicha consulta obtener los nodos origen y destino de un arco se realiza accediendo directamente a los identificadores de objeto de dicho nodos a través de dos mapeos entre el identificador de objeto de dicho arco y los identificadores de los nodos extremos, según los apartadosiykdelareivindicación 1.

6. Procedimiento según la reivindicación 4, en el cual para dicha consulta obtener los nodos de un tipo dado se realiza retornando un mapa de bits existente, según el apartado c de la reivindicación 1.

7. Procedimiento según la reivindicación 4, en el cual para dicha consulta obtener los nodos de un tipo que tienen un cierto valor en un atributo dado implica retornar un mapa de bits existente que se obtiene a través de un mapeo que relaciona el valor con el mapa de bits, según el apartado d de la reivindicación 1.

8. Procedimiento según la reivindicación 4, en el cual en dicha consulta obtener el valor de un atributo para un objeto dado implica devolver el valor asociado al identificador de objeto en el mapeo de identificadores de objeto a valor del atributo correspondiente, según el apartado e de la reivindicación 1.