Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Information Systems and e-Business Management
Erschienen in: Information Systems and e-Business Management 1/2015

01.02.2015 | Original Article

Graph theory and model collection management: conceptual framework and runtime analysis of selected graph algorithms

verfasst von: Dominic Breuker, Patrick Delfmann, Hanns-Alexander Dietrich, Matthias Steinhorst

Erschienen in: Information Systems and e-Business Management | Ausgabe 1/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Analysing conceptual models is a frequent task of business process management (BPM), for instance to support comparison or integration of business processes, to check business processes for compliance or weaknesses, or to tailor conceptual models for different audiences. As recently, many companies have started to maintain large model collections and analysing such collections manually may be laborious, practitioners have articulated a demand for automatic model analysis support. Hence, BPM scholars have proposed a plethora of different model analysis techniques. As virtually any conceptual model can be interpreted as a mathematical graph and model analysis techniques often include some kind of graph problem, in this paper, we introduce a graph algorithm based model analysis framework that can be accessed by specialized model analysis techniques. To prove that basic graph algorithms are feasible to support such a framework, we conduct a performance analysis of selected graph algorithms.
Vorheriger Artikel Measuring precision of modeled behavior
Nächster Artikel Supporting medical ward rounds through mobile task and process management

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Fußnoten
1
See http://​de.​talend.​com/​download for an example of such software.
 
