En esta tesis se presenta un nuevo método, llamado método de los eventos, para la actualización de vistas en bases de datos deductivas. Este método aumenta la base de datos con un conjunto de reglas, llamadas reglas de transición y de evento, que definen explícitamente las inserciones y las supresiones inducidas por una modificación de la base de datos. Mediante estas reglas, se utiliza la resolución SIDNF para obtener todas las traducciones mínimas que satisfacen una petición de actualización de vista.Una de las contribuciones principales de esta tesis es la demostración del hecho que el método de los eventos es completo en bases de datos estratificados. Es decir, en este tipo de bases de datos dicho método obtiene todas las traducciones validas. Otras ventajas importantes del método son la incorporación de la comprobación de integridad en el proceso de traducción, el tratamiento uniforme de inserciones y supresiones, la posibilidad de prevenir efectos laterales y la traducción de peticiones de modificación de vista.Por todas estas razones, se puede decir que el método de los eventos tiene todo el poder de los métodos propuestos hasta el momento actual para la utilización de vistas en bases de datos deductivas, pero sin presentar algunas de sus limitaciones.

Aquesta tesi està dedicada al disseny d'algorismes de mineria de dades per fluxos de dades que evolucionen en el temps i per l'extracció d'arbres freqüents tancats. Primer ens ocupem de cadascuna d'aquestes tasques per separat i, a continuació, ens ocupem d'elles conjuntament, desenvolupant mètodes de classificació de fluxos de dades que contenen elements que són arbres. En el model de flux de dades, les dades arriben a gran velocitat, i els algorismes que els han de processar tenen limitacions estrictes de temps i espai. En la primera part d'aquesta tesi proposem i mostrem un marc per desenvolupar algorismes que aprenen de forma adaptativa dels fluxos de dades que canvien en el temps. Els nostres mètodes es basen en l'ús de mòduls detectors de canvi i estimadors en els llocs correctes. Proposem ADWIN, un algorisme de finestra lliscant adaptativa, per la detecció de canvi i manteniment d'estadístiques actualitzades, i proposem utilitzar-lo com a caixa negra substituint els comptadors en algorismes inicialment no dissenyats per a dades que varien en el temps. Com ADWIN té garanties teòriques de funcionament, això obre la possibilitat d'ampliar aquestes garanties als algorismes d'aprenentatge i de mineria de dades que l'usin. Provem la nostre metodologia amb diversos mètodes d'aprenentatge com el Naïve Bayes, partició, arbres de decisió i conjunt de classificadors. Construïm un marc experimental per fer mineria amb fluxos de dades que varien en el temps, basat en el programari MOA, similar al programari WEKA, de manera que sigui fàcil pels investigadors de realitzar-hi proves experimentals. Els arbres són grafs acíclics connectats i són estudiats com vincles en molts casos. En la segona part d'aquesta tesi, descrivim un estudi formal dels arbres des del punt de vista de mineria de dades basada en tancats. A més, presentem algorismes eficients per fer tests de subarbres i per fer mineria d'arbres freqüents tancats ordenats i no ordenats. S'inclou una anàlisi de l'extracció de regles d'associació de confiança plena dels conjunts d'arbres tancats, on hem trobat un fenomen interessant: les regles que la seva contrapart proposicional és no trivial, són sempre certes en els arbres a causa de la seva peculiar combinatòria. I finalment, usant aquests resultats en fluxos de dades evolutius i la mineria d'arbres tancats freqüents, hem presentat algorismes d'alt rendiment per fer mineria d'arbres freqüents tancats de manera adaptativa en fluxos de dades que evolucionen en el temps. Introduïm una metodologia general per identificar patrons tancats en un flux de dades, utilitzant la Teoria de Reticles de Galois. Usant aquesta metodologia, desenvolupem un algorisme incremental, un basat en finestra lliscant, i finalment un que troba arbres freqüents tancats de manera adaptativa en fluxos de dades. Finalment usem aquests mètodes per a desenvolupar mètodes de classificació per a fluxos de dades d'arbres. / This thesis is devoted to the design of data mining algorithms for evolving data streams and for the extraction of closed frequent trees. First, we deal with each of these tasks separately, and then we deal with them together, developing classification methods for data streams containing items that are trees. In the data stream model, data arrive at high speed, and the algorithms that must process them have very strict constraints of space and time. In the first part of this thesis we propose and illustrate a framework for developing algorithms that can adaptively learn from data streams that change over time. Our methods are based on using change detectors and estimator modules at the right places. We propose an adaptive sliding window algorithm ADWIN for detecting change and keeping updated statistics from a data stream, and use it as a black-box in place or counters or accumulators in algorithms initially not designed for drifting data. Since ADWIN has rigorous performance guarantees, this opens the possibility of extending such guarantees to learning and mining algorithms. We test our methodology with several learning methods as Naïve Bayes, clustering, decision trees and ensemble methods. We build an experimental framework for data stream mining with concept drift, based on the MOA framework, similar to WEKA, so that it will be easy for researchers to run experimental data stream benchmarks. Trees are connected acyclic graphs and they are studied as link-based structures in many cases. In the second part of this thesis, we describe a rather formal study of trees from the point of view of closure-based mining. Moreover, we present efficient algorithms for subtree testing and for mining ordered and unordered frequent closed trees. We include an analysis of the extraction of association rules of full confidence out of the closed sets of trees, and we have found there an interesting phenomenon: rules whose propositional counterpart is nontrivial are, however, always implicitly true in trees due to the peculiar combinatorics of the structures. And finally, using these results on evolving data streams mining and closed frequent tree mining, we present high performance algorithms for mining closed unlabeled rooted trees adaptively from data streams that change over time. We introduce a general methodology to identify closed patterns in a data stream, using Galois Lattice Theory. Using this methodology, we then develop an incremental one, a sliding-window based one, and finally one that mines closed trees adaptively from data streams. We use these methods to develop classification methods for tree data streams.

Gaia, la nova missió astromètrica de la ESA amb un llançament previst pel 2011, observarà més de mil milions d'estels i altres objectes amb una exactitud sense precedents. Els seus ambiciosos objectius desbanquen completament les missions rivals d'altres agències. Al final de la seva vida útil es generarà el major i més complert mapa tridimensional de la nostra Galàxia.Una missió com aquesta suposa grans esforços tecnològics i de disseny ja que caldrà detectar, seleccionar i mesurar centenars d'estels cada segon, per enviar-ne posteriorment les dades cap a la Terra -a més d'un milió i mig de quilòmetres. Hem centrat el treball d'aquesta tesi en aquesta vessant de la missió, proposant dissenys pels sistemes de gestió de dades, de telemetria científica, i de compressió de dades. El nostre objectiu final és fer possible la transmissió a l'estació terrestre d'aquesta immensa quantitat de dades generades pels instruments, tenint en compte la limitada capacitat del canal de comunicacions. Això requereix el disseny d'un sistema de compressió de dades sense pèrdues que ofereixi les millors relacions de compressió i garanteixi la integritat de les dades transmeses. Tot plegat suposa un gran repte pels mètodes de la teoria de la informació i pel disseny de sistemes de compressió de dades.Aquests aspectes tecnològics encara estaven per estudiar o bé només es disposava d'esborranys preliminars -ja que la missió mateixa estava en una etapa preliminar en quan varem començar aquesta tesi. Per tant, el nostre treball ha estat rebut amb entusiasme per part de científics i enginyers del projecte.En primer lloc hem revisat l'entorn operacional del nostre estudi, descrit a la primera part de la tesi. Això inclou els diversos sistemes de referència i les convencions que hem proposat per tal d'unificar les mesures, referències a dades i dissenys. Aquesta proposta s'ha utilitzat com a referència inicial en la missió i actualment altres científics l'estan ampliant i millorant. També hem recopilat les principals característiques de l'instrument astromètric (en el qual hem centrat el nostre estudi) i revisat les seves directrius operacionals, la qual cosa també s'ha tingut en compte en altres equips.A la segona part de la tesi descrivim la nostra proposta pel sistema de gestió de dades de la càrrega útil de Gaia, la qual ha estat utilitzada per presentar els requeriments científics als equips industrials i representa en sí mateixa una opció d'implementació viable (tot i que simplificada). En la següent part estudiem la telemetria científica, recopilant els camps de dades a generar pels instruments i proposant un esquema optimitzat de codificació i transmissió, el qual redueix la ocupació del canal de comunicacions i està preparat per incloure un sistema optimitzat de compressió de dades. Aquest darrer serà descrit a la quarta i última part de la tesi, on veurem com la nostra proposta compleix gairebé totalment els requeriments de compressió, arribant a duplicar les relacions de compressió ofertes pels millors sistemes estàndard. El nostre disseny representa la millor solució actualment disponible per Gaia i el seu rendiment ha estat assumit com a disseny base per altres equips.Cal dir que els resultats del nostre treball van més enllà de la publicació d'una memòria de tesi, complementant-la amb aplicacions de software que hem desenvolupat per ajudar-nos a dissenyar, optimitzar i verificar la operació dels sistemes aquí proposats. També cal indicar que la complexitat del nostre treball ha estat augmentada degut a la necessitat d'actualitzar-lo contínuament als canvis que la missió ha sofert en el seu disseny durant els cinc anys del doctorat. Per acabar, podem dir que estem satisfets amb els resultats del nostre treball, ja que la majoria han estat (o estan essent) tinguts en compte per molts equips involucrats en la missió i per la mateixa Agència Espacial Europea en el disseny final.

