Synopsis Data Structures for XML Databases

Introduction

XML plays a leading role in the vest of “neutral” language/data-specification-format for next-generation Intelligent Information Systems, where the heterogeneity of data and processes pose novel and previously-unrecognized research challenges, beyond classical issues of conventional Database Systems. In fact, XML allows us to nicely overcome structural as well as semantic heterogeneities of distributed databases, such as those one can find in a P2P network. For these reasons, XML databases are becoming the most popular ones in distributed environments (e.g., Bonifati & Cuzzocrea, 2007).

Apart from data/schema integration, XML is also extremely useful in a wide spectrum of novel application scenarios, such as schema mappings, data exchange, and metadata management. On the other hand, XML processing is gaining momentum as it affects the reliability and performance of many computationally intensive applications, ranging from the recent Web-based and Grid-based infrastructures to the more traditional integrated and cooperative information systems. Looking at practical application scenarios, XML processing and management is relevant for a plethora of cases, ranging from social networks to Geographical Information Systems (GIS) and emerging Cloud environments.

In all such cases, efficiently querying native XML databases is a critical issue, due to the evidence that non-native databases may be too inefficient. This is due to several motivations, among which relevant ones are: (i) the XML data model is hierarchical in nature and not prone to be represented as a set of relations or objects; (ii) quite often, XML documents appear in a schema-less fashion (e.g., like those of corporate B2B and B2C e-commerce Web systems), thus making the relational translation more difficult; (iii) the inherent “richness” of the standard XML query language, which defines a comprehensive class of queries with possibly complex syntax and predicates (e.g., for clause of XQuery queries (Chamberlin et al., 2001), twig XML queries (Chamberlin et al., 2001), partial- and exact-match XPath queries (Clark & DeRose, 1999) etc.); (iv) the ambiguity of the XML semantics during query evaluation (Gyssens et al., 2006); (v) problematic update management issues posed by processing XML data (Benedikt et al., 2005; Boncz et al., 2006; Xu et al., 2005).

A possible solution to the above issues consists in computing and packaging synopsis data structures against the original XML documents. The aim of this approach is to obtain a small-size XML document (i.e., a proper synopsis data structure) starting from the input XML document X, in order to reduce the computational overhead due to processing data in X. The intuition behind such data structures is that the information content carried out by is “very similar” to the information content carried out by X. The measure of this similarity can be defined according to different alternatives depending on the target application. As an example, looking at the structure of documents (e.g., (Nierman & Jagadish, 2002)) is useful in the context of algorithms for clustering XML documents, and algorithms for detecting similarities among XML documents. In our approach, XML query processing aspects are taken into account, thus, given a query Q, the similarity measure is introduced in terms of the approximation error of Q, denoted by E(Q). E(Q) is quantified as the relative difference between Q exact answer (i.e., the answer to Q evaluated against X), denoted by A(Q), and Q approximate answer (i.e., the answer to Q evaluated against ), denoted by . E(Q) is thus defined as follows: