text:
# Materialized View Selection and Maintenance Using Multi-Query OptimizationWork partly supported by a Govt. of India, Department of Science and Technology Grant, and by an IBM University Partnership Program Grant. The work of Prasan Roy was supported by an IBM Research Fellowship. Ramamritham was also supported in part by NSF grant IRI-9619588.

## 1 Introduction

Materialization of views can help speed up query and update processing. Views are especially attractive in data warehousing environments because of the query intensive nature of data warehouses. However, when a warehouse is updated, the materialized views must also be updated. Typically, updates are accumulated and then applied to a data warehouse. Loading of updates and view maintenance in warehouses has traditionally been done at night. While the need to provide up-to-date responses to an increasing query load is growing and the amount of data that gets added to data warehouses has been increasing, the time window available for making the warehouse up-to-date has been shrinking. These trends call for efficient techniques for maintaining the materialized views as and when the warehouse is updated.

Given multiple views, the view maintenance problem can be seen as computing the expressions corresponding to the “delta” of the views, given the “delta”s of the base relations that are used to define the views. The contributions of this paper lie in the exploitation of the Multi-Query Optimization (MQO) framework along with our recently developed efficient algorithms for MQO, to compute the delta expressions corresponding to the multiple views defined in a data warehouse.

It is not difficult to motivate that query optimization techniques are important for choosing an efficient plan for maintaining a view. For example, consider the expression $`(AB)C`$, where $`A`$, $`B`$ and $`C`$ are multisets (i.e., relations with duplicates). Given that the multiset of tuples $`\delta _C^+`$ is inserted into $`C`$, the change to the view is given by $`(AB)\delta _C^+`$. This expression can equivalently be computed as $`(A\delta _C^+)B`$ and by $`(B\delta _C^+)A`$, one of which may be substantially cheaper to compute. Further, in some cases the view may be best maintained by recomputing it, rather than by finding the differentials as above. Vista \[Vis98\] describes how to extend the Volcano query optimizer \[GM91\] to choose the best plan for computing the differential of the result of an expression.

Given a set of queries, multiquery optimization \[Sel88\] provides the possibility of reducing costs by computing shared subexpressions once, materializing them temporarily, and reusing them where required in the given set of queries. Although multiquery optimization was earlier viewed as expensive, our recent work \[RSSB00\] has provided efficient algorithms for multiquery optimization, making it practical. In this paper, we provide practical solutions to the problem of optimizing the update of a set of materialized views, by exploiting these algorithms.

Specifically, our contributions are as follows.

1. We extend the multiquery optimization algorithms to find the best plan for computing the differential of a set of expressions, by exploiting shared subexpressions.

Sharing of subexpressions occurs when multiple views are being maintained, since related views may share subexpressions, and as a result the maintenance expressions may also be shared. Furthermore, sharing can occur even within the plan for maintaining a single view, as we illustrate later in the paper.

Our algorithms choose shared expressions to be temporarily materialized during view maintenance, and choose view maintenance plans that utilize these temporarily materialized results.
2. Just as the presence of views allows queries to be evaluated more efficiently, the maintenance of these views can be made more efficient by the presence of additional views/indices \[RSS96\]. That is, given a set of materialized views to be maintained, we need to choose what additional indices and views should be materialized to minimize overall view maintenance costs.

The choice of additional views must be done in conjunction with choosing plans for maintaining the views. For instance, a plan that seems quite inefficient could become the best plan if some intermediate result of the plan is chosen to be materialized and maintained.

Our contribution here is to show how to extend the multiquery optimization algorithms of \[RSSB00\] to tackle the problems of selecting permanent materialized views, in conjunction with choosing the best plans for updating the views.

We show how to cleanly integrate the choice of expressions/indices to be permanently materialized, with the choice of expressions/indices to be temporarily materialized.

It is worth pointing out that although our focus in this paper is to speed up view maintenance, our algorithms can also be used to choose extra temporary and permanent views in order to speed up a workload containing queries and updates (that trigger view maintenance).

There has been much earlier work on choosing a set of views to be materialized and maintained to optimize given workloads of queries and updates. The major differences between our work and earlier work can be summarized as follows (we outline the differences in detail in Section 2):

1. Given a set of related materialized views, temporarily materializing common subexpressions could have significant benefit. However, earlier work did not consider how to exploit common subexpressions by temporarily materializing them because of their focus on permanent materialization and common subexpressions involving differential relations cannot be permanently materialized.
2. The earlier work does not cover efficient techniques for the implementation of materialized view selection algorithms, in particular, their integration with query optimizers. In the context of materialized view maintenance, this is an important problem since the cost of view maintenance can be reduced by the presence of (additional) indices on relations, and of appropriate extra materialized views.

In contrast, we show how to efficiently choose views/indices to be (permanently) materialized by extending the multiquery optimization algorithms of \[RSSB00\].

The rest of the paper is organized as follows. We outline related work in Section 2, and provide the reader with some background in view maintenance in Section 3. We describe the DAG structure used to represent queries in Section 4, and algorithms to find optimal update plans (without materializing additional views) in Section 5. Section 6 presents an optimized greedy algorithm for selecting extra views for materialization. Section 7 outlines results of a performance study, and Section 8 concludes the paper.

## 2 Related Work

There has been a large volume of research on incremental view maintenance in the past decade. Amongst the early work on computing the differential results of operations/expressions was Blakeley et al. \[BCL86\]. More recent work in this area includes \[GL95, CGL+96, MQM97\]. Gupta and Mumick \[GM95\] provide a survey of view maintenance techniques.

Blakeley et al. \[BCL86\] and Ross et al. \[RSS96\] noted that the computation of the expression differentials has the potential for benefiting from multiquery optimization. In the past, multiquery optimization was viewed as too expensive for practical use. As a result they did not go beyond stating that multiquery optimization could be useful for view maintenance. Our recent work in \[RSSB00\] provides efficient heuristic algorithms for multiquery optimization, and demonstrates that multiquery optimization is feasible and effective.

There has been much work on selection of views to be materialized. One notable early work in this area was by Roussopolous \[Rou82\]. Ross et al. \[RSS96\] considered the selection of extra materialized views to optimize maintenance of other materialized views/assertions, and mention some heuristics. Labio et al. \[LQA97\] provide further heuristics. The problem of materialized view selection for data cubes has seen much work, such as \[HRU96\], who propose a greedy heuristic for the problem. Gupta \[Gup97\] and Gupta and Mumick \[GM99\] extend some of these ideas to a wider class of queries. However, (a) none of the above papers consider implementation details that are important for efficient selection of views, and (b) none of these consider how to optimize view maintenance expressions.

Vista \[Vis98\] describes how to extend the Volcano query optimizer to optimize view maintenance. However, she does not consider the materialization of expressions, whether temporary or permanent. Optimizations that exploit knowledge of foreign key dependencies can be used to detect that certain join results involving differentials will be empty \[QGMW96, Vis98\].

Roy et al. \[RSSB00\] consider how to perform multiquery optimization by selecting subexpressions/indices for temporary materialization. They present important optimizations of a greedy heuristic for materialized view selection that makes the heuristic practical. However, they do not consider updates or view maintenance, which is the focus of this paper. We utilize the optimizations proposed in \[RSSB00\], but the extensions required to to take update costs into account, and optimize view maintenance expressions, are non-trivial.

There has been earlier work on multiquery optimization, including \[Sel88, SSN94, SG90\] and more recently \[SV98\], but none of these consider updates.

## 3 Background and Motivation

We assume that updates (inserts/deletes) to relations are logged in corresponding delta relations, which are made available to the view refresh mechanism. We assume for each relation $`r`$, there are two relations $`\delta _r^+`$ and $`\delta _r^{}`$ denoting, respectively, the (multiset of) tuples inserted into and deleted from the relation $`r`$.

The view refresh mechanism is invoked as part of an update transaction for immediate update, or periodically for deferred updates. In the second case, updates performed by many transactions may be collected together in the delta relations $`\delta _r^+`$ and $`\delta _r^{}`$ for a relation $`r`$. Our techniques work regardless of whether the updates are immediate or deferred.

### 3.1 Computing the Differential of an Operation

There is a considerable amount of literature on computing differentials of operations, as outlined in Section 2. For completeness, we briefly review techniques for computing the differential of an operation in the multiset relational algebra.

#### 3.1.1 Differentials of Joins

Consider a multiset join $`AB`$, and suppose $`A`$ and $`B`$ are updated by inserting the multisets of tuples $`\delta _A^+`$ and $`\delta _B^+`$ respectively. Let $`A^{old}`$ and $`B^{old}`$ refer to the old values of $`A`$ and $`B`$, that is their contents before the update. The multiset of tuples that get added to the view $`V`$ are denoted by $`\delta _V^+`$, and can be computed as:

$$\delta _V^+=(\delta _A^+B^{old})(A^{old}\delta _B^+)(\delta _A^+\delta _B^+)$$

View $`V`$ is then updated as follows: $`VV\delta _V^+`$

Similarly, if tuples $`\delta _A^{}`$ and $`\delta _B^{}`$ are deleted from $`A`$ and $`B`$ respectively, the multiset of tuples

$$\delta _V^{}=(\delta _A^{}B^{old})(A^{old}\delta _B^{})(\delta _A^{}\delta _B^{})$$

get deleted from $`V`$, which is then updated by: $`VV\delta _V^{}`$.

Updates can be modeled as deletes followed by inserts. If both inserts and deletes are present on a relation, we get a more complex expression for updating the relation.

