Wong Chung-Yu. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (leaf 75). / Abstracts in English and Chinese. / Abstract --- p.ii / List of figures --- p.viii / List of tables --- p.ix / Chapter 1. --- BACKGROUND --- p.1 / Chapter 1.1 --- An analysis of manuals --- p.1 / Chapter 1.2 --- Existing practice --- p.5 / Chapter 1.3 --- New concept in dynamic manual --- p.7 / Chapter 1.3.1 --- Dynamic representation --- p.7 / Chapter 1.3.2 --- Machine-orientation --- p.8 / Chapter 2. --- DESIGN PHILOSOPHY --- p.10 / Chapter 2.1 --- Concept --- p.10 / Chapter 2.2 --- Data node --- p.12 / Chapter 2.3 --- Characteristic of function and operator --- p.14 / Chapter 2.4 --- Function hierarchy --- p.17 / Chapter 2.5 --- Manual-tree (conceptual and actual) --- p.18 / Chapter 2.6 --- Coding --- p.20 / Chapter 2.7 --- Operation sequence --- p.21 / Chapter 2.8 --- Parameter passing --- p.22 / Chapter 2.9 --- Manual-tree operation --- p.24 / Chapter 3. --- IMPLEMETATION OF DYNAMIC MANUAL SYSTEM --- p.25 / Chapter 3.1 --- Generator --- p.26 / Chapter 3.1.1 --- File format and generation --- p.26 / Chapter 3.2 --- Reader --- p.35 / Chapter 3.2.1 --- Guide service --- p.36 / Chapter 3.2.2 --- Button querying service --- p.37 / Chapter 3.2.3 --- Personal management service --- p.38 / Chapter 3.2.3.1 --- Insert --- p.38 / Chapter 3.2.3.2 --- Delete --- p.40 / Chapter 3.2.3.3 --- Swap --- p.40 / Chapter 3.3 --- The graphics --- p.42 / Chapter 4. --- EXPERIMENTS --- p.43 / Chapter 4.1 --- Experiment I (mobile phone) --- p.43 / Chapter 4.1.1 --- Data preparation --- p.43 / Chapter 4.1.2 --- Generating XML file --- p.46 / Chapter 4.1.3 --- Preparing multimedia material --- p.46 / Chapter 4.1.4 --- Design of Reader --- p.47 / Chapter 4.1.5 --- Testing --- p.51 / Chapter 4.1.5.1 --- Top-down search test --- p.51 / Chapter 4.1.5.2 --- Bottom-up search test --- p.52 / Chapter 4.1.5.3 --- function hierarchy modifying test --- p.53 / Chapter 4.2 --- Experiment II (pager) --- p.54 / Chapter 4.2.1 --- Data preparation --- p.54 / Chapter 4.2.2 --- Generating XML file --- p.54 / Chapter 4.2.3 --- Preparing multimedia material and the Reader --- p.56 / Chapter 4.2.4 --- Testing --- p.57 / Chapter 4.2.4.1 --- Top-down search test --- p.58 / Chapter 4.2.4.2 --- Bottom-up search test --- p.58 / Chapter 4.2.4.3 --- function hierarchy modifying test --- p.59 / Chapter 4.3 --- Control graphics constrain --- p.61 / Chapter 5. --- RESULTS --- p.65 / Chapter 5.1 --- Change of representation --- p.65 / Chapter 5.2 --- Storage and computation requirements --- p.70 / Chapter 6. --- CONCLUSION --- p.72 / References --- p.75 / Appendix A.1 input file of mobile phone (function part) --- p.76 / Appendix A.2 input file of mobile phone (operator part) --- p.96 / Appendix B.1 input file of pager (function part) --- p.105 / Appendix B.2 input file of pager (operator part) --- p.111 / Appendix C Function hierarchies and operator lists of the experiments --- p.113 / Appendix D Key words --- p.117

"Keeping views fresh by maintaining the consistency between materialized views and their base data in the presence of base updates is a critical problem for many applications, including data warehousing and data integration. While heavily studied for traditional databases, the maintenance of XML views remains largely unexplored. Maintaining XML views is complex due to the richness of the XML data model and the powerful capabilities of XML query languages, such as XQuery. This dissertation proposes a comprehensive solution for the general problem of maintaining materialized XQuery views. Our solution is the first to enable the maintenance of a large class of XQuery views including XPath expressions, FLWOR expressions, and Element Constructors. These views may contain arbitrary result construction and arbitrary grouping and join operations. Our solution also supports the unique order requirements of XQuery including source document order and query order. The contributions of this dissertation include: (i) an efficient solution for supporting order in XML query processing and view maintenance, (ii) an identifier-based technique for enabling incremental construction of XML views, (iii) a mechanism for modeling and validating source XML updates, (iv) a counting algorithm for supporting view maintenance on delete and modify updates, (v) an algebraic solution for propagating bulk XML updates, and (vi) an efficient mechanism for refreshing materialized XML views on propagated updates. We provide proofs of correctness of our proposed techniques for materialized XQuery maintenance. We have implemented a prototype of our view maintenance solution on top of the Rainbow XML query engine, developed at WPI. Our experiments confirm that our solution provides a practical and efficient solution for maintaining materialized XQuery views even when handling heterogeneous batches of possibly large source updates. Our solution follows the widely adopted propagate-apply framework for view maintenance common to all mainstream query engines. That is, our solution produces incremental maintenance plans in the same algebraic language used to define the views. These plans can thus be optimized and executed by standard query processing techniques. Being compatible with standard frameworks paves the way for our XML view maintenance solution to be easily adopted by existing database engines."

"Update operations over XML views are essential for applications using XML views. In this dissertation work, we provide scalable solutions to support updating through XML views defined over relational databases. Especially we focus on the update-public semantic, where updates are always public (made to the public database), and the update-local semantic, where update effects are first kept local and then made public as and when required. Towards this, we propose the clean extended-source theory for determining whether a correct view update translation exists, which then serves as a theoretical foundation for us to design practical XML view updating algorithms. Under update-public semantic, state-of-the-art view updating work focus on identifying the correct update translation purely on the data. We instead take a schema-centric solution, which utilizes the schema of the underlying source to effectively prune updates that are guaranteed to be not translatable and pass updates that are guaranteed to be translatable directly to the SQL engine. Only those updates that could not be classified using schema knowledge are finally analyzed by examining the data. This required data-level check is further optimized under schema guidance to prune the search space for finding a correct translation. As the first work addressing the update-local semantic, we propose a practical framework, called LoGo. LoGo Localizes the view update translation, while preserves the properties of views being side-effect free and updates being always updatable. LoGo also supports on-demand merging of the local database of the subject viewinto the public database (also called global database), while still guaranteeing the subject view being free of side effects. A flexible synchronization service is provided in LoGo that enables all other views defined over the same public database to be refreshed, i.e., synchronized with the publically committed changes, if so desired. Further, given that XMLis an ordered datamodel,we propose an ordersensitive solution named O-HUX to support XML view updating with order. We have implemented the algorithms, along with respective optimization techniques. Experimental results confirm the effectiveness of the proposed services, and highlight its performance characteristics."

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