Accurately estimating the cardinality of aggregate views is crucial for logical and physical design of data warehouses. While the warehouse is under development and data are not available yet, the approaches based on accessing data cannot be adopted. This paper proposes an approach to estimate the cardinality of views based on a-priori information derived from the application domain. We face the problem by first computing satisfactory bounds for the cardinality, then by capitalizing on these bounds to determine a good probabilistic estimate for it. Bounds are determined by using, besides the functional dependencies expressed by the multidimensional scheme, additional domain-derived information in the form of cardinality constraints which may bound either the cardinality of a given view or the ratio between the cardinalities of two given views. In particular, we propose a bounding strategy which achieves an effective trade-off between the tightness of the bounds produced and the computational complexity.
(D. Theodoratos, J. Hammer, M. Jeusfeld, M. Staudt, eds.) http://sunsite.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-39/ and data warehouses [AGS97]. It represents facts of interest for the decision process into cubes in which each cell contains numerical measures which quantify the fact from different points of view, while each axis represents an interesting dimension for analysis. For instance, within a 4dimensional cube modeling the phone calls supported by a telecommunication company, the dimensions might be the calling number, the number called, the date, and the time segment in which the call is placed; each cube cell could be associated to a measure of the total duration of the calls made from a given number to another number on a given time segment and date.
The basic mechanism to extract significant information from the huge quantity of fine-grained data stored in base cubes is aggregation according to hierarchies of attributes rooted in dimensions [GL97]. In most application cases, cubes are significantly sparse (for instance, most couples of telephone numbers are never connected by a call in a given date), and so are the aggregate views.
Accurately estimating the actual cardinality of each view is crucial for logical and physical design as well as for query processing and optimization [Vas00]. As a relevant case, consider the view materialization problem, where the aggregate views which are the most useful in answering the workload queries have to be selected for materialization (see [TB00] for a survey). Since the number of possible views which can be derived by aggregating a cube is exponential in the number of attributes, most approaches assume that a constraint on the total disk space occupied by materialization is posed, and attempt to find the subset of views which contemporarily satisfies this constraint and minimizes the workload cost [GR00, Gup97, HRU96]. Another case where estimation of view cardinalities is relevant is index selection [GHRU97].
If the data warehouse has already been loaded, view cardinalities can be quite accurately estimated by using statistical techniques based, say, on histograms [MD88] or sampling [HO91]. However, such techniques cannot be applied at all if the data warehouse is still under development, and the estimation of view cardinalities is needed for F W ! V +, i.e., iff . We call multidimensional lattice V W 8A i 2 V 2 W j ! 2 as follows: iff 9Aj (Aj Ai) (S) we will briefly denote with the view that is their least dim(D) ements are and the empty view fg, respectively. V W bound of and in the lattice; given a set of views S, V W We will denote with the view that is the least upper D for the corresponding lattice, whose top and bottom elDefinition 3 (Roll-up) Given the set VD of all possible views on D, we define on VD the roll-up partial order upper bound.
It should be noted that we are using the term view to denote the set of grouping attributes used for aggregation, while the “actual” views will typically include also one or more measures. This slight abuse in terminology is possible since we are interested in determining the cardinality of views, which only depends on the grouping attributes.
Example 1 Consider an enterprise with branches in different cities. A simple dimensional scheme Transfers modeling the transfers of employees between offices might include:
design purposes. To obviate this, current approaches are based on estimation models that only exploit the cardinality of the base cube and that of the single attribute domains [RS97, SDNR96], which however leads to significant overestimation.
In this paper we propose a novel approach to estimate the cardinality of views based on a-priori information derived from the application domain. Similarly to what is done when estimating the cardinality of projections in relational databases [CM95], we face the problem by first computing satisfactory bounds for the cardinality, then by capitalizing on these bounds to determine a good probabilistic estimate for it. Besides the functional dependencies expressed by the multidimensional scheme, the bounds we determine also take into account additional domainderived information expressed in the form of cardinality constraints, namely, bounds of the cardinality of some views and bounds (called k-dependencies) on the ratio between the cardinalities of two views. The computation of bounds is based on a bounding strategy, which is aimed at achieving an effective trade-off between the tightness of the bounds produced and the computational complexity.
The paper is organized as follows. After providing some basic definitions in Section 2, in Section 3 we introduce kdependencies. In Section 4 we outline our overall approach to estimation and show its benefits with an example. Section 5 introduces the basic properties of bounds, proposes an efficient bounding strategy, and sketches a branch-andbound approach to determine the upper bound of the cardinality of a given view when the cardinality constraints in input do not contain k-dependencies; besides, it discusses how the strategy introduced can be improved. Section 6 shows how the bounds derived may be used to improve the cardinality estimates. Finally, Section 7 discusses the most interesting open issues. In this section we formalize the concept of view, define a partial ordering on the set of views, and present the application domain we will use as an example.
It is
A k-dependency is a relevant case of cardinality constraint which naturally generalizes a functional dependency. In the 12-2 authors’ experience, k-dependencies are particularly useful to characterize the knowledge of the business domain held by the experts in the field. For instance, in the transfer domain, we might have some information concerning the number of destination cities for an employee, or on the number of distinct areas moved to from each area. If such information is in the form of bounds, it can be effectively used to improve the bounds of view cardinality. a a m l a c tiy te in it rd se workload dimensional
scheme, cardinality constraints bounder estimator bounds
view materializer logical scheme X on D. We say that a k-dependency (kD) holds between Y X Y k and , and denote it with !k , when (k 1) is an Y upper bound of the number of distinct tuples of which X Y Definition 4 (k-dependency) Let and be two views X X Y correspond to each distinct tuple of within view .
X Y X = fyear; the following kD: !2 , where employeeg, Y = ftoDeptg. Intuitively, from this we can derive that fyear; employee; toDeptg the cardinality of the view can
Example 2 In the Transfers scheme, assume the domain expert provides the following information: The maximum number of inter-department transfers of an employee during one year is 2. This constraint can be formalized by not exceed twice the cardinality of X. V algorithm requires information about a candidate view ,
The framework for this work is the logical design of multidimensional databases carried out off-line, i.e. assuming that the source data cannot be directly queried to estimate the cardinality of multidimensional views. Without loss of generality, in the following we consider that estimates are needed for the purpose of view materialization, thus reliable information on the size of the candidate views has to be supplied to the materialization algorithm.
As sketched in Figure 1, whenever the materialization V a probabilistic estimate for the cardinality of . Note that I the set of cardinality constraints supplied by the user to our approach works in two steps. First, the bounder uses determine effective bounds for the cardinalities of a proper set of views; then, the estimator uses these bounds to derive this two-steps approach generalizes well-known parametric models for the estimation of the cardinality of relational queries [MCS88], and in particular those for projection size estimation [CM95], for which bounds are typically given as input parameters.
The different forms of cardinality constraints we will consider are: v upper bound, denoted as and v+, respectively.1 The V vocally determines two bounds for the cardinality of , We will assume that at least the upper bounds of the cardinalities of all the single attributes in the dimensional scheme are known. This assumption, which is perfectly reasonable in all application domains, is necessary in order to guarantee that at least one upper bound can be determined for each view.
The set I, together with the dimensional scheme D, uniwhich are called the greatest lower bound and the least interpretation of such bounds is as follows: Note that the “union” rule R4 is not strictly needed, since it can be derived from rules R1 (“extension”), R2 (“transitivity”), and R3 (“decomposition”). 4
The kD’s have been studied in the context of relational database theory, where they are also known as numerical dependencies. Grant and Minker [GM83] proved that kD’s are not finitely axiomatizable, thus no fixed set of inference rules can be used to determine whether or not a given kD is logically implied by a set of kD’s. Nonetheless, a basic set of rules, which naturally extend those for FD’s, was proposed in [GM83]. The rules we use, generalized to the multidimensional lattice, are: Z ! W D, since holds. This inequality also applies to W Z w z 3 it follows that implies in each instance of The basic observation to determine bounds for view cardinalities using bounds of the cardinalities of other views is that the multidimensional lattice induces an isomorphic structure over such cardinalities. In fact, from Definition bounds.
As to k-dependencies, their influence on the determination of bounds is summarized by the following lemma. 5.1
In the rest of this section we first propose a decoupled strategy to compute upper bounds (Section 5.1), then we discuss some issues related to coupled strategies (Section 5.2).
The bounding strategy we propose in this section, called cover-based, relies on the concept of cover of a view to compute upper bounds. The following are two preliminary definitions whose aim is to precisely characterize how sets of views and kD’s can be sinergically combined together. W edge of upper bounds ws+ of other views , but no knowlV puting vs+ for an arbitrary view only requires the knowlI all the bounds in are either greatest lower bounds or least v and vs+ such that vs and v+ vs+ both hold. In I; V tion that, given D, , as well as bounds computed by I In this paper we will assume that the input is sound and I Computing the bounds implied by turns out to be I; V v s ing functions that, given D, and , compute bounds V . In general, this step can use further information from s bounding strategy is characterized by a couple of bounds evaluation. We say that a strategy is decoupled iff comminimal. It is straightforward to derive that, in this case, upper bounds (whereas the opposite is not necessarily true). a challenging combinatorial problem, even for “simple” forms of cardinality constraints. For instance, it is known that the problem is NP-hard for arbitrary patterns of functional dependencies [CM92]. Furthermore, the actual computational effort needed to compute these bounds might limit applicability in real-world cases. For this reason, the bounder is built around the concept of bounding strategy. A other terms, a bounding strategy never computes bounds which are more restrictive than the ones logically implied by the input constraints, trading-off accuracy for speed of edge of lower bounds ws , and vice versa. Thus, for a decoupled bounding strategy, the two bounding functions can be defined independently of each other.
Turning to the estimator, our framework supports different probabilistic models. A probabilistic model is a functhe bounder, provides an estimate, v, for the cardinality of the application domain that is not suitable to derive bounds.
Typically this is the case with information concerning average values (e.g., the number of transfers of each employee on each year is 1.5, on the average). 5 = N 0 S by hypothesis, it is Xi Wji Wji ). Note that K 0 Each kD in an S-compliant set is derived from a cor2 S = Yi and there exists a set of kD’s, K0 fWj1 !k1 2 G(K = (N Xi Wji with Wji S, and 2) 0) 0; E0) is a for: : : ; ! 8i = 1; : : : ; p Y1; Wjp Ypg, such that: 1) it is (S; K) 8i = 1; : : : ; p is called a k-set of views iff it is K responding kD in by applying rules R1 and R3 (since, K 0 always holds and that, in general, multiple S-compliant 2 S each Wji is chosen.
kp est, i.e., a set of disjoint directed trees. We call S-compliant a set K0 with such properties.
sets can be derived from the same C, depending on how A
A'
AB
A'B
ABC
BC B
CD C
D
a+ k1 k2.
Wj 2R(G(K0))[S0 (1) card(( ( (N (S0)) 0))) card( card( (N (S0)) 0)) Y Y card( wj+ (Nt0)) u(C; K20) d=ef u(C). cb based bounding strategy computes vc+b as: Coherently with Theorem 1 and Lemma 3, the coverWj 2S0 v+ which, due to Lemma 2, leads to:
LY1 Yql
YL Yql kl;i
that of their Cartesian product, it is
Wi2S
W1;i = recursion, vc+b v+, is correctly defined since we assumed + has exponential size. On the other hand, the V The space of the -covers to be analyzed in order to V -cover C2 can be discarded from the search space without I the input to be minimal. where ucb(C) is obtained by replacing wj+ with wj+;cb in u(C). In general, evaluating the cover-based bound leads to a recursive computational flow; note that the “case-0” of determine vcb following theorem shows that, under some circumstances, a even computing ucb(C2). (2) (3) 12-6 W w + V view is ground iff is in I. A -cover is said to be
ground when all the views it includes are ground. Y2 Z1 W2
V fAB; BCg6vfABCDg opposite is not always true (e.g., ) SivSj then (Si) (Sj necessarily holds, whereas the CgvfAB; CD; For instance, fA0B; Eg. Note that if ABC though ABCD). S u in is not ground. By recursively applying (3), cb(S) will S Proof (sketch): Since is not ground, at least one view < case of strict inequality (ucb(S1) ucb(S)) can arise since be eventually expressed as a product of bounds in I. The in this recursive process there is no guarantee that a given ground view will be generated just once, thus its least upper bound might appear more than once in ucb(S).
ucb(S2). Z = W1 W2, where is the greatest lower bound opY = that W1ÆW2 and W2ÆW1, let W1 W2 and let
The bounds we derive through the strategy described in Section 5.1 are not necessarily the tightest possible ones. In fact, more complex and effective bounding strategies can be defined to the detriment of computational speed. Basically, in these strategies the concept of cover may be extended by considering more complex patterns of views, where upper and lower bounds are used jointly. In this section we present some preliminary considerations on coupled strategies; for simplicity, we will assume that the input does not contain k-dependencies.
As to upper bounding, the cover-based strategy can be improved by exploiting results from majorization theory, which state that the size of the natural join between two relations is majorized when the distributions of the join attribute(s) in the two relations are maximally skewed [IC91]. The extension of this argument to the multidimensional lattice is as follows. Given two views W1 and W2 such erator on the lattice; it can be proved that
The following theorem immediately derives from Lemmas 4 and 5.
Theorem 3 (Sufficiency of Minimal Covers) It is: (5) (6) minfvc+b; wseg (10)
wse Example 7 In the Transfers scheme, we consider three input situations: = ( vse vc+b; wse) d cardinality of the base cube with an estimate, wse, of the V sure of the maximum cardinality of , and by replacing the + , as a mease In our approach, denoted (“safe-estimate”), the above W V W cardinality of a view such that . This leads to: estimate is improved in two ways: by replacing vmax with the upper bound computed for v, for instance vcb W associated to “sibling” views. Let be a view such that Y i to take into account also size information on Zi and V \ W = Z = V W ;, and ; then: v maxfw j w 2 I; W V of is computed as g. Differ
The pattern consisting of views Yi, Wi+1, Zi, and Yi+1, depicted in Figure 3, can in principle be extended Wi+1 Zi, that is, on non-join attributes; this will further strengthen the upper bound. At present, we guess that the exact computation of v+ might involve taking into account patterns that can extend over the whole lattice. However, besides the theoretical interest, it is important to trade-off the increased complexity with the actual gain that could be obtained by having more accurate bounds, considering also how bounds can be used by the estimator.
A coupled strategy requires also lower bounds to be computed, which is radically different from computing upper bounds. In fact, while computing an upper bound corresponds to bounding the size of a join, computing a lower bound corresponds to bounding the size of a projection, where the relevant difference is that projection is a unary operator. This leads to a much simpler situation to deal with, in which Lemma 1 is exploited and the lower bound ently from upper bounds, no combinatorial issues arise in computing lower bounds through this strategy; thus, complexity is linear in the cardinality of I.
A better bound can be obtained by using information + and wse can be considerably lower than d lattice (whose cardinality is typically known) following a v lem of estimating as the one of distributing the tuples of v dim(D) V determine by following all the paths from to . W view , which are estimated to be wse, over a number of V path leading to . Clearly, this represents a simplification Since both vcb vmax and d, respectively, it is usually the case that vse vsdnr. The rationale for (10) is that we can view the probvc+b “buckets”.
Due to the need to know wse, it is obvious that our estimation process must move downward from the top of the of the correct estimation procedure, which would require to On the other hand, this would lead to combinatorial explosion and necessitate of highly complex probabilistic models that are well beyond the current state-of-the-art knowledge.
From a more practical (numerical) point of view, it should be noted that moving from upper bounds to estimates leads to significant differences under specific conditions only. Two relevant cases should be considered, which arise from the limit behavior of Cardenas’ formula:
This formula turns out to significantly overestimate the cardinalities and can easily lead to violate the constraint vsdnr v+. 12-8 1:2 105 1:2 105 + vcb each year is 2, would allow the cardinality of the base cube to be estimated as twice the cardinality of view Probabilistic estimates. Estimates based on Cardenas’ formula can be improved in several ways. In particular, information on lower bounds could be considered by exploiting the results in [CM95], as well as information concerning the distribution of attribute values over their domains. For this, the challenge is to derive new models that can be applied when the data warehouse has not been loaded yet. 7
Conclusions and Open Issues 1:2 105 1:2 105 + V how the upper bound wcb of , + W of , the upper bound vcb V = ffromOÆce; toOÆceg be the base cube and be the W = dim(D) = fdate; employee; fromOÆce; toOÆceg Let view whose cardinality is to be estimated. Table 1 shows and the estimate vse improve as new cardinality constraints are progressively supplied. The estimate vse is based on the estimate of w, wse, which is assumed to be equal to its upper bound wc+b.
I put I, if is sound and minimal, which we argue can Minimality. Throughout this paper we assumed that the cardinality constraints supplied by the domain expert are sound and non redundant. Of course, this gives rise to the problem of determining, given an inbe dealt with as done for, say, functional dependencies (whose inference rules can be used both for schema normalization as well as for input minimization).
In this paper we have shown how cardinality constraints derived from the application domain may be employed to determine effective bounds on the cardinality of aggregate views and how, in turn, such bounds can be used to estimate the cardinality of the views. In order to improve the approach effectiveness, some issues still need to be investigated. In the following we briefly discuss those we believe to be crucial:
Domination. A characterization of domination between k-sets of views, similar to that reported in Definition 9 for sets of views, needs to be developed in order to reduce the complexity of computing upper bounds in presence of k-dependencies.
Cardinality constraints. The input knowledge may be further extended by considering other forms of cardinality constraints which are typically known to the experts of the application domain. For instance, while in this paper we have defined k-dependencies to express bounds on the ratio between the cardinalities of two views, they may also be used to denote the average of such ratio; while this kind of knowledge cannot be used by the bounder, it allows the cardinality estimations to be improved. For instance, knowing that the average number of transfers for each employee on [GHRU97] H. Gupta, V. Harinarayan, A. Rajaraman, and
J. Ullman. Index Selection for OLAP. In Proc.
ICDE’97, pages 208–219, Birmingham, U
Knowledge and Data Engineering, 7(4):641– 655, 1995.
Nicolas, editors, Advances in Database Theory, volume II. Plenum Publ. Co., 1983.
ization for Neste