Describe the theory of Fuzzy Querying to Relational Databases?

Answer 1

They are used to query to fuzzy databases that are enhanced

from relational databases in a way that fuzzy sets are allowed in

both attribute values and truth values. A fuzzy calculus query

language is constructed based on the relational calculus and

a fuzzy algebra query language is also constructed based on

the relational algebra. In addition, this paper proves a fuzzy

relational completeness theorem such that both the languages

have equivalent expressive power to each other.

Index Terms-Fuzzy database, query languages, relational algebra,

relational calculus, relational completeness.

I. INTRODUCTION

DA TABASE technology has been advanced up to the relational database stage with the purpose that user

interfaces with databases may approach a level of human

interfaces. It is recognized that the fuzzy theory is suitably

applied to some human-oriented engineering fields, one

FUZZY database

..._________________------.---

Select Name where Name I Age I Tuple truth

Age i "vepy young", iiiiiiiiii=j*iiiiiiiiii..=iiii

__....--___> __To. _I_ Youns _I_ t_r u e_ ...----

(---.-...-----------...----- Mary I 30 I 0.7

Tom: A r e = " ~ o u n g ' . Bob I mBddle I nearly 0 . 5

John Inearlr 401 quite true

Ron I old I 0.3

..____________________________

Fig. 1. A query to a fuzzy database.

11. A FUZZY DATABASE MODEL

A fuzzy database is defined as an enhanced relational

database that allows fuzzy attribute values and fuzzy truth

values; both of these are expressed as fuzzy sets. An example

of the fuzzy database is shown in Fig. 1.

of which is information processing, in particular database

retrieval. In fact, fuzzy database models that allow fuzzy

attribute values and fuzzy truth values in enhanced relational

databases have been studied in [3] and [4]. However, these

studies are restricted to just some particular applications and

not grounded on theories of fuzzy database query languages.

Thus fuzzy database systems would not be systematically

developed on the basis of these studies; it is due to Codd's

relational database theory that relational database systems have

been systematically developed. It is desirable that theoretical

foundations of fuzzy databases be established in order to

systematically develop fuzzy database systems.

fuzzy database theory; it develops a theoretical foundation for

the fuzzy functional dependencies of fuzzy databases [I]. The

work encourages further research for the rest of theoretical

foundations of fuzzy databases. This paper thus aims to

databases. It proposes two fuzzy database query languages:

a fuzzy calculus query language and a fuzzy algebra query

language. In addition, it proves a relational completeness theorem

such that both the languages are equivalent in expressive

power to each other. With these theoretical foundations, fuzzy Truth Of any tup1es are either (= true) Or (=

database query systems will be developed systematically.

A. Data

A fuzzy database consists of relations: a relation is a relation

R(tl, ,tn) in a Cartesian product PI x PZ x ... x P, of

domains Pi; each P, is a set of fuzzy sets t, over an attribute

domain D, (1 5 i 5 n). It is assumed that key attributes

take ordinary nonfuzzy values. For the notational convenience,

fuzzy sets are identified with their representative membership

functions; for example, t; also denotes a membership function.

B. Fuzzy Attribute Values

Attribute values such as age have nonfuzzy values such as

fuzzy predicates such as ccyoung9a9n d <Gabout forty" in the

fuzzy database. For example, a fuzzy attribute value of "age

of Dr. x is is expressed as a possibility distribution

p (age of x) = YOUNG; YOUNG denotes a fuzzy set that

are identified with fuzzy sets such as YOUNG.

c. Fuzzy

in the relational database; truth values of any tuples are defined

as fuzzy predicates such as "0.7" and "completely true" in the

fuzzy database. Consider, for example, a tuple t that asserts

a fuzzy proposition: "It is completely true that Dr. x iS Very

much older than twenty." The truth value of t is expressed as

a possibility distribution P[T(t)]= N; T( t )d enotes a truth

value o f t and N denotes a fuzzy set that represents the fuzzy

an work has been done in the Of the 20 in the relational database; attribute values are defined as

a foundation of query languages to represents the fuzzy predicate "young." Thus attribute values

Manuscript received November 21, 1989; revised September 6, 1991 and

The author is with NlT Network Information Systems Laboratories,

IEEE Log Number 9205829.

May 29, 1992.

Kanagawa, Japan.

1041-4347/93$03.00 0 1993 IEEE

Authorized licensed use limited to: University of Tehran. Downloaded on May 29,2010 at 10:52:24 UTC from IEEE Xplore. Restrictions apply.

TAKAHASHI: FUZZY DATABASE QUERY LANGUAGES 123

predicate "completely true." Thus the truth values T(t) are

identified with fuzzy sets such as N over z E [0,1]; the value

z E [0,1] has the following meaning.

1) z = 0 means that the tuple t is completely false.

2) 0 < z < 1 means that the tuple t is true to the degree

