Raisonnements standard et non-standard pour les systèmes décentralisés de gestion de données et de connaissances
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
Peer-to-Peer inference systems (P2PIS) are logic-based systems made of autonomous servers called peers. Each peer manages a knowledge base (BC) and can communicate with other peers through mappings in order to solve a global inference task. This thesis is composed of two parts. In the first one, we propose a fully decentralised algorithm for consequence finding based on linear deduction in propositional P2PIS and we state its communication and space/time complexity. Then, we point out that the notion of non-conservative extension of a BC is important to the P2PIS and we exhibit its relation with the problem of decentralized linear deduction. This is very important since it has connections with the privacy of a peer within a P2PIS and with the quality of service provided by a P2PIS. We therefore study the following tightly related problems: (i) deciding whether a P2PIS is a conservative extension of a given peer and (ii) computing the witnesses to the corruption of a given peer's KB within a P2PIS so that we can forbid it. The second part of the thesis is a direct application of P2PIS to the domain of peer data management systems (PDMS) for the Semantic Web. We provide a decentralized data model and associated algorithms for PDMS based on the DL-LITER description logic. Our approach relies on reducing query reformulation and consistency checking for DL-LITER into reasoning in propositional logic. This enables a straightforward deployment of DL-LITER PDMS on top of the propositional P2PIS presented in the first part of the thesis. We also show how to answer queries using views in DL-LITER in the centralized and decentralized cases.
Abstract FR:
Les systèmes d'inférence pair-à-pair (P2PIS) sont constitués de serveurs autonomes appelés pairs gérant chacun sa propre base de connaissances (BC) et pouvant communiquer entre eux via des mappings afin de réaliser une inférence particulière au niveau global du système. Dans la première partie de la thèse, nous proposons un algorithme totalement décentralisé de calcul de conséquences par déduction linéaire dans les P2PIS propositionnels et nous étudions sa complexité communicationnelle, en espace et en temps. Nous abordons ensuite la notion d'extension non conservative d'une BC dans les P2PIS et nous exhibons son lien théorique avec la déduction linéaire décentralisée. Cette notion est importante car elle est liée à la confidentialité des pairs et à la qualité de service offerte par le P2PIS. Nous étudions donc les problèmes de décider si un P2PIS est une extension conservative d'un pair donné et de calculer les témoins d'une possible corruption de la BC d'un pair de sorte à pouvoir l'empêcher. La deuxième partie de la thèse est une application directe des P2PIS au domaine des systèmes de gestion de données pair-à-pair (PDMS) pour le Web Sémantique. Nous définissons des PDMS basés sur la logique de description DL-LITER et nous fournissons les algorithmes nécessaires de test l'inconsistance et de réponse aux requêtes dans de tels systèmes. Notre approche repose sur les P2PIS propositionnels car nous réduisons les problèmes de la reformulation des requêtes et de test de l'inconsistance à des problèmes de calcul de conséquences en LP. Ce travail est enfin étendu à la gestion de données DL-LITER en termes de vues dans les cas de systèmes centralisés et décentralisés.