Bases de Datos Restrictivas y Geometría Computacional

Jorge Ulises González Medina 2010

Bases de Datos Restrictivas y Geometría Computacional.

Introducción El presente trabajo está estructurado en dos partes principales, la primera de ellas es sobre bases de datos restrictivas y la segunda está enfocada a geometría computacional. Ahora abordaremos los puntos que se tratarán en la primer parte. La búsqueda de cómo almacenar y gestionar la información intensiva, representando los datos en forma de restricción, ha sido el impulso para la creación y el desarrollo de las bases de datos restrictivas, con el objetivo de buscar soluciones cada vez más expresivas y eficientes. Para su estudio exhaustivo se han creado varias de definiciones, junto a la formalización de términos que ayudan a entender mejor tanto sus posibilidades como sus limitaciones. La idea que dio origen al desarrollo de las bases de datos restrictivas surge de la necesidad de una nueva forma de almacenar datos que no toman valores únicos, sino que dependen de parámetros, variables, o vienen definidos por relaciones entre variables mediante ecuaciones o inecuaciones matemáticas. La representación de estos datos de manera extensiva podría crear bases de datos infinitas, por ejemplo al representar un espacio continuo, por lo que hay que buscar alternativas para almacenar los datos de forma intensiva. Una posibilidad es discretizar los datos, pero eso podría conllevar la creación de bases de datos mucho más grandes a la vez que pérdida de información. El crecimiento de las bases de datos también incluye en las operaciones de consulta y modificación, ya que tendrían que ser analizados y modificados muchos más registros que si la información estuviera almacenada de manera más compacta. Sin embargo, si se tuviera la capacidad de representar y almacenar dichas ecuaciones, inecuaciones e incluso combinaciones de ellas, la información sería completa y el espacio necesario para almacenarla muy pequeño debido a la compresión de la información. Las Bases de datos restrictivas abordan la solución de este problema tratando la información no de forma discreta, sino como un conjunto de restricciones sobre variables definidas sobre unos determinados dominios. En el presente trabajo buscamos dar un panorama general acerca de dos bases restrictivas (MLPQ/PReSTO y DISCO); todo esto con el objetivo de poder tener un acercamiento a la forma en que representan información, las estrategias que utilizan para poder extraerla y sobre todo pude establecer comparaciones entre bases de datos que poseen una extensión espacial (como lo es Oracle Spatial) y las bases de datos que utilizan una serie de restricciones para poder almacenar la información. Inicialmente daremos una revisión a los puntos cruciales que llevaron a dar origen a este tipo de bases de datos, los conceptos elementales que manejan y sobre todo la base lógica en la que se sustentan. Posteriormente haremos un recorrido entorno a las dos bases de datos planteadas anteriormente; en el caso de MLPQ/PReSTO describiremos de manera detallada el proceso que se lleva a cabo para poder crear una base de datos elemental, la forma en que debemos colocar los atributos, el formato debe tener nuestro archivo, cuál es el proceso que debemos de seguir para poder cargar nuestro archivo con restricciones, qué elementos conforman la pantalla principal del software que nos provee MLPQ/PReSTO, cómo es que llevamos a cabo consultas utilizando la herramienta especializada para esto, además

presentaremos un ejemplo mucho más complejo para poder entender con mayor claridad cómo es que se construyen las restricciones. Adicionalmente haremos uso de una aplicación que nos permitirá transformar archivos del tipo Shapefile al archivo que maneja MLPQ/PReSTO; todo esto con la finalidad de poder representar la información que utilizamos en el trabajo 2 de bases de datos espaciales, pero ahora representando la geometría de nuestros objetos a través de restricciones. En el caso de la base de datos DISCO, detallaremos los elementos principales que la conforman, el proceso que se lleva a cabo para poder crear una pequeña base de datos y con ello poder llevar a cabo ciertas consultas, describiremos el formato que debe cubrir nuestro archivo para que pueda ser cargado de manera satisfactoria y añadimos algunas cuestiones interesantes para el manejo de información de carácter espacial. El enfoque que daremos a la base de datos MLPQ/PReSTO serán mucho más práctico, mientras que el de DISCO estará encaminado describir y listar características y principios que maneja la propia base de datos. Con el presente trabajo buscamos dar un vistazo general al mundo de las bases de datos que utilizan restricciones, ya que éstas representan una alternativa a las bases de datos que habíamos venido manejando. El reto de este tipo de bases de datos no acaba en la simple necesidad de almacenar la información de forma intensiva, va más allá, ya que se necesita tratar esa información definiendo un lenguaje de consulta, y una metodología que ofrezca una manera eficiente de evaluar los datos. Como ya se había mencionado, la segunda parte de este trabajo está enfocada a la geometría computacional, en concreto se describirán detalladamente dos algoritmos; uno de ellos es el diagrama de Voronoi y el segundo es acerca de intersección entre polígonos y polilíneas. La geometría computacional ha sido siempre un área importante en ingeniería, al punto que ya en la década del ’50 existían sistemas rudimentarios de CAD (Computer Aided Design), a pesar de que el hardware de esa época era sumamente limitado. A finales de los ’70 y comienzos de los ’80 aparecen las work-stations, y fue alli cuando se desarrollaron la mayoría de los algoritmos geométricos que se utilizan hoy en día; sin embargo es con el advenimiento de las PC, los video-juegos, los efectos especiales y recientemente la realidad virtual, que las aplicaciones de computer graphics están alcanzando su máximo potencial. Una particularidad de los algoritmos de la geometría computacional es que por el hecho de requerir de operaciones con números reales, pueden dar un resultado equivocado. Si esto no se tiene en cuenta, los métodos pueden ser poco robustos (en general andan bien, pero en ciertos casos pueden no funcionar). De hecho el arte de la buena programación en esta área gira en torno a este concepto. Para poder describir los algoritmos, presentaremos imágenes, diagramas, pseudocódigo y sobre todo se darán los puntos fundamentales que conforman cada uno de ellos, adicionalmente se presentan algunas estrategias de carácter cognitivo, como los mapas mentales y cuadros resumen, para dar mayor claridad a los elementos que integran a los distintos algoritmos.

Parte I. Bases de datos restrictivas

Orígenes de las bases de datos restrictivas Las Bases de datos de restricciones o restrictivas (CDB, Constraint Databases) tuvieron su origen a principios de 1990 con el artículo de Kanellakis, Kuper y Revesz. Originalmente, el objetivo de las Bases de datos restrictivas fue definir una versión de bases de datos a la que se le añadió funcionalidad relacionada con la Programación Lógica con Restricciones (Constraint Logic Programming - CLP)1. La creación de este tipo de bases de datos fue una evolución natural de la investigación en el campo de la Programación con Restricciones, al igual que las Bases de Datos Deductivas2 y Datalog3 fueron el resultado de la combinación de las bases de datos y la Programación Lógica. Considerando las bases de datos relacionales una forma eficiente, compacta y transparente de representación de datos, se buscó combinar las ventajas del modelo relacional y la Programación Lógica con Restricciones. Las Bases de datos restrictivas se basaron en la equivalencia entre una tupla en una base de datos relacional y un conjunto de restricciones de igualdad o desigualdad sobre los atributos de dicha tupla. Debido a que las restricciones son un mecanismo natural de especificar las consultas de similitud en series de datos, muchas de las características del modelo relacional pueden extenderse al campo de la Programación con Restricciones. En sus inicios, las bases restrictivas se crearon para representar problemas donde se involucran datos espaciales, temporales o ambos a la vez, aunque su capacidad descriptiva y de inferencia puede ser extendida a cualquier dominio cuya información se pueda representar mediante restricciones. Al utilizar originalmente este dominio de aplicación, las propuestas se centraron en las restricciones lineales. Las restricciones lineales permiten describir problemas espacio-temporales de una forma aproximada, siendo más fáciles de evaluar las consultas a nivel de coste computacional que utilizando restricciones polinómicas. Sin embargo, las restricciones polinómicas son más genéricas, teniendo mayor capacidad expresiva.

Las bases de datos restrictivas fueron definidas en base a la lógica y modelo de primer orden4, tanto para la descripción de restricciones como para la evaluación de las consultas. Su fundamento se apoya en la dualidad de representar un conjunto de datos mediante una restricción (fórmula) sobre un conjunto de variables libres {x1; : : : ;xm}, o representarlos como un conjunto de tuplas formadas por atributos (a1; : : : ; an). Esto proporciona gran poder declarativo y

1 La Programación con restricciones es un paradigma de la programación en informática, donde las relaciones entre las variables son expresadas en términos de restricciones (ecuaciones). Actualmente es usada como una tecnología de software para la descripción y resolución de problemas combinatorios particularmente difíciles, especialmente en las áreas de planificación y programación de tareas (calendarización). 2 Un sistema de base de datos deductiva, es un sistema de base de datos pero con la diferencia de que permite hacer deducciones a través de inferencias. Se basa principalmente en reglas y hechos que son almacenados en la base de datos. Las bases de datos deductivas son también llamadas bases de datos lógicas, a raíz de que se basa en lógica matemática. 3 El lenguaje DATALOG se deriva de la lógica de primer orden. Es a la vez un lenguaje de descripción y de manipulación de bases de datos deductivas. El modelo de descripción de datos sostenido por DATALOG es esencialmente relacional, viéndose una relación como un predicado de la lógica. El lenguaje de manipulación es un lenguaje de reglas construido a partir de las cláusulas de Horn. El nombre Datalog significa “lógica para los datos”. Ha sido inventado para sugerir una versión de Prolog utilizable por los datos. 4 La lógica de primer orden, también llamada lógica de predicados o cálculo de predicados, es un sistema formal diseñado para estudiar la inferencia en los lenguajes de primer orden. Los lenguajes de primer orden son, a su vez, lenguajes con cuantificadores que alcanzan sólo a variables de individuo, y con funciones cuyos argumentos son sólo constantes o variables de individuo.

