{'fraction_non_alphanumeric': 0.015161502966381015, 'fraction_numerical': 0.0, 'mean_word_length': 5.515021459227468, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Properties of Languages That Make Recursive Views Unmaintainable

We study the problem of maintaining recursively-deened views, such as the transitive closure of a relation, in traditional relational languages that do not have recursion mechanisms. The main results of this paper show that in most cases such incremental maintenance is impossible if either no auxiliary relations are used or they are limited to be deterministic. Instead of concentrating on proving these results for some particular languages, we try to identify properties of query languages that make such incremental maintenance impossible. That is, we want to use known results on expressive power of languages to derive new results on expressiveness of incremental recomputation. We identify two properties, studied previously in the literature on expressive power of query languages and nite-model theory, that imply unmaintainability of several recursive queries under insertions or deletions. Furthermore, using known results on expressive power of query languages, we simplify existing proofs on unmaintainability of the transitive closure and same-generation queries in relational calculus, and derive new results showing that these queries remain inexpressible in the presence of aggregate functions. Finally, we relate the complexity of updating transitive closure to that of updating the same-generation query and show that the latter is strictly harder than the former, and we extend this to updating queries based on context-free sets.