View Selection and Materialization - Data Warehousing Design and Advanced Engineering Applications - page 119

Figure 1. Tables of TPC-H benchmark

O.orderkey AND O.custkey = C.custkey AND
C.nationkey = N.nationkeyGroup by N.name
P.brand, O.orderdate;
TheAND-OR DAG representation of the query
graph of query Q 1 is shown in Figure 2 (b). Circles
represent AND nodes, i.e., operations and boxes
represent OR nodes, i.e. equivalence nodes. In the
transition from Figure 2 (a) to Figure 2 (b), new
nodes are created to represent the equivalence
nodes (e.g., node labeledA1 12 represents the result
of the aggregation operation).

In this work, The MVMG is built incremen-
tally because the view selection algorithm is ap-
plied as a query arrives. Indeed, the query tree is
integrated into the MVMG. We borrow the rule
provided in (Roy, 2002) for identifying common
subexpressions. For example, equivalent nodes,
obtained after applying join associativity property,
are replaced by a single equivalence node.
We consider metadata like frequency at each
node of the graph (i.e., at the operation and view
nodes).

Figure 2. Query graph of Q (a) A possible query graph of Q 1 (b) AND-OR DAG of Q 1