Operators for reclassification queries in a temporal multidimensional model

Operadores para consultas relacionadas con reclasificaciones en un modelo temporal multidimensional

Data warehouse dimensions are usually considered to be static because their schema and data tend not to change; however, both dimension schema and dimension data can change. This paper focuses on a type of dimension data change called reclassification which occurs when a member of a certain level becomes a member of a higher level in the same dimension, e.g. when a product changes category (it is reclassified). This type of change gives rise to the notion of classification period and to a type of query that can be useful for decision-support. For example, What were total chess-set sales during first classification period in Toy category? A set of operators has been proposed to facilitate formulating this type of query and it is shown how to incorporate them in SQL, a familiar database developer language. Our operators' expressivity is also shown because formulating such queries without using these operators usually leads to complex and nonintuitive solutions.

Usualmente las dimensiones de una bodega de datos son consideradas estáticas porque su esquema y datos tienden a no cambiar. Sin embargo, tanto el esquema como los datos de las dimensiones pueden cambiar. Este artículo se enfoca en un tipo de cambio dimensional denominado reclasificación, que ocurre cuando un miembro de un nivel cambia de miembro en un nivel superior de la dimensión, ejemplo, cuando un producto cambia de categoría (es reclasificado). Este tipo de cambios da lugar al concepto período de clasificación y a un tipo de consultas que pueden ser útiles para la toma de decisiones. Verbigracia, ¿cuál fue el total vendido del producto ajedrez durante su primer periodo de clasificación en la categoría juguete? Para facilitar el planteamiento de este tipo de consultas se propone un conjunto de operadores y se muestra como éstos se incorporan en SQL, un lenguaje familiar para los desarrolladores de bases de datos. También se demuestra la expresividad de los operadores propuestos, ya que la formulación de esas consultas sin usar estos operadores usualmente conduce a soluciones complejas y poco intuitivas.

• HTML (es)
• HTML (en)

Francisco Moreno¹, Fernando Arango²

¹ Ingeniero de sistemas. Ph.D. en Ingeniería, Universidad Nacional de Colombia, Sede Medellín. fjmoreno@unal.edu.co

² Ingeniero Civil. M.Sc y Ph.D. Universidad Nacional de Colombia, Sede Medellín. farango@unal.edu.co

---

RESUMEN

Palabras claves: bodegas de datos temporales, OLAP, reclasificación, período de clasificación.

ABSTRACT

Keywords: temporal data warehouse, OLAP, reclassification, classification period

---

Recibido: febrero 01 de 2010. Aceptado: febrero 7 de 2011

---

Introducción

En los últimos años las bodegas de datos (BD) (Kumar, 2008; Golfarelli, 2009a) han demostrado su utilidad en la integración de sistemas de información y en el soporte a la toma de decisiones. Las BD se modelan usualmente de manera multidimensional. Un modelo multidimensional posee un conjunto de dimensiones asociadas con un fenómeno de interés para una organización denominado hecho. Una dimensión se compone de niveles, organizados jerárquicamente de acuerdo a las necesidades de la información (Torlone, 2003). Así, en una dimensión tiempo con niveles día, mes y año, los días se agrupan en meses y los meses en años; en una dimensión producto con niveles producto y categoría, los productos se agrupan en categorías.

Los hechos típicamente incluyen medidas, es decir, indicadores que permiten evaluar actividades específicas de una organización (Malinowski, 2008). Estas medidas se pueden agregar por medio de los niveles de las dimensiones, lo que permite analizar la información desde diferentes niveles de granularidad. Por ejemplo, considérese un hecho venta, con una medida total vendido, asociado con las dimensiones tiempo y producto. Esta organización de la información facilita consultas tales como "obtener el total vendido de un producto, diaria, mensual o anualmente".

Usualmente las dimensiones se consideran estáticas, mientras que a los hechos se los interpreta dinámicos, ya que nuevos hechos se insertan periódicamente en la BD. Sin embargo, el esquema y los datos de una dimensión también pueden cambiar (Golfarelli, 2009b). Este artículo se enfoca en un tipo de cambios llamado reclasificación y en un tipo de consultas que se originan a raíz de dichos cambios. Una reclasificación sucede cuando un miembro de un nivel cambia de miembro en un nivel superior de la dimensión, por ejemplo, cuando un producto clasificado como juguete pasa a ser clasificado como educativo.

Las reclasificaciones son frecuentes en diversos escenarios: un producto cambia de categoría, un vendedor rota por las tiendas, una tienda o un cliente cambian de estatus, un jugador cambia de equipo, un huracán se mueve de una región a otra, entre otros. En particular, en la reclasificación de productos es posible que un producto experimente varias reclasificaciones durante su existencia. Por tanto, un producto ajedrez puede ser clasificado como juguete durante un periodo (Per₁), luego ser clasificado como educativo durante otro periodo (Per₂), y posteriormente volver a ser clasificado como juguete. Esta sucesión de reclasificaciones puede originar consultas como: ¿Cuál fue el total vendido del producto ajedrez en el primer periodo cuando fue clasificado como juguete? ¿En sus tres primeros períodos cuándo fue clasificado como educativo? ¿Cuál ha sido el período de clasificación en el que el total vendido del producto ajedrez han sido las más altas y en cuál categoría estaba? ¿Mejoran las ventas de un producto en los períodos cuando se clasifica como educativo con respecto a los periodos en que se clasifica como juguete?

