| XML is a simple and flexible format for encoding and exchanging data which has been used in a wide range of applications. Providing efficient management of XML data is an important and challenging problem that has attracted a great deal of attention. This thesis addresses the incremental validation problem, which consists in incrementally checking whether XML documents conform to their schemes in the presence of updates, and is a classical problem in data management. Two instances of the problem are considered. First, we assume a "native" storage approach in which the documents are stored and accessed using special-purpose programs. We propose, implement and evaluate incremental validation algorithms which, for those schemas most commonly used in practice, run in time logarithmic in the size of the document. This improves significantly on brute-force methods and previous approaches; furthermore, our experimental results show our methods exhibit excellent performance and scalability. Next, we consider mapping schemes for storing and accessing XML documents as relational databases. We study natural notions of information preservation for mappings, and relate them to classical notions in the literature; we also show that these properties are undecidable for a large class of mapping schemes that contains all those in the literature. Then, we propose sound methods for designing information-preserving mapping schemes, discuss their implementation on standard relational database management systems, and show through experiments that they perform well in practice for both queries and updates. |
