Advanced search
Start date
Betweenand
Related content
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

Approximate XML structure validation based on document-grammar tree similarity

Full text
Author(s):
Tekli, Joe [1] ; Chbeir, Richard [2] ; Traina, Agma J. M. [3] ; Traina, Jr., Caetano [3] ; Fileto, Renato [4]
Total Authors: 5
Affiliation:
[1] LAU, SOE, Dept Elect & Compt Engn, Beirut - Lebanon
[2] UPPA, LIUPPA Lab, F-64200 Anglet - France
[3] Univ Sao Paulo, ICMC, BR-13566590 Sao Carlos, SP - Brazil
[4] Univ Fed Santa Catarina UFSC, BR-88040900 Florianopolis, SC - Brazil
Total Affiliations: 4
Document type: Journal article
Source: INFORMATION SCIENCES; v. 295, p. 258-302, FEB 20 2015.
Web of Science Citations: 8
Abstract

Comparing XML documents with XML grammars, also known as XML document and grammar validation, is useful in various applications such as: XML document classification, document transformation, grammar evolution, XML retrieval, and the selective dissemination of information. While exact (Boolean) XML validation has been extensively investigated in the literature, the more general problem of approximate (similarity-based) XML validation, i.e., document-grammar similarity evaluation, has not yet received strong attention. In this paper, we propose an original method for measuring the structural similarity between an XML document and an XML grammar (DTD or XSD), considering their most common operators that designate constraints on the existence, repeatability and alternativeness of XML elements/attributes (e.g., ?, {*}, MinOccurs, MaxOccurs, etc.). Our approach exploits the concept of tree edit distance, introducing a novel edit distance recurrence and dedicated algorithms to effectively compare XML documents and grammar structures, modeled as ordered labeled trees. Our method also inherently performs exact validation by imposing a maximum similarity threshold (minimum edit distance) on the returned results. We implemented a prototype and conducted several experiments on large sets of real and synthetic XML documents and grammars. Results underline our approach's effectiveness in classifying similar documents with respect to predefined grammars, accurately detecting document and/or grammar modifications, and performing document and grammar relevance ranking. Time and space analysis were also conducted. (C) 2014 Elsevier Inc. All rights reserved. (AU)

FAPESP's process: 10/00330-2 - XML Ranked Keyword Search
Grantee:Joe Tekli
Support Opportunities: Scholarships in Brazil - Post-Doctoral