Querying Regular Sets of XML Documents

Slawomir Staworko 1 Emmanuel Filiot 1 Jan Chomicki 2
1 MOSTRARE - Modeling Tree Structures, Machine Learning, and Information Extraction
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : We investigate the problem of querying (regular) sets of XML documents represented with tree automata and we consider $n$-ary tree automata queries whose expressive power captures MSO on trees. Because finite automata can represent infinite sets of documents, we propose the notions of {\em universal} and {\em existential} query answers, answers that are present resp. in all and some documents. We study complexity of query answering and show that computing existential query answers is in PTIME if we assume the arity of the query to be a fixed parameter. On the other hand, computing universal query answers is EXPTIME-complete, but we show that it is in PTIME if we assume that the query is fixed (data complexity). Finally, we argue that the framework captures problems central to many novel XML applications like querying inconsistent XML documents. In particular, we demonstrate how to use our framework to compute consistent query answers in XML documents that do not satisfy the schema. This solution significantly extends our previous results in this area.
Type de document :
Communication dans un congrès
International Workshop on Logic in Databases (LiD), May 2008, Rome, Italy. 2008
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

Contributeur : Slawomir Staworko <>
Soumis le : jeudi 24 avril 2008 - 10:45:39
Dernière modification le : jeudi 11 janvier 2018 - 01:49:32
Document(s) archivé(s) le : vendredi 28 septembre 2012 - 13:01:22


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00275491, version 1



Slawomir Staworko, Emmanuel Filiot, Jan Chomicki. Querying Regular Sets of XML Documents. International Workshop on Logic in Databases (LiD), May 2008, Rome, Italy. 2008. 〈inria-00275491〉



Consultations de la notice


Téléchargements de fichiers