O uso da XML (Extensible Markup Language) em aplicações envolvendo bancos de dados vem se consolidando nos últimos dois anos. Os principais sistemas de gerenciamento de banco de dados já incorporam essa tecnologia em suas mais recentes versões. Dentre diversas aplicações destaca-se a publicação de dados relacionais em visões XML. Diferentemente da XML, o Modelo Temporal de Versões (TVM) não apresenta suporte entre os bancos de dados atuais. Esse modelo, que une características temporais com o conceito de versão para projetar aplicações orientadas a objetos, precisa ser mapeado para ser adequadamente controlado em um SGBD (Sistema de Gerenciamento de Banco de Dados). Cumprida essa etapa, aplicações do TVM também podem gerar visões XML. Nesse trabalho é inicialmente apresentada uma forma de representar instâncias de aplicações do TVM em um formato XML. Os documentos definidos a partir desse formato de representação são utilizados como base para consultas. Em seguida, é proposta uma extensão de uma linguagem de consulta XML visando proporcionar recursos para a recuperação de informações temporais e de versão representadas em documentos XML. São definidas funções temporais e versionadas que são incorporadas à linguagem base. O funcionamento das funções e a especificação de consultas temporais versionadas são descritos em detalhes no decorrer do trabalho. Uma ferramenta que implementa a linguagem base é utilizada na realização de testes visando validar as novas funções. / The use of the XML in applications involving databases has grown in the last two years. Recent versions of the main database management systems already incorporate this technology. Publishing relational data in XML can be identified as one of the different applications of XML. The Temporal Version Model (TVM) has no support in current databases. This model matches temporal features with the version concept to project object-oriented applications and needs to be mapped to be managed in a DBMS (Database Management System). Once this mapping is achieved, TVM applications can also generate XML views. This work presents initially a way to represent TVM instances in a XML format. Thus, documents created following this representation may be used in queries. Afterwards, an extension of a XML query language is proposed, aiming to provide features for the retrieval of temporal and version information represented in XML documents. Temporal and version functions are defined and incorporated in a base language. The way functions are executed and the specification of temporal version queries are described in details. A tool that implements the base language is used to test the new functions, with the aim of validation.

O uso da XML (Extensible Markup Language) em aplicações envolvendo bancos de dados vem se consolidando nos últimos dois anos. Os principais sistemas de gerenciamento de banco de dados já incorporam essa tecnologia em suas mais recentes versões. Dentre diversas aplicações destaca-se a publicação de dados relacionais em visões XML. Diferentemente da XML, o Modelo Temporal de Versões (TVM) não apresenta suporte entre os bancos de dados atuais. Esse modelo, que une características temporais com o conceito de versão para projetar aplicações orientadas a objetos, precisa ser mapeado para ser adequadamente controlado em um SGBD (Sistema de Gerenciamento de Banco de Dados). Cumprida essa etapa, aplicações do TVM também podem gerar visões XML. Nesse trabalho é inicialmente apresentada uma forma de representar instâncias de aplicações do TVM em um formato XML. Os documentos definidos a partir desse formato de representação são utilizados como base para consultas. Em seguida, é proposta uma extensão de uma linguagem de consulta XML visando proporcionar recursos para a recuperação de informações temporais e de versão representadas em documentos XML. São definidas funções temporais e versionadas que são incorporadas à linguagem base. O funcionamento das funções e a especificação de consultas temporais versionadas são descritos em detalhes no decorrer do trabalho. Uma ferramenta que implementa a linguagem base é utilizada na realização de testes visando validar as novas funções. / The use of the XML in applications involving databases has grown in the last two years. Recent versions of the main database management systems already incorporate this technology. Publishing relational data in XML can be identified as one of the different applications of XML. The Temporal Version Model (TVM) has no support in current databases. This model matches temporal features with the version concept to project object-oriented applications and needs to be mapped to be managed in a DBMS (Database Management System). Once this mapping is achieved, TVM applications can also generate XML views. This work presents initially a way to represent TVM instances in a XML format. Thus, documents created following this representation may be used in queries. Afterwards, an extension of a XML query language is proposed, aiming to provide features for the retrieval of temporal and version information represented in XML documents. Temporal and version functions are defined and incorporated in a base language. The way functions are executed and the specification of temporal version queries are described in details. A tool that implements the base language is used to test the new functions, with the aim of validation.

