Chapter 03Positioning

This chapter positions GQL within the broader evolution of database models and query languages. We trace the main conceptual lineages that shaped contemporary graph querying, ranging from logic- and graph-oriented formalisms to relational, Semantic Web, and semi-structured paradigms. The aim is to clarify which ideas GQL inherits, which it adapts to property graphs, and where it deliberately departs from established traditions.

The running library example makes these contrasts concrete: following the chain Reader–LibraryAccount–Loan–Book requires a sequence of joins over foreign keys in a relational representation. A document representation can make one access path local through nesting, but shared entities then introduce duplication or references that require cross-document joins, whereas a graph retains the relationships as directly traversable edges (Sadalage and Fowler 2012).

3.1 Scholarly Analysis

The evolution of database models, particularly through the lens of query languages, illustrates a profound shift toward more expressive and flexible methods for data retrieval and manipulation. This evolution is evident in the significant scholarly contributions that have broadened the capabilities of database systems to accommodate complex, non-traditional data structures, especially those represented in graph-based models.

Kuper and Vardi pioneered the integration of formal logic into database systems, significantly enhancing the expressiveness of query languages (Kuper and Vardi 1984). By establishing a logical foundation, their approach facilitated complex queries that were previously infeasible with earlier database models, marking a significant advancement in the theory and application of database logic.

Continuing this trend, Gyssens, Paredaens, and Van Gucht introduced a graph-oriented object model that fundamentally altered how queries could interact with databases (Gyssens et al. 1990). Their model enabled end-users to intuitively query databases through a visual representation of data and schema as graphs, thereby simplifying complex query constructions and making database systems more accessible and easier to manipulate.

The hypernode model developed by Levene and Poulovassilis further expanded the querying capabilities of graph databases by introducing a nested graph structure (Levene and Poulovassilis 1990). This structure enabled the development of a powerful associated query language that could efficiently handle queries over hierarchical and recursive data structures, which are common in applications such as semantic web data and complex networked systems.

Güting introduced GraphDB, providing a specialized framework for modeling and querying graphs within databases, tailored specifically to applications such as geographical information systems and network analysis (Güting 1994). The query language designed for GraphDB was adept at handling connected data and complex relational queries, thus facilitating more sophisticated analyses and optimizations.

The G-Log query language, introduced by Paredaens et al., was another significant advancement, offering a declarative, graph-based language that allowed for the flexible querying of complex objects with identity (Paredaens et al. 1995). G-Log’s ability to express changes in the database schema and instance as graph transformations opened new avenues for dynamic query processing and was particularly impactful in areas requiring advanced pattern matching and traversal capabilities.

Sheng and the Ozsoyoglu team further developed graph query processing techniques, which were crucial for efficiently executing complex queries in large-scale databases (Sheng et al. 1999). Their graph query language addressed the challenges associated with large and interconnected datasets, optimizing query execution to improve both performance and scalability.

Lastly, the nested-graph model by Poulovassilis and Levene provided a robust framework for representing and manipulating complex objects, which was complemented by a highly capable query language (Poulovassilis and Levene 1994). This language facilitated the manipulation of nested structures and complex object relationships, which are essential in fields such as computational biology and document databases.

Earlier work on semistructured data also treated data as labeled graphs and made path navigation central. The Object Exchange Model (OEM) underpinned the Lore repository, whose Lorel language extended the Object Query Language (OQL) with flexible path expressions, while UnQL supplied a language and algebra for rooted edge-labeled graphs based on structural recursion (Abiteboul et al. 1997; Buneman et al. 2000).

An earlier formal treatment of GQL covered a restricted read-only fragment—basic FROM–MATCH–RETURN–WHERE queries with fixed-length rigid patterns—based on the ISO working draft dated 2 February 2020 (Morra 2021). It therefore provides historical context rather than a normative account of the standard used in this book.

3.2 Relational Databases and SQL

The SQL standard has established itself as the central technology for relational database management, with decades of evolution reflected in successive ISO/IEC standardization efforts (ISO/IEC 2023b). Its longevity is due not only to its ubiquity in commercial and open-source systems, but also to a carefully designed combination of data model, typing discipline, transaction model, and declarative query language. As such, SQL constitutes the primary point of comparison for GQL: many of the design decisions in GQL can be read as adaptations of long-established relational ideas to the setting of property graphs, while others deliberately depart from the relational tradition.

At the core of SQL lies a tabular, record-oriented data model. Relations (tables) can be understood as collections of records with a common column structure, and can be naturally viewed as files of records, spreadsheets, or tabular reports. In practice, tables are treated as multisets rather than sets: SQL admits duplicate rows, a feature that proves convenient for representing transactional and event data as they are generated by applications in finance, logistics, or web analytics. Conceptually, such tables can be mapped to text files with a header row and delimited fields, or to logical tables within reporting tools and business intelligence systems. GQL inherits this record orientation: collections of nodes or edges whose property records share the same type are logically equivalent to SQL tables. Each such typed collection can be seen as a possibly overlapping typed subpopulation of the node set $V$ or of the edge set $E$, and these subpopulations are natural sources of binding-table rows in query evaluation. In contrast to SQL, however, GQL’s binding tables disallow multiple columns with the same name, reflecting the importance of unambiguous variable bindings in pattern-based semantics.

An important aspect of SQL’s pragmatic success is its treatment of incomplete information via null values. The language allows individual fields within a row to be marked as having no known value, resulting in three-valued logic in query conditions and a rich, albeit sometimes controversial, semantics for comparison and aggregation in the presence of missing data. This design acknowledges that real-world datasets are often partially known, subject to delayed acquisition, or constrained by privacy and access-control considerations. Although property graphs usually handle the absence of information via missing properties rather than explicit null values, the underlying concern is similar: query languages must remain usable and robust when confronted with incomplete or heterogeneous data.

SQL’s query sublanguage is fundamentally compositional. Queries take one or more input tables and produce an output table, and this closure property underlies both subqueries and views. Nested queries enable the decomposition of complex retrieval tasks into smaller subproblems, while the view mechanism treats fixed queries as virtual tables. Views, whether virtual or materialized, provide multiple perspectives over the same underlying data, support modular query design, and encapsulate physical design decisions such as indexing or partitioning. Compositional closure of the language under its own result type is one of SQL’s most powerful and enduring features. By contrast, present-day GQL is not yet a fully compositional language in this sense, as it lacks a general mechanism for graph-returning subqueries and views that define new persistent graphs. The inability to define graph projections or named graph views within the language constitutes a significant gap relative to SQL, and we return to this issue in our later discussion of possible future enhancements to GQL.

Another pillar of SQL’s design is its schema-governed, closed-world nature. Data must conform to a declared schema that specifies tables, columns, types, and constraints. This strong typing and constraint infrastructure supports data quality, integrity, and consistency: primary keys, foreign keys, uniqueness constraints, and check predicates can all be enforced within the database itself. The metadata describing a schema can be communicated compactly, which in turn supports a regular translation from conceptual data models, such as entity-relationship diagrams (Chen 1976; Elmasri and Navathe 2015; Thalheim 2018) or UML class models (Fowler 2003), to physical database designs. A well-defined type system for field values provides a foundation for portable applications and interoperable tools. At the same time, schema information underpins query planning and optimization: cardinality estimates and other statistics are attached to schema objects, enabling cost-based optimizers to select efficient execution strategies. GQL shares the ambition of being schema-aware, via graph, node, and edge types and associated key and unique constraints, but its current constraint repertoire is considerably weaker than that of mature SQL implementations, especially in areas such as referential integrity, cardinality constraints, and rich domain constraints.

Transactional updates form another domain in which SQL has set long-standing expectations. The language is paired with a transaction model that supports atomic, consistent, isolated, and durable (ACID) execution, typically realized via serializability or well-understood relaxations thereof. Updates operate over schema-defined structures, and the semantics of INSERT, UPDATE, and DELETE statements are defined at the logical level of sets or multisets of rows, even though physical implementations may employ complex logging and indexing schemes. Crucially, transaction boundaries localize the effects of constraint failures. GQL adopts a similar high-level view of transactions over property graphs: its data-modifying operations dynamically validate the applicable graph constraints and graph-type conformance before completing successfully, while broader constraint forms and implementation-defined isolation extensions remain areas for evolution.

The declarative nature of SQL’s data query language is central to its influence. Queries are written as concise statements of interest, multiset comprehensions over tables, rather than as procedural programs with explicit loops and navigational updates. This separation between logical intent and physical access path enables the database system to utilize query optimization techniques that consider storage layout, access methods, and buffering strategies, all of which are transparent to the application. Joins, selections, projections, and aggregations are composed algebraically, and the optimizer is free to reorder and transform these operations as long as the multiset semantics are preserved. Within this declarative framework, relationships between entities are computed through joins based on the equality of attribute values, typically guided by foreign key constraints. This “computed relationship” model is flexible and powerful, but it treats connections between entities as emergent from value equality, rather than as first-class structures.

