Mondrian
A taint-like provenance system, where some subset of the attributes of a tuple are annotated with one or more markers ("colors" in the paper's terminology) that are persisted through queries. The paper also defines a number of new operators for querying tuples based on these annotations e.g., give me all tuples with a particular color of marker attached. Although they prove the language's completeness (in a tech report), the language is un-intuitive, requiring reasoning about the relationship between sets of attributes being annotated, and the annotation itself. For example, selecting a tuple appears to drop any annotation not marking all attributes appearing in the selection condition.