On Database Query Languages for K-relations

The relational model has recently been extended to so-called K-relations in which tuples are assigned a unique value in a semiring K. A query language, denoted by RACK, similar to the classical positive re-lational algebra, allows for the querying of K-relations. In this paper, we define more expressive query languages for K-relations, that extend RACK to express operations on annotated tuples that are natural ex-tensions of corresponding operations of the relational algebra, namely difference and constant annotations. We investigate conditions on semirings under which these operations can be added in a natural way, and establish basic properties of these query languages. Moreover, we show how the provenance semiring of Green et al. can be extended to record provenance of data in the presence of difference and constant anno-tations. Finally, we investigate completeness of RACK and extensions thereof in the sense of Bancilhon and Paredaens (BP)