GQL both inherits and departs from this relational tradition. On the one hand, the property graph data model is firmly record-oriented: nodes and edges carry property records whose types can be aligned with tabular structures. Collections of nodes or edges of the same type can be viewed as tables, supporting familiar ETL pipelines and easing data integration from files, spreadsheets, and relational sources. This record orientation underlies, for example, the tabular graph features in SQL/PGQ (ISO/IEC 2023a), where graph views are projected over existing tabular data. The ease with which property graphs can be layered over existing relational and file-based infrastructures is arguably one of the reasons for their commercial success.

On the other hand, GQL grants relationships a direct representation as edges in a graph, with their own identity and properties. Foreign keys in SQL can be understood as an indirect representation of such relationships via shared values, often requiring additional link tables to represent attributes associated with relationships. In GQL, these attributes can be attached directly to edges, resulting in more transparent and often more concise data models. This direct representation of relationships can be leveraged by systems optimized for edge and path exploration, enabling the efficient discovery of neighborhoods, reachability regions, and complex network patterns.

Finally, the graph-pattern matching sublanguage of GQL, a declarative, graph-oriented pattern language often referred to as GPML (Deutsch et al. 2022), offers expressive capabilities that are difficult to emulate elegantly in SQL. While SQL supports recursive queries, typically via recursive common table expressions, representing multi-hop path patterns, variable-length traversals, or complex topological constraints over large graphs quickly becomes verbose and opaque. In GQL, path patterns and graph patterns enable such traversals to be specified “topologically”, that is, in terms of the shape of the desired paths and neighborhoods, rather than as low-level fixpoint computations over joins. This gives GQL a decisive advantage for tasks centered on graph connectivity, even as SQL remains the more mature and compositional language in the broader landscape of general-purpose database querying.

3.3 RDF and SPARQL

In the domain of the Semantic Web, the development of query languages has been profoundly influenced by established database languages such as SQL and OQL. Standardized as part of the Object Data Management Group (ODMG) object data standard, OQL is a declarative language over an object model with object identity, relationships, collections, and path navigation (Cattell et al. 2000). A notable early effort in this area was RQL (Karvounarakis et al. 2002), which introduced a robust framework combining elementary queries and iterators akin to those found in object query languages (Blakeley et al. 1991). RQL was designed to facilitate data and schema access, allowing queries to target specific types or navigate the RDF graph structure. Despite its comprehensive functionality, RQL’s broad feature set and syntactic complexity led to the development of SeRQL (Broekstra and Kampman 2003), which streamlined query execution by introducing shortcuts like object-property and object lists. Additionally, eRQL (Tolle 2006) emerged as a simplified adaptation of RQL, focusing on a keyword-based query interface that enhanced user accessibility.

Parallel developments included SquishQL and RDQL (Miller et al. 2002), which introduced subgraph matching filters that drew parallels to SQL’s capabilities, and TriQL (Bizer et al. 2005), which extended these ideas by allowing queries over named graphs, thereby enabling evaluations across multiple sets of triples rather than just a single set. Despite their innovations, these languages commonly faced limitations in areas like store management and the definition of protocols for store access, which restricted their practical implementation.

Among these various RDF query languages, SPARQL (Harris and Seaborne 2013; Passant et al. 2013) has ascended as the preeminent standard, recognized for its comprehensive suite of features enabling detailed querying and manipulation of RDF data. SPARQL’s design facilitates complex querying mechanisms that allow users to extract, query, and manipulate data across diverse and heterogeneous data sources. These sources may natively store data in RDF format or present non-RDF data as RDF via middleware solutions, thus extending SPARQL’s utility across different data ecosystems. The influence of SPARQL on GQL is evident in its graph pattern-matching capabilities and the ability to handle complex queries across heterogeneous data sources.

The SELECT query in SPARQL is foundational, enabling the retrieval of raw data values from endpoints and presenting results in a structured tabular format. This function is central to most data retrieval operations, allowing for the precise selection and return of specific data elements. The CONSTRUCT query builds upon this capability by fetching data and reorganizing it into valid RDF structures, thereby facilitating the creation of new RDF graphs from existing data. This feature is particularly beneficial for tasks involving data transformation and integration. Lastly, the ASK query provides a unique function by returning a Boolean result (True or False), which is crucial for performing existence checks or for incorporating conditional logic within applications driven by complex data needs.

3.4 Tree-based Languages

Tree-based data models like JSON and XML have significantly influenced the development of database technologies by providing flexible, hierarchical structures ideal for many modern web and data interchange applications. These formats are inherently non-relational and support nested arrays and objects, which contrasts sharply with the flat, tabular structures typical of SQL databases.