$$VV(A^{old}\delta _B^+)(\delta _A^+B^{old})(\delta _A^+\delta _B^+)(A^{old}\delta _B^{})(\delta _A^{}B^{old})(\delta _A^{}\delta _B^{})$$

In contrast if only one input, say $`A`$, is updated by only insertion the change in the view is much easier to compute:

$$\delta _V^+=\delta _A^+B^{old}$$

and similarly for deletions on $`A`$,

$$\delta _V^{}=\delta _A^{}B^{old}$$

To keep expressions simple (and for another reason which we describe later in Section 3.2.3) we assume that updates are propagated one relation at a time, and only one type of update at a time. This simply means we compute the effect of all inserts on $`A`$, then update $`A`$ with $`\delta _A^+`$, then compute the effects of all deletes on $`A`$, update $`A`$ with $`\delta _A^{}`$. We then proceed with inserts to $`B`$, and then with deletes from $`B`$.

The net result is the same as if the more complicated expressions are used, but the expressions we need to deal with are much simpler. Note that an operation may have two complex expressions as inputs, and if both use a particular relation, even with this restriction there may be differential results on both its inputs, in which case the more complex expression allowing differentials on both inputs must be used.

#### 3.1.2 Differentials of Other Operations

If the result of a groupby/aggregate operation, such as $`{}_{A}{}^{}𝒢_{count(B)}^{}(E)`$, has been materialized (and the aggregate function is distributive), the change in the aggregate result can be computed using only the changes ($`\delta _E^+`$ and $`\delta _E^{}`$) to the input $`E`$, and the old result of the aggregation.111For some operations like $`average`$, the count of tuples in each group must also be materialized. Even for the $`sum`$ operation, the count of tuples is needed to deal with deletions. The group-by/aggregation operation is executed on the tuples from the delta relations, and the results are merged into the existing materialized view using a merge operation. For more details, see, e.g., \[GM95\], and for extensions to operations such as median, see \[RSSS94\].

To compute the differential result of an aggregate/grouping operation whose result has not been materialized, we would have to recompute the aggregate values for all groups which are affected by the update. This may involve significant extra work.222There are techniques, such as \[CGL+96, MQM97\], that use differentials of more complex forms, such as changes in the value of an aggregate result, to avoid recomputing aggregate values in some special cases. Our techniques can be extended to deal with such differentials, but for simplicity we do not consider such techniques here.

Standard techniques are available for computing the differentials of other operations, such as duplicate elimination (and projection), and outer joins \[GL95, GJM97\]. We omit details but note that we can use these techniques without any changes to our optimization algorithms.

### 3.2 Computing the Differential of an Expression

Views are defined by potentially complex expressions, hence we need to find the differential of an entire expressions.

#### 3.2.1 Generating a Differential Expression

Techniques, such as that of \[GL95\] can be used to generate an expression that computes the differential of a given expression. However, the resultant expression can be very large – exponential in the size of the query. For instance consider the view $`V=ABC`$, with inserts on all three relations. The differential in the result of $`V`$ can be computed as

> $`(\delta _A^+BC)(A\delta _B^+C)(AB\delta _c^+)(A\delta _B^+\delta _C^+)`$
> $`(\delta _A^+B\delta _C^+)(\delta _A^+\delta _B^+C)(\delta _A^+\delta _B^+\delta _C^+)`$

The size of this expression is exponential in the number of relations. Optimizing such large expressions can be quite expensive, since query optimization is exponential in the size of the expression. There are many common subexpressions in the above expression, and the above expression could be simplified by factoring, to get:
$`(\delta _A^+BC)((A\delta _A^+)\delta _B^+C)((A\delta _A^+)(B\delta _B^+)\delta _C^+)`$
But creating simplified forms of differential expressions is difficult with more complex expressions containing operations other than join.

Therefore our algorithms use an alternative technique, which we outline in the next section.

#### 3.2.2 Propagating Updates Up An Expression

An alternative to generating a differential expression is to propagate differentials up an expression \[Rou82, RSS96\]. Propagation is best understood by visualizing an expression as a tree. The differential of a node in the tree is computed using the differential (and if necessary, the old value) of its inputs, as described earlier. We start at the leaves of the tree, and proceed upwards, computing the differential expressions at each node.

For example, consider an expression $`(AB)C)`$, and suppose we wish to propagate inserts to $`A`$. We can do so by first computing the differential of the node $`AB`$ as $`\delta _A^+B`$. We then join this differential with $`C`$, which is the other input of its parent node, to get the differential of the parent.

As mentioned earlier, if there are updates to multiple relations, we propagate one type of update to one relation at a time. Doing so simplifies the expressions for computing the differentials, as outlined in Section 3.1, and permits a different evaluation plan to be chosen for each expression; this is essential for efficient view maintenance, as we will see next, in Section 3.2.3.

The process of computing the differential of an expression can be expressed purely in terms of how to compute the differentials for each operation in the expression. There is no need to rewrite the entire expression. Note also that the procedure for computing differentials of an expression can be easily extended to handle expressions using new types of operations, so long as we have a way of incrementally computing the differential of the operation.

#### 3.2.3 The Role of Query Optimization

Consider an expression $`A(BC)`$, and suppose tuples are inserted into $`A`$. We can compute the differential of the result as $`\delta _A^+(BC)`$. If we compute this expression as shown, we would need to compute $`BC`$, which does not involve any $`\delta `$ relation, and hence may be large and expensive. A better way of evaluating the differential may be $`(\delta _A^+B)C`$. Note that the two variants are logically equivalent.

Thus, for efficient differential computation, query optimization must be applied to the update expressions to choose the cheapest variant, as proposed in \[Vis98\].

Furthermore, note that if we wish to compute the differential when tuples are inserted into $`C`$, the plan $`(\delta _C^+B)A`$ or $`(\delta _C^+A)B`$ may be preferable to $`(AB)\delta _C^+`$. Thus, using a single expression, such as $`(AB)C`$ to propagate differentials to $`A`$, $`B`$ and $`C`$ is likely to perform badly for at least one of the differentials.

For this reason, we propagate differentials of only one relation at a time, and choose a separate plan for each differential propagation.

We use a query optimizer for choosing best plans for such propagation, and our optimizer uses a DAG representation that compactly represents all expressions equivalent to a given expression. Since all alternative expressions above are available, the best one can be chosen for the propagation of each differential. We present details in Sections 4 and 5.

Note also that recomputation of a materialized view is always an alternative to computing the differential in its result and updating it. Thus, the query optimizer must choose recomputation over incremental view maintenance, if recomputation is cheaper.

### 3.3 The Role of Multi-Query Optimization in View Update

Multi-query optimization attempts at exploiting common sub-expressions within a query, or across queries in a batch of queries submitted together, to reduce the query evaluation cost. In the context of view update, sharing can occur across the tasks of computing differentials of different views, or even within the task of computing the differential of a single view, as we show below.

It is easy to see that related queries may share subexpressions, and if so, it may be best to compute the shared subexpression once, materialize it, and reuse it. However, this decision must be done in a cost based manner, as the following example from \[RSSB00\] illustrates.

###### Example 3.1

Let $`Q_1`$ and $`Q_2`$ be two queries whose locally optimal plans (i.e., individual best plans) are $`(RS)P`$ and $`(RT)S`$ respectively. The best plans for $`Q_1`$ and $`Q_2`$ do not have any common sub-expressions. However, if we choose the alternative plan $`(RS)T`$ (which may not be locally optimal) for $`Q_2`$, then, it is clear that $`RS`$ is a common sub-expression and can be computed once and used in both queries. This alternative with sharing of $`RS`$ may be the globally optimal choice.

On the other hand, blindly using a common sub-expression may not always lead to a globally optimal strategy. For example, there may be cases where the cost of joining the expression $`RS`$ with $`T`$ is very large compared to the cost of the plan $`(RT)S`$; in such cases it may make no sense to reuse $`RS`$ even if it were available. $`\mathrm{}`$

In the context of view maintenance, if two materialized views have common subexpressions, as in the example above, the expressions for computing the differential of the common subexpression would also be shared.

To illustrate subexpression sharing possibilities within a single view maintenance query, consider a view $`V`$ defined as in the example below.

###### Example 3.2

Let view $`V=ABCD`$. Suppose there are inserts on all four relations.

The differential of $`V`$ can then be computed using

> $`(\delta _A^+BCD)((A\delta _A^+)\delta _B^+CD)`$
> $`((A\delta _A^+)(B\delta _B^+)\delta _C^+D)((A\delta _A^+)(B\delta _B^+)(C\delta _C^+)\delta _D^+)`$

The above expression represents algebraically the effect of propagating differentials one at a time, as described in Section 3.2.2.

Note that there are several potential common subexpressions in the above expression. For instance, if the plans chosen for the first two terms of the above union are $`(\delta _A^+(B(CD)))`$ and $`((A\delta _A^+)(\delta _B^+(CD)))`$, then $`CD`$ is a common subexpression of the two. If the above plans are chosen, the subexpression can be computed once and shared. Similarly, $`(A\delta _A^+)(B\delta _B^+)`$ is potentially a common subexpression.

The alternative plans of $`(((\delta _A^+B)C)D)`$ and $`((((A\delta _A^+)\delta _B^+)C)D)`$ offer no sharing possibilities, but may still be cheaper. $`\mathrm{}`$

