DBScholar

Back to papers

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)

Paper ID
1283
Venue
PODS
Year
2003
Pagerank
6.3470184e-05
Overall Rank
5,146 | 64.70%
DOI
10.1145/773153.773165

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{grahne_pods03,
        address = {New York, NY, USA},
        series = {{PODS} '03},
        title = {{Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints}},
        url = {https://dl.acm.org/doi/10.1145/773153.773165},
        doi = {10.1145/773153.773165},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Grahne, Gösta and Thomo, Alex},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank Citing Paper Year Venue Pagerank
747 Querying Graph Databases 2013 PODS 0.00014400452
3,976 Rewriting XPath Queries Using Materialized Views 2005 VLDB 6.9785468e-05
6,747 Query Processing under GLAV Mappings for Relational and Graph Databases 2013 VLDB 5.784841e-05
9,687 Answering Tree Pattern Queries Using Views 2006 VLDB 5.2351299e-05
12,797 Answering XPath Queries over Networks by Sending Minimal Views 2004 VLDB 5.093636e-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
69 Answering Queries Using Views (Extended Abstract) 1995 PODS 0.00038090878
348 Regular Path Queries with Constraints 1997 PODS 0.00020518814
686 Query Containment for Conjunctive Queries With Regular Expressions 1998 PODS 0.00014948634
2,066 Rewriting of Regular Expressions and Regular Path Queries 1999 PODS 9.2348082e-05
2,114 Query Rewriting for Semistructured Data 1999 SIGMOD 9.1481121e-05
3,103 View-Based Query Processing for Regular Path Queries with Inverse 2000 PODS 7.7562264e-05
3,308 Path Constraints on Semistructured and Structured Data 1998 PODS 7.5381026e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 348 Regular Path Queries with Constraints 1997 PODS
2 4,495 Queries with Incomplete Answers over Semistructured Data 1999 PODS
3 1,658 Finding Regular Simple Paths in Graph Databases 1989 VLDB
4 3,103 View-Based Query Processing for Regular Path Queries with Inverse 2000 PODS
5 3,717 Lossless Regular Views 2002 PODS
6 1,630 On the Decidability of Query Containment under Constraints 1998 PODS
7 12,029 Bounded Query Rewriting Using Views 2016 PODS
8 686 Query Containment for Conjunctive Queries With Regular Expressions 1998 PODS
9 4,445 View-Based Query Containment 2003 PODS
10 2,066 Rewriting of Regular Expressions and Regular Path Queries 1999 PODS