{'fraction_non_alphanumeric': 0.018033490768570203, 'fraction_numerical': 0.0, 'mean_word_length': 5.383561643835616, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Schema-based Statistics and Storage for XML

XML (eXtensible Markup Language) is a highly flexible text format that has become the defacto standard for electronic publishing and data exchange, especially on the Web. XML data is tree-structured and can be described by an XML Schema, which provides types and regular expression constructs to concisely describe the document format. XQuery, a declarative query language, supports the extraction and transformation of XML data. Due to its flexible and nested format, the storage and query processing of XML data throws up a variety of new challenges, not addressed by the classical relational approach which is predicated on rigid flat-structured schemas. In this thesis, we address three important issues arising in the XML context: First, we propose StatiX, a framework for XML data summarization and query result cardinality estimation, that organically handles both structural and value predicates. A rich set of schema transformations are used to improve the accuracy of the summary. Through detailed experimentation with a representative set of XQuery queries on both real and synthetic XML data, we show that StatiX produces concise, accurate and flexible summaries. Second, to cater to dynamic XML applications that frequently update their underlying data, we propose the IMAX algorithm for incrementally maintaining StatiX summaries. IMAX incorporates novel techniques for estimating both the positions of the update and the ordinals of elements in the update fragment – a crucial requirement in the ordered data model of XML. An experimental evaluation shows that it provides comparable accuracy to a compute-from-scratch approach at a fraction of the runtime cost. Finally, to design efficient storage layouts for XML data on the ubiquitous relational database engines, we propose FleXMap, a framework that uses a wide range of transformations on the XML Schema description for characterizing the equivalent relational configuration space. A variety of greedy search algorithms built on the FleXMap framework are experimentally shown to output cost-efficient relational configurations as compared to prior approaches. In summary, this thesis presents a toolkit for effectively supporting the highly popular XML world-view on the underlying storage and processing engines.