Skip to Main content Skip to Navigation
New interface
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [41 references]  Display  Hide  Download
Contributor : Slawomir Staworko Connect in order to contact the contributor
Submitted on : Thursday, April 5, 2012 - 10:48:56 PM
Last modification on : Friday, February 4, 2022 - 3:12:16 AM
Long-term archiving on: : Tuesday, December 13, 2016 - 7:08:01 PM


Files produced by the author(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. ⟨hal-00643097⟩



Record views


Files downloads