Pith. sign in

REVIEW 2 minor 40 references

Reviewed by Pith at T0; open to challenge.

T0 means a machine referee read the full paper against a public rubric. The mark states how deep the mechanical check went, never who wrote it. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

A compositional language for property graphs combines refined regular path queries and #Datalog to fill expressivity gaps in GQL and SQL/PGQ.

2026-06-26 06:30 UTC pith:FSSBAFMJ

load-bearing objection The paper gives a concrete proposal for fixing the compositionality gap in GQL and SQL/PGQ via cleaned RPQs with variables plus #Datalog, and the high-level design looks coherent on the abstract.

arxiv 2606.23399 v1 pith:FSSBAFMJ submitted 2026-06-22 cs.DB cs.LOcs.PL

A Compositional Language for Property Graphs

Marcelo Arenas , Leonid Libkin , Wim Martens This is my paper
classification cs.DB cs.LOcs.PL
keywords property graphsgraph query languagesregular path queriesDatalogcompositionalityGQLSQL/PGQNLOGSPACE
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Standardized graph query languages can express reachability and first-order queries but fall short of full NLOGSPACE expressivity, which is surprising given that reachability is NLOGSPACE-complete. The paper systematically addresses this by proposing a language with cleaned-up regular path queries that support variables and data comparisons, paired with a fully compositional #Datalog variant for transforming graphs. This setup allows arbitrary composition between graph patterns and relational queries while supporting construction of new graphs from nodes, edges, lists, and paths. A reader would care because the standards committee has identified the gap and is seeking extensions, and this provides a principled way to close it without losing compatibility. If correct, the language can express all NLOGSPACE problems and offers a concrete proposal for updating the standards.

Core claim

The central claim is that a language built from cleaned regular path queries with variables and data value comparisons, together with the #Datalog language supporting complete construction of new graph elements, provides full compositionality between graph patterns and relational queries, thereby addressing the expressivity shortcomings of GQL and SQL/PGQ at the NLOGSPACE level and suggesting a path for their extension.

What carries the argument

The key machinery consists of cleaned-up regular path queries with variables and data value comparisons, plus the #Datalog graph-to-graph language that fully supports constructing new graphs from paths and other elements.

Load-bearing premise

The cleaned-up regular path queries with variables and the #Datalog language together provide exactly the missing NLOGSPACE expressivity and stay compatible with GQL and SQL/PGQ semantics.

What would settle it

Finding a specific NLOGSPACE problem that cannot be expressed using the proposed language components, or showing that some existing GQL query behaves differently under the new semantics.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • The proposed language can express all problems complete for NLOGSPACE under first-order reductions.
  • Graph patterns and relational queries become fully composable in both directions.
  • New graph elements, including entire paths, can be constructed and used in further queries.
  • Main features can be incorporated into GQL and SQL/PGQ as concrete additions.
  • The language maintains compatibility with existing semantics for current queries.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This could lead to more uniform query optimization techniques across graph and relational parts.
  • Similar compositional approaches might apply to other emerging graph query standards.
  • Testing the language on real knowledge graphs could reveal practical performance implications of the added expressivity.
  • Connections to existing Datalog-based graph query systems could provide implementation starting points.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 2 minor

Summary. The manuscript identifies a lack of compositionality in the standardized graph query languages GQL and SQL/PGQ. While these languages can express graph reachability and all first-order queries, they fall short of full NLOGSPACE expressivity, which is counterintuitive given that reachability is NLOGSPACE-complete under first-order reductions. The paper proposes a language that restores compositionality between graph patterns and relational queries via two components: a cleaned-up definition of regular path queries with variables and data value comparisons, and a fully compositional graph-to-graph language called #Datalog that supports constructing new graph elements from nodes, edges, lists, and entire paths. It claims this addresses issues recognized by the standards committee and proposes concrete additions to GQL and SQL/PGQ.