Which the above plans should be used, and whether the common subexpressions should materialized and shared is a decision for the multiquery optimizer to make in a cost-based manner. Thus, it is the job of the multiquery optimizer to find the best overall plan taking sharing possibilities into account.

## 4 DAG Representation of Queries

Our algorithms use an extended form of the DAG representation of queries used, for instance, in Volcano \[GM91\]. In this section we summarize the DAG representation and terminology from \[RSSB00\].

An AND–OR DAG is a directed acyclic graph whose nodes can be divided into AND-nodes and OR-nodes; the AND-nodes have only OR-nodes as children and OR-nodes have only AND-nodes as children.

An AND-node in the AND-OR DAG corresponds to an algebraic operation, such as the join operation ($``$) or a select operation ($`\sigma `$). It represents the expression defined by the operation and its inputs. Hereafter, we refer to the AND-nodes as operation nodes. An OR-node in the AND-OR DAG represents a set of logical expressions that generate the same result set; the set of such expressions is defined by the children AND nodes of the OR node, and their inputs. We shall refer to the OR-nodes as equivalence nodes henceforth.

### 4.1 Representing a Single Query

A given query is initially represented directly in the AND-OR DAG formulation. For example, the query tree of Figure 1(a) is initially represented in the AND-OR DAG formulation, as shown in Figure 1(b). Equivalence nodes (OR-nodes) are shown as boxes, while operation nodes (AND-nodes) are shown as circles.

The initial AND-OR DAG is then expanded by applying all possible transformations on every node of the initial query DAG representing the given set of queries. Suppose the only transformations possible are join associativity and commutativity. Then the plans $`A(BC)`$ and $`(AC)B`$, as well as several plans equivalent to these modulo commutativity can be obtained by transformations on the initial AND-OR-DAG of Figure 1(b). These are represented in the DAG shown in Figure 1(c). We shall refer to the DAG after all transformations have been applied as the expanded DAG. Note that the expanded DAG has exactly one equivalence node for every subset of $`\{A,B,C\}`$; the node represents all ways of computing the joins of the relations in that subset.

### 4.2 Representing Sets of Queries in a DAG

Queries are inserted into the DAG structure one at a time. When a query is inserted, equivalence nodes and operation nodes are created for each of the operations in its initial query tree. Some of the subexpressions of the initial query tree may be equivalent to expressions already in the DAG. Further, subexpressions of a query may be equivalent to each other, even if syntactically different. For example, query may contain a subexpression that is logically equivalent to, but syntactically different from another subexpression of the query (e.g., $`(AB)C`$, and $`A(BC)`$).

Before the second subexpression is expanded, the DAG would contain two different equivalence nodes representing the two subexpressions. \[RSSB00\] modifies the Volcano DAG generation algorithm such that whenever it finds nodes to be equivalent (in the above example, after applying join associativity) it unifies the nodes, replacing them by a single equivalence node. The Volcano optimizer \[GM91\] already has a hashing-based scheme to efficiently detect repeated expressions, thereby avoiding creation of new nodes that are equivalent to existing nodes. The extension of \[RSSB00\] additionally unifies existing logically equivalent nodes. Another extension is to detect and handle subsumption derivations. For example, $`\sigma _{A<5}(E)`$ can be computed from $`\sigma _{A<10}(E)`$ if they both appear in a set of queries. Similarly, if we have aggregations $`{}_{dno}{}^{}𝒢_{sum(Sal)}^{}(E)`$ and $`{}_{age}{}^{}𝒢_{sum(Sal)}^{}(E)`$, we can introduce a new equivalence node $`{}_{dno,age}{}^{}𝒢_{sum(Sal)}^{}(E)`$ and add derivations of the other two from this one. For more details of unification and subsumption derivations involving selections and aggregation, see \[RSSB00\].

### 4.3 Physical Properties

It is straightforward to refine the above AND-OR DAG representation to represent physical properties \[GM91\], such as sort order, that do not form part of the logical data model, and obtain a physical AND-OR DAG 333For example, an equivalence node is refined to multiple physical equivalence nodes, one per required physical property, in the physical AND-OR DAG.. The presence of an index on a result is also modeled as a physical property of the result by \[RSSB00\], making the code that handles physical properties also perform index selection. Physical properties of intermediate results are important; for example, if an intermediate result is sorted on a join attribute, the join cost can potentially be reduced by using a merge join. This also holds true of intermediate results that are materialized and shared. Our implementation indeed handles physical properties, including sort orders and indices, but to keep the description simple we do not explicitly consider physical properties.

## 5 Finding Optimal Plans

We first outline how to find optimal plans for queries, following \[RSSB00\], and then outline extensions to find optimal plans for view maintenance. In both cases, we assume that the set of views chosen for materialization is fixed. In Section 6 we outline how to integrate the choice of views to materialize with the choice of optimal plans for view maintenance.

### 5.1 Finding Optimal Plans for Queries

The Volcano optimization algorithm finds the best plan for each node of the expanded DAG by performing a depth first traversal of the DAG. Costs are defined for operation and equivalence nodes. The computation cost of an operation node is $`o`$ is defined as follows:
$`compcost(o)=`$ cost of executing $`(o)`$ \+ $`\mathrm{\Sigma }_{e_ichildren(o)}compcost(e_i)`$
The children of $`o`$ (if any) are equivalence nodes. The computation cost of an equivalence node $`e`$ is given as
$`compcost(e)=min\{compcost(o_i)|o_ichildren(e)\}`$
and is $`0`$ if the node has no children (i.e., it represents a relation).444Relation scans are explicitly represented as an operation and assigned a cost. Note that the cost of executing an operation $`o`$ also takes into account the cost of reading the inputs, if they are not pipelined.

Volcano also caches the best plan it finds for each equivalence node, in case the node is re-visited during the depth first search of the DAG.

A simple extension of the Volcano algorithm to find best plans given a set of materialized views is described in \[RSSB00\]. We outline this extension below.

Let $`reusecost(m)`$ denote the cost of reusing the materialized result of $`m`$, and let $`M`$ denote the set of materialized nodes.

To find the cost of a node given a set of nodes $`M`$ have been materialized, we simply use the Volcano cost formulae above for the query, with the following change. When computing the cost of an operation node $`o`$, if an input equivalence node $`e`$ is materialized (i.e., in $`M`$), the minimum of $`reusecost(e)`$ and $`compcost(e)`$ is used for computing $`compcost(o)`$. Thus, we use the following expression instead:
$`compcost(o,M)=`$ cost of executing $`(o)`$ \+ $`\mathrm{\Sigma }_{e_ichildren(o)}C(e_i,M)`$

| where $`C(e_i,M)=compcost(e_i)`$ if $`e_iM`$ |
| --- |
|  | $`=min(compcost(e_i,M),reusecost(e_i))`$ if $`e_iM`$. |

and $`compcost`$ for equivalence nodes is defined as before. Thus, the extended optimizer computes best plans for the query in the presence of materialized results. The extra optimization overhead is quite small.

### 5.2 Extending the DAG Structure for Computing Differentials

We now outline how to extend the DAG structure to represent the differentials of a set of expressions. We first construct the expanded DAG for the given expression (or set of expressions). As in Volcano, each equivalence node in the DAG has a set of logical properties such as the schema of the expression result, and estimated statistics about the result such as number of tuples. Once the best plan is computed for a node, it is cached in case it is needed later during optimization.

If there are $`n`$ relations, $`R_1,\mathrm{},R_n`$, we need to store information about the differentials of the node with respect to $`\delta _{R_1}^+`$, $`\delta _{R_1}^{}`$, $`\delta _{R_2}^+`$, $`\delta _{R_2}^{}`$, and so on until $`\delta _{R_n}^+`$, $`\delta _{R_n}^{}`$. We number these updates as $`1,\mathrm{},2n`$, and use these numbers to identify the update.

To optimize differential plans, each equivalence node stores information for the differentials of the expression with respect to each update type, in addition to information about the full result. Each equivalence node $`e`$ therefore stores an array of $`2n`$ records, as below. Each odd numbered entry $`2i1,i=1..n`$, of this array contains:

1. logical properties (such as schema and estimated statistics) of the differential of $`e`$ with respect to inserts on $`R_i`$
2. the best plan for computing the differential of $`e`$ with respect to inserts on $`R_i`$
3. the logical properties of the full result of the equivalence node after inserts and deletes to relations $`R_1,\mathrm{},R_{i1}`$ have been propagated

Similarly, each even numbered entry $`2i,i=1..n`$, of this array contains similar information on differentials and best plans with respect to the deletes on $`R_i`$, and the logical properties for the full result of the equivalence node after inserts and deletes to relations $`R_1,\mathrm{},R_{i1}`$, and inserts to $`R_i`$ have been propagated.

In addition, as in the original representation, each node stores the best plan for (and cost of) recomputing the entire result of the node after all updates have been made on the base relations.

The logical properties of the differentials are computed by a bottom-up traversal of the DAG. We describe later how the best plans for computing differentials are computed and stored. If an equivalence node does not depend on relation $`R_i`$, we flag this during the above bottom-up traversal, and set the plans in entry $`2i`$ and $`2i+1`$ to be null.

The traversal also computes and stores an estimate of the execution cost of the differential version of each operation in the DAG (such as a join or an aggregation). The properties of the differentials of its inputs, as well as the full version of the input, where required, are used to compute this estimate.

### 5.3 Finding Optimal Plans for Updates