En aquesta tesi, proposem un nou mètode per a l'actualització consistent de bases de dades deductives. Donada una petició d'actualització, aquest mètode tradueix de forma automàtica aquesta petició en el conjunt de totes les possibles formes d'actualitzar la base de dades extensional de forma que la petició sigui satisfeta i que no es violi cap restricció d'integritat. Aquest nostre mètode està basat en un conjunt de regles que defineixen la diferència entre dos estats consecutius de la base de dades. Aquesta diferència es determina definint explícitament les insercions, esborrats i les modificacions que es poden induir com a conseqüència de l'aplicació d'una actualització a la base de dades. El mètode està basat en una extensió del procediment de resolució SLDNF. Sigui D una base de dades deductiva, A(D) la base de dades augmentada associada, U una petició inicial d'actualització i T un conjunt d'actualitzacions de fets bàsics. Direm que el conjunt T satisfà la petició d'actualització U i no viola cap restricció d'integritat de D si, utilitzant la resolució SLDNF, l'objectiu  U  ¬Ic té èxit amb el conjunt d'entrada A(D)  T. Així doncs, el mètode consistirà en fer tenir èxit a les derivacions SLDNF fracassades. Per a fer-ho, s'inclouran al conjunt T aquelles actualitzacions de fets bàsics que cal realitzar per tal de que la derivació assoleixi l'èxit. Les diferent formes com es pot assolir aquest èxit es corresponen a les diferents solucions a la petició d'actualització U. El mètode proposat es demostra que és correcte i complet. En aquest sentit, es garanteix que donada una petició d'actualització U, el mètode obté totes les possibles formes de satisfer aquesta petició i que, a la vegada, se satisfacin les restriccions d'integritat definides a la base de dades. A diferència d'altres mètodes, el nostre gestiona les modificacions de fets com un nou tipus d'actualització bàsic. Aquest nou tipus d'actualització, junt amb la demostració de correctesa i completesa, és una de les principals aportacions del nostre mètode respecte els mètodes apareguts recentment. La segona gran aportació del nostre mètode és el fet d'utilitzar tècniques per a millorar l'eficiència del procés de traducció de vistes i del procés de manteniment de restriccions d'integritat. Per a millorar l'eficiència del procés de manteniment de restriccions d'integritat, proposem una tècnica per a determinar l'ordre en què cal comprovar les restriccions d'integritat. Aquesta tècnica està basada en la generació en temps de compilació del anomenat Graf de Precedències, el qual estableix les relacions entre violadors i reparadors potencials d'aquestes restriccions. Aquest Graf és utilitzat en temps d'execució per a determinar l'ordre en què es comproven i reparen les restriccions d'integritat. Aquest ordre redueix el nombre de vegades que cada restricció d'integritat ha de ser comprovada (i reparada) després de reparar qualsevol altre restricció. Per a millorar l'eficiència del procés d'actualització de vistes, proposem fer una anàlisi de la petició d'actualització, del contingut de la base de dades i de les regles de la base de dades augmentada abans d'iniciar la traducció de la petició d'actualització U. Aquesta anàlisi té com a objectiu el minimitzar el nombre d'accessos al contingut de base de dades que cal realitzar per a traduir la petició d'actualització, i per altra banda, aquesta anàlisi també ha de permetre determinar quines alternatives no podran donar lloc a una traducció vàlida a la petició U, permetent així, considerar únicament aquelles alternatives que sí proporcionaran una traducció vàlida a U. / Deductive databases generalize relational databases by including not only base facts and integrity constraints, but also deductive rules. Several problems may arise when a deductive database is updated. The problems that are addressed in this thesis are those of integrity maintenance and view updating. Integrity maintenance is aimed to ensure that, after a database update, integrity constraints remain satisfied. When these integrity constraints are violated by some update, such violations must be repaired by performing additional updates. The second problem we deal with is view updating. In a deductive database, derived facts are not explicitly stored into the database and they are deduced from base facts using deductive rules. Therefore, requests to update view (or derived) facts must be appropriately translated into correct updates of the underlying base facts. There is a close relationship between updating a deductive database and maintaining integrity constraints because, in general, integrity constraints can only be violated when performing an update. For instance, updates of base facts obtained as a result of view updating could violate some integrity constraint. On the other hand, to repair an integrity constraint could require to solve the view update problem when integrity constraint may be defined by some derived predicate.In this thesis, we propose a method that deals satisfactorily and efficiently with both problems in an integrated way. In this sense, given an update request, our method automatically translates it into all possible ways of changing the extensional database such that the update request is satisfied and no integrity constraint is violated. Concretely, we formally define the proposed method and we prove its soundness and completeness. The method is sound and complete in the sense that it provides all possible ways to satisfy an update request and that each provided solution satisfies the update request and does not violate any integrity constraint. Moreover, to compare how our method extends previous work in the area, we have proposed a general framework that allows us to classify and to compare previous research in the field of view updating and integrity constraint maintenance. This framework is based on taking into account five relevant dimensions that participate into this process, i.e. the kind of update requests, the database schema considered, the problem addressed, the solutions obtained and the technique used to obtain these solutions. Efficiency issues are also addressed in our approach, either for integrity maintenance as well as for view updating.To perform integrity maintenance efficiently, we propose a technique for determining the order in which integrity constraints should be handled. This technique is based on the generation at compile time of a graph, the Precedence Graph, which states the relationships between potential violations and potential repairs of integrity constraints. This graph is used at run-time to determine the proper order to check and repair integrity constraints. This order reduces significantly the number of times that each integrity constraint needs to be reconsidered after any integrity constraint repair. To improve efficiency during view updating, we propose to perform an initial analysis of the update request, the database contents and the rules of the database. The purpose of this analysis is to minimize the number of accesses to the base facts needed to translate a view update request and to explore only relevant alternatives that may lead to valid solutions of the update request. Furthermore, a detailed comparison with respect to some methods for integrity maintenance that consider efficiency issues is also provided, showing several contributions of our approach.

