Graph Query Language Explained

GQL (Graph Query Language)
Paradigm:Declarative
Family:Query language
Developer:ISO/IEC JTC 1 (Joint Technical Committee 1) / SC 32 (Subcommittee 32) / WG 3 (Working Group 3)
Influenced By:SQL, Cypher, GSQL

GQL (Graph Query Language) is a standardized query language for property graphs first described in ISO/IEC 76120, released in April 2024 by ISO/IEC.

History

The GQL project is the culmination of converging initiatives dating back to 2016, particularly a private proposal from Neo4j to other database vendors in July 2016,[1] and a proposal from Oracle technical staff within the ISO/IEC JTC 1 standards process later that year.[2]

2019 GQL project proposal

In September 2019 a proposal for a project to create a new standard graph query language (ISO/IEC 39075 Information Technology — Database Languages — GQL)[3] was approved by a vote of national standards bodies which are members of ISO/IEC Joint Technical Committee 1(ISO/IEC JTC 1). JTC 1 is responsible for international Information Technology standards. GQL is intended to be a declarative database query language, like SQL.

The 2019 GQL project proposal states:

Official ISO standard

The GQL standard, ISO/IEC 39075:2024 Information technology – Database languages – GQL, was officially published by ISO on 12 April 2024.[4]

GQL project organisation