We now outline how to find optimal plans for updates, using the above mentioned DAG representation. Recall the example from Section 3.2.3, with the expression being $`A(BC)`$, and an insert on $`A`$, the plan $`(\delta _A^+B)C`$, is likely to be more efficient than $`\delta _A^+(BC)`$, and should be considered. Luckily for us, the DAG representation of the query represents $`(AB)C`$ in addition to $`A(BC)`$ (see Figure 1).

We now extend the technique for finding optimal plans for queries described in Section 5.1, to find the optimal way of propagating the differential $`\delta _A^+`$.

Some equivalence nodes do not depend on some relations, and their differential with respect to the relation will be empty. Let $`\text{diffChildren}(o,i)`$ denote all equivalence node children of $`o`$ whose differential is non-empty on update $`i`$, and $`\text{fullChildren}(o,i)`$ denotes all children of $`o`$ whose full results are required to compute the differential of $`o`$, in conjunction with $`\text{diffChildren}(o,i)`$.

For instance, diffChildren for an operation that joins $`A`$ with $`(BC)`$, with respect to an insert on $`B`$, is the node $`BC`$, and correspondingly fullChildren of the node is $`A`$.

Given an operation node $`o`$ in the DAG, let $`\delta (o,i)`$ denote the differential of operation $`o`$ with respect to update $`i`$. Also let $`\text{localDiffCost}(o,i)`$ denote the cost of executing the operations in $`\delta (o,i)`$, without counting the cost of generating its inputs.

Similarly, for an equivalence node $`e`$, let $`\delta (e,i)`$ denote the differential result of $`e`$ with respect to update $`i`$. Then, the total cost of generating the differential result of an operation node $`o`$ with respect to update $`i`$, $`\text{diffCost}(o,i)`$ can be computed by:

$$\text{localDiffCost}(o,i)+\mathrm{\Sigma }_{e_j\text{diffChildren}(o,i)}\text{diffCost}(e_j,i)+\mathrm{\Sigma }_{e_j\text{fullChildren}(o,i)}compcost(e_j)$$

The cost of computing the differential of an equivalence node $`e`$ with respect to update $`i`$ is given as
$`\text{diffCost}(e,i)=min\{\text{diffCost}(o_j,i)|o_jchildren(e)\}`$
and is $`0`$ if the node has no children (i.e., it represents a relation or a relation differential). The definition of $`compcost`$ is as defined earlier in Section 5.1, and represents the cost of recomputation of the node after updates have been performed on the database relations.

The above formula is extended for the case where some nodes are materialized, as follows. Note that the full result of a node may be materialized, and independently, any of its differential results may also be (temporarily) materialized. Let the set of materialized results be $`M`$; For an operation node $`o`$, we compute $`\text{diffCost}(o,M,i)`$ as:

$$\text{localDiffCost}(o,i)+\mathrm{\Sigma }_{e_j\text{diffChildren}(o,i)}C(e_j,M,i)+\mathrm{\Sigma }_{e_j\text{fullChildren}(o,i)}C(e_j,M)$$

where $`C`$ is defined as follows: if $`\delta (e,i)`$ is not materialized (i.e., not in $`M`$),
$`C(e,M,i)=min\{\text{diffCost}(o_j,M,i)|o_jchildren(e)\}`$
and if $`\delta (e,i)`$ is materialized (i.e., in $`M`$),
$`C(e,M,i)=min(reusecost(e,i),min\{\text{diffCost}(o_j,M,i)|o_jchildren(e)\})`$
and $`reusecost(e,i)`$ denotes the cost of reusing the materialized result of $`\delta (e,i)`$. Also, $`C(e_j,M)`$ plays the same role for the full result of node $`e_j`$, as defined in Section 5.1.

For an equivalence node $`e`$, $`\text{diffCost}(e,M,i)=min\{\text{diffCost}(o_j,M,i)|o_jchildren(e)\}`$
and is $`0`$ if the node has no children (i.e., it represents a relation or a relation differential). That is, diffCost represents the cost of computing the differential, even if the differential is materialized.

For each equivalence node $`e`$, the operation node corresponding to the minimum cost in the above formula defines the (top node of the) best plan for $`\delta (e,i)`$, given that results in $`M`$ are materialized.

Further, we can compute the total cost of computing the differential of a node as
$`\text{totalDiffCost}(e,M)=\mathrm{\Sigma }_{i=1\mathrm{}2n}\text{diffCost}(e,M)`$.

We perform a single traversal of the DAG to compute the costs for each equivalence/operation node, based on the above equations. During the traversal we also cache the best (minimum cost) plan computed for each differential, just as we cache the best plans for each full result.

Note that if both inputs to a join $`E_1E_2`$ are expressions using a common relation $`R`$, an update to $`R`$ results in changes to both inputs, and as a result, the update expression for the join is $`(\delta _{E_1}^+E_2)((E_1\delta _{E_1}^+)\delta _{E_2}^+)`$. In this case, a join in the original expression has been converted into a union of two joins. The best plan for each join is found, giving the best plan for the entire expression, and this combined best plan must be stored (and used to compute the cost of finding the differential).

Optimizations that exploit knowledge of foreign key dependencies can be used to detect that certain join results involving differentials will be empty \[QGMW96, Vis98\]. For instance, if $`r.B`$ is a foreign key into $`s.A`$, then the join of $`\delta _s^+`$ and $`r`$ will be empty. Based on this, parts of the differential expression can be detected to be empty, and eliminated during optimization.

## 6 The Greedy Algorithm for Selecting Materialized Views

Till now we assumed that the set of materialized nodes is fixed. We now describe how to integrate the choice of extra materialized views/indices with the choice of best plans for view maintenance. Our algorithm is based on a greedy heuristic. We first present the basic algorithm, then some optimizations, and extensions, below.

### 6.1 The Basic Greedy Algorithm

As outlined earlier, we first take the given set of materialized views $`𝒱`$, and build a DAG structure on the expressions defining the views. The nodes of the DAG corresponding to views in $`𝒱`$ are marked as already chosen for materialization.

We consider both full and differential results for materialization. A result is identified by a node and an update number (in our implementation a full result is identified by the update number $`0`$, and differential results by numbers $`1\mathrm{}2n`$).

If a result is chosen for temporary materialization, we must take into account the cost of computing it. And if it is chosen for permanent materialization, we must take into account the cost of maintaining it (we need not consider the cost of initial materialization since it is a one time cost).

The cost of maintaining a node incrementally is the sum of the costs of its differentials:
$`maintcost(n,M)=\text{totalDiffCost}(n,M)+mergeCost(n)`$
where $`mergeCost(n)`$ denotes the cost of updating the materialized result of $`n`$ using the differentials.

For a full result $`n`$, we define
$`cost(n,M)=min(compcost(n,M)+matcost(n),maintcost(n,M))`$
where $`matcost(n)`$ denotes the cost of writing out the computed result of $`n`$. That is, when finding the cost of the full result of a materialized node, we take the minimum of the cost via recomputation and the cost via computing the differentials.

For a differential result $`x=\delta (n,i)`$, we define
$`cost(x,M)=\text{diffCost}(n,M,i)+matcost(x)`$.
Given a set $`S`$ of results (full/differential), let $`cost(S,M)`$ be defined as
$`cost(S,M)=\mathrm{\Sigma }_{qS}cost(q,M)`$
Given a set of results $`M`$ already chosen to be materialized, and a result $`x`$, the benefit of additionally materializing $`x`$, $`benefit(x,M)`$, is defined as:
$`benefit(x,M)=cost(M,M)(cost(M,\{x\}M)+cost(x,M))`$
Note that $`(cost(M,\{x\}M)+cost(x,M))`$ is equivalent to $`cost(M\{x\},M\{x\})`$.

Figure 2 outlines a greedy algorithm that iteratively picks nodes to be materialized. The procedure takes as input the set of candidate results (equivalence nodes, and their differentials) for materialization. At each iteration, the node $`x`$ that gives the maximum reduction in the cost if it is materialized, is chosen to be added to $`X`$.

The procedure not only selects results for maintenance, but also decides on how they should be maintained. Specifically, for full results, it chooses the cheaper of recomputation (including the cost of storing the result), and differential computation (including the cost of performing the computed differential updates). If recomputation is cheaper for a result, and the result was not part of the given set of materialized view, the result can be materialized temporarily during view maintenance, and discarded later. Differential results that are chosen to be materialized are materialized only temporarily since they are only used during view maintenance.

### 6.2 Optimizations

The greedy algorithm as described above can be expensive due to the large number of times the function $`benefit`$ is called, (which in turn calls the expensive function $`cost()`$).

Some important optimizations to the greedy algorithm for multi-query optimization are presented in \[RSSB00\]. We use two of the optimizations, with some extensions for handling differentials:

1. There are many calls to benefit (and thereby to $`cost()`$) at line L1 of Figure 2, with different parameters. A simple option is to process each call to $`cost`$ independent of other calls. However, observe that the set of materialized nodes which is the second argument of $`cost`$ changes minimally in successive calls — successive calls take parameters of the form $`cost(R,\{x\}X)`$, where only $`x`$ varies. That is, instead of considering $`x_1X`$ for materialization, we are now considering storing $`x_2X`$ for materialization. The best plans computed earlier does not change for nodes that are not ancestors of either $`x_1`$ or $`x_2`$. It makes sense for a call to leverage the work done by a previous call by recomputing best plans only for ancestors of $`x_1`$ and $`x_2`$.

