An Algorithm to Normalize GraphQL Queries

This project is designed for bachelor students, but it may also be extended into a master-student project.

Description: After developing and using it internally for three years, in 2016, Facebook released a specification and a reference implementation of a framework, called GraphQL, that introduces a new type of Web-based data access interfaces. This framework has become highly popular and is employed by an increasing number of users including Coursera, Twitter, Github, and Pinterest.
A core component of this GraphQL framework is a query language for expressing the data retrieval requests issued to GraphQL-aware Web servers. In an ongoing research collaboration between the Universidad de Chile and Linköping University we are studying this new query language. In this context we have defined a normal form for GraphQL queries and a set of corresponding rewriting rules based on which any given GraphQL query can be rewritten into a query that is in the normal form. An advantage of queries that are in this normal form is that they allow for an application of more efficient query execution algorithms (more technically, a query execution algorithm that only focuses on these normal form queries does not need to perform what is called "field collection" in GraphQL). However, while we have formally proven the correctness of the rewriting rules and the desirable properties of the normal form, there does not yet exist an actual algorithm that can be used to perform the query rewriting in practice.
Therefore, the goal of this thesis project is to develop such a query rewriting algorithm based on the aforementioned rewriting rules. Then, the algorithm has to be implemented prototypically and its characteristics have to be evaluated experimentally.

Prerequisites: Students who want to work on this project should have read a course on Database Technology. Additionally, good programming experience is recommended (ideally using JavaScript).

Contact: Olaf Hartig.

Page responsible: Olaf Hartig
Last updated: 2018-10-26