L’analyse statique est une tâche essentielle dans l’optimisation des requêtes et la vérification de la base de graphes RDF. Nous étudions des techniques d’analyse statique pour SPARQL, le langage standard pour l’interrogation des données du Web sémantique. Plus précisément, nous étudions le problème d’inclusion des requêtes et de l’analyse de l’indépendance entre les requêtes et la mise à jour de la base de graphes RDF.Nous sommes intéressés par le développement de techniques grâce à des réductions au problème de la satisfaisabilité de la logique.Nous nous traitons le problème d’inclusion des requêtes SPARQL en présence de l’opérateur OPTIONAL. L’optionalité est l’un des constructeurs les plus compliqués dans SPARQL et aussi celui qui rend ce langage plus expressif que les langages de requêtes classiques, comme SQL.Nous nous concentrons sur la classe de requêtes appelée "well-designed SPARQL", proposées dans la littérature comme un fragment du langage avec de bonnes propriétés en matière d’évaluation des requêtes incluent l’opération OPTIONAL. À ce jour, l’inclusion de requête a été testée à l’aide de différentes techniques: homomorphisme de graphes, bases de données canoniques, techniques de la théorie des automates et réduction au problème de la validité d’une logique. Dans cette thèse, nous utilisons la dernière technique pour tester l’inclusion des requêtes SPARQL avec OPTIONAL utilisant une logique expressive appelée «logique K». En utilisant cette technique, il est possible de régler le problème d’inclusion des requêtes pour plusieurs fragment de SPARQL, même en présence de schémas. Cette extensibilité n’est pas garantie par les autres méthodes.Nous montrons comment traduire a graphe RDF en un système de transitions, ainsi que une requête SPARQL en une formula K. Avec ces traductions, l’inclusion des requêtes dans SPARQL peut être réduite au test de la validité d’une formule logique. Un avantage de cette approche est d’ouvrir la voie pour des implémentations utilisant solveurs de satisfiabilité pour K.Nous présentons un banc d’essais de tests d’inclusion pour les requêtes SPARQL avec OPTIONAL. Nous avons effectué des expériences pour tester et comparer des solveurs d’inclusion de l’état de l’art.Nous présentons également un aperçu préliminaire du problème d’indépendance entre requête et mise à jour. Une requête est indépendante de la mise à jour lorsque l’exécution de la mise à jour ne modifie pas le résultat de la requête. Bien que ce problème ait été intensivement étudié pour des fragments de calcul relationnel, il n’existe pas de travaux pour le langage de requêtes standard pour le web sémantique. Nous proposons une définition de la notion de l’indépendance dans le contexte de SPARQL et nous établissons des premières pistes de analyse statique dans certains situations d’inclusion entre une requête et une mise à jour. / Static analysis is a core task in query optimization and knowledge base verification. We study static analysis techniques for SPARQL, the standard language for querying Semantic Web data. Specifically, we investigate the query containment problem and the query-update independence analysis. We are interested in developing techniques through reductions to the validity problem in logic.We address SPARQL query containment with optional matching. We focus on the class of well-designed SPARQL queries, proposed in the literature as a fragment of the language with good properties regarding query evaluation. SPARQL is interpreted over graphs, hence we encode it in a graph logic, specifically the modal logic K interpreted over label transition systems. We show that this logic is powerful enough to deal with query containment for the well-designed fragment of SPARQL. We show how to translate RDF graphs into transition systems and SPARQL queries into K-formulae. Therefore, query containment in SPARQL can be reduced to unsatisfiability in K.We also report on a preliminary overview of the SPARQL query-update problem. A query is independent of an update when the execution of the update does not affect the result of the query. Determining independence is especially useful in the contest of huge RDF repositories, where it permits to avoid expensive yet useless re-evaluation of queries. While this problem has been intensively studied for fragments of relational calculus, no works exist for the standard query language for the semantic web. We report on our investigations on how a notion of independence can be defined in the SPARQL context

