Th. doct.--Inform. et réseaux--Paris--ENST, 1994. / Bibliogr. p. 145-151.

En la presente tesis nos enfocamos en el manejo de dos problemas diferentes pero relacionados que suelen aparecer en el conocimiento, especialmente en entornos colaborativos: inconsistencias e incoherencias. Inconsistencia es un problema clásico y ampliamente reconocido en la representación de conocimiento, el cual trae importantes consecuencias para los mecanismos cl asicos de inferencia. Incoherencia, por otra parte, ha recibido cada vez más atención desde el surgimiento de lenguajes ontológicos; la misma se relaciona con con- flictos en el conjunto de reglas ontol ogicas que hacen a tales reglas imposibles de satisfacer al mismo tiempo. En este trabajo formalizamos la noción de incoherencia en ontologías Datalog , que se encontraba ausente en la literatura, en t erminos de la satisfacibilidad del conjunto de restricciones en las mismas, y mostramos como bajo ciertas condiciones incoherencia puede llevar a ontologías Datalog inconsistentes.La contribución principal de este trabajo es el desarrollo de dos operadores noveles para la restauración tanto de la consistencia como la coherencia en ontologías Datalog . Los enfoques propuestos se basan en kernel contraction. En el primero de ellos la restauración se realiza mediante la aplicación de funciones de incisión que seleccionan fórmulas para remoción de los conjuntos incoherentes/inconsistentes mínimos encontrados en las ontologías. Tal operador trata los conflictos m nimos de manera local, sin tener en cuenta la relación (si es que existe) entre los diferentes conflictos m nimos. El otro enfoque, que puede ser visto como un enfoque global, tiene en cuenta tal relación mediante el agrupamiento de conflictos m nimos relacionados en nuevas estructuras llamadas clusters, mediante el uso de una relaci on de solapamiento. En esta disertaci on presentamos construcciones tanto para el enfoque local como el global, junto con las propiedades que se espera que los mismos satisfagan, expresadas a través de postulados. Finalmente, establecemos la relación entre las construcciones y las propiedades mediante el uso de teoremas de representación. Si bien la propuesta esta enfocada en la consolidación de ontologías Datalog , estos operadores pueden ser aplicados a otros tipos de lenguajes ontológicos, tales como las Lógicas Descriptivas, haciéndolos aptos para su uso en ambientes colaborativos como la Web Semántica. / In this thesis we focus on the management of two different but related problems that arise in knowledge, especially in collaborative environments: inconsistency and incoherence. Inconsistency is a classic, widely acknowledged issue in knowledge representation, with important consequences to classical reasoning mechanisms. Incoherence, on the other hand, has been increasingly received attention since the arousal of ontological languages; it is related to conflicts in the set of ontological rules that make such rules impossible to satisfy at the same time. In this work we formalize the notion of incoherence for Datalog+ ontologies, which was previously absent in the literature, in terms of satisfiability of sets of constraints, and show how under specific conditions incoherence leads to inconsistent Datalog+ ontologies. The main contribution of this work is the development of two novel approaches to restore both consistency and coherence in Datalog+ ontologies. The proposed approaches are based on kernel contraction. In the first one restoration is performed by the application of incision functions that select formulae to delete from the minimal incoherent/inconsistent sets encountered in the ontologies. Such operator treats minimal conflicts in a local manner, disregarding the relation (if any) among different minimal conflicts. The other approach, which can be seen as a global one, does acknowledge such relation by means of the grouping of related minimal conflicts in new structures called clusters, by means of an overlapping relation. We present constructions for both local and global consolidation operators, along with the properties expected to be satisfied by them, expressed through postulates. Finally, we establish the relation between the constructions and the properties by means of a representation theorems. Although this proposal is presented for Datalog+ ontologies consolidation, these operators can be applied to other types of ontological languages, such as Description Logics, making them apt to be used in collaborative environments like the Semantic Web.

