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.1979445e-05
Overall Rank: 5,249 | 64.82%
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.00014493767
4,090	Rewriting XPath Queries Using Materialized Views	2005	VLDB	6.7964465e-05
6,910	Query Processing under GLAV Mappings for Relational and Graph Databases	2013	VLDB	5.6336774e-05
9,904	Answering Tree Pattern Queries Using Views	2006	VLDB	5.0983308e-05
13,134	Answering XPath Queries over Networks by Sending Minimal Views	2004	VLDB	4.9605343e-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.00037421163
358	Regular Path Queries with Constraints	1997	PODS	0.00020030407
703	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014638214
2,043	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.1266211e-05
2,140	Query Rewriting for Semistructured Data	1999	SIGMOD	8.9688891e-05
3,169	View-Based Query Processing for Regular Path Queries with Inverse	2000	PODS	7.557345e-05
3,377	Path Constraints on Semistructured and Structured Data	1998	PODS	7.3455463e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	358	Regular Path Queries with Constraints	1997	PODS
2	4,609	Queries with Incomplete Answers over Semistructured Data	1999	PODS
3	1,592	Finding Regular Simple Paths in Graph Databases	1989	VLDB
4	3,169	View-Based Query Processing for Regular Path Queries with Inverse	2000	PODS
5	3,811	Lossless Regular Views	2002	PODS
6	1,667	On the Decidability of Query Containment under Constraints	1998	PODS
7	12,373	Bounded Query Rewriting Using Views	2016	PODS
8	703	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS
9	4,533	View-Based Query Containment	2003	PODS
10	2,043	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS