Cypher: An Evolving Query Language for Property Graphs

ABSTRACT

The Cypher property graph query language is an evolving language, originally designed and implemented as part of the Neo4j graph database, and it is currently used by several commercial database products and researchers. We describe Cypher 9, which is the first version of the language governed by the openCypher Implementers Group. We first introduce the language by example, and describe its uses in industry. We then provide a formal semantic definition of the core read-query features of Cypher, including its variant of the property graph data model, and its ASCII Art graph pattern matching mechanism for expressing subgraphs of interest to an application. We compare the features of Cypher to other property graph query languages, and describe extensions, at an advanced stage of development, which will form part of Cypher 10, turning the language into a compositional language which supports graph projections and multiple named graphs.

References

1. H. Abelson et al. Revised report on the algorithmic language Scheme. Higher-Order and Symbolic Computation, 11(1):7--105, 1998.
2. S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995.
3. D. Alocci, J. Mariethoz, O. Horlacher, J. T. Bolleman, M. P. Campbell, and F. Lisacek. Property graph vs RDF triple store: A comparison on glycan substructure search. PLOS ONE, 10(12):1--17, 12 2015.
4. B. Amann and M. Scholl. Gram: a graph data model and query languages. In Proceedings of the ACM conference on Hypertext, pages 201--211. ACM, 1992.
5. R. Angles, M. Arenas, P. Barceló, P. Boncz, G. Fletcher, C. Gutiérrez, T. Lindaaker, M. Paradies, S. Plantikow, J. Sequeda, O. van Rest, and H. Voigt. G-CORE A Core for Future Graph Query Languages. In ACM SIGMOD, 2018.
6. R. Angles, M. Arenas, P. Barceló, A. Hogan, J. Reutter, and D. Vrgovc. Foundations of modern query languages for graph databases. ACM Comput. Surv., 50(5):68:1--68:40, Sept. 2017.
7. R. Angles and C. Gutiérrez. Survey of graph database models. ACM Comput. Surv., 40(1):1:1--1:39, 2008.
8. P. Barceló. Querying graph databases. In Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013, New York, NY, USA - June 22 - 27, 2013, pages 175--188, 2013.
9. P. Barceló, L. Libkin, and J. L. Reutter. Querying regular graph patterns. Journal of the ACM, 61(1):8:1--8:54, 2014.
10. T. Bray, J. Paoli, and C. M. Sperberg-McQueen. Extensible markup language (XML). World Wide Web Journal, 2(4):27--66, 1997.
11. M. Cabra. How the ICIJ used Neo4j to unravel the Panama Papers. Neo4j Blog, May 2016. https://neo4j.com/blog/icij-neo4j-unravel-panama-papers/.
12. S. Chu, C. Wang, K. Weitz, and A. Cheung. Cosette: An automated prover for SQL. In CIDR, 2017.
13. S. Chu, K. Weitz, A. Cheung, and D. Suciu. HoTTSQL: Proving query rewrites with univalent SQL semantics. In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 510--524. ACM, 2017.
14. M. Consens and A. Mendelzon. Graphlog: A visual formalism for real life recursion. In 9th ACM Symposium on Principles of Database Systems (PODS), pages 404--416, 1990.
15. B. Cook, A. Podelski, and A. Rybalchenko. Proving program termination. Commun. ACM, 54(5):88--98, 2011.
16. I. F. Cruz, A. O. Mendelzon, and P. T. Wood. A graphical query language supporting recursion. In SIGMOD Conference, pages 323--330. ACM Press, 1987.
17. G. Drakopoulos, A. Kanavos, and A. K. Tsakalidis. Evaluating twitter influence ranking with system theory. In Proceedings of the 12th International Conference on Web Information Systems and Technologies, WEBIST 2016, Volume 1, Rome, Italy, April 23-25, 2016, pages 113--120, 2016.
18. N. Francis, A. Green, P. Guagliardo, L. Libkin, T. Lindaaker, V. Marsault, S. Plantikow, M. Rydberg, M. Schuster, P. Selmer, and A. Taylor. Formal semantics of the language cypher. CoRR, abs/1802.09984, 2018. https://arxiv.org/abs/1802.09984.
19. G. Graefe and W. J. McKenna. The volcano optimizer generator: Extensibility and efficient search. In Data Engineering, 1993. Proceedings. Ninth International Conference on, pages 209--218. IEEE, 1993.
20. P. Guagliardo and L. Libkin. A formal semantics of SQL queries, its validation, and applications. PVLDB, 11(1):27--39, 2017.
21. A. Gubichev. Query Processing and Optimization in Graph Databases. PhD thesis, Technical University Munich, 2015.
22. Y. Gurevich and J. K. Huggins. The semantics of the C programming language. In Computer Science Logic, pages 274--308, 1992.
23. R. H. Güting. Graphdb: Modeling and querying graphs in databases. In VLDB, pages 297--308. Morgan Kaufmann, 1994.
24. M. Gyssens, J. Paredaens, J. V. den Bussche, and D. V. Gucht. A graph-oriented object database model. IEEE Trans. Knowl. Data Eng., 6(4):572--586, 1994.
25. N. Hawes, B. Barham, and C. Cifuentes. FrappÉ: Querying the linux kernel dependency graph. In Proceedings of the GRADES'15, GRADES'15, pages 4:1--4:6. ACM, 2015.
26. J. Hidders. Typing graph-manipulation operations. In ICDT, volume 2572 of Lecture Notes in Computer Science, pages 391--406. Springer, 2003.
27. H. H. Huang and H. Liu. Big data machine learning and graph analytics: Current state and future challenges. In 2014 IEEE International Conference on Big Data (Big Data), pages 16--17, 2014.
28. B. Iordanov. Hypergraphdb: A generalized graph database. In WAIM Workshops, volume 6185 of Lecture Notes in Computer Science, pages 25--36. Springer, 2010.
29. M. Junghanns, A. Petermann, K. Gómez, and E. Rahm. GRADOOP: scalable graph data management and analytics with hadoop. CoRR, abs/1506.00548, 2015.
30. M. Kay. XPath 2.0 programmer's reference. John Wiley & Sons, 2004.
31. A. J. Kfoury, J. Tiuryn, and P. Urzyczyn. An analysis of ML typability. Journal of the ACM, 41(2):368--398, 1994.
32. N. Klarlund, A. Møller, and M. I. Schwartzbach. MONA implementation secrets. Int. J. Found. Comput. Sci., 13(4):571--586, 2002.
33. E. V. Kostylev, J. L. Reutter, M. Romero, and D. Vrgovc. SPARQL with property paths. In The Semantic Web - ISWC 2015, pages 3--18, 2015.
34. J. Larriba-Pey, N. Martínez-Bazan, and D. Domínguez-Sal. Introduction to graph databases. In Reasoning Web, volume 8714 of Lecture Notes in Computer Science, pages 171--194. Springer, 2014.
35. M. Levene and G. Loizou. A graph-based data model and its ramifications. IEEE Trans. Knowl. Data Eng., 7(5):809--823, 1995.
36. M. Levene and A. Poulovassilis. The hypernode model and its associated query language. In Jerusalem Conference on Information Technology, pages 520--530. IEEE, 1990.
37. M. Levene and A. Poulovassilis. An object-oriented data model formalised through hypergraphs. Data Knowl. Eng., 6:205--234, 1991.
38. L. Libkin, W. Martens, and D. Vrgovc. Querying graphs with data. Journal of the ACM, 63(2):14:1--14:53, 2016.
39. A. Lysenko, I. A. Roznovat, M. Saqi, A. Mazein, C. J. Rawlings, and C. Auffray. Representing and querying disease networks using graph databases. BioData Mining, 9(1):23, Jul 2016.
40. S. Malik and L. Zhang. Boolean satisfiability from theoretical hardness to practical success. Commun. ACM, 52(8):76--82, 2009.
41. J. Marton, G. Szárnyas, and M. Búr. Model-driven engineering of an opencypher engine: Using graph queries to compile graph queries. In SDL Forum, volume 10567 of Lecture Notes in Computer Science, pages 80--98. Springer, 2017.
42. R. Milner, M. Tofte, and R. Harper. Definition of Standard ML. MIT Press, 1990.
43. J. C. Mitchell. Concepts in Programming Languages. Cambridge University Press, 2003.
44. G. Moerkotte and T. Neumann. Dynamic programming strikes back. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pages 539--552. ACM, 2008.
45. J. Mullen, S. J. Cockell, P. Woollard, and A. Wipat. An integrated data driven approach to drug repositioning using gene-disease associations. PLOS ONE, 11(5):1--24, 05 2016.
46. T. Neumann. Efficiently compiling efficient query plans for modern hardware. Proceedings of the VLDB Endowment, 4(9):539--550, 2011.
47. openCypher. Cypher Query Language Reference, Version 9, Nov. 2017. https://github.com/opencypher/openCypher/blob/master/docs/openCypher9.pdf.
48. Y. Papakonstantinou, H. Garcia-Molina, and J. Widom. Object exchange across heterogeneous information sources. In ICDE, pages 251--260. IEEE Computer Society, 1995.
49. N. Papaspyrou. A Formal Semantics for the C Programming Language. PhD thesis, NTUA, 253pp, 1998.
50. M. Paradies. Graph pattern matching in SAP HANA. First openCypher Implementers Meeting, Feb. 2017. https://tinyurl.com/ycxu54pr.
51. A. Poulovassilis and M. Levene. A nested-graph model for the representation and manipulation of complex objects. ACM Trans. Inf. Syst., 12(1):35--68, 1994.
52. I. Robinson, J. Webber, and E. Eifrem. Graph databases. O'Reilly Media, 2013.
53. M. A. Rodriguez. The Gremlin graph traversal machine and language. In DBPL, pages 1--10. ACM, 2015.
54. P. G. Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price. Access path selection in a relational database management system. In Proceedings of the 1979 ACM SIGMOD international conference on Management of data, pages 23--34. ACM, 1979.
55. B. A. Steer, A. Alnaimi, M. A. B. F. G. Lotz, F. Cuadrado, L. M. Vaquero, and J. Varvenne. Cytosm: Declarative property graph queries without data migration. In Proceedings of the Fifth International Workshop on Graph Data-management Experiences &Systems, GRADES'17, pages 4:1--4:6, 2017.
56. O. van Rest, S. Hong, J. Kim, X. Meng, and H. Chafi. PGQL: a property graph query language. In GRADES, page 7. ACM, 2016.
57. M. Veanes, N. Tillmann, and J. de Halleux. Qex: Symbolic SQL query explorer. In Logic for Programming, Artificial Intelligence, and Reasoning (LPAR), pages 425--446, 2010.
58. W3C. SPARQL 1.1 Query Language, 2013. http://www.w3.org/TR/sparql11-query/.
59. W3C. RDF 1.1 Concepts and Abstract Syntax, Sept. 2014. http://www.w3.org/TR/rdf11-concepts/.
60. P. T. Wood. Query languages for graph databases. SIGMOD Record, 41(1):50--60, 2012.
61. B.-H. Yoon, S.-K. Kim, and S.-Y. Kim. Use of graph database for the integration of heterogeneous biological data. Genomics & informatics, pages 19--27, 03 2017.

Index Terms

• Information systems

  • Data management systems

    • Database design and models

      • Graph-based database models

    • Query languages

      • Query languages for non-relational engines

• Software and its engineering

  • Software notations and tools

    • Formal language definitions