Bases de datos Temporales

El tiempo lo es todo

Jesús García Sáez

Zaragoza @ 17-Enero-2007

¿Qué vamos a ver?

• Introducción al contexto y problema
• Ejemplo versión "inicial"
• Profundización BD Temporales
• Ejemplo versión "temporal"
• Más allá de la investigación
• EOF

¿Qué es una BD Temporal?

• BD + Tiempo
  • No hay datos, sino datos temporales
  • Datos + marcas de tiempo
• La información del sistema, y su evolución
  • Datos Actuales
  • Datos Históricos

"El mejor profeta del futuro es el pasado"

Algún concepto...

• Tipos de información temporal
  • Eventos
  • Periodos
• Dimensiones temporales
  • Dimensiones
    • Tiempo de validez
    • Tiempo de transacción
  • Ortogonales
    • Que son diferentes e independientes
  • Datos Bitemporales
    • Dato que contiene tanto tiempo de validez como tiempo de transacción

Tipos de información temporal

• ¡El tiempo es infinito y continuo!
• Discretización del tiempo (Sistema de referencia temporal)
• Linea del tiempo como un conjunto de puntos de una determinada granularidad
  • Granularidad: duración del punto de tiempo aplicable.
• Ejemplos:
  • Paco nació el 15-08-04. Evento, granularidad días
  • Paco vivió desde abril 1923 hasta agosto de 1942 en Madrid. Intervalo, granularidad meses

Dimensiones temporales

• Tiempo de validez
  • Dada una proposición p
    • Paco intenta hacer las prácticas de BDA
  • Conjunto de tiempos (periodo) en los que p es verdadera (en el MundoReal™)
    • Desde hace 2 años [17/01/2005, now]
    • Las hizo el año pasado (en tiempo record) [10/10/2005, 10/02/2006]
• Tiempo de transacción
  • Conjunto de tiempos en los que p estuvo (o está) representada en la BD
    • Mantenido por el sistema
    • Explicita o implicitamente en el sistema de bitácoras

¡Pueden ser diferentes!

BD Temporales, últimos aspectos

• Necesitamos lenguaje de consulta temporal


• Operandos (algebra relacional) "nuevos" temporales


• Nuevos tipos (INTERVAL) temporales.

Operaciones básicas

• Insertar: Paco nace en Zaragoza el 04/08/1923
  • (Paco, Zaragoza, 04/08/1923, now)
• Actualizar: Paco se muda a Soria el 16/04/1942
  • (Paco, Zaragoza, 04/08/1923, 15/04/1942)
  • (Paco, Soria, 16/04/1942, now)
• Eliminar: Paco muere el 01/01/2000
  • (Paco, Zaragoza, 04/08/1923, 15/04/1942)
  • (Paco, Soria, 16/04/1942, 01/01/2000)
• Por complicar, se puede complicar bastante... no lo haremos, todavía...

Ejemplo, Teatro: BD Inicial

Controlamos teatros, los cuales a veces pueden estar cerrados, abiertos, en construccion, etc... en ellos se representan obras. Éstas pueden estar en varios teatros, y cada teatro podrá tener varias obras (como un multicine vamos).

• Teatro (Nombre, Ciudad, Estado, ...)
• Representar (Teatro, Obra)
• Obra (Nombre, ...)

Teatro: BD Inicial (II)

• Las claves primarias son evidentes
• Restricciones de clave externa en Representar
• Par de consultas simples
  • Teatros que emiten alguna obra
    • Proyección simple:
      Representar { Teatro }
    • En SQL:
      SELECT DISTINCT Teatro FROM Representar
  • Teatros que actualmente no emiten ninguna obra
    • Diferencia de dos proyecciones simples:
      Teatro { Nombre } MINUS
      Representar { Teatro }
    • En SQL:
      SELECT Nombre FROM Teatro WHERE NOT IN (
      SELECT DISTINCT Teatro FROM Representar
      )

Teatro: Temporal time!

• ¿Claves? (de Teatro u Obra)
  • ¿candidatas? (Nombre, Fecha_Inicio) y (Nombre, Fecha_Fin)
  • ¿primaria? A gusto del consumidor
• ¿Restricciones?
  • Intervalos absurdos.
    Fecha_Inicio <= Fecha_Fin
  • ¿de Contigüidad?
    Tuplas con mismos valores pero Fecha_Fin₁+1 = Fecha_Inicio₂
  • ¿de Solapamiento?
    Tuplas que sus fechas se solapan.
  • ¿de Clave ajena? En verdad ahora no tenemos clave ajena. ¡No es válida!
    Fechas de Representar, "subconjunto" de fechas de teatro

Teatro: Temporal time!? (II)

• Podemos crear restricciones que cumpliesen los requisitos, aunque serían bastante laboriosas...
• Consultas anteriores
  • Obtener tuplas (Teatro, Fecha_Inicio, Fecha_Fin) para los teatros que han representado obras alguna vez, donde Fecha_Inicio y Fecha_Fin indican un periodo continuo máximo durante el cual el teatro tenía alguna obra.
  • Obtener tuplas (Teatro, Fecha_Inicio, Fecha_Fin) para los teatros que no han podido representar obra alguna durante en algún tiempo, donde Fecha_Inicio y Fecha_Fin indican un periodo continuo máximo durante el cual el teatro no tenía ninguna obra.
• Ahora vas y las haces
• Es hora de inventarse algo

Tipo Intervalo

• Definimos un nuevo tipo INTERVAL(tpPunto).
  • INTERVAL es un generador de tipo.
  • tpPunto es el tipo de punto que determinará el tipo final y la precisión de los puntos
    • Solo válido si posee función sucesora
    • Debe existir un ordenamiento total para todos sus valores