O uso da XML (Extensible Markup Language) em aplicações envolvendo bancos de dados vem se consolidando nos últimos dois anos. Os principais sistemas de gerenciamento de banco de dados já incorporam essa tecnologia em suas mais recentes versões. Dentre diversas aplicações destaca-se a publicação de dados relacionais em visões XML. Diferentemente da XML, o Modelo Temporal de Versões (TVM) não apresenta suporte entre os bancos de dados atuais. Esse modelo, que une características temporais com o conceito de versão para projetar aplicações orientadas a objetos, precisa ser mapeado para ser adequadamente controlado em um SGBD (Sistema de Gerenciamento de Banco de Dados). Cumprida essa etapa, aplicações do TVM também podem gerar visões XML. Nesse trabalho é inicialmente apresentada uma forma de representar instâncias de aplicações do TVM em um formato XML. Os documentos definidos a partir desse formato de representação são utilizados como base para consultas. Em seguida, é proposta uma extensão de uma linguagem de consulta XML visando proporcionar recursos para a recuperação de informações temporais e de versão representadas em documentos XML. São definidas funções temporais e versionadas que são incorporadas à linguagem base. O funcionamento das funções e a especificação de consultas temporais versionadas são descritos em detalhes no decorrer do trabalho. Uma ferramenta que implementa a linguagem base é utilizada na realização de testes visando validar as novas funções. / The use of the XML in applications involving databases has grown in the last two years. Recent versions of the main database management systems already incorporate this technology. Publishing relational data in XML can be identified as one of the different applications of XML. The Temporal Version Model (TVM) has no support in current databases. This model matches temporal features with the version concept to project object-oriented applications and needs to be mapped to be managed in a DBMS (Database Management System). Once this mapping is achieved, TVM applications can also generate XML views. This work presents initially a way to represent TVM instances in a XML format. Thus, documents created following this representation may be used in queries. Afterwards, an extension of a XML query language is proposed, aiming to provide features for the retrieval of temporal and version information represented in XML documents. Temporal and version functions are defined and incorporated in a base language. The way functions are executed and the specification of temporal version queries are described in details. A tool that implements the base language is used to test the new functions, with the aim of validation.

The major goal of information integration is to provide efficient and easy-to-use access to multiple heterogeneous data sources with a single query. At the same time, one of the current trends is to use standard technologies for implementing solutions to complex software problems. In this dissertation, I used XML and XQuery as the standard technologies and have developed an extended projection algorithm to provide a solution to the information integration problem. In order to demonstrate my solution, I implemented a prototype mediation system called Omphalos based on XML related technologies. The dissertation describes the architecture of the system, its metadata, and the process it uses to answer queries. The system uses XQuery expressions (termed metaqueries) to capture complex mappings between global schemas and data source schemas. The system then applies these metaqueries in order to rewrite a user query on a virtual global database (representing the integrated view of the heterogeneous data sources) to a query (termed an outsourced query) on the real data sources. An extended XML document projection algorithm was developed to increase the efficiency of selecting the relevant subset of data from an individual data source to answer the user query. The system applies the projection algorithm to decompose an outsourced query into atomic queries which are each executed on a single data source. I also developed an algorithm to generate integrating queries, which the system uses to compose the answers from the atomic queries into a single answer to the original user query. I present a proof of both the extended XML document projection algorithm and the query integration algorithm. An analysis of the efficiency of the new extended algorithm is also presented. Finally I describe a collaborative schema-matching tool that was implemented to facilitate maintaining metadata.

Processing data streams with Quality-of-Service (QoS) guarantees is an emerging area in existing streaming applications. Although it is possible to negotiate the result quality and to reserve the required processing resources in advance, it remains a challenge to adapt the DSMS to data stream characteristics which are not known in advance or are difficult to obtain. Within this paper we present the second generation of our QStream DSMS which addresses the above challenge by using a real-time capable operating system environment for resource reservation and by applying an adaptation mechanism if the data stream characteristics change spontaneously.

Domain-specific query languages (DSQL) let users express custom business logic. Relational databases provide a limited set of options to execute business logic. Usually, stored procedures or a series of queries with some glue code. Both methods have drawbacks and often business logic is still executed on application side transferring large amounts of data between application and database, which is expensive. We translate a DSQL into a hybrid data-flow execution plan, containing relational operators mixed with procedural ones. A cost model is used to drive the translation towards an optimal mixture of relational and procedural plan operators.

