Database Reference
In-Depth Information
Name Age
Larry Stonebraker 35
Richard Ramos 45
Catherine Spicer 46
Bruce Mourer 47
Jason Haddad 51
Angelina Amin 53
Jo Avery 53
Nicola Stewart 54
Alvin Wood 54
Gerald McMullen 55
Table 7.1
The top-10 youngest patients in the cancer registry.
7.6.3 Min and Max Queries
A
min
query
Q
min
is a special top-
k
query with
k
=
1. For a vertex
v
i
whose value in
attribute
is
x
i
. The
min
probability of
x
i
is the probability that
v
i
is ranked at the
first place in possible worlds. Therefore, the query answering techniques discussed
in Sections 7.3 and 7.4 can be directly applied to answering
min
queries. The only
difference is that we want to derive the histogram answers to a
min
query.
The
min
probability of
x
i
=
A
v
i
.A
can be bounded as
Pr
(
Q
(
G
)=
x
i
)
≤
∏
G
j
Pr
(
∧
v
∈
G
j
∩
S
i
−
1
¬
v
)
(7.12)
G
j
⊆
G
,
v
i
∈
where
G
j
⊆
G
and
G
j
∩
S
i
−
1
=
0.
Let
π(
x
i
)=
∏
G
j
⊆
G
,
v
i
∈
G
j
Pr
(
∧
v
∈
G
i
∩
S
i
−
1
¬
v
)
, we can derive the following pruning
rule.
Theorem 7.9 (Pruning rule).
Given a PME-graph G, a
query Q on attribute
min
A
, a bucket width parameter
η
, and a minimum probability threshold
τ
, let S be the
ranked list of linkages on attribute
A
and x
i
=
v
i
.A
be the value of the i-th vertex
x
i
)
<
η
in S, if
π(
, then for any interval tuple
(φ
j
,
p
j
)
where
φ
j
=[
v
min
+(
j
−
1
)
·
η
,
.
Proof.
The theorem follows with Equation 7.12 directly.
v
min
+
j
·
η ]
and v
min
+(
j
−
1
)
·
η
≤
x
i
,p
j
<
τ
Theorem 7.9 states that, for a tuple interval
φ
j
, once the smallest value in the
φ
j
is smaller or equal to
x
i
, its
min
probability is smaller than
η
interval
. Thus, the
interval tuple is not output.
To compute the answer distribution of a maximum query
Q
max
, we can apply
the same methods as for processing the minimum query. The only difference is,
the linkages are ranked in the descending order of their values in attribute
A
. The
details are omitted for the interest of space.
The complexity of computing the probability of
x
i
being the minimal value is
n
2
O
(
)
where
n
is the number of cliques in the PME-graph.
