ES2713097T3 - Método y aparato para extraer información de una base de datos - Google Patents

Abstract

Método implementado en el ordenador para extraer información a partir de una base de datos, donde dicho método incluye una cadena secuencial de cálculos principales que incluye un primer cálculo principal (P1) que opera un primer elemento de selección (S1) en un conjunto de datos (R0) que representa la base de datos para producir un resultado intermedio (R1), y un segundo cálculo principal (P2) que opera un segundo elemento de selección (S2) en el resultado intermedio (R1) para producir un resultado final (R2), donde dicho método incluye además la recuperación del resultado final mediante las etapas de: (a) calcular un primer valor de identificador de selección (ID1) como una huella digital estadísticamente única generada por una función hash de al menos el primer elemento de selección (S1); (b) buscar, en los objetos de la estructura de datos, el primer valor de identificador de selección (ID1) y, si se encuentra el primer valor de identificador de selección (ID1), localizar y recuperar un primer identificador de resultado (ID2), almacenado con el primer valor de identificador de selección (ID1), como objetos asociados en una iteración precedente; (c) si el primer identificador de resultado (ID2) se encuentra en la subetapa (b), calcular un segundo valor de identificador de selección (ID3) como una huella digital estadísticamente única generada por una función hash de al menos el segundo elemento de selección (S2) y el primer identificador de resultado (ID2) recuperado, y buscar, en los objetos de la estructura de datos, el segundo valor de identificador de selección (ID3) y, si se encuentra el segundo valor de identificador de selección (ID3), localizar y recuperar un resultado final (R2), almacenado con el segundo valor de identificador de selección (ID3), como objetos asociados en una iteración precedente; (d) si el primer identificador de resultado (ID2) no se encuentra en la subetapa (b), ejecutar el primer cálculo principal (P1) para producir el resultado intermedio (R1) y el primer valor de identificador de resultado (ID2) como una huella digital generada por una función hash del resultado intermedio (R1), almacenar el primer valor de identificador de selección (ID1) y el primer valor de identificador de resultado (ID2) como objetos asociados en la estructura de datos; y almacenar el primer valor de identificador de resultado (ID2) y el resultado intermedio (R1) como objetos asociados en la estructura de datos, calcular un segundo valor de identificador de selección (ID3) como una huella digital estadísticamente única generada por una función hash del primer valor de identificador de resultado (ID2) y el segundo elemento de selección (S2), y buscar en los objetos de la estructura de datos basándose en el segundo valor de identificador de selección (ID3) y, si se encuentra el segundo valor de identificador de selección (ID3), localizar y recuperar un resultado final (R2) almacenado con el segundo valor de identificador de selección (ID3) como objetos asociados en una iteración precedente; (e) si el resultado final (R2) no se encuentra en la subetapa (c) o (d), buscar, en los objetos de la estructura de datos basados en el primer valor de identificador de resultado (ID2); (f) si el primer valor de identificador de resultado (ID2) no se encuentra en la subetapa (e), ejecutar el primer cálculo principal (P1) para producir el resultado intermedio (R1) y el primer valor de identificador de resultado (ID2) como una huella digital generada por una función hash del resultado intermedio (R1), almacenar el primer valor de identificador de resultado (ID2) y el resultado intermedio (R1) como objetos asociados en la estructura de datos, y ejecutar el segundo cálculo principal (P2) para producir el resultado final (R2) y almacenar el segundo valor de identificador de selección (ID3) y el resultado final (R2) como objetos asociados en la estructura de datos; y (g) si el primer valor de identificador de resultado (ID2) se encuentra en la subetapa (e), recuperar el resultado intermedio (R1) almacenado con el primer valor de identificador de resultado (ID2) como objetos asociados en una iteración precedente, y ejecutar el segundo cálculo principal (P2) para producir el resultado final (R2) y almacenar el segundo valor de identificador de selección (ID3) y el resultado final (R2) como objetos asociados en la estructura de datos.

Description

DESCRIPCION

Metodo y aparato para extraer informacion de una base de datos

Campo tecnico

[0001] La presente invencion se refiere a tecnicas para extraer informacion de una base de datos y, en particular, a tecnicas que implican una cadena secuencial de calculos principales que comprende un primer calculo principal que opera un primer elemento de seleccion en un conjunto de datos que representan la base de datos para producir un primer resultado, y un segundo calculo principal que opera un segundo elemento de seleccion en el primer resultado para producir un segundo resultado.

Estado de la tecnica

[0002] Con frecuencia, se desea extraer informacion especifica de una base de datos y, especialmente, resumir una gran cantidad de datos en la base de datos y presentar los datos resumidos a un usuario de una forma clara. Dicho procesamiento de datos normalmente se lleva a cabo por un ordenador y puede requerir una capacidad de memoria y una potencia de tratamiento significativas por parte del ordenador. El procesamiento de datos puede tener como objetivo la creacion de una estructura de datos grande comunmente conocida como un cubo multidimensional, a la que el usuario puede a su vez acceder para explorar los datos de la base de datos, por ejemplo visualizando datos seleccionados en las tablas dinamicas o graficamente en graficos 2D y 3D. Un ejemplo de un algoritmo eficaz para crear dicho cubo multidimensional se conoce de la patente US705862.

[0003] Este algoritmo del estado de la tecnica, como muchos otros algoritmos que operan en datos en una base de datos, implica una cadena secuencial de calculos principales, en los que el resultado de un calculo principal se usa como datos de entrada por un calculo principal posterior. Por ejemplo, en el contexto de la patente US7058621, el registro de datos de la base de datos se lee en la memoria principal, a partir de lo cual un usuario puede seleccionar una o mas variables y, opcionalmente, un valor o rango de valores para cada variable, provocando de esta forma que el algoritmo extraiga un subconjunto correspondiente del registro de datos en la base de datos. El subconjunto extraido forma un resultado intermedio. El cubo multidimensional se calcula a continuacion evaluando una funcion matematica seleccionada en el subconjunto extraido, donde la evaluacion de la funcion matematica se lleva a cabo basandose en un conjunto seleccionado de variables de calculo, y donde las dimensiones del cubo se obtienen de un conjunto seleccionado de variables de clasificacion.

[0004] Aunque el algoritmo del estado de la tecnica es eficaz, todavia puede necesitar llevar a cabo un gran numero de operaciones para crear el cubo multidimensional, especialmente si se deben analizar grandes cantidades de datos. En dichas situaciones, el algoritmo puede establecer requisitos indeseablemente altos en el hardware de procesamiento y/o presentar un tiempo de calculo mas largo de lo preferible.

[0005] La patente US2006/0230024 se refiere a un metodo para una infraestructura cache basada en el contexto para habilitar la consulta en el subconjunto acerca de un objeto en cache. En respuesta a la deteccion de una consulta a un contexto raiz de un arbol de contexto, se atraviesa el arbol hasta un contexto original de un subcontexto que corresponde con el par de nombre y valor, que es identificado por un usuario en la consulta. Si el contexto original almacena en cache todos resultados de la consulta, los resultados de la consulta se iteran y los pares de nombre y valor restantes se ignoran. Sin embargo, si el contexto original no almacena en cache todos los resultados de la consulta, la etapa de atravesar se repite para el siguiente contexto original del subcontexto hasta que se encuentra un contexto raiz. Si se encuentra un contexto raiz, se expide una consulta a la base de datos para el par de nombre y valor y el resultado de la consulta a la base de datos se almacena en cache en un contexto nuevo.

Resumen

[0006] Un objetivo de la invencion es superar al menos parcialmente una o mas de las limitaciones del estado de la tecnica identificadas anteriormente.

[0007] Este y otros objetivos, que apareceran en la descripcion siguiente, se consiguen al menos parcialmente mediante un metodo, un medio legible por ordenador y un aparato segun las reivindicaciones independientes, donde los ejemplos de realizacion de los mismos se definen por las reivindicaciones dependientes.

[0008] Un primer aspecto de la invencion es un metodo implementado por ordenador para extraer informacion de una base de datos, donde dicho metodo comprende una cadena secuencial de calculos principales que comprende un primer calculo principal que opera un primer elemento de seleccion en un conjunto de datos que representa la base de datos para producir un resultado intermedio, y un segundo calculo principal que opera un segundo elemento de seleccion en el resultado intermedio para producir un resultado final, donde dicho metodo comprende ademas la recuperacion del resultado final mediante las etapas de:

(a) calcular un primer valor de identificador de seleccion (ID1) como una huella digital estad^sticamente unica generada por una funcion hash de al menos el primer elemento de seleccion (S1);

(b) buscar, en los objetos de la estructura de datos, el primer valor de identificador de seleccion (ID1) y, si se encuentra el primer valor de identificador de seleccion (ID1), localizar y recuperar un primer identificador de resultado (ID2) almacenado con el primer valor de identificador de seleccion (ID1) como objetos asociados en una iteracion precedente;

(c) si el primer identificador de resultado (ID2) se encuentra en la subetapa (b),

