Consistency of injective tree patterns

Claire David 1 Nadime Francis 2 Filip Murlak 3
2 DAHU - Verification in databases
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
Abstract : Testing if an incomplete description of an XML document is consistent, that is, if it describes a real document conforming to the imposed schema, amounts to deciding if a given tree pattern can be matched injectively into a tree accepted by a fixed automaton. This problem can be solved in polynomial time for patterns that use the child relation and the sibling order, but do not use the descendant relation. For general patterns the problem is in NP, but no lower bound has been known so far. We show that the problem is NP-complete already for patterns using only child and descendant relations. The source of hardness turns out to be the interplay between these relations: for patterns using only descendant we give a polynomial algorithm. We also show that the algorithm can be adapted to patterns using descendant and following-sibling, but combining descendant and next-sibling leads to intractability.
Type de document :
Communication dans un congrès
Foundations of Software Technology and Theoretical Computer Science, Dec 2014, New Dehli, India. 2014, 〈http://www.fsttcs.org/〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01094596
Contributeur : Nadime Francis <>
Soumis le : jeudi 8 janvier 2015 - 14:04:22
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : jeudi 9 avril 2015 - 10:36:29

Fichier

25.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01094596, version 2

Citation

Claire David, Nadime Francis, Filip Murlak. Consistency of injective tree patterns. Foundations of Software Technology and Theoretical Computer Science, Dec 2014, New Dehli, India. 2014, 〈http://www.fsttcs.org/〉. 〈hal-01094596v2〉

Partager

Métriques

Consultations de la notice

220

Téléchargements de fichiers

71