Database Reference
In-Depth Information
Notation
Description
O
=
{
o
1
,···,
o
m
}
an uncertain object contains
m
instances
O
a set of uncertain objects
a table with
n
tuples
R
:
t
r
1
⊕···⊕
t
r
m
a generation rule specifying the exclusiveness among
t
r
1
,···,
t
r
m
R
T
=
{
t
1
,···,
t
n
}
a set of generation rules
W
a possible world
W
a set of possible worlds
O
=
o
1
,
o
2
,···
an uncertain data stream
W
t
a set of uncertain data streams in sliding window
W
t
ω
ω
(
O
)
L
(
t
A
,
t
B
)
a probabilistic linkage between tuples
t
A
and
t
B
a simple graph with probabilistic weights
W
Table 2.1
Summary of definitions and frequently used notations.
G
(
V
,
E
,
W
)
Definition 2.1 (Uncertain object).
An
uncertain object
is a set of instances
O
=
{
o
1
,···,
o
m
}
such that each instance
o
i
(
1
≤
i
≤
m
)
takes a
membership probability
i
Pr
(
o
i
)
>
0, and
1
Pr
(
o
i
)=
1.
∑
=
,isthe
number of instances contained in
O
. We denote the set of all uncertain objects as
The
cardinality
of an uncertain object
O
=
{
o
1
,···,
o
m
}
, denoted by
|
O
|
O
.
2.1.1.1 Possible Worlds Semantics
In the basic uncertain object model, we assume that the distributions of uncertain
objects are independent from each other. Correlations among uncertain objects are
discussed in Section 2.3.2. The uncertain objects carry the possible worlds seman-
tics.
Definition 2.2 (Possible worlds of uncertain objects).
Let
O
=
{
O
1
,···,
O
n
}
be
a set of uncertain objects. A
possible world
W
is a set of
instances such that one instance is taken from each uncertain object. The
existence
probability
of
W
is
Pr
=
{
o
1
,···,
o
n
}
(
o
i
∈
O
i
)
n
i
=
1
Pr
(
o
i
)
.
(
)=
W
Let
W
denote the set of all possible worlds, we have the following property.
Corollary 2.1 (Number of possible worlds).
For a set of uncertain objects
O
=
{
O
1
,...,
O
n
}
, let
|
O
i
|
be the cardinality of object O
i
(
1
≤
i
≤
n
)
, the number of all
possible worlds is
n
i
=
1
|
O
i
|.
|W |
=
Moreover,
(
W
)=
w
∈W
Pr
Pr
(
w
)=
1
