XML data placement for effective processing of path queries

Abstract

XML has become the standard of the data representation and exchange through the Internet recently. XML is a markup language that can separate the contents of data and the presentation of data. Because XML data is modeled as a rooted tree, path queries are widely used for the query processing. In the thesis we present XML data placement methods for effective processing of path queries. Specifically, this thesis addresses two issues of XML data placement, data placement on physical medium and wireless air medium. First, we propose an efficient algorithm that places XML data on the physical storage medium (i.e., magnetic disks) such that the number of disk accesses for path query processing is minimized. The proposed algorithm consists of two steps. In the first step, we assign a number (called the mapping indicator) for each node of a tree in a bottom-up fashion. The mapping indicator of a node denotes the minimum number of disk blocks required for storing the node and all of its descendant nodes. In the second step we map the nodes to disk blocks using the assigned mapping indicator. We analyze the optimality of the proposed method with some relevant proofs. We also show the proposed method provides good performance for various query types with XML data set. Secondly, we propose a set of XML data placement method for wireless air channels which support energy-efficient processing of queries over the wireless stream in mobile clients. The mobile clients can access the XML stream, organized by the proposed method, in a selective way through various kinds of link addresses to related data and signature information on the stream. After defining the BUX (Broadcast Unit of XML data) structure, which is our proposed structure for XML data placement wireless medium, we propose a set of event-driven stream generation and path query processing algorithms for the proposed stream structure. Through performance experiments, we show that our approaches can effectively impro...