×

zbMATH — the first resource for mathematics

Rete network slicing for model queries. (English) Zbl 1344.68113
Echahed, Rachid (ed.) et al., Graph transformation. 9th international conference, ICGT 2016, in memory of Hartmut Ehrig, held as part of STAF 2016, Vienna, Austria, July 5–6, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-40529-2/pbk; 978-3-319-40530-8/ebook). Lecture Notes in Computer Science 9761, 137-152 (2016).
Summary: Declarative model queries captured by graph patterns are frequently used in model driven engineering tools for the validation of well-formedness constraint or the calculation of various model metrics. However, their high level nature might make it hard to understand all corner cases of complex queries. When debugging erroneous patterns, a common task is to identify which conditions or constraints of a query caused some model elements to appear in the results. Slicing techniques in traditional programming environments are used to calculate similar dependencies between program statements. Here, we introduce a slicing approach for model queries based on Rete networks, a cache structure applied for the incremental evaluation of model queries. The proposed method reuses the structural information encoded in the Rete networks to calculate and present a trace of operations resulting in some model elements to appear in the result set. The approach is illustrated on a running example of validating well-formedness over UML state machine models using graph patterns as a model query formalism.
For the entire collection see [Zbl 1339.68007].
MSC:
68Q42 Grammars and rewriting systems
68N99 Theory of software
68R10 Graph theory (including graph drawing) in computer science
Software:
Drools; JBoss; VIATRA2
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Reder, A., Egyed, A.: Incremental consistency checking for complex design rules and larger model changes. In: France, R.B., Kazmeier, J., Breu, R., Atkinson, C. (eds.) MODELS 2012. LNCS, vol. 7590, pp. 202–218. Springer, Heidelberg (2012) · Zbl 06240231 · doi:10.1007/978-3-642-33666-9_14
[2] Bergmann, G., Horváth, A., Ráth, I., Varró, D., Balogh, A., Balogh, Z., Ökrös, A.: Incremental evaluation of model queries over EMF models. In: Rouquette, N., Haugen, Ø., Petriu, D.C. (eds.) MODELS 2010, Part I. LNCS, vol. 6394, pp. 76–90. Springer, Heidelberg (2010) · Zbl 05827688 · doi:10.1007/978-3-642-16145-2_6
[3] Ujhelyi, Z., Hegedüs, A., Bergmann, G., Horváth, A., Ráth, I., Varró, D.: EMF-IncQuery: an integrated development environment for live model queries. Sci. Comput. Program. 98, 80–99 (2015) · doi:10.1016/j.scico.2014.01.004
[4] Hegedüs, A., Horváth, A., Ráth, I., Starr, R., Varró, D.: Query-driven soft traceability links for models. Softw. Syst. Model. 1–24 (2014). http://link.springer.com/article/10.1007/s10270-014-0436-y · doi:10.1007/s10270-014-0436-y
[5] Bergmann, G., Ujhelyi, Z., Ráth, I., Varró, D.: A graph query language for EMF models. In: Cabot, J., Visser, E. (eds.) ICMT 2011. LNCS, vol. 6707, pp. 167–182. Springer, Heidelberg (2011) · Zbl 05968259 · doi:10.1007/978-3-642-21732-6_12
[6] Forgy, C.L.: Rete: A fast algorithm for the many pattern/many object pattern match problem. Artif. Intell. 19(1), 17–37 (1982) · doi:10.1016/0004-3702(82)90020-0
[7] Varró, G., Friedl, K., Varró, D.: Adaptive graph pattern matching for model transformations using model-sensitive search plans. Electron. Notes Theoret. Comput. Sci. 152, 191–205 (2006). Proceedings of the International Workshop on Graph and Model Transformation (GraMoT 2005) · doi:10.1016/j.entcs.2005.10.025
[8] Búr, M., Ujhelyi, Z., Horváth, Á., Varró, D.: Local search-based pattern matching features in EMF-IncQuery. In: Parisi-Presicce, F., Westfechtel, B. (eds.) ICGT 2015. LNCS, vol. 9151, pp. 275–282. Springer, Heidelberg (2015) · Zbl 06484121 · doi:10.1007/978-3-319-21145-9_18
[9] Ujhelyi, Z., Horváth, A., Varró, D.: Dynamic backward slicing of model transformations. In: Proceedings of the 2012 IEEE Fifth International Conference on Software Testing, Verification and Validation. ICST 2012, Computer Society , pp. 1–10. IEEE, Washington, DC (2012) · doi:10.1109/ICST.2012.80
[10] Clarisó, R., Cabot, J., Guerra, E., de Lara, J.: Backwards reasoning for model transformations: method and applications. J. Syst. Softw. 116, 113–132 (2016). http://www.sciencedirect.com/science/article/pii/S0164121215001788 · doi:10.1016/j.jss.2015.08.017
[11] Burgueno, L., Troya, J., Wimmer, M., Vallecillo, A.: Static fault localization in model transformations. IEEE Trans. Softw. Eng. 41(5), 490–506 (2015) · doi:10.1109/TSE.2014.2375201
[12] Bergmann, G.: Incremental model queries in model-driven design. Ph.D. dissertation, Budapest University of Technology and Economics, Budapest (2013)
[13] Gurevich, Y.: Sequential abstract-state machines capture sequential algorithms. ACM Trans. Comput. Logic 1(1), 77–111 (2000) · Zbl 1365.68258 · doi:10.1145/343369.343384
[14] The JBoss Project: Drools - The Business Logic integration Platform (2014). http://www.jboss.org/drools
[15] Ghamarian, A., Jalali, A., Rensink, A.: Incremental pattern matching in graph-based state space exploration. Electron. Commun. EASST 32 (2011)
[16] Tip, F.: A survey of program slicing techniques. J. Program. Lang. 3(3), 121–189 (1995)
[17] Xu, B., Qian, J., Zhang, X., Wu, Z., Chen, L.: A brief survey of program slicing. ACM SIGSOFT Softw. Eng. Notes 30(2), 1–36 (2005) · doi:10.1145/1050849.1050865
[18] Varró, D., Balogh, A.: The model transformation language of the VIATRA2 framework. Sci. Comput. Program. 68(3), 214–234 (2007) · Zbl 1131.68040 · doi:10.1016/j.scico.2007.05.004
[19] Leuschel, M., Vidal, G.: Forward slicing by conjunctive partial deduction and argument filtering. In: Sagiv, M. (ed.) ESOP 2005. LNCS, vol. 3444, pp. 61–76. Springer, Heidelberg (2005) · Zbl 1108.68424 · doi:10.1007/978-3-540-31987-0_6
[20] Weber Vasconcelos, W.: A flexible framework for dynamic and static slicing of logic programs. In: Gupta, G. (ed.) PADL 1999. LNCS, vol. 1551, p. 259. Springer, Heidelberg (1999)
[21] Szilágyi, G., Harmath, L., Gyimóthy, T.: The debug slicing of logic programs. Acta Cybernetica 15(2), 257–278 (2001) · Zbl 1006.68022
[22] Szilágyi, G., Gyimóthy, T., Małuszyński, J.: Static and dynamic slicing of constraint logic programs. Autom. Softw. Eng. 9, 41–65 (2002) · Zbl 1034.68678 · doi:10.1023/A:1013280119003
[23] Uzuncaova, E., Khurshid, S.: Kato: A program slicing tool for declarative specifications. In: 29th International Conference on Software Engineering, pp. 767–770. IEEE (2007) · doi:10.1109/ICSE.2007.47
[24] Cui, Y., Widom, J., Wiener, J.L.: Tracing the lineage of view data in a warehousing environment. ACM Trans. Database Syst. 25(2), 179–227 (2000) · doi:10.1145/357775.357777
[25] Freire, J., Koop, D., Santos, E., Silva, C.T.: Provenance for computational tasks: a survey. Comput. Sci. Eng. 10(3), 11–21 (2008) · Zbl 05333439 · doi:10.1109/MCSE.2008.79
[26] Kagdi, H., Maletic, J.I., Sutton, A.: Context-free slicing of UML class models. In: 21st International Conference on Software Maintenance ICSM 2005, pp. 635–638. IEEE (2005) · doi:10.1109/ICSM.2005.34
[27] Schaefer, I., Poetzsch-Heffter, A.: Slicing for model reduction in adaptive embedded systems development. In: International Workshop on Software Engineering for Adaptive and Self-managing Systems, pp. 25–32. ACM, NewYork (2008) · doi:10.1145/1370018.1370024
[28] Shaikh, A., Clarisó, R., Wiil, U.K., Memon, N.: Verification-driven slicing of UML/OCL models. In: 25th IEEE/ACM International Conference on Automated Software Engineering, pp. 185–194. ACM (2010) · doi:10.1145/1858996.1859038
[29] Lano, K., Kolahdouz-Rahimi, S.: Slicing of UML models using model transformations. In: Petriu, D.C., Rouquette, N., Haugen, Ø. (eds.) MODELS 2010, Part II. LNCS, vol. 6395, pp. 228–242. Springer, Heidelberg (2010) · Zbl 05827727 · doi:10.1007/978-3-642-16129-2_17
[30] Androutsopoulos, K., Clark, D., Harman, M., Li, Z., Tratt, L.: Control dependence for extended finite state machines. In: Chechik, M., Wirsing, M. (eds.) FASE 2009. LNCS, vol. 5503, pp. 216–230. Springer, Heidelberg (2009) · Zbl 05535534 · doi:10.1007/978-3-642-00593-0_15
[31] Korel, B., Singh, I., Tahat, L., Vaysburg, B.: Slicing of state-based models. In: IEEE International Conference on Software Maintenance, pp. 34–43 (2003) · doi:10.1109/ICSM.2003.1235404
[32] Lallchandani, J.T., Mall, R.: A dynamic slicing technique for UML architectural models. IEEE Trans. Softw. Eng. 37(6), 737–771 (2011) · doi:10.1109/TSE.2010.112
[33] Sen, S., Moha, N., Baudry, B., Jézéquel, J.-M.: Meta-model Pruning. In: Schürr, A., Selic, B. (eds.) MODELS 2009. LNCS, vol. 5795, pp. 32–46. Springer, Heidelberg (2009)
[34] Bae, J.H., Lee, K., Chae, H.S.: Modularization of the UML metamodel using model slicing. In: 3rd International Conference on Information Technology: New Generations, IEEE, pp. 1253–1254 (2008) · doi:10.1109/ITNG.2008.179
[35] Blouin, A., Combemale, B., Baudry, B., Beaudoux, O.: Modeling model slicers. In: Whittle, J., Clark, T., Kühne, T. (eds.) MODELS 2011. LNCS, vol. 6981, pp. 62–76. Springer, Heidelberg (2011) · Zbl 05981763 · doi:10.1007/978-3-642-24485-8_6
[36] Dhoolia, P., Mani, S., Sinha, V.S., Sinha, S.: Debugging model-transformation failures using dynamic tainting. In: D’Hondt, T. (ed.) ECOOP 2010. LNCS, vol. 6183, pp. 26–51. Springer, Heidelberg (2010) · Zbl 05773888 · doi:10.1007/978-3-642-14107-2_3
[37] Mani, S., Sinha, V.S., Dhoolia, P., Sinha, S.: Automated support for repairing input-model faults. In: 25th IEEE/ACM International Conference on Automated Software Engineering, pp. 195–204. ACM (2010) · doi:10.1145/1858996.1859039
[38] Schoenboeck, J., Kappel, G., Kusel, A., Retschitzegger, W., Schwinger, W., Wimmer, M.: Catch me if you can – debugging support for model transformations. In: Ghosh, S. (ed.) MODELS 2009. LNCS, vol. 6002, pp. 5–20. Springer, Heidelberg (2010) · Zbl 05694372 · doi:10.1007/978-3-642-12261-3_2
[39] Seifert, M., Katscher, S.: Debugging triple graph grammar-based model transformations. In: Fujaba Days, pp. 19–25 (2008)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.