Ent?te

Logo du LIFL

Depuis le 1er janvier 2015 le LIFL et le LAGIS forment le laboratoire CRIStAL

  1. Actualités

Thèse de

Emmanuel Filiot

lundi 13 octobre 2008
Bâtiment des thèses - Université de Lille1

Logique pour requêtes n-aires dans les arbres

Directeur de Thèse : Sophie Tison, Professeur, Université de Lille I
Co-encadrant : Jean-Marc Talbot, Professeur, Université d'Aix-Marseille I
Rapporteurs :
Luc Ségoufin, DR INRIA, ENS de Cachan
Giorgio Ghelli, Professeur, Università di Pisa Italy
Christof Loding, Professeur Assistant, RWTH Aachen Germany
Membres :
Jean-François Raskin, Professeur, Université Libre de Bruxelles Belgique
Laurence Duchien, Professeur, Université de Lille I

Beaucoup de données informatiques sont structurées de manière arborescente. Dans le contexte du Web, c'est le cas en particulier des données au format XML. De par sa généricité, ce format est rapidement devenu un standard pour l'échange et la sauvegarde d'informations. A l'instar des langages de requêtes pour les bases de données relationnelles, le besoin d'avoir des langages de requêtes pour les documents XML est devenu crucial. On distingue les requêtes unaires (sélection d'un ensemble de sous-parties d'un document) des requêtes n-aires (sélection d'un ensemble de n-uplets de sous-parties d'un document). Beaucoup de formalismes logiques pour les requêtes unaires ont été étudiés, en revanche, peu d'approches logiques existent pour les requêtes n-aires. Cette thèse étudie de manière fondamentale les requêtes n-aires, en proposant et en étudiant principalement deux formalismes logiques pour requêtes n-aires : une extension du paradigme navigationnel du standard W3C XPath au cas n-aire, appelée langage de composition, et une adaptation de la logique spatiale d'arbres TQL, introduite par Cardelli et Ghelli. Les questions de pouvoir d'expressivité, de complexité d'évaluation des requêtes ainsi que leur satisfiabilité sont abordées. L'étude du problème de satisfiabilité pour la logique TQL a nécessité l'introduction de nouveaux automates d'arbres avec tests globaux, dont l'étude est réalisée de manière indépendante.

Ours

UMR 8022 - Laboratoire d'Informatique Fondamentale de Lille - Copyright © 2012 Sophie TISON - Crédits & Mentions légales

Page respectant XHTML et CSS.

Pour tout commentaire / Comments and remarks : webmaster