3) z = 1 means that the tuple t is completely true.

In particular, each tuple t of the relation R(t1, . . . , tn) is

given a unique truth value T(t) by system designers at system

generation time. In this case, T(t) determines a mapping

T :P I x PZ x . . . x Pn + P([O1, 1) where P([O,1 1) is a set

of fuzzy sets over z E [O, 11.

expressed by the real number z.

111. QUERY BY TUPLE FUZZY CALCULUS

A. Tuple Fuzzy Calculus

A tuple fuzzy calculus (query language) is constructed as

an enhancement of the tuple relational calculus. Formulas in

the tuple fuzzy calculus are of the form ( t l f ( t ) )t: i s a fuzzy

tuple variable each ith component ti, which is a fuzzy set in

P;; f is a tuple fuzzy well-formed formula (WFF).

Tuple fuzzy WFF's are enhanced from those of the tuple

relational calculus as follows.

1) Atomic Tuple Fuzzy WFF's: An atomic tuple fuzzy

WFF consists of fuzzy sets and a fuzzy comparison operator *.

The fuzzy comparison operator * is one of the operators: equal;

not equal; proper inclusion; inclusion. The fuzzy comparison

operator * is an enhancement from the arithmetic comparison

operator (=, #, <, >, 5,z) in the relational calculus. Then

the atomic tuple fuzzy WFF's are either of the following two

types:

1) (t;)* ( s j ) ; here, it is assumed that t and s are fuzzy tuple

variables such that D; = Dj (1

2 ) (ti)* (c), (c) * (ti);h ere, it is assumed that c is a fuzzy

set over D;.

2) Logical Connectives and Quantifiers: Logical connectives

("AND," "OR," and "NOT") are used for tuple fuzzy

WFF's.

Also, quantifiers ("for all" and "there exists") are used for

tuple fuzzy WFF's.

3) Others: Other definitions concerning tuple fuzzy WFF's

are the same as in the tuple relational calculus.

Thus tuples in any relation R(tl,. . . , tn) that satisfy the

formula { t l f ( t ) }fo rm a set of Cartesian products of fuzzy

sets.

It should be considered further whether or not to include

fuzzy comparison operators * expressed by fuzzy relations

such as "much greater than," "is close to," "is similar to," and

"is relevant to."

i , j 5 n).

B. Query Evaluation

Queries expressed in the tuple fuzzy calculus are evaluated

by two steps as follows.

(Step 1) Selecting resultant tuples: Consider that the query

{tlf(t)} is issued to the relation R(t1,. . . , tn). Resultant

tuples are those r E R(t1, + . . , tn) each of which satisfies

the formula f(r).

(Step 2) Calculating truth values of resultant tuples: Let

any resultant tuple r be expressed as rkl . . . T k j ' . . rk, and

r be a projection of t E R(t1,. . . , tn) onto the components

ICl,...,ICj,...,km (1 5 m 5 n , l 5 k l , . . . , k j , . . . , k , 5

n). Then the truth value T(r) is defined as a projection of T(t)

onto the components k l , . . . , k j , . . . IC,: T(r) = Max .T(t),

where the maximum is taken over those components tk (1 5

Duplicate removal schemes are out of the scope of this paper

and left for future work: if two tuples T I , r2 having different

truth values T( r l ) ,T (r2)a re found to be duplicated, it is left

up to fuzzy database designers which one will be selected. The

fuzzy database designers will also choose which tuples from

the resultant tuples r should be returned to the users:

1) full sets or appropriate subsets of resultant tuples r should

be returned;

2) tuples r that contain truth values T(r) should be returned;

or when users need not make use of truth values T ( r ) ,tu ples r ,

from which truth values T(r) are removed, should be returned.

k 5 n), such that tk # tkj.

IV. QUERY BY DOMAIN FUZZY CALCULUS

A domain fuzzy calculus (query language) is obtained from

1) replacement of tuple variables t with domain variables,

2) replacement of the ith tuple component ti with a domain

the tuple fuzzy calculus through the following replacements:

211212.. . ,Un;

variable ui (1 5 i 5 n).

