Database Reference
In-Depth Information
Uncertain data model
Data type Structure of data Data dependency
Probabilistic database model
Static
No structure
Independent
Uncertain object model
Static
No Structure
Independent
Uncertain stream model
Dynamic
No structure
Independent
Probabilistic linkage model
Static
Tree structure
Dependent
Uncertain road network model
Static
Graph structure
Dependent
(a) Uncertain data models adopted in this topic.
Problem
Ranking query types
Model
Granularity Ranking scope Ranking criteria
Typicality
Instance
Single
Probability
Uncertain
queries
object
data model
Probabilistic
Instance/
Multiple
Score &
Probabilistic
ranking queries
object
objects
probability
database model
Top-
k
stream
Object
Multiple
Score &
Uncertain
monitoring
objects
probability
stream model
Linkage
Instance/
Multiple
Score &
Probabilistic
ranking queries
object
objects
probability
linkage model
Probabilistic
Object set
Multiple
Score &
Uncertain road
path queries
objects
probability
network model
(b) Ranking queries addressed in this topic.
Table 2.5
Uncertain data models and ranking queries discussed in this topic.
volve uncertain data with evolving distributions, such as traffic monitoring and
environmental surveillance.
•
The
probabilistic linkage model
introduces dependencies among different uncer-
tain objects. It contains two object sets
O
A
and
O
B
and a set of linkages
L
. Each
linkage matches one object in
O
B
with a confidence
value indicating the how likely the two objects refer to the same real-life entity.
Two objects from different object sets may share one instance. The probabilistic
linkage model finds important applications in data integration.
O
A
with another object in
•
The
uncertain road network model
considers a set of uncertain objects in a sim-
ple graph. The weight of each edge in a simple graph is an uncertain object
represented by a set of instances. The weights of adjacent edges may involve
dependencies. A probabilistic path query finds the optimal paths between two
end vertices that have small weights with high confidence. The uncertain road
network model is important in applications like real-time trip planning.
Figure 2.7 and Table 2.5(a) summarize the five uncertain data models and their
relationship.
Last, we formulated five ranking problems on uncertain data (listed in Ta-
ble 2.5(b)) and discussed the semantics as well as the potential challenges in query
evaluation. Chapters 4 to 8 will discuss the query answering techniques for the pro-
posed ranking problems.