Les bases de connaissances sont des bases de données déductives où la logique est utilisée pour représenter des connaissances de domaine sur des données existantes. Dans le cadre des règles existentielles, une base de connaissances est composée de deux couches : la couche de données qui représentent les connaissances factuelle et la couche ontologique qui incorpore des règles de déduction et des contraintes négatives. L’interrogation de données à l’aide des ontologies est la fonction de raisonnement principale dans ce contexte. Comme dans la logique classique, les contradictions posent un problème à l’interrogation car « d'une contradiction, on peut déduire ce qu'on veut (ex falso quodlibet) ».Récemment, des approches d’interrogation tolérantes aux incohérences ont été proposées pour faire face à ce problème dans le cadre des règles existentielles. Elles déploient des stratégies dites de réparation pour restaurer la cohérence. Cependant, ces approches sont parfois inintelligibles et peu intuitives pour l'utilisateur car elles mettent souvent en œuvre des stratégies de réparation complexes. Ce manque de compréhension peut réduire l’utilisabilité de ces approches car elles réduisent la confiance entre l'utilisateur et les systèmes qui les utilisent. Par conséquent, la problématique de recherche que nous considérons est comment rendre intelligible à l’utilisateur l’interrogation tolérantes aux incohérences. Pour répondre à cette question de recherche, nous proposons d’utiliser deux formes d’explication pour faciliter la compréhension des réponses retournées par une interrogation tolérante aux incohérences. La première est dite de niveau méta et la seconde de niveau objet. Ces deux types d’explication prennent la forme d'un dialogue entre l'utilisateur et le raisonneur au sujet des déductions retournées comme réponses à une requête donnée. Nous étudions ces explications dans le double cadre de l'argumentation fondée sur la logique et de la dialectique formelle, comme nous étudions leurs propriétés et leurs impacts sur les utilisateurs en termes de compréhension des résultats. / Knowledge bases are deductive databases where the machinery of logic is used to represent domain-specific and general-purpose knowledge over existing data. In the existential rules framework a knowledge base is composed of two layers: the data layer which represents the factual knowledge, and the ontological layer that incorporates rules of deduction and negative constraints. The main reasoning service in such framework is answering queries over the data layer by means of the ontological layer. As in classical logic, contradictions trivialize query answering since everything follows from a contradiction (ex falso quodlibet). Recently, inconsistency-tolerant approaches have been proposed to cope with such problem in the existential rules framework. They deploy repairing strategies on the knowledge base to restore consistency and overcome the problem of trivialization. However, these approaches are sometimes unintelligible and not straightforward for the end-user as they implement complex repairing strategies. This would jeopardize the trust relation between the user and the knowledge-based system. In this thesis we answer the research question: ``How do we make query answering intelligible to the end-user in presence of inconsistency?''. The answer that the thesis is built around is ``We use explanations to facilitate the understanding of query answering''. We propose meta-level and object-level dialectical explanations that take the form of a dialogue between the user and the reasoner about the entailment of a given query. We study these explanations in the framework of logic-based argumentation and dialectics and we study their properties and their impact on users.

With 92% of today’s browsers supporting WebAssembly the need for decompilers to discover malicious code is greater than ever. The introduction of the Datalog to C++ compiler Soufflé, in 2016, enables the implementation of effective Datalog-based decompilers. This thesis investigates if a Datalogbased approach to decompilation can be used to implement a WebAssembly decompiler. Such a decompiler is implemented and then evaluated in terms of decompilability, recompilabilty and semantic equivalence using randomly generated programs of various complexity. Each generated program is first decompiled, then recompiled if the decompilation was successful, and finally executed if the recompilation was successful. The results showed that the implementation can decompile all generated programs and that most of the decompiled programs are recompilable. However, only 70% of the lowest complexity programs maintained the output of the original program. As the complexity increased this percentage fell below 20%, a result of more complex programs being more likely to contain code structures that are not handled correctly. If the similarity of the decompiled programs were instead measured by recompiling the decompiled programs to WebAssembly and observing the number of instructions differing from the original WebAssembly binary the percentages were slightly more satisfying with the percentage of instructions differing ranging from 25% for the lowest complexity programs to 65% for the highest complexity programs. While the results are not distinct enough to draw the conclusion that a Datalog-based approach to decompilation is suitable for implementing a WebAssembly decompiler they instigate the need for further research on the topic, e.g. by supporting more WebAssembly instructions as well as supporting WebAssembly binaries compiled from other languages than C. / Idag stödjer 92% av alla webbläsare WebAssembly och behovet av dekompilatorer för att upptäcka skadlig kod är större än någonsin. Datalog-kompilatorn Soufflé som introducerades 2016 gjorde det möjligt att implementera effektiva Datalog-baserade dekompilatorer. Detta arbete undersöker om en Datalogbaserad dekompilator kan användas för att implementera en WebAssemblydekompilator. Detta genomförs genom att en Datalog-baserad WebAssemblydekompilator implementeras och sedan utvärderas i termer av dekompilerbarhet, återkompilerbarhet och semantisk ekvivalens med hjälp av slumpmässigt genererade program av varierande komplexitet. Varje genererat program dekompileras och kompileras sedan igen för att slutligen exekveras. Resultaten visade att dekompilatorn kunde dekompilera alla genererade program och att de flesta av de dekompilerade programmen var omkompilerbara. Däremot gav endast 70% av programmen med lägst komplexitet samma utdata som respektive ursprungsprogram. När komplexiteten ökade sjönk denna procentsats till under 20%, en följd av att program av en högre komplexitet i högre grad innehåller kodstrukturer som hanteras felaktigt. Om likheten mellan de dekompilerade programmen istället mättes genom att kompilera om de dekompilerade programmen till WebAssembly och titta på antalet instruktioner som skiljer sig från den ursprungliga WebAssembly-binären var resultaten något mer tillfredsställande med endast 25%’s skillnad för programmen med lägst komplexitet upp till 65%’s skillnad för programmen med högst komplexitet. Trots att resultaten inte är tillräckligt tydliga för att dra slutsatsen att en Datalog-baserad dekompilator är lämplig för att implementera en WebAssembly-dekompilator, tydliggör de behovet av vidare forskning på ämnet, t.ex genom att stödja fler WebAssembly-instruktioner samt genom att stödja WebAssembly-binärer kompilerade från andra språk än C.

