Query containment for conjunctive queries with regular expressions
Daniela Florescu, Alon Y. Levy, Dan Mircea Suciu · 1998
All query languages proposed for semistructured data share as common characteristic the ability to traverse arbitrary long path in the data in the form of regular path expressions. The expressive power of these languages lies in between that of the relational calculus, and that of query languages with recursion, like datalog. We consider the problems of query containment and query equivalence for a certain subset of the StruQL language implemented in the Strudel web-site management system, consisting of conjunctive queries with regular expressions. It was previously known that contaiment and equivalence are NP-complete for the conjunctive fragment of the relational calculus, and undeciable for datalog. Weshow that these problems are decidable for conjunctive queries with regular path expressions. Both are PSPACE hard: the complexity of our decision algorithm however is higher, leaving a gap between the lower and upper complexity bounds. For a restricted class of conjunctive queries with regular path exrepssions we show that containment and equivalence are NP-complete. This o ers, to our knowledge, the rst example of a query language with recursion in which containment and equivalence have the same complexity as that of conjunctive queries in the relational calculus. 1