Expressive Languages for Path Queries over Graph-Structured Data

Summary: Introduces ECRPQs: extend CRPQs with path variables in heads and regular relations over tuples of paths, enabling path outputs and expressive relations among paths for tasks like semantic associations and pattern/sequence alignment. Presents automata-based representations, analyzes data/combined complexity and containment, and identifies syntactic restrictions plus FO and arithmetic extensions (length/count constraints) to trade expressiveness for lower complexity. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1502
Venue: PODS
Year: 2010
Pagerank: 0.00010467069
Overall Rank: 1,812 | 87.40%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 24 of 24 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
964	G-CORE: A Core for Future Graph Query Languages	2018	SIGMOD	0.0001497475
1,037	Querying Graph Databases	2013	PODS	0.00014502493
2,304	Querying Semantic Web Data with SPARQL	2011	PODS	9.0648775e-05
2,505	Graph Pattern Matching in GQL and SQL/PGQ	2022	SIGMOD	8.634551e-05
4,280	Query Planning for Evaluating SPARQL Property Paths	2016	SIGMOD	6.2948356e-05
4,946	Querying Graph Patterns	2011	PODS	5.8149362e-05
5,259	On the Optimization of Recursive Relational Queries: Application to Graph Queries	2020	SIGMOD	5.5984356e-05
5,517	Representing Paths in Graph Database Pattern Matching	2023	VLDB	5.4626107e-05
5,651	GPC: A Pattern Calculus for Property Graphs	2023	PODS	5.3905536e-05
6,820	Conjunctive Regular Path Queries with String Variables	2020	PODS	4.9157306e-05
6,847	TriAL for RDF: Adapting Graph Query Languages for RDF Data	2013	PODS	4.9089877e-05
6,948	Semantic Acyclicity on Graph Databases	2013	PODS	4.8898337e-05
7,589	Using Domain-Specific Languages For Analytic Graph Databases	2016	VLDB	4.7030207e-05
7,713	GQL and SQL/PGQ: Theoretical Models and Expressive Power	2025	VLDB	4.6712228e-05
7,897	Correlation Constraint Shortest Path over Large Multi-Relation Graphs	2019	VLDB	4.6230399e-05
8,804	Conjunctive Regular Path Queries under Injective Semantics	2023	PODS	4.4468701e-05
8,827	The Complexity of Regular Trail and Simple Path Queries on Undirected Graphs	2022	PODS	4.4411907e-05
9,493	When is the Evaluation of Extended CRPQ Tractable?	2022	PODS	4.3341665e-05
9,744	Output-Sensitive Evaluation of Regular Path Queries	2025	PODS	4.2897489e-05
10,006	On the Expressiveness of Languages for Querying Property Graphs in Relational Databases	2026	PODS	4.1945683e-05
10,235	Repairing Property Graphs under PG-Constraints	2026	VLDB	4.1945683e-05
10,477	Dangers of List Processing in Querying Property Graphs	2025	SIGMOD	4.1945683e-05
11,064	Efficient Betweenness Centrality Computation over Large Heterogeneous Information Networks	2024	VLDB	4.1945683e-05
11,326	Data Path Queries over Embedded Graph Databases	2022	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
256	GraphLog: a Visual Formalism for Real Life Recursion	1990	PODS	0.00030259041
810	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00016428374
1,870	Flexible Queries over Semistructured Data	2001	PODS	0.00010263799

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
363	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00025715157
6,820	Conjunctive Regular Path Queries with String Variables	2020	PODS	4.9157306e-05
5,424	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS	5.5126983e-05
11,014	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	4.1945683e-05
3,652	The Complexity of Evaluating Path Expressions in SPARQL	2012	PODS	6.875313e-05
8,804	Conjunctive Regular Path Queries under Injective Semantics	2023	PODS	4.4468701e-05
4,946	Querying Graph Patterns	2011	PODS	5.8149362e-05
1,444	Finding Regular Simple Paths in Graph Databases	1989	VLDB	0.00011946075
11,326	Data Path Queries over Embedded Graph Databases	2022	PODS	4.1945683e-05
1,037	Querying Graph Databases	2013	PODS	0.00014502493