## 3 Pricing Data
### Pricing Function  
The pricing function is used to price query so as to generate minimal provenance. First, define the minimum provenance to produce query results. Then, define several important properties that the pricing function must satisfy. Finally, a pricing function is proposed, and all defined properties are proven to be satisfied. **Definition 8** (Contribution tuples [16]). : _Let \(I,Q,Q(I)\) represent a database instance, a query, and the query results, respectively. The minimal provenances of \(Q(I)\), i.e., \(V(Q,I)\) is the contribution tuples of \(Q(I)\)._  
**Property 1**. : _(Monotonicity) In fact, it is necessary to have such a property because it ensures that queries that use more source tuples have higher prices than those that use fewer source tuples. However, the implications of \"using more source tuples\" is uncertain when there are multiple methods for producing query results. If you use only a subset of all the source tuples that produce the results of query \(Q_{2}\) to produce the results of query \(Q_{1}\), you can assume that query \(Q_{2}\) uses more source tuples than query \(Q_{1}\) does._  
**Definition 9**. : _(Containment and equivalence) Let \(I\) represent a database instance and \(Q_{1}\) and \(Q_{2}\) be two queries. The sets of contribution tuples of \(Q_{1}(I)\) and \(Q_{2}(I)\) are denoted by \(V(Q_{1},I)\) and \(V(Q_{2},I)\), respectively. \(Q_{1}\) is contained in \(Q_{2}\) about \(I\), namely \(Q_{1}\subseteq_{C(I)}Q_{2}\), if and only if:_  
\[\forall T^{\prime}(T^{\prime}\in(V(Q_{2},I)\Rightarrow\exists T(T\in(V(Q_{1}, I)\wedge T\subseteq T^{\prime})))) \tag{11}\]  
\(Q_{1}\) and \(Q_{2}\) are equivalent, that is \(Q_{1}\equiv_{C(I)}Q_{2}\), if and only if \(Q_{1}\subseteq_{C(I)}Q_{2}\) and \(Q_{2}\subseteq_{C(I)}Q_{1}\). \(Q_{1}\subseteq_{C}Q_{2}\), if and only if for any database instance \(I,Q_{1}\subseteq_{C(I)}Q_{2}\). \(Q_{1}\equiv_{C}Q_{2}\), if and only if \(Q_{1}\subseteq_{C}Q_{2}\) and \(Q_{2}\subseteq_{C}Q_{1}\). **Example 3**. : _Let \(I\) represent a database instance and \(Q_{1}\), \(Q_{2}\), and \(Q_{3}\) represent three queries. The sets of contributing tuples of \(Q_{1}(I)\), \(Q_{2}(I)\), and \(Q_{3}(I)\) are denoted by \(V(Q_{1},I)\), \(V(Q_{2},I)\), and \(V(Q_{3},I)\), respectively. 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_{1},t_{2},t_{3}\}\},V(Q_{3},I)=\{T^{1}_{3}=\{t_{1},t_{2} \},T^{2}_{3}=\{t_{1},t_{3}\}\}\)._  
\(Q_{1}\subseteq Q_{2}\)_, because for \(T^{1}_{2}\), there exists \(T^{1}_{1}\) such that \(T^{1}_{1}\subseteq T^{1}_{2}\). However, \(Q_{1}\
subseteq_{C(I)}Q_{3}\) because for \(T^{2}_{3}\), \(T^{1}_{1}\
subseteq T^{2}_{3}\) and \(T^{2}_{1}\
subseteq T^{2}_{3}\)._  
For all the methods that produce the results of \(Q_{2}\), we must ensure that the price of \(Q_{1}\) is less than the price of \(Q_{2}\), such that we can find the result of \(Q_{1}\) in a less expensive manner. **Definition 10**. : _(Monotonicity) If given a database instance 1, for any two queries \(Q_{1}\) and \(Q_{2}\), when \(Q_{1}\subseteq_{C(I)}Q_{2}\), \(p_{1}(Q_{1})\leq p_{1}(Q_{2})\), then we can call the pricing function monotonic._  
**Property 2**. : _(Boundedness) The price of the base tuple involved in the query is an upper bound on the price of any query._  
**Definition 11**. : _(Boundedness) Let \(S=\{t\in R|R\varpropto Q\}\) represent the base tuples and \(R\varpropto Q\) represent the relation \(R\) involved in the query \(Q\). If \(\forall Q\), there exists \(\|S\|_{p}\geq p_{1}(Q)\), then we say that the pricing function is bounded._  
**Lemma 1** ([16]). : _If a pricing function is monotonic, then it is bounded._  
**Property 3**. : _(Arbitrage-freeness) The practice of taking full advantage of the price in multiple markets is called arbitrage. Consider the USA business dataset [7]: if \(p\) is the price for the entire dataset and \(p_{1},\ldots,p_{50}\) are the prices for the data in each of the 50 states, then a rational seller would ensure that \(p<p_{1}+\ldots+p_{50}\).