# Internal Data Imputation in Data Warehouse Dimensions

Yuzhao Yang, Fatma Abdelhedi, Jérôme Darmont, Franck Ravat, Olivier Teste

► To cite this version:

Yuzhao Yang, Fatma Abdelhedi, Jérôme Darmont, Franck Ravat, Olivier Teste. Internal Data Imputation in Data Warehouse Dimensions. 32nd International Conference on Database and Expert Systems Applications (DEXA 2021), Sep 2021, Linz, Austria. pp.237-244, 10.1007/978-3-030-86472-9_22 hal-03265060

HAL Id: hal-03265060

https://hal.science/hal-03265060

Submitted on 1 Oct 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Internal Data Imputation
in Data Warehouse Dimensions

Yuzhao Yang¹, Fatma Abdelhédi³, Jérôme Darmont², Franck Ravat¹, and
Olivier Teste¹

¹ IRIT-CNRS (UMR 5505), Université de Toulouse, France

`{Yuzhao.Yang, Franck.Ravat, Olivier.Teste}@irit.fr`

² Université de Lyon, Lyon 2, UR ERIC, France

`jerome.darmont@univ-lyon2.fr`

³ CBI² – TRIMANE, Paris, France

`Fatma.Abdelhedi@trimane.fr`

**Abstract.** Missing data occur commonly in data warehouses and may generate data usefulness problems. Thus, it is essential to address missing data to carry out a better analysis. There exists data imputation methods for missing data in fact tables, but not for dimension tables. Hence, we propose in this paper a data imputation method for data warehouse dimensions that is based on existing data and takes both intra- and inter-dimension relationships into account.

**Keywords:** Data warehouses · Data imputation · Dimensions

# 1 Introduction

Data warehouses (DWs) are widely used in companies and organizations to help building decision support systems. Data in DWs are usually modeled in a multidimensional way, which helps users consult and analyze aggregated data with On-Line Analytical Processing (OLAP). In a DW, there are non-NULL constraints on keys, but not always on the other attributes, so there may be missing data. Missing data may come from the DW's sources (operational data sources, data of other DWs) if not treated during the Extract-Transform-Load (ETL) process. We classify missing data in the DWs into factual missing data and dimensional missing data with respect to their occurrence in fact and dimension tables. Factual missing data are usually quantitative, making analysis results incomplete and preventing users from getting reliable aggregates. Dimensional missing data are usually qualitative, making aggregated data incomplete and making it hard to analyse them with respect to hierarchy levels. Therefore, it is significant to complete the missing data for the sake of a better data analysis.

Data imputation is the process of filling in missing data by plausible values based on information available in the dataset [5]. Imputation of missing data focuses on factual data, with statistic-based [11], K-Nearest Neighbour (KNN)-based [3], linear programming-based [2] and hybrid (KNN and constraint programming) [1] methods. There is no research about dimensional missing data.
However, dimensional data are mostly qualitative and there are methods for qualitative data imputation. Some methods replace missing values through business rules [4,9] or association rules [10,8]. Yet business rules are not always available in practice, and association rules require to define support and confidence thresholds, which is not always easy. External sources can also be employed, e.g., through crowdsourcing [6] or taking advantage of Web information [12]. Yet, suitable external sources may be difficult to find. Eventually, data imputation in DWs should consider the different structural elements in an OLAP systems, such as dimensions and hierarchies. As a result, we propose in this article an internal, i.e., based on existing data, data imputation method for dimensional missing data in DWs, by considering inter- and intra-dimension relationships.

The rest of the paper is organized as follow. In Section 2, we formalize the OLAP model. In Section 3, we detail our imputation method and provide the corresponding algorithms. In Section 4, we validate our proposal through a series of experiments. Finally, in Section 5, we conclude the paper.

## 2 Preliminaries

We introduce here the multidimensional DW concepts and notations used in this paper [7].

**Definition 1.** A data warehouse, denoted DW, is defined as $(N^{DW}, F^{DW}, D^{DW}, Star^{DW})$, where $N^{DW}$ is the data warehouse's name, $F^{DW} = \{F_1^{DW}, ..., F_m^{DW}\}$ is a set of facts, $D^{DW} = \{D_1^{DW}, ..., D_n^{DW}\}$ is a set of dimensions and $Star^{DW}: F^{DW} \rightarrow D^{DW}$ is a mapping associating each fact to its linked dimensions.

