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 . 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.
propose learning of @math -contextual tree languages to infer queries for web wrappers @cite_20 . @math -contextual tree languages form a subclass of regular tree languages that allows to specify conditions on the nodes of the tree at depth up to @math and each condition involves exactly @math subsequent children of a node. Because only nodes at bounded depth can be inspected and the relative order among children is used, @math -contextual tree languages are incomparable with twig queries which can inspect nodes at arbitrary depths but ignore the relative order of nodes.
@cite_20
2126183407
This paper introduces a novel method for learning a wrapper for extraction of information from web pages, based upon (k,l)-contextual tree languages. It also introduces a method to learn good values of k and l based on a few positive and negative examples. Finally, it describes how the algorithm can be integrated in a tool for information extraction.