calcular un segundo valor de identificador de seleccion (ID3) como una huella digital estadisticamente unica generada por una funcion hash de al menos el segundo elemento de seleccion (S2) y el primer identificador de resultado (ID2) recuperado, y

buscar, en los objetos de la estructura de datos, el segundo valor de identificador de seleccion (ID3) y, si se encuentra el segundo valor de identificador de seleccion (ID3), localizar y recuperar un resultado final (R2) almacenado con el segundo valor de identificador de seleccion (ID3) como objetos asociados en una iteracion precedente;

(d) si no se encuentra el primer identificador de resultado (ID2) en la subetapa (b),

ejecutar el primer calculo principal (P1) para producir el resultado intermedio (R1) y el primer valor de identificador de resultado (ID2) como una huella digital generada por una funcion hash del resultado intermedio (R1),

almacenar el primer valor de identificador de seleccion (ID1) y el primer valor de identificador de resultado (ID2) como objetos asociados en la estructura de datos; y

almacenar el primer valor de identificador de resultado (ID2) y el resultado intermedio (R1) como objetos asociados en la estructura de datos,

calcular un segundo valor de identificador de seleccion (ID3) como una huella digital estadisticamente unica generada por una funcion hash del primer valor de identificador de resultado (ID2) y el segundo elemento de seleccion (S2), y

buscar en los objetos de la estructura de datos basandose en el segundo valor de identificador de seleccion (ID3) y, si se encuentra el segundo valor de identificador de seleccion (ID3), localizar y recuperar un resultado final (R2) almacenado con el segundo valor de identificador de seleccion (ID3) como objetos asociados en una iteracion precedente;

(e) si no se encuentra el resultado final (R2) en la subetapa (c) o (d),

buscar en los objetos de la estructura de datos basandose en el primer valor de identificador de resultado (ID2);

(f) si no se encuentra el primer valor de identificador de resultado (ID2) en la subetapa (e),

ejecutar el primer calculo principal (P1) para producir el resultado intermedio (R1) y el primer valor de identificador de resultado (ID2) como una huella digital generada por una funcion hash del resultado intermedio (R1),

almacenar el primer valor de identificador de resultado (ID2) y el resultado intermedio (R1) como objetos asociados en la estructura de datos, y

ejecutar el segundo calculo principal (P2) para producir el resultado final (R2) y almacenar el segundo valor de identificador de seleccion (ID3) y el resultado final (R2) como objetos asociados en la estructura de datos; y

(g) si se encuentra el primer valor de identificador de resultado (ID2) en la subetapa (e),

recuperar el resultado intermedio (R1) almacenado con el primer valor de identificador de resultado (ID2) como objetos asociados en una iteracion precedente, y

ejecutar el segundo calculo principal (P2) para producir el resultado final (R2) y almacenar el segundo valor de identificador de seleccion (ID3) y el resultado final (R2) como objetos asociados en la estructura de datos.

[0009] De esta forma, en el metodo segun el primer aspecto, el primer y el segundo resultado se guardan en cache en la memoria informatica y quedan disponibles para su reutilizacion en iteraciones posteriores del metodo, reduciendo asi la necesidad de ejecutar el primer y/o segundo calculo principal para la extraccion de la informacion. La reutilizacion puede implicar calcular el primer y/o segundo valor de identificador de seleccion durante una iteracion posterior y acceder a la estructura de datos para recuperar potencialmente el primer y/o segundo resultado.

[0010] Un segundo aspecto de la invencion es un medio legible por ordenador con un programa informatico almacenado que, cuando lo ejecuta un ordenador, es apto para llevar a cabo el metodo segun el primer aspecto.

[0011] Un tercer aspecto de la invencion es un aparato para extraer informacion de una base de datos, donde dicho aparato incluye medios para ejecutar una cadena secuencial de calculos principales que comprende un primer calculo principal que opera un primer elemento de seleccion en un conjunto de datos que representa la base de datos para producir un primer resultado, y un segundo calculo principal que opera un segundo elemento de seleccion en el primer resultado para producir un segundo resultado, donde dicho aparato comprende ademas medios para recuperar el resultado final mediante los pasos de:

(a) calcular un primer valor de identificador de seleccion (ID1) como una huella digital estadisticamente unica generada por una funcion hash de al menos el primer elemento de seleccion (S1);

(b) buscar, en los objetos de la estructura de datos, el primer valor de identificador de seleccion (ID1) y, si se encuentra el primer valor de identificador de seleccion (ID1), localizar y recuperar un primer identificador de resultado (ID2) almacenado con el primer valor de identificador de seleccion (ID1) como objetos asociados en una iteracion precedente;

(c) si se encuentra el primer identificador de resultado (ID2) en la subetapa (b),

calcular un segundo valor de identificador de seleccion (ID3) como una huella digital estadisticamente unica generada por una funcion hash de al menos el segundo elemento de seleccion (S2) y el primer identificador de resultado (ID2) recuperado, y

buscar, en los objetos de la estructura de datos, el segundo valor de identificador de seleccion (ID3) y, si se encuentra el segundo valor de identificador de seleccion (ID3), localizar y recuperar un resultado final (R2) almacenado con el segundo valor de identificador de seleccion (ID3) como objetos asociados en una iteracion precedente;

(d) si no se encuentra el primer identificador de resultado (ID2) en la subetapa (b),

ejecutar el primer calculo principal (P1) para producir el resultado intermedio (R1) y el primer valor de identificador de resultado (ID2) como una huella digital generada por una funcion hash del resultado intermedio (R1),

almacenar el primer valor de identificador de seleccion (ID1) y el primer valor de identificador de resultado (ID2) como objetos asociados en la estructura de datos; y

almacenar el primer valor de identificador de resultado (ID2) y el resultado intermedio (R1) como objetos asociados en la estructura de datos,

calcular un segundo valor de identificador de seleccion (ID3) como una huella digital estadisticamente unica generada por una funcion hash del primer valor de identificador de resultado (ID2) y el segundo elemento de seleccion (S2), y

buscar en los objetos de la estructura de datos basandose en el segundo valor de identificador de seleccion (ID3) y, si se encuentra el segundo valor de identificador de seleccion (ID3), localizar y recuperar un resultado final (R2) almacenado con el segundo valor de identificador de seleccion (ID3) como objetos asociados en una iteracion precedente;

(e) si el resultado final (R2) no se encuentra en la subetapa (c) o (d),

buscar en los objetos de la estructura de datos basandose en el primer valor de identificador de resultado (ID2);

(f) si el primer valor de identificador de resultado (ID2) no se encuentra en la subetapa (e),

ejecutar el primer calculo principal (P1) para producir el resultado intermedio (R1) y el primer valor de identificador de resultado (ID2) como una huella digital generada por una funcion hash del resultado intermedio (R1),

almacenar el primer valor de identificador de resultado (ID2) y el resultado intermedio (R1) como objetos asociados en la estructura de datos, y

ejecutar el segundo calculo principal (P2) para producir el resultado final (R2) y almacenar el segundo valor de identificador de seleccion (ID3) y el resultado final (R2) como objetos asociados en la estructura de datos; y

(g) si el primer valor de identificador de resultado (ID2) se encuentra en la subetapa (e),

recuperar el resultado intermedio (R1) almacenado con el primer valor de identificador de resultado (ID2) como objetos asociados en una iteracion precedente, y

ejecutar el segundo calculo principal (P2) para producir el resultado final (R2) y almacenar el segundo valor de identificador de seleccion (ID3) y el resultado final (R2) como objetos asociados en la estructura de datos.

[0012] El aparato del tercer aspecto comparte las ventajas del metodo del primer aspecto y puede comprender caracteristicas adicionales que corresponden a cualquiera de los ejemplos de realizacion anteriormente descritos en relacion con el primer aspecto.

[0013] Otros objetivos, caracteristicas, aspectos y ventajas de la presente invencion apareceran en la siguiente descripcion detallada, las reivindicaciones adjuntas y los dibujos.

Breve descripcion de los dibujos

[0014] Los ejemplos de realizacion de la invencion se describiran a continuacion con mas detalle con referencia a los dibujos esquematicos de acompanamiento, donde los mismos numeros de referencia se utilizan para identificar los elementos correspondientes.

La Fig. 1 ilustra un proceso que implica una cadena de calculos para extraer informacion de una base de datos, donde los identificadores y los resultados se almacenan selectivamente y se recuperan de una memoria informatica.

La Fig. 2 ilustra un ejemplo de un proceso como se muestra en la Fig. 1.

La Fig. 3 ilustra otro ejemplo de un proceso como se muestra en la Fig. 1.

La Fig. 4 ilustra una forma de realizacion del proceso de la Fig. 1.

La Fig. 5 ilustra otro ejemplo de un proceso como se muestra en la Fig. 1.

La Fig. 6 es un diagrama de flujo que ejemplifica el proceso de la Fig. 5.

La Fig. 7 es una vision de conjunto del proceso de la Fig. 5 implementada en un contexto especifico

La Fig. 8 es un diagrama de bloques de un entorno de ordenador para implementar los ejemplos de realizacion de la invencion.

