Learning Twig and Path Queries

Abstract : We investigate the problem of learning XML queries, \emph{path} queries and \emph{twig} queries, from examples given by the user. A learning algorithm takes on the input a set of XML documents with nodes annotated by the user and returns a query that selects the nodes in a manner consistent with the annotation. We study two learning settings that differ with the types of annotations. In the first setting the user may only indicate \emph{required nodes} that the query must return. In the second, more general, setting, the user may also indicate \emph{forbidden nodes} that the query must not return. The query may or may not return any node with no annotation. We formalize what it means for a class of queries to be \emph{learnable}. One requirement is the existence of a learning algorithm that is \emph{sound} i.e., always returns a query consistent with the examples given by the user. Furthermore, the learning algorithm should be \emph{complete} i.e., able to produce every query with sufficiently rich examples. Other requirements involve tractability of the learning algorithm and its robustness to nonessential examples. We identify practical classes of Boolean and unary, path and twig queries that are learnable from positive examples. We also show that adding negative examples to the picture renders learning unfeasible.
Type de document :
Communication dans un congrès
International Conference on Database Theory (ICDT), Mar 2012, Berlin, Germany. 2012
Liste complète des métadonnées

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

Contributeur : Slawomir Staworko <>
Soumis le : jeudi 5 avril 2012 - 22:48:56
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : mardi 13 décembre 2016 - 19:08:01


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


  • HAL Id : hal-00643097, version 1



Slawomir Staworko, Piotr Wieczorek. Learning Twig and Path Queries. International Conference on Database Theory (ICDT), Mar 2012, Berlin, Germany. 2012. 〈hal-00643097〉



Consultations de la notice


Téléchargements de fichiers