The Complexity of Aggregates over Extractions by Regular Expressions

The Complexity of Aggregates over Extractions by Regular Expressions
复制标题

聚合相对于正则表达式提取的复杂性

DOI：
--
复制
发表时间：
2020
期刊：
International Conference on Database Theory
影响因子：
--
通讯作者：
W. Martens
W. Martens
中科院分区：
--
文献类型：
--
作者：
J. Doleschal;Noa Bratman;B. Kimelfeld;W. Martens

文献摘要

被引文献

相似文献

带有捕获变量的正则表达式，也称为regex-formulas， 提取跨度（由其开始和结束标识的间隔）的关系 索引）的文本。反过来，常规文档空间的类是 关系代数下正则表达式的闭包。我们调查的 通过聚合函数查询文本的计算复杂度，例如sum， 平均值和分位数。为此我们 在常规文档空间上正式定义聚合函数，并分析 精确计算和近似计算的计算复杂性。更 准确地说，我们表明，在一个限制的情况下，所有研究的聚合函数， 可以在多项式时间内计算。一般来说，虽然精确 计算是棘手的，一些聚合仍然可以近似为 全多项式时间随机近似格式（FPRAS）
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).