Combining Fuzzy Information From Multiple Systems

Ron Fagin

IBM Almaden Research Center


In a traditional database system, the result of a query is a set of values (those values that satisfy the query). In a system with queries based on image content, 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 system must somehow synthesize both types of queries in a consistent manner. In this talk we discuss the solution adopted by Garlic, a multimedia information system being developed at the IBM Almaden Research Center. This solution is based on "graded" (or "fuzzy") sets. Issues of query optimization in a multimedia system are very different from those in a traditional database system. This is because the multimedia system receives answers to subqueries from various subsystems, which can be accessed only in limited ways. As a first step in dealing with these fascinating new issues, an optimal algorithm for evaluating an important class of Garlic queries is presented. This talk will be completely self-contained.