Processing of Incorrect XML Data

• Thesis title in Czech: Zpracování nekorektních XML dat
• Thesis title in English: Processing of Incorrect XML Data
• Key words: XML, validita, opravy
• English key words: XML, validity, corrections
• Academic year of topic announcement: 2008/2009
• Thesis type: diploma thesis
• Thesis language: angličtina
• Department: Department of Software Engineering (32-KSI)
• Supervisor: doc. RNDr. Irena Holubová, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 06.11.2008
• Date of assignment: 06.11.2008
• Date and time of defence: 06.09.2010 00:00
• Date of electronic submission: 06.09.2010
• Date of proceeded defence: 06.09.2010
• Opponents: doc. Mgr. Martin Nečaský, Ph.D.

Guidelines

Since XML has become a de-facto standard for data representation and manipulation, there exists a huge amount of applications having their data represented in XML. The problem is that all such applications assume that their input is correct, i.e. the XML documents are well-formed and valid against eventually existing XML schema. But, according to analyses, almost 50% of real-world XML documents involve various errors and for further processing need to be appropriately corrected or treated specifically.
The aim of this work is a research on possibilities and limitations of techniques for processing and/or correction of incorrect XML data. First of all it is necessary to analyze existing solutions (both theoretical and commercial) and to discuss their advantages and disadvantages. The core of the work should be a proposal and implementation of own approach dealing with the identified disadvantages. The work will include experimental results.

References

Mlynkova, I. - Necasky, M. - Pokorny, J. - Richta, K. - Toman, K. - Toman, V.: Technologie XML - Principy a aplikace v praxi. Grada Publishing, Prague, Czech Republic, zari 2008. ISBN 978-80-247-2725-7.

W3C. W3C Technical Reports and Publications. http://www.w3.org/TR/

HtmlCleaner: http://htmlcleaner.sourceforge.net/

Bertino, E. - Guerrini, G. - Mesiti, M. - Tosetto, L.: Evolving a Set of DTDs According to a Dynamic Set of XML Documents. In EDBT '02, pages 45-66, London, UK, 2002. Springer-Verlag.

Guerrini, G. - Mesiti, M. - Sorrenti, M. A.: XML Schema Evolution: Incremental Validation and Efficient Document Adaptation. In XSym '07, pages 92-106, Berlin, Heidelberg, 2007. Springer.

Rahm, E. - Bernstein, P. A.: An Online Bibliography on Schema Evolution. SIGMOD Rec., 35(4):30-31, 2006.

Preliminary scope of work

XML dokumenty a technologie reprezentují široce akceptovaný standard pro správu a výměnu semistrukturovaných dat. Překvapivě vysoký počet XML dokumentů však obsahuje chyby dobré formovanosti, strukturální validity nebo nekonzistence dat. Cílem této práce je analýza existujících přístupů vedoucí k návrhu nového korekčního systému. Představený model zahrnuje opravy elementů a atributů vůči jednotypovým stromovým gramatikám. Průchodem stavového prostoru automatu na rozpoznávání regulárních výrazů jsme vždy schopni nalézt všechny minimální opravy. Tyto opravy jsou kompaktně reprezentovány rekurzivními multigrafy, které se dají přeložit do konkrétních sekvencí editačních operací modifikujících datové stromy. Navrženy byly čtyři konkrétní algoritmy doplněné o prototypovou implementaci a experimentální výsledky. Nejvíce efektivní algoritmus heuristicky sleduje pouze perspektivní směry oprav a brání jakýmkoli opakovaným výpočtům.

Preliminary scope of work in English

XML documents and related technologies represent widely accepted standard for managing and exchanging semi-structured data. However, surprisingly high number of XML documents is affected by well-formedness errors, structural invalidity or data inconsistencies. The aim of this thesis is the analysis of existing approaches resulting to the proposal of a new correction framework. The introduced model involves repairs of elements and attributes with respect to single type tree grammars. Via the inspection of the state space of an automaton recognising regular expressions, we are always able to find all minimal repairs. These repairs are compactly represented by recursively nested multigraphs, which can be translated to particular sequences of edit operations altering data trees. We have proposed four particular algorithms and provided the prototype implementation supplemented with experimental results. The most efficient algorithm heuristically follows only perspective repair directions and avoids repeated computations using the caching mechanism.