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
9.0015589e-05
Overall Rank
2,342 | 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
48 Data Integration: A Theoretical Perspective 2002 PODS 0.00069720859
1,155 A Scalable Algorithm for Answering Queries Using Views 2000 VLDB 0.00013616518
2,034 Views and Queries: Determinacy and Rewriting 2005 PODS 9.7156155e-05
2,399 Query Rewriting for Semistructured Data 1999 SIGMOD 8.8973689e-05
2,505 Graph Pattern Matching in GQL and SQL/PGQ 2022 SIGMOD 8.634551e-05
4,010 A Web Odyssey: from Codd to XML 2001 PODS 6.5351699e-05
4,191 Efficiently Answering Regular Simple Path Queries on Large Labeled Networks 2019 SIGMOD 6.3735885e-05
4,280 Query Planning for Evaluating SPARQL Property Paths 2016 SIGMOD 6.2948356e-05
4,977 Constraint Satisfaction and Database Theory: a Tutorial 2000 PODS 5.7881576e-05
4,990 ZipG: A Memory-efficient Graph Store for Interactive Queries 2017 SIGMOD 5.7825419e-05
5,406 Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints 2003 PODS 5.5243825e-05
5,517 Representing Paths in Graph Database Pattern Matching 2023 VLDB 5.4626107e-05
9,676 Schema-Based Query Optimisation for Graph Databases 2025 SIGMOD 4.3047774e-05
9,826 Exploiting Structure in Regular Expression Queries 2023 SIGMOD 4.2751057e-05
11,014 Efficient Regular Simple Path Queries under Transitive Restricted Expressions 2024 VLDB 4.1945683e-05
11,079 Complex-Path: Effective and Efficient Node Ranking with Paths in Billion-Scale Heterogeneous Graphs 2024 VLDB 4.1945683e-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.00054402763
114 A Query Language and Optimization Techniques for Unstructured Data 1996 SIGMOD 0.00046339735
253 Query Caching and Optimization in Distributed Mediator Systems 1996 SIGMOD 0.00030569863
256 GraphLog: a Visual Formalism for Real Life Recursion 1990 PODS 0.00030259041
274 Regular Path Queries with Constraints 1997 PODS 0.00029390022
291 Answering Queries Using Templates With Binding Patterns (Extended Abstract) 1995 PODS 0.00028831632
297 Complexity of Answering Queries Using Materialized Views 1998 PODS 0.00028596715
363 A Graphical Query Language Supporting Recursion 1987 SIGMOD 0.00025715157
393 From Structured Documents to Novel Query Facilities 1994 SIGMOD 0.00024524092
532 Answering Recursive Queries Using Views 1997 PODS 0.00020778506
578 The GMAP: A Versatile Tool for Physical Data Independence 1994 VLDB 0.00019838707
584 Answering Queries with Aggregation Using Views 1996 VLDB 0.0001971526
810 Query Containment for Conjunctive Queries With Regular Expressions 1998 PODS 0.00016428374
971 Rewriting Aggregate Queries Using Views 1999 PODS 0.00014925576
1,081 Catching the Boat with Strudel: Experiences with a Web-Site Management System 1998 SIGMOD 0.00014216794
1,314 Semistructured Data 1997 PODS 0.0001263326
1,490 On the Decidability of Query Containment under Constraints 1998 PODS 0.00011699154
2,536 Rewriting Queries Using Views in Description Logics 1997 PODS 8.5837937e-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
82 Answering Queries Using Views (Extended Abstract) 1995 PODS 0.00054402763
11,826 Bounded Query Rewriting Using Views 2016 PODS 4.1945683e-05
810 Query Containment for Conjunctive Queries With Regular Expressions 1998 PODS 0.00016428374
5,144 Scalable Query Rewriting: A Graph-Based Approach 2011 SIGMOD 5.6651982e-05
1,444 Finding Regular Simple Paths in Graph Databases 1989 VLDB 0.00011946075
3,531 Lossless Regular Views 2002 PODS 7.003412e-05
971 Rewriting Aggregate Queries Using Views 1999 PODS 0.00014925576
2,536 Rewriting Queries Using Views in Description Logics 1997 PODS 8.5837937e-05
3,228 View-Based Query Processing for Regular Path Queries with Inverse 2000 PODS 7.3405281e-05
5,406 Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints 2003 PODS 5.5243825e-05