Otras Tendencias en Bases de Datos: Parte...

Otras Tendencias en Bases de 2Datos: Parte 2

Curso 2010/2011

Sergio Ilarri Artigas

B d D t E i lBases de Datos Espaciales: Parte 1Parte 1

Introduccin (I)

Objetivo: gestin de datos espaciales 2D:

rea geogrfica (GIS)U di h d VLSI (V L S l I i ) Un diseo hardware VLSI (Very Large Scale Integration)

3D:El universo (astronoma) El universo (astronoma)

Un modelo del cerebro (medicina) La estructura de una molcula (biologa)La estructura de una molcula (biologa)

Por tanto, una BD espacial puede en principio ser til en distintas reasser til en distintas reas

Introduccin (II)

Una base de datos espacial: Ofrece tipos de datos espaciales

En su modelo de datosEn su modelo de datos En su lenguaje de consultas

Ofrece soporte para el manejo de dichos Ofrece soporte para el manejo de dichos tipos de datos:

Indexacin de datos espaciales Indexacin de datos espaciales Algoritmos e implementaciones eficientes para

operar con ellos: joins espaciales etcoperar con ellos: joins espaciales, etc.

Objetos Bsicos a Representar

Puntos

Lneas Lneas

Polilneas

Regionesg(extensin)

Colecciones de Objetos jRelacionados (I)

Particiones del espacio

Celdas de Voronoi Provincias de un pas

Colecciones de Objetos jRelacionados (II)

Particiones del espacio

Parcelas de terreno Distritos de una ciudad

Colecciones de Objetos jRelacionados (III)

Redes (grafos)

Red de carreteras, ferrocarriles,calles, etc.

Ros, lneas de electricidad, etc.

Tipos de Datos Espaciales (I) Spatial Data Types (SDT) Ejemplo: Geo-Relational Algebra (Gting, EDBT88)

Tipo de dato Significado

NUM Nmeros

REL Relaciones

STR StringsSTR Strings

BOOL Valores booleanos

POINT Puntos en el espaciop

LINE Secuencias de segmentos de una lnea

REG Regiones en el plano (PGON o AREA)

PGON Polgono (posible interseccin entre 2 valores de mismo atributo)

AREA rea (para modelar subdivisiones del plano, no interseccin)

Tipos de Datos Espaciales (II)

Por ejemplo, para representar ciudades: Ciudad(nombre: STRING, centro: POINT,

numHab: NUM))

Tipos adicionales:EXT LINE REG ( bj t t i ) EXT = LINE REG (objetos con extensin)

GEO = POINT EXT (cualquier objeto geomtrico)

Tipos de Datos Espaciales (III)