A novel incremental cost update algorithm is presented in \[RSSB00\]. This algorithm maintains the state of the DAG (which includes previously computed best plans for the equivalence nodes) across calls to $`cost`$, and may even avoid visiting many of the ancestors of $`x_1`$ (which is unmaterialized) and $`x_2`$ (which is materialized).

In our context of finding update plans, we have to modify the incremental cost update algorithm slightly.

1. If the full result of a node is materialized, we update not only the cost of computing the full result of each ancestor node, but also the costs for the $`2n`$ differentials of each ancestor node since the full result may be used in any of the $`2n`$ differentials. Propagation up from an ancestor node can be stopped if there is no change in cost to computing the full result or any of the differentials.
    2. If the differential of a node with respect to update $`i`$ is materialized, we update only the differentials of its ancestors with respect to update $`i`$. Propagation can stop on ancestors whose differentials with respect to $`i`$ do not change in cost.
2. The monotonicity optimization works as follows. With the greedy algorithm as presented above, in each iteration the benefit of every candidate node that is not yet materialized is recomputed since it may have changed.

The monotonicity optimization is based on the assumption that the benefit of a node cannot increase as other nodes are chosen to be materialized – while this is not always true, it is often true in practice. The monotonicity optimization makes the above assumption, and does not recompute the benefit of a node $`x`$ if the new benefit of some node $`y`$ is higher than the previously computed benefit of $`x`$. It is clearly preferable to materialize $`y`$ at this stage, rather than $`x`$ — assuming monotonicity holds, the benefit of $`x`$ could not have increased since it was last computed, and it cannot be the node with highest benefit now, hence its benefit need not be recomputed now.

Thus, recomputations of benefit are greatly reduced.

\[RSSB00\] presents a third optimization based on potential sharability of nodes between queries. This optimization is not relevant here, since even a node that is not sharable may be worth materializing permanently.

For the purpose of this paper, the details of the above optimizations are not critical, but the interested reader may refer to \[RSSB00\] for details.

The Greedy procedure can be extended in a straightforward manner to consider a workload of queries, along with periodic updates, and to choose the best set of results (and indices) to materialize, to minimize the cost of the queries and view update. Some optimizations are needed to handle large workloads \[RSSB00\]. We can also introduce limits on space for storing permanently materialized results and temporarily materialized results. Results can then be materialized in the order of benefit per unit space, instead of just benefit.

## 7 Performance Study

We implemented the algorithm described earlier for finding optimal plans for view maintenance. Like the existing multiquery optimization code, the new code implements index selection along with selection of results to materialize. Our current implementation has a restriction in that it only considers full results for materialization, although a version which also considers differential results for materialization should be ready shortly. Thus our estimated benefits are actually conservative, and we may be able to get even better results once the full implementation is ready. However, the benefits are already very significant.

### 7.1 Performance Model

We used a benchmark consisting of TPC-D queries (and some variants based on the same TPC-D schema). The performance measure is estimated execution cost, called plan cost in the performance graphs. Our cost model extends the cost model used in the multiquery optimizer, by taking differential computation into account. The cost model used takes into account number of seeks, amount of data read, amount of data written, and CPU time for in-memory processing. Since we do not currently have a query execution engine which we can extend to perform differential view maintenance, we are unable get actual numbers. However, the cost model is fairly sophisticated, and further, benefits for multiquery optimization predicted by the basic cost model have been verified by running rewritten queries on commercial database systems (\[RSSB00\], and results in a companion paper on query result caching), giving support to the accuracy of estimated benefits.

We provide performance numbers for different percentages of updates to the database relations; we assume that all relations are updated by the same percentage. To model a growing database, we have twice as many inserts as deletes. In our notation, a 10 percent update to a relation consists of inserting 10% as many tuples are currently in the relation, and deleting 5% of the current tuples.

We compare the performance of our greedy algorithm (referred to as Greedy in our discussion and figures) with plain Volcano query optimization extended to choose between recomputation and incremental maintenance of views (referred to as NoGreedy). (The algorithm of \[Vis98\] falls in the same class as NoGreedy, although the optimization method is somewhat different.) For each query, we present results at different update percentages, ranging from 1% to 80%.

The cost of view maintenance is affected by the presence of indices. Normally, databases have indices on the primary key attributes of each relation, to check for uniqueness. Hence we assume that for each of the TPC-D relations, an index is present on the primary key attributes. However, we also ran our benchmark assuming that no indices are initially present, and found that all required indices got chosen for permanent materialization by our algorithm. Thus, the cost of the plans we generate were not significantly affected by the presence of indices, although the cost of plans without our optimizations rose if indices were not already present.

We assume a TPC-D database at scale factor of 0.1, that is the relations occupy a total of 100 MB. The buffer size is set at 8000 blocks, each of size 4KB, although we also ran some tests at a much smaller buffer size of 1000 blocks. The tests were run on an Ultrasparc 10, with 256 MB of memory.

### 7.2 Performance Results

Maintaining Individual Views. Figure 3 shows our results on two queries, the first consisting of the join of 4 relations, without aggregation, and the second consisting of aggregation on the same join. As can be seen from the figures significant benefits are to be had, especially at low update percentages, but there are benefits even at relatively high update percentages.

Maintaining a Set of Views. Figure 4 shows our results on two sets of queries, the first containing five queries without aggregation and the second containing five queries with aggregation. The benefit ratio due to Greedy is again excellent at lower update percentages. There is a jump in cost at one point, which is because of the use of an algorithm that depends on an input fitting in memory, and when the input does not fit in memory its cost increases sharply.

Figure 5 shows the results on a set of 10 queries, with indices already present on all primary key attributes, and without any indices present initially; all required indices got chosen for materialization.

Cost of Optimization. For a set of 10 materialized views, each a join of 3 to 4 TPC-D relations, (whose results are shown in Figure 5), the time for Greedy optimization was 31 seconds. Note however that 31 seconds is low compared to the savings of up to 1000 seconds obtained for one run of view maintenance, and besides it is a one-time cost whereas view maintenance is typically at least a daily task in a data warehouse. Thus, the extra cost for our algorithms is worthwhile.

The number of candidates for materialization grows exponentially with the number of relations in a query. We are currently working on techniques to prune the set of candidates, in order to keep optimization time in tight control even with a higher number of relations.

Temporary vs. Permanent Materialization. Out of a total of 1600 results that were materialized (totalling across many different queries and query sets that we considered, and across update percentages ranging from 1 percent to 90 percent), we found that for about 1000 the recomputation cost was less, meaning they are materialized temporarily, and for 600 the maintenance cost was less, meaning they were materialized permanently. At 1 to 5 % update rates, the ratio was 281 to 306, while at 50 to 90 % update rates, the ratio changed to 360 to 88, in favor of recomputation.

Effect of Buffer Size. With a buffer size of 1000 blocks (instead of 8000 blocks), we found that the costs of plans with and without Greedy optimization went up, but the increase was more for recomputation plans and the benefit ratio for small update percentages was actually more strongly in favor of our algorithms.

## 8 Conclusions and Future Work

The problem of finding the best way to maintain a given set of materialized views is an important practical problem, especially in data warehouses/data marts, where the maintenance windows are shrinking. We have presented solutions that exploit commonality between different tasks in view maintenance, to minimize the cost of maintenance. Our techniques are easy to implement on an existing multiquery optimizer. As shown by the results in section 7, our techniques can generate significant speedup in view maintenance cost, and the increase in cost of optimization is acceptable. We therefore believe that our results are a timely solution to an important practical problem.

Future work includes further heuristics to decrease optimization cost, and implementing extensions to efficiently handle workloads containing queries. We also plan to port the system to a dynamic query result caching environment; in a companion paper, we study the issue of selecting results to cache dynamically, in the absence of updates.


format: text

text:
# An Analysis of the Asymptotic Limit of Gluon Shadowing.

## Abstract

We examine the gluon distributions in nuclei in the asymptotic region defined by $`Q^2\mathrm{}`$, $`x0`$. An analysis using the Double Asymptotic Scaling variables of Ball and Forte is proposed. New scaling relations are predicted which can help disentangling the different mechanisms of low $`x`$ perturbative QCD evolution in nuclei.

Submitted to Physics Letters B

1. Nuclear shadowing or the depletion at low Bjorken $`x`$ of the nuclear Deep Inelastic (DI) structure function, $`F_2^A`$, with respect to the nucleon one, $`F_2^N`$, has been observed in a number of experiments ( and references therein). Assuming the universality of parton distributions in nuclei, one expects nuclear shadowing to be present in other high energy processes as well, such as Drell-Yan pair, $`J/\psi `$ and $`\mathrm{{\rm Y}}`$ production in lepton-nucleus, hadron-nucleus and nucleus-nucleus collisions ( and references therein). In particular nuclear shadowing might be concurring with the other mechanisms, among which is the quark-gluon plasma formation, that result in a depletion of the observed cross sections for these processes. Moreover, as the very low $`x`$ regime has become accessible at HERA, new phenomenological studies of high density QCD at the saturation scale predicted in  are now possible . A quantitative understanding of both the $`x`$ and $`Q^2`$ dependences of the nuclear parton distributions at low $`x`$ therefore constitutes a practical and necessary step both for interpreting the outcome of future experiments at RHIC and at the LHC and for investigating the onset of parton saturation.

