En esta tesis, presentamos un nuevo enfoque para validar mappings entre esquemas de datos que permite al diseñador comprobar si el mapping satisface o no ciertas propiedades deseables. La respuesta que obtiene el diseñador no se limita a un simple valor booleano, sino que dependiendo del resultado de la comprobación obtendrá un ejemplo/contraejemplo que ilustre ese resultado, o bien se le indicará el conjunto de restricciones de integridad de los esquemas y formulas del mapping responsables de ese resultado. Una de las características principales de nuestro enfoque es que es capaz de tratar una clase muy expresiva de mappings y esquemas relacionales. En particular, nuestro enfoque es capaz de tratar con formulas de mapping consistentes en inclusiones y igualdades de consultas, además de permitir el uso de negaciones y comparaciones aritméticas tanto en las propias formulas del mapping como en las vistas definidas en los esquemas. Nuestro enfoque también permite tratar restricciones de integridad, las cuales pueden estar definidas no solo sobre las tablas sino también sobre las vistas de los esquemas. Dado que razonar sobre este tipo de mappings y esquemas es, desafortunadamente, indecidible, proponemos realizar un test de terminación previo a la validación del mapping. Si el test de terminación da una respuesta positiva, entonces podremos estar seguros de que la posterior comprobación de la propiedad deseable correspondiente terminará. Finalmente, también extendemos nuestro enfoque más allá del caso relacional y lo aplicamos al contexto de mappings entre esquemas XML. / In this thesis, we present a new approach to the validation of mappings between data schemas. It allows the designer to check whether the mapping satisfies certain desirable properties. The feedback that our approach provides to the designer is not only a Boolean answer, but either a (counter)example for the (un)satisfiability of the tested property, or the set of mapping assertions and schema constraints that are responsible for that (un)satisfiability. One of the main characteristics of our approach is that it is able to deal with a very expressive class of relational mapping scenarios; in particular, it is able to deal with mapping assertions in the form of query inclusions and query equalities, and it allows the use of negation and arithmetic comparisons in both the mapping assertions and the views of the schemas; it also allows for integrity constraints, which can be defined not only over the base relations but also in terms of the views. Since reasoning on the class of mapping scenarios that we consider is, unfortunately, undecidable, we propose to perform a termination test as a pre-validation step. If the answer of the test is positive, then checking the corresponding desirable property will terminate. We also go beyond the relational setting and study the application of our approach to the context of mappings between XML schemas.

Since the World Wide Web Consortium (W3C) has recommended XQuery as the standard XML query language, the interest in using existing relational technology to query the XML data has dramatically increased. The most significant challenge of the relational approach is how to fully support XQuery semantics in XQuery-to-SQL translation. To eliminate the implicit semantics of XQuery, an XQuery fragment must be defined with simple syntax and explicit semantics. XQ is proposed as an XQuery fragment to express XML queries. <br /><br /> In this thesis, XQ is intensively investigated. It is encoded by <em>System F</em>, a second-order lambda calculus with a considerable expressive power and a strong normalization property. Since XML data is defined as inductive data types, XML tree and XML forest, in <em>System F</em>, all basic XML operators in XQ have been successfully encoded. Also, the semantics of XQ are represented in <em>System F</em> where XQ's semantics environment is encoded by an <em>Environment</em> data type with the corresponding operators. The successful encoding of XQ by <em>System F</em> ensures the termination of XQ query evaluation. <br /><br /> Moreover, an extension of XQ by a new tree operator Xtree and a vertical Vfor clause is proposed in this thesis to express some <em>undefinable</em> XQ queries. It is demonstrated that this extension still allows XQ to retain its XQ-to-SQL translation property that ensures the polynomial evaluation time complexity, and its <em>System F</em> encodable property that ensures the termination of query evaluation.

Fine-grained access control for XML is about controlling access to XML documents at the granularity of individual elements or attributes. This thesis addresses two problems related to XML access controls. The first is efficient, secure evaluation of XPath expressions. We present a technique that secures path expressions by means of query modification, and we show that the query modification algorithm is correct under a language-independent semantics for secure query evaluation. The second problem is to provide a compact, yet useful, representation of the access matrix. Since determining a user's privilege directly from access control policies can be extremely inefficient, materializing the access matrix---the net effect of the access control policies---is a common approach to speed up the authorization decision making. The fine-grained nature of XML access controls, however, makes the space cost of matrix materialization a significant issue. We present a codebook-based technique that records access matrices compactly. Our experimental study shows that the codebook approach exhibits significant space savings over other storage schemes, such as the access control list and the compressed accessibility map. The solutions to the above two problems provide a foundation for the development of an efficient mechanism that enforces fine-grained access controls for XML databases in the cases of query access.

