| This dissertation addresses mainly three issues needed to support query relaxation for XML model: framework formalization, extension of existing database techniques, and data conversion between XML and relational models.; XML (eXtensible Markup Language) is the new universal format for structured documents and data on the World Wide Web. As the Web becomes a major means of disseminating and sharing information and as the amount of XML data increases substantially, there are increased needs to manage and query such XML data in a novel yet efficient way. Especially, one of the useful query processing methods is known as Query Relaxation. Unlike relational databases where the schema is relatively small and fixed, XML model allows varied/missing structures and values, which make it difficult for users to ask questions precisely and completely. To address such problems, query relaxation technique enables systems to automatically weaken, when not satisfactory, the given user query to a less restricted form to permit approximate answers as well.; Therefore, the goal of our study is to investigate issues involved in supporting query relaxation for XML model. (1) We first present a formal framework where users can express the precise semantics and behaviors of query relaxation. This framework can also be used as the basis for designing and implementing the eventual relaxation-enabled query language. (2) We then study a myriad of issues that are related to support query relaxation using native XML engines. Especially, we focus on the notion of similarity between XML data trees using tree edit distance and the issue of selectivity estimation of a set of relaxed XML queries. (3) Finally, we present issues involved in converting data between XML and relational models and propose three novel conversion algorithms that not only capture the original structures and values, but also well preserve the semantic constraints of the original schema. This is a necessary step to support query relaxation for XML model by way of using the mature relational database systems. |