Las respuestas podrían ayudar a identificar los períodos apropiados para reclasificar los productos con el fin de incrementar las ventas. En otros escenarios, consultas análogas podrían servir para ajustar las políticas de rotación de personal o evaluar el desempeño de los jugadores a medida que rotan por los equipos, evaluar el impacto de fenómenos naturales cíclicos y de las políticas diseñadas para minimizar sus estragos, por ejemplo: ¿disminuyó el área de cultivos destruidos la segunda vez que el fenómeno de El Niño afectó a Perú? En este artículo se propone un conjunto de operadores para facilitar la formulación de este tipo de consultas. El resto del artículo se organiza así: en la sección 2 se presentan trabajos relacionados; en la sección 3 se ofrece el modelo formal temporal multidimensional; en la sección 4 se introduce y formaliza el concepto de período de clasificación; en la sección 5 se proponen y ejemplifican operadores para consulta de períodos de clasificación; en la sección 6 se incorporan los operadores en SQL; y finalmente, en la sección 7, se plantean las conclusiones y el trabajo futuro.

Trabajos relacionados

Aunque se han propuesto lenguajes de consulta multidimensionales (Cabibbo, 1997; Datta, 1999; Pedersen 2001; Jensen, 2004; Whitehorn, 2005), éstos carecen de elementos que consideren el aspecto dinámico de las dimensiones. Sin embargo, existen trabajos que consideran este aspecto. Hurtado (1999) y Blaschka (1999) proponen operadores para borrrar, insertar y actualizar el esquema y los datos de las dimensiones. Kaas (2004) propone operadores para cambiar el esquema de una BD, entre ellos operadores para insertar y borrar dimensiones y niveles. Otros autores (Eder, 2001; Body, 2002; Morzy, 2004; Golfarelli, 2006; Ravat, 2006; Rechy-Ramirez, 2006; Wrembel, 2007), se enfocan en el problema de versionamiento de una BD, es decir, cómo transformar o consultar datos que abarcan varias versiones de una BD originadas a partir de cambios en las dimensiones. Un estado del arte reciente sobre BD que consideran aspectos temporales, se puede ver en Golfarelli (2009b).

Unos pocos trabajos tratan específicamente con reclasificaciones. Chamoni (1999), Pedersen (2001) y Malinowski (2008) usan intervalos para registrarlas; no obstante, no plantean operadores que faciliten la formulación de consultas como las enunciadas en la sección 1. Por otro lado, en (Mendelzon, 2000) y (Vaisman, 2004) se propone un modelo multidimensional que soporta cambios en el esquema y en los datos de las dimensiones. También se propone un lenguaje de consulta denominado Tolap. Una consulta como "cuál fue el total vendido del producto ajedrez cuando ha sido clasificado como juguete" se puede formular en Tolap, pero este lenguaje no está orientado a resolver consultas como las enunciadas en la sección 1. Finalmente, en Moreno (2009a) se identifica informalmente este tipo de consultas, y en Moreno (2010) se propone un operador que puede ser considerado como una primera aproximación para resolver algunas de estas consultas. Un enfoque más completo y diferente se plantea aquí. Además, este nuevo enfoque puede ser fácilmente incorporado en SQL.

Modelo temporal multidimensional

El modelo multidimensional que se presenta a continuación se basa en el trabajo de Moreno (2009b), que a su vez se basó en el de Mendelzon (2000). representa el conjunto de los números naturales que incluyen el cero y .

Dimensiones

Un esquema de dimensión es una 5-tupla (DNOMBRE, ND, , All,⊥), donde: i) DNOMBRE es nómbrela denominación del esquema de dimensión, ii) ND es un conjunto de niveles. Cada nivel n ∈ ND se asocia con un conjunto de miembros (valores del nivel), es decir, un dominio denotado dom(n). Un miembro puede incluir atributos (Golfarelli, 2009b), los cuales dan información adicional sobre el nivel, iii) es un orden parcial en el conjunto ND. Sean n₁, n₂ ∈ ND, n₁ n₂ , significa que n₁ rolls up to n₂ (n₁ se agrupa en n₂). Se denota ′ a la reducción transitiva de , iv) All ∈
ND es el nivel superior del orden parcial , es decir, ∀n ∈ ND, n All; dom(All) = {all} y v) ⊥ ∈
ND es el nivel inferior del orden parcial , es decir, ∀n ∈ ND, ⊥ n.

Ejemplo 1. Sea el esquema de dimensión (PRODUCTO, {Producto, Categoría, All},, All, Producto), donde ´ = {(Producto, Categoría), (Categoría, All)}. Un miembro del nivel Producto podría incluir atributos como nombre, precio y descripción.

Adición de tiempo a las dimensiones

El tiempo se representa en forma discreta, o sea que un punto en la línea del tiempo corresponde a un entero positivo. Un entero positivo representa una instancia de una unidad temporal, por ejemplo, una hora, un día, un mes. Por claridad, se escribirá ‘día 1´ (o un valor como ‘enero 1 de 2000´) en vez de simplemente un 1. Además, sean x, y, z ∈
, [x, z] representa un intervalo que corresponde a un conjunto de enteros positivos: x <= y <= z. Las funciones Inicio(I) y Fin(I) devuelven el primer y el último entero positivo de un intervalo I, respectivamente.

Existe una relación ser más fino que entre algunas unidades temporales. Por ejemplo, cada día está incluido en un mes específico, así la unidad temporal Día es más fina que la unidad temporal Mes. Por otro lado, Semana no es más fina que Mes, y Mes es no es más fino que Semana. Sean μ1 y μ2 unidades temporales, si μ1 es más fina que μ2, se escribe μ1 μ2.

El tiempo se incorpora a las dimensiones (excepto a la dimensión TIEMPO) de dos maneras. La primera es adicionando un intervalo a cada miembro de un nivel con el fin de registrar su tiempo de existencia en la BD. La segunda es adicionando un intervalo entre dos miembros, con el propósito de registrar los períodos correspondientes a sus asociaciones (clasificaciones).