Ejemplos considerando los tipos adicionales: Ciudad(nombre: STRING, centro: POINT, ext: ( , ,

REG, numHab: NUM) Ro(nombre: STRING, ruta: LINE) Estado(nombre: STRING, area: REG, numHab:

NUM)

Tipos de Datos Espaciales (IV)

Predicados geomtricos:

Podran proponerse ms predicados: p p pabove, below, south_of, etc.

Tipos de Datos Espaciales (V)

Operaciones sobre relaciones (conjuntos de objetos geomtricos):

Tipos de Datos Espaciales (VI)

Operaciones que devuelven objetos geomtricos:

Polgono convexo ms pequeoque encierra todos los puntos

Convex hull

Tipos de Datos Espaciales (VII)

Operaciones geomtricas que devuelven nmeros:

Ejemplos de Preguntas

Ejemplos (adaptados de Gting, EDBT88) Ciudades select [centro inside Spain] Ciudades select [centro inside Spain] Ros select [ruta intersects rea]

Ci d d l t [di t( t Z ) Ciudades select [dist(centro, Zaragoza) 100 and numHab > 50 000]

Ciudades Estados join [centro inside rea] Ciudades Ros join [distance(centro, ruta) Spatial

joinsj [ ( , )

< 50]joins

Joins Espaciales

Join espacial: join basado en un predicado que compara valores de atributos espaciales Podra no atributos espaciales

Ejemplos:d l d

ser un joinespacial

Encontrar todos los parques de atracciones de todas las ciudades de Espaa

Encontrar todas las carreteras que cruzan una provincia

Encontrar pares de objetos que se solapan

Requerimientos para las q pConsultas Espaciales (I)

Segn (Egenhofer 1994):1. Tipos abstractos de datos (indep. codific.)2 Mostrar los resultados de forma grfica2. Mostrar los resultados de forma grfica3. Combinacin de resultados, interaccin

M t l t t id4. Mostrar el contexto, aunque no se pida explcitamente (interpretar el resultado)

5. Mecanismos para controlar el contenido de la salida en pantalla (dado que puede mostrar mltiples resultados)

Requerimientos para las q pConsultas Espaciales (II)

Segn (Egenhofer 1994):6. Seleccin e interaccin directa con

elementos de la pantallap7. Diversas representaciones grficas

Leyenda descriptiva (resumen)8. Leyenda descriptiva (resumen)9. Etiquetas asociadas a los objetos grficos10. Permitir seleccionar las escalas11. Soporte para restringir consultas a un p p g

rea (en lugar de a toda la BD espacial)

Ej l R l i dEjemplo Relacionado Grnulos de LocalizacinGrnulos de Localizacin

Motivacin del Ejemplo

Veamos un sistema para procesar preguntas dependientes de la localiz. Al que le vendra muy bien poder disponer Al que le vendra muy bien poder disponer

de capacidades espaciales Point queries buffering interseccin etc Point queries, buffering, interseccin, etc.

Es decir, se beneficiara de la utilizacin de una BD espacialuna BD espacial

Adems, combina ideas de dos contextos: Bases de datos de objetos mviles

Bases de datos espaciales

Contexto: PreguntasContexto: Preguntas Dependientes de la Localizacin

Preguntacontinua (fupdate)

M i i t libMovimiento libreInters en las localizaciones

Contexto: PreguntasContexto: Preguntas Dependientes de la Localizacin

Puede ser necesaria una infraestructura distribuida

Proxy

Proxy

y

Red Fija

ProxyProxyRed Fija

Grnulos de Localizacin (I)

A veces no se necesitan las localizaciones GPS

LocalizacionesGPS

GrnulodGPS de localizacin

Grnulos de Localizacin (II)

Algunas razones para usar grnulos de localizacin: Las localizaciones GPS precisas pueden no Las localizaciones GPS precisas pueden no

estar disponiblesEl usuario puede no desear GPS El usuario puede no desear GPS

Privacidad (Ej., estoy en el Ada Byron vs. t l f t d l Ad B )estoy en la cafetera del Ada Byron)

Con grnulos de localizacin es posible expresar consultas que de otro modo no seran posibles

Grnulos de Localizacin (III)

El usuario debera poder expresar consultas y recuperarconsultas y recuperar resultados de acuerdo al conceptoacuerdo al concepto de localizacin que

i ( inecesite (regiones, provincias, edificios, petc.)

Tipos de Datos (I)

Tipos de Datos (II)

P i li id d d i h l fi lPor simplicidad, podemos asumir que hay una sola figura por grnulo y no hay solapamiento

Tipos de Datos (III)

Mapas de Grnulos

Mapa de grnulos ProvinciasEspaa

Mapa de grnulos RegionesEspaap g p

Mapas de Grnulos

Andaluca

Mapa de grnulos ProvinciasEspaa

Mapa de grnulos RegionesEspaa

Nuevo mapa de grnulos(en Andaluca: provincias,

en el resto: regiones)p g pen el resto: regiones)

Arquitectura Bsica

Adems, puede estar distribuido

Grnulos de Localizacin

Pueden afectar y mejorar: La presentacin de resultados La semntica de las preguntas La semntica de las preguntas El rendimiento del procesamiento de

preguntaspreguntasPresentacin

SemnticaSintaxis tipo SQL

Grnulos en las Proyecciones yde la Consulta (I)

Si se especifican grnulos en el SELECT, los grnulos recuperados se pueden representar de muchas manerasrepresentar de muchas maneras

Como hemos visto antes, (Egenhofer 1994) f ti b l i t i d l1994) ya enfatizaba la importancia de la variedad de representaciones

Grnulos en las Proyecciones yde la Consulta (II)SELECT gr(car, province)FROM carWHERE inside(10 miles car38 car)

Identificador del mapa de g n los

SELECT gr(car, province)FROM carWHERE inside(10 miles car38 car)WHERE inside(10 miles, car38, car) de grnulos

Radiol t

Objeto de f

Clase objetivoRestriccin dependiente de la localizacin (en el WHERE)

WHERE inside(10 miles, car38, car)

relevante referencia

Grnulos en las Proyecciones yde la Consulta (III)SELECT gr(person, subwayLine)FROM personWHERE person name = Little JohnWHERE person.name = Little John

Cambia a la lnea marrn

Grnulos en las Proyecciones yde la Consulta: Demo

Restricciones Inside

inside(r, obj, target)radiorelevante

objeto de referencia

clase objetivo(objetos objetivo)

Por defecto, las localizaciones de obj y de los objetos t t i t t GPSen target se interpretan como GPS

Sin embargo, es posible interpretarlas tambin en trminos de mapas de grnulos (map1 map2):trminos de mapas de grnulos (map1, map2): obj gr(map1, obj) target gr(map2, target)target gr(map2, target)

Restricciones Inside: GPSSELECT Car.idFROM CarWHERE inside(130 miles car38 Car)WHERE inside(130 miles, car38, Car)

El rea relevantees un crculoes un crculo

objeto de referencia (car38)objetos objetivo (instancias de Car)

Restricciones Inside: Grnulo para el Objeto de ReferenciaSELECT Car.idFROM CarWHERE inside(130 miles gr(province car38) Car)WHERE inside(130 miles, gr(province, car38), Car)

El rea relevanteNO es un crculoNO es un crculo


Restricciones Inside: Grnulo para los Objetos ObjetivoSELECT Car.idFROM CarWHERE inside(130 miles car38 gr(province Car))WHERE inside(130 miles, car38, gr(province, Car))


Restricciones Inside: Grnulos paraRestricciones Inside: Grnulos para Objetos de Referencia y ObjetivoSELECT Car.idFROM CarWHERE inside(130 miles gr(province car38) gr(province Car))

Podran ser dos mapas de grnulos

WHERE inside(130 miles, gr(province, car38), gr(province, Car))


Restricciones Inside: Demo

Restricciones Nearest

nearest(k, obj, target)nmero de objetos arecuperar (por defecto 1)

objeto de referencia

clase objetivo(objetos objetivo)

Por defecto, las localizaciones de obj y de los objetos t t i t t GPSen target se interpretan como GPS

Sin embargo, es posible interpretarlas tambin en trminos de mapas de grnulos (map1 map2):trminos de mapas de grnulos (map1, map2): obj gr(map1, obj) target gr(map2, target)target gr(map2, target)

Restricciones Nearest: GPSSELECT Car.idFROM CarWHERE nearest(2 car38 Car)WHERE nearest(2, car38, Car)

objeto de referencia (car38)objeto de referencia (car38)objetos objetivo (instancias de Car)objetos objetivo recuperados

Restricciones Nearest: Grnulo para el Objeto de ReferenciaSELECT Car.idFROM CarWHERE nearest(4 gr(province car38) Car)WHERE nearest(4, gr(province, car38), Car)

Distancia al grnulo distancia a sus lmites


Restricciones Nearest: Grnulo para el Objeto de ReferenciaSELECT Car.idFROM CarWHERE nearest(2 gr(province car38) Car)WHERE nearest(2, gr(province, car38), Car)



Restricciones Nearest: Grnulo para los Objetos ObjetivoSELECT Car.idFROM CarWHERE nearest(2 car38 gr(province Car))WHERE nearest(2, car38, gr(province, Car))



Restricciones Nearest: Grnulos paraRestricciones Nearest: Grnulos para Objetos de Referencia y ObjetivoSELECT Car.idFROM CarWHERE (2 ( i 38) ( i C ))

Podran ser dos mapas de grnulos

WHERE nearest(2, gr(province, car38), gr(province, Car))

Distancia entre grnulos distancia entre sus lmites


Restricciones Nearest: Demo

Incertidumbre en las Posiciones

Hasta ahora hemos asumido que el Servidor de Localizaciones es capaz de proporcionar posiciones GPS

Pero puede no ser el caso, p.ej. debido a: La imprecisin del mecanismo dep

posicionamiento (ej., cell-ID) Cuestiones de rendimiento en el proceso de p

tracking (ej., utilizar una poltica de actualizacin de posiciones conservadora)

La latencia de las comunicaciones Cuestiones de privacidad

Incertidumbre en las Posiciones: Demo

B d D t E i lBases de Datos Espaciales: Parte 2Parte 2

Arquitectura del SGBD: qArquitectura Integrada (I)

Los objetos geomtricos bsicos se representan por medio de objetos o tipos de datostipos de datos Es necesaria una implementacin eficiente

de sus operacionesde sus operaciones Algoritmos de Geometra Computacional

Arquitectura del SGBD: qArquitectura Integrada (II)

Y luego esos tipos de datos pueden ser atributos de relaciones. Ejemplo (como hemos visto antes):hemos visto antes): Ciudad(nombre: STRING, centro: POINT, ext:

REG, numHab: NUM), ) Ro(nombre: STRING, ruta: LINE) Estado(nombre: STRING, rea: REG, numHab:Estado(nombre: STRING, rea: REG, numHab:

NUM)

Arquitectura del SGBD: qArquitectura Integrada (III)

Si la extensin la implementa el usuario, en algunos casos puede ser complicado Por ejemplo, para representar una particin Cmo garantizamos

que las regiones son disjuntas?

Cmo representamoseficientemente las relaciones de adyacencia?

Cmo modelamos una red de carreteras? Interesa que haya cierto soporte

Arquitectura del SGBD: qArquitectura Integrada (IV)

Estructuras de indexacin espaciales Optimizador de consultas

Funciones de coste para operaciones Funciones de coste para operaciones espacialesE t d ti ti l l ti id d d Estadsticas para estimar la selectividad de las selecciones y joins espaciales

Utilizacin del algoritmo ms adecuado

Extensiones grficas del interfaz de Extensiones grficas del interfaz de usuario

Arquitectura del SGBD: qUsando un SGBD Cerrado (I)

En este caso es ms complicado Solucin 1: montar el sistema a partir

de relaciones normalesde relaciones normales Estado(idEstado: NUM, nombre: STRING,

H b NUM)numHab: NUM) Arista(idArista: NUM, idEstado: NUM clave

ajena de Estado, x1: NUM, y1: NUM, x2: NUM, y2: NUM)

