Querying graph data: Where we are and where to go

Leonid Libkin; Wim Martens; Filip Murlak; Liat Peterfreund; Domagoj Vrgoč

doi:10.1145/3722234.3725822

Querying graph data: Where we are and where to go

Leonid Libkin, Wim Martens, Filip Murlak, Liat Peterfreund, Domagoj Vrgoč

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Although graph query languages such as Cypher, SQL/PGQ, and GQL take inspiration from theoretical languages such as conjunctive regular path queries (CRPQs), their pattern matching facilities are significantly more powerful in order to cope with real world use cases. Four such extensions are treatment of both nodes and edges, variables that bind to paths or lists, path modes, and data filters.

In this paper, we define CRPQs with data tests and list variables (dl-CRPQs), which extend CRPQs with these features and give the reader a quick idea of how these features relate to the classical literature on graph pattern matching. Then, we discuss where the design of SQL/PGQ and GQL stands today and identify a host of opportunities in research and query language design. In particular, we believe that a closer connection between graph query languages and automata theory will open up opportunities for query optimization that will benefit graph query languages in the long term

Original language	English
Title of host publication	Companion of the 44th Symposium on Principles of Database Systems
Place of Publication	New York, NY, USA
Publisher	Association for Computing Machinery (ACM)
Pages	1-19
Number of pages	19
DOIs	https://doi.org/10.1145/3722234.3725822
Publication status	Accepted/In press - 22 Apr 2025
Event	The 2025 ACM SIGMOD/PODS International Conference on Management of Data - Intercontinental Berlin, Berlin, Germany Duration: 22 Jun 2025 → 27 Jun 2025 https://2025.sigmod.org/

Publication series

Name	Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
Publisher	Association for Computing Machinery (ACM)
ISSN (Print)	1055-6338

Conference

Conference	The 2025 ACM SIGMOD/PODS International Conference on Management of Data
Abbreviated title	SIGMOD/PODS 2025
Country/Territory	Germany
City	Berlin
Period	22/06/25 → 27/06/25
Internet address	https://2025.sigmod.org/

Keywords / Materials (for Non-textual outputs)

graph databases
query languages
query language design
regular path queries
paths
automata

Access to Document

10.1145/3722234.3725822

LibkinEtalPODSCompanion2025QueryingGraphDataAccepted author manuscript, 743 KBLicence: Creative Commons: Attribution (CC-BY)

Cite this

Libkin, L., Martens, W., Murlak, F., Peterfreund, L., & Vrgoč, D. (Accepted/In press). Querying graph data: Where we are and where to go. In Companion of the 44th Symposium on Principles of Database Systems (pp. 1-19). (Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems). Association for Computing Machinery (ACM). https://doi.org/10.1145/3722234.3725822

@inproceedings{f939aba36af7400ca4f6bc18729861a2,

title = "Querying graph data: Where we are and where to go",

abstract = "Although graph query languages such as Cypher, SQL/PGQ, and GQL take inspiration from theoretical languages such as conjunctive regular path queries (CRPQs), their pattern matching facilities are significantly more powerful in order to cope with real world use cases. Four such extensions are treatment of both nodes and edges, variables that bind to paths or lists, path modes, and data filters. In this paper, we define CRPQs with data tests and list variables (dl-CRPQs), which extend CRPQs with these features and give the reader a quick idea of how these features relate to the classical literature on graph pattern matching. Then, we discuss where the design of SQL/PGQ and GQL stands today and identify a host of opportunities in research and query language design. In particular, we believe that a closer connection between graph query languages and automata theory will open up opportunities for query optimization that will benefit graph query languages in the long term",

keywords = "graph databases, query languages, query language design, regular path queries, paths, automata",

author = "Leonid Libkin and Wim Martens and Filip Murlak and Liat Peterfreund and Domagoj Vrgo{\v c}",

year = "2025",

month = apr,

day = "22",

doi = "10.1145/3722234.3725822",

language = "English",

series = "Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems",

publisher = "Association for Computing Machinery (ACM)",

pages = "1--19",

booktitle = "Companion of the 44th Symposium on Principles of Database Systems",

address = "United States",

note = "The 2025 ACM SIGMOD/PODS International Conference on Management of Data, SIGMOD/PODS 2025 ; Conference date: 22-06-2025 Through 27-06-2025",

url = "https://2025.sigmod.org/",

}

