## 5 Experimental Results
### Efficiency  
This section studies the efficiency of the algorithm from different dimensions. The running time and memory consumption of the different algorithms were verified by performing different query operations on the two datasets. Firstly, we still considered the parameterized query that contained selection and join in the previous section \(Q_{u}^{\mathbb{N}}\):  
**select**_c.User_1D_, _c.Amount_, _c.Price_**as**_c_price_, _m.Price_**as**_m_price_**from**_consume_c_, _message_ _m_**where**_c.User_1D = m.User_1D_**limit**_\(n\)_;_  
When the number of result tuples \(n\) was 10, 20, 30, 40, and 50, the exact pricing calculated the query price in 0.035 s, 0.050 s, 0.075 s, 0.080 s, and 0.096 s, the approximate pricing calculated the query price in 0.023 s, 0.025 s, 0.028 s, 0.028 s, and 0.030 s, and the why-provenance calculated the query price in 0.023 s, 0.025 s, 0.026 s, 0.026 s, and 0.026 s, respectively. It can be observed intuitively from Figure 6 that the run time of the exact pricing was much greater than that of the approximate pricing, but the run time of the approximate pricing was slightly larger than that of the why-provenance, and they maintained a linear increasing relationship with the number of result tuples. The experimental results show that the approximate pricing was more effective. Even for a simple join query, the exact pricing can calculate the query price in polynomial time, but the run time was much longer than the approximate algorithm. Although the run time of approximate pricing was slightly higher than why-provenance, its price was much lower than why-provenance. This result further proved that the approximate pricing was very efficient. Next, we will still consider a complex query with multiple tables and multiple logics on the MovieLens dataset:  
**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 orr.Movie1D=2)\)**and**\((r.User1D=u.User1D)\)**limit**_\(n\)_;_  
When the number of result tuples \(n\) was 5, 10, 15, 20, and 25, the exact pricing calculated the query price in 0.070 s, 0.099 s, 0.134 s, 0.618 s, and 3.03 s, the approximate pricing calculated the query price in 0.078 s, 0.087 s, 0.145 s, 0.152 s, and 0.160 s, and the why-provenance calculated the query price in 0.021 s, 0.047 s, 0.061 s, 0.073 s, and 0.078 s, respectively. It can be observed intuitively from Figure 7 that the run time of the exact pricing was much greater than that of the approximate pricing, but the run time of the approximate pricing was slightly larger than that of the why-provenance, and they maintained a linear increasing relationship with the number of result tuples. The experimental results showed that the approximate pricing was more effective. Even for a simple join query, the exact pricing can calculate the query price in polynomial time. However, for a complex query, the run time of exact pricing would increase exponentially with the increase of the number of result tuples. As can be  
Figure 6: Running time by different algorithms in the select-joint query. seen from Figure 7, when the number of result tuples was 25, the run time reached 3 s, which further proved that the time complexity of calculating exact pricing was NP-hard. Although the run time of approximate pricing was slightly higher than why-provenance, its price was much lower than why-provenance. This result further proves that the approximate pricing was very efficient. Finally, from Figure 8, we can see that the memory cost of why-provenance was greater than the exact pricing and approximate pricing when performing the join query. However, Figure 9 shows that the memory cost of exact and approximate pricing was greater than why-provenance when complex query was executed. In terms of memory consumption alone, our model might consume more memory. However, our model considered removing redundant and unnecessary result tuples, pursuing minimum provenance, and obtaining the lowest query price. That is the most important thing.