Document Spanners: From Expressive Power to Decision Problems

We examine document spanners, a formal framework for information extraction that was introduced by Fagin, Kimelfeld, Reiss, and Vansummeren (PODS 2013, JACM 2015). A document spanner is a function that maps an input string to a relation over spans (intervals of positions of the string). We focus on document spanners that are defined by regex formulas, which are basically regular expressions with capture groups that map matched subexpressions to corresponding spans, and on core spanners, which extend regex formulas by a relational algebra. The main results are matching upper and lower bounds on the complexity of query evaluation and various aspects of static analysis. Most of these proofs require only little effort, as it is possible to use existing results on three different models from formal language theory and combinatorics on words: Pattern languages, word equations, and regular expressions with back references. This also illustrates how these models can be used as a general toolkit for query languages with string equality operators. This talk is based on the paper with the same name that appeared at ICDT 2016, which is a joint work with Mario Holldack, available at http: //ddfy. de/publications/FH-DSFEPtDP. html

Authors

• Dominik D. Freydenberger
• Mario Holldack

Keywords

No keywords are indexed for this paper.