V. QUERY BY FUZZY ALGEBRA

A. Fuzzy Algebra

A fuzzy algebra (query language) is constructed as an

enhancement of the relational algebra. Fundamental fuzzy algebraic

operations are union, set difference, Cartesian product,

projection, and selection, which are defined as follows.

I ) Union: Let R and S denote any relations in the fuzzy

database. The union of R and S is a set of tuples that belongs

to R or S. The union is equal to that in set theory.

Any resultant tuple t by the union of R and S inherits the

truth value T(t) from its original tuple in R or S.

2) Set Difference: The difference R - S of R from S is a

set of tuples, each of which belongs to R and does not belong

to S. The difference is equal to that in set theory.

Any resultant tuple t by the set difference R - S inherits

the truth value T(t) from its original tuple in R.

3) Cartesian Product: The Cartesian product R x S of R

and S is a set of tuples, {(r, s ) l r : tuple in R, s: tuple in S}.

The Cartesian product is equal to that in set theory.

The truth value T(t) of the resultant tuple t = (rl s) by the

Cartesian product R x S is the minimum of T(r) and T(s)

where T(r) and T(s) are truth values of r and s, respectively.

4) Projection: The projection Proj(IC1, . . . , kj, . . . , k,)(R)

of R onto the lcjth attributes is a set of tuples of the lcjth

attribute values. The projection is equal to that in set theory.

Let r denote any resultant tuple of the projection

Proj(i1,i z,. . . , im) (R)o f t E R. Then the truth value T( r )i s

Authorized licensed use limited to: University of Tehran. Downloaded on May 29,2010 at 10:52:24 UTC from IEEE Xplore. Restrictions apply.

-

124 IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 5, NO. 1, FEBRUARY 1993

the maximum of T(t) taken over those components tk, such

5) Selection: Let G denote a fuzzy WFF involving the

i) operands that are constant fuzzy sets and attribute item

ii) the fuzzy set comparison operators * (equal, not equal,

iii) logical connectives "OR," "AND," and "NOT."

The selection SelG(R) of the relation R is a set of tuples

t in R each of which satisfies the fuzzy WFF G when any

occurrences of the number i in G are replaced with the ith

component of T in R.

When any resultant tuple T is made by the selection

SelG(R)t, E R inherits the truth value T( t )f rom the original

tuple t in R: T(T) = T(t).

Some additional fuzzy algebraic operations such as intersection,

quotient, &join, and natural join are defined as

combinations of the fundamental fuzzy algebraic operations

defined previously in the same way as in the relational algebra.

For example, the &join and the natural join are defined as

follows.

6) 0-Join: The &join of R and 5' is defined as a combination

of two fundamental fuzzy algebraic operations: the

Cartesian product and the selection where 8 is enhanced

to a fuzzy comparison operator * (equal, not equal, proper

inclusion, inclusion). Truth values of resultant tuples by the

&join are calculated as those of combinations of the two

fundamental fuzzy algebraic operations.

7) Natural Join: The natural join of R and S is defined as a

combination of three fundamental fuzzy algebraic operations:

the Cartesian product, the selection, and the projection. Truth

values of resultant tuples by the natural join are calculated as

those of combinations of the three fundamental fuzzy algebraic

operations.

that tk # tkj.

following constituents:

numbers of the relation R;

proper inclusion, inclusion);

B. Que? Evaluation

Any query by the fuzzy algebra is expressed as a combination

of the fundamental fuzzy algebraic operations. Thus the

resultant tuples T and their truth values T ( T )by this query are

obtained as combinations of its constituent fundamental fuzzy

algebraic operations.

Duplicate removal schemes and return methods of resultant

tuples to users are the same as described in the fuzzy calculus.

VI. RELATIONACLO MPLETENESTSH EOREM

FOR FUZZY DATABASE QUERY LANGUAGES

The relational database theory establishes the relational

completeness theorem such that the relational calculus is

equivalent in expressive power to the relational algebra [2].

A similar theorem in the fuzzy database is given.

Theorem: The following three fuzzy database query languages

have the same expressive power:

1) tuple fuzzy calculus;

2) domain fuzzy calculus;

3) fuzzy algebra.

Proof: The fundamental idea of the proof of this theorem

is given by Ullman [2, pp. 114-1221; it presents the proof of

the relational completeness theorem for the relational database

query languages. Ullman's proof techniques consist of the

following three reduction techniques:

i) reduction of the relational algebra to the tuple relational