Libkin, L, Martens, W, Murlak, F, Peterfreund, L & Vrgoč, D 2025, Querying graph data: Where we are and where to go. in Companion of the 44th Symposium on Principles of Database Systems. Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Association for Computing Machinery (ACM), New York, NY, USA, pp. 1-19, The 2025 ACM SIGMOD/PODS International Conference on Management of Data, Berlin, Berlin, Germany, 22/06/25. https://doi.org/10.1145/3722234.3725822

Querying graph data: Where we are and where to go. / Libkin, Leonid; Martens, Wim; Murlak, Filip et al.
Companion of the 44th Symposium on Principles of Database Systems. New York, NY, USA: Association for Computing Machinery (ACM), 2025. p. 1-19 (Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Querying graph data

T2 - The 2025 ACM SIGMOD/PODS International Conference on Management of Data

AU - Libkin, Leonid

AU - Martens, Wim

AU - Murlak, Filip

AU - Peterfreund, Liat

AU - Vrgoč, Domagoj

PY - 2025/4/22

Y1 - 2025/4/22

N2 - Although graph query languages such as Cypher, SQL/PGQ, and GQL take inspiration from theoretical languages such as conjunctive regular path queries (CRPQs), their pattern matching facilities are significantly more powerful in order to cope with real world use cases. Four such extensions are treatment of both nodes and edges, variables that bind to paths or lists, path modes, and data filters. In this paper, we define CRPQs with data tests and list variables (dl-CRPQs), which extend CRPQs with these features and give the reader a quick idea of how these features relate to the classical literature on graph pattern matching. Then, we discuss where the design of SQL/PGQ and GQL stands today and identify a host of opportunities in research and query language design. In particular, we believe that a closer connection between graph query languages and automata theory will open up opportunities for query optimization that will benefit graph query languages in the long term

AB - Although graph query languages such as Cypher, SQL/PGQ, and GQL take inspiration from theoretical languages such as conjunctive regular path queries (CRPQs), their pattern matching facilities are significantly more powerful in order to cope with real world use cases. Four such extensions are treatment of both nodes and edges, variables that bind to paths or lists, path modes, and data filters. In this paper, we define CRPQs with data tests and list variables (dl-CRPQs), which extend CRPQs with these features and give the reader a quick idea of how these features relate to the classical literature on graph pattern matching. Then, we discuss where the design of SQL/PGQ and GQL stands today and identify a host of opportunities in research and query language design. In particular, we believe that a closer connection between graph query languages and automata theory will open up opportunities for query optimization that will benefit graph query languages in the long term

KW - graph databases

KW - query languages

KW - query language design

KW - regular path queries

KW - paths

KW - automata

U2 - 10.1145/3722234.3725822

DO - 10.1145/3722234.3725822

M3 - Conference contribution

T3 - Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

SP - 1

EP - 19

BT - Companion of the 44th Symposium on Principles of Database Systems

PB - Association for Computing Machinery (ACM)

CY - New York, NY, USA

Y2 - 22 June 2025 through 27 June 2025

ER -

Libkin L, Martens W, Murlak F, Peterfreund L, Vrgoč D. Querying graph data: Where we are and where to go. In Companion of the 44th Symposium on Principles of Database Systems. New York, NY, USA: Association for Computing Machinery (ACM). 2025. p. 1-19. (Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems). doi: 10.1145/3722234.3725822

Querying graph data: Where we are and where to go

Abstract

Publication series

Conference

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Cite this