Pendant la dernière décennie, le format de données XML est devenu l'un des principaux moyens de représentation et d'échange de données sur le Web. La détection de l'indépendance entre une requête et une mise à jour, qui a lieu en absence d'impact d'une mise à jour sur une requête, est un problème crucial pour la gestion efficace de tâches comme la maintenance des vues, le contrôle de concurrence et de sécurité. Cette thèse présente une nouvelle technique d'analyse statique pour détecter l'indépendance entre requête et mise à jour XML, dans le cas où les données sont typées par un schéma. La contribution de la thèse repose sur une notion de type plus riche que celle employée jusqu'ici dans la littérature. Au lieu de caractériser les éléments d'un document XML utiles ou touchés par une requête ou mise à jour en utilisant un ensemble d'étiquettes, ceux-ci sont caractérisés par un ensemble de chaînes d'étiquettes, correspondants aux chemins parcourus pendant l'évaluation de l'expression dans un document valide pour le schéma. L'analyse d'indépendance résulte du développement d'un système d'inférence de type pour les chaînes. Cette analyse précise soulève une question importante et difficile liés aux schémas récursifs: un ensemble infini de chaînes pouvant être inférées dans ce cas, est-il possible et comment se ramener à une analyse effective donc finie. Cette thèse présente donc une technique d'approximation correcte et complète assurant une analyse finie. L'analyse de cette technique a conduit à développer des algorithmes pour une implantation efficace de l'analyse, et de mener une large série de tests validant à la fois la qualité de l'approche et son efficacité.

In the last decade XML became one of the main standards for data storage and exchange on the Web. Detecting XML query-update independence is crucial to efficiently perform data management tasks, like those concerning view-maintenance, concurrency control, and security. This thesis presents a novel static analysis technique to detect XML query-update independence, in the presence of a schema. Rather than types, the presented system infers chains of types. Each chain represents a path that can be traversed on a valid document during query/update evaluation. The resulting independence analysis is precise, although it raises a challenging issue: recursive schemas may lead to infer infinitely many chains. This thesis presents a sound and complete approximation technique ensuring a finite analysis in any case, together with an efficient implementation performing the chain-based analysis in polynomial space and time.

Kernel patches are frequently released to fix security vulnerabilities and bugs. However, users and system administrators often delay installing these updates because they require a system reboot, which results in disruption of service and the loss of application state. Unfortunately, the longer an out-of-date system remains operational, the higher is the likelihood of a system being exploited. Approaches, such as dynamic patching and hot swapping, have been proposed for updating the kernel. All of them either limit the types of updates that are supported, or require significant programming effort to manage. We have designed a system that checkpoints application-visible state, updates the kernel, and restores the application state. By checkpointing high-level state, our system no longer depends on the precise implementation of a patch and can apply all backward compatible patches. The results show that updates to major kernel releases can be applied with minimal changes.

The topic of the dissertation is revision programming. It is a knowledge representation formalismfor describing constraints on databases, knowledge bases, and belief sets, and providing acomputational mechanism to enforce them. Constraints are represented by sets of revision rules.Revision rules could be quite complex and are usually in a form of conditions (for instance, ifthese elements are present and those elements are absent, then this element must be absent). Inaddition to being a logical constraint, a revision rule specify a preferred way to satisfy the constraint.Justified revisions semantics assigns to any database a set (possibly empty) of revisions.Each revision satisfies the constraints, and all deletions and additions of elements in a transitionfrom initial database to the revision are derived from revision rules.Revision programming and logic programming are closely related. We established an elegantembedding of revision programs into logic programs, which does not increase the size of a program.Initial database is used in transformation of a revision program into the corresponding logicprogram, but it is not represented in the logic program.The connection naturally led to extensions of revision programming formalism which correspondto existing extensions of logic programming. More specific, a disjunctive and a nestedversions of revision programming were introduced.Also, we studied annotated revision programs, which allow annotations like confidence factors,multiple experts, etc. Annotations were assumed to be elements of a complete infinitely distributivelattice. We proposed a justified revisions semantics for annotated revision programs which agreedwith intuitions.Next, we introduced definitions of well-founded semantics for revision programming. It assignsto a revision problem a single "intended" model which is computable in polynomial time.Finally, we extended syntax of revision problems by allowing variables and implemented translatorsof revision programs into logic programs and a grounder for revision programs. The implementationallows us to compute justified revisions using existing implementations of the stablemodel semantics for logic programs.

