A Framework for Extraction and Transformation of Documents

We start the study of ET programs from an evaluation perspective. Towards this goal, we devise a specific instantiation of our ET framework that achieves a desirable balance between the following objectives:

After reviewing further related work, Section 2 introduces the class of multispanners. In Section 3, we present the general setting of ET programs. Then, in Section 4, we instantiate this setting to the case of regular ET programs. In Section 5, we study the expressive power of regular ET programs, and in Section 6, we present our evaluation algorithm. In Section 7, we study the composition of such programs. Finally, we discuss future work in Section 8. Due to space limitations, proof details can be found in the online version [38].

String transductions [9, 32, 10] – a classical model in computer science – have recently gained renewed attention with the theory of polyregular functions [2]. Although we can see an ET program as a single transduction, our work has several novel contributions compared to classical string transductions. Firstly, our framework models the process by two declarative phases (which is natural from a data management perspective), contrary to string transductions that model the task as a single process. Secondly, we are concerned with bag semantics, which are usually not considered in the context of transductions. Moreover, efficient enumeration algorithms have not been studied in this context.

On the practical side, there are systems for transforming documents into documents (e.g., [27]). For example, they used a combination of regular expressions with replace operators [28] or parsing followed by a transduction over the parsing tree [27]. Indeed, in practice, regular expressions support some special commands for transforming data (also called substitutions). Our study has a theoretical emphasis on information extraction. To the best of our knowledge, previous systems neither use the expressive power of document spanners nor regular functions. In particular, previous systems cannot define queries like $(E_2,T_2)$ through regular expressions plus a transformation.

