Database Reference

In-Depth Information

conjunct for which
J
1
≡

and relax this predicate as follows: we keep each

(

i

,

j

)

J
2
and discard (i.e., relax) the remaining ones. We then obtain
J
k

∈
J
1
∩
J
2
J
k

as the set of join predicates in the merged view. This predicate can be more

general than the original
J
1
∨

J
2
, but the view-matching procedure would

match
V
m
with respect to the join subsumption test in this case. We use

the same idea for
Z
1
∨

Z
2
, and therefore the residual predicate for
V
m
is

Z
k

Z
2
Z
k
.

It turns out that we can do better for range predicates
R
1
∨

∈

Z
1
∩

R
2
due to

their specific structure. Using the same argument, we first rewrite
R
1
∨

R
2

as
i
,
j
(

, where each
R
i
1
and
R
2
are disjunctions of open or closed

intervals over some column. As before, if
R
i
1
and
R
2
are defined over different

columns, we discard that conjunct. However, if they are defined over the same

column, we keep the predicate even when
R
i
1
and
R
2
are not the same, by

taking the union of the corresponding intervals (we denote this operation

R
2
)

R
i
1
∨

with the symbol
). To avoid missing some predicates, we first add conjuncts

−∞
<

to one of the range predicates if column
x
is present only

in the other range predicate (it does not change the semantics of the input

predicates but further restricts the result). If, after calculating the union of

ranges, the predicate over some column
x
becomes
−∞
<

x

<
∞

x

<
∞
, we discard

this conjunct from the result. As an example, consider:

R
1
=

(

10

≤

a

≤

20

∨

30

≤

a

≤

40

)
∧

20

≤

b

≤

30

∧

c

≤

40

R
2
=

15

≤

a

≤

35

∧

10

≤

b

≤

25

∧

c

≥

30

∧

10

≤

d

≤

20

R
1
R
2
=

10

≤

a

≤

40

∧

10

≤

b

≤

30

∧

10

≤

d

≤

20

After obtaining join, range, and residual predicates as described already,

we assemble the set of columns in the merged view. At a minimum, this set

must contain the union of columns present in both input views. However, this

is not enough in general, as shown next:

V
1
= SELECT a

V
2
= SELECT b

FROM R

FROM R

WHERE 10<c<20

WHERE 15<c<30

The candidate merged view
V
=
SELECT a,b FROM R WHERE 10<c<30
does

not satisfy property 1 because
V
1
and
V
2
cannot be obtained from
V
. The

reason is that we need to apply additional predicates to
V
(
c<20
to obtain
V
1

and
15<c
to obtain
V
2
), but
V
does not expose column
c
. For that reason, we

need to add to the set of columns in the merged view all the columns that are

used in join, range, and residual predicates that are eliminated in the merged

view. Similarly, if some range predicate changed from the input to the merged

view, we need to add the range column as an output column, or otherwise

we would not be able to reconstruct the original views. To summarize, the

Search WWH ::

Custom Search