Breakthroughs and Limitations of XML Grammar Similarity

Abstract

W3C’s XML (eXtensible Mark-up Language) has recently gained unparalleled importance as a fundamental standard for efficient data management and exchange. The use of XML covers data representation and storage, database information interchange, data filtering, as well as Web applications interaction and interoperability. XML has been intensively exploited in the multimedia field as an effective and standard means for indexing, storing, and retrieving complex multimedia objects. SVG1, SMIL2, X3D3 and MPEG-74 are only some examples of XML-based multimedia data representations. With the ever-increasing Web exploitation of XML, there is an emergent need to automatically process XML documents and grammars for similarity classification and clustering, information extraction, and search functions. All these applications require some notion of structural similarity, XML representing semi-structured data. In this area, most work has focused on estimating similarity between XML documents (i.e., data layer). Nonetheless, few efforts have been dedicated to comparing XML grammars (i.e., type layer). Computing the structural similarity between XML documents is relevant in several scenarios such as change management (Chawathe, Rajaraman, Garcia- Molina, & Widom, 1996; Cobéna, Abiteboul, & Marian, 2002), XML structural query systems (finding and ranking results according to their similarity) (Schlieder, 2001; Zhang, Li, Cao, & Zhu, 2003) as well as the structural clustering of XML documents gathered from the Web (Dalamagas, Cheng, Winkel, & Sellis, 2006; Nierman & Jagadish, 2002). On the other hand, estimating similarity between XML grammars is useful for data integration purposes, in particular the integration of DTDs/schemas that contain nearly or exactly the same information but are constructed using different structures (Doan, Domingos, & Halevy, 2001; Melnik, Garcia-Molina, & Rahm, 2002). It is also exploited in data warehousing (mapping data sources to warehouse schemas) as well as XML data maintenance and schema evolution where we need to detect differences/updates between different versions of a given grammar/schema to consequently revalidate corresponding XML documents (Rahm & Bernstein, 2001). The goal of this article is to briefly review XML grammar structural similarity approaches. Here, we provide a unified view of the problem, assessing the different aspects and techniques related to XML grammar comparison. The remainder of this article is organized as follows. The second section presents an overview of XML grammar similarity, otherwise known as XML schema matching. The third section reviews the state of the art in XML grammar comparison methods. The fourth section discusses the main criterions characterizing the effectiveness of XML grammar similarity approaches. Conclusions and current research directions are covered in the last section.

Key Terms in this Chapter

Schema Matching: It is generally viewed as the process of finding correspondences between elements of two schemas/grammars. The schema matching operator can be defined as a function that takes two schemas, S1 and S2, as input and returns a mapping between those schemas as output

XML Grammar: It is a structure specifying the elements and attributes of an XML document, as well as how these elements/attributes interact together in the document ?(e.g., DTD – Document Type Definition or XML Schema)

XML: It stands for eXtensible Markup Language, developed by WWW consortium in 1998

Hybrid Matcher: It is a matcher that combines multiple criterions within a single algorithm. In general, these criterions (e.g., element name, data type, repeatability constraints, etc.) are fixed and used in a specific way

Simple Matcher: It is a process that identifies mappings between schema/grammar elements based on a single specific criterion, for example, element name syntactic similarity, element repeatability constraints, and so forth

Composite Matcher: It combines the results of several independently-executed matching algorithms (which can be simple or hybrid). It generally provides more flexibility in performing the matching, as it is possible to select, add, or remove different matching algorithms following the matching task at hand

XML Tree: XML documents represent hierarchically-structured information and can be modeled as trees, that is, Ordered Labeled Trees. Nodes, in an XML tree, represent XML elements/attributes and are labeled with corresponding element tag names