189 @inproceedings{xml2015,

   190 author = {Bj\"{o}rklund, Henrik and Martens, Wim and Timm, Thomas},

   191 title = {Efficient Incremental Evaluation of Succinct Regular Expressions},

   192 year = {2015},

   193 isbn = {9781450337946},

   194 publisher = {Association for Computing Machinery},

   195 address = {New York, NY, USA},

   196 url = {https://doi.org/10.1145/2806416.2806434},

   197 doi = {10.1145/2806416.2806434},

   198 abstract = {Regular expressions are omnipresent in database applications. They form the structural core of schema languages for XML, they are a fundamental ingredient for navigational queries in graph databases, and are being considered in languages for upcoming technologies such as schema- and transformation languages for tabular data on the Web. In this paper we study the usage and effectiveness of the counting operator (or: limited repetition) in regular expressions. The counting operator is a popular extension which is part of the POSIX standard and therefore also present in regular expressions in grep, Java, Python, Perl, and Ruby. In a database context, expressions with counting appear in XML Schema and languages for querying graphs such as SPARQL 1.1 and Cypher.We first present a practical study that suggests that counters are extensively used in practice. We then investigate evaluation methods for such expressions and develop a new algorithm for efficient incremental evaluation. Finally, we conduct an extensive benchmark study that shows that exploiting counting operators can lead to speed-ups of several orders of magnitude in a wide range of settings: normal and incremental evaluation on synthetic and real expressions.},

   199 booktitle = {Proceedings of the 24th ACM International on Conference on Information and Knowledge Management},

   200 pages = {1541–1550},

   201 numpages = {10},

   202 keywords = {regular expressions, schema, regular path queries, xml},

   203 location = {Melbourne, Australia},

   204 series = {CIKM '15}

   205 }

   206 

   207