En esta tesis se analiza el problema de la representación asociada a un conjunto sobre el que tenemos definida una distancia verificando el axioma del cuarto punto, realizando un estudio formal de los principales aspectos relacionados con este tipo de representaciones tales como una caracterización de las mismas tratando a través de ella las relaciones entre distancias ultramétricas y aditivas. En concreto, se estudia una estructura de variedad diferenciable sobre el conjunto de las distancias aditivas con configuración inferencia en árboles y confección de algoritmos de construcción de árboles aditivos.

El presente Ensayo jurídico constitucional, tiene como objetivos primordiales, el estudio, análisis y planteamientos teóricos y prácticos, sobre la que llamamos Avisión iusinformática@ de los derechos y libertades fundamentales, y enparticular, la del derecho a la intimidad, con incidencia en el derecho público administrativo y penal. A tales efectos, tomamos como punto de partida, la interpretación hermenéutica del Ensayo escrito en 1890 por Samuel Warren y LouisBrandeis, intitulado AThe Right to Privacy@, la ADeclaración Universal de Derechos Humanos de 10 de Diciembre de 1948"; luego, el análisis comparativo de las normas jurídicas internacionales ( El Pacto de San José, El Pacto de New York y la Resolución de la OCDE de 1980, sobre procesamiento de datos personales yderecho a la intimidad), las normas comunitarias europeas ( El Convenio de Roma sobre Derechos Humanos de 1950, El Convenio de Estrasburgo de 1981, la Directiva 95/46/CE y 97/66/CE, sobre tratamiento informatizado de datos personalesy derecho a la intimidad), las normas jurídicas estatales de protección de datos de carácter personal cuando han sido sometidos a procesamiento informático, electrónico o telemáticos por personas jurídicas, naturlaes, públicas o privadas(principalmente, La Ley alemana de 1977, la Ley Australiana AThe privacy and Data protecction Bill de 1994 -NSW-@ y la Ley Orgánica de España, sobre datos personales e intimidad --LORTAD de Octubre 29 de 1992--). Y, finalmente, la revisión puntual de las posiciones doctrinales y jurisprudenciales en España, Alemania, Colombia, Italia y Estados Unidos, sobre el llamado ANuevo Derecho@de la Alibertad informática@ o Aautodeterminación informática@, Aintimidad informática@, @habeas data@.ABSTRACTThe present constitutional juridical Rehearsal, has as primordial objectives, the study, analysis and theoretical and practical positions, on which call Avision iusinformática@ of the rights and fundamental freedoms, and in particular, the one of the right to the intimacy, with incidence in the administrative and penal public right.To such effects, we take as starting point, the interpretation hermeneutic of theRehearsal written in 1890 by Samuel Warren and Louis Brandeis, entitled AThe Right to Privacy@, the Universal Declaration of Human Rights of December 10 of 1948; then, the comparative analysis of the international juridical norms (San José=s Pact, The Pact of New York and the Resolution of the OECD of 1980, have morethan enough prosecution of personal data and right to the intimacy), the European Community norms (The Agreement of Rome has more than enough Human Rights of 1950, The Agreement of Strasbourg 1981, the Directive 95/46/CE and 97/66/CE, have more than enough computerized treatment of personal data and right to the intimacy), the state juridical norms of protection of data of personal character when they have been subjected to computer, electronic or telematic prosecution forjuridical people, naturlaes, public or private (mainly, The German Law of 1977, theAustralian Law AThe privacy and Dates protecction Bill of 1994 -NSW -@ and the Organic Law of Spain, about personal data and intimacy --LORTAD of October 29 of 1992--). And, finally, the punctual revision of the doctrinal positions andjurisprudence in Spain, Germany, Colombia, Italy and United States, on the call ANew Right@ of the ALibertad Informática@ --computer freedom-- (or computer self-determination, intimacy computer science, habeas data).

