The Complexity of Incremental View Maintenance

This page demonstrates the main result of our paper Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries :

Given a hierarchical query with factorization width $\mathsf{w}$, a database of size $N$, and $\epsilon \in [0,1]$, we can compute in time $\mathcal{O}(N^{1 + (\mathsf{w} -1)\epsilon})$ a data structure that allows the enumeration of the query result with $\mathcal{O}(N^{1-\epsilon})$ delay.



Please enter an hierarchical query (with one connected component):


The input query is not a valid hierarchical query.



Click to check the following sample queries:

Static width $\mathsf{w}$ = {{widths.static_width}}

Dynamic width: $\delta$ = {{widths.delta_width}}


Preprocessing time: {{widths.static_width == 2 ? '1 + ' : '1 + ' + (widths.static_width - 1)}}$\epsilon$

Preprocessing time: 1

Amortized update time: {{widths.delta_width == 1 ? '' : widths.delta_width}}$\epsilon$

Amortized update time: {{widths.delta_width == 1 ? '' : widths.delta_width}}

Enumeration delay: 1 $-$ $\epsilon$

Enter one value to obtain the others

$\epsilon$:



Preprocessing time:



Amortized update time:



Enumeration delay:



{{error_message}}

Computing...