License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2021.4
URN: urn:nbn:de:0030-drops-137124
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13712/
Schmid, Markus L. ;
Schweikardt, Nicole
A Purely Regular Approach to Non-Regular Core Spanners
Abstract
The regular spanners (characterised by vset-automata) are closed under the algebraic operations of union, join and projection, and have desirable algorithmic properties. The core spanners (introduced by Fagin, Kimelfeld, Reiss, and Vansummeren (PODS 2013, JACM 2015) as a formalisation of the core functionality of the query language AQL used in IBM’s SystemT) additionally need string equality selections and it has been shown by Freydenberger and Holldack (ICDT 2016, Theory of Computing Systems 2018) that this leads to high complexity and even undecidability of the typical problems in static analysis and query evaluation. We propose an alternative approach to core spanners: by incorporating the string-equality selections directly into the regular language that represents the underlying regular spanner (instead of treating it as an algebraic operation on the table extracted by the regular spanner), we obtain a fragment of core spanners that, while having slightly weaker expressive power than the full class of core spanners, arguably still covers the intuitive applications of string equality selections for information extraction and has much better upper complexity bounds of the typical problems in static analysis and query evaluation.
BibTeX - Entry
@InProceedings{schmid_et_al:LIPIcs.ICDT.2021.4,
author = {Schmid, Markus L. and Schweikardt, Nicole},
title = {{A Purely Regular Approach to Non-Regular Core Spanners}},
booktitle = {24th International Conference on Database Theory (ICDT 2021)},
pages = {4:1--4:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-179-5},
ISSN = {1868-8969},
year = {2021},
volume = {186},
editor = {Yi, Ke and Wei, Zhewei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13712},
URN = {urn:nbn:de:0030-drops-137124},
doi = {10.4230/LIPIcs.ICDT.2021.4},
annote = {Keywords: Document spanners, regular expressions with backreferences}
}
|
Keywords: |
|
Document spanners, regular expressions with backreferences |
|
Collection: |
|
24th International Conference on Database Theory (ICDT 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
11.03.2021 |
