There is a large body of work on Boolean provenance for database queries (e.g., [1]}, [2]}, [3]}, [4]}, [5]}, [6]}, [7]}, [8]}). The basic paradigm is that one starts by associating a Boolean variable with every tuple in the input database; then, for queries in a given language (say, Select-Project-Join-Union), we explain how the query operators can be extended to annotate their results with Boolean expressions depending on the input tuples. For instance, for the join operation, a tuple obtained by the joining two tuples annotated by \(x\)  and \(y\)  will be annotated by \(x \wedge y\) . If we union two relations and the same tuple occurs in both with annotations by \(x\)  and \(y\) , then the tuple in the (set) union of the two relations will be annotated by \(x \vee y\) . A basic property of such provenance structures, dating back to [7]}, is that these provenance expressions describe the Possible Worlds that make the query true: a truth valuation \(v\)  of the Boolean variables satisfies the provenance expression annotating a tuple \(t\)  if and only if \(t\)  appears in the query result when running the query over the sub-database consisting only of the tuples annotated by variables that \(v\)  maps to True.