Descripcion detallada de las formas de realizacion ejemplares

[0015] La presente invencion se refiere a tecnicas para extraer informacion a partir de una base de datos. Para una mayor facilidad de comprension, algunos principios subyacentes se discutiran en primer lugar en relacion con un ejemplo general. Mas adelante, se comentaran diferentes aspectos, caracteristicas y ventajas en relacion con una implementacion especifica.

GENERAL

[0016] La Fig. 1 ilustra un ejemplo de un proceso implementado en el ordenador para extraer informacion de una base de datos DB, que puede almacenarse o no almacenarse de forma externa al ordenador que implementa el proceso. El proceso de extraccion incluye la extraccion de un conjunto o campo de datos inicial RO de la base de datos DB, por ejemplo leyendo el conjunto de datos inicial RO en la memoria principal (por ejemplo RAM) del ordenador. El conjunto de datos inicial RO puede incluir todo el contenido de la base de datos DB o un subconjunto de la misma.

[0017] El proceso de la Figura 1 incluye una secuencia de procedimientos de calculo principales PI, P2 que operan para generar un resultado final R2 basado en el conjunto de datos inicial RO. En concreto, un primer procedimiento PI opera en el conjunto de datos inicial RO para producir un resultado intermedio R1, y el segundo procedimiento P2 opera en el resultado intermedio para producir el resultado final R2.

[0018] Un primer elemento de seleccion S1, que puede originarse o no a partir de una entrada del usuario, controla el primer procedimiento P1. De forma similar, un segundo elemento de seleccion S2, que puede originarse o no a partir de una entrada del usuario, controla el segundo procedimiento P2. Cada elemento de seleccion S1, S2 puede incluir cualquier combinacion de variables y para funciones matematicas que definen los datos de entrada al respectivo procedimiento, es decir, el conjunto de datos RO y el resultado intermedio R1, respectivamente.

[0019] La Fig. 1 tambien indica que el proceso de extraccion interactua con una memoria informatica 10 (habitualmente memoria RAM o cache), con el primer y el segundo procedimiento PI, P2 operando para almacenar elementos de datos en la memoria 10 y recuperar los elementos de datos de la memoria 10. En el ejemplo ilustrado, el primer procedimiento PI opera para memorizar y recuperar los identificadores, generalmente designados por ID, y los resultados intermedios R1; y el segundo procedimiento P2 opera para memorizar y recuperar los identificadores, generalmente designados por ID, los resultados intermedios R1 y los resultados finales R2. En lo sucesivo, el procedimiento de almacenamiento de identificadores y resultados en la memoria informatica 10 tambien se denominara "almacenamiento en cache".

[0020] Los diferentes identificadores se generan habitualmente mediante los procedimientos PI, P2 en funcion de uno o mas parametros del proceso, tales como otro identificador y/o un elemento de seleccion S1, S2 y/o un resultado R1, R2. Las diferentes funciones pueden usarse o no para generar diferentes identificadores. La/las funcion/funciones para generar un identificador puede(n) ser un algoritmo de hash que genere una huella digital del/de los parametro(s) de proceso pertinente(s). La funcion/funciones se configura(n) adecuadamente de manera que cada combinacion de valores de parametro unicos tiene como resultado un valor identificador que es unico entre todos los valores identificadores que se generan para todos los diferentes identificadores en el proceso. En este contexto, "unico" no solo incluye valores de identificador teoricamente unicos, sino tambien valores de identificador estadisticamente unicos. Un ejemplo no limitativo de dicha funcion es un algoritmo de hash que genera una huella digital de al menos 256 bits.

[0021] En un proceso ilustrado mas adelante en la Fig. 2, el primer procedimiento P1 se configura para que calcule un primer valor de identificador de seleccion ID 1 en funcion del primer elemento de seleccion S1, es decir ID1=f(S1) y el segundo procedimiento P2 se configura para que calcule un segundo valor de identificador de seleccion ID3 en funcion del segundo elemento de seleccion S2 y el resultado intermedio R1, es decir ID3=f(S2, Rl). El primer procedimiento P1 tambien se configura para que almacene ID1 y el resultado intermedio R1 como objetos asociados en una estructura de datos 12 en la memoria informatica, y el segundo procedimiento P2 se configura para que almacene ID3 y R2 como objetos asociados en la estructura de datos 12. De este modo, la estructura de datos 12 en la memoria informatica 10 se configura para que almacene un conjunto heterogeneo de objetos, es decir, objetos de diferentes tipos.

[0022] Este proceso permite una reduccion del tiempo de respuesta en el proceso de extraccion y/o una reduccion de los requisitos de tratamiento del ordenador que implementa el proceso de extraccion reduciendo la necesidad de ejecutar los procedimientos de calculo principales PI, P2 para calcular el resultado intermedio R1 y el resultado final R2, respectivamente. Por ejemplo, el proceso de extraccion se puede configurar para que use la estructura de datos 12, siempre que sea posible, para encontrar el resultado final R2 basado en el primer elemento de seleccion S1 y el segundo elemento de seleccion S2. Asi, cuando el proceso descubre una necesidad de calcular el resultado final R2, basado en S1 y S2, puede generar ID1=f(S1) y acceder a la estructura de datos 12 basada en ID1. Si se ha usado un primer elemento de seleccion S1 identico con el primer procedimiento P1 precedente, es posible encontrar el valor generado de ID1 en la estructura de datos 12 y que este se asocie con el resultado intermedio correspondiente R1. De este modo, el resultado intermedio R1 se puede recuperar a partir de la estructura de datos 12 en lugar de calculandolo mediante el procedimiento P1. Si el resultado intermedio R1 no se encuentra en la estructura de datos 12, el proceso puede hacer que el primer procedimiento P1 calcule el resultado intermedio R1. Ademas, despues de la obtencion del resultado intermedio R1, el proceso puede generar ID3=f(R1; S2) y acceder a la estructura de datos 12 basada en ID3. Nuevamente, si la misma operacion ha sido ejecutada por el procedimiento anterior, es posible que el valor generado de ID3 se encuentre en la estructura de datos 12 y se asocie al resultado final correspondiente R2. Por lo tanto, el resultado final R2 se puede recuperar de la estructura de datos 12 en lugar de calculandolo mediante el procedimiento P2.

[0023] En el proceso ilustrado mas adelante en la Fig. 3, el primer procedimiento P1 se configura posteriormente para calcular un primer valor de identificador de resultado ID2 en funcion del resultado intermedio R1. El primer procedimiento P1 tambien se configura para que almacene ID 1 e ID2 como objetos asociados en la estructura de datos 12 y para que almacene ID2 y el resultado intermedio R1 como objetos asociados en la estructura de datos 12.

[0024] Esta forma de realizacion del proceso permite una reduccion del tamano de la memoria informatica requerida por el proceso, ya que cada resultado intermedio R1 se almacena solo una vez en la estructura de datos 12, aunque dos o mas primeros elementos de seleccion S1 produzcan resultados intermedios identicos R1. Esta forma de realizacion es particularmente pertinente cuando los resultados intermedios R1 son altos, que es con frecuencia el caso cuando se procesa informacion de bases de datos.

[0025] El calculo del primer valor de identificador de resultado ID2 tambien permite una forma de realizacion, ilustrada en la Fig. 4, en la que el resultado intermedio R1 se representa mediante el primer valor de identificador de resultado ID2 en el calculo del segundo valor de identificador de seleccion ID3, es decir ID3=f(ID2, S2).

[0026] Esta forma de realizacion reduce la necesidad de almacenar el resultado intermedio R1 en la estructura de datos 12, ya que se puede recuperar el resultado final R2 de la estructura de datos 12 basandose en ID3, que se genera basandose en ID2, no el resultado intermedio R1. Esto permite calcular eficazmente el resultado final R2, aunque el resultado intermedio R1 se ha eliminado de la estructura de datos 12. Por ejemplo, el proceso se puede configurar para que use la estructura de datos 12, siempre que sea posible, para encontrar el resultado final R2 basandose en el primer elemento de seleccion S1 y el segundo elemento de seleccion S2. Asi, cuando el proceso descubre una necesidad de calcular el resultado final R2, basandose en S1 y S2, puede generar ID1=f(S1) y acceder a la estructura de datos 12 basandose en ID1 para recuperar ID2 asociado con ello, si previamente se ha usado un primer elemento de seleccion identico S1 con el primer procedimiento P1. A continuacion, el proceso puede generar ID3=f(ID2; S2) y acceder a la estructura de datos 12 basandose en ID3 para recuperar el resultado final R2 asociado con ello, si el segundo procedimiento P2 ha operado en un resultado intermedio identico R1 y un segundo elemento de seleccion identico S2 previamente. En este ejemplo, el resultado final R2 puede recuperarse asi de la estructura de datos 12 aunque se haya eliminado el resultado intermedio R1.

[0027] En un proceso ilustrado en la Fig. 5, el primer procedimiento P1 se configura posteriormente para que calcule un segundo valor de identificador de resultado ID4 en funcion del resultado final R2. El segundo procedimiento P2 tambien se configura para que almacene ID3 e ID4 como objetos asociados en la estructura de datos 12 y para que almacene ID4 y el resultado final R2 como objetos asociados en la estructura de datos 12.

