Annotations are relative

Peter Buneman, Egor V. Kostylev, Stijn Vansummeren

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Most systems that have been developed for annotation of data assume a two-level structure in which annotation is superimposed on, and separate from, the data. However there are many cases in which an annotation may itself be annotated. For example threads in e-mail and newsgroups allow the imposition of one comment on another; belief annotations can be compounded; and valid time, regarded as an annotation can be freely mixed with belief annotations (at time t1, B1 believed that at time t2, B2 believed that...).

In this paper we describe a hierarchical model of annotation in which there is no absolute distinction between annotation and data. First, we introduce a term model for annotations and, in order to express the fact that an annotation may apply to two or more data values with some shared structure, we provide a simple schema for annotation hierarchies. We then look at how queries can be applied to such hierarchies; in particular we ask the usual question of how annotations should propagate through queries. We take the view that the query together with schema describes a level in the hierarchy: everything below this level is treated as data to which the query should be applied; everything above it is annotation which should, according to certain rules, be propagated with the query. We also examine the representation of annotation hierarchies in conventional relational structures and describe a technique for annotating datalog programs.

Original languageEnglish
Title of host publicationProceedings of the 16th International Conference on Database Theory
Place of PublicationNew York, NY, USA
Number of pages12
ISBN (Print)978-1-4503-1598-2
Publication statusPublished - 2013


  • annotation
  • provenance
  • terms

Cite this