Measuring Similarity Between ETL Processes Using Graph Edit Distance

• Autorzy: Brzeski Maciej , Roman Adam

Identyfikatory

DOI

10.4467/20838476SI.23.001.19323

• Języki publikacji: EN

Abstrakty

EN

Maintaining data warehouses and ETL processes is becoming increasingly difficult. For this reason, we introduce a similarity measure on ETL processes, based on the edit distance of a graph, which models the process. We show both the exact way how to calculate it and heuristic approaches to compute the estimated similarity more quickly. We propose methods to improve graph edit distance based on the assumption that the ETL process model is a directed acyclic graph.

Słowa kluczowe

EN

ETL process; ETL similarity; graph edit distance; error-tolerant graph matching

• Wydawca: Wydawnictwo Uniwersytetu Jagiellońskiego
• Czasopismo: Schedae Informaticae
• Rocznik: 2023
• Tom: Vol. 32
• Strony: 9--25
• Opis fizyczny: Bibliogr. 45 poz., rys.

Twórcy

autor

Brzeski Maciej

• Faculty of Mathematics and Computer Science, Jagiellonian University, Łojasiewicza 6, 30-348 Kraków, Poland
• Informatica Polska, Kamienna 21, Kraków, Poland

autor

Roman Adam

• Faculty of Mathematics and Computer Science, Jagiellonian University, Łojasiewicza 6, 30-348 Kraków, Poland

Bibliografia