[0028] Este proceso permite reducir el tamano de la memoria informatica requerida por el proceso, ya que cada resultado final R2 se almacena solo una vez en la estructura de datos 12, aunque dos o mas segundos elementos de seleccion S2 produzcan resultados finales identicos R2. Este proceso es particularmente pertinente cuando los resultados finales R2 son altos.

[0029] Hasta ahora, se ha supuesto que la base de datos DB, y por tanto el conjunto de datos R0, es estatica. Si la base de datos es dinamica, puede ser adecuado generar el primer identificador de seleccion ID1 en funcion del primer elemento de seleccion S1 y el conjunto de datos R0, es decir, ID1=f(S1, R0). Con dicha modificacion, todos los procesos y formas de realizacion descritos en relacion con la Fig. 1-5 se pueden aplicar igualmente a una base de datos dinamica, es decir, una base de datos que puede cambiar en cualquier momento.

[0030] La Fig. 6 es un diagrama de flujo que ilustra una implementacion de ejemplificacion del proceso mostrado en la Fig. 5, adaptado para que opere en una base de datos dinamica. El proceso comienza con la entrada del conjunto de datos R0 (etapa 600), el primer elemento de seleccion S1 (etapa 602) y el segundo elemento de seleccion S2 (604). A continuacion, se genera un valor del primer identificador de seleccion ID1 en funcion de S1 y R0 (etapa 606). Se lleva a cabo una busqueda en la estructura de datos basada en ID1 (etapa 608). Si se encuentra el valor de ID1 en la estructura de datos, es decir, se ha almacenado en cache en una iteracion precedente, el proceso recupera el valor del primer identificador de resultado ID2 asociado con ello (etapa 610) y procede a la etapa 612.

[0031] Si no se encuentra el valor de ID1 en la estructura de datos en la etapa 608, el proceso provoca que el primer procedimiento P1 calcule R1, operando S1 en R0 (etapa 614). A continuacion, el valor de ID2 se genera en funcion de R1 (etapa 616), y los valores de ID1, ID2 y R1 se almacenan en la estructura de datos en pares asociados ID1:ID2 e lD2:R1 (etapa 618). Seguidamente, el proceso continua a la etapa 612.

[0032] En la etapa 612, el valor del segundo identificador de seleccion ID3 se genera en funcion de S2 e ID2. Despues, se lleva a cabo una busqueda en la estructura de datos basada en ID3 (etapa 620). Si se encuentra el valor de ID3 en la estructura de datos, es decir, se ha almacenado en cache en una iteracion precedente, el proceso recupera el valor del segundo identificador de resultado ID4 asociado con ello (etapa 622). Se lleva a cabo una busqueda adicional en la estructura de datos basada en ID4 (etapa 624). Si se encuentra el valor de ID4 en la estructura de datos, es decir, se ha almacenado en cache en una iteracion precedente, el proceso recupera el resultado final R2 asociado con ello (etapa 626).

[0033] Si no se encuentra el valor de ID3 en la estructura de datos en la etapa 620, se lleva a cabo una busqueda adicional en la estructura de datos basada en el valor de ID2 determinado en la etapa 610 o en la etapa 616 (etapa 628). Si se encuentra el valor de ID2 en la estructura de datos, es decir, se ha almacenado en cache en una iteracion precedente, el proceso recupera el primer resultado R1 asociado con ello (etapa 630). El proceso provoca a continuacion que el segundo procedimiento P2 calcule R2, operando S2 en R1 (etapa 632). Para actualizar la estructura de datos, el proceso tambien genera el valor de ID4 en funcion de R2 (etapa 634) y almacena los valores de ID3, ID4 y R2 en la estructura de datos en pares asociados ID3:ID4 e ID4:R2 (etapa 636).

[0034] Si no se encuentra el valor de ID2 en la estructura de datos en la etapa 628, el proceso provoca que el primer procedimiento P1 calcule R1, operando S1 en R0 (etapa 638), y almacena los valores de ID2 y R1 en la estructura de datos en un par asociado ID2:R1 (etapa 640). El proceso procede a continuacion a la etapa 632. Sin embargo, debe tenerse en cuenta que si el resultado intermedio R1 ya se ha calculado en la etapa 614, no es necesario realizar las etapas 628, 630, 638 y 640. En tal caso, si ID3 no se encuentra en la etapa 620, el proceso puede proceder directamente a la etapa 632, donde se provoca que el segundo procedimiento P2 calcule R2, operando S2 en R1.

[0035] Si no se encuentra el valor de ID4 en la estructura de datos en la etapa 622, el proceso provoca que el segundo procedimiento P2 calcule R2, operando S2 en R1 (etapa 642). Para actualizar la estructura de datos, el proceso tambien genera el valor de ID4 en funcion de R2 (etapa 644) y almacena los valores de ID4 y R2 en la estructura de datos en un par asociado ID4:R2 (etapa 646).

[0036] El experto entendera facilmente que los procesos y ejemplos de realizacion de las Figs. 2-4 provocan los procesos de almacenamiento y recuperacion correspondientes, utilizando sin embargo combinaciones de identificadores diferentes. Para mantener la brevedad de la presentacion, estos procesos no se ilustran en las tablas de flujo, sino que se presentan meramente como procesos de ejemplificacion y formas de realizacion en la seccion Resumen precedente.

[0037] Debe comprenderse que se puede utilizar cualquier estructura de datos 12, lineal o no lineal, para almacenar los identificadores y resultados. Sin embargo, por cuestiones de velocidad de tratamiento, puede ser preferible usar una estructura de datos 12 con un sistema de indice eficaz, como una lista ordenada, una tabla hash o un arbol binario, como un arbol AVL.

Formas de realizacion espedficas, aplicaciones y ejemplos

[0038] En lo sucesivo, se comentaran y ejemplificaran en detalle formas de realizacion de la invencion, aplicaciones y ejemplos.

[0039] En algunas formas de realizacion de la invencion, se usan calculos y resultados previos en el procesamiento de las peticiones sucesivas para nuevos datos y calculos. Con este fin, el proceso de extraccion se disena para almacenar en cache los resultados durante el procesamiento de las solicitudes de datos. Cuando se procesa una solicitud posterior, el proceso de extraccion determina si ya se ha generado y almacenado en cache un resultado precedente apropiado. Si es asi, el resultado precedente se usa en el procesamiento de la solicitud posterior. Ya que los calculos previos no necesitan regenerarse, se puede reducir considerablemente el tiempo de procesamiento para la solicitud posterior.

[0040] En algunas formas de realizacion de la invencion, se usan identificadores digitales (huellas digitales) para identificar la informacion almacenada en cache y, de esta manera, tambien se puede reutilizar un resultado almacenado en cache cuando se alcanza de forma diferente al calculo precedente.

[0041] En algunas formas de realizacion de la invencion, los identificadores digitales se almacenan en la cache. Concretamente, el identificador de la entrada para un procedimiento de calculo se almacena junto con el identificador digital de la salida del procedimiento de calculo. Por lo tanto, tambien se puede alcanzar el resultado final de una operacion de muchas etapas cuando el/los resultado(s) intermedio(s) complejo(s) requerido(s) se ha(n) eliminado de la cache. Solo se necesita el identificador digital del/de los resultado(s) intermedio(s).

[0042] En algunas formas de realizacion de la invencion, la cache se implementa mediante una estructura de datos que puede almacenar objetos heterogeneos, tales como tablas, subconjuntos de datos, matrices e identificadores digitales.

[0043] Las formas de realizacion de la invencion pueden, por lo tanto, servir para minimizar, o al menos reducir, los tiempos de respuesta para un usuario que consulta un almacenamiento de datos mediante una consulta ejecutada recientemente por el mismo u otro usuario.

[0044] Las formas de realizacion de la invencion tambien pueden servir para minimizar, o al menos reducir, el uso de memoria por la cache al reutilizar la misma entrada de cache para multiples consultas o calculos diferentes, en el caso de que dos consultas o calculos produzcan el mismo resultado.

[0045] Las formas de realizacion de la invencion se pueden aplicar para extraer cualquier tipo de informacion de cualquier tipo de base de datos conocida, como bases de datos relacionales, bases de datos postrelacionales, bases de datos orientadas a objetos, bases de datos jerarquicas, etc. Internet tambien se puede considerar como una base de datos en el contexto de la presente invencion.

[0046] La Fig. 7 divulga una forma de realizacion espedfica de la invencion, que consiste en un proceso de extraccion o busqueda de informacion que implica una consulta de base de datos con un calculo del grafico posterior basada en el resultado de la consulta. El resultado del calculo del grafico, denominado Resultado del grafico, consiste habitualmente en datos que se agregan, clasifican o reagrupan en una, dos o multiples dimensiones, por ejemplo en forma de un cubo multidimensional tal y como se ha comentado en la seccion de Contexto.

