This paper is situated in the area of the so-called fuzzy databases, i.e., databases containing imprecise information. It is now recognized that querying databases containing imperfect information raises several problems, including complexity. In this paper, we consider a specific kind of queries, called possibilistic queries, of the form “to what extent is it possible that a given tuple t belongs to the answer of Q (a regular relational query).” The major objective is to show that a reasonable complexity can be expected for a specific (although not too restricted) subset of possibilistic queries.