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.00014680086
Overall Rank: 699 | 95.31%
DOI: 10.1145/275487.275503

Incoming Non-self Citations Over Time

Authors

1. Daniela Florescu (INRIA)
2. Alon Levy (University of Washington)
3. Dan Suciu (AT&T)

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.00055018384
720	Querying Graph Databases	2013	PODS	0.00014522278
1,315	DTD Inference for Views of XML Data	2000	PODS	0.00011053178
1,468	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS	0.00010561507
2,043	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.1379399e-05
2,128	Query Rewriting for Semistructured Data	1999	SIGMOD	8.9984814e-05
2,733	Efficient Algorithms for Minimizing Tree Pattern Queries	2002	SIGMOD	8.0780747e-05
2,883	On the minimization of XPath queries	2003	VLDB	7.9096688e-05
3,474	The Complexity of Evaluating Path Expressions in SPARQL	2012	PODS	7.2684123e-05
4,594	Queries with Incomplete Answers over Semistructured Data	1999	PODS	6.5106109e-05
5,230	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS	6.2178069e-05
5,559	Representing Paths in Graph Database Pattern Matching	2023	VLDB	6.082972e-05
6,233	The Impact of Virtual Views on Containment	2010	VLDB	5.8412765e-05
6,323	Containment of Nested XML Queries	2004	VLDB	5.8126093e-05
6,855	Minimizing Conjunctive Regular Path Queries	2025	PODS	5.6624049e-05
7,142	Semantic Acyclicity on Graph Databases	2013	PODS	5.5979329e-05
7,350	Containment of Graph Queries Modulo Schema	2024	PODS	5.5432318e-05
7,421	Structured Materialized Views for XML Queries	2007	VLDB	5.5301467e-05
7,440	Conjunctive Regular Path Queries with String Variables	2020	PODS	5.5248786e-05
7,558	Flag & Check: Data Access with Monadically Defined Queries	2013	PODS	5.4954839e-05
7,818	The Complexity of Regular Trail and Simple Path Queries on Undirected Graphs	2022	PODS	5.4461633e-05
8,069	Correlation Constraint Shortest Path over Large Multi-Relation Graphs	2019	VLDB	5.3929452e-05
8,366	Conjunctive Regular Path Queries under Injective Semantics	2023	PODS	5.3447929e-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,840	Data Path Queries over Embedded Graph Databases	2022	PODS	4.9769913e-05
12,525	Spanners: A Formal Framework for Information Extraction	2013	PODS	4.9769913e-05
12,661	Determining Relevance of Accesses at Runtime	2011	PODS	4.9769913e-05

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.

Rank	Cited Paper	Year	Venue	Pagerank
72	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.0003753293
117	Querying Heterogeneous Information Sources Using Source Descriptions	1996	VLDB	0.00031616101
130	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00030306096
317	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00021210493
642	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00015236058
875	Queries Independent of Updates	1993	VLDB	0.0001331025
979	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012723733
1,191	Object Fusion in Mediator Systems	1996	VLDB	0.00011585418
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,521	Constraint Checking with Partial Information	1994	PODS	0.00010374735
1,661	On the Decidability of Query Containment under Constraints	1998	PODS	9.9545204e-05
1,830	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.5453747e-05
3,316	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.4342107e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,128	Query Rewriting for Semistructured Data	1999	SIGMOD
2	1,818	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS
3	8,366	Conjunctive Regular Path Queries under Injective Semantics	2023	PODS
4	7,350	Containment of Graph Queries Modulo Schema	2024	PODS
5	7,066	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS
6	1,468	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS
7	2,043	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS
8	4,594	Queries with Incomplete Answers over Semistructured Data	1999	PODS
9	1,661	On the Decidability of Query Containment under Constraints	1998	PODS
10	5,230	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS