Possibilistic databases and generalized yes/no queries

This paper is concerned with the handling of imprecise information in possibilistic relational databases. Since the processing of general algebraic queries raises severe problems in terms of tractability in the presence of imprecise information, a specific family of queries called generalized yes/no queries is considered. Their format is: "to what extent is it possible and certain that the answer to Q is nonempty?". A strategy for processing such queries efficiently is proposed under some assumptions as to the operators appearing in the query Q.