Recent calculations rely on non-perturbative models for the nuclear parton distributions at a given (low) scale, $`Q_o^2`$, combined with DGLAP  perturbative evolution. They are all therefore affected by the uncertainty in the initial parton distributions and, in particular, in the gluon distribution which governs evolution at low $`x`$, and which is poorly known experimentally. A strong effect is seen by changing the value of $`Q_o^2`$ itself which can plausibly vary within the range, $`Q_o^2=0.8few\mathrm{GeV}^2`$, leading to sensibly different values for the shadowing of both the structure function and the gluon distribution at large $`Q^2`$.

Now, as $`Q^2`$ increases the (low $`x`$) gluon distribution in a proton should tend to a universal asymptotic value, corresponding to the Double Leading Logarithmic Approximation (DLLA) result of Ref.. Numerically, this value is attained at $`Q^210^3\mathrm{GeV}^2`$ provided the initial distributions grow much slower than $`x^{1/2}`$. Because of the coupling between the singlet quark and gluon distributions’ evolution, a similar behavior is predicted for the structure function, $`F_2`$ . It is therefore natural to address the question of whether the differences in the initial non perturbative nuclear shadowing will decrease with growing $`Q^2`$ and give rise to a universal asymptotic curve which is within the range of planned experiments. Our first result is a negative one: we will show that because of the form that DGLAP evolution takes in a nucleus the influence of initial conditions is carried on to the largest attainable $`Q^2`$ values.

We then examine carefully the asymptotic behavior of the shadowing ratios $`R_G=G_A/G_N`$ and $`R_F=F_2^A/F_2^N`$, in the DLLA (notations are: $`G_{N(A)}`$ and $`F_2^{N(A)}`$ for the gluon distributions and the structure function in a nucleon, $`(N)`$, and in an isoscalar nucleus, $`(A)`$, respectively). Our goal is to ascertain whether it is possible to distinguish among the different approximations the perturbation series takes in a nucleus and at very low $`x`$.

The proton structure function data analyzed recently at HERA  have been shown  to lie in the asymptotic region ($`Q^2Q_o^2=1\mathrm{GeV}^2`$ and $`xx_o=0.1`$, and to evolve according to DLLA . The key test is to prove that the data obey Double Asymtptotic Scaling (DAS) in the variables $`\rho =\gamma ((YY_o)/\xi )^{1/2}`$ and $`\sigma =\gamma ^1((YY_o)\xi )^{1/2}`$, $`\gamma =6/(332N_f)^{1/2}`$, $`Y=\mathrm{ln}1/x`$, $`\xi =\gamma ^2\mathrm{ln}(\mathrm{ln}Q^2/\mathrm{\Lambda }_{QCD}^2/\mathrm{ln}Q_o^2/\mathrm{\Lambda }_{QCD}^2`$). Violations from DAS (other than due to the fact that the data lie in a pre-asymptotic region ) would signal either the onset of contributions beyond standard pQCD evolution , including the beginning of parton saturation .

The approach to asymptotia in a nucleus can be first analyzed by assuming that evolution proceeds through DLLA equations as well. We have found that in this case the ratios $`R_F`$ and $`R_G`$ display exact scaling in $`\sigma `$, thus becoming a function of $`\rho `$ only. As in the proton case, this is a model independent result in that we obtain a scaling form, independent from the initial conditions. We then use this result as a basis for addressing the next question i.e. the detection of violations of DAS scaling in nuclei, which could possibly originate at different values of $`xx_o^A`$ and $`Q^2Q_{o,A}^2`$, than in the proton. In particular Unitarity Shadowing Corrections (USC)  are expected to affect evolution at $`x_o^A>x_o`$ because of the increase of the tranverse gluon density in a nucleus due to the overlapping of nucleons in the longitudinal direction. On a more speculative basis one might also expect the transition to the $`\mathrm{ln}(1/x)`$ resummation to appear in a different regime or, in the most “exotic” scenario, that medium modifications of the anomalous dimensions could be observed. In our approach such questions can be addressed systematically as they introduce specific scaling violations from the DLLA result, appearing as different $`\sigma `$ dependences in the ratios $`R_G`$ and $`R_F`$.

Our main observation is therefore that although it is technically predictable that for a proton target DGLAP evolution and DLLA should break down at very low values of $`x`$ and sufficiently large $`Q^2`$ and give way to $`\mathrm{ln}(1/x)`$ summation and to USC, it is still a major task to be able to pinpoint where and if the transition from the different regimes is going to take place in the kinematical regimes currently under exploration. Our goal is to obtain some new insight by using nuclear targets where the asymptotic regime can in principle be reached at larger $`x`$. As a by-product we obtain quantitative predictions in the asymptotic kinematic regime which should be attainable at RHIC and at the LHC.

2. We first summarize results for ordinary DGLAP evolution applied to the nuclear ratios at low $`x`$, assuming that the proton and the nuclear distributions evolve similarly. As it is well known evolution is driven by the gluon distribution which dominates over the sea quarks one and one can predict the behavior of the shadowing ratios, $`R_G`$ and $`R_F`$ with $`Q^2`$:

$`{\displaystyle \frac{R_G}{\mathrm{ln}Q^2}}`$ $``$ $`{\displaystyle _x^1}P_{GG}({\displaystyle \frac{x}{y}},\alpha _S(Q^2)){\displaystyle \frac{G_N(y,Q^2)}{G_N(x,Q^2)}}\left[R_G(y,Q^2)R_G(x,Q^2)\right]{\displaystyle \frac{dy}{y}}`$ (1)
$``$ $`{\displaystyle \frac{G_N/Q^2}{G_N}}\left({\displaystyle \frac{G_A(x,Q^2)/\mathrm{ln}Q^2}{G_N(x,Q^2)/\mathrm{ln}Q^2}}R_G(x,Q^2)\right),`$ (2)
$$\frac{R_F}{\mathrm{ln}Q^2}_x^1P_{qG}(\frac{x}{y},\alpha _S(Q^2))\frac{G_N(y,Q^2)}{\mathrm{\Sigma }_N(x,Q^2)}\left[R_G(y,Q^2)R_F(x,Q^2)\right]\frac{dy}{y},$$
(3)
where we have disregarded the sea quarks distribution on the r.h.s. of the coupled DGLAP evolution equations; $`P_{qG}`$ and $`P_{GG}`$ are the splitting functions evaluated at NLO; and we used the approximation $`F_2^{N(A)}5/18\mathrm{\Sigma }_{N(A)}`$, with $`\mathrm{\Sigma }=_iq_i(x,Q^2)+\overline{q}_i(x,Q^2)`$. For ease of presentation we will use the following notation: $`G_{N(A)}^{}=G_{N(A)}(x,Q^2)/\mathrm{ln}Q^2`$. Eqs.(1) and (2) show that the $`Q^2`$ dependence of the ratios $`R_G`$ and $`R_F`$ is determined by a subtle balance involving both the parton distributions and the ratios themselves . Based on Eqs.(1) and (2), and defining $`R_G(x,Q_o^2)R_G^o`$ and $`R_F(x,Q_o^2)R_F^o`$ for the initial distributions, one can make the following predictions for the $`Q^2`$ dependence of $`R_G`$ and $`R_F`$: i) $`R_G`$ grows with $`Q^2`$. In fact, if as predicted by non-perturbative shadowing models $`R_G`$ is a growing function of $`x`$, then it also grows with $`Q^2`$, the r.h.s. of Eq.(1) being positive ($`yx`$); ii) if $`R_F^o<R_G^o`$, then $`R_F`$ grows with $`Q^2`$; if $`R_F^o>R_G^o`$, then $`R_F`$ initially decreases with $`Q^2`$ until it reaches the value of $`R_G^o`$ and it subsequently starts increasing along with $`R_G`$.

Note that from the behavior of $`R_F`$ and $`R_G`$ obtained from the straighforward application of DGLAP equations, one cannot predict the approach of e.g. $`R_G`$ to a universal limiting curve at large $`Q^2`$. As a matter of fact, although the form of Eq.(1) might seem suggestive of a fixed point behavior , this is a priori not the case, since the quantity $`G_A/G_N`$ depends on $`Q^2`$. The rate of change with $`Q^2`$ is instead governed both by: (a) by the ratio, $`G_N^{}/G_N`$; (b) by the difference $`\mathrm{\Delta }_G=G_A^{}/G_N^{}R_G(x,Q^2)`$ at $`Q^2=Q_o^2`$ . Current parametrizations  feature an ultra-soft behavior of the gluon distribution at $`Q_o^21\mathrm{GeV}^2`$, i.e. $`G_N0`$ as $`x0`$, thus causing (because of (a)) a rapid evolution which strongly reduces the shadowing in both $`R_G`$ and $`R_F`$, between $`Q_o^2`$ and $`Q^212\mathrm{GeV}^2`$. If on the contrary one assumes $`Q_o^2`$ ranging from $`2`$ to $`5\mathrm{GeV}^2`$, where harder low $`x`$ initial gluons are expected, then the evolution is slower ($`G_N`$ is larger) and the nuclear ratio is basically unchanged at $`Q^210100\mathrm{GeV}^2`$. A further model dependence follows from the usage of different non-perturbative shadowing mechanisms. We examine two in particular: the Aligned Jet Model (AJM) (see  and references therein), and Initial State Recombination (ISR) . Both models explain qualitatively the initial onset of shadowing. Accurate quantitative calculations have been performed using the AJM in .

