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.
a specification [2] and a reference implementation3 of its GraphQL framework. This framework introduces a new type of Web-based data access interfaces that presents an alternative to the notion of REST-based interfaces [6]. Since its release GraphQL has gained significant momentum and has been adopted by an increasing number of users.4
A core component of the GraphQL framework is a query language that is used to express the data retrieval requests issued to GraphQL-aware Web servers. While there already exist a number of implementations of this language (which is not to be confused with an earlier graph query language of the same name [5]), a more fundamental understanding of the properties of the language is missing. This paper presents preliminary work towards closing this gap, which is important to identify fundamental limitations and optimization opportunities of possible implementations and to compare the GraphQL framework to other Web-based data access interfaces such as REST services [6], SPARQL endpoints [3], and other Linked Data Fragments interfaces [8].
queries and querying in the GraphQL framework: Syntactically, GraphQL queries resemble the JavaScript Object Notation (JSON) [1]. However, in contrast to arbitrary JSON objects, GraphQL queries are written in terms of a so-called schema which the queried Web server supports [2]. Informally, such a schema defines types of objects by specifying a set of so-called fields for which the objects may have values; the possible values can be restricted to a specific type of scalars or objects. For instance, Figure 1 presents a GraphQL schema specification about Star Wars movies, which is also given in a JSON-like syntax [2] (we describe the elements in the schema specification in more detail below). Figure 2(a) presents a corresponding GraphQL query that, for the hero of 3 http://graphql.org/code/ 4 http://graphql.org/users/ (note that popular sites such as Coursera, Github, Pinterest are users) } } } type Starship { id: ID! name: String! length(unit: String): Float interface Character { id: ID! name: String! friends: [Character] appearsIn: [Episode]! type Droid implements Character { id: ID! name: String! friends: [Character] appearsIn: [Episode]! primaryFunction: String type Human implements Character { id: ID! name: String! friends: [Character] appearsIn: [Episode]! starships: [Starship] totalCredits: Int } } union SearchResult = Human | Droid | Starship enum Episode { NEWHOPE, EMPIRE, JEDI } type Query { hero(episode: Episode!): Character droid(id: ID!): Droid node(id: ID!): SearchResult the JEDI episode, returns the name and the episodes that the hero appears in; additionally, the query returns the value of either the totalCredits or the primaryFunction field, depending on whether the hero is a human or a droid. The GraphQL specification defines the semantics of such queries by using an operational definition that assumes an “internal function [...] for determining the [...] value of [any possible] field” of any given object [2]. This internal function is not specified any further and, instead, it is left to the implementation what exactly this function does. Hence, the given query semantics is not formally grounded in any specific data model. However, the data that is exposed via a GraphQL interface can be conceived of as a virtual, graph-based view of an underlying dataset; this view is established by the implementation of the aforementioned internal function and it takes the form of a graph that is similar to a Property Graph [7].
As a basis for our work we define a logical data model that formally captures the notion of this graph, as well as the corresponding notion of a GraphQL schema (cf. Section 2). Thereafter, based on our data model, we formalize the semantics of GraphQL queries by using a compositional approach (cf. Section 3). These are the main conceptual contributions of the paper. As a technical contribution we use our formalization to study the computational complexity of the language (cf. Section 4). We show that, even though the size of query results may be exponential in the size of the queries, the evaluation decision problem lies in a very low complexity class; it can be solved in
2
the foundation of GraphQL. However, the specification implicitly assumes a logical data model that is implemented as a virtual, graph-based view over some underlying DBMS.
2.1
We consider the following infinite countable sets: Fields (field names, §2.5 of [2]), Arguments (argument names, §2.6 of [2]), Types (type names, §3.1 of [2]) , and we assume that Fields, Arguments and Types are disjoint and that there exists a finite hero[episode:JEDI]{ name appearsIn on Human{ totalCredits } on Droid{ primaryFunction } set Scalars (scalar type names, §3.1.1 of [2])5 which is a subset of Types. We also consider a set Vals of scalar values, and a function values : Scalars ! 2Vals that assigns a set of values to every scalar type.
F, A, and T be finite sets such that F Fields, A Arguments, and T Types. We also assume that T is the disjoint union of OT (object types, §3.1.2 of [2]), IT (interface types, §3.1.3 of [2]), UT (union types, §3.1.4 of [2]) and Scalars, and we denote by LT the set f[ t ] j t 2 Tg of list types constructed from T (cf. §3.1.7 of [2]).
We now have all the necessary to define a GraphQL schema over (F; A; T). Definition 1. A GraphQL schema S over (F; A; T) is composed of three assignments: – fieldsS : (OT [ IT) ! 2F that assigns a set of fields to every object or interface type, – argsS : F ! 2A that assigns a set of arguments to every field, – typeS : F [ A ! T [ L that assigns a type or a list type to every field and argument, where arguments are assigned scalar types; i.e., typeS(a) 2 Scalars for all a 2 A, and functions that define interface and union types: – unionS : UT ! 2OT that assigns a nonempty set of object types to every union type, – implementationS : IT ! 2OT that assigns a set of object types to every interface. Additionally, S contains a distinguished type qS 2 OT called the query type.
non-null types (cf. §3.1.8 of [2]), and a mutation type (§3.3 of [2]). However, we capture the concept of interfaces and their implementation (cf. §3.1.3 of [2]) by introducing a notion of consistency. Informally, a GraphQL schema is consistent if every object type that implements an interface type i defines at least all the fields that i defines. Formally, S is consistent if fieldsS(i) fieldsS(t) for every t 2 implementationS(i). From now on we assume that all GraphQL schemas in this paper are consistent.
Example 1. The schema specified in Figure 1 may be captured as S over (F; A; T) with F = fid f ; name; friends; appearsIn; starships; totalCredits;
primaryFunction; length; hero; droid; nodeg; A = fida; unit; episodeg; and T = OT [ IT [ UT [ Scalars such that:
OT = fHuman; Droid; Starship; Queryg; Scalars = fID; String; Int; Float; Episodeg; IT = fCharacterg; UT = fSearchResultg:
separately in the GraphQL specification (cf. §3.1.5 of [2]).
As we can see in Figure 1, in the original GraphQL syntax, object types are defined using the keyword type, interface types with the keyword interface, and union types with the keyword union. Also notice that the schema in Figure 1 introduces both a field and an argument with name id. To avoid ambiguities we have used two di erent names: id f and ida. The values for the scalar types are implicit in their names (String; Float; Int) except for ID which is a special scalar type used for unique identifiers in a GraphQL schema specification (cf. §3.1.1.5 of [2]), and Episodes which is an enum type such that values(Episodes) = fNEWHOPE; EMPIRE; JEDIg. Regarding the functions that compose S we have that fieldsS defines the assignments: Starship ! fidf ; name; lengthg; Character ! fidf ; name; friends; appearsIng;
Droid ! fidf ; name; friends; appearsIn; primaryFunctiong; Human ! fidf ; name; friends; appearsIn; starships; totalCreditsg;
Query ! fhero; droid; nodeg: argsS defines the assignments: and typeS defines the assignments: ida ! ID; idf ! ID; droid ! Droid; length ! funitg; droid ! fidag; hero ! fepisodeg; node ! fidag; episode ! Episode; friends ! [Character]; appearsIn ! [Episode]; totalCredits ! Int; primaryFunction ! String; unit ! String; name ! String; hero ! Character; node ! SearchResult; length ! Float;
unionS(SearchResult) = fHuman; Droid; Starshipg; implementationS(Character) = fHuman; Droidg:
in a graph-based form. Such a graph is a directed, edge-labeled multigraph in which each node has a type and properties. We define this graph by using the aforementioned domain (F; A; T). Then, each node in the graph is associated with an object type from T. The edge labels, as well as the names of node properties, consist of a field name from F and a set of arguments, where such an argument is a pair consisting of a distinct argument name from A and a corresponding value (note that the set of arguments may be empty). The value of each node property is either a single scalar value or a sequence thereof. The following definition captures our notion of a GraphQL graph formally. Definition 2. A GraphQL graph over (F; A; T) is a tuple G = (N; E; ; ) where: – N is a set of nodes, – E is a set of edges of the form (u; f[ ]; v) where u; v 2 N, f 2 F, and is a partial mapping from A to Vals, – : N ! OT is a total function that assigns a type to every node, and
is a partial function that assigns a scalar value v 2 Vals or a sequence [v1 vn] of scalar values (vi 2 Vals) to some pairs of the form (u; f[ ]) where u 2 N, f 2 F, and is a partial mapping from A to Vals.
Example 2. Figure 3 illustrates a small GraphQL graph Gex = (Nex; Eex; ex; ex) over the domain (F; A; T) as given in Example 1. Gex contains two nodes, Nex = fn0; n1g, and three edges, including (n0; droid[ 1]; n1) 2 Eex with 1(ida) = 2001. Function ex defines the assignments: n0 ! Query; n1 ! Droid; and function ex defines the assignments:
(n1; id f [ ;]) ! 2001; (n1; appearsIn[ ;]) ! [NEWHOPE EMPIRE JEDI]: (n1; name[ ;]) ! "R2-D2";
any particular GraphQL schema. However, for the purpose of defining queries over such a graph, the graph is assumed to conform to a given schema. Informally, the conditions that conformance to a schema imposes on a GraphQL graph are summarized as follows:
schema specifies for the type of the source node of the edge. The type that the schema associates with this field name must match the type of the target node of the edge, and if this type associated with the field name is not a list type, then the target node is the only node connected to the source node by an edge with the given field name. Moreover, for every argument associated with an edge, the argument name must be among the argument names that the schema associates with the field name that labels the edge, and the value of the argument must be of the type associated with that argument name. In addition to these conditions for the edge labels, there exist similar conditions for the node properties. Finally, the graph must contain a designated node whose type is the query type of the schema. Providing a formal definition of these conditions is straightforward. Due to space limitations, we therefore omit the definition in this paper.
3
ticular, we first define a concise syntax of GraphQL queries that resembles closely the
we define a formal semantics of these queries. However, before going into the formal definitions, we give some intuition of the expressions based on which GraphQL queries may be constructed and how these expressions are evaluated over a GraphQL graph.
The most basic construction in our syntax of GraphQL queries are expressions of the form f[ ]. Informally, when evaluated over a GraphQL graph, such an expression can be used to match node properties whose name has the same form. Then, assuming the value of the property is a scalar value v, or a sequence [v1 vn] of scalar values, then the result of the evaluation is a string of the form f:v, or f:[v1 vn]. An alternative to the construction f[ ] is `:f[ ] which captures the notion of “field aliases” (cf. §2.7 of [2]). Such aliases can be used to rename the field names that appear in the query result. That is, when using this alternative construction, the results will be strings of the form `:v or `:[v1 vn].
To match edges, expressions of the form f[ ]{'} can be used, where ' is a subquery to be evaluated in the context of the target nodes. Then, for the case of a single matching edge, the result is a string of the form f:{ } with being the string resulting from the evaluation of the subquery '. On the other hand, if the number of matching edges may be greater than one (which may be the case if the type associated with field f is a list type), then the result string is of the form f:[{ 1} { n}]. Expressions of the form f[ ]{'} can also be prefixed with a field alias: `:f[ ]{'}.
Our query syntax introduces two more constructions: on t{'} and '1 'n. While the latter is simply an enumeration of multiple subexpressions whose results are meant to be concatenated, the former captures the notion of a “type condition” that is given by what the GraphQL specification refers to as an “inline fragment” (cf. §2.8.2 of [2]). Hence, t is either an object type, an interface type, or a union type, and ' is a subquery to be evaluated only for non-terminal nodes whose associated (object) type is compatible with t (a formal definition of this notion of compatibility follows shortly).
ification may notice that we do not capture a number of additional language features, namely, (non-inline) “fragments” (§2.8 of [2]), “variables” (§2.10 of [2]), and “directives” (§2.12 of [2]). We emphasize that these features are merely syntactic sugar that a query parser may resolve by using the features captured in the presented syntax.
Definition 3. A GraphQL query over (F; A; T) is an expression constructed from the following grammar where [, ], {, }, :, and on are terminal symbols, f 2 F, ` 2 Fields, t 2 OT [ IT [ UT, and represents a partial mapping from A to Vals. ' ::= f[ ] j `:f[ ] j f[ ]{'} j `:f[ ]{'} j on t{'} j ' '
tax), for sub-expressions of the form f[ ] with the empty mapping, we just write f.
semantics described in the GraphQL specification assume that queries satisfy a notion of validity w.r.t. a given GraphQL schema (cf. §5 of [2]). We make the same assumption.
Definition 4. Let S be a GraphQL schema over (F; A; T), let Q be a GraphQL query over (F; A; T), and let t be a type in OT [ IT [ UT T. Then, Q conforms to S in the context of t , denoted by Q j=t S, if Q satisfies the following conditions: 1. If Q is of the form f[ ] or `:f[ ], then – t < UT, f 2 fieldsS(t ), dom( ) argsS(f), and – assuming typeS(f) = t or typeS(f) = [t], t 2 Scalars. 2. If Q is of the form f[ ]{'} or `:f[ ]{'}, then – t < UT, f 2 fieldsS(t ), dom( ) argsS(f), and t .
– assuming typeS(f) = t or typeS(f) = [t], t < Scalars and ' j= S 34.. IIff QQ iiss ooff tthhee ffoorrmm o'n1 t{''}n,, tthheenn ''i j=j=tt SS. for every 'i 2 f'1; ::: ; 'ng. Moreover, we say that Q conforms to S if Q j=qS S (where qS is the query type of S).
Definition 5. A GraphQL result object is constructed from the following grammar where ` 2 Fields, v; v1; ::: ; vn 2 Vals, and {, }, [, ], :, and null are terminal symbols: ::= `:v j `:[v1 vn] j `:{ } j `:[{ } { }] j j `:null
Definition 6. Let G = (N; E; ; ) be a GraphQL graph over (F; A; T), let Q be a GraphQL query over (F; A; T), and let S be a GraphQL schema over (F; A; T) such that G and Q conform to S. The S-specific evaluation of Q over G from node u 2 N, denoted by JQKGu, is a GraphQL result object that is defined recursively as follows.
Jf[ ]KGu = ( f: (u; f[ ]) if (u; f[ ]) 2 dom( )
f:null else.
J`:f[ ]KGu = ( `: (u; f[ ]) if (u; f[ ]) 2 dom( )
`:null else.
J f[ ]f'gKGu = <>>>>8 ff::{[{'J'KGvKGv}1} > >
J >> f:null > > > > : J `:f[ ]f'gKGu = <>>>>8 ``::{[{'J'KGvKGv}1} > >
J >> `:null > > > > : {J'KGvk }] if typeS(f) 2 LT and fv1; ::: ; vkg = fvi j (u; f[ ]; vi) 2 Eg if typeS(f) < LT and (u; f[ ]; v) 2 E if typeS(f) < LT and there is no v 2 N s.t. (u; f[ ]; v) 2 E {J'KGvk }] if typeS(f) 2 LT and fv1; ::: ; vkg = fvi j (u; f[ ]; vi) 2 Eg if typeS(f) < LT and (u; f[ ]; v) 2 E if typeS(f) < LT and there is no v 2 N s.t. (u; f[ ]; v) 2 E 8 'KGu if t 2 OT and (u) = t >>> J Jon tf'gKGu = ><>>>>>> JJ''KKGGuu iiff tt 22 UITT aanndd ((uu)) 22 iumnipolenmS(etn)tationS(t)
>:> " in other case. (" denotes the empty word) J'1 'kKGu = J'1KGu
J'kKGu Finally, the S-specific evaluation of Q over G, denoted by J'KG, is simply J'KG = J'KGu where u is the single node in G such that (u) = qS.
In the third and fourth cases in Definition 6 whenver typeS(f) 2 LT the evaluation produces a sequence from a set of nodes fv1; ::: ; vkg. Notice that the order of the sequence depends on the order in which we consider the nodes in the previous set. The original GraphQL specification implicitly assumes an order associated to every outgoing edge in the graph, and this order is used to produce the mentioned sequences. To keep our formalization as simple as possible we did not formally introduce these order relations in this paper. of this example query over the graph in Example 2.
Example 5. Consider the GraphQL query in Figure 2(a) and the GraphQL schema S introduced in Example 1. Figure 2(b) illustrates the result of the S-specific evaluation 4
Proposition 1. For every GraphQL query ' and GraphQL graph G it holds that J'KG is of size O(jGjj'j). Moreover, there exists a family of queries f'ngn 1 and a graph G, such that every query 'n is of size O(n) but the evaluation J'nKG is of size (2n). Proof (sketch). Consider a schema with an object type Person with fields name and knows such that name is a scalar, and knows is a list in which every element is of type Person. Additionally, the query type q S has a single field query of type Person. (v; knows; x); (w; knows; v); (x; knows; v)g, (u) = qS, (v) = Let G = (V; E; ; ) be such that V = fu; v; w; xg, E = f(u; query; v); (v; knows; w); (w) = (x) = Person, (v; name) = Alice. Consider now the queries given by the following recurrence 1 = name; and
i = knows{knows{ i 1}} (for every i > 1); and define 'n as query{ n}. It is clear that the size of 'n is linear in n but the evaluation of 'n over G is of size exponential in n; in fact, the name Alice occurs 2 n 1 times over the evaluation function in Definition 6. in J'n G. The exponential upper bound can be proved by a simple induction argument K tu
We now go to some of the related decision problems for GraphQL. Notice that the result of a GraphQL query is not a set of tuples (as it is for more classical query languages). Thus, we need to introduce some further notions to properly define the evaluation decision problem in our context. Given two GraphQL result objects and 0, we say that occurs in 0 if
is a substring of 0. Notice that a result object may occur several times in another. We next introduce the notion of removing a result object. Assume that occurs in 0, then the result object obtained by removing from 0 is the substring of 0 obtained from deleting an (arbitrary) occurrence of and then recursively performing the following procedure: 1. delete every substring of the form {}, 2. delete every substring of the form `:[] (with ` 2 Fields),
1 = p:{n:Alice knows:[{n:Bob}{n:Charly}] son:{n:Dylan knows:[{n:Ed}]}} 2 = n:Dylan knows:[{n:Ed}] 3 = p:{n:Alice knows:[{n:Bob}{n:Charly}]} 4 = p:{n:Alice knows:[{n:Bob}]} 5 = knows:[{n:Bob}] Then 2 occurs in 1. Also notice that, although 3 does not occur in 1, result object 3 is obtained from 1 by removing 2. Now, we say that is a reduction of 0 if can be obtained from 0 by removing some result objects that occur in it. Finally, we say that is a subresult of 0 if occurs in a reduction of 0. Considering our example above, we have that 4 is a reduction of 3 and thus is also a reduction of 1. Moreover, since 5 occurs in 4, we have that 5 is a subresult of 1. Intuitively, when is a subresult of 0, we know that all the data in appears in 0 respecting the structure of the original result object. With these definitions we can formalize the following decision problem: Problem : GqlEval
Question : is a subresult of J'KG? Theorem 1. GqlEval is NL-complete.
objects as trees. Intuitively, a query can be seen as a edge-labeled tree that follows the structure of the {} symbols. For instance the GraphQL query a{b{c d} e{f}} can be represented as a tree in which the root has a single outgoing a-labeled edge to a node, say n, with two outgoing edges labeled with b and e. The b-child of n has two outgoing edges labeled with c and d, while the e-child of n has only one f-labeled outgoing edge. For result objects the situations is similar but structures of the form a:[{ 1} { k}] represents several a-labeled edges to every one of the trees constructed from 1; ::: ; k, and structures of the form a:v with v a scalar, represent an edge pointing to a leaf node labeled with v. With this representation we can talk about root, paths, and leaves in
We now have all the necessary to sketch the NL membership of GqlEval. First we guess the position, say p, of a label in ', and a node, say u, in G. The intuition is that p represents the part of the query ' that when evaluated over G from node u contains as a subresult object. This last property can be checked in NL as follows. We first check that matches the schema of query ' at position p. To this end, we consider every edge of the form a:v (that is, an edge to a leaf node) in and its corresponding path from the root of . Lets denote by Pa:v this path (which is essentially a sequence of labels). Then we check that there is a path in the query ' starting at p that matches Pa:v. Notice that we are performing reachability tests that can de done in NL (actually in L since the reachability is on trees). We still need to check two further properties: (1) that node u can be reached from the query node in G by following the corresponding path in ' from the root to position p, and that (2) the data in result object can actually be obtained To check (2) we only need to iterate over all leaves of the form a:v in and check that there exists a path in G from u to a node v that matches the labels of the path from the root of
to a:v, and such that (v; a) = v. It can be proven that these checks are a necessary and su
cient condition to check that
a directed graph G with N nodes and two nodes u and v, we create a GraphQL graph G0 by adding a label, say a to every edge, an initial query node q to G, an edge labeled q from q to u, and a data value, say 1, associated to attribute b in node v. Types of nodes in G0 are arbitrary. Then we consider the sequence of queries constructed recursively as 0 = b and i = b a{ i 1}, and the query ' = q{ N 1}. It is not di cult to argue that
object b:1 is a subresult of J'KG0 if and only if v is reachable from u in G. is a subresult of J'KG. 5
formalized its syntax and semantics and presented some initial complexity results. This new language opens several interesting directions for future research.
more practical problems related to GraphQL, including the parallel evaluation of queries and the estimation of the size of a result object before computing the result. Our initial findings show that, as for the case of the evaluation decision problems, these problems also have a very low computational complexity.
query language with classical query languages. An immediate candidate in terms of expressive power and complexity is the language of acyclic conjunctive queries (ACQs).
that NL ( LOGCFL, the membership of GqlEval in NL shows an important di erence in terms of complexity between the two languages.