# Maintenance of Discovered High Average-Utility Itemsets in Dynamic Databases
## 4 Proposed FUP-HAUIM Algorithm with Transaction Insertion
### The Adapted Fast Updated Concept  
The designed FUP-HAUUBI algorithm categorizes 1-HAUUBIs into four cases according to the FUP concept, which is extended from [25]. The 1-HAUUBIs of each case are then, respectively, processed by the designed procedures to update the 1-HAUUBIs. The four cases of the adapted FUP concept are shown in Figure 4. Thus, we can obtain the following information as:  
* **Case 1:** An itemset is a 1-HAUUBI both in the original database and in the inserted transactions. In this case, this itemset remains a 1-HAUUBI after the database is updated. * **Case 2:** An itemset is a 1-HAUUBI in the original database but not a 1-HAUUBI in the inserted transactions. In this case, the itemset is a 1-HAUUBI or not a 1-HAUUBI after the database is updated. * **Case 3:** An itemset is a non 1-HAUUBI in the original database but a 1-HAUUBI in the inserted transactions. In this case, an additional database scan is needed to obtain the average-utility of the itemset in the original database, and then update its average-utility after the database is updated. * **Case 4:** An itemset is a non 1-HAUUBI both in the original database and in the inserted transactions. In this case, an itemset remains a non 1-HAUUBI after the database is updated. Based on the above cases, lemmas, proofs, and corollaries are provided as follows to ensure the correctness and completeness for discovering 1-HAUUBIs for incremental HAUIM. **Lemma 1**. : _An itemset \(X\) is a 1-HAUUBI in the original Database (D) and inserted transactions (d). Thus, it remains a 1-HAUUBI in the updated Database (U)._  
Figure 4: Four cases of the adapted FUP concept. Figure 3: The constructed AUL-structures of the original database. Proof. : Since \(X\) is a 1-HAUUBI both in (\(D\)) and (\(d\)), its \(uuub(X)^{D}\geq TU^{D}\times\delta\) and \(uub(X)^{d}\geq TU^{d}\times\delta\). Thus, the updated result is: \(auub(X)^{U}=auub(X)^{D}+auub(X)^{d}=TU^{D}\times\delta+TU^{d}\times\delta= \mathfrak{t}(TU^{D}+TU^{d})\times\delta\). Hence, we conclude that the itemset remains a 1-HAUUBI in the updated Database (\(U\)). Corollary 1: _An itemset \(X\) remains a 1-HAUUBI in (\(U\)) if it belongs to Case 1._  
Lemma 2: _An itemset \(X\) is a 1-HAUUBI in (\(D\)) but a non 1-HAUUBI in (\(d\)). There are two possible situations: (1) it is a 1-HAUUBI in (\(U\)); or (2) it becomes a non 1-HAUUBI in (\(U\))._  
Proof. : Since an itemset \(X\) is a 1-HAUUBI in (\(D\)), it follows that \(auub(X)^{D}\geq TU^{D}\times\delta\). It is a non 1-HAUUBI in (\(d\)) since \(auub(X)^{d}<TU^{d}\times\delta\). There are two possible situations: (1) \(auub(X)^{U}=auub(X)^{D}+auub(X)^{d}\geq TU^{D}\times\delta+TU^{d}\times\delta= (TU^{D}+TU^{d})\times\delta\); or (2) \(auub(X)^{U}<(TU^{D}+TU^{d})\times\delta\). Corollary 2: _Two situations may occur for the itemset \(X\): (1) it remains a 1-HAUUBI in (\(U\)); or (2) it is a non 1-HAUUBI in (\(U\)) if it belongs to Case 2._  
Lemma 3: _If an itemset \(X\) is a non 1-HAUUBI in (\(D\)) but is a 1-HAUUBI in (\(d\)), an additional database scan is needed to obtain the \(auub(X)^{D}\). There are two possible situations: (1) it remains a non 1-HAUBBI in (\(U\)); or (2) it becomes a 1-HAUUBI in (\(U\))._  
Proof. : An itemset \(X\) is a non 1-HAUUBI in (\(D\)) such as \(auub(X)^{D}<TU^{D}\times\delta\), and is a 1-HAUUBI in (\(d\)) such as \(auub(X)^{d}\geq TU^{d}\times\delta\). Thus, we can have that: (1) \(auub(X)^{U}=auub(X)^{D}+auub(X)^{d}\geq TU^{D}\times\delta+TU^{d}\times\delta\) (\(=TU^{D}+TU^{d})\times\delta\); or (2) \(auub(X)^{U}<(=TU^{D}+TU^{d})\times\delta\). Corollary 3: _For an itemset \(X\), two situations may occur: (1) it remains a non 1-HAUUBI in (\(U\)); or (2) it becomes a 1-HAUUBI in (\(U\)) if it appears in Case 3._  
Lemma 4: _If an itemset \(X\) is a non 1-HAUUBI in both (\(D\)) and (\(d\)), it remains a non 1-HAUUBI in (\(U\))._  
Proof. : An itemset \(X\) is a non 1-HAUUBI both in (\(D\)) and (\(d\)) such that \(auub(X)^{D}<TU^{D}\times\delta\), and \(auub(X)^{d}<TU^{d}\times\delta\).