XML stream applications bring the challenge of efficiently processing queries on sequentially accessible token-based data streams. The automaton paradigm is naturally suited for pattern retrieval on tokenized XML streams, but requires patches for implementing the filtering or restructuring functionalities common for the XML query languages. In contrast, the algebraic paradigm is well-established for processing self-contained tuples. However, it does not traditionally support token inputs. This dissertation proposes a framework called Raindrop, which accommodates both the automaton and algebra paradigms to take advantage of both. First, we propose an architecture for Raindrop. Raindrop is an algebra framework that models queries at different abstraction levels. We represent the token-based automaton computations as an algebraic subplan at the high level while exposing the automaton details at the low level. The algebraic subplan modeling automaton computations can thus be integrated with the algebraic subplan modeling the non-automaton computations. Second, we explore a novel optimization opportunity. Other XML stream processing systems always retrieve all the patterns in a query in the automaton. In contrast, Raindrop allows a plan to retrieve some of the pattern retrieval in the automaton and some out of the automaton. This opens up an automaton-in-or-out optimization opportunity. We study this optimization in two types of run-time environments, one with stable data characteristics and one with fluctuating data characteristics. We provide search strategies catering to each environment. We also describe how to migrate from a currently running plan to a new plan at run-time. Third, we optimize the automaton computations using the schema knowledge. A set of criteria are established to decide what schema constraints are useful to a given query. Optimization rules utilizing different types of schema constraints are proposed based on the criteria. We design a rule application algorithm which ensures both completeness (i.e., no optimization is missed) and minimality (i.e., no redundant optimization is introduced). The experimentations on both real and synthetic data illustrate that these techniques bring significant performance improvement with little overhead.

"As information on the World Wide Web continues to proliferate at an astounding rate, the Extensible Markup Language (XML) has been emerging as a standard format for data representation on the web. In many application domains, specific document type definitions (DTDs) are designed to enforce a semantically agreed-upon structure of the XML documents. In XML context, these structural definitions serve as schemata. However, both the data and the structure (schema) of XML documents tend to change over time for a multitude of reasons, including to correct design errors in the DTD, to allow expansion of the application scope over time, or to account for the merging of several businesses into one. Most of the current software tools that enable the use of XML do not provide explicit support for such data or schema changes. Using these tools in a changing environment entails making manual edits to DTDs and XML data and reloading them from scratch. In this vein, we put forth the first solution framework, called XML Evolution Manager (XEM), to manage the evolution of DTDs and XML documents. XEM provides a minimal yet complete taxonomy of basic change primitives. These primitives, classified as either data or schema changes, are consistency-preserving. For a data change, they ensure that the modified XML document conforms to its DTD both in structure and constraints. For a schema change, they ensure that the new DTD is well-formed, and all existing XML documents are transformed also to conform to the modified DTD. We prove both the completeness of our evolution taxonomy, as well as its consistency-preserving nature. To verify the feasibility of our XEM approach we have implemented a working prototype system in Java, using the XML4J parser from IBM and PSE Pro as our backend storage system. We present an experimental study run on this system where we compare the relative efficiencies of the primitive operations in terms of their execution times. We then contrast these execution times against the time to reload the data, which would be required in a manual system. Based on the results of these experiments we conclude that our approach improves upon the previous method of making manual changes and reloading data from scratch by providing automated evolution management facilities for DTDs and XML documents."

Materialized XML views are a popular technique for integrating data from possibly distributed and heterogeneous data sources. However, the problem of the incremental maintenance of such XML views poses new challenges which to date remain unaddressed. One, XML views not only filter the data, but may radically restructure it to construct new XML nested document structures. Moreover, order is inherent in the XML model, and XML views reflect both the implicit document order of the underlying sources and the order explicitly imposed in the view definition. Therefore, order also has to be preserved at view maintenance time. In this thesis we present an algebraic approach for the incremental maintenance of XQuery views, called VOX (View maintenance for Ordered XML). To the best of our knowledge, this is the first solution to order-preserving XML view maintenance. Our strategy correctly transforms an update to source XML data into sequences of updates that refresh the view. Our technique is based on an algebraic representation of the XQuery view expression using an XML algebra. The XML algebra has ordered bag semantics; hence most of the operators logically are order preserving. We propose an order-encoding mechanism that migrates the XML algebra to (non-ordered) bag semantics, no longer requiring most of the operators to be order-aware. Furthermore, this now allows most of the algebra operators to become distributive over update operations. This transformation brings the problem of maintaining XML views one step closer to the problem of maintaining views in other (unordered) data models. We are thus now able to adopt some of the existing (relational) maintenance techniques towards our goal of efficient order-sensitive XQuery view maintenance. In addition we develop a full set of rules for propagating updates through XML specific operations. We have proven the correctness of the VOX view maintenance approach. A full implementation of VOX on top of RAINBOW, the XML data management system developed at WPI, has been completed. Our experimental results performed using the data and queries provided by the XMark benchmark, confirm that incremental XML view maintenance indeed is significantly faster than complete recomputation in most cases. Incremental maintenance is shown to outperform recomputation even for large updates.

"XML streams have become increasingly prevalent in modern applications, ranging from network traffic monitoring to real-time information publishing. XQuery evaluation over XML streams require the temporary buffering of XML elements, which not only utilizes system buffer and CPU resources but also causes un-necessary output latency. This thesis presents a semantic query optimization solution to minimize memory footprint during XQuery evaluation by exploiting XML schema knowledge. In many practical applications, XML streams are generated conforming to pre-defined schema constraints typically expressed via a DTD or an XML schema specification. Utilizing such constraints enables us to on-the-fly predict the non-occurrence of a given pattern within a bound context. This helps us to avoid data buffering and to release buffered data at an earlier moment, thus achieving a minimized memory footprint. In this work, we focus on one particular class of constraints, namely, the Pattern Non-Occurrence (PNO) constraint. We develop an automaton-based technique to detect PNO constraints at runtime. For a given query, optimization opportunities which can be triggered by runtime PNO detection are explored for memory footprint minimization. Optimization decisions are encoded using our proposed Condition-Action Graph (CAG). The optimization-embedded execution strategy is then proposed to execute an optimized plan by detecting PNO constraints at run-time and then triggering the corresponding encoded actions when certain predefined conditions are satisfied. To ensure the efficiency of such PNO-triggered optimization, we propose optimization strategy on shrinking the CAGs by utilizing constraint knowledge during the query plan compiling phase. We implement our optimization technique within the Raindrop XQuery engine. Our system implementation processes XQuery utilizing the Raindrop algebra. It is efficiently augmented by our optimization module, which uses Glushkov automaton technique to capture and monitor PNO constraints in parallel with the query-driven pattern retrieval. Finally, we conduct experimental studies using both real and synthetic data streams to illustrate that our techniques bring significant performance improvement in both memory and CPU usage as well as improved output latency over state-of-the-art solutions, with little overhead."

When updating a valid XML Data or Schema, an efficient yet light-weight mechanism is needed to determine if the update would invalidate the document. Towards this goal, we have developed a framework called SAXE. First, we analyzed the constraints expressed in XML schema specifications to establish constraint rules that must be observed when a schema or an XML data conforming to a given XML Schema is altered. We then classify the rules based on their relevancy for a given update case. That is, we show the minimal set of rules that must be checked to guarantee the safety for each update primitive. Next, we illustrate that this set of incremental constraint checks can be specified using generic XQuery expressions composed of three type of components. Safe updates for the XML data have the following components: (1) XML schema meta-queries to retrieve any con-straint knowledge potentially relevant to the given update from the schema or XMl data being altered, (2) retrieval of specific characteristics from the to-be-modified XML, and (3) lastly an analysis of information collected about the XML schema and the affected XML document to determine validity of the update. For the safe schema alteration, the components are: (1) XML schema meta-queries to retrieve relevant information from the schema (2)analysis and usage of retrieved information to update the schema, and lastly to (3) propagate the changes to the XML data when necessary. As a proof of concept, we have established a library of these generic XQuery constraint checks for the type-related XML constraints. The key idea of SAXE is to rewrite each XQuery update into a safe XML Query by extending it with appropriate constraint check subqueries. This en-hanced XML update query can then safely be executed using any existing XQuery engine that supports updates - thus turning any update engine automatically into an incremen-tal constraint-check engine. In order to verify the feasibility of our approach, we have implemented a prototype system SAXE that generates safe XQuery updates. Our experimental evaluation assesses the overhead of rewriting as well as the relative performance of our loosely-coupled incremental constraint check approach against the more traditional first-change-document and then revalidate-it approach.

XML has emerged as the standard data format for Internet-based business applications. In many bussiness settings, a relational database management system(RDBMS) will serve as the storage manager for data from XML documents. In such a system, once the XML data is shredded and loaded into the storage system, XML queries posed against these (now virtual) XML documents are processed by translating them as much as possible into SQL queries against the underlying relational storage. Clearly, in order to support full database functionalities over XML data, we must allow users not only to query but also to specify updates on XML documents. Today while the XML query language XQuery is being standardized by W3C, no syntax for updating XML documents is included in this language proposal as of now. In this thesis, we have developed techniques for supporting translation of XML updates on XML views of relational data into SQL updates on the underlying relations. These techniques are based on techniques for supporting translation of updates on object-based views of relational data into SQL updates on underlying relations cite{keller91}. The system has been implemented as a part of XML Management System, called Rainbow, that is being developed at the Worcester Polytechnic Institute (WPI). We have used XQuery as XML query language and Oracle as the backend relational store for implementation of the system. Experimental studies show that incremental XML updates supported by our system is a better choice than complete reload of XML documents under a variety of system settings.

Woo Kwan Ho. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2005. / Includes bibliographical references (leaves 148-155). / Abstracts in English and Chinese. / Contents --- p.ii / Abstract --- p.iv / Acknowledgements --- p.vii / List of Figures --- p.viii / List of Tables --- p.x / Chapter Chapter 1 --- Introduction --- p.1 / Chapter Chapter 2 --- Literature Reviews --- p.7 / Chapter 2.1 --- Block Clustering --- p.7 / Chapter 2.2 --- Clustering XML by structure --- p.10 / Chapter 2.2.1 --- Definition of XML schematic information --- p.10 / Chapter 2.2.2 --- Identification of XML schematic information --- p.12 / Chapter Chapter 3 --- Bi-Tour Ant Colony Optimization for diagonal clustering --- p.15 / Chapter 3.1 --- Motivation --- p.15 / Chapter 3.2 --- Framework of Bi-Tour Ant Colony Algorithm --- p.21 / Chapter 3.3 --- Re-order of the data matrix in BTACO clustering method --- p.27 / Chapter 3.3.1 --- Review of Ant Colony Optimization --- p.29 / Chapter 3.3.2 --- Bi-Tour Ant Colony Optimization --- p.36 / Chapter 3.4 --- Determination of partitioning scheme --- p.44 / Chapter 3.4.1 --- Weighed Sum of Error (WSE) --- p.48 / Chapter 3.4.2 --- Materialization of partitioning scheme via hypothetic matrix --- p.50 / Chapter 3.4.3 --- Search of best-fit hypothetic matrix --- p.52 / Chapter 3.4.4 --- Dynamic programming approach --- p.53 / Chapter 3.4.5 --- Heuristic partitioning approach --- p.57 / Chapter 3.5 --- Experimental Study --- p.62 / Chapter 3.5.1 --- Data set --- p.63 / Chapter 3.5.2 --- Study on DP Approach and HP Approach --- p.65 / Chapter 3.5.3 --- Study on parameter settings --- p.69 / Chapter 3.5.4 --- Comparison with GA-based & hierarchical clustering methods --- p.81 / Chapter 3.6 --- Chapter conclusion --- p.90 / Chapter Chapter 4 --- Application of BTACO-based clustering in XML database system --- p.93 / Chapter 4.1 --- Introduction --- p.93 / Chapter 4.2 --- Overview of normalization and vertical partitioning in relational DB design --- p.95 / Chapter 4.2.1 --- Normalization of relational models in database design --- p.95 / Chapter 4.2.2 --- Vertical partitioning in database design --- p.98 / Chapter 4.3 --- Clustering XML documents --- p.100 / Chapter 4.4 --- Proposed approach using BTACO-based clustering --- p.103 / Chapter 4.4.1 --- Clustering XML documents by structure --- p.103 / Chapter 4.4.2 --- Clustering XML documents by user transaction patterns --- p.109 / Chapter 4.4.3 --- Implementation of Query Manager for our experimental study --- p.114 / Chapter 4.5 --- Experimental Study --- p.118 / Chapter 4.5.1 --- Experimental Study on the clustering by structure --- p.118 / Chapter 4.5.2 --- Experimental Study on the clustering by user access patterns --- p.133 / Chapter 4.6 --- Chapter conclusion --- p.141 / Chapter Chapter 5 --- Conclusions --- p.143 / Chapter 5.1 --- Contributions --- p.144 / Chapter 5.2 --- Future works --- p.146 / Bibliography --- p.148 / Appendix I --- p.156 / Appendix II --- p.168 / Index tables for Profile A --- p.168 / Index tables for Profile B --- p.171 / Appendix III --- p.174

