Abstract. In this paper, we propose a new probabilistic relational database model, denoted by
PRDB, as an extension of the classical relational database model where the uncertainty of relational
attribute values and tuples are respectively represented by finite sets and probability intervals. A
probabilistic interpretation of binary relations on finite sets is proposed for the computation of their
probability measures. The combination strategies on probability intervals are employed to combine
attribute values and compute uncertain membership degrees of tuples in a relation. The fundamental
concepts of the classical relational database model are extended and generalized for PRDB. Then, the
probabilistic relational algebraic operations are formally defined accordingly in PRDB. In addition,
a set of the properties of the algebraic operations in this new model also are formulated and proven

18 trang |

Chia sẻ: thanhle95 | Lượt xem: 378 | Lượt tải: 1
Bạn đang xem nội dung tài liệu **Extending relational database model for uncertain information**, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên

Journal of Computer Science and Cybernetics, V.35, N.4 (2019), 355–372
DOI 10.15625/1813-9663/35/4/13907
EXTENDING RELATIONAL DATABASE MODEL FOR
UNCERTAIN INFORMATION
NGUYEN HOA
Department of Information Technology, Saigon University
Faculty of Information Technology, Industrial University of Ho Chi Minh City
nguyenhoa@sgu.edu.vn
Abstract. In this paper, we propose a new probabilistic relational database model, denoted by
PRDB, as an extension of the classical relational database model where the uncertainty of relational
attribute values and tuples are respectively represented by finite sets and probability intervals. A
probabilistic interpretation of binary relations on finite sets is proposed for the computation of their
probability measures. The combination strategies on probability intervals are employed to combine
attribute values and compute uncertain membership degrees of tuples in a relation. The fundamental
concepts of the classical relational database model are extended and generalized for PRDB. Then, the
probabilistic relational algebraic operations are formally defined accordingly in PRDB. In addition,
a set of the properties of the algebraic operations in this new model also are formulated and proven.
Keywords. Probability Interval; Probabilistic Combination Strategy; Probabilistic Relation; Pro-
babilistic Functional Dependency; Probabilistic Relational Algebraic Operation.
1. INTRODUCTION
Although the classical relational database model [3, 4], denoted by CRDB, is very useful
for modeling, designing and implementing large-scale systems, it is restricted for representing
and handling uncertain and imprecise information that are pervasive in the real world [6, 11,
13]. For example, applications of the CRDB model can neither deal with queries as “find all
patients who are young”; nor “find all patients who are at least 90% likely to catch either
hepatitis or cirrhosis”, etc. Here, “young” is a vague concept that can be defined by a fuzzy
set [28] or a possibility distribution [17], and “hepatitis or cirrhosis” uncertainly expresses a
patient’s possible diseases that can be represented by the discrete set comprising of the two
diseases. Meanwhile, “90%” is the uncertainty degree, i.e., probability, of that whole fact
about the patient. To overcome the shortcoming of CRDB, this model has to be extended
for uncertain and imprecise information.
For building database models, uncertainty and imprecision are two different aspects of
information that require respective theories and methods to handle. In particular, the fuzzy
set theory is employed to express and handle imprecise information and extend CRDB to
fuzzy relational database (FRDB) models, meanwhile the probability theory is used to re-
present and manipulate uncertain information and develop CRDB to probabilistic relational
database (PRDB) models.
c© 2019 Vietnam Academy of Science & Technology
356 NGUYEN HOA
Up to now, many FRDB models have been built, e.g. in [1, 17, 20], and a large number of
PRDB models have been proposed, e.g. in [2, 5, 6, 9, 10, 14, 16, 22, 24, 27], respectively for
representing and handling uncertain and imprecise information. However, no model would be
so universal that could include all measures and tackle all facets of uncertain and imprecise
information. Thus, new databases model still continue to be developed for modeling data
objects of the real world.
PRDB models have been extended from CRDB in these two main directions [11] (1)
at the attribute level, where uncertain values of an attribute are defined by a probability
associating with a value on the domain of that attribute; Or (2) at the relational tuple level,
where attribute values are precise, but each tuple in a relation is associated with a probability
measure that expresses the uncertainty degree of that tuple in the relation.
For instances, in [2, 6, 9, 13, 15], the value of an attribute was assigned to a probability
to represent the uncertain level for that attribute to take the value. The models in [22, 27]
allowed the value of each attribute associated with a probability interval to represent the
uncertain degree of both the probability and the value that the attribute could take. More
flexibly, the model in [7] represented the value of each attribute as a probability distribution
on a set. It means that each attribute associated with a set of values and a probability
distribution expressing possibility that the attribute can take one of values of the set with
a probability computed from the distribution. The models in [18, 19] extended more the
model in [7], where a pair of lower and upper bound probability distributions is used instead
of a probability distribution as in [7]. In [10, 26], each tuple in a relation had an uncertainty
degree, measured by a probability value for it belonging to the relation. The model in [5]
extended the models in [10, 26], where used a pair of lower and upper bound probabilities
[23] instead of a probability to represent the uncertain degree for a tuple belonging to a
relation.
The models mentioned above are extensions with probability of the CRDB model in
different levels to represent uncertain information of objects in practice. However, these
models still have the restrictions. Particularly, regarding the models in [2, 6, 9, 10, 13, 15, 26],
the probability associated with each tuple or each attribute value is not always determined
exactly in practice. The models in [7, 18, 19, 22, 27] overcame the shortcoming of the models
in [2, 6, 9, 13, 15] by estimating a probability interval or a pair of lower and upper bound
probabilities for each attribute value of relations. However, in [7, 18, 19, 22, 27], the uncertain
degree of each tuple in a relation was not represented. Meanwhile, in contrast for the models
in [5, 10, 26], each tuple had a probability for it belonging to a relation but the attribute
value of the tupe is single and the probability for that attribute taking the single value was
not known.
In this paper, we propose a new probabilistic relational database model (PRDB) that
combines the representable relevance and strength of both the relational attribute level and
the relational tuple level for dealing with uncertain information. To build the PRDB model,
we express the value of an attribute as a finite set and associate each relational tuple with
a probability interval, then we propose a probabilistic interpretation of binary relations on
sets and use the combination strategies on probability intervals in [8] to define all the basic
concepts and probabilistic relational algebraic operations for PRDB. It is due to combining
both of the representable levels for uncertain information, our model can overcome the shor-
tcomings of the above mentioned models to represent and manipulate uncertain information
EXTENDING RELATIONAL DATABASE MODEL 357
in practice.
Basic probability definitions as a mathematical foundation for PRDB are presented in
Section 2. The PRDB model including the fundamental concepts such as schema, relation
and probabilistic functional dependency is introduced in Section 3. Section 4 and 5 present
probabilistic relational algebraic operations and their properties in PRDB. Finally, Section
6 concludes the paper and outlines further research directions in the future.
2. BASIC PROBABILITY DEFINITIONS
This section presents some basic probability definitions to build PRDB for representing
and handling uncertain information.
2.1. Probabilistic interpretation of relations on sets
For computing the probability of a binary relation on atrribute values in PRDB, we
propose the probabilistic interpretation of binary relations on sets as following definitions.
Definition 1. Let A and B be sets, U and V be value domains, and θ be a binary relation
from {=, 6=,≤,≥, ,⇒}. The probabilistic interpretation of the relation A θ B, denoted
by prob(A θ B), is a value in [0, 1] that is defined by
1. prob(A θ B) = p(u θ v|u ∈ A, v ∈ B), where A is a subset of U, B is a subset of V
and θ ∈ {=, 6=,≤, } assumed to be valid on (U × V ), p (u θ v|u ∈ A, v ∈ B) is
the conditional probability of u θ v given u ∈ A and v ∈ B.
2. prob(A⇒ B) = p(u ∈ B|u ∈ A), where A and B are two subsets of U , p(u ∈ B|u ∈ A)
is the conditional probability for u ∈ B given u ∈ A.
Intuitively, given propositions “x ∈ A” and “y ∈ B”, prob(A θ B) is the probability
for x θ y being true. Meanwhile prob(A ⇒ B) is that, given a proposition “x ∈ A” being
true, prob(A⇒ B) is the probability for “x ∈ B” being true.
Example 1. Let A = {3, 4} and B = {4, 5} be two sets on the domain {1, 2, 3, 4, 5, 6}. Then
1. prob(A = B) = p(u = v|u ∈ A, v ∈ B)
= p(u = v|u ∈ {3, 4}, v ∈ {4, 5}) = 0.25.
2. prob(A⇒ B) = p(u ∈ B|u ∈ A)
= p(u ∈ {4, 5}|u ∈ {3, 4}) = 0.5.
2.2. Probabilistic combination strategies
Let two events e1 and e2 have probabilities in the intervals [L1, U1] and [L2, U2], respecti-
vely. Then the probability intervals of the conjunction event e1∧e2, disjunction event e1∨e2,
or difference event e1 ∧¬e2 can be computed by alternative strategies. In this work, we em-
ploy the conjunction, disjunction, and difference strategies given in [8, 19] as presented in
Table 1, where ⊗, ⊕ and denote the conjunction, disjunction, and difference operators,
respectively.
358 NGUYEN HOA
Table 1. Definitions of probabilistic combination strategies
Strategy Operators
Ignorance ([L1, U1]⊗ig [L2, U2]) ≡ [max(0, L1 + L2 − 1),min(U1, U2)]
([L1, U1]⊕ig [L2, U2]) ≡ [max(L1, L2),min(1, U1 + U2)]
([L1, U1] ig [L2, U2]) ≡ [max(0, L1 − U2),min(U1, 1− L2)]
Independence ([L1, U1]⊗in [L2, U2]) ≡ [L1.L2, U1.U2]
([L1, U1]⊕in [L2, U2]) ≡ [L1 + L2 − (L1.L2), U1 + U2 − (U1.U2)]
([L1, U1] in [L2, U2]) ≡ [L1.(1− U2), U1.(1− L2)]
Positive correlation
(when e1 implies e2,
or e2 implies e1)
([L1, U1]⊗pc [L2, U2]) ≡ [min(L1, L2),min(U1, U2)]
([L1, U1]⊕pc [L2, U2]) ≡ [max(L1, L2),max(U1, U2)]
([L1, U1] pc [L2, U2]) ≡ [max(0, L1 − U2),max(0, U1 − L2)]
Mutual exclusion
(when e1 and e2 are
mutually exclusive)
([L1, U1]⊗me [L2, U2]) ≡ [0, 0]
([L1, U1]⊕me [L2, U2]) ≡ [min(1, L1 + L2),min(1, U1 + U2)]
([L1, U1] me [L2, U2]) ≡ [L1,min(U1, 1− L2)]
3. PROPOSED PRDB MODEL
As for CRDB, the schema, relation, functional dependency and key are the fundamental
concepts in the PRDB model.
3.1. PRDB schemas
A PRDB schema consists of a set of attributes (as in CRDB) associated with a mem-
bership function representing the lower-bound and upper-bound probabilities for an instance
tuple of the relational attributes being true and is defined as follows.
Definition 2. A PRDB schema is a pair R = (U , ℘), where
1. U = {A1, A2, ..., Ak} is a set of pairwise different relational attributes.
2. ℘ is a function that maps each (v1, v2, ..., vk) ∈ 2D1 × 2D2 × ... × 2Dk to a subinterval
of the interval [0, 1], Di is the domain of the attribute Ai, i = 1, ..., k.
We note that a precise value can be considered as a special set. That is, each precise value
v ∈ D can be defined as a set {v} on D. Therefore, the above definition can accommodate
relational attributes whose values are precise as in CRDB. Also, the PRDB schema is actually
a generalization of the probabilistic relational database schemas in [6, 26, 27], where relational
attributes could take only precise and single values.
As in CRDB, the notations R(U , ℘) and R can be used to replace R = (U , ℘). In
addition, each t = (v1, v2, ..., vk) is called a tuple on the set of attributes A1, A2, ..., Ak, the
domain of each attribute A is denoted by dom(A).
Example 2. Suppose a PRDB schema PATIENT(P ID, P NAME, P AGE, P DISEASE,
P COST, ℘), where the attributes P ID, P NAME, P AGE, P DISEASE, and P COST
respectively describe the information about the identifier, name, age, disease, and daily
treatment cost of each patient, ℘ maps each information tuple of patients to an interval
[α, β] ⊆ [0, 1].
EXTENDING RELATIONAL DATABASE MODEL 359
3.2. PRDB relations
A PRDB relation is an instance of a PRDB schema in which each relational attribute
takes a value set in its domain and each tuple takes a probability interval on [0, 1] as the
definition below.
Definition 3. Let U = {A1, A2, ..., Ak} be a set of k pairwise different attributes. A PRDB
relation r over the schema R = (U , ℘) is a finite set {t|t = (v1, v2, ..., vk) ∈ 2D1×2D2×...×2Dk ,
℘(t) = [α, β] ⊆ [0, 1]} where ℘(t) represents the probabilistic membership degree of t in r
and Di is the domain of the attribute Ai for every i = 1, 2, ..., k.
We note that each component vi of the tuple t = (v1, v2, ..., vk) in a PRDB relation r
is a set in 2Di but the attribute Ai only takes one of the values in vi and ℘(t) expresses
the uncertain membership degree of the tuple t, that is a probability between α and β.
Definition 3 is a proper extension of the definitions of relations in CRDB and the models
in [6, 26, 27], where the value of an attribute was certain and the membership degree of a
tuple was 0, 1 or a single probability. As in [3, 7, 26], the PRDB model adopts the closed
world assumption (CWA). It means, for every tuple t = (v1, v2, ..., vk) on the set of attributes
U = {A1, A2, ..., Ak} of the schema R(U , ℘) such that ℘(t) = [0, 0] (Definition 2) then there
does not exist any relation r over R including t.
For each probabilistic tuple t, we write t.Ai and t.℘ to denote the value (set) vi and the
probability interval [α, β], respectively. For each set of attributes X ⊆ {A1, A2, ...Ak}, the
notation t[X] is used to denote the rest of t after eliminating the value of attributes not
belonging to X.
Example 3. Table 2 shows an example relation PATIENT over the schema PATIENT in
Example 2. For the attributes P ID and P NAME, their values are assumed to be single, cer-
tain. In reality, while being diagnosed, the actual disease of a patient may still be uncertain.
Similarly, the treatment cost for patients is also not known definitely even as the patients
know their diseases. Therefore, for the attribute P DISEASE, its values can be as certain as
“tuberculosis” or as uncertain as {hepatitis, cirrhosis} meaning the patients disease could be
either “hepatitis” or “cirrhosis”. For the attribute P COST, the value “85” means 85 USD
per day, {175, 200} means that the daily treatment cost can be either 175 or 200 USD.
Meanwhile, the probability interval [0.8, 1], for instance, expresses that the uncertain
degree for the tuple (P442, Mary, 16, {hepatitis, cirrhosis}, {7, 8}) belonging to the relation
PATIENT is between 0.8 and 1.
Table 2. Relation PATIENT
P ID P NAME P AGE P DISEASE P COST ℘
P115 John 65 tuberculosis {175, 200} [0.9, 1]
P226 Anna 50 bronchitis 6 [1, 1]
P338 Bill 30 cholecystitis 85 [0.7, 1]
P442 Mary 16 {hepatitis, cirrhosis} {7, 8} [0.8, 1]
P555 Paul {45, 46} diabetes {5, 6} [1, 1]
Now, the notion of a probabilistic relational database is defined as follows.
Definition 4. A probabilistic relational database over a set of attributes is a set of probabi-
listic relations corresponding with the set of their probabilistic relational schemas.
360 NGUYEN HOA
Note that, if we only care about a unique relation over a schema then we can unify its
symbol name with its schemas name.
3.3. PRDB value-equivalent tuples
A relational database model, either being classical or non-classical, does not allow re-
dundant tuples in a relation, i.e., those whose respective attribute values are equal. For the
model in [6], where relational attributes could take only precise values and the uncertain
membership degree of tuples was a single probability value, the authors introduced the no-
tion of value-equivalence. Two tuples were said to be value-equivalent if and only if their
respective relational attribute values are equal. Then they should be coalesced into a single
tuple with the same relational attribute values and the combined uncertain membership de-
gree as the sum of their ones. Similarly, in [7], identical tuples as the result of the projection
operation were also coalesced.
In [26], the authors added the notion of ε-equality. Two tuples were said to be ε-equal
if and only if they are value-equivalent, as defined in [6], and the absolute difference of their
probabilistic attribute values is less than ε.
In our proposed PRDB, since relational attribute values can be proper sets, the value-
equivalence of two tuples is not the matter of “to be or not to be” as in [6] but to a
certain degree. To be coherent with the probabilistic framework of the model, we evaluate
the likelihood of the value-equivalence of two tuples and introduce the notion of ε-value-
equivalence as follows.
Definition 5. Let R = (U , ℘) be a PRDB schema, X be a subset of U , t1 and t2 be
two tuples on X, ε ∈ [0, 1]. Then t1 and t2 are said to be ε − value − equivalent with
respect to a probabilistic conjunction strategy ⊗, denoted by t1 ≈ε⊗ t2 if and only if
⊗A∈Xprob (t1.A = t2.A) ≥ ε.
We note that, by Definition 1, prob(t1.A = t2.A) is the probability for the values of
attribute A in t1 and t2 being equal. The introduction of ε-value-equivalence is to coalesce
two PRDB tuples under some probabilistic combination strategy if their equality likelihood
is greater than or equal to a certain threshold ε, or not to coalesce them otherwise. The
definition of value-equivalence in [6] could be considered as a special case of our definition
with ε = 1.
Example 4. Suppose there is a new piece of information coming for John and the following
tuple is added to the relation in Example 3: 〈(P115 John, 65, tuberculosis, 175), [0.8, 1]〉.
Then the value-equivalence likelihood of these two tuples about John, namely t1 and t2,
under the independence probabilistic conjunction strategy ⊗in is
⊗A∈{P ID, P NAME, P AGE, P DISEASE, P COST}prob(t1.A = t2.A) = 1× 1× 1× 1× 0.5 = 0.5
and t1 and t2 can be coalesced into the tuple t under the equivalent threshold ε = 0.5
and the independence probabilistic disjunction strategy ⊕in, where t.A = t1.A ∩ t2.A,
℘(t) = ℘ (t1)⊕in ℘ (t2). That is
t = (P115, John, 65, tuberculosis, 175) with ℘(t) = [0.9, 1]⊕in [0.8, 1] = [0.98, 1].
EXTENDING RELATIONAL DATABASE MODEL 361
3.4. PRDB functional dependencies
Functional dependencies play an important role in CRDB. In [18, 19] a probabilistic
functional dependency was defined under the probability degree for values of two attributes
being equal. Meanwhile, functional dependencies were not formally defined in previous
works. For PRDB, our definition is as follows.
Definition 6. LetR = (U , ℘) be a PRDB schema, r be a relation overR, ⊗ be a probabilistic
conjunction strategy, X ⊆ U and Y ⊆ U . A PRDB functional dependency of Y on X under
⊗, denoted by X→⊗ Y, holds if and only if
∀t1, t2 ∈ r : ⊗A∈Xprob (t1.A = t2.A) ≤ ⊗A∈Y prob (t1.A = t2.A) .
One can see that this definition subsumes that of CRDB. Also, it is easy to see that for
every PRDB schema R(U , ℘) then U →⊗ Y with Y ⊆ U under all probabilistic conjunction
strategies.
Example 5. In every relation r over the schema PATIENT with the set of attributes
U = {P ID, P NAME, P AGE, P DISEASE, P COST} in Example 3, the values of the
attribute P ID, that describe the identifiers of patients, are single and pairwise different.
Thus, for two tuples t1, t2 ∈ r and an attribute A ∈ U , prob(t1.P ID = t2.P ID) = 0, while
prob (t1.A = t2.A) ≥ 0. So, ⊗A∈Y prob (t1.A = t2.A) ≥ 0 with Y ⊆ U , by Definition 6,
there is the PRDB functional dependency P ID→⊗ Y in the schema PATIENT under all
probabilistic conjunction strategies.
As for CRDB, the values of the key attributes of a schema in PRDB are the basis to
identify a tuple in a relation, as defined below.
Definition 7. Let R = (U , ℘) be a PRDB schema, r be a relation over R, and ⊗ be a
probabilistic conjunction strategy. A non-empty set of attributes K ⊆ U is a