Results are summarized in Fig.1, where we show the $`Q^2`$ dependence of the ratios $`R_F(x,Q^2)`$ and $`R_G(x,Q^2)`$ in $`{}_{}{}^{40}Ca`$ at fixed $`x=10^4`$ (Fig. 1(a)) and $`x=10^2`$ (Fig. 1(b)), for both the AJM (full lines) and the ISR model (short dashes). In order to show the dependence on the initial scale $`Q_0^2`$, results are presented for both models by taking, $`Q_0^2=0.8`$ GeV2, and $`Q_0^2=5`$ GeV2 (the latter can be easily distinguished in the graph by observing the shift in the starting point of the curves). Moreover, as the main purpose of the figure is to illustrate the main features of both the nuclear models and the initial parton distributions that will lead to our description on the asymptotic behavior, we have not sought for $`R_F`$ the best agreement with the data. Details on this part are going to be given elsewhere . A remarkable feature is the sensitivity of the ISR model to this initial scale $`Q_0^2`$. It is only for $`Q_0^21`$ GeV2 that a sizeable gluon shadowing is obtained due to the fact that the amount of initial shadowing is proportional to the square of the initial gluon distributions and to $`\alpha _s(Q_0^2)/Q_0^2`$ . Results obtaind with the AJM vary less dramatically with the initial scale, $`Q_0^2`$, which in this case enters just the $`(q\overline{q})nucleon`$ (or $`(gg)nucleon`$) cross sections . Nonetheless, the initial difference is carried on to $`Q^2`$ as large as 103 GeV2. Moreover, in both cases we can observe the $`Q^2`$ behaviour outlined before: a rapid suppression of shadowing in the range of $`Q^2`$ up to 2 GeV2 and a subsequent softer evolution. The comparison between the $`Q^2`$ behaviour for different fixed $`x`$ values (Fig. 1(a) and Fig. 1(b)) shows that evolution is slower for smaller $`x`$. This can be technically understood by noting that, in the DLLA limit the logarithmic derivative of $`R_G`$ in Eq. (2) vanishes. This is why initial discrepancies between models are more likely to persist at smaller $`x`$.

In summary, the asymptotic behavior of $`R_G`$ depends on the initial conditions up to the largest values of $`Q^2`$ attainable at low $`x`$. This feature is in common with the proton gluon distributions themselves as shown e.g. in . As it is well known, neither the data nor theoretical arguments can help us defining the optimal values of $`R_G(x,Q_o^2)`$ and $`R_F(x,Q_o^2)`$.

The situation that we have described calls for some redefinition of the approach to asymptotia in deep inelastic scattering from nuclei. In the next Section we illustrate how different behaviors of the data could be revealed by extending the double asymptotic scaling analysis of Ref. to nuclei.

3. We now examine the nuclear DI structure function and gluon distribution in the asymptotic regime defined by $`x0`$, $`Q^2\mathrm{}`$. Our goal is to explore scaling relations in nuclei in order to be able to compare theory with data in a model independent way. The derivation of the equations of the DLLA in a nucleus parallels the one for the proton, namely one first writes the DGLAP evolution equation for the gluon distribution in the limit $`n1`$, $`n`$ being the variable in moments space (we have omitted the subscripts $`N(A)`$ unless necessary):

$$\frac{g(n,Q^2)}{\mathrm{ln}Q^2}=\frac{\alpha _s(Q^2)}{2\pi }\gamma _{GG}^0(n)g(n,Q^2),$$
(4)
$`\gamma _{gg}^0(n)2C_A/(n1)+\kappa `$ being the anomalous dimension in the limit $`n1`$ ($`\kappa =11/6n_f/3C_A`$ is the next-order or subleading contribution in this limit). Solutions in $`(x,Q^2)`$ are found by evaluating the anti-Mellin transform,

$$G(x,Q^2)=\frac{1}{2\pi i}_C𝑑ng(n,Q^2)\mathrm{exp}\left[Y(n1)\right],$$
(5)
with the saddle point method . In Eq.(5), $`g(n,Q^2)=g(n,Q_0^2)\mathrm{exp}\left[\xi /(n1)+\xi \kappa /2\right]`$; $`g(n,Q_0^2)=_0^1𝑑xx^{(n1)}g(x,Q_0^2)`$, $`g(x,Q_o^2)`$ being the initial gluon distribution, and $`G(x,Q^2)=xg(x,Q^2)`$; $`Y=\mathrm{ln}(1/x)`$, and $`\xi =\gamma ^2\mathrm{ln}(\mathrm{ln}(Q^2/\mathrm{\Lambda }^2)/(\mathrm{ln}Q_o^2/\mathrm{\Lambda }^2))`$, $`\gamma ^2=C_A/(\pi b)`$, $`b=(332N_f)/12\pi `$. We rewrite the integrand in Eq.(5) as:

$$\stackrel{~}{g}(n,Q^2)=g(n,Q_o^2)\mathrm{exp}\xi \kappa /2\mathrm{exp}[Yf_1(n)+\xi f_2(n)],$$
(6)
where $`f_1(n)=n1`$, $`f_2(n)=(n1)^1`$ and $`Y`$ and $`\xi `$ are both similarly large. If one takes “soft” initial conditions such as, $`G(x,Q_0^2)A_Nx^\lambda `$, $`\lambda 0`$, then $`g(n,Q_0^2)A_N/(n(\lambda +1))`$ has a pole to the left of the saddle point which is found by setting $`[Yf_1(n)+\xi f_2(n)]/n=0`$. The integral in Eq.(5) is then approximated by:

$`G(x,Q^2)`$ $`=`$ $`\sqrt{2\pi }\left({\displaystyle \frac{\stackrel{~}{g}(n_o,Q_o^2)}{\stackrel{~}{g}^{\prime \prime }(n_o,Q_o^2)}}\right)^{1/2}\stackrel{~}{g}(n_o,Q^2)=`$ (7)
$`=`$ $`\sqrt{2\pi }g(n_o,Q_o^2)\mathrm{exp}(\xi \kappa /2){\displaystyle \frac{\mathrm{exp}[Yf_1(n_o)+\xi f_2(n_o)]}{\left|Yf_1^{\prime \prime }(n_o)+\xi f_2^{\prime \prime }(n_o)\right|^{1/2}}}`$ (8)
where $`n_0=1+\sqrt{\xi /\mathrm{\Delta }Y}`$, $`\mathrm{\Delta }Y=YY_o`$, $`Y_o=\mathrm{ln}(1/x_o)`$, $`x_o0.1`$, is the saddle point and $`f_{1(2)}^{\prime \prime }(n_o)=^2f_{1(2)}(n)/n^2|_{n=n_o}`$.

By introducing the variables, $`\rho =\gamma ((YY_o)/\xi )^{1/2}`$ and $`\sigma =\gamma ^1((YY_o)\xi )^{1/2}`$,  one has:

$$n_on_o(\rho )=1+\gamma /\rho ,$$
(9)
and,

$$GG^{DAS}(\rho ,\sigma )=\sqrt{\pi }f_G(\rho /\gamma )\left(\frac{\gamma }{\rho }\right)\frac{\mathrm{exp}\left[2\gamma \sigma \gamma ^2\kappa /2\right]}{\sqrt{\sigma \gamma }},$$
(10)
where $`f_G(\rho /\gamma )`$ is a smooth function describing the initial conditions.

DAS is the prediction that, in the hypothesis of soft initial conditions, and in the asymptotic limit defined by $`\sigma \mathrm{}`$ and $`\rho O(1)`$, $`\mathrm{ln}(G^{DAS}/f_G(\rho ,\sigma ))`$ becomes a linear function of $`\sigma `$, independent of the value of $`\rho `$, with slope fixed by the known constant, $`\gamma `$.

A similar behavior is found for $`F_2^p`$  and can therefore be compared to the available data . The structure function’s asymptotic behavior is in fact obtained by solving the equation ***We refer here to the singlet part of the structure function:

$$\frac{F_2^p(x,Q^2)}{\mathrm{ln}Q^2}=\frac{5}{18}\frac{\alpha _S}{\pi }G(x,Q^2),$$
(11)
yielding:

$$F_2^p(\rho ,\sigma )=f_\mathrm{\Sigma }(\rho ,\sigma )\mathrm{exp}(2\gamma \sigma ),$$
(12)
where $`f_\mathrm{\Sigma }`$ was derived by using the LO expression for $`\alpha _s`$ and, as for the gluons, it depends on the initial conditions. The scaling of $`F_2^p`$ can be seen from Fig.2 (top-right). From Fig.2 one can also see that the data from NMC (triangles) , corresponding to larger $`x`$ with respect to the 1995 HERA ones (open squares) , as well as some of the more recent HERA data with very low $`x`$ and $`Q^2`$ (open dots) , violate scaling (for a better reading compare with top-left). These scaling violations have been interpreted as due to the fact that the kinematics is not yet asymptotic, as it can be easily seen from the fact that the data lie well below $`\sigma 1`$.

Deviations from DAS can be predicted also in the case of hard initial conditions i.e. when $`g(n_0,Q_0^2)A_N/(n(\lambda +1))`$ with $`\lambda 0.2`$. Intuitively this corresponds to taking the limit $`Y\xi `$ in Eq.(5), thus defining the new saddle point: $`n_o=(1+\lambda )+1/\mathrm{\Delta }Y`$. The corresponding gluon distribution is then