<pre>The proliferation of digital data, driven by factors like social media, e-commerce, etc., has created an increasing demand for highly processed data at higher levels of fidelity, which puts increasing demands on modern data processing systems. In the past, data processing systems faced bottlenecks due to limited main memory availability. However, as main memory becomes more abundant, their optimization focus has shifted from disk I/O to optimized computation through techniques like compilation. This dissertation addresses several critical limitations within such compilation-based data processing systems.<br><br>In modern data analytics pipelines, combination of workloads from various paradigms, such as traditional DBMS and Machine Learning, is common. <br>These pipelines are typically managed by specialized systems designed for specific workload types. While these specialized systems optimize their individual performance, substantial performance loss occurs when they are combined to handle mixed workloads. This loss is mainly due to overheads at system boundaries, including data copying and format conversions, as well as the general inability to perform cross-system optimizations.<br><br>This dissertation tackles this problem in two angles. First, it proposes an efficient post-hoc integration of individual systems using generative programming via the construction of common intermediate layers. This approach preserves the best-of-breed performance of individual workloads while achieving state-of-the-art performance for combined workloads. Second, we introduce a high-level query language capable of expressing various workload types, acting as a general substrate to implement combined workloads. This allows the generation of optimized code for end-to-end workloads through<br>the construction of an intermediate representation (IR).<br><br>The dissertation then shifts focus to data processing systems used for incremental view maintenance (IVM). While existing IVM systems achieve high performance through compilation and novel algorithms, they have limitations in handling specific query classes. Notably, they are incapable of handling queries involving correlated nested aggregate subqueries. To address this, our work proposes a novel indexing scheme based on a new data structure and a corresponding set of algorithms that fully incrementalize such queries. This approach result in substantial asymptotic speedups and order-of-magnitude performance improvements for workloads of practical importance.<br><br>Finally, the dissertation explores efficient and expressive fixed-point computations, with a focus on Datalog--a language widely used for declarative program analysis. Although existing Datalog engines rely on compilation and specialized code generation to achieve performance, they lack the flexibility to support extensions required for complex program analysis. Our work introduces a new Datalog engine built using generative programming techniques that offers both flexibility and state-of-the-art performance through specialized code generation.</pre><p></p>

