# Maintenance of Discovered High Average-Utility Itemsets in Dynamic Databases
## 3 Preliminaries and Problem Statement  
In this section, an example is given to explain the definitions of the designed approach, which is shown in Table 1. Each transaction consists of several distinct items, and purchase quantities are attached to items. The unit profit table of the original database is shown in Table 2. The user's minimum high average-utility threshold \(\delta\) is set to 14.4%, which is set by the user based on its preferences and the application domain. **Definition 1**. : _The average-utility of an item \(i_{j}\) in the transaction \(T_{q}\) can be denoted as \(au(i_{j},T_{q})\), which is defined as:_  
\[au(i_{j},T_{q})=\frac{q(i_{j},T_{q})\times p(i_{j})}{1}, \tag{1}\]  
_where \(q(i_{j},T_{q})\) is the quantity of \(i_{j}\) in \(T_{q}\), and \(p(i_{j})\) is the unit profit value of \(i_{j}\)._  
For instance, the average-utilities of Items (\(b\)-\(d\)) in \(T_{1}\) are calculated as \(au(b,T_{1})=\frac{1\times\mathbb{S}}{1}(=5)\), \(au(c,T_{1})=\frac{2\times\mathbb{S}}{1}(=8)\), and \(au(d,T_{1})=\frac{1\times\mathbb{S}}{1}(=8)\), respectively. \begin{table}
\begin{tabular}{c c c c c c c c c c c c c c c c c c c c  
Definition 2: The average-utility of a \(k\)-itemset \(X\) in a transaction \(T_{q}\) can be denoted as \(au(X,T_{q})\), which is defined as:  
\[au(X,T_{q})=\frac{\sum\limits_{i_{j}\subseteq X\wedge X\subseteq T_{q}}q(i_{j},T _{q})\times p(i_{j})}{|X|}=\frac{\sum\limits_{i_{j}\subseteq X\wedge X\subseteq T _{q}}q(i_{j},T_{q})\times p(i_{j})}{k}, \tag{2}\]  
where \(k\) is the number of items in \(X\). For instance, the average-utility of Itemsets (\(ac\)) and (\(acd\)) in \(T_{1}\) are calculated as \(au(ac,T_{1})=\frac{4\times 3+2\times 4}{2}\) (\(=10\)), and \(au(acd,T_{1})=\frac{4\times 3+2\times 4+1\times 8}{3}\) (\(=9.3\)), respectively. Definition 3: The average-utility of an itemset \(X\) in \(D\) is denoted as \(au(X)\), and defined as:  
\[au(X)=\sum\limits_{X\subseteq T_{q}\wedge T_{q}\in D}au(X,T_{q}). \tag{3}\]  
For instance, the average-utility of Itemset (\(ac\)) in the database is calculated as: \(au(ac,T_{1})+au(ac,T_{3})(=\frac{20}{2}+\frac{19}{2})(=19.5)\). Definition 4: The transaction utility of a transaction \(T_{q}\) is denoted as \(tu(T_{q})\), and defined as:  
\[tu(T_{q})=\sum\limits_{i_{j}\subseteq T_{q}}u(i_{j},T_{q}). \tag{4}\]  
For instance, \(tu(T_{1})(=12+4+8+8)(=32)\), \(tu(T_{2})(=77)\), \(tu(T_{3})(=44)\), \(tu(T_{4})(=42)\), and \(tu(T_{5})(=49)\). Definition 5: The total utility of a database \(D\) is denoted as \(TU^{D}\), which is the sum of all transaction utilities as:  
\[TU^{D}=\sum\limits_{T_{q}\in D}tu(T_{q}). \tag{5}\]  
For instance, the total utility of Table 1 is calculated as \(TU^{D}\) (\(=32+77+44+42+49\)) (\(=244\)). To obtain a downward closure property for pruning unpromising candidates early, the average-utility upper bound (\(auub\)) model [20] was designed. It overestimates the utility of itemsets. This process ensures the correctness and completeness of the process for mining itemsets. The definitions are as follows. Definition 6 (Transaction-maximum utility, tmu): The transaction-maximum utility of a transaction \(T_{q}\) is denoted as \(tmu(T_{q})\) and defined as:  
\[tmu(T_{q})=max\{u(i_{j})|i_{j}\subseteq X\wedge X\subseteq T_{q}\}. \tag{6}\]  
For instance, the \(tmu\) of transactions \(T_{1}\) to \(T_{5}\) are calculated as \(tmu(T_{1})(=12)\), \(tmu(T_{2})(=24)\), \(tmu(T_{3})(=21)\), \(tmu(T_{4})(=22)\), and \(tmu(T_{5})(=35)\), respectively. Definition 7 (Average-utility upper-bound, auub): The average-utility upper-bound (auub) of an itemset \(X\) in the original database is denoted as \(auub(X)^{D}\) and defined as:  
\[auub(X)^{D}=\sum\limits_{X\subseteq T_{q}\wedge T_{q}\in D}tmu(T_{q}), \tag{7}\]  
where \(tmu(T_{q})\) is the maximum utility of transaction \(T_{q}\) such that \(i_{j}\subseteq X\wedge X\subseteq T_{q}\). For instance, the \(auub\) values of the itemsets (\(a\)) and (\(ac\)) are calculated as: \(auub(a)^{D}\)(\(=12+21+35\))(\(=68\)) and \(auub(ac)^{D}\)(\(=12+21\))(\(=33\)), respectively.