DBScholar

Back to papers

Query Containment for Conjunctive Queries With Regular Expressions

Summary: Proves decidability of query containment for STRUQLO (conjunctive queries with regular path expressions) by reducing it to checking finitely many canonical databases. Introduces syntactic 'query mappings' generalizing CQ containment mappings and shows an NP‑complete restricted fragment. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
h4e576afd753db4cb
Venue
PODS
Year
1998
Pagerank
0.00014638214
Overall Rank
703 | 95.29%
DOI
10.1145/275487.275503

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{florescu_pods98,
        address = {New York, NY, USA},
        series = {{PODS} '98},
        title = {{Query Containment for Conjunctive Queries With Regular Expressions}},
        url = {https://dl.acm.org/doi/10.1145/275487.275503},
        doi = {10.1145/275487.275503},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Florescu, Daniela and Levy, Alon and Suciu, Dan},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 28 of 28 citing papers.

Rank Citing Paper Year Venue Pagerank
24 Data Integration: A Theoretical Perspective 2002 PODS 0.00055201845
719 Querying Graph Databases 2013 PODS 0.00014493767
1,326 DTD Inference for Views of XML Data 2000 PODS 0.0001101664
1,474 Expressive Languages for Path Queries over Graph-Structured Data 2010 PODS 0.00010526746
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
2,743 Efficient Algorithms for Minimizing Tree Pattern Queries 2002 SIGMOD 8.0513978e-05
2,897 On the minimization of XPath queries 2003 VLDB 7.8835751e-05
3,483 The Complexity of Evaluating Path Expressions in SPARQL 2012 PODS 7.2450764e-05
4,609 Queries with Incomplete Answers over Semistructured Data 1999 PODS 6.4891057e-05
5,249 Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints 2003 PODS 6.1979445e-05
5,574 Representing Paths in Graph Database Pattern Matching 2023 VLDB 6.0628579e-05
6,244 The Impact of Virtual Views on Containment 2010 VLDB 5.8219706e-05
6,333 Containment of Nested XML Queries 2004 VLDB 5.7933985e-05
6,872 Minimizing Conjunctive Regular Path Queries 2025 PODS 5.6436814e-05
7,163 Semantic Acyclicity on Graph Databases 2013 PODS 5.5797798e-05
7,372 Containment of Graph Queries Modulo Schema 2024 PODS 5.5249024e-05
7,441 Structured Materialized Views for XML Queries 2007 VLDB 5.5118606e-05
7,461 Conjunctive Regular Path Queries with String Variables 2020 PODS 5.5066099e-05
7,573 Flag & Check: Data Access with Monadically Defined Queries 2013 PODS 5.4773124e-05
7,835 The Complexity of Regular Trail and Simple Path Queries on Undirected Graphs 2022 PODS 5.4281549e-05
8,085 Correlation Constraint Shortest Path over Large Multi-Relation Graphs 2019 VLDB 5.3751128e-05
8,380 Conjunctive Regular Path Queries under Injective Semantics 2023 PODS 5.3271197e-05
10,024 Schema-Based Query Optimisation for Graph Databases 2025 SIGMOD 5.082116e-05
10,205 Exploiting Structure in Regular Expression Queries 2023 SIGMOD 5.0491152e-05
11,884 Data Path Queries over Embedded Graph Databases 2022 PODS 4.9605343e-05
12,568 Spanners: A Formal Framework for Information Extraction 2013 PODS 4.9605343e-05
12,704 Determining Relevance of Accesses at Runtime 2011 PODS 4.9605343e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Previous Page 1 / 1 Next

Semantically Similar Papers