Database Reference
In-Depth Information
Chapter 3
Related Work
In this chapter, we review the existing studies related to ranking queries on uncertain
data. First, we introduce the state-of-the-art studies on uncertain data modeling and
processing as well as database ranking queries. Then, we discuss the related work
on each of the proposed problems in this topic.
3.1 Uncertain Data Processing
Modeling and querying uncertain data has been a fast growing research direc-
tion [39, 13, 40, 7] and receives increasing attention. In this section, we review
the studies realted to uncertain data modeling and query processing.
3.1.1 Uncertain Data Models and Systems
Various models for uncertain and probabilistic data have been developed in litera-
ture. The working model for uncertain data proposed in [7] describes the existence
probability of a tuple in an uncertain data set and the constraints (i.e., exclusive-
ness) on the uncertain tuples. One extensively used model described in [7] is the
probabilistic database model discussed in Section 2.1.2. A probabilistic database
comprises of multiple probabilistic tables. A probabilistic table contains a set of tu-
ples, where each tuple is associated with a membership probability. A probabilistic
table may also come with some generation rules to capture the dependencies among
tuples, where a generation rule specifies a set of exclusive tuples, and each tuple is
involved in at most one generation rule.
Another popularly used model is the uncertain object model [18, 19, 20, 21] dis-
cussed in Section 2.1. An uncertain object is conceptually described by a probability
density function in the data space. In a scenario where the probability density func-
33
