Learning XML Twig Queries
  We investigate the problem of learning XML queries, path queries and tree
pattern 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 required nodes that the query must
return. In the second, more general, setting, the user may also indicate
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 sound i.e., always returns a query consistent with the
examples given by the user. Furthermore, the learning algorithm should be
complete i.e., able to produce every query with a sufficiently rich example.
Other requirements involve tractability of learning and its robustness to
nonessential examples. We show that the classes of simple path queries and
path-subsumption-free tree queries are learnable from positive examples. The
learnability of the full class of tree pattern queries (and the full class of
path queries) remains an open question. We show also that adding negative
examples to the picture renders the learning unfeasible.
  Published in ICDT 2012, Berlin.
