Database Reference
In-Depth Information
C 1
v 1
v 1
v 1
C 1
C 1
C 1
v 2
v
v
v
3
3
3
C 2
v 4
v 4
v 4
v 4
C 2
C 2
C 2
v 5
v
v 5
v 5
6
v 7
C 3
C 3
C 3
v 6,7
v 6,7
v 6,7
C 3
(a) PME-graph.
(b) Preprocessing.
(c) Case 1.
(d) Case 2.
Fig. 7.5 A chain of cliques.
Due to the dependencies among tuples, the query answering techniques devel-
oped in Chapter 5 cannot be directly applied to answering probabilistic threshold
top- k queries on the probabilistic linkage model. There are four major differences,
as discussed in Sections 7.3.1 to 7.3.4, respectively.
7.3.1 Predicate Processing
To answer a top- k selection query Q P , f , the first step is to deal with the query predi-
cate P . The predicate processing technique used for probabilistic linkages is differ-
ent from the technique used for independent uncertain objects.
As discussed in Section 5.1, given an uncertain table T and a top- k selection
query Q P , f , we can apply the query predicate P as preprocessing. That is, we select
all tuples satisfying the query predicate as P
. The
problem of answering the PT- k query on T can be transformed into finding the
tuples in P
(
T
)= {
t
|
t
T
P
(
t
)=
true
}
whose top- k probability values pass the probability threshold.
The same preprocessing does not work on the probabilistic linkage model due to
dependencies, as illustrated in the following example.
(
T
)
Example 7.3 (Processing query predicates). Consider the linkages in Figure 7.2.
Suppose a predicate P selects linkages
.l 2 and l 5 do not satisfy the
predicate P. We use a PME-graph to represent the linkages and use the shaded
nodes to represent the linkages satisfying predicate P, as shown in Figure 7.5(a). If
we adopt the same preprocessing method described in Section 5.1, then, we should
remove vertices v 2 and v 5 that do not satisfy P.
However, by removing vertex v 5 , the vertices in C 3 and those in C 2 become dis-
connected, which means that they are independent. Then, the dependencies among
vertices are not preserved.
At the same time, removing v 2 does not change the dependencies among vertices,
and thus, does not affect the answers to the query.
{
l 1 ,
l 3 ,
l 4 ,
l 6 ,
l 7 }
Search WWH ::




Custom Search