[0047] En un primer paso, se define el Campo de busqueda de informacion. En el caso de una consulta de base de datos, el campo se define mediante las tablas incluidas en una instruccion SELECCIONAR (o equivalente) y como estas se unen. Para una busqueda en internet, el campo puede ser un indice de las paginas web encontradas, normalmente tambien organizadas como una o mas tablas. De esta forma, la salida de la primera etapa es un conjunto de datos (cf. R0 en las Figs. 1-6).

[0048] En una segunda etapa, un usuario hace una Seleccion en el conjunto de datos, lo que provoca que un Motor de inferencia evalue un numero de filtros en el conjunto de datos. El motor de inferencia podria ser, por ejemplo, un motor de base de datos, una herramienta de consulta o una herramienta de inteligencia empresarial. Por ejemplo, en una consulta en una base de datos que almacena datos de ordenes transmitidas, esto podria requerir que el ano de la orden sea "2007" y el grupo de productos "Productos lacteos". De esta forma, la seleccion puede definirse unicamente mediante una lista de campos incluidos y, para cada campo, una lista de valores seleccionados o, de manera mas general, una condicion.

[0049] Basandose en la seleccion (cf. S1 en las Figs. 1-6), el motor de inferencia ejecuta un procedimiento de calculo (cf. P1 en las Figs. 1-6) para generar un Subconjunto de datos (cf. R1 en las Figs. 1-6) que representa una parte del campo (cf. R0 en las Figs. 1-6). El subconjunto de datos puede contener asi un conjunto de registros de datos pertinentes del campo, o una lista de referencias (por ejemplo indices, indicadores o numeros binarios) a estos registros de datos pertinentes. En el ejemplo anterior, los registros de datos pertinentes unicamente serian los registros de datos que pertenecen al ano "2007" y al grupo de productos "Productos lacteos".

[0050] Si la seleccion no se ha hecho previamente, el motor de inferencia de la Fig. 7 se acciona para que calcule el subconjunto de datos. Sin embargo, si el calculo se ha hecho previamente, el motor de inferencia se acciona en su lugar para que reutilice el resultado precedente accediendo a una estructura de datos especifica: una "cache".

[0051] Con frecuencia, la etapa siguiente consiste en hacer algunos calculos adicionales, por ejemplo agregacion/agregaciones y/o ordenacion/ordenaciones y/o agrupamiento(s), basados en el subconjunto de datos. En el ejemplo de la Figura 7, estos calculos posteriores se llevan a cabo mediante un Motor del grafico que calcula el Resultado del grafico basado en el subconjunto de datos y un conjunto seleccionado de Propiedades del grafico (cf. S2 en las Figs. 1-6). De esta forma, el motor del grafico ejecuta un procedimiento de calculo del grafico (cf. P2 en las Figs. 1-6) para que genere el resultado del grafico (cf. R2 en las Figs. 1-6). Si estos calculos no se han hecho antes, el motor del grafico de la Fig. 7 se acciona para que genere el resultado del grafico. Sin embargo, si estos calculos se han hecho antes, el motor del grafico se acciona en su lugar para que reutilice el resultado precedente accediendo a la cache antes mencionada. El resultado del grafico puede, a continuacion, ser visualizado por un usuario en tablas dinamicas o, de forma grafica, en graficos 2D y 3D.

[0052] La Fig. 7 tambien ilustra el proceso de uso de la cache, donde f representa el algoritmo de hash que se opera para generar los identificadores digitales, donde ID1-ID4 representan los identificadores digitales generados de esta forma y las flechas de linea continua representan el flujo de datos para generar los identificadores ID1-ID4. Mas adelante en la Fig. 7, las flechas discontinuas representan las busquedas cache.

[0053] En la Fig. 7, cuando un usuario lleva a cabo una seleccion nueva, el motor de inferencia calcula el subconjunto de datos. Asimismo, el identificador ID1 para la seleccion junto con el campo se genera basandose en los filtros en la seleccion y el campo. Posteriormente, el identificador ID2 para el subconjunto de datos se genera a partir de la definicion del subconjunto de datos, habitualmente una secuencia de bits que define el contenido del subconjunto de datos. Finalmente, el ID2 se almacena en la cache utilizando ID1 como identificador de busqueda. Asimismo, la definicion de subconjunto de datos se almacena en la cache usando ID2 como identificador de consulta.

[0054] En la Fig. 7, el calculo del grafico se desarrolla de manera similar. En este caso, hay dos conjuntos de informacion: el subconjunto de datos y las propiedades del grafico pertinentes. El ultimo es, normalmente aunque no restringido a ello, una funcion matematica junto con variables de calculo y variables de clasificacion (dimensiones). Ambos conjuntos de informacion se utilizan para calcular el resultado del grafico y ambos conjuntos de informacion se utilizan tambien para generar el identificador ID3 para la entrada en el calculo del grafico. ID2 ya se habia generado en la etapa precedente, e ID3 se genera como la primera etapa en el procedimiento de calculo del grafico.

[0055] El identificador ID3 se forma a partir de ID2 y las propiedades del grafico pertinentes. ID3 puede verse como un identificador para una instancia especifica de generacion del grafico, que incluye toda la informacion necesaria para calcular un resultado del grafico especifico. Ademas, se crea un identificador de resultado del grafico ID4 a partir de la definicion de resultado del grafico, generalmente una secuencia de bits que define el resultado del grafico. Finalmente, ID4 se almacena en la cache usando ID3 como identificador de busqueda. Asimismo, la definicion de resultado del grafico se almacena en la cache usando ID4 como identificador de busqueda.

[0056] En este ejemplo especifico, se lleva a cabo un almacenamiento en cache del resultado en dos etapas, tanto en el procedimiento de inferencia como en el procedimiento de calculo del grafico. En el procedimiento de inferencia, ID1 e ID2 representan cosas diferentes: la seleccion y la definicion del subconjunto de datos, respectivamente. Si dos selecciones diferentes producen el mismo subconjunto de datos, lo cual es bastante probable, el almacenamiento en cache en dos etapas (ID1:ID2; ID2: subconjunto de datos) provoca que el subconjunto de datos se almacene en cache solo una vez. Esto se denominara en lo sucesivo Combinacion de objetos, es decir, diferentes objetos de datos que en la cache comparten la misma entrada cache. De forma similar, en el procedimiento de calculo del grafico, ID3 e ID4 representan cosas diferentes: la instancia de generacion del grafico y la definicion del resultado del grafico, respectivamente. Si dos instancias de generacion del grafico diferentes producen el mismo resultado del grafico, lo cual es bastante probable, el almacenamiento en cache en dos etapas (ID3:ID4; ID4: resultado del grafico) provoca que el resultado del grafico se almacene en cache solo una vez.

[0057] Ademas, almacenando en cache ID3, el resultado del grafico tambien se puede recrear si la definicion del subconjunto de datos se ha eliminado de la cache. Esto supone una ventaja relevante, ya que la definicion del subconjunto de datos puede ser muy amplia y, por lo tanto, propensa a ser eliminada de la cache si se implementa un mecanismo de eliminacion de la cache. Mas adelante, se describe un ejemplo no limitativo de dicho mecanismo.

[0058] Durante el proceso de extraccion, los identificadores se calculan a partir de la seleccion, las propiedades del grafico pertinentes, etc. y se usa para buscar resultados de calculo posiblemente almacenados en cache, como indican las flechas discontinuas en la Fig. 7. Si se encuentra el identificador, se reutilizara el resultado almacenado en cache correspondiente. Si no se encuentra, el proceso de extraccion generara nuevos identificadores y los almacenara en cache con el resultado respectivo.

[0059] Para ejemplificar de forma adicional el proceso de extraccion, cabe considerar la seleccion antes mencionada del ano de orden "2007" y del grupo de productos "Productos lacteos". La primera etapa consiste en generar un identificador digital ID1 en funcion de esta seleccion, por ejemplo (escrito en notacion hexadecimal): "31dca7ad013964891df428095ad9b78ad7a69eaaa1ca3886bcf05d8f8184e84a".

[0060] Con el objetivo de mantener la brevedad, en el siguiente ejemplo, cada identificador se representa por sus 4 caracteres iniciales. Asi, ID1 se vuelve, en cambio, "31dc". Asimismo, por motivos de claridad, las tablas ilustrativas siguientes incluyen etiquetas de identificador, por ejemplo " iD l:" delante de los identificadores digitales. Esto no es necesario en la solucion real.

[0061] El proceso de extraccion posterior es el siguiente: cuando se ha generado ID1, este se busca en la cache. La primera vez que se lleva a cabo la seleccion, este identificador no se encontrara en la cache, por lo que el subconjunto de datos resultante debe calcularse de la forma normal. Una vez esto se haya hecho, se puede generar ID2 desde el subconjunto de datos para que sea, por ejemplo, "d2b8". A continuacion, ID1 se almacena en cache, senalando a ID2; e ID2 se almacena, senalando a la secuencia de bits que define el subconjunto de datos resultante. Esta secuencia de bits puede tener un tamano considerable. El contenido de la cache se muestra en Tabla 1 mas abajo.

