Browse Prior Art Database

Combining Fuzzy Information from Multiple Systems

IP.com Disclosure Number: IPCOM000117437D
Original Publication Date: 1996-Feb-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 4 page(s) / 146K

Publishing Venue

IBM

Related People

Fagin, R: AUTHOR

Abstract

In a traditional database system, the result of a query is a set of values (those values that satisfy the query). On the other hand, in a system that deals with fuzzy information (such as color), the result of a query is a sorted list. For example, the query might ask for objects that are a particular shade of red, and the result of the query would be a sorted list of objects in the database, sorted by how well the color of the object matches that given in the query. A multimedia database system that obtains information from a number of different subsystems must be able to somehow combine these different types of queries. The problem is: 1. how to combine queries that are possibly of different types, and 2. how to resolve such combined queries efficiently.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 32% of the total text.

Combining Fuzzy Information from Multiple Systems

      In a traditional database system, the result of a query is a
set of values (those values that satisfy the query).  On the other
hand, in a system that deals with fuzzy information (such as color),
the result of a query is a sorted list.  For example, the query might
ask for objects that are a particular shade of red, and the result of
the query would be a sorted list of objects in the database, sorted
by how well the color of the object matches that given in the query.
A multimedia database system that obtains information from a number
of different subsystems must be able to somehow combine these
different types of queries.  The problem is:
  1.  how to combine queries that are possibly of different types,
and
  2.  how to resolve such combined queries efficiently.

      The solution to the first problem, of how to combine queries
that are possibly of different types is to treat all data as graded
(or fuzzy) sets.  A graded set is a set of pairs (x, g), where x is
an object (such as a tuple), and g (the grade) is a real number in
the interval (0,1).  It is sometimes convenient to think of a graded
set as corresponding to a sorted list, where the objects are sorted
by their grades.  Thus, a graded set is a generalization of both a
set and a sorted list.

      Define atomic queries to be of the form X = v, where X is
the name of an attribute, and &upsilon.  is a target.  Queries are
Boolean combinations of atomic queries.  For each atomic query, a
grade is assigned to each object.  The grade represents the extent to
which that object fulfills that atomic query, where the larger the
number is, the better the match.  In particular, a grade of 1
represents a perfect match.  For traditional database queries, the
grade for each object is either 0 or 1, where 0 means that the query
is false about the object, and 1 means that the query is true about
the object.  For other queries, such as those about color, grades may
be intermediate values between 0 and 1.  Grades may be assigned to
Boolean combinations of atomic queries by a number of possible
combining rules, including the standard rules of fuzzy logic (where
the grade of an object under a conjunction is the minimum of the
grades of the object under the conjuncts).  Here, simply assume that
there is a scoring function t such that
  1.  the grade of object x under the conjunction A sub 1 and ... and
       A sub m ' 'is' ' t(mu sub <A sub 1> (x),..., mu sub <A sub
       m>(x)), ' 'where' ' mu sub <A sub i> (x) is the grade of
object
       x under query A sub i, and
  2.  t is monotone, which means that t(x sub 1 ,..., x sub m)'
'lesym'
       't (x sub 1 sup prime ,..., x prime sub m )' 'if' ' x sub i '
       'lesym' ' x sub i sup prime for every i.

      Apparently every scoring function t in the literature for
evaluating the conjunction, including the standard scoring...