DBScholar

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
hb37439655933ad58
Venue
PODS
Year
1999
Pagerank
9.1379399e-05
Overall Rank
2,043 | 86.28%
DOI
10.1145/303976.303996

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{calvanese_pods99,
        address = {New York, NY, USA},
        series = {{PODS} '99},
        title = {{Rewriting of Regular Expressions and Regular Path Queries}},
        url = {https://dl.acm.org/doi/10.1145/303976.303996},
        doi = {10.1145/303976.303996},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Calvanese, Diego and De Giacomo, Giuseppe and Lenzerini, Maurizio and Vardi, Moshe Y.},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank Citing Paper Year Venue Pagerank
24 Data Integration: A Theoretical Perspective 2002 PODS 0.00055018384
936 A Scalable Algorithm for Answering Queries Using Views 2000 VLDB 0.00012983552
1,494 Graph Pattern Matching in GQL and SQL/PGQ 2022 SIGMOD 0.00010497226
2,046 Views and Queries: Determinacy and Rewriting 2005 PODS 9.1331561e-05
2,128 Query Rewriting for Semistructured Data 1999 SIGMOD 8.9984814e-05
3,422 Query Planning for Evaluating SPARQL Property Paths 2016 SIGMOD 7.3112898e-05
3,523 Efficiently Answering Regular Simple Path Queries on Large Labeled Networks 2019 SIGMOD 7.2309001e-05
4,266 A Web Odyssey: from Codd to XML 2001 PODS 6.6941178e-05
5,230 Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints 2003 PODS 6.2178069e-05
5,453 ZipG: A Memory-efficient Graph Store for Interactive Queries 2017 SIGMOD 6.1229951e-05
5,559 Representing Paths in Graph Database Pattern Matching 2023 VLDB 6.082972e-05
6,406 Constraint Satisfaction and Database Theory: a Tutorial 2000 PODS 5.7934139e-05
9,989 Schema-Based Query Optimisation for Graph Databases 2025 SIGMOD 5.0989764e-05
10,171 Exploiting Structure in Regular Expression Queries 2023 SIGMOD 5.0658661e-05
11,567 Efficient Regular Simple Path Queries under Transitive Restricted Expressions 2024 VLDB 4.9769913e-05
11,615 Complex-Path: Effective and Efficient Node Ranking with Paths in Billion-Scale Heterogeneous Graphs 2024 VLDB 4.9769913e-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
72 Answering Queries Using Views (Extended Abstract) 1995 PODS 0.0003753293
130 A Query Language and Optimization Techniques for Unstructured Data 1996 SIGMOD 0.00030306096
238 Complexity of Answering Queries Using Materialized Views 1998 PODS 0.00023580688
298 GraphLog: a Visual Formalism for Real Life Recursion 1990 PODS 0.00021830158
301 Answering Queries Using Templates With Binding Patterns (Extended Abstract) 1995 PODS 0.00021673683
305 A Graphical Query Language Supporting Recursion 1987 SIGMOD 0.00021580917
356 Regular Path Queries with Constraints 1997 PODS 0.0002009439
399 Query Caching and Optimization in Distributed Mediator Systems 1996 SIGMOD 0.00019134783
532 Answering Recursive Queries Using Views 1997 PODS 0.00016821057
567 Answering Queries with Aggregation Using Views 1996 VLDB 0.00016264813
577 The GMAP: A Versatile Tool for Physical Data Independence 1994 VLDB 0.00016111779
582 From Structured Documents to Novel Query Facilities 1994 SIGMOD 0.00015975125
699 Query Containment for Conjunctive Queries With Regular Expressions 1998 PODS 0.00014680086
880 Rewriting Aggregate Queries Using Views 1999 PODS 0.00013274554
1,254 Semistructured Data 1997 PODS 0.00011331788
1,330 Catching the Boat with Strudel: Experiences with a Web-Site Management System 1998 SIGMOD 0.00010994625
1,661 On the Decidability of Query Containment under Constraints 1998 PODS 9.9545204e-05
2,574 Rewriting Queries Using Views in Description Logics 1997 PODS 8.2749164e-05
3,367 Path Constraints on Semistructured and Structured Data 1998 PODS 7.3693945e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 72 Answering Queries Using Views (Extended Abstract) 1995 PODS
2 12,330 Bounded Query Rewriting Using Views 2016 PODS
3 699 Query Containment for Conjunctive Queries With Regular Expressions 1998 PODS
4 6,227 Scalable Query Rewriting: A Graph-Based Approach 2011 SIGMOD
5 1,597 Finding Regular Simple Paths in Graph Databases 1989 VLDB
6 3,802 Lossless Regular Views 2002 PODS
7 880 Rewriting Aggregate Queries Using Views 1999 PODS
8 2,574 Rewriting Queries Using Views in Description Logics 1997 PODS
9 3,156 View-Based Query Processing for Regular Path Queries with Inverse 2000 PODS
10 5,230 Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints 2003 PODS