# Decision-Tree-Based Horizontal Fragmentation Method for Data Warehouses
## 3 Materials and Methods
### Build data sets  
This step consists of building \(W-1\) data sets used to train the J48 algorithm to select the best horizontal fragmentation scheme (HFS). J48 was used because it obtained better performance than other decision tree algorithms according to [28], where it was demonstrated that J48 built decision trees with better results considering four evaluation metrics: precision, recall, F-measure, and ROC area. Algorithm 1 shows the steps to build the data sets. According to lines 1-3, it receives as an input \(W\) and a predicate usage matrix (PUM) of the queries executed in both the fact table and \(dim\). Table 5 shows the PUM for the example. The data sets in ARFF (attribute-relation file format) are the output of Algorithm 1 (line 4). In line 5, \(c\) is set to two because this is the minimum number of fragments of the scheme. Then, a partition tree (PT) is generated [29], where initially, every predicate is considered to be in a single partition (see Table 6, where each column corresponds to a fragment and the * indicates an empty partition); from step 1 to step \(r-1\), where \(r\) is the number of predicates of \(dim\), a merging profit matrix (MPM) is obtained (lines 6 and 7), which measures the benefit obtained by merging a pair of predicates. When a pair of predicates is merged, the number of remote tuples accessed is reduced, as some queries that previously required tuples from multiple fragments will now only need to access one fragment. For example, the PUM of Table 5 shows that the \begin{table}
\begin{tabular}{c c} \hline \hline
**Dimension** & **Importance** \\ \hline _date_ & _38,076,239_ \\ _supplier_ & _4,549,634_ \\ _part_ & _485,328_ \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Dimension importance for the scenario. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Pr** & **Description** & **S** \\ \hline \(p_{1}\) & \(d\_year=1992\) & \(sel_{1}=907,987\) \\ \(p_{2}\) & \(d\_sellingsseason='Summer'\) & \(sel_{2}=2,076,040\) \\ \(p_{3}\) & \(d\_year=1993\) & \(sel_{3}=908,288\) \\ \(p_{4}\) & \(d\_sellingsseason='Christmas'\) & \(sel_{4}=912,008\) \\ \(p_{5}\) & _Dumont=’January’_ & \(sel_{5}=541,483\) \\ \(p_{6}\) & \(d\_year=1995\) & \(sel_{6}=909,991\) \\ \(p_{7}\) & \(d\_sellingsseason='Winter'\) & \(sel_{7}=1,577,160\) \\ \(p_{8}\) & \(p\_category='MFGR#12'\) & \(sel_{8}=236,816\) \\ \(p_{9}\) & \(s\_region='AMERICA\"\) & \(sel_{9}=1.134,371\) \\ \(p_{10}\) & \(p\_brand1='MFGR#2221'\), & \(sel_{10}=5848\) \\ \(p_{11}\) & \(s\_region='EUROPE'\) & \(sel_{11}=1,140,311\) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Predicates used by the queries. query \(q_{2}\) uses the predicates \(p_{1}\) and \(p_{2}\); when they are combined in a partition in the second step of the PT depicted in Table 6, \(q_{2}\) only accesses one fragment, while the number of irrelevant tuples retrieved is increased because some queries will now have to retrieve all tuples from the new fragment even if they only require those from one of the merged fragments. For example, in Table 5, the query \(q_{1}\) only needs the tuples that satisfy the predicate \(p_{1}\), but when the two predicates (\(p_{1}\) and \(p_{2}\)) are merged, it also has to access the tuples from predicate \(p_{2}\). The MPM is obtained as in [30], which takes the PUM as the input and calculates the decreased volume of remote tuples retrieved (DRT) and the increased number of irrelevant tuples obtained (IIT). The merging benefit of two predicates will be equal to the difference between DRT and IIT. The predicate pair with the highest merging profit will be merged (lines 8-9). When step \(r\)-(\(W\)-c) is reached (line 10), the first data set (\(data\_set_{c}\)) is obtained (line 11). With each merger, a new data set will be generated with one more fragment (line 12), until finding the last data set consisting of \(W\) minus one, because the last fragment would be the complement.