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: h315b69d293aacab9
Venue: PODS
Year: 2003
Pagerank: 6.2207517e-05
Overall Rank: 5,226 | 64.87%
DOI: 10.1145/773153.773165

Incoming Non-self Citations Over Time

Authors

1. Gösta Grahne (Concordia University)
2. Alex Thomo (Concordia University)

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
719	Querying Graph Databases	2013	PODS	0.00014529156
4,066	Rewriting XPath Queries Using Materialized Views	2005	VLDB	6.8221983e-05
6,887	Query Processing under GLAV Mappings for Relational and Graph Databases	2013	VLDB	5.6550447e-05
9,862	Answering Tree Pattern Queries Using Views	2006	VLDB	5.1176676e-05
13,087	Answering XPath Queries over Networks by Sending Minimal Views	2004	VLDB	4.9793485e-05

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
72	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00037549176
356	Regular Path Queries with Constraints	1997	PODS	0.00020103855
699	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014686953
2,041	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.1421879e-05
2,127	Query Rewriting for Semistructured Data	1999	SIGMOD	9.0005009e-05
3,155	View-Based Query Processing for Regular Path Queries with Inverse	2000	PODS	7.5858519e-05
3,365	Path Constraints on Semistructured and Structured Data	1998	PODS	7.3728818e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	719	Querying Graph Databases	2013	PODS
2	4,592	Queries with Incomplete Answers over Semistructured Data	1999	PODS
3	1,597	Finding Regular Simple Paths in Graph Databases	1989	VLDB
4	3,155	View-Based Query Processing for Regular Path Queries with Inverse	2000	PODS
5	3,799	Lossless Regular Views	2002	PODS
6	1,660	On the Decidability of Query Containment under Constraints	1998	PODS
7	12,324	Bounded Query Rewriting Using Views	2016	PODS
8	699	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS
9	4,514	View-Based Query Containment	2003	PODS
10	2,041	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS