On solving efficiently the view selection problem under bag and bag-set semantics.pdfVIP

Information Systems 42 (2014) 153–176 Contents lists available at ScienceDirect Information Systems journal homepage: /locate/infosys On solving efficiently the view selection problem under bag and bag-set semantics $ Foto Afrati a, Matthew Damigos a,n, Manolis Gergatsoulis b a Department of Electrical and Computing Engineering, National Technical University of Athens (NTUA), 15773 Athens, Greece b Department of Archives, Library Science and Museology, Ionian University, Ioannou Theotoki 72, 49100 Corfu, Greece a r t i c l e i n f o a b s t r a c t Article history: In this paper, we investigate the problem of view selection for workloads of conjunctive Received 29 August 2012 queries under bag and bag-set semantics. In particular, for both semantics we aim to limit Received in revised form the search space of candidate viewsets. We also start delineating boundaries between 12 December 2013 query workloads for which certain even more restricted search spaces suffice. They suffice Accepted 8 January 2014 in the sense that they do not compromise optimality in that they contain at least one of Recommended by: J. Van den Bussche Available online 18 January 2014 the optimal solutions. We start with the general case for both bag and bag-set semantics, where we give a tight condition that candidate views can satisfy and still the search space Keywords: (thus limited) do