Mining association rules can be expensive. In a large, dynamic database of transactions, we want to store the frequent itemsets and incrementally update them upon arrival of a set of new transactions. Let DB denote the last state of our database and DB-new a set of new transactions. We assume that we use the Apriori-algorithm and have stored all frequent itemsets in DB with respect to min-sup. The task is to incrementally determine the frequent itemsets in (DB \union DB-new) with respect to min-sup, without re-applying the Apriori-algorithm to the whole updated database DB\union DB-new.

a) For which itemsets do you need to count the support in DB? For which itemsets do you need to count the support in DB-new? Provide proofs for your answers.

b) Describe the entire method for incrementally updating the set of frequent itemsets.