## 4 Pricing Algorithm
### Exact Algorithm
The above \(P\) instance reduces to an MinCostSAT instance, as: there are four Boolean variables \(y_{1},y_{2},y_{3},y_{4}\) with the weights \(w(y_{1})=p(t_{y_{1}}),w(y_{2})=p(t_{y_{2}}),w(y_{3})=p(t_{y_{3}}),w(y_{4})=p(t_{y _{4}})\). We have the formula \(C=((y_{1}\wedge y_{2})\vee(y_{2}\wedge y_{3}))\wedge((y_{1}\wedge y_{3})\vee( y_{2}\wedge y_{4}))\). \(C\) can be easily converted into its CNF, as \(C^{\prime}=(y_{1}\lor y_{2})\wedge(y_{1}\lor y_{3})\wedge(y_{2}\lor y_{2}) \wedge(y_{2}\lor y_{3})\wedge(y_{1}\lor y_{2})\wedge(y_{1}\lor y_{4})\wedge(y_ {3}\lor y_{2})\wedge(y_{3}\lor y_{4})\). For the ease of explanation, we discuss using \(C\). The solution to this MinCostSAT instance is the model with the least expensive cost. It is obvious to see that the constructed instance of \(P\) is satisfiable iff the transformed instance of MinCostSAT has a solution. Thus, the reduction from \(P\) to MinCostSAT is valid and can be done in polynomial time. We have \(P\leq\) MinCostSAT. Based on the above proof, \(P\equiv\) MinCostSAT. It was shown in [18] that MinCostSAT is NP-hard. Therefore, \(P\) is also NP-hard. We propose an exact algorithm for calculating the exact price of a query, although the time complexity may be exponential. Section 2 explained the difference between the minimal provenance proposed by us and the minimal why-provenance proposed in [11]. The relationship between them will be studied in detail below. Given \(V(Q,I)\) and \(W^{i}\), \(M(Q,I)\) represents the set in which each element is the union of \(W^{i}\), i.e., \(M(Q,I)=\{\bigcup_{i}w^{i}_{k_{i}}|w^{i}_{k_{i}}\in W^{i}\}\). \(V(Q,I)\
eq M(Q,I)\) can be verified through the following example. **Example 5**. : _Suppose \(Q(I)=\{t_{1},t_{2}\}\). Let \(W^{1}=\{\{x_{1},x_{2}\}\), \(\{x_{1},x_{4}\}\}\) and \(W^{2}=\{\{x_{3},x_{4}\}\}\). \(M(Q,I)=\{\{x_{1},x_{2},x_{3},x_{4}\},\{x_{1},x_{3},x_{4}\}\}\), which is not the set of minimal provenances. The proper subset \((\{x_{1},x_{3},x_{4}\})\) of \(\{x_{1},x_{2},x_{3},x_{4}\}\) is a minimal provenance; thus, it cannot be a minimal provenance._  
It can be observed from Example 5 that \(M(Q,I)\) may include nonminimal provenances that are not included in \(V(Q,I)\). Below, the relationship between \(V(Q,I)\) and \(M(Q,I)\) excluding nonminimal provenances is studied. \(M^{\prime}(Q,I)\) represents the set after filtering all nonminimal provenances from \(M(Q,I)\). **Theorem 4**. : _Let \(Q,I,Q(I)\) represent a query, a database instance, and the query results, respectively. \(V(Q,I)=M^{\prime}(Q,I)\) is true._  
In accordance with Theorem 4, we must filter nonminimal provenances from \(M(Q,I)\) to produce \(M^{\prime}(Q,I)\)). However, as shown below, the cost of \"filtering\" is high. Suppose that the query results contain \(n\) result tuples, each of which contains \(m\)\(W^{i}\). In this case, \(M(Q,I)\) have \(m^{n}\) provenances of the query result. Because we must compare the inclusion relationship between a provenance \(v\) in \(M(Q,I)\) and all other \(m^{n}-1\) provenances, the time complexity of checking the minimality of a provenance \(v\) is \(O(m^{n})\). The time complexity of checking all provenances in \(M(Q,I)\) is \(O(m^{2n})\). Fortunately, we can avoid such expensive \"filtering\" of nonminimal provenances, because our aim is computing the price of the least expensive provenance of the query result, rather than computing \(V(Q,I)\). Thus, a nonminimal provenance will not affect the final query result. **Lemma 2**. : \(min_{T\in M(Q,I)}\|T\|_{p}=min_{T\in U^{\prime}(Q,I)}\|T\|_{p}\) _is true._  
Proof. : Due to \(M(Q,I)\) containing nonminimal provenances, \(M^{\prime}(Q,I)\subseteq M(Q,I)\). Let \(\triangle M\) denote the nonminimal provenances, that is \(\triangle M=M(Q,I)-M^{\prime}(Q,I)\). Suppose that \(min_{T\in M^{\prime}(Q,I)}\|T\|_{p}=w^{min}\). All the provenances in \(\triangle M\) have prices that are not less than \(w^{min}\).