**Definition 2.** A dimension, denoted $D \in D^C$, is defined as $(N^D, A^D, H^D, I^D)$, where $N^D$ is the dimension's name, $A^D = \{a_1^D, ..., a_u^D\} \cup \{id^D\}$ is a set of attributes, where id^D represents the dimension's identifier. $H^D = \{H_1^D, ..., H_v^D\}$ is a set of hierarchies. $I^D = \{i_1^D, ..., i_e^D\}$ is a set of dimension instances. The value of instance $i_e^D$ for attribute $a_u^D$ is denoted as $i_e^D \cdot a_u^D$.

**Definition 3.** A hierarchy of dimension $D$, denoted $H \in H^D$, is defined as $(N^H, Param^H)$, where $N^H$ is the hierarchy's name. $Param^H = \langle id^D, p_2^H, ..., p_v^H \rangle$ is an ordered set of dimension attributes, called parameters, which set granularity levels along the dimensions: $\forall k \in [1...v], p_k^H \in A^D$. The case where $p_1^H$ rolls up to $p_2^H$ in $H$ is denoted by $p_1^H \le_H p_2^H$. $Weak^H = Param^H \rightarrow (A^D - Param^H)$ is a mapping possibly associating each parameter with one or several weak attributes, which are also dimension attributes providing additional information. $Weak^H[p_x^H] = \{w_1^{p_x^H}, ..., w_y^{p_x^H}\}$ is the weak attribute set for parameter $p_x^H$.

## 3 Internal Data Imputation for Dimensions

Internal data imputation consists in replacing missing data in dimensions with the aid of existing data. Existing data imputation is convincing because we use
accurate data and not predictions or otherwise computed values. Imputation can be achieved through intra- and inter-dimensional relationships. Let us introduce these two types of data imputation.

**Intra-dimensional Imputation** Intra-dimension imputation relies on data from the same dimension. There are indeed functional dependencies between attributes in the same hierarchy. If an attribute is a parameter, its values depend on the values of lower-granularity parameters. Our intra-dimension imputation method is presented in Algorithm 1. We first check each parameter in hierarchies of the DW. If there exists missing data for this parameter (Lines 1-2), we search for an instance with value in a lower-granularity parameter and whose value exists (Lines 3-4). Then, we can then fill in the missing data with this value (Line 5).

<caption>**Algorithm 1:** Intra-dimension Imputation</caption>

1 **for** each $p_v^H \in Param^H$, where $H \in H^D$, $D \in D^{DW}$ **do**
2 &nbsp;&nbsp;&nbsp;&nbsp;2 **for** each $i_e^D \in I^D$, where $i_e^D \cdot p_v^H$ is null **do**
3 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;3 **while** $p_{v2}^H \in Param^H \land p_{v2}^H \le_H p_v^H$ **do**
4 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;4 **if** $\exists i_{e2}^D \in I^D, i_{e2}^D \cdot p_{v2}^H = i_e^D \cdot p_{v2}^H \land i_{e2}^D \cdot p_v^H$ is not null **then**
5 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;5 $i_e^D \cdot p_v^H \leftarrow i_{e2}^D \cdot p_{v2}^H$
6 &nbsp;&nbsp;&nbsp;&nbsp;6 **for** each $i_{e3}^D \in I^D$, where $i_{e3}^D \cdot w_y^p$ is null, $w_y^p \in Weak^H[p_v^H]$ **do**
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;7 **while** $p_{v3}^H \in Param^H \land (p_{v3}^H \le_H p_v^H \lor p_{v3}^H = p_v^H)$ **do**
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;8 **if** $\exists i_{e4}^D \in I^D, i_{e4}^D \cdot p_{v3}^H = i_{e3}^D \cdot p_{v3}^H \land i_{e4}^D \cdot p_v^H$ is not null **then**
9 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;9 $i_{e3}^D \cdot w_y^p \leftarrow i_{e4}^D \cdot w_y^p$

The value of a weak attribute depends on the values of its parameter. Then, for each weak attribute of the parameter we check, if there are missing data (Line 6), we search for the instance that has the same value of its parameter or a lower-granularity parameter whose value exists (Lines 7-8). The missing weak attribute data can then be supplied by this value (Line 9). It is important to note that, since the parameter sets of hierarchy are ordered sets, checking parameters is sequential (from the lowest-granularity to the highest-granularity parameter). This ensures that imputation is maximal, as the value of a higher-granularity parameter depends on its lower-granularity parameters.

**Inter-dimensional Imputation** In a DW, there may be attributes that are common to different dimensions. Therefore, we can replace missing data with such inter-dimensional common attributes. The main idea of inter-dimension imputation is similar to intra-dimension imputation's, except that instead of
searching for parameters in the same hierarchy, we search for common parame-
ters of hierarchies in other dimensions (Algorithm 2, Lines 3-4 and 9-10). When
performing the imputation of weak attributes, we must make sure that, in the
searched dimension, the searched parameter is semantically identical with the
parameter of the weak attribute to be completed; and that it bears a seman-
tically identical weak attribute (Lines 10-11). We say “semantically identical”
because in a DW, common attributes may be presented differently in different
dimensions. Since in a DW, the designer would normally not use two vocabu-
laries to describe a same entity, but may use the different prefixes or suffixes to
distinguish the same entity in different dimensions, we must therefore use string
similarity to match attribute names.

<table><caption>**Algorithm 2:** Inter-dimension Imputation</caption>
  <tbody>
    <tr>
      <td>1</td>
      <td>for each p<sup>H</sup><sub>v</sub> &isin; Param<sup>H</sup>, where H &isin; H<sup>D</sup>, D &isin; D<sup>DW</sup> do</td>
    </tr>
    <tr>
      <td>2</td>
      <td>for each i<sup>D</sup><sub>e</sub> &isin; I<sup>D</sup>, where i<sup>D</sup><sub>e</sub> &middot; p<sup>H</sup><sub>v</sub> is null do</td>
    </tr>
    <tr>
      <td>3</td>
      <td>for each p<sup>H2</sup><sub>v2</sub> &isin; Param<sup>H2</sup>, where H2 &isin; H<sup>D2</sup>, D2 &isin; D<sup>DW</sup> &and; D2 &ne; D do</td>
    </tr>
    <tr>
      <td>4</td>
      <td>if p<sup>H2</sup><sub>v2</sub> &asymp; p<sup>H</sup><sub>v</sub> then</td>
    </tr>
    <tr>
      <td>5</td>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;while p<sup>H2</sup><sub>v3</sub> &isin; Param<sup>H2</sup> &and; p<sup>H2</sup><sub>v3</sub> &leq; H2 p<sup>H2</sup><sub>v2</sub> do</td>
    </tr>
    <tr>
      <td>6</td>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;if &exist; i<sup>D2</sup><sub>e2</sub> &isin; I<sup>D2</sup>, i<sup>D2</sup><sub>e2</sub> &middot; p<sup>H</sup><sub>v3</sub> = i<sup>D</sup><sub>e</sub> &middot; p<sup>H</sup><sub>v3</sub> &and; i<sup>D2</sup><sub>e2</sub> &middot; p<sup>H2</sup><sub>v2</sub> is not null then</td>
    </tr>
    <tr>
      <td>7</td>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i<sup>D</sup><sub>e</sub> &middot; p<sup>H</sup><sub>v</sub> &larr; i<sup>D2</sup><sub>e2</sub> &middot; p<sup>H2</sup><sub>v2</sub></td>
    </tr>
    <tr>
      <td>8</td>
      <td>for each i<sup>D</sup><sub>e3</sub> &isin; I<sup>D</sup>, where w<sup>H</sup><sub>y</sub> &isin; Weak<sup>H</sup>[p<sup>H</sup><sub>v</sub>], i<sup>D</sup><sub>e3</sub> &middot; w<sup>H</sup><sub>y</sub> is null do</td>
    </tr>
    <tr>
      <td>9</td>
      <td>for each p<sup>H3</sup><sub>v4</sub> &isin; H3, where H3 &isin; H<sup>D3</sup>, D3 &isin; D<sup>DW</sup> &and; D3 &ne; D do</td>
    </tr>
    <tr>
      <td>10</td>
      <td>if p<sup>H3</sup><sub>v4</sub> &asymp; p<sup>H</sup><sub>v</sub> &and; &exist; w<sup>H3</sup><sub>y2</sub> &isin; Weak<sup>H3</sup>[p<sup>H3</sup><sub>v4</sub>], w<sup>H3</sup><sub>y2</sub> &asymp; w<sup>H</sup><sub>y</sub> then</td>
    </tr>
    <tr>
      <td>11</td>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;while p<sup>H3</sup><sub>v4</sub> &isin; Param<sup>H3</sup> &and; (p<sup>H3</sup><sub>v5</sub> &leq; H3 p<sup>H</sup><sub>v</sub> &or; p<sup>H3</sup><sub>v5</sub> &asymp; p<sup>H</sup><sub>v</sub>) do</td>
    </tr>
    <tr>
      <td>12</td>
      <td>&nbsp;&nbsp;&nbsp;&nbsp; if &exist; i<sup>D3</sup><sub>e4</sub> &isin; I<sup>D3</sup>, i<sup>D3</sup><sub>e4</sub> &middot; p<sup>H3</sup><sub>v5</sub> = i<sup>D</sup><sub>e3</sub> &middot; p<sup>H3</sup><sub>v5</sub> &and; i<sup>D3</sup><sub>e4</sub> &middot; w<sup>H3</sup><sub>y2</sub> is not null</td>
    </tr>
    <tr>
      <td>13</td>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;then</td>
    </tr>
    <tr>
      <td></td>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i<sup>D</sup><sub>e3</sub> &middot; w<sup>H</sup><sub>y</sub> &larr; i<sup>D3</sup><sub>e4</sub> &middot; w<sup>H3</sup><sub>y2</sub></td>
    </tr>
  </tbody>
