Download Artículo Completo - Revista INVURNUS

INVURNUS
“En busca del conocimiento”
Volumen 5 No. 1 ( Enero-Junio 2010): 3-12
División de Ciencias Administrativas, Contables y Agropecuarias
PROGRAMACIÓN
Algoritmo de Selección de Vistas a Materializar para la Arquitectura ROLAP
Serna Encinas María Trinidad 1* y Manzano Torres Isidro2
1
2
División de Estudios de Postgrado e Investigación, Instituto Tecnológico de Hermosillo. [email protected].
Academia de Ciencias Administrativas y Sociales, Universidad de Sonora. [email protected].
Un almacén de datos (Data Warehouse) integra información que proviene de fuentes de datos internas y externas a la empresa. El
conjunto de datos es utilizado para la ayuda a la toma de decisión, de ahí que el diseño del modelo multidimensional y la selección de
vistas a materializar representan un proceso complejo y delicado. En este artículo, se propone un algoritmo para la selección del
conjunto óptimo de vistas a materializar de un cubo multidimensional. El algoritmo utiliza los parámetros de frecuencia de uso, de
costo de cálculo y de frecuencia de actualizaciones a las relaciones de base. Se tuvo la oportunidad de trabajar en el marco de un
proyecto médico, para el cual se diseñó un esquema multidimensional y se tomó como base para realizar las experimentaciones, lo
que permitió verificar y validar la propuesta sobre datos reales.
Palabras clave: almacén de datos, modelo multidimensional, vistas materializadas, consultas OLAP.
Algorithm of Selection of Views to Materialize for the ROLAP Architecture
Abstract
A Data Warehouse integrates information coming from data sources within and outside the company. The data set is used to aid
decision making, hence the multidimensional model design and selection of materialized views represent a complex and delicate
process. In this paper, we propose an algorithm for selecting the optimal set of views to materialize in a multidimensional cube. The
algorithm uses the parameters of frequency of use, cost calculation and frequency of updates to base relations. We had the opportunity
to work within the framework of a medical project, for which we designed a multidimensional schema and took as the basis for the
experiments, which allowed verifying and validating the proposal on real data.
Keywords: Data Warehouse, multidimensional model, materialized views, OLAP queries.
*Autor para envío de correspondencia: Nueva Tanzania 15-B, Col. Nuevo Nogales. Nogales, México, C. P. 84092. Tel/Fax: (631) 63144650. E-mail:
[email protected].
© 2010 Editorial UNISON –URN. Derechos reservados.
4
INVURNUS, Vol. 5 No. 1 (2010): 3-12
Introducción
Los almacenes de datos aparecieron al inicio del año
1990 en respuesta a la necesidad de reunir toda la
información de la empresa en una base de datos única
destinada a los analistas y administradores (Doucet &
Gangarski, 2001). Los datos deben pasar por un proceso de
transformación y de limpieza antes de su registro en el
almacén. El conjunto de datos, incluidos los datos
históricos, es utilizado para la ayuda a la toma de decisión
(Kimball, 1996; Kimball & Ross, 2003).
El diseño y la construcción de un almacén de datos es
una tarea compleja y delicada. Ella se compone de varios
procesos comúnmente llamados: extracción-integración,
organización e interrogación. Para la extracción-integración,
se debe analizar el conjunto de fuentes de datos internas y
externas. Este análisis sirve tanto para la selección del
conjunto de datos a registrar en el almacén, como a la
selección de herramientas requeridas para la extracción y la
transformación de estos datos antes de su almacenamiento.
El segundo proceso consiste a organizar dichos datos al
interior del almacén. Para ello, se debe esquematizar el
modelo multidimensional a utilizar, así como definir el
conjunto óptimo de vistas a materializar. Finalmente, el
último proceso consiste en determinar las herramientas
necesarias para la visualización de los datos.
Este artículo se focaliza sobre el proceso de
organización. En él se describe el proyecto ADELEM (Ayuda
a la Decisión Logística y Médica, por sus siglas en francés) y
las fuentes de datos, se presenta el diseño de un modelo
multidimensional, se muestra la materialización del
hypercubo y el algoritmo propuesto para la selección del
conjunto óptimo de vistas a materializar, se analizan los
trabajos existentes y finalmente se presentan las
conclusiones.
Materiales y Métodos
Se tuvo la oportunidad de participar en el proyecto
ADELEM, lo que permitió validar la propuesta. Así, en este
trabajo, se presenta una experimentación sobre datos
médicos del proyecto.
El presente trabajo se realizó como parte del proyecto
NODS (Networked Open Database Services). http://wwwlsr.imag.fr/Les.Groupes/STORM/Storm\\2002/Francais/index.html.
El proyecto ADELEM
Este proyecto consiste en la construcción de herramientas de
software necesarias para la toma de decisión logística y
médica, en el marco de las SROS (Organizaciones de Salud
y Social, por sus siglas en francés) administradas por las ARH
(Agencias Regionales de Hospitales, por sus siglas en
francés). En el sistema de cuidados de una región, estas
agencias se encargan de distribuir de manera óptima los
servicios médicos (la "oferta") en relación a las necesidades
de salud (la "demanda"). A partir de las observaciones de
salud que constituyen la información primaria,
esencialmente contenidas en los datos PMSI (Programa de
Medicina del Sistema de Información de los hospitales, por
sus siglas en francés), es necesario el diseño y construcción
de herramientas de software para el análisis y la
visualización de los datos.
El proyecto ADELEM fue abordado por un equipo
interdisciplinario, compuesto por: personal médico
(Laboratorio TIMC IMAG, UMR CNRS 5525), personal del
Laboratorio de Biometría y Biología Evolutiva, UMR CNRS
5558, que proporciona el análisis estadístico de los datos
médicos y por la Organización Mundial de la Salud
(domiciliada en Suiza), quien desarrolló un software
denominado HealthMapper para la creación y la
manipulación de datos geográficos. Nuestro equipo,
Laboratorio LSR IMAG, UMR CNRS 5526, proporcionó el
soporte requerido para las bases de datos y los almacenes de
datos.
En el marco del proyecto ADELEM, se propone adaptar
nuestro conocimiento al problema de la gestión de datos
médicos,
que
constituyen
un
marco
aplicativo
particularmente interesante. De hecho, estos datos se
encuentran distribuidos en varias fuentes que hay que, en
un primer esfuerzo, federar para constituir un almacén de
datos pertinentes para la aplicación deseada. Esta etapa es
importante, puesto que se debe no sólo identificar las
fuentes, sino también determinar la forma de extraer de
dichas fuentes los datos seleccionados. De igual forma antes
de su almacenamiento, se debe determinar si los datos serán
extraídos como están, o si hay que precalcularlos
aplicándoles funciones específicas como agrupaciones,
sumas, etc. Además, se debe establecer un mecanismo para
la gestión de la evolución. Para esto último, hay que adaptar
la aplicación de extracción, la de los agregados y la del
análisis.
Esta problemática es general a la construcción de
cualquier almacén, sin embargo, se debe, en este caso,
tener en cuenta la naturaleza particular de los datos de
estudio: tipo, formato, semántica, confidencialidad, grado
de fiabilidad y de confianza, informaciones faltantes o
Serna Encinas y Manzano Torres., Algoritmo para la arquitectura ROLAP.
5
INVURNUS, Vol. 5 No. 1 (2010):3-12
incompletas, etc. En resumen, se trata de construir un
almacén que contenga datos pertinentes y de calidad sobre
los cuales se fundamentará la herramienta de análisis y el
proceso de ayuda a la toma de decisión.
Las fuentes del proyecto ADELEM son distribuidas,
heterogéneas y contienen datos de salud públicos (RSA
"Resumen de Salidas Anónimas", RHA "Resumen Mensuales
Anónimas", CIM10 "Clasificación Internacional de
Enfermedades Versión 10", FINESS "Archivo Nacional de
Establecimientos Sanitarios y Sociales") y datos demográficos
(RP99 "Censo Poblacional") (Belot, 2002). Estos últimos datos
provienen del Instituto Nacional de Estadística y de Estudios
Económicos.
Diseño de un Modelo Multidimensional
Se mencionó precedentemente que el diseño de un modelo
es una tarea compleja y delicada. A continuación se
presenta el esquema en constelación propuesto para
ADELEM.
Esquema en copos de nieve para ADELEM. La Figura 1
muestra el esquema en copo de nieve con una relación de
hechos y sus dimensiones. La relación de hechos
Paciente_MCO (Medicina-Cirugía-Obstetricia) fue creada
para la gestión de estancias cortas hospitalarias, y se
compone de las dimensiones CIM10, Modo_salida, Tiempo,
Edad, Peso_nac, Establecimiento y Zona_geo. Además, las
jerarquías H_Tiempo, H_Geo y H_Region.
A continuación, se describe la relación de hechos
Paciente_MCO:
El esquema de un cubo es un tupla Cs = (cn, M, D),
donde:
cn = Paciente_MCO
M = {CompteDuree_sejour, SommeDuree_sejour}
D = {Etablecimiento, CIM10, Modo_salida, Tiempo, Edad,
Zona_geo, Peso_nac}
El esquema de una dimensión es una tupla Ds = (dn, P,
H), donde:
dn = Establecimiento.
P = {Cle_Finess, Raison_Sociale, Adresse, Codepostal, CA1 .. CA7,
CMO1 .. CMO7, Commune, Departement, Region, Pays}
H = {H_Geo}
El esquema de una jerarquía es una tupla Hs = (hn, L, ∝),
donde:
hn = H_Geo
L = {Ciudad, Departamento, Region, Pais}
∝ = {(Ciudad, Departamento), (Departamento, Region),
(Region, Pais)}
Vistas materializadas. Para el caso experimental, se retoma
la estrella Paciente_MCO y solamente las dimensiones:
Establecimiento, CIM10, Tiempo y Modo_salida. Utilizando
este esquema se construyó un almacén conteniendo una
muestra de 10% de los datos reales. Se utilizó el sistema
decisional de Oracle9i Entreprise Edition Release 9.2.0.1.0
para la creación del esquema y para la generación de vistas
materializadas. Esto permitió conocer el costo de
almacenamiento (representado por el número de tuplas del
resultado) de cada vista y de poder fácilmente determinar su
costo de cálculo (producto de las cardinalidades
aproximativas de las relaciones de base).
Figura 1. Esquema en constelación para ADELEM.
6
INVURNUS, Vol. 5 No. 1 (2010): 3-12
Materialización del Hipercubo
En los sistemas de decisión, los usuarios están interesados en
consultas de tipo: "número de pacientes del hospital E1 para
la enfermedad C1". En este caso, la célula (E1, C1, ALL1, ALL,
m1), conteniendo el valor de: "número de pacientes del
hospital E1 para la enfermedad C1 para todos los meses
(ALL) y para todos los modos de salida (ALL)".
Podemos calcular el valor de la célula (E1, C1, ALL, ALL,
m1) como la suma de los valores de las células de (E1, C1,
T1, M1, m1), ..., (E1, C1, TNtemps, MNmode, m1), donde TNtemps y
MNmode representan respectivamente el conjunto de meses y
el conjunto de modos de salida. Todas las células
conteniendo el valor ALL en uno de sus ejes son células
dependientes. Así, para la selección de vistas a materializar,
el problema se reduce a determinar el conjunto de células
dependientes a materializar. Puesto que el costo de
almacenamiento2 para una materialización de todas la vistas
es de 206781 tuplas ( ∑i=1, ..., nCS(vi), donde CS(vi) es el costo
de almacenamiento de las vistas de la tabla 1, tenemos un
porcentaje de 74% ((206781-53799)*100/206781) de
células dependientes para el esquema Paciente_MCO
construido.
La vista V1 representa los datos de detalle del
subesquema Paciente_MCO. El costo de almacenamiento
(representado por el número de tuplas del resultado) es de
aproximadamente 54K y el costo de cálculo (producto de las
cardinalidades aproximativas de las relaciones de base) es de
90M. Por lo que se refiere al costo de cálculo, se determinó
de la siguiente manera:
CC(Establecimiento)*CC(CIM10):3.7K*18K = 70M,
Donde: CC representa el costo de cálculo+CS(V6)*CC(Tiempo):
14K*12 = 168K, donde CS representa:
costo de almacenamiento+CS(V2)*CC(Modo_salida):47K*5=235K
Entonces tenemos: (70M+168K+235K) ≈ 70M
La Figura 2 representa el latice del cubo, conteniendo el
costo de almacenamiento a la derecha de cada nodo (vista)
y el costo de cálculo a la izquierda:
A continuación, se determinó el conjunto de vistas
posibles a materializar. La Tabla 1, contiene las 15 vistas
para una materialización completa, así como su costo de
almacenamiento y de cálculo3. La Figura 2 representa el
hypercubo
sobre
4
dimensiones
del
esquema
Paciente_MCO, se utilizó la notación: M por millón y K por
mil.
Tabla 1. Relación de vistas con el costo de cálculo y de
almacenamiento.
Vista
Relaciones
V1
Establecimiento+CIM10+
Tiempo+Modo_salida
E+C+T
E+C+M
M+C+T
E+T+M
E+C
C+T
C+M
E+T
E+M
T+M
C
E
T
M
V2
V3
V4
V5
V6
V7
V8
V9
V10
V11
V12
V13
V14
V15
Costo de
almacenamiento
53799 tuplas
Costo de
cálculo
70M
47133
18456
32918
603
13973
26058
8186
184
58
48
5329
19
12
4
70M
70M
344K
46K
70M
214K
90K
45K
19K
60
18K
3.7K
12
5
1
Se utilizó la recomendación de agregar el valor ALL al dominio de la dimensión T y
M, presentada en Gray y col., 1995.
2
El costo de almacenamiento de una consulta es el número de tuplas del resultado.
3
Producto de las cardinalidades aproximativas de la relaciones de base.
Figura 2. Hipercubo del esquema Paciente_MCO.
Selección de vistas a materializar. Se formalizó la selección
de vistas a materializar utilizando el algoritmo Greedy
propuesto por (Harinarayan, Rajaraman & Ullman 1995;
Harinarayan, Rajaraman & Ullman 1996). Se decidió
utilizar este algoritmo por dos razones, la primera porque se
tienen todos los datos necesarios para su utilización. Así, no
se necesitó hacer hipótesis, principalmente, para el costo de
almacenamiento, puesto que se cuenta con el costo real de
almacenamiento de cada vista posible a ser materializada.
La segunda razón, a nuestro conocimiento la más
importante, es la idea que tenemos de reutilizar el número
de vistas dependientes como un parámetro inicial para la
Serna Encinas y Manzano Torres., Algoritmo para la arquitectura ROLAP.
7
INVURNUS, Vol. 5 No. 1 (2010):3-12
frecuencia de utilización de una vista (Recordamos que una
vista Vi es dependiente de Vj si y sólo si, podemos responder
Vi utilizando Vj, así, Vi ∝ Vj).
Se utilizó el hipercubo de la Figura 2 y se considera que
el costo de almacenamiento está representado por el
número de tuplas de la vista. Así, se puede determinar el
conjunto de vistas dependientes de cada vista de la manera
siguiente:
Relaciones de dependencia al interior del hipercubo:
V2: V6 ∝ V2, V7 ∝ V2, V9 ∝ V2, V12 ∝ V2, V13 ∝ V2, V14 ∝ V2,
V16 ∝ V2.
V3: V6 ∝V3, V8 ∝V3, V10 ∝ V3, V12 ∝ V3, V13 ∝ V3, V15 ∝ V3,
V16 ∝ V3.
V4: V7 ∝ V4, V8 ∝ V4, V11 ∝ V4, V12 ∝ V4, V14 ∝ V4, V15 ∝
V4, V16 ∝ V4.
V5: V9 ∝ V5, V10 ∝ V5, V11 ∝ V5, V13 ∝ V5, V12 ∝ V5, V15 ∝
V5, V16 ∝ V5.
V6: V12 ∝ V6, V13 ∝ V6, V16 ∝ V6.
V7: V12 ∝ V7, V14 ∝ V7, V16 ∝ V7.
V8: V12 ∝ V8, V15 ∝ V8, V16 ∝ V8.
V9: V13 ∝ V9, V14 ∝ V9, V16 ∝ V9.
V10: V13 ∝ V10, V15 ∝ V10, V16 ∝ V10.
V11: V14 ∝ V11, V15 ∝ V11, V16 ∝ V11.
V12: V16 ∝ V12.
V13: V16 ∝V13.
V14: V16 ∝V14.
V15: V16 ∝ V14.
Algunas notaciones:
n = Número de iteraciones.
C(v) = Costo de almacenamiento de la vista v (representada
por el número de tuplas del resultado).
∝ = Relación de dependencia. Por ejemplo, Q2 ∝ Q1 si y
solamente si, Q2 puede ser respondido por Q1.
S = Conjunto de vistas seleccionadas,
B(v, S) = Beneficio de la vista v relativa a S,
1) Por cada w ∝ v, definir la cantidad Bw por:
a) Si u es la vista de costo inferior en S, tal que w ∝ u}.
Subrayamos que el
conjunto S contiene al menos la
vista V1 (top view), y
b) Si C(v) < C(u), entonces Bw = C(v) - C(u). Si no Bw = 0.
2) Definir B(v, S) = ∑w ∝ v Bw.
A continuación se muestra el pseudocódigo del algoritmo
Greedy para una selección de n vistas a materializar.
Se utilizó el hipercubo de la Figura 2 para la aplicación
del algoritmo. La siguiente tabla describe los resultados con
n igual a 7 (Tabla 2).
A continuación, se formaliza la selección de vistas a
materializar utilizando el algoritmo Greedy.
Vista
1ª Selección
Tabla 2. Aplicación del algoritmo Greedy a los datos ADELEM.
2ª Selección
3ª Selección
4ª Selección
5ª Selección
6ª Selección
7ª Selección
V2
V3
V4
V5
(7K)*8=56K
(35K)*8=280K
(20K)*8=160K
(53K)*8=424K
(7K)*4=28K
(36K)*4=144K
(20K)*4=80K
--
(7K)*2=14K
-(20K)*2=40K
--
(7K)*1=7K
----
(7K)*1=7K
----
(7K)*1=7K
----
-----
V6
(40K)*4=160K
(40K)*2=80K
(4K)*2=8K
(4K)*2=8K
(4K)*1=5K
(4K)*1=5K
(4K)*1=5K
V7
(28K)*4=112K
(28K)*2=56K
(28K)*1=28K
(7K)*1=7K
(7K)*1=7K
--
--
V8
(46K)*4=184K
(46K)*2=92K
(10K)*2=20K
(10K)*2=20K
--
--
V9
V10
V11
(54K)*4=216K
(54K)*4=216K
(54K)*4=216K
(419)*4=2K
(545)*4=2K
(555)*4=2K
(419)*4=2K
(545)*4=2K
(555)*4=2220
(419)*3=1K
(545)*4=2K
(555)*4=2220
(419)*4=2K
(419)*4=2K
(545)*4=2K
(545)*4=2K
(555)*4=2220 (555)*4=2220
(419)*4=2K
(545)*4=2K
(555)*4=2220
V12
V13
(49K)*2=98K
(54K)*2=108K
(48470)*1=49K
(584)*2=1K
(13127)*1=13K
(584)*2=1K
(13127)*1=13K
(584)*2=1K
(2857)*1=3K
(584)*2=1K
(2857)*1=3K
(584)*2=1K
(2857)*1=3K
(584)*2=1K
V14
V15
(54K)*2=108K
(54K)*2=108K
(591)*2=1K
(599)*2=1K
(591)*2=1K
(599)*2=1K
(591)*2=1K
(599)*2=1K
(591)*2=1K
(599)*2=1K
(591)*2=1K
(599)*2=1K
(591)*2=1K
(599)*2=1K
V16
(54K)=54K
(602)=602
(602)=602
(602)=602
(602)=602
(602)=602
(602)=602
{V1}
S=S+V5
S=S+V3
S=S+V4
S=S+V8
S=S+V7
S=S+V2
S=S+v6
--
8
INVURNUS, Vol. 5 No. 1 (2010): 3-12
Para la primera iteración, el funcionamiento del
algoritmo Greedy es bastante simple, puesto que solamente
tenemos la vista V1 en el conjunto S; de esta manera el
valor de u es igual a 54K (el costo de V1), ya que ella
representa la vista con el costo de almacenamiento menor
en el conjunto S. Así, para obtener el beneficio óptimo de
V2, se debe calcular la diferencia del costo de
almacenamiento de V2 en relación a V1 (47K–54K) y se
multiplica la diferencia por el número de relaciones
dependientes de V2 (V2, V6, V7, V9, V12, V13, V14 y V16),
lo que da 56K (7K*8) de beneficio óptimo para V2. Para
V3, el mecanismo es parecido, así se tiene 280K. En el caso
de V6, se multiplica la diferencia del costo de
almacenamiento entre V6 y V1 por las vistas dependientes
de V6 (V6, V12, V13, y V16) y así sucesivamente.
Una vez calculado el beneficio óptimo del conjunto de
vistas, se debe escoger la que tenga el beneficio mayor. En
la primera iteración, la selección es la vista V5, con el
beneficio más elevado (53K*8 = 424K), el beneficio es
calculado de la manera siguiente: costo (V5)–costo(V1) =
53K multiplicado por 8, el número de vistas dependientes
de V5 (V5, V9, V10, V11, V13, V12, V15 y V16).
Sin embargo, conforme se llena el conjunto S, se debe
siempre escoger el costo de almacenamiento mínimo de u al
interior de S del cual la vista dependa. Así, en la segunda
selección, para algunas vistas, u es representada por 54K (el
costo de almacenamiento de V1), mientras que para las
vistas que dependan de V5 (que fue seleccionada en la
primera iteración), u es 603 (el costo de almacenamiento de
V5). Por ejemplo, el beneficio óptimo de V2 es 28K, puesto
que la diferencia entre los costos de almacenamiento de V2
y V1 (siempre 7K) es multiplicado por 4 (V2, V6, V7 y V12).
Las otras vistas dependientes de V2 (V9, V13, V14 y V16) no
son tomadas en cuenta, ya que tienen un beneficio más
elevado con la vista V5.
En la segunda iteración, la selección es V3 con 144K
(36K*4 (V3, V6, V8 y V12)), las otras vistas dependientes de
V3 no son consideradas, puesto que tienen un beneficio
óptimo con la vista V5. Finalmente, la última línea contiene
el resultado, ella representa el conjunto S = {V5, V3, V4,
V8, V7, V2, V6}.
Algoritmo propuesto para la selección de vistas a
materializar. En nuestro algoritmo, las relaciones
dependientes de una vista juegan un rol esencial, así, se
considera que su número representa un parámetro inicial
para la frecuencia de utilización así como para el costo de
cálculo. Para el primero, se multiplica el beneficio óptimo,
dado por el algoritmo Greedy, por el número total de
relaciones dependientes, ya que para nosotros, la frecuencia
de utilización aumenta en proporción directa al número de
relaciones dependientes. Para el costo de cálculo, se
considera que disminuye con relación al número de
relaciones dependientes, así, se divide el costo de cálculo
entre el número total de relaciones dependientes.
El presente algoritmo considera también la probabilidad
de cambio de las relaciones de base. En ese caso, se
necesita el número de elementos al interior de la vista que
pueden sufrir cambios. Consideremos por ejemplo la vista
V2. Ella se compone de las relaciones Establecimiento,
CIM10 y Tiempo. La relación Establecimiento contiene 24
atributos, CIM10 y Modo_salida contienen 2 atributos y
Tiempo 4 (cf. Párrafo: Esquema en copos de nieve para
ADELEM). Se tuvieron 36 elementos que pueden
evolucionar (32 propiedades y 4 dimensiones). Suponiendo
que se tiene una probabilidad de cambio de 20%, así, el
cálculo para la frecuencia de actualizaciones de V2 es
(33*100/36*.20), donde 33 es el número de elementos de
la vista V2.
Algunas notaciones:
CC = costo de cálculo (producto de cardinalidades
aproximativas de las relaciones base) dividido entre el
numero de relaciones dependientes. Por ejemplo, el CC(v) si
v = V2 es: CC(V2) = ((3.7K*18K)+(14K*12))/8≈70M/8 =
9M, donde 8 es el número total de relaciones dependientes
de V2.
PC = Probabilidad de cambio de relaciones de base
multiplicado por el costo de cálculo. Por ejemplo, si se tiene
la hipótesis de 20% de cambio de los elementos del
esquema sobre la vista V2 (3 dimensiones y 30 atributos que
pueden cambiar), entonces PC(V2) = (3300/36*.20)*9M=
2M.
V = Conjunto de vistas.
S = Conjunto de vistas seleccionadas.
w = Número de iteraciones.
fq(v) = Complejidad de la vista (número total de las
relaciones dependientes de la vista v).
v = Vista seleccionada.
vo = C(vista T “top view”).
La Figura 3 muestra el algoritmo propuesto incluyendo la
frecuencia de utilización, el costo de cálculo y la
probabilidad de cambio; mientras que la Tabla 3 muestra los
resultados de la aplicación de nuestro algoritmo para las 7
primeras selecciones, considerando el 20% como frecuencia
de actualizaciones sobre las relaciones base.
Serna Encinas y Manzano Torres., Algoritmo para la arquitectura ROLAP.
9
INVURNUS, Vol. 5 No. 1 (2010):3-12
Figura 3. Pseudocódigo del algoritmo propuesto.
Para la primera selección el valor de vo es igual a 54K, el
costo de V1, ya que ella representa la vista con el costo de
almacenamiento mínimo en el conjunto S. Para la segunda y
tercera elección ella está representada por 603 (el costo de
V5), ya que es la vista que tiene el costo inferior al interior
de S. En la primera iteración, la selección es la vista V5, ya
que representa la más alta ganancia (((((53K*8)*8) =
3392K–((61K/8)*1.18 = 9K) = 3M). La ganancia es
Vista
V2
V3
V4
1ª Selección
(427K-8M)=-8M
(1M-8M)=-7M
(1M-42K)=1M
calculada de la manera siguiente: costo(V5)–costo(V1) =
(53K*8) representa la ganancia de Greedy, se multiplica esta
ganancia por el numero de relaciones dependientes de V5
(V5, V9, V10, V11, V12, V13, V15 y V16). Enseguida, se le
resta el costo de cálculo dividido entre el número de
relaciones dependientes y multiplicadas por la frecuencia de
actualizaciones.
Tabla 3. Aplicación del algoritmo propuesto a los datos ADELEM.
2ª Selección
3ª Selección
4ª Selección 5ª Selección
-8M
-7M
625K
-8M
-7M
--
-8M
-7M
--
-8M
-7M
--
6ª Selección
7ª Selección
-8M
-8M
--
-8M
-8M
--
V5
(3M-6K)=3M
--
--
--
--
--
--
V6
(637K-17M)=-16M
-16M
-16M
-16M
-16M
-16M
-16M
V7
(444K-53K)=391K
169K
2K
-26K
-26K
-26K
-26K
V8
V9
V10
V11
V12
V13
V14
V15
(730K-22K)=708K
(858K-11K)=847K
(860K-5K)=855K
(860K-15)=860K
(388K-9K)=379K
(430K-2K)=428K
(215K-6)=215K
(215-2)=215K
343K
-4K
4K
9K
88K
474
2K
2K
176K
-4K
4K
9K
46K
474
1K
2K
--4K
4K
9K
-3K
474
2K
2K
--8K
-292
--3K
-2K
137
173
--8K
-292
--3K
-693
65
--
--8K
-292
--3K
-693
---
{V1}
S=S+V5
S=S+V4
S=S+V8
S=S+V11
S=S+V15
S=S+V14
S=S+V10
10
INVURNUS, Vol. 5 No. 1 (2010): 3-12
que el beneficio es mínimo, pero que los costos de su
materialización prácticamente se duplican.
La segunda selección es la vista V4 con 625K (((21K*4*8)
=672K–((346K/8)*1.06=46K)=626K),
las
vistas
dependientes son (V4, V7, V8 y V12), las otras vistas
dependientes de V4 no son consideradas, puesto que tienen
una ganancia inferior al de la vista V5. Sin embargo,
multiplicamos el resultado por el número total de vistas
dependientes y se dividió el costo de cálculo entre este
número total. Finalmente, la última línea contiene el
resultado, representando el conjunto S = {V5, V4, V8, V11,
V15, V14, V10}.
La gráfica de la Figura 4 contiene el costo de
almacenamiento en el eje Y en número de tuplas y las 7
primeras
vistas
seleccionadas
para
su
posible
materialización, en el eje X. Se puede constatar que el
algoritmo Greedy es simple y eficaz, sin embargo, en
nuestra experimentación, en la 6ta elección, el algoritmo
selecciona una de las vistas más costosas (V2).
La Figura 5 muestra la aplicación de nuestro algoritmo
con relación a los costos de cálculo. Consideramos los 7
primeros resultados y constatamos que nuestro algoritmo da
mejores resultados que los obtenidos por el algoritmo
Greedy. En particular, si se toma como referencia la figura 2
del hipercubo, se remarca que la selección está hecha de la
manera siguiente: del segundo nivel (3 Dim), nuestro
algoritmo selecciona las dos vistas de ganancia óptima. Para
el tercer nivel (2 Dim), selecciona las 3 mejores y finalmente
para el último nivel (1 Dim), selecciona las dos primeras
vistas óptimas en nuestro caso experimental.
Resultados y Discusión
En la figura siguiente, se dibuja un gráfico que muestra
la aplicación del algoritmo Greedy y del algoritmo
propuesto en relación al costo de almacenamiento.
Consideramos solamente los 7 primeros resultados, incluso
si, a partir de la 6ta iteración, no se tiene ninguna ventaja
para la materialización. Por ejemplo, la vista V2, resultado
de la 6ta iteración, tiene por costo de almacenamiento 47K.
Si se hace la comparación de este resultado, en relación con
la vista V1, que estamos obligados a materializar, se percibe
V2
Greedy
50K
40K
Número de
tuplas
V4
Algoritmo
propuesto
V4
V7
30K
20K
10K
1K
V6
V3
V8
V8
V5
V11
V5
1
2
3
V15
4
V10
V14
5
6
7
……….
n
Figura 4. Comparación de resultados en relación al costo de almacenamiento.
Serna Encinas y Manzano Torres., Algoritmo para la arquitectura ROLAP.
11
INVURNUS, Vol. 5 No. 1 (2010):3-12
V4
70M
V3
.
.
.
.
V2
V4
V6
Greedy
Número
400K
de
tuplas
Algoritmo.
propuesto
300K
V7
200K
100K
V8
V5
V8
V5
V11 V15
1
2
3
4
5
V14
6
V10
7 ……….
n
Figura 5. Comparación de resultados en relación al costo de cálculo.
Conclusiones
Del diseño de un esquema en constelación propuesto
para ADELEM, se tomó la tabla de hechos Paciente_MCO y
4 de sus dimensiones para la implementación del
subesquema Paciente_MCO.
En relación a la selección de vistas a materializar, se
utilizó el subesquema Paciente_MCO construido para lograr
la materialización del hypercubo, lo que permitió conocer
el costo de almacenamiento de las vistas y de poder
determinar su costo de cálculo. Se utilizó el algoritmo
Greedy para la selección del conjunto óptimo de vistas a
materializar, sin embargo, en nuestra experimentación, a
partir de la 6ta iteración, el algoritmo Greedy seleccionó las
vistas más costosas. Esto nos motivó a proponer un
mecanismo para una selección más confiable. Nuestro
algoritmo considera los parámetros de frecuencia de uso, de
costo de cálculo y de probabilidad de cambio en las
relaciones de base. Probamos el algoritmo propuesto con
datos médicos reales y se constató que nuestra proposición
dio mejores resultados en nuestro caso experimental, tanto
en la comparación de costos de almacenamiento, como en
la de costos de cálculo, lo que nos permite concluir que el
algoritmo propuesto brinda una alternativa más confiable y
robusta al determinar la selección del conjunto óptimo de
vistas a materializar.
Bibliografía
Doucet, A. & Gangarski, S. 2001. Entrepôts de Données et
Internet, Modèles, langages et systèmes. France: Hermès.
Kimball, Ralph 1996. Entrepôts de données, Guide pratique du
concepteur de data Warehouse. France : John Wiley and Sons,
Inc.
Kimball, Ralph & Ross M. 2003. Entrepòts de données, Guide
pratique de modélisation dimensionnelle. France : Vuibert.
Belot, Aurélian. 2002.
Développement d’un logiciel de
cartogaphie de l’offre et de la demande de soins hospitaliers en
France. France : Projet ADELEM-SIGT.
Gray, J., Bosworth, A., Layman, A. & Pirahesh, H. 1995. Data
Cube: A Relational Aggregation Operator Generalizing Group-By,
Cross-Tab and Sub-Totals. USA: Microsoft.
Harinarayan, V., Rajaraman, A. & Ullman, J. 1995. Implementing
Data Cubes Efficiently. A full version. USA: Stanford.
12
INVURNUS, Vol. 5 No. 1 (2010): 3-12
Harinarayan, V., Rajaraman, A. & Ullman, J. 1996. Implementing
Data Cubes Efficiently. USA: SIGMOD-ACM.
Gupta, A & Mumick, I. 1995. Maintenance of Materialized Views:
Problems, Techniques and Applications, Revista, vol. 18, núm 2.
USA: IEEE Quarterly Bulletin on Data Engineering: Special Issue
on Materialized Vies and Data Warehousing.
Levy, A., Mendelzon, A., Sagiv, Y. & Srivastava, D. 1995.
Answering Queries Using Views. USA: Proceedings of the 14th
ACM SIGACT-SIGMOD-SIGART.
Chan, G., Li, Q. & Feng, L. 1999. Design and Selection of
Materialized Views in Data Warehousing: A Case Study. USA:
ACM International Workshop on Data Warehousing and OLAP.
Yang, J., Karlapalem, K. & Li, Q. 1997. Algorithms for Materialized
View Design in Data Warehousing Environment. USA: Very
Large Data Bases.
Baril, X. & Bellahsène, Z. 2003. Selection of Materialized Views: A
Cost-Based Approach. USA: J. Eder and M. Missikoff.
Zhang, C., Yao, X. & Yang, J. 2001. An evolutionary approach to
materialized view selection in da data warehouse environment,
Revista, Vol 31. USA: IEEE Trans. Systems, Man, Cybernetics,
PART C.
Serna Encinas y Manzano Torres., Algoritmo para la arquitectura ROLAP.