The GQL project is led by Stefan Plantikow (who was the first lead engineer of Neo4j's Cypher for Apache Spark project) and Stephen Cannan (Technical Corrigenda editor of SQL). They are also the editors of the initial early working drafts[5] of the GQL specification.

As originally motivated,[2] the GQL project aims to complement the work of creating an implementable normative natural-language specification with supportive community efforts that enable contributions from those who are unable or uninterested in taking part in the formal process of defining a JTC 1 International Standard.[6] [7] In July 2019 the Linked Data Benchmark Council (LDBC) agreed to become the umbrella organization for the efforts of community technical working groups. The Existing Languages and the Property Graph Schema working groups formed in late 2018 and early 2019 respectively. A working group to define formal denotational semantics for GQL was proposed at the third GQL Community Update in October 2019.[8]

ISO/IEC JTC 1/SC 32 WG3

Seven national standards bodies (those of the United States, China, Korea, the Netherlands, the United Kingdom, Denmark and Sweden) have nominated national subject-matter experts to work on the project, which is conducted by Working Group 3 (Database Languages) of ISO/IEC JTC 1's Subcommittee 32 (Data Management and Interchange), usually abbreviated as ISO/IEC JTC 1/SC 32 WG3, or just WG3 for short. WG3 (and its direct predecessor committees within JTC 1) has been responsible for the SQL standard since 1987.[9] [10]

ISO stages

ISO stages by date[11]

  1. 2019-09-10 : 10.99 New project approved
  2. 2019-09-10 : 20.00 New project registered in TC/SC work programme
  3. 2021-11-22 : 30.00 Committee draft (CD) registered
  4. 2021-11-23 : 30.20 CD study initiated
  5. 2022-02-25 : 30.60 Close of comment period
  6. 2022-08-29 : 30.92 CD referred back to Working Group
  7. 2022-08-29 : 30.00 Committee draft (CD) registered
  8. 2022-08-30 : 30.20 CD study initiated
  9. 2022-10-26 : 30.60 Close of comment period
  10. 2023-03-22 : 30.99 CD approved for registration as DIS
  11. 2023-03-24 : 40.00 DIS registered
  12. 2023-05-24 : 40.20 DIS ballot initiated: 12 weeks
  13. 2023-08-17 : 40.60 Close of voting
  14. 2023-11-28 : 40.99 Full report circulated: DIS approved for registration as FDIS
  15. 2023-12-11 : 50.00 Final text received or FDIS registered for formal approval
  16. 2024-01-26 : 50.20 Proof sent to secretariat or FDIS ballot initiated: 8 weeks
  17. 2024-03-23 : 50.60 Close of voting. Proof returned by secretariat
  18. 2024-03-23 : 60.00 International Standard under publication
  19. 2024-04-12 : 60.60 International Standard published

GQL property graph data model

GQL is a query language specifically for property graphs. A property graph closely resembles a conceptual data model, as expressed in an entity–relationship model or in a UML class diagram (although it does not include n-ary relationships linking more than two entities). Entities are modelled as nodes, and relationships as edges, in a graph. Property graphs are multigraphs: there can be many edges between the same pair of nodes. GQL graphs can be mixed: they can contain directed edges, where one of the endpoint nodes of an edge is the tail (or source) and the other node is the head (or target or destination), but they can also contain undirected (bidirectional or reflexive) edges.

Nodes and edges, collectively known as elements, have attributes. Those attributes may be data values, or labels (tags). Values of properties cannot be elements of graphs, nor can they be whole graphs: these restrictions intentionally force a clean separation between the topology of a graph, and the attributes carrying data values in the context of a graph topology. The property graph data model therefore deliberately prevents nesting of graphs, or treating nodes in one graph as edges in another. Each property graph may have a set of labels and a set of properties that are associated with the graph as a whole.

Current graph database products and projects often support a limited version of the model described here. For example, Apache Tinkerpop[12] forces each node and each edge to have a single label; Cypher allows nodes to have zero to many labels, but relationships only have a single label (called a reltype). Neo4j's database supports undocumented graph-wide properties, Tinkerpop has graph values which play the same role, and also supports "metaproperties" or properties on properties. Oracle's PGQL supports zero to many labels on nodes and on edges, whereas SQL/PGQ supports one to many labels for each kind of element. The NGSI-LD information model specified by ETSI is an attempt at formally specifying property graphs, with node and relationship (edge) types that may play the role of labels in previously mentioned models and support semantic referencing by inheriting classes defined in shared ontologies.

The GQL project will define a standard data model, which is likely to be the superset of these variants, and at least the first version of GQL is likely to permit vendors to decide on the cardinalities of labels in each implementation, as does SQL/PGQ, and to choose whether to support undirected relationships.

Additional aspects of the ERM or UML models (like generalization or subtyping, or entity or relationship cardinalities) may be captured by GQL schemas or types that describe possible instances of the general data model.

Implementations

Although the GQL Standard is not yet publicly available, the first in-memory graph database that can interpret GQL is available.[13] [14] Aside from the implementation, one can also find a formalization and read the syntax of the specific subset of GQL.[15]

Extending existing graph query languages

The GQL project draws on multiple sources or inputs, notably existing industrial languages and a new section of the SQL standard. In preparatory discussions within WG3 surveys of the history[16] and comparative content of some of these inputs[17] were presented. GQL will be a declarative language with its own distinct syntax, playing a similar role to SQL in the building of a database application. Other graph query languages have been defined which offer direct procedural features such as branching and looping (Apache Tinkerpop's Gremlin,[18]), and GSQL, making it possible to traverse a graph iteratively to perform a class of graph algorithms, but GQL will not directly incorporate such features.[19] [20] However, GQL is envisaged as a specific case of a more general class of graph languages, which will share a graph type system and a calling interface for procedures that process graphs.

SQL/PGQ Property Graph Query

Prior work by WG3 and SC32 mirror bodies, particularly in INCITS Data Management (formerly INCITS DM32), has helped to define a new planned Part 16 of the SQL Standard, which allows a read-only graph query to be called inside a SQL SELECT statement, matching a graph pattern using syntax which is very close to Cypher, PGQL and G-CORE, and returning a table of data values as the result. SQL/PGQ also contains DDL to allow SQL tables to be mapped to a graph view schema object with nodes and edges associated to sets of labels and set of data properties.[21] [22] [23] The GQL project coordinates closely with the SQL/PGQ "project split" of (extension to) ISO 9075 SQL, and the technical working groups in the U.S. (INCITS DM32) and at the international level (SC32/WG3) have several expert contributors who work on both projects.[22] The GQL project proposal mandates close alignment of SQL/PGQ and GQL, indicating that GQL will in general be a superset of SQL/PGQ.

More details about the pattern matching language can be found in the paper "Graph Pattern Matching in GQL and SQL/PGQ"[24] [25]

Cypher

Cypher[26] is a language originally designed by Andrés Taylor and colleagues at Neo4j Inc., and first implemented by that company in 2011. Since 2015 it has been made available as an open source language description[27] with grammar tooling, a JVM front-end that parses Cypher queries, and a Technology Compatibility Kit (TCK) of over 2000 test scenarios, using Cucumber for implementation language portability.[28] The TCK reflects the language description and an enhancement for temporal datatypes and functions documented in a Cypher Improvement Proposal.[29]

Cypher allows creation, reading, updating and deleting of graph elements, and is a language that can therefore be used for analytics engines and transactional databases.

Querying with visual path patterns

Cypher uses compact fixed- and variable-length patterns which combine visual representations of node and relationship (edge) topologies, with label existence and property value predicates. (These patterns are usually referred to as "ASCII art" patterns, and arose originally as a way of commenting programs which used a lower-level graph API.[16]) By matching such a pattern against graph data elements, a query can extract references to nodes, relationships and paths of interest. Those references are emitted as a "binding table" where column names are bound to a multiset of graph elements. The name of a column becomes the name of a "binding variable", whose value is a specific graph element reference for each row of the table.

For example, a pattern    will generate a two-column output table. The first column named    will contain references to nodes with a label   . The second column named    will contain references to nodes with a label   , denoting the city where the person lives.

The binding variables    and    can then be dereferenced to obtain access to property values associated with the elements referred to by a variable. The example query might be terminated with a  , resulting in a complete query like this:

MATCH (p:Person)-[:LIVES_IN]->(c:City)RETURN p.first_name, p.last_name, c.name, c.stateThis would result in a final four-column table listing the names of the residents of the cities stored in the graph.

Pattern-based queries are able to express joins, by combining multiple patterns which use the same binding variable to express a natural join using the    clause:

MATCH (p:Person)-[:LIVES_IN]->(c:City), (p:Person)-[:NATIONAL_OF]->(EUCountry)RETURN p.first_name, p.last_name, c.name, c.stateThis query would return the residential location only of EU nationals.

An outer join can be expressed by   :

MATCH (p:Person)-[:LIVES_IN]->(c:City) OPTIONAL MATCH (p:Person)-[:NATIONAL_OF]->(ec:EUCountry)RETURN p.first_name, p.last_name, c.name, c.state, ec.nameThis query would return the city of residence of each person in the graph with residential information, and, if an EU national, which country they come from.

Queries are therefore able to first project a sub-graph of the graph input into the query, and then extract the data values associated with that subgraph. Data values can also be processed by functions, including aggregation functions, leading to the projection of computed values which render the information held in the projected graph in various ways. Following the lead of G-CORE and Morpheus, GQL aims to project the sub-graphs defined by matching patterns (and graphs then computed over those sub-graphs) as new graphs to be returned by a query. Patterns of this kind have become pervasive in property graph query languages, and are the basis for the advanced pattern sub-language being defined in SQL/PGQ, which is likely to become a subset of the GQL language. Cypher also uses patterns for insertion and modification clauses (   and   ), and proposals have been made in the GQL project for collecting node and edge patterns to describe graph types.

Cypher 9 and Cypher 10

The current version of Cypher (including the temporal extension) is referred to as Cypher 9. Prior to the GQL project it was planned to create a new version, Cypher 10 ['''REF HEADING BELOW'''], that would incorporate features like schema and composable graph queries and views. The first designs for Cypher 10, including graph construction and projection, were implemented in the Cypher for Apache Spark project starting in 2016.[30]

PGQL

PGQL[31] is a language designed and implemented by Oracle Inc., but made available as an open source specification,[32] along with JVM parsing software.[33] PGQL combines familiar SQL SELECT syntax including SQL expressions and result ordering and aggregation with a pattern matching language very similar to that of Cypher. It allows the specification of the graph to be queried, and includes a facility for macros to capture "pattern views", or named sub-patterns. It does not support insertion or updating operations, having been designed primarily for an analytics environment, such as Oracle's PGX product. PGQL has also been implemented in Oracle Big Data Spatial and Graph, and in a research project, PGX.D/Async.[34]

G-CORE

G-CORE is a research language designed by a group of academic and industrial researchers and language designers which draws on features of Cypher, PGQL and SPARQL.[35] [36] The project was conducted under the auspices of the Linked Data Benchmark Council (LDBC), starting with the formation of a Graph Query Language task force in late 2015, with the bulk of the work of paper writing occurring in 2017. G-CORE is a composable language which is closed over graphs: graph inputs are processed to create a graph output, using graph projections and graph set operations to construct the new graph. G-CORE queries are pure functions over graphs, having no side effects, which mean that the language does not define operations which mutate (update or delete) stored data. G-CORE introduces views (named queries). It also incorporates paths as elements in a graph ("paths as first class citizens"), which can be queried independently of projected paths (which are computed at query time over node and edge elements). G-CORE has been partially implemented in open-source research projects in the LDBC GitHub organization.[37] [38] [39]

GSQL

GSQL[40] is a language designed for TigerGraph Inc.'s proprietary graph database. Since October 2018 TigerGraph language designers have been promoting and working on the GQL project. GSQL is a Turing-complete language that incorporates procedural flow control and iteration, and a facility for gathering and modifying computed values associated with a program execution for the whole graph or for elements of a graph called accumulators. These features are designed to enable iterative graph computations to be combined with data exploration and retrieval. GSQL graphs must be described by a schema of vertexes and edges, which constrains all insertions and updates. This schema therefore has the closed world property of an SQL schema, and this aspect of GSQL (also reflected in design proposals deriving from the Morpheus project[41]) is proposed as an important optional feature of GQL.

Vertexes and edges are named schema objects which contain data but also define an imputed type, much as SQL tables are data containers, with an associated implicit row type. GSQL graphs are then composed from these vertex and edge sets, and multiple named graphs can include the same vertex or edge set. GSQL has developed new features since its release in September 2017,[42] most notably introducing variable-length edge pattern matching[43] using a syntax related to that seen in Cypher, PGQL and SQL/PGQ, but also close in style to the fixed-length patterns offered by Microsoft SQL/Server Graph[44]

GSQL also supports the concept of Multigraphs [45] which allow subsets of a graph to have role-based access control. Multigraphs are important for enterprise-scale graphs that need fine-grain access control for different users.

Morpheus: multiple graphs and composable graph queries in Apache Spark

The opencypher Morpheus project[30] implements Cypher for Apache Spark users. Commencing in 2016, this project originally ran alongside three related efforts, in which Morpheus designers also took part: SQL/PGQ, G-CORE and design of Cypher extensions for querying and constructing multiple graphs.[46] The Morpheus project acted as a testbed for extensions to Cypher (known as "Cypher 10") in the two areas of graph DDL and query language extensions.

Graph DDL features include[47]

  1. definition of property graph views over JDBC-connected SQL tables and Spark DataFrames[48]
  2. definition of graph schemas or types defined by assembling node type and edge type patterns, with subtyping[48]
  3. constraining the content of a graph by a closed or fixed schema
  4. creating catalog entries for multiple named graphs in a hierarchically organized catalog
  5. graph data sources to form a federated, heterogeneous catalog
  6. creating catalog entries for named queries (views)

Graph query language extensions include[47]

  1. graph union
  2. projection of graphs computed from the results of pattern matches on multiple input graphs
  3. support for tables (Spark DataFrames) as inputs to queries ("driving tables")
  4. views which accept named or projected graphs as parameters.

These features have been proposed as inputs to the standardization of property graph query languages in the GQL project.

See also

External links

Notes and References

  1. Web site: Creating an Open Industry Standard for a Declarative Property Graph Query Language. Green. Alastair. July 2016. opencypher.org. November 12, 2019.
  2. Web site: Working towards a New Work Item for GQL, to complement SQL PGQ, ANSI INCITS DM32.2 submission DM32.2-2018-00128r1. Green. Alastair. July 2018. opencypher.org. November 12, 2019.
  3. Web site: ISO/IEC 39075 Information Technology — Database Languages — GQL. January 7, 2022. ISO.
  4. Web site: ISO/IEC 39075:2024 Information technology — Database languages — GQL . ISO . 25 May 2024.
  5. Web site: GQL Early Working Draft v2.2.. Eds. Plantikow. Stefan. Cannan. Stephen. October 2019. ISO. November 9, 2019.
  6. Web site: GQL Standard. November 12, 2019.
  7. Web site: GQL Community Updates. November 12, 2019.
  8. Web site: Formal Semantics Working Group. Libkin. Leonid. November 12, 2019.
  9. Web site: JTC 1/SC 32 Data Management and Interchange. ISO/IEC JTC1. October 6, 2019.
  10. Web site: Scope from the original standard, ISO 9075-1987, Database Language SQL. ISO/IEC JTC1. November 9, 2019.
  11. Web site: Iso/Iec 39075:2024 .
  12. Web site: Apache Tinkerpop. Apache Software Foundation. November 11, 2019.
  13. Web site: GQL Parser. GitHub. January 18, 2021.
  14. Web site: First GQL research implementation from Olof Morra at TU Eindhoven!. Alastair Green. January 18, 2021.
  15. Web site: A Semantics of GQL; a New Query Language for Property Graphs Formalized. Olof Morra. January 18, 2021.
  16. Web site: An overview of the recent history of Graph Query Languages. Lindaaker. Tobias. May 2018. opencypher.org. October 6, 2019.
  17. Web site: Summary Chart of Cypher, PGQL, and G-Core. Plantikow. Stefan. May 2018. opencypher.org. November 3, 2019.
  18. Book: Rodriguez, Marko A.. Proceedings of the 15th Symposium on Database Programming Languages. The Gremlin graph traversal machine and language (Invited talk). 2015. 1–10. ACM. 10.1145/2815072.2815073. 1508.03843. 9781450339025. 32623848. November 10, 2019.
  19. Query languages for graph databases. Wood. Peter T.. ACM SIGMOD Record. 25 April 2012. 41. 1. 50–60. ACM. 10.1145/2206869.2206879. 13537601. October 25, 2019.
  20. Foundations of Modern Query Languages for Graph Databases. Angles. Renzo. ACM Computing Surveys. etal. September 2017. 50. 5. 68:1–40. ACM. 10.1145/3104031. 1610.06264. 13526884. November 12, 2019.
  21. Web site: ISO/IEC 9075-16 Information technology — Database languages SQL — Part 16: SQL Property Graph Queries (SQL/PGQ). January 7, 2022. ISO.
  22. Web site: SQL and GQL, W3C Workshop on Web Standardization for Graph Data. Creating Bridges: RDF, Property Graph and SQL.. Hare. Keith. etal. March 2019. W3C. October 6, 2019.
  23. Web site: Property graph extensions for the SQL standard. LDBC 12th TUC.. Trigonakis. Vasileios. July 2019. LBDC. January 7, 2022.
  24. Deutsch. Alin. Francis. Nadime. Green. Alastair. Hare. Keith. Li. Bei. Libkin. Leonid. Lindaaker. Tobias. Marsault. Victor. Martens. Wim. Michels. Jan. Murlak. Filip. 10. 2021-12-12. Graph Pattern Matching in GQL and SQL/PGQ. cs.DB. 2112.06217.
  25. Book: Deutsch . Alin . Francis . Nadime . Green . Alastair . Hare . Keith . Li . Bei . Libkin . Leonid . Lindaaker . Tobias . Marsault . Victor . Martens . Wim . Michels . Jan . Murlak . Filip . Plantikow . Stefan . Selmer . Petra . van Rest . Oskar . Voigt . Hannes . Proceedings of the 2022 International Conference on Management of Data . Graph Pattern Matching in GQL and SQL/PGQ . 2022-06-11 . https://doi.org/10.1145/3514221.3526057 . SIGMOD '22 . New York, NY, USA . Association for Computing Machinery . 2246–2258 . 10.1145/3514221.3526057 . 978-1-4503-9249-5. 245124268 .
  26. Book: Francis, Nadime. Proceedings of the 2018 International Conference on Management of Data. Cypher: An Evolving Query Language for Property Graphs. 27 May 2018. 1433–1445. etal. ACM. 10.1145/3183713.3190657. 9781450347037. 13919896. October 25, 2019.
  27. Web site: Cypher Query Language Reference (Version 9) . etal. opencypher.org. November 10, 2019.
  28. Web site: openCypher Resources. etal. ACM. November 10, 2019.
  29. Web site: CIP2015-08-06 - Date and Time. 15 May 2019. opencypher.org. October 25, 2019.
  30. Web site: Morpheus brings the leading graph query language, Cypher, onto the leading distributed processing platform, Spark.. Rydberg. Mats. etal. July 2016. openCypher. November 3, 2019.
  31. Book: van Rest, Oskar. https://dl.acm.org/citation.cfm?id=2960421/ . Proceedings of the Fourth International Workshop on Graph Data Management Experiences and Systems . PGQL: A property graph query language . etal. June 2016. 1–6 . ACM. 10.1145/2960414.2960421. 978-1-4503-4780-8 . 6806901. October 25, 2019.
  32. Web site: PGQL. pgql.org. October 6, 2019.
  33. Web site: PGQL is an SQL-based query language for the Property Graph data model. . van Rest. Oskar. etal. September 2015. pgql.org. November 3, 2019.
  34. Book: Roth, Nicholas P.. https://dl.acm.org/citation.cfm?doid=3078447.3078454/ . Proceedings of the Fifth International Workshop on Graph Data-management Experiences & Systems . PGX.D/Async: A Scalable Distributed Graph Pattern Matching Engine . etal. 2017. 1–6 . ACM. 10.1145/3078447.3078454. 978-1-4503-5038-9 . 26283328. October 29, 2019.
  35. Book: Angles, Renzo. https://dl.acm.org/citation.cfm?id=3190654/ . Proceedings of the 2018 International Conference on Management of Data . G-CORE: A Core for Future Graph Query Languages . etal. 2018. 1421–1432 . ACM. 10.1145/3183713.3190654. 978-1-4503-4703-7 . 4623760. November 9, 2019.
  36. Web site: G-CORE: The LDBC Graph Query Language Proposal. In archives of FOSDEM 2018.. Voigt. Hannes. February 2018. November 12, 2019.
  37. Web site: G-CORE Grammar and Parser. van Rest. Oskar. 2017. LDBC. November 12, 2019.
  38. Web site: A G-CORE (Graph Query Language) Interpreter, Master's Thesis in Parallel and Distributed Computer Systems, CWI and Vrije Universiteit Amsterdam. Ciocîrdel. Georgiana Diana. 2018. CWI. November 12, 2019.
  39. Web site: G-CORE interpreter on Spark. Ciocîrdel. Georgiana Diana. Boncz. Peter. 2017. LDBC. November 12, 2019.
  40. Web site: GSQL: An SQL-Inspired Graph Query Language. Wu. Mingxi. Deutsch. Alin. November 9, 2019.
  41. Web site: Property Graph Schema, ANSI INCITS DM32.2 SQL Property Graph Extensions Ad Hoc submission sql-pg-2018-0056r1, Neo4j Query Languages Standards and Research Team. Voigt. Hannes. Selmer. Petra. Lindaaker. Tobias. Plantikow. Stefan. Green. Alastair. Furniss. Peter. December 2018. openCypher.org. November 12, 2019.
  42. Web site: GSQL documentation Tigergraph 1.0.. 2017. November 9, 2019.
  43. Web site: Pattern Matching, TigerGraph 2.4 Release Notes.. June 2019. November 9, 2019.
  44. Web site: Query language extensions, Graph processing with SQL Server and Azure SQL Database. etal. 2017. Microsoft Inc.. November 10, 2019.
  45. Web site: Multigraphs, TigerGraph Online Documentation. June 2019. January 7, 2022.
  46. Web site: CIP2017-06-18 Querying and constructing multiple graphs. Taylor. Andrés. Plantikow. Stefan. Selmer. Petra. 2017–2018. opencypher.org. November 12, 2019.
  47. Web site: Multiple graphs and composable queries in Cypher for Apache Spark. openCypher Implementers Meeting V, Berlin.. Kiessling. Max. 2019. opencypher.org. November 9, 2019.
  48. Web site: graphddl-example-ldbc: A cypher-for-apache-spark example showing the use of SqlPropertyGraphSource and GraphDDL to provide a property graph view of a SQL dataset.. Johanssen. Tobias. GitHub. etal. 2019. November 9, 2019.