×

zbMATH — the first resource for mathematics

Rewriting-based repairing strategies for XML repositories. (English) Zbl 1283.68130
Summary: Keeping XML data in a consistent state w.r.t. both structure and content is a burdensome task. To maintain the consistency of ever-larger, complex XML repositories, suitable mechanisms that are able to fix every possible inconsistency are needed. In this article, we present a methodology for semi-automatically repairing faulty XML repositories that can be integrated on top of an existing rewriting-based verification engine. As a formal basis for representing consistency criteria, we use a rule-based description formalism that is realized in the language Maude. Then, starting from a categorization of the kinds of errors that can be found during the verification process, we formulate a stepwise transformation procedure that achieves correctness and completeness of the XML repository w.r.t. its Maude formal specification while strictly observing the structure of the XML documents. With the aim of increasing the level of automation of our repair methodology, we also define two correction strategies and two completion strategies that reduce either the amount of information to be changed or the number of repair actions to be executed in order to deliver an XML repository that is both correct and complete. Finally, we describe a prototype implementation of the repairing tool, which we use for an experimental evaluation of our method with good results.

MSC:
68P05 Data structures
68Q42 Grammars and rewriting systems
Software:
Maude; XCentric; XMark
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alexandre, L.; Coelho, J., A high-level approach to web content verification, Advances in Computer Science, Engineering & Applications, Advances in Intelligent and Soft Computing, 166, 755-764, (2012)
[2] Alpuente, M.; Ballis, D.; Falaschi, M., VERDI: an automated tool for web sites verification, (Alferes, J. J.; Leite, J., Proc. of the 9th European Conference on Logics in Artificial Intelligence (JELIAʼ04), Lecture Notes in Computer Science, vol. 3229, (2004), Springer), 726-729
[3] Alpuente, M.; Ballis, D.; Falaschi, M., A rewriting-based framework for web sites verification, Proc. of 1st Intʼl Workshop on Ruled-Based Programming (RULEʼ04), ENTCS, 124, 1, 41-61, (2005)
[4] Alpuente, M.; Ballis, D.; Falaschi, M., Rule-based verification of web sites, Software Tools for Technology Transfer, 8, 565-585, (2006)
[5] Alpuente, M.; Ballis, D.; Falaschi, M.; Ojeda, P.; Romero, D., An abstract generic framework for web site verification, (Proc. of the 2008 Intʼl Symposium on Applications and the Internet (SAINT 2008), (2008), IEEE Computer Society), 104-110
[6] Alpuente, M.; Ballis, D.; Falaschi, M.; Ojeda, P.; Romero, D., A fast algebraic web verification service, (Proc. of First Intʼl Conference on Web Reasoning and Rule Systems (RR 2007), in, Lecture Notes in Computer Science, vol. 4524, (2007)), 239-248
[7] Alpuente, M.; Ballis, D.; Falaschi, M.; Romero, D., A semi-automatic methodology for reparing faulty web sites, (Proc. of the 4th IEEE Intʼl Conference on Software Engineering and Formal Methods, SEFMʼ06, (2006), IEEE Computer Society Press), 31-40
[8] Alpuente, M.; Ballis, D.; Romero, D., Specification and verification of web applications in rewriting logic, (Formal Methods, Second World Congress FM 2009, Lecture Notes in Computer Science, vol. 5850, (2009), Springer), 790-805
[9] Ballis, D.; Romero, D., Fixing web sites using correction strategies, (Proc. of 2nd Intʼl Workshop on Automated Specification and Verification of Web Systems (WWVʼ06), Paphos, Cyprus, (2007), IEEE Computer Society Press), 11-19
[10] Baxter, I. D.; Ricca, F.; Tonella, P., Web application transformations based on rewrite rules, Information and Software Technology, 44, 811-825, (2002)
[11] Bertossi, L.; Pinto, J., Specifying active rules for database maintenance, (Saake, G.; Schwarz, K.; Türker, C., Transactions and Database Dynamics, 8th Intʼl Workshop on Foundations of Models and Languages for Data and Objects, Lecture Notes in Computer Science, vol. 1773, (1999), Springer), 112-129
[12] Capra, L.; Emmerich, W.; Finkelstein, A.; Nentwich, C., Xlinkit: A consistency checking and smart link generation service, ACM Transactions on Internet Technology, 2, 2, 151-185, (2002)
[13] Clavel, M.; Durán, F.; Eker, S.; Lincoln, P.; Martí-Oliet, N.; Meseguer, J.; Talcott, C., All about maude: A high-performance logical framework, Lecture Notes in Computer Science, vol. 4350, (2007), Springer-Verlag · Zbl 1115.68046
[14] Clavel, M.; Durán, F.; Eker, S.; Lincoln, P.; Martí-Oliet, N.; Meseguer, J.; Talcott, C., The maude 2.0 system, (Rewriting Techniques and Applications (RTA 2003), Lecture Notes in Computer Science, vol. 2706, (2003)), 76-87 · Zbl 1038.68559
[15] Coelho, J.; Florido, M., Type-based static and dynamic website verification, (Intʼl Conference on Internet and Web Applications and Services (ICIW 2007), Le Morne, Mauritius, May 13-19, 2007, (2007), IEEE Computer Society), 32
[16] Coelho, J.; Florido, M., Xcentric: logic programming for XML processing, (Fundulaki, I.; Polyzotis, N., 9th ACM International Workshop on Web Information and Data Management (WIDM 2007), Lisbon, Portugal, November 9, 2007, (2007), ACM), 1-8
[17] Coelho, J.; Dundua, B.; Florido, M.; Kutsia, T., A rule-based approach to XML processing and web reasoning, (Hitzler, P.; Lukasiewicz, T., Web Reasoning and Rule Systems - Fourth International Conference (RR 2010), Proceedings, Bressanone/Brixen, Italy, September 22-24, 2010, Lecture Notes in Computer Science, vol. 6333, (2010), Springer), 164-172
[18] Dershowitz, N.; Plaisted, D., Rewriting, (Handbook of Automated Reasoning, vol. 1, (2001)), 535-610 · Zbl 0992.68123
[19] Henzinger, M. R.; Henzinger, T. A.; Kopke, P. W., Computing simulations on finite and infinite graphs, (IEEE Symp. on Found. of Computer Science, (1995)), 453-462 · Zbl 0938.68538
[20] Hosoya, H.; Pierce, B., Regular expressions pattern matching for XML, (Proc. of 25th ACM SIGPLAN-SIGACT Intʼl Symp. POPL, (2001), ACM), 67-80 · Zbl 1323.68076
[21] Kirchner, C.; Qian, Z.; Singh, P.-K.; Stuber, J., Xemantics: a rewriting calculus-based semantics of XSLT, (2002), Rapport de recherche A01-R-386
[22] Klop, J., Term rewriting systems, (Abramsky, S.; Gabbay, D.; Maibaum, T., Handbook of Logic in Computer Science, vol. I, (1992), Oxford University Press), 1-112
[23] Leuschel, M., Homeomorphic embedding for online termination of symbolic methods, (The Essence of Computation, Lecture Notes in Computer Science, vol. 2566, (2002)), 379-403 · Zbl 1026.68028
[24] Mancarella, P.; Terreni, G.; Toni, F., Web sites repairing through abduction, Electronic Notes in Theoretical Computer Science, 235, 137-152, (2009)
[25] Mayol, E.; Teniente, E., A survey of current methods for integrity constraint maintenance and view updating, (Proc. of Advances in Conceptual Modeling (ER ʼ99), Lecture Notes in Computer Science, vol. 1727, (1999), Springer), 62-73
[26] Meseguer, J., Twenty years of rewriting logic, Journal of Logic and Algebraic Programming, 81, 7-8, 721-781, (October-November 2012)
[27] MessageAUTOMATION Validator, available at http://www.messageautomation.com/products/validator.html, 2010.
[28] Martí-Oliet, N.; Palomino, M.; Verdejo, A., Rewriting logic bibliography by topic: 1990-2011, Journal of Logic and Algebraic Programming, 81, 7-8, 782-815, (October-November 2012)
[29] Nentwich, C.; Emmerich, W.; Finkelstein, A., Consistency management with repair actions, (Proc. of the 25th Intʼl Conference on Software Engineering, ICSEʼ03, (2003), IEEE Computer Society), 455-464
[30] Scheffczyk, J.; Borghoff, U. M.; Rödig, P.; Schmitz, L., Consistent document engineering: formalizing type-safe consistency rules for heterogeneous repositories, (Proc. of the 2003 ACM Symposium on Document Engineering (DocEng ʼ03), (2003), ACM Press), 140-149
[31] Scheffczyk, J.; Rödig, P.; Borghoff, U. M.; Schmitz, L., Managing inconsistent repositories via prioritized repairs, (Proc. of the 2004 ACM Symposium on Document Engineering (DocEng ʼ04), (2004), ACM Press), 137-146
[32] Scheffczyk, J.; Rödig, P.; Borghoff, U. M.; Schmitz, L., S-DAGs: towards efficient document repair generation, (Proc. of the 2nd Intʼl Conference on Computing, Communications and Control Technologies, vol. 2, (2004)), 308-313
[33] Schmidt, A.; Waas, F.; Kersten, M. L.; Carey, M. J.; Manolescu, I.; Busse, R., Xmark: A benchmark for XML data management, (VLDB 2002, Proceedings of 28th Intʼl Conference on Very Large Data Bases, Hong Kong, China, August 20-23, (2002)), 974-985
[34] (TeReSe, Term Rewriting Systems, (2003), Cambridge University Press Cambridge, UK) · Zbl 1030.68053
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.