Database Reference
In-Depth Information
Figure 7. Computing distributive functions
Our objective is to update aggregate values
without computing them again from all data.
Some classical computing technics (Palpanas,
Sidle, Cochrane & Pirahesh, 2002; Chou & Zhang,
2004) are used below.
Let
w
be a DW obtained from one or more data
sources (DB
s
with s ∈ [1..b]) and let Δ
T
be a se-
quence of updates from one or several sources.
By applying the ConstrView() algorithm on Δ
T
,
we obtain
w'
such that
w'
=
ConstrView
(Δ
T
). We
note that
w
and
w'
have the same logical schema.
Let
w
t
(respectively
w'
t
) be a version (respectively
an update) of the DW at the instant t. Maintaining
data of a DW consists in computing a new DW
version:
w
t
=
w
t−
1
∪
w'
t
.
Let us consider now that a materialized view
v
, defined on the DW
w
, is the result of comput-
ing aggregate functions with
v
=
f
(
w
). We can
then calculate
v'
, defined on
w'
, with the same
manner:
v'
=
f
(
w'
).
Let us consider that:
W
=
{w
i
, i≥
1
}
the set of DWs
and
V
=
{v
i
, i≥
1
}
the set of all MV computed on
W.
V
A
⊂
V
the set of all special materialized views
called auxiliary MV.f
f
an aggregate function defined
as follow:
f
:
W→ V
;
f
(
w
t
) =
v
t
Since
w
t
=
w
t−
1
∪
w'
t
; we can then write
f
(
w
t
) =
f
(
w
t−
1
∪
w'
t
) =
v
t
According to the definitions given above, one
can find that:
•
for a
distributive
function
f
, a function
h
:
V × V → V
;
h
(
v
t−
1
,
v '
t
) =
v
t
such that
f
(
w
t−
1
∪
w'
t
)=
h
(
f
(
w
t−
1
),
f
(
w'
t
))We have then
f
(
w
t
) =
f
(
w
t−
1
∪
w'
t
) =
h
(
f
(
w
t−
1
),
f
(
w'
t
)) =
h
(
v
t−
1
,
v'
t
) =
v
t
•
for an
algebraic
function
f
, an aggregate
function
g
and a function
h
A
such as:
g
:
W → V
;
g
(
w
t
) =
v
t
A
h
A
:
V
A
× V
A
→ V
with
h
(
v
t-
1
A
,
v'
t
A
) =
v
t
f
(
w
t−
1
∪
w'
t
) =
h
A
(
g
(
w
t−
1
),
g
(
w'
t
))
We have then
f
(
w
t
) =
f
(
w
t−
1
∪
w'
t
) =
h
A
(
g
(
w
t−
1
),
g
(
w'
t
))=
h
(
v
t−
1
A
, v'
t
A
) =
v
t
Let us apply the above results to the most
frequently used functions into practice (such as
count, sum, max, min, variance, stddev).
The next two figures (Figure 7 and Figure 8)
summarize the used technique to maintain incre-
mentally aggregate functions.
Let
E
i
be a set of discrete elements such that:
E
i
=
{x
i1
, x
i
2
,
x
i
3
,
..., x
ip
}
with
|E
i
|
=
Count
(
E
i
) and
Avg
(
E
i
) the arithmetic average.
E
= ∪
i
=1
n
(
E
i
) is a set with ∩
i
=1
n
(
E
i
)= ∅ and
|E|
=∑
i
=1
n
(count(
E
i
))
And
v
t
.a
f
the aggregate value of the function
f
computed on
w
t
and stored in the view
v
at the
Search WWH ::
Custom Search