• [1] Alexander Albrecht and Felix Naumann. Managing ETL Processes. In International Workshop on New Trends in Information Integration, 2008.
• [2] Alexander Albrecht and Felix Naumann. Systematic ETL management - Experiences with high-level operators. In MIT International Conference on Information Quality, 2013.
• [3] Michael Becker and Ralf Laue. A comparative survey of business process similarity measures. Comput. Ind., 63:148–167, 2012.
• [4] Neepa Biswas, Samiran Chattapadhyay, Gautam Mahapatra, Santanu Chatterjee, and Kartick Chandra Mondal. A New Approach for Conceptual Extraction- Transformation-Loading Process Modeling. Int. J. Ambient Comput. Intell., 10:30–45, 2019.
• [5] David B. Blumenthal. New Techniques for Graph Edit Distance Computation. ArXiv, abs/1908.00265, 2019.
• [6] David B. Blumenthal, Nicolas Boria, Johann Gamper, Sébastien Bougleux, and Luc Brun. Comparing heuristics for graph edit distance computation. The VLDB Journal, 29:419–458, 2019.
• [7] Sébastien Bougleux and Luc Brun. Linear Sum Assignment with Edition. ArXiv, abs/1603.04380, 2016.
• [8] Sébastien Bougleux, Luc Brun, Vincenzo Carletti, Pasquale Foggia, Benoit Gaüzère, and Mario Vento. Graph edit distance as a quadratic assignment problem. Pattern Recognit. Lett., 87:38–46, 2017.
• [9] Sébastien Bougleux, Benoit Benoit Gaüzère, David B. Blumenthal, and Luc Brun. Fast linear sum assignment with error-correction and no cost constraints. Pattern Recognit. Lett., 134:37–45, 2020.
• [10] Sébastien Bougleux, Benoit Benoit Gaüzère, and Luc Brun. A Hungarian Algorithm for Error-Correcting Graph Matching. In Workshop on Graph Based Representations in Pattern Recognition, 2017.
• [11] Silvio Cesare, Yang Xiang, and Wanlei Zhou. Control Flow-Based Malware VariantDetection. IEEE Transactions on Dependable and Secure Computing, 11(4):307–317, 2014.
• [12] Yingwei Cui and Jennifer Widom. Lineage tracing for general data warehouse transformations. The VLDB Journal, 12:41–58, 2003.
• [13] Stefan Deßloch, Mauricio A. Hernández, Ryan Wisnesky, Ahmed M. Radwan, and Jindan Zhou. Orchid: Integrating Schema Mapping and ETL. 2008 IEEE 24th International Conference on Data Engineering, pages 1307–1316, 2008.
• [14] Asma Dhaouadi, Khadija Bousselmi, Mohamed Mohsen Gammoudi, Sébastien Monnet, and Slimane Hammoudi. Data Warehousing Process Modeling from Classical Approaches to New Trends: Main Features and Comparisons. Data, 7:113, 2022.
• [15] Remco M. Dijkman, Marlon Dumas, and Luciano García-Bañuelos. Graph Matching Algorithms for Business Process Model Similarity Search. In International Conference on Business Process Management, 2009.
• [16] Remco M. Dijkman, Marlon Dumas, Boudewijn F. van Dongen, Reina Uba, and Jan Mendling. Similarity of business process models: Metrics and evaluation. Inf. Syst., 36:498–516, 2011.
• [17] Remco M. Dijkman, Boudewijn F. van Dongen, Marlon Dumas Luciano García-Bañuelos, Matthias Kunze, Henrik Leopold, Jan Mendling, Reina Uba, Matthias Weidlich, Mathias Weske, and Zhiqiang Yan. A Short Survey on Process Model Similarity. In Seminal Contributions to Information Systems Engineering, 2013.
• [18] Dawid Duda, Jeffrey T. Pascoe, Wojciech Matyjewicz, and Krzysztof Maziarz. Method and apparatus for analyzing and migrating data integration applications, U.S. Patent No. 2012/0296862 A1, Nov. 2012.
• [19] Yang Fa. Malware Detection Based on Graph Edit Distance. Journal of Wuhan University, 2013.
• [20] Lester Randolph Ford and Delbert Ray Fulkerson. Maximal Flow Through a Network. Canadian Journal of Mathematics, 8:399 – 404, 1956.
• [21] Daniela Grigori, Juan Carlos González Corrales, Mokrane Bouzeghoub, and Ahmed Gater. Ranking BPEL Processes for Service Discovery. IEEE Transac tions on Services Computing, 3:178–192, 2010.
• [22] Informatica. Informatica Intelligent Cloud Services. https://www.informatica.com/products/cloud-integration.html.
• [23] Md Rofiqul Islam and Tomas Cerny. Business Process Extraction Using Static Analysis. In 2021 36th IEEE/ACM International Conference on Automated Software Engineering (ASE), pages 1202–1204, 2021.
• [24] ISO/IEC 25010 : 2011. Systems and software engineering - Systems and software Quality Requirements and Evaluation (SQuaRE) - System and software quality models, 2011.
• [25] Roy Jonker and A. Volgenant. A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing, 38:325–340, 1987.
• [26] Derek Justice and Alfred O. Hero. A binary linear programming formulation of the graph edit distance. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28:1200–1214, 2006.
• [27] Harold W. Kuhn. The Hungarian method for the assignment problem. Naval Research Logistics (NRL), 52, 1955.
• [28] Vladimir Iosifovich Levenshtein. Binary codes capable of correcting deletions, insertions and reversals. Soviet Physics Doklady, 10(8):707–710, feb 1966. Doklady Akademii Nauk SSSR, V163 No4 845-848 1965.
• [29] Chih-Long Lin. Hardness of Approximating Graph Transformation Problem. In International Symposium on Algorithms and Computation, 1994.
• [30] Dimitrios Michail, Joris Kinable, Barak Naveh, and John V. Sichi. JGraphT- A Java Library for Graph Data Structures and Algorithms. ACM Trans. Math. Softw., 46(2), May 2020.
• [31] James R. Munkres. Algorithms for the Assignment and Transportation Problems. Journal of The Society for Industrial and Applied Mathematics, 10:196– 210, 1957.
• [32] Bruno Oliveira and Orlando Belo. ETL Standard Processes Modelling - A Novel BPMN Approach. In International Conference on Enterprise Information Systems, 2013.
• [33] Basel Committee on Banking Supervision. Principles for effective risk data aggregation and risk reporting, 2013.
• [34] Ronald C. Read and Derek G. Corneil. The graph isomorphism disease. J. Graph Theory, 1:339–363, 1977.
• [35] Kaspar Riesen and Horst Bunke. Approximate graph edit distance computation by means of bipartite graph matching. Image Vis. Comput., 27:950–959, 2009.
• [36] Kaspar Riesen, Stefan Fankhauser, and Horst Bunke. Speeding Up Graph Edit Distance Computation with a Bipartite Heuristic. In Mining and Learning with Graphs, 2007.
• [37] Elena Samota. Representing ETL Flows with BPMN 2.0, 2015.
• [38] Francesc Serratosa. Fast computation of Bipartite graph matching. Pattern Recognit. Lett., 45:244–250, 2014.
• [39] Alkis Simitsis. Modeling and managing ETL processes. In VLDB PhD Workshop, 2003.
• [40] Alkis Simitsis. Mapping conceptual to logical models for ETL processes. In International Workshop on Data Warehousing and OLAP, 2005.
• [41] Alkis Simitsis, Panos Vassiliadis, Umeshwar Dayal, Anastasios Karagiannis, and Vasiliki Tziovara. Benchmarking etl workflows. In Raghunath Nambiar and Meikel Poess, editors, Performance Evaluation and Benchmarking, volume 5895, pages 199–220, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg.
• [42] Alkis Simitsis, Panos Vassiliadis, Manolis Terrovitis, and Spiros Skiadopoulos. Graph-Based Modeling of ETL Activities with Multi-level Transformations and Updates. In International Conference on Data Warehousing and Knowledge Discovery, 2005.
• [43] Juan Trujillo and Sergio Luján-Mora. A UML Based Approach for Modeling ETL Processes in Data Warehouses. In International Conference on Conceptual Modeling, 2003.
• [44] Kevin Wilkinson, Alkis Simitsis, Malu Castellanos, and Umeshwar Dayal. Leveraging Business Process Models for ETL Design. In International Conference on Conceptual Modeling, 2010.
• [45] Zhiping Zeng, Anthony K. H. Tung, Jianyong Wang, Jianhua Feng, and Lizhu Zhou. Comparing Stars: On Approximating Graph Edit Distance. Proc. VLDB Endow., 2:25–36, 2009.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).