Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints
Summary: Reduces containment of regular path queries under general path constraints to the semi-Thue word-rewrite problem, deriving strong undecidability and identifying a large practical decidable fragment. Gives a constructive characterization for computing optimal constrained view-based rewritings of RPQs. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Gösta Grahne
- 2. Alex Thomo
Incoming Citations (Sorted by Pagerank)
Showing 5 of 5 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,037 | Querying Graph Databases | 2013 | PODS | 0.00014502493 |
| 4,568 | Rewriting XPath Queries Using Materialized Views | 2005 | VLDB | 6.0784118e-05 |
| 5,717 | Query Processing under GLAV Mappings for Relational and Graph Databases | 2013 | VLDB | 5.3553228e-05 |
| 9,534 | Answering Tree Pattern Queries Using Views | 2006 | VLDB | 4.3268303e-05 |
| 12,604 | Answering XPath Queries over Networks by Sending Minimal Views | 2004 | VLDB | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 7 of 7 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 82 | Answering Queries Using Views (Extended Abstract) | 1995 | PODS | 0.00054402763 |
| 274 | Regular Path Queries with Constraints | 1997 | PODS | 0.00029390022 |
| 810 | Query Containment for Conjunctive Queries With Regular Expressions | 1998 | PODS | 0.00016428374 |
| 2,342 | Rewriting of Regular Expressions and Regular Path Queries | 1999 | PODS | 9.0015589e-05 |
| 2,399 | Query Rewriting for Semistructured Data | 1999 | SIGMOD | 8.8973689e-05 |
| 3,228 | View-Based Query Processing for Regular Path Queries with Inverse | 2000 | PODS | 7.3405281e-05 |
| 3,257 | Path Constraints on Semistructured and Structured Data | 1998 | PODS | 7.3151681e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,037 | Querying Graph Databases | 2013 | PODS | 0.00014502493 |
| 3,681 | Queries with Incomplete Answers over Semistructured Data | 1999 | PODS | 6.8492288e-05 |
| 1,444 | Finding Regular Simple Paths in Graph Databases | 1989 | VLDB | 0.00011946075 |
| 3,228 | View-Based Query Processing for Regular Path Queries with Inverse | 2000 | PODS | 7.3405281e-05 |
| 3,531 | Lossless Regular Views | 2002 | PODS | 7.003412e-05 |
| 11,826 | Bounded Query Rewriting Using Views | 2016 | PODS | 4.1945683e-05 |
| 1,490 | On the Decidability of Query Containment under Constraints | 1998 | PODS | 0.00011699154 |
| 810 | Query Containment for Conjunctive Queries With Regular Expressions | 1998 | PODS | 0.00016428374 |
| 4,553 | View-Based Query Containment | 2003 | PODS | 6.091702e-05 |
| 2,342 | Rewriting of Regular Expressions and Regular Path Queries | 1999 | PODS | 9.0015589e-05 |