Combining Rewriting and Incremental Materialisation Maintenance for\n Datalog Programs with Equality

Materialisation precomputes all consequences of a set of facts and a datalog\nprogram so that queries can be evaluated directly (i.e., independently from the\nprogram). Rewriting optimises materialisation for datalog programs with\nequality by replacing all equal constants with a single representative; and\nincremental maintenance algorithms can efficiently update a materialisation for\nsmall changes in the input facts. Both techniques are critical to practical\napplicability of datalog systems; however, we are unaware of an approach that\ncombines rewriting and incremental maintenance. In this paper we present the\nfirst such combination, and we show empirically that it can speed up updates by\nseveral orders of magnitude compared to using either rewriting or incremental\nmaintenance in isolation.\n