Arquitectura del SGBD: qUsando un SGBD Cerrado (II)

Problemas de la solucin 1: Se viola el principio de independencia de los datos

Necesitamos conocer la estructura interna de los objetos para formular preguntaspara formular preguntas

Rendimiento bajo Se necesitan muchas tuplas para representar objetos Se necesitan muchas tuplas para representar objetos

geomtricos simples

Dificultad de definir nuevos tipos de datosp Imposibilidad de expresar clculos geomtricos

(point queries, window queries, tests de adyacencia, etc.)

Arquitectura del SGBD: qUsando un SGBD Cerrado (III)

Solucin 2: representar los objetos espaciales como secuencia de bytes y utilizar cdigo espacial aparte parautilizar cdigo espacial aparte para manejarlo

Capa de Integracin

SGBD E t d S b i t E i lSGBD Estndar Subsistema Espacial

Arquitectura del SGBD: qUsando un SGBD Cerrado (IV)

Con esta segunda solucin: Los atributos estndar los trata

directamente el SGBD Los atributos de estructuras espaciales los

considera el subsistema espacialconsidera el subsistema espacial Inconveniente: las consultas hay que

descomponerlas en dos partesdescomponerlas en dos partes Ventaja: flexibilidad para cambiar las

t t d d t i l t iestructuras de datos e implementaciones del subsistema espacial