Sea un esquema de dimensión (DNOMBRE, ND, , All, ⊥ ). Una pareja de niveles (n₁, n₂)
∈ ´, n₂ ≠ All se puede asociar con una unidad temporal μ, la cual define la granularidad temporal de reclasificación (GTR) entre n₁ y n₂. Se dice entonces que la pareja (n₁, n₂) es temporal.

Ejemplo 2. Considérese el ejemplo 1. Un producto se clasifica en una categoría durante un período de días. Por lo tanto, se asocia una GTR μ = Día con la pareja (Producto, Categoría) con el objetivo de registrar las asociaciones entre productos y categorías sobre una base diaria.

Una instancia de un esquema de dimensión es una 2-tupla (D, FR), donde D es un esquema de dimensión y FR un conjunto de funciones rollup. Sea ND el conjunto de niveles de D; n₁, n₂ ND, y el orden parcial en el conjunto ND entonces: i) para cada pareja temporal (n₁, n₂) ∈ ´ con GTR μ, existe una función rollup RUP_n₁_n₂: dom(n₁) x dom(μ)→ dom(n₂) y ii) para cada pareja no-temporal (n₁, n₂) ∈´, existe una función rollup RUP_n₁_n₂: dom(n₁)→ dom(n₂). Nótese que RUP_n₁_n₂ es un metanombre, es decir, n₁ y n₂ se refieren a nombres de niveles.

Ejemplo 3. Sea una instancia del esquema de dimensión del ejemplo 2. Sean los dominios: dom(Categoría) = {Juguete, Educativo}, dom(Producto) = {Prod₁, Prod₂}, dom(All) = {all} y dom(Día) = Las funciones rollup entre los miembros de los niveles en el ´ de ND se muestran en la tabla 1. Por ejemplo, RUP_Producto_Categoría(Prod₁, día 1) = Juguete.

Hechos

Un esquema de hecho es una 3-tupla (FNOMBRE, FL, M), donde: i) FNOMBRE es como se llama el esquema de hecho, ii) FL = {n₁, …, n_k} es un conjunto de niveles. Cada nivel n_i ∈ FL es el nivel inferior (⊥) en un esquema de dimensión y iii) M = {m₁, …, m_m} es un conjunto de medidas. Cada medida m_i se asocia con un dominio dom(m_i).

Ejemplo 4. Sea el esquema de hecho (VENTAS, {Producto, Vendedor, Día}, {TotalVendido, UnidadesVendidas}), como se ilustra en la figura 1. Se usa la notación de Malinowski (2008) para representar el modelo conceptual, la cual se basa en la notación del modelo entidad-relación. Se adiciona la representación de las GRTs (Moreno, 2009b).

Una instancia de hecho de un esquema de hecho (FNOMBRE, FL, M), FL = {n₁, …, n_k} y M = {m₁, …, m_m}, es una 2-tupla (fl, m) donde fl = {miembro(n₁), …, miembro(n_k)} es un conjunto de miembros y m = {valor(m₁), …, valor(m_m)} es un conjunto de valores de medidas. Cada miembro(n_i,/)∈ dom(n_i) es un miembro de un nivel inferior (⊥) en una instancia de esquema de dimensión. Cada valor(m_i) ∈ dom(m_i) es un valor para la medida m_i.Una tabla de hechos es un conjunto de instancias de hecho.

Ejemplo 5. Sean los dominios: dom(Producto ) = {Prod₁, Prod₂},dom(Vendedor) = {Vend₁, Vend₂} y dom(Día) =. Una tabla de hechos Ventas correspondiente al esquema de hecho VENTAS del ejemplo 4 es {({Prod₁, Vend₁, día 1}, {1000, 2}), ({Prod₁, Vend₂, día 1}, {1500, 3}), ({Prod₂, Vend₁, día 2},{2000, 4}), ({Prod₂, Vend₂, día 2}, {500, 1})}.

Períodos de clasificación

Informalmente un período de clasificación (PC) es un intervalo durante el cual determinado miembro de un nivel se asocia con cierto miembro de un nivel superior, por ejemplo, un PC de un producto en una categoría, de un vendedor en una tienda, de una tienda en un estatus. A continuación se presenta una definición formal de un PC entre un miembro a de un nivel n₁ y un miembro b de un nivel superior n_k de n₁. Sean n₁, n₂, n₃, …, n_k niveles de un esquema de dimensión, k > 1, donde n₁ ´ n₂´ n₃ … ´ n_k. Sea U≠ Ø el conjunto de GTRs a lo largo del camino n₁ ´ n₂ ´ n₃ … ´ n_k, a ∈
dom(n₁) y b ∈ dom(n_k). Un PC de a en b es un intervalo l con granularidad temporal μ´, donde: i) ∀μ∈ U, μ´ μ, ii) ∀t ∈ l, RUP_n₁_n_k(a, t) = b, iii) si RUP_n₁_n_k (a, Inicio(l) − 1) está definida, entonces RUP_n₁_n_k(a, Inicio(l) − 1) ≠ b, y iv) si RUP_n₁_n_k(a, Fin(l) + 1) está definida, entonces RUP_n₁_n_k(a, Fin(l) + 1) ≠ b.

Nótese que las condiciones iii) y iv) garantizan que I es un intervalo máximo durante el cual a se asocia con b. Si U = Ø entonces durante su existencia en la BD a se asocia siempre con b; por lo tanto, se considera a l como el único PC de a en b, donde Inicio(l) y Fin(l) corresponden al tiempo de existencia de a en la BD.

Ejemplo 6. Considérese el ejemplo 4. Los valores rollup (categorías) correspondientes a Prod₁ se muestran en la tabla 2.