Significance. If the proposed constructions achieve the claimed NLOGSPACE expressivity while preserving compatibility with existing GQL and SQL/PGQ semantics, the work would offer a systematic, theoretically grounded solution to a recognized limitation in graph query standards. The motivation correctly invokes standard complexity facts about reachability without circularity, and the emphasis on full compositionality could influence future language extensions.

minor comments (2)
  1. The abstract refers to 'we show that the resulting language addresses the issues' but supplies no high-level sketch of the constructions or compatibility argument; a brief illustrative example of an NLOGSPACE query that is inexpressible in current GQL but expressible in the proposed language would strengthen the introduction.
  2. The invented notation '#Datalog' and the phrase 'cleaned up regular path queries' are introduced without an immediate forward reference to their formal definitions; adding such pointers would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our work and the recommendation of minor revision. The assessment correctly captures the core motivation regarding the expressivity gap in GQL and SQL/PGQ relative to NLOGSPACE and the role of compositionality. We are pleased that the significance for standards development is recognized.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper identifies an expressivity gap in GQL/SQL/PGQ (inability to capture all NLOGSPACE queries despite supporting reachability and FO queries), cites the standard external fact that reachability is NLOGSPACE-complete under first-order reductions, and proposes a new compositional language built from cleaned-up RPQs with variables plus #Datalog. No load-bearing step reduces by construction to its own inputs, no parameters are fitted then renamed as predictions, and no uniqueness or ansatz is smuggled via self-citation chains. The central claim is a language proposal whose correctness is asserted via construction and standard complexity results external to the paper.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 2 invented entities

The proposal rests on standard complexity background and introduces new language constructs without independent evidence for their practical viability.

axioms (2)
  • standard math Reachability is NLOGSPACE-complete under first-order reductions
    Invoked in abstract to highlight the counterintuitive gap.
  • domain assumption GQL and SQL/PGQ express reachability and all first-order queries but fall short of NLOGSPACE
    Central premise stated in abstract.
invented entities (2)
  • #Datalog no independent evidence
    purpose: Fully compositional graph-to-graph language with support for constructing new graph elements from nodes, edges, lists, and paths
    New construct proposed to achieve compositionality; no independent evidence supplied.
  • cleaned up regular path queries with variables and data value comparisons no independent evidence
    purpose: To enable more expressive path queries within the compositional framework
    Improved version of existing concept introduced as key component.

pith-pipeline@v0.9.1-grok · 5773 in / 1446 out tokens · 42407 ms · 2026-06-26T06:30:18.103741+00:00 · methodology

0 comments
read the original abstract

A major shortcoming of the recently standardized graph query languages GQL and SQL/PGQ is their lack of compositionality. Given the importance of these languages in querying knowledge graphs, we address this shortcoming and propose both theoretical solutions and a path to adding them to the new standards. The highlight of the non-compositionality problem is that while both GQL and SQL/PGQ can express graph reachability and all first-order queries, they fall short of the problems in NLOGSPACE. In view of the completeness of reachability for NLOGSPACE under first-order reductions, this is extremely counterintuitive. The issue is well recognized by the standards committee that has been searching for language extensions to fill the gaps at the level of some specific inexpressible queries. We address the issue in a systematic way and propose a language that fills expressivity gaps by allowing full compositionality between graph patterns and relational queries. It does so by using two key components: a cleaned up definition of regular path queries with variables and data value comparisons, and a fully compositional graph-to-graph language #Datalog with complete support for constructing new graph elements from nodes, edges, lists of nodes and edges, and even entire paths. We show that the resulting language addresses the issues facing the standards committee, and propose a concrete addition to GQL and SQL/PGQ that incorporates its main features.

Figures

Figures reproduced from arXiv: 2606.23399 by Leonid Libkin, Marcelo Arenas, Wim Martens.