</table>

4 Experimental Assessment

We implement our algorithms<fnref n="4" /> and conduct experiments with different datasets.
Our code is developed in Python 3.7 and is executed on a Intel(R) Core(TM)
i5-10210U 1.60 GHz CPU with a 16 GB RAM. Data are integrated in R-OLAP
format with Oracle 11g.

<footnote n="4">⁴ https://github.com/BI4PEOPLE/Internal-Data-Imputationin-Data-Warehouse-Dimensions/</footnote>
## 4.1 Datasets and Experimental Method

Our experiments are based on one benchmark dataset and three real-world datasets. The TPC-H benchmark (TPCH) provides a relational schema<fnref n="5" /> with 8 tables and a data generator we use to produce 100 MB of data. The first real-world dataset is a customer-centric dataset (GlobalStore) of a global super store<fnref n="6" />. It contains the order data of different customers and products. The second real world dataset is a regional sale dataset (RegionalSales) storing sales data for a company across US regions<fnref n="7" />. The third dataset (GeoFrance) contains information about French cities, departments and regions from the French government open data site<fnref n="8" />. We create a DW for each real-world dataset.

In our experiments, the parameter of the first granularity level in dimension hierarchies is the primary key of the dimension table. Its values are not repetitive, so weak attributes of the first granularity level and parameters of the second granularity level cannot be completed. Therefore, we generate missing data for parameters from the third granularity level of dimension hierarchies and for weak attributes from the second granularity level. Moreover, we apply different missing rates (1%, 5%, 10%, 20%, 30%, 40% and 50%). To generate a certain percentage of missing data for an attribute, we sort randomly all the tuples and remove attribute data of the first certain percentage of tuples. For each dataset, we carry out 20 tests and get the average imputation rate, accuracy and runtime. Imputation rate is the number of replaced values divided by the number of missing values. Accuracy is the number of correctly replaced values divided by the number of all replaced values.

## 4.2 Intra-dimensional Imputation Experiments

The datasets **TPCH**, **GlobalStore** and **RegionalSales** are employed in this experiment intra-dimensional imputation experiment. The imputation rate ranges between 61.73% and 100%; the accuracy between 97.08% and 100%; and missing rate between 1% and 50%.

**Imputation Rate** In Figure 1, imputation rates (X-axis) vary with respect to missing rates (Y-axis). We observe that, for dataset **TPCH**, the imputation rate is always 100%, while the imputation rates of the other datasets decrease when the missing rate increases. The imputation rate of **RegionalSales** is much lower than the two others. Since missing data are replaced by the tuple having the same value on a lower-granularity parameter, the imputation rate of an attribute depends on the ratio of the distinct values and the coefficient of variation of each distinct value of its lower-granularity parameters. For example, in the dimension *Part of TPCH*, imputation rate and ratio are 0.125% and 0.027 for the second

<footnote n="5">⁵ http://tpc.org/tpc_documents_current_versions/pdf/tpc-h_v2.18.0.pdf</footnote>

<footnote n="6">⁶ https://data.world/vikas-0731/global-super-store</footnote>

<footnote n="7">⁷ https://data.world/dataman-udit/us-regional-sales-data</footnote>

<footnote n="8">⁸ https://www.data.gouv.fr/fr/datasets/communes-de-france-base-des-codes-postaux/</footnote>
granularity level parameter, respectively; while in dimension *StoreLocation* of
**RegionalSales**, they are 62.13% and 1.1, respectively.

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Intra-dimensional imputation experiment results</figcaption></figure>

**Accuracy** We can see in Figure 1 that the accuracy of **TPCH** is always 100%, while the accuracy of the two other datasets is always less than 100%. Since our imputation method is based on the hierarchy relationships, non-strict and incomplete hierarchies may impact accuracy. By analysing the data, we find that there are non-strict hierarchies in these datasets **GlobalStore** and **RegionalSales**, i.e., in the dimension *Customer* of **GlobalStore**, there are some tuples whose *City* values are the same, but they belong to different *States*. There is a similar case in dimension *StoreLocation* of **RegionalSales**.