Mtodos de Indexacin

Point Access Methods (PAMs) Permite indexar puntos en el espacio Ej.: grids

Spatial Access Methods (SAMs) Permite indexar regiones en el espaciog p Ej.: el R-tree Otra posible opcin para indexar regionesp p p g

Representarlas como puntos: (xmin, xmax, ymin, ymax) del MBR U PAM Usar un PAM

El procesamiento de las consultas puede ser ms difcil

PAMs: Problema a Resolver

Dado un conjunto de puntos y una consulta rectangular, obtener los puntos situados dentro del rectngulosituados dentro del rectngulo

Query

Adaptado de transparencias de George Kollios

GridCubetas / Bloques

de disco

Directorio Grid

Linear scale

YY

Linear scale X

Kd-tree

rbol binario donde cada nodo es un punto de k dimensiones

En cada nivel se usa una dimensin diferente

Puntos: (2,3), (5,4), (9,6), (4,7), (8,1), (7,2)Extrado de http://en.wikipedia.org/wiki/Kd-tree

Otros PAMs

Space Filling Curves (Hilbert curves) Transforma puntos de 2 dimensiones a 1

dimensin y luego utiliza un B+-tree para y g pindexar los puntos unidimensionales

KDB-tree KDB-tree LSD-tree

SAMs: Problema a Resolver

Dada una coleccin de objetos Dada una coleccin de objetos geomtricos (puntos, lneas, polgonos, t ) i l d f fi i tetc.), organizarlos de forma eficiente en

el disco para responder point queries range queriesrange queries k-nn queries spatial joins (all pairs queries) spatial joins ( all pairs queries)


R-Trees (I)

Nos permite indexar las coordenadas (X, Y) de datos geogrficos (regiones), aunque es multidimensional en generalaunque es multidimensional en general

Para resolver eficientemente consultas Obt l i 2 K como: Obtener los cines a 2 Km

Divide el espacio jerrquicamente en p j qMBRs (Minimum Bounding Rectangles)

Id d i i it t lIdea de aproximacin para evitar tener que cargar la geometra precisa del objeto ( falsos positivos):Filter step + refinement step

R-Trees (II) Cada nodo tiene un nmero variable de entradas

(entre un mnimo y un mximo) bloque(entre un mnimo y un mximo) bloque Todas las hojas estn al mismo nivel

E t d d i t di Entrada en un nodo intermedio: Referencia a un nodo hijo El MBR del espacio abarcado por todos los nodos hijos El MBR del espacio abarcado por todos los nodos hijos