Uno de los mayores retos que debe ser afrontado por los diseñadores de micro-procesadores es el de mitigar la gran latencia de las instrucciones de carga de datos en registros. Esta tesis analiza una de las posibles alternativas para atacar dicho problema: predicción de direcciones y ejecución especulativa.Varios autores han comprobado que las direcciones efectivas calculadas por las instrucciones de carga son bastante predecibles. En primer lugar, hemos analizado a qué es debida dicha predictabilidad. Este estudio intenta establecer las estructuras típicas presentes en lenguajes de alto nivel que, al ser compiladas, generas instruciones de carga predecibles. También se analizan los predictores convencionales con el objetivo de determinar qué predictores son más adecuados para las típicas aplicaciones.El estudio continúa con la propuesta de nuevos predictores de direcciones que utilizan sus recursos de almacenamiento de forma más eficiente que los previos predictores. Los predictores alamacenan información respecto al comportamiento de las instrucciones de carga; sin embargo, los requisitos de las instrucciones predecibles son diferentes de los de las instrucciones no predecibles. Consecuentemente, se propone una organización de las tablas de predicción que considere la existencia de ambos tipos de instruciones. También se muestra que existe un cierto grado de redundnacia en las tablas de predicción de los predictores. Este estudio propoen organizar las tablas de predicción de forma que se reduzca dicha redundancia. Todas estas propuestas permiten reducir los requisitos de los predictores referentes a espacio de alamacenamiento, sin causar menoscabo en el rendimiento de los predictores.Posteriormente, se evalúa el impacto de la predicción de direcciones en el rendimiento de los processadores. Las evaluaciones asumen que las predicciones se utilizan para iniciar de forma especulativa accessos a memoria y para ejecutar de forma especulativa sus instrucciones dependientes. En caso de una predicción correcta, todo el trabajo realizado de forma especulativa puede considerarse como correcto; en caso de error de predicción, el tranajo realizado especulativamente debe ser descartado. El estudio se centra en diversos aspectos como la interacción entre predicción de direcciones y predicción de saltos, la implementación de mecanismods de verification, los mecanismos re recuperación en casos de errores de predicción y la influencia de varios parámetreos del procesador (el tamaño de la ventana de emisión de instrucciones, la latencia de la memora cache, y la anchura de emisión de instrucciones) en le impacto de la predicción de direcciones en el rendimiento de los procesadores.Finalmente, se han evaluado mechanismos de recuperación para el caso de errores de predicción de latencia. La predicción de latencia es una técnica de ejecución especulativa utilizada por los planificadores de alguncos procesadores superescalares para tratar las instrucciones de latencia variable (por ejemplo, las instrucciones de carga). Nuestras evaluaciones se centran en un mecanismo convencional de recuperación para errores de predicción de latencia y en una nueva propuesta. También se evalúan los mecanismos propuestos en el ámbito de predicción de direcciones. Se concluye con que éstos mecanismos representan una alternativa rentable a los mecanismos de recuperación convencionales utilizados para tratar los errores de predicción de direcciones. / Mitigating the effect of the large latency of load instructions is one of challenges of micro-processor designers. This thesis analyses one of the alternatives for tackling this problem: address prediction and speculative execution.Several authors have noticed that the effective addresses computed by the load instructions are quite predictable. First of all, we study why this predictability appears; our study tries to detect the high-level language structures that are compiled into predictable load instructions. We also analyse the conventional address predictors in order to determine which address predictors are most appropriate for the typical applications.Our study continues by proposing address predictors that use their storage structures more efficiently. Address predictors track history information of the load instructions; however, the requirements of the predictable instructions are different from the requirements of the unpredictable instructions. We then propose an organization of the prediction tables considering the existence of both kinds of instructions. We also show that there is a certain degree of redundancy in the prediction tables of the address predictors. We propose organizing the prediction tables in order to reduce this redundancy. These proposals allow us to reduce the area cost of the address predictors without impacting their performance.After that, we evaluate the impact of address prediction on processor performance. Our evaluations assume that address prediction is used to start speculatively some memory accesses and to execute speculatively their dependent instructions. On a correct prediction, all the speculative work is considered as correct; on a misprediction, the speculative work must be discarded. Our study is focused on several aspects such as the interaction of address prediction and branch prediction, the implementation of verification mechanisms, the recovery mechanism on address mispredictions, and the influence of several processor parameters (the issue-queue size, the cache latency and the issue width) on the performance impact of address prediction. Finally, we evaluate several recovery mechanisms for latency mispredictions. Latency prediction is a speculative technique used by the schedulers of some superscalar processors to deal with variable-latency instructions (for instance, load instructions). Our evaluations are focused on a conventional recovery mechanism for latency mispredictions and a new proposal. We also evaluate the proposed recovery mechanism in the scope of address prediction; we conclude that it represents a cost-effective alternative to the conventional recovery mechanisms used for address mispredictions.