We find an orientation of a tree with 20 vertices such that the corresponding fixed-template constraint satisfaction problem (CSP) is NP-complete, and prove that for every orientation of a tree with fewer vertices the corresponding CSP can be solved in polynomial time. We also compute the smallest tree that is NL-hard (assuming L≠NL), the smallest tree that cannot be solved by arc consistency, and the smallest tree that cannot be solved by Datalog. Our experimental results also support a conjecture of Bulín concerning a question of Hell, Nešetřil and Zhu, namely that ‘easy trees lack the ability to count’. Most proofs are computer-based and make use of the most recent universal-algebraic theory about the complexity of finite-domain CSPs. However, further ideas are required because of the huge number of orientations of trees. In particular, we use the well-known fact that it suffices to study orientations of trees that are cores and show how to efficiently decide whether a given orientation of a tree is a core using the arc-consistency procedure. Moreover, we present a method to generate orientations of trees that are cores that works well in practice. In this way we found interesting examples for the open research problem to classify finite-domain CSPs in NL.

A runtime file system checker protects file-system metadata integrity. It checks the consistency of file system update operations before they are committed to disk, thus preventing corrupted updates from reaching the disk. In this thesis, we describe our experiences with building Brunch, a runtime checker for an emerging Linux file system called Btrfs. Btrfs supports many modern file-system features that pose challenges in designing a robust checker. We find that the runtime consistency checks need to be expressed clearly so that they can be reasoned about and implemented reliably, and thus we propose writing the checks declaratively. This approach reduces the complexity of the checks, ensures their independence, and helps identify the correct abstractions in the checker. It also shows how the checker can be designed to handle arbitrary file system corruption. Our results show that runtime consistency checking is still viable for complex, modern file systems.

A runtime file system checker protects file-system metadata integrity. It checks the consistency of file system update operations before they are committed to disk, thus preventing corrupted updates from reaching the disk. In this thesis, we describe our experiences with building Brunch, a runtime checker for an emerging Linux file system called Btrfs. Btrfs supports many modern file-system features that pose challenges in designing a robust checker. We find that the runtime consistency checks need to be expressed clearly so that they can be reasoned about and implemented reliably, and thus we propose writing the checks declaratively. This approach reduces the complexity of the checks, ensures their independence, and helps identify the correct abstractions in the checker. It also shows how the checker can be designed to handle arbitrary file system corruption. Our results show that runtime consistency checking is still viable for complex, modern file systems.

Universiẗat, Diss., 2001--Bonn.