Entrada en una hoja: Identificador del objeto espacial (o el objeto espacial Identificador del objeto espacial (o el objeto espacial

propiamente dicho) El MBR de dicho objeto

R-Trees (III)

Bsqueda (entrada query box): Usa los MBRs recursivamente para decidir si se

debe buscar o no dentro de un nodo hijoE d i ifi i h l i Es decir, verificar si hay solapamiento

Cada nodo padre cubre completamente a sus hijosEl MBR d bj t d d h j d t El MBR de un objeto de un nodo hoja puede estar cubierto por varios nodos, pero se almacena slo en unoen uno

Una bsqueda puede seguir mltiples ramas

R-Trees (IV)

Ejemplo

I

A C GH

I

B

E

F H

JD

E J


R-Trees (V)

Ejemplo (considerando un mximo de 4 entradas nodo)

IP1 P3

A C G

IComo se observa en la figura, los MBRs pueden solaparse

B F H

J H I JA B CD

E JP2

P4F GD E

H I JA B C


R-Trees (VI)

Ejemplo (considerando un mximo de 4 entradas nodo)

IP1 P3

A C G

IP1 P2 P3 P4

B F H

J H I JA B CD

E JP2

P4F GD E

H I JA B C


R-Trees (VII)

Bsqueda:

IP1 P3

A C G

IP1 P2 P3 P4

B F H

J H I JA B CD

E JP2

P4F GD E

H I JA B C


R-Trees (VIII)

Bsqueda:

IP1 P3

A C G

IP1 P2 P3 P4

B F H

J H I JA B CD

E JP2

P4F GD E

H I JA B C


R-Trees (IX)

Insercin (restriccin mnima cobertura): Se basa en los MBRs para asegurar que los

elementos cercanos se insertan en el mismo nodo hojahoja Escoger el MBR que tiene que crecer menos para

acomodar la insercin (en caso de empate, escoger el de ( p , gmenor rea)

Idea bsica: Minimizar el crecimiento de los MBRs agrupar rectngulos cercanosagrupar rectngulos cercanos

El procedimiento de insercin va descendiendo de forma recursivaforma recursiva

Si el nodo hoja ya est lleno, dividirlo

R-Trees (X)

Insertar X:

IP1 P3P1 P2 P3 P4

A CF

GH

P1 P2 P3 P4

B

E

F H

JP4 H I JA B CXD

EP2

P4F GD E X


R-Trees (XI)

Insertar Y:

IP1 P3P1 P2 P3 P4

A CF

GH

P1 P2 P3 P4

B

E

F H

JP4 H I JA B CYD

EP2

P4F GD E

Y


R-Trees (XII)

Insertar Y:

IP1 P3P1 P2 P3 P4

A CF

GH

P1 P2 P3 P4

B

E

F H

JP4 H I JA B CYD

EP2

P4F GD E

YY


R-Trees (XIII)

Eliminacin: Encontrar la hoja que contiene la entrada y

eliminar dicha entrada Si hay insuficiencia (underflow):

Eliminar el nodo hoja y la entrada del padre Eliminar el nodo hoja y la entrada del padre que lo apunta

Reinsertar las entradas eliminadas de la hoja Reinsertar las entradas eliminadas de la hoja utilizando el algoritmo de insercin

R-Trees (XIV)

Ventaja: El objeto espacial (o la clave) se almacena

en un nico nodo hojaj

Desventaja:D d l d l d Dado que las reas de los nodos intermedios pueden solaparse, puede ser

i i it i d b dpreciso visitar ms caminos de bsqueda que los estrictamente necesarios

R-Trees (XV)

Variantes: R+-tree R*-tree R tree Hilbert R-tree

R+-Tree

Similar al R-Tree, pero no hay solapamiento entre las reas de los nodos intermediosnodos intermedios Si es necesario para evitar el solapamiento,

un objeto podra almacenarse en ms deun objeto podra almacenarse en ms de una hoja

R*-Tree

Adems de minimizar el rea cubierta por cada nodo, hay otros criterios de optimizacin

posibles El R*-Tree trata de minimizar tanto la

cobertura como el solapamiento Cambiando los algoritmos de insercin y borrado

Soporte Espacial en SGBD p pComerciales (I) Oracle Locator 11g

Di ibl t d l di i d O l Disponible en todas las ediciones de Oracle Soporte para puntos, lneas y polgonos Indexacin de datos espaciales con R-Tree Indexacin de datos espaciales con R Tree Clculo de distancias, reas, longitud, buffering Transformacin de coordenadas Integracin con Oracle Application Server 11g MapViewer Soporte para

SQL/MM (ISO/IEC 13249) SQL/MM (ISO/IEC 13249) Open Geodata Interchange Standard (OGIS)

Soporte Espacial en SGBD p pComerciales (II)

Oracle Spatial 11g Opcin de Oracle Database 11g Enterprise Edition Gestin de datos espaciales avanzada

Ms de 400 funciones espaciales Agregados espaciales

Modelo de datos de red (conectividad clculo del camino Modelo de datos de red (conectividad, clculo del camino ms corto, vecinos ms cercanos, etc.)

Extiende las funcionalidades de Oracle Locator

Soporte Espacial en SGBD p pComerciales (III)

Informix Spatial DataBlade (mdulo) IBM DB2 Spatial Extender

PostGIS (para PostgreSQL cdigo PostGIS (para PostgreSQL, cdigo abierto)

MySQL Spatial Extensions ArcSDE ArcSDE Spatial Query Server (SQS, para Sybase) SQL Server 2008

Creciente Importancia de las pBases de Datos Espaciales (I)

Hay una necesidad creciente de integrar informacin espacial

Aparicin de distintos tipos de servicios: Aparicin de distintos tipos de servicios: Google Maps Yahoo! Maps Mapquestpq Google Earth

NASAs Earth Observation System (EOS) NASA s Earth Observation System (EOS) Varios terabytes de imgenes por da

Creciente Importancia de las pBases de Datos Espaciales (II)

Diversas aplicaciones: Planificacin de rutas Gestin de emergencias/desastres Gestin de emergencias/desastres Monitorizacin del crimen o del entorno

U b i Urbanismo

Bases de Datos Espaciales como backend para Geographic Informationbackend para Geographic InformationSystems (GIS)

B d D t T lBases de Datos Temporales

Motivacin

Las Bases de Datos tradicionales almacenan informacin del estado actualactual

Pero existen aplicaciones que requieren i f i d Ejinformacin pasada. Ej.: Aplicaciones mdicas (historial del

paciente) Evolucin de ventas de una empresap Historial de prstamos de una biblioteca

Introduccin (I)

Una Base de Datos Temporal es una base datos especializada en gestin de datos que cambian con el tiempo y quedatos que cambian con el tiempo y que permite guardar registro de su evolucinevolucin

Introduccin (II)

Una Base de Datos Temporal: Incorpora explcitamente la nocin del

tiempo, aadiendo marcas temporales:p , p A las tuplas, o a atributos u objetos a atributos u objetos

Mantiene informacin histricaNo slo los resultados de los cambios sino No slo los resultados de los cambios, sino tambin los propios cambios, se almacenan en la base de datos

Acceso eficiente a informacin pasada

Introduccin (III)

Por el contrario, una Base de Datos convencional (Snapshot Database): Mantiene slo el estado actual de los datos

Snapshot de los datos No hay informacin acerca del pasado

L t i h bi d t d Las transacciones hacen cambiar de un estado a otro, pero no se almacena informacin del propio cambiocambio

Guardar informacin histrica en una BD convencional resulta problemticoco e c o a esu ta p ob e t co Ej., repeticin de claves para intervalos distintos o

restricciones de integridad referencial temporales

Consideracin Explcita del pTiempo

Los modelos de datos temporales extienden el modelo relacional aadiendo atributos

temporales a las relaciones Han aparecido diversos lenguajes de

consultas temporales: TQUEL TSQL2

SQL3 SQL3 ATSQL

Tres Formas de Considerar el Tiempo

Transaction Time Tiempo de transaccin: cuando el hecho est

almacenado en la base de datos

Valid Time Tiempo vlido: cuando el hecho es verdad en el

mundo real Puede ser futuro; por ejemplo, la fecha de

d id d d t j t d ditcaducidad de una tarjeta de crdito

Bitemporal Cuando se considera tanto el tiempo de validez

como el tiempo de transaccin

Transaction Time: Rollback Databases

Cada registro tiene asociado un intervalo temporal: [t.start, t.end)

Cuando se inserta un registro en la BD en tiempo t0, dicho intervalo es: [t0, now)

Cuando se elimina un registro en tiempo t1,Cuando se elimina un registro en tiempo t1, su intervalo cambia de [t0, now) a: [t0, t1) No hay borrado fsico de la BD, slo borrado lgico No hay borrado fsico de la BD, slo borrado lgico Esto permite seguir la evolucin temporal de los

datos (ej., del salario de un empleado)( j , p )

No se puede/permite cambiar el pasado

Valid Time: Historic Databases

Cada registro tiene asociado un intervalo de validez

Se permite todo tipo de cambios (borrados, inserciones, modificaciones) en cualquier instante Se permiten borrados fsicos en la base de datos,

a diferencia de lo que sucede con las anteriores

Se puede preguntar por el futuro, pasado, o presente, en relacin con un cierto instante p ,de tiempo t

Transaction Time and Valid Time: Bitemporal Databases

Gestiona tanto el valid time como el transaction time Valid time: Dnde viva el empleado con Valid time: Dnde viva el empleado con

identificador idEmp25 en 1992?Transaction time: Qu informacin tena Transaction time: Qu informacin tena la BD en 1992 con respecto al lugar donde viva el empleado con identificadorviva el empleado con identificador idEmp25?

Tratamiento del Tiempo

Ejemplos de consultas: Timestamp queries: obtener todos los productos

que fabricaba la empresa en Mayo de 2009 Interval queries o period queries: obtener todos

los productos que fabricaba la empresa entre Mayo y Septiembre de 2009Mayo y Septiembre de 2009

S i t d d i d i Se precisan mtodos de indexacin adecuados (ej., Multiversion B-tree)

Soporte en SGBDs

1. TimeDB (http://www.timeconsult.com/Software/Software.html) No es realmente un SGBD temporal sino un

intrprete p Traduce sentencias temporales SQL (ATSQL)

en sentencias estndar SQLQ Las sentencias estndar SQL pueden luego

ejecutarse en un SGBD comercial (Oracle, Sybase, etc.)

2. Oracle 10g Workspace Managerg p g

Soporte en SGBDs: TimeDB p(I)

Creacin de una tabla bitemporal: CREATE TABLE Employees (EmpID INTEGER,

Name CHAR(30), Department CHAR(40), Salary INTEGER)INTEGER) AS VALIDTIME AND TRANSACTIONTIME;

Insercin de datos temporales: Insercin de datos temporales: VALIDTIME PERIOD '1985-1990'

INSERT INTO Employees VALUES (10 'John'INSERT INTO Employees VALUES (10, John , 'Research', 11000);

VALIDTIME PERIOD '1993-forever' VALIDTIME PERIOD 1993-forever INSERT INTO Employees VALUES (10, 'John', 'Sales', 12000);

Soporte en SGBDs: TimeDB p(II)

Consultas sobre los datos: VALIDTIME

SELECT * FROM Employees; TRANSACTIONTIME

SELECT * FROM Employees; VALIDTIME AND TRANSACTIONTIME

SELECT * FROM Employees;

Soporte en SGBDs: TimeDB p(III)

Restricciones temporales: CREATE TABLE Employees (EmpID INTEGER,

Name CHAR(30), Department CHAR(40) VALIDTIME REFERENCES Departments(department), Salary INTEGER) AS VALIDTIME AND TRANSACTIONTIME;VALIDTIME AND TRANSACTIONTIME;

Restriccin de integridad referencial temporal: expresamos la restriccin de que en los instantesexpresamos la restriccin de que en los instantes de tiempo en los que una persona era empleado su departamento tena que existir

B d D t E iBases de Datos Espacio-TemporalesTemporales

Introduccin

Son BD que gestionan datos espaciales cuya geometra (extensin y/o localizacin) vara con el tiempo. Ej.:localizacin) vara con el tiempo. Ej.: Un punto mvil

Una regin mvil y de forma cambiante Una regin mvil y de forma cambiante (ej., una tormenta)

Consultas Espacio-Temporales p p(I)

Consultas de rango espacio-temporal: Obtener todos los objetos que pasan por

un rea durante un cierto intervalo detiempo

Consultas NN: Consultas NN: Encontrar el objeto ms cercano a un

t d d d t i t i t l dpunto dado durante un cierto intervalo detiempo (o en un cierto instante de tiempo)

Consultas Espacio-Temporales p p(II)

Joins espacio-temporales: Obtener parejas de objetos cuyas

extensiones intersectan durante un ciertointervalo de tiempo

Obtener parejas de aviones a menos de Obtener parejas de aviones a menos de100 Km el uno del otro durante un ciertointervalo de tiempointervalo de tiempo

Consultas Espacio-Temporales p p(III)

Consultas de similaridad: Obtener objetos que siguieron una

trayectoria similar a la de uno dadoydurante un cierto intervalo de tiempo

Consultas de agregacin: Consultas de agregacin: Obtener cuntos coches pasaron por

i t t d l t i t d tcierto tramo de la autopista durante un cierto intervalo de tiempo

Indexacin (I)

Usando un R-Tree Asumir que el tiempo es otra dimensin 3D MBR 3D MBR Varios problemas, como por ejemplo:

Al i t d h ( l d Almacenamiento de ahora (usar un valor de tiempo grande)Los objetos de larga duracin tendrn MBRs Los objetos de larga duracin tendrn MBRsgrandes, difciles de agrupar

Slo funciona para cambios discretos Slo funciona para cambios discretos Mucho solapamiento y espacio desperdiciado

Indexacin (II)

Historical R-Trees (HR-Trees) Mantiene un R-Tree para cada instante R-Trees para instantes consecutivos R Trees para instantes consecutivos

pueden compartir ramas (ahorro espacio)Eficiente para consultas acerca de un cierto Eficiente para consultas acerca de un cierto instante de tiempoP Pero Consumo de espacio excesivo Las preguntas por un intervalo de tiempo son

poco eficientes

Indexacin (III)

Otras estructuras de indexacin: MVR-Tree (Multi-Version R Tree)

Objetivo: compartir nodos entre versionesObjetivo: compartir nodos entre versiones siempre que sea posible

Time-Parametrized R-Tree (TPR-Tree) Time Parametrized R Tree (TPR Tree) Almacena los MBRs como funciones del tiempo Los MBRs crecen con el tiempo Los MBRs crecen con el tiempo Se puede calcular los MBRs en un instante

futuroutu o

Comentarios Finales Las Bases de Datos de Objetos Mviles (introducidas

en el tema anterior) pueden considerarse un ejemploen el tema anterior) pueden considerarse un ejemplo de BD espacio-temporal Si se considera tambin el factor tiempo Si se considera tambin el factor tiempo Aunque habra que enfatizar los aspectos espaciales (manejo

de reas) Tipos de consultas: future queries, historic/past queries,

present queries Time Parameterized Queries (TP Queries) Time Parameterized Queries (TP Queries)

Devuelven el resultado actual, el periodo de validez y el cambio que causa la expiracin del resultado

B d D t D d tiBases de Datos Deductivas

Introduccin (I)

Tambin llamadas: Bases de Datos Logicas Lenguajes de Programacin de BD: BD + LP

Orientacin a Objetos: BD + OO = BDOOOrientacin a Objetos: BD + OO BDOO Programacin Lgica: BD + PL = BDD

U BD l i l l Una BD relacional almacena conocimiento explcito, las reglas deductivas representan conocimiento implcitop

Introduccin (II)

Aproximaciones: Extender un lenguaje de programacin

lgica (ej., Prolog) para que incluya g ( j , g) p q ycapacidades de BD (concurrencia, transacciones, etc.), )

Extender un SGBD convencional para que incluya capacidades deductivasincluya capacidades deductivas Incluir un operador de clausura transitiva

Disear un SGBD deductivo desde cero Disear un SGBD deductivo desde cero (Ej., Datalog)

Informacin en Una BD Deductiva

Base de datos extensional: hechos o aserciones

Base de datos intensional: reglas o Base de datos intensional: reglas o axiomas

Un sistema de inferencia es capaz de deducir informacin derivada de los hechos y reglasLas reglas se expresan en un lenguaje Las reglas se expresan en un lenguaje declarativo (Ej., Datalog)

Lenguaje de Preguntas (I)

Uso de la lgica como lenguaje de preguntas

Los predicados representan tuplas de Los predicados representan tuplas de relaciones:

l ( d d ) vuelo(1,Madrid,Pars,13:30,15:30).

Las reglas representan definiciones de g pvistas:

vuelo Mad tarde(N S L HS HL) : vuelo_Mad_tarde(N,S,L,HS,HL) :-vuelo(N,Madrid,L,HS,HL), HS > 14:00.

Lenguaje de Preguntas (II)

La conjuncin de predicados a demostrar seran las preguntas: :- vuelo(N,Madrid,L,HS,HL), HS > 14:00. : vuelo(N, Madrid ,L,HS,HL), HS > 14:00 .

Ventaja: la definicin de vistas es h t t l imucho ms potente en lgica ya que

puede utilizarse la recursin Se parece al lenguaje relacional QBE

(Query By Example)(Query By Example)

Ejemplos de Preguntas (I)

vuelo(idVuelo, ciudadSalida, ciudadLlegada, horaSalida, horaLlegada)

Seleccin: vuelo_mediodia(N,S,L,HS,HL):-

vuelo(N S L HS HL) HS>=12:00 HL= 12:00 ,HL

Ejemplos de Preguntas (II)

vuelo(idVuelo, ciudadSalida, ciudadLlegada, horaSalida, horaLlegada)

vueloreal(idVuelo, idAvion, fecha, precio)

Join: Join: vuelo_inf_completo(N,S,L,HS,HL,Fec,Av,Pr):-

vuelo(N S L HS HL) vueloreal(N Av Fec Pr)vuelo(N,S,L,HS,HL),vueloreal(N,Av,Fec,Pr)

Combinacin de operadores:l b (N) num_vuelo_barato(N) :-

vuelo(N,_,_,_,_),vueloreal(N,_,_,P),P

Ejemplos de Preguntas (III) vuelo(idVuelo, ciudadSalida, ciudadLlegada,

horaSalida horaLlegada)horaSalida, horaLlegada)

Preguntas recursivas: vuelo_compuesto(S,L):-vuelo(_,S,L,_,_). vuelo_compuesto(S,L):-

l ( S L1 ) l t (L1 L)vuelo(_S,L1,_,_),vuelo_compuesto(L1,L). Comprobar que no hay ciclos

ibl SQ 92 h b ibi No es posible en SQL92, habra que escribir un programa (SQL embebido o PL/SQL)

SQL99 incorpora recursividad (with recursive) SQL99 incorpora recursividad ( with recursive )

Soporte Actual

Las BD deductivas no han tenido xito hasta ahora fuera del mbito acadmico

Ejemplos: Ejemplos: Datalog Educational System (DES) h // fd / f /f /d /http://www.fdi.ucm.es/profesor/fernan/des/

ConceptBasehttp://www.dbis.rwth-aachen.de/CBdoc/

OtOtros

Bases de Datos Multimedia

Son bases de datos especializadas en la f gestin de informacin multimedia

(normalmente a nivel de investigacin): Vdeos Imgenes Audio Texto Objetos grficos Documentos multimedia

SQL/MM (SQL con extensiones multimedia)

Bases de Datos Multimedia: Ejemplo Vdeos (I)

Tcnicas de procesamiento para: Anlisis de vdeos (extraccin de caractersticas) Segmentacin de vdeos Reconocimiento de objetos Seguimiento de movimientos

Modelos de datos expresivosp Tcnicas de indexacin, bsqueda y

clasificacinclasificacin

Bases de Datos Multimedia: Ejemplo Vdeos (II)

Entorno de consultas adecuado Condiciones espacio-temporales Contenidos del vdeo Caractersticas del vdeo (colores, etc.)

Ejemplo (BilVideo):j p ( )select segmentfrom allfrom allwhere appear(o1).

Bases de Datos Multimedia: Ejemplo Vdeos (III)

Ejemplo (BilVideo):select count(segment), segment, Yfrom videoFragmentgwhere goalkeeper(X, liverpool) and

player(Y, manchester)p y ( , )and touch(Y, ball)meets not(touch(Z, ball))( ( , ))meets touch(X, ball).

Find the number of direct shots to the goalkeeperg pof Liverpool by each player of Manchester United in agiven video clip and return such video segments.

Bases de Datos Multimedia: Ejemplo Vdeos (IV)

Ejemplo (BilVideo):select count(segment)from 1where samelevel(ball, net) and

overlap(ball, net).p( , )

Find the number of goals of Liverpool scoredagainst Manchester United in a given video clip against Manchester United in a given video clip.

Bases de Datos en Memoria

Son BDs que residen en memoria en lugar de en disco

Por tanto son ms rpidas Por tanto, son ms rpidas Normalmente las transacciones carecen

de la propiedad de durabilidad Aunque puede proporcionarse usando q p p p

mecanismos tales como una RAM no voltil o mediante logging en un almacenamiento gg gestable

Sistemas de Gestin de Data Streams Data stream (flujo de datos) secuencia continua e

infinita de tuplas de datosinfinita de tuplas de datos Caractersticas especiales:

Alta tasa de llegada de tuplas Alta tasa de llegada de tuplas Datos altamente dinmicos Secuencia infinita no es posible esperar a tener todos los p p

datos para procesar una consulta (tratamiento especial de operadores bloqueantes), preguntas continuas, uso de ventanas deslizantesventanas deslizantes

Se precisan tcnicas alternativas a las BD tradicionales, gestin de datos en memoria, etc., g ,

Y An Hay Ms

Bases de Datos Probabilsticas Bases de Datos Documentales

Bases de Datos NoSQL (no relacionales Bases de Datos NoSQL (no relacionales, no propiedades ACID)

Bases de Datos Biolgicas Bases de Datos Cientficas Bases de Datos Cientficas Almacenes de Datos

Otras Tendencias en Bases de Datos: Parte...

Documents

Transcript of Otras Tendencias en Bases de Datos: Parte...