If you can't read please download the document
Upload
truongtram
View
227
Download
2
Embed Size (px)
Citation preview
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
objeto de referencia (car38)objetos objetivo (instancias de Car)
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))
objeto de referencia (car38)objetos objetivo (instancias de 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))
objeto de referencia (car38)objetos objetivo (instancias de 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
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(2 gr(province car38) Car)WHERE nearest(2, gr(province, car38), Car)
Distancia al grnulo distancia a sus lmites
objeto de referencia (car38)objeto de referencia (car38)objetos objetivo (instancias de Car)objetos objetivo recuperados
Restricciones Nearest: Grnulo para los Objetos ObjetivoSELECT Car.idFROM CarWHERE nearest(2 car38 gr(province Car))WHERE nearest(2, car38, gr(province, Car))
Distancia al grnulo distancia a sus lmites
objeto de referencia (car38)objeto de referencia (car38)objetos objetivo (instancias de Car)objetos objetivo recuperados
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
objeto de referencia (car38)objeto de referencia (car38)objetos objetivo (instancias de Car)objetos objetivo recuperados
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)
Adaptado de transparencias de George Kollios
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
Adaptado de transparencias de George Kollios
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
Adaptado de transparencias de George Kollios
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
Adaptado de transparencias de George Kollios
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
Adaptado de transparencias de George Kollios
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
Adaptado de transparencias de George Kollios
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
Adaptado de transparencias de George Kollios
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
Adaptado de transparencias de George Kollios
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
Adaptado de transparencias de George Kollios
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