## On Solving Efficiently the View Selection Problem under Bag-semantics

### Foto Afrati, Matthew Damigos, and Manolis Gergatsoulis

**Abstract:** In this paper, we investigate the problem of view selection for
workloads of conjunctive queries under bag semantics. In particular we aim to
limit the search space of candidate viewsets. In that respect we start
delineating the boundary between query workloads for which certain restricted
search spaces suffice. They suffice in the sense that they do not compromise
optimality in that they contain at least one of the optimal solutions. We start
with the general case, where we give a tight condition that candidate views can
satisfy and still the search space (thus limited) does contain at least one
optimal solution. Preliminary experiments show that this reduces the size of the
search space significantly. Then we study special cases. We show that for chain
query workloads, taking only chain views may
miss all optimum solutions, whereas, if we further limit the queries to be path
queries (i.e., chain queries over a single binary relation), then path views
suffice. This last result shows that in the case of path queries, taking query
subexpressions suffice.