2026-07-22T01:43:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25627 2026-06-23T12:04:03Z ddc:004 open_access

Complexity of Evaluating GQL Queries Figueira, Diego Lin, Anthony W. Peterfreund, Liat Graph query languages GQL complexity database theory GQL has recently emerged as the standard query language over graph databases, particularly, property graphs. Indeed, this is analogous to the role of SQL for relational databases. Unlike SQL, however, fundamental problems regarding GQL are still unsolved, most notably the complexity of query evaluation. In this paper we provide a complete solution to this problem for the core fragment of GQL and for its extension with path restrictors. In particular, we show that the data complexity of these fragments is P^NP[log]-complete in general, and drops to NL-complete when restrictors are disallowed. Using techniques from embedded finite model theory, we show that this is true, even when the queries use data from infinite concrete domains such as real numbers with arithmetic. In proving these results, we establish and exploit tight connections between GQL and query languages over relational databases, especially extensions of relational calculus with transitive closure operators and fragments of second-order logic. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Diego Figueira and Anthony W. Lin and Liat Peterfreund 2026 Is Part Of LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2026.13 urn:nbn:de:0030-drops-256278 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.13 eng https://creativecommons.org/licenses/by/4.0/legalcode