# Lossless Join Decomposition for Extended Possibility-Based Fuzzy Relational Databases

Authors: Julie Yu-Chih Liu
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

Functional dependency is the basis of database normalization. Various types of fuzzy functional dependencies have been proposed for fuzzy relational database and applied to the process of database normalization. However, the problem of achieving lossless join decomposition occurs when employing the fuzzy functional dependencies to database normalization in an extended possibility-based fuzzy data models. To resolve the problem, this study defined fuzzy functional dependency based on a notion of approximate equality for extended possibility-based fuzzy relational databases. Examples show that the notion is more applicable than other similarity concept to the research related to the extended possibility-based data model. We provide a decomposition method of using the proposed fuzzy functional dependency for database normalization and prove the lossless join property of the decomposition method.


---

## Body

## 1. Introduction

Database normalization plays a crucial role in the design theory of relational database to avoid insertion and deletion and update anomalies in a database. The database normalization involves decomposition of a relation schema (table) into several smaller ones. The essential requirement of the decomposition islossless join property, which ensures that the original relation can be obtained from its decomposed results via combination operations [1]. Several methods have been proposed to design normalized relation schemes based on the keys and functional dependencies of a relation to achievelossless join decomposition [2, 3]. The design theory has been applied to fuzzy databases, in which uncertain and imprecise information can be represented and manipulated. The fuzzy databases are extended from the classical databases based on fuzzy sets and possibility theory [4], and they can be resemblance-based fuzzy model [5, 6] and possibility-based fuzzy model [7, 8]. In the context of fuzzy databases, fuzzy functional dependency (FFD) has emerged to extend the classical functional dependency to represent functional relationships between classes/attributes of objects for fuzzy database models. Various FFD definitions have been proposed in some fuzzy data models for database normalization [9, 10].However, very few research methods discuss lossless join property for the normalization in possibility-based fuzzy databases. To achieve lossless join decomposition by using FFDs for the possibility-based fuzzy databases is more difficult than for the resemblance-based fuzzy databases, especially for extended possibility-based fuzzy database. The extended possibility-based fuzzy database [7] is an extension of possibility-based fuzzy database [8] by including a resemblance-based fuzzy model [6]. In the fuzzy database, attribute values could be the possibility distributions of the attribute on its domain. Additionally, the elements in a domain have some degree of resemblance. Previous work has applied FFDs on the decomposition for the fuzzy database [10–12]. Informally, these FFDs are based on a certain degree of similarity between two attribute values. Namely, two tuples that are similar but not identical might be regarded as redundant. Applying the similarity-based FFDs on relation decomposition prompts the difficulty for lossless join decomposition on two facets: (i) redundancy removal: how to eliminate redundant tuples that are not identical from the decomposed results so that the results can be, later on, used to produce the original relation without losing information and (ii) tuple merging: how to combine two relations via merging their tuples of which attribute values are similar but not identical.Complicating this problem further, most similarity measures [7, 13, 14] of values in the form of possibility distribution are nottransitive. When tuple redundancy is determined by the similarity measures of nontransitivity, the result of eliminating redundant tuples from a decomposed relation might be not unique (or order sensitive1). An inconsistent data redundancy removal not only leads to unstable results of data integration, as described in [15], but also causes decomposition results not lossless. When the decomposition result of a relation is not unique, the combination of the result will have many different outcomes, at least one of which is different from the original relation. Accordingly, the decomposition inevitably violates the lossless join property. Moreover, the nonunique results occur for relation combination when the attribute values to be joined/merged have similarity relation of nontransitivity.To avoid nontransitivity, Chen et al. provided FFD with embedded classical FD [11, 16], where redundancy removal is restricted to duplicate tuples. But, this restriction draws the normalization process back to the traditional operations of crisp data. To obtain transitive relationship among tuples, some research applied the max-min transitive closure on the relationship matrix of similarity degree between tuples [17]. The max-min transitive closure of a relationship matrix must be a matrix with max-min transitivity [18]. By referring to the transitive closure of the relationship matrix, the tuples which have similarity higher than a given threshold can be grouped into disjointed sets. The tuples in the same set were regarded as redundant. However, this approach cannot determine the similarity of two tuples by merely examining these two, and the similarity is changed by inserting or deleting other tuples. The nondeterministic and dynamic characteristic is not applicable to the practice of databases.To our knowledge, very few studies provide a complete guideline to perform normalization that ensures lossless join decomposition in the fuzzy databases. Therefore, the purpose of this study is to fill up this gap. This study first proposes a notion of approximate equality which represents the transitive equivalent relation among tuples. Then, it provides new definition of FFD and lossless join decomposition based on approximate equality for the fuzzy databases. Both functional dependencies and lossless join decomposition in a traditional database are special cases in this proposal. Examples show that the notion is more applicable than other similarity concepts to the research related to the fuzzy databases. This work also provides the method of achieving the lossless join decomposition for the fuzzy databases.The remainder of this paper is organized as follows. Section2 gives a brief introduction to database normalization and fuzzy database and the survey of the similarity measures related to the fuzzy database. Section 3 demonstrates the problem of using nontransitive similarity measures for determining tuple redundancy and provides a notion of approximate equality for it. The FFD is then defined based on the approximate equality in Section 4. Besides, the lossless join decomposition is proposed for the fuzzy databases, and its property is proven as well. Section 5 draws the conclusion of this paper.


## 2. Preliminaries

This section first briefly reviews the essential operations for lossless join decomposition in traditional databases. Then, it introduces the fuzzy databases considered in this work and the similarity measures of values in form of possibility distribution.


### 2.1. Essential Operations for Lossless Join Decomposition

In traditional relational database, a row is called a tuple; a column header is called an attribute; and the table is called a relation. Given anm-ary relation schema R
(
A
1
,
A
2
,
…
,
A
m
), an instance of R denoted by r
(
R
) is the set of all tuples in R. Let Α denote a set of attributes A
1
,
A
2
,
…
,
A
m. A functional dependency FD A
i
→
A
j existing in R
(
A
) represents the tuples having the same values on attribute A
i that must be identical on A
j, where A
i
,
A
j
∈
A. Two operations are related to the lossless join decomposition:projection andnatural join. The operationprojection generates a result by selecting certain attributes from given relation and removing redundant tuples. Let Θ denote a set of attributes in R
(
A
); that is, Θ
⊂
A. The result of projection R over attributes Θ
⊆
A is Π
Θ
(
R
)
=
{
t
[
Θ
]
∣
t
∈
r
(
R
)
}, where t
[
Θ
] represents the composite of values on Θ in tuple t. Thenatural join (denoted by *) of R
′
(
X
Y
) and R
′′
(
Y
Z
) is obtained by removing duplicate attribute from the results ofequal join on joined attribute Y and is denoted as shown below:
(1)
R
′
*
R
′′
=
{
(
t
′
[
X
]
,
t
′
[
Y
]
,
t
′′
[
Z
]
)
:
t
′
[
Y
]
=
t
′′
[
Y
]
∣
t
′
∈
r
(
R
′
)
,
t
′′
∈
r
(
R
′
)
}
.
Thenatural join andprojection operations are, respectively, used to combine and decompose relations.Formally, decomposition{
R
1
,
R
2
,
…
,
R
k
} of R islossless join if equation r
(
R
)
=
Π
R
1
(
R
)
*
Π
R
2
(
R
)
*
⋯
*
Π
R
k
(
R
) holds. In other words, thelossless join decomposition ensures that the combination of the decomposed results of a relation has no spurious tuple or missing tuple to the relation via natural join operation [1].For example, given a relationR, the results of R
′
=
Π
A
1
,
A
2
(
R
) and R
′
′
=
Π
A
2
,
A
3
(
R
) are shown in Table 1.Table 1
R
R
′
R
′
′
A
_
1
_
A
2
A
3
A
_
1
_
A
2
A
2
A
3
t
1:
x
p
m
x
p
p
m
t
2:
y
p
m
y
p
q
n
t
3:
z
q
n
z
qIn this case, the decomposition{
R
′
,
R
′
′
} of R has lossless join property because thenatural join result of R
′ and R
′
′ is exactly the same as R (as shown in Table 2).Table 2
equal join ofR
′ and R
′
′ on A
2
R
′
*
R
′
′
A
_
1
_
A
2
A
2
A
3
A
_
1
_
A
2
A
3
t
1:
x
p
p
m
x
p
m
t
2:
y
p
p
m
y
p
m
t
3:
z
q
q
n
z
q
n


