Semantics and Complexity of GraphQL

ABSTRACT

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. This has prevented the formal study of the main properties of the language. We embark on the formalization and study of GraphQL. To this end, we first formalize the semantics of GraphQL queries based on a labeled-graph data model. Thereafter, we analyze the language and show that it admits really efficient evaluation methods. In particular, we prove that the complexity of the GraphQL evaluation problem is NL-complete. Moreover, we show that the enumeration problem can be solved with constant delay. This implies that a server can answer a GraphQL query and send the response byte-by-byte while spending just a constant amount of time between every byte sent. Despite these positive results, we prove that the size of a GraphQL response might be prohibitively large for an internet scenario. We present experiments showing that current practical implementations suffer from this issue. We provide a solution to cope with this problem by showing that the total size of a GraphQL response can be computed in polynomial time. Our results on polynomial-time size computation plus the constant-delay enumeration can help developers to provide more robust GraphQL interfaces on the Web.

References

1. 4Catalyzer Corporation. 2017. GraphQL Validation Complexity. https://github.com/4Catalyzer/graphql-validation-complexity/. (2017).
2. Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. 2007. On Acyclic Conjunctive Queries and Constant Delay Enumeration Computer Science Logic, 21st International Workshop, CSL 2007, 16th Annual Conference of the EACSL, Lausanne, Switzerland, September 11--15, 2007, Proceedings. 208--222.
3. Nadia Creignou, Markus Kröll, Reinhard Pichler, Sebastian Skritek, and Heribert Vollmer. 2017. On the Complexity of Hard Enumeration Problems. In Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Umeå, Sweden, March 6--9, 2017, Proceedings. 183--195.
4. Arnaud Durand, Nicole Schweikardt, and Luc Segoufin. 2014. Enumerating answers to first-order queries over databases of low degree Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS'14, Snowbird, UT, USA, June 22--27, 2014. 121--131.
5. Facebook, Inc.. 2016. GraphQL. Working Draft, Oct. 2016. Online at: http://facebook.github.io/graphql, retrieved on Dec. 12, 2016. (Oct.. 2016).
6. Georg Gottlob, Nicola Leone, and Francesco Scarcello. 2001. The complexity of acyclic conjunctive queries. J. ACM Vol. 48, 3 (2001), 431--498.
7. Olaf Hartig and Jorge Pérez. 2017. An Initial Analysis of Facebook's GraphQL Language Proceedings of the 11th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW).
8. D. S. Johnson. 1990. A catalog of complexity classes. In Handbook of Theoretical Computer Science, J. van Leeuwen (Ed.). Vol. Vol. A. Elsevier, Chapter 2.
9. Wojciech Kazana and Luc Segoufin. 2013. Enumeration of first-order queries on classes of structures with bounded expansion Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013, New York, NY, USA - June 22 - 27, 2013. 297--308.
10. Markus Kröll, Reinhard Pichler, and Sebastian Skritek. 2016. On the Complexity of Enumerating the Answers to Well-designed Pattern Trees 19th International Conference on Database Theory, ICDT 2016, Bordeaux, France, March 15--18, 2016. 22:1--22:18.
11. Ivo Meißner. 2017. GraphQL Query Complexity Analysis for graphql-js. https://github.com/ivome/graphql-query-complexity/. (2017).
12. Reinhard Pichler and Sebastian Skritek. 2013. Tractable counting of the answers to conjunctive queries. J. Comput. Syst. Sci. Vol. 79, 6 (2013), 984--1001.
13. Leonard Richardson, Mike Amundsen, and Sam Ruby. 2013. RESTful Web APIs. O'Reilly Media, Inc.
14. Luc Segoufin. 2013. Enumerating with constant delay the answers to a query Joint 2013 EDBT/ICDT Conferences, ICDT '13 Proceedings, Genoa, Italy, March 18--22, 2013. 10--20.
15. Luc Segoufin and Alexandre Vigny. 2017. Constant Delay Enumeration for FO Queries over Databases with Local Bounded Expansion 20th International Conference on Database Theory, ICDT 2017, March 21--24, 2017, Venice, Italy. 20:1--20:16.
16. Stem Disintermedia, Inc.. 2016. Join Monster. https://github.com/stems/join-monster. (2016).
17. Stem Disintermedia, Inc.. 2017. GraphQL Depth Limit. https://github.com/stems/graphql-depth-limit/. (2017).
18. Moshe Y. Vardi. 1982. The Complexity of Relational Query Languages (Extended Abstract) Proceedings of the 14th Annual ACM Symposium on Theory of Computing, May 5--7, 1982, San Francisco, California, USA. 137--146.
19. Mihalis Yannakakis. 1981. Algorithms for Acyclic Database Schemes. In Very Large Data Bases, 7th International Conference, September 9--11, 1981, Cannes, France, Proceedings. 82--94.

Index Terms

• Information systems

  • Data management systems

    • Database design and models

      • Graph-based database models

    • Query languages

      • Query languages for non-relational engines

  • World Wide Web

    • Web services

      • RESTful web services

      • Service discovery and interfaces