About the processing of possibilistic queries involving a difference operation

In this paper, the issue of querying databases that may contain ill-known values represented by possibility distributions is considered. The queries dealt with, called possibilistic queries, are of the form: “to what extent is it possible that tuple t belongs to the result of query Q?”, where Q denotes a usual relational query. An evaluation method suited to these queries has been previously proposed, in the case where Q does not include any difference operation. It does not entail making explicit the different possible worlds of the database and therefore, it is possible to avoid the combinatorial growth that would be induced by a “naı¨ve” evaluation method. In this paper, we propose an evaluation process of possibilistic queries that makes it possible, under certain conditions, to deal with the difference operation in query Q, still without making explicit the different worlds associated with the database.