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.00010458164
Overall Rank: 1,812 | 87.41%
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.00014967208
1,040	Querying Graph Databases	2013	PODS	0.00014483577
2,302	Querying Semantic Web Data with SPARQL	2011	PODS	9.0662698e-05
2,504	Graph Pattern Matching in GQL and SQL/PGQ	2022	SIGMOD	8.629969e-05
4,276	Query Planning for Evaluating SPARQL Property Paths	2016	SIGMOD	6.2884651e-05
4,949	Querying Graph Patterns	2011	PODS	5.8090034e-05
5,267	On the Optimization of Recursive Relational Queries: Application to Graph Queries	2020	SIGMOD	5.5930569e-05
5,527	Representing Paths in Graph Database Pattern Matching	2023	VLDB	5.4573655e-05
5,663	GPC: A Pattern Calculus for Property Graphs	2023	PODS	5.3853781e-05
6,818	Conjunctive Regular Path Queries with String Variables	2020	PODS	4.911014e-05
6,846	TriAL for RDF: Adapting Graph Query Languages for RDF Data	2013	PODS	4.9042778e-05
6,945	Semantic Acyclicity on Graph Databases	2013	PODS	4.8874695e-05
7,592	Using Domain-Specific Languages For Analytic Graph Databases	2016	VLDB	4.6985656e-05
7,712	GQL and SQL/PGQ: Theoretical Models and Expressive Power	2025	VLDB	4.6667433e-05
7,897	Correlation Constraint Shortest Path over Large Multi-Relation Graphs	2019	VLDB	4.6186066e-05
8,803	Conjunctive Regular Path Queries under Injective Semantics	2023	PODS	4.4426077e-05
8,827	The Complexity of Regular Trail and Simple Path Queries on Undirected Graphs	2022	PODS	4.4369334e-05
9,494	When is the Evaluation of Extended CRPQ Tractable?	2022	PODS	4.3300131e-05
9,743	Output-Sensitive Evaluation of Regular Path Queries	2025	PODS	4.2856385e-05
10,005	On the Expressiveness of Languages for Querying Property Graphs in Relational Databases	2026	PODS	4.1905499e-05
10,235	Repairing Property Graphs under PG-Constraints	2026	VLDB	4.1905499e-05
10,487	Dangers of List Processing in Querying Property Graphs	2025	SIGMOD	4.1905499e-05
11,067	Efficient Betweenness Centrality Computation over Large Heterogeneous Information Networks	2024	VLDB	4.1905499e-05
11,328	Data Path Queries over Embedded Graph Databases	2022	PODS	4.1905499e-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.00030241337
808	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.000164132
1,873	Flexible Queries over Semistructured Data	2001	PODS	0.00010255165

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
364	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00025657601
6,818	Conjunctive Regular Path Queries with String Variables	2020	PODS	4.911014e-05
5,435	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS	5.5074113e-05
11,017	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	4.1905499e-05
3,659	The Complexity of Evaluating Path Expressions in SPARQL	2012	PODS	6.8684407e-05
8,803	Conjunctive Regular Path Queries under Injective Semantics	2023	PODS	4.4426077e-05
4,949	Querying Graph Patterns	2011	PODS	5.8090034e-05
1,445	Finding Regular Simple Paths in Graph Databases	1989	VLDB	0.00011937596
11,328	Data Path Queries over Embedded Graph Databases	2022	PODS	4.1905499e-05
1,040	Querying Graph Databases	2013	PODS	0.00014483577