## 3 Pricing Data
### Minimal Provenance  
To prevent arbitrary queries from charging users for the entire database, you must consider enough source tuples to generate the given query results. However, there may be more than one minimum set of enough source tuples. This paper defines the provenance of query results as a whole, not as a single source tuple. In our pricing model, a tuple is paid at most once, regardless of how many times it contributes to the query result. **Definition 4** (Provenance [16]). : _Let \(I,Q,Q(I)\) represent a database instance, a query, and the query results, respectively. A provenance of \(Q(I)\) is a set of source tuples \(T(T\subseteq I)\) so that \(Q(I)\subseteq Q(T)\)._  
**Definition 5** (Minimal provenance [16]). : _Let \(V(Q,I)\) represent the minimum provenance set of \(Q(I)\). \(V(Q,I)\) is a provenance \(T\) of \(Q(I)\), so that \(\forall T^{\prime},T^{\prime}\subseteq T\Rightarrow T^{\prime}=T\), where \(T^{\prime}\) is a provenance of \(Q(I)\)._  
**Example 2**. : _Based on Example 1, the query results \(Q(I)\) have four minimal provenances, i.e., \(T_{1}=\{t_{1},t_{2},t_{5},t_{7}\},T_{2}=\{t_{1},t_{4},t_{5},t_{8}\},T_{3}=\{t_ {1},t_{2},t_{6},t_{7}\},T_{4}=\{t_{1},t_{4},t_{6},t_{8}\}\)._  
Let us explain \(T_{1}\). \(T_{1}\) means the query result \(\{<John>,<Tom>\}\) is produced by the set of source tuples \(\{t_{1},t_{2},t_{5},t_{7}\}\), but the query result \(\{<John>,<Tom>\}\) cannot be produced by any subsets of \(O_{1}\). From Example 2, it can be observed that several \(V(Q,I)\) exist in query result \(Q(I)\). The following demonstrates that \(V(Q,I)\) remains constant in the query rewriting. **Theorem 1**. : \(\forall I\)_, if \(Q_{1}\equiv Q_{2}\), then \(V(Q_{1},I)=V(Q_{2},I)\)._  
Proof. : Suppose that \(Q_{1},Q_{2}\) are two equivalent queries: \(Q_{1}\equiv Q_{2}\). \(\forall I\), \(Q_{1}(I)=Q_{2}(I)\). Suppose that \(\exists I^{\prime}\) such that \(V(Q_{1},I^{\prime})\
eq V(Q_{2},I^{\prime})\). Thus, at least one of the two sets contains some elements that the other does not. Suppose: \[\exists T^{*}\in V(Q_{1},I^{\prime})\wedge(\forall T_{2}\in V(Q_{2},I^{\prime}) \Rightarrow T^{*}\
eq T_{2})\] (1) Consider the following cases: \(1.\quad\exists T^{\prime}\in V(Q_{2},I^{\prime})\) such that \(T^{*}\subset T^{\prime}\). Build a database instance \(I^{-}=T^{*}\). Because \(T^{*}\) denotes a minimal provenance of \(Q_{1}(I^{\prime})\), \[Q_{1}(I^{-})=Q_{1}(T^{*})=Q_{1}(I^{\prime})\] (2) Moreover, \(T^{*}\) is not the provenance of \(Q_{2}(I^{\prime})\). In that case, \(T^{\prime}\) cannot be a minimal provenance, \[Q_{2}(I^{-})=Q_{2}(T^{*})\
ot\supseteq Q_{2}(I^{\prime})\] (3) Thus, \[Q_{2}(I^{-})\
eq Q_{2}(I^{\prime})\] (4) Since \(Q_{1}\equiv Q_{2}\), \(Q_{1}(I^{\prime})=Q_{2}(I^{\prime})\) and \(Q_{1}(I^{-})\
eq Q_{2}(I^{\prime})\). This result violates \(Q1\equiv Q2\). \(2.\quad\exists T^{\prime}\in V(Q_{2},I^{\prime})\) such that \(T^{\prime}\subset T^{*}\). Build a database instance \(I^{-}=T^{\prime}\). Because \(T^{\prime}\) denotes a minimal provenance of \(Q_{2}(I^{\prime})\), \[Q_{2}(I^{-})=Q_{2}(T^{\prime})=Q_{2}(I^{\prime})\] (5) Moreover, \(T^{\prime}\) is not the provenance of \(Q_{1}(I^{\prime})\). In that case, \(T^{*}\) cannot be a minimal provenance, \[Q_{1}(I^{-})=Q_{1}(T^{\prime})\
ot\supseteq Q_{1}(I^{\prime})\] (6) Thus, \[Q_{1}(I^{-})\
eq Q_{1}(I^{\prime})\] (7) Since \(Q_{1}\equiv Q_{2}\), \(Q_{1}(I^{\prime})=Q_{2}(I^{\prime})\) and \(Q_{1}(I^{-})\
eq Q_{2}(I^{-})\). This result violates \(Q1\equiv Q2\). \(3.\quad\
exists T^{\prime}\in V(Q_{2},I^{\prime})\) so that \(T^{\prime}\subset T^{*}\) or \(T^{*}\subset T^{\prime}\). Build a database instance \(I^{-}=T^{*}\). Because \(T^{*}\) denotes a minimal provenance of \(Q_{1}(I^{\prime})\), \[Q_{1}(I^{-})=Q_{1}(T^{*})=Q_{1}(I^{\prime})\] (8) Moreover, \(T^{*}\) is not the provenance of \(Q_{2}(I^{\prime})\) since \(\forall T^{\prime}\in V(Q_{2},I^{\prime})\Rightarrow T^{*}\
eq T^{\prime}\). Additionally, \(T^{*}\) cannot be a provenance of \(Q_{2}(I^{\prime})\).