research-article

N-way model merging

Authors:

Marsha ChechikAuthors Info & Claims

ESEC/FSE 2013: Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering

Pages 301 - 311

https://doi.org/10.1145/2491411.2491446

Published: 18 August 2013 Publication History

Abstract

Model merging is widely recognized as an essential step in a variety of software development activities. During the process of combining a set of related products into a product line or consolidating model views of multiple stakeholders, we need to merge multiple input models into one; yet, most of the existing approaches are applicable to merging only two models. In this paper, we define the n-way merge problem. We show that it can be reduced to the known and widely studied NP-hard problem of weighted set packing. Yet, the approximation solutions for that problem do not scale for real-sized software models. We thus evaluate alternative approaches of merging models that incrementally process input models in small subsets and propose our own algorithm that considerably improves precision over such approaches without sacrificing performance.

References

[1]

S. Apel, J. Liebig, B. Brandl, C. Lengauer, and C. Kästner. Semistructured Merge: Rethinking Merge in Revision Control Systems. In Proc. of ESEC/FSE’11, pages 190–200, 2011.

Digital Library

[2]

E. M. Arkin and R. Hassin. On Local Search for Weighted k-Set Packing. Mathematics of Operations Research, 23(3):640–648, 1998.

[3]

P. Berman. A d/2 Approximation for Maximum Weight Independent Set in d-Claw Free Graphs. In Proc. of SWAT’00, volume 1851 of LNCS, pages 214–219, 2000.

Digital Library

[4]

G. Brunet, M. Chechik, S. Easterbrook, S. Nejati, N. Niu, and M. Sabetzadeh. A Manifesto for Model Merging. In Proc. of GaMMa’06, pages 5–12, 2006.

Digital Library

[5]

B. Chandra and M. M. Halldórsson. Greedy Local Improvement and Weighted Set Packing Approximation. J. Algorithms, 39(2):223–240, 2001.

Digital Library

[6]

A. Duley, C. Spandikow, and M. Kim. A Program Differencing Algorithm for Verilog HDL. In Proc. of ASE’10, pages 477–486, 2010.

Digital Library

[7]

S. Duszynski, J. Knodel, and M. Becker. Analyzing the Source Code of Multiple Software Variants for Reuse Potential. In Proc. of WCRE’11, pages 303–307, 2011.

Digital Library

[8]

J. Edmonds and R. M. Karp. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. J. ACM, 19(2):248–264, 1972.

Digital Library

[9]

B. Fluri, M. Wuersch, M. Pinzger, and H. Gall. Change Distilling: Tree Differencing for Fine-Grained Source Code Change Extraction. IEEE TSE, 33:725–743, 2007.

Digital Library

[10]

P. Frenzel, R. Koschke, A. P. J. Breu, and K. Angstmann. Extending the Reflexion Method for Consolidating Software Variants into Product Lines. In Proc. of WCRE’07, pages 160–169, 2007.

Digital Library

[11]

D. Jackson and D. A. Ladd. Semantic Diff: A Tool for Summarizing the Effects of Modifications. In Proc. of ICSM’94, pages 243–252, 1994.

Digital Library

[12]

C. Kästner and S. Apel. Integrating Compositional and Annotative Approaches for Product Line Engineering. In Proc. of GPCE Wrksp. on Modul., Comp. and Gen. Tech. for PLE (McGPLE), pages 35–40, 2008.

[13]

U. Kelter, J. Wehren, and J. Niere. A Generic Difference Algorithm for UML Models. In Software Engineering, volume 64 of LNI, pages 105–116. GI, 2005.

[14]

S. Kpodjedo, F. Ricca, P. Galinier, G. Antoniol, and Y.-G. Gueheneuc. MADMatch: Many-to-many Approximate Diagram Matching for Design Comparison. IEEE TSE, 2013.

Digital Library

[15]

H. W. Kuhn. The Hungarian Method for the Assignment Problem. Naval Research Logistics Quarterly, 2:83–97, 1955.

[16]

S. Nejati, M. Sabetzadeh, M. Chechik, S. Easterbrook, and P. Zave. Matching and Merging of Statecharts Specifications. In Proc. of ICSE’07, pages 54–64, 2007.

Digital Library

[17]

Y. T. Rad and R. Jabbari. Use of Global Consistency Checking for Exploring and Refining Relationships between Distributed Models: A Case Study. Master’s thesis, Blekinge Institute of Technology, School of Computing, January 2012.

[18]

J. Rubin and M. Chechik. Combining Related Products into Product Lines. In Proc. of FASE’12, pages 285–300, 2012.

Digital Library

[19]

J. Rubin and M. Chechik. Quality of Merge-Refactorings for Product Lines. In Proc. of FASE’13, pages 83–98, 2013.

Digital Library

[20]

M. Sabetzadeh and S. Easterbrook. View Merging in the Presence of Incompleteness and Inconsistency. Requirements Engineering J., 11:174–193, June 2006.

Digital Library

[21]

Z. Xing and E. Stroulia. UMLDiff: an Algorithm for Object-Oriented Design Differencing. In Proc. of ASE’05, pages 54–65, 2005.

Digital Library

Cited By

