**Subcase h = h' · h''.** Let $v' = nw(h')$ and $v'' = nw(h'')$ so $v = v' · v'' = nw(h)$. The following rule must have been applied:

$$ \frac{q \notin Q_{shp}^{\Delta} \qquad (q, \varepsilon) \xrightarrow{v'}^{str} \qquad (p, \sigma) \text{ wrt } \Delta \qquad (p, \sigma) \xrightarrow{v''}^{str} \qquad (q', \varepsilon) \text{ wrt } \Delta}{(q, \varepsilon) \xrightarrow{v', v''}^{str} \qquad (q', \varepsilon) \text{ wrt } \Delta} $$

Since $v'$ is a nested word, it follows that $\sigma = \varepsilon$ too. By induction hypothesis applied to the nested words $v'$ and $v''$ we get $(q, \varepsilon) \xrightarrow{v'}^{str} (p, \varepsilon)$ wrt $\Delta$ and $(p, \varepsilon) \xrightarrow{v''}^{str} (q', \varepsilon)$ wrt $\Delta$. Hence, we can apply the following rule:

$$ \frac{(q, \varepsilon) \xrightarrow{v'}^{str} (p, \varepsilon) \text{ wrt } \Delta \qquad (p, \varepsilon) \xrightarrow{v''}^{str} \qquad (q', \varepsilon) \text{ wrt } \Delta}{(q, \varepsilon) \xrightarrow{v', v''}^{str} \qquad (q', \varepsilon) \text{ wrt } \Delta} $$

This shows $(q, \varepsilon) \xrightarrow{v}^{str} (q', \varepsilon)$ as required.

**Subcases h = $\langle h' \rangle$ or h = a or h = $\varepsilon$.** Straightforward.

This ends the proofs of both directions. □

A streaming evaluator with subhedge projection for deterministic SHA$^↓$s A on hedges h can thus be obtained by computing the streaming transition relation with subhedge projection for A of $nw(h)$ starting with the initial configuration. This costs time at most $O(1)$ per letter of $nw(h)$, i.e. constant time per event of the stream.

### 9.3. Streaming Complexity of Earliest Membership with Subhedge Projection

By using streaming evaluators for SHA$^↓$s we can test membership earliest and with subhedge projection in streaming mode by running the SHA$^↓$ $A^{cgr}(S)_{e(S)}$.

**Corollary 7.** For any complete dSHAs $(\Sigma, Q, \Delta, I, F)$, $F \subseteq F_S \subseteq Q$, language $L = \mathcal{L}(A)$, and schema $S = \mathcal{L}(A[F/F_S])$, earliest membership with complete subhedge projection for L wrt S can be tested in streaming mode for any hedge $h \in S$ in time $O(|1|)$ per nonprojected letter of $nw(h)$ after a preprocessing time of $O(|A^{cgr}(S)_{e(S)}| + n^3d + n s)$, where d is the number of difference relations and s the number of safe subsets in states of $Q_{e(S)}^{cgr}(S)$. The space required is in $O(\text{depth}(h) + |A^{cgr}(S)_{e(S)}|)$.

**Proof.** By Theorem 5 the dSHA$^↓$ $A^{cgr}(S)_{e(S)}$ is earliest and sound and complete for subhedge projection. By Propositions 57 and 58 we can thus obtain a streaming membership tester with subhedge projection for a hedge $h \in S$ by running the streaming evaluator with subhedge projection of $A^{cgr}(S)_{e(S)}$ on the nested word $nw(h)$. Since this SHA$^↓$ is deterministic, the streaming evaluation can be done in time $O(|1|)$ per letter of $nw(h)$ after a preprocessing time of $O(|A^{cgr}(S)_{e(S)}| + n^3d + n s)$. □

As for safe-no-change projection, the exponential preprocessing time can again be avoided by creating the part of the SHA$^↓$ $A^{cgr}(S)_{e(S)}$ needed for the evaluation of the hedge on the fly. The size of the needed part is in $O(|h|)$. Hence, the space requirements can also be reduced to $O(|h|)$ which may be too much for large streams $nw(h)$. The needed part of $A^{cgr}(S)_{e(S)}$, however, may be much smaller than $|h|$. Furthermore, a stack of size depth(h) has to be maintained, but this dependence on h may be acceptable even for large streams $nw(h)$.
## 10. Monadic Regular Queries and XPath

We next consider the problem of how to answer monadic regular queries on hedges in an earliest manner and with subhedge projection. Each monadic query defines a set of positions for each input hedge. The XPath queries `self::list[child::item]`, for instance can be applied to the hedge `⟨list.⟨list⟩.⟨item⟩⟩.⟨list.⟨item⟩⟩` where it selects the position of the first top-most tree labeled by `list`, since it contains a child tree labeled by `item`. We identify positions of hedges by integers. For instance, the selected `list` element in the hedge above is identified by the integer 2. Therefore, the answer set of the above query on the above hedge is `{2}`. Note that monadic queries do not return any other information about the selected positions, in contrast to the subtree semantics of XPath in the official W3C standard.

Answering this query is more complicated than verifying whether the XPath filter `[self::list/child::item]` matches at the root of the first subtree of the hedge, since the answer set needs to be constructed too. Concerning memory consumption, alive answer candidates need to be buffered for monadic query answering. Therefore the memory consumption of streaming evaluators of monadic queries may grow linearly in the size of the stream, it the number of the alive candidates does.

### 10.1. Monadic Regular Queries

Monadic queries on hedges in $H_Σ$ can be identified with languages of annotated hedges in $H_{Σ \cup \{x\}}$ where $x \notin Σ$ in an arbitrarily fixed selection variable. A monadic query on hedges in $H_Σ$ can then be identified with the language of all annotated hedges in $H_{Σ \cup \{x\}}$, in which a single position got $x$-annotated and this position is selected by query.

Therefore, regular monadic queries on hedges in $H_Σ$ can be defined by nested regular expressions in $nRegExp_{Σ \cup \{x\}}$ or by a dSHA with the same signature. The regular XPath query `self::list[child::item]`, for instance, can be defined by following nested regular expression:

$$⟨list \cdot x \cdot \top \cdot ⟨ \cdot item \cdot \top \rangle \cdot \top⟩ \cdot \top$$

where $\top$ is like a wildcard accepting any hedge in $H_Σ$ without $x$, i.e., for some recursion variable $z \in V$:

$$\top = \mu z.(+_{a \in \Sigma} a + ⟨z⟩)^*$$

Note that the nested regular expression for the XPath filter `[self::list/child::item]` in $nRegExp_Σ$ can be obtained from that of the XPath query `self::list[child::item]` by removing the $x$. In addition, for any monadic query on hedges, we have to restrict the annotated hedges to be recognized by the language of the query such that exactly one position in each hedge is annotated by $x$. This can be done by intersection with the following nested regular expression $one_x$:

$$\mu z. (T.x.T + T.⟨z⟩.T)$$

The previous schema $[doc]$ for pattern matching has now to be changed from to $S = [doc_x] \cap [one_x]$ where $doc_x \in nRegExp_{Σ \cup \{x\}}$ is like doc but over the signature $Σ \cup \{x\}$. For the regular XPath query `self::list[child::item]` we obtain the dSHA in Fig. 22. The transition rules with the special letter $x$ indicate, where positions may be bound to the selection variable: $x$ can be bound only in state 2, that is in subtrees starting with a `list` element. The same automaton can be used to define the schema $S = [doc_x] \cap [one_x]$ by using the schema-final states $F_S = \{14, 20\}$ instead of the final states $F = \{20\}$. Indeed, we constructed the automaton by intersecting the automaton obtained from the XPath expression with the automata computed from the regular expressions $doc_x$ and $one_x$ for the schema. Note that 20 is a final state for the query (and the schema), while 14 is a sink state for the query (but not for the schema).
<figure><img src="image_47.png" /><figcaption>**Figure 22.** The dSHA for the XPath query `self::list[child::item]`. The selection position is indicated by *x*.</figcaption></figure>

## 10.2. Earliest Query Answering with Subhedge Projection

A naive query evaluation algorithm for a hedge automaton with signature $Σ ∪ \{x\}$ receives an input hedge $h ∈ H_Σ$, 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↓ $A_{e(S)}$ with signature $Σ ∪ \{x\}$ depending on the schema. It should be noticed that automata used in [21] are dNWAs instead of SHA↓s, and that schemas are ignored there. The needed adaptations are therefore discussed in Appendix N. How to obtain an efficient query answering algorithm in streaming mode from $A_{e(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_{e(S)}^{cgr}$. The earliest congruence projection for the XPath query `self::list[child::item]` is shown in Fig. 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_{e(S)}^{π}$. Instead of $A_{e(S)}^{cgr}$. We don't give the details, but claim for the present query that the projection power of both automaton is the same.

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 59.** We call a prefix $v$ binding irrelevant for L and S if 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. Given an dSHA $A$ and a set of schema final-states $F_S$, one can decide whether a prefix is subhedge irrelevant if the current state $q$ does accept
<figure><img src="image_48.png" /><figcaption>**Figure 23.** The earliest congruence projection $A^{cgr}([doc] \cap [one_x])_{e([doc] \cap [one_x])}$ for the dSHA A in Fig. 22 with $F_S = \{14,20\}$. It defines the query of the XPath self::list[child::item].</figcaption></figure>

hedges containing $x$ but can access some other state that is not safe for rejection and permits $x$-bindings. In ground Datalog, we can distinguish binding irrelevant states $q$ by imposing the following rules for all $q, q' \in Q$:

binding_irrelev(q) :- state(q), not binding_relev(q).

binding_relev(q) :- not bind_x(q), acc(q,q'), bind_x(q'), not rej(q').

Note in our example of the XPath query self::list[child::item] that state 2D3 of the dSHA$^↓$ $A^{cgr}([doc] \cap [one_x])_{e([doc] \cap [one_x])}$ in Fig. 23 is binding irrelevant, since $x$ must be bound on the top-level list element in state 2D1, so it cannot be bound on any list element below.

# 11. Experiments with Streaming XPath Evaluation

We compare experimentally three streaming evaluators for dSHA, for earliest monadic query answering, without subhedge projection, with safe-no-change projection, and with congruence projection.

## 11.1. Benchmark dSHA for XPath Queries

We start from dSHA defining monadic queries for the regular XPath queries A1-A8 from the XPathMark benchmark [7] that are given in Table 24. These XPath queries show most of the features of the regular fragment of XPath. In Table 25, we added 14 further XPath path queries that we found useful for testing too.

Deterministic SHAs for A1-A8 were provided earlier in [21]. For the other XPath queries we compiled them to dSHAs via nested regular expression.

In order to produce the input dSHAs for our evaluators, we intersect these automata with a dSHA for the schema $[doc'_x] \cap [one_x]$ where $doc'_x$ is the schema we use for hedge encodings of real-world XML documents with $x$ annotations. Thereby we could identify the schema final states $F_S$. We minimized and completed the result. Fig. 26 reports the size of the input dSHAs for our evaluators obtained by the above procedure. For each dSHA A, the size is given by two numbers size(n), the first for the overall size and the second for the number of states n.

For the input dSHA A of each query, we statically computed the whole $dSHA^↓_S A^{cgr}(S)_{e(S)}$ while using the necessary parts of the determinization algorithm from [16]. The size of the $dSHA^↓_S$ obtained and the number $d$ of difference relations are reported in Fig. 26 too. The biggest size is 2091(504) for the input dSHA for A8. The largest number of difference relations $d=24$ is also obtained for this query. So, indeed the size of these automata is much smaller than one might expect from a construction that is
<table><caption>**Figure 24.** Regular XPath queries A1-A8 from XPathMark collection.</caption><thead><tr><td>Query ID</td><td>XPath expression</td></tr></thead><tbody><tr><td>A1</td><td>/site/closed_auctions/closed_auction/annotation/description/ text/keyword</td></tr><tr><td>A2</td><td>//closed_auction//keyword</td></tr><tr><td>A3</td><td>/site/closed_auctions/closed_auction//keyword</td></tr><tr><td>A4</td><td>/site/closed_auctions/closed_auction[annotation/description/ text/keyword]/date</td></tr><tr><td>A5</td><td>/site/closed_auctions/closed_auction [descendant::keyword]/date</td></tr><tr><td>A6</td><td>/site/people/person[profile/gender and profile/age]/name</td></tr><tr><td>A7</td><td>/site/people/person[phone or homepage]/name</td></tr><tr><td>A8</td><td>/site/people/person[address and (phone or homepage) and (creditcard or profile)]/name</td></tr></tbody></table>

<table><caption>**Figure 25.** Additional regular XPath queries for XPathMark documents.</caption><tr><td>A0</td><td>/site</td></tr><tr><td>A1_0a</td><td>/site/*</td></tr><tr><td>A1_0b</td><td>/site/@*</td></tr><tr><td>A1_0c</td><td>/site//@*</td></tr><tr><td>A1_1a</td><td>//bidder/personref[starts-with(@person, 'person0')]</td></tr><tr><td>A1_1d</td><td>//bidder/personref[@person='person0']</td></tr><tr><td>A1_2</td><td>//person</td></tr><tr><td>A1_3</td><td>/site/regions/africa//@*</td></tr><tr><td>A1_4</td><td>/site/regions/africa/*</td></tr><tr><td>A1_5</td><td>/site/regions/*</td></tr><tr><td>A1_6</td><td>//closed_auction/annotation//keyword</td></tr><tr><td>A2_1</td><td>//closed_auction[descendant::keyword]</td></tr><tr><td>A4_0</td><td>/site/closed_auctions/closed_auction[annotation]/date</td></tr><tr><td>A4_1</td><td>/site[open_auctions]/closed_auctions</td></tr></table>

highly exponential in the worst case. However, the only query that we couldn't obtain its correspondent deterministic earliest congruence projection $A^{cgr}(S)_{e(S)}$ is A5.

The time for computing the earliest congruence projection took between 2.3 to 26 seconds.

We note that we have not yet computed the complete $dSHA↓_S$ statically for safe-no-change projection $A^{snc}$, pure congruence projection $A^{cgr}(S)$ and earliest query answering $A_{e(S)}$. We believe that these automata may become bigger than $A^{cgr}(S)_{e(S)}$ that we constructed in a single shot.

## 11.2. Streaming Evaluation Tool: AStream

We are using and developing the AStream tool for answering monadic dSHA queries on XML streams with schema restrictions. Version 1.01 of AStream was presented in [21] supports earliest query answering without projection. Given a dSHA A defining a monadic query, a set of schema final states $F_S$ and an XML stream $w$, it constructs on-the-fly the needed part of the $SHA↓_S A_{e(S)}$ while parsing $w$ and evaluating A on the hedge encoding $w$.

For the FCT conference version of the present paper [24], we enhanced AStream with safe-no-change projection. This leads to version AStream 2.01. It constructs the earliest safe-no-change projection $dSHA↓_S A^{snc}_{e(S)}$ on the fly while evaluating the monadic query defined by A on the hedge encoding the XML stream $w$. Subhedge projection can be switched on or off, in order to compare both versions without further implementation differences.

For this present journal version, we added earliest congruence projection and integrated it into AStream leading to AStream 3.0.

AStream 3.0 is different from the two previous versions in that the $dSHA↓_S A^{cgr}_{e(S)}$ is constructed statically and entirely, independently of the input hedge. We then use a generic earliest streaming evaluator for $SHA↓_S$ that rejects in rejection states, selects in selection
<table><thead><tr><th>Query ID</th><th>dSHA A size(n)</th><th>dSHA<sup>↓</sup> size(#state)</th><th>#diff-rel. d</th></tr></thead><tbody><tr><td>A1</td><td>482(68)</td><td>1296(324)</td><td>16</td></tr><tr><td>A2</td><td>224(42)</td><td>316(82)</td><td>7</td></tr><tr><td>A3</td><td>320(53)</td><td>662(156)</td><td>10</td></tr><tr><td>A4</td><td>629(74)</td><td>1651(404)</td><td>18</td></tr><tr><td>A5</td><td>438(63)</td><td>1226(269)</td><td>13</td></tr><tr><td>A6</td><td>675(76)</td><td>2090(500)</td><td>22</td></tr><tr><td>A7</td><td>394(59)</td><td>728(184)</td><td>12</td></tr><tr><td>A8</td><td>648(79)</td><td>2091(504)</td><td>24</td></tr><tr><td>A0</td><td>203(40)</td><td>158(44)</td><td>5</td></tr><tr><td>A1_0a</td><td>224(42)</td><td>145(44)</td><td>6</td></tr><tr><td>A1_0b</td><td>203(39)</td><td>68(23)</td><td>5</td></tr></tbody></table>

<table><caption>**Figure 26.** Overall size and number *n* of states of the input dSHA A for the query with schema-final states *F*<sub>S</sub>, the overall size and number of states of the SHA<sup>↓</sup> A<sup>e</sup><sub>S</sub> obtained by earliest congruence projection, and the number *d* its difference relations.</caption><thead><tr><th>Query ID</th><th>dSHA A size(n)</th><th>dSHA<sup>↓</sup> size(#state)</th><th>#diff-rel. d</th></tr></thead><tbody><tr><td>A1_0c</td><td>230(43)</td><td>238(62)</td><td>6</td></tr><tr><td>A1_1a</td><td>305(54)</td><td>384(101)</td><td>8</td></tr><tr><td>A1_1d</td><td>305(54)</td><td>382(101)</td><td>8</td></tr><tr><td>A1_2</td><td>194(39)</td><td>152(42)</td><td>5</td></tr><tr><td>A1_3</td><td>318(53)</td><td>672(159)</td><td>10</td></tr><tr><td>A1_4</td><td>312(52)</td><td>479(132)</td><td>10</td></tr><tr><td>A1_5</td><td>266(47)</td><td>293(84)</td><td>8</td></tr><tr><td>A1_6</td><td>265(47)</td><td>588(142)</td><td>9</td></tr><tr><td>A2_1</td><td>232(42)</td><td>295(78)</td><td>7</td></tr><tr><td>A4_0</td><td>392(59)</td><td>719(184)</td><td>12</td></tr><tr><td>A4_1</td><td>292(49)</td><td>287(78)</td><td>8</td></tr></tbody></table>

states, and projects in all subhedge projection states. This evaluator could also be run with A<sup>snc</sup><sub>e(S)</sub> or A<sub>e(S)</sub>, as long as these do not grow too big.

It should be noticed that A<sup>e</sup><sub>S</sub><sup>gr</sup> turned out to be nicely small for our whole benchmark, while the other dSHA<sup>↓</sup>S A<sup>snc</sup><sub>e(S)</sub> and A<sub>e(S)</sub> risk becoming bigger. As stated earlier, we did not construct these dSHA<sup>↓</sup>S so far for our benchmark queries. This is why we continued to run the earliest streaming with safe-no-change projection with AStream 2.01, while we used AStream 3.0 for earliest streaming with congruence projection.

All AStream versions rely on Java's abc-Datalog for computing the least fixed points of Datalog programs in a bottom-up manner. Datalog programs are needed for all logical reasoning: for computing subsets of states that are safe for rejection, selection, or subhedge projection on all levels. Also, the difference relations are computed based on Datalog. Note that earliest on-the-fly query evaluation requires running Datalog during query evaluation, while with a static approach for constructing dSHA<sup>↓</sup>S entirely, Datalog is only needed at preprocessing time during the automaton construction.

### 11.3. Evaluation Measures

We want to measure the time for running the three streaming query evaluators for all dSHAs obtained from the XPath expressions in the collection in Tables 24 and 25.

One advantage of the XPathMark benchmark is that it comes with a generator of XML documents to which the queries can be applied and that can be scaled in size. We created an XML document of size 1.1 GB, which is sufficiently large to make streaming mandatory. Our experiments show that the efficiency of query evaluation grows linearly with the size of the non-projected part of the XML document. This holds for each of our three evaluators. Therefore, measuring the time of the evaluator on XML documents of other sizes would not show any new insights, except that memory consumption remains moderate too.

The time gain of projection for a query *Q* is the percentage of time saved by projection during query evaluation when ignoring the pure document parsing time *t*<sub>parse</sub> seconds:

$$time-gain_{Q} = 100 * \left( 1 - \frac{t_{\text{noprojectq}} - t_{\text{parse}}}{t_{\text{projectq}} - t_{\text{parse}}} \right)$$

We can measure the time gain for earliest safe-no-change projection by AStream 2.01 and for earliest congruence projection by AStream 3.0, since projection can be switched off in both of them. The disadvantage of the time gain is that it depends on the details of the implementation.

The event gain is a better measure for the projection power. The parser sends a stream of needed events to the SHA<sup>↓</sup>, while ignoring parts of the input document that can be projected away. For this, it must always be informed by the automaton about what kind of
<table><thead><tr><th>Query ID</th><th>#answer</th><th>time in sec</th><th>time gain</th><th>event gain</th></tr></thead><tbody><tr><td>A1</td><td>38267</td><td>29.3</td><td>98.1%</td><td>98.9%</td></tr><tr><td>A2</td><td>117389</td><td>171.8</td><td>77.9%</td><td>81.1%</td></tr><tr><td>A3</td><td>117389</td><td>33.4</td><td>97.4%</td><td>97.8%</td></tr><tr><td>A4</td><td>24959</td><td>33.2</td><td>97.8%</td><td>98.9%</td></tr><tr><td>A5</td><td>50186</td><td></td><td></td><td></td></tr><tr><td>A6</td><td>30307</td><td>45.9</td><td>96.9%</td><td>98.2%</td></tr><tr><td>A7</td><td>179889</td><td>30.5</td><td>98.0%</td><td>98.7%</td></tr><tr><td>A8</td><td>67688</td><td>37.8</td><td>97.3%</td><td>98.7%</td></tr><tr><td>A0</td><td>1</td><td>21.3</td><td>99.1%</td><td>100.0%</td></tr><tr><td>A1_0a</td><td>6</td><td>15.2</td><td>99.9%</td><td>100.0%</td></tr><tr><td>A1_0b</td><td>0</td><td>0.0</td><td>100.0%</td><td>100.0%</td></tr></tbody></table>

<table><caption>**Figure 27.** Time gain and event gain by earliest congruence projection with AStream3.01 on a 1.1GB XPathMark stream.</caption><thead><tr><th>Query ID</th><th>#answer</th><th>time in sec</th><th>time gain</th><th>event gain</th></tr></thead><tbody><tr><td>A1_0c</td><td>3600816</td><td>226.6</td><td>72.9%</td><td>75.7%</td></tr><tr><td>A1_1a</td><td>2</td><td>187.8</td><td>78.1%</td><td>80.3%</td></tr><tr><td>A1_1d</td><td>2</td><td>217.3</td><td>74.8%</td><td>80.3%</td></tr><tr><td>A1_2</td><td>1062965</td><td>238.2</td><td>68.2%</td><td>76.0%</td></tr><tr><td>A1_3</td><td>25074</td><td>16.2</td><td>99.1%</td><td>99.8%</td></tr><tr><td>A1_4</td><td>5170</td><td>17.5</td><td>99.7%</td><td>100.0%</td></tr><tr><td>A1_5</td><td>6</td><td>14.3</td><td>100.0%</td><td>100.0%</td></tr><tr><td>A1_6</td><td>117389</td><td>188.7</td><td>75.4%</td><td>81.1%</td></tr><tr><td>A2_1</td><td>50186</td><td>199.7</td><td>76.5%</td><td>81.1%</td></tr><tr><td>A4_0</td><td>91650</td><td>21.8</td><td>99.0%</td><td>99.3%</td></tr><tr><td>A4_1</td><td>1</td><td>12.0</td><td>100.0%</td><td>100.0%</td></tr></tbody></table>

events can be projected in the current state. The event gain of projection $event-gain_Q$ is then the percentage of events that are recognized to be irrelevant and thus no more created by a projecting evaluator for query Q. One might expect that the time gain is always smaller than the event gain.

$$time-gain_Q \leq event-gain_Q$$

Indeed, this will be confirmed by our experiments. We believe that these discrepancies between these two measure indicate how much room remains for optimizing the implementation of an evaluator. In this way, we can be observe that some room for further optimizations AStream 3.0 still remains.

## 11.4. Experiments

We use Java's XMLStreamReader Interface v1.0 from javax.xml.stream package to parse and stream XML files in Scala. Parsing a 1.1 GB XML documents requires $t_{parse} = 15$ seconds, while querying it without projection took us in average $t_{noproject\_avg} = 752$ seconds, while varying from 600 to 900 seconds. The average processing time for 1 MB is thus 0.72 seconds. Once knowing this, one can predict the expected evaluation time from the size of the non-projected part of the XML document. It is:

$$event-gain_Q * 1100 * 0.72 \text{ seconds} + t_{parse} \text{ seconds}$$

Without projection, the parser generates 1,012,018,728 events for the 1.1GB XML document. This is the baseline for computing $event-gain_Q$ for all queries Q.

We ran AStream with Scala v2.13.3, on a machine with the operating system Ubuntu 20.04.06 LTS (64-bit). The machine is Dell Precision-7750 machine, equipped with an Intel® Core™ i7-10875H CPU @ 2.30GHz × 16 and 32 GB of RAM.

### 11.4.1. Earliest Congruence Projection

We present the measures of our evaluator with the earliest congruence projection in Fig. 27. The event gain is high, varying between 75.7% for A1_0c to 100% for A0, A1_0a, A1_0b, A1_4, A1_5, and A4_1. The event gain for queries without descendant axis is above 98.2%. For these queries, all subtrees that are not on the main path of the query can be projected away. In particular, only subtrees until a fixed depth have to be inspected. These are the queries A1, A4, A6-A8 and A4_0 and the queries with event gain 100% listed above. The time gain for all these queries is a little smaller than the event gain but still above 98.2%.

We next consider the second type of queries having the descendant axis, specifically A2, A1_0c, A1_1a, A1_1d, A1_2, A1_6, and A2_1. Intuitively, a lower event gain is expected in these cases because subhedge projection with the descendant axis cannot directly exclude
<table><caption>**Figure 28.** Time gain for earliest safe-no-change and earliest congruence projection, and the event gain of earliest congruence projection.</caption><thead><tr><th>Query ID</th><th>time (sec) snc</th><th>time (sec) congr</th><th>time gain snc</th><th>time gain congr</th><th>event gain congr</th></tr></thead><tbody><tr><td>A1</td><td>72.8</td><td>29.3</td><td>92.3%</td><td>98.1%</td><td>98.9%</td></tr><tr><td>A2</td><td>664.6</td><td>171.8</td><td>8.5%</td><td>77.9%</td><td>81.1%</td></tr><tr><td>A3</td><td>666.1</td><td>33.4</td><td>10.9%</td><td>97.4%</td><td>97.8%</td></tr><tr><td>A4</td><td>78.5</td><td>33.2</td><td>92.4%</td><td>97.8%</td><td>98.9%</td></tr><tr><td>A5</td><td>77.7</td><td></td><td>92.3%</td><td></td><td></td></tr><tr><td>A6</td><td>65.2</td><td>45.9</td><td>95.1%</td><td>96.9%</td><td>98.2%</td></tr><tr><td>A7</td><td>24.6</td><td>30.5</td><td>98.8%</td><td>98.0%</td><td>98.7%</td></tr><tr><td>A8</td><td>24.8</td><td>37.5</td><td>98.9%</td><td>97.3%</td><td>98.7%</td></tr></tbody></table>

an entire subtree under a given element; all descendant elements must be inspected. For instance, the query A1_0c equal to /site//@* must select all attributes of all elements under the root element *site*, requiring the inspection of every XML element in the document, for attribute presence, except for the root element *site*.

The lower event gain reported for the aforementioned queries align with the above expectation, showing percentages ranging from 75.7% to 81.1%. Also, these queries exhibit a larger gap between time gain and event gain, which ranges from 2.2% to 5.7% and will be subject to future optimization. It is worth noting that some of these queries combine multiple features at once, like queries A1_1a and A1_1d which have descendant axis, filter with attributes, and string comparison.

The only exception to this trend for the queries having descendant axis are A3 and A1_3, with respective event gains of 97.8% and 99.8%. The reason behind this high gain is that these queries starts from the root, with a child axis path of depth 3 before querying the descendant axis. This initial path allows for the exclusion and projection of most elements under *site* that do not fit the specified path, with their entire subtrees.

### 11.4.2. Earliest Safe-No-Change Projection

We compare earliest safe-no-change projection with the earliest congruence projection in see Table 28. For this we restrict ourselves to the queries A1 – A8 from the XPathMark in Table 24.

The XPath queries A1, A4, A6, A7, A8 don't have descendant axes. The time gain for safe-no-change projection on these queries is between 92.3 – 98.9%. For earliest congruence projection, the time gain was better for A1, A4, A6 with at least 96.6%. For A7 and A7, the time gain of safe-no-change projection is close to the event gain of congruence projection, but the time gain of congruence projection is 1.5% lower. So we hope that an optimized version of congruence projection could outperform safe-no-change projection in all cases.

The XPath queries with descendant axis are A2, A3, A5. For A2 and A3 in particular, the time gain of safe-no-change projection is very low with even not 10.9% while congruence projection yields at least 77.9%. We believe that this is bug in our current implementation of safe-no-change projection, which may be prohibiting the projection of attributes and text nodes for these queries (but not for the others). Congruence projection on A2 gains 77.9% of time and 81.1% of events. This is much better, but still far from the projection power for queries without descendant axis. For A3, congruence projection gains 97.4% of time. This is much better than for A2 since the descendant axis in A3 is at the end, while for A2 it is at the beginning of the path. But even for A2, congruence projection is very helpful.

### 11.4.3. Comparison to External Tools

QuiXPath was shown to be the most efficient large coverage external tool for regular XPath evaluation on XML streams [4]. We therefore compare the efficiency of congruence projection to QuiXPath in Table 29, and thereby by transitivity to the many alternative tools. We note that QuiXPath performs early query answering by compilation to possibly
<table><thead><tr><th>Query ID</th><th>parse-free time (sec) QuiXPath</th><th>parse-free time (sec) congr. prj.</th><th>fract.</th></tr></thead><tbody><tr><td>A1</td><td>11.0</td><td>14.3</td><td>1.3</td></tr><tr><td>A4</td><td>11.6</td><td>18.2</td><td>1.6</td></tr><tr><td>A6</td><td>10.7</td><td>30.9</td><td>2.9</td></tr><tr><td>A7</td><td>8.6</td><td>15.5</td><td>1.8</td></tr><tr><td>A8</td><td>8.8</td><td>22.5</td><td>2.6</td></tr></tbody></table>

<table><caption>**Figure 29.** Comparison of parse-free timings in seconds for XPathMark queries with QuiXPath and earliest congruence projection.</caption><thead><tr><th>Query ID</th><th>parse-free time (sec) QuiXPath</th><th>parse-free time (sec) congr. prj.</th><th>fract.</th></tr></thead><tbody><tr><td>A2</td><td>11.4</td><td>156.8</td><td>13.8</td></tr><tr><td>A3</td><td>11.5</td><td>18.4</td><td>1.6</td></tr><tr><td>A5</td><td>12.0</td><td></td><td></td></tr></tbody></table>

nondeterministic NWAs with selection states, without always being earliest. Apart from this, it bases its efficiency on both subtree projection and descendant projection.

The experiments with QuiXPath in [4] use the parse-free time. We therefore do the same for congruence projection by reducing the measured overall time by 15 seconds of parsing time.

Compared to the parsing-free times for the XPath queries without descendant axis, the earliest congruence projection demonstrates significant improvements. On average, our projection is only slower by a factor of 1.3 - 2.9 than QuiXPath. This shows that our implementation is already close to be competitive with the existing XML streaming tools, while being the only one guaranteeing earliest query answering.

For query A2 with descendant axis, congruence projection is by a factor of 13.8 slower than QuiXPath. The reason is that QuiXPath supports descendant projection, while congruence projection concerns only subhedge. For query A3 with a descendant axis at the end, congruence projection is only by a factor of 1.6 behind, so descendant projection seems less relevant here.

## 12. Related Automata Models

A large number of alternative automata notions for trees, forest and hedges were proposed in the literature. We compare them to SHAs and SHA$^s$ in what follows, and discuss the implications.
## 12.1. SHAs versus Tree, Forest, and Hedge Automata

**Standard Hedge Automata.** Standard hedge automata [9,10,34,35] operate on labeled hedges in a bottom-up manner similarly to SHAs. Also they have the same expressiveness, but horizontal languages are specified differently, leading to a problematic notion of determinism [36]. For this reason unique minimization fails for deterministic standard hedge automata. Still, they have the same expressiveness as SHAs when restricted to labeled hedges.

**Standard Tree Automata and SHA Minimization.** Syntactically, any SHA A is a standard tree automaton over the following ranked signature:

* a unary symbol for any letter $a \in \Sigma$,

* a binary symbol @, and

* a constant $\langle\rangle$.

Semantically, however, there is no perfect general correspondence. Only for subclasses a perfect correspondence can be made up via binary encoding. This was shown in [8] for the subclass of dSHAs with $I = \langle\rangle^\Delta$. In [37], it could also be shown for the subclass of multi-module dSHAs. This leads to unique minimization results for both subclasses of deterministic SHAs.

**Bojanczyk's Forest Automata.** Standard hedge automata also have the same expressiveness as Bojanczyk's forest automata (see Section 3.3 of [38]). These are based on the idea of transition monoids, rather than on the idea of transition rules such as SHAs or finite state automata or Neuman's and Seidl's forest automata. As a consequence, however, there is an exponential difference in succinctness between SHAs and Bojanczyk's forest automata [37].

## 12.2. SHA$^\downarrow$s versus SHAs

We start explaining why SHA$^\downarrow$s have the same expressiveness as SHAs. Basically it is the same reason for why NWAs have the same expressiveness as SHAs (see e.g. [8]). For the easier direction, we argued already that any SHA $A = (\Sigma, Q, \Delta, I, F)$ can converted to a SHA$^\downarrow$ down(A).

**Downward Elimination.** Conversely, we can convert any dSHA$^\downarrow$ A into an equivalent SHA elim$^\downarrow$(A) while possibly introducing nondeterminism as follows:

$$ 
\begin{align*}
I^{\text{elim}^{\downarrow}} &= I \times Q \\
F^{\text{elim}^{\downarrow}} &= F \times Q
\end{align*}
$$

$$ 
\begin{gather*}
\frac{q \xrightarrow{a} q' \text{ in } \Delta \quad r \in Q}{(r, q) \xrightarrow{a} (r, q')} \qquad \frac{q @ p \rightarrow q' \text{ in } \Delta \quad r \in Q}{(r, q) @ (q, p) \rightarrow (r, q')} \text{ in } \Delta^{\text{elim}^{\downarrow}}
\end{gather*}
$$

**Proposition 60.** $\mathcal{L}(A) = \mathcal{L}(\text{elim}^\downarrow(A))$.

The construction is analogous to the conversion of NWAs to SHAs [8] or to hedge automata [26]. The correctness proofs for these compilers are standard.

**Unique Minimization.** Unique minimization fails for dSHA$^\downarrow$s as usual for deterministic multiway automata. This even happens for deterministic two-way finite state automata on words. In contrast, the subclass of dSHAs with the restriction that the initial state and the tree initial state are the same enjoys unique minimization [8].

**Neuman and Seidl's Pushdown Forest Automata.** Standard hedge automata are also known to have the same expressiveness than Neumann and Seidl's pushdown forest automata [25]. The latter can be identified with SHA$^\downarrow$s for labeled hedges. What is needed
to map pushdown forest automata to standard hedge automata is downward elimination, as for mapping SHA↓s to SHAs.

### 12.3. SHA↓s versus NWAs

The streaming evaluator for SHA↓s via a visibly pushdown machine can also be obtained by compiling a SHA↓ to a nested word automaton (NWA) [11], whose streaming evaluator is given by a visibly pushdown machine [12], previously known as *input driven automata* [13–15].

**Definition 61.** A nested word automata (NWA) is a tuple $(\Sigma, Q, \Gamma, \Delta, I, F)$, where $\Sigma, \Gamma$ and $Q$ are sets, $I, F \subseteq Q$, and $\Delta = ((a^\Delta)_{a \in \Sigma}, \langle \Delta, \rangle^\Delta)$ contains relations: $a^\Delta \subseteq Q \times Q$, $\langle \Delta \subseteq Q \times (\Gamma \times Q)$ and $\rangle^\Delta \subseteq Q \times \Gamma \times Q$. A NWA is deterministic or equivalently a dNWA if $I$ contains at most one element and all above relations are partial functions.

The elements of $\Gamma$ are called stack symbols. The transition rules in $\Delta$ again have three forms: Internal rules $q \xrightarrow{a} q'$ in $\Delta$ as for SHAs, opening rules $q \xrightarrow{\langle \downarrow \gamma \rangle} q'$ in $\Delta$ if $\langle \Delta(q) = (q', \gamma) \rangle$ and closing rules $q \xrightarrow{\rangle \uparrow \gamma} q'$ in $\Delta$ if $\rangle^\Delta(q, \gamma) = q'$.

**Streaming evaluators for NWAs.** The streaming evaluator for NWAs can be seen as pushdown machines for evaluating the nested words of hedges in streaming manner. A configuration of the pushdown machine is a pair in $\mathcal{K} = Q \times \Gamma^*$ containing a state and a stack. For any word $v \in \hat{\Sigma}^*$ we define a streaming transition relation $v \xrightarrow{\text{str}} \subseteq \mathcal{K} \times \mathcal{K}$ such that for all $q, q' \in Q$ and $\sigma \in \Gamma^*$:

$$ \begin{array}{ccc} \begin{array}{c} \text{true} \\ \hline (q, \sigma) \xrightarrow{\epsilon \text{ str}} (q, \sigma) \text{ wrt } \Delta \end{array} & \begin{array}{c} (q, \sigma) \xrightarrow{v \text{ str}} (q', \sigma) \\ \hline (q, \sigma) \xrightarrow{v \cdot v' \text{ str}} (q'', \sigma) \text{ wrt } \Delta \end{array} & \begin{array}{c} (q', \sigma) \xrightarrow{v' \text{ str}} (q'', \sigma) \text{ wrt } \Delta \\ \hline (q', \sigma) \xrightarrow{v \cdot v' \text{ str}} (q'', \sigma) \text{ wrt } \Delta \end{array} \\ \begin{array}{c} q \xrightarrow{a} q' \text{ in } \Delta \\ \hline q \xrightarrow{a \text{ str}} q' \text{ wrt } \Delta \end{array} & \begin{array}{c} q \xrightarrow{\langle \downarrow \gamma \rangle} q' \text{ in } \Delta \\ \hline (q, \sigma) \xrightarrow{\langle \text{str}} (q', \sigma) \text{ wrt } \Delta \end{array} & \begin{array}{c} q \xrightarrow{\rangle \uparrow \gamma} q' \text{ in } \Delta \\ \hline (q, \sigma \cdot \gamma) \xrightarrow{\rangle \text{str}} (q', \sigma) \text{ wrt } \Delta \end{array} \end{array} $$

**From SHA↓s to NWAs.** For any SHA↓ $A = (\Sigma, Q, \Delta, I, F)$ we can define the NWA $A^{nwa} = (\Sigma, Q, \Gamma, \Delta^{nwa}, I^{nwa}, F^{nwa})$ while preserving determinism, such that $\Gamma = Q$, while $\Delta^{nwa}$ contains for all $a \in \Sigma$ and $q, p \in Q$ the transition rules:

$$ \begin{array}{ccc} \begin{array}{c} q \xrightarrow{a} q' \text{ in } \Delta \\ \hline q \xrightarrow{a} q' \text{ in } \Delta^{nwa} \end{array} & \begin{array}{c} q \xrightarrow{\langle \rangle} q' \text{ in } \Delta \\ \hline q \xrightarrow{\langle \downarrow q \rangle} q' \text{ in } \Delta^{nwa} \end{array} & \begin{array}{c} q \xrightarrow{p} q' \text{ in } \Delta \\ \hline p \xrightarrow{\rangle \uparrow q} q' \text{ in } \Delta^{nwa} \end{array} \end{array} $$

For instance, the dNWA $A^{nwa}$ of the dSHA↓ $A$ in Fig. 9 obtained from the dSHA for the [self::list/child::item] from the introduction is given in Fig. 30. And the dNWA $A^{nwa}$ of the dSHA↓ $A$ in Fig. 21 is given in Fig. 31.

**Lemma 62.** $\mathcal{L}(A^{nwa}) = \mathcal{L}(A)$.

The runs of SHA↓s $A$ and NWAs $A^{nwa}$ can be identified.

**Projection for NWAs.** Projecting evaluators for NWAs were proposed in the context of projecting NWAs [4]. They are based on the following notion of states of irrelevant subtrees for NWAs.
<figure><img src="image_49.png" /><figcaption>**Figure 30.** The dNWA $A^{nwa}$ for the $dSHA^↓$ A in Fig. 9 obtained by applying the *down* operator to the $dSHA$ in Fig. 4 for the filter `[self::list/child::item]`.</figcaption></figure>

<figure><img src="image_50.png" /><figcaption>**Figure 31.** The dNWA $(A^{snc}_{e(\llbracket doc \rrbracket)})^{nwa}$ for the earliest $dSHA^↓$ with safe-no-change projection in Fig. 21.</figcaption></figure>

**Definition 63 (Variant of Definition 3 of [4]).** We call a state $q$ of an NWA a state of irrelevant subtrees if there exist two different stack symbols $\gamma, \gamma'$ and a state $q'$ such that the transitions shown on the right exist, but no further opening transitions with $\gamma$, no further transitions with $\gamma'$, and no further closing transition in $q$ popping $\gamma$. In this case, we write $q \in \text{i-tree}_{\Sigma \setminus \emptyset}$.

<figure><img src="image_51.png" /></figure>

**Lemma 64.** Any subhedge projection state of a complete $SHA^↓$ A is a state of irrelevant subtrees of $A^{nwa}$.

It was then shown in [4] how to map an NWA with a subset $Q_{shp}^\Delta$ of states of irrelevant subtrees to a projecting NWA, whose streaming semantics yields a streaming evaluator with subhedge projection. The presentation of subhedge projection for $SHA^↓$s without passing via NWAs yields the same result in a more direct manner.

It should also be noticed that projecting NWAs support descendant projection beside of subhedge projection. For SHAs, this is left to future research.

**sectionConclusion and Future Work** We introduced the notion of irrelevant subhedges for membership to hedge language under schema restrictions. We developed algorithms with subhedge projection that jump over irrelevant subhedges for testing membership to the regular hedge languages defined by dSHAs. All our algorithms can be run in in-memory mode and in streaming mode. The difficulty was how to push the needed finite state information for subtree projection top-down given that SHAs operate bottom-up. We solved it based on compilers from SHAs to downward SHAs.

This first compiler propagates safety information about non-changing states. The second compiler, which we prove to be complete for subhedge projection, propagates
difference relations. We then combined subhedge projection with earliest membership
testing and combine it earliest monadic query answering. We integrated both safe-no-
change and complete congruence in our AStream tool and confirmed their usefulness
experimentally: we showed that it can indeed speed up the the AStream tool, for answering
algorithm regular XPath queries on XML streams. Moreover, congruence projection showed
much higher event projection gain rates than safe-no-change, ranging between 75.7% and
100%, for the class of queries that does not have descendant axis and thus, becoming
competitive in time with the best existing streaming tools for regular XPath queries without
recursive axis.

A remaining open theoretical and practical question is how to obtain descendant
projection for SHAs, as needed to speed up the evaluation of XPath queries with descendant
axis. On the implementation and experimental side, it would be nice to investigate the in-
memory version of our subhedge algorithms too. And finally, it would be nice to optimize
streaming earliest-query answering tools further until they outperform the best streaming
tools in all cases, while being better for queries where the other tools are not earliest.

References

1. Marian, A.; Siméon, J. Projecting XML Documents. In Proceedings of the VLDB, 2003, pp. 213–224.

2. Frisch, A. Regular Tree Language Recognition with Static Information. In Proceedings of the Exploring New Frontiers of Theoretical Informatics, IFIP 18th World Computer Congress, TCS 3rd International Conference on Theoretical Computer Science, 2004, pp. 661–674.

3. Maneth, S.; Nguyen, K. XPath Whole Query Optimization. VLPB Journal 2010, 3, 882–893.

4. Sebastian, T.; Niehren, J. Projection for Nested Word Automata Speeds up XPath Evaluation on XML Streams. In Proceedings of the International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), Harrachov, Czech Republic, 2016.

5. Kay, M. The saxon XSLT and XQuery processor, 2004. https://www.saxonica.com/

6. Gienieczko, M.; Murlak, F.; Paperman, C. Supporting Descendants in SIMD-Accelerated JSONPath. In Proceedings of the Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 1, ASPLOS 2024. ACM, 2024, pp. 15–29.

7. Al Serhali, A.; Niehren, J. A Benchmark Collection of Deterministic Automata for XPath Queries. In Proceedings of the XML Prague 2022, Prague, Czech Republic, 2022.

8. Niehren, J.; Sakho, M. Determinization and Minimization of Automata for Nested Words Revisited. *Algorithms* **2021**, *14*, 68. https://doi.org/10.3390/a14030068

9. Comon, H.; Dauchet, M.; Gilleron, R.; Löding, C.; Jacquemard, F.; Lugiez, D.; Tison, S.; Tommasi, M. Tree Automata Techniques and Applications. Available online since 1997: http://tata.gforge.inria.fr, 2007.

10. Thatcher, J.W. Characterizing derivation trees of context-free grammars through a generalization of automata theory. *Journal of Computer and System Science* **1967**, *1*, 317–322. https://doi.org/10.1016/S0022-0000(67)80022-9

11. Alur, R. Marrying Words and Trees. In Proceedings of the 26th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. ACM-Press, 2007, pp. 233–242.

12. Alur, R.; Madhusudan, P. Visibly pushdown languages. In Proceedings of the Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004; Babai, L., Ed. ACM, 2004, pp. 202–211. https://doi.org/10.1145/1007352.1007390.

13. Mehlhorn, K. Pebbling Moutain Ranges and its Application of DCFL-Recognition. In Proceedings of the Automata, Languages and Programming, 7th Colloquium, Noordweijkerhout, The Netherlands, July 14-18, 1980, Proceedings; de Bakker, J.W.; van Leeuwen, J., Eds. Springer, 1980, Vol. 85, Lecture Notes in Computer Science, pp. 422–435. https://doi.org/10.1007/3-540-10003-2_89

14. von Braunmühl, B.; Verbeek, R. Input Driven Languages are Recognized in log n Space. In Topics in the Theory of Computation; Karplinski, M.; van Leeuwen, J., Eds.; North-Holland, 1985; Vol. 102, North-Holland Mathematics Studies, pp. 1 – 19. https://doi.org/10.1016/S0304-0208(08)73072-X

15. Okhotin, A.; Salomaa, K. Complexity of input-driven pushdown automata. *SIGACT News* **2014**, *45*, 47–67. https://doi.org/10.1145/2636805.2636821
16. Niehren, J.; Sakho, M.; Al Serhali, A. Schema-Based Automata Determinization. In Proceedings of the Proceedings of the 13th International Symposium on Games, Automata, Logics and Formal Verification, GandALF 2022, Madrid, Spain, September 21-23, 2022; Ganty, P.; Monica, D.D., Eds., 2022, Vol. 370, EPTCS, pp. 49–65. https://doi.org/10.4204/EPTCS.370.4.

17. Lick, A.; Schmitz, S. XPath Benchmark, Last visited April 13th 2022.

18. Mozafari, B.; Zeng, K.; Zaniolo, C. High-performance complex event processing over XML streams. In Proceedings of the SIGMOD Conference; Candan, K.S.; Chen, Y.; Snodgrass, R.T.; Gravano, L.; Fuxman, A.; Candan, K.S.; Chen, Y.; Snodgrass, R.T.; Gravano, L.; Fuxman, A., Eds. ACM, 2012, pp. 253–264. https://doi.org/10.1145/2213836.2213866.

19. Grez, A.; Riveros, C.; Ugarte, M. A Formal Framework for Complex Event Processing. 2019, pp. 5:1–5:18. https://doi.org/10.4230/LIPIcs.ICDT.2019.5.

20. Muñoz, M.; Riveros, C. Streaming Enumeration on Nested Documents. In Proceedings of the 25th International Conference on Database Theory, ICDT 2022, March 29 to April 1, 2022, Edinburgh, UK (Virtual Conference); Olteanu, D.; Vortmeier, N., Eds. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, Vol. 220, LIPIcs, pp. 19:1–19:18. https://doi.org/10.4230/LIPIcs.ICDT.2022.19.

21. Al Serhali, A.; Niehren, J. Earliest Query Answering for Deterministic Stepwise Hedge Automata. In Proceedings of the Implementation and Application of Automata - 27th International Conference, CIAA 2023, Famagusta, North Cyprus, September 19-22, 2023, Proceedings; Nagy, B., Ed. Springer, 2023, Vol. 14151, Lecture Notes in Computer Science, pp. 53–65. https://doi.org/10.1007/978-3-031-40247-0_3.

22. Gauwin, O.; Niehren, J.; Tison, S. Earliest Query Answering for Deterministic Nested Word Automata. In Proceedings of the 17th International Symposium on Fundamentals of Computer Theory. Springer Verlag, 2009, Vol. 5699, Lecture Notes in Computer Science, pp. 121–132. https://doi.org/10.1007/978-3-642-03409-1_12.

23. Debarbieux, D.; Gauwin, O.; Niehren, J.; Sebastian, T.; Zergaoui, M. Early nested word automata for XPath query answering on XML streams. Theor. Comput. Sci. 2015, 578, 100–125. https://doi.org/10.1016/j.tcs.2015.01.017.

24. Al Serhali, A.; Niehren, J. Subhedge Projection for Stepwise Hedge Automata. In Proceedings of the Fundamentals of Computation Theory - 24th International Symposium, FCT 2023, Trier, Germany, September 18-21, 2023, Proceedings; Fernau, H.; Jansen, K., Eds. Springer, 2023, Vol. 14292, Lecture Notes in Computer Science, pp. 16–31. https://doi.org/10.1007/978-3-031-43587-4_2.

25. Neumann, A.; Seidl, H. Locating Matches of Tree Patterns in Forests. In Proceedings of the Foundations of Software Technology and Theoretical Computer Science. Springer Verlag, 1998, Vol. 1530, Lecture Notes in Computer Science, pp. 134–145. https://doi.org/10.1007/978-3-642-03409-1_12.

26. Gauwin, O.; Niehren, J.; Roos, Y. Streaming Tree Automata. Information Processing Letters 2008, 109, 13–17. https://doi.org/10.1016/j.ipl.2008.08.002.

27. Franceschet, M. XPathMark Performance Test. https://users.dimi.uniud.it/~massimo.franceschet/xpathmark/PTbench.html. Accessed: 2020-10-25.

28. Hosoya, H.; Pierce, B.C. XDuce: A Statically Typed XML Processing Language. ACM Trans. Internet Technol. 2003, 3, 117–148. https://doi.org/10.1145/767193.767195.

29. Gécseg, F.; Steinby, M. Tree Automata; Akadémiai Kiadó, Budapest, 1984.

30. Gold, E.M. Language Identification in the Limit. Inf. Control. 1967, 10, 447–474. https://doi.org/10.1016/S0019-9958(67)91165-5.

31. Carme, J.; Niehren, J.; Tommasi, M. Querying Unranked Trees with Stepwise Tree Automata. In Proceedings of the Rewriting Techniques and Applications, 15th International Conference, RTA 2004, Aachen, Germany, June 3-5, 2004, Proceedings; van Oostrom, V., Ed. Springer, 2004, Vol. 3091, Lecture Notes in Computer Science, pp. 105–118. https://doi.org/10.1007/978-3-540-25979-4_8.

32. Neumann, A.; Seidl, H. Locating Matches of Tree Patterns in Forests. In Proceedings of the 18-th Conference on Foundations of Software Technology and Theoretical Computer Science, 1998. https://doi.org/10.1007/b71635.

33. Debarbieux, D.; Gauwin, O.; Niehren, J.; Sebastian, T.; Zergaoui, M. Early nested word automata for XPath query answering on XML streams. Theor. Comput. Sci. 2015, 578, 100–125. https://doi.org/10.1016/j.tcs.2015.01.017.

34. Pair, C.; Quéré, A. Définition et étude des bilangages réguliers. Information and Control 1968, 13, 565–593.
<figure><img src="image_52.png" /><figcaption>**Figure A32.** The earliest dSHA↓ $A_e$ for the dSHA A in Fig. 19 with schema [[doc]] for the XPath filter [self::list/child::item]. The states of $A_e$ correspond to the following tuples: 0 = (0, {1, 2, 3, 5}, {4}), 0' = (0, {2, 4, 5}, {3, 4}), 1' = (1, {2, 4, 5}, {3, 4}), 0'' = (0, ∅, {2, 4, 5}), 1'' = (1, ∅, {2, 4, 5}), 0''' = (0, ∅, ∅), 1''' = (1, ∅, ∅), 2''' = (1, ∅, ∅), and 3''' = (1, ∅, ∅).</figcaption></figure>

35. Murata, M. Hedge Automata: a Formal Model for XML Schemata. Web page, 2000.

36. Martens, W.; Niehren, J. On the Minimization of XML Schemas and Tree Automata for Unranked Trees. *Journal of Computer and System Science* **2007**, 73, 550–583.

37. Niehren, J. Stepwise Hedge Automata are exponentially more succinct than Forest Automata, in preparation.

38. Bojanczyk, M.; Walukiewicz, I. Forest algebras. In Proceedings of the Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas]; Flum, J.; Grädel, E.; Wilke, T., Eds. Amsterdam University Press, 2008, Vol. 2, *Texts in Logic and Games*, pp. 107–132.

## Appendix N Earliest Membership

We adapt the earliest membership tester for dSHAs from [21] so that it compiles to SHA↓s instead of NWAs and such that it accounts for schemas.

### Appendix N.1 Schema Safety is an Inclusion Problem

The idea for testing certain membership and certain nonmembership is to consider states are safe to reach final states except if going out of the schema. Let $A = (Σ, Q, Δ, I, F)$ be an SHA with schema S such that there exists $F ⊆ F_S ⊆ Q$ with $S = L(A[F/F_S])$. Note that $L(A) ⊆ S ⊆ H_Σ$ in particular. The set of states that are safe to reach a subset $P ⊆ Q$ for all hedges that do not go out of the schema S then is:

$$ safe_S^Δ(P) = safe^Δ(P \cup (Q \setminus F_S)) $$

If A is deterministic and schema-complete for S then the safety of a state of A with respect to schema S is an inclusion problem.

**Lemma A65.** Let $S = L(A[F/F_S])$. If A is deterministic and schema-complete for S then for all states $q \in Q$:

$$ L(A[I/\{q\}, F/F_S]) \subseteq L(A[I/\{q\}]) \Leftrightarrow q \in safe_S^Δ(F) $$

**Proof.** “$\Leftarrow$”. Suppose that $q \notin safe_S^Δ(F)$. The definition of schema-based safety yields $acc^Δ(\{q\}) \cap (F_S \setminus F) \neq \emptyset$. So there exists some hedge $h \in H_Σ$ such that such that $q \xrightarrow{h} F_S \setminus F$ wrt $Δ$. In particular, $q \in L(A[I/\{q\}, F/F_S])$. By determinism there exists no other transition on $h$ from $q$ and thus $q \notin L(A[I/\{q\}])$. Hence $L(A[I/\{q\}, F/F_S]) \not\subseteq L(A[I/\{q\}])$.
$$
\begin{array}{r@{\quad}l@{\quad}l@{\quad}l}
\multicolumn{4}{c}{\begin{array}{@{}c@{\quad}l@{}}
  & \displaystyle \frac{q \xrightarrow{a} q' \text{ in } \Delta \quad q' \notin S \cup R}{(q, S, R) \xrightarrow{a} (q', S, R) \text{ in } \Delta_e}
\end{array}} \\
& \begin{array}{@{}c@{\quad}l@{}}
  & \displaystyle \frac{\langle\rangle \qquad q' \text{ in } \Delta \quad (q, S, R) \in \mathcal{Q}_e \quad q' \notin \text{s-down}^\Delta(q, S) \cup \text{s-down}^\Delta(q, R)}{(q, S, R) \xrightarrow{\langle\rangle} (q', s-down^\Delta(q, S), s-down^\Delta(q, R)) \text{ in } \Delta_e}
\end{array} & & \\
& \begin{array}{@{}c@{\quad}l@{}}
  & \displaystyle \frac{q@p \to q' \text{ in } \Delta \quad q' \notin S \cup R}{(q, S, R)@(p, s-down^\Delta(q, S), s-down^\Delta(q, R)) \to (q', S, R) \text{ in } \Delta_e}
\end{array} & & \\
& \begin{array}{@{}c@{\quad}l@{}}
  & \displaystyle \frac{q \xrightarrow{a} q' \text{ in } \Delta \quad q' \in S}{(q, S, R) \xrightarrow{a} \text{sel in } \Delta_e} \\
  & \displaystyle \frac{\langle\rangle \qquad q' \text{ in } \Delta \quad (q, S, R) \in \mathcal{Q}_e \quad q' \in \text{s-down}^\Delta(q, S)}{(q, S, R) \xrightarrow{\langle\rangle} \text{sel in } \Delta_e}
\end{array} & & \\
& \begin{array}{@{}c@{\quad}l@{}}
  & \displaystyle \frac{q@p \to q' \text{ in } \Delta \quad q' \in S}{(q, S, R)@(p, s-down^\Delta(q, S), s-down^\Delta(q, R)) \to \text{sel in } \Delta_e}
\end{array} & & \\
& \begin{array}{@{}c@{\quad}l@{}}
  & \displaystyle \frac{a \in \Sigma}{\text{sel} \xrightarrow{a} \text{sel in } \Delta_e} \\
  & \displaystyle \frac{\mu \in \mathcal{Q}_e}{\text{sel@}\mu \to \text{sel in } \Delta_e} \\
  & \displaystyle \frac{\mu \in \mathcal{Q}_e}{\text{\mu@sel} \to \text{sel in } \Delta_e} \\
  & \displaystyle \frac{\text{true}}{\text{sel} \xrightarrow{\langle\rangle} \text{sel in } \Delta_e}
\end{array} & & \\
\multicolumn{4}{c}{\begin{array}{@{}c@{\quad}l@{}}
  & \mathcal{L}(A[I/\{q\}]) = \mathcal{H}_\Sigma \Leftrightarrow q \in \text{safe}^\Delta(F)
\end{array}}
\end{array}
$$

<caption>**Figure A33.** The earliest transition rules $\Delta_e$ inferred from transition rules $\Delta$ of some SHA.</caption>

"⇒". Suppose that $q \in \text{safe}_S^\Delta(F)$. Let $h \in \mathcal{L}(A[I/\{q\}, F/F_S])$. Then there exists $q' \in F_S$ such that $q \xrightarrow{h} q'$ wrt $\Delta$. Hence $q' \in \text{acc}^\Delta(\{q\})$ so that $\text{acc}^\Delta(\{q\}) \subseteq F \cup (Q \setminus F_S)$ implies $q' \in F$. Thus, $h \in \mathcal{L}(A[I/\{q\}])$. $\square$

Lemma A65 with $F_S = Q$ shows Lemma 5 of [21], which states for any complete dSHAs $A$ that safety is a universality problem:

$$ \mathcal{L}(A[I/\{q\}]) = \mathcal{H}_{\Sigma} \Leftrightarrow q \in \text{safe}^{\Delta}(F) $$

This is since the schema-completeness of $A$ for $S = \mathcal{H}_\Sigma$ implies the completeness of $A$ and thus $\mathcal{L}(A[I/\{q\}, F/Q]) = \mathcal{H}_\Sigma$.

## Appendix N.2 Algorithm

We now present our earliest membership tester for dSHAs with schema restrictions. Given a SHA $A$ we compute a SHA$^\downarrow A_{e(S)} = (\Sigma, \mathcal{Q}_e, \Delta_e, I_{e(S)}, F_{e(S)})$ as follows. Let $\text{sel}$ be a fresh symbol. We start with set of states that are safe for selection $S_0 = \text{safe}_S^\Delta(F)$ and respectively safe for rejection $R_0 = \text{safe}_S^\Delta(Q \setminus F)$. The state sets of $A_{e(S)}$ are then:

$$
\begin{align*}
\mathcal{Q}_e &= (Q \times 2^Q \times 2^Q) \cup \{\text{sel}\} \\
I_{e(S)} &= \{(q, R_0, S_0) \mid q \in I, q \notin R_0 \cup S_0\} \cup \{\text{sel} \mid I \cap S_0 \neq \emptyset\} \\
F_{e(S)} &= \{(q, R_0, S_0) \mid q \in F\} \cup \{\text{sel}\}
\end{align*}
$$

The transition rules in $\Delta_e$ are given by the in Fig. A33. For illustration, reconsider the dSHA from Fig. 4. This dSHA is not complete but schema-complete for the schema $[[\text{doc}]]$. We get $\text{s-down}^\Delta(0, \{4\}) = \{3, 4\}$. It may seem counter intuitive that note only state 3 but also state 4 down remains safe for selection. This reflects the fact that no proper subhedge of any hedge satisfying the intended schema may ever get into state 4. Applying the earliest construction with safe-no-change projection to dSHA in Fig. 4 yields the dSHA$^\downarrow$ in Fig. A32.
Appendix N.3 Soundness and Completeness

We next provide soundness and completeness results for our earliest in-memory
membership tester with projection.

**Proposition A66 (Soundness).** For any SHA A with schema $S = \mathcal{L}(A[F/F_S])$, hedge $h \in S$, and partial run $v$ of $A_{e(S)}$ on $h$ that ends in state $sel$ then $h \in \mathcal{L}(A)$.

So if the partial run reaches state *sel* then *proj*<sub>S</sub>(*v*) is certain for membership to *L*(A)
with respect to S. Evaluating a SHA<sup>↓s</sup> *A*<sub>*e*(S)</sub> yields an earliest in-memory membership tester
for dSHA A. A single adaptation is in order: whenever *sel* is reached, the evaluation can
stop all over and accept the input hedge.

**Theorem A8 (Completeness).** Let $A = (\Sigma, Q, \Delta, I, F)$ be a dSHA that is schema-complete for schema $S = \mathcal{L}(A[F/F_S])$. For any hedge $h \in S$ and prefix $v$ of $nw(h)$:

* if $v$ is certain for membership in $\mathcal{L}(A)$ with $S$ then there exists a partial run $w$ for $A_{e(S)}$ on $h$ such that $v = \text{proj}_{\Sigma}(w)$ and $w$ ends with state $sel$.

* if $v$ is certain for nonmembership in $\mathcal{L}(A)$ with $S$ then there exists blocking partial run $w$ for $A_{e(S)}$ on $h$ such that $\text{proj}_{\Sigma}(w)$ is a prefix of $v$.

This means that certainty for membership and nonmembership are detected at the
earliest prefix when running the evaluator for $A_{e(S)}$.

**Proof sketch.** We notice that this algorithm is basically the same as the earliest membership tester from Proposition 6 of [21], except that it also check for safe rejection and that it accounts for schemas. The fact that NWAs are used there instead of SHA$^\downarrow$s here is not essential. So we can lift the soundness and completeness proof from there without problem. □