On solving efficiently the view selection problem under bag-semantics (EN)

Damigos, M (EN)

Gergatsoulis, M (EN)

Afrati, F (EN)

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. © 2009 Springer Berlin Heidelberg. (EN)

conferenceItem (EN)

Optimum solution (EN)

Optimal systems (EN)

Optimal solutions (EN)

Semantics (EN)

Optimality (EN)

Sub-expressions (EN)

View selection problem (EN)

Path queries (EN)

View selection (EN)

Binary relation (EN)

Search spaces (EN)

Conjunctive queries (EN)

Εθνικό Μετσόβιο Πολυτεχνείο

Ψηφιακό Αποθετήριο της Κεντρικής Βιβλιοθήκης του ΕΜΠ | Dspace@NTUA

Κεντρική Βιβλιοθήκη Ε.Μ.Π.

Ιδρυματικό Αποθετήριο

Δημοσιεύσεις μελών Δ.Ε.Π. σε συνέδρια

Lecture Notes in Business Information Processing (EN)

2009 (EN)

http://hdl.handle.net/123456789/35831

12 (EN)

18651348 (EN)

28 (EN)

10.1007/978-3-642-03422-0_2 (EN)

27 LNBIP (EN)