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
1173
Venue
PODS
Year
1999
Pagerank
9.2348082e-05
Overall Rank
2,066 | 85.83%
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.

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
69 Answering Queries Using Views (Extended Abstract) 1995 PODS 0.00038090878
124 A Query Language and Optimization Techniques for Unstructured Data 1996 SIGMOD 0.00030950263
225 Complexity of Answering Queries Using Materialized Views 1998 PODS 0.00024101949
298 Answering Queries Using Templates With Binding Patterns (Extended Abstract) 1995 PODS 0.00022138018
300 GraphLog: a Visual Formalism for Real Life Recursion 1990 PODS 0.00022046803
312 A Graphical Query Language Supporting Recursion 1987 SIGMOD 0.00021733819
348 Regular Path Queries with Constraints 1997 PODS 0.00020518814
381 Query Caching and Optimization in Distributed Mediator Systems 1996 SIGMOD 0.00019549294
515 Answering Recursive Queries Using Views 1997 PODS 0.00017177428
554 Answering Queries with Aggregation Using Views 1996 VLDB 0.00016580778
570 The GMAP: A Versatile Tool for Physical Data Independence 1994 VLDB 0.00016328445
571 From Structured Documents to Novel Query Facilities 1994 SIGMOD 0.0001632382
686 Query Containment for Conjunctive Queries With Regular Expressions 1998 PODS 0.00014948634
869 Rewriting Aggregate Queries Using Views 1999 PODS 0.00013503594
1,233 Semistructured Data 1997 PODS 0.00011562468
1,302 Catching the Boat with Strudel: Experiences with a Web-Site Management System 1998 SIGMOD 0.00011238375
1,630 On the Decidability of Query Containment under Constraints 1998 PODS 0.00010180625
2,527 Rewriting Queries Using Views in Description Logics 1997 PODS 8.4625195e-05
3,308 Path Constraints on Semistructured and Structured Data 1998 PODS 7.5381026e-05
Previous Page 1 / 1 Next

Semantically Similar Papers