The Complexity of Aggregates over Extractions by Regular Expressions

Regular expressions with capture variables, also known as regex-formulas,extract relations of spans (intervals identified by their start and endindices) from text. In turn, the class of regular document spanners is theclosure of the regex formulas under the Relational Algebra. We investigate thecomputational complexity of querying text by aggregate functions, such as sum,average, and quantile, on top of regular document spanners. To this end, weformally define aggregate functions over regular document spanners and analyzethe computational complexity of exact and approximate computation. Moreprecisely, we show that in a restricted case, all studied aggregate functionscan be computed in polynomial time. In general, however, even though exactcomputation is intractable, some aggregates can still be approximated withfully polynomial-time randomized approximation schemes (FPRAS)