Tabla 1:

ID Valor en cache

ID1:31dc ID2:d2b8

ID2:d2b8 <registros de datos en el subconjunto de datos

resultante>

[0062] En la siguiente ocasion en la que se realice la misma seleccion, el proceso sera diferente: ahora, ID1 se encuentra en la cache, senalando a "ID2:d2b8", que a su vez se usa para una segunda busqueda, tras lo cual la secuencia de bits del subconjunto de datos resultante se encuentra, recupera y utiliza en lugar de un calculo, que consumiria mucho tiempo.

[0063] Cabe considerar ahora el caso en el que se realiza una seleccion diferente, pero que produce el mismo subconjunto de datos resultante. Por ejemplo, puede ocurrir que un usuario seleccione exactamente los clientes que han comprado "Productos lacteos" sin solicitar explicitamente "Productos lacteos" y estos han comprado exclusivamente productos lacteos. En este caso, ID1 se genera como, por ejemplo, "f142" y no se encontrara en la cache. Asi, el subconjunto de datos resultante debe calcularse de la forma normal. Una vez esto este hecho, ID2 se puede generar a partir del subconjunto de datos y se encuentra como "d2b8", que ya se ha almacenado en la cache. Asi, la necesidad del algoritmo solo anade una entrada a la cache, donde "ID1 :f142" senala a "ID2:d2b8". El contenido de la cache se muestra en Tabla 2 mas abajo.

Tabla 2:

ID Valor en cache

ID1 :f142 ID2:d2b8

ID1:31dc ID2:d2b8

ID2:d2b8 <registros de datos en el subconjunto de datos

resultante>

[0064] Esta vez no se ha ahorrado tiempo de calculo, pero las entradas cache se reutilizan para prevenir que la cache aumente de forma innecesaria. Asi, tanto "ID1 :f142" como "ID1:31dc" senalan a la entrada cache que contiene el mismo subconjunto de datos resultante: "ID2:d2b8", y ambos se pueden usar en busquedas posteriores. Esto es, por lo tanto, un ejemplo de la "combinacion de objetos" antes mencionada.

[0065] Una ventaja adicional de almacenar en cache los identificadores digitales resultara evidente cuando se lleve a cabo el calculo del grafico posterior. Asi, se asume que las selecciones anteriores se han llevado a cabo y se ha realizado el calculo del grafico posterior. ID3 e ID4 se han generado como "e40A" y "7505", respectivamente, y almacenado en la cache. El contenido de la cache se muestra en la Tabla 3 mas abajo.

Tabla 3:

ID Valor en cache

ID1 :f142 ID2:d2b8

ID1:31dc ID2:d2b8

ID2:d2b8 <registros de datos en el subconjunto de datos

resultante>

ID3:e40A ID4:7505

ID4:7505 <matriz de numeros que representa el resultado

del grafico>

[0066] De las cinco entradas de la Tabla 3, es muy probable que una sea considerablemente mayor que las demas: "ID2:d2b8", que contiene toda la secuencia de bits que define el subconjunto de datos potencialmente grande. Su tamano la hace una candidata para ser eliminada cuando/si la cache se mantiene, tal y como se describe de forma adicional mas adelante. Asi, despues de un tiempo, el contenido de la cache puede ser tal y como se muestra en la Tabla 4 mas adelante.

Tabla 4:

ID Valor en cache

ID1 :f142 ID2:d2b8

ID1:31dc ID2:d2b8

ID3:e40A ID4:7505

ID4:7505 <matriz de numeros que representa el resultado

del grafico>

[0067] Sin embargo, ya que los identificadores digitales se han almacenado en cache, todavia es posible obtener el resultado del grafico sin tener que recalcular el subconjunto de datos intermedio. En cambio, cuando se lleva a cabo la seleccion, se calcula ID1. A continuacion, se realiza una busqueda de ID1 en la cache, que provoca que se recupere ID2. Posteriormente, ID3 se genera a partir de la combinacion de las propiedades del grafico pertinente e ID2. Se lleva a cabo una busqueda de ID3 en la cache y se recupera ID4. Finalmente, se realiza una busqueda de ID4 en la cache y se recupera el resultado del grafico. Por lo tanto, el resultado del grafico se encuentra sin calculos pesados, sino simplemente basandose en los identificadores digitales, que se pueden generar mediante operaciones rapidas y eficientes durante el procesamiento.

[0068] A partir de lo anterior, se entiende que los identificadores digitales deberian ser unicos de modo que el significado de cada identificador en la cache no sea ambiguo. En una forma de realizacion, los identificadores digitales se generan utilizando un algoritmo o funcion hash. Los algoritmos de hash son transformaciones que se sirven de una entrada de tamano arbitrario (el mensaje) y devuelven una cadena de tamano fijo llamada valor de hash (resumen de mensaje). Normalmente el algoritmo corta y mezcla, por ejemplo, sustituye o traspone, la entrada para crear una huella digital de la misma. Los algoritmos de hash mas sencillos y antiguos son operaciones modulo por primo sencillas. Los algoritmos de hash se usan para una variedad de fines computacionales, incluyendo la criptografia. En terminos generales, un algoritmo de hash deberia comportarse, dentro de lo posible, como una funcion aleatoria, generando cualquier cadena de tamano fijo posible con igual "probabilidad", mientras todavia es verdaderamente determinista.

[0069] Hay multiples algoritmos de hash conocidos y usados frecuentemente que se pueden utilizar para generar los identificadores digitales anteriormente mencionados. Los diferentes algoritmos de hash se optimizan para usos diferentes, donde algunos se optimizan para una computacion eficaz y rapida del valor de hash, mientras que otros se disenan para una seguridad criptografica alta. Un algoritmo con una alta seguridad criptografica se disena para que sea dificil calcular un mensaje que coincida con un valor de hash determinado en un tiempo razonable, y para encontrar un segundo mensaje que genere el mismo valor de hash que un primer mensaje determinado. Dichos algoritmos de hash incluyen SHA (por sus siglas en ingles, algoritmo de hash seguro) y MD5 (por sus siglas en ingles, algoritmo de resumen de mensaje 5). Los algoritmos de hash eficientes en el procesamiento habitualmente muestran una menor seguridad criptografica. Dichos algoritmos de hash incluyen los algoritmos FNV (Fowler/Noll/Vo), disenados para que sean rapidos y mantener generalmente un indice de colision muy bajo. Un algoritmo FNV habitualmente comienza con una base de desplazamiento, que en principio podria ser cualquier cadena de valores aleatoria, pero generalmente, por tradicion, es siempre la firma del inventor en codigo hexadecimal a traves del algoritmo FNV-0 original. Para generar un valor de hash FNV de 256-bits, normalmente se usa la base de desplazamiento siguiente:

"0xdd268dbcaac550362d98c384c4e576ccc8b1536847b6bbb31023b4c8caee0535".

[0070] Para cada byte en la entrada al algoritmo de hash, el desplazamiento se multiplica primero por un numero primo grande, posteriormente se compara con el byte de la entrada y finalmente se calcula la diferencia simetrica a nivel de bits (XOR) para formar el valor de hash para el bucle siguiente. Los numeros primos apropiados se encuentran en la literatura disponible. Cualquier numero primo grande funcionara, pero algunos son mas resistentes a la colision que otros.

[0071] Los identificadores digitales se pueden generar utilizando cualquier algoritmo de hash que sea razonablemente resistente a la colision. En una forma de realizacion, los identificadores se generan utilizando un algoritmo de hash rapido con alta resistencia a la colision y baja seguridad criptografica.

[0072] En una forma de realizacion especifica, se puede crear un identificador de 256-bits mediante concatenacion de cuatro valores de hash FVN de 64-bits, donde cada uno se ha generado utilizando un multiplicador primo diferente. Usando cuatro valores de hash mas cortos y concatenandolos, el identificador se puede generar mas rapido. Para aumentar la velocidad de la generacion del identificador, el algoritmo se puede modificar para que use no solo un byte de la entrada por bucle, sino cuatro bytes. Este puede suponer una perdida de seguridad criptografica, mientras que la resistencia a la colision se mantiene aproximadamente igual.

[0073] Los identificadores con una longitud de al menos 256 bits pueden producir una resistencia a la colision beneficiosa. Un valor de hash de 256-bits significa que hay aproximadamente 1E+77 valores identificadores posibles. Este numero se puede comparar con el numero de atomos en el universo, que se ha estimado en 1E+80. Esto significa que el riesgo de colisiones, es decir, el riesgo de que dos selecciones/subconjuntos de datos/propiedades del grafico/resultados del grafico diferentes produzcan el mismo identificador no es solo extremadamente pequeno, sino insignificante. De esta forma, se puede decir con certeza que el riesgo de colisiones es aceptablemente pequeno. Esto significa que, aunque el algoritmo de hash no genera identificadores teoricamente unicos, si que genera, sin embargo, identificadores estadisticamente unicos. No obstante, debe entenderse que los identificadores con menores longitudes de bit, como 64 o 128 bits, pueden ser lo bastante estadisticamente unicos para una aplicacion especifica.