$`G(x,Q^2)`$ $`=`$ $`f_G^h\mathrm{exp}\left[\lambda (YY_o)+\xi /\lambda +\xi \kappa /2\right]`$ (13)
$`=`$ $`f_G^h\mathrm{exp}\left[\lambda \sigma \rho +(\gamma ^2/\lambda +\kappa /2)\xi \right]`$ (14)
with $`f_G^h(\rho ,\sigma )=\sqrt{2\pi \rho \sigma }A_N`$ (see also ). This behavior supports the presence of USC appearing as a non-linear term in the evolution equation , which has the effect of damping the steep rise of the gluon distribution at small $`x`$. An alternative possible explanation of DAS violations in the recent HERA data  which accounts also for the peculiar stooping of the logarithmic slope of the proton structure function, $`F_2/\mathrm{ln}Q^2`$, at low $`x`$ and $`Q^2`$, is that indeed USC  need to be taken into account.

We now study these two different scenarios for the asymptotic behavior in nuclei, where it is well known that some aspects of perturbative evolution such as USC, are expected (simply based on geometrical arguments) to arise at larger values of $`x`$. In Fig.2 we present the world low $`x`$ data on the nuclear ratios, Eq.(2) as a function of the DAS variable, $`\sigma `$ (bottom-right), and we compare both data and their kinematics (bottom-left) with the proton ones (top). We use in both cases the following values of $`Q_o^2`$, $`\mathrm{\Lambda }_{QCD}`$, $`\rho `$ and $`\sigma `$: $`Q_o^2=1\mathrm{GeV}^2`$, $`\mathrm{\Lambda }_{QCD}=185`$ MeV (LO). In the NLO analysis performed in  it was found that: $`Q_o^2=1.8\mathrm{GeV}^2`$, $`\mathrm{\Lambda }_{QCD}=200`$ MeV (NLO), $`\rho 1`$ and $`\sigma 1.2`$. From the figure it appears that the existing nuclear data are scarse and do not presently support a DAS type analysis and, moreover, they seem to lie mainly in a pre-asymptotic region. Experiments at RHIC and LHC are however expected to be able to cover the asymptotic region. Although experimental extractions of the logarithmic slopes in nuclei have been performed in , very little can be concluded from these data as well .

We evaluate the ratios $`R_G`$ and $`R_F`$, Eq.(2) in DAS, i.e. within the hypotheses: i) the quark and gluon distributions are initially shadowed due to some non-perturbative mechanism; ii) the pQCD evolution mechanism is not affected by the nuclear medium; iii) the initial distributions are soft. The DLLA predictions are:

$$R_G(x,Q^2)=\left[\frac{\stackrel{~}{g}_A(n_o,Q^2)}{\stackrel{~}{g}_N(n_o,Q^2)}\right]^{3/2}[\frac{\stackrel{~}{g}_N^{\prime \prime }(n_o,Q^2)}{\stackrel{~}{g}_A^{\prime \prime }(n_o,Q^2)}]^{1/2},$$
(15)
where $`n_o`$ is the saddle point defined by Eq.(9) for both the proton and the nucleus We rewrite Eq.(15) as a function of the DAS variables by using Eq.(10):

$$R_G^{DAS}=\frac{f_G^A(\rho /\gamma )}{f_G^N(\rho /\gamma )}$$
(16)
i.e. the exponential terms appearing in $`G^{DAS}(\rho ,\sigma )`$, Eq.(10), are the same in a nucleus and in a single nucleon respectively, thus canceling the $`\sigma `$ dependence in the ratio $`R_G`$: $`R_G`$ is predicted to scale exactly in $`\sigma `$ to a smooth function of $`\rho `$ that is determined entirely by the (soft) initial conditions.

The onset of a different evolution mechanism in the nucleus will appear as a $`\sigma `$-scaling violation modifying the exponential behavior of Eqs.(10)-(15) with respect to the single nucleon case. Since the low $`x`$ behavior of recent HERA data seem to show evidence for rather large screening corrections, and at the same time they do not rule out the hard pomeron contribution, we consider the effect of: (A) USC combined with soft initial conditions; (B) USC combined with hard initial conditions; (C) Hard initial conditions in both nucleon and nucleus, no USC.

The effect of USC is taken into account through a “damping factor”, $`D_G(x,Q^2)1`$, (Ref. and references therein), evaluated using Mueller-Glauber’s eikonal approximation . We extended the calculation to nuclei by assuming that two gluons inside a nucleus are correlated by a larger confinement radius, $`R_Ar_0A^{1/3}`$, than in a nucleon, corresponding to a smeared impact parameter space two-gluon form factor (details of this calculation will be included in ). As a result the effect USC is enhanced in a nucleus with respect to a nucleon target, due to the larger transverse gluon density at similar values of $`x`$.

The asymptotic gluon distribution function is written in terms of the damping factor as:

$$G_{N(A)}^{SC}(\rho ,\sigma )=D_G^{N(A)}\times G^{DAS}(\rho ,\sigma ).$$
(17)
By using Eq.(17) We can now calculate the ratio $`R_G`$, for the cases listed above. We obtain:

$`R_G^{(A)}(\rho ,\sigma )`$ $`=`$ $`R_G^{DAS}(\rho )\times {\displaystyle \frac{\mathrm{exp}\left[2\gamma (\sigma \sigma _A)\frac{\gamma ^2\kappa }{2}\frac{\sigma }{\rho }\right]}{\mathrm{exp}\left[2\gamma (\sigma \sigma _N)\frac{\gamma ^2\kappa }{2}\frac{\sigma }{\rho }\right]}}`$ (19)
$``$ $`R_G^{DAS}(\rho )\times \mathrm{exp}\left[(\sigma _A\sigma _N)\right].`$ (20)
$`R_G^{(B)}(\rho ,\sigma )`$ $`=`$ $`{\displaystyle \frac{f_G^{h,A}}{f_G^{h,N}}}\times {\displaystyle \frac{\mathrm{exp}\left[\lambda _A\sigma \rho +\frac{\gamma ^2}{\lambda _A}\frac{\sigma }{\rho }\sigma _A\right]}{\mathrm{exp}\left[\lambda _N\sigma \rho +\frac{\gamma ^2}{\lambda _N}\frac{\sigma }{\rho }\sigma _N\right]}}`$ (21)
$``$ $`C\mathrm{exp}\left[(\lambda _A\lambda _N)\sigma \rho +\gamma ^2({\displaystyle \frac{1}{\lambda _A}}{\displaystyle \frac{1}{\lambda _N}}){\displaystyle \frac{\sigma }{\rho }}\right]\times \mathrm{exp}\left[(\sigma _A\sigma _N)\right].`$ (22)
$`R_G^{(C)}(\rho ,\sigma )`$ $`=`$ $`C\mathrm{exp}\left[(\lambda _A\lambda _N)\sigma \rho +\gamma ^2({\displaystyle \frac{1}{\lambda _A}}{\displaystyle \frac{1}{\lambda _N}}){\displaystyle \frac{\sigma }{\rho }}\right].`$ (23)
Here $`R_G^{DAS}`$ is the same as in Eq.(16); $`\sigma _{N(A)}(\rho ,\sigma )=1/2\gamma \mathrm{ln}(1/D_G)`$; and the shadowing for the initial hard distributions has been parametrized as $`R_G^{(o)}=f_G^{h,A}/f_G^{h,N}=Cx^\alpha `$, with $`C1.3`$ and $`\alpha 0.080.1`$. Moreover, we have chosen $`Q_o^2=1\mathrm{GeV}^2`$ for both soft and hard initial conditions and $`\lambda _N=0.35`$. Our scaling result, Eq.(16), and the scaling violating ones, Eqs.(15a)-(15c), are shown in Fig.3 for two different values of $`\rho `$: $`\rho =1.8`$ well inside the asymptotic region shown in Fig.2, and $`\rho =3.4`$ corresponding to very low $`x`$ and almost fixed $`Q^2`$ where we expect standard DGLAP to break down.

A few comments are in order. Starting from soft initial conditions one obtains either the $`\sigma `$-scaling curves (full lines) or the $`\sigma `$-scaling violation, Eq.(15a), induced by USC (dashed lines). These corrections are driven by the damping factor given for each value of $`\rho `$ by the dashed curves below. The decreasing trend with growing $`\sigma `$ is larger at large $`\rho `$ because of the correspondingly decreasing values of $`x`$ at similar values of $`Q^2`$. On the other side, hard initial conditions, Eq.(14) and dot-dashed curves in Fig.3, show sensible deviations from $`\sigma `$-scaling at large $`\rho `$ where the $`\mathrm{ln}(1/x)`$ term dominates over the $`\mathrm{ln}Q^2`$ one. This effect is enhanced by USC (dotted curves). An interesting observation is the change in slope of the scaling violations both when passing from soft to hard initial conditions at low $`\rho `$, and when passing from low $`\rho `$ to large $`\rho `$. These and similar other regularities could be studied systematically both for the gluon and the structure function ratios once a much larger set of data will be available.

Most importantly, with the approach proposed here we eliminate the ambiguities in the determination of the value of gluons and quarks nuclear shadowing illustrated in Fig.1, in that we identify scaling relations that must be verified independently from the initial non-perturbative nuclear shadowing.

In conclusion, by applying DAS to nuclei we have shown model independent predictions, i.e. scaling in the variable $`\rho `$ for the ratios of the nuclear gluon distributions to the free nucleon ones in the asymptotic region. Similar relations hold for the nuclear structure functions. We have considered a few possible sources of scaling violations due to the onset of USC and to the domination of a hard pomeron. As a result, by studying the $`A`$-dependence of shadowing we find some new constraints on perturbative evolution at low $`x`$. Our calculations are relevant for the regime accessible at future experiments at RHIC, LHC and at the $`eA`$ project at DESY .