Dans le contexte de la recherche d'information par le contenu visuel, lorsque l'utilisateur formule une requête visuelle, sa cible de recherche est rarement représentée par une image entière comme le suppose le paradigme classique de recherche par une image exemple. L'image ne doit pas être traitée comme une unité atomique, car elle est généralement constituée d'un ensemble composite de zones visuelles exprimant une certaine sémantique.<br /><br /> Un système de recherche d'information visuelle doit permettre à l'utilisateur de désigner d'une manière explicite la cible visuelle qu'il recherche se rapportant aux différentes composantes de l'image. Notre objectif au cours de ce travail a été de réfléchir à comment définir des clés de recherche visuelle permettant à l'utilisateur d'exprimer cette cible visuelle, de concevoir et d'implémenter efficacement les méthodes correspondantes.<br /><br /> Les contributions originales de cette thèse portent sur de nouvelles approches permettant de retrouver des images à partir de leurs différentes composantes visuelles selon deux paradigmes de recherche distincts.<br /><br /> Le premier paradigme est celui de la recherche par région exemple. Il consiste à retrouver les images comportant une partie d'image similaire à une partie visuelle requête. Pour ce paradigme, nous avons mis au point une approche de segmentation grossière en régions et de description fine de ces régions ensuite. Les régions grossières des images de la base, extraites par notre nouvel algorithme de segmentation non supervisée, représentent les composantes visuellement saillantes de chaque image. Cette décomposition permet à l'utilisateur de désigner séparément une région d'intérêt pour sa requête. La recherche de régions similaires dans les images de la base repose sur un nouveau descripteur de régions (ADCS). Il offre une caractérisation fine, compacte et adaptative de l'apparence photométrique des régions, afin de tenir compte de la spécificité d'une base de descripteurs de régions. Dans cette nouvelle approche, la segmentation est rapide et les régions extraites sont intuitives pour l'utilisateur. La finesse de description des régions améliore la similarité des régions retournées par rapport aux descripteurs existants, compte tenu de la fidélité accrue au contenu des régions.<br /><br /> Notre seconde contribution porte sur l'élaboration d'un nouveau paradigme de recherche d'images par composition logique de catégories de régions. Ce paradigme présente l'avantage d'apporter une solution au problème de la page zéro. Il permet d'atteindre les images, quand elles existent dans la base, qui se rapprochent de la représentation mentale de la cible visuelle de l'utilisateur. Ainsi aucune image ou région exemple n'est nécessaire au moment de la formulation de la requête. Ce paradigme repose sur la génération non-supervisée d'un thésaurus photométrique constitué par le résumé visuel des régions de la base. Pour formuler sa requête, l'utilisateur accède directement à ce résumé en disposant d'opérateurs de composition logique de ces différentes parties visuelles. Il est à noter qu'un item visuel dans ce résumé est un représentant d'une classe photométrique de régions. Les requêtes logiques sur le contenu des images s'apparentent à celles en recherche de texte. L'originalité de ce paradigme ouvre des perspectives riches pour de futurs travaux en recherche d'information visuelle.

Cette thèse présente les fondements théoriques et pratiques d'un système pour l'analyse statique de langages manipulant des documents et données XML. Le système s'appuie sur une logique temporelle de point fixe avec programmes inverses, dérivée du mu-calcul modal, dans laquelle les modèles sont des arbres finis. Cette logique est suffisamment expressive pour prendre en compte les langages réguliers d'arbres ainsi que la navigation multidirectionnelle dans les arbres, tout en ayant une complexité simplement exponentielle. Plus précisément, la décidabilité de cette logique est prouvée en temps 2^O(n) où n est la taille de la formule dont le statut de vérité est déterminé.<br /><br />Les principaux concepts de XML sont traduits linéairement dans cette logique. Ces concepts incluent la navigation et la sémantique de sélection de noeuds du langage de requêtes XPath, ainsi que les langages de schémas (incluant DTD et XML Schema). Grâce à ces traductions, les problèmes d'importance majeure dans les applications XML sont réduits à la satisfaisabilité de la logique. Ces problèmes incluent notamment l'inclusion, la satisfaisabilité, l'équivalence, l'intersection, le recouvrement des requêtes, en présence ou en l'absence de contraintes régulières d'arbres, et le typage statique d'une requête annotée.<br /><br />Un algorithme correct et complet pour décider la logique est proposé, accompagné d'une analyse détaillée de sa complexité computationnelle, et des techniques d'implantation cruciales pour la réalisation d'un solveur efficace en pratique. Des expérimentations avec l'implantation complète du système sont présentées. Le système apparaît efficace et utilisable en pratique sur plusieurs scénarios réalistes.<br /><br />La principale application de ce travail est une nouvelle classe d'analyseurs statiques pour les langages de programmation utilisant des requêtes XPath et des types réguliers d'arbres. De tels analyseurs permettent de s'assurer, au moment de la compilation, de propriétés importantes comme le typage correct des programmes ou leur optimisation, pour un traitement plus sûr et plus efficace des données XML.