El principal objetivo de esta tesis es ampliar el estudio de los esquemas externos en BDOO, en particular, su proceso de definición. Una nueva metodología de definición de esquemas externos que simplifica considerablemente dicho proceso y los resultados obtenidos es presentada. Se considera como referencia el entorno ANSI/SPARC. Los sistemas de definición del esquema conceptual y los esquemas externos están basados en un diccionario de datos.En BDOO, los esquemas externos pueden contener clases del esquema conceptual así como clases derivadas definidas a partir de clases previamente existentes (derivadas o no); las clases derivadas ofrecen vistas de la información contenida en las clases a partir de las que son definidas. La definición de clases derivadas es una cuestión importante en la definición de esquemas externos en BDOO. Por tanto, éste es el segundo tema de investigación. Dos de los problemas principales de la definición de clases derivadas son estudiados: La generación de identificadores para los objetos de las clases derivadas, y la transmisión de modificaciones entre los objetos de las clases derivadas y los de las clases a partir de los que son definidos.Uno de los usos principales de los esquemas externos es proporcionar un mecanismo que soporte la simulación de cambios del esquema. La información en los esquemas externos ha de ser derivada a partir del esquema conceptual; el tipo de cambios del esquema que pueden ser simulados usando esquemas externos es condicionado por este hecho. Por tanto, el tercer objetivo es presentar un mecanismo que soporte la simulación de un espectro más amplio de cambios en el esquema. Este mecanismo está basado en la definición de esquemas externos pero incorpora ampliaciones adicionales. Para proporcionar mayor flexibilidad en este área, proponemos la definición de clases derivadas que puedan contener información no derivada en su intensión y extensión. Cuando un esquema externo con información no derivada ha de ser definido, el esquema conceptual ha de ser modificado para incluir la información no derivada del nuevo esquema. Para evitar modificaciones innecesarias del esquema conceptual el uso de un entorno de prueba para la definición de esquemas externos temporales es propuesto. / The main target of this thesis is to broaden the study of external schemas in OODBs, in particular, the external schema definition process. A new external schema definition methodology that considerably simplifies the process of definition and the results obtained, is presented. The ANSI/SPARC framework is taken as a reference. The systems of conceptual and external schema definition are based on a data dictionary.In OODBs, external schemas can contain classes from the conceptual schema as well as derived classes defined from previously existing classes (derived or non-derived); derived classes offer views of the information contained in the classes from which they are defined. The definition of derived classes is an important issue in the definition of external schemas in OODBs. Therefore, the definition of derived classes is the second focus of research. Two of the main problems of defining derived classes are studied: the generation of identifiers for the objects of the derived classes; and the transmission of modifications between the objects of the derived classes and those of the classes from which they are defined. One of the main uses of external schemas is to provide a mechanism that supports the simulation of schema changes. Information in external schemas has to be derived from the conceptual schema; the kind of schema changes that can be simulated using external schemas is conditioned by this fact. Therefore, the third target is to present a mechanism that supports the simulation of a wider spectrum of schema changes. This mechanism is based on the definition of external schemas but incorporates some additional extensions. In order to provide more flexibility in this area, we propose the definition of derived classes that can contain non-derived information in their intension as well as in their extension: partially derived classes. When an external schema with non-derived information is to be defined, the conceptual schema has to be modified in order to include the non-derived information of the new schema. In order to avoid unnecessary modifications of the conceptual schema the use of a test environment for the definition of temporal external schemas is also proposed.

