Optimization of distributed incremental graph queries

OData support
Szárnyas Gábor
Department of Measurement and Information Systems

As the magnitude of data we process increases in databases, reevaluating entire queries every time an entity is modified becomes costly. The low response time of these queries is crucial for user experience, when the databases are used interactively, \eg when the user is waiting for results on their terminal.

One way of fast query evaluation is the Rete algorithm, that builds a so-called Rete network to execute the queries. It a way of evaluating the queries incrementally, meaning that after the initialization of the network, reevaluation is only done on the parts of the database that are changed. This speed, however comes at the price of having to keep the state of the whole network in memory, which is infeasible for large datasets and/or complex queries. Due to the memory requirements, very large data sets require the distribution of the network.

The goal of this thesis is to design a truly scalable distributed Rete network, that is able to execute complex graph queries by sharding their contents.


Please sign in to download the files of this thesis.