Database Paper Browser

Back to papers

Rewriting of Regular Expressions and Regular Path Queries

Summary: Algorithm to express a regular expression E via given regex views, returning an exact equivalent when possible or otherwise the maximal view-expressible sublanguage of E. Proves essentially optimal complexity bounds and applies them to view-based rewriting of regular path queries in semi-structured data. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1174
Venue
PODS
Year
1999
Pagerank
8.9933611e-05
Overall Rank
2,345 | 83.71%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank Citing Paper Year Venue Pagerank
47 Data Integration: A Theoretical Perspective 2002 PODS 0.00069691761
1,155 A Scalable Algorithm for Answering Queries Using Views 2000 VLDB 0.00013606507
2,039 Views and Queries: Determinacy and Rewriting 2005 PODS 9.7059912e-05
2,397 Query Rewriting for Semistructured Data 1999 SIGMOD 8.8888995e-05
2,504 Graph Pattern Matching in GQL and SQL/PGQ 2022 SIGMOD 8.629969e-05
4,014 A Web Odyssey: from Codd to XML 2001 PODS 6.5300582e-05
4,191 Efficiently Answering Regular Simple Path Queries on Large Labeled Networks 2019 SIGMOD 6.3676619e-05
4,276 Query Planning for Evaluating SPARQL Property Paths 2016 SIGMOD 6.2884651e-05
4,978 Constraint Satisfaction and Database Theory: a Tutorial 2000 PODS 5.7833452e-05
4,987 ZipG: A Memory-efficient Graph Store for Interactive Queries 2017 SIGMOD 5.7769841e-05
5,415 Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints 2003 PODS 5.5188622e-05
5,527 Representing Paths in Graph Database Pattern Matching 2023 VLDB 5.4573655e-05
9,676 Schema-Based Query Optimisation for Graph Databases 2025 SIGMOD 4.3006524e-05
9,825 Exploiting Structure in Regular Expression Queries 2023 SIGMOD 4.2710095e-05
11,017 Efficient Regular Simple Path Queries under Transitive Restricted Expressions 2024 VLDB 4.1905499e-05
11,082 Complex-Path: Effective and Efficient Node Ranking with Paths in Billion-Scale Heterogeneous Graphs 2024 VLDB 4.1905499e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 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.00054430106
115 A Query Language and Optimization Techniques for Unstructured Data 1996 SIGMOD 0.00046301137
253 Query Caching and Optimization in Distributed Mediator Systems 1996 SIGMOD 0.00030517335
256 GraphLog: a Visual Formalism for Real Life Recursion 1990 PODS 0.00030241337
276 Regular Path Queries with Constraints 1997 PODS 0.00029365217
288 Answering Queries Using Templates With Binding Patterns (Extended Abstract) 1995 PODS 0.00028885849
297 Complexity of Answering Queries Using Materialized Views 1998 PODS 0.00028572729
364 A Graphical Query Language Supporting Recursion 1987 SIGMOD 0.00025657601
393 From Structured Documents to Novel Query Facilities 1994 SIGMOD 0.00024506032
533 Answering Recursive Queries Using Views 1997 PODS 0.00020767726
578 The GMAP: A Versatile Tool for Physical Data Independence 1994 VLDB 0.00019825485
583 Answering Queries with Aggregation Using Views 1996 VLDB 0.00019705383
808 Query Containment for Conjunctive Queries With Regular Expressions 1998 PODS 0.000164132
971 Rewriting Aggregate Queries Using Views 1999 PODS 0.00014915911
1,080 Catching the Boat with Strudel: Experiences with a Web-Site Management System 1998 SIGMOD 0.00014204122
1,314 Semistructured Data 1997 PODS 0.00012618313
1,489 On the Decidability of Query Containment under Constraints 1998 PODS 0.00011687823
2,539 Rewriting Queries Using Views in Description Logics 1997 PODS 8.5759464e-05
3,262 Path Constraints on Semistructured and Structured Data 1998 PODS 7.3081091e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
82 Answering Queries Using Views (Extended Abstract) 1995 PODS 0.00054430106
11,834 Bounded Query Rewriting Using Views 2016 PODS 4.1905499e-05
808 Query Containment for Conjunctive Queries With Regular Expressions 1998 PODS 0.000164132
5,144 Scalable Query Rewriting: A Graph-Based Approach 2011 SIGMOD 5.6597671e-05
1,445 Finding Regular Simple Paths in Graph Databases 1989 VLDB 0.00011937596
3,534 Lossless Regular Views 2002 PODS 6.9965349e-05
971 Rewriting Aggregate Queries Using Views 1999 PODS 0.00014915911
2,539 Rewriting Queries Using Views in Description Logics 1997 PODS 8.5759464e-05
3,231 View-Based Query Processing for Regular Path Queries with Inverse 2000 PODS 7.3333516e-05
5,415 Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints 2003 PODS 5.5188622e-05