For a document $𝐃\in {\mathrm{\Sigma }}^{\ast }$ and for every $i,j\in [|𝐃|+1]$ with $i\le j$, $[i,j⟩$ is a span of $𝐃$ and its value, denoted by $𝐃[i,j⟩$, is the substring of $𝐃$ from symbol $i$ to symbol $j-1$. In particular, $𝐃[i,i⟩=\text{ε}$ (called an empty span) and $𝐃[1,|𝐃|+1⟩=𝐃$. By $\text{Spans}(𝐃)$, we denote the set of spans of $𝐃$, and by $\text{Spans}$ we denote the set of all spans $\{[i,j⟩\mid i,j\in \mathbb{N},i\le j\}$. Two spans $[i,j⟩$ and $[i^{\prime },j^{\prime }⟩$ are disjoint if $j\le i^{\prime }$ or $j^{\prime }\le i$. A multispan is a (possibly empty) set of pairwise disjoint spans. Let $𝒳$ be a finite set of variables. A span-tuple (over a document $𝐃$ and variables $𝒳$) [18] is a function $t:𝒳\to \text{Spans}(𝐃)$. We define a multispan-tuple as a function $t:𝒳\to 𝒫(\text{Spans}(𝐃))$ such that, for every $\text{x}\in 𝒳$, $t(\text{x})$ is a multispan. Note that every span-tuple $t$ can be considered as a special case of a multispan-tuple $t^{\prime }$ with $t^{\prime }(\text{x})=\{t(\text{x})\}$ for every $\text{x}\in 𝒳$. For simplicity, we usually denote multispan-tuples in tuple-notation, for which we assume an order on $𝒳$. For example, if $𝒳=\{{\text{x}}_1,{\text{x}}_2,{\text{x}}_3\}$ with , the multispan-tuple $t=(\{[1,6⟩\},\mathrm{\varnothing },\{[2,3⟩,[5,7⟩\})$ maps ${\text{x}}_1$ to $\{[1,6⟩\}$, ${\text{x}}_2$ to $\mathrm{\varnothing }$ and ${\text{x}}_3$ to $\{[2,3⟩,[5,7⟩\}$. Note that $[2,3⟩$ and $[5,7⟩$ are disjoint, while $[1,6⟩$ and $[5,7⟩$ are not, which is allowed, since they are spans of different multispans.

A multispan-relation (over a document $𝐃$ and variables $𝒳$) is a possibly empty set of multispan-tuples over $𝐃$ and $𝒳$. Given a finite alphabet $\mathrm{\Sigma }$, a multispanner (over $\mathrm{\Sigma }$ and $𝒳$) is a function that maps every document $𝐃\in {\mathrm{\Sigma }}^{\ast }$ to a multispan-relation over $𝐃$ and $𝒳$. Note that the empty relation $\mathrm{\varnothing }$ is also a valid image of a multispanner.

Similarly to the framework of document spanners [18], it is convenient to represent multispanners over $\mathrm{\Sigma }$ and $𝒳$ by formal languages over the alphabet $\mathrm{\Sigma }\cup \{{}_{\text{x}}{}^{}\text{⊢},{\text{⊣}}_{\text{x}}\mid \text{x}\in 𝒳\}$. This allows us to represent multispanners by formal language descriptors, e. g., regular expressions.

In this section, we adapt the concept of ref-words (commonly used for classical document spanners; see [23, 21, 14, 41]) to multispanners.

For any set $𝒳$ of variables, we shall use the set ${\mathrm{\Gamma }}_{𝒳}=\{{}_{\text{x}}{}^{}\text{⊢},{\text{⊣}}_{\text{x}}\mid \text{x}\in 𝒳\}$ as an alphabet of meta-symbols. In particular, for every $\text{x}\in 𝒳$, we interpret the pair of symbols ${}_{\text{x}}{}^{}\text{⊢}$ and ${\text{⊣}}_{\text{x}}$ as a pair of opening and closing parentheses. A multiref-word (over alphabet $\mathrm{\Sigma }$ and variables $𝒳$) is a word $w\in {(\mathrm{\Sigma }\cup {\mathrm{\Gamma }}_{𝒳})}^{\ast }$ such that, for every $\text{x}\in 𝒳$, the subsequence of the occurrences of ${}_{\text{x}}{}^{}\text{⊢}$ and of ${\text{⊣}}_{\text{x}}$ is well-balanced and unnested, namely, has the form ${({}_{\text{x}}{}^{}\text{⊢}{\text{⊣}}_{\text{x}})}^k$ for some $k\ge 0$.

Intuitively, any multiref-word $w$ over $\mathrm{\Sigma }$ and $𝒳$ uniquely describes a document ${𝐃}_w\in {\mathrm{\Sigma }}^{\ast }$ and a multispan-tuple ${\text{t}}_w$ as follows. First, let ${𝐃}_w$ be obtained from $w$ by erasing all symbols from ${\mathrm{\Gamma }}_{𝒳}$. We note that, for every $\text{x}\in 𝒳$, every matching pair ${}_{\text{x}}{}^{}\text{⊢}$ and ${\text{⊣}}_{\text{x}}$ in $w$ (i. e., every occurrence of ${}_{\text{x}}{}^{}\text{⊢}$ and the following occurrence of ${\text{⊣}}_{\text{x}}$) uniquely describes a span of ${𝐃}_w$: ignoring all other occurrences of symbols from ${\mathrm{\Gamma }}_{𝒳}$, this pair encloses a factor of ${𝐃}_w$. Consequently, we simply define that, for every $\text{x}\in 𝒳$, ${\text{t}}_w(\text{x})$ contains all spans defined by matching pairs ${}_{\text{x}}{}^{}\text{⊢}$ and ${\text{⊣}}_{\text{x}}$ of $w$. The property that the subsequence of $w$ of the occurrences ${}_{\text{x}}{}^{}\text{⊢}$ and ${\text{⊣}}_{\text{x}}$ has the form ${({}_{\text{x}}{}^{}\text{⊢}{\text{⊣}}_{\text{x}})}^k$ for some $k\ge 0$ implies that all spans of ${\text{t}}_w(\text{x})$ are pairwise disjoint.

The advantage of the notion of multiref-words is that it allows to easily describe both a document and some multispan-tuple over this document. Therefore, one can use any set of multiref-words to define a multispanner as follows. A multiref-language (over terminal alphabet $\mathrm{\Sigma }$ and variables $𝒳$) is a set of multiref-words over $\mathrm{\Sigma }$ and $𝒳$. Any multiref-language $L$ describes the multispanner $⟦L⟧$ over $\mathrm{\Sigma }$ and $𝒳$ defined as follows. For every $𝐃\in {\mathrm{\Sigma }}^{\ast }$: $⟦L⟧(𝐃)=\{{\text{t}}_w\mid w\in L\text{ and }{𝐃}_w=𝐃\}$.

Analogously to classical spanners (cf. [39, 23, 21, 14, 41]), we define the class of regular multispanners as those multispanners $S$ with $S=⟦L⟧$ for some regular multiref-language $L$. Moreover, as done in [18] for classical spanners, we will use a class of regular expressions to define a subclass of regular multispanners that shall play a central role in the extraction phase of our extraction and transformation framework.

Let $\mathrm{\Sigma }$ be a finite alphabet and let $𝒳$ be a finite set of variables. We now define multispanner-expressions (over $\mathrm{\Sigma }$ and $𝒳$). Roughly speaking, these expresssions are a particular class of regular expressions for defining sets of multiref-words and therefore multispanners. A multispanner-expression $R$ (over $\mathrm{\Sigma }$ and $𝒳$) satisfies the syntax:

for every $\text{x}\in 𝒳$ such that x does not appear in $R$. Such a multispanner-expression $R$ naturally defines a set of multiref-words $ℒ(R)$ as follows: $ℒ(\text{ε})=\{\text{ε}\}$, $ℒ(a)=\{a\}$, $ℒ(R\cdot R^{\prime })=ℒ(R)\cdot ℒ(R^{\prime })$, $ℒ(R+R^{\prime })=ℒ(R)\cup ℒ(R^{\prime })$, $ℒ(R^{\ast })=ℒ{(R)}^{\ast }$, and $ℒ(\text{x}\{R\})=\{{}_{\text{x}}{}^{}\text{⊢}\}\cdot ℒ(R)\cdot \{{\text{⊣}}_{\text{x}}\}$, where, for every $L,L^{\prime }\subseteq {\mathrm{\Sigma }}^{\ast }$, $L\cdot L^{\prime }=\{uv\mid u\in L\wedge v\in L^{\prime }\}$, $L^0=\{\text{ε}\}$, $L^i=L\cdot L^{i-1}$ for every $i\ge 1$, and $L^{\ast }={\bigcup }_{i=0}^{\mathrm{\infty }}{L}^i$. As usual, we use $R^{+}$ as a shorthand for $(R\cdot R^{\ast })$.

One can easily prove that any multispanner-expression defines a multiref-language, since we do not allow expressions of the form $\text{x}\{R\}$ whenever $R$ mentions x. Thus, we can define the multispanner $⟦R⟧$ specified by $R$ as $⟦R⟧=⟦ℒ(R)⟧$. Furthermore, we say that a multispanner $S$ is a regex multispanner if $S=⟦R⟧$ for some multispanner-expression $R$. Note that regex multispanners form a strict subclass of regular multispanners, similar to the class of regex spanners and regular spanners [18].

Multispanners are designed to naturally extend the classical model of spanners from [18] to the setting where variables are mapped to sets of spans instead of single spans. Let us discuss a few particularities of our definitions.

We first note that since classical span-tuples, span-relations and spanners (in the sense of [18]) can be interpreted as special multispan-tuples, multispan-relations and multispanners, respectively, our framework properly extends the classical spanner framework.

A multispan-tuple $t$ allows $[i,j⟩\in t(\text{x})$ and $[k,l⟩\in t(\text{y})$ with and $\text{x}\ne \text{y}$ (and this is also the case for classical span-tuples). However, $[i,j⟩,[k,l⟩\in t(\text{x})$ with is not possible for multispan-tuples, since then representing $[i,j⟩$ and $[k,l⟩$ by parentheses ${}_{\text{x}}{}^{}\text{⊢}\mathrm{\dots }{\text{⊣}}_{\text{x}}$ in the document cannot be distinguished from representing $[i,l⟩$ and $[k,j⟩$. Furthermore, for distinct $s,s^{\prime }\in t(\text{x})$ we require that $s$ and $s^{\prime }$ are disjoint, which is motivated by the fact that without this restriction, the subsequence of all ${}_{\text{x}}{}^{}\text{⊢}$ and ${\text{⊣}}_{\text{x}}$ occurrences could be an arbitrary well-formed parenthesised expression (instead of a sequence ${({}_{\text{x}}{}^{}\text{⊢}{\text{⊣}}_{\text{x}})}^k$); thus, recognising whether a given string over $\mathrm{\Sigma }\cup {\mathrm{\Gamma }}_{𝒳}$ is a proper multiref-word cannot be done by an NFA, as is the case for classical spanners.

Our main motivation for multispanners is that they can express information extraction tasks that are of interest in the context of our extract-transform framework (and that cannot be represented by classical spanners in a convenient way). However, there are other interesting properties of multispanners not related to their application in our extract-transform framework, which deserve further investigation. For example, if $L$ and $L^{\prime }$ are multiref-languages (i. e., $⟦L⟧$ and $⟦L^{\prime }⟧$ are multispanners), then $L\cup L^{\prime }$, $L\cdot L^{\prime }$ and $L^{\ast }$ are also multiref-languages (and therefore $⟦L\cup L^{\prime }⟧$, $⟦L\cdot L⟧$ and $⟦L^{\ast }⟧$ are also multispanners). For classical spanners, this is only true for the union. Consequently, multispanners show some robustness not provided by classical spanners.

An extract-transform program (for short: ET program) is a pair $(E,T)$ such that, for some finite alphabet $\mathrm{\Sigma }$,

• $\mathrm{■}$

  $E$ is a multispanner (over $\mathrm{\Sigma }$ and some finite set $𝒳$ of variables), and

• $\mathrm{■}$

  $T$ is a function that, for every document $𝐃\in {\mathrm{\Sigma }}^{\ast }$, maps $(𝐃,E(𝐃))$ to the desired output.

In other words, given a document $𝐃$, the multispanner $E$ specifies how to extract the relevant data from $𝐃$ as a multispan-relation $E(𝐃)$, and $T$ specifies how to transform the extracted data $(𝐃,E(𝐃))$ into new data. The output of $T$ is application-dependent, and various contexts are conceivable, such as transforming the data into a relational database, a graph database, a single document, or a collection of documents.

One may wonder why we must define the setting in two phases and why not simplify it into one phase. In the end, the purpose of users is to transform data, and then they may like to specify the transformation with a single query language. From a user perspective, we argue that it is useful to have a two-phase specification for several reasons. First, it is already the case that, in practice, people specify the transformation of documents with a two-phase approach. For example, search-and-replace is given by a pattern (i.e., $E$) and the string to be replaced (i.e., $T$). More generally, the so-called regex substitutions [33, 25] are specified by a regex (i.e., $E$) and a replacement pattern (i.e., $T$). Second, in a more general sense, data transformation today is performed between different data models by ETL programs [44] (for Extract-Transform-Load) where the extract and transform steps are specified by different languages with different purposes. We made the same decision here, where multispanners are well-suited for the extraction phase, and we left open the language to be used for the transformation phase (that depends on the application). Last, one can argue that separating the process between extraction and transformation aids in decoupling the source from the target data, simplifying the overall specification for users. Indeed, an expert user in the source data can specify the multispanner $E$, whereas another expert user in the target data can provide the transformation $T$. Moreover, this separation allows that whenever the middle schema (i.e., $𝒳$) is not changed, one can update $E$ or $T$ without modifying the other part.

In this work, we focus on the case where the transformation $T$ is given by a function $M_T$ that maps a pair $(𝐃,t)$ to a document. This means that the transformation $T$ is fully determined by the function $M_T$. For a given document $𝐃$, the output of an ET program $(E,T)$ is a bag of documents defined as follows:

In the introduction, we presented two examples of this setting, where the ET programs map documents into a bag of documents. Next, we provide another example to show that this setting also includes the search-and-replace scenario as a special case.

Our decision to focus on bags (instead of sets) is that each multispan-tuple represents a data item and context in the document. Although $T$ could map two data pieces to the same output document, a user may want to keep both copies, given that they come from different positions in the document. Let us motivate this briefly by a more practical example. Assume that the extraction phase marks the addresses in a list of customer orders, while the transformation phase then transforms these addresses into a format suitable for printing on the parcels to be shipped to the customers. In the likely situation that there are different orders by the same person, the extraction phase produces different markings that will all be transformed into the same address label. Such duplicates, however, are important, since we actually want to obtain an address label for each distinct order (i. e., distinct marking), even if these addresses are the same (although the orders are not). This means that the output sets of our ET programs should actually be bags for this scenario. Indeed, similar situations occur for relational data management systems (and database systems in general) where bag semantics is usually adopted [26]. Of course, one can also consider the scenario when the output is a single document or a set of documents. Both are interesting scenarios, and we leave them for future work (see Section 8 for further discussion).

The main technical goal of this paper is to identify a large class of ET programs $(E,T)$ for which, upon input of any document $𝐃$, the output $⟦E\cdot T⟧(𝐃)$ can be computed efficiently. Arguably, identifying such a large class of ET-programs is crucial for the foundations of extract-transform tasks. On the one hand, it determines which ET-programs can be used in practice and, on the other hand, it guides the design of query languages for the specifications $E$ and $T$, which depends on the application.

In this work, we study the case when $M_T$ is given by a regular function, an expressive class of string-to-string functions that has several equivalent characterizations and good algorithmic properties. In the sequel, we show how to combine the result of a regex multispanner $E$ with a regular function to then present our approach to evaluate such ET programs efficiently.

The representation of documents and multispan-tuples $(𝐃,t)$ by multiref-words allows us to define multispanners by multiref-languages. But this representation is not unique, which is inconvenient if we want to use it for encoding multispan-tuples as strings. As a remedy, we adopt the following approach: We represent a document $𝐃\in {\mathrm{\Sigma }}^{\ast }$ and multispan-tuple $t$ as a multiref-word $w$ such that factors of $w$ that belong to ${\mathrm{\Gamma }}_{𝒳}^{\ast }$ (i.e., factors between two letters of $𝐃$) have the form:  $({\text{⊣}}_{\text{x}}\text{+}\text{ε})({}_{\text{x}}{}^{}\text{⊢}{\text{⊣}}_{\text{x}}\text{+}\text{ε})({}_{\text{x}}{}^{}\text{⊢}\text{+}\text{ε})({\text{⊣}}_{\text{y}}\text{+}\text{ε})({}_{\text{y}}{}^{}\text{⊢}{\text{⊣}}_{\text{y}}\text{+}\text{ε})({}_{\text{y}}{}^{}\text{⊢}\text{+}\text{ε})\mathrm{\dots }.$

Specifically, let $𝐃\in {\mathrm{\Sigma }}^{\ast }$ be a document and $t$ a multispan-tuple over $𝐃$ and variables $𝒳$. For a variable $\text{x}\in 𝒳$ and $i\in [|𝐃|+1]$, define $t[i,x]={({\text{⊣}}_{\text{x}})}^c{({}_{\text{x}}{}^{}\text{⊢}{\text{⊣}}_{\text{x}})}^e{({}_{\text{x}}{}^{}\text{⊢})}^o$, where $c,e,o\in \{0,1\}$ with $c=1$ iff $[j,i⟩\in t(\text{x})$ for some $j\ne i$; $e=1$ iff $[i,i⟩\in t(\text{x})$; and $o=1$ iff $[i,j⟩\in t(\text{x})$ for some $j\ne i$. E. g., for the tuple $t$ in Example 1, we have that $t[3,\text{x}]={}_{\text{x}}{}^{}\text{⊢}$ and $t[4,\text{y}]={\text{⊣}}_{\text{y}}{}_{\text{y}}{}^{}\text{⊢}$.

Let $𝒳=\{{\text{x}}_1,{\text{x}}_2,\mathrm{\dots },{\text{x}}_m\}$ with ${\text{x}}_1⪯{\text{x}}_2⪯\mathrm{\dots }⪯{\text{x}}_m$, where $⪯$ is some fixed linear order on $𝒳$. For every $i\in [|𝐃|+1]$, we define $t[i]:=t[i,{\text{x}}_1]\cdot t[i,{\text{x}}_2]\cdot \mathrm{\dots }\cdot t[i,{\text{x}}_m]$. We can then define the encoding of $t$ and $𝐃$ as the multiref-word:

Coming back to Example 1, we have $\mathrm{𝚎𝚗𝚌}(t,𝐃)=\mathrm{𝚊𝚊}{}_{\text{x}}{}^{}\text{⊢}{}_{\text{y}}{}^{}\text{⊢}𝚋{\text{⊣}}_{\text{y}}{}_{\text{y}}{}^{}\text{⊢}𝚊{\text{⊣}}_{\text{y}}{}_{\text{y}}{}^{}\text{⊢}\mathrm{𝚋𝚋𝚋}{\text{⊣}}_{\text{y}}{}_{\text{y}}{}^{}\text{⊢}\mathrm{𝚊𝚊}{\text{⊣}}_{\text{y}}{}_{\text{y}}{}^{}\text{⊢}𝚋{\text{⊣}}_{\text{y}}{\text{⊣}}_{\text{x}}$ by using the order $\text{x}⪯\text{y}$. Note that $\mathrm{𝚎𝚗𝚌}(t,𝐃)$ is a multiref-word, ${𝐃}_{\mathrm{𝚎𝚗𝚌}(t,𝐃)}=𝐃$ and ${\text{t}}_{\mathrm{𝚎𝚗𝚌}(t,𝐃)}=t$. Thus, $\mathrm{𝚎𝚗𝚌}(t,𝐃)$ is a correct and unique encoding for $t$ and $𝐃$ as a multiref-word.

We are now ready to formally define the following class of ET programs. An ET program $(E,T)$ is called a regular ET program (from $\mathrm{\Sigma }$ to $\mathrm{\Omega }$) if $E$ is a regex multispanner specified by some multispanner-expression $R$ over $\mathrm{\Sigma }$ and some finite set $𝒳$ of variables, and $T$ is specified by a regular string-to-string function $f_T$ with input alphabet $\mathrm{\Sigma }\cup {\mathrm{\Gamma }}_{𝒳}$ and output alphabet $\mathrm{\Omega }$. The result of $(E,T)$ on $𝐃\in {\mathrm{\Sigma }}^{\ast }$ is defined as

Note that this definition of $⟦E\cdot T⟧(𝐃)$ means that we first apply the spanner specified by $R$ on $𝐃$, which produces a multispan-relation $⟦R⟧(𝐃)$. Then, for every multispan-tuple $t\in ⟦R⟧(𝐃)$, we apply $f_T$ on the multiref-word $\mathrm{𝚎𝚗𝚌}(t,𝐃)$ producing a new document in the output bag $⟦E\cdot T⟧(𝐃)$. Note that while $\mathrm{𝚎𝚗𝚌}(\cdot ,\cdot )$ is injective, the function $f_T$ might not be. Hence, for $t,t^{\prime }\in ⟦R⟧(𝐃)$ with $t\ne t^{\prime }$ we might have $f_T(\mathrm{𝚎𝚗𝚌}(t,𝐃))=f_T(\mathrm{𝚎𝚗𝚌}(t^{\prime },𝐃))$. This leads to duplicates, but, as explained before, we keep them, since we want each distinct $t\in ⟦R⟧(𝐃)$ of the extraction phase to correspond to a transformed document in the output.

So far, we have introduced our object of study, regular ET-programs, but we still need to define how to specify them. In particular, how to specify the regular string-to-string function $f_T$. Regular string-to-string functions are a robust class that admit several possible representations and people have proposed logic-based languages to specify them like MSO transductions and regular transducer expressions [10]. In particular, one can use any of them as the basis for a declarative query language for specifying $f_T$. In this paper, we concentrate on the evaluation problem of regular ET-programs. Toward this goal, we use deterministic streaming string transducers (DSSTs, [3]) as our model for defining regular functions.

Let $ℛ$ be a finite set of registers and $\mathrm{\Omega }$ a finite alphabet. An assignment is a partial function $\sigma :ℛ\rightharpoonup {(ℛ\cup \mathrm{\Omega })}^{\ast }$ that assigns each register $X\in ℛ$ to a string $\sigma (X)$ of registers and letters from $\mathrm{\Omega }$. We define the extension $\widehat{\sigma }:{(ℛ\cup \mathrm{\Omega })}^{\ast }\rightharpoonup {(ℛ\cup \mathrm{\Omega })}^{\ast }$ of an assignment such that $\widehat{\sigma }({\alpha }_1\mathrm{\dots }{\alpha }_n)=\sigma ({\alpha }_1)\cdot \mathrm{\dots }\cdot \sigma ({\alpha }_n)$ for every string ${\alpha }_1\mathrm{\dots }{\alpha }_n\in {(ℛ\cup \mathrm{\Omega })}^{\ast }$ where $\sigma (\begin{array}{c}\text{<div class="ltx\_inline-block ltx\_transformed\_outer" style="width:4.8pt;height:4.3pt;vertical-align:-0.0pt;"><span class="ltx\_transformed\_inner" style="transform:translate(0.0pt,0.0pt) scale(1.0,1.0) ;"> <p class="ltx\_p"><xmath xmlns="http://dlmf.nist.gov/LaTeXML"><xmtok role="UNKNOWN" font="italic">o</xmtok></xmath></p> </span></div>}\hfill \\ \text{<div class="ltx\_inline-block ltx\_transformed\_outer" style="width:10.5pt;height:8.4pt;vertical-align:-2.2pt;"><span class="ltx\_transformed\_inner" style="width:9.8pt;transform:translate(0.36pt,0pt) rotate(30deg) ;"> <p class="ltx\_p"><span class="ltx\_text ltx\_font\_sansserif" style="position:relative; bottom:1.7pt;"> <span class="ltx\_inline-block ltx\_transformed\_outer" style="width:9.8pt;height:2.3pt;vertical-align:-0.0pt;"><span class="ltx\_transformed\_inner" style="transform:translate(-2.6pt,0.6pt) scale(0.65,0.65) ;"> <span class="ltx\_p"><xmath xmlns="http://dlmf.nist.gov/LaTeXML"><xmtok lpadding="5.0pt" name="smile" role="RELOP" font="serif bold">⌣</xmtok></xmath></span> </span></span></span></p> </span></div>}\hfill \end{array})=\begin{array}{c}\text{<div class="ltx\_inline-block ltx\_transformed\_outer" style="width:4.8pt;height:4.3pt;vertical-align:-0.0pt;"><span class="ltx\_transformed\_inner" style="transform:translate(0.0pt,0.0pt) scale(1.0,1.0) ;"> <p class="ltx\_p"><xmath xmlns="http://dlmf.nist.gov/LaTeXML"><xmtok role="UNKNOWN" font="italic">o</xmtok></xmath></p> </span></div>}\hfill \\ \text{<div class="ltx\_inline-block ltx\_transformed\_outer" style="width:10.5pt;height:8.4pt;vertical-align:-2.2pt;"><span class="ltx\_transformed\_inner" style="width:9.8pt;transform:translate(0.36pt,0pt) rotate(30deg) ;"> <p class="ltx\_p"><span class="ltx\_text ltx\_font\_sansserif" style="position:relative; bottom:1.7pt;"> <span class="ltx\_inline-block ltx\_transformed\_outer" style="width:9.8pt;height:2.3pt;vertical-align:-0.0pt;"><span class="ltx\_transformed\_inner" style="transform:translate(-2.6pt,0.6pt) scale(0.65,0.65) ;"> <span class="ltx\_p"><xmath xmlns="http://dlmf.nist.gov/LaTeXML"><xmtok lpadding="5.0pt" name="smile" role="RELOP" font="serif bold">⌣</xmtok></xmath></span> </span></span></span></p> </span></div>}\hfill \end{array}$ for every $\begin{array}{c}\text{<div class="ltx\_inline-block ltx\_transformed\_outer" style="width:4.8pt;height:4.3pt;vertical-align:-0.0pt;"><span class="ltx\_transformed\_inner" style="transform:translate(0.0pt,0.0pt) scale(1.0,1.0) ;"> <p class="ltx\_p"><xmath xmlns="http://dlmf.nist.gov/LaTeXML"><xmtok role="UNKNOWN" font="italic">o</xmtok></xmath></p> </span></div>}\hfill \\ \text{<div class="ltx\_inline-block ltx\_transformed\_outer" style="width:10.5pt;height:8.4pt;vertical-align:-2.2pt;"><span class="ltx\_transformed\_inner" style="width:9.8pt;transform:translate(0.36pt,0pt) rotate(30deg) ;"> <p class="ltx\_p"><span class="ltx\_text ltx\_font\_sansserif" style="position:relative; bottom:1.7pt;"> <span class="ltx\_inline-block ltx\_transformed\_outer" style="width:9.8pt;height:2.3pt;vertical-align:-0.0pt;"><span class="ltx\_transformed\_inner" style="transform:translate(-2.6pt,0.6pt) scale(0.65,0.65) ;"> <span class="ltx\_p"><xmath xmlns="http://dlmf.nist.gov/LaTeXML"><xmtok lpadding="5.0pt" name="smile" role="RELOP" font="serif bold">⌣</xmtok></xmath></span> </span></span></span></p> </span></div>}\hfill \end{array}\in \mathrm{\Omega }$. Further, we assume that $\widehat{\sigma }({\alpha }_1\mathrm{\dots }{\alpha }_n)$ is undefined iff $\sigma ({\alpha }_i)$ is undefined for some $i\in [n]$. Given two assignments ${\sigma }_1$ and ${\sigma }_2$, we define its composition ${\sigma }_1\circ {\sigma }_2$ as a new assignment such that $[{\sigma }_1\circ {\sigma }_2](X)={\widehat{\sigma }}_1({\sigma }_2(X))$. We say that an assignment $\sigma$ is copyless if, for every $X\in ℛ$, there is at most one occurrence of $X$ in all the strings $\sigma (Y)$ with $Y\in ℛ$.

Note that copyless assignments are closed under composition, namely, if ${\sigma }_1$ and ${\sigma }_2$ are copyless assignments, then ${\sigma }_1\circ {\sigma }_2$ is copyless as well. We denote by $\text{Asg}(ℛ,\mathrm{\Omega })$ the set of all copyless assignments over registers $ℛ$ and alphabet $\mathrm{\Omega }$.

A deterministic streaming string transducer (DSST) [3] is a tuple $𝒯=(Q,\mathrm{\Sigma },\mathrm{\Omega },ℛ,\mathrm{\Delta },q_0,F)$, where $Q$ is a finite set of states, $\mathrm{\Sigma }$ is the input alphabet, $\mathrm{\Omega }$ is the output alphabet, $ℛ$ is a finite set of registers, $\mathrm{\Delta }:Q\times \mathrm{\Sigma }\rightharpoonup \text{Asg}(ℛ,\mathrm{\Omega })\times Q$ is the transition function, $q_0$ is the initial state, and $F:Q\rightharpoonup {(ℛ\cup \mathrm{\Omega })}^{\ast }$ is a final partial function such that, for every $q\in Q$ and $X\in ℛ$, $X$ appears at most once in $F(q)$. Intuitively, if $F(q)$ is defined, then $q$ is a final (i.e., accepting) state.

A configuration of a DSST $𝒯$ is a pair $(q,\nu )$ where $q\in Q$ and $\nu \in \text{Val}(ℛ,\mathrm{\Omega })$, and $\text{Val}(ℛ,\mathrm{\Omega })$ is the set of all assignments $ℛ\rightharpoonup {\mathrm{\Omega }}^{\ast }$, which are called valuations. A run $\rho$ of $𝒯$ over a string $a_1\mathrm{\dots }{a}_n$ is a sequence of configurations $(q_i,{\nu }_i)$ of the form:

such that $\mathrm{\Delta }(q_i,a_{i+1})=({\sigma }_{i+1},q_{i+1})$, ${\nu }_0$ is the empty assignment, i. e. ${\nu }_0(X)=\text{ε}$ for every $X\in ℛ$, and ${\nu }_{i+1}={\nu }_i\circ {\sigma }_{i+1}$ for every . A run $\rho$ is called an accepting run if ${\nu }_n(F(q_n))$ is defined. The output of an accepting run $\rho$ is defined as the string $\text{out}(\rho ):={\nu }_n(F(q_n))$.

Since $\mathrm{\Delta }$ is a partial function, we can see that DSSTs are deterministic, i.e., for every input word $w$, there exists at most one run $\rho$. Thus, every DSST $𝒯$ defines a string-to-string function $⟦𝒯⟧$ such that $⟦𝒯⟧(w)=\text{out}(\rho )$ iff $\rho$ is the run of $𝒯$ over $w$ and $\rho$ is accepting.

DSSTs define a well-behaved class of string-to-string functions, equivalent to the the class of regular string-to-string functions (see [10, 3]). In other words, we can use DSSTs as our computational model for specifying the function $f_T$ since all other formalisms for declaring regular functions can be effectively compiled into DSSTs (e.g., MSO transductions or regular transducer expressions). Moreover, DSSTs perform a single pass over the input string, while other equivalent models (e.g., two-way transducers) may do several passes. This streaming behavior of DSSTs will be very useful for designing algorithms for regular ET programs. For this reason, we use DSSTs as our model of string-to-string functions for regular ET programs.

We extend DSSTs to the nondeterministic case and bag semantics. Let us explain the model by pointing out its differences to DSSTs.¹¹1Note that nondeterministic streaming string transducers with set semantics instead of bag semantic have already been introduced in [4].

A nondeterministic streaming string transducer (NSST) is a tuple $𝒯=(Q,\mathrm{\Sigma },\mathrm{\Omega },ℛ,\mathrm{\Delta },I,F)$, where $Q$, $\mathrm{\Sigma }$, $\mathrm{\Omega }$, $ℛ$ and $F$ have the same meaning as for DSSTs. The partial function $I:Q\rightharpoonup \text{Val}(ℛ,\mathrm{\Omega })$ plays the role of the initial state, i. e., a state $q$ is a possible initial state if $I(q)$ is defined, and in this case $I(q)$ is an initial valuation of the registers. Moreover, $\mathrm{\Delta }$ is a bag of elements from $Q\times \mathrm{\Sigma }\times \text{Asg}(ℛ,\mathrm{\Omega })\times Q$. Note that we define $\mathrm{\Delta }$ as a bag and not as a set for technical reasons (e.g., the proof of Proposition 10 or Theorem 12).

The semantics of the model are as expected. A run over a string $a_1\mathrm{\dots }{a}_n$ is a sequence of configurations $(q_i,{\nu }_i)$ of the form (4) such that $I(q_0)$ is defined and ${\nu }_0=I(q_0)$, $(q_i,a_{i+1},{\sigma }_{i+1},q_{i+1})\in \mathrm{\Delta }$ and ${\nu }_{i+1}={\nu }_i\circ {\sigma }_{i+1}$ for every . As for DSSTs, $\rho$ is an accepting run if ${\nu }_n(F(q_n))$ is defined, and the output of an accepting run $\rho$ is the string $\text{out}(\rho )={\nu }_n(F(q_n))$. We define ${\text{Runs}}_{𝒯}(a_1\mathrm{\dots }{a}_n)$ as the bag of all accepting runs of $𝒯$ over $a_1\mathrm{\dots }{a}_n$.

Finally, we define the semantics of an NSST $𝒯$ over a string $w\in {\mathrm{\Sigma }}^{\ast }$ as the bag:

We show that regular ET programs and NSSTs are equivalent. This is a fundamental insight with respect to the expressive power of ET programs. Moreover, the fact that the two-stage model of regular ET programs can be described by a single NSST will be important for our enumeration algorithm (Section 6) and their composition (Section 7).

Before going into the technical details, one may wonder why regular ET programs have two phases when this characterization of the expressive power shows that we can do the whole process with a single NSST. As we already argued in Section 3, a two-phase process is designed from a user perspective that aids the declaration of the whole process and helps for the future use of the specifications. On the contrary, the one-phase process of NSSTs is helpful for an algorithmic perspective, where we want to evaluate the ET program as a single process and in a single pass.

We first discuss how regular ET programs can be transformed into NSSTs. Every multiref-word over $\mathrm{\Sigma }$ and $𝒳$ describes a document ${𝐃}_w$ and a multispan-tuple ${\text{t}}_w$. Hence, we can extend the encoding $\mathrm{𝚎𝚗𝚌}(\cdot )$ to multiref-words by setting $\mathrm{𝚎𝚗𝚌}(w)=\mathrm{𝚎𝚗𝚌}({\text{t}}_w,{𝐃}_w)$. Intuitively speaking, applying the function $\mathrm{𝚎𝚗𝚌}(\cdot )$ on a multiref-word $w$ simply means that every maximal factor $u\in {\mathrm{\Gamma }}_{𝒳}^{\ast }$ of $w$ is re-ordered according to the order $⪯$ on $𝒳$, and superfluous matching brackets ${}_{\text{x}}{}^{}\text{⊢}{\text{⊣}}_{\text{x}}$ are removed (since several of those in the same maximal factor over ${\mathrm{\Gamma }}_{𝒳}$ would describe the same empty span several times). We define $\mathrm{𝚎𝚗𝚌}(L)=\{\mathrm{𝚎𝚗𝚌}(w)\mid w\in L\}$ for multiref-languages $L$.

Let us consider a regular ET program $⟦E\cdot T⟧$, i. e., $E$ is a regex multispanner represented by some multispanner-expression $r$, and $T$ is a regular function represented by some DSST $𝒯$. The high-level idea of the proof is to construct an NSST ${𝒯}^{\prime }$ that simulates a DFA $M$ for $\mathrm{𝚎𝚗𝚌}(ℒ(r))$ and the DSST $𝒯$ in parallel. More precisely, we read an input $𝐃\in {\mathrm{\Sigma }}^{\ast }$, but between reading a symbol $𝐃[i]$ and the next symbol $𝐃[i+1]$, we pretend to read a sequence of symbols from ${\mathrm{\Gamma }}_{𝒳}$ with $𝒯$ and $M$ at the same time. Thus, we virtually read some multiref-word $w$ with the property ${𝐃}_w=𝐃$. We need the DSST $𝒯$ for producing an output on that multiref-word, and we need the DFA $M$ to make sure that the virtual multiref-word has the form $\mathrm{𝚎𝚗𝚌}(t,𝐃)$ for some $t\in E(𝐃)$.

One may wonder why we want $M$ to be a DFA rather than an NFA. The reason is: Having to deal with bag semantics (rather than just set semantics) makes things more complicated. In particular, this means that we need $M$ to be deterministic to have a one-to-one correspondence between the accepting runs of ${𝒯}^{\prime }$ and the accepting runs of $M$ on the corresponding multiref-word. Otherwise, if $M$ was an NFA, the different possible accepting paths of $M$ on the same multiref-word would translate into different accepting paths of ${𝒯}^{\prime }$ which would cause erroneous duplicates in $⟦{𝒯}^{\prime }⟧(𝐃)$.

We can transform $r$ into a DFA $M$ for $\mathrm{𝚎𝚗𝚌}(ℒ(r))$ by standard automata constructions, but the fact that $M$ needs to be deterministic means that the construction is (one-fold) exponential in $|r|$, and the fact that it has to accept $\mathrm{𝚎𝚗𝚌}(ℒ(r))$ and not just $ℒ(r)$ means that the construction is also (one-fold) exponential in $|𝒳|$. In summary, we obtain the following.

Let us now move on to representing general NSSTs by ET programs. When an NSST $𝒯$ is in a state $p$ and reads a symbol $b\in \mathrm{\Sigma }$, then the number of possible nondeterministic choices it can make is the sum over all the multiplicities of elements $(p,b,\sigma ,q)\in \mathrm{\Delta }$ (recall that $\mathrm{\Delta }$ is the bag of transitions). We shall call this number the nondeterministic branching factor of $p$ and $b$. The nondeterministic branching factor of $𝒯$ is the maximum over all the nondeterministic branching factors of $p$ and $b$ for all $(p,b)\in Q\times \mathrm{\Sigma }$.

The only obstacle in the simulation of an NSST by a DSST is that the latter cannot deal with the nondeterministic choices. However, in regular ET programs, a DSST gets an annotated version of the actual document $𝐃$ as input, i. e., a multiref-word $w$ with ${𝐃}_w=𝐃$. Consequently, the DSST could interpret the additional information given by $w$ in the form of the symbols from ${\mathrm{\Gamma }}_{𝒳}$ as information that determines which nondeterministic choices it should make. More formally, we can construct a regex multispanner that, for every $i\in [1,2,\mathrm{\dots },|𝐃|]$, nondeterministically chooses some ${\text{x}}_{\mathrm{\ell }}\in \{{\text{x}}_1,{\text{x}}_2,\mathrm{\dots },{\text{x}}_m\}$, where $m$ is the NSST’s nondeterministic branching factor, and puts the empty span $[i,i⟩$ into $t(\text{x})$. On the level of multiref-words, this simply means that every symbol is preceded by ${}_{{\text{x}}_{\mathrm{\ell }}}{}^{}\text{⊢}{\text{⊣}}_{{\text{x}}_{\mathrm{\ell }}}$ for some $\mathrm{\ell }$. Such an occurrence of ${}_{{\text{x}}_{\mathrm{\ell }}}{}^{}\text{⊢}{\text{⊣}}_{{\text{x}}_{\mathrm{\ell }}}$ can then be interpreted by the DSST as an instruction to select the ${\mathrm{\ell }}^{\text{th}}$ nondeterministic choice when processing the next symbol from $\mathrm{\Sigma }$. In summary, we obtain the following result.