Annotated Data and Uncertain Databases
Todd J. Green
University of Pennsylvania

ABSTRACT
   In this talk, I will discuss semiring-annotated relations and show
   how they can be used fruitfully as a unifying formalism for various
   kinds of ``uncertain'' databases, including incomplete databases,
   probabilistic databases, fuzzy databases, 4-valued logic databases,
   and data integration systems with probabilistic mappings.  I will
   discuss an extension to semiring-annotated XML and show two novel
   applications in that context, incomplete XML and XML with access
   control annotations.  I will illustrate how some of these concepts
   are being put into practice in Orchestra, a collaborative data
   sharing system under development at Penn.  Finally, I will discuss
   query optimization for databases with semiring annotations, and
   present a number of positive decidability results for query
   containment and equivalence.