Adrian Colyer reviews a paper on the mathematical properties behind GraphQL:

The authors study the

computational complexityof GraphQL looking at three central questions:

- The
evaluation problem: what can we say about the complexity of GraphQL query evaluation?- The
enumeration problem: how efficiently can we enumerate the results of a query in practice?- The
response sizeproblem: how large can responses get, and what can we do to avoid obtaining overly large response objects?In order to do this, they need to find some solid ground to use for reasoning. So the starting point is a formalisation of the semantics of GraphQL.

This is a review of a published academic paper rather than a how-to guide, so it’s math-heavy. I am enjoying seeing the development of normal forms for graph processing languages—it’s the beginning of a new generation of normalization purists.

Kevin Feasel

2018-05-23

Graph