Minimization of Tree Pattern Queries

We investigate minimization of tree pattern queries that use the child relation, descendant relation, node labels, and wildcards. We prove that minimization for such tree patterns is complete for the second level of the polynomial hierarchy and thus solve a problem first attacked by Flesca, Furfaro, and Masciari in 2003. We first provide an example that shows that tree patterns cannot be minimized by deleting nodes. This example shows that the M-NR conjecture, which states that minimality of tree patterns is equivalent to their nonredundancy, is false. We then show how the example can be turned into a gadget that allows us to prove hardness. The paper will be presented at PODS 2016.

Authors

• Matthias Niewerth

Keywords

No keywords are indexed for this paper.