Web service composition through declarative queries: the case of conjunctive queries with union and negation

A Web service operation can be seen as a function op: X₁,..., X_n → Y₁,..., Y_m having an input message (request) with n arguments (parts), and an output message (response) with m parts. We study the problem of deciding whether a query Q is feasible, i.e., whether there exists a logically equivalent query Q\´ that can be executed observing the limited access patterns given by the Web service (source) relations. Executability depends on the specific syntactic form of a query, while feasibility is a more "robust" semantic notion, involving all equivalent queries (i.e., reorderings, minimized queries, etc). We show that deciding query feasibility (called "stability") is NP-complete for conjunctive queries (CQ) and for conjunctive queries with union (UCQ).