Towards an algebraic query language for possibilistic databases

This paper is situated in the area of databases containing ill-known attribute values represented by possibility distributions. Any such database has a canonical interpretation as a set of more or less possible regular databases, but, it is well known that their manipulation raises a number of problems, in particular with respect to the soundness of querying operations and the tractability of the evaluation process. In this paper, we propose a query language including four operators which are soundly defined on extended possibilistic (compact) relations, which is the key for tractability. The originality of the approach is twofold: i) a nesting mechanism is introduced in the data model in order to support the expression of the result of some of the operations allowed and ii) a join operation enables to compose possibilistic relations under some reasonable hypotheses.