Abstract

We study concepts and techniques for modeling and processing uncertain relations. Intuitively a piece of data is uncertain if its truth is not established definitely. Similarly, a relation is uncertain when its true state is not ascertained. A major source of difficulties is the semantics of uncertain relations defined based on the notion of possible worlds, which is a set of standard relations one of which represents the true state of the real world data but we don't know which one. This has posed serious challenges for over two decades in database and AI research, however, the topic has gained revived attention in database community again due to some emerging applications such as sensor networks, surveys and imputation techniques, and privacy-preserving data mining applications that require storing and processing such data effectively. Our work is motivated by and concerned with practical issues affected by the exponential number of the possible worlds.
We study existing models and techniques and consider the semiring model, a representation model of annotated relations, to represent uncertain relations in our work. Our choice of model is justified for being equipped with an algebra for evaluating queries over annotated relations. We illustrate how the model lends itself to a framework to study models and algorithms for both uncertain relations and probabilistic relations in a unified manner. The ideas and solutions provide a basis for development of a system for annotated data management.