This paper investigates the problem of reverse engineering, i.e., learning, select-project-join (SPJ) queries from a user-provided example set, containing positive and negative tuples. The goal is then to determine whether there exists a query returning all the positive tuples, but none of the negative tuples, and furthermore, to find such a query, if it exists. These are called the satisfiability and learning problems, respectively. The ability to solve these problems is an important step in simplifying the querying process for non-expert users.

This article investigates the problem of learning tree patterns that return nodes with a given set of labels, from example graphs provided by the user. Example graphs are annotated by the user as being either positive or negative . The goal is then to determine whether there exists a tree pattern returning tuples of nodes with the given labels in each of the positive examples, but in none of the negative examples, and furthermore, to find one such pattern if it exists. These are called the satisfiability and learning problems, respectively. This article thoroughly investigates the satisfiability and learning problems in a variety of settings. In particular, we consider example sets that (1) may contain only positive examples, or both positive and negative examples, (2) may contain directed or undirected graphs, and (3) may have multiple occurrences of labels or be uniquely labeled (to some degree). In addition, we consider tree patterns of different types that can allow, or prohibit, wildcard labeled nodes and descendant edges. We also consider two different semantics for mapping tree patterns to graphs. The complexity of satisfiability is determined for the different combinations of settings. For cases in which satisfiability is polynomial, it is also shown that learning is polynomial. (This is nontrivial as satisfying patterns may be exponential in size.) Finally, the minimal learning problem, that is, that of finding a minimal-sized satisfying pattern, is studied for cases in which satisfiability is polynomial.

This paper investigates the problem of learning tree patterns that return nodes with a given set of labels, from example graphs provided by the user. Example graphs are annotated by the user as being either positive or negative. The goal is then to determine whether there exists a tree pattern returning tuples of nodes with the given labels in each of the positive examples, but in none of the negative examples, and, furthermore, to find one such pattern if it exists. These are called the satisfiability and learning problems, respectively. This paper thoroughly investigates the satisfiability and learning problems in a variety of settings. In particular, we consider example sets that (1) may contain only positive examples, or both positive and negative examples, (2) may contain directed or undirected graphs, and (3) may have multiple occurrences of labels or be uniquely labeled (to some degree). In addition, we consider tree patterns of different types that can allow, or prohibit, wildcard labeled nodes and descendant edges. We also consider two different semantics for mapping tree patterns to graphs. The complexity of satisfiability is determined for the different combinations of settings. For cases in which satisfiability is polynomial, it is also shown that learning is polynomial (This is non-trivial as satisfying patterns may be exponential in size). Finally, the minimal learning problem, i.e., that of finding a minimal-sized satisfying pattern, is studied for cases in which satisfiability is polynomial.

Formulating an XPath query over an XML document is a difficult chore for a non-expert user. This paper introduces a novel approach to ease the querying process. Instead of specifying a query, the user simply marks positive examples χ+ of nodes that fit her information need. She may also mark negative examples χ− of undesirable nodes. A deductive method, to suggest additional nodes that will interest the user, is developed in this paper.

When a query is evaluated under bag semantics, each answer is returned as many times as it has derivations. Bag semantics has long been recognized as important, especially when aggregation functions will be applied to query results. This article is the first to focus on bag semantics for tree pattern queries. In particular, the problem of bag equivalence of a large class of tree pattern queries (which can be used to model XPath) is explored. The queries can contain unions, branching, label wildcards, the vertical child and descendant axes, the horizontal following and following-sibling axes, as well as positional (i.e., first and last) axes. Equivalence characterizations are provided, and their complexity is analyzed. As the descendant axis involves a recursive relationship, this article is also the first to address bag equivalence over recursive queries, in any setting.

When a query is evaluated under bag semantics, each answer is returned as many times as it has derivations. Bag semantics has long been recognized as important, especially when aggregation functions will be applied to query results. This paper is the first to focus on bag semantics for XPath queries. In particular, the problem of bag-equivalence of a large class of XPath queries (modeled as tree patterns) is explored. The queries can contain unions, branching, label wildcards, the vertical child and descendant axes, the horizontal following, following-sibling and immediately-following sibling axes, as well as positional (i.e., first and last) axes. Equivalence characterizations are provided, and their complexity is analyzed. As the descendent axis involves a recursive relationship, this paper is also the first to address bag equivalence over recursive queries, in any setting.