A partir de la tabla 2 se observa que [día 1, día 45], [día 211, día 390] y [día 481, día 540] son PC de Prod₁ en la categoría juguete. Ahora se considera el orden de los PC entre dos miembros y se define el concepto del n-ésimo PC. Sea l un PC de a en b. l es el primer PC de a en b si no existe un PC I´ de a en b tal que Fin (l´) < Inicio(l). l es el segundo PC de a en b, si existe sólo un PC l´ de a en b tal que Fin(l´) < Inicio(l). En general, sea = {l₁, l₂, …, l_n} un conjunto de PC de a en b; por lo tanto, l_i
∈ es el nésimo PC de a en b, donde . Este número se denomina número de PC. Por ejemplo, a partir del ejemplo 6 se tiene que [día 1, día 45] es el primer PC de Prod₁ en la categoría juguete, [día 211, día 390] es el segundo y [día 481, día 540] es el tercero.

Operadores de consulta para PC

Considérese el ejemplo 6. La operación rollup RUP_ Producto_Categoría (Prod₁, día 1) retorna la categoría del Prod₁ en el día 1 (juguete). Sin embargo, la operación no retorna ni el número ni el intervalo correspondiente al PC de Prod1 en dicha categoría. Para obtener estos datos se propone un conjunto de operadores de consulta para PC. Los operadores deben responder a peticiones de usuario reales, como los descritos en la sección 1 y en la tabla 3

Sean n₁, n₂, n₃, …, n_k niveles de un esquema de dimensión, k > 1, donde n₁ ´ n₂´ n₃ … ´ n_k. Sea U ≠ Ø el conjunto de GTRs a lo largo del camino n₁ ´ n₂ ´ n₃ … ´ n_k; y μ´ una unidad temporal arbitraria, donde ∀μ∈ U, μ´ μ. En la tabla 4 se presentan los operadores de consulta para PC propuestos. Si U = Ø, es decir, todas las parejas del camino n₁´ n₂´ n₃ … ´ n_k son no-temporales, entonces #PC_n₁_n_k y #PCs_n₁_n_k retornan 1, e IPC_n₁_n_k retorna un intervalo l con granularidad temporal μ´, donde Inicio(l) y Fin(l) corresponden al tiempo de existencia de a en la BD, donde a es el miembro perteneciente al dominio de n₁.

Incorporación de los operadores de consulta para PC en SQL

En esta sección se muestra cómo se incorporan los operadores para PCs en SQL, un lenguaje familiar para los desarrolladores de bases de datos. Otra opción a considerar es MDX (Whitehorn, 2005), un lenguaje de consulta multidimensional (no temporal). En la figura 2 se muestran algunas tablas SQL del esquema de la figura 1. La tabla Prod_Cat representa la relación temporal entre producto y categoría. En la tabla 5 se registran consultas relacionadas con PC. A continuación se ofrece una solución en SQL (sin usar los operadores propuestos) para la última consulta de la tabla 5. Primero se enumeran los PC de cada producto en cada categoría:

CREATE VIEW PCs AS SELECT IdProd, NomCat, ROW_NUMBER() OVER (PARTITION BY IdProd, NomCat ORDER BY DiaInicio) AS NroPC, DiaInicio, DiaFin FROM Prod_Cat;

Ahora se obtiene el total vendido de cada producto en cada PC:

SELECT IdProd, NomCat, NroPC, SUM(Total vendido) AS Total FROM PCs, Ventas

WHERE IdProd = Producto AND Dia BETWEEN DiaInicio AND DiaFin

GROUP BY IdProd, NomCat, NroPC;

Nótese que aunque la función analítica ROW_NUMBER facilita la formulación de esta consulta, la expresión correspondiente de la tabla 5 es más simple e intuitiva. Por otro lado, la simulación de una consulta que incluya operadores de PC entre dos niveles no adyacentes, por ejemplo, vendedor y estatus, es mucho más compleja y larga. Por límites de espacio no se presenta.

Conclusiones y trabajos futuros

Debido a las reclasificaciones que se pueden presentar entre los miembros de los niveles de una dimensión se introdujo el concepto período de clasificación. Este concepto da origen a un tipo de consultas que pueden ayudar en la toma de decisiones estratégicas en varios escenarios, tales como ventas, deportes, recursos humanos, fenómenos naturales, entre otros.

Se propuso un conjunto de operadores para facilitar la formulación de las consultas expuestas y se mostró cómo estos operadores se pueden incorporar en un lenguaje como SQL. También se expuso el esfuerzo de codificación requerido para simular los operadores propuestos en SQL, evidenciando así su expresividad.

Se plantea desarrollar los siguientes trabajos: i) extender los operadores al campo de las BD espaciales, de esta forma se podrían estructurar consultas como "obtener el total vendido por un vendedor en sus dos primeros PC cuando estuvo asociado con las tiendas delimitadas por una región determinada", ii) permitir PC superpuestos, por ejemplo, un producto podría pertenecer a varias categorías durante un mismo tiempo y iii) dividir un PC; por ejemplo, supóngase que se presenta la reelección de un gerente como presidente de un departamento. En vez de manejar un único PC para el presidente en ese departamento, se podrían definir dos PC: uno correspondiente a su primer mandato y otro a su segundo. De esta forma se podría evaluar su desempeño durante cada mandato.

Agradecimientos:

Este trabajo hace parte de los resultados del doctorado en Ingeniería - Sistemas, del primer autor.

---

Referencias

Blaschka, M., Sapia, C., Höfling, G., On schema evolution in multidimensional databases., 1st DaWaK, Florencia, Italia, 1999, pp. 153 - 164.

Body, M., Miquel, M., Bèdard, Y., Tchounikine, A., A multidimensional and multiversion structure for OLAP applications., 5th DOLAP, McLean, USA, 2002, pp. 1 - 6.

Cabibbo, L., Torlone, R., Querying multidimensional databases., 6th DBPL-6, Estes Park, USA, 1997, pp. 319-335.

