Query Evaluation over SLP-Represented Document Databases with Complex Document Editing
Markus L. Schmid, Nicole Schweikardt · 2022
It is known that the query result of a regular spanner over a single document D can be enumerated after O(|D|) preprocessing and with constant delay in data complexity (Florenzano et al., ACM TODS 2020, Amarilli et al., ACM TODS 2021). It has been shown (Schmid and Schweikardt, PODS'21) that if the document is represented by a straight-line program (SLP) S, then enumeration is possible with a delay of O(log |D|), but with preprocessing that is linear in |S| (which, in the best case, is logarithmic in |D|). Hence, this compressed setting allows for spanner evaluation in sub-linear time, i.e., with logarithmic upper bounds for preprocessing and delay, if the document is highly-compressible.