On the enhancement of Big Data Pipelines through Data Preparation, Data Quality, and the distribution of Optimisation Problems

UNIVERSIDAD DE SEVILLA DOCTORAL THESIS On the enhancement of Big Data Pipelines through Data Preparation, Data Quality, and the distribution of Optimisation Problems Author: Álvaro Valencia Parra Advised by: Dr. Mª Teresa Gómez López Dr. Angel J. Varela Vaca A thesis submitted in fulfillment of the requirements for the degree of Doctor in Computer Engineering in the IDEA Research Group Department of Computer Languages and Systems Escuela Técnica Superior de Ingeniería Informática June, 2022 UNIVERSIDAD DE SEVILLA TESIS DOCTORAL On the enhancement of Big Data Pipelines through Data Preparation, Data Quality, and the distribution of Optimisation Problems Autor: Álvaro Valencia Parra Dirigida por: Dr. Mª Teresa Gómez López Dr. Angel J. Varela Vaca Memoria que presenta para optar al título de Doctor en Informática realizada en IDEA Research Group Departamento de Lenguajes y Sistemas Informáticos Escuela Técnica Superior de Ingeniería Informática Junio de 2022 iii A mis padres. v UNIVERSIDAD DE SEVILLA Abstract Escuela Técnica Superior de Ingeniería Informática Departamento de Lenguajes y Sistemas Informáticos Doctor in Computer Engineering On the enhancement of Big Data Pipelines through Data Preparation, Data Quality, and the distribution of Optimisation Problems by Álvaro Valencia Parra Nowadays, data are fundamental for companies, providing operational support by facilitating daily transactions. Data has also become the cornerstone of strategic decision-making processes in businesses. For this purpose, there are numerous techniques that allow to extract knowledge and value from data. For example, optimisation algorithms excel at supporting decision-making processes to improve the use of resources, time and costs in the organisation. In the current industrial context, organisations usually rely on business processes to orchestrate their daily activities while collecting large amounts of information from heterogeneous sources. Therefore, the support of Big Data technologies (which are based on distributed environments) is required given the volume, variety and speed of data. Then, in order to extract value from the data, a set of techniques or activities is applied in an orderly way and at different stages. This set of techniques or activities, which facilitate the acquisition, preparation, and analysis of data, is known in the literature as Big Data pipelines. In this thesis, the improvement of three stages of the Big Data pipelines is tackled: Data Preparation, Data Quality assessment, and Data Analysis. These improvements can be addressed from an individual perspective, by focussing on each stage, or from a more complex and global perspective, implying the coordination of these stages to create data workflows. The first stage to improve is the Data Preparation by supporting the preparation of data with complex structures (i.e., data with various levels of nested structures, such as arrays). Shortcomings have been found in the literature and current technologies for transforming complex data in a simple way. Therefore, this thesis aims to improve the Data Preparation stage through Domain-Specific Languages (DSLs). Specifically, two DSLs are proposed for different use cases. While one of them is a general-purpose Data Transformation language, the other is a DSL aimed at extracting event logs in a standard format for process mining algorithms. The second area for improvement is about the assessment of Data Quality. Depending on the type of Data Analysis algorithm, poor-quality data can seriously skew the results. A clear example are optimisation algorithms. If the data are not sufficiently accurate and complete, vi the search space can be severely affected. Therefore, this thesis formulates a methodology for modelling Data Quality rules adjusted to the context of use, as well as a tool that facilitates the automation of their assessment. This allows to discard the data that do not meet the quality criteria defined by the organisation. In addition, the proposal includes a framework that helps to select actions to improve the usability of the data. The third and last proposal involves the Data Analysis stage. In this case, this thesis faces the challenge of supporting the use of optimisation problems in Big Data pipelines. There is a lack of methodological solutions that allow computing exhaustive optimisation problems in distributed environments (i.e., those optimisation problems that guarantee the finding of an optimal solution by exploring the whole search space). The resolution of this type of problem in the Big Data context is computationally complex, and can be NP-complete. This is caused by two different factors. On the one hand, the search space can increase significantly as the amount of data to be processed by the optimisation algorithms increases. This challenge is addressed through a technique to generate and group problems with distributed data. On the other hand, processing optimisation problems with complex models and large search spaces in distributed environments is not trivial. Therefore, a proposal is presented for a particular case in this type of scenario. As a result, this thesis develops methodologies that have been published in scientific journals and conferences. The methodologies have been implemented in software tools that are integrated with the Apache Spark data processing engine. The solutions have been validated through tests and use cases with real datasets. vii UNIVERSIDAD DE SEVILLA Resumen Escuela Técnica Superior de Ingeniería Informática Departamento de Lenguajes y Sistemas Informáticos Doctor en Informática On the enhancement of Big Data Pipelines through Data Preparation, Data Quality, and the distribution of Optimisation Problems por Álvaro Valencia Parra Hoy en día los datos se han consolidado como una pieza fundamental en las empresas, ya que, además de facilitar las transacciones del día a día a nivel operacional, ayudan a mejorar la toma de decisiones estratégicas en el negocio. Para ello, existen diversas técnicas que permiten extraer conocimiento y valor de los datos. Un ejemplo son los algoritmos de optimización, los cuales permiten utilizar los datos para dar soporte a la toma de decisiones con el fin de mejorar el uso de los recursos, tiempo y costes en todos los ámbitos de una organización. En el contexto industrial actual, las organizaciones frecuentemente se apoyan en procesos de negocio con los que orquestan sus actividades diarias al mismo tiempo que recolectan grandes cantidades de información de orígenes heterogéneos. Por ello, necesitan el soporte de tecnologías Big Data dado el volumen, la variedad y la velocidad de los datos. El procesamiento mediante técnicas Big Data se lleva a cabo en entornos distribuidos, en los que, según el caso de uso, se aplican una serie de métodos para extraer valor de los datos. Este conjunto de técnicas o actividades, aplicadas de una forma ordenada y en distintas etapas, se denomina Big Data pipeline y facilita la adquisición de los datos, la preparación, y su análisis. Se han detectado aspectos a mejorar en las fases de preparación, valoración de la calidad, y análisis de datos. Estas se pueden abordar desde una perspectiva individual, enfocada en cada fase, o desde un nivel más complejo y global dentro de un workflow de datos. En esta tesis, abordamos la mejora de cada una de estas partes de distintas formas. En primer lugar, esta tesis se enfoca en la preparación de datos con estructuras complejas, es decir, datos con estructuras anidadas a distintos niveles. Se han encontrado carencias en la literatura y en las tecnologías actuales para transformarlos de manera sencilla. Es por eso por lo que esta tesis se propone perfeccionar la preparación de datos complejos mediante Lenguajes Específicos de Dominio (DSL, por sus siglas en inglés). En concreto, se presentan dos, según el caso de uso: uno de propósito general, y otro orientado a la extracción de logs de eventos en un formato estándar para algoritmos de minería de procesos. La segunda área de mejora está relacionada con la valoración de la calidad de los datos. Según el tipo de algoritmo de análisis que se utilice, los datos de mala calidad pueden llegar a 2Chapter 1. Introduction Although this scenario brings great opportunities, several challenges arise. The main challenges are related to the nature of this type of data, which follows three characteristics: There are large amounts of data (volume) generated at high speed (velocity) and showing high heterogeneity (variety). These challenges promoted the emergence of the Big Data paradigm to address these limitations. This paradigm is intended to capture, store, manage, and analyse data [54] that meet the characteristics of volume, velocity, and variety. These characteristics are formally described as the three dimensions of Big Data [52, 53]. Other authors [53, 2, 58] included an additional dimension: Veracity. Following these authors, this dimension is related to the uncertainty and unreliability that are implicit in certain data sources, motivated by the lack of quality of the data, manifested as accuracy, completeness, consistency, latency, ambiguity, and availability issues. Each dimension of Big Data entails several challenges that must be addressed [8]. Focussing on the variety of data, note that processing heterogeneous data is not trivial. In Big Data scenarios, data with different semantics and structures (i.e., structured data with different attributes, or unstructured data such as plain text, logs, images, audio, videos [63, 53]) must be integrated. On the other hand, if we focus on the dimension of veracity, the challenges that arise are related to the quality, reproducibility, and security [91, 28] of the data. The higher volume, variety, and velocity, then the more Data Quality issues [32] (derived from the integration of data from different data sources, with different semantics and schemata), the more complex the reproducibility [36] is (since combining high amounts of heterogeneous data increases the number of operations to perform), and the more security issues might arise [51] (e.g., due to the combination of data with different security and privacy policies). The ultimate objective of the Big Data paradigm is to process this type of data to extract knowledge and value [26, 95, 93]. It is done through Big Data pipelines, which are processes composed of activities to extract value from data. This concept and the activities that make up it have been widely studied in the literature [22, 9, 64, 26]. Big data pipelines play a key role in the industrial context of today [56]. On the one hand, it is capable of providing support at the operational level by facilitating the automation of the processing and storage of transactions in business processes and is capable of processing large volumes of heterogeneous data. On the other hand, the Big Data pipelines are the cornerstone of the strategic and tactical levels of the organisations, since these enables the analysis of the transactional data in conjunction with third-party data. In summary, Big Data pipelines are key to assisting companies in aspects such as decisionmaking in business processes.This thesis focusses on this type of Big Data pipelines and on the use of optimisation algorithms to facilitate decision-making processes.Therefore, we face the challenges derived from the distributed data with Big Data technologies to distribute the computation of optimisation problems so that optimal solutions can be efficiently obtained. Within the optimisation paradigm, several types of algorithms can be found. These can be classified into metaheuristic algorithms [17] and exhaustive algorithms [33]. As we discuss later, there exist several proposals [14, 13, 1, 94] to support metaheuristic algorithms in distributed environments. However, we noted a lack of support for exhaustive optimisation algorithms. Furthermore, exhaustive optimisation algorithms do not scale well, since the 1.1. Context and Motivation 3 computation time significantly increases as the search space increases. This implies an important challenge in the current scenario, since the processing of large volumes of heterogeneous data is required, as well as the computation of more optimisation problems. These factors contribute to increasing search space, leading to scalability issues. The next Section (Section 1.1.2) goes into more detail on the different areas that are subject to improvement in order to support this type of analysis in Big Data pipelines. 1.1.2 Motivation This thesis focusses on the enhancement of those Big Data pipelines that are intended to solve large and complex optimisation problems to assist decision-making processes. We focus on exhaustive optimisation problems, which usually are NP-complete, increasing their complexity as the amount of data to be processed augments due to the increase in the size of the search space. Therefore, we seek to improve this type of analysis in Big Data environments. The optimisation problems can require different data type structures, depending on the optimisation model. For example, in this thesis, we tackle use cases whose optimisation models require data with complex structures (i.e., data with nested arrays or other structures) or very specific data formats. For this reason, we also pursue improving the Data Preparation stage by supporting the transformation of data with complex structures. The results of the optimisation problems are meaningfully influenced by the quality of the input data, requiring the use of Data Quality measurement and assessment techniques to ensure the quality of the results. However, Data Quality measurement and assessment must be performed in accordance with the context of data use. In this thesis, we also strive to enhance the way in which Data Quality is evaluated and modelled. This thesis is developed within the IDEA Research Group1. This group has proven experience in the application of optimisation problems, business process modelling, process mining, and data governance. The need to use techniques based on the Big Data paradigm (and consequently, Big Data pipelines) is derived from research projects at the national and local levels, as well as from collaborative projects with private companies. Next, we present the list of research projects in which this thesis plays a key role: •Aether-US2(PID2020-112540RB-C44). This project aims to improve the way data is managed by following a context-aware basis to support business processes. •ECLIPSE3(RTI2018-094283-B-C33). This project focusseson improving Data Quality and Data Security in business processes. •METAMORFOSIS4(US-1381375). This project aims to support digital transformation processes by improving data management, business processes, and security governance. 1IDEA Research Group: https://www.idea.us.es/ 2Aether-US: https://investigacion.us.es/sisius/sis_proyecto.php?idproy=33855 3ECLIPSE: https://investigacion.us.es/sisius/sis_proyecto.php?idproy=29615 4METAMORFOSIS: https://investigacion.us.es/sisius/sis_proyecto.php?idproy=33186 4Chapter 1. Introduction •COPERNICA5(P20_01224). This project aims to improve business processes through data governance. •Clean Sky 26(P036-19/E08). This project is carried out in collaboration with Airbus. Its objective is to improve the diagnostic of business processes in the aircraft assembly process. This thesis supports the data management and processing part of each of these projects. The ultimate objectives of data processing in these projects are (i) to facilitate decision-making and (ii) to diagnose business processes. optimisation techniques are typically employed for these purposes (e.g., assisting in the selection of an optimal delivery route that reduces the cost, finding an optimal schedule for an industrial activity, selecting optimal configurations, or discovering the deviation between process execution and process model). Since the use cases we handle require processing large volumes of heterogeneous data, we decided to employ Big Data pipelines to address them. However, we discovered that there exists a lack of support for optimisation techniques in Big Data environments. Within the optimisation problem paradigm, the distribution of metaheuristic optimisation problems has been widely studied, and there exist several approaches [14, 13, 1, 94]. Metaheuristic optimisation algorithms [17] do not explore the entire search space. Instead, these employ a heuristic function to find quasi-optimal solutions in a limited time. Therefore, metaheuristic optimisation is not exact, and the results obtained from these types of algorithms can be considered approximations to optimal values. On the other hand, exhaustive optimisation algorithms analyse the whole search space and are able to return the optimal value or values. In this respect, we noticed a lack of proposals for the computation of large-scale exhaustive optimisation problems. Constraint optimisation [73] is one of the most popular exhaustive optimisation paradigms. This paradigm entails techniques that allow us to establish mathematical models to optimise an objective function by taking into account a set of constraints. It has traditionally been of paramount importance in decision-making processes [35, 81, 25], since this paradigm allows us to model real-world problems through mathematical functions. However, this type of problem tends to be NP-complete [33]. In Big Data scenarios, this situation worsens, since large volumes of data could potentially increase search space. In order to face the distribution of Constraint Optimisation Problems (COPs), the distribution of the search space has been proposed as a solution, known as Distributed Constraint Optimisation Problems (D-COP) [42]. However, the algorithms that have been proposed are too complex, since these require sharing and synchronising the problem states and search spaces, not existing commercial solutions applied in Big Data context. In this thesis, instead of distributing the whole search space of these types of problems, we seek to distribute and compute individual non-complex problems. We focus on two particular cases. • The distribution of small individual problems. We call this approach Constraint Optimisation Problems with Distributed Data (COPDD). The idea is that the user groups the 5COPERNICA: https://investigacion.us.es/sisius/sis_proyecto.php?idproy=33720 6Clean Sky 2: https://investigacion.us.es/sisius/sis_proyecto.php?idproy=31890 1.1. Context and Motivation 5 data in such a way that a Constraint Optimisation Problem is formed for each record of the distributed dataset. As an advantage, COPDDs can be solved with traditional constraint optimisation algorithms and solvers. However, there are two drawbacks. On the one hand, each record must have all the information necessary to build the COPs, which potentially implies the appearance of data with complex structures. On the other hand, some individual problems can generate bottlenecks, so techniques are required to reduce the domain of individual problems. • The distribution of big complex optimisation problems.In these cases, the way the distribution is carried out is strongly dependent on the type of problem. As an example, we use the case of conformance checking [21], which is a process mining technique that is fundamental in the diagnosis of business processes, since it allows one to calculate the alignment between the execution of a business process and its model. Conformance checking techniques entail the use of optimisation algorithms in order to find an optimal value within a search space. In this thesis, we seek a methodology to solve conformance checking problems through the distribution of the event logs (i.e., the execution traces of a business process), the decomposition of business process models, and an algorithm to combine and distribute the execution traces along with the different parts of the business process. For these optimisation techniques to be employed in Big Data pipelines, Data Preparation activities must be properly carried out. As we mentioned above, the use of COPDDs may imply the use of data models with complex structures (i.e., data with various levels of nested structures such as arrays). This is the case in the case studies that are faced in this thesis. In our research, we found that most proposals do not support this type of data in a straightforward way, since most of the proposals are specifically designed for table-orientated data models, requiring intermediate abstract operations to perform Data Transformations within the nested data structures. For this reason, we decided to contribute in this direction. Furthermore, referring to the Data Preparation process, the application of process mining techniques, such as conformance checking, requires that the event logs have a specific format (i.e., the XES format [44]). In this direction, we found the opportunity to contribute to the extraction of event log from semi-structured complex data, since we discovered that most approaches are focused on relational data. In conclusion, this thesis seeks to contribute to the Data Preparation activity by supporting the transformation of data with complex structures in both general and process mining contexts. The research projects we mentioned also focus on Data Quality. This is of paramount importance in the context of data governance. Furthermore, the success of the Data Analysis stage depends on the quality of the data, especially when optimisation algorithms are implied. For example, inaccurate data or missing data values can cause errors during the analysis process, leading to failures in decision making or misdiagnosis of business processes [32]. Due to the importance of Data Quality, this thesis also seeks to contribute to this field. In particular, we intend to provide context-aware mechanisms to model Data Quality rules, as well as automate the evaluation of the usability of data. In this way, data records that are not usable 6Chapter 1. Introduction within a particular use case can be discarded, guaranteeing that the Data Analysis process is carried out only with those data records that meet established quality standards. In summary, this thesis intends to improve Data Preparation, Data Quality, and Data Analysis techniques to support the processing of complex data, the extraction of event logs from complex semi-structured data, the modelling of Data Quality rules, the evaluation of the data usability, and the analysis of the data through optimisation techniques. 1.2 Background This section outlines the main concepts that are closely related to this thesis. Section 1.2.1 defines the concept of Big Data pipeline and the activities that make up it. Next, Section 1.2.2 dives into the concept of Data Preparation, and describes several of the most relevant activities related to this stage. Afterwards, Sections 1.2.3 and 1.2.4 show the definition of Data Quality, and describe the decision rule modelling language on which we rely in our proposal to face up the Data Quality rule modelling. Finally, Section 1.2.5 delves into the Data Analysis activities and contextualises the optimisation problem paradigm. 1.2.1 Big Data Pipeline The term Big Data pipeline is extensively studied in the literature [22, 9, 64, 26]. The consensual definition could be that a Big Data pipeline is a process made up of a set of activities that, executed in a coordinated way, allow extracting value from the data. In a preliminary work [88], we performed a thorough study of the literature on the different definitions and descriptions of Big Data pipelines, as well as the activities and stages that comprise them. Figure 1.1 shows the different stages that make up the Big Data pipelines, as well as the activity that could be carried out within each stage. Data Acquisition Data Collection Data Analysis Extensions Data Preparation Data Integration Data Ingestion Data Fusion Data Transformation Extract- Transform- Load Data Wrangling Data Cleaning Data Curation Interpretation and Delivery Data Visualization Query Engine Data Quality Data Provenance Data Security Business Intelligence Data Science Data Storage FIGURE 1.1: Big Data pipeline activities. •Data Acquisition. This stage comprises the extraction and collection of data from different data sources. Activities within this stage involve data collection and ingestion [64, 1.2. Background 7 22] (that is, data extraction from data sources and transportation to the preprocessing stages). •Data Preparation. During the Data Preparation process, the raw data are prepared for the next processing activity in the pipeline. In short, Data Preparation consists of cleaning, formatting, transforming, and integrating data [22, 9]. •Data Analysis. Its objective is to extract value from the data. There are several activities and algorithms that can perform this task [26]. •Interpretation and Delivery. It is the final stage of a Big Data pipeline, and its objective is to report the value extracted from the data [22, 9, 26]. These results are consumed by end users or services. The way data are represented and delivered depends on the context of its use. This Big Data pipeline framework also includes several additional activities: •Extension activities. These activities are intended to provide support during the entire life cycle of the pipeline. These are: (i) Data Curation, which comprises the management of data during its life cycle [46] and entails monitoring the quality of the data and its enrichment; (ii) Data Quality, which involves monitoring the degree to which data satisfy requirements for its use [75]; (iii) Data Provenance, which is intended to keep track of the data during its life cycle [5], and; (iv) Data Security, which establishes the security requirements of the data and monitors their fulfilment during the life cycle. •Data Storage. This is a transversal activity that provides persistence and access features when required by any activity. There exist technologies that support modelling and executing Big Data pipelines. For example, Apache Spark [7], is a data processing engine that enables the programmatic implementation of data pipelines and workflows. This tool also implements functionalities to carry out certain activities of the Big Data pipelines. In this thesis, we focus mainly on Apache Spark and strive to enrich this tool by implementing the different methodologies that we devise. 1.2.2 Data Preparation The Data Preparation stage is composed of activities that are intended to prepare the data for its analysis [9] by giving the data the appropriate format. In other words, it strives to transform raw data into a clean consumable dataset [48]. Next, we list typical activities that could be carried out in the Data Preparation stage. •Data Cleaning. Data cleaning aims to identify and repair data values that fail to meet the Data Quality requirements of the use case [70, 45]. •Data Integration. This activity aims to provide unified access to data by combining data from different data sources [29, 48]. 8Chapter 1. Introduction •Data Transformation. It is intended to facilitate data conversion and reformatting in order to adapt raw data to a specific data model [Cong2009, 48]. This process, which entails the transformation of the data schema and the modification and creation of data attributes, can be applied to structured, semi-structured, and unstructured data schemata. •Extract-Transform-Load (ETL). This is a paradigm that has traditionally been applied to data warehouses [30]. This concept refers to the integration, cleaning, and transformation of heterogeneous data with the objective of unifying the schema and format of data from several data sources. •Data Wrangling. This concept has recently become popular [43]. This activity aims to provide Data Transformation mechanisms to non-expert users [41] so that they can transform structured, semi-structured, and unstructured data without high domain knowledge. Specifically, we focus on the Data Transformation activity. Data Transformation has traditionally been used in data warehouses for Data Preparation through general purpose query languages or software to support ETL (Extract, Transform Loads) processes [23, 24]. However, ETL processes typically require specific and ad-hoc tools, as well as specialised programming skills. In [50], Joseph et al. remark on the differences between ETL and the new research concept of self-service Data Preparation [16], which is closely related to Data Wrangling. This activity has evolved into a new paradigm where the transformations are provided by non-expert users to perform end-to-end Data Preparation without programming knowledge. Currently, the efforts are directed towards facilitating and enriching the Data Transformations. These lines of research are consistent with the need to speed up the design of Big Data pipelines. An easy implementation of Data Transformation stages is crucial in order to effectively test alternative solutions and compare their results or to adapt a pipeline to a new or evolving source of data [22]. In this direction, several tools have been produced. Trifacta Wrangler™[50] and other derived tools such as Google Cloud Dataprep are examples of solutions that enable Data Transformation. However, most of the solutions, including Trifacta, are specialised in table-orientated data models, requiring a number of intermediate abstract operations to modify data that are in deep levels of the data structure. In this context, it is of paramount importance to identify languages to facilitate the transformation of complex data structures [11]. 1.2.3 Data Quality Data Quality can be formally defined as a condition of data that can be measured and assessed through a set of characteristics or dimensions [15]. In the Big Data pipeline, Data Quality is typically used as part of the Data Preparation process [78] by providing insights that can be useful during Data Cleaning activities. With respect to Data Quality measurement and assessment, we rely on the notion adopted by Juran [77] and I. Caballero [19], which states that the objective of the Data Quality assessment is to assess how usable data are in a specific context. On the other hand, Data Quality 1.2. Background 9 measurement is focused on measuring how well data are built according to a set of requirements or rules. Regarding the Data Quality model, we rely on the one proposed in the international standard ISO 25012 [75]. This model states that the measurement of the Data Quality depends on one or several Data Quality dimensions (a.k.a. Data Quality characteristics). The characteristics to measure depend on the context in which the data are used. The completeness (i.e., the degree to which the data are complete), the accuracy (i.e., the degree to which the data are accurate) and the consistency (i.e., the degree to which data are consistent) are examples of Data Quality dimensions. 1.2.4 Decision Model and Notation (DMN) DMN is a decision rule modelling standard [60] created by the Object Management Group (OMG). DMN offers a framework that enables the creation of decision rules visually, grouping them into decision tables (i.e., DMN tables). The decision rules are specified in different rows by following an if-then logic. In summary, the DMN tables are composed of three parts. •Inputs. These represent the input attributes whose values will be evaluated; •Outputs. These are intended to indicate the output value that would be produced if the decision rule is triggered. •Rows. Each row specifies the set of conditions that the input values must meet to produce the output value indicated in that row. Regarding the output, each DMN table can return one or multiple values depending on (i) the number of decision rules (rows) that are triggered and (ii) the hit policy specified in the DMN table. The hit policy enables one to define how to handle multiple matches. Some examples of hit policies are as follows. •First (F): In case multiple decision rules are triggered, return the output which corresponds to the first decision rule defined in the table. •Priority (P): In case multiple decision rules are triggered, return the one with highest priority. •Unique (U). Only one decision rule must be triggered. •Collect (C): In case several decision rules are triggered, return an aggregation of their corresponding outputs (see [60] for further hit policies and details). DMN supports expression languages that facilitate the description of the conditions that data must meet. In our proposal, we rely on the FEEL7expression language. It is a versatile language that supports several data types (e.g., Integer, Decimal, Date, String, Boolean), and offers a set of built-in functions to write complex conditions. Its versatility also enables users to modify and write their own built-in functions. Finally, note that FEEL supports conditions that are always true (“-"). 7https://docs.camunda.org/manual/7.4/reference/dmn11/feel/ 10 Chapter 1. Introduction 1.2.5 Data Analysis and Optimisation Problems The Data Analysis stage includes activities that use algorithms to extract value from the data [22]. These activities take properly structured and formatted data as input so that the algorithm can process them properly. Depending on the ultimate objective of the pipeline, the analysis can be [9, 67] descriptive (i.e., the objective is to identify phenomena and discover their causes), predictive (i.e., the objective is the prediction of future events), or prescriptive (i.e., the objective is to assist in decision making once an event has been detected through a descriptive or predictive analysis). This dissertation focusses on the use of optimisation problems in the Data Analysis stage. These techniques are widely used in decision making scenarios [35, 81, 25] to help optimise resources, costs, or time. Optimisation techniques enable modelling real-world problems in the form of a set of variables and one or more objective functions that depend on that set of variables. These algorithms try to find a combination of values for the variables that maximise or minimise the value returned by the objective function. With respect to optimisation algorithms, several techniques can be found in the literature. In summary, these can be classified into metaheuristic or exhaustive optimisation algorithms. •Metaheuristic optimisation algorithms. These algorithms do not explore the entire search space [17]. Instead, these use heuristic functions use that guide the search towards local optimal values. •Exhaustive optimisation algorithms. These algorithms explore the entire search space, and therefore are able to find global optimal values, guaranteeing the finding of optimal values. The main drawback of exhaustive optimisation algorithms is the fact that these can become NP-complete [33] depending on the search space, negatively affecting to the scalability. However, metaheuristic optimisation algorithms can be more scalable in certain cases [94]. In this thesis, we focus on exhaustive optimisation problems, in general, and on Constraint Optimisation Problems (COPs), in particular. A Constraint Optimisation Problem [73] is a Constraint Satisfaction Problem (CSP) with an objective function that must be optimised according to the criteria defined by the user. Therefore, the optimal value reached by the objective function represents the best solution among all possible solutions. Next, we include a formal definition of CSP, given by M. T. Gómez-López et al. [38]. A CSP represents a reasoning framework consisting of variables, domains and constraints ⟨V,D,C⟩, where Vis a set of nvariables {v1,v2, . . ., vn}whose values are taken from finite domains {Dv1,Dv2, . . ., Dvn} respectively, and Cis a set of constraints on their values. The constraint ck (xk1, . . ., xkm)is a predicate defined on the Cartesian product Dk1×. . . ×Dkm. This predicate is true iff the assignment of the value of each variable xkisatisfies the constraint ck. Therefore, a COP is intended to explore the search space of the variables V, limited by their domain Dand constraints C. This exploration strives to optimise an objective function which must be minimised or maximised (i.e., the objective could be finding the minimum or maximum value returned for this function). The objective function depends on the values 1.3. Objectives 11 taken by the variables V. The values taken by each variable vi∈Vmust be within the domain of this variable (Dvi), and must meet the predicates defined in each constraint ck. Then, the best solution is the set of variables values that returns the optimal value. 1.3 Objectives In this Section, the objectives of this thesis are presented. These are related to the enhancement of various activities in the Big Data pipelines to help companies process their data, emphasising those use cases that require using optimisation problems for decision making. Given the context in which this thesis is developed, the objectives traced are related to improving Data Preparation, Data Quality, and Data Analysis activities. Figure 1.2 summarises the three global objectives that we address. •OBJ 1. This objective is related to the Data Preparation stage. In particular, it addresses the transformation of complex data and the extraction of event logs from complex semistructured data. •OBJ 2. This objective aims to improve the Data Quality activity by enhancing the way in which Data Quality rules are modelled, focusing on a context-aware basis. This objective also aims to promote the automation of data usability evaluation and the improvement of data usability repair. •OBJ 3. The last objective is related to the Data Analysis stage. It aims to improve the computation of optimisation problems with distributed data. Data AnalysisData Preparation Data Acquisition OBJ 1 OBJ 3 Interpretation and Delivery Data Storage Data Transformation Small Individual Optimisation problems Big Complex Optimisation Problems Event log extraction Extensions Data Quality OBJ 2 Data quality modelling Data usability evaluation and repair Data Curation Data Provenance Data Security OBJ 2.1 OBJ 2.2 OBJ 1.1 OBJ 1.2 OBJ 3.1 OBJ 3.2 FIGURE 1.2: Summary of the objectives of this dissertation. 18 Chapter 1. Introduction Both solutions are presented in Chapter 2 (Section 2.4). The results that have been produced with respect to the objectives OBJ 3.1 and OBJ 3.2 are discussed in Chapter 3. 1.4. Research Methodology and Resources 19 Problems identified Objectives traced Solutions designed and developed Global Problem Enhancement of Big Data Pipelines P-DT. Data Transformation of data with complex structures P-DT-1. General-purpose complex data transformation P-DT-2. Transformation and extraction of event logs OBJ 1. Improve the Data Preparation process with complex data structures OBJ 1.1. Develop a DSL supported by a framework to transform complex data OBJ 1.2. Develop a DSL to support the extraction of event logs from semistructured data S-DT-1. Data Chamaleon framework S-DT-2. Data Chamaleon DSL S-DT-3. Event Log Extractor DSL Demonstrations and evaluations carried out Communications Activity 1 Activity 2 Activity 3 Activities 4 and 5 Activity 6 D-DT-1. Data Chamaleon framework benchmark UC-DT-1. Complex Data Transformation of data from electricity distribution companies UC-DT-2. Extraction of event logs from Airbus aircraft manufacturing logs P-DT-1. Data Chamaleon: Framework to improve Data Wrangling with Complex Data Presented in ICIS'19 P-DT-2. Enabling Process Mining in Airbus Manufacturing Presented in BPM'19 Industry Forum and published in BPM Cases Vol.2 METHODOLOGY OUTPUTS FOR THE DATA PREPARATION SCOPE Class 2 P-DT-1. General-purpose complex data transformation P-DT-2. Transformation and extraction of event logs P-DT. Data Transformation of data with complex structures OBJ 1. Improve the Data Preparation process with complex data structures OBJ 1.2. Develop a DSL to support the extraction of event logs from semistructured data FIGURE 1.3: Methodology activities outputs related to the Data Preparation scope. 20 Chapter 1. Introduction Problems identified Objectives traced Solutions designed and developed Global Problem Enhancement of Big Data Pipelines P-DQ. Data Quality modelling and evaluation in a context-aware basis P-DQ-1. Data Quality modelling P-DQ-2. Data Usability evaluation and repair OBJ 2. Improve the evaluation of Data Quality OBJ 2.1. Develop a methodology to model Data Quality rules in a contextaware basis OBJ 2.2. Develop a framework to facilitate the detection of the root causes of poor quality data, as well as data repair S-DQ-1. DMN4DQ Methodology S-DQ-3. DMN4DQ+ framework Demonstrations and evaluations carried out Communications Activity 1 Activity 2 Activity 3 Activities 4 and 5 Activity 6 D-DQ-1. DMN4DQ+ Benchmark UC-DQ-1. Evaluation of the data usability of data in the context of catalogue cloud server instances P-DQ-2. DMN4DQ: When Data Quality meets DMN Published in DSS P-DQ-3. Optimising Data Repair to enhance Data Usability To be published in DSS METHODOLOGY OUTPUTS FOR THE DATA QUALITY SCOPE S-DQ-2. DMN4Spark tool UC-DQ-2. Repair of the usability of nonusable data from the catalogue of cloud server instances P-DQ-1. DMN for Data Quality Measurement and Assessment Presented in DEC2H'19 Q1 FIGURE 1.4: Methodology activities outputs related to the Data Quality scope. 1.4. Research Methodology and Resources 21 Problems identified Objectives traced Solutions designed and developed Global Problem Enhancement of Big Data Pipelines P-OP. Generation and computation of distributed optimisation problems P-OP-1. Computation of large volumes of Constraint Optimisation Problems P-OP-2. Computation of big complex optimisation problems OBJ 3. Enhance the computation of optimisation problems in Big Data environments OBJ 3.1. Develop a framework to model, generate and solve Constraint Optimisation problems in Big Data Pipelines OBJ 3.2. Develop a solution to compute big complex optimisation problems in Big Data environments applied to Conformance Checking techniques Demonstrations and evaluations carried out Communications Activity 1 Activity 2 Activity 3 Activities 4 and 5 Activity 6 UC-OP-1. Optimisation of electricity bill settings P-OP-1. Unleashing Constraint Optimisation Problem solving in Big Data environments Published in JCOS P-OP-2. Empowering conformance checking using Big Data through horizontal decomposition Published in Inf.Syst. METHODOLOGY OUTPUTS FOR THE DATA ANALYSIS SCOPE S-OP-2. Methodology to compute big complex conformance checking problems implemented in CC4Spark P-OP-3. CC4Spark: Distributing Event Logs and big complex Conformance Checking Problems Presented in BPM'21 Tools & Resources. S-OP-1. Framework to compute COPDDs implemented in FABIOLA D-OP-2. CC4Spark benchmark UC-OP-2. Detecting deviations in milk manufacturing process D-OP-1. FABIOLA benchmark Q3 Q2 OBJ 3.1. Develop a framework to model, generate and solve Constraint Optimisation problems in Big Data Pipelines OBJ 3.2. Develop a solution to compute big complex optimisation problems in Big Data environments applied to Conformance Checking techniques OBJ 3. Enhance the computation of optimisation problems in Big Data environments OBJ 3.1. Develop a framework to model, generate, and solve Constraint Optimisation Problems with Distributed Data OBJ 3.2. Develop a solution to compute big complex optimisation problems in Big Data environments applied to Conformance Checking techniques. OBJ 3. Enhance the distribution and computation of optimisation problems in Big Data environments. P-OP-1. Computation of large volumes of Constraint Optimisation Problems FIGURE 1.5: Methodology activities outputs related to the Data Analysis scope. 22 Chapter 1. Introduction 1.4.3 Resources With regard to resources, the following have been used during the development of this research project: • Scientific documentation. Research has been carried out through the study of the literature. The University of Seville has provided access to different scientific databases. • Cloud servers and clusters. The IDEA Research Group has provided a private cloud. This cloud has been used to deploy big data processing and storage tools. • Big Data processing tools, such as Apache Spark and Apache Kafka. • Database management systems such as MongoDB and MySQL. • Additional software to produce diagrams (such as draw.io, Microsoft Visio, Astah), documents (Latex through Overleaf, Microsoft Word), and presentations (Google Presentations, Microsoft PowerPoint). All the software resources that have been employed are either open source or proprietary. The proprietary software has been employed through licences provided by the University of Seville. 1.5 Roadmap The remainder of this thesis is structured as follows. Chapter 2 presents a summary of the results obtained for each objective defined in Section 1.3. Chapter 3 discusses the results and presents the publications that form and support this thesis. Finally, Chapter 4 draws conclusions from this thesis and discusses future work. 23 Chapter 2 Summary of the Results This chapter presents the results of the research of this dissertation, introducing the different solutions that have been developed to fulfil the objectives defined. Section 2.1 gives an overall view of the results. Next, Sections 2.2, 2.3 and 2.4 describe and summarise the results related to the Data Preparation, Data Quality and Data Analysis stages, respectively. Finally, Section 2.5 presents two use cases in which the different solutions that have been proposed are employed. 2.1 Introduction to the results As advanced in Chapter 1, the objectives of this thesis can be grouped into three large blocks: Data Preparation, Data Quality, and Data Analysis. Therefore, in this section, the results are presented following the same logic. First, in Section 2.2 the results related to the Data Preparation stage are presented: A Data Wrangling language to transform data with complex structures and a Domain-Specific Language to transform semi-structured data into XES event logs. Second, in Section 2.3 the results related to the Data Quality assessment activity are presented. There, we describe DMN4DQ, a context-aware methodology to assess the usability of the data. We also present a proposal to automate the Data Quality assessment, and a framework to help users repair their data. Finally, in Section 2.4, we present the results related to the Data Analysis activity, a solution to generate and solve Constraint Optimisation Problems in Big Data environments, and a solution to solve big complex conformance checking problems. 2.2 Data Preparation (OBJ 1) This Section describes the solutions developed to accomplish objectives OBJ 1.1 and OBJ 1.2. • The solution S-DT-1 (Data Chameleon framework) supports both OBJ 1.1 and OBJ 1.2. The framework is presented in this Section. • The solution S-DT-2 (Data Chamaleon DSL) iis intended to satisfy OBJ 1.1. This is presented in Section 2.2.1. • The Solution S-DT-3 (Event Log Extractor DSL) fulfills OBJ 1.2. This is described in Section 2.2.2. 24 Chapter 2. Summary of the Results Our proposal to contribute to the Data Preparation with complex structures has two parts. On the one hand, we propose Data Chameleon [83], a general-purpose Data Transformation framework that includes a Domain-Specific Language (hereinafter, DSL) to transform data with complex schemata. Besides, we developed Event Log Extractor [86] (ELE), a DSL based on the Data Chameleon framework. ELE is designed for a specific domain: The transformation of business process event logs with complex data structures into a standard process mining format (XES [44]). First, we must define what “complex data" means. Complex data are data structures that contain several levels of depth and consist of lists of data structures. According to our study[83], there is a lack of tools that facilitate Data Transformation with different depth levels. Traditional tools do not allow one to operate directly with these types of structure and require intermediate operations to bring the nested levels to the top level of the data schema. Data Chameleon intends to avoid these intermediate transformations, pretending that each operation applied to the source data has the desired final effect on the destination data. Figure 2.1 shows an overview of the position of the Data Chameleon in a Big Data pipeline. The objective of it is to make the transformation of (complex) data from different data sources easier. In this example, different transformation recipes (i.e., T1,T2 and Tn) are applied to unify the data structure of the data from different sources. This standardisation enables the application of Data Analysis algorithms. Data Acquisition Data Preparation Data Analysis DS1 DS2 T1 T2 DSn ... ... Tn Delivery and Interpretation FIGURE 2.1: Data Chamaleon acts in the Data Prepration phase. Data Chamaleon consists of a core framework that we have developed1. This can be extended to different DSLs. Figure 2.2 illustrates this differentiation. The Data Chameleon DSL is introduced in Section 2.2.1, while the ELE DSL is described in Section 2.2.2. With regard to the framework, it supports simple (i.e., String, Date, Boolean, Double, Float, Long and Integer) and complex data types, such as arrays (i.e., an indexed collection of typed attributes) and structures (i.e., a structure composed of a set of attributes with unique names). The implementation is supported by the Scala programming language [80], and is supported by a structure of classes following the composite design pattern [72], allowing complex objects to 1Data Chamaleon: https://github.com/IDEA-Research-Group/Data-Chameleon 2.2. Data Preparation (OBJ 1) 25 be created from simpler ones. This is fundamental in our proposal, since it allows modelling the transformations of nested structures by means of composite classes. Data Chamaleon Event Log Extractor (ELE) DSL Framework data-chamaleon-core ... FIGURE 2.2: The Data Chamaleon framework can be extended by multiple Domain-Specific Languages (DSL). 2.2.1 Data Chameleon DSL: A general-purpose complex Data Transformation language Next, we briefly describe the definition of the Data Chamaleon default DSL, extracted from our publication [83]. As mentioned above, this is a general-purpose DSL for performing all sorts of transformations. The definition is given through the Extended Backus-Naur form notation [71] in the Listing 2.1. 1 Syntax : := Expression 2 Expression ::= Select|Index|Rename|CreateStruct|CreateArray|Iterat e 3 |Transform 4 Select :: = ' t ' '" ' ( StringLiteral | ' [ ' Digit+ '] ' ) 5 ( ' . ' ( StringLiteral | ' [ ' Digit+ '] ' ) )*' " ' 6 Rename ::= StringLiteral '<<' Expression 7 CreateStruct : := ' struct ' ' ( ' Expression ( ' , ' Expression )*') ' 8 CreateArray : := ' array ' ' ( ' Expression ( ' , ' Expression )*' ) ' 9 Iterat e : := Expression ' iterate ' Expression Transform 10 Transform ::= Expression '−> ' DTF 11 DTF ::= 'max'| 'min'| ' avg '| 'sum'| ' substract '| ' t o I n t | 'toDouble ' 12 | ' toString '| ' toDate ( ' StringLiteral ' ) ' LISTING 2.1: Data Chamaleon DSL syntax definition. This proposal was applied to two case studies [83]. For the sake of simplicity, in this summary, we show only one: The case study of Airbus, an aircraft manufacturer. The data contains information on the aircraft testing process. The dataset, which is given as a JSON file, contains information about the workstations (i.e., the stations where the aircrafts are tested). Each of them produces data on the tests that are carried out there, indicating the code of the workstation (workstation), the aircraft tested (accode), and a nested attribute indicating the list of incidents detected during the tests (incidents). Each incident is described with three attributes that indicate the date on which the incident began (start_date), the date on which the incident was resolved (resolution_date), and the type of incident (incident_type). Both date fields are represented as Strings with a specific format. Figure 2.3 depicts the source and target schemata. The transformations are as follows. 26 Chapter 2. Summary of the Results •T1 and T2. Rename the attributes accode and workstation to aircraft and ws, respectively. •T3. Create a new field avg_resolution_time, which represents the average resolution time. accode: string workstation: string incidents: array element: struct: start_date: string resolution_date: string incident_type: string aircraft: string ws: string avg_resolution_time: double T3 T1 T2 FIGURE 2.3: Left: Source schema. Right: Target schema. The transformations are shown in Listing 2.2. Lines 1 and 2 perform transformations T1 and T2, while lines 3-6 perform transformation T3. In T1 and T2, the operator ”<<" is employed to perform the rename operation. In T3, the array of incidents is iterated using the “iterate" operator. For each nested structure, the attributes resolution_date and start_date are transformed into date data types. This is done with the “toDate" transformation function, indicating the format of the date. Once transformed, both attributes are subtracted by means of the transformation function “ substract". Finally, the average of the resulting array is calculated with the “avg" transformation function. 1 " a i r c r a f t " << t " accode " 2 "ws" << t " workstation " 3 " avg_resolution_time " << ( t " incidents " iter ate substract ( 4 t " resolution_date " −> toDate ("MM/dd/yyyy HH:mm: ss ") , 5 t " start_date " −> toDate ("MM/dd/yyyy HH:mm: ss ") 6 )) −> avg LISTING 2.2: BNF Notation As we explained previously, CHAMELEON DSL aims to abstract the user from intermediate operations when performing complex transformations. In our study, we compare it to a leading Data Wrangling tool, Trifacta. Trifacta is a table-orientated tool that requires transformations to be performed at the top of the data structure. In Trifacta, this case study requires a total of seven operations, of which 4 (57%) are intermediate, that is, these are necessary in order to bring the nested structures to the top level of the schema (e.g., flattening, dropping, or renaming), increasing the difficulty of the transformations. 2.2.2 ELE DSL: A language to extract and transform event logs In the current industrial context, business processes tend to employ a myriad of IoT sensors to monitor processes. Consequently, it favours the proliferation of event logs with different structures and formats. In this context, specialised techniques are required to extract and transform event logs into such a format that they can be employed during the use of process 2.2. Data Preparation (OBJ 1) 27 mining algorithms. Within the Big Data pipelines, the extraction of event logs from data can be considered a Data Preparation activity, which strives to transform, format, and prepare the event logs for their consumption by process mining techniques such as conformance checking. In the literature, several authors agree on the importance of extracting event logs to proceed with the analysis of business processes [37, 12, 20, 57]. Some proposals focus on extracting event logs from relational data [57, 20], while others focus on XML, JSON, or other types of unstructured log files [37, 12]. However, we have not found any proposal focused on the transformation of complex structures into XES [44] event logs. In this context, we propose ELE2(Event Log Extractor) [86], a DSL that enables the transformation of event logs into XES [44] event logs. It is the result of a collaboration with Airbus and aims to improve the extraction of event logs from IoT scenarios. Since it is based on the Chameleon framework, it is capable of processing event logs with complex nested structures. Figure 2.4 shows an example in which extraction recipe is applied to produce XES event logs. The XES [44] format is an IEEE standard (IEEE 1849-2016) that aims at standardising the way in which process logs are represented. In short, XES event logs are made up of the following fields. •Case ID: It is the identifier of a specific instance or case of the process. •Activity: It represents the identifier of a particular event and is associated with the case in which the event takes place. •Timestamp: this is an attribute of the event that indicates the moment when the event occurred. Log, traces, and events can have more attributes according to the standard, and ELE supports some of these, such as Resource,TransactionType,Costs or Customer. Listing 2.3 shows the syntax definition of ELE using the Extended Backus-Naur form notation. It reuses elements from the Data Chamaleon DSL (Expression refers to the definition given in Listing 2.1 line 2). In this way, the trace ID (line 2) and the elements that compose the Event (lines 3-6) can be defined as a complex Data Transformation. 1 Syntax : := ' extract ( ' Trace Event ' ) ' From Save 2 Trace ::= ' define trace id ( ' Expression ') ' 3 Event :: = ' define trace event ( ' ( ' acti vity = ' Expression ) | 4 ( ' a ctivity = ' Expression ) | ( ' timestamp = ' Expression ) | 5 ( ' resource = ' Expression ) | ( ' transactionType = ' Expression ) | 6 ( ' costs = ' Expression ) | ( ' customer = ' Expression ) ') ' 7 From :: = 'from ' String 8 Save ::= ' save ' String LISTING 2.3: ELE syntax definition. Listing 2.4 shows an example of the use of this DSL. This is an extract of our work published in Business Process Management Cases Vol. 2 [87], where we solve three different scenarios 2Event Log Extractor DSL: https://github.com/IDEA-Research-Group/ELE 34 Chapter 2. Summary of the Results each data record, this graph is generated as follows. First, the nodes are built hierarchically as follows. • Decision. This is the root node, and its value represents the output of the evaluation of the DMN table BR.DUD. • Assessment. This node is the child of the Decision node, and its value represents the output of the DMN table BR.DQA. • Measurement. These nodes are children of the Assessment node. There is a node for each Data Quality dimension, and their value are the output of the BR.DQM DMN tables. • Observations. These nodes are the children of the Measurement nodes. There is a node for each BR.DV table, and its values correspond to the output of these tables. Regarding the edges, these have the following semantics: There is an edge between a node nand its children nodes if the values represented by the children nodes produce the output represented by n. Following the example in Figure 2.7, we have calculated the usability profiles using that model and the dataset we used in our work [89]. This dataset contains 1,048,571 records and produced 29 different usability profiles, of which 22 had the usability decision “do not use". In Figure 2.8, we show three of these usability profiles, of which up1and up2are classified as “do not use", and up3is classified as “use". There are 97,120 records with the usability profile up1, 53,247 with up2, and 221, 147 records with the usability profile up3. This representation facilitates the diagnosis of the root causes of poor-quality data. BR.DUD do not use BR.DQA bad quality BR.DQM.Completeness not complete BR.DV.01 false BRDV.02 false ClockSpeed Memory BR.DQM.Accuracy 0 BR.DV.03 false up1 (A) Usability profile up1. BR.DUD do not use BR.DQA bad quality BR.DQM.Completeness complete BR.DV.01 true BRDV.02 false ClockSpeed Memory BR.DQM.Accuracy 0 BR.DV.03 false up2 (B) Usability profile up2. BR.DUD use BR.DQA suitable BR.DQM.Completeness complete BR.DV.01 true BRDV.02 true ClockSpeed Memory BR.DQM.Accuracy 100 BR.DV.03 true up3 (C) Usability profile up3. FIGURE 2.8: Usability profiles in the guiding example. DMN4DQ+ also proposes a methodology to help users find an optimal set of corrective actions to repair their data. This methodology requires users to relate each BR.DV to a specific Data Quality problem (i.e., a problem derived from non-compliance with business rules). Data Quality problems have been widely studied in the literature [92, 59, 6]. P. Woodall et al. [92] proposed a set of techniques to solve each type of Data Quality problem. In our methodology, 2.4. Data Analysis (OBJ 3) 35 we studied the classifications of these authors and formalised a list of Data Quality problems that can be detected with DMN4DQ, and a set of corrective actions associated with each Data Quality problem. Regarding Data Quality problems, since DMN4DQ performs the evaluation record-by-record, the Data Quality problems that can be detected are those that comprise one or multiple attributes in a single tuple (e.g., syntax violation or violation of functional dependency). DMN4DQ+ allows the user to define a catalogue of corrective actions. This catalogue includes, for each corrective action: • The Data Quality problem to solve (e.g., violation of functional dependency). • The corrective action to apply (e.g., data rules). • The attributes that would be affected by such action. • The operation to perform (e.g., in this case, the specific data rules to apply). • The consequences of the application of the corrective action (i.e., the user must specify the new outputs of the BR.DVs affected by the corrective action). • The requirements and conditions, which include the output values required for each BR.DV before applying the corrective action. • The cost of applying the corrective action. This cost must be set by the user using a Likert scale, which weighs the cost in human and computational terms. Once the catalogue of corrective actions has been defined, the user can specify one usability profile to repair (e.g., a usability profile whose usability decision is “do not use"). We have developed a Constraint Optimisation Problem to select the set of corrective actions that modify the usability profile so that the usability decision is “use" with the optimal cost. The Constraint Optimisation Problem takes the following inputs: (i) the Data Quality model (i.e., the DMN model) in order to transform the DMN rules into constraints; (ii) the catalogue of corrective actions in order to build the constraints and variables, and (iii) the usability profile to repair. The variables are intended to select the corrective actions to perform, while the constraints allow one to bound the eligible actions by checking their feasibility in accordance to the consequences and conditions of the corrective action and the Data Quality model. 2.4 Data Analysis (OBJ 3) This Section describes the solutions developed to accomplish objectives OBJ 3.1 and OBJ 3.2. • The solution S-OP-1 (Framework to compute COPDDs implemented in FABIOLA) supports the objective OBJ 3.1, and is presented in Section 2.4.1. • The solution S-OP-2 (Methodology to compute big complex conformance checking problems implemented in CC4Spark) is intended to satisfy the objective OBJ 3.2. This is presented in Section 2.4.2. 36 Chapter 2. Summary of the Results 2.4.1 Constraint Optimisation Problem solving in Big Data environments Our proposal is motivated by the importance of Constraint Optimisation Problems (hereinafter COP) within the decision-making paradigm. Formally, a COP is a reasoning framework that consists of input data, variables, constraints, and an objective function. The COP algorithms are intended to optimise the objective function either by maximising or minimising it by producing permutations of values that the variables take. These values are bounded within a specific domain and must meet the defined constraints. Since COP algorithms are ultimately implemented through search algorithms, certain COPs can become NP-complete [33]. Furthermore, the complexity of the COPs increases as the amount of data increases. This complexity is motivated by an increase in the amount of input, variables, and constraints. In this distributed context, Distributed Constraint Optimisation Problems (hereinafter DCOPs) emerged [42]. These were intended to solve COPs where constraints, variables, and data were not in a single system. The algorithms must then be able to share and synchronise the problem states and search spaces. However, DCOPs are not focused on Big Data environments and do not provide mechanisms to enhance the distribution of COPs. Therefore, our proposal focusses on improving the computation of individual COPs in distributed environments and optimisation of the execution of queries by distributing the COPs in chunks of data. Next, we discuss the concept of Constraint Optimisation Problem with Distributed Data (hereinafter COPDD), which summarises our contribution in [90]. A COPDD is applied to a dataset DS, and produces a dataset DSoutput that includes the results of the COPs for each chunk of data. Therefore, a COPDD is composed of the following elements: ⟨COP, DS, DM, DMAPDS→DM,DMAPDM→COP⟩. •COP. This represents the model of the Constraint Optimisation Problem to be computed for each piece of data. •DS. The dataset that is employed to build the COPs. •DM. This serves as the data model which specifies the relationships between the attributes of the dataset (DS) and the COP model (COP). •DMAPDS→DM. This element alludes to the data mapping (i.e., the attribute alignment) between the dataset attributes (DS) and the attributes of the data model (DM). •DMAPDM→COP. This refers to the data mapping between the attributes of the data model and the COP model. Figure 2.9 summarises the phases that we propose for the generation and resolution of COPDDs. •Data Preparation. At this stage, the datasets are integrated and transformed so that they can be mapped to the data model (DM). •COP description. It contains the definition of the COP (i.e., the inputs, variables, constraints, and objective function). 2.4. Data Analysis (OBJ 3) 37 •Data Mapping. This task is intended to map or align the attributes of the dataset, the data model, and the COP. •Data Querying. This enables querying on the input and output data obtained from the computation of the COPs. IN OUTOT Dataa Datan Datab DS DSoutput Mapping COPs Query Optimized Query DSoutput’ Transformation Data Preparation DM Data Querying COP Description … FIGURE 2.9: Overview of the approach to compute COPDDs. The data model is divided into three groups of attributes: (i) IN, which represent the attributes that will be linked to the inputs of the COP; (ii) OUT, which are the attributes that represent the output values after the execution of the COPs, and (ii) OT, which includes those attributes that provide additional information that are not related to the COP but can be useful for querying tasks. To illustrate the proposal, a real-world scenario is presented. This is part of the case study that we solved in the article in which we presented this proposal [90]. In this scenario, there are three Spanish electricity distribution companies that need to generate recommendations about the tariff configuration of their customers. For this purpose, they use COPs to obtain a hired power configuration that minimises the amount of the electricity bill, using the consumption data of each client as input. This scenario can be solved using COPDDs. An example is shown in Figure 2.10, representing one of the three datasets (DS), the data model (DM), and an excerpt of the COP model. Within the curated datasets, each record provides information about the contract and the consumption of the customer during different billing periods. Consumption is modelled as an array of structured data. Within each structure, the initial and final dates of the billing period are specified, along with the power consumed in three different periods of the day. Regarding the COP model, it requires as input the type of customer tariff (T) and a matrix Cin which each row represents the different billing periods, and the columns represent the power consumed in each hourly period. One of the variables in the COP model is PH. It is an array that represents the power configuration that the customer must hire for 38 Chapter 2. Summary of the Results each hourly period. The data model (DM) contains the input values (IN) required by the COP (Tis assigned to Tarif f and Cis assigned to Consumptions). It also includes the output values (OUT) produced by the COP (in this case, PH is assigned to PowerToHire and TI is mapped to TotalInvoince), as well as other attributes (OT) that will be useful for other purposes. The attributes of the dataset (DS) must be properly transformed according to the data model (DM). In this scenario, the use of Data Preparation techniques is ideal. For example, the nested structure consumption in the dataset (DS) must be mapped to Consumptions in the data model (DM). It implies a complex Data Transformation, since it requires to transform a complex data structure. This motivates the use of the Data Chameleon DSL to perform this transformation. customerID: string consumption: array element: struct startDate: string endDate: string power: struct period1: double period2: double period3: double location: string tariff: string Dataset (DS) Data Model (DM) IN Tariff: string Consumptions: matrix OUT PowerToHire: array TotalInvoince: double OT ID: string Location: string Constraint Optimisation problem (COP) Inputs T: string C: matrix Variables PH: array TI: double FIGURE 2.10: Example of data mapping between a dataset, a data model and a COP. As mentioned above, our proposal supports querying operators to make queries to DSoutput through the data model (DM). Depending on the type of query, the execution of the COPDDs can be optimised. First, we describe the operators that are supported: • Selection (σ). It enables selecting specific rows in DSoutput. This query can be performed before or after the COPDDs are computed. • Projection (∏). It allows the selection of specific attributes within DSoutput. If the attributes selected in the projection are within the OUT group, then the implied COPDDs must be executed previously. • Aggregation (Ω). This operation implies performing a calculation that involves a group of records. In our proposal, the following aggregator operators are supported: SUM (it sums the values of a specific attribute within each group of records), COUNT (it counts the number of records within each group), AVG (it calculates the average value of a specific attribute within each group of records), MAX and MIN (these are employed to obtain the maximum and minimum values of a specific attribute within each group of records). This operation can be applied to attributes IN,OUT and OT. If an attribute within OUT is involved in the aggregation, then the COPDDs must be executed. The closure property of the relational algebra allow to combine these operators. These also enable to optimise the execution of the COPDDs in twofold. First, depending on the query, not all COPs in the dataset must be computed. For example, if a selection operation is performed, only the COPs related to the selected rows are computed. Second, if aggregation operators are employed, in certain cases the COPs can be grouped in different workgroups. In 2.4. Data Analysis (OBJ 3) 39 our proposal, a workgroup is a group of COPs that can be computed together taking advantage of the information provided by the computation of COPs within the same workgroup. Therefore, our proposal provides two modes of execution. Figure 2.11a represents the execution mode in which each record generates a COP, each COP being computed independently and distributed among the nodes in the distributed environment. On the other hand, Figure 2.11b illustrates the execution mode when an aggregation operator is performed. In this scenario, the COPs are grouped into workgroups. Then, each workgroup is computed at a specific node of the distributed environment. The optimisation to apply depends on the aggregation operator. For example, with respect to the aforementioned real-world scenario, an aggregation query could be: Obtain, for each location, the customer who would pay the least amount when contracting the tariff configuration recommended by the COP. This query implies grouping the records by the Location attribute of the data model, and using the MIN aggregation operator on the TotalInvoice attribute of the data model. Since this attribute is of type OUT, its value depends on the COP result. An optimisation that can be applied here is to use the value for TotalInvoice obtained for each COP within the same workgroup to bound the domain of this variable to the rest of the COPs within the same workgroup. This leads to a reduction of the search space on each COP and, therefore, could improve the computation time. ds1 dsn Tuples … Data Sets COPi …… COPj COPm COPx … COPy COPz … WORKGROUP Constraint Values COP (A) Each COP is computed independently. ds1 Tuples Data Sets COPi … WORKGROUPS Constraints Values COPj COPz … dsn COPi … COPj COPz … … Ω Ω reductions reductions MapReduce (B) COPs are computed in workgroups. FIGURE 2.11: Two different COP computation modes. This proposal is supported by FABIOLA (FAst BIg cOnstraint LAboratory) 6, a tool with a user interface that implements the different stages of our proposal. This tool is described in our work [90]. Next, we summarise the components of it. •FABIOLA Metastore. It stores metadata comprising the definition of COPs, data models, data mappings, and the results of COPs. It is implemented on MongoDB [47] and Hadoop HDFS [39]. •FABIOLA Nodes. This is the cluster of nodes that is responsible for generating and computing the COPs on a distributed basis. This cluster is implemented in Apache Spark [7]. •FABIOLA UI. This is the user interface that implements the core functionalities of our proposal. The components of the interface enables to define and execute the COPDDs. 6FABIOLA for Spark: https://github.com/IDEA-Research-Group/fabiola-spark-jobs, FABIOLA user interface: https://github.com/IDEA-Research-Group/fabiola-gui-core 40 Chapter 2. Summary of the Results –Data importer. It enables importing the datasets, supporting several types of data sources. –Repository of data mappings. It enables the creation, review, and editing of data mappings between a specific dataset and a COP definition. –Repository of problem configuration. This component allows to model, review, and edit COPs. The current version of FABIOLA supports the modelling of COPs with the choco-solver library [68] by using the Scala programming language [80]. •FABIOLA Dashboard. It is a dashboard where the user can use several reporting and querying components. The case study we presented in [90] was successfully solved. We compared parallel execution to sequential execution, and we also tested the scalability of the proposal as the number of COPs to solve increased. We managed to significantly reduce the computation time with respect to the sequential computation of the COPs (about 65% on average). 2.4.2 Computing and distributing big complex optimisation problems applied to conformance checking In certain cases, the optimisation problem is so large that it cannot be easily distributed. In these cases, the context of the problem must be studied carefully to analyse whether it can be divided and distributed. In this thesis, we focus on the particular case: The conformance checking. The conformance checking discipline is a process mining technique that enables to discover deviation and abnormalities in business process models. Therefore, this technique is of paramount importance to assert the quality of a business process. Conformance checking enables to relate business process models and observed behaviours (i.e., event logs from that process model). The core of this technique is based on a highly complex optimisation problem: The alignment problem. In summary, this technique consists of computing an end-to-end model run that more closely resembles a specific trace within the event log. The alignment problem is, in essence, an optimisation problem in which a search space must be explored to find optimal values. Since the complexity of this problem is exponential [3], the computation time does not scale well in the cases where (i) the process model becomes more complex and (ii) the amount of event logs increases. In order to face highly complex business processes, decompositional techniques have been widely employed. These techniques allow us to divide the model into different parts. In this way, the number of alignment problems increases, but these tend to be less complex. In our proposal, we present a new decomposition technique: Horizontal decomposition, which seeks to reduce the complexity of complex process models with high cyclicity. Unlike the traditional vertical decomposition that breaks both traces and process models into different fragments in order to minimise the search space of each alignment problem, the horizontal decomposition generates end-to-end cuts of the process model. Cuts are generated by acyclic covers (i.e., end- to-end runs without cycles). In our proposal, these cuts, which are partial representations of the original process model, are called partial models, being less complex than the original 2.4. Data Analysis (OBJ 3) 41 process model due to the lack of cycles. Once a process model is decomposed, each partial model can be combined with the traces of the event log in order to build alignment problems. Since the partial models are less complex, the search space of the alignment problems is reduced, and hence the computation time is dramatically reduced. Once the alignment problems derived from the partial models have been solved, the solutions can be combined to find the alignment value. Basically, the solution is the alignment problem that gives the optimal alignment value. The second challenge is related to computing alignment problems with large amounts of event logs. To face this challenge, our proposal distributes the traces of the event logs along the nodes of a Big Data cluster. Since the alignment problem seeks to find the best alignment for each trace, each trace of the event log can be combined with the process model to generate an alignment problem. Our proposal goes one step further and allows each trace of the event log to be combined with each partial model. The following steps indicate how this works: 1. The event log is distributed, producing a total of ntraces. Let Tr =⟨tr0,tr1. . . trn−1⟩be the set of traces. 2. The process model is horizontally decomposed, producing a total of mpartial models. Let Pm =⟨pm0,pm1. . . pmm−1⟩be the set of partial models. 3. The set of traces and the set of partial models are combined through the Cartesian product. This produces a set AP = (Tr ×Pm).AP contains all existing combinations between the elements of Tr and Pm. We say that ap =⟨tri,pmj⟩,ap ∈AP is an alignment subproblem (i.e., each element of AP is called an alignment subproblem). 4. AP is distributed along the nodes of the cluster according to the distribution criteria selected by the user. Figure 2.12 depicts this distribution process. The column Input represents AP. Then, it is distributed into partitions of alignment problems (see the Partitions column). Each partition contains a number of alignment problems that are computed at a specific node of the cluster, being isolated from the rest of the partitions. 5. Next, a MapReduce [27] operation is initiated. The Map phase is now described (see column Map in Figure 2.12). Within each partition, the alignment subproblems are grouped by trace. Next, an estimation is calculated for the alignment subproblem. Although the estimation function can be specified by the user, we propose an algorithm that calculates a lower bound for the alignment value of each ap =⟨tri,pmj⟩, obtaining the lowest value that the alignment can take. Next, each group is sorted from lowest to highest estimate. The alignment subproblems are then computed. If the result of one of these computations produces a better alignment than the estimation for the same trace, then the computation of alignment subproblem is stopped for that group. At the end of this phase, there is an alignment value for each single trace within each partition. 6. Finally, during the Reduce phase, the partitions are combined. For each trace, the best alignment value found is returned. 42 Chapter 2. Summary of the Results Partitions Map Reduce <tr1,pm1> <tr1,pm2> <tr1,pm3> ... <tr2,pm1> <tr2,pm2> <tr2,pm3> <tr1,pm100> <tr1,pm101> <tr1,pm102> ... <tr2,pm100> <tr2,pm101> <tr2,pm102> <tr100,pm100> <tr100,pm101> <tr100,pm102> ... <tr200,pm100> <tr200,pm101> <tr200,pm102> <tr1,aligmentk> ... <tr2,alignmentm> <tr1,alignmentr> ... <tr2,alignments> <tr100,alignmentj> ... <tr200,alignmentn> <tr1,alignmentk> <t2,alignmentr> <tr100,alignmentx> <tr200,alignmentz> ... ... ... ... Input <tr1,pm1> <tr1,pm2> <tr1,pm3> ... <tr1,pm100> <tr1,pm101> <tr1,pm102> <tr2,pm1> <tr2,pm2> <tr2,pm3> ... <tr2,pm100> <tr2,pm101> <tr2,pm102> <tr3,pm1> <tr3,pm2> <tr3,pm3> ... <tr3,pm100> <tr3,pm101> <tr3,pm102> ... <tr100,pm100> <tr100,pm101> <tr100,pm102> ... <tr200,pm100> <tr200,pm101> <tr200,pm102> FIGURE 2.12: Schema of the distribution and computation of the alignment problems through the Map Reduce paradigm. Our proposal is agnostic to the algorithm employed to compute the alignments. In our benchmark, we use a well-known algorithm based on A* [18] implemented in the PM4Py [66] Python library. We also propose an innovative approach based on the constraint optimisation paradigm: Our work includes a Constraint Optimisation Problem model that enables one to solve conformance checking problems defined as a set of variables, constraints, and an objective function. We developed a tool, CC4Spark7[82], that enables one to generate and distribute conformance checking problems. It takes as input a process model or a decomposed process model and event logs. It applies the methodology explained above and returns the alignment values for each trace. This tool is based on PySpark (the Python version of Apache Spark [7]) and the PM4Py library. While Spark is employed to facilitate the distribution of event logs in Big Data clusters, PM4Py facilitates the serialisation of process models and event logs. It also provides a set of algorithms to compute alignment problems. The proposal was tested with five well-known datasets in the conformance checking community due to their complexity. The performance of CC4Spark with the A* algorithm and the proposal based on the constraint optimisation paradigm was compared with the traditional standalone approach with the A* algorithm. CC4Spark managed the best results in terms of computational time in four of the five datasets. 7CC4Spark: https://github.com/IDEA-Research-Group/conformancechecking4spark 2.5. Overall picture and Summary 43 2.5 Overall picture and Summary This Chapter presented the results of this thesis. These are focused on improving Data Preparation, Data Quality and Data Analysis in those Big Data pipelines that are intended to compute optimisation problems in cases where the input data is distributed and meets the characteristics of Big Data (i.e., volume, variety, and velocity), and/or the problems are too large and complex, requiring a special treatment. Moreover, the type of problems that we are facing require (i) processing complex data structures, and (ii) extracting event logs in a standard format from semi-structure data. The optimisation techniques that we use are also sensitive to bad-quality data, since this type of data leads to bad results. Therefore, the proposals in this thesis are intended to enrich the techniques that are available at different stages of Big Data pipelines. The tools developed are also designed to be used in Big Data pipelines through the Apache Spark [7] data processing engine. Next, we present two Big Data pipelines that have been employed to solve several case studies. The first is shown in Figure 2.13 and includes the use cases UC-DT-1,UC-DQ-1, and UC-OP-1. The ultimate objective of this pipeline is to support the Data Analysis in the use case UC-OP-1. The FABIOLA solution (Section 2.4.1) must be used to calculate large amounts of individual COPs. In this particular case, the data are acquired from one of the three electricity distribution companies. The data contains information about the consumption of each customer. Consumption is given within a nested data structure. Next, in the Data Preparation stage, we employ the Data Chameleon DSL [83] (Section 2.2.1) to transform the source data schema into the format required by the Data Model of the COP. Subsequently, the Data Quality of each record is assessed. This is done using DMN4Spark applying the DMN4DQ methodology [89] (Section 2.3.1). The purpose is to filter out the data records that are nonusable. In this case, we wanted to avoid data records with values null and outside the range. Then, the Data Filtering activity forks the data flow so that the data that have been qualified as usable go to the next stage of the pipeline (i.e., Data Analysis), while the non-usable data are stored in the data storage system. In this way, non-usable data can be diagnosed and repaired using DMN4DQ+ (Section 2.3.2). Finally, FABIOLA is employed as a Data Analysis tool. It receives the records from the dataset that have been qualified as usable and collects the Data Model and COP model from the data storage system. The second Big Data pipeline is presented in Figure 2.14, which includes the use cases UC-DT-2,UC-DQ-1, and UC-OP-2. This is orientated towards the process mining paradigm, since the Data Analysis stage intends to employ conformance checking techniques to compute the alignment between a process model and the event logs of such a process. Conformance checking involves the computation of optimisation problems with large search spaces. In this case, we use CC4Spark [85]. This proposal has been summarised in Section 2.4.2. The case study presented in Figure 2.14 was presented in [82], and is related to the milk manufacturing industry. The purpose of this pipeline is to discover potential errors and defects in this process. In the data acquisition activity, raw event logs from the process are collected. The Data Quality of each record is then evaluated with DMN4Spark, following the DMN4DQ methodology [89] (Section 2.3.1). In this case, incomplete and inaccurate data is penalised. As in 50 Chapter 3. Discussion and Publications Regarding the benchmark, the aim was to demonstrate the scalability of the proposal as the number of COPs to be solved increased. For this, an asymptotic analysis was performed. For each dataset, the computation time of each of them was sampled from 5,000,000 to 25,000,000 COPs. The performance of the FABIOLA solution (the COPs are distributed and resolved in parallel) was compared with a sequential execution. The asymptotic study revealed that the complexity of the sequential execution is linear (i.e., O(n)), while the execution using FABIOLA (in parallel) presented a sublinear complexity, three times lower than the sequential execution (i.e., O(n 3)). Clarify that the cluster in which FABIOLA was launched had 4 nodes. A second benchmark was performed to check the impact when aggregation operators are introduced (in this case, grouping operators). In summary, the application of these operators did not improve performance in terms of time due to the impact of grouping operations. However, if we compare the COP resolution stage, we observe an improvement in two of the three datasets (i.e., a 9.7% of improvement in one of them and a 41.6% in the other). We concluded that the impact of the optimisation of aggregation operators depends on the nature of the data. OBJ 3.2. Develop a solution to compute big complex optimisation problems in Big Data environments applied to conformance checking techniques This objective is achieved through the proposal that we published in the Information Systems journal [85]. The journal’s rank is Q3 (JCR’20 2.309). This work was made in collaboration with Professors Josep Carmona and Robin Bergenthum, both of whom are experts in the process mining and conformance checking fields. The proposal resulted in a tool (CC4Spark), which was presented in Business Process Management Demonstrations & Resources 2021 [82]. The proposal is intended to facilitate the computation of complex conformance checking problems in those scenarios where one or both conditions are met: (i) the business process model is too complex, and (ii) the dataset containing the event logs is too large. Usually in these cases traditional Conformance Checking solutions fail to find a solution in a reasonable time, as we demonstrated in our study. In order to validate our proposal, we employed five different datasets that are known by the conformance checking community because of their complexity. Thanks to our proposal, the complex Petri nets could be broken down into smaller units. On the other hand, the event logs could be distributed among the nodes of a Big Data cluster. First, we compare the sequential computation of the conformance checking algorithm based on A* with the parallel computation that we propose. We also tested the parallel computation of the solution based on COPs. Regarding parallel execution, several distribution configurations were tested to find the best balance between the number of partitions and the number of partial problems within each partition. We got a very significant improvement by parallelising the computation of conformance checking problems. In summary, the sequential A* algorithm showed better results in one of the five datasets. On the other hand, the parallel A* algorithm using our proposal achieved the best results in two of the five datasets. Finally, the algorithm based on parallel COPs that we propose showed better results in two of the five datasets. With respect to the results, the A* algorithm, both sequentially and in parallel, was able to produce optimal 3.1. Discussion of the Results 51 solutions for each dataset. However, the COP-based solution was not always able to return an optimal solution due to the setting of timeouts. However, the percentage of optimal solutions was higher than 80%. Our solution, CC4Spark, was also applied in the case study presented in [82]. This scenario consists of a milk manufacturing process that describes how milk cans are processed through the production chain. Event logs were produced by IoT sensors located within each machine, collecting data on temperature and pressure. This case study was successfully solved and managed to monitor the whole process and detect abnormalities in the final products. 52 Chapter 3. Discussion and Publications 3.2 Publications 3.2.1 CHAMALEON: Framework to improve Data Wrangling with Complex Data Published in the International Conference on Information Systems (ICIS 2019), Munich, Germany. December 2019. •Authors: Álvaro Valencia-Parra, Ángel Jesús Verala-Vaca, María Teresa Gómez-López, Paolo Ceravolo. •URL:https: // aisel. aisnet. org/ icis2019/ data_ science/ data_ science/ 16 . •Rating: GGS Class 2. Framework to improve Data Wrangling with Complex Data Fortieth International Conference on Information Systems, Munich 2019 1 CHAMALEON: Framework to improve Data Wrangling with Complex Data Completed Research Paper Álvaro Valencia-Parra Universidad de Sevilla Avda. Reina Mercedes S/N 41012 Sevilla - SPAIN [email protected] Ángel Jesús Varela-Vaca Universidad de Sevilla Avda. Reina Mercedes S/N 41012 Sevilla - SPAIN [email protected] María Teresa Gómez-López Universidad de Sevilla Avda. Reina Mercedes S/N 41012 Sevilla - SPAIN [email protected] Paolo Ceravolo Università degli Studi di Milano Via Giovanni Celoria, 18, 20133 Milano – ITALY [email protected] Abstract Data transformation and schema conciliation are relevant topics in Industry due to the incorporation of data-intensive business processes in organizations. As the amount of data sources increases, the complexity of such data increases as well, leading to complex and nested data schemata. Nowadays, novel approaches are being employed in academia and Industry to assist non-expert users in transforming, integrating, and improving the quality of datasets (i.e., data wrangling). However, there is a lack of support for transforming semi-structured complex data. This article makes a state-of- the-art by identifying and analyzing the most relevant solutions that can be found in academia and Industry to transform this type of data. In addition, we propose a Domain- Specific Language (DSL) to support the transformation of complex data as a first approach to enhance data wrangling processes. We also develop a framework to implement the DSL and evaluate it in a real-world case study. Keywords: Data Wrangling, Complex Data, Data Transformation, Semi-structured Data, Data Preparation Introduction The continuous technological advances in Industry are leading to data-driven business processes. These changes (Gerbert et al. 2015) are motivated by the concept of Industry 4.0, whose objective is to improve their production processes by means of Cyber-Physical Systems. These systems enable companies to capture real-time data on any aspect related to these productive processes. On the other hand, Industry 4.0 promotes companies to a broader integration with their external environment. Therefore, the necessity of integration of internal data with data from external sources (e.g., data from other organizations, open data, social network data) arises (Obitko and Jirkovský 2015). The ultimate objective is to process this data in order to discover knowledge, improve the decision making, and optimize production processes. Big Data technologies are an essential part in this industrial context (Gerbert et al. 2015) since data to be processed fulfill the three Big Data dimensions (a.k.a., the three V's) (Lee 2017): volume (they are massively generated), velocity (creation rates increase as Cyber-Physical Systems and IoT are included in production 3.2. Publications 53 Framework to improve Data Wrangling with Complex Data Fortieth International Conference on Information Systems, Munich 2019 2 processes), and variety (data become more heterogeneous as the amount of data sources increase). This new context has promoted the creation of new solutions adapted to the complexity of data. Data complexity and heterogeneity are a prominent challenge. When the amount of data and the creation rate increase drastically, data heterogeneity tends to rise as well, resulting in non-structured data models with nested and complex schemata (hereinafter, complex data). Derived from the data complexity, data integration becomes also in a prominent challenge of Big Data management (Ceravolo et al. 2018; Jin et al. 2017; Stefanowski et al. 2017), since it involves combining diversified sources in a unified view supporting data analytic or reporting procedures (Dong and Srivastava 2015). Data integration requires, therefore, several transformations to be made, changing data values and structure but keeping at the same time the validity and consistency of data or event enhancing their value. For this reason, data transformation, as a part of the data preparation process, is considered the most time-consuming stage of data analytics (Guo et al. 2011). In traditional data warehousing, this process has been extensively analyzed, proposing integration tools for data transformation by using the Extract-Transform-Load (ETL) approaches. Regarding the complex data, various query languages can be found in industry (Beyer et al. 2011; Florescu and Fourny 2013) to facilitate the transformation, integration and querying of data sources with complex data in ETL processes. However, with the emergence of the Big Data paradigm, actors focusing on the commoditization of Big Data technologies are addressing the fast roll-out of Big Data pipelines proposing visual data flow orchestrators (Milutinovic et al. 2017) and catalogs of congruent services (Ardagna et al. 2018). The aim is the introduction of the as-a-service approach in Big Data technologies, supporting the composition of services in an easy way and offering, at the same time, a guarantee about the consistency of the proposed compositions (Ardagna et al. 2018). In this sense, data wrangling has become one of the most employed techniques to facilitate the transformation and mapping of data from a raw format into the format required by data analysis processes in Big Data context. The current trend is to provide self-service data preparation (Hellerstein et al. 2018). It points at easing the data preparation process for non-expert users through data profiling and the automation of the tasks. Therefore, this assistance comes along with user-friendly Domain-Specific Languages, user interfaces, and features for data cleaning and data quality improvement. Nowadays, several data wrangling solutions can be found in Industry. Although some of them are able to work with complex data, they are entirely focused on a table-oriented data model, flattening data into static structures avoiding nested data. It implies that operations must be directly applied over top-level attributes (i.e., columns). This operative inevitably difficulties the transformation of complex structures, requiring nested attributes to be shift to top-level positions. Consequently, (i) the number of operations needed to transform the format and/or schema of a dataset becomes significantly high depending on the depth of the nested attributes and the target schema, and (ii) the definition of the transformation operations becomes non-easy-to-use and anti-intuitive, being far away from the shape of the target schema, and hence, being more error-prone and hindering debugging operations. In this context, the identification of languages for data transformation that support complex operations by a concise syntax is of paramount importance for a flexible handling of data sources (Arputhamary and Arockiam 2015). Moreover, linking these operations to their effects on performances, in relation to the data structure, is crucial to increase the awareness of designers about the effects of their specifications. Trying to reduce the existing gap in complex data transformation in data wrangling, this paper pursues to cover two main aspects: (i) discuss the approaches in the industry, and the academia to support the transformation of complex data in the data wrangling and self-service data preparation fields, and; (ii) the proposition of a framework, that includes a Domain-Specific Language (DSL), to support the transformation of data with complex schema. This language aims to provide a functional way to enable users to define the target schema along with the transformations needed to reach it from the source schema, minimizing the number of operations and the complexity of the language. The rest of the paper is structured as follows. First, two real-world case studies are presented to understand the proposal better. Then, our proposal is described, depicting the solution, including a DSL that facilitates the complex data transformation in data wrangling context. The proposed implementation is introduced, before the most relevant references related to data wrangling and complex data are discussed. Next, the related work is discussed, and then we compare our proposal with other data wrangling tools. Finally, some conclusions are drawn. 54 Chapter 3. Discussion and Publications Framework to improve Data Wrangling with Complex Data Fortieth International Conference on Information Systems, Munich 2019 3 Case Studies This section describes two case studies which demonstrate the applicability of our proposal in two different industries that require the transformation of datasets: (A) the transformation of datasets from several electricity wholesales to extract information about the consumption of electricity, and (B) the transformation of datasets taken from several IoT sensors to detect potential deficiencies in aircraft assembly processes. Case Study A: Formatting datasets from several electricity wholesales In order to introduce the necessity to facilitate the complex data transformation, we use a real case study based on the integration datasets provided by seven electricity companies that sell energy for private customers in Spain. The electricity wholesales describe consumption data in different formats and using different frequency of meter reading, depending on factors such as the distributor or the tariff hired for each customer. These various formats need to be uniform in order to be processed and analyzed later, such as to create patterns of behavior or to look for the best tariff for each customer (Parody et al. 2017). However, each electricity provider offers information using different nested schemata, depending on some factors, such as the number of months included in the meter reading, number of days, types and tariff. Therefore, all these heterogeneous schemata need to be transformed into a unified one being possible to integrate every dataset in a unified view. The quantity of information, the heterogeneity and the updating of the information, Big Data infrastructure must be used to facilitate the data analysis. Figure 1 illustrates the scenario where several data sources must be conciliated into a unified format accessible to the final user by means of a set of transformation, each one applicable to a single data source. As mentioned above, the provided information does not follow the same schema, but they generally share a customer ID, a tariff identifier, the contracted power for each daily billing period, and a list of consumption over a period (e.g., twelve months or more). Each consumption period keeps information on the start and end date for that period, and the power consumption for each daily billing period. Figure 2 shows a possible input schema for the data of the example and its relationships with the target schema. Figure 1. Case Study scenario Figure 2. Transformations to convert the source schema (left) into the target schema (right) 3.2. Publications 55 Framework to improve Data Wrangling with Complex Data Fortieth International Conference on Information Systems, Munich 2019 4 Source Schema Description The source schema is composed of basic and nested attributes. The description of the dataset attributes is given as follows: • customerID. It is a string which identifies a unique customer supply point. • consumption. It is the power consumption over a period, such as twelve months or more. It is an array of data structures. Each element represents a period, and it includes the following information: o power. It is the power consumption for each daily billing period. It is represented by a data structure with six decimal numeric attributes, each one representing the consumed power for a daily billing period. o startDate. It is the start date for the billing period represented by this element. o endDate. It is the end date for the billing period represented by this element. Transformations and Target Schema In order to reach the target schema, several transformations must be applied for each electricity supplier. For the example, six transformations are needed as depicted in Figure 2: • T1. customerID must be renamed to ID. No further transformations are required. • T2. consumption is transformed into a matrix C, whose rows have three elements that are calculated from the pi attributes in power in accordance with the defined rules by the government. • T3. In the target schema, AVG_C is a data structure with three elements: p1, p2, and p3. It represents the average consumed power for each daily billing period. The calculation is carried out by means of the matrix calculated in T2. • T4. In the target schema, DATES is an array whose attributes are of type date. It is calculated by means of the startDate attribute in the source schema. Case Study B: Detecting deficient aircraft This case study is based on the aeronautic industry. It is a real case study from the aircraft factory of Airbus placed in Seville. The datasets represent the logs of an aircraft production plant. It is about the tests that are performed in the workstations where the aircraft are tested, and the incidents that occurred during these. Each workstation produces a dataset with a different schema and data format but they all have a set of attributes related to the aircraft, the workstation and the incidents occurred during the tests, as detailed in in (Valencia-Parra et al. 2019). It is required to wrangle this data in order to obtain a formatted dataset so that it helps experts to discover potential deficient aircraft. Source Schema Description The source schema is composed of the following attributes: • accode. It is a string attribute representing the code of an aircraft. • workstation. It is a string identifying the workstation where the tests have been executed. • incidents. It is an array whose elements represent information about the incidents that have occurred during the test execution. It contains nested structures with the following attributes: o start_date. It is a string representing the date when the incidence started. o resolution_date. It is a string representing the date when the incidence was resolved. Transformations and Target Schema The following transformations are required in order to reach the target schema: • T1 and T2. Attributes accode and workstation are renamed as aircraft and ws, respectively. 56 Chapter 3. Discussion and Publications Framework to improve Data Wrangling with Complex Data Fortieth International Conference on Information Systems, Munich 2019 5 • T3. avg_incidents is a numeric attribute created by calculating the average value of the array which results from iterating incidents and performing the following operation: resolution_date - start_date. It represents the average time that the incidents took to be solved. The objective of these transformations is to produce a dataset that can be processed by an algorithm that detects abnormalities during the test of the aircrafts in the workstations, and thus, to detect potential deficient aircraft. Our Proposal This section depicts CHAMELEON: the proposal we have devised to improve the data wrangling processes when dealing with complex data. It consists of framework and a Domain-Specific Language (DSL), whose objective is to link the operations with their effects in the target schema. First, the necessary concepts to understand the proposal are presented. Then, Framework is introduced, following with the proposed DSL. Finally, the case studies are solved by using the proposal. Related Concepts Next, the concepts Data Schema, data type, and Transformation Function are defined. These concepts will facilitate the understanding of the DSL that is defined in this section. Definition. A Data Schema is a set of attributes, {a1: t1, a2: t2, …, an: tn}, identified by a name (ai) and a data type (ti). Regarding the data type (ti), two categories of data types have been identified: • Simple type. It is a data type which represents a single value: o Numeric. It represents a numeric data type, i.e., Integer, Long, Float, and Double. o String. It is a sequence of characters. o Boolean. It is a two-valued data type which represents the truth values. o Date. It is a set of characters with a specific format that represents an instant of time. • Complex type. It is a composite data type that can be: o Array. It is a collection of typed attributes identified with a unique numeric index. o Struct. It is a data type composed of a set of attributes, each one identified by a unique name. Definition. A Transformation Function, fx, is a function that receives an attribute, ainput, and returns an attribute, aoutput, resulting from applying an operation which modifies the value of ainput. 𝑓 𝑥: 𝑎𝑖𝑛𝑝𝑢𝑡 → 𝑎𝑜𝑢𝑡𝑝𝑢𝑡 Framework Modeling We have developed a framework 1 to implement the DSL so that we can solve the case studies in a real-world environment. The framework has been designed according to the composite design pattern (Riehle et al. 1997). In short, this pattern enables to build complex objects by using simpler ones. It means that an object could be composed of nested objects. Figure 3 depicts a schema of this pattern. As can be seen, the classes Composite1 and Composite2 are composed of a set of Components, which can be Composite1, Composite2, or Leaf. The latter is called Leaf because it is not compounded by any other Component. In this pattern, the instances of objects could be represented as a tree structure. Figure 4 depicts the UML diagram of the transformation framework. As mentioned above, the instances of this model can be represented as a tree structure. In this structure, the leaves are operations that access the attributes, and internal nodes are intended to transform or create new structures. To better understand it, 1 The implementation can be found in: http://www.idea.us.es/datatransformation/ 3.2. Publications 57 Framework to improve Data Wrangling with Complex Data Fortieth International Conference on Information Systems, Munich 2019 6 Figure 5 shows an instance of the transformation T1 exposed in the case study A, and Figure 6 shows its tree representation. Figure 3. Composite design pattern In this model, the Component is the Evaluable interface. An Evaluable represents an expression whose main objective is to perform transformation functions on attributes. Two methods can be applied over every Evaluable expression (hereinafter, expression): getValue and getDataType. • getValue. It receives an attribute and returns another attribute as a result of applying a transformation to it. • getDataType. It receives a data type and returns the data type as a result of applying a transformation to it. These are intended to be the entry-point of the framework. The way these functions work depends on the Leaf or the Composite components. Next, the leaves of the transformation framework model are listed. • Select. It is meant to select the attribute whose name matches the string name from an attribute of type struct. • Index. It is meant to select the attribute whose position matches the integer index from an attribute of type array. Figure 4. Framework modeling 58 Chapter 3. Discussion and Publications Framework to improve Data Wrangling with Complex Data Fortieth International Conference on Information Systems, Munich 2019 7 Figure 5. Instance of the model to perform the transformation T1. Code representation Figure 6. Instance of the model to perform the transformation T1. Tree representation. Lastly, the Composites of the transformation framework model are listed. • Rename. It is meant to transform an Evaluable expression (hereinafter, expression) which returns an attribute of any type by replacing its name by the string name. • CreateStruct. It is meant to create an attribute of type struct from a set of expressions attrs. • CreateArray. It is meant to create an attribute of type array from a set of expressions attrs. • Iterate. It is meant to create an attribute of type array resulting from iterating over an expression which returns an attribute of type array (expr1). An expression (expr2) is applied to each element in that array. • Operator. It is meant to transform an expression by applying a Data Transformation Function (hereinafter, DTF). • DTF. It is meant to apply a transformation function to an expression. These enable users to perform advanced transformations on attributes of any data type. DSL Definition The DSL has been defined with two main goals: (i) provide versatility so that a wide range of transformations can be carried out, and (ii) reduce the gap between the definition of the transformations and their effects in the target schemas. The syntax of the grammar is given bellow by means of Extended Backus-Naur form notation (Reilly et al. 2003). Syntax is the entry-point to the language. It is given by an Expression, which might be one of the following: Select, Index, Rename, CreateStruct, CreateArray, Iterate, or Transform. Syntax ::= Expression Expression ::= Select|Index|Rename|CreateStruct|CreateArray|Iterate|Transform Select is intended to be the syntax for selecting either an attribute in a struct or a position in an array. For instance, regarding the case study A, t"customerID" selects the attribute customerID, and t"consumption.[0]", selects the position 0 of the consumption array. Select ::= 't' '"' ( StringLiteral | '[' Digit+ ']' ) ( '.' ( StringLiteral | '[' Digit+ ']' ) )* '"' Rename is meant to modify the name of an attribute. For example, "ID" << t"customerID" changes the name of the attribute customerID to ID. Rename ::= StringLiteral '<<' Expression 3.2. Publications 59 Framework to improve Data Wrangling with Complex Data Fortieth International Conference on Information Systems, Munich 2019 14 Figure 9. Representation of the intermediate steps needed for the transformation T2 in case study A Case Study A Table 2 shows the operations performed to complete the case study A with Trifacta. This case study requires 34 operations, where 26 of them are intermediate operations and 8 of them are not. Approximately the 77% of the operations written by the user are intermediate. Transformations T2 and T3 have a similar proportion of intermediate operations, while in T4 this percentage increases to the 85%. Our proposal abstracts users from these intermediate operations, so we can state that, except for T1 (that does not require to transform nested attributes), it improves the way the transformations are carried out. Table 2. Operations to complete Case Study A with Trifacta Unnesting Nesting Flattening Grouping Dropping Renaming Nonintermediate Total T1 0 0 0 0 0 0 1 1 T2 1 4 1 1 2 1 3 13 T3 1 4 1 1 2 1 3 13 T4 1 1 1 1 1 1 1 7 TOTAL 3 9 3 3 5 3 8 34 Table 2. Operations to complete Case Study A with Trifacta Case Study B Table 3 shows the operations performed to complete case study B with Trifacta. The most complex transformation here is T3, which is the only one that requires access to nested attributes. It requires a total of 5 operations, being 4 of them intermediate operations. Hence, the 80% of the operations for T3 are intermediate operations. Ultimately, the 57% of the operations of the case study are intermediate. Our proposal also improves the transformation process for this case study. 66 Chapter 3. Discussion and Publications Framework to improve Data Wrangling with Complex Data Fortieth International Conference on Information Systems, Munich 2019 15 Table 3. Operations to complete Case Study B with Trifacta Unnesting Nesting Flattening Grouping Dropping Renaming Nonintermediate Total T1 0 0 0 0 0 0 1 1 T2 0 0 0 0 0 0 1 1 T3 1 0 1 1 0 1 1 5 TOTAL 1 0 1 1 0 1 3 7 Table 3. Operations to complete Case Study B with Trifacta Conclusions One of the most important challenges that last advances in Industry poses is the transformation of complex data and the conciliation of complex data schemata. There is an emerging field in Big Data which intends to ease these tasks for non-expert users: data wrangling and self-service data preparation. This study has highlighted the lack of support for complex data in these fields. Our proposal is intended to contribute to the improvement of data wrangling techniques by means of a framework that includes a Domain-Specific Language. The goal of it is to link the operations carried out by users to their effects in the target schema. It represents an improvement in relation to the data wrangling solutions that can be found in Industry since they are not focused on dealing with complex data. Several well-known query languages for semi-structured data have been studied to enhance our proposal. Future Work The limitations of our proposal define the actions that we want to face up for the future. First, our proposal lacks support for data profiling, data quality assessment, and automatic assistance to users. These shortcomings are hence a great opportunity for the future, since as proven in this study, data wrangling and self-service data preparation are of paramount relevance in both academia and Industry. In particular, we identify prior opportunities (Furche et al. 2016) in the automation of error-detection and feedback giving in the definition of transformation rules by users. It would be a pioneering proposal in the field of semi-structured complex data. Acknowledgments This work has been partially funded by the Ministry of Science and Technology of Spain by ECLIPSE project (RTI2018-094283-B-C33) and the European Regional Development Fund (ERDF/FEDER) via METAMORFOSIS project. References Ardagna, C. A., Bellandi, V., Bezzi, M., Ceravolo, P., Damiani, E., and Hebert, C. 2018. “Model-Based Big Data Analytics-as-a-Service: Take Big Data to the Next Level,” IEEE Transactions on Services Computing, pp. 1–1. (https://doi.org/10.1109/TSC.2018.2816941). Ardagna, C. A., Bellandi, V., Ceravolo, P., Damiani, E., Di Martino, B., D’Angelo, S., and Esposito, A. 2018. “A Fast and Incremental Development Life Cycle for Data Analytics as a Service,” in 2018 IEEE International Congress on Big Data (BigData Congress), IEEE, July, pp. 174–181. (https://doi.org/10.1109/BigDataCongress.2018.00030). Arputhamary, B., and Arockiam, L. 2015. “Data Integration in Big Data Environment,” Bonfring International Journal of Data Mining (5:1), Bonfring, pp. 01–05. (https://doi.org/10.9756/BIJDM.8001). Beyer, K. S., Ercegovac, V., Gemulla, R., Balmin, A., Eltabakh, M. Y., Kanne, C.-C., Özcan, F., and Shekita, 3.2. Publications 67 Framework to improve Data Wrangling with Complex Data Fortieth International Conference on Information Systems, Munich 2019 16 E. J. 2011. “Jaql: A Scripting Language for Large Scale Semistructured Data Analysis,” in Proceedings of VLDB Conference. (https://www.semanticscholar.org/paper/Jaql%3A-A-Scripting-Language-for- Large-Scale-Data-Beyer-Ercegovac/28d0280e2b972155c203b96bd6eb9f826aa73850). Botoeva, E., Calvanese, D., Cogrel, B., and Xiao, G. 2018. “Expressivity and Complexity of MongoDB Queries,” DROPS-IDN/8607, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. (https://doi.org/10.4230/LIPICS.ICDT.2018.9). Ceravolo, P., Azzini, A., Angelini, M., Catarci, T., Cudré-Mauroux, P., Damiani, E., Mazak, A., Van Keulen, M., Jarrar, M., Santucci, G., Sattler, K. U., Scannapieco, M., Wimmer, M., Wrembel, R., and Zaraket, F. 2018. “Big Data Semantics,” Journal on Data Semantics (7:2), Springer Berlin Heidelberg, pp. 65– 85. (https://doi.org/10.1007/s13740-018-0086-2). Dong, X. L., and Srivastava, D. 2015. “Big Data Integration,” Synthesis Lectures on Data Management (7:1), Morgan & Claypool Publishers, pp. 1–198. (https://doi.org/10.2200/S00578ED1V01Y201404DTM040). Florescu, D., and Fourny, G. 2013. “JSONiq: The History of a Query Language,” IEEE Internet Computing (17:5), pp. 86–90. (https://doi.org/10.1109/MIC.2013.97). Furche, T., Gottlob, G., Libkin, L., Orsi, G., and Paton, N. W. 2016. “Data Wrangling for Big Data: Challenges and Opportunities,” in 19th International Conference on Extending Database Technology (EDBT), pp. 473–478. (https://doi.org/10.5441/002/EDBT.2016.44). Gerbert, P., Lorenz, M., Rüßmann, M., Waldner, M., Justus, J., Engel, P., and Harnisch, M. 2015. “Industry 4.0: The Future of Productivity and Growth in Manufacturing Industries,” Boston Consulting Group. (https://www.bcg.com/publications/2015/engineered_products_project_business_industry_4_fut ure_productivity_growth_manufacturing_industries.aspx, accessed December 19, 2018). Guo, P. J., Kandel, S., Hellerstein, J. M., and Heer, J. 2011. “Proactive Wrangling: Mixed-Initiative End- User Programming of Data Transformation Scripts,” in Proceedings of the 24th Annual ACM Symposium on User Interface Software and Technology - UIST ’11, New York, New York, USA: ACM Press, p. 65. (https://doi.org/10.1145/2047196.2047205). Hellerstein, J. M., Heer, J., and Kandel, S. 2018. “Self-Service Data Preparation: Research to Practice,” Undefined. (https://www.semanticscholar.org/paper/Self-Service-Data-Preparation%3A-Research- to-Practice-Hellerstein-Heer/715cba311d4e5ad6b5f8cba7694ccc03ef7583b7). Jin, Z., Anderson, M. R., Cafarella, M., and Jagadish, H. V. 2017. “Foofah: Transforming Data By Example,” in Proceedings of the 2017 ACM International Conference on Management of Data - SIGMOD ’17, New York, New York, USA: ACM Press, pp. 683–698. (https://doi.org/10.1145/3035918.3064034). Kandel, S., Paepcke, A., Hellerstein, J., and Heer, J. 2011. “Wrangler: Interactive Visual Specification of Data Transformation Scripts,” in Proceedings of the 2011 Annual Conference on Human Factors in Computing Systems - CHI ’11, New York, New York, USA: ACM Press, p. 3363. (https://doi.org/10.1145/1978942.1979444). Kusumasari, T. F., and Fitria. 2016. “Data Profiling for Data Quality Improvement with OpenRefine,” in 2016 International Conference on Information Technology Systems and Innovation (ICITSI), IEEE, October, pp. 1–6. (https://doi.org/10.1109/ICITSI.2016.7858197). Lee, I. 2017. “Big Data: Dimensions, Evolution, Impacts, and Challenges,” Business Horizons (60:3), Elsevier, pp. 293–303. (https://doi.org/10.1016/J.BUSHOR.2017.01.004). Milutinovic, V., Kotlar, M., Stojanovic, M., Dundic, I., Trifunovic, N., and Babovic, Z. 2017. DataFlow Systems: From Their Origins to Future Applications in Data Analytics, Deep Learning, and the Internet of Things, Springer, Cham, pp. 127–148. (https://doi.org/10.1007/978-3-319-66125-4_5). Obitko, M., and Jirkovský, V. 2015. Big Data Semantics in Industry 4.0, Springer, Cham, pp. 217–229. (https://doi.org/10.1007/978-3-319-22867-9_19). Ong, K. W., Papakonstantinou, Y., and Vernoux, R. 2014. “The SQL++ Semi-Structured Data Model and Query Language: A Capabilities Survey of Sql-on-Hadoop, Nosql and Newsql Databases,” CoRR, Abs/1405.3631. 68 Chapter 3. Discussion and Publications Framework to improve Data Wrangling with Complex Data Fortieth International Conference on Information Systems, Munich 2019 17 Ostrovsky, D., Haji, M., and Rodenski, Y. 2015. “The N1QL Query Language,” in Pro Couchbase Server, Berkeley, CA: Apress, pp. 107–133. (https://doi.org/10.1007/978-1-4842-1185-4_6). Parody, L., Vaca, Á. V., Gómez-López, M., and Gasca, R. 2017. “FABIOLA: Defining the Components for Constraint Optimization Problems in Big Data Environment,” in International Conference on Information Systems Development (ISD) 2017, , September 26. (https://aisel.aisnet.org/isd2014/proceedings2017/CogScience/3). Reilly, E. D., Ralston, A., and Hemmendinger, D. 2003. “Backus-Naur Form (BNF),” in Encyclopedia of Computer Science, Wiley, pp. 129–131. (https://dl.acm.org/citation.cfm?id=1074155). Riehle, D., Dirk, Riehle, and Dirk. 1997. “Composite Design Patterns,” ACM SIGPLAN Notices (32:10), ACM, pp. 218–228. (https://doi.org/10.1145/263700.263739). Stefanowski, J., Krawiec, K., and Wrembel, R. 2017. “Exploring Complex and Big Data,” International Journal of Applied Mathematics and Computer Science (27:4), Walter de Gruyter & Co., pp. 669– 679. (https://doi.org/10.1515/amcs-2017-0046). Valencia-Parra, Á., Ramos-Gutiérrez, B., Varela-Vaca, Á. J., Gómez-López, M. T., and Gracía Bernal, A. 2019. “Enabling Process Mining in Aircraft Manufactures: Extracting Event Logs and Discovering Processes from Complex Data,” in Proceedings of the Industry Forum at BPM 2019, Vienna, pp. 166– 177. 3.2. Publications 69 70 Chapter 3. Discussion and Publications 3.2.2 DMN4DQ: When data quality meets DMN Published in the Decision Support Systems journal (Vol. 141, p.113450). Elsevier BV. •Authors: Álvaro Valencia-Parra, Luisa Parody, Ángel Jesús Verala-Vaca, Ismael Caballero, María Teresa Gómez-López. •DOI: 10.1016/j.dss.2020.113450. •Rating: Q1 (JCR’20 5.795). Decision Support Systems 141 (2021) 113450 Available online 18 November 2020 0167-9236/© 2020 Elsevier B.V. All rights reserved. DMN4DQ: When data quality meets DMN ´ Alvaro Valencia-Parra a , * , Luisa Parody b , ´ Angel Jesús Varela-Vaca a , Ismael Caballero c , María Teresa G´ omez-L´ opez a a Dpto. Lenguajes y Sistemas Inform´ aticos, Universidad de Sevilla, Sevilla, Spain b Dpto. M´ etodos Cuantitativos, Universidad Loyola Andalucía, Sevilla, Spain c Information Systems and Technologies Institute, University of Castilla-La Mancha, Ciudad Real, Spain ARTICLE INFO Keywords: Data usability Data quality Decision model and notation Data quality rule Data quality assessment Data quality measurement ABSTRACT To succeed in their business processes, organizations need data that not only attains suitable levels of quality for the task at hand, but that can also be considered as usable for the business. However, many researchers ground the potential usability of the data on its quality. Organizations would benefit from receiving recommendations on the usability of the data before its use. We propose that the recommendation on the usability of the data be supported by a decision process, which includes a context-dependent data-quality assessment based on business rules. Ideally, this recommendation would be generated automatically. Decision Model and Notation (DMN) enables the assessment of data quality based on the evaluation of business rules, and also, provides stakeholders (e.g., data stewards) with sound support for the automation of the whole process of generation of a recommendation regarding usability based on data quality. The main contribution of the proposal involves designing and enabling both DMN-driven mechanisms and a guiding methodology (DMN4DQ) to support the automatic generation of a decision-based recommendation on the potential usability of a data record in terms of its level of data quality. Furthermore, the validation of the proposal is performed through the application of a real dataset. 1. Introduction The witnessed changes that Digital Transformation (e.g., Industry 4.0) is introducing in different business processes across various domains have positioned data at the core of operations and strategies [33]. To a certain extent, it can be stated that the role previously played by steam engines in Industry 1.0 is now played by the new and powerful AI- based machines [12]. However, and as happened in those times, the success of these new AI-machines, and therefore, of business processes, largely relies on the quality of the raw material employed, in this case, data. Consequently, the management of the quality of data has become essential in this digital era [20,25]. Given the need for data with adequate levels of quality in such domains, we propose that if organizations could automatically incorporate ways to decide on whether to use or discard records, then business processes would greatly benefit from preventing results that would otherwise produce low levels of data quality. This decision regarding the potential usability of the data could be made after the generation of a recommendation based on the assessment of the quality of the data records. Since it is generally accepted that the assessment of data quality is context-dependent [3,15], and since we propose that the usability of the data largely depends on the quality of the data, it can therefore be stated that the usability of data is also largely dependent on the context of the use of the data [14,37,44]. This implies modelling the context in which the data is to be used and when a data record is potentially usable. In order to convert this idea into action, we conducted an investigation to tackle two challenges: (i) how to describe whether a data record is usable for its intended use in a given context; and (ii) how to automate the process of producing a recommendation on the usability of the data for this context. To deal with the first challenge, we studied how others had already faced the problem of modelling the context, the data, and the rules that describe when a data record is of sufficient quality by identifying and describing various types of business rules for data quality and how the recommendation of the usability of the data could be determined. In * Corresponding author. E-mail addresses: [email protected] (´ A. Valencia-Parra), [email protected] (L. Parody), [email protected] (´ A.J. Varela-Vaca), [email protected] (I. Caballero), [email protected] (M.T. G´ omez-L´ opez). Contents lists available at ScienceDirect Decision Support Systems journal homepage: www.elsevier.com/locate/dss https://doi.org/10.1016/j.dss.2020.113450 Received 10 June 2020; Received in revised form 15 November 2020; Accepted 15 November 2020 3.2. Publications 71 Decision Support Systems 141 (2021) 113450 2 order to ensure rigour and repeatability on the process, we decided to incorporate all the elements identified and the necessary steps into a methodology. The second challenge to address is the necessity to support the generation of the recommendation on the usability of the data, based on its levels of quality in an automatic and technological-agnostic way [35]. This is even more challenging in scenarios where high efficiency is required in terms of computational cost, such as in Internet of Things (IoT) or in the context of CyberPhysical Systems (CPS). As part of this second challenge, and to set our proposal in motion, we suggest the use of a solution that facilitates the description and validation of the business rules employed in the assessment of the level of usability based on data quality, thereby promoting the application of repeatable decisions that can be semantically interoperable with the various technologies through which data quality assessment could be applied. We found that in order to tackle these challenges, it was recommendable to use a decision language that facilitates the description of the business rules so that they could be verified automatically. In this respect, OMG’s Decision Model and Notation (DMN) [30] and the FEEL expression language for modelling conditions could prove themselves to be perfect allies in achieving these two challenges. For this reason, DMN is the main pillar of the structure of proposal. Therefore, the main contribution of the proposal involves designing and enabling DMN-driven mechanisms to support the automatic generation of a business-based recommendation on the potential usability of a data record in terms of its level of data quality. To this end, our proposal includes the following actions: 1. Development of the foundations of the proposal through a set of integrated and hierarchical business rules that address the concepts of data quality measurement and data quality assessment for the generation of a data-usability recommendation (Section 3.1). 2. Identification and tailoring of the necessary elements provided by the standard DMN to support our proposal (Section 3.2). 3. Definition of a methodology, called DMN4DQ, to enable data-related users (e.g., stakeholders and data stewards) to drive the process of instantiating the corresponding elements when it comes to producing recommendations for a given dataset in a given context. This includes the definition and implementation of a software architecture supported by commercial implementations of reference (e.g., Camunda DMN) to automate the process of generating the recommendation (Section 4). 4. Validation of the proposal in a case study with real data (Section 5). The remainder of the paper is organised as follows: Section 6 shows related work; Section 7 analyses threats to the validity of the approach; and finally, Section 8 presents concluding remarks and lessons learned. 2. Foundations In order to combine DMN and data quality, and before detailing our proposal, it is necessary to revisit certain concepts regarding data quality management and DMN to enable a better understanding of how DMN can be used to describe whether a data record is usable in terms of its level of quality in a given context. 2.1. Data quality management: measurement and assessment Throughout the literature, the two most widely used definitions of “data quality” are based on the notions of “meeting requirements” (i.e., a measure of the numbers of defects) given by Crosby, and “fitness for use” coined by Juran [38]. From our understanding, these two definitions involve a major difference: while the first definition enables somebody to measure “how well data is built” (for instance, by counting the number of times that the data fails to meet stated requirements), the second lets somebody assess “how usable the data is” in a given context by comparing the number of defects found (the “measures”) with a threshold value representing the appetite for risk of the organisation regarding the reliability of the data in an specific context [8]. Even though the terms “measurement” and “assessment” can sometimes be considered as synonyms, we highlight this difference because it is important for our proposal: the “assessment” requires the “measurement”, in the same way that the “generation of a recommendation on the usability” requires the “assessment”. Our proposal goes a step beyond, since before determining whether a record is potentially usable, it is necessary to make the most important decision: While taking into account the impact that using data with inadequate levels of quality can have on the success of the business processes, should the assessed data record be used or discarded in the context of the task at hand?. If the use of the data is potentially risky for the business, then data stewards may decide: to enhance the data (e.g., data cleansing); to use the unaltered data, thereby assuming a risk; or alternatively, to discard the data record. The main aim of our proposal is therefore to provide business-based recommendations to data stewards to facilitate decision-making on whether to use or discard the data as part of their business activities. Therefore, there is a patent need to manage data quality. The concept of data quality dimension (also called data quality characteristic) lies at the core of data quality management. A data quality dimension can be understood as a criterion employed to evaluate the quality of data [28,37,44]. These dimensions or characteristics represent the data quality requirements stated or expected by the various stakeholders involved in the execution of the business processes [45]. A set of data quality dimensions is called a data quality model. Several researchers and practitioners in a variety of contexts have proposed their own data quality models [32,36]. Due to its importance at different stages of the data quality management discipline, we would like to highlight two generic models from among all the existing models: (1) the model proposed by Wang et al. [43] (see Table 1); and (2) the model proposed in ISO 25012 [21] (see Table 2). The first model has been the most widely used in recent years since it is the most authoritative reference in the field. Moreover, it guides the identification of the specific data quality requirements that are important for a given context. In order to validate the compliance of these requirements, business rules are typically employed in data quality contexts [7,10,34]. The second model, ISO 25012, should not necessarily be understood as an alternative to the proposal of Wang et al. In fact, in conjunction with ISO 25024 [22], it complements their model by providing important indications for the definition of measurements and measurement methods for the data quality dimensions or characteristics. ISO 25012 introduces fifteen data quality characteristics, which are classified into the following three groups: (i) Inherent. The definition for these data quality characteristics is introduced in Table 2; (ii) System dependent. There are various characteristics whose measurement or assessment largely depends on the implementation of the systems in which data is stored, retrieved or processed; (iii) Inherent and system dependent. This group contains some of the previous data quality characteristics whose measurement and/or assessment can be subject to a two-fold interpretation based on the ideas introduced in the two previous groups. Please, note that Wang et al. (and many other investigations based on this seminal work) use the term “dimension”, whereas in the standards, Table 1 Data quality dimensions by Wang et al. [43]. Data quality category Data quality dimension Intrinsic Accuracy, Objectivity, Believability, Reputation Accessibility Access, Security Contextual Relevancy, Value-Added, Timeliness, Completeness, Amount of data Representational Interpretability, Ease of understanding, Concise representation, and Consistent representation ´ A. Valencia-Parra et al. 72 Chapter 3. Discussion and Publications Decision Support Systems 141 (2021) 113450 3 the term “characteristic” is preferred. Even though it would be possible to justify the difference, for the sake of the simplicity, let us consider these two terms as synonymous in this manuscript. As previously stated, measurement and assessment of data quality characteristics is a complex process, which largely depends on the context of use of the data. The context of the data includes: the organisational environment and the description of the business processes in which data is used; the technological architecture supporting the use of the data; and the skills and knowledge of both data stewards and data quality analysts in charge of managing or using the data [8,24]. In order to deal with this complexity, several researchers and practitioners have proposed different methodologies, which include a variety of metrics and/or measurement methods [4,29,34,43]. Typically, measurement methods that are to be applied first require relational datasets to be profiled for a better understanding of the nature of the data. These profiling processes are often performed in batch activities that include all data records in the dataset and by means of data profiling tools [13,34]. Nevertheless, in order to measure data quality, most authors have developed their own rule-based data quality measurement systems. The foundations of these rule-based data quality measurement systems have been formalised by Bronselaer et al. in [7]. The creation of rule-based data quality measurement systems involves that stakeholders (i.e. data stewards) should conform to the semantics of the data and their context. However, if stakeholders remain unaware of the semantics of the data and the way in which these semantics have been implemented throughout the various data models (conceptual, logical, and physical), then the application of this kind of tool will require an extra effort towards diagnosing the root causes of the low levels of data quality, since the methodology behind these tools fails to contemplate the context in which the data quality process is applied. The instantiating of these frameworks involves the creation of various elements, such as the set of business rules to which data must adhere, and the possible results of the measurement that the capacity function should produce. An example of the instantiating of this conceptualization for the measurement of the level of quality in information systems research is presented in [39], wherein Timmerman and Bronselaer, after reviewing the foundations of rule-based data quality measurement, present a rule-based framework for the measurement and assessment of the quality of data in Information Systems research. As we will explain in Section 3, our proposal, goes beyond the measurement of data quality, involving more stages. Consequently, we have to describe and relate several sets of business rules. 2.2. Decision model and notation Decision Model and Notation (DMN) is the modelling language and notation standard defined by OMG to describe decision rules [30]. Thus, DMN is a standard approach that facilitates the modelling of repeatable decisions. The decisions can be customised according to the necessities of each organisation or moment, thereby ensuring that the decision models are interchangeable. DMN facilitates the declarative description and formalisation of the decisions with the form “if-then” [19]. Furthermore, since DMN is supported by a set of engines, such as Camunda - DMN Engine 1 and Drools - DMN Engine, 2 we found DMN to be the most suitable concept to come to the data quality assessment to real applicability of it. DMN provides a mechanism to define a decision logic model that is understandable by non-expert users (i.e., business data stewards in charge of describing the data quality requirements). In addition, DMN enables the separation of the decision logic from the control-flow logic, thereby centralising the conditional expressions that guide the decisions. The DMN standard provides two customisable components: the Decision requirement diagram, which enables the definition to be made of the decisions to be taken, of their interrelationships, and of their requirements for decision logic; and the Decision logic, which allows the representation of the required decisions with sufficient details to enable validation and/or automation. Decision logic is described by means of a decision table (see Fig. 1), which includes a set of inputs, decision rules, and output values. In a horizontal representation of the rules (an equivalent vertical representation is also possible), the input and outputs are defined in columns and the rules as rows. Each IF-THEN condition is represented in a row, as a conjunction of basic expressions written in FEEL (Friendly Enough Expression Language) [30]. The output returns the values of the row that is satisfiable according to the input. The example considers three features given as input data (i.e., CPU, Memory, and Storage), which returns a decision as output for the variable Instance − Family. Each condition that appears in the DMN table (such as >=2.9) relies on FEEL, 3 an expression language that enables the writing of the conditions for the rules in the DMN tables. FEEL supports several data types as input and output values (e.g., String, Integer, Decimal, Date, Boolean), and implements a set of built-in functions to write more complex conditions on the input values. In addition, this expression language also supports null values and conditions that are always true (‘−’). Users can modify the behaviour of the built-in functions as well as creating their own functions to better adjust the rules to the nature of their data. This versatility ensures that any of the types of business rules defined in Section 3.1 can be modelled with this technology, and formalised as described in Section 3.2. The information item name is the name of the variable for which the decision table provides the decision logic. The hit policy indicator determines how to handle the multiple matches of the rules described in DMN [30]. This indicator takes any of 5 values: Unique (U): only one rule can be triggered, and it is not possible that more than one can satisfy a Table 2 Definition of the inherent data quality characteristics from ISO 25012 [21]. Data quality characteristic Definition Accuracy The degree to which data has attributes that correctly represent the true value of the intended attribute of a concept or event in a specific context of use. Completeness The degree to which subject data associated with an entity has values for all expected attributes and related entity instances in a specific context of use. Consistency The degree to which data has attributes that are free from contradiction and are coherent with other data in a specific context of use. Credibility The degree to which data has attributes that are regarded as true and believable by users in a specific context of use. Currentness The degree to which data has attributes that are of the right age in a specific context of use. Fig. 1. Decision table for selecting the Instance Family depending on the CPU, Memory, and Storage of the server. 1 https://camunda.com/products/dmn-engine/ 2 https://www.drools.org/learn/dmn.html 3 https://docs.camunda.org/manual/7.4/reference/dmn11/feel/ ´ A. Valencia-Parra et al. 3.2. Publications 73 Decision Support Systems 141 (2021) 113450 4 rule for an input tuple; Any (A): Multiple rules can be triggered, but they must agree in the output; Priority (P): Multiple rules can be triggered, and the output corresponds to the rule that has the highest priority; First (F): Multiple rules can be triggered, and the output corresponds to the order of the rows in the decision table; and Collect (C): Multiple rules can be triggered, and the output is an aggregation. In our case, F means that although multiple rules can match, only the first hit by rule order is returned. Finally, the possible results of this decision table are “Compute optimised”, “Memory optimised”, “Storage optimised”, and “General purpose”. Table 3 depicts the results of applying the DMN table presented in Fig. 1. Decision tables can be combined in a hierarchical way, in that the output of one table can be the input of another further up in the hierarchy. For instance, as shown in Fig. 2, the output of “Instance Family Selection” will be used as input of the decision table “Supplier Selection”. Unlike other alternatives for the verification of business rules, DMN allows users to define their rules in a hierarchical way, thereby maintaining the coherence with the logical structure previously explained. The way in which rules are graphically modelled, its versatility, and the possibility of automating the evaluation of the rules, make DMN the ideal candidate for technically supporting our methodology. 3. Rationale of DMN4DQ Given the goal of our investigation, in this section, the rationale of our proposal is presented. Firstly, we describe the conceptualization of how to generate the recommendation on the usability of a data record based on its level of quality. Subsequently, an explanation is given on how DMN has been employed to represent and evaluate the required sets of business rules to automate the generation of a recommendation for the use of a data record. 3.1. Business rules for the determination of the usability of the data records The generation of a recommendation of a business-driven decision on using or discarding a data record can be based on several criteria, but, to our understanding, data quality is the most important criterion because decisions are no better than the data on which they are based [44]. Consequently, to generate this recommendation, it is necessary to assess the level of data quality within a context of use. As stated in Section 2.1, this assessment requires a previous stage of measurement of data quality. Both the assessment and measurement require different data quality dimensions that represent stakeholders’ data quality requirements for each task at hand. It is known that business rules define certain business constraints of an organisation, such as who can execute an action, the order of the activities, and the acceptable thresholds for specific KPIs. In this respect, it is possible to define business rules to address data quality concerns for the proper execution of the processes of an organisation. Hence, business rules for data quality gather the knowledge acquired by an organisation to reflect when a data record can provide value for specific business goals. There exists a consensus that business rules are an effective way to control data quality [2], and the term “Data Quality Rule” has been used in the context of data quality management [27,34]. Our proposal introduces the notion of Business Rules for Data Decisions (BR.DD), that must be defined in order to ascertain the usability of a data record. The types of BR.DD considered in our proposal are the following: •The “Business Rules for Data Values” (BR.DV) are those aimed towards evaluating the extent to which a data requirement is met. An example of BR.DV is provided in the following: Given that the length of a String must be longer than 6, if the length of an input String is from 3 to 6 then it returns ‘A’, else if it is from 6 to 9 then it returns ‘B’, and ‘C’ is returned otherwise. Semantically, ‘A’ is intended to represent the lowest level of fulfilment, and ‘C’ represents a suitable level of fulfilment, with ‘B’ representing an average term. We consider that this is not a proper data quality measurement since data quality dimensions have yet to be involved. However, the output of this evaluation will be the input of the specific data quality measurement. •The “Business Rules for Data Quality Measurement” (BR.DQM) are those rules employed to compute the measurement of the level of quality of each data quality dimension according to the BR.DV. For example, a BR.DQM for the accuracy dimension could be stated as follows: A record can be considered as Dramatically Non-Accurate if the output of BR.DV.01 is ‘A’, and Accurate if the output of BR.DV.01 is ‘B’ or ‘C’. •The “Business Rules for Data Quality Assessment” (BR.DQA) are those rules that describe the assessment of the data quality in accordance with a set of BR.DQM by combining the results of the measurement of several data quality dimensions, as indicated by the business. An example of BR.DQA is A record can be considered as: Usable but assuming High Risk if it is Accurate or Correct; Usable and assuming Low Risk, if it is Accurate and Correct; and non-usable otherwise. •The “Business Rules for Data Usability Decision” (BR.DUD) are those rules employed to generate the recommendation about using or discarding the data record for the intended use based on the assessment of its level of data quality. At this point, the organisational risk-appetite of the organisation should be considered with regard to the use of this specific data record. For instance, A record will be used if it is Usable and assuming Low Risk. 3.2. Tailoring DMN elements to make the decision operative regarding data usability Regardless of the type of business rules previously described, the formalisation of all of them is the same. The relations between them lies in the semantics derived from our conception on the hierarchy as established in the previous sections, and consequently, we will build and relate the decision table in a hierarchical structure. 3.2.1. Formalisation of data quality rules based on DMN Based on DMN, the business rules applied in the generation of a recommendation on the potential use of a data record based on data quality concerns are formalised below. The definition of the rules include: (i) a set of input parameters; (ii) a list of if-then conditions; and (iii) the output values for each condition. Let an instance of Business Rules for Data Decision (BR.DD) be a tuple 〈Inputs, Rules, Outputs〉where: Table 3 Results of applying the DMN table to a set of data records. ID CPU Memory Storage Instance Family (DMN Output) 1 2.4 128 500 GB SSD Memory Optimised 2 3.2 32 1000 GB Compute Optimised 3 2.7 32 1000 GB General Purpose 4 3.0 64 250 GB SSD Compute Optimised Fig. 2. Decision requirement diagram example. ´ A. Valencia-Parra et al. 74 Chapter 3. Discussion and Publications Decision Support Systems 141 (2021) 113450 5 •Inputs: This is a tuple of attributes a i of type A i , 〈a 1 :A 1 , …, a n :A n 〉, where the types permitted are String, Boolean, Integer, Real, and Date. It is represented by means of the Input data of the DMN tables. •Output: This is a tuple of attributes b i of type B i , 〈b 1 :B 1 , …, b m :B m 〉, where the types permitted are: String, Boolean, and Integer (in a limited and finite domain). It is represented by means of the output data of the DMN tables. •Rules: This is an ordered list of if-then rules 〈r 1 , …, r k 〉where r i−1 has greater priority than r i , which corresponds with the Hit Policy indicator (F) of the DMN table. Each r i corresponds with a tuple of a DMN table, where each r i has the form 〈{Q 1 , …, Q n }, {o 1 , …, o n }〉, where Q j represents the conditions applied to the attribute a i expressed in FEEL (if), and o j represents the resulting then expression. Next, the formalisation presented in [9] is detailed: Q::=“−” ∣ Term ∣ “not(“Term ”)” ∣ Comparison ∣Interval ∣Q1,Q2 Comparison ::=COpTerm COp ::=“=” ∣ “ <” ∣ “ >” ∣ “ ≤” ∣ “ ≥” ∣ “ ∈” Interval ::= (“(”|“[”)Term1“..”Term2(“)”|“]”) Term ::=v∣f(Term1,…,Termm) For the grammar of FEEL certain remarks are needed: (i) v is a value of the domain and f is a function (e.g., +, −, round, ceiling, duration, day, etc.); (ii) “−“represents any value; (iii) Comparison and Interval are only applicable to numeric types; (iv) “Q 1 , Q 2 “represents “Q 1 ∨Q 2 “; and (v) if an attribute a i fails to exist, the only condition that it could meet is “−“. For a further description of FEEL, please consult [30]. 3.2.2. DMN hierarchical structure As stated in Section 3.1, we have identified different types of BR.DD involved in the process of generating a recommendation on the usability of a data record. As stated, each BR.DD can be described by means of a decision table in DMN, and BR.DDs can be combined according to their semantics to generate a final decision regarding the data record usability. Therefore, we propose a description of all the BR.DDs as DMN tables and a combination thereof in a hierarchical way as shown in Fig. 3. The hierarchy enables: (1) BR.DV (at the top) is evaluated for every data record provided as Input. This data record can be of any of the types defined in the formalisation; (2) for each data quality dimension, a BR.DQM uses the retrieved Outputs of the required BR.DVs as Input (which can be Boolean, String or a bounded range of Integers) in a similar way; (3) a BR.DQA uses the output of different DMN tables related to the measurement of a dimension (BR.DQM) as Input; and (4) BR.DUD (at the bottom of the hierarchy) takes the Outputs of BR.DQA as Input to which it applies its if-then rules. In addition, the output of the business rules for data decisions must return an output from an established and ordered scale, whereby the best and the worst outputs are indicated, in order to guarantee the monotonicity of the business rule [39]. 4. DMN4DQ: a methodology to develop a system to generate recommendations on the usability of a data record In order to systematically instantiate all the DMN elements identified in Section 3.1, we now introduce a methodology called DMN4DQ. DMN4DQ will guide data stewards and stakeholders towards achieving the goal of implementing a system that can be integrated along with the Information Systems supporting the business process. The methodology consists of the following phases: (i) Phase 1. Define Business Rules for Data Decisions and the underlying hierarchy (see Subsection 4.1); (ii) Phase 2. Instantiate the DMN tables of the DMN4DQ hierarchy (see Subsection 4.2); (iii) Phase 3. Deploy, test, and integrate the DMN4DQ hierarchy into the systems needing a recommendation on the potential use of a data record (see Subsection 4.3). Fig. 4 summarises these phases. We provide a detailed description of each phase in the next sections. 4.1. Phase 1. Define business rules for data decisions with the aim of generating a recommendation on data usability The Definition of the Business Rules for Data Decisions includes the following steps aligned with the types of business rules defined in the previous section: •Step 1.1. Define Data Context: Describe the context in which the data is used. •Step 1.2. Describe the Dataset: Describe the dataset, its attributes, and the technological stack that supports the management and use of the data. •Step 1.3. Define Business Rules for Data Values (BR.DV): Identify the business rules to enable the validation of the data requirements on the data to generate a value representing the extent to which the data requirement is met. All these requirements should be desirably implemented during the design of the data repository [11,28]. •Step 1.4. Select the Data Quality Dimensions that best represent the usability of the data: Identify the combination of relevant data quality dimensions that best represent business requirements for data in the specific context of the use of data, such as completeness, consistency, or any of those dimensions identified by Wang et al. [43] or ISO 25012 [21] as introduced in Section 2.1. In addition, it is necessary to identify the possible output values that can be assigned to the measurement of every data quality dimension. Although stakeholders can define any domain of values for the results of these activities, for the sake of simplicity, we propose employing Likert scales [23]. For example, the data quality dimension of consistency could admit three possible values as a result: “Sufficiently Consistent”, “Insufficiently Consistent”, and “Dramatically Non-consis- tent”. Additionally, in order to ensure the monotonicity of the rule [39], it is necessary to denote which value represents the highest level of quality and which represents the lowest level of quality. For example, “Sufficiently Consistent” and “Dramatically Non-consis- tent”, respectively. •Step 1.5. Define Business Rules for Data Quality Measurement (BR. DQM): Identify, describe, and validate the business rules aimed to measure the chosen data quality dimensions in Step 1.4. This step needs to be broken down into two further steps: (1) to associate specific BR.DV to every data quality dimension considered; and (2) to produce the “Data Quality Measurement Business Rules” (BR. DQM) that consider the data quality requirements stated by the business data stewards for the data in a given context. Depending on the granularity, a BR.DQM can cover one or more attributes and one or more BR.DVs [34]. •Step 1.6. Define Business Rules for Data Quality Assessment (BR. DQA): Identify, describe, and validate the business rules aimed to assess the level of data quality. This step includes the following actions: (i) Identify the relative importance (i.e., weight) of the data quality dimension in the assessment of the data quality of every data record in the context of use; (ii) identify the possible states of the usability of the data (output of BR.DQA). The states that can be enumerated include: “Fully Usable”, “Usable but cleansing recommended”, “Usable with a high risk”, “Not usable”; (iii) produce the “Data Quality Assessment Business Rules” (BR.DQA) that cover the combination or aggregation of the data quality dimensions involved, and by considering their relative importance. •Step 1.7. Define Business Rules for the generation of a recommendation on the potential usability of Data: Identify and describe the business rules aimed to generate a recommendation on the use of the data (BR.DUD) in the given context of the data. To generate a recommendation on “Using” or “Discarding” the data, it is crucial to take into account the organisational appetite-risk related to data ´ A. Valencia-Parra et al. 3.2. Publications 75 Decision Support Systems 141 (2021) 113450 12 Technology of Spain via ECLIPSE (RTI2018-094283-B-C33 and RTI2018-094283-B-C31) projects; the Junta de Andalucíavia the COPERNICA and METAMORFOSIS projects; the European Fund (ERDF/ FEDER); the Junta de Comunidades de Castilla-La Mancha via GEMA: Generation and Evaluation of Models for dAta quality (Ref.: SBPLY/17/ 180501/000293), and by the Universidad de Sevilla with VI Plan Propio de Investigaci´ on y Transferencia (VI PPIT-US). References [1] Z. Abedjan, L. Golab, F. Naumann, Profiling relational data: a survey, VLDB J. 24 (2015) 557–581. [2] P. Alpar, S. Winkelstr¨ ater, Assessment of data quality in accounting data with association rules, Expert Syst. Appl. 41 (2014) 2259–2268. [3] D. Ardagna, C. Cappiello, W. Sam´ a, M. Vitali, Context-aware data quality assessment for big data, Futur. Gener. Comput. Syst. 89 (2018) 548–562, https:// doi.org/10.1016/j.future.2018.07.014. [4] C. Batini, C. Cappiello, C. Francalanci, A. Maurino, Methodologies for data quality assessment and improvement, ACM Comput. Surv. (CSUR) 41 (2009) 1–52. [5] P. Bohannon, W. Fan, F. Geerts, X. Jia, A. Kementsietsidis, Conditional functional dependencies for data cleaning, in: 2007 IEEE 23rd International Conference on Data Engineering, 2007, pp. 746–755. [6] A. Boskovitz, R. Gor´ e, M. Hegland, A logical formalisation of the fellegi-holt method of data cleaning, in: M. Berthold, H.J. Lenz, E. Bradley, R. Kruse, C. Borgelt (Eds.), Advances in Intelligent Data Analysis V, Springer Berlin Heidelberg, Berlin, Heidelberg, 2003, pp. 554–565. [7] A. Bronselaer, R. De Mol, G. De Tr´ e, A measure-theoretic foundation for data quality, IEEE Trans. Fuzzy Syst. 26 (2017) 627–639. [8] I. Caballero, E. Verbo, C. Calero, M. Piattini, A Data Quality Measurement Information Model Based on iso/iec 15939, ICIQ, Cambridge, MA, 2007, pp. 393–408. [9] D. Calvanese, M. Dumas, Ü. Laurson, F.M. Maggi, M. Montali, I. Teinemaa, Semantics and analysis of dmn decision tables, in: M. La Rosa, P. Loos, O. Pastor (Eds.), Business Process Management, Springer International Publishing, 2016, pp. 217–233. [10] F. Chiang, R.J. Miller, Discovering data quality rules, in: Proceedings of the VLDB Endowment 1, 2008, pp. 1166–1177. [11] E.F. Codd, Extending the database relational model to capture more meaning, ACM Trans. Database Syst. 4 (1979) 397–434, https://doi.org/10.1145/ 320107.320109. [12] T. Davenport, J. Harris, Competing on Analytics: Updated, with a New Introduction: The New Science of Winning, Harvard Business Press, 2017. [13] L. Ehrlinger, E. Rusz, W. W¨ oß, A Survey of Data Quality Measurement and Monitoring Tools, 2019 arXiv preprint arXiv:1907.08138. [14] A. Even, G. Shankaranarayanan, Utility-driven assessment of data quality, in: ACM SIGMIS Database: The DATABASE for Advances in Information Systems 38, 2007, pp. 75–93. [15] A. Even, G. Shankaranarayanan, P.D. Berger, Evaluating a model for cost-effective data quality management in a real-world crm setting, Decis. Support. Syst. 50 (2010) 152–163. [16] W. Fan, Data quality: Theory and practice, in: H. Gao, L. Lim, W. Wang, C. Li, L. Chen (Eds.), Web-Age Information Management. WAIM 2012. Lecture Notes in Computer Science vol. 7418, Springer, Berlin, Heidelberg, 2012, pp. 548–553. [17] W. Fan, Data quality: from theory to practice, ACM SIGMOD Rec. 44 (2015) 7–18. [18] W. Fan, J. Li, S. Ma, N. Tang, W. Yu, Towards certain fixes with editing rules and master data, VLDB J. 21 (2012) 213–238. [19] K. Figl, J. Mendling, G. Tokdemir, J. Vanthienen, What we know and what we do not know about DMN, Enterpr. Model. Inform. Syst. Architect. 13 (2) (2018) 1–16. [20] B. Glavic, Big data provenance: Challenges and implications for benchmarking, in: Specifying Big Data Benchmarks - First Workshop, WBDB 2012, San Jose, CA, USA, May 8-9, 2012, and Second Workshop, WBDB 2012, Pune, India, December 17-18, 2012, Revised Selected Papers, 2012, pp. 72–80, https://doi.org/10.1007/978-3- 642-53974-9_7. [21] ISO-25012, Iso/iec 25012: Software Engineering-Software Product Quality Requirements and Evaluation (square)-Data Quality Model, 2008. [22] ISO-25024, Iso/iec 25024:2015 Systems and Software Engineering — Systems and Software Quality Requirements and Evaluation (square) — Measurement of Data Quality, 2015. [23] A. Joshi, S. Kale, S. Chandel, D.K. Pal, Likert scale: explored and explained, Br. J. Appl. Sci. Technol. 7 (2015) 396. [24] J. Ladley, Data Governance: How to Design, Deploy, and Sustain an Effective Data Governance Program, Academic Press, 2019. [25] S. Lee, B. Lud¨ ascher, B. Glavic, PUG: a framework and practical implementation for why and why-not provenance, VLDB J. 28 (2019) 47–71. [26] Y. Liu, Y. Wang, K. Zhou, Y. Yang, Y. Liu, Semantic-aware data quality assessment for image big data, Futur. Gener. Comput. Syst. 102 (2020) 53–65. [27] D. Loshin, 17 - data quality and business rules in practice, in: D. Loshin (Ed.), Enterprise Knowledge Management, Academic Press, San Diego. The Morgan Kaufmann Series in Data Management Systems, 2001, pp. 425–461, https://doi. org/10.1016/B978-012455840-3.50017-0. [28] D. Loshin, The practitioner’s Guide to Data Quality Improvement, Elsevier, 2010. [29] J. Merino, I. Caballero, B. Rivas, M.A. Serrano, M. Piattini, A data quality in use model for big data, Future Generation Comp. Syst. 63 (2016) 123–130, https://doi. org/10.1016/j.future.2015.11.024. [30] OMG, Decision Model and Notation (DMN), Version 1.2, URL, https://www.omg. org/spec/DMN, 2019. [31] OMG, Semantics Of Business Vocabulary And Rules, Version 1.5, URL, http s://www.omg.org/spec/SBVR/About-SBVR/, 2019. [32] B. Otto, Y.W. Lee, I. Caballero, Information and data quality in business networking: a key concept for enterprises in its early stages of development, Electron. Mark. 21 (2011) 83. [33] J.M. P´ erez-´ Alvarez, A. Mat´ e, M.T. G´ omez-L´ opez, J. Trujillo, Tactical businessprocess-decision support based on kpis monitoring and validation, Comput. Ind. 102 (2018) 23–39, https://doi.org/10.1016/j.compind.2018.08.001. [34] L. Sebastian-Coleman, Measuring Data Quality for Ongoing Improvement: A Data Quality Assessment Framework, Newnes, 2012. [35] K. Sha, S. Zeadally, Data quality challenges in cyber-physical systems, J. Data Inform. Qual. (JDIQ) 6 (2015) 1–4. [36] G. Shankaranarayanan, Y. Cai, Supporting data quality management in decisionmaking, Decis. Support. Syst. 42 (2006) 302–317, https://doi.org/10.1016/j. dss.2004.12.006. [37] V.C. Storey, R.M. Dewan, M. Freimer, Data quality: setting organizational policies, Decis. Support. Syst. 54 (2012) 434–442, https://doi.org/10.1016/j. dss.2012.06.004. [38] J.G. Suarez, in: Philip B. Crosby, W. Edwards Deming, Joseph M. Juran (Eds.), Three Experts on Quality Management, Total Quality Leadership Office, Arlington VA, 1992. Technical Report. [39] Y. Timmerman, A. Bronselaer, Measuring data quality in information systems research, Decis. Support. Syst. 126 (2019) 113138, https://doi.org/10.1016/j. dss.2019.113138. [40] ´ A. Valencia-Parra, ´ A.J. Varela-Vaca, M.T. G´ omez-L´ opez, P. Ceravolo, Chamaleon: Framework to Improve Data Wrangling with Complex Data, in: 40th International Conference on Information Systems, ICIS 2019, Association for Information Systems, 2019. URL, https://aisel.aisnet.org/icis2019/data_science/data_science /16. [41] J. Vanthienen, E. Dries, Illustration of a decision table tool for specifying and implementing knowledge based systems, Int. J. Artif. Intell.Tools 3 (1994) 267–288. [42] J. Vanthienen, C. Mues, A. Aerts, An illustration of verification and validation in the modelling phase of KBS development, Data Knowl. Eng. 27 (1998) 337–352, https://doi.org/10.1016/S0169-023X(98)80003-7. [43] R.Y. Wang, A product perspective on total data quality management, Commun. ACM 41 (1998) 58–65. [44] R.Y. Wang, M.P. Reddy, H.B. Kon, Toward quality data: an attribute-based approach, Decis. Support. Syst. 13 (1995) 349–372, https://doi.org/10.1016/ 0167-9236(93)E0050-N (information technologies and systems). [45] S. Watts, G. Shankaranarayanan, A. Even, Data quality assessment in context: a cognitive perspective, Decis. Support. Syst. 48 (2009) 202–211, https://doi.org/ 10.1016/j.dss.2009.07.012. [46] C. Wohlin, P. Runeson, M. H¨ ost, M.C. Ohlsson, B. Regnell, Experimentation in software engineering, Springer. (2012), https://doi.org/10.1007/978-3-642- 29044-2. ´ Alvaro Valencia-Parra (PhD. Student) Universidad de Sevilla, Dpto. Lenguajes y sistemas inform´ aticos – Spain. ´ Alvaro Valencia-Parra obtained his B.S degree in Software Engineering at the University of Seville in 2017. In 2019, he graduated with honors from the University of Seville with a M.Sc. degree in Computer Engineering. Currently, he is a PhD student. His research areas include the improvement of different activities in the Big Data Pipeline, such as data transformation, data quality, and data analysis. The scenarios he is facing up are mainly focused on the process mining paradigm. Hence, his goal is to improve the way in which final users deal with data preparation and specific scenarios in which configuring a Big Data Pipeline might be tricky. For this purpose, he is working in the improvement of these processes by designing Domain-Specific Languages, user interfaces, and semi-automatic approaches in order to assist users in these tasks. He has participated in prestigious congresses such as the BPM Industry Forum or the International Conference on Information Systems (ICIS). ´ A. Valencia-Parra et al. 82 Chapter 3. Discussion and Publications Decision Support Systems 141 (2021) 113450 13 Luisa Parody (Associate Professor), Universidad Loyola Andalucía, Sevilla, Spain. Luisa Parody studied computer engineering (including a minor in systems engineering) at the Universidad de Sevilla (Spain) and graduated with honors in July 2009. She then earned an M.Sc.degree in software engineering and technology(2010) and obtained her international PhD with honors at the Universidad Sevilla (2014). Since 2018, she has been working as an associate professor in Dto. M´ etodo Cuantitativos at the Universidad Loyola. She belongs to the IDEA Research Group and has participated in several private and public research projects and has published several high-impact papers. ´ Angel Jesús Varela-Vaca, (Assistant Professor) Universidad de Sevilla, Dpto. Lenguajes y sistemas inform´ aticos – Spain. Angel J. Varela-Vaca received the B.S. degree in Computer Engineering at the University of Seville (Spain) and graduated in July 2008. M.Sc. on Software Engineering and Technology (2009) and obtained his PhD with honors at the University of Seville (2013). Angel is currently working as Assistant Professor at Languages and System Informatics Department at the Universidad Sevilla and belongs to the Idea Research Group. Angel has and leaded various private projects and participated in several public research projects and he has published several impact papers. He was nominated as a member of Program Committees such as ISD 2016, BPM Workshops 2017, SIMPDA 2018. He has been reviewer for international journals such as Journal of Supercomputing, International Journal of Management Science and Engineering Management Multimedia Tools and Applications, Human- Centric Computational and Information Sciences, Mathematical Methods in Applied Sciences among others. Ismael Caballero, (Associate Professor) Universidad de Castilla-La Mancha, Dpto. Tecnologías y Sistemas de Informaci´ on. ISMAEL CABALLERO received the M.Sc. and Ph.D. degrees in computer science from the University of Castilla-La Mancha, Spain, in 2004, where he works as Associate Professor with the Information Systems and Technologies Department. In 2017, he cofounded the spinoff DQTeam where he serves as Training Head. He has been researching on data quality management and data governance, since 1998, coauthoring several books, conference and journal articles. He teaches data quality management and data governance foundations in many universities and companies. He holds several professional certifications: CISA certification by ISACA, since 2016, CDO-1 certification by UALR-MIT, since 2017. He is currently a member of ISO TC184/SC4 working as Project Editor for several parts of ISO 8000-60 series development project. He led the project of ISO 8000-62SMAEL CABALLERO received the M.Sc. and Ph.D. degrees in computer science from the University of Castilla-La Mancha, Spain, in 2004, where he works as Associate Professor with the Information Systems and Technologies Department. In 2017, he cofounded the spinoff DQTeam where he serves as Training Head. He has been researching on data quality management and data governance, since 1998, coauthoring several books, conference and journal articles. He teaches data quality management and data governance foundations in many universities and companies. He holds several professional certifications: CISA certification by ISACA, since 2016, CDO-1 certification by UALR-MIT, since 2017. He is currently a member of ISO TC184/SC4 working as Project Editor for several parts of ISO 8000-60 series development project. He led the project of ISO 8000-62. María Teresa G´ omez-L´ opez, (Associate Professor) Universidad de Sevilla, Dpto. Lenguajes y sistemas inform´ aticos – Spain. María Teresa G´ omez-L´ opez is a Lecturer at the University of Seville and the head of the IDEA Research Group. Her research areas include Business Processes and Data management, and how to improve the business process models including better decisions and enriching the model with Data Perspectives. She has led several private and public research projects and has published several impact papers, among others in Information and Software Technology, Information Systems, Information & Software Technology, or Data & Knowledge Engineering. She was nominated as a member of Program Committees, such as ER, BPM, EDOC, ISD or CAISE Doctoral Consortium. She has been reviewing for international journals, such as International Journal of Data and Information Quality, Journal of Systems and Software, Artificial Intelligence in Medicine; Business & Information Systems Engineering Journal or Information Science. She has been invited as a keynote speaker in various occasions, such as at the Workshop on Data & Artifact Centric BPM, International Workshop on Decision Mining & Modelling for Business Processes BPM, the X National Conference of BPM, the 28th IBIMA Conference. ´ A. Valencia-Parra et al. 3.2. Publications 83 84 Chapter 3. Discussion and Publications 3.2.3 Unleashing Constraint Optimisation Problem solving in Big Data environments Published in the Journal of Computational Science (Vol. 45, p.101180). Elsevier BV. •Authors: Álvaro Valencia-Parra, Ángel Jesús Verala-Vaca, Luisa Parody, María Teresa Gómez- López. •DOI: 10.1016/j.jocs.2020.101180. •Rating: Q2 (JCR’20 3.976). Journal of Computational Science 45 (2020) 101180 Contents lists available at ScienceDirect Journal of Computational Science journa l h om epage: www.elsevier.com/locate/jocs Unleashing Constraint Optimisation Problem solving in Big Data environments Álvaro Valencia-Parraa, Ángel Jesús Varela-Vacaa,∗, Luisa Parodyb, María Teresa Gómez-Lópeza,1 aDpto. Lenguajes y Sistemas Informáticos, Universidad de Sevilla, IDEA Research group, Spain bDpto. Métodos Cuantitativos, Universidad Loyola Andalucía, IDEA Research group, Spain a r t i c l e i n f o Article history: Received 25 November 2019 Received in revised form 2 June 2020 Accepted 18 June 2020 Available online 24 June 2020 Keywords: Big Data Optimisation problem Constraint programming Distributed data Heterogeneous data format a b s t r a c t The application of the optimisation problems in the daily decisions of companies is able to be used for finding the best management according to the necessities of the organisations. However, optimisation problems imply a high computational complexity, increased by the current necessity to include a massive quantity of data (Big Data), for the creation of optimisation problems to customise products and services for their clients. The irruption of Big Data technologies can be a challenge but also an important mechanism to tackle the computational difficulties of optimisation problems, and the possibility to distribute the problem performance. In this paper, we propose a solution that lets the query of a data set supported by Big Data technologies that imply the resolution of Constraint Optimisation Problem (COP). This proposal enables to: (1) model COPs whose input data are obtained from distributed and heterogeneous data; (2) facilitate the integration of different data sources to create the COPs; and, (3) solve the optimisation problems in a distributed way, to improve the performance. It is done by means of a framework and supported by a tool capable of modelling, solving and querying the results of optimisation problems. The tool integrates the Big Data technologies and commercial solvers of constraint programming. The suitability of the proposal and the development have been evaluated with real data sets whose computational study and results are included and discussed. © 2020 Elsevier B.V. All rights reserved. 1. Introduction The use of optimisation problems let organisations manage the resources, time, and cost of their processes. However, the necessity to create customised products according to the profiles of the clients implies the creation of thousands of optimisation problems. Moreover, the incorporation of more interesting data, frequently provided by multiple systems and services [33], will make companies more competitive. Moreover, the integration of more complex data implies the resolution of optimisation problems that could suppose a computationally complex task, further an extra effort to integrate heterogeneous data format provided by different sources. COPs are frequently used to model and solve optimisation problems since they include among their advantages: the ability to model ∗Corresponding author. E-mail addresses: [email protected] (Á. Valencia-Parra), [email protected] (Á.J. Varela-Vaca), [email protected] (L. Parody), [email protected] (M.T. Gómez-López). 1http://www.idea.us.es/ problems declaratively, regardless of how it will be solved; their applicability to many real-life examples of industry, so its versatility and power are empirically demonstrated; and the existence of a significant amount of commercial tools that solve the constraint satisfaction problems locally. The resolution time of the problem can be compromised for both the complexity of the constraints and the size of the data set. Thereby, in the current scenarios, the information involved in a COP is not always centralised. The exponential growth of the data produced and stored and the distribution of the information have promoted the use of Big Data paradigm [25,31], producing difficulties that have not been adapted to COPs [41]. This new situation can produce that, the data and constraints that model their relations are distributed among different subsystems (also known as nodes) that constitute the global model. These models can be computationally highly complex since they can have distributed data or constraints. This interruption of Big Data into COPs can be seen as a new challenge, but also as a new opportunity to solve distributed problems and data. Before the Big Data burst into the scene, Distributed Constraint Optimisation Problems (DCOPs) [21,11] were defined to solve COPs where neither their constraints nor data were in a single system. https://doi.org/10.1016/j.jocs.2020.101180 1877-7503/© 2020 Elsevier B.V. All rights reserved. 3.2. Publications 85 2 Á. Valencia-Parra, Á.J. Varela-Vaca, L. Parody et al. / Journal of Computational Science 45 (2020) 101180 DCOP paradigm proposes a set of algorithms to solve a set of COPs that share variables. The resolution of each of them must be aware of the rest of the constraints that restrict the values of the variables. For this reason, DCOPs are focused on the communication between the distributed nodes that must synchronise the share variables to obtain a correct result of every constraint, variable and in each node. However, DCOP proposals do not provide a mechanism for a better distribution of the DCOPs for the optimal resolution of them. In this context, our proposal is based on the creation and distribution of isolated COPs in a Big Data infrastructure, whose partial resolution provides information to solve a greater problem utilising the MapReduce paradigm [10]. Furthermore, none of the algorithms proposed to solve DCOP have been presented as a practical and appropriate solution to actual environments, even less when the data used is characterised by its high variability, velocity, and volume (i.e., Big Data). Although the existence of the problem was formulated in our previous works [35,36], to the best of our knowledge, there are no solutions that adequate the COPs to data supported by Big Data infrastructure, dealing with large amounts of data, using the distributed node to parallelise the computation, getting results quickly, and managing a variety of data efficiently. As aforementioned, we identified the necessity of the COP resolution within different Big Data scenarios in [35,36]. In those previous work, we focused on describing the scenarios and their characteristics, then a solution was prototyped. However, the previous work lacks formalisation, implementation and evaluation with real data was done. In order to fulfil those gaps, we propose a solution which enables to define, execute and solve Constraint Optimisation Problems with Distributed Data in Big Data environment. The main contributions are four main: •Formalisation of Constraint Optimisation Problems with Distributed (Big) Data: An optimisation problem must be modelled describing the constraints that relate the data and the objective function to be optimised. When the data is distributed and the resolution of the problems depends on this data, the description of the model must include the distributed data than can have heterogeneous formats and come from Big Data environments. We formalise COP models that include these aspects. •Integration and transformation of heterogeneous data formats: The heterogeneity of the data formats makes necessary data preparation by means of a transformation into a unified format to apply the latter analysis. This task is especially relevant in our proposal since the mapping between input data to the optimisation problem must be defined, at the same time that the output obtained must be recovered. •Enable the optimal evaluation of queries over data provided by the resolution of Optimisation Problems: The resolution of various COPs can provide useful information, for example, to ascertain the most suitable products for each provider. However, to select the most appropriate for a specific organisation, these partial solutions obtained from the evaluation of the COPs must be queried. Our proposal is focused on the analysis of the queries over the COP data output to avoid, when it is possible, the resolution of the COPs, minimising the evaluation time. •Provide an integral framework to support the process: To cover the previous proposals, it is necessary a leap of advances in technologies that support the integration of the Big Data infrastructures with constraint optimisation solvers. This new technology is proposed as a new component in the Big Data ecosystem to enable the management of a great amount of data and the creation and distribution of several COPs, whose output data can be later queried. Unfortunately, there are no technological solutions that enable the application of optimisation problems with Big Data characteristics in real scenarios. This lack of tools means that these challenges need an extra effort to be solved. In order to tackle our proposal, FAst BIg cOstraint LAboratory (FABIOLA) framework is proposed. FABIOLA is a new Hadoop-based component [3] in the Big Data ecosystem. FABIOLA enables the modelling of optimisation problems whose heterogeneous format of the data, the amount of data to deal with, and the required velocity in the resolution of the problems forces a Big Data solution. The FABIOLA framework also provides the necessary techniques to solve COPs in a distributed way, either to obtain a result by optimising time and resources or because the nature of the problem is distributed. FABIOLA prototype was presented in previous works [35,36], thereby, this paper can be seen as an extension of the previous ones. However, certain challenges tackled here were not tackled in that previous works: how to transform the data for its integration with other distributed data; how to optimise the data obtained from the optimisation by means of a query language that reduces the COPs evaluation, and; how an integral solution could support the whole process providing an implemented tool used for the community as a new component of the Big Data ecosystem, and; the empirical evaluation of the approach with real data. The remainder of the paper is organised as follows: Section 2 formalises the modelling of the optimisation problems in Big Data environments. Section 3 details the different phases of the proposal that are illustrated with a running example to make the problem understandable. Section 4 analyses various operators for processing the results obtained from the resolution of the optimisation problems. Section 5 details the proposed architecture and the methodology necessary to support FABIOLA framework and the developed infrastructure. Section 6 presents the formalisation applied to a real case with a high volume of data. This section also shows a computational, statistical, and analytical study of our proposal. Section 7 includes the main related work. Finally, conclusions are drawn and future work is proposed in Section 8. 2. Overview of the proposal: Optimisation Problems within Big Data scenario The creation of a COPDD is a complex task, especially when the quantity of data involved, and the number of COPs is very high. This is why this creation must be recommendable automated. For this reason, our proposal integrates a set of components that facilitate both the creation and the distribution of the COPs for their resolution. Definition 1. A COPDD is defined by the tuple DS, COP, DM, DMapDS →DM, DMapDM →COP → DSoutput, where: •DS is the Data Set used as input data to find out the optimal solution of the problem. •COP is the Constraint Optimisation Problem. •DM is the Data Model that describes the relationship between the attributes of the DS and the COP. •DMapDS →DM and DMapDM →COP are the Data Mapping (DMap) that represents the relation between the attributes of the DS and the attributes of the DM, and the attributes of the DM and the variables used in the COP, respectively. •DSoutput is a data set obtained from the resolution of an optimisation problem according to the attributes defined in the DM and their corresponding values. Each element of the tuple of the COPDD plays a role to create and solve the COPs in an efficient way, as shown in Fig. 1. They are combined to create a framework that integrates the four phases of the 86 Chapter 3. Discussion and Publications Á. Valencia-Parra, Á.J. Varela-Vaca, L. Parody et al. / Journal of Computational Science 45 (2020) 101180 3 Fig. 1. Overview of the approach. COPDD creation: (1) data set preparation; (2) COP description; (3) mapping among the data sets and the COP, and; (4) data querying optimising the performance. Some definitions have been included to clarify the phases of the proposal, each of them is detailed in the following sections. 2.1. Running example To understand the proposal, a simple running example is used, although a real and more complex case study to compute the evaluation is given in Section 6. The running example is about a planning problem [9], that describes a company that manufactures two types of products: a standard product A, and a more sophisticated product B. Management charges a certain price for each unit of product A and a price for the unit of product B, whose profits are pAand pB respectively. Therefore, the profit of the company comes from the multiplication of the price by the number of units (i.e., qAand qB for products A and B) of each product. Manufacturing one unit of product A requires hAhours of labour and rmAunits of raw material. Similarly, for one unit of B, hBhours of labour and rmBunits of raw material are needed. Besides, the company’s policy indicates that the number of units manufactured of product A has to be, at least, the double of units than the produced for product B. At present, a nH of hours of labour and a nRM of units of raw material are available. The problem is focused on to maximise the company’s total revenue. Although every element of the COPDD will be described in the following sections, a brief approximation to the formalisation with the running example can be done at this point by identifying the Data Set (DS) and data to optimise: •DS: priceA, priceB, numUnitsA, numUnitsB, hoursA, hoursB, hoursLabour, rawA, rawB, unitsRawMaterial. •COP is defined to maximise the profit. 3. Phases of the proposal As presented in Fig. 1, four are the phases that our proposal supports to create and solve the COPDDs. Following sections describe each of them. 3.1. Data set preparation Data preparation is one of the most consuming processes in the Big Data pipeline [22,44]. One of the steps is the data transformation to fit the heterogeneous data formats into a single one for a later application of algorithms over all tuples. This type of problem is also tackled for the COPDD, that needs a DS with homogeneous tuples used as inputs. It implies that each input data (Dataa, Datab, . . ., Datan) must be transformed into a single one structure (DS), following the data transformation processes as detailed in [46]. Therefore, a heterogeneous data format is a set of data (Dataa, Datab, . . ., Datan) formed of a different set of attributes among them. Definition 2. A DS is a set of tuples formed of a set of attributes, {a1, a2, . . ., an}, where each tuple presents an assignment of values {val1, val2, . . ., valn} to each attribute. Some of the elements of the second row of Table 1 (cf., #ID, nH, nRM, hA, rmA, pA, hB, rmB, pB) presents the elements of the DS for the running example. 3.2. Constraint Optimisation Problem description A COP is a Constraint Satisfaction Problem (CSP) where an optimisation function determines the ‘best solution’ from the set of possibles. They come from Constraint Programming (CP) [39], an Artificial Intelligence (AI) discipline where a large number of problems and other areas of Computer Science can be seen as individual cases of CSP. Examples include scheduling, temporal reasoning, graph problems, and configuration problems. The basis of CP stands on the resolution of a CSP. Thereby, to understand correctly what is a COP, the CSP definition must be introduced before. Definition 3. A CSP represents a reasoning framework consisting of variables, domains and constraints V, D, C, where V is a set of n variables {v1, v2, . . ., vn} whose values are taken from finite domains {Dv1, Dv2, . . ., Dvm} respectively, and C is a set of constraints on their values. The constraint ck(xk1, . . ., xkm) is a predicate that is defined on the Cartesian product Dk1× . . . × Dkj. This predicate is true iff the value assignment of these variables satisfies the constraint ck. 3.2. Publications 87 4 Á. Valencia-Parra, Á.J. Varela-Vaca, L. Parody et al. / Journal of Computational Science 45 (2020) 101180 Table 1 Example of tuples for the running example. IN OUT OT #ID nH nRM hArmApAhBrmBpBprofit qAqBComp. #1 1500 400 3 4 5 4 6 10 570 58 28 Comp1 #2 900 200 1 2 3 2 3 4 300 100 0 Comp2 #3 1200 – 7 4 14 – 7 30 160 80 4640 Comp2 #4 – 300 2 3 9 4 6 11 900 100 0 Comp3 #5 1500 – – 1 8 – – 15 12000 1500 0 Comp4 Table 2 COP for the running example. Variables &domains: priceA, priceB, profit: Float; numUnitsA, numUnitsB, hoursA, hoursB: Integer; rawA, rawB, hoursLabour, unitsRawMaterial: Integer; Constraints: B i=A(hoursi∗ numUnitsi) ≤ hoursLabour B i=A(rawi∗ numUnitsi) ≤ unitsRawMaterial numUnitsA− 2 * numUnitsB≥ 0 profit =B i=A(pricei∗ numUnitsi) Optimisation function: Maximise(profit) The search for solutions for a CSP is based on the instantiation concept. An assignment of a variable, or instantiation, is a pair variable-value (x, a) which represents the assignment of the value a to the variable x. An instantiation of a set of variables is a tuple of ordered pairs, where each sorted pair (x, a) assigns the value a to the variable x. A tuple ((x1, a1), . . ., (xi, ai)) is consistent if it satisfies all the constraints formed by variables of the tuple. Several possible solutions can be found to satisfy a CSP, but sometimes only the more suitable wants to be obtained, one that optimises the solution. In those cases, a COP must be modelled. Definition 4. A COP is a CSP in which the solutions optimise (minimise or maximise) an objective function, f. For the example, for maximising the company’s total revenue can be formulated as shown in Table 2. The values of nH, nRM, hA, rmA, pA, hB, rmB, pBdepend on the company where the products are built. Table 1 shows some possible scenarios, where the output data (i.e., profit, qA, qB) is obtained according to each input data (per tuple). Every input data can be instantiated (e.g., tuples # 1 and # 2), and the output indicates the resulting profit and how many units of each product produces (cf., qAand qB). It is also possible that some input values were unknown (cf., the value ‘–’ in the table). In that case, the COP tries to find values for these variables to optimise the variable profit (cf., tuples # 3, # 4 and # 5). In this example, we can observe that there is another attribute, such as Company (cf., Comp.), that is not part of and does not influence the resolution of the optimisation problem. However, this kind of variables can be helpful to answer later queries, such as, Which is the manufacturer with the highest profit? Which is the manufacturer that produces more products B? If there are several tuples of input data, several are the possible optimal solutions that can be found. Thereby, the created COP can be seen as a meta-COP which is partially instantiated for each tuple of the DS. How to map the attributes of DS with the inputs of the COP is described is explained in the next subsections. 3.3. The mapping between the DS and COP In order to link the DS with the COP, it is necessary to define an independent DM which allow users to define how the data from the DS is used as input of the COPs, and the resultant data obtained by solving the COPs. Definition 5. A DM is a set of attributes, {a1, a2, . . ., an}, which is divided into three disjointed groups: Input (IN), Output (OUT), and Others (OT) attributes. IN ∩ OUT = ∅ ∧ IN ∩ OT = ∅ ∧ OT ∩ OUT = ∅(1) These sets of attributes are defined as: •IN: specific attributes from the DS that will be linked to the input variables of the COP. •OUT: attributes that describe the output data of the COP. The values of these attributes are obtained from the COP resolution. •OT: specific attributes form the DS that describe additional information and that can be used to make further queries combining them with output attributes. These attributes are unrelated to the COP since they lack influence in its resolution. The DM enables the separation of the DS and the COP model in such a way that the COP model can be applied to many data sets. However, to relate the DM and attributes of the DS and the variables of the COP, we need to introduce another concept, the DMap. Following definitions determine how the DS attributes and the COPs inputs are mapped through the DM. Definition 6. DMapDS →DM is the relation between the attributes of DS and the IN and OT attributes of the DM, formed of a list of attributes {a i, . . ., a m} ⊆ DS where a subset of attributes are related to IN, {a i, . . ., a m} → {IN}, and another subset of attributes are related to OT, {a h, . . ., a g} → {OT}. DMapDS→DM : DS → {IN, OT}, (2) ∀a i∈ DS : ∃ix∈ IN|a i= ix∧ oh∈ OT|a i= oh, |IN| ≥ 1 (3) Definition 7. DMapDM →COP is the relation between the attributes of the data model DM and the variables of the COP, V. It is described by a list of attributes {ik, . . ., in, outg, . . ., outl} where a subset of attributes from IN are related to the input variables of the COP, {ik, . . ., in} → {V}, and another subset of attributes from OUT are related to the output variables of the COP, {outg, . . ., outl} → {V}. DMapDM→V: {IN, OUT} → V, |V| ≥ 2 (4) ∀ik∈ IN : ∃vj∈ V|ik= vj∧ vh∈ V|ik= vh(5) ∀outg∈ OUT : ∃vi∈ V|outg= vi∧ vj∈ V|outg= vj, (6) ∀(ik, outg)|ik∈ IN, outg∈ OUT : vt∈ V|ik= vt∧ outg= vt(7) Following the running example, the DS in Table 1 is remarked as IN, OT, and OUT according to the DM definition and to represent the DMap. To illustrate how the Data Mapping is carried out, once the transformation has been performed. Fig. 2 represents the mapping between the DS and the COP through the DM. A first DMap determines the relation between the attributes of the DS and the DM. The second DMap relates the DM and the variables of the COPs [46]. Applied to the running example, the attributes of DS (nH, nRM, hA, rmA, pA, hB, rmB, pB, Comp.) are mapped into attributes of the DM as labelled as IN and OT in Table 2. For instance, nH from the DS is mapped as nH IN’s attribute. Similarly, nH IN’s attribute is mapped as hoursLabour variable of the COP. 88 Chapter 3. Discussion and Publications Á. Valencia-Parra, Á.J. Varela-Vaca, L. Parody et al. / Journal of Computational Science 45 (2020) 101180 5 Fig. 2. Data mapping applied to the example. Fig. 3. Process for computing COPDD for distributed data. Regarding the constraints, the COP can be modelled employing a set of fixed constraints such as seen in the example of Table 2. Therefore, each tuple represents a possible assignment of data to the variables of the COP, which can be solved (i.e., OUT) independently. However, in other types of problems, the constraints are built dynamically due to the constrained-relation existing between the values of the attributes of the DM. Thus, each tuple produces a customised COP. The solution of these customised COPs could be influenced by a criterion regarding the IN attributes, for instance, to order the COPs based on descending criteria of pAattribute. This 3.2. Publications 89 6 Á. Valencia-Parra, Á.J. Varela-Vaca, L. Parody et al. / Journal of Computational Science 45 (2020) 101180 Fig. 4. Illustration for independent resolution of COPDDs. criterion establishes the solution of ID tuples: # 3, # 4, # 5, # 1, and # 2. Thus, COP for the tuple # 3 will be solved in the first place, the COP for the tuple # 4 in the second place, and so on. 3.4. Data querying The DSoutput contains every DS tuple combined with the outputs (OUT) obtained after the distributed COPs evaluations. Later analysis of this data should be relevant. Following the running example, to know the maximum profit, the minimum or the average. Classical query operators can be applied to DSoutput, but it is necessary to analyse which types of attributes (IN, OUT and OT) can be involved in each operator. For this reason, we revisit the classical relational algebra [42] employing its unary operators (i.e., selection, projection and aggregation) that can be applied to DSoutput. •Selection (). When the selection operator is applied to a DSoutput, depending on the types of attributes involved in the ϕ, the selection can be applied before and/or after the resolution of the COPDD. In our proposal, only IN and OT attributes can be involved. •Projection (). When the projection operator is applied to a DSoutput, the attributes involved {a1, a2, . . ., an}⊂ {IN, OUT, OT}. For this reason, the projection is applied after the optimisation problem resolutions, since OUT attributes can be included in the projection. •Aggregation (). There are five aggregation functions (f), i.e., SUM, COUNT, AVG, MAX, and MIN. The application of each function returns a number (Integer or Float) and can be applied in IN, OUT and OT attributes. These three operators can be combined and nested (thanks to the closure property of the relational algebra) to query a DSoutput. In following section, we propose to overtake part of the query evaluation to the COPs resolution to reduce the number of optimisation problems to solve, and take the advantages of the distributed and parallel evaluation of the COPs, as it is detailed in the following subsections. 4. Optimising data set query for solving COPs The presented operators can involve every tuple, however, some data analysis done by querying could not entail every tuple, such as ’to obtain the maximum profit when nH is greater than 1, 200’. In this section, we analyse how they can be solved to reduce the computation complexity of obtaining and querying DSoutput, proposing the systematic process shown in Fig. 3 applied before the COPDDs evaluation, since the order in which the operators are applied affects the time consuming of the distributed resolution of the optimisation problems drastically, being crucial how the tasks to solve a query are scheduled [43] in Big Data ecosystems. The application of these steps avoids the resolution of COPs that do not fit the selection operator or those that do not correspond with the attribute to aggregate. The first step is to analyse whether a selection operator is included. It might reduce the input data involved in the COPDDs. For instance, in the running example of the previous section, let be only optimised the products whose rmAhave a value greater than 2, the tuples # 2 and # 5 might not be included in the computation of the COPDDs. If there is a selection operator, the application of the filtering must be developed, as it is carried out in classical data. In the current proposal, only selections over input and other types of attributes can be applied. The second step is related to the aggregation operator. If an aggregation operator is included, how the information is managed depends on the types of attributes and the aggregation functions (i.e., SUM, COUNT, AVG, MAX, and MIN). IN and OT are managed as usual data applying the aggregation operator or relational algebra, meanwhile OUT for MIN or MAX function will be used to improve the optimisation of the COPs to reduce the search space of the variables. Therefore, the Computation of independent COPDD or Computation COPDD with reduction will be carried out depending on whether an aggregation operator over OUT attributes have been used or not. Both types of COPDDs are explained in the following subsections. The third step is related to the projection operator, where a new DS is created as a subset of attributes of the DSoutput. This new DS is the result of the projection operator and the solution to the problem. An example is to obtain the profit but not being necessary to return qAand qB. 4.1. Computation of independent COPDD When operators are applied to OUT attributes, every COPs can be solved individually, being or not in distributed nodes. Thereby, the DS described in the formalisation can be divided into different and distributed nodes. DS can be represented as a set of data sets, ds1, ds2, . . ., dsn, each of them located in an independent node. Each tuple p within a dsi∈ {ds1, ds2, . . ., dsn} represents a problem to be optimised. Each COP depends on the values of the DM for each tuple. It is similar to use each tuple p to instantiate the COP, creating a COPpin which the values are taken from p. The group of COPs generated for each tuple of all DS conforms a workgroup, as we defined in Fig. 4. A particularity of this scenario is that the COPs within the workgroup can be computed independently without the application of any operator. Thus, the workgroup can be seen as a unique task 90 Chapter 3. Discussion and Publications Á. Valencia-Parra, Á.J. Varela-Vaca, L. Parody et al. / Journal of Computational Science 45 (2020) 101180 7 Fig. 5. Illustration for reduction based on aggregation. Fig. 6. Architecture and methodology of FABIOLA. that needs to be computed in a distributed way. As commented, in the running example can be to obtain the average of the profit for all the products, being necessary to compute all the COPs to obtain the profit values before obtaining the average. The calculation of the profit for each COP is unrelated to any other COP. Therefore, the computation of the COPs can be performed independently at any order, because all the COPs must be solved. 4.2. Computation of COPDD with reduction When an aggregation operator is applied to obtain the MAX or MIN value of an OUT attribute, the evaluation of a COPpcan use solutions obtained from the resolution of previous COPs of the same DS (dsi). Thus, each tuple conforms a COPpin which constraints and values are taken directly from p. There are possible values from the same DS that might be shared from one solved COPito another unsolved COPjto improve the search for solutions reducing the search space. Thus, the domain of variables of the (unsolved) COPjmight be reduced to enhance the search space. Following the running example, the objective function could be to determine the maximum profit with the minimum value of units of A (cf., qA). In this case, assuming the solution of the COP, for instance, for the tuple # 1 the values of profit and qA(cf., Table 1) could be used to reduce the domains of the variables profit and numUnitsAin the unsolved COPs since a greater value of numUnitsAand a less value of profit than previously calculated are unacceptable. Despite reduction operations, the aggregation operator (i.e., ) is necessary since the results of all COPs must be combined to determine the maximum profit and the minimum qA. As defined in Fig. 3, the aggregation operation has to be applied in the output variables profit and numUnitsA. In this scenario, problems from the same DS might be related internally to each other by reduction operations but they are unrelated to problems from other DSs. Therefore, the COPs of each DS, dsi, conforms independent workgroups that can be solved without regarding other workgroups. Thus, each workgroup can be seen as a unique task that needs to be computed in a distributed way. In Fig. 5, two workgroups are depicted related to the DS, ds1and dsn, 3.2. Publications 91 14 Á. Valencia-Parra, Á.J. Varela-Vaca, L. Parody et al. / Journal of Computational Science 45 (2020) 101180 Fig. 14. Behaviour of the ERT and number of non-optimal COPs as the timeout increases. Red columns represent the average ERT of five executions, and black lines represent the average number of non-optimal COPs of five executions. 6.3.2. Benchmark II: computation COPDDs with domain reductions All the metrics in the previous section can help to understand the problem in the form of the COPs and the impact of parallelisation in the resolution of COPs. In the Benchmark II, we want to demonstrate other aspects related to the application of operators and their impact in the time of solution. This benchmark pursues the determination of the best profit (i.e., minimum cost) in terms of improvement (cf., maximum) of the estimated cost. First, an aggregation operator is applied to range the customer from low to the high hired tariff. Afterwards, the customers are split into workgroups. The reduction operation is applied since the minimum cost is pursued the previously estimated cost is used to feed the unsolved COPs into the same workgroup. When all the customers have to be processed the minimum of each workgroup have to be combined (cf. MapReduce) in order to determine the global minimum. In terms of the COP resolution, the objective is the reduction of the domain of the variables, by introducing an upper bound to the objective variable. This experiment is similar to the asymptotic analysis performed in Benchmark I, but only parallel executions have been carried Table 5 Trend-line equations for the execution performance per DS. Data set Aggregation and COP resolution COP resolution after reduction COP resolution without reduction DS1 y = 0.54x − 23300 y = 0.28x + 141 y = 0.31x + 64862 DS2 y = 0.57 + 101583 y = 0.14x + 56593 y = 0.24x + 56840 DS3 y = 0.76x + 9763 y = 0.27x + 750 y = 0.26x + 65171 out. Fig. 16 depicts the results of this study, and Table 5 shows the trend-line equations for each DS. As can be seen, the aggregation operator not only outperforms the execution without such operator, but worsens the scalability (cf., note that the slopes are 0.54, 0.57 and 0.76 for DS1, DS2 and DS3, respectively). Nonetheless, by comparing the COP resolution stages of the execution, it can be checked that the reduction of the domain improves both the run-time and the scalability, except for the two first executions of DS2. It might be due to the fact that those points represent small data sets and the improvement is not noticeable by limiting the domain when running in parallel. Regarding the scalability, for DS3 the slope is slightly higher when applying reductions, which might 98 Chapter 3. Discussion and Publications Á. Valencia-Parra, Á.J. Varela-Vaca, L. Parody et al. / Journal of Computational Science 45 (2020) 101180 15 Fig. 15. Memory consumption as the number of COPs scale progressively. Each point represents the average of the total of five executions (Kbytes). be due to the fact that the domain reduction for this data set is not very significant. To sum up, the application of aggregation operators does not improve the execution performance in terms of time, but it might improve the COP resolution stage of the execution depending on the nature of the data. However, this improvement might not be significant since the aggregation stage takes from the 40% to the 50% of the execution time, and also scales worse as the number of COPs increases. Respect to the percentage of optimised COPs, when applying this aggregation operator there is a high amount of COPs which are not optimally solved. Note that reducing the COP domains might lead to unfeasible problems. Hence, the proportion of solved COPs respect to the all possible COPs are 12.11% for DS1; 12.38% for DS2, and 24.9% for DS3. Regarding the memory performance, in this case the program is composed of three stages. The read phase from the data sources and the COP resolution phase are the similar as Benchmark I, but between those stages another phase is included which consists of aggregating the data. This operation implies an extra memory consumption, since the records from the data set must be redistributed among the nodes of the cluster. Fig. 17 shows these results. Since applying aggregation operators require more memory consumption, these outperform the previous results. It can be checked both in the values of memory consumed and in the slope of the trend-lines, which are higher than in the previous case, implying a worsening in the scalability. 7. Related work Big Data faces up new challenges [25,31] in how to carry out optimisation problems with heterogeneous, incomplete, and uncertain data, besides, to immediate responses for some types of questions. The Apache Hadoop project [3] actively supports multiple projects to extend Hadoop’s capabilities and make it easier to use. There are several excellent projects to helping in the creation of development tools as well as for managing Hadoop data flow and processing. Many commercial third-party solutions build on their developed technologies within the Apache Hadoop ecosystem. Spark [49], Pig [32], and Hive [45] are three of the best-known Apache Hadoop projects. All of them are used to create applications to process Hadoop data. While there are a lot of articles and discussions about which is the best one, in practice, many organisations 3.2. Publications 99 16 Á. Valencia-Parra, Á.J. Varela-Vaca, L. Parody et al. / Journal of Computational Science 45 (2020) 101180 Fig. 16. Each point, triangle and square is the Elapsed Real Time average for five executions. Black continuous line represents the overall Elapsed Real Time of the execution including aggregations and COP resolutions; black pointed line represents the Elapsed Real Time of the COP resolutions with domain reduction, and red line represents the Elapsed Real Time of the COP resolution without domain reduction. use various of them since each one is optimised for specific functionality. Although FABIOLA is not a new Big Data solution, it aims to be part of the Hadoop ecosystem. FABIOLA provides the necessary components to drive the solution of COPs with distributed data on a Hadoop-based architecture. In [54], Zhu et al. present various proposals that solve some of the challenges for optimisation problems in distributed information systems. The proposals focus on the optimisation of systems performance and three of them combine optimisation problems in big data environments. First, Zeng et al. [50] emphasised minimising the cost of renting cloud resources for executing MapReduce applications in public clouds, and propose a greedy-based scheduling algorithm to tackle this issue. Secondly, Zhou et al. [53] efficiently distribute data on different devices by considering the asymmetric characteristics among devices and data. To do that, they propose a preference model to quantitatively weight the storage performance imbalance when data are distributed on different devices. Finally, Zhao et al. [52] propose an algorithm to solve the data allocations under multiple constraints in polynomial time. However, these proposals are focused on performance optimisation and not on optimising the results obtained. On the other hand, Chen et al. [8] present a survey where challenges and opportunities of Big Data in data-intensive systems are identified. The authors identified the opportunity to improve decision-making focused on the customer, for instance, by developing customised products. In order to do that, the authors identified the techniques and technologies of Big Data. The authors highlight the need for the application of optimisation techniques to efficiently process a large volume of data within limited run times. Several optimisation techniques are mentioned (cf., Mathematical tools) however they missed out CP as an optimisation technique. CP presents a challenge in the scalability by solving some hard problems. However, CP has been successfully applied in different domains for solving optimisation problems, such as scheduling and planning. Although there exist several CP tools, such as IBM CPLEX Optimisation [23] and ChocoSolver [37] and solutions that create Constraint Problems according to the constraints extracted from databases [5,18,19,17,38], none of them provides an integrated solution for a Big Data solution. Big Data provides to CP a new perspective concerning the size and volume of data, and it is an excellent opportunity to exploit its possibilities to gain efficiency and optimisation in operational processes [34]. Additionally, Big Data tackles new challenges [16] dealing with automation of decision-making that involves several (millions) decision variables 100 Chapter 3. Discussion and Publications Á. Valencia-Parra, Á.J. Varela-Vaca, L. Parody et al. / Journal of Computational Science 45 (2020) 101180 17 Fig. 17. Memory consumption as the number of COPs scale progressively. Each point represents the average of the total of five executions (Kbytes). in optimisation of resource consumption, sustainability services, and finance. Nevertheless, the optimisation problems in CP need more flexibility and adaptability, since the exploration of heterogeneous, enormous and dynamic generation of data requires a quick adaptation of optimisation problem to more holistic solutions. DCOPs have been widely tackled in the literature [15,26,29,48,27,47]. Due to the complexity of the problems (NP-complete, [7,4]) most of the efforts have been done in a theoretical way with the proposition of models, algorithms, and strategies to solve this type of problems. Only ad-hoc applications [29], heuristic approaches [14,13] or simulators [15] have been developed for the community to solve those type of problems. The main challenges in the DCOP solvers are based on overcoming the massive use of memory needed to run the algorithms and to manage the highest number of messages exchanged between nodes. Currently, none approach of DCOPs applied to Big Data has been identified in the literature. To the best of our knowledge, FABIOLA is the first approach that applied Big Data in CP, although various have been the examples where the necessity to optimise problems with Big Data has been detected [51,24]. There are seminal works related to the application of Big Data in CP. Sunny-CP [1,2] is a portfolio of CP-solvers which can exploit the multicore capabilities of the machines to solve CSPs and COPs. However, this approach lacks applicability in the context of Big Data with multiple data sources with a large-scale amount of data. Cao et al. [6] study how to improve the solution of a largescale Integer Linear Programming (ILP) problems employing Big Data architecture. ILP is a discrete approach compared with CP. The authors applied ILP to solve traffic flow management. In [28], the authors propose the application of a CP-based scheduler for a Big Data architecture. On the other hand, there is an initiative to create a new language to adapt CP languages for Big Data applications [40], it is currently a very undeveloped approach with no continued development. Other approaches to Big Data and Optimisation techniques applied to real cases have been studied in [12]. For instance, the maritime logistics problem is modeled as a constraint problem and optimisation techniques have been applied although most of the approaches are focused on machine learning or logic programming techniques. 3.2. Publications 101 18 Á. Valencia-Parra, Á.J. Varela-Vaca, L. Parody et al. / Journal of Computational Science 45 (2020) 101180 8. Conclusions and future work Optimisation problems are found in several real-life scenarios. These optimisation problems become an extraordinary problem when the data involved are in a Big Data environment, which implies a massive quantity of information, that is also distributed and heterogeneous. FABIOLA has been developed to support the definition and resolution of COPs within Big Data scenarios. FABIOLA isolates the resolution of optimisation problems from where the data are and how the optimal outputs are found. Thanks to this isolation, the resolution of optimisation problems in Big Data environments has never been so simple as with FABIOLA. Internally, FABIOLA has been provided with a set of operators to query the optimal information obtained. In order to reduce the computational time and resources needed to solve the optimisation problems, the operators are applied to enrich the capabilities of the resolution of COPs by using the MapReduce operations. Besides, our solution facilitates the COPs modelling through a user interface, FABIOLAUI, that guides the final users through the application. FABIOLA has been evaluated in real scenarios where the necessity of improving the billing of thousands of customers by using COPs is essential. FABIOLA demonstrated to be a scalable and adaptable solution that improves trivial and stand-alone solutions. However, the most important results are the incredible improvement regarding the performance of execution and resource consumption in optimisation problems. The resolution of optimisation problems in Big Data environments has never been as simple to model and fast to solve as with FABIOLA. As future work, it would be interesting to extend FABIOLA to support the adaptation of various constraint solvers in the architecture. On the other hand, FABIOLA can be extended in many directions, for instance, related to the inclusion of new operators to optimise the queries. The possibilities of extends FABIOLA in many directions related to the operators and other scenarios such as distributed optimisation problems are desirable. Authors’ contribution All the authors are responsible for the concept of the paper, the results presented and the writing. All the authors have approved the final content of the manuscript. No potential conflict of interest was reported by the authors. Conflict of interest All the authors are responsible for the concept of the paper, the results presented and the writing. All the authors have approved the final content of the manuscript. No potential conflict of interest was reported by the authors. Acknowledgements This research was partially supported by Ministry of Science and Technology of Spain with projects ECLIPSE (RTI2018-094283- B-C33) and by Junta de Andalucía with METAMORFOSIS projects; the European Regional Development Fund (ERDF/FEDER); and by the University of Seville with VI Plan Propio de Investigación y Transferencia (VI PPIT-US). References [1] R. Amadini, M. Gabbrielli, J. Mauro, A multicore tool for constraint solving, Buenos Aires, Argentina, July 25–31, in: Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, 2015, 2015, pp. 232–238. [2] R. Amadini, M. Gabbrielli, J. Mauro, SUNNY-CP and the minizinc challenge, TPLP 18 (2018) 81–96. [3] Apache, Apache hadoop, 2018, Online. http://wiki.apache.org/hadoop (Accessed 18 May 2018). [4] C. Bessiere, I. Brito, P. Gutierrez, P. Meseguer, Global constraints in distributed constraint satisfaction and optimization, Comput. J. 6 (2013). [5] D. Borrego, R. Eshuis, M.T. Gómez-López, R. M. Gasca, Diagnosing correctness of semantic workflow models, Data Knowl. Eng. 87 (2013) 167–184, http://dx. doi.org/10.1016/j.datak.2013.04.008. [6] Y. Cao, D. Sun, Large-Scale and Big Optimization Based on Hadoop, Springer International Publishing, Cham, 2016, pp. 375–389. [7] P. Cheeseman, B. Kanefsky, W.M. Taylor, Where the really hard problems are, in: Proceedings of the 12th International Joint Conference on Artificial Intelligence - vol. 1, Morgan Kaufmann Publishers Inc, San Francisco, CA, USA, 1991, pp. 331–337 http://dl.acm.org/citation.cfm?id=1631171.1631221. [8] C.P. Chen, C.Y. Zhang, Data-intensive applications, challenges, techniques and technologies: a survey on big data, Inform. Sci. 275 (2014) 314–347, http://dx. doi.org/10.1016/j.ins.2014.01.015. [9] G. Cornuejols, M. Trick, Quantitative Methods for the Management Sciences 45-760. Course Notes, 1998. [10] J. Dean, S. Ghemawat, Mapreduce: simplified data processing on large clusters, Commun. ACM 51 (2008) 107–113, http://dx.doi.org/10.1145/ 1327452.1327492. [11] K.R. Duffy, C. Bordenave, D.J. Leith, Decentralized constraint satisfaction, IEEE/ACM Trans. Netw. 21 (2013) 1298–1308, http://dx.doi.org/10.1109/ TNET.2012.2222923. [12] A. Emrouznejad, Big Data Optimization: Recent Developments and Challenges, Springer, 2016. [13] D. Fernández-Cerero, A. Fernández-Montes, J.A. Ortega, Energy policies for data-center monolithic schedulers, Expert Syst. Appl. 110 (2018) 170–181. [14] D. Fernández-Cerero, Á.J. Varela-Vaca, A. Fernández-Montes, M.T. Gómez-López, J.A. Alvárez-Bermejo, Measuring data-centre workflows complexity through process mining: the Google cluster case, J. Supercomput. (2019), http://dx.doi.org/10.1007/s11227-019-02996-2. [15] F. Fioretto, E. Pontelli, W. Yeoh, Distributed constraint optimization problems and applications: a survey, J. Artif. Intell. Res. 61 (2018) 623–698, http://dx. doi.org/10.1613/jair.5565. [16] E.C. Freuder, B. O’Sullivan, Grand challenges for constraint programming, Constraints 19 (2014) 150–162, http://dx.doi.org/10.1007/s10601-013-9155- 1. [17] M.T. Gómez-López, R. Ceballos, R.M. Gasca, C.D. Valle, Developing a labelled object-relational constraint database architecture for the projection operator, Data Knowl. Eng. 68 (2009) 146–172, http://dx.doi.org/10.1016/j.datak.2008. 09.002. [18] M.T. Gómez-López, R.M. Gasca, Using constraint programming in selection operators for constraint databases, Expert Syst. Appl. 41 (2014) 6773–6785, http://dx.doi.org/10.1016/j.eswa.2014.04.047. [19] M.T. Gómez-López, R.M. Gasca, Object relational constraint databases for GIS, Encyclopedia of GIS (2017) 1449–1457, http://dx.doi.org/10.1007/978-3-319- 17885-1 1598. [20] Red Eléctrica Group, ‘red eléctrica espa na’, 2018, Available at http://www. ree.es/es. [21] P. Gutiérrez Faxas, Distributed Constraint Optimization Related With Soft Arc Consistency, Universidad Autónoma de Barcelona. Departamento Ciencias de la Computación, 2013, Ph.D. thesis. [22] J.M. Hellerstein, J. Heer, S. Kandel, Self-service data preparation: research to practice, IEEE Data Eng. Bull. 41 (2018) 23–34. [23] IBM, Ibm-ilog Cplex Optimization. https://www.ibm.com/products/ilogcplex-optimization-studio (Accessed January 2018). [24] K. Kolomvatsos, C. Anagnostopoulos, S. Hadjiefthymiades, An efficient time optimized scheme for progressive analytics in big data, Big Data Res. 2 (2015) 155–165, http://dx.doi.org/10.1016/j.bdr.2015.02.001. [25] A. Labrinidis, H.V. Jagadish, Challenges and opportunities with big data, Proc. VLDB Endow. 5 (2012) 2032–2033, http://dx.doi.org/10.14778/2367502. 2367572. [26] T. Le, T.C. Son, E. Pontelli, W. Yeoh, Solving Distributed Constraint Optimization Problems Using Logic Programming, 2017 arXiv:1705.03916. [27] A.R. Leite, F. Enembreck, J.P.A. Barthas, Distributed constraint optimization problems: review and perspectives, Expert Syst. Appl. 41 (2014) 5139–5157, http://dx.doi.org/10.1016/j.eswa.2014.02.039. [28] N. Lim, S. Majumdar, P. Ashwood-Smith, A constraint programming based Hadoop scheduler for handling mapreduce jobs with deadlines on clouds, in: Proceedings of the 6th ACM/SPEC International Conference on Performance Engineering, ACM, New York, NY, USA, 2015, pp. 111–122, http://dx.doi.org/ 10.1145/2668930.2688058. [29] D.K. Molzahn, F. Dörfler, H. Sandberg, S.H. Low, S. Chakrabarti, R. Baldick, J. Lavaei, A survey of distributed optimization and control algorithms for electric power systems, IEEE Trans. Smart Grid 8 (2017) 2941–2962. [30] Mongo, Mongodb, 2018, Available at https://www.mongodb.com/. [31] T. Nasser, R. Tariq, Big data challenges, Comput. Eng. Inform. Technol. 4 (2015) 1–10, http://dx.doi.org/10.4172/2324-9307.1000133. [32] C. Olston, B. Reed, A. Silberstein, U. Srivastava, Automatic optimization of parallel dataflow programs, USENIX 2008 Annual Technical Conference, USENIX Association, Berkeley, CA, USA (2008) 267–273 http://dl.acm.org/ citation.cfm?id=1404014.1404035. 102 Chapter 3. Discussion and Publications Á. Valencia-Parra, Á.J. Varela-Vaca, L. Parody et al. / Journal of Computational Science 45 (2020) 101180 19 [33] OMG, The OMG Data-Distribution Service for Real-Time Systems, 2018, Online. http://portals.omg.org/dds/ (Accessed 18 January 2018). [34] B. O’Sullivan, Opportunities and challenges for constraint programming, in: Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, AAAI Press, 2012, pp. 2148–2152 http://dl.acm.org/citation.cfm?id=2900929. 2901033. [35] L. Parody, Á.J. Varela-Vaca, M.T. Gómez-López, R.M. Gasca, FABIOLA: Defining the Components for Constraint Optimization Problems in Big Data environment, Information System Development - Improving Enterprise Communication, [Proceedings of the 26th International Conference on Information Systems Development, ISD 2017, Larnaca, Cyprus] (2017). [36] L. Parody, Á.J. Varela Vaca, M.T. Gómez López, R. M. Gasca, Fabiola: Towards the resolution of constraint optimization problems in big data environment, in: Paspallis, N, Raspopoulos M, Barry C, Lang M, Linger H, C. Schneider (Eds.), Advances in Information Systems Development, Springer International Publishing, Cham, 2018, pp. 113–127. [37] C. Prud’homme, J.G. Fages, X. Lorca, Choco Documentation. TASC – LS2N CNRS UMR 6241, COSLING S.A.S., 2017 http://www.choco-solver.org. [38] P.Z. Revesz, Introduction to Constraint Databases. Texts in Computer Science, Springer, 2002, http://dx.doi.org/10.1007/b97430. [39] F. Rossi, P. van Beek, T. Walsh, Handbook of Constraint Programming, Elsevier, 2006. [40] F. Rossi, V. Saraswat, Constraint Programming Languages for Big Data Applications, 2010 https://github.com/saraswat/C10. [41] R. Sahal, M.H. Khafagy, F.A. Omara, Exploiting coarse-grained reused-based opportunities in big data multi-query optimization, J. Comput. Sci. 26 (2018) 432–452, http://dx.doi.org/10.1016/j.jocs.2017.05.023. [42] S. Sai, S. Esakkirajan, Fundamentals of Relational Database Management Systems, vol. 47, 2007, http://dx.doi.org/10.1007/978-3-540-48399-1. [43] M. Soualhia, F. Khomh, S. Tahar, Task scheduling in big data platforms: a systematic literature review, J. Syst. Softw. 134 (2017) 170–189, http://dx.doi. org/10.1016/j.jss.2017.09.001. [44] J. Stefanowski, K. Krawiec, R. Wrembel, Exploring complex and big data, Int. J. Appl. Math. Comput. Sci. 27 (2017) 669–679. [45] A. Thusoo, J.S. Sarma, N. Jain, Z. Shao, P. Chakka, S. Anthony, H. Liu, P. Wyckoff, R. Murthy, Hive: a warehousing solution over a map-reduce framework, Proc. VLDB Endow. 2 (2009) 1626–1629, http://dx.doi.org/10.14778/1687553. 1687609. [46] A. Valencia-Parra, A. Varela-Vaca, M. Gómez-López, P. Ceravolo, Chamaleon: framework to improve data wrangling with complex data, ICIS (2019) 205–207. [47] T. Yang, X. Yi, J. Wu, Y. Yuan, D. Wu, Z. Meng, Y. Hong, H. Wang, Z. Lin, K.H. Johansson, A survey of distributed optimization, Annu. Rev. Control 47 (2019) 278–305, http://dx.doi.org/10.1016/j.arcontrol.2019.05.006. [48] W. Yeoh, A. Felner, S. Koenig, Bnb-Adopt: An Asynchronous Branch-and-Bound DCOP Algorithm, 2014 arXiv:1401.3490. [49] M. Zaharia, R.S. Xin, P. Wendell, T. Das, M. Armbrust, A. Dave, X. Meng, J. Rosen, S. Venkataraman, M.J. Franklin, A. Ghodsi, J. Gonzalez, S. Shenker, I. Stoica, Apache spark: a unified engine for big data processing, Commun. ACM 59 (2016) 56–65, http://dx.doi.org/10.1145/2934664. [50] X. Zeng, S.K. Garg, Z. Wen, P. Strazdins, A.Y. Zomaya, R. Ranjan, Cost efficient scheduling of mapreduce applications on public clouds, J. Comput. Sci. 26 (2018) 375–388, http://dx.doi.org/10.1016/j.jocs.2017.07.017. [51] Z. Zhang, K.R. Choo, B.B. Gupta, The convergence of new computing paradigms and big data analytics methodologies for online social networks, J. Comput. Science 26 (2018) 453–455, http://dx.doi.org/10.1016/j.jocs.2018.04.007. [52] H. Zhao, M. Qiu, M. Chen, K. Gai, Cost-aware optimal data allocations for multiple dimensional heterogeneous memories using dynamic programming in big data, J. Comput. Sci. 26 (2018) 402–408, http://dx.doi.org/10.1016/j. jocs.2016.06.002. [53] W. Zhou, D. Feng, Z. Tan, Y. Zheng, Improving big data storage performance in hybrid environment, J. Comput. Sci. 26 (2018) 409–418, http://dx.doi.org/10. 1016/j.jocs.2017.01.003. [54] X. Zhu, L.T. Yang, H. Jiang, P. Thulasiraman, B.D. Martino, Optimization in distributed information systems, J. Comput. Sci. 26 (2018) 305–306, http://dx. doi.org/10.1016/j.jocs.2018.04.020. Álvaro Valencia-Parra is a computer science Ph.D. student at the University of Seville. His research areas include the improvement of data transformation and data quality fields in Big Data paradigms. His goal is to improve the way in which final users deal with data preparation and specific scenarios in which configuring a Big Data pipeline might be tricky. For this purpose, he is working in the improvement of the data transformation processes by designing Domain-Specific Languages for very specific purposes, user interfaces, and semi-automatic approaches in order to assist users in these tasks. Angel J. Varela-Vaca received the B.S. degree in Computer Engineering at the University of Seville (Spain) and graduated in July 2008. M.Sc. on Software Engineering and Technology (2009) and obtained his PhD with honors at the University of Seville (2013). Angel is currently working as Assistant Professor at Languages and System Informatics Department at the Universidad Sevilla and belongs to the Idea Research Group. Angel has and leaded various private projects and participated in several public research projects and he has published several impact papers. He was nominated as a member of Program Committees such as ISD 2016, BPM Workshops 2017, SIMPDA 2018. He has been reviewer for international journals such as Journal of Supercomputing, International Journal of Management Science and Engineering Management Multimedia Tools and Applications, Human-Centric Computational and Information Sciences, Mathematical Methods in Applied Sciences among others. Luisa Parody studied computer engineering (including a minor in systems engineering) at the Universidad de Sevilla (Spain) and graduated with honours in July 2009. She then earned an M.Sc. degree in software engineering and technology (2010) and obtained her international PhD with honours at the Universidad Sevilla (2014). Since 2018, she has been working as an associate professor in Dto. Método Cuantitativos at the Universidad Loyola. She belongs to the IDEA Research Group and has participated in several private and public research projects and has published several high-impact papers. María Teresa Gómez-López is a Lecturer at the University of Seville and the head of the IDEA Research Group. Her research areas include Business Processes and Data management, and the things that disturb his thoughts are how to improve the business process models including better decisions and enriching the model with Data Perspectives. She has led several private and public research projects and has published several impact papers, among others in Information and Software Technology, Information Systems, Information & Software Technology, or Data & Knowledge Engineering. She was nominated as a member of Program Committees, such as ER 2018, BPM 2017, ISD 2017, ICIQ 2016, PHM 2016, IAwDQ 2013 or CLEIS 2012. She has been reviewing for international journals, such as International Journal of Data and Information Quality, Journal of Systems and Software, Artificial Intelligence in Medicine; Business & Information Systems Engineering Journal or Information Science. She has given keynotes or was invited speaker at the IV Workshop on Data & Artifact Centric BPM in Innsbruck, 5th International Workshop on Decision Mining & Modeling for Business Processes BPM in Barcelona, the X National Conference of BPM in Madrid, in the 28th IBIMA Conference, and in the biannual International Summer School on Fault Diagnosis of Complex Systems. 3.2. Publications 103 104 Chapter 3. Discussion and Publications 3.2.4 Empowering Conformance Checking using Big Data through horizontal decomposition Published in the Information Systems journal (Vol. 99, p.101731). Elsevier BV. •Authors: Álvaro Valencia-Parra, Ángel Jesús, María Teresa Gómez-López, Josep Carmona, Robin Bergenthum. •DOI: 10.1016/j.is.2021.101731. •Rating: Q3 (JCR’20 2.309). Information Systems 99 (2021) 101731 Contents lists available at ScienceDirect Information Systems journal homepage: www.elsevier.com/locate/is Empowering conformance checking using Big Data through horizontal decomposition Álvaro Valencia-Parraa, Ángel Jesús Varela-Vacaa,∗, María Teresa Gómez-López a, Josep Carmonab, Robin Bergenthumc aDepartamento de Lenguajes y Sistemas Informáticos, Universidad de Sevilla, Spain1 bDepartment of Computer Science, Universitat Politècnica de Catalunya, Spain2 cFakultät für Mathematik und Informatik, FernUniversität in Hagen, Germany3 article info Article history: Received 1 March 2020 Received in revised form 17 November 2020 Accepted 24 January 2021 Available online 18 February 2021 Recommended by Gottfried Vossen Keywords: Conformance checking Decompositional techniques Big Data MapReduce abstract Conformance checking unleashes the full power of process mining: techniques from this discipline enable the analysis of the quality of a process model through the discovery of event data, the identification of potential deviations, and the projection of real traces onto process models. In this way, the insights gained from the available event data can be transferred to a richer conceptual level, amenable for human interpretation. Unfortunately, most of the aforementioned functionalities are grounded in an extremely difficult fundamental problem: given an observed trace and a process model, find the model trace that most closely resembles to the trace observed. This paper presents an architecture that supports the creation and distribution of alignment subproblems based on an innovative horizontal acyclic model decomposition, disengaged from the conformance checking algorithm applied for their solution. This is supported by a Big Data infrastructure that facilitates the customised distribution of a gross amount of data. Experiments are provided that testify to the enormous potential of the architecture proposed, thereby opening the door to further research in several directions. ©2021 Elsevier Ltd. All rights reserved. 1. Introduction By means of conceptual models, organisations tend to define complex business processes that must be followed to achieve their objectives [1]. Sometimes the corresponding processes are distributed across various systems, in which the majority of cases include human tasks, thereby inadvertently enabling the occurrence of unexpected deviations with respect to the (normative) process model. This is aggravated by the appearance of increasingly complex processes, where the observations are provided by heterogeneous sources, such as Internet-of-Things (IoT) devices involved in Cyber–physical Systems [2]. Conformance checking [3] techniques provide mechanisms to relate modelled and observed behaviour, so that the deviations ∗Corresponding author. E-mail addresses: [email protected] (Á. Valencia-Parra), [email protected] (Á.J. Varela-Vaca), [email protected] (M.T. Gómez-López), [email protected] (J. Carmona), [email protected] (R. Bergenthum). 1http://www.idea.us.es. 2https://www.cs.upc.edu. 3https://www.fernuni-hagen.de. between the footprints left by process executions and the process models that formalise the expected behaviour can be revealed. One of the major challenges in conformance checking is the alignment problem: given an observed trace σ, compute an end- to-end model run that more closely resembles σ. Computing alignments is an extremely difficult problem, with a complexity exponential in the size of the model or the trace [4]. Intuitively, computing an alignment requires a search through the state space of the model which, in certain cases implies an extensive exploration when the process model is large and/or highly concurrent. In order to face the challenge of computing alignments, the conformance checking community has proposed widely differing alternatives. Among these, we highlight decompositional techniques, which break the alignment problem into segments, whose solutions can be composed to reconstruct the final alignment [5– 8]. All these decompositional approaches feature a common strategy which involves decomposing the problem by means of vertical cuts of the process model, and then projecting the traces in the log accordingly in order to derive subtraces that only contain events of the alphabet corresponding to each model fragment. Although, in very particular cases (e.g., well-structured process models), the aforementioned decompositional approaches represent a significant alleviation of the alignment problem, they https://doi.org/10.1016/j.is.2021.101731 0306-4379/©2021 Elsevier Ltd. All rights reserved. 3.2. Publications 105 Á. Valencia-Parra, Á.J. Varela-Vaca, M.T. Gómez-López et al. Information Systems 99 (2021) 101731 Fig. 1. Functional description of the Big Data architecture to compute alignments. rely on very stringent conditions (e.g., model fragments should agree on the alphabet at the frontiers), and provide weak guarantees (e.g., necessary conditions for deriving an alignment), which hamper them from being applied in general. In this paper, we step back from the decompositional approach, and focus on working at a more abstract, architectural level. As earlier mentioned, normally the complexity of computing the alignment problem has been addressed by means of the horizontal and vertical decomposition techniques [9]. We propose a Big Data infrastructure focused on a specific horizontal decomposition, which involves the unfolding of process models, and employing the MapReduce paradigm [10] for the decomposition and aggregation. At first sight, our functional strategy (depicted in Fig. 1) will not bring any new ideas to the landscape of decompositional techniques: the process model is decomposed into a set of partial models, and traces in the log are projected into subtraces. These two types of elements are then distributed and their partial solutions are composed to aggregate a final alignment. This distribution of the problem may facilitate the simplification of the problem, by splitting the conformance analysis into partial models (with smaller search spaces) and subtraces across several nodes (Map), and combining the partial alignments4obtained from different algorithms in the nodes (Reduce). The general idea of applying MapReduce for conformance checking is not new, as is analysed in the related work section. However, the Big Data [11] framework proposed in this paper is innovative for the following reasons: •A new decomposition is proposed, which differs from the aforementioned approaches in one important feature: instead of a vertical cut, it is based on horizontal, end-to-end cuts that can be obtained by what we call acyclic cover, which originates from a partial order representation of the initial process model. The horizontal decomposition of the model limits the search space dividing the model into its possible execution models, and analysing the alignment with every trace. However, in the vertical decomposition, both traces and the model are fragmented, thereby reducing the search space for each part of the model and each trace fragment. •The framework enables the construction, distribution, and parallelisation of the computing alignment between different nodes in a Big Data environment to be tuned in 4Partial alignment means the computation of the alignment for a partial model and a subtrace. accordance with the features of the problem and the available requirements. Moreover, the application of heuristics is proposed to optimise the resolution of the subproblems. •It enables us to choose and customise the conformance checking algorithm, by making it possible to compute the alignment with different techniques. In this case, we have used the A* algorithm as a classic solution, and the Constraint Programming Paradigm [12] as a new solution, in order to show how different types of alignment algorithms can be applied in the distributed paradigm. •The development of a practicable infrastructure based on Big Data represents a leap forward in the resolution of conformance checking problems of a more complex nature, and reduces the resource limitations of the current solutions evaluated locally. The paper is organised as follows: Section 2analyses the related work. Section 3includes the necessary foundations to understand the state of the art and the proposal. Section 4deter- mines how the use of Big Data techniques provides mechanisms for the partitioning and distribution of the computation of the conformance checking analysis. Section 5describes how the A* algorithm and Constraint Programming can be applied to traces that represent the acyclic horizontal partial models. Section 6 depicts the experiments carried out to evaluate our proposal, and finally, Section 7presents the conclusions. 2. Related work The seminal work in [4] proposed the notion of alignment and developed a technique based on A∗to compute optimal alignments for a particular class of process models. Improvements of this approach have been presented recently in various papers [13,14]. These approaches represent the state-of-the-art technique for computing alignments, and can be adapted (at the expense of a significant increase in the memory footprint) to provide all optimal alignments. Alternatives to A∗have appeared in recent years: in the approach presented in [15], the alignment problem is mapped as an instance of automated planning. Automata-based techniques have also appeared [16,17]. The techniques in [16] (and recently extended in [18]) rely on state-space exploration and determination of the automata corresponding to both the event log and the process model, whilst the technique in [17] is based on computing several subsets of activities and projecting the alignment instances accordingly. In spite of the significant progress made, the aforementioned techniques still have problems in dealing with large inputs. The work in [19] presents the notion of approximate alignment to alleviate computational demands by proposing a recursive paradigm on the basis of the structural theory of Petri nets. In spite of its resource efficiency, the solution is not guaranteed to be executable. Alternatively, the technique in [20] presents a framework to reduce a process model and the event log accordingly, with the goal of alleviating the computation of alignments. The obtained alignment, called macro-alignment since some of the positions are high-level elements, is expanded based on the information gathered during the initial reduction. Techniques using a local search have also recently been proposed [21]. Although the approximate techniques can provide solutions where exact/optimal techniques fail, they only provide certain guarantees for very restricted classes of models. Against this background, the process mining community has focused on dividing and conquering the problem of computing alignments as a valid alternative to this problem, with the aim of alleviating its complexity without degrading the quality of the solutions found. Our focus now turns to decompositional 2 106 Chapter 3. Discussion and Publications Á. Valencia-Parra, Á.J. Varela-Vaca, M.T. Gómez-López et al. Information Systems 99 (2021) 101731 approaches towards the computation of alignments, which are more closely related to the research of this paper. Decompositional techniques have been presented [5–7] which, instead of computing optimal alignments, focus on the crucial problem of whether a given trace fits a process model. These techniques vertically decompose the process model into pieces that satisfy certain conditions. Therefore, only valid decompositions [5], which satisfy restrictive conditions on the labels and connections forming a decomposition, guarantee the derivation of a real alignment. The notion of recomposition has since been proposed on top of decompositional techniques, in order to obtain optimal alignments whenever possible by modifying the decomposition (typically by merging sets) when the required conditions are not met [8]. In contrast to the aforementioned vertical decomposition techniques, our methodology does not require this last modification of partial solutions, and therefore can provide a fast alternative to these methods at the expense of losing the guarantee of optimality. There has also been related work on the use of partial order representations of process models for the computation of alignments. In [22], unfoldings are employed to capture all possible transition relations of a model so that they can be used for online conformance checking. In contrast, unfoldings were used recently in a series of papers [23,24] to significantly accelerate the computation of alignments. We believe that these approaches, especially the latter two, can easily be integrated into our framework. The work of [18] can also be considered a decompositional approach since it proposes decomposing the model into sequential elements (S-components) so that the state-space explosion of having concurrent activities is significantly alleviated. This work is compatible with the framework suggested in this paper since the model restrictions assumed in [18] are satisfied by the partial models arising from our horizontal decomposition. Finally, the MapReduce distributed programming model has previously been considered for process mining. For instance, Evermann applies it to process discovery [25], whilst [26] applies it for monitoring declarative business processes. 3. Foundations We denote ⊥as the empty set. Let Abe a set of elements, and we denote A∗as the set of all sequences over elements of A. Let a,b∈(A∪{⊥})∗be two sequences. We denote a⊥ as the sequence a, but omit all elements ⊥from a. We write aˆ=bif a⊥ =b⊥ holds. 3.1. Process models In this paper, we describe process models and partial models by means of labelled Petri nets. Definition 1 (Labelled Petri Net).A labelled Petri net is a tuple (P,T,F,Σ, ℓ) where Pand Tare finite disjoint sets of places and transitions, respectively, F:(P×T)∪(T×P)→ {0,1}is the flow-relation, Σis the alphabet, and ℓ:T→Σ∪ {⊥} is the labelling function. Fig. 2 depicts a labelled Petri net. Places are represented by circles and transitions by rectangles. Every transition has a unique name and a label on top. Places and transitions are connected in accordance with the flow-relation. In Petri nets, there is the so-called firing rule. Transitions of a Petri net can be fired, thereby changing the state of the net. Fig. 2. A labelled Petri net. Definition 2 (Firing Rule).Let N=(P,T,F,Σ, ℓ) be a labelled Petri net. A function m:P→N0is a marking of N. We define, •t:P→ {0,1}as •t(p):= F(p,t), and t• : P→ {0,1}as t•(p):= F(t,p). A transition t∈Tis enabled at marking mif m≥ •tholds. If transition tis enabled, then transition tcan be fired. In this case, we write m[t⟩. Firing tchanges the marking m to m′:= m− •t+t•. In this case, we write m[t⟩m′. We depict a marking by putting black dots, called tokens, in the places of the marking. For example, Fig. 2 depicts the initial state of the labelled Petri net. The initial marking only contains place ionce. In this marking, only transition t1, labelled as A, is enabled. Firing t1leads to the marking where idoes not carry a token, and both places in the post-set of t1each carry a token. Starting at the initial marking, sequentially enabled sequences of transitions are words of the language of the Petri net. The related traces of labels are the so-called trace-language. Definition 3 (Language of a Petri Net).Let N=(P,T,F,Σ, ℓ) be a labelled Petri net. A marked Petri net is a tuple (N,m0,mf) where m0is the initial marking and mfis the final marking. A sequence ⟨t1,...,tn⟩∈T∗is a firing sequence. If there is a sequence of markings ⟨m1,...,mn+1⟩such that m1[t1⟩m2,m2[t2⟩m3,. . ., mn[tn⟩mn+1holds, we can write m1[t1,...,tn⟩mn+1. L(N):= {⟨t1,...,tn⟩∈T∗|m0[t1,...,tn⟩mf} T(N):= {σ∈Σ∗|⟨t1,...,tn⟩∈L(N)∧σˆ=⟨ℓ(t1), . . . , ℓ(tn)⟩} L(N) is the language of N;T(N) is the trace-language of N. In Fig. 2, if we assume the final marking where only place f carries one token, for example ⟨t1,t2,t3,t6,t7⟩and ⟨t1,t2,t3,t5, t4,t2,t3,t7⟩are words of the language, and ⟨A,B,C,F,G⟩and ⟨A,B,C,E,D,B,C,G⟩are the related traces. 3.2. Conformance checking Event logs record the behaviour observed from the execution of a business process. Definition 4 (Trace, Event Log).Let Σbe an alphabet. A sequence σ∈Σ∗is a trace. A multi-set of traces L:Σ∗→N0is an event log. The classic notion of aligning an event log and a process model was introduced by [4]. An alignment maps a trace of an event log to a firing sequence of the model. An alignment replays the trace and the firing sequence simultaneously, where either the trace, the firing sequence, or both move. Trace and sequence are allowed to move synchronously only if the label of the transition matches the event. We consider the Petri net depicted in Fig. 2 with initial state i and final state f. By aligning the Petri net to the trace ⟨A,A,B,C, 3 3.2. Publications 107 Á. Valencia-Parra, Á.J. Varela-Vaca, M.T. Gómez-López et al. Information Systems 99 (2021) 101731 or-splits. In fact, this helps reduce the complexity of the COP regarding the number of restrictions and the number of variables and the domain of the variables. 5.2.1. Constraint and optimisation problems in a nutshell Constraint Programming is a paradigm that permits the declarative description of the constraints that determine a problem [30, 31]. Constraint Programming brings together a set of algorithms to determine the solutions of a problem described. Definition 10 (The Constraint Satisfaction Problem).(CSP) is defined by a 3-tuple ⟨X,D,C⟩, where X={x1,. . .,xn} is a finite set of variables, D={d(x1), . . .,d(xn)} is a set of domains of the values of the variables, and C={C1,. . .,Cm} is a set of constraints. Each constraint Cidetermines relations Rbetween a subset of the variables V={xi,xj,. . .,xl}. A constraint Ci=(Vi,Ri) simultaneously specifies the possible values of the variables in Vthat satisfy R. Let Vk={xk1,. . .,xkl} be a subset of X, and an l-tuple (xk1,. . .,xkl) from d(xk1), . . .,d(xkl) can therefore be called an instantiation of the variables in Vk. An instantiation is a solution iff it satisfies the constraints C. The CSP solvers enable one tuple of instantiation of one, multiple, or all these values to be sought in accordance with the requirement of the problem. An example of its applicability in the alignment context is given by its representation of the order relation existing in the models and the traces, as found in Fig. 6. By using a set of variables to represent the order of the events, and by satisfying the relative constraints of the activities that appear in the partial model, the alignment can be encoded in the following CSP. // Variables positionA,positionB,positionC. . . in the domain {0..trace.length-1} // Constraints of the log trace positionA== 0 positionC== 1 positionB== 2 positionAD == 3 . . . positionAZ == 14 // Constraints of the partial model positionA<positionC positionC<positionAC positionC<positionAF positionAC <positionAD . . . If the model and the event cannot be aligned, this CSP will not be satisfied. However, no more feedback regarding the level of misalignment is provided by the resolution of the CSP. In this case, a Constraint Optimisation Problem (COP) is able to ascertain the minimal distance between the partial model and the log observed since a COP is a CSP that includes an optimisation function. Only the solution of the CSP that satisfies the optimal function can be the solution of the COP. Constraint Optimisation Problems (COPs) have already been employed to detect the alignment between the expected and the observed behaviour in model-based diagnosis [32,33], specifically when the behaviour is described by means of business process models [34–36]. These studies used the concept of reified constraints as a mechanism to assign a Boolean value to the constraints included in the model [34], whereby a constraint that cannot be satisfied during the CSP resolution can be relaxed. Since the idea is to determine the minimal distance between the model and the log, these relaxed constraints must be the minimum number, defined as the objective of the function to be optimised. Following the previous example, the COP below is created where the Ref variables relate to the reified constraints. // Variables RefA,RefC,RefC. . . in the domain {0..1} positionA,positionB,positionC. . . in the domain {0..trace.lenght-1} // Constraints of trace positionA== 0 positionC== 1 positionB== 2 positionAD == 3 . . . positionA== 14 // Constraints of the model RefA∧RefCH⇒ (positionA<positionC) RefC∧RefAC H⇒ (positionC<positionAC ) RefC∧RefAF H⇒ (positionC<positionAF ) RefAC ∧RefAD H⇒ (positionAC <positionAD) . . . maximize(RefA+RefC+. . . +RefAF ) Although the idea of the COP modelling follows the previous COP, in the following subsection, we approach the definition included in Section 3in relation with a COP to determine the alignment between a partial model and a log trace. 5.2.2. Constraint optimisation problem for solving an alignment subproblem Our proposal builds the COP from the perspective of the placement of the events in a positional order that satisfies both the log trace order and that of the partial model. However if this is not possible, then a number of the constraints are ignored from the COP firing reified constraints. The structure of the COP is as shown in Fig. 13. As defined above, a COP is composed of a set of variables, a set of constraints, and an objective function. It is important to take into account the possibility that an event can appear more than once in a log trace derived, for example, from an unfolding process. In this case, a relabelling of the events is necessary to differentiate the variables that represent one or another , although some constraints must be included to express that they can represent the same transition. In detail, a COP is formed of: •Variables for the Log Events: for each event in the log trace, two variables are created: –Position (pos): Integer variable with a domain between 0 and the number of events, that is, all the different locations of the events. This domain represents all the possible positions with respect to the partial model. In the running example, all the variables receive a domain from 0 to 8 since 9 is the total number of events, although the event Eis not in the partial model and the transition Hin the partial model is not included in the events. –Deviation (dev): Boolean variable which represents the correct or incorrect order of the event according to the model. Thus, semantically the false value indicates that the event is aligned with the partial model, and the true value indicates otherwise. These variables are the key to obtain the log and model moves in the alignment calculation as will be seen in the objective function. These variables are also used to enable/disable the firing of the reified constraints of the COP. •Constraints to enforce Log Traces: According to the logrelation of the events in the trace, the events are enforced to take those positions. Thus, a set of reified constraints are built to represent conditions of the position of the events 10 114 Chapter 3. Discussion and Publications Á. Valencia-Parra, Á.J. Varela-Vaca, M.T. Gómez-López et al. Information Systems 99 (2021) 101731 Fig. 13. COP for the example of Fig. 6. with respect to the log trace. For instance, event Aoccurs first: ¬A.devH⇒ A.pos == 0 (1) In the case where the event does not occur in the partial model, it is a deviation, and therefore a constraint is included to force the establishment of a true value for the dev variable of the event, as occurs with event E: E.dev== true (2) In the case of the repeated events, the COP must evaluate all the possibilities of occurrence, as in the case of B1 and B2. The reified constraint must consider the two possibilities, as follows: ¬B1.devH⇒ B1.pos == 1∨B1.pos == 5 (3) •Constraints to Enforce Partial Model Run: These reified constraints represent conditions of the position (pos) of the events with regard to the partial model. The reified constraint describes whether an event can be aligned according to the partial model. According to the flow-relation of the partial model, we build reified constraints to represent the related ‘later than’-relations between the occurrences of transitions. It should be taken into account that, in the partial models used in our proposal, the XORs are eliminated, and every transition of the model participates in any correct event log. Therefore, the next constraint is an example of this type of reified constraint: ¬A.dev∧ ¬B1.devH⇒ A.pos <B1.pos (4) The reified constraint means that if events Aand B1 are aligned with the model, then the value assigned to pos of event Ahas to be lower than the values of pos of event B1. In the case of repeated events (e.g., B1 and B2), extra constraints have to be included in order to prevent their occurrence at the same position: B1.pos = B2.pos (5) When a transition in the model is not supported by the execution of an event (taking into account that in the partial model supported by the proposal every transition must be involved in a correct trace since only and-branches are included), constraints related to this transition are not added, although a misalignment will be included (a model move). See below for a description of how this is computed. •Optimisation function: The objective function strives to find a solution that minimises the number of deviations. The Boolean variables are considered as Integer, that is, false is the 0 value and true is the 1 value. As shown in Fig. 13, the objective function is the minimisation of the sum of all deviation variables of our problem. Thus, finding a solution (an assignment) where all the dev variables are fixed as false, means that every event of the log trace is aligned with the partial model. In the case where any dev variable is fixed to true, the alignment will be, at least, the number of dev true values. This COP enables the possible deviations between the partial models and the events to be detected: •Log moves: The log moves are determined by consulting the false values fixed in the deviation (dev). If the dev variable of an event reach a false value, then this event does not produce a log move. When an event does not occur in the partial model, this situation is a log move, and therefore this situation is controlled by forcing the true value in the dev variable of the event. •Model moves: Model moves occur when there exists a transition in the partial model that does not occur in the log trace. This situation is easy to identify since a partial model is conflict-free (see Definition 7), meaning that all the transitions must occur in a partial model run. Hence, this situation is penalised as a model move by adding one to the alignment cost function. Subsequent to the COP resolution, the log and model moves are known, and therefore the alignment cost function can be determined as follows: alignment = i ∑ ei∈Tr ei.dev    log moves + i ∑ ei∈Pm∧ei/∈Tr 1    model moves (6) 11 3.2. Publications 115 Á. Valencia-Parra, Á.J. Varela-Vaca, M.T. Gómez-López et al. Information Systems 99 (2021) 101731 For the example, the COP reached two optimal solutions where the alignment is equal to 3: one value for the E.dev =true, and another value due to the C1.dev =true (D.dev =true in the other equivalent solution) since it is impossible to locate it according to the log trace, and another value because Hdoes not occur in the log trace. The inclusion of the time limit is crucial in Constraint Programming since the solvers return partial solutions during its execution. If the solver is stopped by the time limit, then we have, at least, the best option found up to that moment, although it may not be the global optimal since the search space has not been completely solved. 6. Experiments and evaluation In order to evaluate our proposal, we have performed various tests to compare the distributed approach proposed in this paper with the classic standalone A* algorithm for computing alignments. Regarding the distributed approach, two algorithms are employed for encoding alignments: the A* algorithm and the COP-based approach presented in this paper (see Section 5). This section is structured as follows: •Design of the architecture and the technology stack to support our framework (see Section 6.1). •Selection of a set of representative datasets (see Section 6.2) that includes examples which work better with the distributed approach proposed in this paper, and examples which work better with the classic standalone approach. The configuration of the parameters is also studied. •Analysis of the approach proposed in this paper, by solving the alignment subproblems derived from the previously selected datasets. The distributed approach is compared to the classic standalone approach (see Section 6.3). For the evaluation and comparison, the performance is considered in terms of the Elapsed Real Time (ERT)7related to the computation of the alignments. 6.1. Architecture We propose the use of a three-layer architecture, as shown in Fig. 14. Additionally, we include information regarding the technological stack that has been employed to instantiate this architecture and to perform the experiments. •Storage Layer. The role of this layer is to store the log and process model so that these can be accessed by the nodes that comprise the system. In our particular implementation, it is based on Hadoop HDFS,8which is a distributed storage system. •Persistence Layer. This layer is intended to store the results of the alignments. Our implementation relies on the NoSQL database MongoDB.9 •Computing layer. It is intended to perform the computing operations related to the generation and distribution of partitions and computing alignments. Our implementation is based on Apache Spark,10 which is a distributed computing framework that enables users to implement applications for the distribution of tasks and Big Data processing. 7The Elapsed Real Time (ERT) is the time from the start of the execution of a program to its completion. 8HDFS: https://hadoop.apache.org/. 9MongoDB: https://www.mongodb.com/. 10 Apache Spark: https://spark.apache.org/. The mechanism for the generation and distribution of partitions explained in Section 4.2 has been implemented in Apache Spark. As mentioned earlier, we have integrated the PM4Py11 platform for the computation of alignments using the A* algorithm. On the other hand, the COPs have been implemented with ILOG CPLEX12 although other solvers can be applied. Regarding the architecture of the Apache Spark cluster (i.e., the architecture of the Computing layer), it is composed of five nodes. Each node is configured with 16GB of RAM and 4 CPUs. This cluster is composed of three types of nodes: •Cluster manager. This is responsible for monitoring and assigning resources among the nodes of the cluster. There is one node entirely dedicated to this task. •Driver program. This node is responsible for distributing the tasks among the Executor nodes. Regarding our implementation, it will schedule the partitioning process by assigning the partitions and their related tasks to the executor nodes. In our case, the driver program is configured to use 8 GB of RAM and 1 CPU by default, and it is run on one of the five nodes of the cluster. •Executor nodes. These nodes execute the tasks assigned by the driver program. They receive the partitions and execute their corresponding tasks. We configured each executor node with 8 GB of RAM and 4 CPUs by default. Each of the four nodes of the cluster hosts one executor. Both the source code with the implementation of the framework and the datasets used for the experimentation are available at http://www.idea.us.es/confcheckingbigdata/. 6.2. Setting experiments Five benchmark datasets have been used for the experiments. These are composed of a set of files in XES format as event logs and a set of partial models in Labelled partial order (LPO) format [37]. For a better understanding, the LPO format is a simplification but remains compatible with the PNML format. An LPO represents a run of a place/transition Petri net if it is enabled w.r.t the net. The events of the LPO modelling transition occurrences can fire in the net in accordance with the concurrency and dependency relations given by the LPO. The event logs and Petri nets employed to illustrate how our proposal works with problems of different sizes are extracted from [20,38,39], whereas the partial models are obtained from the unfolding of Petri nets. Table 1 summarises the dimensions of the datasets employed for this evaluation in terms of: (1) the event logs (number of cases, events, variants, and size); (2) Petri net (number of places, transitions, arcs, and the Cardoso metric (CFC) [40]); and (3) partial models (number of unfolded partial models, number of problems to compute to solve the alignment problem and size, regarding the number of problems to tackle). Once traces and partial models are combined, the total number of subproblems (see Num. of Problems of Table 1) is derived from the application of the Cartesian product and their required theoretical storage space. The objective of this table involves obtaining an estimate of the complexity involved in the solution of all the problems of each dataset, especially M5 and prGm6, in which more than five and forty million subproblems must be solved, respectively. Approximately, the approach must manage a total of 96 GB and 2.5 TB of data volume, as appear for M5 and prGm6 in the table. The distribution of the alignment computation 11 PM4Py: https://pm4py.fit.fraunhofer.de/. 12 IBM-ILOG CPLEX: https://www.ibm.com/products/ilog-cplex-optimization- studio. 12 116 Chapter 3. Discussion and Publications Á. Valencia-Parra, Á.J. Varela-Vaca, M.T. Gómez-López et al. Information Systems 99 (2021) 101731 Fig. 14. Cluster architecture. can imply the transfer of a vast amount of data between the executors, thereby producing a negative impact on the performance. For this reason, the access to traces and partial models has been centralised and they are each accessed by a unique identifier. The main aspects that might influence the performance of our approach include the setup configuration in terms of the number of partitions for the set of traces (n), and the number of partitions for a set of partial models (m). It is crucial to ascertain out the best setup in terms of the timeout, n, and m, albeit dependent on the type of problem. These parameters are configured as explained below: •Grouping the subproblems from the same trace in a partition helps to reduce the number of subproblems to solve. The approach is optimised in order to prevent the execution of subproblems for two reasons: (a) a subproblem is executed iff its estimation of the alignment is lower than the best alignment value obtained for the subproblem related to the same trace in the same partition; and (b) the subproblems are sorted by estimation in ascending order. In consequence, when any subproblem is not executed for the aforementioned reason, the execution of the remaining subproblems related to the same trace are skipped since the estimation will always be worse. For this reason, a good setup should concentrate all the problems related to the same trace in the fewest number of partitions as possible, but without over-reducing the parallelisation. By setting n equal to the number of cases in the log, we can assure that each partition will contain subproblems related to the same trace. Hence, this parameter is set to: 500 for M2, M5 and M8; 1265 for CCC20d, and 1200 for prGm6. •Balancing the number of partitions of alignment subproblems. Some alignment subproblems are too complex and may lead to the formation of bottlenecks in the resolution of the whole alignment problem. A proper partitioning might help in preventing such bottlenecks. For instance, if there is a low number of partitions, it is possible to take advantage of the factor explained above (i.e., avoiding mixing subproblems generated from different traces). The drawback of a low number of partitions is that there could be one or several partitions with a group of complex subproblems which would disproportionately increase the workload of certain executors, while simultaneously leaving other executors idle. The other extreme involves having a high number of partitions. In such a case, the number of subproblems to be solved would increase, since it would not take advantage of the factor previously explained. In this situation, we assume the rule of thumb to be that the higher the number of partitions is, the more subproblems are solved. However, the lower the number of partitions is, the fewer subproblems are solved, although this situation may trigger the creation of bottlenecks. Since it is not possible to know what is the best number of partitions for each dataset, we will test the following values for min the tests: 1, 2, 4, 5, 6, 8, 12, and 16. In addition, for each configuration, 10 executions will be performed, and all the results depicted are the average of those executions. 6.3. Results of the experiments This section is organised as follows. First, Section 6.3.1 highlights the results obtained from the distributed approach proposed in Section 4. Two algorithms are compared with this approach: the A* algorithm, and the COP-based approach. Secondly, Section 6.3.2 compares those results with the classic standalone approach with the A* algorithm. The metric we employ in order to measure and compare each approach is the Elapsed Real Time (ERT)13 for each scenario and dataset. Each ERT shown in this section comprises the average of ten executions. The evaluation is performed by means of an analytic study. This study includes: (i) graphics which depict how the ERT evolves as the number of partitions increases; and (ii) an analysis of the trendline of each dataset. By analysing the slope of each trendline, we can quantitatively observe how the ERT scales as the number of partitions increases. For each dataset, if the slope is positive, it means that the creation of more partitions (i.e., a better distribution) is not beneficial for that dataset, and the greater the slope is, the worse it scales. If the slope is negative, it means that the approach does scale well for that dataset (and the less steep the slope is, the better it scales). The slope also enables a comparison between several datasets with the same configuration. 13 The Elapsed Real Time (ERT) is the time from the start of the execution of a program to the end of it. 13 3.2. Publications 117 Á. Valencia-Parra, Á.J. Varela-Vaca, M.T. Gómez-López et al. Information Systems 99 (2021) 101731 Table 1 Datasets used for the experimentation. Dataset Event log Petri net Partial models Cases Events Variants Size (MB) Places Transitions Arcs CFC Num. of models Num. of problems Size (MB) M2 [20] 500 8,809 500 2.20 34 34 160 36 102 51,000 509.4 M5 [20] 500 17,028 500 4.2 35 33 156 35 10,545 5,272,500 96,989 M8 [20] 500 8,246 432 2.1 17 15 72 18 4,1590 2,079.5 31,408.733 CCC20d[38] 1265 28,440 732 13.3 45 44 94 47 26 32,890 346.619 prGm6 [39] 1200 171,685 335 41.8 714 335 1644 383 33,457 40,148,400 2,488,254.81 6.3.1. Results obtained from the distributed approach The chart in Fig. 15a shows the evolution of the ERT increasing the number of partitions of the set of partial models (m) for the datasets M2, M5, M8, and CCC20d. For these tests, no timeout has been established since the A* algorithm can solve all the subproblems in a reasonable time. Therefore, all the alignments that have been obtained are optimal. Note that the results for prGm6 are not in the chart because of the complexity in that particular case, and it is therefore analysed separately. In detail, the best ERTs for M5 and M8 have been obtained with m=2. From there, the ERTs tend to worsen. If the slopes of their trendlines are analysed, that for M5 is 0.08, while that for M8 is 0.16. For M2 and CCC20d, the best ERT is obtained with m=1, and the slopes of their trendlines are 0.22 and 0.57, respectively. This means that M5 benefits more from the distribution than the other three datasets. As aforementioned, the results obtained for the dataset prGm6 are depicted in Fig. 15b. Due to memory issues arising from the size of the partitions, it has not been possible to employ values for mfrom 1 to 6. For this reason, we have used the following values for min this benchmark: 8, 10, 12, 13, 14, 16, 20, and 24. The best ERT value is obtained for m=24, with the slope of the trendline at −1.28. It means that this dataset benefits from a better distribution, since the ERT tends to decrease as the number of partitions increases. From these results, we can conclude that the datasets that produce a larger number of subproblems more benefit are from a larger distribution. It is especially noticeable in the prGm6 dataset, as it has a clear tendency to decrease the ERT when the number of partitions increases. It should be noted that M5, which also produces a large number of alignment subproblems, has a slope of 0.08, which shows better scalability than M8, M2, and CCC20d. Next, we present the results obtained from the distributed approach with the COP-based approach. Fig. 15c shows the evolution of the ERT increasing the number of partitions of the set of partial models (m). Once again, the larger mbecomes, the smaller are the distributed partitions. For these tests, a timeout of 500 ms per subproblem has been established, since the COP is not capable of solving all the subproblems in a reasonable time if it is unbounded (note that the datasets which have a large number of subproblems might contain a high number thereof producing bottlenecks). Therefore, certain alignments might not achieve the optimal. In the next section, the percentage of traces per dataset for which an optimal alignment value is found will be shown and analysed. Due to the excessive memory consumption by the COPs, it has been impossible to successfully complete any of the executions for the prGm6 dataset; hence no results are shown. Analysing the results for M5 and M8, the best ERT is obtained for m=6. The slopes of the trendline for the two datasets are −3.13 and −1.44, respectively. This shows that the distribution of the alignment subproblems improve the resolution in terms of ERT. This is observed when ERT is compared to the previous results with the A* algorithm, where the slopes for M5 and M8 are 0.08 and 0.16, respectively. However, in absolute terms, the ERT tends to be higher with the COP solver. On the other hand, for M2 and CCC20d, the best ERT value is obtained for m=1. The slopes of both datasets are 0.02, and 0.06, respectively, which also shows a better scaling than in the previous case with the A* algorithm. For these datasets, the ERTs are similar to those obtained with the A* algorithm. 6.3.2. Comparing the A* algorithm in standalone with the distributed approaches Fig. 16a presents a comparison between the ERT of the A* algorithm in standalone, and the best results obtained from the distributed approach.14,15 Fig. 16b depicts the percentage of optimal alignments found over the set of traces for each dataset. Note that the only dataset for which the COP-based approach is able to find an optimal value for all the traces is CCC20d. In summary, the distributed approach attains better results for M2, M5, and prGm6 with the A* algorithm, and for CCC20dwith the COP-based approach. The datasets which produce a larger number of subproblems, in general, gain greater benefits from a larger distribution (note that the trendlines of M5 and M8 have a negative slope when solved with the COP-based approach, and a slightly positive tendency when solved with A*). Note also that datasets with extremely complex models might be solved in a reasonable time with the distributed approach, as can be seen with prGm6. However, in certain cases, the application of decomposition and the distribution of the subproblems fails to produce the best results. For example, the best results of M8 were obtained from the standalone A* algorithm. This is due to the characteristics of the model. An in-depth study into the factors which make a decomposition worthwhile in terms of ERT could be performed in the future. By comparing the distributed approach with A* and the COP- based approach, we can conclude that the more complex the algorithm for computing alignments is, the more benefits the execution attains from a larger distribution. This is justified by the fact that the slopes of the trendlines tend to be closer to zero or negative as the time spent by the subproblems increases. It is especially noticeable in the case of the COP-based approach, which takes more time per subproblem than does the A* algorithm. In the light of the results, we can conclude that our approach to decomposing the alignment problem into subproblems and their subsequent distribution, in general, achieves better results in terms of ERT in comparison with the standalone approach. Finally, we remark that the complexity of the conformance checking algorithm exerts a heavy influence both on the ERT and on the number of optimal alignments (e.g., the COP-based approach). 7. Conclusion In this paper, a Big Data framework is provided for the parallelisation and distribution of the conformance checking analysis disengaged from the algorithm applied. The creation of subproblems that can be solved distributed makes it possible to tackle 14 There are no results for the COP-based approach in standalone since the COP implementation proposed in this paper was only conceived to be performed in distributed scenarios. 15 There are no results for the prGm6 and the A* algorithm in standalone because the PM4Py execution took more than 24 h without yielding any result. 14 118 Chapter 3. Discussion and Publications Á. Valencia-Parra, Á.J. Varela-Vaca, M.T. Gómez-López et al. Information Systems 99 (2021) 101731 Fig. 15. Results in terms of ERT for the distributed algorithm (logarithmic scale). Fig. 16. Comparison between the standalone A* and the distributed A* and the COP-based approach in terms of ERT and percentage of optimal traces. problems whose complexity could not be approached with local algorithms. For the decomposition, we have proposed an innovative horizontal technique to build subproblems whose resolution is based on a map function, and combined by a reduceByKey strategy, with the improvement of an estimation metric that prevents the resolution of unpromising subproblems. The proposed framework includes the capacity of customising the distribution of models and traces to determine the best configuration for the distribution of the alignment resolution. To demonstrate the applicability of our proposal, the framework has been tested by two alignment techniques: the classic A* approach and a new approach based on the Constraint Optimisation paradigm. The analysis of these two options is derived from the interest in comparing a classic solution with others, such as Constraint Optimisation Problems, which enables the domain to be enclosed and the amount of time available for finding an optimal alignment value to be limited. Five different datasets have been used for testing our framework to compare local (standalone) and distributed solutions, the distributed solution among them, and the effects of the configuration of the distribution on the performance. In summary, the framework provides a high degree of flexibility, since it facilitates the tuning of the parameters that determine the level of distribution of the subproblems, the application of different alignment algorithms, and the applicability of an estimation of the alignment, before it is computed, in order to prevent the analysis of unpromising subproblems. 15 3.2. Publications 119 Á. Valencia-Parra, Á.J. Varela-Vaca, M.T. Gómez-López et al. Information Systems 99 (2021) 101731 From this analysis of the experiments, it is possible to find examples where a local solver is more efficient, but for other examples, the distribution of the problem is more efficient than the local. By comparing the two algorithms in distributed scenarios, it is possible to pinpoint the problem areas where each algorithm can find a better solution or take a shorter time. This is why we plan to carry out a more in-depth analysis of the features of the models and logs in order to characterise the problems in terms of ascertaining which performs better before computing the alignments. Declaration of competing interest The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper. Acknowledgements This work has been partially funded by the Ministry of Science and Technology of Spain ECLIPSE (RTI2018-094283-B-C33) project, the European Regional Development Fund (ERDF/FEDER), MINECO, Spain (TIN2017-86727-C2-1-R), and by the University of Seville, Spain with VI Plan Propio de Investigación y Transferencia (VI PPIT-US). Disclosure All the authors are responsible for the concept of the paper, the results presented and the writing. All the authors have approved the final content of the manuscript. No potential conflict of interest was reported by the authors. References [1] M. Dumas, W.M.P. van der Aalst, A.H.M. ter Hofstede, Process-Aware Information Systems: Bridging People and Software Through Process Technology, Wiley, 2005, URL: http://eu.wiley.com/WileyCDA/WileyTitle/ productCd-0471663069.html. [2] H. Roehm, J. Oehlerking, M. Woehrle, M. Althoff, Model conformance for cyber-physical systems: A survey, TCPS 3 (2019) 30:1–30:26, http: //dx.doi.org/10.1145/3306157. [3] J. Carmona, B.F. van Dongen, A. Solti, M. Weidlich, Conformance Checking - Relating Processes and Models, Springer, 2018, http://dx.doi.org/10.1007/ 978-3-319-99414-7. [4] A. Adriansyah, Aligning Observed and Modeled Behavior (Ph.D. thesis), Technische Universiteit Eindhoven, 2014. [5] W.M.P. van der Aalst, Decomposing Petri nets for process mining: A generic approach, Distrib. Parallel Databases 31 (2013) 471–507, http://dx.doi.org/ 10.1007/s10619-013-7127-5. [6] J. Munoz-Gama, J. Carmona, W.M.P. van der Aalst, Single-entry singleexit decomposed conformance checking, Inf. Syst. 46 (2014) 102–122, http://dx.doi.org/10.1016/j.is.2014.04.003. [7] H.M.W. Verbeek, W.M.P. van der Aalst, Merging alignments for decomposed replay, in: F. Kordon, D. Moldt (Eds.), Application and Theory of Petri Nets and Concurrency: 37th International Conference, PETRI NETS 2016, Toruń, Poland, June 19-24, 2016; Proceedings, Springer International Publishing, Cham, 2016, pp. 219–239, http://dx.doi.org/10.1007/978-3-319-39086-4_14. [8] W.L.J. Lee, H.M.W. Verbeek, J. Munoz-Gama, W.M.P. van der Aalst, M. Sepúlveda, Recomposing conformance: Closing the circle on decomposed alignment-based conformance checking in process mining, Inform. Sci. 466 (2018) 55–91, http://dx.doi.org/10.1016/j.ins.2018.07.026. [9] W.M.P. van der Aalst, Distributed process discovery and conformance checking, in: J. de Lara, A. Zisman (Eds.), Fundamental Approaches to Software Engineering, Springer Berlin Heidelberg, Berlin, Heidelberg, 2012, pp. 1–25. [10] J. Dean, S. Ghemawat, MapReduce: Simplified data processing on large clusters, in: E.A. Brewer, P. Chen (Eds.), 6th Symposium on Operating System Design and Implementation (OSDI 2004), USENIX Association, San Francisco, 2004, pp. 137–150, URL: https://ai.google/research/pubs/pub62. [11] S. Sakr, Z. Maamar, A. Awad, B. Benatallah, W.M.P. van der Aalst, Business process analytics and big data systems: A roadmap to bridge the gap, IEEE Access 6 (2018) 77308–77320, http://dx.doi.org/10.1109/ACCESS.2018. 2881759. [12] M.T. Gómez-López, D. Borrego, J. Carmona, R.M. Gasca, Computing alignments with constraint programming: The acyclic case, in: Proceedings of the International Workshop on Algorithms & Theories for the Analysis of Event Data 2016 Satellite event of the conferences (ATAED) 2016, Torun, Poland, June 20-21, 2016, 2016, pp. 96–110. URL: http://ceur-ws.org/Vol- 1592/paper07.pdf. [13] B.F. van Dongen, J. Carmona, T. Chatain, F. Taymouri, Aligning modeled and observed behavior: A compromise between computation complexity and quality, in: Advanced Information Systems Engineering - 29th International Conference, Essen, Germany, June 12-16, 2017, 2017, pp. 94–109. [14] B.F. van Dongen, Efficiently computing alignments - using the extended marking equation, in: Business Process Management - 16th International Conference, BPM 2018, Sydney, NSW, Australia, September 9-14, 2018, Proceedings, 2018, pp. 197–214. [15] M. de Leoni, A. Marrella, Aligning real process executions and prescriptive process models through automated planning, Expert Syst. Appl. 82 (2017) 162–183. [16] D. Reißner, R. Conforti, M. Dumas, M.L. Rosa, A. Armas-Cervantes, Scalable conformance checking of business processes, in: OTM CoopIS, Rhodes, Greece, 2017, pp. 607–627. [17] S.J.J. Leemans, D. Fahland, W.M.P. van der Aalst, Scalable process discovery and conformance checking, Softw. Syst. Model. 17 (2018) 599–631, http: //dx.doi.org/10.1007/s10270-016-0545-x. [18] D. Reißner, A. Armas-Cervantes, R. Conforti, M. Dumas, D. Fahland, M. La Rosa, Scalable alignment of process models and event logs: An approach based on automata and s-components, Inf. Syst. 94 (2020) 101561, http: //dx.doi.org/10.1016/j.is.2020.101561, URL: http://www.sciencedirect.com/ science/article/pii/S0306437920300545. [19] F. Taymouri, J. Carmona, A recursive paradigm for aligning observed behavior of large structured process models, in: 14th International Conference of Business Process Management (BPM), Rio de Janeiro, Brazil, September 18-22, 2016, pp. 197–214. [20] F. Taymouri, J. Carmona, Model and event log reductions to boost the computation of alignments, in: P. Ceravolo, C. Guetl, S. Rinderle-Ma (Eds.), Data-Driven Process Discovery and Analysis, Springer International Publishing, 2018, pp. 1–21. [21] F. Taymouri, J. Carmona, Computing alignments of well-formed process models using local search, ACM Trans. Softw. Eng. Methodol. 29 (2020) 15:1–15:41, http://dx.doi.org/10.1145/3394056. [22] A. Burattin, S.J. van Zelst, A. Armas-Cervantes, B.F. van Dongen, J. Carmona, Online conformance checking using behavioural patterns, in: Business Process Management - 16th International Conference, BPM 2018, Sydney, NSW, Australia, September 9-14, 2018, Proceedings, 2018, pp. 250–267. [23] F. Taymouri, J. Carmona, Structural computation of alignments of business processes over partial orders, in: 19th International Conference on Application of Concurrency to System Design, ACSD 2019, Aachen, Germany, June 23-28, 2019, 2019, pp. 73–81. [24] L. Padró, J. Carmona, Approximate computation of alignments of business processes through relaxation labelling, in: Business Process Management - 17th International Conference, BPM 2019, Vienna, Austria, September 1-6, 2019, Proceedings, 2019, pp. 250–267. [25] J. Evermann, Scalable process discovery using map-reduce, IEEE Trans. Serv. Comput. 9 (2016) 469–481, http://dx.doi.org/10.1109/TSC.2014.2367525. [26] F. Chesani, A. Ciampolini, D. Loreti, P. Mello, Map reduce autoscaling over the cloud with process mining monitoring, in: M. Helfert, D. Ferguson, V. Méndez Muñoz, J. Cardoso (Eds.), Cloud Computing and Services Science, Springer International Publishing, Cham, 2017, pp. 109–130. [27] J. Engelfriet, Branching processes of petri nets, Acta Inf. 28 (1991) 575–591, http://dx.doi.org/10.1007/BF01463946. [28] R. Bergenthum, S. Mauser, R. Lorenz, G. Juhás, Unfolding semantics of petri nets based on token flows, Fund. Inform. 94 (2009) 331–360, http: //dx.doi.org/10.3233/FI-2009-134. [29] D. Fahland, W.M.P. van der Aalst, Simplifying discovered process models in a controlled manner, Inf. Syst. 38 (2013) 585–605, http://dx.doi.org/10. 1016/j.is.2012.07.004. [30] R. Dechter, Constraint Processing (The Morgan Kaufmann Series in Artificial Intelligence), Morgan Kaufmann, 2003. [31] K. Apt, Principles of Constraint Programming, Cambridge University Press, New York, NY, USA, 2003. [32] M.T. Gómez-López, R. Ceballos, R.M. Gasca, C.D. Valle, Developing a labelled object-relational constraint database architecture for the projection operator, Data Knowl. Eng. 68 (2009) 146–172, http://dx.doi.org/10.1016/ j.datak.2008.09.002. [33] A.J. Varela-Vaca, L. Parody, R.M. Gasca, M.T. Gómez-López, Automatic verification and diagnosis of security risk assessments in business process models, IEEE Access 7 (2019) 26448–26465, http://dx.doi.org/10.1109/ ACCESS.2019.2901408. 16 120 Chapter 3. Discussion and Publications Á. Valencia-Parra, Á.J. Varela-Vaca, M.T. Gómez-López et al. Information Systems 99 (2021) 101731 [34] M.T. Gómez-López, R.M. Gasca, J.M. Pérez-Álvarez, Compliance validation and diagnosis of business data constraints in business processes at runtime, Inf. Syst. 48 (2015) 26–43, http://dx.doi.org/10.1016/j.is.2014.07.007. [35] M.T. Gómez-López, L. Parody, R.M. Gasca, S. Rinderle-Ma, Prognosing the compliance of declarative business processes using event trace robustness, in: On the Move to Meaningful Internet Systems: OTM 2014 Conferences - Confederated International Conferences: CoopIS, and ODBASE 2014, Amantea, Italy, October 27-31, 2014, Proceedings, 2014, pp. 327–344. [36] D. Borrego, R. Eshuis, M.T. Gómez-López, R.M. Gasca, Diagnosing correctness of semantic workflow models, Data Knowl. Eng. 87 (2013) 167–184. [37] R. Bergenthum, S. Mauser, Synthesis of petri nets from infinite partial languages with viptool, in: 15th German Workshop on Algorithms and Tools for Petri Nets, Algorithmen und Werkzeuge für Petrinetze, AWPN 2008, Rostock, Germany, September 26-27, 2008, Proceedings, 2008, pp. 81–86. URL: http://ceur-ws.org/Vol-380/paper13.pdf. [38] J. Buijs, Environmental permit application process (‘wabo’), in: CoSeLoG Project, 2014, http://dx.doi.org/10.4121/UUID:26ABA40D-8B2D-435B- B5AF-6D4BFBD7A270, URL: https://data.4tu.nl/collections/Environmental_ permit_application_process_WABO_CoSeLoG_project/5065529. [39] J. Munoz-Gama, J. Carmona, W.M.P. van der Aalst, Conformance checking in the large: Partitioning and topology, in: F. Daniel, J. Wang, B. Weber (Eds.), Business Process Management, Springer Berlin Heidelberg, Berlin, Heidelberg, 2013, pp. 130–145. [40] J. Cardoso, Business process control-flow complexity: Metric, evaluation, and validation, Int. J. Web Serv. Res. 5 (2008) 49–76, URL: http://www.igiglobal.com/bookstore/titledetails.aspx?titleid=1079. 17 3.2. Publications 121 123 Chapter 4 Conclusion and Future Work This Chapter concludes this thesis by summarising the main solutions that have been proposed to achieve the objectives that were traced. Section 4.1 highlights the conclusions of this thesis. Afterward, Section 4.2 discusses the limitations of the proposals and the possible extensions that could be commited in the future. 4.1 Conclusion In this thesis, we have presented innovative techniques to improve three key activities in Big Data pipelines. These are Data Preparation, Data Quality assessment, and Data Analysis. The contributions are intended to improve the Big Data pipelines that use optimisation problems as a mechanisms of Data Analysis to support decision-making processes. Specifically, the optimisation algorithms that we have improved are exhaustive, which are able to explore the entire search space and can guarantee optimal solutions. These can become NP-complete, especially if large amounts of data are involved. Although the Big Data paradigm is ideal for performing this type of computation, we found a lack of support for these techniques in Big Data environments. For this reason, one of the three main objectives of this thesis is to develop solutions to enhance the distribution and computation of Constraint Optimisation Problems (COPs) and big complex optimisation problems in distributed environments (OBJ 3). When building Big Data pipelines to use these techniques, we found two problems regarding Data Preparation and Data Quality. On the one hand, our case studies required the transformation of data with complex nested structures, since the COPs used this type of data as input. In this regard, we found the opportunity to develop Domain-Specific Languages (DSL) to make Data Transformation processes easier (OBJ 1). However, we realised that poorquality data spoilt the results of the Data Analysis. Therefore, we found the opportunity to develop a methodology to model Data Quality rules and automate the evaluation of data usability, as well as facilitate their repair (OBJ 2). To summarise, this thesis is focused on: 1. Improving Data Preparation activities in cases where data present complex and nested structures (OBJ 1). 2. Improving the evaluation of the Data Quality activity (OBJ 2). 130 Bibliography [10] Danilo Ardagna et al. “Context-aware data quality assessment for big data”. In: Future Generation Computer Systems 89 (2018), pp. 548–562. ISSN: 0167-739X. DOI:https://doi. org / 10 . 1016 / j . future . 2018 . 07 . 014.URL:https : / / www . sciencedirect . com / science/article/pii/S0167739X17329151. [11] B. Arputhamary and L. Arockiam. “Data Integration in Big Data Environment”. In: Bonfring International Journal of Data Mining 5.1 (2015), pp. 01–05. ISSN: 2250107X. DOI: 10.9756/BIJDM.8001.URL:http://journal.bonfring.org/abstract.php?id=2& archiveid=429. [12] Rolf B. Banziger, Artie Basukoski, and Thierry Chaussalet. “Discovering Business Processes in CRM Systems by Leveraging Unstructured Text Data”. In: 2018 IEEE 20th International Conference on High Performance Computing and Communications; IEEE 16th International Conference on Smart City; IEEE 4th International Conference on Data Science and Systems (HPCC/SmartCity/DSS). 2018, pp. 1571–1577. DOI:10.1109/HPCC/SmartCity/ DSS.2018.00257. [13] Cristóbal Barba-González et al. “Injecting domain knowledge in multi-objective optimization problems: A semantic approach”. In: Computer Standards Interfaces 78 (2021), p. 103546. ISSN: 0920-5489. DOI:10.1016/J.CSI.2021.103546. [14] Cristóbal Barba-González et al. “BIGOWL: Knowledge centered Big Data analytics”. In: Expert Systems with Applications 115 (2019), pp. 543–556. ISSN: 0957-4174. DOI:https: //doi.org/10.1016/j.eswa.2018.08.026.URL:https://www.sciencedirect.com/ science/article/pii/S0957417418305347. [15] Carlo Batini and Monica Scannapieco. Data and information quality: dimensions, principles and techniques. 2016. ISBN: 9783319241067. [16] Bloor Research. Data Preparation (Self-Service). 2018. URL:https://www.bloorresearch. com/technology/data-preparation-self-service/. [17] Christian Blum and Andrea Roli. “Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison”. In: ACM Computing Surveys 35.3 (2003), 268 – 308. DOI:10.1145/937503.937505. [18] J.C.A.M. Buijs. Environmental permit application process (‘WABO’), CoSeLoG project. nl. 2014. DOI:10.4121/UUID: 26ABA40D- 8B2D- 435B- B5AF- 6D4BFBD7A270.URL:https: //data.4tu.nl/collections/Environmental_permit_application_process_WABO_ CoSeLoG_project/5065529. [19] Ismael Caballero et al. “A Data Quality Measurement Information Model Based On ISO/IEC 15939.” In: ICIQ. Cambridge, MA. 2007, pp. 393–408. [20] Diego Calvanese et al. “Ontology-Driven Extraction of Event Logs from Relational Databases”. In: Business Process Management Workshops. Ed. by Manfred Reichert and Hajo A. Reijers. Cham: Springer International Publishing, 2016, pp. 140–153. ISBN: 978- 3-319-42887-1. Bibliography 131 [21] Josep Carmona et al. Conformance Checking - Relating Processes and Models. Springer, 2018. ISBN: 978-3-319-99413-0. DOI:10.1007/978-3-319-99414-7.URL:https://doi.org/ 10.1007/978-3-319-99414-7. [22] Paolo Ceravolo et al. “Big Data Semantics”. In: Journal on Data Semantics 7.2 (2018), pp. 65–85. ISSN: 18612040. DOI:10.1007/s13740- 018- 0086- 2.URL:http://link. springer.com/10.1007/s13740-018-0086-2. [23] Chen Chen et al. “BigGorilla: An Open-Source Ecosystem for Data Preparation and Integration”. In: IEEE Data Eng. Bull. 41.2 (2018), pp. 10–22. [24] P. Cong and Z. Xiaoyi. “Research and Design of Interactive Data Transformation and Migration System for Heterogeneous Data Sources”. In: 2009 WASE International Conference on Information Engineering. Vol. 1. 2009, pp. 534–536. [25] William H. Crown. “The Potential Role of Constrained Optimization Methods in Healthcare Decision Making”. In: Applied Health Economics and Health Policy 2020 18:4 18.4 (2020), pp. 461–462. ISSN: 1179-1896. DOI:10.1007/S40258- 020- 00559- 8.URL: https://link.springer.com/article/10.1007/s40258-020-00559-8. [26] Edward Curry. “The big data value chain: Definitions, concepts, and theoretical approaches”. In: New Horizons for a Data-Driven Economy: A Roadmap for Usage and Exploitation of Big Data in Europe. Cham: Springer International Publishing, 2016, pp. 29– 37. ISBN: 9783319215693. DOI:10.1007/978-3-319-21569-3_3. [27] Jeffrey Dean and Sanjay Ghemawat. “MapReduce: Simplified Data Processing on Large Clusters”. In: 6th Symposium on Operating System Design and Implementation (OSDI 2004). Ed. by Eric A. Brewer and Peter Chen. San Francisco: USENIX Association, 2004, pp. 137–150. URL:https://ai.google/research/pubs/pub62. [28] Yuri Demchenko et al. “Big security for big data: Addressing security challenges for the big data infrastructure”. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 8425 LNCS. Springer, Cham, 2014, pp. 76–94. ISBN: 9783319068107. DOI:10 . 1007 / 978 - 3 - 319 - 06811-4_13.URL:http://link.springer.com/10.1007/978-3-319-06811-4_13. [29] Xin Luna Dong and Divesh Srivastava. “Big Data Integration”. In: Synthesis Lectures on Data Management 7.1 (2015), pp. 1–198. ISSN: 2153-5418. DOI:10 . 2200 / S00578ED1V01Y201404DTM040. [30] Shaker H. Ali El-Sappagh, Abdeltawab M. Ahmed Hendawi, and Ali Hamed El Bastawissy. “A proposed model for data warehouse ETL processes”. In: Journal of King Saud University - Computer and Information Sciences 23.2 (2011), pp. 91–104. ISSN: 1319- 1578. DOI:10.1016/J.JKSUCI.2011.05.005.URL:https://www.sciencedirect.com/ science/article/pii/S131915781100019X/?imgSel=Y. [31] Adir Even, G. Shankaranarayanan, and Paul D. Berger. “Evaluating a model for costeffective data quality management in a real-world CRM setting”. In: Decision Support Systems 50.1 (2010), pp. 152–163. ISSN: 0167-9236. DOI:https://doi.org/10.1016/j. 132 Bibliography dss.2010.07.011.URL:https://www.sciencedirect.com/science/article/pii/ S016792361000117X. [32] André Freitas and Edward Curry. “Big Data Curation”. In: New Horizons for a Data- Driven Economy. Cham: Springer International Publishing, 2016, pp. 87–118. DOI:10. 1007/978-3-319-21569-3_6. [33] Eugene C. Freuder and Richard J. Wallace. “Partial constraint satisfaction”. In: Artificial Intelligence 58.1-3 (1992), pp. 21–70. ISSN: 00043702. DOI:10.1016/0004-3702(92)90004- H. [34] Tim Furche et al. “Data Wrangling for Big Data: Challenges and Opportunities”. In: 19th International Conference on Extending Database Technology (EDBT). Vol. 8062 LNAI. 2016, pp. 473–478. DOI:10.5441/002/EDBT.2016.44. [35] Xinbo Geng and Le Xie. “Data-driven Decision Making with Probabilistic Guarantees (Part 1): A Schematic Overview of Chance-constrained Optimization”. In: (2019). DOI: 10.48550/arxiv.1903.10621. arXiv: 1903.10621.URL:https://arxiv.org/abs/1903. 10621v2. [36] Boris Glavic. “Big data provenance: Challenges and implications for benchmarking”. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 8163 LNCS. Springer Verlag, 2014, pp. 72–80. ISBN: 9783642539732. DOI:10.1007 /978- 3 - 642- 53974- 9 _7.URL:https :/ /link. springer.com/chapter/10.1007/978-3-642-53974-9_7. [37] Monika Gupta and Ashish Sureka. “Nirikshan: Mining Bug Report History for Discovering Process Maps, Inefficiencies and Inconsistencies”. In: Proceedings of the 7th India Software Engineering Conference. ISEC ’14. Chennai, India: Association for Computing Machinery, 2014. ISBN: 9781450327763. DOI:10.1145/2590748.2590749.URL:https: //doi.org/10.1145/2590748.2590749. [38] María Teresa Gómez-López and Rafael M. Gasca. “Using Constraint Programming in Selection Operators for Constraint Databases”. In: Expert Systems with Applications 41.15 (2014), pp. 6773–6785. ISSN: 0957-4174. DOI:https : / / doi . org / 10 . 1016 / j . eswa . 2014 . 04 . 047.URL:https : / / www . sciencedirect . com / science / article / pii / S095741741400270X. [39] Hadoop HDFS Architecture Guide.URL:https://hadoop.apache.org/docs/r1.2.1/ hdfs_design.html. [40] Francisco José de Haro-Olmo et al. “Data curation in the Internet of Things: A decision model approach”. In: Computational and Mathematical Methods 3.6 (2021), e1191. DOI: https://doi.org/10.1002/cmm4.1191. eprint: https://onlinelibrary.wiley.com/ doi/pdf/10.1002/cmm4.1191.URL:https://onlinelibrary.wiley.com/doi/abs/10. 1002/cmm4.1191. [41] Joseph M. Hellerstein, Jeffrey Heer, and Sean Kandel. “Self-Service Data Preparation: Research to Practice”. In: IEEE Data Eng. Bull. 41 (2018), pp. 23–34. Bibliography 133 [42] Katsutoshi Hirayama and Makoto Yokoo. “Distributed partial constraint satisfaction problem”. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 1330 (1997), pp. 222–236. ISSN: 16113349. DOI:10.1007/BFB0017442. [43] Philip Howard. Data Preparation (self-service) – Bloor Research. 2018. URL:https://www. bloorresearch . com / technology / data - preparation - self - service/ (visited on 06/14/2022). [44] “IEEE Standard for eXtensible Event Stream (XES) for Achieving Interoperability in Event Logs and Event Streams”. In: IEEE Std 1849-2016 (2016), pp. 1–50. DOI:10.1109/ IEEESTD.2016.7740858. [45] Ihab F Ilyas and Xu Chu. Data cleaning. ACM, 2019. [46] Illinois School of Information Sciences. Foundations of Data Curation. 2018. URL:https: //ischool.illinois.edu/degrees-programs/courses/is531 (visited on 06/14/2022). [47] Introduction to MongoDB - MongoDB Manual.URL:https://www.mongodb.com/docs/ manual/introduction/. [48] Jagreet Kaur. Data Preprocessing and Data Wrangling Machine Learning. 2017. URL:https: //www.xenonstack.com/blog/data-preparation (visited on 06/14/2022). [49] Zhongjun Jin et al. “Foofah: Transforming Data By Example”. In: Proceedings of the 2017 ACM International Conference on Management of Data - SIGMOD ’17. New York, New York, USA: ACM Press, 2017, pp. 683–698. ISBN: 9781450341974. DOI:10.1145/3035918. 3064034.URL:http://dl.acm.org/citation.cfm?doid=3035918.3064034. [50] Jeffrey Heer Joseph M. Hellerstein and Sean Kandel. Self-Service Data Preparation: Research to Practice. Tech. rep. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 2018. [51] Nikunj Joshi and Bintu Kadhiwala. “Big data security and privacy issues — A survey”. In: 2017 Innovations in Power and Advanced Computing Technologies (i-PACT). 2017, pp. 1– 5. DOI:10.1109/IPACT.2017.8245064. [52] Doug Laney. “3D data management: Controlling data volume, velocity, and variety”. In: META Group (2001). URL:https://blogs.gartner.com/doug-laney/files/2012/01/ ad949-3D-Data-Management-Controlling-Data-Volume-Velocity-and-Variety.pdf. [53] In Lee. “Big data: Dimensions, evolution, impacts, and challenges”. In: Business Horizons 60.3 (2017), pp. 293–303. ISSN: 0007-6813. DOI:10.1016/J.BUSHOR.2017.01.004.URL: https://www.sciencedirect.com/science/article/pii/S0007681317300046. [54] James Manyika et al. Big data: The next frontier for innovation, competition, and productivity | McKinsey. 2011. URL:https://www.mckinsey.com/business-functions/digitalmckinsey/our-insights/big-data-the-next-frontier-for-innovation (visited on 04/25/2022). 134 Bibliography [55] Mohsen Marjani et al. “Big IoT Data Analytics: Architecture, Opportunities, and Open Research Challenges”. In: IEEE Access 5 (2017), pp. 5247–5261. ISSN: 21693536. DOI: 10.1109/ACCESS.2017.2689040. arXiv: 2017.URL:http://ieeexplore.ieee.org/ document/7888916/. [56] Aiswarya Raj Munappy, Jan Bosch, and Helena Homström Olsson. “Data Pipeline Management in Practice: Challenges and Opportunities”. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 12562 LNCS (2020), pp. 168–184. ISSN: 16113349. DOI:10.1007/978-3-030- 64148-1_11.URL:https://link.springer.com/chapter/10.1007/978-3-030-64148- 1_11. [57] Eduardo González López de Murillas, Wil M. P. van der Aalst, and Hajo A. Reijers. “Process Mining on Databases: Unearthing Historical Data from Redo Logs”. In: Business Process Management. Ed. by Hamid Reza Motahari-Nezhad, Jan Recker, and Matthias Weidlich. Cham: Springer International Publishing, 2015, pp. 367–385. ISBN: 978-3-319- 23063-4. [58] Marek Obitko, Václav Jirkovský, and Jan Bezdíˇcek. “Big data challenges in industrial automation”. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 8062 LNAI. 2013, pp. 305– 316. ISBN: 9783642400896. DOI:10.1007/978-3-642-40090-2_27. [59] Paulo Oliveira, Fátima Rodrigues, and Pedro Rangel Henriques. “A Formal Definition of Data Quality Problems.” In: ICIQ. 2005. [60] OMG. Decision Model and Notation (DMN), Version 1.2. Object Management Group, 2019. URL:https://www.omg.org/spec/DMN. [61] Operational support and enterprise systems.URL:https://www.britannica.com/topic/ information-system/Management-support. [62] Barry O’Sullivan. “Opportunities and Challenges for Constraint Programming”. In: Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence. AAAI’12. Toronto, Ontario, Canada: AAAI Press, 2012, pp. 2148–2152. URL:http : / / dl . acm . org / citation.cfm?id=2900929.2901033. [63] Ahmed Oussous et al. “Big Data technologies: A survey”. In: Journal of King Saud University - Computer and Information Sciences 30.4 (2018), pp. 431–448. ISSN: 1319-1578. DOI: 10.1016/J.JKSUCI.2017.06.001.URL:https://www.sciencedirect.com/science/ article/pii/S1319157817300034. [64] Pekka Pääkkönen and Daniel Pakkala. “Reference Architecture and Classification of Technologies, Products and Services for Big Data Systems”. In: Big Data Research 2.4 (2015), pp. 166–186. ISSN: 2214-5796. DOI:10.1016/J.BDR.2015.01.001.URL:https: //www.sciencedirect.com/science/article/pii/S2214579615000027. Bibliography 135 [65] Ken Peffers et al. “A Design Science Research Methodology for Information Systems Research”. In: https://doi.org/10.2753/MIS0742-1222240302 24.3 (2014), pp. 45–77. ISSN: 07421222. DOI:10.2753/MIS0742-1222240302.URL:https://www.tandfonline.com/ doi/abs/10.2753/MIS0742-1222240302. [66] PM4Py - Process Mining for Python. Fraunhofer Institute for Applied Information Technology. 2022. URL:https://pm4py.fit.fraunhofer.de/docs. [67] Shakthi Poornima and Mullur Pushpalatha. “A journey from big data towards prescriptive analytics”. In: ARPN Journal of Engineering and Applied Sciences 11.19 (2016), pp. 11465–11474. ISSN: 18196608. [68] Charles Prud’homme, Jean-Guillaume Fages, and Xavier Lorca. Choco Documentation. TASC - LS2N CNRS UMR 6241, COSLING S.A.S. 2017. URL:http : / / www . choco - solver.org. [69] José Miguel Pérez-Álvarez et al. “Tactical Business-Process-Decision Support based on KPIs Monitoring and Validation”. In: Computers in Industry 102 (2018), pp. 23–39. ISSN: 0166-3615. DOI:https://doi.org/10.1016/j.compind.2018.08.001.URL:https: //www.sciencedirect.com/science/article/pii/S0166361517307819. [70] Erhard Rahm and Hong Hai Do. “Data cleaning: Problems and current approaches”. In: IEEE Data Eng. Bull. 23.4 (2000), pp. 3–13. [71] Edwin D. Reilly, Anthony. Ralston, and David. Hemmendinger. “Backus-Naur form (BNF)”. In: Encyclopedia of Computer Science. Wiley, 2003, pp. 129–131. ISBN: 0470864125. URL:https://dl.acm.org/citation.cfm?id=1074155. [72] Dirk Riehle et al. “Composite design patterns”. In: ACM SIGPLAN Notices 32.10 (1997), pp. 218–228. ISSN: 03621340. DOI:10.1145/263700.263739.URL:http://portal.acm. org/citation.cfm?doid=263700.263739. [73] F. Rossi, P. van Beek, and T. Walsh. Handbook of Constraint Programming. Elsevier, 2006. ISBN: 978-0-444-52726-4. [74] Kewei Sha and Sherali Zeadally. “Data Quality Challenges in Cyber-Physical Systems”. In: J. Data and Information Quality 6.2–3 (2015). ISSN: 1936-1955. DOI:10.1145/2740965. URL:https://doi.org/10.1145/2740965. [75] Software engineering — Software product Quality Requirements and Evaluation (SQuaRE) — Data quality model. Standard. International Organization for Standardization, 2019. [76] Jerzy Stefanowski, Krzysztof Krawiec, and Robert Wrembel. “Exploring complex and big data”. In: International Journal of Applied Mathematics and Computer Science 27.4 (2017), pp. 669–679. ISSN: 2083-8492. DOI:10.1515/amcs-2017-0046.URL:http://content. sciendo.com/view/journals/amcs/27/4/article-p669.xml. [77] J Gerald Suarez. Three Experts on Quality Management: Philip B. Crosby, W. Edwards Deming, Joseph M. Juran. Tech. rep. TOTAL QUALITY LEADERSHIP OFFICE ARLINGTON VA, 1992. [Document text truncated for crawler view.]