Golfarelli, M., Lechtenbörger, J., Rizzi, S., Vossen, G., Schema Versioning in Data Warehouses., Data and Knowledge Engineering, Vol. 59, No. 2, 2006, pp. 435-459.

Golfarelli, M., Rizzi, S., Data Warehouse Design: Modern principles and methodologies., 1st Edn., McGraw-Hill Osborne Media, New York, 2009a.

Golfarelli, M., Rizzi, S., A Survey on Temporal Data Warehousing.,Int. Journal of Data Warehousing and Mining, Vol. 5, No. 1, 2009b, pp. 1-17.

Hurtado, C. A., Mendelzon, A. O., Vaisman, A. A., Updating OLAP dimensions., ACM 2nd DOLAP, Kansas City, USA, 1999, pp. 60 -66.

Jensen, C. S., Kligys, A., Pedersen, T. B., Timko, I., Multidimensional Data Modeling for Location-based Services., VLDB Journal, Vol. 13, No. 1, 2004, pp. 1-21.

Kaas, C., Pedersen, T. B., Rasmussen, B., Schema evolution for stars and snowflakes., 6th ICEIS, Porto, Portugal, 2004, pp. 425-433.

Kumar, N., Gangopadhyay, A., Bapna, S., Karabatis, G., Chen, Z. Measuring interestingness of discovered skewed patterns in data cubes., Decision Support Systems, Vol. 46, No. 1, 2008, pp. 429-439.

Malinowski, E., Zimányi, E., Advanced data warehouse design: from conventional to spatial and temporal applications., Nueva York, Springer, 2008.

Mendelzon, A. O., Vaisman, A. A., Temporal queries in OLAP., 26th VLDB., El Cairo, Egipto, 2000, pp. 242-253.

Moreno, F., Arango, F., Fileto, R., Season Queries on a Temporal Multidimensional Model., 11th IM2 (presentación oral corta), Valencia, España, 2009a.

Moreno, F., Arango, F., Fileto, R., A multigranular temporal multidimensional model., 32nd Mipro, Opatija, Croacia, 2009b, pp. 206-210.

Morzy, T., Wrembel, R., On querying versions of multiversion data warehouse., ACM 7th DOLAP, Washington D.C., USA, 2004, pp. 92-101.

Pedersen, T. B., Jensen, C. S., Dyreson, C. E., A Foundation for Capturing and Querying Complex Multidimensional Data., Information Systems, Vol. 26, No. 5, 2001, pp. 383-423.

Ravat, F., Teste, O., Supporting Data Changes in Multidimensional Data Warehouses., Int. Review on Computers and Software, Vol.1, No. 3, 2006, pp. 251-259.

Rechy-Ramirez, E., Benitez-Guerrero, E., A model and language for bitemporal schema versioning in data warehouses., 15th CIC, Ciudad de Mexico, Mexico, 2006, pp. 309-314.

Torlone, R., Conceptual Multidimensional Models., Multidimensional Databases: Problems and Solutions., M. Rafanelli (ed.), Nueva York, Idea Group, 2003, pp. 69 - 90.

Vaisman, A. A., Mendelzon, A. O., Ruaro, W., Cymerman, S. G., Supporting Dimension Updates in an OLAP Server, Information Systems, Vol. 29, No. 2, 2004, pp. 165-185.

Whitehorn, M., Zare, R., Pasumansky, M., Fast Track to MDX, Nueva York, Springer, 2005.

Wrembel, R., Bebel, B., Metadata Management in a Multiversion Data Warehouse., Journal of Data Semantics, Vol. 8, No. 1, 2007, pp. 118-157.

---

Francisco Moreno¹, Fernando Arango²

¹ Systems Engineer. Ph.D. Engineering, Universidad Nacional de Colombia, venue Medellín. fjmoreno@unal.edu.co

² B.Sc. Civil Engineering. M.Sc and Ph.D., Universidad Nacional de Colombia, venue Medellín. farango@unal.edu.co

---

ABSTRACT

Keywords: temporal data warehouse, OLAP, reclassification, classification period.

---

Received: Feuary 01th 2010. Accepted: Feuary 7th 2011

---

Introduction

Data warehouses (DW) (Kumar, 2008; Golfarelli, 2009a) have proved their usefulness in integrating information systems and supporting decision-making during recent years. DWs are usually modelled using a multidimensional view of data. A multidimensional model has a set of dimensions associated with a subject of interest for an organisation called fact. A dimension is composed of levels structured as a hierarchy according to analysis needs (Torlone, 2003). For example, in a time dimension with day, month, and year levels, days are grouped into months and months into years; whereas in a product dimension having product and category levels, products are grouped into categories.

A fact usually includes measures, namely, indicators allowing one to evaluate an organisation´s specific activities (Malinowski, 2008). Measures can be aggregated throughout dimension levels, allowing information from different granularity levels to be analysed. For example, consider a fact sale, having a total sold measure associated with time and product dimensions. This way of organising data facilitates formulating queries such as, "What was the total daily, monthly or annual sale of a certain product?

Usually, dimensions are considered static in DW while facts are considered dynamic because new facts are periodically added to DW. However, dimension schema and dimension data can also change (Golfarelli, 2009b). This paper focuses on a type of dimension data change called reclassification and on a type of query arising from such changes. Reclassification occurs when a member of a certain level changes its parent (a member of a higher level from the same dimension), e.g. when a product classified as a toy is reclassified as being educational.

Reclassification is common in several domains: a product changes category, a salesperson shifts position in a store, a store or a customer changes status, a player changes team, a hurricane moves from one region to another. In product reclassification, it is possible for a product to undergo several reclassifications during its lifespan. For example, a chess set can be classified as a toy during period Per₁, then be classified as educational during period Per₂, and again be reclassified as a toy. This succession of reclassifications may give rise to queries such as, "What was the total sale of chess sets during the first period when it was classified as a toy?" "What was the total sale of chess sets during the three first periods when it was classified as educational?" "What was the classification period when total chess sets sold has been the highest and which category were they in?" "Are sales of a product better in periods when classified as educational compared to periods when classified as a toy?"