Kernel patches are frequently released to fix security vulnerabilities and bugs. However, users and system administrators often delay installing these updates because they require a system reboot, which results in disruption of service and the loss of application state. Unfortunately, the longer an out-of-date system remains operational, the higher is the likelihood of a system being exploited. Approaches, such as dynamic patching and hot swapping, have been proposed for updating the kernel. All of them either limit the types of updates that are supported, or require significant programming effort to manage. We have designed a system that checkpoints application-visible state, updates the kernel, and restores the application state. By checkpointing high-level state, our system no longer depends on the precise implementation of a patch and can apply all backward compatible patches. The results show that updates to major kernel releases can be applied with minimal changes.

Thesis advisor: Amy Hutton / While the implementation of new accounting standards requires significant firm resources, the literature is largely silent on how firms allocate resources to comply with new accounting standards. I investigate whether firms make information systems (IS) investments to comply because IS are the primary means through which firms’ economic activities are captured, aggregated, and summarized for managerial decision-making. I use a requirement that firms disclose factors that materially affect their internal controls to identify IS investments. I find that—despite the large direct and indirect costs of IS investments and alternatives to comply with GAAP changes—new accounting standards lead to significant IS investments for the firms most affected by the GAAP changes. Moreover, the IS investments improve firms’ internal information environments. The results suggest that the IS investments and IIE improvements extend beyond the scope of the GAAP changes. / Thesis (PhD) — Boston College, 2022. / Submitted to: Boston College. Carroll School of Management. / Discipline: Accounting.

Multi-core processors require a program to be decomposable into independent parts that can execute in parallel in order to scale performance with the number of cores. But parallel programming is hard especially when the program requires state, which many system programs use for optimization, such as for example a cache to reduce disk I/O. Most prevalent parallel programming models do not support a notion of state and require the programmer to synchronize state access manually, i.e., outside the realms of an associated optimizing compiler. This prevents the compiler to introduce parallelism automatically and requires the programmer to optimize the program manually. In this dissertation, we propose a programming language/compiler co-design to provide a new programming model for implicit parallel programming with state and a compiler that can optimize the program for a parallel execution. We define the notion of a stateful function along with their composition and control structures. An example implementation of a highly scalable server shows that stateful functions smoothly integrate into existing programming language concepts, such as object-oriented programming and programming with structs. Our programming model is also highly practical and allows to gradually adapt existing code bases. As a case study, we implemented a new data processing core for the Hadoop Map/Reduce system to overcome existing performance bottlenecks. Our lambda-calculus-based compiler automatically extracts parallelism without changing the program's semantics. We added further domain-specific semantic-preserving transformations that reduce I/O calls for microservice programs. The runtime format of a program is a dataflow graph that can be executed in parallel, performs concurrent I/O and allows for non-blocking live updates.