One of the major issues faced by Web applications is the management of evolving of data. In this thesis, we consider this problem and in particular the evolution of active documents. Active documents is a formalism describing the evolution of XML documents by activating Web services calls included in the document. It has already been used in the context of the management of distributed data \cite{axml}. The main contributions of this thesis are theoretical studies motivated by two systems for managing respectively stream applications and workflow applications. In a first contribution, we study the problem of view maintenance over active documents. The results served as the basis for an implementation of stream processors based on active documents called Axlog widgets. In a second one, we see active documents as the core of data centric workflows and consider various ways of expressing constraints on the evolution of documents. The implementation, called Axart, validated the approach of a data centric workflow system based on active documents. The hidden Web (also known as deep or invisible Web), that is, the partof the Web not directly accessible through hyperlinks, but through HTMLforms or Web services, is of great value, but difficult to exploit. Wediscuss a process for the fully automatic discovery, syntacticand semantic analysis, and querying of hidden-Web services. We proposefirst a general architecture that relies on a semi-structured warehouseof imprecise (probabilistic) content. We provide a detailed complexityanalysis of the underlying probabilistic tree model. We describe how wecan use a combination of heuristics and probing to understand thestructure of an HTML form. We present an original use of a supervisedmachine-learning method, namely conditional random fields,in an unsupervised manner, on an automatic, imperfect, andimprecise, annotation based on domain knowledge, in order to extractrelevant information from HTML result pages. So as to obtainsemantic relations between inputs and outputs of a hidden-Web service, weinvestigate the complexity of deriving a schema mapping between databaseinstances, solely relying on the presence of constants in the twoinstances. We finally describe a model for the semantic representationand intensional indexing of hidden-Web sources, and discuss how toprocess a user's high-level query using such descriptions.

Introduktionen av AJAX har möjliggjort skapandet av dynamiska webbapplikationer på Internet. Dessa dynamiska webbapplikationer bygger på att skicka data mellan klient och server med hjälp av asynkrona förfrågningar. Detta görs med hjälp av ett serialiseringsformat som används för att kompaktera data och möjliggöra kommunikation mellan olika programmeringsspråk. Binära serialiseringsformat har konsistent visat sig prestera bättre än de textbaserade alternativen på plattformar som tillåter binär transport av data. AJAX är en plattform som endast tillåter textbaserad transport av data. Detta arbete syftar till att jämföra prestandan av textbaserade och binära serialiseringsformat för AJAX med hjälp av bland annat round-trip time. Arbetet har utförts genom att skapa en webbapplikation som utför prestandamätningar med hjälp av olika datamängder med varierande storlek och innehåll. Resultaten visar att binära serialiseringsformat endast skulle kunna vara ett tänkbart alternativ när det rör sig om webbapplikationer som skickar mycket sifferdominant data.

This thesis discusses the differences between an automated and design centered layout process. The work has beenconducted at CBG Konsult AB, a service provider of multilingual solutions, translations and localization.The purpose with this work was to investigate some limitations and issues with the layout process involving the languagefamily XSL used for automated layout at CBG Konsult AB.

Software Defined Radio (SDR) is a conception of implementing radio functions in computer software, instead of having electronics performing the functions. This thesis aims to compare two different ways of implementing these functions, or waveforms. The Software Communications Architecture (SCA) is an open standard developed by the United States Department of Defense. It uses a CORBA interface environment to make waveform applications interoperable and platform independent. This method of developing SDR is compared to an open-source initiative going by the name GNU Radio. Two waveform applications are developed, one transmitter using SCA, and one receiver using GNU Radio. The analog radio interface is simulated using the sound cards of two regular PCs. The development is done using the C++ and Python programming languages. This thesis examines pros and cons of the two SDR methods, as well as performing studies of Software Defined Radio in general.

Since the World Wide Web Consortium (W3C) has recommended XQuery as the standard XML query language, the interest in using existing relational technology to query the XML data has dramatically increased. The most significant challenge of the relational approach is how to fully support XQuery semantics in XQuery-to-SQL translation. To eliminate the implicit semantics of XQuery, an XQuery fragment must be defined with simple syntax and explicit semantics. XQ is proposed as an XQuery fragment to express XML queries. <br /><br /> In this thesis, XQ is intensively investigated. It is encoded by <em>System F</em>, a second-order lambda calculus with a considerable expressive power and a strong normalization property. Since XML data is defined as inductive data types, XML tree and XML forest, in <em>System F</em>, all basic XML operators in XQ have been successfully encoded. Also, the semantics of XQ are represented in <em>System F</em> where XQ's semantics environment is encoded by an <em>Environment</em> data type with the corresponding operators. The successful encoding of XQ by <em>System F</em> ensures the termination of XQ query evaluation. <br /><br /> Moreover, an extension of XQ by a new tree operator Xtree and a vertical Vfor clause is proposed in this thesis to express some <em>undefinable</em> XQ queries. It is demonstrated that this extension still allows XQ to retain its XQ-to-SQL translation property that ensures the polynomial evaluation time complexity, and its <em>System F</em> encodable property that ensures the termination of query evaluation.

Fine-grained access control for XML is about controlling access to XML documents at the granularity of individual elements or attributes. This thesis addresses two problems related to XML access controls. The first is efficient, secure evaluation of XPath expressions. We present a technique that secures path expressions by means of query modification, and we show that the query modification algorithm is correct under a language-independent semantics for secure query evaluation. The second problem is to provide a compact, yet useful, representation of the access matrix. Since determining a user's privilege directly from access control policies can be extremely inefficient, materializing the access matrix---the net effect of the access control policies---is a common approach to speed up the authorization decision making. The fine-grained nature of XML access controls, however, makes the space cost of matrix materialization a significant issue. We present a codebook-based technique that records access matrices compactly. Our experimental study shows that the codebook approach exhibits significant space savings over other storage schemes, such as the access control list and the compressed accessibility map. The solutions to the above two problems provide a foundation for the development of an efficient mechanism that enforces fine-grained access controls for XML databases in the cases of query access.

While centralized query processing over collections of XML data stored at a single site is a well understood problem, centralized query evaluation techniques are inherently limited in their scalability when presented with large collections (or a single, large document) and heavy query workloads. In the context of relational query processing, similar scalability challenges have been overcome by partitioning data collections, distributing them across the sites of a distributed system, and then evaluating queries in a distributed fashion, usually in a way that ensures locality between (sub-)queries and their relevant data. This thesis presents a suite of query evaluation techniques for XML data that follow a similar approach to address the scalability problems encountered by XML query evaluation. Due to the significant differences in data and query models between relational and XML query processing, it is not possible to directly apply distributed query evaluation techniques designed for relational data to the XML scenario. Instead, new distributed query evaluation techniques need to be developed. Thus, in this thesis, an end-to-end solution to the scalability problems encountered by XML query processing is proposed. Based on a data partitioning model that supports both horizontal and vertical fragmentation steps (or any combination of the two), XML collections are fragmented and distributed across the sites of a distributed system. Then, a suite of distributed query evaluation strategies is proposed. These query evaluation techniques ensure locality between each fragment of the collection and the parts of the query corresponding to the data in this fragment. Special attention is paid to scalability and query performance, which is achieved by ensuring a high degree of parallelism during distributed query evaluation and by avoiding access to irrelevant portions of the data. For maximum flexibility, the suite of distributed query evaluation techniques proposed in this thesis provides several alternative approaches for evaluating a given query over a given distributed collection. Thus, to achieve the best performance, it is necessary to predict and compare the expected performance of each of these alternatives. In this work, this is accomplished through a query optimization technique based on a distribution-aware cost model. The same cost model is also used to fine-tune the way a collection is fragmented to the demands of the query workload evaluated over this collection. To evaluate the performance impact of the distributed query evaluation techniques proposed in this thesis, the techniques were implemented within a production-quality XML database system. Based on this implementation, a thorough experimental evaluation was performed. The results of this evaluation confirm that the distributed query evaluation techniques introduced here lead to significant improvements in query performance and scalability both when compared to centralized techniques and when compared to existing distributed query evaluation techniques.