Daten werden noch immer groesstenteils in Dateien und nicht in Datenbanken gespeichert. Dieser Trend wird durch den Internetboom der 90er Jahre nur noch verstaerkt. Daraus ist das Forschungsgebiet der semistrukturierten Daten entstanden. Semistrukturierte Daten sind Daten, die meist in Dokumenten gespeichert sind und eine implizite und irregulaere Struktur aufweisen. HTML- oder BibTeX-Dateien oder in ASCII-Dateien gespeicherte Genomdaten sind Beispiele. Traditionelles Datenbankmanagement erfordert Design und sichert Deklarativitaet zu. Dies ist im Umfeld der semistrukturierten Daten nicht gegeben, ein flexiblerer Ansatz wird gebraucht. In dieser Arbeit wird ein neuer Ansatz des Abfragens semistrukturierter Daten praesentiert. Wir schlagen vor, semistrukturierte Daten durch eine Menge von partiellen Schemata zu beschreiben, anstatt zu versuchen, ein globales Schema zu definieren. Letzteres ist zwar geeignet, einen effizienten Zugriff auf Daten zu ermoeglichen; ein globales Schema fuer semistrukturierte Daten leidet aber zwangslaeufig an der Irregularitaet der Struktur der Daten. Wegen der vielen Ausnahmen vom intendierten Schema wird ein globales Schema schnell sehr gross und wenig repraesentativ. Damit wird dem Nutzer ein verzerrtes Bild ueber die Daten gegeben. Hingegen koennen partielle Schemata eher ein repraesentatives Bild eines Teils der Daten darstellen. Mit Hilfe statistischer Methoden kann die Guete eines partiellen Schemas bewertet werden, ebenso koennen irrelevante Teile der Datenbank identifiziert werden. Ein Datenbanksystem, das auf partiellen Schemata basiert, ist flexibler und reflektiert den Grad der Strukturierung auf vielen Ebenen. Seine Benutzbarkeit und seine Performanz steigen mit einem hoeheren Grad an Struktur und mit seiner Nutzungsdauer. Partielle Schemata koennen auf zwei Arten gewonnen werden. Erstens koennen sie durch einen Datenbankdesigner bereitgestellt werden. Es ist so gut wie unmoeglich, eine semistrukturierte Datenbank komplett zu modellieren, das Modellieren gewisser Teile ist jedoch denkbar. Zweitens koennen partielle Schemata aus Benutzeranfragen gewonnen werden, wenn nur die Anfragesprache entsprechend entworfen und definiert wird. Wir schlagen vor, eine Anfrage in einen ``Was''- und einen ``Wie''-Teil aufzuspalten. Der ``Was''-Teil wird durch partielle Schemata repraesentiert. Partielle Schemata beinhalten reiche semantische Konzepte, wie Variablendefinitionen und Pfadbeschreibungen, die an Konzepte aus Anfragesprachen angelehnt sind. Mit Variablendefinitionen koennen verschiedene Teile der Datenbank miteinander verbunden werden. Pfadbeschreibungen helfen, durch das Zulassen einer gewissen Unschaerfe, die Irregularitaet der Struktur der Daten zu verdecken. Das Finden von Stellen der Datenbank, die zu einem partiellen Schema passen, bildet die Grundlage fuer alle Arten von Anfragen. Im ``Wie''-Teil der Anfrage werden die gefundenen Stellen der Datenbank fuer die Antwort modifiziert. Dabei koennen Teile der gefundenen Entsprechungen des partiellen Schemas ausgeblendet werden oder auch die Struktur der Antwort voellig veraendert werden. Wir untersuchen die Ausdrucksstaerke unserer Anfragesprache, in dem wir einerseits die Operatoren der relationalen Algebra abbilden und andererseits das Abfragen von XML-Dokumenten demonstrieren. Wir stellen fest, dass das Finden der Entsprechungen eines Schemas (wir nennen ein partielles Schema in der Arbeit nur Schema) den aufwendigsten Teil der Anfragebearbeitung ausmacht. Wir verwenden eine weitere Abstraktionsebene, die der Constraint Satisfaction Probleme, um die Entsprechungen eines Schemas in einer Datenbank zu finden. Constraint Satisfaction Probleme bilden eine allgemeine Klasse von Suchproblemen. Fuer sie existieren bereits zahlreiche Optimierungsalgorithmen und -heuristiken. Die Grundidee besteht darin, Variablen mit zugehoerigen Domaenen einzufuehren und dann die Werte, die verschiedene Variablen gleichzeitig annehmen koennen, ueber Nebenbedingungen zu steuern. In unserem Ansatz wird das Schema in Variablen ueberfuehrt, die Domaenen werden aus der Datenbank gebildet. Nebenbedingungen ergeben sich aus den im Schema vorhandenen Praedikaten, Variablendefinitionen und Pfadbeschreibungen sowie aus der Graphstruktur des Schemas. Es werden zahlreiche Optimierungstechniken fuer Constraint Satisfaction Probleme in der Arbeit vorgestellt. Wir beweisen, dass die Entsprechungen eines Schemas in einer Datenbank ohne Suche und in polynomialer Zeit gefunden werden koennen, wenn das Schema ein Baum ist, keine Variablendefinitionen enthaelt und von der Anforderung der Injektivitaet einer Einbettung abgesehen wird. Zur Optimierung wird das Enthaltensein von Schemata herangezogen. Das Enthaltensein von Schemata kann auf zwei Weisen, je nach Richtung der Enthaltenseinsbeziehung, genutzt werden: Entweder kann der Suchraum fuer ein neues Schema reduziert werden oder es koennen die ersten passenden Stellen zu einem neuen Schema sofort praesentiert werden. Der gesamte Anfrageansatz wurde prototypisch zunaechst in einem Public-Domain Prolog System, spaeter im Constraintsystem ECLiPSe implementiert und mit Anfragen an XML-Dokumente getestet. Dabei wurden die Auswirkungen verschiedener Optimierungen getestet. Ausserdem wird eine grafische Benutzerschnittstelle zur Verfuegung gestellt. / Most of today's data is still stored in files rather than in databases. This fact has become even more evident with the growth of the World Wide Web in the 1990s. Because of that observation, the research area of semistructured data has evolved. Semistructured data is typically stored in documents and has an irregular, partial, and implicit structure. The thesis presents a new framework for querying semistructured data. Traditional database management requires design and ensures declarativity. The possibilities to design are limited in the field of semistructured data, thus, a more flexible approach is needed. We argue that semistructured data should be represented by a set of partial schemata rather than by one complete schema. Because of irregularities of the data, a complete schema would be very large and not representative. Instead, partial schemata can serve as good representations of parts of the data. While finding a complete schema turns out to be difficult, a database designer may be able to provide partial schemata for the database. Also, partial schemata can be extracted from user queries if the query language is designed appropriately. We suggest to split the notion of query into a ``What''- and a ``How''-part. Partial schemata represent the ``What''-part. They cover semantically richer concepts than database schemata traditionally do. Among these concepts are predicates, variable definitions, and path descriptions. Schemata can be used for query optimization, but they also give users hints on the content of the database. Finding the occurrences (matches) of such a schema forms the most important part of query execution. All queries of our approach, such as the focus query or the transformation query, are based on this matching. Query execution can be optimized using knowledge about containment relationships between different schemata. Our approach and the optimization techniques are conceptually modeled and implemented as a prototype on the basis of Constraint Satisfaction Problems (CSPs). CSPs form a general class of search problems for which many techniques and heuristics exist. A CSP consists of variables that have a domain associated to them. Constraints restrict the values that variables can simultaneously take. We transform the problem of finding the matches of a schema in a database to a CSP. We prove that under certain conditions the matches of a schema can be found without any search and in polynomial time. For optimization purposes the containment relationship between schemata is explored. We formulate a sufficient condition for schema containment and test it again using CSP techniques. The containment relationship can be used in two ways depending on the direction of the containment: It is either possible to reduce the search space when looking for matches of a schema, or it is possible to present the first few matches immediately without any search. Our approach has been implemented into the constraint system ECLiPSe and tested using XML documents.

