An initial analysis of facebook's GraphQL language

Abstract

Facebook's GraphQL is a recently proposed, and increasingly adopted, conceptual framework for providing a new type of data access interface on the Web. The framework includes a new graph query language whose semantics has been specified informally only. The goal of this paper is to understand the properties of this language. To this end, we first provide a formal query semantics. Thereafter, we analyze the language and show that it has a very low complexity for evaluation. More specifically, we show that the combined complexity of the main decision problems is in NL (Nondeterministic Logarithmic Space) and, thus, they can be solved in polynomial time and are highly parallelizable.