GQL and SQL/PGQ: Theoretical Models and Expressive Power

Summary: Introduce Core PGQ and Core GQL formal models capturing SQL/PGQ vs GQL and contrasting PGQ's bottom-up with GQL's pipelined evaluation. Theoretically pinpoint expressiveness gaps that necessitate language extensions and empirically show standard workarounds are impractical. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 14026
Venue: VLDB
Year: 2025
Pagerank: 5.5853593e-05
Overall Rank: 7,603 | 47.84%
DOI: 10.14778/3725688.3725707

Incoming Non-self Citations Over Time

Authors

1. Amélie Gheerbrant (Centre National de la Recherche Scientifique; Institut de Recherche en Informatique Fondamentale; Université Paris Cité)
2. Leonid Libkin (RelationalAI; University of Edinburgh)
3. Liat Peterfreund (Hebrew University)
4. Alexandra Rogova (Centre National de la Recherche Scientifique; Institut de Recherche en Informatique Fondamentale; Université Paris Cité)

BibTeX Citation

@article{gheerbrant_vldb25,
        title = {{GQL and SQL/PGQ: Theoretical Models and Expressive Power}},
        author = {Gheerbrant, Amélie and Libkin, Leonid and Peterfreund, Liat and Rogova, Alexandra},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {6},
        pages = {1798--1810},
        doi = {10.14778/3725688.3725707},
        url = {https://doi.org/10.14778/3725688.3725707},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,143	Raqlet: Cross-Paradigm Compilation for Recursive Queries	2026	CIDR	5.093636e-05
10,178	On the Expressiveness of Languages for Querying Property Graphs in Relational Databases	2026	PODS	5.093636e-05
10,756	Dangers of List Processing in Querying Property Graphs	2025	SIGMOD	5.093636e-05
11,064	Property Graph Standards: State of the Art & Open Challenges	2025	VLDB	5.093636e-05
11,069	Versatile Property Graph Transformations	2025	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
300	GraphLog: a Visual Formalism for Real Life Recursion	1990	PODS	0.00022046803
312	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00021733819
547	Cypher: An Evolving Query Language for Property Graphs	2018	SIGMOD	0.00016731552
747	Querying Graph Databases	2013	PODS	0.00014400452
1,575	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS	0.00010318258
1,591	SQLGraph: An Efficient Relational-Based Property Graph Store	2015	SIGMOD	0.00010255536
1,836	Graph Pattern Matching in GQL and SQL/PGQ	2022	SIGMOD	9.6489549e-05
3,697	Aggregation Support for Modern Graph Analytics in TigerGraph	2020	SIGMOD	7.1903457e-05
4,367	SQL Has Problems. We Can Fix Them: Pipe Syntax In SQL	2024	VLDB	6.7395125e-05
5,264	Implementation Strategies for Views over Property Graphs	2024	SIGMOD	6.2947526e-05
5,425	GPC: A Pattern Calculus for Property Graphs	2023	PODS	6.223218e-05
6,439	DuckPGQ: Bringing SQL/PGQ to DuckDB	2023	VLDB	5.8787285e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,181	Expressive Languages for Querying the Semantic Web	2014	PODS
2	9,430	A Theory of Regular Queries	2016	PODS
3	10,117	Semantic Data Modeling, Graph Query, and SQL, Together at Last?	2026	CIDR
4	12,289	Efficient Implementation of Generalized Quantification in Relational Query Languages	2013	VLDB
5	1,661	PG-Schema: Schemas for Property Graphs	2023	SIGMOD
6	747	Querying Graph Databases	2013	PODS
7	1,836	Graph Pattern Matching in GQL and SQL/PGQ	2022	SIGMOD
8	9,682	Graph Data Models, Query Languages and Programming Paradigms	2018	VLDB
9	5,425	GPC: A Pattern Calculus for Property Graphs	2023	PODS
10	10,178	On the Expressiveness of Languages for Querying Property Graphs in Relational Databases	2026	PODS