Notre but est de permettre à un utilisateur du Web d’organiser la gestionde ses données distribuées en place, c’est à dire sans l’obliger à centraliserses données chez un unique hôte. Par conséquent, notre système diffèrede Facebook et des autres systèmes centralisés, et propose une alternativepermettant aux utilisateurs de lancer leurs propres pairs sur leurs machinesgérant localement leurs données personnelles et collaborant éventuellementavec des services Web externes.Dans ma thèse, je présente Webdamlog, un langage dérivé de datalogpour la gestion de données et de connaissances distribuées. Le langage étenddatalog de plusieurs manières, principalement avec une nouvelle propriété ladélégation, autorisant les pairs à échanger non seulement des faits (les données)mais aussi des règles (la connaissance). J’ai ensuite mené une étude utilisateurpour démontrer l’utilisation du langage. Enfin je décris le moteur d’évaluationde Webdamlog qui étend un moteur d’évaluation de datalog distribué nomméBud, en ajoutant le support de la délégation et d’autres innovations tellesque la possibilité d’avoir des variables pour les noms de pairs et des relations.J’aborde de nouvelles techniques d’optimisation, notamment basées sur laprovenance des faits et des règles. Je présente des expérimentations quidémontrent que le coût du support des nouvelles propriétés de Webdamlogreste raisonnable même pour de gros volumes de données. Finalement, jeprésente l’implémentation d’un pair Webdamlog qui fournit l’environnementpour le moteur. En particulier, certains adaptateurs permettant aux pairsWebdamlog d’échanger des données avec d’autres pairs sur Internet. Pourillustrer l’utilisation de ces pairs, j’ai implémenté une application de partagede photos dans un réseau social en Webdamlog. / Our goal is to enable aWeb user to easily specify distributed data managementtasks in place, i.e. without centralizing the data to a single provider. Oursystem is therefore not a replacement for Facebook, or any centralized system,but an alternative that allows users to launch their own peers on their machinesprocessing their own local personal data, and possibly collaborating with Webservices.We introduce Webdamlog, a datalog-style language for managing distributeddata and knowledge. The language extends datalog in a numberof ways, notably with a novel feature, namely delegation, allowing peersto exchange not only facts but also rules. We present a user study thatdemonstrates the usability of the language. We describe a Webdamlog enginethat extends a distributed datalog engine, namely Bud, with the supportof delegation and of a number of other novelties of Webdamlog such as thepossibility to have variables denoting peers or relations. We mention noveloptimization techniques, notably one based on the provenance of facts andrules. We exhibit experiments that demonstrate that the rich features ofWebdamlog can be supported at reasonable cost and that the engine scales tolarge volumes of data. Finally, we discuss the implementation of a Webdamlogpeer system that provides an environment for the engine. In particular, a peersupports wrappers to exchange Webdamlog data with non-Webdamlog peers.We illustrate these peers by presenting a picture management applicationthat we used for demonstration purposes.

Datalog ist die relationale Variante der logischen Programmierung und ist eine Standard-Abfragesprache in der Datenbankentheorie geworden. Die Programmkomplexität von Datalog im bisherigen Hauptanwendungsgebiet, auf endlichen Strukturen, ist bekanntermassen in EXPTIME. Wir untersuchen die Komplexität von Datalog auf unendlichen Strukturen, motiviert durch mögliche Anwendungen von Datalog auf unendlichen Strukturen (z.B. linearen Ordnungen) im zeitlichen und räumlichen Schliessen, aber auch durch das aufkommende Interesse an unendlichen Strukturen bei verwandten theoretischen Problemen, wie Constraint Satisfaction Problems (CSP): Im Gegensatz zu endlichen Strukturen können Datalog-Berechnungen auf unendlichen Strukturen unendlich lange dauern, was zur Unentscheidbarkeit von Datalog auf unendlichen Strukturen führen kann. Aber auch in den entscheidbaren Fällen kann die Komplexität von Datalog auf unendlichen Strukturen beliebig hoch sein. Im Hinblick auf dieses Ergebnis widmen wir uns dann unendlichen Strukturen mit der niedrigsten Komplexität von Datalog: Wir zeigen, dass Datalog auf linearen Ordnungen (auch dichte und diskrete, mit oder ohne Konstanten und sogar gefärbte) und Baumordnungen EXPTIME-vollständig ist. Für die Bestimmung der oberen Schranke werden Werkzeuge für Datalog auf Ordnungen eingeführt: Ordnungstypen, Abstandstypen und typdisjunkte Programme. Die Typkonzepte liefern eine endliche Beschreibung der unendlichen Programmergebnisse und könnten auch für praktische Anwendungen von Interesse sein. Wir erzeugen spezielle typdisjunkte Programme, die sich ohne Rekursion lösen lassen. Ein Transfer unserer Methoden auf CSPs zeigt, dass CSPs auf unendlichen Strukturen mit beliebig hoher Zeitkomplexität vorkommen, wie Datalog. / Datalog is the relational variant of logic programming and has become a standard query language in database theory. The (program) complexity of datalog in its main context so far, on finite databases, is well known to be in EXPTIME. We research the complexity of datalog on infinite databases, motivated by possible applications of datalog to infinite structures (e.g. linear orders) in temporal and spatial reasoning on one hand and the upcoming interest in infinite structures in problems related to datalog, like constraint satisfaction problems: Unlike datalog on finite databases, on infinite structures the computations may take infinitely long, leading to the undecidability of datalog on some infinite structures. But even in the decidable cases datalog on infinite structures may have arbitrarily high complexity, and because of this result, we research some structures with the lowest complexity of datalog on infinite structures: Datalog on linear orders (also dense or discrete, with and without constants, even colored) and tree orders has EXPTIME-complete complexity. To achieve the upper bound on these structures, we introduce a tool set specialized for datalog on orders: Order types, distance types and type disjoint programs. The type concept yields a finite representation of the infinite program results, which could also be of interest for practical applications. We create special type disjoint versions of the programs allowing to solve datalog without the recursion inherent in each datalog program. A transfer of our methods shows that constraint satisfaction problems on infinite structures occur with arbitrarily high time complexity, like datalog.