The answers to the previous queries can help identify suitable periods for reclassifying products to increase their sales. In other domains, analogous queries can help adjust personnel shifting policies, evaluate players´ performance as they shift through teams, evaluate the impact of cyclical natural phenomena as well as policies designed to minimise their damage, e.g. "Did the area of destroyed crops decrease the second time El Niño affected Peru?" A set of operators is proposed in this paper for facilitating the formulation of this type of query.

Related work

Although several multidimensional query languages have been proposed (Cabibbo, 1997; Datta, 1999; Pedersen 2001; Jensen,

2004; Whitehorn, 2005), they lack elements considering the dynamic aspect of dimensions. However, some studies have considered this aspect. Hurtado (1999) and Blaschka (1999) have proposed operators for deleting, inserting and updating dimension schema and dimension data. Kaas (2004) has proposed operators for changing DW schema, including operators for inserting and deleting dimensions and levels. Other authors (Eder, 2001; Body, 2002; Morzy, 2004; Golfarelli, 2006; Ravat, 2006; Rechy-Ramirez, 2006; Wrembel, 2007) have focused on DW versioning, i.e. how to transform and/or query data covering several DW versions arising from dimension changes. A recent survey on DWs considering temporal aspects can be found in Golfarelli (2009b).

A few works have specifically dealt with reclassification. Chamoni (1999), Pedersen (2001) and Malinowski (2008) have used intervals to record them. However, they have not proposed operators facilitating the formulation of queries like those outlined in section 1. On the other hand, a multidimensional model supporting changes in dimension schema and dimension data is proposed in (Mendelzon, 2000) and (Vaisman, 2004). They have also proposed a query language called TOLAP. A query such as, "What was the total sale of chess sets when classified as a toy?" can be formulated in TOLAP; however, this language is not orientated towards solving queries such as those outlined in section 1. Moreno (2009a) informally identified this type of query and Moreno (2010) proposed an operator that can be considered a first approach to solving some of these queries. A different and more complete approach is followed here; such new approach can easily be incorporated into SQL.

Temporal multidimensional model

The multidimensional model presented here was based on work by Moreno (2009b), in turn based on work by Mendelzon (2000). represented the set of natural numbers including zero and .

Dimensions

A dimension schema was a 5-tuple (DNAME, ND, , All,⊥) where: i) DNAME was the name of the dimension schema, ii) ND was a set of levels. Each level n ∈ ND was associated with a set of members (level values), i.e. a domain denoted by dom(n). A member could include attributes (Golfarelli, 2009b) providing supplementary information about a level, iii) was a partial order in set ND. n₁, n₂ ∈ ND, n₁ n₂ meant that n₁ rolled up to n₂ (n₁ was grouped into n₂). ´ was denoted as the transitive reduction of , iv) All ∈ ND was the top level of partial order . ∀n ∈ ND, All; dom(All) = {all}, and v) ⊥ ∈ ND was the bottom level of partial order . ∀n ∈ ND,⊥ n.

Example 1. Consider dimension schema (PRODUCT, {Product, Category, All}, , All, Product), where ´ = {(Product, Category), (Category, All)}. A member of level Product could include attributes such as name, price and description

Adding time to dimensions

Time was represented as discrete: a point on a timeline corresponding to a positive integer. A positive integer represented an instance of a temporal unit, e.g. an hour, day or a month. For clarity, ‘day 1´ (or a value such as ‘January 1 2011´) has been written instead of just 1. In addition, x, y, z ∈ , [x, z] represented an interval corresponding to a set of positive integers: x <= y <= z. Functions Start(I) and End(I) returned the first and the last positive integer of interval I, respectively.

There was a finer than relationship among temporal units. For example, a day is included in a specific month; thus temporal unit day is finer than temporal unit month. On the other hand, week is not finer than month, and month is not finer than week. μ1 and μ2 were temporal units, if μ1 was finer than μ2, then this would be written as μ1 μ2.

Time was incorporated into other dimensions (other than the TIME dimension) in two ways. The first was by adding an interval to each member of a level to record its timespan in the DW. The second way was by adding an interval between two members to record their corresponding association (classification) periods.

Consider a dimension schema (DNAME, ND, , All, ⊥). A pair of levels (n₁, n₂) ∈ , n₂ ≠ All, could be associated with temporal unit μ defining temporal reclassification granularity (TRG) between n₁ and n₂. The pair (n₁, n₂) would then be said to be temporal.

Example 2. Consider Example 1. A product is classified in a category during a period of days. Therefore, TRG μ = Day would be associated with the pair (Product, Category) to record associations between products and categories on a daily basis.

A dimension schema instance was a 2-tuple (D, FR) where D was dimension schema and FR a set of rollup functions. ND was the set of levels of D; n₁, n₂ ∈ ND, and partial order in the set ND then: i) for each temporal pair (n₁, n₂) ∈ ´ with TRG μ, there would be rollup function RUP_n₁_n₂: dom(n₁) x dom(μ) → dom (n₂) and ii) for each non-temporal pair (n₁, n₂) ∈ ´, there would be rollup function RUP_n₁_n₂: dom(n₁)→dom(n₂). Note that RUP_n₁_n₂ wass a metaname: n₁ and n₂ referred to level names.

Example 3. Consider the dimension schema given in Example 2 and domains: dom(Category) = {Toy, Educational}, dom (Product) = {Prod₁, Prod₂}, dom(All) = {all}, and dom(Day) = . The rollup functions between the members of levels in ´ of ND are shown in Table 1. For example, RUP_Product_Category(Prod₁, day 1) = Toy.

