Functional Testing of Graph Query Engines by Automated Graph Generators

OData support
Supervisor:
Dr. Semeráth Oszkár
Department of Measurement and Information Systems

Nowadays the data is stored in multiple formats. One of this is the graph database,

where entities are represented as graph nodes and the relations between entities as edges.

Utilizing rich data structure, a variety of graph querying languages have been created in

order to query complex structures.

Testing of graph query engines is a challenging task, especially in an automated way.

The greatest challenge, in this case, is the automatic and systematic creation of a diverse

set of models and queries, which serve as test inputs. In addition, the development of

performance benchmarks for graph databases would be greatly aided.

The purpose of my thesis is to find solutions to these problems. In my thesis, I will show

an approach to automatically generate a diverse set of models, that can be interpreted

as queries of the graph query engine under test (e.g. Neo4j graph database queries).

Additionally, I propose a testing process.

In the course of my work, I produce models with the help of state-of-the-art logic solvers

(SAT solvers and Graph Solvers), and use neighborhood shapes to ensure their diversity

and create effective equivalence partitioning. The results of the logic solvers are interpreted

as queries and database contents, and the result of query evaluation can be compared to

other implementations. I illustrate my solution in a case study.

This method makes it possible to develop more reliable graph query engines at a lower

cost. And such a set of models translated to multiple graph querying languages can be

used in those graph query engines for performance measurements by measuring response

times.

Downloads

Please sign in to download the files of this thesis.