Thesis (MBA)--Stellenbosch University, 2002. / ENGLISH ABSTRACT: The Extensible Markup Language (XML) has become the language of choice for any kind of data transfer between different business entities. Technologies based on XML like the Extensible Stylesheet Language, the Extensible Linking Language and SOAP add vital functionality and make the use of XML in many different business application scenarios possible. Companies that start employing XML as their format of choice for data exchange are often faced with the problem of different XML dialects within their company or with their business partners. This research project looks at the different solutions that are available for this problem and evaluates their appropriateness for certain scenarios. The first viable solution is employing the Extensible Stylesheet Language which allows for basic transformation on the basis of stylesheets. Companies that use this technology for simple conversion problems can either develop applications themselves or rely on tools from third-party vendors. For more advanced conversion needs a more flexible solution is appropriate. Custom made conversion frameworks developed by using a fourth generation programming language like Java offer the advantages of scalability by connecting more than one communication partner, platform-independency and a high degree of flexibility. Another option that will payoff in the future is the adherence to one of the developing industry XML standards. Such standards are mostly still in the development phase and have not been adopted widely yet. But once it becomes clear which standards are going to survive for each industry the adoption of such a standard will eliminate the need for any customised conversion and facilitate data exchange between business partners that adhere to the same standard. In general it is recommended to research existing XML standards before developing a proprietary one. When a proprietary format already exists the choice of the conversion tools and methods depends on the complexity of the transformation. Simple transformation needs can be solved by employing the XSLT technology while more advanced needs require the development of a customised conversion framework. / AFRIKAANSE OPSOMMING: Die Extensible Markup Language (XML) het die taal van keuse geword vir enige soort van data oordraging tussen verskillende bedryfsentiteite. Tegnologie gebaseer op XML soos die Extensible Stylesheet Language, die Extensible Linking Language en Simple Object Access Protocol (SOAP) dra by tot betekenisvolle waardetoevoeging en maak die gebruik van XML in 'n groot verskeidenheid van besigheidstoepassings scenarios moontlik. Ondernemings wat XML as hul formaat van keuse vir data oordraging meer en meer begin gebruik, word dikwels met die probleem van verskillende XML dialekte intern tot hul onderneming sowel as ekstern tot hul sakevennote, gekonfronteer. Hierdie studie ontleed die verskillende oplossings wat beskikbaar is vir die probleem en evalueer dan die toepaslikheid vir sekere scenarios. Die eerste uitvoerbare oplossing is die gebruik van die Extensible Stylesheet Language wat toelaat vir basiese transformasie op die grondslag van stylblaaie. Ondernemings wat hierdie tegnologie vir eenvoudige omsettingsprobleme wil gebruik kan óf self toepassings ontwikkel of staatmaak op gereedskap vanaf derde party verskaffers. Vir meer gevorderde omsettingsbehoeftes is 'n meer buigsame oplossing geskik. Doelgemaakte omskakelingsraamwerke wat ontwikkel word deur gebruik te maak van 'n vierde generasie programmeringstaal soos JAVA bied die voordele van skalering deur meer as een kommunikasievennoot te konnekteer, platform onafhanklikheid en 'n hoë graad van buigsaamheid. Nog 'n opsie wat rendement in die toekoms kan lewer is om te bly by een van die ontwikkelende industrie XML standaarde. Sulke standaarde is meesal nog in die ontwikkelingsfase en word nog nie tot nou algemeen aanvaar nie. As dit egter begin duidelik word watter standaarde gaan oorleef vir elke industrie sal die aanvaarding van sulke standaarde die nodigheid vir doelgemaakte omskakeling elimineer en sal dit data uitruiling tussen sakevennote wat hou by dieselfde standaarde bevorder. In die algemeen word dit aanbeveel dat bestaande XML standaarde goed nagevors word alvorens 'n alleenreg een ontwikkel word. Wanneer 'n alleenregformaat alreeds bestaan sal die keuse van transformasiegereedskap en metodes afhang van die kompleksiteit van die transformasie. Eenvoudige transformeerde behoeftes kan bevredig word deur die XSLT tegnologie te gebruik, terwyl meer gevorderde behoeftes die ontwikkeling van 'n doelgemaakte omskakelingraamwerk sal benodig.

We have developed a new approach to annotate the uncertainty information of geospatial data. This framework is composed of a geospatial platform and the data with uncertainty. The framework supports geospatial sources such as Geography Markup Language (GML) with uncertainty information. The purpose of this framework is to integrate the uncertainty information of data from the application users and thereby ease the development of processing uncertainty information of geospatial data. Having well organized data and using this framework, the end-users can store the uncertainty information on the current geospatial data structure. For example, a GIS user can share the error information for environmental and geospatial data to others. We have also reported the enhanced geographic information system function.

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.