Combining dependent annotations for relational algebra

Annotation is some form of data that is added to an existing database. It could be additional data that for whatever reason cannot be stored in the original database, or it could be some form of metadata such as comments, probabilities, timestamps that are not normally regarded part of the basic database design. It has recently been observed that, in order to determine how annotations should be propagated through database queries, we need to have some structure on them. Although various forms of annotation have been considered in some detail, each form has been considered in isolation.

In this paper we consider what happens when different forms of annotation are combined. We show that there are many cases in which annotations, for quite natural reasons, depend on one another. What is the appropriate structure to place on such annotations? We provide a method for combining different forms and provide a normal form which is useful in deciding whether two or more combined annotations are equivalent.