FDB Research

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 $w$ , a database of size $N$ , and $ϵ \in [0, 1]$ , we can compute in time $O (N^{1 + (w - 1) ϵ})$ a data structure that allows the enumeration of the query result with $O (N^{1 - ϵ})$ 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:

{{sample_query}}

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

Dynamic width: $δ$ = {{widths.delta_width}}

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

Preprocessing time: 1

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

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

Enumeration delay: 1 $-$ $ϵ$

Enter one value to obtain the others

$ϵ$ :

Preprocessing time:

Amortized update time:

Enumeration delay:

{{error_message}}

Computing...