Literatur
Aalst WMP, Hee KM, Hofstede AHM, Sidorova N, Verbeek HMW, Voorhoeve M, Wynn MT (2010) Soundness of workflow nets: classification, decidability, and analysis. Form Asp Comput 23:333–363CrossRef
Awad A (2007) BPMN-Q: a language to query business processes. In: Reichert M, Strecker S, Turowski K (eds) In: Proceedings of the 2nd international workshop on enterprise modelling and information systems architectures (EMISA’07). St. Goar, pp 115–128
Awad A, Sakr S (2010) Querying graph-based repositories of business process models. In: Yoshikawa M, Meng X, Yumoto T, Ma Q, Sun L, Watanabe C (eds) Proceedings of the 15th international workshops on database systems for advanced applications. Springer, Berlin, pp 33–44
Awad A, Polyvyanyy A, Weske M (2008) Semantic querying of business process models. In: 12th international IEEE enterprise distributed object computing conference (EDOC 2008). IEEE, Munich, pp 85–94
Awad A, Decker G, Weske M (2008) Efficient compliance checking using BPMN-Q and temporal logic. In: Dumas M, Reichert M, Shan M-C (eds) Proceedings of the 6th international conference on business process management (BPM’08). Springer, Berlin, pp 326–341
Batra D (2005) Conceptual data modeling patterns. J Database Manag 16:84–106CrossRef
Becker J, Schütte R (2004) Handelsinformationssysteme. Redline Wirtschaft, Frankfurt
Becker J, Breuker D, Weiß B, Winkelmann A (2010a) Exploring the status quo of business process modelling languages in the banking sector—an empirical insight into the usage of methods in banks. 21st Australasian Conference on Information Systems (ACIS 2010). Brisbane, Australia
Becker J, Bergener P, Räckers M, Weiß B, Winkelmann A (2010b) Pattern-based semi-automatic analysis of weaknesses in semantic business process models in the banking sector. Proceedings of the European conference on information systems (ECIS’10). Pretoria, South Africa
Becker J, Breuker D, Delfmann P, Dietrich H-A, Steinhorst M (2012a) Identifying business process activity mappings by optimizing behavioral similarity. In: Proceedings of the 18th Americas conference on information systems (AMCIS 2012). Seattle, Washington
Becker J, Breuker D, Delfmann P, Dietrich H-A, Steinhorst M (2012b) A runtime analysis of graph-theoretical algorithms to detect patterns in process model collections. In: La Rosa M, Soffer P (eds) Proceedings of the 2nd International Workshop on Process Model Collections. Tallinn, Estonia, pp 31–42
Beeri C, Eyal A, Kamenkovich S, Milo T (2005) Querying business processes with BP-QL. In: Proceedings of the 31st international conference on very large data bases (VLDB’05). VLDB Endowment, Trondheim, pp 1255–1258
Beeri C, Eyal A, Kamenkovich S, Milo T (2006) Querying business processes. In: Dayal U, Whang K-Y, Lomet D, Alonso G, Lohman G, Kersten M, Cha SK, Kim Y-K (eds) Proceedings of the 32nd international conference on very large data bases (VLDB’06). VLDB Endowment, Seoul, pp 343–354
Beeri C, Eyal A, Kamenkovich S, Milo T (2008) Querying business processes with BP-QL. Inf Syst 33:477–507CrossRef
Bräuer S, Delfmann P, Dietrich H-A, Steinhorst M (2013) Using a generic model query approach to allow for process model compliance checking—an algorithmic perspective. In: Alt R, Franczyk B (eds) In: Proceedings of the 11th International Conference on Wirtschaftsinformatik (WI) 2013. Universität Leipzig, Leipzig, pp 1245–1259
Brzozowski JA (1962) Canonical regular expressions and minimal state graphs for definite events. Symposium on the mathematical theory of automata. New York, pp 529–561
Cordella LP, Foggia P, Sansone C, Vento M (2004) A (sub)graph isomorphism algorithm for matching large graphs. IEEE Trans Pattern Anal Mach Intell 26:1367–1372CrossRef
Curran TA, Keller G (1998) SAP R/3 business blueprint: business engineering mit den R/3-referenzprozessen. Addison-Wesley, Bonn
Delfmann P, Herwig S, Lis L (2009) Unified enterprise knowledge representation with conceptual models—capturing corporate language in naming conventions. 30th International conference on information systems (ICIS 2009). Phoenix, Arizona
Derguech W, Vulcu G, Bhiri S (2010) An indexing structure for maintaining configurable process models. In: Bider I, Halpin T, Krogstie J, Nurcan S, Proper E, Schmidt R, Ukor R (eds) Enterprise, business-process and information systems modeling. Springer, Berlin, pp 157–168CrossRef
Deutch D, Milo T (2007) Querying structural and behavioral properties of business processes. In: Arenas M, Schwartzbach MI (eds) 11th International symposium on database programming languages (DBPL 2007). Springer, Berlin, pp 169–185
Dijkman R, Dumas M, van Dongen B, Käärik R, Mendling J (2011a) Similarity of business process models: metrics and evaluation. Inf Syst 36:498–516CrossRef
Dijkman R, Gfeller B, Küster J, Völzer H (2011b) Identifying refactoring opportunities in process model repositories. Inf Softw Technol 53:937–948CrossRef
Dijkman R, La Rosa M, Reijers HA (2012) Managing large collections of business process models—current techniques and challenges. Comput Ind 63:91–97CrossRef
Dumas M, García-Bañuelos L, Dijkman R (2009) Similarity search of business process models. IEEE Comput Soc Tech Comm Data Eng 32:23–28
Dumas M, García-Bañuelos L, La Rosa M, Uba R (2013) Fast detection of exact clones in business process model repositories. Inf Syst 38:619–633CrossRef
Ekanayake C, Rosa M, Hofstede AM, Fauvet M-C (2011) Fragment-based version management for repositories of business process models. In: Meersman R, Dillon T, Herrero P, Kumar A, Reichert M, Qing L, Ooi B-C, Damiani E, Schmidt D, White J, Hauswirth M, Hitzler P, Mohania M (eds) On the move to meaningful internet systems: OTM 2011. Springer, Berlin, pp 20–37CrossRef
Ekanayake CC, Dumas M, García-Bañuelos L, La Rosa M, ter Hofstede AHM (2012) Approximate clone detection in repositories of business process models. In: Barros A, Gal A, Kindler E (eds) Proceedings of the 10th international conference on business process management (BPM 2012). Springer, Berlin, pp 302–318
Fahland D, Jobstmann B, Koehler J, Lohmann N, Hagen V, Wolf K (2009) Instantaneous soundness checking of industrial business process models. In: Dayal U, Eder J, Koehler J, Reijers HA (eds) 7th International Conference on Business Process Management (BPM 2009). Springer, Berlin, pp 278–293
Fauvet MC, La Rosa M, Sadegh M, Alshareef A, Dijkman RM, García-Bañuelos L, Reijers HA, van der Aalst WMP, Dumas M, Mendling J (2010) Managing process model collections with AProMoRe. Service-Oriented Computing, pp 699–701
Feja S, Speck A, Witt S, Schulz M (2011) Checkable graphical business process representation. In: Catania B, Ivanović M, Thalheim B (eds) 14th East European conference on advances in databases and information systems (ADBIS 2010). Springer, Berlin, pp 176–189
Fettke P, Loos P (2005) Zur Identifikation von Strukturanalogien in Datenmodellen—Ein Verfahren und seine Anwendung am Beispiel des Y-CIM-Referenzmodells von Scheer. Wirtschaftsinformatik 47:89–100CrossRef
García-Bañuelos L (2008) Pattern identification and classification in the translation from BPMN to BPEL. In: Meersman R, Tari Z (eds) Proceedings of the international conference on the move to meaningful internet systems (OTM’08). Springer, Berlin, pp 436–444
Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman and Company, New York
Gottschalk F, Aalst WP, Jansen-Vullers M (2008a) Merging event-driven process chains. In: Meersman R, Tari Z (eds) On the move to meaningful internet systems (OTM 2008). Springer, Berlin, pp 418–426CrossRef
Gottschalk F, van der Aalst WMP, Jansen-Vullers MH, La Rosa M (2008b) Configurable workflow models. Int J Coop Inf Syst 17:177–221CrossRef
Hallerbach A, Bauer T, Reichert M (2009) Capturing variability in business process models: the provop approach. J Softw Maint Evol Res Pract 22:519–546CrossRef
Hopcroft JE (1971) An n log n algorithm for minimizing states in a finite automaton. In: Kohavi Z (ed) Theory of machines and computations. Academic Press, London, pp 189–196CrossRef
Hopcroft JE, Motwani R, Ullman JD (2008) Introduction to automata theory, languages, and computation. Pearson Education
Houy C, Fettke P, Loos P, Aalst WMP, Krogstie J (2011) Business process management in the large. Bus Inf Syst Eng 3:385–388CrossRef
Huffman DA (1954) The synthesis of sequential switching circuits. J Frankl Inst 257:161–190CrossRef
Jin T, Wang J, Wu N, La Rosa M, Ter Hofstede AHM (2010) Efficient and accurate retrieval of business process models through indexing. In: Meersman R, Dillon T, Herrero P (eds) Proceedings of the 2010 international conference on on the move to meaningful internet systems (OTM’10). Springer, Berlin, pp 402–409
Jin T, Wang J, Wen L (2011a) Efficient retrieval of similar business process models based on structure. In: Meersman R, Dillon T, Herrero P, Kumar A, Reichert M, Qing L, Ooi B-C, Damiani E, Schmidt D, White J, Hauswirth M, Hitzler P, Mohania M (eds) On the move to meaningful internet systems (OTM 2011). Springer, Berlin, pp 56–63CrossRef
Jin T, Wang J, Wen L (2011b) Querying business process models based on semantics. In: Yu JX, Kim MH, Unland R (eds) 16th International conference on database systems for advanced applications (DASFAA 2011). Springer, Berlin, pp 164–178
Jin T, Wang J, Wen L (2012) Efficient retrieval of similar workflow models based on behavior. In: Sheng QZ, Wang GSC, Xu G (eds) 14th Asia-Pacific web conference (APWeb 2012). Springer, Berlin, pp 677–684
Knuplesch D, Ly L, Rinderle-Ma S, Pfeifer H, Dadam P (2010) On enabling data-aware compliance checking of business process models. In: Parsons J, Saeki M, Shoval P, Woo C, Wand Y (eds) 29th International conference on conceptual modeling (ER 2010). Springer, Berlin, pp 332–346
Koch I (2001) Enumerating all connected maximal common subgraphs in two graphs. Theor Comput Sci 250:1–30CrossRef
Kunze M, Weske M (2011) Metric trees for efficient similarity search in large process model repositories. In: Muehlen M, Su J (eds) Business process management workshops. Springer, Berlin, pp 535–546CrossRef
Kunze M, Weidlich M, Weske M (2011) Behavioral similarity—a proper metric. In: Rinderle-Ma S, Toumani F, Wolf K (eds) 9th International conference on business process management (BPM 2011). Springer, Berlin, pp 166–181
La Rosa M, Dumas M, Uba R, Dijkman R (2010) Merging business process models. In: Meersman R, Dillon T, Herrero P (eds) On the move to meaningful internet systems: OTM 2010. Springer, Berlin, pp 96–113CrossRef
La Rosa M, Reijers HA, van der Aalst WMP, Dijkman RM, Mendling J, Dumas M, García-Bañuelos L (2011a) APROMORE: an advanced process model repository. Expert Syst Appl 38:7029–7040CrossRef
La Rosa M, Dumas M, ter Hofstede AHM, Mendling J (2011b) Configurable multi-perspective business process models. Inf Syst 36:313–340CrossRef
La Rosa M, Dumas M, Uba R, Dijkman R (2013) Business process model merging: an approach to business process consolidation. ACM Trans Softw Eng Methodol 22:1–42CrossRef
Levenshtein VI (1966) Binary codes capable of correcting deletions, insertions, and reversals. Sov Phys Dokl 10:707–710
Levi G (1973) A note on the derivation of maximal common subgraphs of two directed or undirected graphs. Calcolo 9:341–352CrossRef
Li C, Reichert M, Wombacher A (2009) Discovering reference models by mining process variants using a heuristic approach. In: Dayal U, Eder J, Koehler J, Reijers HA (eds) 7th International Conference on Business Process Management (BPM 2009). Springer, Berlin, pp 344–362
Li C, Reichert M, Wombacher A (2010) The minadept clustering approach for discovering reference process models out of process variants. Int J Coop Inf Syst 19:159–203CrossRef
Lincoln M, Gal A (2011) Searching business process repositories using operational similarity. In: Meersman R, Dillon T, Herrero P, Kumar A, Reichert M, Qing L, Ooi B-C, Damiani E, Schmidt D, White J, Hauswirth M, Hitzler P, Mohania M (eds) International conference on the move to meaningful internet systems (OTM 2011). Springer, Berlin, pp 2–19
Lu R, Sadiq S, Governatori G (2009) On managing business processes variants. Data Knowl Eng 68:642–664CrossRef
Mahleko B, Wombacher A (2006) Indexing business processes based on annotated finite state automata. In: 2006 IEEE International Conference on Web Services (ICWS’06). IEEE, Washington, pp 303–311
Marc W, Meinl T, Fischer I, Philippsen M (2005) A quantitative comparison of the subgraph miners MoFa, gSpan, FFSM, and Gaston. In: Jorge AM, Torgo L, Brazdil P, Camacho R, Gama J (eds) 9th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD 2005). Springer, Berlin, pp 392–403
McGregor JJ (1982) Backtrack search algorithms and the maximal common subgraph problem. Softw Pract Exp 12:23–34CrossRef
Mendling J, Simon C (2006) Business process design by view integration. In: Eder J, Dustdar S (eds) Business process management workshops. Springer, Berlin, pp 55–64CrossRef
Mendling J, Neumann G, van der Aalst WMP (2007) Understanding the occurrence of errors in process models based on metrics. In: Meersman R, Tari Z (eds) On the move to meaningful internet systems (OTM 2007). Springer, Berlin, pp 113–130
Mendling J, Verbeek HMW, van Dongen BF, van der Aalst WMP, Neumann G (2008) Detection and prediction of errors in EPCs of the SAP reference model. Data Knowl Eng 64:312–329CrossRef
Momotko M, Subieta K (2004) Process query language: a way to make workflow processes more flexible. In: Benczúr A, Demetrovics J, Gottlob G (eds) 8th East European conference on advances in databases and information systems (ADBIS 2004). Springer, Berlin, pp 306–321
Nijssen S, Kok JN (2005) The gaston tool for frequent subgraph mining. Electron Notes Theor Comput Sci 127:77–87CrossRef
Nijssen S, Kok JN (2006) Frequent subgraph miners: runtimes don’t say everything. international workshop on mining and learning with graphs (MLG 2006), pp 173–180
Ouyang C, Dumas M, Arthur HM, van der Aalst WMP (2008) Pattern-Based translation of BPMN process models to BPEL web services. Int J Web Serv Res 5:42–62CrossRef
Pascalau E, Awad A, Sakr S, Weske M (2011) On maintaining consistency of process model variants. In: Muehlen M, Su J (eds) Business process management workshops. Springer, Berlin, pp 289–300CrossRef
Polyvyanyy A, Smirnov S, Weske M (2010) Business process model abstraction. In: Brocke J, Rosemann M (eds) Handbook on business process management 1. Springer, Berlin, pp 149–166CrossRef
Qiao M, Akkiraju R, Rembert AJ (2011) Towards efficient business process clustering and retrieval: combining language modeling and structure matching. In: Rinderle-Ma S, Toumani F, Wolf K (eds) 9th International conference on business process management (BPM 2011). Springer, Berlin, pp 199–214
Rahm E, Bernstein PA (2001) A survey of approaches to automatic schema matching. VLDB J 10:334–350CrossRef
Reijers HA, Mans RS, van der Toorn RA (2009) Improved model management with aggregated business process models. Data Knowl Eng 68:221–243CrossRef
Reijers HA, Mendling J, Dijkman RM (2011) Human and automatic modularizations of process models to enhance their comprehension. Inf Syst 36:881–897CrossRef
Rosemann M (2006) Potential pitfalls of process modeling: part A. Bus Process Manag J 12:249–254CrossRef
Rosemann M, van der Aalst WMP (2007) A configurable reference modelling language. Inf Syst 32:1–23CrossRef
Sakr S, Awad A (2010) A framework for querying graph-based business process models. In: Proceedings of the 19th international conference on World Wide Web (WWW’10). ACM Press, New York, pp 1297–1300
Scheer A-W (1992) Architecture of integrated information systems: foundations of enterprise modelling. Springer, BerlinCrossRef
Scheidegger CE, Vo HT, Koop D, Freire J, Silva CT, Silva T (2008) Querying and re-using workflows with VsTrails. In: Proceedings of the 2008 ACM SIGMOD international conference on Management of data—SIGMOD’08. ACM Press, New York, pp 1251–1254
Shao Q, Sun P, Chen Y (2009) WISE: a workflow information search engine. In: 25th International conference on data engineering (ICDE’09). IEEE, Shanghai, pp 1491–1494
Sun S, Kumar A, Yen J (2006) Merging workflows: a new perspective on connecting business processes. Decis Support Syst 42:844–858CrossRef
Thomas O, Fellmann MA (2009) Semantic process modeling—design and implementation of an ontology-based representation of business processes. Bus Inf Syst Eng 1:438–451CrossRef
Ullmann JR (1976) An algorithm for subgraph isomorphism. J ACM 23:31–42CrossRef
Van der Aalst WMP (1998) The APPLICATION OF PETRI NETS TO WORKflOW MANAGEMENT. J Circuits Syst Comput 08:21–66CrossRef
Van der Aalst WMP (2013) Business process management: a comprehensive survey. ISRN Softw Eng 2013:1–37CrossRef
Vardi MY (2007) Automata-theoretic model checking revisited. In: Cook B, Podelski A (eds) Verification, model checking, and abstract interpretation (VMCAI 2007). Springer, Berlin, pp 137–150CrossRef
Wang J, Jin T, Wong RK, Wen L (2013) Querying business process model repositories—a survey of current approaches and issues. World Wide Web
Weber B, Reichert M, Mendling J, Reijers HA (2011) Refactoring large process model repositories. Comput Ind 62:467–486CrossRef
Weidlich M, Mendling J, Weske M (2011) A foundational approach for managing process variability. In: Mouratidis H, Rolland C (eds) 23rd International conference on advanced information systems engineering (CAiSE 2011). Springer, Berlin, pp 267–282
Welling R (2011) A performance analysis on maximal common subgraph algorithms. In: 15th Twente Student Conference on IT., Enschede, Netherlands
Wynn M, Verbeek HMW, van der Aalst WMP, ter Hofstede AHM, Edmond D (2009) Business process verification—finally a reality! Bus Process Manag J 15:74–92CrossRef
Yan X, Han J (2002) gSpan: graph-based substructure pattern mining. IEEE international conference on data mining. IEEE Comput. Soc, Maebashi City, Japan, pp 721–724
Yan Z, Dijkman R, Grefen P (2012) Fast business process similarity search. Distrib Parallel Databases 30:105–144CrossRef
Metadaten
Titel
Graph theory and model collection management: conceptual framework and runtime analysis of selected graph algorithms
verfasst von
Dominic Breuker
Patrick Delfmann
Hanns-Alexander Dietrich
Matthias Steinhorst
Publikationsdatum
01.02.2015
Verlag
Springer Berlin Heidelberg
Erschienen in
Information Systems and e-Business Management / Ausgabe 1/2015
Print ISSN: 1617-9846
Elektronische ISSN: 1617-9854
DOI
https://doi.org/10.1007/s10257-014-0243-6

Weitere Artikel der Ausgabe 1/2015

Information Systems and e-Business Management 1/2015 Zur Ausgabe

Original Article

A visual analysis of the process of process modeling

Editorial

Special issue on best papers from the “BPM 2012” workshops

Original Article

Measuring precision of modeled behavior

Original Article

A model-driven approach for event-based business process monitoring

Original Article

Supporting medical ward rounds through mobile task and process management

Premium Partner

    Bildnachweise