Facts

A fact schema was a 3-tuple (FNAME, FL, M) where: i) FNAME was the name of the fact schema, ii) FL = {n₁, …, n_k} was a set of levels. Each level n_i ∈ FL was the bottom level (⊥) in a dimension schema, and iii) M = {m₁, …, m_m} was a set of measures. Each measure m_i was associated with a domain dom(m_i).

Example 4. Consider the fact schema (SALES, {Product, Salesperson, Day}, {TotalSold, UnitsSold}), see Figure 1. Malinowski´s notation (2008) was used for representing the conceptual model, which was based on entity-relationship model notations. TRG representation was included (Moreno, 2009b).

A fact instance of a fact schema (FNAME, FL, M), FL = {n₁, …, n_k} and M = {m₁, …, m_m}, was a 2-tuple (fl, m) where fl = {member(n₁), …, member(n_k)} was a set of members and m = {value(m₁), …, value(m_m)} was a set of values from measures. Each member(n_i)∈ dom(n_i) was a member of a bottom level (⊥) in a dimension schema instance. Each value(m_i)∈ dom(m_i) was a value for measure m_i. A fact table was a set of fact instances.

Example 5. Consider domains: dom(Product) = {Prod₁, Prod₂}, dom(Salesperson) = {Sp₁, Sp₂}, and dom(Day) = . A fact table Sales for the fact schema SALES in Example 4 was {({Prod₁, Sp₁, day 1}, {1000, 2}), ({Prod₁, Sp₂, day 1}, {1500, 3}), ({Prod₂, Sp₁, day 2}, {2000, 4}), ({Prod₂, Sp₂, day 2}, {500, 1})}.

Classification period

Informally, a classification period (CP) is an interval during which a member of a level is associated with a member of a higher level, e.g. a CP for a product in a category, a CP for a salesperson in a store, a CP for a store regarding its status. A formal definition of a CP is presented between member a of level n1 and member b from higher level n_k of n₁. n₁, n₂, n₃, …, n_k were levels of a dimension schema, k > 1, where n₁ ´ n₂ ´ n₃ … ´ n_k. U≠ Ø were the set of TRGs along path n₁ ´ n₂ ´ n₃ … ´ n_k, a ∈ dom(n₁) and b ∈ dom(n_k). A CP of a in b was an interval I with

temporal granularity μ´, where: i) ∀μ ∈ U, μ´ μ, ii) ∀t ∈ I, RUP_n₁_n_k(a, t) = b, iii) if RUP_n₁_n_k(a, Start(I) − 1) was defined then RUP_n₁_n_k(a, Start(I) − 1) ≠ b and iv) if RUP_n₁_n_k(a, End(I) + 1) was defined then RUP_n₁_n_k(a, End(I) + 1) ≠ b.

Note that conditions iii) and iv) guaranteed that I was a maximum interval during which a was associated with b. If U = Ø then during its lifespan in the DW a was always associated with b; therefore, I was considered as the unique CP of a in b, where Start(_I) and End(_I) corresponded to the lifespan of a in the DW.

Example 6. Consider again Example 4. The corresponding rollup values (categories) to Prod1 are shown in Table 2.

Table 2 shows that [day 1, day 45], [day 211, day 390] and [day 481, day 540] were CPs of Prod₁ in Toy category. Now, considering the ordering of CPs between two members and defining the n^th CP concept. I would be a CP of a in b. I was the first CP of a in b if there were no CP I´ of a in b so that End(I´) < Start(I). I was the second CP of a in b, if there were only CP I´ of a in b so that End(I´) < Start(I). In general, = {l₁, l₂, …, l_n} would be a set of CPs of a in b; therefore, l_i
∈ would be the n^th CP of a in b, where . This number has been called CP number. For instance, in Example 6 [day 1, day 45] was the first CP of Prod1 in Toy category, [day 211, day 390] was the second one, and [day 481, day 540] was the third one.

Query operators for CPs

Consider again Example 6. The rollup operation RUP_Product_ Category (Prod₁, day 1) returned the category (Toy) of Prod₁ in day 1. However, this operation did not return the corresponding interval of Prod1 in Toy category or the CP number. A set of query operators for CPs has thus been proposed for obtaining such data. Operators must be based on real users´ requests, such as those described in Section 1 and Table 3.

n₁, n₂, n₃, …, n_k were levels for a dimension schema, k > 1, where n₁ ´ n₂ ´ n₃ … ´ n_k.U ≠ Ø was the set of TRGs along path n₁ ´ n₂ ´ n₃ … ´ n_k; and μ´ was an arbitrary temporal unit, where "μ Î U, μ´ μ. Table 4 presents our query operators for CPs. If U = Ø, i.e. all pairs along path n₁ ´ n₂ ´ n₃ … ´ n_k were non-temporal, then #CP_n₁_n_k and #CPs_n₁_n_k returned 1, and ICP_n₁_n_k returned an interval I with temporal granularity μ´, where Start(I) and End(I) corresponded to the lifespan of a in the DW, where a was a member of the domain of n₁.

Incorporating query operators for CPs in SQL

Here we show how to incorporate our query operators for CPs into SQL which is a familiar language for database developers. Another alternative is MDX (Whitehorn, 2005), a multidimensional query language (non-temporal). Figure 2 shows some SQL tables corresponding to the schema shown in Figure 1. Table Prod_Cat represents a temporal relationship between Product and Category. Table 5 presents some queries related to CPs. an SQL solution is now presented (without using our proposed operators) for the last query in Table 5. First, the CPs for each product in each category are enumerated:

