Recent years have seen a surge in the popularity of XML, a markup language for representing semi-structured data. Some of this popularity can be attributed to the success that the semi-structured data model has had in environments where the relational data model has been insufficiently expressive. Concomitant with XMLs growing popularity, the world of database research has seen the rebirth of interest in tree-structured, hierarchical database systems. This thesis analyzes several problems that arise when constructing XML data management systems, particularly in the case where such systems must handle dynamic content. In the first chapter, we consider the problem of incremental schema validation, which arises in almost any XML database system. We build upon previous work by finding several classes of schemas for which very efficient algorithms exist. We also develop an algorithm that works for any schema, and prove that it is optimal. In the second chapter, we turn to the problem of improving query evaluation times on extremely large database systems. In particular, we boost the performance of the structural and twig joins, fundamental XML query evaluation techniques, through the use of an adaptive index. This index tunes itself to the query workload, providing a 20-80% boost in speed for these join operators. The adaptive nature of the index also allows updates to the database to be easily tracked. While accurate selectivity estimation is a critical problem in any database system due to its importance in choosing optimal query plans, there has been very little work on selectivity estimation in the presence of updates. We ask whether it is possible to design a structure for selectivity in XML databases that is updateable, and can return results with theoretically sound error guarantees. Through a combination of lower and upper bounds, we give strong evidence suggesting that this is unlikely in practice. Motivated by these results, we then develop a heuristic selectivity estimation structure for XML databases. This structure is the first such synopsis that can handle all aspects of core XPath, and is also updateable. Our experimental results demonstrate the efficacy of the approach.

As the World Wide Web continues to grow, people clearly want to do much more with it than just publish static pages of text and graphics. While such increased interactivity has traditionally been accomplished through the use of server-side CGI scripts, much recent research on Web browsers has been on extending their capabilities through the addition of various types of client-side services. The most popular of these extensions take the form of plug-ins, applets, and "document scripts" such as Java Script. However, because these extensions have been created in a haphazard way by a variety of independent groups, they suffer greatly in terms of flexibility, uniformity, and interoperability. Interactive HTML is a system that addresses these problems by combining plug-ins, applets, and document scripts into one uniform and cohesive architecture. It is implemented as an external C library that can be used by a browser programmer to add client-side services to the browser. The IHTML services are implemented as dynamically loaded "language modules," allowing new plug-ins and language interpreters to be added to an iHTML browser without recompiling the browser itself. The system is currently integrated with NCSA's X Mosaic browser and includes language modules for a text viewer plug-in and Python language interpreter. This thesis examines the iHTML architecture in the context of the historical development of Web client-side services and presents an example of iHTML's use to collect usage information about Web documents. / Graduation date: 1997

The eXtensible Markup Language (XML) has become the standard format for data exchange on the Internet, providing interoperability between different business applications. Such wide use results in large volumes of heterogeneous XML data, i.e., XML documents conforming to different schemas. Although schemas are important in many business applications, they are often missing in XML documents. In this thesis, we present a suite of algorithms that are effective in extracting schema information from a large collection of XML documents. We propose using the cost of NFA simulation to compute the Minimum Length Description to rank the inferred schema. We also studied using frequencies of the sample inputs to improve the precision of the schema extraction. Furthermore, we propose an evaluation framework to quantify the quality of the extracted schema. Experimental studies are conducted on various data sets to demonstrate the efficiency and efficacy of our approach.

Thesis (M.S.)--University of Florida, 2001. / Title from first page of PDF file. Document formatted into pages; contains x, 75 p.; also contains graphics. Vita. Includes bibliographical references (p. 71-74).

Thesis (M.Sc.)--York University, 2008. Graduate Programme in Computer Science. / Typescript. Includes bibliographical references (leaves 147-152). Also available on the Internet. MODE OF ACCESS via web browser by entering the following URL: http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&res_dat=xri:pqdiss&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&rft_dat=xri:pqdiss:MR38782

Thesis (Ph. D.)--Florida State University, 2003. / Advisor: Dr. Gary Burnett, Florida State University, School of Information Studies. Title and description from dissertation home page (viewed Apr. 06, 2004). Includes bibliographical references.

Thesis (Ph. D.)--Hong Kong University of Science and Technology, 2004. / Includes bibliographical references (leaves 107-120). Also available in electronic version. Access restricted to campus users.

Thesis (Ph. D.)--University of Missouri-Columbia, 2003. / Typescript. Vita. Includes bibliographical references (leaves 186-201). Also available on the Internet.

Thesis (Ph. D.)--College of Computing, Georgia Institute of Technology, 2004. Directed by Ling Liu. / Vita. Includes bibliographical references (leaves 153-158).

Thesis (Ph. D.)--University of Missouri-Columbia, 2003. / Typescript. Vita. Includes bibliographical references (leaves 186-201). Also available on the Internet.