## 5 Experimental Results
### Effectiveness  
Compared with why-provenance [12], the proposed model used minimal provenance to eliminate unnecessary result tuples in the query result, so our pricing was more accurate and lower. Thus, as depicted in Figure 1, the price of why-provenance was much more expensive than our pricing model. When the \(p\) value of the p-norm was used to adjust the price, the higher \(p\) was, the lower the price was, and the price was highest when \(p\) was one. Similarly, when the \(p\) of p-norm was used to adjust the performance ratio, the higher the \(p\) was, the lower the performance ratio was, and the highest performance ratio was reached when \(p\) was one.  
Although Theorem 3 says that calculating the exact price of a query is NP-hard, we show that computing the exact price of the query with selection and join can only be achieved in polynomial time.  
Firstly, we performed a selection and join query on the shuhuibao dataset. Let us consider a parameterized query \(Q_{u}^{\mathbf{x}}\):  
**select**_c.User_ID, _c.Amount_, _c.Price_**as**_c_price_, _m.Price_**as**_m_price_**from**_consume**_c_, message_m_**where**_c.User_ID =_m.User_ID_**limit**_n_;When the number of result tuples \(n\) was 10, 20, 30, 40, and 50, the query price of our exact and approximate pricing was 14, 14, 23, 26, and 24, respectively, whereas the why-provenance calculated the query price to be 35, 35, 59, 65, and 67, respectively. It can be intuitively observed from Figure 2 that the exact price is equal to the approximate price, but much less than the why-provenance price, and they maintained a linear increasing relationship with the result tuples, which conformed to the consistency between the number of result tuples and the price, i.e., the more result tuples, the higher the price. The ratio \(\alpha\) between the approximate price and the exact price was 1, 1, 1, 1, and 1, respectively. When setting \(p=1\) for the p-norm, the performance ratio \(r=\sqrt[p]{n}\) value was 3.16, 4.47, 5.47, 6.32, and 7.07, respectively. It can be intuitively observed from Figure 3 that the value of \(\alpha\) was far less than the value of \(r\), which further proved that the approximate pricing that we proposed was very effective.  
Next, we performed complex queries on the MovieLens dataset. Let us consider a complex query with multiple tables and multiple logics:  
**select**\(r.User1D\), \(r.Movie1D\), \(r.Rating\), \(r.Price\), \(u.User\)\(1D\), \(u.Gender\), \(u.Price\)**from**\(ratings\)\(r\), _users_\(u\)**where**\((r.Movie1D=1\)**or**\(r.Movie1D=2)\)**and**\((r.User1D=u.User1D)\)**limit**\(n\);  
When the number of result tuples \(n\) was 5, 10, 15, 20, and 25, the query price of our exact pricing was 5, 12, 23, 34, and 38, the approximate pricing was 8, 19, 32, 45, and 50, and the why-provenance calculated the query price to be 26, 58, 90, 123, and 138, respectively. It can be intuitively observed from Figure 4 that the exact price was slightly lower than the approximate price, but much less than the why-provenance price, and they maintained a linear increasing relationship with the result tuples,  
Figure 1: Price comparison under the p-norm. As the value of \(p\) increases from one to five, the price decreases.  
Figure 2: Price comparison under join query.  
which conformed to the consistency between the number of result tuples and the price, i.e., the more result tuples, the higher the price. The ratio \(\alpha\) between the approximate price and the exact price was 1.6, 1.58, 1.39, 1.32, and 1.31, respectively. When setting \(p=1\) for the p-norm, the performance ratio \(r=\sqrt[]{n}\) value was 2.23, 3.16, 3.87, 4.47, and 5, respectively. It can be intuitively observed from Figure 5 that the value of \(\alpha\) was far less than the value of \(r\), which further proves that the approximation algorithm that we proposed was very effective.  
Figure 4: Price comparison under complex query.  
Figure 3: Price ratio vs. approximability of the approximate algorithm.