The present paper investigates the dynamic complexity of document spanners, a formal framework for information extraction introduced by Fagin, Kimelfeld, Reiss, and Vansummeren (JACM 2015). We first look at the class of regular spanners and prove that any regular spanner can be maintained in the dynamic complexity class DynPROP. This result follows from work done previously on the dynamic complexity of formal languages by Gelade, Marquardt, and Schwentick (TOCL 2012). To investigate core spanners we use SpLog, a concatenation logic that exactly captures core spanners. We show that the dynamic complexity class DynCQ is more expressive than SpLog and therefore can maintain any core spanner. This result is then extended to show that DynFO can maintain any generalized core spanner and that DynFO is more powerful than SpLog with negation.
 Welcome to my talk titled Dynamic Complexity of Document Spanners. This is based on work done with Dominic Freidenberger. The question we try and answer with our work is what is the complexity of querying text which is subject to updates. As the title of this talk suggests, by querying text we mean document spanners. The idea behind document spanners is simple. We have regx formulas which extracts tables from our text. We then allow a relational algebra on the extracted tables and we have classes based on what operators we allow. Here's an example of a regx formula. All a regx formula is is a regular expression with variables. This formula has one variable x which is either wine or cake and x is any prefix in any suffix. So given a text like this, this one has three occurrences of wine or cake. We get a table with three entries. Each entry represents the interval in the text with the match occurs for that variable. We can have formulas with more variables which gives us tables with more columns. We can also have multiple formulas to give us multiple tables on which we can do our algebra. We now look at the classes of spanners we will use. First, regular spanners. This is regx formulas where we allow projection, union and join on the extracted tables. If we extend this with string equality we get core spanners. All string calls does is checks whether intervals at different positions represent the same sub word. If we further extend this with set difference we get generalized core spanners. These three classes form a hierarchy. Now moving on to the complexity side we use the dynamic complexity framework introduced by Pat Nakanimamun. The idea is we want to avoid recomputing query results after an update. To do this we store extra relations in an auxiliary database. Any change to our main database or input database triggers our auxiliary relations to be updated. We then have descriptive complexity classes based on the expressiveness of the logic needed to update the auxiliary relations. More formally we have a finite set known as a domain, an origin on that domain and for each symbol in alphabet we have a unary relation which labels nodes of our domain. This makes up the input structure. We then have updates on this input structure which are the form setting a node to a symbol or setting a node to an empty word. This implies that the length of the word is often smaller than the size of the domain. And we have an auxiliary structure which is a set of relations over the input structures domain. Each relation has an update formula for each type of modification and the update formulas are in a fragment of first order logic. Here are the four classes we look at. First, DINFO, this is where update formulas are in first order logic. We have DINPROP, where update formulas are quantifier free first order logic. We have DINCQ, where update formulas are conjunctive queries and we have DINUCQ, where update formulas are unions of conjunctive queries. It is known that DINPROP is a proper subclass of DINFO and under the assumptions we work with DINUCQ and DINCQ are equivalent. This was shown by Zeiman and Shrentik. Here are our main results. First, regular spanners can be maintained in DINPROP. By maintained we mean any relation that can be expressed by a regular spanner can be correctly updated using quantifier free update formulas. We have that DINCQ is more expressive than core spanners and we have DINFO is more expressive than generalized core spanners. To show regular spanners are in DINPROP. It is known that automata can be maintained in DINPROP. It is also known that instead of REGX formulas we can use v automata for regular spanners. Hence, with a bit of work we can maintain regular spanners in DINPROP. Our main result is that DINCQ is more expressive than core spanners. We prove this by maintaining the equal substring relation, by maintaining regular constraints and then using splog as an intermediate model. Splog is a logic which captures core spanners. Using a word structure like this one we would get an equal substring relation like this which is just saying here that 1 is equal to 3, 2 is equal to 5 and the subword 1, 2 is equal to the subword 3, 5. We also have regular constraints which is given a regular language. We have every subword that is a member of that regular language. To maintain the equal substring relation we look at all the cases and for each case we produce an update formula. Here is an example of one case. We have that this tuple is not a member of the equal substring relation but if we update 2 to be a b we have that 1, 2. This subword is equal to 3, 5. This subword they are both a b so we have that tuple in the relation. Moving on to splog this was a logic introduced by Frydenberger. It is based on weird equations and regular constraints. It allows for existential quantification, conjunction and disjunction. Splog captures core spanners and if we add negation on top of this we get a generalized core spanners. Here is an example of a splog formula which follows the example from earlier. We say there exists a prefix in the suffix such that our weird w is equal to the prefix a variable x in the suffix and that x is either wine or cake. So stepping back and looking at our main result we prove that any relation expressible by splog can be maintained in dintcq which would mean that dintcq is at least as powerful as core spanners. We use the equal substring relation for the weird equations. We use regular constraints which we can maintain from work done by Galadatal. Didn't you see q update formulas can have conjunction, disjunction and existential quantification. We use this for structural induction on our splog formulas and under our assumptions we have that dintcq and dintcq are equivalent hence we can maintain any relation expressible by splog in dintcq. We go one step further and we prove that dintcq is more expressive than core spanners. To do this we give relations which we can maintain in dintcq but which aren't expressible by splog and in fact dintcq can maintain relations which aren't even expressible by generalized core spanners. Here's an example of such relation. This gives us all pairs of subwords of our input database such that the number of a's in both the subwords is equal. So here the consequences of our results. First we have upper bounds for the three main classes of spanners. We hope that this work could lead to efficient algorithms for querying dynamic text and we also have some consequences for dynamic complexity. We can use splog or splog with negation as shorthand for dintcq and dintfo and we also get some free results such that a large class of regular expressions with back references are in dintcq. Thank you.
 Welcome to my talk titled Dynamic Complexity of Document Spanners. This is based on work  done with Dominic Freidenberger. The question we try and answer with our work is what is  the complexity of querying text which is subject to updates. As the title of this talk suggests,  by querying text we mean document spanners. The idea behind document spanners is simple.  We have regx formulas which extracts tables from our text. We then allow a relational  algebra on the extracted tables and we have classes based on what operators we allow.  Here's an example of a regx formula. All a regx formula is is a regular expression with  variables. This formula has one variable x which is either wine or cake and x is any  prefix in any suffix. So given a text like this, this one has three occurrences of wine  or cake. We get a table with three entries. Each entry represents the interval in the  text with the match occurs for that variable. We can have formulas with more variables which  gives us tables with more columns. We can also have multiple formulas to give us multiple  tables on which we can do our algebra. We now look at the classes of spanners we will  use. First, regular spanners. This is regx formulas where we allow projection, union  and join on the extracted tables. If we extend this with string equality we get core spanners.  All string calls does is checks whether intervals at different positions represent the same  sub word. If we further extend this with set difference we get generalized core spanners.  These three classes form a hierarchy. Now moving on to the complexity side we use the  dynamic complexity framework introduced by Pat Nakanimamun. The idea is we want to avoid  recomputing query results after an update. To do this we store extra relations in an auxiliary  database. Any change to our main database or input database triggers our auxiliary relations  to be updated. We then have descriptive complexity classes based on the expressiveness of the  logic needed to update the auxiliary relations. More formally we have a finite set known as  a domain, an origin on that domain and for each symbol in alphabet we have a unary relation  which labels nodes of our domain. This makes up the input structure. We then have updates  on this input structure which are the form setting a node to a symbol or setting a node  to an empty word. This implies that the length of the word is often smaller than the size  of the domain. And we have an auxiliary structure which is a set of relations over the input  structures domain. Each relation has an update formula for each type of modification and the  update formulas are in a fragment of first order logic. Here are the four classes we  look at. First, DINFO, this is where update formulas are in first order logic. We have  DINPROP, where update formulas are quantifier free first order logic. We have DINCQ, where  update formulas are conjunctive queries and we have DINUCQ, where update formulas are  unions of conjunctive queries. It is known that DINPROP is a proper subclass of DINFO  and under the assumptions we work with DINUCQ and DINCQ are equivalent. This was shown by  Zeiman and Shrentik. Here are our main results. First, regular spanners can be maintained  in DINPROP. By maintained we mean any relation that can be expressed by a regular spanner  can be correctly updated using quantifier free update formulas. We have that DINCQ is  more expressive than core spanners and we have DINFO is more expressive than generalized  core spanners. To show regular spanners are in DINPROP. It is known that automata can  be maintained in DINPROP. It is also known that instead of REGX formulas we can use v  automata for regular spanners. Hence, with a bit of work we can maintain regular spanners  in DINPROP. Our main result is that DINCQ is more expressive than core spanners. We  prove this by maintaining the equal substring relation, by maintaining regular constraints  and then using splog as an intermediate model. Splog is a logic which captures core spanners.  Using a word structure like this one we would get an equal substring relation like this  which is just saying here that 1 is equal to 3, 2 is equal to 5 and the subword 1, 2  is equal to the subword 3, 5. We also have regular constraints which is given a regular  language. We have every subword that is a member of that regular language. To maintain  the equal substring relation we look at all the cases and for each case we produce an  update formula. Here is an example of one case. We have that this tuple is not a member  of the equal substring relation but if we update 2 to be a b we have that 1, 2. This  subword is equal to 3, 5. This subword they are both a b so we have that tuple in the  relation. Moving on to splog this was a logic introduced by Frydenberger. It is based on  weird equations and regular constraints. It allows for existential quantification, conjunction  and disjunction. Splog captures core spanners and if we add negation on top of this we get  a generalized core spanners. Here is an example of a splog formula which follows the example  from earlier. We say there exists a prefix in the suffix such that our weird w is equal  to the prefix a variable x in the suffix and that x is either wine or cake. So stepping  back and looking at our main result we prove that any relation expressible by splog can  be maintained in dintcq which would mean that dintcq is at least as powerful as core spanners.  We use the equal substring relation for the weird equations. We use regular constraints  which we can maintain from work done by Galadatal. Didn't you see q update formulas can have  conjunction, disjunction and existential quantification. We use this for structural induction on our  splog formulas and under our assumptions we have that dintcq and dintcq are equivalent  hence we can maintain any relation expressible by splog in dintcq. We go one step further  and we prove that dintcq is more expressive than core spanners. To do this we give relations  which we can maintain in dintcq but which aren't expressible by splog and in fact dintcq can  maintain relations which aren't even expressible by generalized core spanners. Here's an example  of such relation. This gives us all pairs of subwords of our input database such that  the number of a's in both the subwords is equal. So here the consequences of our results.  First we have upper bounds for the three main classes of spanners. We hope that this work  could lead to efficient algorithms for querying dynamic text and we also have some consequences  for dynamic complexity. We can use splog or splog with negation as shorthand for dintcq  and dintfo and we also get some free results such that a large class of regular expressions  with back references are in dintcq. Thank you.
FreydenbergerThompson_0_263.png FreydenbergerThompson_264_455.png FreydenbergerThompson_456_1007.png FreydenbergerThompson_1008_1415.png FreydenbergerThompson_1416_2111.png FreydenbergerThompson_2112_2459.png FreydenbergerThompson_2460_3023.png FreydenbergerThompson_3024_3923.png FreydenbergerThompson_3924_5183.png FreydenbergerThompson_5184_6143.png FreydenbergerThompson_6144_6755.png FreydenbergerThompson_6756_7895.png FreydenbergerThompson_7896_8327.png FreydenbergerThompson_8328_8579.png FreydenbergerThompson_8580_9887.png FreydenbergerThompson_9888_10703.png FreydenbergerThompson_10704_11699.png FreydenbergerThompson_11700_12551.png FreydenbergerThompson_12552_13403.png FreydenbergerThompson_13404_13531.png