**Runtime** The evolution of runtime with respect to missing rate is linear (Figure 1), which is in line with the complexity of Algorithm 1, which is $O(n)$, where $n$ is the missing rate.

**4.3 Inter-dimensional Imputation Experiments**

We use **TPCH** and **GeoFrance** in this inter-dimensional imputation experi-
ment. There are two **TPCH** dimensions, *Customer* and *Supplier*, which have
same geographical attributes. In **GeoFrance**, we create two dimensions and
randomly divide the original data into two partitions with the same number of
tuples. Then, we load each partition into one of the dimensions. The imputation rate ranges between 48.67% and 100%. The accuracy always remain at 100% with respect to missing rate.

**Imputation Rate** Yet again, the imputation rate of TPCH is always 100% (Figure 2), for the same reason as intra-dimensional imputation. GeoFrance's imputation rate is low when the missing rate is very low, then it increases with the missing rate. After analysing the data, we find that there is a tuple where the values of *RegionCode* and *RegioName* are originally missing. The lower-granularity parameter *DepartmentCode* being unique, *RegionCode* and *RegioName* missing data cannot be imputed. When the missing rate is low, the number of total missing data is low, too. Thus, the missing data in this tuple account for a large proportion of total missing data, which can explain why GeoFrance's imputation rate is low when the missing rate is very low.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Inter-dimensional imputation experiment results</figcaption></figure>

**Accuracy** There is no incomplete nor non-strict hierarchy in TPCH's and GeoFrance's DWs. Hence, the accuracy for these two datasets is always 100% (Figure 2).

**Runtime** Again, the evolution of runtime with respect to missing rate is linear (Figure 2), which is in line with the complexity of Algorithm 2, which is $O(n)$, where $n$ is the missing rate.
# 5 Conclusion and future work

In this article, we propose an internal data imputation method for dimensional missing data in DWs. Our method is based on the existing data found in both intra- and inter-dimensional relationships. We take in charge the imputation of both parameters and weak attributes. The solutions are formalized as algorithms and are actually implemented. Our method is validated by a series of experiments with the different percentages of missing data of the different attributes. However, not all missing data can be completed by the existing data, thus in the future we will also combine our method with web-based methods to achieve a better imputation

# Acknowledgement

This research is funded by the French National Research Agency (ANR), project ANR-19-CE23-0005 BI4people (Business Intelligence for the people).

# References

1. F. Amanzougarene, K. Zeitouni, and M. Chachoua. Predicting missing values in a data warehouse by combining constraint programming and knn. In *EDA*, 2014.

2. S. Bimonte, L. Ren, and N. Koueya. A linear programming-based framework for handling missing data in multi-granular data warehouses. *Data & Knowledge Engineering*, 128, 2020.

3. L. de S. Ribeiro, R. R. Goldschmidt, and M. C. Cavalcanti. Complementing data in the etl process. In *DaWaK*, pages 112–123, 2011.

4. W. Fan, L. Jianzhong, M. Shuai, T. Nan, and Y. Wenyuan. Towards certain fixes with editing rules and master data. *The VLDB Journal*, pages 173–184, 2010.

5. D. Li, J. Deogun, W. Spaulding, and B. Shuart. Towards missing data imputation: A study of fuzzy k-means clustering method. In *RSCTC*, pages 573–579, 2004.

6. C. Lofi, K. El Maarry, and W.-T. Balke. Skyline queries over incomplete data-error models for focused crowd-sourcing. In *Conceptual Modeling*, pages 298–312, 2013.

7. F. Ravat, O. Teste, R. Tournier, and G. Zurfluh. Algebraic and graphic languages for olap manipulations. *Inter. J. of Data Warehousing and Mining*, 4:17–46, 2008.

8. J.-J. Shen, C.-C. Chang, and Y.-C. Li. Combined association rules for dealing with missing values. *Journal of Information Science*, 33(4):468–480, 2007.

9. S. Song, A. Zhang, L. Chen, and J. Wang. Enriching data imputation with extensive similarity neighbors. *VLDB Endowment*, 8(11):1286–1297, 2015.

10. C.-H. Wu, C.-H. Wun, and H.-J. Chou. Using association rules for completing missing data. In *HIS*, pages 236–241, 2004.

11. X. Wu and D. Barbará. Modeling and imputation of large incomplete multidimensional datasets. In *DaWak*, pages 286–295, 2002.

12. M. Yakout, K. Ganjam, K. Chakrabarti, and S. Chaudhuri. Infogather: Entity augmentation and attribute discovery by holistic matching with web tables. In *SIGMOD*, page 97–108, 2012.