The provenance annotations of the input database can be propagated to the query output, so that Boolean expressions annotating tuples in the query output reflect the possible worlds of the input annotated database for which the output tuple appears in the query result. In particular, Select-Project-Join-Union (SPJU) queries are known to yield provenance in the form of monotone Boolean expressions (without negation), which are computable in DNF (i.e., as disjunctions of conjunctions) in PTIME [1]}. When relational difference is allowed (SPJUD queries), the provenance expressions may also include negation [2]} and may no longer be in DNF.
<FIGURE>