Containment between unions of XPath queries

In this paper, we address the containment problem for unions of XPath queries with and without schema. We find the problem can be always reduced into containment problem between one single query and a union of queries. When schema is not available, the problem can be further reduced into checking containment between pairwise queries (each from one union), but this only holds for some XPath subsets, such as XP { /,//,[] } , but not for XP { /,//,[],* } . We then show the problem is still solvable in XP { /,//,[],* } , though no efficient algorithm exists. When schema is at hand, we propose a strategy to rewrite a query into a union of simplified queries based on schema information, and then apply methods developed when schema is not taken into account. The problem is then reduced into checking containment between unions of queries in XP { /,[] } without schema.