A large body of work studied query evaluation in probabilistic databases [1]}, [2]}, [3]}, [4]}, [5]}, which resembles our work in the use of data provenance [6]}, [7]} to track the connection between input and query output and the approach of identifying classes of queries that yield provenance expressions of favorable structure.
In particular, prior work on probabilistic databases has characterized query classes where provenance may be transformed into read-once form for its useful properties such as easy probability computation [8]}, [9]}, [10]}, [11]}. In our context, we have studied the evasiveness of such expressions (Section REF ).