### 2.2. The Fuzzy Databases

In last two decades, fuzzy concepts have been incorporated in traditional databases [5, 8, 19] and applied to measure the relation between data [20–22]. The fuzzy databases enable dealing with imprecision and uncertainty in the real world based on the theory of fuzzy sets and possibility distribution theory. The possibility-based fuzzy theory has been widely applied in environmental management, such as flood-diversion planning [23], water resources management [24], and air quality management [25]. This work considers the extended possibility-based databases proposed by Chen et al. [7] because it can capture both the possibility-based fuzzy model and the resemblance-based fuzzy concept. The fuzzy database has drawn much attention of research on semantic measures, information processing, update operation, and UML class diagram therewith [20, 26, 27]. The data model of the fuzzy databases is a hybrid of a possibility-based data model in [8] and a resemblance-based data model in [6]. The possibility-based model derives from Zadeh’s fuzzy theory. In the theory [4], a fuzzy set F on a universe of discourse U is described by {
μ
F
(
u
)
/
u
∣
u
∈
U
}, where μ
F
:
U
→
[
0,1
] is a membership function for the fuzzy set F and μ
F
(
u
) denotes the degree of membership of u in F. In a possibility-based database [8], the value of an attribute A on a domain D is a possibility distribution π
A
=
{
π
A
(
u
)
/
u
∣
u
∈
D
}, where π
A
(
u
) denotes the possibility that u is the actual value of A. For example, D
=
{
u
1
,
u
2
,
u
3
} and π
A
=
{
0.8
/
u
1
,
0.5
/
u
2
,
0.6
/
u
3
}. An example of applying the possibility-based fuzzy theory2 in real world is shown below. Consider a domain of attribute “eye color” is {black, brown, blue, green} and a possibility distribution is given below:
(2)
Asia-Color
=
{
1.0
black
,
0.8
brown
,
0.3
blue
,
0.1
green
}
.
Suppose that John’s eye color is an “Asia color.” Then, according to the interpretation for possibility-based fuzzy theory, one concludes that the possibility of John’s eye being brown blue color is 0.3.In the extended possibility-based database, attribute values are represented by possibility distributions of an attribute on its domain, and a domain is associated with a similarity relation of domain elements. Formally, anm-ary relation instance r on a schema R
(
A
1
,
A
2
,
…
,
A
m
) in the fuzzy database is a subset ofCartesian product of Φ
(
A
1
)
×
Φ
(
A
2
)
×
⋯
×
Φ
(
A
m
), where Φ
(
A
i
) represents a set of all possibility distributions of attribute A
i on its domain. For a domain D
i, a proximity relation is given to describe the resemblance between domain elements in D
i. A proximity is a mapping s
i
:
D
i
×
D
i
→
[
0
,
1
] with reflexivity and symmetry; that is, s
i
(
u
,
u
)
=
1 and s
i
(
u
,
v
)
=
s
i
(
v
,
u
). The elements in a domain cannot directly be partitioned into disjoint equivalent classes by a threshold cutting on the proximity relation for the domain elements.To acquire equivalent classes of a proximity relation on a domain, Shenoi et al. [18] proposed α-proximate relation. Two elements u
,
v
∈
D are α-proximate (denoted by u
S
α
+
v) if s
(
u
,
v
)
>
α or there exists a sequence w
1
,
w
2
,
…
,
w
r
∈
D, Such that min
⁡
{
s
(
u
,
w
1
)
,
s
(
w
1
,
w
2
)
,
…
,
s
(
w
r
-
1
,
w
r
)
,
s
(
w
r
,
v
)
}
>
α. Given a proximity relation s and a threshold α for domain D, the domain can be partitioned into disjoint subsets (called α-proximate equivalent classes) such that the elements in a partition are α-proximate. The equivalent classes are regarded as basic concepts for the methods being reviewed or proposed hereinafter.By extending traditional functional dependency, research has proposed variety of fuzzy functional dependencies (FFDs) for fuzzy databases [14, 21, 28]. The FFDs are determined by the degree of similarity of attribute values rather than by the identity. Several similarity measures of attribute values are proposed for the extended possibility-based frameworks [7, 16, 20, 29]. Most of them provide the estimates within the interval [
0,1
]. The similarity measures are briefly restated hereinafter, in which s and α
∈
[
0,1
], respectively, denote the proximity relation and a threshold defined on a given domain D
=
{
u
1
,
u
2
,
…
,
u
n
}; π
A and π
B represent two possibility distributions on D. The degree of closeness between π
A and π
B, denoted by ξ
1
(
π
A
,
π
B
), is defined as follows [29]:
(3)
ξ
1
(
π
A
,
π
B
)
=
{
0
min
⁡
u
i
,
u
j
∈
D
^
s
(
u
i
,
u
j
)
<
α
min
⁡
u
i
∈
D
(
1
-
|
π
A
(
u
i
)
-
π
B
(
u
i
)
|
)
otherwise
,
where D
^
=
{
u
i
∈
D
:
π
A
(
u
i
)
>
0
}
∪
{
u
i
∈
D
:
π
B
(
u
i
)
>
0
}.The measure ofξ
1 may give low degree of similarity for two values that are very similar to each other, for example, ξ
1
(
{
0.9
/
excellent
,
1
/
good
}
,
{
1
/
good
}
)
=
0.1. To prevent some counter-intuitive estimates of ξ
1, Chen et al. defined the possibility that π
A
=
π
B is true as shown below [7] (here ∧ denotes minimum):
(4)
ξ
2
(
π
A
,
π
B
)
=
sup
⁡
s
(
u
i
,
u
j
)
≥
α
,
u
i
,
u
j
∈
D
(
π
A
(
u
i
)
∧
π
B
(
u
j
)
)
.
This assessment is widely adopted in the extended possibility-based databases and is adoptable for the application with subnormal distribution (i.e., ξ
2
(
π
A
,
π
A
)
<
1, or see [4] for details). For normal distribution, Chen et al. [16] includedidentity relation (denoted by =
id) into (4) as follows:
(5)
ξ
3
(
π
A
,
π
B
)
=
{
1
π
A
=
id
π
B
sup
⁡
s
(
u
i
,
u
j
)
≥
α
,
u
i
,
u
j
∈
D
π
A
(
u
i
)
∧
π
B
(
u
j
)
o
.
w
.Ma et al. defined the similarity measure from the perspective of the semantic closeness between two attribute values [20] as shown below:
(6)
ξ
4
(
π
A
,
π
B
)
=
δ
(
π
A
,
π
B
)
∧
δ
(
π
B
,
π
A
)
,
where δ denotes a semantic inclusion degree. Consider the following:
(7)
δ
(
π
A
,
π
B
)
=
∑
u
i
,
u
j
∈
D
,
s
(
u
i
,
u
j
)
≥
α
(
π
A
(
u
i
)
∧
π
B
(
u
j
)
)
∑
j
=
1
n
π
B
(
u
j
)
.
The notion of ξ
4 may violate the convention that the similarity degree of two values lies within [
0,1
]; ξ
4
(
π
A
,
π
B
)
=
1.52 for the case that π
A
=
{
0.9
/
excellence
,
0.8
/
good
} and π
B
=
{
0.7
/
excellence
,
0.6
/
good
} when the similarity of “excellence” and “good” is larger than the given threshold; that is, s
(
excellence
,
good
)
≥
α. It is difficult to set up a proper threshold for estimates that range out of [
0,1
], having an unpredictable upper bound.Liu et al. [13] extended the semantic equivalence to ensure that the result of similarity measure lies within [
0,1
]. The measurement adjusts the possibility distributions of values based on  α-proximate equivalent classes of the domain before measuring their similarity. Let C
=
{
C
1
,
C
2
,
…
,
C
r
} be the α-proximate equivalent classes of domain D. The adjusted value of possibility distribution π
• is defined as follows:
(8)
π
~
•
=
⋃
k
=
1
r
{
u
-
•
k
u
′
:
u
′
∈
C
k
}
,
where u
-
•
k
=
∑
j
=
1
,
u
j
∈
C
k
|
C
k
|
π
•
(
u
j
)
/
|
C
^
k
| and C
^
k
=
{
u
j
∈
C
k
:
π
•
(
u
j
)
>
0
}, k
=
1
,
…
,
r. Then,
(9)
ξ
5
(
π
A
,
π
B
)
=
δ
(
π
A
,
π
B
)
∧
δ
(
π
B
,
π
A
)
,
where
δ
(
π
A
,
π
B
)
=
∑
i
=
1
n
(
π
~
A
(
u
i
)
∧
π
~
B
(
u
i
)
)
∑
j
=
1
n
π
~
B
(
u
j
)
.Although the methods mentioned above differ from each other on measuring similarity of attribute values, most of the methods of measuring the similarity of tuples are the same. The methods adopt the minimum of the similarity of each pair of attribute values. Given tuplest
=
(
π
A
1
,
π
A
2
,
…
,
π
A
m
) and t
′
=
(
π
A
1
′
,
π
A
2
′
,
…
,
π
A
m
′
), the resemblance of tuples t and t
′, denoted by η
(
t
,
t
′
), is given by
(10)
η
(
t
,
t
′
)
=
min
⁡
i
=
1
,
…
,
m
ξ
•
(
π
A
i
,
π
A
i
′
)
,
where ξ
• could be either ξ
1, ξ
2, ξ
3, ξ
4, or ξ
5 in (3)–(9). Tuples t and t
′ are redundant to each other if η
(
t
,
t
′
)
≥
α, where α is a given threshold. The similarity measure of tuples has been applied to extract representative tuples for reducing information redundancy [17].Fuzzy functional dependency (FFD) is a concept derived from traditional FD. Both FFD and FD have several applications on databases, for example, redundancy elimination [30], missing data prediction, fuzzy data compression [17, 31], and lossless join decomposition [10, 28, 32]. In literature, various FFDs are defined for different fuzzy data model. For some fuzzy data representation, FFDs are defined based on the equivalence classes of tuples, such as the similarity-based fuzzy data model [33]. In the extended possibility-based databases, the definition of FFD is also of variety, such as literature [10, 14, 34, 35]. One example among the FFD definitions in the literature is listed below.Definition 1 (see [10], fuzzy functional dependency).
LetX
~
>
Y denote that attribute X is fuzzy functional which depends on attribute Y in a relation R. The FFD: X
~
>
Y holds in the instance r
(
R
) if and only if η
(
t
[
X
]
,
t
′
[
X
]
)
≦
η
(
t
[
Y
]
,
t
′
[
Y
]
) for every t
,
t
′
∈
r
(
R
).The example helps in understanding the problem of applying the FFDs on relation decomposition in the fuzzy databases illustrated in Section3.


## 2.1. Essential Operations for Lossless Join Decomposition

In traditional relational database, a row is called a tuple; a column header is called an attribute; and the table is called a relation. Given anm-ary relation schema R
(
A
1
,
A
2
,
…
,
A
m
), an instance of R denoted by r
(
R
) is the set of all tuples in R. Let Α denote a set of attributes A
1
,
A
2
,
…
,
A
m. A functional dependency FD A
i
→
A
j existing in R
(
A
) represents the tuples having the same values on attribute A
i that must be identical on A
j, where A
i
,
A
j
∈
A. Two operations are related to the lossless join decomposition:projection andnatural join. The operationprojection generates a result by selecting certain attributes from given relation and removing redundant tuples. Let Θ denote a set of attributes in R
(
A
); that is, Θ
⊂
A. The result of projection R over attributes Θ
⊆
A is Π
Θ
(
R
)
=
{
t
[
Θ
]
∣
t
∈
r
(
R
)
}, where t
[
Θ
] represents the composite of values on Θ in tuple t. Thenatural join (denoted by *) of R
′
(
X
Y
) and R
′′
(
Y
Z
) is obtained by removing duplicate attribute from the results ofequal join on joined attribute Y and is denoted as shown below:
(1)
R
′
*
R
′′
=
{
(
t
′
[
X
]
,
t
′
[
Y
]
,
t
′′
[
Z
]
)
:
t
′
[
Y
]
=
t
′′
[
Y
]
∣
t
′
∈
r
(
R
′
)
,
t
′′
∈
r
(
R
′
)
}
.
Thenatural join andprojection operations are, respectively, used to combine and decompose relations.Formally, decomposition{
R
1
,
R
2
,
…
,
R
k
} of R islossless join if equation r
(
R
)
=
Π
R
1
(
R
)
*
Π
R
2
(
R
)
*
⋯
*
Π
R
k
(
R
) holds. In other words, thelossless join decomposition ensures that the combination of the decomposed results of a relation has no spurious tuple or missing tuple to the relation via natural join operation [1].For example, given a relationR, the results of R
′
=
Π
A
1
,
A
2
(
R
) and R
′
′
=
Π
A
2
,
A
3
(
R
) are shown in Table 1.Table 1
R
R
′
R
′
′
A
_
1
_
A
2
A
3
A
_
1
_
A
2
A
2
A
3
t
1:
x
p
m
x
p
p
m
t
2:
y
p
m
y
p
q
n
t
3:
z
q
n
z
qIn this case, the decomposition{
R
′
,
R
′
′
} of R has lossless join property because thenatural join result of R
′ and R
′
′ is exactly the same as R (as shown in Table 2).Table 2
equal join ofR
′ and R
′
′ on A
2
R
′
*
R
′
′
A
_
1
_
A
2
A
2
A
3
A
_
1
_
A
2
A
3
t
1:
x
p
p
m
x
p
m
t
2:
y
p
p
m
y
p
m
t
3:
z
q
q
n
z
q
n


## 2.2. The Fuzzy Databases

In last two decades, fuzzy concepts have been incorporated in traditional databases [5, 8, 19] and applied to measure the relation between data [20–22]. The fuzzy databases enable dealing with imprecision and uncertainty in the real world based on the theory of fuzzy sets and possibility distribution theory. The possibility-based fuzzy theory has been widely applied in environmental management, such as flood-diversion planning [23], water resources management [24], and air quality management [25]. This work considers the extended possibility-based databases proposed by Chen et al. [7] because it can capture both the possibility-based fuzzy model and the resemblance-based fuzzy concept. The fuzzy database has drawn much attention of research on semantic measures, information processing, update operation, and UML class diagram therewith [20, 26, 27]. The data model of the fuzzy databases is a hybrid of a possibility-based data model in [8] and a resemblance-based data model in [6]. The possibility-based model derives from Zadeh’s fuzzy theory. In the theory [4], a fuzzy set F on a universe of discourse U is described by {
μ
F
(
u
)
/
u
∣
u
∈
U
}, where μ
F
:
U
→
[
0,1
] is a membership function for the fuzzy set F and μ
F
(
u
) denotes the degree of membership of u in F. In a possibility-based database [8], the value of an attribute A on a domain D is a possibility distribution π
A
=
{
π
A
(
u
)
/
u
∣
u
∈
D
}, where π
A
(
u
) denotes the possibility that u is the actual value of A. For example, D
=
{
u
1
,
u
2
,
u
3
} and π
A
=
{
0.8
/
u
1
,
0.5
/
u
2
,
0.6
/
u
3
}. An example of applying the possibility-based fuzzy theory2 in real world is shown below. Consider a domain of attribute “eye color” is {black, brown, blue, green} and a possibility distribution is given below:
(2)
Asia-Color
=
{
1.0
black
,
0.8
brown
,
0.3
blue
,
0.1
green
}
.
Suppose that John’s eye color is an “Asia color.” Then, according to the interpretation for possibility-based fuzzy theory, one concludes that the possibility of John’s eye being brown blue color is 0.3.In the extended possibility-based database, attribute values are represented by possibility distributions of an attribute on its domain, and a domain is associated with a similarity relation of domain elements. Formally, anm-ary relation instance r on a schema R
(
A
1
,
A
2
,
…
,
A
m
) in the fuzzy database is a subset ofCartesian product of Φ
(
A
1
)
×
Φ
(
A
2
)
×
⋯
×
Φ
(
A
m
), where Φ
(
A
i
) represents a set of all possibility distributions of attribute A
i on its domain. For a domain D
i, a proximity relation is given to describe the resemblance between domain elements in D
i. A proximity is a mapping s
i
:
D
i
×
D
i
→
[
0
,
1
] with reflexivity and symmetry; that is, s
i
(
u
,
u
)
=
1 and s
i
(
u
,
v
)
=
s
i
(
v
,
u
). The elements in a domain cannot directly be partitioned into disjoint equivalent classes by a threshold cutting on the proximity relation for the domain elements.To acquire equivalent classes of a proximity relation on a domain, Shenoi et al. [18] proposed α-proximate relation. Two elements u
,
v
∈
D are α-proximate (denoted by u
S
α
+
v) if s
(
u
,
v
)
>
α or there exists a sequence w
1
,
w
2
,
…
,
w
r
∈
D, Such that min
⁡
{
s
(
u
,
w
1
)
,
s
(
w
1
,
w
2
)
,
…
,
s
(
w
r
-
1
,
w
r
)
,
s
(
w
r
,
v
)
}
>
α. Given a proximity relation s and a threshold α for domain D, the domain can be partitioned into disjoint subsets (called α-proximate equivalent classes) such that the elements in a partition are α-proximate. The equivalent classes are regarded as basic concepts for the methods being reviewed or proposed hereinafter.By extending traditional functional dependency, research has proposed variety of fuzzy functional dependencies (FFDs) for fuzzy databases [14, 21, 28]. The FFDs are determined by the degree of similarity of attribute values rather than by the identity. Several similarity measures of attribute values are proposed for the extended possibility-based frameworks [7, 16, 20, 29]. Most of them provide the estimates within the interval [
0,1
]. The similarity measures are briefly restated hereinafter, in which s and α
∈
[
0,1
], respectively, denote the proximity relation and a threshold defined on a given domain D
=
{
u
1
,
u
2
,
…
,
u
n
}; π
A and π
B represent two possibility distributions on D. The degree of closeness between π
A and π
B, denoted by ξ
1
(
π
A
,
π
B
), is defined as follows [29]:
(3)
ξ
1
(
π
A
,
π
B
)
=
{
0
min
⁡
u
i
,
u
j
∈
D
^
s
(
u
i
,
u
j
)
<
α
min
⁡
u
i
∈
D
(
1
-
|
π
A
(
u
i
)
-
π
B
(
u
i
)
|
)
otherwise
,
where D
^
=
{
u
i
∈
D
:
π
A
(
u
i
)
>
0
}
∪
{
u
i
∈
D
:
π
B
(
u
i
)
>
0
}.The measure ofξ
1 may give low degree of similarity for two values that are very similar to each other, for example, ξ
1
(
{
0.9
/
excellent
,
1
/
good
}
,
{
1
/
good
}
)
=
0.1. To prevent some counter-intuitive estimates of ξ
1, Chen et al. defined the possibility that π
A
=
π
B is true as shown below [7] (here ∧ denotes minimum):
(4)
ξ
2
(
π
A
,
π
B
)
=
sup
⁡
s
(
u
i
,
u
j
)
≥
α
,
u
i
,
u
j
∈
D
(
π
A
(
u
i
)
∧
π
B
(
u
j
)
)
.
This assessment is widely adopted in the extended possibility-based databases and is adoptable for the application with subnormal distribution (i.e., ξ
2
(
π
A
,
π
A
)
<
1, or see [4] for details). For normal distribution, Chen et al. [16] includedidentity relation (denoted by =
id) into (4) as follows:
(5)
ξ
3
(
π
A
,
π
B
)
=
{
1
π
A
=
id
π
B
sup
⁡
s
(
u
i
,
u
j
)
≥
α
,
u
i
,
u
j
∈
D
π
A
(
u
i
)
∧
π
B
(
u
j
)
o
.
w
.Ma et al. defined the similarity measure from the perspective of the semantic closeness between two attribute values [20] as shown below:
(6)
ξ
4
(
π
A
,
π
B
)
=
δ
(
π
A
,
π
B
)
∧
δ
(
π
B
,
π
A
)
,
where δ denotes a semantic inclusion degree. Consider the following:
(7)
δ
(
π
A
,
π
B
)
=
∑
u
i
,
u
j
∈
D
,
s
(
u
i
,
u
j
)
≥
α
(
π
A
(
u
i
)
∧
π
B
(
u
j
)
)
∑
j
=
1
n
π
B
(
u
j
)
.
The notion of ξ
4 may violate the convention that the similarity degree of two values lies within [
0,1
]; ξ
4
(
π
A
,
π
B
)
=
1.52 for the case that π
A
=
{
0.9
/
excellence
,
0.8
/
good
} and π
B
=
{
0.7
/
excellence
,
0.6
/
good
} when the similarity of “excellence” and “good” is larger than the given threshold; that is, s
(
excellence
,
good
)
≥
α. It is difficult to set up a proper threshold for estimates that range out of [
0,1
], having an unpredictable upper bound.Liu et al. [13] extended the semantic equivalence to ensure that the result of similarity measure lies within [
0,1
]. The measurement adjusts the possibility distributions of values based on  α-proximate equivalent classes of the domain before measuring their similarity. Let C
=
{
C
1
,
C
2
,
…
,
C
r
} be the α-proximate equivalent classes of domain D. The adjusted value of possibility distribution π
• is defined as follows:
(8)
π
~
•
=
⋃
k
=
1
r
{
u
-
•
k
u
′
:
u
′
∈
C
k
}
,
where u
-
•
k
=
∑
j
=
1
,
u
j
∈
C
k
|
C
k
|
π
•
(
u
j
)
/
|
C
^
k
| and C
^
k
=
{
u
j
∈
C
k
:
π
•
(
u
j
)
>
0
}, k
=
1
,
…
,
r. Then,
(9)
ξ
5
(
π
A
,
π
B
)
=
δ
(
π
A
,
π
B
)
∧
δ
(
π
B
,
π
A
)
,
where
δ
(
π
A
,
π
B
)
=
∑
i
=
1
n
(
π
~
A
(
u
i
)
∧
π
~
B
(
u
i
)
)
∑
j
=
1
n
π
~
B
(
u
j
)
.Although the methods mentioned above differ from each other on measuring similarity of attribute values, most of the methods of measuring the similarity of tuples are the same. The methods adopt the minimum of the similarity of each pair of attribute values. Given tuplest
=
(
π
A
1
,
π
A
2
,
…
,
π
A
m
) and t
′
=
(
π
A
1
′
,
π
A
2
′
,
…
,
π
A
m
′
), the resemblance of tuples t and t
′, denoted by η
(
t
,
t
′
), is given by
(10)
η
(
t
,
t
′
)
=
min
⁡
i
=
1
,
…
,
m
ξ
•
(
π
A
i
,
π
A
i
′
)
,
where ξ
• could be either ξ
1, ξ
2, ξ
3, ξ
4, or ξ
5 in (3)–(9). Tuples t and t
′ are redundant to each other if η
(
t
,
t
′
)
≥
α, where α is a given threshold. The similarity measure of tuples has been applied to extract representative tuples for reducing information redundancy [17].Fuzzy functional dependency (FFD) is a concept derived from traditional FD. Both FFD and FD have several applications on databases, for example, redundancy elimination [30], missing data prediction, fuzzy data compression [17, 31], and lossless join decomposition [10, 28, 32]. In literature, various FFDs are defined for different fuzzy data model. For some fuzzy data representation, FFDs are defined based on the equivalence classes of tuples, such as the similarity-based fuzzy data model [33]. In the extended possibility-based databases, the definition of FFD is also of variety, such as literature [10, 14, 34, 35]. One example among the FFD definitions in the literature is listed below.Definition 1 (see [10], fuzzy functional dependency).
LetX
~
>
Y denote that attribute X is fuzzy functional which depends on attribute Y in a relation R. The FFD: X
~
>
Y holds in the instance r
(
R
) if and only if η
(
t
[
X
]
,
t
′
[
X
]
)
≦
η
(
t
[
Y
]
,
t
′
[
Y
]
) for every t
,
t
′
∈
r
(
R
).The example helps in understanding the problem of applying the FFDs on relation decomposition in the fuzzy databases illustrated in Section3.


## 3. Redundancy Removal and Tuple Merging

Several factors determine whether the relation decomposition possesses the lossless join property. They are the ways to decompose a relation, to remove redundant tuples, and to combine the decomposed results. Redundancy removal is to eliminate redundant tuples. If the similarity measures used to measure tuple redundancy are nottransitive, the result of redundancy removal could be nonunique. An example ofnontransitivity is that tuples t
′ and t
′
′ are redundant to each other, and t
′ and t
′
′ are redundant as well, but t and t
′
′ are not redundant. In this case, the result of redundancy removal will be {
t
,
t
′
′
} if t
′ is deleted first, which differs from the one-tuple result (either {
t
} or {
t
′
′
}) when first deleting the tuples other than t
′. The nontransitivity makes the result of redundancy removal order sensitive and hinders the lossless join decomposition.Nevertheless, most well-defined similarity measures [7, 10, 20, 29] for the values of possibility distribution are reflexive and symmetric but not transitive. For example, consider adopting (4) to measure the similarity of tuples. Given three values π
A
=
{
0.6
/
u
1
,
1.0
/
u
2
,
0.6
/
u
3
}, π
A
′
=
{
1.0
/
u
1
,
1.0
/
u
2
,
0.6
/
u
3
}, and π
A
′′
=
{
1.0
/
u
1
,
0.6
/
u
2
,
0.6
/
u
3
}, then we have ξ
2
(
π
A
,
π
A
′
)
=
1, ξ
2
(
π
A
′
,
π
A
′′
)
=
1, and ξ
2
(
π
A
,
π
A
′′
)
=
0.6. Considering tuples t
=
(
π
A
), t
′
=
(
π
A
′
), and t
′′
=
(
π
A
′′
), we have η
(
t
,
t
′
)
≥
α and η
(
t
′
,
t
′′
)
≥
α but η
(
t
,
t
′′
)
<
α for any α
>
0.6 according to (10). Thus, the similarity measure of tuples is not transitive.In generalizingprojection andequal join operations of traditional database to fuzzy databases, when the redundancy removal is order sensitive, it is hard to obtain lossless join decomposition. Consider the case that Y
~
>
Z holds in the instance r
(
R
) of relation R
(
X
,
Y
,
Z
) based on Definition 1; namely, η
(
t
[
Y
]
,
t
′
[
Y
]
)
≦
η
(
t
[
Z
]
,
t
′
[
Z
]
) for every t
,
t
′
∈
r
(
R
). Assuming that r
(
R
) consists of three tuples 〈
x
1
,
y
,
z
〉, 〈
x
2
,
y
′
,
z
′
〉, 〈
x
3
,
y
′
′
,
z
′
′
〉 and X is a key attribute, it is possible that the two values in each of pairs (
y
,
y
′
), (
y
,
y
′
′
), (
z
,
z
′
), and (
z
,
z
′
′
) are redundant to each other, but (
y
′
,
y
′
′
) and (
z
′
,
z
′
′
) are not. Since Y
~
>
Z, R should be decomposed to avoid redundancy. After decomposing R
(
X
,
Y
,
Z
) to R
′
(
X
,
Y
) and R
′
′
(
Y
,
Z
), if tuple 〈
y
,
z
〉 is first removed because it is redundant to tuple 〈
y
′
,
z
′
〉, the result of R
′
′
(
Y
,
Z
) contains two tuples 〈
y
′
,
z
′
〉 and 〈
y
′
′
,
z
′
′
〉. The natural join of R
′
(
X
,
Y
) and R
′
′
(
Y
,
Z
) generates a four-tuple result 〈
x
1
,
y
,
z
′
〉, 〈
x
1
,
y
,
z
′
′
〉, 〈
x
2
,
y
′
,
z
′
〉, 〈
x
3
,
y
′
′
,
z
′
′
〉, which contains spurious tuple.To resolve this problem, this study proposes the operations ofprojection andequal join for the fuzzy databases, which involves evaluation of redundancy and tuple merging. Since the decomposition of relations is based on FFD, it depends on the similarity of tuples. For the data in the fuzzy model, (3)–(9) can be used to measure the similarity of tuples and define FFDs in the fuzzy databases. However, (5) restricts redundant tuples to those duplicate. Equations (3), (4), and (6) lack transitivity. Therefore, this work adopts (9) and (10) to defineapproximate equality for the tuples that might not be identical but have high similarity degree. Theapproximate equality enables obtaining a unique result of redundancy removal.Definition 2 (approximately equal tuples).
Two tuplest
=
(
π
1
,
π
2
,
…
,
π
m
) and t
′
=
(
π
1
′
,
π
2
′
,
…
,
π
m
′
) are approximately equal, denoted by t
≅
t
′, if it is satisfied that min
⁡
j
=
1
,
…
,
m
{
ξ
5
(
π
j
,
π
j
′
)
}
=
1.In other words, tuplest and t
′ are approximately equal if their similarity η
(
t
,
t
′
)
=
1.Lemma 3.
The approximate equality of tuples (or attribute values) is transitive.Proof.
Based on (9), it is obvious that if ξ
5
(
π
A
,
π
B
)
=
1 and ξ
5
(
π
B
,
π
G
)
=
1, then ξ
5
(
π
A
,
π
G
)
=
1. Thus, if t
≅
t
′ and t
′
≅
t
′′, then t
≅
t
′′ based on (10).The tuples ofapproximate equality are considered to be redundant to each other. The notion of approximate equality can be applied to query processing with the predicate containing fuzzy concept [36] for fuzzy databases in different models. For simplicity, we let π
A
≅
π
B denote ξ
5
(
π
A
,
π
B
)
=
1 hereafter.Example 4.
Given valuesπ
A
=
{
0.75
/
pretty
,
0.65
/
cuteness
} and π
B
=
{
0.6
/
pretty
,
0.7
/
charm
,
0.8
/
cuteness
} on domain D and equivalent classes C
1
=
{
pretty
} and C
2
=
{
charm
,
cuteness
} for D, the average possibilities of π
B are u
-
B
1
=
0.6
/
1
=
0.6 and u
-
B
2
=
(
0.7
+
0.9
)
/
2
=
0.8, yielding π
~
B
=
{
0.6
/
pretty
,
0.8
/
charm
,
0.8
/
cuteness
}. Likewise, u
-
A
1
=
0.8, u
-
A
2
=
0.65, and π
~
A
=
{
0.75
/
pretty
,
0.65
/
charm
,
0.65
/
cuteness
}. We have δ
(
π
A
,
π
B
)
=
(
0.6
+
0.65
+
0.65
)
/
(
0.6
+
0.8
+
0.8
)
=
0.86 and δ
(
π
B
,
π
A
)
=
1.9
/
2.05
=
0.92. Thus, ξ
5
(
π
A
,
π
B
)
=
min
⁡
{
0.86
,
0.92
}
=
0.86. Given π
G
=
{
0.6
/
pretty
,
0.65
/
charm
,
0.85
/
cuteness
} on D, we have π
G
≅
π
B even though π
G is not identical to π
B.Proposition 5.
The approximate equality can be used to classify values of the fuzzy database into disjoint sets (equivalence classes).Proof.
Based on the definition of (9), it is obvious that ξ
5 isreflective andsymmetric; that is, ξ
5
(
π
A
,
π
A
)
=
1 and ξ
5
(
π
A
,
π
B
)
=
ξ
5
(
π
B
,
π
A
) for values π
A and π
B. Besides, approximate equality istransitive according to Lemma 3. Therefore, two different sets of approximately equal values are either disjoint sets or same class sets, where any two of the values are approximately equal to each other.The transitivity of similarity measure is important to any operation involving redundancy removal or tuple merging. Besides, the measure of transitivity can be applied to clustering methods or data groupings, such as the ones in [36, 37].Proposition 6.
Givenπ
A and its adjusted value π
~
A  following (8), π
A
≅
π
~
A.Proof.
It is obvious by the definition of (9).Buckles and Petry first proposed the way of tuple merging and applied it to remove redundant tuples in a fuzzy database [5]. Tuple merging can also be used at join operation. This study extends the tuple merging of Chen et al. [16] to be (11) for relation combination as well as redundancy removal. Given tuples t
=
(
π
A
1
,
π
A
2
,
…
,
π
A
m
) and t
′
=
(
π
A
1
′
,
π
A
2
′
,
…
,
π
A
m
′
), tuple merging of t and t
′, denoted by t
∘
t
′, is given by
(11)
t
∘
t
′
=
(
π
~
A
1
∪
F
π
~
A
1
′
,
π
~
A
2
∪
F
π
~
A
2
′
,
…
,
π
~
A
m
∪
F
π
~
A
m
′
)
,
where each π
~
• (or π
~
•
′) is the adjusted value of π
• (or π
•
′) according to (8) and ∪
F denotes fuzzy union. For single-value tuples t
=
(
π
A
1
) and t
′
=
(
π
A
1
′
), tuple merging is alternatively denoted by π
A
1
∘
π
A
1
′.Lemma 7.
Letπ
A and π
A
′ be two possibility distributions on the same domain. If π
A
≅
π
A
′, then π
A
≅
π
A
∘
π
A
′
≅
π
A
′.Proof.
Based on (9) and (11), it is obvious that if ξ
5
(
π
A
,
π
A
′
)
=
1, then ξ
5
(
π
A
,
π
A
∘
π
A
′
)
=
1 and ξ
5
(
π
A
′
,
π
A
∘
π
A
′
)
=
1.Based on the literature review and Lemma7, we summarize the property of different similarity measures with threshold α
=
1 in Table 3 to show the merit of (9) adopted in this work.Table 3
Property of different similarity measures with thresholdα
=
1.
Properties∖measures
Equation (5) [16]
Equation (6) [20]
Equation (9) [13]
Transitivity
Yes
No
Yes
Result after merging
Lossless
Non-lossless
Approximate lossless
Predicates for lossless join
Identical values
Different values
Different values


## 4. Approximate Lossless Join Decomposition

This section first offers the operations for relation decomposition and combination. Then, it proposes a notion ofapproximate lossless join decomposition (ALJD), which incorporates fuzzy concepts into lossless join decomposition. It also provides the method to achieve the ALJD.Similar to the works in [37], this study generalizes theprojection andnatural join operations in traditional database to the fuzzy databases, as below. Here, given a relation R, Θ denotes a set of attributes in R (i.e., Θ
⊂
R), and t
[
Θ
] denotes the composite of values in tuple t over attribute Θ. For example, given t
∈
r
(
R
), t
=
(
π
A
1
,
π
A
2
,
…
,
π
A
m
), and Θ
=
(
A
2
,
A
3
,
A
4
), then t
[
Θ
]
=
(
π
A
2
,
π
A
3
,
π
A
4
).Projection. Projecting the instance of relation R on attributes Θ
⊂
R, denoted by Π
Θ
(
R
), is given by
(12)
Π
Θ
(
R
)
=
{
t
[
Θ
]
∘
t
′
[
Θ
]
:
t
[
Θ
]
≅
t
′
[
Θ
]
∣
t
,
t
′
∈
r
(
R
)
}
.Natural Join. Natural join instances of R
(
X
,
Y
) and R
′
(
Y
,
Z
), denoted by R
⊗
R
′, are defined as follows:
(13)
R
⊗
R
′
=
{
(
t
[
X
]
,
t
[
Y
]
∘
t
′
[
Y
]
,
t
′
[
Z
]
)
:
t
[
Y
]
≅
t
′
[
Y
]
∣
t
∈
r
(
R
)
,
t
′
∈
r
(
R
′
)
}
.
In (12) and (13), tuple redundancy is determined by approximate equality (e.g., t
[
Y
]
≅
t
′
[
Y
]; see Definition 2), and both redundancy removal and tuple combination use tuple merging in (11).Proposition 8.
The projection result of a relation based on (12) must be unique.Proof.
It can be directly derived from Proposition5.Based on the operations (12) and (13), the ALJD is formally defined following the extension of approximate equality from tuple level to relation level in Definition 9.Definition 9 (approximately equal relation instances).
Two relation instancesr
(
R
) and r
′
(
R
) in the fuzzy database are approximately equal, denoted by r
(
R
)
≈
r
′
(
R
), if for every tuple t
∈
r
(
R
), there must exist a tuple t
′
∈
r
′
(
R
) such that t
≅
t
′ and vice versa.Definition 10 (approximate lossless join).
A composition{
R
1
,
R
2
,
…
,
R
k
} of a relation R in the fuzzy database is approximate lossless join if r
(
R
)
≈
(
Π
R
1
(
R
)
⊗
Π
R
2
(
R
)
⊗
⋯
⊗
Π
R
k
(
R
)
).The approximate lossless join decomposition means the natural join of all decomposed results of a relation instance is approximately equal to the original relation instance. More specifically, every tuple in the original relation isapproximately equal to one of tuples in the combination result.Proposition 11.
Consider the following:(14)
Π
Θ
(
R
)
≈
{
t
[
Θ
]
t
∈
r
(
R
)
}
.Proof.
It can be derived from (11) and (12).Corollary 12.
Consider the following:(15)
Π
R
(
R
)
≈
r
(
R
)
.Proof.
It can be derived directly from Proposition11.The projection of a relation over the same schema, as shown in Corollary12, represents no operations other than removing redundant tuples from the instance of the relation via tuple merging. Corollary 12 shows that the result of redundancy removal of a relation instance is approximately equal to the original instance. This property is essential for obtaining the combination result that is approximately equal to the original instance after relation decomposition.This study proposes FFD for the decomposition in the fuzzy database as shown below.Definition 13.
The FFDX
~
>
Y holds in the relation instance r
(
R
) if r
(
R
) satisfies that, for every t, t
′
∈
r
(
R
); if t
[
X
]
≅
t
′
[
X
], then t
[
Y
]
≅
t
′
[
Y
].Remark 14.
An FD in a traditional database is a special case of the FFD. If a FDX
→
Y holds in r
(
R
), then X
~
>
Y holds as well. It is because t
[
Θ
]
≅
t
′
[
Θ
] must be true for any Θ
⊂
R if t
[
Θ
]
=
t
′
[
Θ
].Lemma 15.
Given relationsR and R
′ and r
(
R
′
)
≈
r
(
R
), if r
(
R
) satisfies a set F of FFDs, then r
(
R
′
) satisfies F.Proof.
Proof by contradiction: we assumed thatr
(
R
′
)
≈
r
(
R
) and there exists an FFD X
~
>
Y such that R satisfies X
~
>
Y and R
′ does not. Because X
~
>
Y exists in r
(
R
),
(16)
for
every
t
1
,
t
2
∈
r
(
R
)
if
t
1
[
X
]
≅
t
2
[
X
]
,
then
t
1
[
Y
]
≅
t
2
[
Y
]
.
Since X
~
>
Y does not exist in r
(
R
′
), there exists t
1
′
,
t
2
′
∈
r
(
R
′
), such that t
1
′
[
X
]
≅
t
2
′
[
X
] and η
(
t
1
′
[
Y
]
,
t
2
′
[
Y
]
)
≠
1. Since r
(
R
′
)
≈
r
(
R
), there exists t
′′
∈
r
(
R
) such that t
≅
t
1
′ and t
′′
≅
t
2
′. Then, we have t
,
t
′′
∈
r
(
R
) and t
[
X
]
≅
t
′′
[
X
] but η
(
t
[
Y
]
,
t
′′
[
Y
]
)
≠
1, which contradicts (16).It is noted that the FFD in Definition13 satisfies Armstrong’s axioms (inference rules), including reflexive rule, augmentation rule, and transitive rule3. This property enables the result oflossless join decomposition that has dependency preservation property4 [1].Lemma 16.
LetR
(
A
,
X
,
Y
) be a relation and X
~
>
Y be an FFD in r
(
R
). If R
1
=
Π
(
A
,
X
)
(
R
) and R
2
=
Π
(
X
,
Y
)
(
R
), then the decomposition {
R
1
,
R
2
} of R has approximate lossless join property.Proof.
We proved that
r
(
R
)
≈
Π
R
1
(
R
)
⊗
Π
R
2
(
R
) based on Definition 10. Let R
′ be a relation such that r
(
R
′
)
=
Π
R
1
(
R
)
⊗
Π
R
2
(
R
). We first prove that, for all t
∈
r
(
R
), there exist t
′
∈
r
(
R
′
) and t
′
≅
t and then prove that, for all t
∈
r
(
R
′
), there must exist t
′
∈
r
(
R
) and t
′
≅
t. Proof by contradiction: let us assume that t
∈
r
(
R
) is the tuple such that no t
′
∈
r
(
R
′
) satisfies t
′
≅
t. Let t
1 and t
2 be tuples such that t
1
=
t
[
A
,
X
] and t
2
=
t
[
X
,
Y
]. Based on Proposition 11, there must be t
^
1
∈
r
(
R
1
) and t
^
2
∈
r
(
R
2
) such that t
^
1
≅
t
1 and t
^
2
≅
t
2 because R
1
=
Π
(
A
,
X
)
(
R
) and R
2
=
Π
(
X
,
Y
)
(
R
). Since r
(
R
′
)
≈
Π
R
1
(
R
)
⊗
Π
R
2
(
R
) and t
1
[
X
]
≅
t
[
X
]
≅
t
2
[
X
], there must exist t
′
∈
r
(
R
′
) such that t
′
≅
(
t
1
[
A
]
,
t
1
[
X
]
∘
t
2
[
X
]
,
t
2
[
Y
]
) according to (13). Also, since t
1
=
t
[
A
,
X
] and t
2
=
t
[
X
,
Y
], we have (
t
1
[
A
]
,
t
1
[
X
]
∘
t
2
[
X
]
,
t
2
[
Y
]
)
≅
(
t
[
A
]
,
t
[
X
]
,
t
[
Y
]
) by Lemma 7. Thus, t
′
≅
t, which contradicts the assumption.
Proof by contradiction for second part with renewed symbols: assume thatt
′
∈
r
(
R
′
) is the tuple such that no t
∈
r
(
R
) satisfies t
′
≅
t. Since r
(
R
′
)
Π
R
1
(
R
)
⊗
Π
R
2
(
R
), there exist t
1
∈
r
(
R
1
) and t
2
∈
r
(
R
2
) such that t
1
≅
t
′
[
A
,
X
], t
2
≅
t
′
[
X
,
Y
], and t
1
[
X
]
≅
t
2
[
X
] based on (13). Also, we let t
^
1 and t
^
2 be the tuples such that
(17)
t
^
1
∈
r
(
R
1
)
,
t
^
2
∈
r
(
R
2
)
,
t
^
1
≅
t
′
[
A
,
X
]
,
t
^
2
≅
t
′
[
X
,
Y
]
.
Since R
1
=
Π
(
A
,
X
)
(
R
), based on Proposition 11, there must exist t
∈
r
(
R
) such that
(18)
t
[
A
,
X
]
≅
t
^
1
.
(19)
Likewise
,
there
must
also
exist
t
′
′
∈
r
(
R
)
such
that
t
′
′
[
X
,
Y
]
≅
t
^
2
.
Based on (17) and (18), we have t
[
X
]
≅
t
′′
[
X
]. Because X
~
>
Y, t
[
Y
]
≅
t
′
′
[
Y
] holds based on Definition 13. Thus, t
[
Y
]
≅
t
^
2
[
Y
]
≅
t
′
[
Y
] based on (19), and t
′
≅
t, which contradicts the assumption.In Lemma16, each one of A, X, and Y could be a single attribute or a set of attributes.Definition 17.
LetF be the set of FFDs. An FFD f
:
X
~
>
Y in F is trivial if there exists an FFD f
’
:
X
~
>
Y
′ in F such that Y
⊂
Y
′.Based on Armstrong’s inference rules, IR1 and IR3 (see endnote 2), if a setF of FFD contains X
~
>
Y
Z, the closure of F will also contain X
~
>
Y and X
~
>
Z, which is trivial. When a relation is decomposed into more relations, it takes more join operations to obtain the original data for query process. Considering the cost of join operations, it is not efficient to decompose a relation that has already been in the third normal form. A relation is in the third normal form if there is no functional dependency between nonkey attributes in the relation [1]. Accordingly, the relation decomposition has two prerequisites as follows.(i)
It needs to avoid decomposing a relation based ontrivial FFDs.
(ii)
It needs to make sure that the decomposed result preserves the closure of FFDs in the original relation.For example, if X is not a key in r
(
R
), then R will be decomposed based on X
~
>
Y
Z rather than on trivial FFD X
~
>
Y or X
~
>
Z. Based on Lemma 16 and Definition 17, we propose an algorithm for ALJD (see Algorithm 1).Algorithm 1:ALJD Algorithm.
InputsR and F, where R is a relation and Fis the set of FFDs exists in r
(
R
).
Step  1. Let R
=
{
R
} and F
′ be the set of all f
∈
F that are not trivial.
Step  2. For a f
′: X~>Y in F
′, Let R
′ be the relation chosen from R such that both X and Y are in R
′.
Step  3. If X is not a key attribute in R
′, do followings:
(1) decomposeR
′ into R
1 and R
2, such that R
1
=
Π
(
X
,
Y
)
(
R
′
) and R
2
=
Π
R
′
(
X
-
)
(
R
′
)
(2) letF
′
=
F
′
-
{
f
′
} (remove f
′ from F
′)
(3) letR
=
R
∪
{
R
1
,
R
2
}
-
{
R
′
}.
Step  4. Go to Step  2 if F
′ is not empty.
Output isR, the set of relations decomposed from R.
Note:R
′
(
X
-
) represents the list of all attributes in R
′ other than X.In the ALJD algorithm, an FFD containing key attributes is excluded from the decomposition process at Step 3. This follows the concept of the normalization of traditional databases, where only the FD of nonkey attributes is considered. To have a consistent presentation of data, this work generalizes the definition of key attributes for the fuzzy databases; namely, an attributeA is akey attribute in R if there does not exist two tuples t and t
′ in r
(
R
) such that t
[
A
]
≅
t
′
[
A
]. The exclusion of processing FFDs containing key attributes can prevent unnecessary decomposing on the relations which have no update anomaly problem. Although the decomposition without the key exclusion is still an ALJD, it increases the cost of the join operations of query process.Proposition 18.
LetR
(
A
,
X
,
Y
) be a relation and let X
~
>
Y be an FFD in r
(
R
). If R
1
=
Π
(
A
,
X
)
(
R
) and R
2
=
Π
(
X
,
Y
)
(
R
), then (i) each FFD existing in r
(
R
1
) or r
(
R
2
) must exist in r
(
R
) and (ii) every FFD existing in r
(
R
) must either exist in r
(
R
1
) or r
(
R
2
) or be derived via FFDs in r
(
R
1
) and r
(
R
2
).Proof.
Statement (i) can be derived by Proposition11 and Lemma 15. Statement (ii) can be derived by Lemma 16 and the property of FFD (namely, Armstrong’s axiom IRs 1, 2, and 3, described at endnote 2).The above statements show that the ALJD also preserves the closure of FFDs in the original relation, which is important to the issues related to the application of FFDs.


## 5. Conclusion

The contribution of this work is threefold. First, it highlights the problem of relation decomposition when tuple elimination is order sensitive. To overcome the problem, it proposes the notion of approximate equality for the tuples or relations in the fuzzy databases and provides the measure of the approximate equality. The measurement is reflexive, symmetric, and transitive. It enables classifying tuples into disjoint sets and ensures that a decomposed relation has unique result after redundancy removal or tuple merging. Therefore, the notion of approximate equality is important for data operations in the fuzzy databases. Second, it proposes approximate lossless join decomposition for the fuzzy databases and defines two operationsprojection andequal join for the decomposition, all of which are based on the approximate equality. The data operations and ALJD can be applied to the issue on data compression in the fuzzy databases. Third, this work defines FFDs and proposes an algorithm to decompose relations in the fuzzy databases based on the FFDs. The decomposition by the algorithm ensures the approximate lossless join property. The FFD and ALJD proposed for the fuzzy databases are, respectively, the general cases of the traditional FD and lossless join decomposition. The general property is important for dealing with the databases containing crisp data and fuzzy data. Forth, similar to the existing approaches of database normalization on resemblance-based fuzzy databases, this study provides several propositions to prove that the proposed approach of decomposition satisfies a degree of lossless join property. Compared to the normalization approaches for resemblance-based fuzzy databases, achieving lossless join decomposition for the extended possibility-based fuzzy databases is more difficult because of having more complex data.There are some directions of future work. Future study can adopt the notion of approximate equality to define data operations for the query processing in the fuzzy databases. Research can apply the notion on the research related to data compression, fuzzy association rules, missing value prediction, relation compactness, and the integrity constraint in the fuzzy databases. Study aims to incorporate the fuzzy concept into clustering methods or data groupings for decision-making in marketing, healthcare applications, or business operations that can adopt the approximate equality for the similarity measures. Since the fuzzy concept has been incorporated into object-oriented databases in literature, future work can provide the approximate equality specifically for the data in the fuzzy object-oriented data models.



---

*Source: 842680-2014-08-21.xml*