XPath (Robie et al. 2017) and XQuery (Dyck et al. 2017) are two of the most prominent query languages designed for XML data. XPath is used to navigate through elements and attributes in an XML document. It provides powerful syntax to pinpoint parts of an XML document, supporting complex querying capabilities such as Boolean operations, numerical operations, and node testing. XQuery, an extension of XPath, was designed to query and transform collections of XML data. It acts like a database query language but is tailored specifically for XML’s hierarchical structure. Both XPath and XQuery leverage the tree-like nature of XML to perform sophisticated document manipulations and retrievals. GQL draws inspiration from these languages in its approach to handling nested and hierarchical data within graphs, enhancing its capability to model complex relationships.

In JSON, a similar trend is observed with languages such as JSONPath (Gössner et al. 2024), which provides capabilities analogous to XPath but is adapted for JSON’s structure. JSONPath allows for the traversal of JSON objects using a path expression, making extracting and manipulating data from complex JSON structures straightforward. JMESPath (Saryerwinnie 2015) is another JSON query language that extends JSONPath’s capabilities with additional operators and functions for more sophisticated querying and transformation tasks.

SQL:2016 (ISO/IEC 2016) has integrated robust support for JSON. This includes native JSON data types and functions like JSON_VALUE, JSON_QUERY, and JSON_EXISTS, allowing for efficient extraction and manipulation of JSON data within SQL queries. The standard also defines a JSON path language, similar to JSONPath, for navigating and querying JSON documents. Functions such as JSON_OBJECT and JSON_ARRAY facilitate the construction of JSON data from SQL query results, while predicates like IS JSON enable validation of JSON data. This integration allows seamless querying and manipulation of JSON data within a relational database context, combining the strengths of relational and non-relational data models.

LINQ (Language Integrated Query) (Albahari and Albahari 2008) is another influential technology that bridges the gap between programming languages and data queries. It provides a consistent model for managing data across different data sources, including XML and JSON. LINQ enables developers to use familiar list comprehension syntax from languages like C# to query various data structures, treating them as collections in the language itself. This integration enhances the accessibility and power of data manipulation directly within the programming environment.

These tree-based query languages have dramatically shaped the landscape of data querying and manipulation, making it easier for developers to interact with hierarchical data formats directly. Their influence extends to the design of modern database systems and querying interfaces, which increasingly cater to complex, nested data structures prevalent in contemporary applications. GQL’s ability to handle such structures is a testament to these influences, providing a versatile and robust framework for modern data management needs.

3.5 Key-value and Document Databases

Key-value and document databases have also influenced the development of modern query languages by providing models that emphasize flexibility and simplicity, catering to various use cases where traditional relational databases may fall short.

Key-value databases, such as Amazon DynamoDB (Sivasubramanian 2012) and Redis (Da Silva and Tavares 2015), store data as a collection of key-value pairs. This simple data model allows for rapid read and write operations, making key-value databases suitable for high-performance applications and caching mechanisms. The query capabilities in key-value stores are often basic, focusing on efficiently retrieving values based on their keys. However, the key-value concept aligns closely with the property model in property graphs, where each node or edge can have associated key-value pairs representing various properties.

Document databases, such as MongoDB (Banker et al. 2016) and Couchbase (Brown 2012), extend the key-value model by storing structured data (documents) in formats like JSON. Each document contains key-value pairs but can embed complex data structures, such as nested arrays and objects. Document databases represent an expanded concept of key-value databases, allowing for a more nuanced and detailed representation of data. GQL benefits from these concepts by enabling the representation of complex data structures within graph nodes and edges, thus facilitating more detailed and expressive data models.

MongoDB’s query language (Botoeva et al. 2018) offers extensive support for filtering, projecting, and aggregating data, enabling users to perform sophisticated data manipulations and analytics directly within the database. Couchbase supports advanced indexing and querying capabilities by using views and design documents, which allow users to define custom queries, transformations, and aggregations. Other document query languages include ArangoDB’s AQL (ArangoDB 2024), which supports complex querying across JSON documents.

N1QL (Brown 2012) is Couchbase’s query language designed to combine the power and familiarity of SQL with the flexibility of JSON. N1QL allows users to query, manipulate, and transform JSON data using a declarative syntax similar to SQL. Yet another query language is SQL++ (Ong et al. 2014), an extension of SQL designed for semi-structured data models. It builds on the foundation of SQL and expands it to handle nested, schema-less, and flexible data structures commonly found in JSON documents. SQL++ aims to provide a unified query language that bridges the gap between relational and NoSQL databases, allowing seamless integration and querying of heterogeneous data sources.

The influence of these databases on GQL is seen in how GQL handles semi-structured data. GQL’s ability to represent properties on nodes and edges and to manage dynamic and evolving schemas draws inspiration from the document-oriented approach of these databases. Additionally, the efficient query execution and indexing strategies developed for key-value and document databases have informed the design of GQL’s querying mechanisms, ensuring they can handle large, complex graph datasets with high performance.