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

翻译：获取变量的正则表达式, 也称为 regex- formulas, 从文本中提取跨度关系( 以其起始指数和终点指数识别的交互关系) 。 反过来, 普通的文档显示器的类别是 关系代数下的正则公式关闭 。 我们根据常规文档显示器的总计函数, 如总和、 平均值 和 量来调查质询文本的计算复杂性 。 为此, 我们正式定义常规文档显示器的总函数, 并分析精确和近似计算的复杂性 。 更准确地说, 我们显示, 在受限制的案例中, 所有研究过的合计函数都可以在多边时间计算 。 但是, 一般来说, 尽管精确计算是棘手的, 一些总计仍然可以与全圆时随机近比( FPRAS ) 。