Highlights Conference 2020 Conference Abstract
Dynamic Complexity of Document Spanners
- Sam M. Thompson
This talk is on the dynamic complexity of document spanners. Document spanners are a formal framework for information extraction which allows us to query text like we would a relational database. The question we investigate is, what is the complexity of computing the results of these queries if the text is subject to updates? To investigate this question, we use the dynamic complexity framework, which defines complexity classes based on the logic needed to write update formulas for a given query. Update formulas are used to keep the result of a query correct when updates to a database occur. If we can write such update formulas, then we can “maintain” that query. In our work, we show that the class of regular spanners can be maintained by the dynamic complexity class DynPROP (update formulas are in quantifier-free first-order logic), that the class DynCQ (update formulas are conjunctive queries) is more expressive than the class of core spanners, and that the class DynFO (update formulas are in first-order logic) is more expressive than generalized core spanners. This talk is based on a paper presented in ICDT 2020 and is joint work with Dominik Freydenberger.