[0074] Como se ha mencionado anteriormente, se puede implementar un mecanismo de eliminacion para eliminar la cache de entradas antiguas o sin usar. Una estrategia puede ser eliminar la(s) entrada/entradas con menos uso en la cache. Sin embargo, se puede implementar un mecanismo de eliminacion mas avanzado para apoyar la optimizacion tanto del uso del procesador como del uso de la memoria. Una forma de realizacion de dicho mecanismo de eliminacion avanzado opera en tres parametros: Uso, Tiempo de calculo y Memoria necesaria.

[0075] El parametro de Uso es un valor numerico que puede considerar tanto si se ha accedido a una entrada "recientemente, pero no a menudo" como si se ha accedido a la entrada "a menudo, pero no recientemente". Esto se puede lograr asociando cada entrada a un parametro de uso U que se aumenta mediante, por ejemplo, una unidad cada vez que se accede a la entrada, pero reduce su valor exponencialmente, o por cualquier otra funcion, a lo largo del tiempo. En una implementacion, todos los valores de U en la cache se reducen periodicamente en una cantidad fija. Asi, el parametro de uso tiene una vida media, similar a la desintegracion radiactiva. El valor de U reflejara ahora con que frecuencia y hace cuanto tiempo se ha accedido a la entrada.

[0076] Si el tiempo de procesador necesario para calcular una entrada es considerable, entonces la entrada se deberia mantener durante mas tiempo en la cache. Por el contrario, si el tiempo de procesador necesario para el calculo es poco, entonces el coste de recalcular es bajo y el beneficio de mantener la entrada en la cache tambien es bajo. Asi, cada entrada se asocia a un parametro temporal T que representa el tiempo de calculo estimado.

[0077] Si el espacio de memoria necesario para memorizar una entrada es considerable, entonces supone el uso de muchos de los recursos de la cache para mantenerlo y deberia eliminarse de la cache antes que una entrada que requiera menos espacio de memoria. Por el contrario, una entrada que requiera poco espacio de memoria se puede mantener durante mas tiempo en la cache. Asi, cada entrada se asocia con un parametro de memoria M que representa la memoria necesaria estimada.

[0078] Por cada entrada en la cache, los valores de los parametros U, T y M se evaluan mediante una funcion de peso W obtenida por: W = U * T / M.

[0079] Un valor de W alto para una entrada indica que hay buenas razones para mantener esta entrada en la cache. Asi, las entradas con valores W altos deberian mantenerse en la cache y aquellas con valores W bajos deberian ser eliminadas.

[0080] Un mecanismo de eliminacion eficaz puede implicar ordenar la cache segun los valores W y eliminar la cache ordenada en un extremo, es decir, las entradas con los valores W mas bajos. Un metodo posible, pero no necesario, para mantener una cache ordenada podria ser almacenar los identificadores, resultados y valores U, T, M y W como un arbol AVL (Adelson-Velsky y Landis), es decir, un arbol binario de busqueda equilibrado.

[0081] El mecanismo de eliminacion puede eliminar intermitentemente todas las entradas con un valor W que esten por debajo de un valor umbral predeterm inado.

[0082] De forma alternativa, el mecanismo de eliminacion se puede controlar mediante la cantidad de memoria disponible en el ordenador o la proporcion de memoria disponible de la memoria total. Asi, siempre que el tamano de la memoria cache campo un valor umbral de memoria, el mecanismo de eliminacion elimina entradas de las entradas cache basandose en sus respectivos valores W. Ajustando el umbral de memoria, es posible adaptar el tamano de cache a las condiciones del hardware local, por ejemplo intercambiando la potencia de procesamiento con la memoria. Por ejemplo, es posible compensar un procesador mas lento en un ordenador anadiendo mas memoria principal al ordenador y aumentando el umbral de memoria. Asi, se retendran mas resultados en la cache y la necesidad de procesamiento se reducira.

[0083] Las formas de realizacion de la invencion tambien se refieren a un aparato para realizar cualquiera de los algoritmos, metodos, procesos y procedimientos descritos previamente. Este aparato puede construirse especialmente para el fin requerido o puede incluir un ordenador general que se activa o reconfigura selectivamente mediante un programa informatico almacenado en el ordenador.

[0084] La Fig. 8 es un diagrama de bloques de un entorno de ordenador para implementar cualquiera de las formas de realizacion de la invencion. Un usuario 1 interactua con un sistema de tratamiento de datos 2, que incluye un procesador 3 que ejecuta el software del sistema operativo, asi como uno o mas programas de aplicacion que implementan una forma de realizacion de la invencion. El usuario introduce informacion en el sistema de tratamiento de datos 2 usando uno o mas dispositivos de entrada conocidos 4, como un raton, un teclado, un panel tactil, etc. De forma alternativa, la informacion se puede introducir con o sin intervencion del usuario con cualquier otro tipo de dispositivo de entrada, tal como un lector de tarjetas, un lector optico u otro sistema informatico. La respuesta visual se puede hacer llegar al usuario mostrando caracteres, simbolos graficos, ventanas, teclas, etc., en una pantalla 5. El sistema de tratamiento de datos incluye ademas la memoria 10 antes mencionada. El software ejecutado por el procesador 3 almacena informacion acerca de su operacion en la memoria 10 y recupera informacion apropiada desde la memoria 10. La memoria 10 incluye habitualmente una memoria principal (como RAM, memoria cache, etc.) y una memoria secundaria no volatil (disco duro, memoria flash, soporte extraible). La base de datos se puede almacenar en la memoria 10 del sistema de tratamiento de datos o se puede acceder a ella en un dispositivo de memoria externa a traves de una interfaz de comunicaciones 6 en el sistema de tratamiento de datos 2.

[0085] La invencion se ha descrito antes principalmente en referencia a algunas formas de realizacion. Sin embargo, como el experto en la tecnica podra notar facilmente, tambien son posibles otras formas de realizacion aparte de las que se han descrito previamente.

[0086] Por ejemplo, la presente invencion no solo se puede aplicar para calcular cubos multidimensionales, sino que puede ser util en cualquier situacion en la que se extrae informacion de una base de datos que se sirve de una cadena de calculos.

[0087] Ademas, el proceso de extraccion inventivo se puede aplicar a una cadena de calculos que implica mas de dos calculos consecutivos. Por ejemplo, cada uno de dos o mas resultados intermedios en una cadena de calculos se puede almacenar en cache y recuperar posteriormente de forma similar al resultado intermedio descrito anteriormente.

[0088] Asimismo, el proceso de extraccion inventivo no requiere almacenar en cache y posteriormente recuperar el resultado final, sino que puede operar solo para almacenar en cache y recuperar uno o mas resultados intermedios en una cadena de calculos.

[0089] Adicionalmente, se debe tener en cuenta que la etapa inicial de extraccion de un conjunto o campo de datos inicial de la base de datos se puede omitir y el proceso de extraccion puede, en cambio, operar directamente en la base de datos.

Claims (13)

REIVINDICACIONES

1. Metodo implementado en el ordenador para extraer informacion a partir de una base de datos, donde dicho metodo incluye una cadena secuencial de calculos principales que incluye un primer calculo principal (P1) que opera un primer elemento de seleccion (S1) en un conjunto de datos (R0) que representa la base de datos para producir un resultado intermedio (R1), y un segundo calculo principal (P2) que opera un segundo elemento de seleccion (S2) en el resultado intermedio (R1) para producir un resultado final (R2), donde dicho metodo incluye ademas la recuperacion del resultado final mediante las etapas de:

(a) calcular un primer valor de identificador de seleccion (ID1) como una huella digital estadisticamente unica generada por una funcion hash de al menos el primer elemento de seleccion (S1);

(b) buscar, en los objetos de la estructura de datos, el primer valor de identificador de seleccion (ID1) y, si se encuentra el primer valor de identificador de seleccion (ID1), localizar y recuperar un primer identificador de resultado (ID2), almacenado con el primer valor de identificador de seleccion (ID1), como objetos asociados en una iteracion precedente;

(c) si el primer identificador de resultado (ID2) se encuentra en la subetapa (b),

calcular un segundo valor de identificador de seleccion (ID3) como una huella digital estadisticamente unica generada por una funcion hash de al menos el segundo elemento de seleccion (S2) y el primer identificador de resultado (ID2) recuperado, y

buscar, en los objetos de la estructura de datos, el segundo valor de identificador de seleccion (ID3) y, si se encuentra el segundo valor de identificador de seleccion (ID3), localizar y recuperar un resultado final (R2), almacenado con el segundo valor de identificador de seleccion (ID3), como objetos asociados en una iteracion precedente;

(d) si el primer identificador de resultado (ID2) no se encuentra en la subetapa (b),

ejecutar el primer calculo principal (P1) para producir el resultado intermedio (R1) y el primer valor de identificador de resultado (ID2) como una huella digital generada por una funcion hash del resultado intermedio (R1),

almacenar el primer valor de identificador de seleccion (ID1) y el primer valor de identificador de resultado (ID2) como objetos asociados en la estructura de datos; y