Approved for public release; distribution is unlimited / Handheld devices have evolved significantly from mere simple organizers to more powerful handheld computers that are capable of network connectivity, giving it the ability to send e-mail, browse the World Wide Web, and query remote databases. However, handheld devices, because of its design philosophy, are limited in terms of size, memory, and processing power compared to desktop computers. This thesis investigates the use of Data Flow Query Language (DFQL) in querying local and remote databases from a handheld device. Creating Standard Query Language (SQL) queries can be a complex undertaking; and trying to create one on a handheld device with a small screen only adds to its complexity. However, by using DFQL, the user can submit queries with an easy to use graphical user interface. Although handheld devices are currently more powerful than earlier PCs, they still require applications with a small footprint, which is a limiting factor for software developed. This thesis will also investigate the best division of labor between handheld device and remote servers. / Sergeant, United States Army

Ce travail de thèse s'inscrit dans le cadre du projet < personnalisation des environnements informatiques pour l'apprentissage humain (EIAH) > financé par la Région Rhône-Alpes. La personnalisation des EIAH est essentiellement dépendante de la capacité à produire des traces pertinentes et exploitables des activités des apprenants interagissant avec un EIAH. Dans ce domaine, l'exploitation des traces relève explicitement plusieurs problématiques allant de sa représentation de manière normalisée et intelligible à son traitement et interprétation en temps différé ou en temps réel au moment même de l'apprentissage. La multiplication des pratiques et des usages des traces requiert des outils génériques pour soutenir leurs exploitations. L'objectif de cette thèse est de définir les fondements théoriques de tels outils génériques permettant l'exploitation des traces d'interaction. Ceci nous a amené à définir la notion de Systèmes à Base de Trace modélisées : une classe de systèmes à base de connaissances facilitant le raisonnement et l'exploitation des traces modélisées. L'approche théorique proposée pour construire de tels systèmes s'articule autour de deux contributions : (1) La définition d'un cadre conceptuel définissant les concepts, l'architecture et les services mobilisés par les SBT. (2) La définition d'un cadre formel pour les systèmes à base de traces modélisées. Plus précisément, la proposition d'un langage pour l'interrogation et la transformation de trace modélisées à base de règles permettant des évaluations ponctuelles et continues. La sémantique formelle de ce langage est définie sous forme d'une théorie des modèles et d'une théorie de point fixe, deux formalismes habituellement utilisés pour décrire la sémantique formelle des langages de représentation de connaissances / This thesis is funded by the Rhône-Alpes Region as a part of the project < Personalisation of Technology-Enhanced Learning (TEL) Systems >. Personalising TEL Systems is, above all, dependent on the capacity to produce relevant and exploitable traces of individual or collaborative learning activities. In this field, exploiting interaction traces addresses several problems ranging from its representation in a normalised and intelligible manner to its processing and interpretation in continuous way during the ongoing TEL activities. The proliferation of trace-based exploitations raises the need of generic tools to support their representation and exploitation. The main objective of this thesis is to define the theoretical foundations of such generic tools. To do that, we define the notion of Trace-Based System (TBS) as a kind of Knowledge-based system whose main source of knowledge is a set of trace of user-system interactions. This thesis investigates practical and theoretical issues related to TBS, covering the spectrum from concepts, services and architecture involved by such TBS (conceptual framework) to language design over declarative semantics (formal framework). The central topic of our framework is the development of a high-level trace transformation language supporting deductive rules as an abstraction and reasoning mechanism for traces. The declarative semantics for such language is defined by a (Tarski-style) model theory with accompanying fixpoint theory