• Un intervalo i de tipo INTERVAL(tpPunto) es un valor escalar para el cual están definidos
  • START(i) y END(i) que devuelven un valor tipo tpPunto
  • START(i) <= END(i)
  • p IN i verdaderos si y solo si START(i) <= p AND p <= END(i), siendo p un valor de tipo tpPunto.
• Evidente, ¿no? Ahora vienen cosas más divertidas.

Operadores sobre Intervalos (I)

Sea i1=[s1,e1] e i2=[s2,e2] de tipo INTERVAL(tpPunto)

• Operadores de Allen
• i1 = i2, sii s1 = s2 AND e1 = e2
• il BEFORE i2, sii e1 < s2
• i1 MEETS i2, sii s2 = e1 + 1 OR s1 = e2 + 1
• i1 OVERLAPS i2, sii s1 <= e2 AND s2 <= e1
• i1 DURING i2, sii s2 <= s1
• i1 STARTS i2, sii s1 = s2 AND e1 <= e2
• i1 FINISHES i2, sii e1 = e2 AND s1 >= s2


• Operadores adicionales
  • i1 MERGES i2, sii i1 MEETS i2 OR i1 OVERLAPS i2
  • i1 CONTAINS i2, sii i2 DURING i1


• Operadores diádicos que devuelven segmentos
  • i1 UNION i2, devuelve [MIN(s1, s2), MAX(e1, e2)] sii i1 MERGES i2
  • i1 INTERSECT i2, devuelve [MAX(s1, s2), MIN(e1, e2)] sii i1 OVERLAPS i2

Operadores sobre Intervalos (II)

Operadores UNFOLD y COALESCE. Toman un conjunto de intervalos del mismo tipo y devuelven otro conjunto similar equivalente.

{ [d01, d01], [d03, d05], [d04, d06] }
{ [d01, d01], [d03, d04], [d05, d05], [d05, d06] }

• UNFOLD, forma desdoblada. Conjunto de todos los intervalos de la forma [p, p], donde p es un punto, que está en algún de los conjuntos iniciales
  
  { [d01, d01], [d03, d03], [d04, d04], [d05, d05], [d06, d06] }
• COALESCE, forma fundida. Conjunto de intervalos donde no existen intervalos distintos, i1 e i2, tal que i1 MERGES i2
  
  { [d01, d01], [d03, d06] }

Podrían considerarse como las formas canónicas del original.

Teatro: Restricciones ¡Esta vez si!

Teatro: Consultas (I), ¡Esta vez si!

Teatro: Consultas (II), ¡Esta vez si!

Cuando y qué teatros no han podido representar alguna obra. Muy similar al anterior.

• Se requiere la forma desdoblada de ambas tablas para realizar entonces una resta
  • Definimos operador "desdoblar relación" R UNFOLD A
• Pasito a pasito:
  • Forma desdoblada de Teatro
    • (Teatro(Nombre, Durante) UNFOLD Durante) AS T1
  • Forma desdoblada de Representar
    • (Representar(Teatro, Durante) UNFOLD Durante) AS T2
  • Resta y agrupación. Done :)
    • (T1 MINUS T2) COALESCE Durante
• En verdad podemos declarar I_MINUS como
  • R1 I_MINUS R2 ON A
    ((R1 UNFOLD A) MINUS (R2 UNFOLD A)) COALESCE A

En definitiva, estamos reescribiendo los operadores a su versión temporal

Posibles descomposiciones

Aspectos a tener en cuenta a la hora del diseño físico

• Descomposición horizontal
  • Separar información en Histórica y Actual
  • Normalmente mala, pues quizá querramos modificar datos "históricos".
• Descomposición vertical
  • ¿Se modifican los datos con distintia frecuencia?
  • Aconsejable en la mayoría de los casos
  • Transformaríamos nuestra entidad Teatro(Nombre, Ciudad, Estado, Durante) en:
    • Teatro(Nombre, Durante)
    • Teatro_Ciudad(Nombre, Ciudad, Durante)
    • Teatro_Estado(Nombre, Estado, Durante)

BD Temporales y el mundo real

• Se empezaron a estudiar en los 70
  • En aquella época, no parecían muy atractivas debido a que se necesitaría mucho almacenamiento
• Se estudian, se estudian y se vuelven a estudiar
• Pero no hay nada listo para usarse, comercial o no-comercial
• Existen muchos lenguajes de consulta temporales, pero uno de ellos sobresale
  • TSQL2
    • Se presentó a estandar para SQL92, pero no continuó
    • Se espera que sea introducido como una extensión para SQL3
      • Para cuando salga claro...

TSQL2

• Nuevos tipos INTERVAL
• Tablas definidas como
  • Event Tablas
  • State Tables
  • Bitemporal Tables
• Posibilidad de definir CALENDARs, que son tipos que definen una granularidad
• Selecciones Valid-Time
• Selecciones Transactional-Time
• Indeterminidad temporal

Resumen

• En una BDT tenemos la evolución de los datos gracias a marcas de tiempo
• Tratamos el tiempo discrétamente mediante intervalos
• Ampliación de los operandos, con versiones temporales
• Grandes ventajas, mucha más información al alcance
• Campo excesivamente ligado a la investigación, por ahora

Referencias y bibliografía

• Date, C.J. An introduction of database systems. 2001
• J.F.Allen: "Maintaning Knowledge about Temporal Intervals", CACM 16, No 11 (nov 1983)
• Richard T. Snodgrass: The Temporal Query Language TSQL2. 1995
• Piattini, M. y Díaz, O. Advanced database technology and design.

¿Dudas existenciales?