# Complete Subhedge Projection for Stepwise Hedge Automata +
## 10 Monadic Regular Queries and XPath
### Earliest Query Answering with Subhedge Projection  
A naive query evaluation algorithm for a hedge automaton with signature \(\Sigma\cup\{x\}\) receives an input hedge \(h\in\mathcal{H}_{\Sigma}\), guesses all possible positions of where to insert \(x\) into \(h\), and tests for all of them whether the annotated hedge obtained is accepted by \(A\). In a less naive manner, one inserts \(x\) only at those position where the current state has an outgoing \(x\) transition. All this can be improved if the hedge automaton under consideration supports selection, rejection, or projection states. In all cases, the algorithm has to buffer all binding candidates, that are not yet in a selection or rejection state. In the worst case it has to buffer the bindings to all positions. Therefore, the state space of the evaluator of monadic queries is no more finite. Selection and rejection states can be identified by adapting the earliest query answering algorithm from [21]. This can be made such that one obtains an ShA\({}^{1}\)\(A_{\epsilon(\mathbf{S})}\) with signature \(\Sigma\cup\{x\}\) depending on the schema. It should be noticed that automata used in [21] are dNwas instead of ShA\({}^{1}\)s, and that schemas are ignored there. The needed adaptations are therefore discussed in Appendix A. How to obtain an efficient query answering algorithm in streaming mode from \(A_{\epsilon(\mathbf{S})}\) is the main topic of [21]. This is the base algorithm that we will extend with subhedge projection for our experiments. In order to add congruence projection to the earliest query answering algorithm, we have to run the automaton \(A_{\epsilon(\mathbf{S})}^{\mathcal{H}^{\mathcal{H}^{\mathcal{H}^{\mathcal{H}^{ \mathcal{H}^{\mathcal{H}^{\mathcal{H}^{\mathcal{H}^{\mathcal{H}^{\mathcal{H}^{ \mathcal{H}^{\mathcal{H}^{\mathcal{H}^{\mathcal{H}^{\mathcal{H}^{\mathcal{H}}^{ \mathcal{H}}}}}}}}}}}}}}\). The earliest congruence projection for the XPath query self::list[child::item] is shown in Figure 23. It binds \(x\) in state 2D1 after having read a top-level list-element and then checks for the existence of a child element item, going into selection state 1D3 once it is found. All other children of the top-level list element are projected in state 2D3. For adding earliest query answering to self-no-change projection, we have to run the automaton \(A_{\epsilon(\mathbf{S})}^{\mathcal{H}^{\mathcal{H}^{\mathcal{H}^{\mathcal{H}^{ \mathcal{H}^{\mathcal{H}^{\mathcal{H}^{\mathcal{H}^{\mathcal{H}^{\mathcal{H}}^{ \mathcal{H}^{\mathcal{H}}}}}}}}}}}}\) instead of \(A_{\epsilon(\mathbf{S})}^{\mathcal{H}^{\mathcal{H}^{\mathcal{H}^{\mathcal{H} {\mathcal{H}^{\mathcal{H}{\mathcal{H}^{\mathcal{H}^{\mathcal{H}}^{\mathcal{H} {\mathcal{H}}^{\mathcal{H}^{\mathcal{H}}^{\mathcal{H}}}}}}}}}}}}\). We do not give the details, but claim for the present query that the projection power of both automaton is the same. Figure 22: The dSha for the XPath query self::list[child::item]. The selection position is indicated by \(x\). Fortunately, the soundness and completeness theorems for earliest membership testing with subhedge projection do only affect the constructions of these Sha's, but not how they are to be evaluated. However, there is one additional issue: Nested word prefixes cannot be considered as irrelevant for the subsequent subhedge, if the selection variable \(x\) can be bound there, even if the acceptance doesn't depend on where it will be bound. This is since the position of the binding is to be returned by any query answering algorithm. **Definition 15**. : _We call a prefix \(v\) binding irrelevant for \(L\) and \(S\) it there does not exist any hedge \(h\) containing \(x\) and suffix \(w\) such that \(v\cdot w\in nw(S)\) and \(v\cdot nw(h)\cdot w\in nw(L)\)._  
Our subhedge projecting evaluator can project only at subhedge irrelevant prefixes that are also binding irrelevant.