expresivo, como se muestra en la figura, donde se describe la equivalencia entre una restricción y su almacenamiento en una base de datos relacional, en este caso una restricción lineal de igualdad en el dominio de los naturales. Este es un caso donde se generaría una bases de datos relacional infinita si la información no se representara mediante restricciones.

MLPQ/PReSTO

Esta base de datos restrictiva presenta una combinación del sistema MLPQ (Management of Linear Programming Queries) y PReSTO (Parametric Rectangle Spatio Temporal Object), ambos desarrollados en la Universidad de Nebraska-Lincoln. El sistema MLPQ da soporte a la gestión de bases de datos con restricciones lineales. MLPQ fue esencialmente diseñada para el tratamiento de información espacial, gracias a un entorno gráfico que permite trabajar en 2 ó 3 dimensiones y a la interacción del usuario con el conocimiento almacenado mediante consultas. Por otra parte, PReSTO es un sistema de base de datos temporales, el cual permite consultas sobre sistemas que cambian en el tiempo.

A continuación se describirá como implementar una base de datos relacional (convencional) en MLPQ/PReSTO.

Dadas las siguientes tablas, se desean implementar en el entorno MLPQ/PReSTO; para ello tenemos la facilidad de crear el código en un archivo de texto plano y después cargarlo en el entorno correspondiente.

Pintor id_pintor nombre telefono

123 Ross 888-4567 126 Itero 345-1122 234 Picasso 456-3345 335 OKeefe 567-8999 456 Miro 777-7777

Obra de arte id_obra titulo precio id_pintor

2345 Wild Waters 245.00 126 4536 Sea Storm 8359.00 335 6666 Wild Waters 6799.00 234 7878 High Tide 98000.00 456 6789 Paradise 590000.00 234 7896 Faded Rose 145.00 123 9889 Sunset 975000.00 234

Galería id_obra propietario

2345 Johnson 6666 Johnson 4536 McCloud 7878 McCloud 6789 Palmer 7896 Palmer 9889 Palmer

Procedemos a abrir un editor de texto y en él tecleamos el código correspondiente a las tablas mostradas anteriormente.

begin %galeria% pintor(id_pintor, nombre, telefono) :- id_pintor=123, nombre="Rose", telefono="888-4567". pintor(id_pintor, nombre, telefono) :- id_pintor=126, nombre="Itero", telefono="345-1122". pintor(id_pintor, nombre, telefono) :- id_pintor=234, nombre="Picasso", telefono="456-3345". pintor(id_pintor, nombre, telefono) :- id_pintor=335, nombre="OKeefe", telefono="567-8999". pintor(id_pintor, nombre, telefono) :- id_pintor=456, nombre="Miro", telefono="777-7777". obra_de_arte(id_obra, titulo, precio, id_pintor) :- id_obra=2345, titulo="Wild Waters", precio=245, id_pintor=126. obra_de_arte(id_obra, titulo, precio, id_pintor) :- id_obra=4536, titulo="Sea Storm", precio=8359, id_pintor=335. obra_de_arte(id_obra, titulo, precio, id_pintor) :- id_obra=6666, titulo="Wild Waters", precio=6799, id_pintor=234. obra_de_arte(id_obra, titulo, precio, id_pintor) :- id_obra=7878, titulo="High Tid_pintore", precio=98000, id_pintor=456. obra_de_arte(id_obra, titulo, precio, id_pintor) :- id_obra=6789, titulo="Paradise", precio=590000, id_pintor=234. obra_de_arte(id_obra, titulo, precio, id_pintor) :- id_obra=7896, titulo="Faded Rose", precio=145, id_pintor=123. obra_de_arte(id_obra, titulo, precio, id_pintor) :- id_obra=9889, titulo="Sunset", precio=975000, id_pintor=234. galeria(id_obra, propietario) :- id_obra=2345, propietario="Johnson". galeria(id_obra, propietario) :- id_obra=6666, propietario="Johnson". galeria(id_obra, propietario) :- id_obra=4536, propietario="McCloud". galeria(id_obra, propietario) :- id_obra=7878, propietario="McCloud". galeria(id_obra, propietario) :- id_obra=6789, propietario="Palmer". galeria(id_obra, propietario) :- id_obra=7896, propietario="Palmer". galeria(id_obra, propietario) :- id_obra=9889, propietario="Palmer". end %galeria%

Es posible notar que la estructura general de un archivo que será leído por MLPQ/PReSTO, debe de poseer el siguiente formato:

begin %galeria% --------> aquí se coloca el contenido<--------- end %galeria% Lo que corresponde al contenido, debemos colocar línea a línea cada uno de los registros que conformarán las tablas de la base de datos; respetando el siguiente formato:

Nombre_de_la_tabla(nombre_atributo1, nombre_atributo2, …, nombre_atributoN) :- nombre_atributo1=valor_atributo1, nombre_atributo2=valor_atributo2,

… nombre_atributoN=valor_atributoN. Una vez que tenemos el archivo de texto plano con el contenido correspondiente, debemos cargarlo en el entorno de MLPQ/PReSTO, para ello debemos de abrir la aplicación correspondiente haciendo clic en el icono denominado “mlpq_nt”

Una vez que el software está abierto, observamos la pantalla principal.

El proceso que debemos de seguir para que nuestro archivo de texto plano se ha leído por MLPQ/PReSTO es el siguiente:

1. De antemano debemos conocer la ruta donde se ubica nuestro archivo de texto plano; en nuestro caso el archivo se llama “gallery” y se encuentra una carpeta denominada “ archivos mlpq”

2. Hacemos clic en el menú FILE y elegimos la opción de OPEN.

3. Buscamos nuestro archivo y una vez localizado lo seleccionamos y hacemos clic en el botón de ABRIR.

4. Posteriormente observamos que nuestro archivo está cargado, siempre y cuando sea sintácticamente correcto.

Del lado derecho en la pantalla observamos un sistema de referencia, el cual nos permitirá visualizar de manera fácil los datos de carácter espacial; en nuestro caso aún no tenemos datos de este tipo. Para poder observar los datos que conforman cada una de las tablas, hacemos clic derecho en alguna de ellas y se nos desplegará una pantalla con la información que tenemos almacenada en la tabla que elegimos.

Agregando restricciones

Las bases de datos restrictivas en MLPQ/PReSTO constan de un conjunto de reglas Datalog, donde el cuerpo está formado por restricciones lineales. Estas restricciones lineales tienen la forma:

a1x1 + a2x2 + … + anxn µ b donde ai , b son constantes, xi variables y µ es un operador de comparación de entre

{= < >}. La sintaxis del lenguaje de consulta de ambos sistemas (MLPQ y PReSTO) es muy similar a la de SQL, concretamente es un subconjunto de éste. En su lenguaje de consulta incorpora palabras reservadas de SQL como SELECT, WHERE, GROUP BY, HAVING, junto a funciones del tipo MIN y MAX. Un ejemplo de base de datos de MLPQ/PReSTO puede ser: Se requiere crear una base de datos restrictiva para almacenar información acerca de pastelerías y las localidades en donde éstas se ubican. Las características que la base de datos debe cumplir son:

Se desea almacenar un conjunto de localidades (localidad (id, x, y, t)) donde se tienen los puntos geográficos pertenecientes a cada localidad (x; y), el identificador único (id) y el año t al que corresponde dichas características; las localidades únicamente pertenecen al Distrito Federal.

La base de datos también almacena la ubicación de las pastelerías (pasteleria (p, x,y)), donde (x; y) representa su posición geográfica y “p” el identificador único asociado a cada una de ellas.

Junto a estas dos relaciones, localidad y pastelería, también se solicita almacenar información relativa a las ganancias (t, p, g) que representa la ganancia “g” de una determinada pastelería “p” en un instante de tiempo “t”.

Un ejemplo de la información puede ser: begin%ejemplo% localidad(id,x,y,t):- id = 1, x >= 0, x <= 4, y >=5 , y <= 15, t >=1800 , t <=1950. localidad(id,x,y,t):- id = 1, x >= 0, x <= 8, y >=5, y <=15, t >=1950 , t <= 2000. localidad(id,x,y,t):- id = 2, x >= 4, x <= 12, y >=5 , y <=15 , t >= 1800, t <=1950 . localidad(id,x,y,t):- id = 2, x >= 8, x <= 12, y >=5 , y <=15 , t >= 1950, t <= 2000. localidad(id,x,y,t):- id = 3, x >= 0, x <= 12, y >=0 , y <=5 , t >= 1800, t <= 2000. pasteleria(p,x,y):- x = 3, y = 2, c = 101. pasteleria(p,x,y):- x = 7, y = 3, c = 102. pasteleria(p,x,y):- x = 5, y = 6, c = 103. pasteleria(p,x,y):- x = 7, y = 10, c = 104. pasteleria(p,x,y):- x = 10, y = 8, c = 105. pasteleria(p,x,y):- x = 1, y = 7, c = 106. pasteleria(p,x,y):- x = -8, y = 6, c = 107. ganancias(t,p,g):::- c = 101, p = 15000 , t >=1800 , t <= 2000. ganancias(t,p,g):::- c = 102, p = 25700 , t >=1800 , t <= 2000. ganancias(t,p,g):::- c = 103, p = 36400 , t >=1800 , t <= 2000. ganancias(t,p,g):::- c = 104, p = 34100 , t >=1800 , t <= 2000. ganancias(t,p,g):::- c = 105, p = 50050 , t >=1800 , t <= 2000. ganancias(t,p,g):::- c = 106, p = 35540 , t >=1800 , t <= 2000. end%ejemplo%

A continuación se muestran las imágenes que corresponden a cada una de las localidades presentadas en el ejemplo.

localidad con id = 1