L'objectiu d'aquesta tesi ha estat Ia construcció d'un analitzador morfològic automatitzat de la llengua catalana.L'interès de l'anàlisi morfològica computacional recolza en el fet que en qualsevol de les aplicacions de la lingüística computacional cal un tractament del text en aquest sentit que redueixi el volum del diccionari i les tasques de manteniment, especialment quan es tracta de Ilengües altament flexives.La finalitat de l'analitzador morfològic és la segmentación dels textos en unitats rellevants per al seu posterior tractament sintàctic o semàntic i l'associació d'informació a aquestes unitats.L'analitzador que ens ocupa té una arquitectura modular i està basat en un autòmat d'estats finits omplint amb condicions. La modularitat del sistema garanteix la independència de les dades entre elles i de les dades respecte del procés.La pertinència d'un autòmat per realitzar el procès d'anàlisi recolza en la seva adeqüació per al reconeixement dels mots en el sentit esquerra-dreta i en el fet que en els mots podem definir uns components, arrels, sufixos i elements flexius, que presenten un comportament distribucional i combinatori regular.El disseny de l'analitzador consisteix en la definició de l'estratègia de segmentació dels mots, en l'agrupament dels segments resultants en models segons les seves característiques morfològiques i en la definición de regles que determinen lo combinatòria correcta dels mòduls. Les condicions de les regles permeten controlar la capacitat d'anàlisi.Les arrels, els sufixos i els elements flexius es troben emmagatzemats en diccionaris específics. Cada un d'aquests elements duu associat un model i els atributs morfològics corresponents.Els models representen un nivell superior d'organització del material lingüístic que permet representar el comportament homogeni en la flexió i en la derivació: totes Ies arrels amb un mateix comportament flexiu estan agrupades en un únic model i els sufixos i els elements de flexió que combinen amb un mateix model d'arrels es troben igualment agrupats en un únic model. L'autòmat concatena models, de manera que les combinacions de les arrels amb els sufixos flexius i derivatius no s'han d'especificar individualment sinò al model al qual pertanyen.La informació morfològica es pot assignar als models i/o als elements dels diccionaris, segons es vulgui generalitzar o particularitzar.L'estructura de l'autòmat ha estat definida tenint en compte tant les característiques de la llengua com la funcionalitat del disseny. L'esquema de l'analitzador es fonamenta en la definició dels estats. Així, s'han definit tres estats reconeixedors d'arrels verbals, corresponents o la primera, segona i tercera conjugació, i un estat reconeixedor de les arrels nominals i adjectives. D'aquests estats surten els models corresponents a la flexió com els models de sufixos derivatius. De l'estat que reconeix els sufixos derivatius surten també els models de la flexió.Es tracta d'un disseny general, en el sentit que s'ha realitzat sense tenir en compte cap aplicació en concret. Aquest fet ha permès definir criteris metodològics de validesa general així com avaluar les diferents opcions en Ia segmentació de les formes, en la definició de models i en la construcción de l'autòmat. Com a resultat d'aquesta investigación actualment es disposa d'un analitzador de la llengua catalana que, per cada mot, dóna la seva categoria morfològica, les subcategories associades i l'arrel a partir de la qual s'ha analitzat.L'analitzador permet l'anàlisi de qualsevol forma de la llengua catalana sempre que correspongui a un dels models de flexió definits. L'anàlisi d'una nova forma només requereix donar d'alta Ia seva arrel aI diccionari i assignar-li el model de flexió que li correspon. Les formes derivades es resolen habitualment amb atributs a l'arrel, encara que alguns derivats, pel seu elevat rendiment, es validen aIs models i per tant es generalitzen per a totes les seves entrades.Les aportacions d'aquest analitzador respecte d'altres sistemes d'anàlisi morfològica automatitzada són: a) La possibilitat de resoldre tant les formes flexives com les derivades, fet que permet reduir en gran manera el volum de les dades enmagatzemades als diccionaris; b) La doble possibilitat d'anàlisi i generació. A més d'analitzar els textos, el sistema permet generar totes les formes flexives i derivades a partir d'una determinada arrel; c) La possibilitat de definir metaregles que permeten l'anàlisi de seqüències de sufixos o bé de grups de sufixos; d) La capacitat d'associar informació lèxica i morfològica a les unitats de l'anàlisi; i e) La simultaneïtat del procés d'anàlisi i de filtratge dels resultats.Resten obertes línies d'investigació que en el present estudi han quedat només esbossades. En primer lloc, seria interessant fer més exhaustiu l'ús de metarregles, fet que requereix un estudi acurat de les seqüències així com de Ia comparació de sufixos. Segonament, seria interessant definir amb detall quin tipus d' información lèxica es pot associar als mots, en general o per a una determinada aplicació. Finalment caldria tractar la resolució de les formes compostes dels verbs i del perfet perifràstic.L'analitzador està escrit en FORTRAN i està implementat en un VAX-750. / The aim of this research has been the design and implementation of an automatic morphological analyzer of Catalan. The morphological analysis by computers is necessary in most applications of Computational Linguistics, especially when they deal with very non-flexive languages like Catalan, Spanish, French, Italian, etc.The purpose of this analyzer is segmentation of texts in units that can be useful in a further syntactic or semantic processing and morphological and logical information attachment. Modularity, both in data structures and programs, is one of its more important features. The analyzer is based on a finite states automaton augmented by conditions. The design of that analyzer requires deciding a strategy to segment the words, the definition of patterns of morphological behaviour, the attachment of a pattern to each segment and the definition of rules that determines the correct combinations of these patterns.The contributions of this morphological analyzer in front of other systems are: a) The treatment of derivation and inflexion that permits to reduce in a very important way the size of the dictionaries; b) The system allows both analysis and generation; c) The possibility to define meta-rules that make possible the analysis of sequences and groups of suffixes; d) The ability to put together morphological and lexical information.As a result of this research, now we have available a morphological analyzer or Catalan that gives, in the analysis of each word, its morphological category, its associated subcategories and its root.The system has been written in FORTRAN and is implemented in a VAX-750.

