A data model and algebra for probabilistic complex values

We present a probabilistic data model for complex values. More precisely, w e introduce probabilistic complex value relations, which combine the concep t of probabilistic relations with the idea of complex values in a uniform f ramework. We elaborate a model-theoretic definition of probabilistic combin ation strategies, which has a rigorous foundation on probability theory. We then define an algebra for querying database instances, which comprises th e operations of selection, projection, renaming, join, Cartesian product, u nion, intersection, and difference. We prove that our data model and algebr a for probabilistic complex values generalizes the classical relational dat a model and algebra. Moreover, we show that under certain assumptions, all our algebraic operations are tractable. We finally show that most of the qu ery equivalences of classical relational algebra carry over to our algebra on probabilistic complex value relations. Hence, query optimization techniq ues for classical relational algebra can easily be applied to optimize quer ies on probabilistic complex value relations.