Definition 2.4 (Provenance for Query results) 

Given an annotated database \(\bar{D} = (D, L)\)  and a query \(Q\)  over \(D\) , the query result is \(Q(\bar{D})=(Q(D), L^{\prime })\)  where \(Q(D)\)  is the standard query result and \(L^{\prime }:Q(D)\!\rightarrow \!\mathrm {Bool}[X]\)  where \(\mathrm {Bool}[X]\)  is the semiring of all Boolean expressions over \(X\)  [1]}, [2]}. For every \(t\in Q(D)\) , and every valuation \(\mathrm {val}\)  over \(X\) , we require that the expression \(\varphi =L^{\prime }(t)\)  is such that \(\mathrm {val}\!\left({\varphi }\right)=\textrm {True}{}\)  if and only if \(t\in D_{\mathrm {val}}\)  (Def REF ).