Aquesta tesi estudia la complexitat de les dades i el seu rol en la definició del comportament de les tècniques d'aprenentatge supervisat, i alhora explora la generació artificial de conjunts de dades mitjançant estimadors de complexitat. El treball s'ha construït sobre quatre principis que s'han succeït de manera natural. (1) La crítica de la metodologia actual utilitzada per la comunitat científica per avaluar el rendiment de nous sistemes d'aprenentatge ha desencadenat (2) l'interès per estimadors alternatius basats en l'anàlisi de la complexitat de les dades i el seu estudi. Ara bé, tant l'estat primerenc de les mesures de complexitat com la disponibilitat limitada de problemes del món real per fer el seu test han inspirat (3) la generació sintètica de problemes, la qual ha esdevingut l'eix central de la tesi, i (4) la proposta de fer servir estàndards artificials amb semblança als problemes reals. L'objectiu que es persegueix a llarg termini amb aquesta recerca és proporcionar als usuaris (1) unes directrius per escollir el sistema d'aprenentatge idoni per resoldre el seu problema i (2) una col•lecció de problemes per, o bé avaluar el rendiment dels sistemes d'aprenentatge, o bé provar les seves limitacions. / Esta tesis profundiza en el estudio de la complejidad de los datos y su papel en la definición del comportamiento de las técnicas de aprendizaje supervisado, a la vez que explora la generación artificial de conjuntos de datos mediante estimadores de complejidad. El trabajo se ha construido sobre cuatro pilares que se han sucedido de manera natural. (1) La crítica de la metodología actual utilizada por la comunidad científica para evaluar el rendimiento de nuevos sistemas de aprendizaje ha desatado (2) el interés por estimadores alternativos basados en el análisis de la complejidad de los datos y su estudio. Sin embargo, tanto el estado primerizo de las medidas de complejidad como la limitada disponibilidad de problemas del mundo real para su testeo han inspirado (3) la generación sintética de problemas, considerada el eje central de la tesis, y (4) la propuesta del uso de estándares artificiales con parecido a los problemas reales. El objetivo que se persigue a largo plazo con esta investigación es el de proporcionar a los usuarios (1) unas pautas pare escoger el sistema de aprendizaje más idóneo para resolver su problema y (2) una colección de problemas para evaluar el rendimiento de los sistemas de aprendizaje o probar sus limitaciones. / This thesis takes a close view of data complexity and its role shaping the behaviour of machine learning techniques in supervised learning and explores the generation of synthetic data sets through complexity estimates. The work has been built upon four principles which have naturally followed one another. (1) A critique about the current methodologies used by the machine learning community to evaluate the performance of new learners unleashes (2) the interest for alternative estimates based on the analysis of data complexity and its study. However, both the early stage of the complexity measures and the limited availability of real-world problems for testing inspire (3) the generation of synthetic problems, which becomes the backbone of this thesis, and (4) the proposal of artificial benchmarks resembling real-world problems. The ultimate goal of this research flow is, in the long run, to provide practitioners (1) with some guidelines to choose the most suitable learner given a problem and (2) with a collection of benchmarks to either assess the performance of the learners or test their limitations.