Abstract
Recently, the call for database management systems (DBMS) with uncertainty capabilities is getting stronger. Many of the existing approaches to modeling uncertainty in database management systems are based on the theory of fuzzy sets. High performance is a necessary precondition for the acceptance of such systems by end users. However, performance issues have been quite neglected in research on fuzzy DBMS so far. In this article they are addressed explicitly. We propose new index structures for fuzzy DBMS based on the well known technique of superimposed coding together with detailed cost models. The correctness of the cost models as well as the efficiency of the index structures proposed is validated by a number of measurements on experimental fuzzy databases