localidad con id = 2

localidad con id = 3

Una cuestión que es importante notar, es que la base de datos no sólo almacena información de carácter numérico y categórico; es decir, nombres, identificadores únicos, etc; sino también es capaz de manejar información de carácter temporal (como nuestro caso fueron años). Las imágenes presentadas anteriormente fueron obtenidas a través del entorno que nos proporciona MLPQ/PReSTO; simplemente haciendo una selección de aquellas localidades que tuvieran identificador único con valor 1, 2 o 3. Para poder realizar consultas, lo hacemos a través de una interfaz gráfica donde vamos colocando los datos que nos son solicitados, para poder acceder a este modulo, hacemos clic en el icono que se encuentra en la parte superior izquierda, tal como se muestra en la siguiente imagen.

Al dar clic en este botón se nos desplegará un menú donde debemos de elegir el tipo de consulta que queremos realizar.

La primera opción es la de “SQL BASIC”, donde podremos crear consultas sencillas, únicamente formadas por los atributos que deseamos seleccionar y las condiciones que queremos aplicar. Es importante notar que se nos solicita un “VIEW NAME”, éste será el nombre para nuestra consulta. Cada vez que nosotros generamos una consulta, ésta se almacena un archivo de texto plano en la misma ubicación donde se encuentra el archivo de la base de datos que estamos utilizando.

Si deseamos utilizar algunas cláusulas como “GROUP BY” y “HAVING”, debemos optar por la opción de “SQL AGGREGATION”.

Si en nuestra consulta nos topamos con la necesidad de utilizar subqueries, debemos elegir la opción de “NESTED SQL”; en este apartado tenemos un listbox con los operadores para la manipulación de las subconsultas.

Otra elección que podemos hacer es la de utilizar consultas con los operadores de “INTERSECT” y “UNION”; para ello debemos elegir el construir consultas con la interfaz denominada “SQL SETS”.

Cuando nuestra consulta implica el utilizar relacionar recursivas, tenemos la facilidad de construir ese tipo de queries a través de la pantalla “SQL RECURSIVE”

A manera de ejemplo se presentan los siguientes problemas, donde es necesario crear una consulta que los resuelva; para ello haremos uso de las tablas pintor, obra de arte y galería.

Se desea encontrar el nombre y número telefónico del pintor cuyo id es 456. Utilizaremos la opción de “BASIC SQL”, tecleando la información que se muestra en la figura.

Y obtenemos los siguientes resultados

Listar a todos los pintores con el total del costo de sus pinturas que se encuentran en venta en las distintas galerías.

En este caso optaremos por “SQL AGGREGATION”, colocando los datos correspondientes al query.

Una vez que ejecutamos la consulta, obtenemos los siguientes resultados.

Listar el nombre de todas las obras de arte que pertenezcan a “Picasso” o “Miro”. Para dar solución a esta consulta haremos uso de “SQL SETS”, colocando la información que compone la consulta tal y como se muestra imagen; es importante notar que estamos utilizando el operador UNION.

Una vez ejecutado el query, se nos muestra una pantalla con los resultados correspondientes.

Encontrar el nombre y el precio de la obra de arte más costosa. Para resolver esta consulta, haremos uso de subqueries; eligiendo la opción de “SQL NESTED”

Una vez a la consulta, obtenemos los siguientes resultados

Para poder mostrar un ejemplo más complejo, se creará el código correspondiente a la siguiente figura. Se utilizarán todas las restricciones que sean necesarias de tal manera que se genere un modelo lo más parecido al de la imagen.

Solución: begin%cara_personaje% sonrisa(i, x, y, t) :- i = 0, x > 100, x - y > -450, y < 650, x + y < 1250, x < 700, 2x - y - 2t < 1150, y > 0, 2x + y + 2t > 450, t >= 0, t <= 20. cara(i, x, y, t) :- i = 501, x > 200, y < 700, x < 600, y > 650, t >= 0, t <= 20. cabello(i, x, y, t) :- i = 502, 1.5x - y > -400, x < 200, x - y < -450, t >= 0, t <= 20.

cabello(i, x, y, t) :- i = 503, 1.5x + y < 1600, x > 600, x + y > 1250, t >= 0, t <= 20. oreja(i, x, y, t) :- i = 601, x > 50, y < 500, x < 100, 3x + y > 600, t >= 0, t <= 20. oreja(i, x, y, t) :- i = 602, y < 500, x < 750, 3x - y < 1800, x > 700, t >= 0, t <= 20. boca(i, x, y, t) :- i = 1, y > 90, x - y - 2t < 400, 0.5x - y - 0.5t > 120,

t >= 0, t <= 20. boca(i, x, y, t) :- i = 2, 0.5x - y - 0.5t < 120, y - 0.6t < 140, 0.5x + y + 0.5t > 280, y > 90, t >= 0, t <= 20. boca(i, x, y, t) :- i = 3, y > 90, x + y + 2t> 400, 0.5x + y + 0.5t < 280, t >= 0, t <= 20. ojo(i, x, y, t) :- i = 11, y + 0.8t < 450, x + y - 0.5t < 1050, x - y - 0.5t < 250, y - 0.8t > 350, x + y + 0.5t > 850, x - y + 0.5t > 50, t >= 0, t <= 20. ojo(i, x, y, t) :- i = 12, y + 0.8t < 450, x + y - 0.5t < 750, x - y - 0.5t < -50, y - 0.8t > 350, x + y + 0.5t > 550, x - y + 0.5t > -250, t >= 0, t <= 20. ceja(i, x, y, t) :- i = 701, x + 0.5t > 175, y + 0.5t < 500, x - 0.5t < 325, y > 475, t >= 0,

t <= 20. ceja(i, x, y, t) :- i = 702, x + 0.5t > 475, y + 0.5t < 500, x - 0.5t < 625, y > 475, t >= 0, t <= 20. nariz(i, x, y, t) :- i = 21, y > 200, 2x + y < 1160, 2x - y > 440, t >= 0, t <= 20. pupila(i, x, y, t) :- i = 101, x > 220, x - y > -190, y < 430, x + y < 690, x < 280, x - y < -110, y > 370, x + y > 610, t >= 0, t <= 20. pupila(i, x, y, t) :- i = 102, x > 520, x - y > 110, y < 430, x + y < 990, x < 580, x - y < 190, y > 370, x + y > 910, t >= 0, t <= 20. end%cara_personaje%

Aplicando MLPQ/PReSTO al trabajo 2 del curso de bases de datos espaciales 2010-1

Como ejemplo adicional utilizaremos MLPQ/PReSTO para manipular la información que se utilizó en el trabajo 2. Ya es sabido que uno de los aspectos que cubrió el anterior trabajo, fue generar los archivos”Shapefile”5, haciendo uso de ellos y utilizando la herramienta para poder convertir de Shapefile al formato que maneja MLPQ/PReSTO, representaremos la información pero utilizando restricciones. Inicialmente debemos localizar la aplicación que nos permite transformar de un formato a otro, hacemos clic en ella.

De entrada observamos la pantalla principal, la cual está compuesta por tres elementos principales: El área para localizar nuestro archivo con extensión.shp, la sección para poder determinar qué atributos queremos transformar al formato que maneja MLPQ/PReSTO y finalmente una sección para poder colocar características adicionales.

5 El formato ESRI Shapefile (SHP) es un formato de archivo informático propietario abierto de datos espaciales desarrollado por la compañía ESRI, quien crea y comercializa software para Sistemas de Información Geográfica como Arc/Info o ArcGIS. Originalmente se creó para la utilización con su producto ArcView GIS, pero actualmente se ha convertido en formato estándar de facto para el intercambio de información geográfica entre Sistemas de Información Geográfica por la importancia que los productos ESRI tienen en el mercado SIG y por estar muy bien documentado.

El proceso de transformación de un formato otro es muy sencillo, basta con localizar el archivo .shp, colocar en nombre del atributo que contienen la geometría, y seleccionar los atributos que queremos aparezcan en el código que se ha cargado en MLPQ/PReSTO. La siguiente imagen muestra el proceso para poder transformar el archivo .shp que contiene información acerca de las áreas deportivas; en este caso la tutor contiene la geometría de cada una de las áreas se denomina “geo”, y la tabla tiene dos atributos adicionales, el identificador para cada uno de los deportes y el hombre asociado a éstos. Basta con seleccionar dichos atributos y colocar los datos que nos requiere la aplicación y con ello hacer clic en el botón de “Create MLPQ file”.

En caso de que todo haya salido correcto, se nos muestra un mensaje que nos indica que la transformación se llevaba a cabo de manera satisfactoria.

Esta es una muestra del archivo generado; es posible observar que se han creado las restricciones tanto para X. como para Y; el archivo completo será enviado vía correo electrónico al profesor.

Una vez que tenemos nuestro archivo, podemos cargarlo en MLPQ/PReSTO, para ello debemos hacer clic en abrir archivo, localizando a éste.

Una vez que lo hemos cargado se muestran en la parte izquierda de la pantalla dos aspectos, uno es relativo a las características descriptivas de las colonias (identificador único y nombre) y el otro es texto está asociado con la geometría que cada una posee.

Si hacemos clic derecho en “geo”, podremos apreciar todas las restricciones que se tienen para poder representar la geometría de las colonias porque, en el caso de “colonia” observaremos datos de nombres, identificadores, etcétera.

Ahora es momento de realizar algunas consultas para poder recabar información en particular. En nuestro caso deseamos obtener la geometría de cada una de las colonias, para poder representarlas como se hizo en el trabajo 2; para ellos hemos clic en el botón denominado “SQL”.

Elegimos la opción de “SQL Basic”.

Y en la pantalla que se nos despliega, colocaremos la información correspondiente a la consulta; los aspectos a resaltar son: Toda consulta debe llevar un nombre, en nuestro caso denominaremos las consultas “ colonia_#”. Para poder asociar el identificador de las colonias y la geometría que éstas poseen hacemos uso de los identificadores, mismos que podemos encontrar si desplegamos la información como lo hemos hecho en pasos previos. Una parte que resulta crucial es el momento de extraer información de carácter geométrico, en este caso deseamos seleccionar todos los puntos tanto en coordenadas X, como en coordenadas Y que conforman a la colonia; para ello colocamos “geo.x” , “geo.y” en el área de SELECT; en la cláusula WHERE simplemente asociamos el identificador de la colonia con el identificador de sus restricciones e indicamos el identificador que tiene asociada la colonia que buscamos.

Debemos de realizar los pasos anteriormente descritos para poder extraer la geometría de cada una de las colonias; cada vez que nosotros creamos una consulta, en la parte izquierda de la pantalla se nos muestre nombre de esta crisis y hacemos clic en ella podemos observar en la parte derecha la imagen de la geometría correspondiente.

Una vez que tenemos todas las consultas necesarias, podemos observar cada una de las colonias que forman parte del área geográfica en cuestión.

El sistema DISCO DISCO es un sistema de base de datos restrictiva que pone en práctica Datalog6 con limitaciones booleanas sobre las variables, mismas que se extienden en los rangos finitos e infinitos de los números enteros.

En la primera sección se describe la sintaxis de consultas DISCO y se dan algunos ejemplos. Posteriormente describe la aplicación del sistema DISCO, incluida la conversión al álgebra relacional, y la evaluación sencilla y semi_sencilla. En penúltima sección se aborda el tema de cómo el sistema DISCO puede ser utilizado; y finalmente hablaremos sobre la extensión del sistema de Disco a otras álgebras de Boole.

Consultas DISCO El archivo de entrada comienza con una línea que contiene "Begin" y termina con una línea que contiene 'End.'. Entre estas líneas hay un conjunto de normas de Datalong y hechos con limitaciones Boolean tal como se hizo para la base de datos MLPQ/PReSTO.

El dominio de cada variable en DISCO es un elemento del álgebra de Boole BN en el que el elemento cero es el conjunto vacío, el único elemento es el conjunto de enteros, el operador ∧ se interpreta como una intersección de conjuntos, tal como se establece en la unión con el operador ∨ y en el complemento con el ‘operador’. El ≤ es el operador de precedencia, que se define como x ≤ y si y sólo si x ∧ y '= 0, también se permite en DISCO y se interpreta como la relación de igualdad en un subconjunto.

Conmutación de paquetes en una red.

6 Datalog (Database Logic) es un lenguaje lógico que es la forma más simple de lógica desarrollada para el modelo relacional. Datalog sin recursión tiene el mismo poder expresivo que el álgebra relacional.Datalog recursivo permite expresar consultas que no se pueden satisfacer en SQL2.Sin embargo, SQL:1999 ha usado la solución para la recursión en Datalog para el desarrollo de consultas recursivas. Datalog es similar a Prolog en su sintaxis, pero su semántica operacional es diferente.

Debido a que el teclado no contiene símbolos como , , y ≤ el sistema DISCO utiliza los símbolos / \ \ /, y <=. Además, DISCO utiliza @ para el elemento cero, y ! = para el símbolo de la desigualdad.

Ejemplo 1 Tomando en cuenta la conmutación de paquetes de red en la figura muestra de la página anterior, es posible salvar como en esta red jerárquica hay cuatro capas, cada una con cuatro nodos. Cada nodo representa un router y las líneas dirigidas representan las conexiones a través del cual los paquetes pueden ser enviados. Un conjunto de paquetes llegan a la capa superior y dinámicamente tiene que ser encaminado a los nodos de la capa inferior, con algunas restricciones en el envió de las capas medias. Las conexiones de la red implican algunas restricciones, que pueden ser representados por la relación de conexión:

/* las conexiones entre las capas 1 y 2 */ connect({1},A,B,C,D,E,F,G,H) :- E <= A, F <= A \/ B, G <= B \/ D, H <= C \/ D. /* las conexiones entre las capas 2 y 3 */ connect({2},E,F,G,H,I,J,K,L) :- I <= E, J <= E \/ H, K <= F, L <= G \/ H. /* las conexiones entre las capas 3 y 4 */ connect({3},I,J,K,L,M,N,O,P) :- M <= I, N <= J, O <= I \/ K, P <= L. Supongamos ahora que algunos paquetes se envían desde los nodos de la capa superior a los nodos de la capa inferior. Por ejemplo, podemos tener el siguiente conjunto de los paquetes a ser enviados desde y hacia:

(Desde)from(A,B,C,D) :- A == {1,2,3}, B == {4,5}, C == {6,7}, D == {8,9}. (Hacia)to(M,N,O,P) :- M == {1}, N == {2,6,8}, O == {3,4}, P == {5,7,9}. Para contar el número de capas en la red, se define la relación próxima con los siguientes hechos:

next({1},{2}). next({2},{3}). next({3},{4}). La consulta siguiente busca a dónde puede ser enviado cada paquete:

path({1},A,B,C,D) :- from(A,B,C,D).

path(Z,V,W,X,Y) :- path(Z1,Q,R,S,T), connect(Z1,Q,R,S,T,V,W,X,Y), next(Z1,Z).

Ejemplo 2

La siguiente consulta busca que los paquetes que se deben enviar a los nodos de cada capa. La consulta se define como el conjunto de los paquetes enviados a una capa tal que cada uno de los nodo recibe un subconjunto de paquetes que pueden ser enviados a la capa, con la restricción adicional de que cada paquete es enviado sólo a un nodo en cada capa, y, en particular, sólo los paquetes solicitados son para ser enviados a la capa inferior.

route({4},M,N,O,P) :- path({4},M,N,O,P), to(M,N,O,P). route(Z,Q,R,S,T) :- path(Z,Q,R,S,T), connect(Z,Q,R,S,T,V,W,X,Y), route(Z1,V,W,X,Y), next(Z,Z1), Q /\ R == @, Q /\ S == @, Q /\ T == @, R /\ S == @, R /\ T == @, S /\ T == @.

Ejemplo 3 Ahora supongamos que en lugar de la exigencia de que cada paquete se enviará a sólo un sucesor, tenemos la regla que cada paquete es difundido, es decir, es enviado a todos los sucesores. Entonces, las conexiones pueden ser representadas como sigue: /* conexiones de transmisión entre las capas 1 y 2 */ connect({1},A,B,C,D,E,F,G,H) :- A <= E, A <= F, B <= F, B <= G, C <= H, D <= G, D <= H. /* las conexiones entre las capas 2 y 3 */ connect({2},E,F,G,H,I,J,K,L) :- E <= I, E <= J, F <= K, G <= L, H <= J, H <= L. /* las conexiones entre las capas 3 y 4 */ connect({3},I,J,K,L,M,N,O,P) :- I <= M, I <= O, J <= N, K <= O, L <= P. Supongamos que sabemos que en la capa superior de algunos paquetes se produce tanto en el nodo de B y C:

from(A,B,C,D) :- B /\ C != @.

¿Qué puede decirse de los nodos de la capa inferior? La consulta DISCO es la misma para la ruta, por consiguiente se puede utilizar tal y como lo hicimos en el ejemplo 1

Implementación. Conversión Reglas Datalog a Fórmulas de Álgebra Relacional

Ahora nos abocaremos a convertir cada restricción de Datalog DISCO en una representación de álgebra relacional. En el interior del álgebra relacional se utilizan los siguientes operadores: join (), proyección (π), unión (∪), y seleccione (σ). En DISCO el producto-cruz normal (×) es el operador tratado como un caso especial de combinación. Además el join y la unión son operadores que pueden tener más de dos argumentos. Hay dos funciones ligeramente diferentes usadas para convertir reglas de Datalog a reglas de álgebra relacional:

Función EVAL - La conversión de Datalog al álgebra relacional es estándar,

a excepción de la sintaxis ligeramente diferente de las operaciones de selección. Básicamente, de cada cuerpo de la regla de Datalog se traduce como una expresión de álgebra relacional que es una combinación de las relaciones que ocurren en el cuerpo seguido de una secuencia de selecciones, una por cada restricción en el cuerpo, seguida de una proyección a las variables que se producen en la cabeza de la regla

Función EVAL_INCR - Esta función es similar a la función eval. La diferencia es que antes de cada

regla de conversión es copiado tantas veces como el número de símbolos de relación definida en su cuerpo. En el ith copian , símbolo que es puesto antes del ith la relación definida.

Ejemplo 4

La consulta en el ejemplo 1 se cambia por EVAL_INCR en:

path({1},A,B,C,D) :- from(A,B,C,D). path(Z,V,W,X,Y) :- path(Z1,Q,R,S,T),

connect(Z1,Q,R,S,T,V,W,X,Y), next(Z1,Z).

Luego esta se traduzca en fórmulas de álgebra relacional como sigue. La primera regla es traducida:

πZ,A,B,C,D (σZ={1} From(A, B,C, D) ⊲⊳ Z(Z)

Donde Z (Z) es la relación que contiene sólo la variable Z sola sin ninguna restricción. La segunda regla es traducida:

πZ,V,W,X,Y (Path (Z1, Q, R, S, T ) ⊲⊳ Connect (Z1, Q, R, S, T, V,W, X, Y)

⊲⊳ Next (Z1, Z)) La unión de las dos primeras expresiones será una expresión de álgebra relacional para el camino.

Métodos de Evaluación sencillos y semi_sencillos

DISCO utiliza los métodos de evaluación sencillos y semi-sensillo para las consultas. El método sencillo en repetidas ocasiones evalúa las fórmulas de álgebra relacional que son obtenidos usando la función EVAL hasta que el tamaño de las relaciones de salida siga creciendo. El pseudo-código del método sencillo es el siguiente:

Metodo Sencillo for := 1 to m do

Pi := ∅ repeat for i:= 1 to m do

Qi := Pi for i:= 1 to m do

Pi := EVAL(i,Q1, ..., Qm) until Pi = Qi for all i ( 1 ≤ i ≤ m)

Donde Pi es la tupla de la relación de ith y Qi es la tupla de la relación de ith en el paso anterior. Al principio, borrar todas las tuplas. Luego, repita los pasos del algoritmo hasta que los resultados de los dos últimos pasos sean idénticos. Durante un paso almacenamos las tuplas primero (Qi: = Pi), a continuación, calcular las tuplas nuevas utilizando las tuplas calculadas en los pasos anteriores. El cálculo se realiza por la función EVAL. En la función, denoto el índice de la relación actual y Q1,. . . Qm, Denotan las tuplas de las relaciones, que puede ser utilizado por EVAL.

Método Semi_Sencillo

La principal desventaja del método sencillo es que esto vuelve a calcular las mismas tuplas en cada iteración. En el ejemplo anterior, durante el primer paso del algoritmo, cálculo a los padres, durante la segunda fase, pasan los padres y los abuelos, durante los pasos tres y cuarto pasan los padres, abuelos y bisabuelos.

Por lo tanto, el algoritmo calcula los padres cuatro veces. Si el número de los pasos es mayor, y en una aplicación real es varias veces mayor, entonces esta desventaja es también mayor. La idea principal del método semi-sencillo es omitir estos nuevos cálculos.

Si durante el cálculo sólo usamos tuplas de edad (tuplas que se calcularon antes de la etapa anterior), entonces sólo volver a calcular algunas tuplas mayores. Por lo tanto, si queremos calcular nuevas tuplas debemos utilizar al menos una nueva tupla que se ha calculado en el paso anterior.

Naturalmente, el primer paso es una excepción, porque no hay nuevas tuplas antes del primer paso, por lo tanto, los primeros pasos de los métodos semi-sencillos y sencillos son iguales.

El pseudo-código de evaluación semi-sencillo es la siguiente:

Donde Pi denota las tuplas de la relación de ith, Pi de la tuplas nuevas en la actual relación, y Qi las nuevas tuplas en la iteración anterior de las relaciones. En la la primera iteración se utiliza la función EVAL para calcular las tuplas. Luego de la iteración del algoritmo hasta que no haya nuevas tuplas derivadas. En cada iteración primero almacena las nueva tuplas (Qi = Pi) y luego calcular las tuplas nuevas con la función EVAL_ INCR. Después comprobamos, si las tuplas nuevas son realmente nuevas (Pi = Pi-Pi). Al final de la iteración se debe actualizar el valor de pi (pi = Pi + Pi). La función EVAL_ INCR tiene más parámetros que la función EVAL, ya que la función EVAL_ INCR no sólo necesita de todas las tuplas, pero también de las nuevas tuplas

Ejemplo 5

Vamos a ver cómo el ejemplo 4 se evaluará por medio de DISCO. En la primera iteración de la expresión de la primera regla del álgebra, es la única que le dará una tupla:

path({1},A,B,C,D) :- A == {1,2,3}, B == {4,5}, C == {6,7}, D == {8,9}.

En la segunda iteración, la expresión de la segunda regla del álgebra nos dará la tupla, donde usamos algunos cambios de nombre de una legibilidad mayor:

/* E,F,G,H are renamings for V,W,X,Y */ path({2},E,F,G,H) :- E <= {1,2,3},

F <= {1,2,3,4,5}, G <= {4,5,8,9}, H <= {6,7,8,9}.

Del mismo modo, en las iteraciones tercera y cuarta, se obtiene:

/* I, J, K, L son cambios de nombre para V, W, X, Y */ path({3},I,J,K,L) :- I <= {1,2,3},

J <= {1,2,3,6,7,8,9}, K <= {1,2,3,4,5}, L <= {4,5,6,7,8,9}.

/* M, N, O, P son cambios de nombre para V, W, X, Y */ path({4},M,N,O,P) :- M <= {1,2,3},

N <= {1,2,3,6,7,8,9}, O <= {1,2,3,4,5}, P <= {4,5,6,7,8,9}.

Para bases de datos restrictivos y consultas que contienen sólo subconjunto o igual a restricciones de desigualdad monótona, DISCO implementa el operador de proyección basada en parte del método de eliminación del cuantificador existencial.

Ejemplo 6

Es fácil comprobar que la base de datos de restrictivas en el ejemplo 3 contiene sólo la orden y las restricciones de desigualdad monótona. Cuando la misma consulta de la ruta que en el ejemplo 1 se ejecuta en esta base de datos de entrada, DISCO encuentra las siguientes tuplas:

path({1},A,B,C,D) :- B /\ C != @.

/* E,F,G,H son cambios de nombre para V,W,X,Y */ path({2},E,F,G,H) :- F /\ G != @,

F /\ H != @, G /\ H != @.

/* I,J,K,L son cambios de nombre para V,W,X,Y */ path({3},I,J,K,L) :- J /\ K != @,

J /\ L != @, K /\ L != @.

/* M,N,O,P son cambios de nombre para V,W,X,Y */ path({4},M,N,O,P) :- N /\ O != @,

N /\ P != @, O /\ P != @.

Esta es una respuesta correcta, porque estas son las únicas conclusiones que se pueden extraerse del hecho de que la entrada de B / \ C ! = @ porque O y P son accesibles de B, N y P son accesibles desde C, y por lo que sabemos de los otros nodos en la capa superior puede estar vacío.

Método Interactivo Semi-sencillo

El método interactivo de evaluación semi-sencillo es como el método evaluación semi-sencillo, salvo que después de cada iteración, el usuario puede investigar las nuevas tuplas y decidir si necesario añadirlos a la base de datos de restrictiva. El siguiente es un ejemplo de la evaluación interactiva semi-sencillo.

Ejemplo 7

Tenga en cuenta la evaluación de la relación de la ruta en el ejemplo 2 después de la relación de ruta del ejemplo 1 se calcula y se agrega a la base de datos restrictiva. En el modo interactivo de la primera iteración daría:

> route({4},M,N,O,P) :- M == {1}, N == {2,6,8}, O == {3,4}, P == {5,7,9}.

> accept tuple (Y/N)? Supongamos que la tupla es aceptada. Entonces, la siguiente iteración dará (en este caso las variables Q, R, S, T significa (destinan) I, J, K, L):

> route({3},Q,R,S,T) :- {1} <= Q, Q <= {1,3}, {2,6,8} <= R, R <= {2,3,6,8}, {4} <= S, S <= {3,4}, T == {5,7,9}, Q /\ R = @, Q /\ S = @, R /\ S = @.

Esta tupla demuestra que mientras la mayor parte de los paquetes tienen un lugar decidido, los 3 paquetes pueden ser enviados a tres lugares diferentes. Supongamos que el usuario decida enviar el paquete 3 por entrada:

> accept tuple (Y/N)? N > replace tuple (Y/N)? Y > replace tuple with: route({3},Q,R,S,T) :- Q == {1,3},

R == {2,6,8}, S == {4}, T == {5,7,9}.

Ahora, la evaluación interactiva sigue, y la tupla siguiente (donde las variables Q, R, S, T significa E, F, G, H) se devuelve:

> route({2},Q,R,S,T) :- Q == {1,2,3}, R == {3,4}, {5} <= S, S <= {5,9}, {6,7,8} <= T, T <= {6,7,8,9}, S /\ T = @.

Por último, la cuarta iteración devolverá la tupla final, donde las variables Q, R, S, T A, significa B, C, D, se acepta que:

> route({1},Q,R,S,T) :- Q == {1,2,3}, R == {4,5}, S == {6,7}, T == {8,9}.

> accept tuple (Y/N)? Y La relación de ruta calculada con la evaluación interactiva semi-sencilla, muestra que los paquetes se deben enviar a cual nodo en cada capa.

Aunque no se aplica en DISCO, observamos que el método de evaluación interactivo puede ser sustituido por un método donde las decisiones son tomadas por algún programa. Por ejemplo, un programa en C pueden interactuar con el sistema de DISCO y siempre hacen las siguientes opciones para cada ruta (Z, Q, R, S, T) tupla:

Z = Z Q = Qmax R = Rmax − Qmax S = Smax − Qmax − Rmax T = Tmax − Qmax − Rmax – Smax Donde los subíndices min y max denotan los límites inferior y superior de la variable.

Uso del Sistema de DISCO

El sistema DISCO ha sido implementado en el lenguaje de programación Java. Por lo tanto, se puede ejecutar tanto en Windows y UNIX. El programa se inicia escribiendo el nombre de archivo de DISCO ejecutable en el sistema operativo del sistema. Después de iniciar el programa un nuevo sistema aparecerá y el sistema espera un comando de usuario.

Después de que el usuario entra en el comando, el sistema espera el siguiente comando. Este proceso se termina si el usuario sale del sistema.

Los comandos más importantes proporcionados en el sistema DISCO son los siguientes:

consult ‘filename’— Este comando carga un nombre de archivo "el archivo de entrada" que debería estar en el formato descrito al inicio.

display [‘R’] [onto ‘filename’] — Cuando una relación llamada "R" se da imprime DISCO fuera de las normas de la relación. Si no se da "R", entonces imprime DISCO fuera de los nombres y arities de todas las relaciones. Si se especifica un nombre de archivo, entonces la fórmula se imprimirán en el archivo, de lo contrario, se imprimirán en la pantalla.

displaydf [onto ’filename’]— Este comando imprime hacia fuera todos los hechos derivados en la base de datos a la pantalla o el archivo especificado.

memory— Este comando muestra el total de memoria libre y utilizada por el sistema. clear— Este comando borra todas las relaciones y las reglas de la base de datos. R(E1, . . . , En)?— En este comando cada Ei puede ser una variable o un conjunto de constantes. bye— Este comando cierra el programa.

El sistema DISCO también proporciona varios interruptores que controlan la evaluación del sistema. Estos interruptores on-off incluyen el tiempo, para mostrar el tiempo utilizado durante la evaluación; seguimiento, para mostrar la representación interna de las normas; optimizar, las rutinas a utilizar de optimización de álgebra relacional; semi-sencilla, a uso semi-sencilla en lugar de la evaluación sencilla; e interactivo, para la utilización evaluación interactiva semi- sencilla.

Para configurar un conmutador, uno tiene que escribir cualquiera de los nombres de interruptor en el modo de comando switchname o switchname apagado. El valor predeterminado de tiempo, el rastro, e interactivo es desactivado y para optimizar y en el semi-sencillo está encendido.

Extensibilidad del sistema DISCO

Aunque el sistema DISCO implementa el álgebra de Boole específica, es decir, el álgebra de Boole de conjuntos de números enteros, es posible extender el sistema para tratar con otras álgebras de Boole. La aplicación de nuevas álgebras de Boole nos permite expresar muchas consultas más interesantes.

En el amino nuevo a un álgebra de Boole, tenemos que reemplazar sólo algunas de las rutinas básicas de DISCO. En primer lugar, es necesario redefinir los operadores ∧, ∨, y '. También tenemos que cambiar algunas de las estructuras de almacenamiento de datos y modificar los métodos de evaluación sencillos y semi-sencillos con una nueva prueba de la subsunción. Algunos de estos requieren cierto trabajo, pero, en principio, gran parte del software escrito para el sistema DISCO podrían ser reutilizados.

Resultados experimentales

A continuación se presentan los tiempos de duración de la trayectoria de consulta en el ejemplo 1, la trayectoria de consulta en el ejemplo 2, y la trayectoria nueva de la consulta en el ejemplo 3 con las conexiones de red de transmisión.

Problema Sencillo Semi-Sencillo

Sin la optimización

Con optimización

Sin la optimización

Con optimización

Trayectoria 3.746 1.472 2.383 1.261

Difusión 1.392 0.921 1.131 0.921

Ruta 35.872 17.966 40.819 18.036

Parte II. Algoritmos de geometría computacional

El término Geometría Computacional alberga el estudio sistemático de algoritmos geométricos de muy diversos tipos y con muy diversos campos de aplicación; guarda una intensa relación con la Matemática discreta, con el Análisis Combinatorio, con el Diseño de Algoritmos y Estructuras de Datos, con la Técnica Aplicada en Robótica, CAD, SIG (Sistemas de Información Geográfica) y muchos otros campos.

Diagramas de Voronoi

Intuitivamente, dado un conjunto de puntos, se trata de asociar el lugar de los puntos del espacio más cercano a cada uno de ellos. El concepto de diagrama de Voronoi surge en el siglo XVII, y fue estudiado por Descartes (1644). No es hasta 1908 que se le empieza a conocer por su nombre.

Aplicaciones

Cristalografía (interpolación del espacio). Estudios de mercado (distribución de comercios). Sociología. Cartografía. Antropología. Arqueología. Biología. Ecología. Estudios forestales (control de incendios). Geografía. Meteorología. Física. Fisiología. Planificación urbana y regional, etc..

Concepto Un diagrama de Voronoi puede considerarse como el resultado de asociar a todas las localizaciones del espacio euclídeo con su miembro más próximo del conjunto de puntos según la distancia euclídea. Polígono de Voronoi: conjunto cerrado cuya frontera son segmentos, semirrectas o líneas infinitas (ejes de Voronoi). Si dos polígonos comparten algún eje se dice que son adyacentes. Dado un conjunto de n puntos en el plano, el polígono o región de Voronoi V(pi) para el punto pi se define como V(pi) = { x : |pi – x| ≤ |pj – x|, ∀j≠i }

El diagrama de Voronoi lo constituye el conjunto de todas esas regiones, V = { V(p1), V(p2), ..., V(pn) }

Elementos de un diagrama de Voronoi

Los conceptos anteriores pueden extenderse a 3 dimensiones.

Propiedades

1. Todas las regiones de Voronoi son convexas o infinitas. 2. La unión de todas las regiones de Voronoi es el plano. 3. Un polígono de Voronoi es infinito si su generador pertenece a la envolvente convexa. 4. Para cualquier punto del plano, el punto generador más cercano es aquél que forma la región polar

donde dicho punto se encuentra. 5. Si se toma como centro de un círculo cualquier punto del plano y se traza una circunferencia que

pase por un solo punto generador, dicho punto es interior a una región de Voronoi. Si toca exactamente a dos puntos generadores, separa exactamente a dos regiones de Voronoi, es decir, ese punto es parte de un eje de Voronoi. Si se puede dibujar una circunferencia que toque a tres más puntos generadores, es un vértice de Voronoi, esto es, la intersección de dos ejes de Voronoi.

6. Para cada vértice de Voronoi, existe un único círculo centrado en dicho vértice y que pasa por tres generadores (o más en el caso de que existan degeneraciones) y dicho círculo es el mayor de todos los círculos que puede construirse sin que contenga dentro a otro generador distinto del tomado como centro del círculo.

(Si el vértice v es un vértice de Voronoi, p4 no puede estar ahí)

7. El número de vértices de un diagrama de Voronoi en el plano cumple que nv – ne + n = 1 (el

número de vértices menos el número de ejes más el total de generadores es igual a uno).

8. El número de ejes es igual a 3n – 6, para n generadores. 9. El número de vértices es igual a 2n – 4, para n generadores.

Triangulación de Delaunay

Es una teselación7 del plano dual al diagrama de Voronoi.

Se puede construir la triangulación de Delaunay a partir del diagrama de Voronoi. Basta con unir todos aquellos generadores que compartan un ejede Voronoi.

Si el diagrama de Voronoi es degenerado, el paso anterior no devuelve una triangulación, sino una pretriangulación de Delaunay, aunque es un polígono inmediato de triangular.

Triangulación de Delaunay – Definición

Una triangulación de Delaunay es un grafo dual al diagrama de Voronoi uniendo dos puntos generadores que comparten un eje de Voronoi; también uniendo aquellos puntos vecinos en regiones de Voronoi abiertas. Los casos degenerados los encontramos cuando tenemos cuatro puntos alineados. En vez de obtener un triángulo se consigue un cuadrado, fácilmente triangulable. Los ejes de Delaunay son los segmentos que definen los triángulos.

Triangulación de Delaunay – Propiedades

1. Cada triángulo de Delaunay posee como vértices a los generadores del diagrama de Voronoi. 2. La frontera de la triangulación de Delaunay es la envolvente convexa de los puntos. 3. El interior de cada triángulo no posee generadores. Una triangulación es de Delaunay si y sólo si

todos los círculos que pasen por tres vértices de un triángulo de Delaunay son vacíos. 4. Una triangulación de Delaunay es aquella que maximiza el mínimo ángulo, lo cual le hace ser la

mejor triangulación porque genera los triángulos más equiláteros posibles. 5. Una triangulación de Delaunay es única si no existen casos degenerados.

Métodos de construcción del diagrama de Voronoi

Método incremental

Es simple y su orden de ejecución puede reducirse a O(n) mediante técnicas algorítmicas. Se parte de un diagrama con 3 generadores y se van añadiendo puntos.

7 Una teselación es una regularidad o patrón de figuras que cubre o pavimenta completamente una superficie plana que cumple con dos requisitos: 1. que no queden huecos 2. que no se superpongan las figuras Las teselaciones se crean usando transformaciones isométricas sobre una figura inicial. Distintas culturas en el tiempo han utilizado esta técnica para formar pavimentos o muros de mosaicos en catedrales y palacios.

Se añade p, y se detecta que se encuentra en la región generada por q. Se calcula el bisector entre ambos puntos, que corta en w1 y w2 a la región de q. Dichos puntos serán el origen para seguir construyendo bisectores entre q y el resto de sus nuevos

vecinos, hasta completar la nueva región de Voronoi de q. Para hacer eficiente el algoritmo, la estructura de datos usada debe contener información sobre las

regiones adyacentes, de manera que, una vez localizado q y construido el bisector, se pueda pasar a la región contigua en tiempo constante.

El método tiene un orden de ejecución O(n·logn). Método Divide y Vencerás

No es tan eficiente como el anterior, pero garantiza trabajar en tiempo O(n·logn) en el peor de los casos.

Para que la unión de dos diagramas polares en uno sea posible, necesitamos encontrar una cadena divisoria capaz de mezclar dichos diagramas.

La construcción de la cadena divisoria comienza de abajo hacia arriba. Problema: conocer cuál de los dos generadores iniciales participa en la creación de la envolvente

convexa.

Método Divide y Vencerás. Algoritmo: Entrada : Una lista P con los n generadores en orden creciente de abscisa Salida : El diagrama de Voronoi correspondiente

1. Inicio 2. SI n ≤ 3 3. ENTONCES construir el diagrama de Voronoi directamente 4. SINO hacer 5. Sea t la parte entera de n/2 y dividir P en Pi y Pd ( parte izda y decha, respectivamente ) 6. Construir el diagrama de Voronoi para Pi 7. Construir el diagrama de Voronoi para Pd 8. Mezclar los dos diagramas anteriores obteniendo el diagrama de Voronoi de P 9. Fin

El paso realmente importante es el de mezclar eficientemente dos diagramas de Voronoi. La cadena divisoria es una polilínea que se construye de abajo hacia arriba, siempre como bisector de dos puntos, uno en el diagrama izquierdo y otro en el derecho.

Mezclar Envolventes. Algoritmo: Entrada : Los diagramas de Voronoi de Pi y Pd

Salida : El diagrama de Voronoi para P 1. INICIO 2. Construir la envolvente convexa para Pi y Pd 3. Encontrar la tangente menor común a Pi y Pd que toca a ambos en los puntos ti y td

respectivamente 4. Sea w[ 0 ] un punto del infinito y que se une al bisector por ti y td 5. MIENTRAS no se alcanza la tangente mayor entre Pi y Pd 6. i ← i + 1 7. Encontrar a ai, punto de corte del bisector con Pi, sea ri la region que alcanza 8. Encontrar al punto ad que corta el bisector con Pd, sea rd la region que alcanza 9. SI ai tiene menor ordenada que ad 10. ENTONCES w[ i ] ← ai 11. SINO w[ i ] ← ad 12. FIN_SI 13. Calcular el bisector entre ri y rd 14. FIN_MIENTRAS 15. Añadir la nueva línea poligonal eliminando todos los ejes de Pi que queden a la derecha de ésta y 16. todos los de Pd que queden a la izquierda. 17. FIN

Problemas que resuelven el diagrama de Voronoi

Problemas de proximidad.

Dado un conjunto P de n puntos en el plano, para cada punto pi, ¿cuál es el lugar geométrico de los puntos (x, y) en el plano más cercanos a pi que a ningún otro punto de P?

Cada pi genera una región de Voronoi que da respuesta a la pregunta (p.e., localizar la oficina de correos más próxima a cualquier punto donde nos encontremos).

El vecino más cercano.

El diagrama de Voronoi evita hacer búsquedas exhaustivas con coste lineal: Una región de Voronoi suele tener un número inferior o igual a 6 vecinos ⇒ Inmediato.

Extensión: Vecino más cercano para cada pi ∈ P. Dado que el diagrama de Voronoi se calcula en tiempo O(n·logn), se amplía en tiempo lineal se consigue un grafo done cada punto indica aquél punto más cercano. Dicha relación no tiene porqué ser biunívoca, es decir, si pj es el punto más cercano a pi, éste no tiene por qué ser el más cercano para pj.

Es el más sencillo. Se asigna como valor de la función para p el mismo valor que su punto generador más cercano: Si p pertenece a la región de Voronoi del punto si, f(p) = f(si).

Es adecuado sobre todo cuando los valores pueden medirse en una escala nominal (p.e. tipo de vegetación o de roca).

El círculo más pequeño/grande.

De especial interés en estudios de mercado. Se desea construir una nueva residencia tan lejos como sea posible de las n existentes en la

actualidad. Equivale a encontrar el círculo más grande que no contenga a ninguno de los pi ∈ P que representan a los n puntos

Se pretende conocer el valor de una función para cualquier punto del espacio a partir del valor de una serie de puntos estratégicos.

Ejemplo ¿Cuál es el punto más cercano al punto x?

El punto x está dentro de la región de puntos más cercanos al punto pi

La región de Voronoi del punto pi la denominamos V(pi) La unión de todas las regiones de Voronoi es el diagrama de Voronoi: V(P)={V(p0),V(p1),...,V(p0)}

Método Incremental PASO i+1 Partiendo del diagrama de Voronoi para los i puntos, V(P0P1,...,Pi), se añade el punto i+1, del siguiente modo: 1.Se localiza en punto pi+1 en V(p0,p1,...,pi) en tiempo O(logn). Sea V(pk) la región en la que se encuentra. 2.Encontrar las bisectrices entre pi+1 y pk ,y entre pk y el resto de puntos cuya frontera es intersectada por las sucesivas bisectrices 3.Eliminar las porciones de arista y los vértices que queden dentro de la nueva región de Voronoi

Áreas de aplicación: • Diseño de circuitos VLSI.• Sistemas de Información Geográfica. Intersección de segmentos

Orden de ejecución: O(n·m). Objetivo: Si los polígonos son convexos, se puede realizar en O(n+m). Propiedad: La intersección de dos polígonos convexos es un polígono convexo.

Nomenclatura: A, B: ejes. a: punto de cabecera de A y H(A): semiplano cerrado a la izquierda de A y H(B), semiplano cerrado a la izquierda de B. AxB > 0 si el giro más corto de girar A hacia B es en sentido inverso a las agujas del reloj.

En cada iteración, se avanza el eje A ó el sincronizando para encontrar todas las intersecciones. Reglas de avance:

Intersección de polígonos convexos

PROCEDIMIENTO IntersecaPoligonosConvexos(VAR P,Q: TipoPoligono; n ,m:Entero ) ENTRADA: P, Q de tamaño n y mSALIDA : CONSTANTES: Origen: ( 0 , 0 )

1. INICIO 2. a ← 0 3. b ← 0 4. Dentro ← –1 5. REPETIR 6. (*)

Intersecciones

• Diseño de circuitos VLSI. • Sistemas de Información Geográfica.

Intersección de segmentos

Intersección de polígonos convexos

Orden de ejecución: O(n·m). Si los polígonos son convexos, se puede realizar en O(n+m).

Propiedad: La intersección de dos polígonos convexos es un polígono convexo.

a: punto de cabecera de A y b, punto de cabecera de B.H(A): semiplano cerrado a la izquierda de A y H(B), semiplano cerrado a la izquierda de B.AxB > 0 si el giro más corto de girar A hacia B es en sentido inverso a las agujas del reloj.

En cada iteración, se avanza el eje A ó el B (siempre en sentido antihorario). Dichosencontrar todas las intersecciones.

Intersección de polígonos convexos – Algoritmo(I)

IntersecaPoligonosConvexos(VAR P,Q: TipoPoligono; n ,m:

ENTRADA: P, Q de tamaño n y m

CONSTANTES: Origen: ( 0 , 0 )

Intersecciones

polígonos convexos

Si los polígonos son convexos, se puede realizar en O(n+m). Propiedad: La intersección de dos polígonos convexos es un polígono convexo.

b, punto de cabecera de B. H(A): semiplano cerrado a la izquierda de A y H(B), semiplano cerrado a la izquierda de B.AxB > 0 si el giro más corto de girar A hacia B es en sentido inverso a las agujas del reloj.

(siempre en sentido antihorario). Dichos avances se deben ir

IntersecaPoligonosConvexos(VAR P,Q: TipoPoligono; n ,m:

H(A): semiplano cerrado a la izquierda de A y H(B), semiplano cerrado a la izquierda de B. AxB > 0 si el giro más corto de girar A hacia B es en sentido inverso a las agujas del reloj.

avances se deben ir

7. HASTA (AvanA >= n AND AvanB >= m) 8. SI Dentro = – 1 9. ENTONCES ESCRIBIR "No ha habido intersección."; 10. FIN_SI 11. FIN

Intersección de polígonos convexos – Algoritmo (II) REPETIR (*) a1 ← (a + n – 1) mod n b1 ← (b + m – 1) mod m Subvector(P[a], P[a1] , A) Subvector(Q[b], Q[b1] , B) ProductoX ← Area2(Origen, A, B) bHA ← IzdaSobre(P[a1], P[a], Q[b] ) aHB ← IzdaSobre(Q[b1], Q[b], P[a] ) SI ( Interseca(P[a1], P[a], Q[b1], Q[b], P ) ) ENTONCES SI Dentro = – 1 ENTONCES AvanA ← 0 AvanB ← 0 FIN_SI Dentro ← TestDentro(aHB) FIN_SI (**) HASTA (AvanA >= n AND AvanB >= m) Intersección de polígonos convexos – Algoritmo (III) REPETIR (*) (**) SI (ProductoX >= 0) ENTONCES SI (bHA) ENTONCES a ← Avanza( a, AvanA, n, Dentro, P[a] ) SINO b ← Avanza( b, AvanB, m, NOT Dentro, Q[b] ) FIN_SI SINO SI (aHB) ENTONCES b ← Avanza( b, AvanB, m, NOT Dentro,Q[b]) SINO a ← Avanza( a, AvanA, n, Dentro, P[a] ) FIN_SI FIN_SI HASTA (AvanA >= n AND AvanB >= m) Intersección de polígonos convexos – Funciones auxiliares FUNCION TestDentro( H: Entero ) : Lógico INICIO

SI H < > 0 ENTONCES TestDentro ← 1 SINO TestDentro ← 0 FIN_SI

FIN FUNCION Avanza(VAR ab, Avd: Entero; n: Entero; Dentro: Lógico; v: TipoPunto )

INICIO SI Dentro ENTONCES Pintar( v ) FIN_SI Adv ← Adv + 1 ab ← (ab + 1) mod n

FIN PROCEDIMIENTO Subvector(VAR a, b, c : TipoPunto ) INICIO

PARA i ← 0 HASTA 1 INCR + 1 REPETIR c[i] ← a[i] – b[i] FIN_PARA

FIN

Intersección de polígonos convexos – Ejemplo

Intersección de segmentos

Un ejemplo donde podemos utilizarlo es en la representación de una carretera y un río, asi como para el cálculo de los puentes.

1er. Algoritmo: ~O(n2), con un número similar de ríos y carreteras. - Procesaría todos los ríos con todas las carreteras, con cálculos innecesarios.

Estrategia mejorada: Barrer de arriba abajo con una línea horizontal L. Estructuras de datos:

P: Conjunto de segmentos iniciales. Tamaño n×4, siendo cada fila un segmento {x0, y0, x1, y1}, con y0>y1.

Q: Cola de eventos. Almacena el conjunto de vértices y de puntos de intersección. Puntos ordenados de mayor a menor ordenada. La estructura debe permitir intersecciones.

T: Simula el comportamiento de la línea imaginaria L. Mantendrá ordenados de izquierda a derecha los segmentos que vaya atravesando en el momento actual. Debe permitir intersecciones y borrados en tiempo logarítmico.

I: Estructura para almacenar las intersecciones localizadas.

ALGORITMO Encontrar_Interseccion ENTRADA: P, conjunto de segmentos en el plano de tamaño n SALIDA : Conjunto I de interseccIones del plano

1. INICIO 2. Ordenar(P, n, Q) 3. Inicializar( T ) 4. Tam ← n 5. i ← 0 6. MIENTRAS ( tam>1 ) REPETIR 7. ManejarEvento( P, Q, i, Tam ) 8. FIN_MIENTRAS 9. FIN.

PROCEDIMIENTO ManejarEvento(VAR P: TipoConjuntoSegmento; VAR Q: Array(2, n) de Enteros; i, Tam: Entero; VAR Intersecciones : TipoConjuntoPuntos; VAR Tam: Entero ) ENTRADA: P de tamaño n; Q de tamaño n; i posición de Q a procesar SALIDA : Intersecciones INICIO

InicializarLista(U); InicializarLista(L); InicializarLista(C); REPETIR k ← Q( i, 0 ) Tipo ← Q( i, 1 ) EN CASO DE QUE Tipo SEA 1 : ListaInsertar( U, k ) 0 : ListaInsertar( C, k ) –1: ListaInsertar( L, k ) FIN_CASE i ← i + 1 Tam ← Tam – 1 HASTA NO ( IgualesCoordenadas(P(k, Tipo), P(Q(i, 0), Q(i, 1) ) (*)

FIN. (*) SI (TamanioLista(U) + TamanioLista(C) + TamanioLista( L )) > 1 ENTONCES InsertarLista( Intersecciones , k ) FIN_SI PARA l ← 0 HASTA TamanioLista( L ) – 1 ListaEliminar( T, ElementoLista( L, l ) ) FIN_PARA PARA l ← 0 HASTA TamanioLista(U) – 1 ListaInsertar( T, ElementoLista( U, l ) ) FIN_PARA SI TamanioLista(U) + TamanioLista(C) = 0 ENTONCES sl ← BuscarListaIzdo( T, k ) sr ← BuscarDecho ( T, k )

SI Interseca( P, sl , sr , q ) ENTONCES InsertarOrdenado(Q, q, 0 ) Tam ← Tam + 1 FIN_SI SINO (**) FIN_SI (**) SI TamanioLista(C ) = 0 ENTONCES s1 ← PrimeroLista(U) sl ← BuscarListaIzdo( T, s1 ) SI Interseca(P, s1, sl, q ) ENTONCES InsertarOrdenado( Q, q, 0 ) Tam ← Tam + 1 FIN_SI s2 ← PrimeroLista(U) sr ← BuscarListaDecho( T, s2 ) SI Interseca( P, s2, sr, q ) ENTONCES InsertarOrdenado( Q, q, 0 ) Tam ← Tam + 1 FIN_SI SINO sl ← PrimeroLista(C) sr ← UltimoLista(C) IntercambiarPosiciones( T, sl, sr ) FIN_SI Sin embargo, la función de intersección de segmentos desarrollada en el primer tema no es válida para conocer el punto de intersección entre dos segmentos, sólo para saber si dicha intersección se produce. El algoritmo también detecta las intersecciones de los segmentos por sus extremos, ya que hay que tener en cuenta que los segmentos pueden llegar desordenados y sin relación unos con otros.

FUNCION Interseccion_segment(VAR a, b, c, d : TipoPunto; VAR p : TipoPunto ): Lógico; ENTRADA: Los segmentos ab y cd SALIDA : el punto p si hay intersección

1. INICIO 2. denominador ← a[0]*( d[1] – c[1] ) + b[0]*( c[1] – d[1] ) + 3. d[0]*( b[1] – a[1] ) + c[0]*( a[1] – b[1] )

4. SI denominador = 0.0 5. ENTONCES Interseccion_segment ← falso 6. FIN_SI 7. s ← (a[0]*( d[1] – c[1] ) + c[0]*( a[1] – d[1] ) + d[0]*( c[1] – a[1] ) ) / denominador; 8. t ← –(a[0]*( c[1] – b[1] ) + b[0]*( a[1] – c[1] ) + c[0]*( b[1] – a[1] ) ) / denominador; 9. p[0] ← a[0] + s*( b[0] – a[0] ) 10. p[1] ← a[1] + t*( b[1] – a[1] ) 11. SI (( 0.0<=s ) AND ( s<=1.0 ) AND ( 0.0<=t ) AND ( t<=1.0 )) 12. ENTONCES Interseccion_segment ← verdad 13. SINO Interseccion_segment ← falso 14. FIN_SI 15. FIN

Conclusiones Tras haber realizado el trabajo 3 denominado “Bases de datos restrictivas y geometría computacional” se pudo tener un panorama general de los aspectos principales que integran una base de datos que utiliza restricciones para representar la información, las principales diferencias que existen con las bases de datos convencionales y sobre todo la forma en que debemos construir las diferentes consultas; dos fueron las bases de datos elegidas para ejemplificar lo anteriormente dicho: MLPQ/PReSTO y DISCO. En el caso de MLPQ/PReSTO se logró conseguir el software para poder llevar a cabo las pruebas de manera real, de tal manera que se pudiera comprobar cómo es que podemos implementar una base de datos, las consideraciones que debemos tomar en cuenta como lo son el formato, los símbolos, la ubicación de las restricciones, convención para nombres, etc. Todo esto nos permitió poder crear ejemplos vistosos y significativos haciendo uso de las principales funciones y herramientas con las que la base de datos cuenta, como lo son las pantallas para poder crear los distintos queries, la forma en que podemos observar la información almacenada, la manera en que debemos de cargar nuestro archivo con restricciones, entre muchas más. Uno de los puntos importantes a mencionar, es que utilizamos una aplicación que nos permite convertir nuestro archivo en formato .shp al formato que trabaja MLPQ/PReSTO, haciendo uso de los archivos shapefile que generamos en el trabajo 2, los transformamos al formato de MLPQ/PReSTO y cargamos la información, pudiendo llevar a cabo ciertas consultas pero ahora a través del uso de una base datos restrictiva. La segunda base de datos que se utilizó fue DISCO, desafortunadamente no se pudo contar con el software correspondiente, por ello únicamente se realizó una investigación de carácter bibliográfico y recabando información en algunas páginas web; sin lugar a dudas esta base de datos resultó mucho más compleja de comprender y analizar, dado que sólo contábamos con lo que los libros y la web nos proporcionaban. La segunda parte del trabajo consistió en describir dos algoritmos de la geometría computacional, el primero de ellos fue el del diagrama de Voronoi, el cual es una estructura geométrica que representa información de proximidad acerca de un conjunto de puntos u objetos; es decir, el diagrama de Voronoi de un conjunto de objetos geométricos es una partición del espacio en celdas, cada una de la cuales contiene una colindancia con sus puntos más cercanos. Se eligió este algoritmo por ser uno de los principales dentro del campo de la geometría computacional, siendo sus aplicaciones muy vastas tales como sociología, biología, fisiología, astronomía, entre muchas más; sin lugar a dudas uno de los algoritmos que mayor impacto ha tenido. El segundo algoritmo que se desarrolló fue relativo a intersecciones entre polígonos y polilíneas, donde colocamos los elementos principales que conforman los algoritmos, ejemplos que permiten apreciar los detalles de éstos y sobre todo presentamos el pseudocódigo correspondiente a cada una de las fases que integran el proceso de determinar la intersección entre diversos elementos. Sin temor a equivocarnos, ha sido un trabajo que nos ha dejado un buen sabor de boca, el trabajar con otra perspectiva de bases de datos siempre es enriquecedor, ampliando nuestro campo de visión y sobre todo permitiéndonos analizar y comprender los principales elementos que conforman los gestores de bases de datos para el tratamiento de Información representada mediante restricciones. Con respecto a los algoritmos de geometría computacional, pudimos conocer otros algoritmos que utilizan estrategias incrementales, de división o partición o en su caso de líneas de barrido; todo esto otorgándonos un bagaje mucho mayor en lo que a estrategias de geometría computacional se refiere.

Con este trabajo damos cierre a los temas impartidos en el curso de bases de datos espaciales, siendo gratamente satisfactorio el haber tenido la oportunidad de adentramos en el fascinante mundo que se aboca a tratar la información de carácter espacial.

Bibliografía y Mesografía F. Benhamou, L. Granvilliers, Continuous and interval constraints, in: F. Rossi, P. van Beek, T. Walsh (eds.), Handbook of Constraint Programming, Foundations of Arti_cial Intelligence, chap. 16, Elsevier Science Publishers, Amsterdam, The Netherlands, 2006. Franco P. Preparata and Michael Ian Shamos. Computational Geometry an Introduction. Springer, (August 6, 1993) G. Kuper, L. Libkin, J. Paredaes, "Introduction", Constraint Databases, G. Kuper and L. Libkin and J. Paredaes, Springer, 2000. G. Kuper, L. Libkin, J. Paredaes, "The DISCO SYSTEM", Constraint Databases, G. Kuper and L. Libkin and J. Paredaes, Springer, 2000. G. Kuper, L. Libkin, J. Paredaes, Constraint Databases, Springer, 1998. Jacob E. Goodman and Joseph O’Rourke (editors). Handbook of Discrete and Computational Geometry. Chapman & Hall/CRC, 2nd edition (April 15, 2004) Joseph O’Rourke. Computational Geometry in C. Cambridge University Press; 2000 edition (February 15, 2001). Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer, 3rd edition (April 16, 2008) P. C. Kanellakis, G. M. Kuper, P. Revesz, Constraint query languages, Symposium on Principles of Database Systems (1990) 299_313. http://cse.unl.edu/~revesz/MLPQ/mlpq.htm http://cse.unl.edu/~revesz/MLPQ/WebImplementation.pdf http://springerlink.com/index/xh49765171t63176.pdf