calculus;

ii) reduction of the tuple relational calculus to the domain

relational calculus;

iii) reduction of the domain relational calculus to the relational

algebra.

The reduction technique ii) is just the transformation between

variable expressions, and thus is not influenced by the

enhancements of the fuzzy database query languages. Therefore,

it should be proved here that the reduction techniques i)

and iii) can also be extended to cover the enhancements of the

fuzzy database query languages.

There are two essential enhancements in the fuzzy database

query languages from the relational database.

1) The fuzzy database allows fuzzy sets as attribute values;

the fuzzy comparison operators * (equal, not equal, proper

inclusion, inclusion) are used in the fuzzy database query languages

instead of the arithmetic comparison operators (=, #

, <, > ,z2,) used in the relational database query languages.

2) The fuzzy database allows fuzzy sets as truth values

T(t),t E R; truth values T(r) of resultant tuples T are

inherited from T(t) of original tuples t E R, or calculated

as combinations of Cartesian products or projections of T(t)

of original tuples t E R.

The enhancement 1) is easily incorporated into the reduction

techniques i) and iii) by replacing the arithmetic comparison

operators with the fuzzy comparison operators.

Next, consider the enhancement 2). Remember that the truth

value T(t) of the tuple t is defined just depending on the fuzzy

set and fuzzy set operations that have been established in fuzzy

theory; calculations of T(r) are made independently of any of

the definitions of the fuzzy database query languages. Thus the

reduction techniques i) and iii) can be extended to incorporate

the enhancement 2). This completes the proof. QED

VII. CONCLUDINGR EMARKS

This paper proposes two fuzzy database query languages

(fuzzy relational calculus and fuzzy relational algebra)

based on the relational database query languages. In

addition, it proves the relational completeness theorem

such that both the languages are equivalent in expressive

power to each other. As in the case of the relational

database, this relational completeness theorem in the fuzzy

database is expected to provide a criterion for the

minimum fuzzy database query capability that must be

implemented in any reasonable real fuzzy database query

languages.

There are interesting further theoretical studies still left.

More complicated fuzzy queries, including more general fuzzy

comparison operators such as "much greater than," and "is

close to", need to be studied. Such queries include, for

example, a statement "select several persons where their age is

Authorized licensed use limited to: University of Tehran. Downloaded on May 29,2010 at 10:52:24 UTC from IEEE Xplore. Restrictions apply.

TAKAHASHI: FUZZY DATABASE QUERY LANGUAGES 125

a little over than that of v,o ung bovs." Other studies need to be 131 M. Umano. "Relational algebra in fuzzy database," IEICE Tech. Rep. U , . >

devoted to duplicate removal schemes and query optimization cih Japanese) v01r86, no. 192>-PP. 1986.

[4] M. Zemankova-Leech and A. Kandel, "Fuzzy relational databases-A techniques to improve execution efficiency of the fuzzy query key to expert systems," Verlag TUV Rheinland GmbH, 1984. I . -

languages; both of these are completely out of the scope of

this paper though these are essential to the fuzzy database.

Practically, there also should be an interesting further study

how to implement the fuzzy database query languages in this

paper by extending the existing real relational database query

languages, such as the international standard database language

SQL.

REFERENCES

[l] K. V. S. V. N. Raju and A. K. Majumdar, "Fuzzy functional dependencies

and lossless join decomposition of fuzzy relational database

systems," ACM Trans. Database Sysr., vol. 13, no. 2, pp. 129-166, June

1 OR!?

Yoshikane Takahashi received the M.Sc. degree in

mathematics from the University of Tokyo, Tokyo,

Japan in 1975.

He is currently with NlT Network Information

Systems Laboratories, Kanagawa, Japan. His

research fields include communications protocol,

fuzzy theory, neural networks, nonmonotonic logic,

genetic algorithms, and knowledge information theory.

Mr. Takahashi was awarded the Moto-oka Commemorative

Award in 1986. He is a member of the

[Z] J. D. Ullman, Principles of Database Systems. Rockville, MD: Com- Japanese Institute of Electronics, Information, and Communication Engineers,

puter Science, 1980. and the Information Processing Society of Japan.

Authorized

Answer 2

Fuzzy querying in relational databases involves retrieving results that are approximate or similar to the query conditions specified by the user. This can help account for variations, typos, or inaccuracies in the data. Fuzzy querying usually involves techniques like similarity matching, partial matching, or using fuzzy logic to provide more flexible and inclusive search results.