## 3 Pricing Data
### Pricing Function
Otherwise, no buyer would pay for the entire dataset, but would instead buy all 50 states' datasets separately._  
This paper addresses contributing tuples, thus the concept of arbitrage must be adapted for contributing tuples. For a query \(Q\), its contribution tuples are \(\{\{t_{1},t_{2},t_{3}\}\}\), and the price is \(p\); for another query \(Q_{1}\), its contribution tuples are \(\{\{t_{1},t_{2}\}\}\), and the price is \(p_{1}\); and for a third query \(Q_{2}\), its contribution tuples are \(\{\{t_{3},t_{4}\}\}\), and the price is \(p_{2}\). The data seller must be sure that \(p<p_{1}+p_{2}\). Otherwise, this results in the price of \(\{\{t_{1},t_{2},t_{3},t_{4}\}\}\) being lower than the price of \(\{t_{1},t_{2},t_{3}\}\), which is unreasonable. In this situation, in which users can obtain contributing tuples, and if the query is not carefully defined, arbitrage can occur. We have to avoid arbitrage, and we will formally define arbitrage-freeness. **Definition 12**. : _(Arbitrage-freeness) A pricing function is arbitrage-free if:_  
\[(\forall S(S=\bigcup_{1\leq i\leq m}T^{i}_{k_{i}}(T^{i}_{k_{i}}\in V(Q_{i},I)) \Rightarrow\exists T(T\in V(Q,I)\wedge T\subseteq S))) \tag{12}\]  
\(\sum_{i}p_{I}(Q_{i})\geq p_{I}(Q)\)_holds._  
**Example 4**. : _Suppose that \(V(Q_{1},I)=\{T^{1}_{1}=\{t_{1},t_{2}\},T^{2}_{1}=\{t_{2},t_{3}\}\}\), \(V(Q_{2},I)=\{T^{1}_{2}=\{t_{2},t_{4}\},T^{2}_{2}=\{t_{1},t_{4}\}\}\), and \(V(Q,I)=\{T^{1}=\{t_{1},t_{2}\},T^{2}=\{t_{2},t_{3}\},T^{3}=\{t_{1},t_{4}\}\}\)._  
For \(T^{1}_{1}\cup T^{1}_{2}=\{t_{1},t_{2},t_{4}\}\), there exists \(T^{1}\subseteq T^{1}_{1}\cup T^{1}_{2}\). For \(T^{2}_{1}\cup T^{1}_{2}=\{t_{2},t_{3},t_{4}\}\), there exists \(T^{2}\subseteq T^{2}_{1}\cup T^{1}_{2}\). For \(T^{1}_{1}\cup T^{2}_{2}=\{t_{1},t_{2},t_{4}\}\), there exists \(T^{1}\subseteq T^{1}_{1}\cup T^{2}_{2}\). For \(T^{2}_{1}\cup T^{2}_{2}=\{t_{1},t_{2},t_{3},t_{4}\}\), there exists \(T^{1}\subseteq T^{2}_{1}\cup T^{2}_{2}\). If \(p_{I}(Q_{1})+p_{I}(Q_{2})\geq p_{I}(Q)\), then this pricing function is arbitrage-free. **Definition 13** (Price of a query [16]). : _The price of the least expensive minimal provenance of \(Q(I)\) defines the price of a query \(Q\) in a database instance I:_  
\[P_{I}(Q)=\min_{T\in V(Q,I)}\|T\|_{p} \tag{13}\]  
**Theorem 2** ([16]). : _The pricing function in Definition 13 satisfies the following properties:_  
* _Equivalent queries should have the same price._  
Proof. : Suppose that \(Q_{1}\), \(Q_{2}\) are two equivalent queries: \(Q_{1}\equiv Q_{2}\). For \(\forall\)\(I\), \(Q_{1}(I)=Q_{2}(I)\), according to Theorem 1, we get \(V(Q_{1},I)=V(Q_{2},I)\). According to Definition 13, we get \(P_{I}(Q_{1})=\min_{T\in V(Q_{1},I)}\|T\|_{p}\) and \(P_{I}(Q_{2})=\min_{T\in V(Q_{2},I)}\|T\|_{p}\). Because \(V(Q_{1},I)=V(Q_{2},I)\), so \(P_{I}(Q_{1})=P_{I}(Q_{2})\). * The pricing function is monotonic. Proof. : Suppose that \(Q_{1}\) and \(Q_{2}\) satisfy \(Q_{1}\subseteq_{C(I)}Q_{2}\). The least expensive minimal provenance of \(Q_{2}(I)\) is denoted by \(T^{\prime}_{min}\); thus, \(p_{I}(Q_{2})=\|T^{\prime}_{min}\|_{p}\). Due to \(Q_{1}\subseteq_{C(I)}Q_{2}\), \(\exists T\in V(Q_{1},I)\) such that \(T\subseteq T^{\prime}_{min}\). \[P_{I}(Q_{2})=\|T^{\prime}_{min}\|_{p}\geq\|T\|_{p}\geq\min_{O\in V(Q_{1},I)}\| T\|_{p}=p_{I}(Q_{1}) \tag{14}\]  
According to Definition 10, the pricing function is monotonic. * The pricing function is bounded. Proof. : According to Lemma 1, we know that it is bounded. * The pricing function is arbitrage-free. Proof. : Suppose that \(Q\) and \(\{Q_{i}\}(1\leq i\leq m)\) satisfy the following:  
\[\forall S(S=\bigcup_{1\leq i\leq m}T^{i}_{k_{i}}(T^{i}_{k_{i}}\in V(Q_{i},I))) \Rightarrow\exists T(T\in V(Q,I)\wedge T\subseteq S) \tag{15}\]  
Suppose that the least expensive minimal provenance of \(V(Q_{i},I)\) is denoted by \(Q^{i}_{min}\).