Figure 1
Figure 1. Figure 1: Definition of reachability among annotated paths for RPQVs. [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

40 extracted references

  1. [1]

    Boncz, George H

    Renzo Angles, Marcelo Arenas, Pablo Barceló, Peter A. Boncz, George H. L. Fletcher, Claudio Gutierrez, Tobias Lindaaker, Marcus Paradies, Stefan Plantikow, Juan F. Sequeda, Oskar van Rest, and Hannes Voigt. G-CORE: A core for future graph query languages. InConference on Management of Data (SIGMOD), pages 1421–1432, 2018

    2018

  2. [2]

    Cambridge University Press, 2014

    Marcelo Arenas, Pablo Barceló, Leonid Libkin, and Filip Murlak.Foundations of Data Ex- change. Cambridge University Press, 2014

    2014

  3. [3]

    Counting beyond a yottabyte, or how SPARQL 1.1 property paths will prevent adoption of the standard

    Marcelo Arenas, Sebastián Conca, and Jorge Pérez. Counting beyond a yottabyte, or how SPARQL 1.1 property paths will prevent adoption of the standard. InWorld Wide Web Con- ference (WWW), pages 629–638. ACM, 2012

    2012

  4. [4]

    A trichotomy for regular simple path queries on graphs.J

    Guillaume Bagan, Angela Bonifati, and Benoît Groz. A trichotomy for regular simple path queries on graphs.J. Comput. Syst. Sci., 108:29–48, 2020

    2020

  5. [5]

    Efficient evaluation and static analysis for well-designed pattern trees with projection.ACM Trans

    Pablo Barceló, Markus Kröll, Reinhard Pichler, and Sebastian Skritek. Efficient evaluation and static analysis for well-designed pattern trees with projection.ACM Trans. Database Syst., 43(2):8:1–8:44, 2018

    2018

  6. [6]

    Transforming property graphs.Proc

    Angela Bonifati, Filip Murlak, and Yann Ramusat. Transforming property graphs.Proc. VLDB Endow., 17(11):2906–2918, 2024

    2024

  7. [7]

    Consens and Alberto O

    Mariano P. Consens and Alberto O. Mendelzon. GraphLog: a visual formalism for real life recursion. InSymposium on Principles of Database Systems (PODS), pages 404–416. ACM Press, 1990

    1990

  8. [8]

    Cruz, Alberto O

    Isabel F. Cruz, Alberto O. Mendelzon, and Peter T. Wood. A graphical query language sup- porting recursion. InConference on Management of Data (SIGMOD), pages 323–330. ACM Press, 1987

    1987

  9. [9]

    Graph 20 pattern matching in GQL and SQL/PGQ

    Alin Deutsch, Nadime Francis, Alastair Green, Keith Hare, Bei Li, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Wim Martens, Jan Michels, Filip Murlak, Stefan Plantikow, Petra Selmer, Oskar van Rest, Hannes Voigt, Domagoj Vrgoč, Mingxi Wu, and Fred Zemke. Graph 20 pattern matching in GQL and SQL/PGQ. InConference on Management of Data (SIGMOD), pages ...

    2022

  10. [10]

    Alin Deutsch, Yu Xu, Mingxi Wu, and Victor E. Lee. Aggregation support for modern graph analytics in TigerGraph. InConference on Management of Data (SIGMOD), 2020

    2020

  11. [11]

    Pathfinder: Returning paths in graph queries

    Benjamín Farias, Wim Martens, Carlos Rojas, and Domagoj Vrgoc. Pathfinder: Returning paths in graph queries. InInternational Semantic Web Conference (ISWC), pages 135–154. Springer, 2024

    2024

  12. [12]

    GPC: A pattern calculus for property graphs

    Nadime Francis, Amélie Gheerbrant, Paolo Guagliardo, Leonid Libkin, Victor Marsault, Wim Martens, Filip Murlak, Liat Peterfreund, Alexandra Rogova, and Domagoj Vrgoc. GPC: A pattern calculus for property graphs. In Floris Geerts, Hung Q. Ngo, and Stavros Sintos, editors,Symposium on Principles of Database Systems (PODS), pages 241–250. ACM, 2023

    2023

  13. [13]

    A re- searcher’s digest of GQL

    Nadime Francis, Amélie Gheerbrant, Paolo Guagliardo, Leonid Libkin, Victor Marsault, Wim Martens, Filip Murlak, Liat Peterfreund, Alexandra Rogova, and Domagoj Vrgoc. A re- searcher’s digest of GQL. InInternational Conference on Database Theory (ICDT), volume 255 ofLIPIcs, pages 1:1–1:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023

    2023

  14. [14]

    Cypher: An evolving query language for property graphs

    Nadime Francis, Alastair Green, Paolo Guagliardo, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Stefan Plantikow, Mats Rydberg, Petra Selmer, and Andrés Taylor. Cypher: An evolving query language for property graphs. InConference on Management of Data (SIG- MOD), pages 1433–1445, 2018

    2018

  15. [15]

    GQL and SQL/PGQ: theoretical models and expressive power.Proc

    Amélie Gheerbrant, Leonid Libkin, Liat Peterfreund, and Alexandra Rogova. GQL and SQL/PGQ: theoretical models and expressive power.Proc. VLDB Endow., 18(6):1798–1810, 2025

    2025

  16. [16]

    Dangers of list processing in query- ing property graphs.Proc

    Amélie Gheerbrant, Leonid Libkin, and Alexandra Rogova. Dangers of list processing in query- ing property graphs.Proc. ACM Manag. Data, 3(3):144:1–144:25, 2025

    2025

  17. [17]

    Updating graph databases with cypher.Proc

    Alastair Green, Paolo Guagliardo, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Stefan Plantikow, Martin Schuster, Petra Selmer, and Hannes Voigt. Updating graph databases with cypher.Proc. VLDB Endow., 12(12):2242–2253, 2019

    2019

  18. [18]

    A graph-oriented object database model.IEEE Trans

    Marc Gyssens, Jan Paredaens, Jan Van den Bussche, and Dirk Van Gucht. A graph-oriented object database model.IEEE Trans. Knowl. Data Eng., 6(4):572–586, 1994

    1994

  19. [19]

    Soonbo Han and Zachary G. Ives. Implementation strategies for views over property graphs. Proc. ACM Manag. Data, 2(3):146, 2024

    2024

  20. [20]

    Harris and A

    S. Harris and A. Seaborne. SPARQL 1.1 query language. Technical report, World Wide Web Consortium (W3C), 2010

    2010

  21. [21]

    LDQL: A query language for the web of linked data.J

    Olaf Hartig and Jorge Pérez. LDQL: A query language for the web of linked data.J. Web Semant., 41:9–29, 2016

    2016

  22. [22]

    Graduate texts in computer science

    Neil Immerman.Descriptive complexity. Graduate texts in computer science. Springer, 1999

    1999

  23. [23]

    Kostylev, and Bernardo Cuenca Grau

    Mark Kaminski, Egor V. Kostylev, and Bernardo Cuenca Grau. Query nesting, assignment, and aggregation in SPARQL 1.1.ACM Trans. Database Syst., 42(3):17:1–17:46, 2017. 21

    2017

  24. [24]

    Querying graph data: Where we are and where to go

    Leonid Libkin, Wim Martens, Filip Murlak, Liat Peterfreund, and Domagoj Vrgoc. Querying graph data: Where we are and where to go. InSymposium on Principles of Database Systems (PODS), pages 9–26. ACM, 2025

    2025

  25. [25]

    Predicates on sequences of edges

    Tobias Lindaaker. Predicates on sequences of edges. Technical report, ISO/IEC JTC1/ SC32 WG3:W26-027, 2023

    2023

  26. [26]

    The complexity of regular expressions and property paths in SPARQL.ACM Trans

    Katja Losemann and Wim Martens. The complexity of regular expressions and property paths in SPARQL.ACM Trans. Database Syst., 38(4):24, 2013

    2013

  27. [27]

    A trichotomy for regular trail queries.Log

    Wim Martens, Matthias Niewerth, and Tina Popp. A trichotomy for regular trail queries.Log. Methods Comput. Sci., 19(4), 2023

    2023

  28. [28]

    Representing paths in graph database pattern matching.Proc

    Wim Martens, Matthias Niewerth, Tina Popp, Carlos Rojas, Stijn Vansummeren, and Do- magoj Vrgoc. Representing paths in graph database pattern matching.Proc. VLDB Endow., 16(7):1790–1803, 2023

    2023

  29. [29]

    The complexity of regular trail and simple path queries on undirected graphs

    Wim Martens and Tina Popp. The complexity of regular trail and simple path queries on undirected graphs. InSymposium on Principles of Database Systems (PODS), pages 165–174. ACM, 2022

    2022

  30. [30]

    Mendelzon and Peter T

    Alberto O. Mendelzon and Peter T. Wood. Finding regular simple paths in graph databases. SIAM J. Comput., 24(6):1235–1258, 1995

    1995

  31. [31]

    Factorized databases.SIGMOD Rec., 45(2):5–16, 2016

    Dan Olteanu and Maximilian Schleich. Factorized databases.SIGMOD Rec., 45(2):5–16, 2016

    2016

  32. [32]

    Semantics and complexity of SPARQL

    Jorge Pérez, Marcelo Arenas, and Claudio Gutierrez. Semantics and complexity of SPARQL. InInternational Semantic Web Conference (ISWC), pages 30–43. Springer, 2006

    2006

  33. [33]

    Semantics and complexity of SPARQL

    Jorge Pérez, Marcelo Arenas, and Claudio Gutiérrez. Semantics and complexity of SPARQL. ACM TODS, 34(3):16:1–16:45, 2009

    2009

  34. [34]

    nSPARQL: A navigational language for RDF.J

    Jorge Pérez, Marcelo Arenas, and Claudio Gutierrez. nSPARQL: A navigational language for RDF.J. Web Semant., 8(4):255–270, 2010

    2010

  35. [35]

    From SPARQL to rules (and back)

    Axel Polleres. From SPARQL to rules (and back). InInternational Conference on World Wide Web (WWW), pages 787–796. ACM, 2007

    2007

  36. [36]

    On the expressiveness of languages for querying prop- erty graphs in relational databases.Proc

    Hadar Rotschield and Liat Peterfreund. On the expressiveness of languages for querying prop- erty graphs in relational databases.Proc. ACM Manag. Data, 3(5):279:1–279:18, 2025

    2025

  37. [37]

    TRIPLE — A query, inference, and transformation language for the semantic web

    Michael Sintek and Stefan Decker. TRIPLE — A query, inference, and transformation language for the semantic web. InInternational Semantic Web Conference (ISWC), pages 364–378. Springer, 2002

    2002

  38. [38]

    GQL rules: Deterministic and safe rule-based materialization for property graphs.IEEE Access, 14:62746–62762, 2026

    Dominik Tomaszuk. GQL rules: Deterministic and safe rule-based materialization for property graphs.IEEE Access, 14:62746–62762, 2026

    2026

  39. [39]

    PGQL: a property graph query language

    Oskar van Rest, Sungpack Hong, Jinha Kim, Xuming Meng, and Hassan Chafi. PGQL: a property graph query language. InGRADES, page 7. ACM, 2016

    2016

  40. [40]

    FOR EACH SEGMENT discussion

    Fred Zemke. FOR EACH SEGMENT discussion. Technical report, ISO/IEC JTC1/ SC32 WG3:BGI-022, 2024. 22

    2024