In this paper we focus on the following problem in information management: given a large collection of recorded information and some knowledge of the process that is generating this data we want to build a compact, non-redundant collection of summary (aggregate) tables and indices to facilitate flexible decision support analysis. The additional knowledge is depicted as a graph called the sketch that is supper-imposed over the process and indicates particular parts that we want to analyze. We first show how to select a minimum set of views to answer queries with path-expressions over the given sketch. For queries that also include aggregations, we define two partial orders among the views. The first is used to pick the minimum set of aggregate views to answer any query with no false dismissals, while the second describes an augmented set that allows fewer false positives. Computing a non materialized aggregate is done through appropriate rewriting of the user query. We describe two indexing schemes that use phantom aggregate values and allow us to query a view efficiently even for non-materialized aggregates. Experimental results show these schemes to perform well on synthetic and real datasets.
展开▼
