CSP y Bases de Datos Restrictivas

Inteligencia Artificial, Revista Iberoamericana de Inteligencia Artificial. No.20 (2003) ISSN: 1137-3601. © AEPIA (http://www.aepia.org/revista) pp 151-163. ARTÍCULO CSP and Restricted Databases M. T. Gómez, R. M. Gasca, C. Del Valle, R. Ceballos Depto de Lenguajes y Sistemas, Universidad de Sevilla, Sevilla, España, e-mail: {mayte, gasca, carmelo, ceballosg}@lsi.us.es Constraint Databases were proposed because it was necessary to represent infinite relations in a more modular and compact way. In this way, Constraint Databases were used to handle continuous data, like spatio-temporal, and to enrich both the data model and the queries with constraints. It allows us to handle these constraints and it makes easier to construct and model the Constraint Satisfaction Problems (CSP) when we want to evaluate these queries. In this paper, we carry out a study of the different reasons, methodologies and tools that have helped to the development of Constraint Databases. Also, we present a study of some defects and how to improve them. To help us in the CSP construction, we show a modular framework, with all the advantages that it implies. Finally, we show an example to understand better the reasons that have helped to the development of our system. CSP y Bases de Datos Restrictivas M. T. G´omez, R. M. Gasca, C. Del Valle, R. Ceballos Depto de Lenguajes y Sistemas, Universidad de Sevilla, Sevilla, Espa˜na, {mayte, gasca, carmelo, ceballos}@lsi.us.es Resumen Las Bases de Datos Restrictivas se originaron ante la necesidad de representar de forma m´as compacta y modular datos de gran tama˜no. De esta forma, y como medio para tratar datos continuos como es el caso de los espacio-temporales, se opt´o por tratar la informaci´on como restricciones almacenadas en una base de datos. Gracias a esta forma de tratar las restricciones, se facilita la construcci´on y el modelado de problemas de satisfacci´on de restricciones (CSP) y su posterior resoluci´on. En este art´ıculo, se realiza un recorrido por las distintas razones, metodolog´ıas y herramientas que han ayudado al desarrollo de las Bases de Datos Restrictivas. Junto a dicho estudio, se lleva a cabo un an´alisis de sus deficiencias y de los posibles aspectos a mejorar. Para aumentar la habilidad en la construcci´on de modelos, y ayudando a la resoluci´on de problemas de satisfacci´on de restricciones (CSP), se ofrece una arquitectura de implementaci´on modular, con las ventajas que eso conlleva. Para finalizar, se presenta un ejemplo que aclara las razones que han movido al desarrollo de nuestra propuesta. Palabras clave: Bases de Datos Restrictivas, CSP, ´ Algebra Relacional, Base de Datos Relacional, Lenguajes de Consulta. 1. Introducci´on Para el desarrollo de ciertas aplicaciones, es necesario la utilizaci´on de datos continuos, para los que las bases de datos convencionales presentan considerables limitaciones. Por ejemplo, ante la necesidad de almacenar y tratar informaci´on espacio-temporal, cient´ıfica, m´edica, biol´ogica..., aparece el problema del car´acter f´ısico de los soportes, que obliga a un tama˜no finito, junto al inconveniente que genera el almacenamiento masivo de datos, tanto para su tratamiento, como a la hora de inferir conocimiento partiendo de dichos datos. Pese a las limitaciones que en principio parecen presentar las tecnolog´ıas relacionales para el tratamiento de las datos actuales, no se debe olvidar al potencia que ofrecen a la hora de deducir conocimiento de registros relacionales. Partiendo de este planteamiento, las Bases de Datos Restrictivas, pretenden resolver los problemas aprovechando tanto la versatilidad de las bases de datos relacionales, como la potencia de la programaci´on con restricciones para representar informaci´on continua. Combinando ambos campos, ser´a posible almacenar la informaci´on de gran tama˜no en un n´umero reducido de registros. Un ejemplo donde se tienen datos que no son convencionales, en lo que respecta a su forma de almacenamiento, podr´ıa ser un sistema donde se encuentran un conjunto de parcelas, las cuales tienen al menos un propietario. La informaci´on que es necesaria almacenar, es de tipo discreto en el caso de los datos de los propietarios (nombre, direcci´on...), pero de car´acter geogr´afico para poder localizar las parcelas. En ejemplos de este tipo, ser´ıa oportuno la utilizaci´on de Bases de Datos Relacionales, ya que se puede integrar las bases 1 de datos relacionales, con la versatilidad que ello conlleva, y los problemas de satisfacci´on de restricciones para poder resolver consultas como por ejemplo ’qui´enes son los propietarios de las parcelas por las que pasa una carretera’. En este art´ıculo, se pretende repasar los or´ıgenes hist´oricos de las Bases de Datos Restrictivas, gracias a las aplicaciones que ofrece, y la situaci´on actual. Como aportaci´on, se muestra una nueva arquitectura para la construcci´on de CSP ayudado por Bases de Datos Restrictivas, junto a un ejemplo para analizar su funcionalidad. 2. Introducci´on Hist´orica El campo de las Bases de Datos Restrictivas [1, 5] tuvo su origen a principios de 1990 en el art´ıculo de Kanellakis, Kuper y Revesz [3], cuyo objetivo era definir una versi´on de bases de datos para la Programaci´on L´ogica con Restricciones (CLP), continuando la misma l´ınea de la definici´on de Datalog, como una nueva versi´on de base de datos Prolog. El objetivo inicial de las Bases de Datos Restrictivas, fue abarcar aplicaciones donde los datos pod´ıan ser representados como un gran conjun- to de restricciones, combinando las bases de datos con la Programaci´on L´ogica con Restricciones. Los desarrollos en este campo, se incentivaron a´un m´as ante la necesidad de nuevas formas de almacenamiento, ocasionado por la existencia de gran cantidad de datos de car´acter continuo. La idea clave fue la noci´on de que una tupla en una base de datos relacional, pod´ıa ser sustituida por un conjunto de restricciones, y que muchas de las caracter´ısticas del modelo relacional pod´ıan ser extendidas al campo de la l´ogica con restricciones. De esta manera un lenguaje de consulta, permitir´a a los usuarios obtener la informaci´on almacenada en una base de datos convencional, de una forma trasparente. Para abordar esta propuesta, se parti´o de un modelo de datos ya introducido [1], fundamentado en considerar una tupla en una base de datos, como un conjunto de restricciones lineales de igualdad o desigualdad en los atributos de dicha tupla, ya que las restricciones son un mecanismo natural de especificar las consultas de similitud en un conjunto de datos. 2.1. Aplicaciones de las Bases de Datos Restrictivas Considerando las limitaciones que las bases de datos convencionales, presentan ante las necesidades que plantea la inferencia de conocimiento en algunas de las aplicaciones actuales, se abre el campo de la tecnolog´ıa en Bases de Datos Restrictivas, que originalmente involucran datos espaciales [10]. Muchos de los datos espaciales pueden ser descritos utilizando restricciones lineales o polin´omicas. Mientras que las restricciones polin´omicas son m´as generales, tambi´en tienen m´as coste de implementaci´on y ejecuci´on. Los sistemas de restricciones lineales son m´as eficientes a la hora de resolverse, aunque m´as limitados en el tipo de datos que pueden representar. Pese a ´esto, las restricciones lineales son suficientes en muchas de las aplicaciones, incluyendo a los Sistemas de Informaci´on Geogr´afica (GIS). En la pr´actica, los datos espaciales en un GIS consisten en segmentos lineales, de forma que las restricciones lineales son particularmente apropiadas para representar estos datos. La principal diferencia entre las Bases de Datos Restrictivas Lineales y la mayor´ıa de las sistemas geogr´aficos, radica en que las Bases de Datos Restrictivas est´an basadas en un modelo relacional, suministrando una estructura uniforme para el tratamiento de los datos tanto espaciotemporales, como con otros tipos de informaci´on. ´ Esto provoca que uno de los mayores problemas de los GIS, haya sido la dif´ıcil integraci´on con otros tipos datos, lo que es mejorable combinando la informaci´on espacio-temporal con una estructura uniforme resultante de un lenguaje de consulta, y facilitando su uso. La expresividad de las Bases de Datos Relacionales puede ser tambi´en aplicadas a problemas de configuraci´on o en sistemas din´amicos, que han sido resueltos mediante otras t´ecnicas en trabajos anteriores [2, 7]. 2.2. Herramientas y Prototipos para Bases de Datos Restrictivas En la actualidad existen varias propuestas en la implementaci´on y construcci´on de prototipos para Bases de Datos Restrictivas, cuyo principal objetivo es el tratamiento de sistemas espaciotemporales. A continuaci´on, se hace un recorrido por las de mayor transcendencia. 2.2.1. MLPQ MLPQ (Management of Linear Programming Queries) es un sistema desarrollado en el Departamento de Ciencia de la Computaci´on e Ingenier´ıa de la Universidad de Nebraska [12], para la gesti´on de consultas con programaci´on lineal para una Base de Datos Restrictiva, que permite consultas Datalog, y a˜nadir operadores sobre funciones lineales. Hay dos ´areas principales de desarrollo para el sistema MLPQ. La primera es en la investigaci´on de operadores cuando los datos disponibles en una base de datos, necesitan ser modificados por alguna consulta, suministrando en este caso MLPQ de la flexibilidad necesaria. La segunda, y principal aplicaci´on de MLPQ, es para el tratamiento de informaci´on espacio-temporal, gracias a un entorno gr´afico que permite trabajar en 2 ´o 3 dimensiones, mediante la interacci´on del usuario con el conocimiento almacenado, todo ello mediante consultas Datalog. 2.2.2. PReSTO PReSTO (Parametric Rectangle Spatiotemporal Objects [5, 13]) es un sistema de base de datos espacio-temporales, que al igual que MLPQ, fue desarrollado en el Departamento de Ciencia de la Computaci´on e Ingenier´ıa de la Universidad de Nebraska. Dicho sistema permite consultas del ´algebra relacional a sistemas que cambian en funci´on del tiempo. El formato de fichero de entrada en PReSTO es de la forma: begin %STDB % r1 r2 . . . rn end %STDB % Donde cada ries una regla o un par´ametro para la representaci´on de periodicidad. Un ejemplo de reglas, ofrecido por la herramienta, podr´ıan ser: clouds(h) : −i= 1, x1−t= 80, y1−0,5t= 100, x2−1,1t= 220, y2−0,6t= 200, t >= 0, t <= 300, p=−1, s = 0, h= 0. clouds(h) : −i= 1, x1−t= 105, y1−0,5t= 200, x2−t= 111, y2−0,6t= 205, t >= 0, t <= 300, p=−1, s = 0, h= 0. clouds(h) : −i= 1, x1−t= 111, y1−0,5t= 200, x2−1,1t= 225, y2−0,6t= 210, t >= 0, t <= 300, p=−1, s = 0, h= 0. En este caso se muestra un ejemplo donde un elemento, en este caso una nube (cloud), cambia su posici´on en funci´on del tiempo (t). 2.2.3. MLPQ/PReSTO El sistema MLPQ/Presto [5, 13] proviene de la combinaci´on de los sistemas MLPQ y PReSTO. Un ejemplo, ofrecido por la herramienta, de los ficheros que son tratados y almacenados podr´ıa ser: AK(1, x, y) : − −27x+ 39y < 5682, 8x+ 67y < 14656, 75x+ 19y < 15575, −33x+ 33y > −1683, −53x+ 57y > −2335, 59x+ 43y > 6751, −83x+ 8y < −2785. AK(1, x, y) : − 28x+ 9y < 6053, −5x+ 42y > 3149, −33x+ 33y < −1683. AK(1, x, y) : − 34x+ 80y < 14050, −16x+ 13y > −3421, 41x+ 67y > 13481, 9x > 1665. HI(2, x, y) : − −24x+ 10y < −7298, 28x+ 30y < 12806, −18x+ 24y > −4986, 22x+ 16y > 8678. WA(3, x, y) : − 7x+ 36y < 20488, −39x+ 22y > 10270, 46x+ 14y > 8660. /* the capital cities */ Capital( 1, name) :- name=”Juneau”. Capital( 2, name) :- name=”Honolulu”. Capital( 3, name) :- name=”Seattle”. En este ejemplo, se muestra la situaci´on geogr´afica de un conjunto de estados americanos, y las capitales de cada uno de ellos. 2.2.4. DEDALE DEDALE [15] es una implementaci´on realizada en 1999 por miembros de centro de investigaci´on CNAM y del instituto franc´es para la investigaci´on en inform´atica (INRIA). El objetivo principal de este sistema se basa en aplicaciones de car´acter geom´etrico, bas´andose en un modelo de restricciones lineales con bases de datos, dando soluci´on a los GIS, y a los sistemas espaciotemporales. DEDALE ofrece un lenguaje para la consulta a bases de datos de conocimiento mediante un interfaz gr´afico, que permite obtener informaci´on de la base de datos, y mostrar los resultados. Para la representaci´on de las restricciones se utiliza orientaci´on a objeto, m´as apropiado para estructura de datos complejos. Un ejemplo de los datos que permite DEDALE [18] puede ser de la forma: PEOPLE={[ name : string, category : string, activity : {name : string, time : Q}, trajectory : {space : Q2, time : Q} ]} En este ejemplo, se observa el tratamiento de datos espacio-temporales, como es el caso de la trajectoria. Una posible instancia de este ejemplo ser´ıa la descrita en la tabla 1 [18]. 2.2.5. CCUBE CCUBE (Constraint Object-Oriented Database System) es la primera implementaci´on de una Base de Datos Restrictiva orientada a objetos [16], desarrollada por el grupo de investigaci´on en Programaci´on con restricciones y Bases de Datos de la Universidad de George Mason en 1999. El sistema se basa en dar uniformidad a la heterogeneidad de los datos existentes en la actualidad, como es el caso de las trayectorias en 4 dimensiones, interconexi´on entre distintos sistemas coordinados entre si o GIS. Aportando principalmente, adem´as de las ventajas de la combinaci´on de las restricciones con las bases de datos, la implementaci´on a alto nivel mediante la orientaci´on a objetos, lo que provee de mayor versatilidad a la hora de construir un sistema software. 2.2.6. Inconvenientes de las Herramientas Los inconvenientes de la utilizaci´on de algunas de las herramientas actuales para el tratamiento de Bases de Datos Restrictivas, radica en varios puntos: 1. Pese a incluir un interfaz gr´afico, necesitan que el usuario conozca lenguajes de consulta como SQL o Datalog, ya que la interacci´on del usuario con la informaci´on se realiza con la ayuda de ellos. 2. Tratamiento de restricciones ´unicamente lineales, que pese a ser m´as eficientes no reflejan todo el dominio de las aplicaciones existentes en la actualidad. 3. Poca modularidad en la forma de almacenar datos, lo que dificulta la adaptaci´on con sistemas ya existentes. 4. Tratamiento con grandes cantidades de informaci´on, ya que la capacidad del interfaz gr´afico para mostrar datos es limitada. Si los rangos de los dominios de los datos que se presentan, son muy diferentes, es dif´ıcil mostrar la informaci´on el sistema con claridad y de forma fidedigna. 5. Dificultad en el almacenamiento masivo de datos, ya que en sistemas como MLPQ/PReSTO se utilizan ficheros de tex- to (Datalog) como medio para el almacenamiento. Si se utilizaran bases de datos relacionales, ser´ıa posible tratar gran volumen de informaci´on y hacer uso de las ventajas que ofrecen las bases de datos relacionales. 3. Consultas a Bases de Datos Restrictivas Una consulta es una f´ormula en una determinada l´ogica, donde tanto la entrada como la salida Name Category Activity Trajectory (name=’Sleep’ (x= 1230 ∧y= 134 ∧2< t < 10) ∧1< t < 11) Jonh Tourist ∨(name=’Eat’ ∨(3x−2y≤49 ∧10 < t < 11) ∧23x+ 2y≥134 . . . ∨(name=’Ski’ ∧11 < t < 16) ∧11 < t < 15)) . . . . . . Tabla 1: Ejemplo de DEDALE para una tupla. son un conjunto de relaciones. En el caso del tratamiento de las Bases de Datos Restrictivas, se pueden utilizar diferentes lenguajes de consulta, como es el caso del ´algebra relacional o el lenguaje SQL. Una vez construidas las consultas, ´estas son ’evaluadas’ reemplazando las instancias de los predicados de la base de datos por la f´ormula que define la relaci´on, y usando la eliminaci´on de cuantificadores para convertir el resultado en la forma normal disjunta (DNF). Las propiedades que constituyen las consultas a bases de datos relacionales descrita abajo, son entre otras las que contribuyen al ´exito del modelo relacional: Clausura: Propiedad de los lenguajes cuya ´algebra relacional es cerrada, lo que significa que la entrada son un conjunto de relaciones y la salida es de la misma forma. La clausura es una propiedad muy ´util, por ejemplo que se pueda descomponer una consulta para optimizar cierto prop´osi- to, y atender cada parte de la relaci´on como una consulta en ella misma. Eficiencia de Evaluaci´on: Las consultas pueden evaluarse eficientemente usando las nociones de complejidad de dato, que consiste en evaluar una consulta en t´erminos del tama˜no de la base de datos. C´alculo/´ Algebra: Gracias a la existencia de equivalencias entre el ´algebra relacional y los lenguajes de consulta a m´as alto nivel, es posible que el usuario construya consultas en lenguaje declarativo, mientras que el sistema utilice un lenguaje procedural para la obtenci´on de resultados. La uni´on de lenguajes de consulta con restricciones (CQL) [3], se origin´o ante la b´usqueda de mayor potencia y la posibilidad de utilizar estructura de datos m´as complejas. De esta forma en [3] se propone un una sintaxis del CQL, que es la uni´on de los lenguajes de consulta convencionales y la l´ogica. Un ejemplo para aclarar el funcionamiento de un CQL se puede encontrar al representar dos superficie rectangulares, cada una de ellas descrita mediante 4 puntos. Sobre esta informaci´on almacenada en una base de datos, se pueden realizar consultas como si las superficies comparten espacio, o a qu´e superficie pertenece un determinado punto. Al tener almacenada la informaci´on mediante los puntos que definen la superficie, es necesario realizar una transformaci´on de los datos a forma de restricci´on. Por ejemplo, la zona de intersecci´on entra las superficies (1,2)(3,2)(1,4)(3,4), y (2,3)(6,3)(2,7)(6,7) vendr´a representada por la restricci´on: {1≤x≤3∧2≤y≤4∧2≤x≤6∧3≤y≤7} 4. Generaci´on de CSP consultando a Bases de Datos Restrictivas Como principales objetivos en nuestra propuesta, est´a unir la potencia de consulta de las bases de datos relacionales, y el almacenamiento de datos restrictivos. En principio, no ser´a objetivo de nuestros estudios c´omo se resolver´an las restricciones, sino ofrecer un mecanismo de construcci´on din´amica de CSP en funci´on de la informaci´on almacenada en una base de datos relacional. Tambi´en es interesante destacar, la posibilidad que se ofrece de construir distintos CSP, en funci´on del motor de inferencia que se encargar´a de su resoluci´on, sin que ello intervenga en la arquitectura de la base de datos y de los datos all´ı almacenados. Entre otra de las ventajas de la utilizaci´on de bases de datos relacionales, en lugar de ficheros de texto, se encuentra que tan s´olo se construir´a el CSP con los datos involucrados en nuestro problema no con toda la base de conocimiento. No obstante, las ventajas que ofrece la utilizaci´on de bases de datos relacionales se reflejar´a con mayor claridad en 5. Pese a ser la construcci´on de CSP la parte cla- ve de la arquitectura que se propone, no hay que olvidar que no siempre ser´a necesario construir y resolver un CSP, ya que las consultas donde no se involucran datos restrictivos, se pueden resolver exclusivamente con consultas SQL convencionales. 4.1. Formas de almacenar las Restricciones Para poder tratar la informaci´on de una forma r´apida y adecuada, es necesario que se busque la manera m´as correcta de almacenar los datos continuos, abord´andolo desde distintas opciones para encontrar la mejor elecci´on. 4.1.1. Representaci´on Mediante Puntos Para sistemas din´amicos, una de las t´ecnicas que ha proliferado mucho en el tratamiento de datos continuos, radica en simulaci´on el sistema y la discretizaci´on de los resultados obtenidos. Para tener una idea m´as tangible del tipo de conocimiento con el que se puede tratar, se propone el sistema din´amico que describe el comportamiento de un muelle: d dtv=−kx −µv y donde los valor de kse encuentran en el rango [k0..k00], por ejemplo [1,8. . . 1,9]. Esta t´ecnica se basa en la obtenci´on de conocimiento mediante la simulaci´on de los sistemas y discretizando la informaci´on continua, lo que transforma un problema de car´acter infinito, en uno finito. La informaci´on obtenida tras la discretizaci´on ser´a la almacenada en la base de datos, y de donde se inferir´an futuros conocimientos [11]. Como se muestra la figura 1, se obtiene el comportamiento del sistema para un conjunto de los valores que puede tomar k, como por ejemplo 1.81, 1.82, 1.83... Esta opci´on, llevada a cabo en trabajos previos [6, 11], tiene entre sus inconvenientes: 1. P´erdida de informaci´on al realizar la obligada discretizaci´on, con la consecuente poda de datos ante la imposibilidad de almacenar un n´umero de valores infinitos. 2. Saturaci´on innecesaria de la base de conocimiento, que pasar´a a contener gran n´umero de registros, cuya cantidad ser´a proporcional a la exactitud con la que se pretenda representar el sistema simulado. 3. Necesidad de decidir la cantidad de datos a almacenar, lo que necesitar´a de un estudio anterior a la simulaci´on del sistema, para valorar el nivel entre veracidad de la informaci´on y velocidad de acceso, lo que tambi´en provocar´a p´erdida en tiempo y recursos. 4. P´erdida de simbolog´ıa, con la consecuente dificultad en el tratamiento y aprendizaje del conocimiento. 4.1.2. Representaci´on de los T´erminos del Sistema La segunda opci´on se encuentra almacenando las variables que sean necesarias para conocer el comportamiento del sistema. Por ejemplo, en el caso de almacenar una restricci´on polin´omica, se guardar´an los distintos t´erminos que lo constituyen: x Indep Relaci´on 3−2> . . . . . . . . . ≡3x - 2 >y O para mayor n´umero de t´erminos: x2x Indep Relaci´on 3 0 5 < . . . . . . . . . . . . ≡3x2+ 5 <y Esta propuesta ofrece importantes ventajas, ya que permite almacenar informaci´on continua con poco gasto de espacio y no perder informaci´on en la discretizaci´on. Tambi´en entre sus ventajas se encuentra, el tener una manera f´acil de realizar modificaciones en los datos ya almacenados. Por ejemplo, cambiar todo el dominio que representa una restricci´on Cpor su complementario C, significa cambiar tan s´olo una desigualdad, lo que Figura 1: Ejemplo de simulaci´on de sistemas din´amicos implica modificar un solo registro. De esta manera, pasar de representar un determinado ´area a su opuesta, ser´a posible con tan s´olo cambiar ≤por >. Otra de las ventajas, que mejora la primera de las soluciones (discretizaci´on de datos continuos), es la no necesidad de un estudio previo del sistema para decidir c´omo se va a realizar la poda de informaci´on, ya que dicha poda no es necesaria cuando almacenamos la restricci´on en si en lugar de datos discretos. Pese a las comentadas ventajas, tambi´en presenta el inconveniente de no permitir incorporar f´acilmente el comportamiento de caracter´ısticas heterog´eneas, debido a la p´erdida de simbolog´ıa. Cada vez que se pretenda incluir en la base de datos un comportamiento con distinto n´umero de par´ametros, se deber´a crear una nueva tabla con los campos necesarios, provocando ante un sistema cambiante, constantes modificaciones en la arquitectura de la base de datos. 4.1.3. Almacenamiento de las Restricciones como Cadenas: Ante las estudiadas desventajas que presentan sistemas convencionales, en este trabajo se propone una tercera soluci´on, donde se abordan las Bases de Datos Restrictivas, almacenando las restricciones sin ning´un tipo de formato, tan s´olo como un campo m´as. Esta soluci´on aprovecha lo aportado por la segunda soluci´on (Representaci´on de los t´erminos), pero mejorando sus deficiencias. Con esta nueva forma, es posible almacenar informaci´on continua en muy poco espacio, evitando tambi´en la simulaci´on y el pretratamiento de datos, junto a una f´acil modificaci´on de la informaci´on, ya que tan s´olo es necesario modificar un registro. A su vez, resuelve el problema que presentaba la segunda soluci´on, ante la incorporaci´on de sistemas con distinto n´umero de par´ametros, ya que en esta propuesta la restricci´on se guarda como una cadena, sin estudiar en principio las partes de la sentencia. Esta aportaci´on, ofrece tratar las Bases de Datos Restrictivas a un alto nivel de abstracci´on, siendo posible almacenar en una base de datos relacional cualquier informaci´on, donde algunos de sus registros tienen car´acter continuo, sin que ´esto intervenga en la arquitectura de la base de datos. ´ Esta situaci´on origin´o la necesidad de la b´usqueda de una nueva arquitectura que aprovechara tan- to la potencia de las bases de datos relacionales y las consultas, como los avances en el campo de Satisfacci´on de Restricciones. La aportaci´on que se describe a continuaci´on, propone abordar el razonamiento mediante bases de datos restrictivas almacenando las restricciones sin ning´un tipo de formato, en una base de datos relacional convencional, siendo posible representar el conocimiento de una manera simb´olica evitando as´ı el pretratamiento de datos, junto a la facilidad la modificaci´on de la informaci´on y el tratamiento cognoscitivo. Esta aportaci´on, ofrece tratar las bases de datos con restricciones a un alto nivel de abstracci´on, ya es posible almacenar en una base de datos relacional cualquier informaci´on, donde algunos de sus registros tienen car´acter continuo, sean o no lineales, y sin que ´esto intervenga en la arquitectura de la base de datos ni al tratamiento del conocimiento. Bas´andose en esta idea, se desarrolla una arquitectura en el punto 4.3, que permite aprovechar al m´aximo las caracter´ısticas de las Bases de Datos Restrictivas. 4.2. Modelo de Datos Para la resoluci´on del problema se plantea el almacenamiento de las restricciones en forma de cadena, dentro de un determinado campo. Para obtener las restricciones, s´olo se tendr´a que acceder al registro adecuado. La gram´atica del Modelo de Datos que se utilizar´a para representar las restricciones (c) que pueden aparecer en las tuplas, ser´a de la forma: c:expr =expr |expr ≥expr |expr ≤expr |expr > expr |expr < expr |si(c1)⇒c2 |c1∨c2 |c1∧c2 | ¬c1 expr :constante |V ariable |f(expr) |expr +expr |expr −expr |expr ∗expr |expr/expr |d dt V ariable Las consultas que se pueden realizar a una Base de Datos Restrictiva, pueden ser de la misma forma que a cualquier base de datos relacional, s´olo que hay que tener en cuenta que se puede tanto obtener, como modificar restricciones, almacenadas en forma de cadena, adem´as de cualquier tipo de datos que soporte la base de datos relacional en concreto. 4.3. Arquitectura del Sistema Una vez encontrada una mejor forma de almacenar las restricciones para que el tratamiento y modificaci´on del conocimiento sea lo m´as vers´atil posible, es necesario abordar la manera de extraer la informaci´on para adquirir la mayor potencia, tanto de la base de datos en s´ı, como de las restricciones almacenadas en ella. Para ello, se propone la arquitectura de la figura 2. Esta arquitectura propone la consulta a una base de datos, con datos restrictivos, para la construcci´on de problemas de satisfacci´on de restricciones. La construcci´on de los problemas se realizar´an mediante las restricciones almacenadas en la base de datos, obtenidas mediante consultas, y Restricciones Externas que son datos restrictivos introducidos por el usuario que ayudan a la construcci´on del CSP final. Las partes de la arquitectura se dividen principalmente en los m´odulos: Interfaz de Usuario: Interfaz gr´afico que facilita la relaci´on de un usuario no experto en restricciones y en lenguajes de consulta, con el sistema. Gracias a un entorno mediante el cual puede definir sus necesidades, y marque al sistema c´omo tiene que construir el CSP e introducir Restricciones Externas. Construcci´on de Consultas: Una vez definidas las necesidades del usuario, el sistema construye las consultas SQL necesarias para obtener de la bases de datos la informaci´on concreta, tanto restricciones como datos discretos. Bases de Datos Restrictivas: Implementada con cualquier tipo de base de datos relacional, que ser´a seleccionada en funci´on de las necesidades del sistema, como puede ser la velocidad de acceso, paralelismo de consultas, soporte de gran cantidad de registros,distribuci´on de la informaci´on... Obtenci´on del Conocimiento: En el m´odulo de la obtenci´on de conocimiento se decide si es necesario construir un CSP o ya se tiene toda la informaci´on necesaria. En el caso de que los datos sean restrictivos y haya que obtener m´as informaci´on, ser´a necesario construir un CSP para que sea resulto por el motor de inferencia, en caso contrario, la informaci´on se mostrar´a por la interfaz de usuario. Construcci´on del CSP: Mediante la informaci´on conseguida del m´odulo de Obtenci´on de Conocimiento y las Restricciones Externas, se construye el o los CSP. De esta forma, se ayuda a enriquecer m´as a´un la implementaci´on del problema, y es posible minimizar el tiempo de b´usqueda de informaci´on deductiva por parte del motor de inferencia, pudiendo hacer tratamiento del conocimiento de diversos tipos para la satisfacci´on de restricciones: 1. Sin que sufran ning´un tipo de modificaci´on, insert´andolas directamente en el modelo. 2. Combin´andolas con otras restricciones (de la propia base de datos o externas) mediante operaciones del ´algebra Booleana como AND, OR, NOT... Al tener almacenadas las restricciones directamente, resultar´a mucho m´as f´acil combinar distintas restricciones e inferir nuevos conocimientos, que si la informaci´on estuviera discretizada. Motores de Inferencia: Son los encargados que resolver propiamente los CSP, pudiendo dar como