CREATE VIEW CPs AS SELECT IdProd, NameCat, ROW_NUMBER() OVER (PARTITION BY IdProd, NameCat ORDER BY Day-Start) AS NrCP, DayStart, DayEnd FROM Prod_Cat;

Now we found the total sold of each product in each CP:

SELECT IdProd, NameCat, NrCP, SUM(TotalSold) AS Total FROM CPs, Sales

WHERE IdProd = Product AND Day BETWEEN DayStart AND DayEnd

GROUP BY IdProd, NameCat, NrCP;

Note that although the analytic function ROW_NUMBER facilitated formulating this query, the corresponding expression in Table 5 is simpler and more intuitive. On the other hand, simulating a query that includes CP operators between two nonadjacent levels (e.g., salesperson and status) is much more complex and longer. This has not been shown due to space limitations.

Conclusions and future work

The concept of classification period was introduced due to reclassifications which may occur amongst dimension level members. This concept gives rise to a type of query which can help in decision-making in several domains such as sales, sports, human resources and natural phenomena.

A set of operators has been proposed to facilitate formulating CP queries and it has been shown how these operators can be incorporated into a language such as SQL. The encoding effort required to simulate our operators in SQL has also been shown, thus demonstrating its expressiveness.

The following work is planned. Extending our operators to the field of spatial DWs, so that queries may be formulated such as, "What was the total sold by a salesperson in his/her two first CPs when he/she was associated with the stores contained in a particular region?" Allowing overlapping CPs, e.g. a product could be associated with several categories simultaneously. It is also planned splitting a CP, e.g. suppose a manager is re-elected in a department. Instead of defining a unique CP for the manager in that department, two CPs could be defined: one corresponding to his first term and another to his/her second term. Performance in each term could thus be assessed.

---

References

Blaschka, M., Sapia, C., Höfling, G., On schema evolution in multidimensional databases., 1st DaWaK, Florencia, Italia, 1999, pp. 153 - 164.

Body, M., Miquel, M., Bèdard, Y., Tchounikine, A., A multidimensional and multiversion structure for OLAP applications., 5th DOLAP, McLean, USA, 2002, pp. 1 - 6.

Cabibbo, L., Torlone, R., Querying multidimensional databases., 6th DBPL-6, Estes Park, USA, 1997, pp. 319-335.

Golfarelli, M., Lechtenbörger, J., Rizzi, S., Vossen, G., Schema Versioning in Data Warehouses., Data and Knowledge Engineering, Vol. 59, No. 2, 2006, pp. 435-459.

Golfarelli, M., Rizzi, S., Data Warehouse Design: Modern principles and methodologies., 1st Edn., McGraw-Hill Osborne Media, New York, 2009a.

Golfarelli, M., Rizzi, S., A Survey on Temporal Data Warehousing.,Int. Journal of Data Warehousing and Mining, Vol. 5, No. 1, 2009b, pp. 1-17.

Hurtado, C. A., Mendelzon, A. O., Vaisman, A. A., Updating OLAP dimensions., ACM 2nd DOLAP, Kansas City, USA, 1999, pp. 60 -66.

Jensen, C. S., Kligys, A., Pedersen, T. B., Timko, I., Multidimensional Data Modeling for Location-based Services., VLDB Journal, Vol. 13, No. 1, 2004, pp. 1-21.

Kaas, C., Pedersen, T. B., Rasmussen, B., Schema evolution for stars and snowflakes., 6th ICEIS, Porto, Portugal, 2004, pp. 425-433.

Kumar, N., Gangopadhyay, A., Bapna, S., Karabatis, G., Chen, Z. Measuring interestingness of discovered skewed patterns in data

cubes., Decision Support Systems, Vol. 46, No. 1, 2008, pp. 429-439.

Malinowski, E., Zimányi, E., Advanced data warehouse design: from conventional to spatial and temporal applications., Nueva York, Springer, 2008.

Mendelzon, A. O., Vaisman, A. A., Temporal queries in OLAP., 26th VLDB., El Cairo, Egipto, 2000, pp. 242-253.

Moreno, F., Arango, F., Fileto, R., Season Queries on a Temporal Multidimensional Model., 11th IM2 (presentación oral corta), Valencia, España, 2009a.

Moreno, F., Arango, F., Fileto, R., A multigranular temporal multidimensional model., 32nd Mipro, Opatija, Croacia, 2009b, pp. 206-210.

Morzy, T., Wrembel, R., On querying versions of multiversion data warehouse., ACM 7th DOLAP, Washington D.C., USA, 2004, pp. 92-101.

Pedersen, T. B., Jensen, C. S., Dyreson, C. E., A Foundation for Capturing and Querying Complex Multidimensional Data., Information Systems, Vol. 26, No. 5, 2001, pp. 383-423.

Ravat, F., Teste, O., Supporting Data Changes in Multidimensional Data Warehouses., Int. Review on Computers and Software, Vol.1, No. 3, 2006, pp. 251-259.

Rechy-Ramirez, E., Benitez-Guerrero, E., A model and language for bitemporal schema versioning in data warehouses., 15th CIC, Ciudad de Mexico, Mexico, 2006, pp. 309-314.

Torlone, R., Conceptual Multidimensional Models., Multidimensional Databases: Problems and Solutions., M. Rafanelli (ed.), Nueva York, Idea Group, 2003, pp. 69 - 90.

Vaisman, A. A., Mendelzon, A. O., Ruaro, W., Cymerman, S. G., Supporting Dimension Updates in an OLAP Server, Information Systems, Vol. 29, No. 2, 2004, pp. 165-185.

Whitehorn, M., Zare, R., Pasumansky, M., Fast Track to MDX, Nueva York, Springer, 2005.

Wrembel, R., Bebel, B., Metadata Management in a Multiversion Data Warehouse., Journal of Data Semantics, Vol. 8, No. 1, 2007, pp. 118-157.

---