Databases Reference
In-Depth Information
CHAPTER
2
Models of Uncertainty
Uncertainty is the refuge of hope.
- Henri Frederic Amiel
The AI literature offers a rich body of work on modeling uncertainty, including, among
others, studies on
lower and upper probabilities
,
Dempster-Shafer belief functions
,
possibility measures
(see [
Halpern
,
2003
]), and
fuzzy sets
and
fuzzy logic
[
Zadeh
,
1965
]. As an introduction to the
modeling and handling of uncertainty in schema matching, we first present two common mecha-
nisms for uncertainty management, namely probability theory and fuzzy set theory. According to
Magnani and Montesi
[
2010
], the former is representative of quantitative approaches in schema
matching (
e.g.
,[
Cheng et al.
,
2010
,
Dong et al.
,
2007
,
Gal et al.
,
2009
]) and the latter of qualitative
approaches (
e.g.
,[
Gal et al.
,
2005a
]). Other approaches for modeling uncertainty in schema matching
include interval probabilities [
Magnani et al.
,
2005
], probabilistic datalog [
Nottelmann and Straccia
,
2005
], possibilistic logic, and information loss estimation [
Mena et al.
,
2000
].
This chapter can be skipped if the reader is familiar with the basics of probability and fuzzy
set theories. Also, it can be skipped at first reading, to be used as reference whenever the relevant
theories are used in the text.
2.1
PROBABILITY THEORY
The most well-known and widely used framework for quantitative representation and reasoning
about uncertainty is probability theory (see,
e.g.
,[
Ross
,
1997
]). An intuitively appealing way to
define a probability space involves possible world semantics [
Green and Tannen
,
2006
]. Using such
a definition, a probability space is a triple
pred
=
(W,F,μ)
such that:
W
is a set of possible worlds, with each possible world corresponding to a specific set of event
occurrences that is considered possible. A typical assumption is that the real world is one of
the possible worlds.
2
|
W
|
is a
σ
-algebra over
W
.
σ
-algebra, in general, and in particular
F
, is a nonempty
collection of sets of possible worlds that is closed under complementation and countable
unions. These properties of
σ
-algebra enable the definition of a probability space over
F
.
F
⊆
μ
:
F
→[
0
,
1
]
is a probability measure over
F
.
