## 4 Pricing Algorithm
### Exact Algorithm  
**Theorem 3** ([16]). : _If given the price of each base tuple, a database instance \(I\), the minimal why-provenances of each result tuple \(t_{i}\in Q(I)\), then the complexity of computing the price \(p_{I}(Q)\) is NP-hard._  
We reduce this problem to the minimum-cost satisfiability (MinCostSAT) problem [18] to prove this theorem, which is known to be NP-hard. Proof. : Recall in Definition 13 that \(p_{I}(Q)\) is the price of the least expensive set of source tuples that guarantees producing all the result tuples in the query result. We refer to the problem of finding the least expensive set of source tuples that guarantees producing all the result tuples in the query result as \(P\). We reduce a known MinCostSAT problem ([18]) to \(P\), i.e., MinCostSAT \(\leq P\). If a Boolean formula \(F\) in conjunctive normal form (CNF) has \(n\) variables and \(m\) clauses and the cost function specifies a non-negative weight \(w_{i}\) for \(x_{i}\), the MinCostSat seeks a satisfactory assignment for \(F\) that minimizes the objective function [18]:  
\[\sum_{i=1}^{n}w_{i}x_{i} \tag{17}\]  
where \(i\in[1,n]\) and \(x_{i}\in\{0,1\}\). MinCostSat is NP-hard. We construct an MinCostSAT instance. There are five Boolean variables \(y_{1},y_{2},y_{3},y_{4},y_{5}\) with their weights \(w(y_{1}),w(y_{2}),w(y_{3}),w(y_{4}),w(y_{5})\). We have a CNF formula \(C=(y_{1}\lor y_{2}\lor y_{3})\wedge(y_{3}\lor y_{4})\wedge(y_{4}\lor y_{5}\lor y _{1})\). The solution to this MinCostSAT instance is the model with the minimum cost. We reduce the MinCostSAT instance to a \(P\) instance. Construct a source tuple for each Boolean variable. A source tuple is selected in the solution if the value of the corresponding Boolean variable is true; otherwise, the corresponding source tuple is not selected. The price of a source tuple is the weight of the corresponding Boolean variable. For a source tuple \(t_{i}\in Q(I)\), \(W^{i}\) represents its set of minimal why-provenances [11], so \(W^{i}\) is constructed from a conjunct in the formula. The above MinCostSAT instance reduces to a pricing computation problem, as: there are five source tuples \(t_{y_{1}},t_{y_{2}},t_{y_{3}},t_{y_{4}},t_{y_{5}}\), with their prices \(p(t_{y_{1}})=w(y_{1}),p(t_{y_{2}})=w(y_{2}),p(t_{y_{3}})=w(y_{3}),p(t_{y_{4}}) =w(y_{4}),p(t_{y_{5}})=w(y_{5})\); there are three result tuples \(t_{1},t_{2},t_{3}\) in the query result; \(W^{1}=\{\{t_{y_{1}}\},\{t_{y_{2}}\},\{t_{y_{3}}\},\)\(W^{2}=\{\{t_{y_{3}}\},\{t_{y_{4}}\}\}\), and \(W^{3}=\{\{t_{y_{4}}\},\{t_{y_{5}}\},\{t_{y_{1}}\}\}\). The solution to this price computation problem is finding the least expensive set of source tuples being able to produce \(t_{1},t_{2},t_{3}\). It is obvious to see that the constructed instance of MinCostSAT is satisfiable iff the transformed instance of \(P\) has a solution. Thus, the reduction from MinCostSAT to \(P\) is valid and can be done in polynomial time. We have MinCostSAT \(\leq P\). We reduce \(P\) to a known MinCostSAT problem, i.e., \(P\leq\) MinCostSAT. We construct a \(P\) instance. There are four source tuples \(t_{y_{1}},t_{y_{2}},t_{y_{3}},t_{y_{4}}\), with their prices \(p(t_{y_{1}}),p(t_{y_{2}}),p(t_{y_{3}}),p(t_{y_{4}})\). There are two result tuples \(t_{1},t_{2}\) in the query result \(W^{1}=\{\{t_{y_{1}},t_{y_{2}}\},\{t_{y_{2}},t_{y_{3}}\}\}\), \(W^{2}=\{\{t_{y_{1}},t_{y_{3}}\},\{t_{y_{2}},t_{y_{4}}\}\}\). The solution to this \(P\) instance is the least expensive set of source tuples being able to produce \(t_{1},t_{2}\). We reduce the \(P\) instance to an MinCostSAT instance. The basic idea of the reduction is as follows. Construct a Boolean variable for each source tuple. The value of a Boolean variable is true if the corresponding source tuple is selected in the solution; otherwise, the value is false. The weight of a Boolean variable is the price of the corresponding source tuple. Each conjunct in the formula is constructed from \(W^{i}\).