almacenar el primer valor de identificador de resultado (ID2) y el resultado intermedio (R1) como objetos asociados en la estructura de datos,

calcular un segundo valor de identificador de seleccion (ID3) como una huella digital estadisticamente unica generada por una funcion hash del primer valor de identificador de resultado (ID2) y el segundo elemento de seleccion (S2), y

buscar en los objetos de la estructura de datos basandose en el segundo valor de identificador de seleccion (ID3) y, si se encuentra el segundo valor de identificador de seleccion (ID3), localizar y recuperar un resultado final (R2) almacenado con el segundo valor de identificador de seleccion (ID3) como objetos asociados en una iteracion precedente;

(e) si el resultado final (R2) no se encuentra en la subetapa (c) o (d),

buscar, en los objetos de la estructura de datos basados en el primer valor de identificador de resultado (ID2); (f) si el primer valor de identificador de resultado (ID2) no se encuentra en la subetapa (e),

ejecutar el primer calculo principal (P1) para producir el resultado intermedio (R1) y el primer valor de identificador de resultado (ID2) como una huella digital generada por una funcion hash del resultado intermedio (R1),

almacenar el primer valor de identificador de resultado (ID2) y el resultado intermedio (R1) como objetos asociados en la estructura de datos, y

ejecutar el segundo calculo principal (P2) para producir el resultado final (R2) y almacenar el segundo valor de identificador de seleccion (ID3) y el resultado final (R2) como objetos asociados en la estructura de datos; y

(g) si el primer valor de identificador de resultado (ID2) se encuentra en la subetapa (e),

recuperar el resultado intermedio (R1) almacenado con el primer valor de identificador de resultado (ID2) como objetos asociados en una iteracion precedente, y

ejecutar el segundo calculo principal (P2) para producir el resultado final (R2) y almacenar el segundo valor de identificador de seleccion (ID3) y el resultado final (R2) como objetos asociados en la estructura de datos.

2. Metodo segun la reivindicacion 1, donde la huella digital comprende al menos 256 bits.

3. Metodo segun la reivindicacion 1 o la reivindicacion 2, que incluye ademas la etapa de eliminar selectivamente los registros de datos que contienen dichos objetos asociados en la estructura de datos, basandose al menos en el tamano del registro de datos.

4. Metodo segun la reivindicacion 3, donde la etapa de eliminacion selectiva se configura para que provoque la eliminacion de los registros de datos que contienen dicho primer resultado (R1).

5. Metodo segun la reivindicacion 3 o 4, que comprende ademas la etapa de asociar cada registro de datos con un valor de peso, que se calcula en funcion de un parametro de uso para cada registro de datos, un parametro de calculo de tiempo para cada registro de datos y un parametro de tamano para cada registro de datos, donde el parametro de uso es un valor numerico que representa con que frecuencia y hace cuanto tiempo se ha accedido al registro de datos, donde el parametro de calculo de tiempo representa el tiempo de calculo estimado para el registro de datos y el parametro de tamano representa el tamano del registro de datos.

6. Metodo segun la reivindicacion 5, donde el valor de peso se calcula evaluando una funcion de peso obtenida por W=U*T/M, donde U es el parametro de uso, T es el parametro de tiempo de calculo y M es el parametro de tamano.

7. Metodo segun la reivindicacion 5 o 6, donde el valor del parametro de uso se incrementa siempre que se accede al registro de datos, mientras que disminuye exponencialmente en funcion del tiempo.

8. Metodo segun cualquiera de las reivindicaciones 4-7, donde la etapa de eliminacion selectiva se basa en el valor de peso del registro de datos en la estructura de datos.

9. Metodo segun cualquiera de las reivindicaciones 4-8, donde la etapa de eliminacion selectiva se desencadena basandose en una comparacion entre un tamano actual de la estructura de datos y un valor umbral.

10. Metodo segun cualquiera de las reivindicaciones precedentes, donde la base de datos es una base de datos dinamica y, por lo tanto, una base de datos que puede cambiar en cualquier momento, y el primer valor de identificador de seleccion (ID1) se calcula en funcion de al menos el primer elemento de seleccion (S1) y el conjunto de datos (R0).

11. Metodo segun cualquiera de las reivindicaciones precedentes, donde el primer elemento de seleccion (S1) define un conjunto de campos en el conjunto de datos (R0) y una condicion para cada campo, donde el resultado intermedio (R1) es representativo de un subconjunto del conjunto de datos (R0), donde el segundo elemento de seleccion (S2) define una funcion matematica, una o mas variables de calculo incluidas en el resultado intermedio (R1) y una o mas variables de clasificacion incluidas en el resultado intermedio (R1), y donde el resultado final (R2) es una estructura de datos de cubo multidimensional que contiene el resultado de operar la funcion matematica en dichas una o mas variables de calculo para cada valor unico de cada variable de clasificacion.

12. Medio legible por ordenador que almacena un programa informatico que, cuando se ejecuta por medio de un ordenador, es apto para llevar a cabo el metodo de cualquiera de las reivindicaciones 1-11.

13. Aparato para extraer informacion a partir de una base de datos, donde dicho aparato comprende medios para ejecutar una cadena secuencial de calculos principales que comprende un primer calculo principal (P1) que opera un primer elemento de seleccion (S1) en un conjunto de datos (R0) que representa la base de datos para producir un resultado intermedio (R1), y un segundo calculo principal (P2) que opera un segundo elemento de seleccion (S2) en el resultado intermedio (R1) para producir un resultado final (R2), donde dicho aparato comprende ademas medios para recuperar el resultado final mediante las etapas de:

(a) calcular un primer valor de identificador de seleccion (ID1) como una huella digital estadisticamente unica generada por una funcion hash de al menos el primer elemento de seleccion (S1);

(b) buscar, en los objetos de la estructura de datos, el primer valor de identificador de seleccion (ID1) y, si se encuentra el primer valor de identificador de seleccion (ID1), localizar y recuperar un primer identificador de resultado (ID2) almacenado con el primer valor de identificador de seleccion (ID1) como objetos asociados en una iteracion precedente;

(c) si el primer identificador de resultado (ID2) se encuentra en la subetapa (b),

calcular un segundo valor de identificador de seleccion (ID3) como una huella digital estadisticamente unica generada por una funcion hash de al menos el segundo elemento de seleccion (S2) y el primer identificador de resultado (ID2) recuperado, y

buscar, en los objetos de la estructura de datos, el segundo valor de identificador de seleccion (ID3) y, si se encuentra el segundo valor de identificador de seleccion (ID3), localizar y recuperar un resultado final (R2) almacenado con el segundo valor de identificador de seleccion (ID3) como objetos asociados en una iteracion precedente;

(d) si el primer identificador de resultado (ID2) no se encuentra en la subetapa (b),

ejecutar el primer calculo principal (P1) para producir el resultado intermedio (R1) y el primer valor de identificador de resultado (ID2) como una huella digital generada por una funcion hash del resultado intermedio (R1),

almacenar el primer valor de identificador de seleccion (ID1) y el primer valor de identificador de resultado (ID2) como objetos asociados en la estructura de datos; y

almacenar el primer valor de identificador de resultado (ID2) y el resultado intermedio (R1) como objetos asociados en la estructura de datos,

calcular un segundo valor de identificador de seleccion (ID3) como una huella digital estadisticamente unica generada por una funcion hash del primer valor de identificador de resultado (ID2) y el segundo elemento de seleccion (S2), y

buscar en los objetos de la estructura de datos basandose en el segundo valor de identificador de seleccion (ID3) y, si se encuentra el segundo valor de identificador de seleccion (ID3), localizar y recuperar un resultado final (R2) almacenado con el segundo valor de identificador de seleccion (ID3) como objetos asociados en una iteracion precedente;

(e) si el resultado final (R2) no se encuentra en la subetapa (c) o (d),

buscar en los objetos de la estructura de datos basandose en el primer valor de identificador de resultado (ID2);

(f) si el primer valor de identificador de resultado (ID2) no se encuentra en la subetapa (e)

ejecutar el primer calculo principal (P1) para producir el resultado intermedio (R1) y el primer valor de identificador de resultado (ID2) como una huella digital generada por una funcion hash del resultado intermedio (R1),

almacenar el primer valor de identificador de resultado (ID2) y el resultado intermedio (R1) como objetos asociados en la estructura de datos, y

ejecutar el segundo calculo principal (P2) para producir el resultado final (R2) y almacenar el segundo valor de identificador de seleccion (ID3) y el resultado final (R2) como objetos asociados en la estructura de datos; y

(g) si el primer valor de identificador de resultado (ID2) se encuentra en la subetapa (e)

recuperar el resultado intermedio (R1) almacenado con el primer valor de identificador de resultado (ID2) como objetos asociados en una iteracion precedente, y

ejecutar el segundo calculo principal (P2) para producir el resultado final (R2) y almacenar el segundo valor de identificador de seleccion (ID3) y el resultado final (R2) como objetos asociados en la estructura de datos.