An initial approach to the evaluation of possibilistic queries addressed to possibilistic databases

It is now recognized that querying databases containing imprecise information raises several problems, including that of the computational complexity of evaluating the query. In this paper, we consider a new kind of query, called possibilistic query, of the form "to what extent is it possible that a given tuple t belongs to the answer of Q", where Q is a regular relational query. The aim is to show that a reasonable complexity can be expected for a specified subset of possibilistic queries. (C) 2003 Elsevier B.V. All rights reserved.