A general XML index can itself be sizable leading to low efficiency. To alleviate this predicament, frequently asked queries can be indexed by a database system. They are referred to as views. Answering queries using materialized views is always cheaper than evaluating over the base data. Traditional techniques solve this problem by considering only a single view. We approach this problem by exploiting the potential relationships of multiple views, which can be used together to answer a given query. Experiments show that significant performance gain can be achieved from multiple views. / A XML query can be decomposed to a sequence of structural joins (e.g., parent/child and ancestor/descendant) and content joins. Thus, structural join optimization is a key to improving join-based evaluation. We optimize structural join with two orthogonal methods: partition-based method exploits the spatial specialities of XML encodings by projecting them on a plane; and location-based method improves structural join by accurately pruning all irrelevant nodes, which cannot produce results. / As XML (eXtensible Markup Language) becomes a universal medium for data exchange over the Internet, efficient XML query processing is now the focus of considerable research and development activities. This thesis describes works toward efficient XML query evaluation and optimization in native XML databases. / XML indexes are widely studied to evaluate XML queries and in particular to accelerate join-based approaches. Index-based approaches outperform join-based approaches (e.g., holistic twig join) if the queries match the index. Existing XML indexes can only support a small set of XML queries because of the varieties in XML query representations. A XML query may involve child-axis only, both child-axis and branches, or additional descendant-or-self-axis but only in the query root. We propose novel indexes to efficiently support a much wider range of XML queries (with /, //, [], *). / Tang, Nan. / "December 2007." / Advisers: Kam-Fei Wong; Jeffrey Xu Yu. / Source: Dissertation Abstracts International, Volume: 69-08, Section: B, page: 4861. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (p. 152-163). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts in English and Chinese. / School code: 1307.

Cheung Wing Hang. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2001. / Includes bibliographical references (leaves 107-112). / Abstracts in English and Chinese. / Abstract --- p.ii / Abstract in Chinese --- p.iv / Acknowledgments --- p.v / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Firewall Issue in Distributed Systems --- p.2 / Chapter 1.2 --- Heterogeneous Communication Protocols --- p.4 / Chapter 1.3 --- Translator for Converting Interface Definition to Flexible XML --- p.8 / Chapter 1.4 --- An Implementation of a Scalable Mediator Query System --- p.9 / Chapter 1.5 --- Our Contributions --- p.9 / Chapter 1.6 --- Outline of This Thesis --- p.10 / Chapter 2 --- Related Work and Technologies --- p.12 / Chapter 2.1 --- Overview of XML Technology --- p.12 / Chapter 2.1.1 --- XML Basic Syntax --- p.13 / Chapter 2.1.2 --- DTD: The Grammar Book --- p.15 / Chapter 2.1.3 --- Representing Complex Data Structures --- p.17 / Chapter 2.2 --- Overview of Java Servlet Technology --- p.18 / Chapter 2.3 --- Overview of Simple Object Access Protocol --- p.20 / Chapter 2.4 --- Overview of XML-RPC --- p.21 / Chapter 2.5 --- Overview of XIOP --- p.22 / Chapter 3 --- Using XML and Servlets to Support CORBA Calls --- p.24 / Chapter 3.1 --- Objective --- p.24 / Chapter 3.2 --- General Concept of Our Mechanism --- p.25 / Chapter 3.2.1 --- At Client Side --- p.27 / Chapter 3.2.2 --- At Server Side --- p.28 / Chapter 3.3 --- Data in Transmission --- p.30 / Chapter 3.3.1 --- Using XML --- p.30 / Chapter 3.3.2 --- Format of Messages in Transmission --- p.30 / Chapter 3.4 --- Supporting Callbacks in CORBA Systems --- p.33 / Chapter 3.4.1 --- What is callback? --- p.33 / Chapter 3.4.2 --- Enhancement to Allow Callbacks --- p.34 / Chapter 3.5 --- Achieving Transparency with Add-on Components --- p.37 / Chapter 4 --- A Translator to Convert CORBA IDL to XML --- p.39 / Chapter 4.1 --- Introduction to CORBA IDL --- p.39 / Chapter 4.2 --- Mapping from IDL to XML --- p.40 / Chapter 4.2.1 --- IDL Basic Data Types --- p.41 / Chapter 4.2.2 --- IDL Complex Data Types --- p.42 / Chapter 4.2.3 --- IDL Interface --- p.48 / Chapter 4.2.4 --- Attributes --- p.48 / Chapter 4.2.5 --- Operations (Methods) --- p.49 / Chapter 4.2.6 --- Exceptions --- p.50 / Chapter 4.2.7 --- Inheritance --- p.51 / Chapter 4.2.8 --- IDL Modules --- p.52 / Chapter 4.2.9 --- A Sample Conversion --- p.52 / Chapter 4.3 --- Making a Request or Response --- p.53 / Chapter 4.4 --- Code Generation for Add-on Components --- p.54 / Chapter 4.4.1 --- Generation of Shadow Objects --- p.54 / Chapter 4.4.2 --- Generation of Servlet Components --- p.55 / Chapter 5 --- Communication in Heterogeneous Distributed Environments --- p.58 / Chapter 5.1 --- Objective --- p.58 / Chapter 5.2 --- General Concept --- p.60 / Chapter 5.3 --- Case Study 1 - Distributed Common Object Model --- p.61 / Chapter 5.3.1 --- Brief Overview of Programming in DCOM --- p.61 / Chapter 5.3.2 --- Mapping the Two Different Interface Definitions --- p.63 / Chapter 5.3.3 --- Sample Architecture of Communicating Between DCOM and CORBA --- p.66 / Chapter 5.4 --- Case Study 2 - Java Remote Methods Invocation --- p.67 / Chapter 5.4.1 --- Brief Overview of Programming in Java RMI --- p.67 / Chapter 5.4.2 --- Mapping the Two Different Interface Definitions --- p.69 / Chapter 5.4.3 --- Sample Architecture of Communicating Between JavaRMI and CORBA --- p.71 / Chapter 5.5 --- Be Generic: Binding with the WEB --- p.72 / Chapter 6 --- Building a Scalable Mediator-based Query System --- p.74 / Chapter 6.1 --- Objectives --- p.74 / Chapter 6.2 --- Introduction to Our Mediator-based Query System --- p.76 / Chapter 6.2.1 --- What is mediator? --- p.76 / Chapter 6.2.2 --- The Architecture of our Mediator Query System --- p.77 / Chapter 6.2.3 --- The IDL Design of the Mediator System --- p.79 / Chapter 6.2.4 --- Components in the Query Mediator System --- p.80 / Chapter 6.3 --- Helping the Mediator System to Expand Across the Firewalls --- p.83 / Chapter 6.3.1 --- Implementation --- p.83 / Chapter 6.3.2 --- Across Heterogeneous Systems with DTD --- p.87 / Chapter 6.4 --- Adding the Callback Feature to the Mediator System --- p.89 / Chapter 6.5 --- Connecting our CORBA System with Other Environments --- p.90 / Chapter 6.5.1 --- Our Query System in DCOM --- p.91 / Chapter 6.5.2 --- Our Query System in Java RMI --- p.92 / Chapter 6.5.3 --- Binding Heterogeneous Systems --- p.93 / Chapter 7 --- Evaluation --- p.95 / Chapter 7.1 --- Performance Statistics --- p.95 / Chapter 7.1.1 --- Overhead in other methods --- p.97 / Chapter 7.2 --- Means for Enhancement --- p.98 / Chapter 7.2.1 --- Connection Performance of HTTP --- p.98 / Chapter 7.2.2 --- Transmission Data Compression --- p.99 / Chapter 7.2.3 --- Security Concern --- p.99 / Chapter 7.3 --- Advantages of Using Our Mechanism --- p.101 / Chapter 7.4 --- Disadvantages of Using Our Mechanism --- p.102 / Chapter 8 --- Conclusion --- p.104

by Fung Tze Wa. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2003. / Includes bibliographical references (leaves 92-96). / Abstracts in English and Chinese. / Abstract in English --- p.i / Abstract in Chinese --- p.ii / Acknowledgements --- p.iii / Table of Contents --- p.iv-vi / List of Figures --- p.vii-ix / List of Tables --- p.x / Chapter Chapter 1 --- Introduction / Chapter 1.1 --- Introduction --- p.1 / Chapter 1.2 --- Motivation --- p.3 / Chapter 1.3 --- Purposes of this Research --- p.6 / Chapter 1.4 --- Contribution of this Research --- p.7 / Chapter 1.5 --- Outline of the Thesis --- p.9 / Chapter Chapter 2 --- Literature Review And Research Issues / Chapter 2.1 --- Introduction --- p.11 / Chapter 2.2 --- Spatial Access Methods --- p.14 / Chapter 2.2.1 --- R-Tree --- p.15 / Chapter 2.2.2 --- R*-Tree --- p.19 / Chapter 2.2.3 --- R+-Tree --- p.21 / Chapter 2.3 --- Spatial Network Analysis --- p.22 / Chapter 2.4 --- Nearest Neighbor Queries --- p.23 / Chapter 2.5 --- Summary --- p.25 / Chapter Chapter 3 --- Data Preparation / Chapter 3.1 --- "Introduction (XML, GML), XML indexing" --- p.26 / Chapter 3.2 --- Spatial data from Lands Department --- p.31 / Chapter 3.3 --- Graph representation for Road Network data --- p.32 / Chapter 3.4 --- Summary --- p.35 / Chapter Chapter 4 --- XML Indexing for Spatial Data / Chapter 4.1 --- Introduction --- p.36 / Chapter 4.2 --- STR Packed R-Tree --- p.38 / Chapter 4.2.1 --- Implementation --- p.39 / Chapter 4.2.2 --- Experimental Result --- p.41 / Chapter 4.3 --- Summary --- p.48 / Chapter Chapter 5 --- Spatial Network / Chapter 5.1 --- Introduction --- p.50 / Chapter 5.2 --- CCAM: Connectivity-Clustered Access Method --- p.53 / Chapter 5.3 --- Shortest Path in Spatial Network --- p.56 / Chapter 5.4 --- A New Algorithm Specially for Partitioning /Clustering Network --- p.63 / Chapter 5.5 --- A New Simple heuristic for Shortest Path Problem for Spatial Network --- p.70 / Chapter 5.6 --- Summary --- p.74 / Chapter Chapter 6 --- Nearest Neighbor Queries / Chapter 6.1 --- Introduction --- p.76 / Chapter 6.2 --- Modified Algorithm for Nearest Neighbor Queries --- p.78 / Chapter 6.3 --- Summary --- p.83 / Chapter Chapter 7 --- Conclusion and Future Work / Chapter 7.1 --- Conclusion --- p.84 / Chapter 7.2 --- Future Work --- p.85 / Appendix Space Driven Algorithm / Chapter A.1 --- Introduction --- p.87 / Chapter A.2 --- Fixed Grid --- p.88 / Chapter A.3 --- Z-curve --- p.89 / Chapter A.4 --- Hilbert curve --- p.90 / Chapter A.5 --- Conclusion --- p.91 / Bibliography --- p.92