Ces dernières années ont été marquées par l’adoption en masse de XML comme format d’échange et de représentation des données stockées sur le web. Cette évolution s’est accompagnée du développement de langages pour l’interrogation et la manipulation des données XML et de la mise en œuvre de plusieurs systèmes pour le stockage et le traitement des ces dernières. Parmi ces systèmes, les moteurs mémoire centrale ont été développés pour faire face à des besoins spécifiques d’applications qui ne nécessitant pas les fonctionnalités avancées des SGBD traditionnels. Ces moteurs offrent les mêmes fonctionnalités que les systèmes traditionnels sauf que contrairement à ces derniers, ils nécessitent de charger entièrement les documents en mémoire centrale pour pouvoir les traiter. Par conséquent, ces systèmes sont limités quant à la taille des documents pouvant être traités. Dans cette thèse nous nous intéressons aux aspects liés à l’évolution des données XML et à la gestion de la dimension temporelle de celles-ci. Cette thèse comprend deux parties ayant comme objectif commun le développement de méthodes efficaces pour le traitement des documents XML volumineux en utilisant les moteurs mémoire centrale. Dans la première partie nous nous focalisons sur la mise à jour des documents XML statiques. Nous proposons une technique d’optimisation basée sur la projection XML et sur l’utilisation des schémas. La projection est une méthode qui a été proposée dans le cadre des requêtes afin de résoudre les limitations des moteurs mémoire centrale. Son utilisation pour le cas des mises à jour soulève de nouveaux problèmes liés notamment à la propagation des effets des mises à jour. La deuxième partie est consacrée à la construction et à la maintenance des documents temporels, toujours sous la contrainte d’espace. A cette contrainte s’ajoute la nécessité de générer des documents efficaces du point de vue du stockage. Notre contribution consiste en deux méthodes. La première méthode s’applique dans le cas général pour lequel aucune information n’est utilisée pour la construction des documents temporels. Cette méthode est conçue pour être réalisée en streaming et permet ainsi le traitement de document quasiment sans limite de taille. La deuxième méthode s’applique dans le cas où les changements sont spécifiés par des mises à jour. Elle utilise le paradigme de projection ce qui lui permet en outre de manipuler des documents volumineux de générer des documents temporels satisfaisant du point de vue du stockage. / The last decade has witnessed a rapid expansion of XML as a format for representing and exchanging data through the web. In order to follow this evolution, many languages have been proposed to query, update or transform XML documents. At the same time, a range set of systems allowing to store and process XML documents have been developed. Among these systems, main-memory engines are lightweight systems that are the favored choice for applications that do not require complex functionalities of traditional DBMS such as transaction management and secondary storage indexes. These engines require to loading the documents to be processed entirely into main-memory. Consequently, they suffer from space limitations and are not able to process quite large documents. In this thesis, we investigate issues related to the evolution of XML documents and to the management of the temporal dimension for XML. This thesis consists of two parts sharing the common goal of developing efficient techniques for processing large XML documents using main-memory engines. The first part investigates the optimization of update for static XML documents. We have developed a technique based on XML projection, a method that has been proposed to overcome the limitations of main-memory engines in the case of querying. We have devised for a new scenario for projection allowing the propagation of the updates effects. The second of the thesis investigates building and maintaining time-stamped XML documents under space limitations. Our contribution consists in two methods. The first method can be applied in the general case where no restriction is made on the evolution of the XML documents. This method is designed to be performed in streaming and allows thus processing large documents. The second method deals with the case where the changes are specified by updates. It is based on the projection paradigm which it allows it for processing large documents and for generating time-stamped documents satisfactory from the point of view of storage. We provide a means to comparing time-stamped wrt space occupancy.

One of the problems of real-life production scheduling is dynamics of manufacturing environments with new production demands and breaking machines during the schedule execution. Simple rescheduling from scratch in response to unexpected events occurring on the shop floor may require excessive computation time. Moreover, the recovered schedule may be prohibitively deviated from the ongoing schedule. This thesis reviews existing approaches in the field of dynamic scheduling and proposes techniques how to modify a schedule to accommodate disturbances such as resource failure, hot order arrival or order cancellation. The importance is put on the speed of suggested procedures as well as on a minimum modification from the original schedule. The scheduling model is motivated by the FlowOpt project, which is based on the Temporal Networks with Alternatives. The algorithms are written in the C# language.

XML has emerged as the standard data format for Internet-based business applications. In many bussiness settings, a relational database management system(RDBMS) will serve as the storage manager for data from XML documents. In such a system, once the XML data is shredded and loaded into the storage system, XML queries posed against these (now virtual) XML documents are processed by translating them as much as possible into SQL queries against the underlying relational storage. Clearly, in order to support full database functionalities over XML data, we must allow users not only to query but also to specify updates on XML documents. Today while the XML query language XQuery is being standardized by W3C, no syntax for updating XML documents is included in this language proposal as of now. In this thesis, we have developed techniques for supporting translation of XML updates on XML views of relational data into SQL updates on the underlying relations. These techniques are based on techniques for supporting translation of updates on object-based views of relational data into SQL updates on underlying relations cite{keller91}. The system has been implemented as a part of XML Management System, called Rainbow, that is being developed at the Worcester Polytechnic Institute (WPI). We have used XQuery as XML query language and Oracle as the backend relational store for implementation of the system. Experimental studies show that incremental XML updates supported by our system is a better choice than complete reload of XML documents under a variety of system settings.