Evaluation of openCypher graph queries with a local search-based algorithm

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

Since the 1970s database management had been almost exclusively based on

relational technologies. However, the last decade saw the birth and rise of

dozens of

systems faciliating nonrelational models. One particular branch of these so-called NoSQL

systems are graph databases, which usually employ the distinctive ``property graph'' model.

Neo4j, which is arguably the most popular such graph database provides

its own language called Cypher. Following the heritage of SQL, the openCypher

initiative - established in 2015 - set on a mission to standardize the language,

with the incentive to reach general adoption and compatibility between


The ingraph system, developed at the Department of Measurement and Information Systems,

features incremental query evaluation. This approach supports effective

execution of repeated queries by caching interim results, however it is not suitable

for running complex one-off queries. For these, algorithms using graph exploration

may prove far more suitable. In my work, I extend and adapt a dynamic

programming based polynomial time

algorithm for ingraph. My engine is already able to handle a wide range of

patterns defined on openCypher, such as vertex, edge and type criteria,

negative patterns and can be extended to support more constraints and patterns.

I support the performance and scalability properties of the system

with benchmarks.


Please sign in to download the files of this thesis.