Incremental recomputation in local languages

We study the problem of maintaining recursively defined 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 are negative ones: we show that a certain property of query languages implies impossibility of such incremental maintenance. The property we use is locality of queries, which is known to hold for relational calculus and various extensions, including those with grouping and aggregate constructs (essentially, plain SQL).

Authors

• Guozhu Dong
• Leonid Libkin
• Limsoon Wong

Keywords

• Incremental recomputation
• First-order logic
• Transitive closure
• Locality
• SQL