Tavassoli SKhosravi R(2024)Efficient construction of family-based behavioral models from adaptively learned modelsSoftware and Systems Modeling10.1007/s10270-024-01199-5Online publication date: 7-Aug-2024
https://doi.org/10.1007/s10270-024-01199-5
He XLiu YHe H(2024)Accelerating similarity-based model matching using dual hashingSoftware and Systems Modeling10.1007/s10270-024-01173-1Online publication date: 29-Apr-2024
https://doi.org/10.1007/s10270-024-01173-1
Acher MMartinez J(2023)Generative AI for Reengineering Variants into Software Product LinesProceedings of the 27th ACM International Systems and Software Product Line Conference - Volume B10.1145/3579028.3609016(57-66)Online publication date: 28-Aug-2023
https://dl.acm.org/doi/10.1145/3579028.3609016
Show More Cited By

Index Terms

N-way model merging
1. Social and professional topics
  1. Professional topics
    1. Management of computing and information systems
      1. Software management
        Software maintenance
2. Software and its engineering
  1. Software creation and management

Recommendations

Business Process Model Merging: An Approach to Business Process Consolidation

This article addresses the problem of constructing consolidated business process models out of collections of process models that share common fragments. The article considers the construction of unions of multiple models (called merged models) as well ...
3-D models merging based on cost optimization
ICIMCS '15: Proceedings of the 7th International Conference on Internet Multimedia Computing and Service

Model merging is growing to be of great need with the development of 3D modeling and incremental manufacturing. Most current solutions for model merging are by hand. Researches in automatic merging only work in their own simple merging scenarios. This ...
Merging of Use Case Models: Semantic Foundations
TASE '09: Proceedings of the 2009 Third IEEE International Symposium on Theoretical Aspects of Software Engineering

Use case models are the artifact of choice for capturing functional requirements. This typically collaborative activity makes merging a necessity. Use cases however, are often neglected when it comes to model merging, since they are commonly treated as ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ESEC/FSE 2013: Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering

August 2013

738 pages

ISBN:9781450322379

DOI:10.1145/2491411

General Chair:
Bertrand Meyer
ETH Zurich, Switzerland
,
Program Chairs:
Luciano Baresi
Politecnico di Milano, Italy
,
Mira Mezini
TU Darmstadt, Germany

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSOFT: ACM Special Interest Group on Software Engineering

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 August 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ESEC/FSE'13

Sponsor:

SIGSOFT

ESEC/FSE'13: Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering

August 18 - 26, 2013

Saint Petersburg, Russia

Acceptance Rates

Overall Acceptance Rate 112 of 543 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

53
Total Citations
View Citations
553
Total Downloads

Downloads (Last 12 months)50
Downloads (Last 6 weeks)8

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tavassoli SKhosravi R(2024)Efficient construction of family-based behavioral models from adaptively learned modelsSoftware and Systems Modeling10.1007/s10270-024-01199-5Online publication date: 7-Aug-2024
https://doi.org/10.1007/s10270-024-01199-5
He XLiu YHe H(2024)Accelerating similarity-based model matching using dual hashingSoftware and Systems Modeling10.1007/s10270-024-01173-1Online publication date: 29-Apr-2024
https://doi.org/10.1007/s10270-024-01173-1
Acher MMartinez J(2023)Generative AI for Reengineering Variants into Software Product LinesProceedings of the 27th ACM International Systems and Software Product Line Conference - Volume B10.1145/3579028.3609016(57-66)Online publication date: 28-Aug-2023
https://dl.acm.org/doi/10.1145/3579028.3609016
Michelon GMartinez JSotto-Mayor BArrieta AAssunção WAbreu REgyed A(2023)Spectrum-based feature localization for families of systemsJournal of Systems and Software10.1016/j.jss.2022.111532195:COnline publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1016/j.jss.2022.111532
Adhikari BRapos EStephan M(2023)SimIMA: a virtual Simulink intelligent modeling assistantSoftware and Systems Modeling10.1007/s10270-023-01093-623:1(29-56)Online publication date: 13-Mar-2023
https://doi.org/10.1007/s10270-023-01093-6
Yang SSahraoui HKühn TSousa V(2022)Towards automatically extracting UML class diagrams from natural language specificationsProceedings of the 25th International Conference on Model Driven Engineering Languages and Systems: Companion Proceedings10.1145/3550356.3561592(396-403)Online publication date: 23-Oct-2022
https://dl.acm.org/doi/10.1145/3550356.3561592
He XTang LLi YSyriani ESahraoui H(2022)Accelerating similarity-based model matching using on-the-fly similarity preserving hashingProceedings of the 25th International Conference on Model Driven Engineering Languages and Systems10.1145/3550355.3552406(244-254)Online publication date: 23-Oct-2022
https://dl.acm.org/doi/10.1145/3550355.3552406
Kasaei MSharbaf MZamani B(2022)A Rule-Based Language for Configurable N-way Model Matching2022 12th International Conference on Computer and Knowledge Engineering (ICCKE)10.1109/ICCKE57176.2022.9960014(129-135)Online publication date: 17-Nov-2022
https://doi.org/10.1109/ICCKE57176.2022.9960014
Kasaei MSharbaf MZamani B(2022)Towards a Formalism for Specifying N-way Model Merging Rules2022 27th International Computer Conference, Computer Society of Iran (CSICC)10.1109/CSICC55295.2022.9780481(1-7)Online publication date: 23-Feb-2022
https://doi.org/10.1109/CSICC55295.2022.9780481
Liu CMacedo NCunha A(2022)Merging cloned Alloy models with colorful refactoringsScience of Computer Programming10.1016/j.scico.2022.102829220(102829)Online publication date: Aug-2022
https://doi.org/10.1016/j.scico.2022.102829
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents